2017-09-24

グリーン・タオ論文の§1, 4を読む

それでは記念碑的論文

B. Green, T. Tao, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics. 167 (2), (2008), 481–547.

を読んでいきましょう。

§1から§4まではイントロ的内容で本格的な証明は§5から始まります。なので、§1-§4については掻い摘んで記述します。

§1 Introduction には何はともあれ、我々の主結果が書かれています*1。

定理１ (Theorem 1.1) 素数達は全ての $k$ に対して長さ $k$ の等差数列を無数に含む。

彼らは"予想"と表現していますが、誰が予想したかということはあまりわかっていないようです*2。

この直後に、実際にはもう少し強い形の定理を示すことができると続きます。それを述べる前にSzemerédiの定理の無限版(または素朴版)についてこの場で解説します。

van der Waerdenの定理

van der Waerdenの定理 (1927) 任意の正の整数 $k, m$ に対して、或る正の整数 $N_{\text{vdW}}(k, m)$ が存在して次が成り立つ: $N\geq N_{\text{vdW}}(k, m)$ なる任意の整数 $N$ に対して、 $1$ から $N$ までの整数をどのように $m$ 色に塗り分けたとしても、必ず同じ色で塗られた長さ $k$ の等差数列が存在する。

にはもっと素朴に表現したヴァージョンがあり、

Baudet予想 正の整数全体を幾つかのクラスに分ける。このとき、少なくとも一つのクラスは任意の長さの等差数列を含む。

と同値であることを

integers.hatenablog.com

で紹介しました。実は、Szemerédiの定理(こちらは有限版)

Szemerédiの定理 (Proposition 2.1) $k$ を任意の正整数とし、 $\delta$ を $0 < \delta \leq 1$ を満たす任意の実数とする。このとき、或る正の整数 $N_{\text{SZ}}(k, \delta )$ が存在して次が成り立つ:
$N \geq N_{\text{SZ}}(k, \delta)$ なる任意の整数 $N$ に対して、 $\{1, 2, \dots, N\}$ の部分集合 $A$ であって

$\displaystyle\frac{\#A}{N} \geq \delta$

を満たすものは、必ず長さ $k$ の等差数列を含む。

にも、もっと素朴な表現による同値な言い換え(無限版)が存在します。

定義１ $\mathbb{N}$ を正の整数全体のなす集合とし、 $A$ を $\mathbb{N}$ の部分集合とする。このとき、 $A$ の上漸近密度 $\overline{d}(A)$ を

$\displaystyle \overline{d}(A):=\limsup_{N \to \infty}\frac{\#\left\{A\cap \{1, 2, \dots, N\}\right\}}{N}$

と定義する。

Szemerédiの定理 (無限版) $A$ を $\mathbb{N}$ の部分集合とする。 $A$ の上漸近密度が正であれば、 $A$ は任意の長さの等差数列を含む。

素数全体集合の上漸近密度は $0$ なので*3、Szemerédiの定理からはGreen-Taoの定理が出ないことを再確認できます。それでは、同値であることの証明を確認しましょう。集合の記法 $[N]:=\{1, 2, \dots, N\}$ と $A+a := \{x+a \mid x \in A\}$ を用います。

有限版 $\Longrightarrow$ 無限版の証明

$\overline{d}(A)=\delta > 0$ とする。このとき、正整数 $k$ に対して或る $N \geq N_{\text{SZ}}(k, \delta/2)$ が存在して

$\displaystyle \#\left\{A\cap [N]\right\} \geq \frac{1}{2}\delta N$

が成り立つので、有限版Szemerédiの定理より $A\cap [N]$ は長さ $k$ の等差数列を含む。つまり、 $A$ は長さ $k$ の等差数列を含む。 $k$ は任意なので無限版Szemerédiの定理が示された。 Q.E.D.

無限版 $\Longrightarrow$ 有限版の証明

背理法で証明するために有限版の主張を否定する。このとき、

正整数 $k$
正の数 $\delta$
狭義単調増大正整数列 $N_1 < N_2 < N_3 < N_4 < \cdots$
有限集合 $A_i \subset [N_i] \ (i \geq 1)$ s.t. $\#A_i \geq \delta N_i$ かつ $A_i$ は長さ $k$ の等差数列を含まない

が存在する。このデータに対して、 $N_{n_{i+1}} \geq 3N_{n_i}$ が成り立つような番号の列

$n_1 < n_2 < n_3 < n_4 < \cdots$

をとる。 $\displaystyle d_i := \sum_{j=1}^{i-1}N_{n_j} \ (d_1:=0)$ とし、集合 $A$ を

$\displaystyle A:= \bigsqcup_{i=1}^{\infty}\left(A_{n_i}+d_i\right)$

と定義する( $d_i$ の定義からちゃんと非交差和になっている)。すると、 $\overline{d}(A) \geq \delta$ である。理由: 各 $i \geq 1$ に対して

$\displaystyle \frac{\#\left\{A\cap[d_{i+1}]\right\}}{d_{i+1}} = \frac{\#A_{n_1}+\#A_{n_2}+\cdots +\#A_{n_i}}{d_{i+1}} \geq \frac{\delta N_{n_1}+\delta N_{n_2}+\cdots +\delta N_{n_i}}{d_{i+1}} = \delta$

であることからわかる。従って、 $A$ の上漸近密度は正なので、無限版Szemerédiの定理より $A$ は任意の長さの等差数列を含む。特に、長さ $3k$ の等差数列 $a+id; 0 \leq i < 3k$ を含む。ここで、

$d_l \leq a+(3k-1)d < d_{l+1}$

であるような $l$ をとる(明らかに $l \geq 2$ )。すると、 $a+2kd \leq d_l$ が成り立つ。理由: もし $a+2kd > d_l$ ならば、 $A$ の定義によって、 $A_{n_l}+d_l$ は

$a+2kd, a+2kd+d, \dots, a+2kd+(k-1)d=a+(3k-1)d$

を含むことになる。これは $A_{n_l}$ が長さ $k$ の等差数列を含まないことに反する。一方、 $\{n_i\}$ の取り方から $d_l > 3d_{l-1}$ なので

$\displaystyle a+kd \geq \frac{1}{3}\left(a+(3k-1)d\right)\geq \frac{1}{3}d_l > d_{l-1}$

である。これは、 $A$ の定義によって、 $A_{n_{l-1}}+d_{l-1}$ が

$a+kd, a+kd+d, \dots, a+kd+kd=a+2kd$

を含むことを意味し、 $A_{n_{l-1}}$ が長さ $k$ の等差数列を含まないことに矛盾する。 Q.E.D.

素数版Szemerédiの定理

さて、予告していたGreen-Taoの定理は(無限版)Szemerédiの定理の素数版です。

定義２ $A$ を素数のみからなる任意の集合とする。このとき、 $A$ の相対上漸近密度 $\overline{d}_{\pi}(A)$ を

$\displaystyle \overline{d}_{\pi}(A):=\limsup_{N \to \infty}\frac{\#\left\{A\cap \{1, 2, \dots, N\}\right\}}{\pi(N)}$

と定義する。ここで、 $\pi(N)$ は $N$ 以下の素数の個数。

素数版Szemerédiの定理 (Theorem 1.2) $A$ を素数のみからなる集合とする。 $A$ の相対上漸近密度が正であれば、 $A$ は任意の長さの等差数列を含む。

もちろん論文に書いてあるのですが、知名度の観点ではThm 1.1に比べてあまり知られていないような気がします*4。例えば、次のようなことが言えます：

系 (算術級数版Green-Taoの定理) $a, b$ を互いに素な正整数とする。このとき、正整数 $n$ を用いて $an+b$ という形で書ける素数のみから構成される任意の長さの等差数列が存在する。

等間隔に並ぶ整数達の中に等間隔に並ぶ素数達が存在する！！

証明. $an+b$ の形をした素数全体のなす集合の相対上漸近密度は算術級数の素数定理によって、 $1/\varphi(a) > 0$ である。従って、素数版Szemerédiの定理によって主張が従う。 Q.E.D.

等間隔に並ぶ素数を追い求めて〜グリーン・タオの定理〜 - INTEGERSにあげた数値例では一桁目が一致しているものが殆どですが、例えば「一桁目が $1$ であるような素数のみから構成される任意の長さの等差数列が存在する」ことも言えるわけです。

また、Fermatのクリスマス定理によって「二つの平方数の和として表わすことができるような素数のみから構成される任意の長さの等差数列が存在する」ことも言えます。

論文で使われる記号の解説

ここに、§4 Notation に書かれている内容を含めて、Green-Tao論文で使われる記号をまとめておきます。Tao(2006)の記号を前提として、違いに注意してください。

整数 $N$ に対して $\mathbb{Z}_N:=\mathbb{Z}/N\mathbb{Z}$ 、非負整数全体集合を $\mathbb{R}^+$ と表すのはTaoの論文と同じ。 $\mathbb{Z}^+$ は正の整数全体集合。
漸近挙動に関する記号はTaoの論文と同じく、指定がなければ $N \to \infty$ における挙動を表す。ただし、Vinogradov記号は用いない代わりにスモールオー記号 $o(X)$ を用いる。パラメータ依存を添字で表示するのも同じ*5。
期待値の記号は添字で表現していた部分を縦棒を使って関数と同じ大きさで表す。つまり、 $\mathbb{E}_A(f)$ や $\mathbb{E}_{P(x)}(f(x))$ としていたのを $\left.\mathbb{E}(f\right|A)=\left.\mathbb{E}(f(x)\right| x \in A)$ や $\left.\mathbb{E}(f(x)\right|P(x))$ のように表す。文脈上明らかな場合( $A=\mathbb{Z}_N$ の場合など)は $\mathbb{E}(f)$ と書くこともある。記述が多変数になっても定義は同様である。また、積分記号とシフト作用素の記号は用いない。
特性関数の記号表記 $\mathbf{1}_{\Omega}$ や $\mathbf{1}_{P(x)}$ はTaoの論文と同じ。
§5以降では、整数 $k \geq 3$ 、素数 $N$ という記号を固定して話を進める。 $N$ は $k$ に依存して十分大きいものとする*6。
(重要) §5以降、パラメータに関する $k$ 依存は漸近挙動の記号などにおいて基本的に明示しない。

$\mathbb{Z}_N$ 上定義される関数については、Taoの論文とは違って、Green-Taoの論文では実数値関数のみを扱います。

定義３ (Definition 4.1) $1 \leq q < \infty$ と関数 $f \colon \mathbb{Z}_N \to \mathbb{R}$ に対して $L^q$ -ノルム $\left\|f\right\|_{L^q}$ を

$\displaystyle \left\|f\right\|_{L^q}:=\mathbb{E}(\left|f\right|^q)^{\frac{1}{q}}$

と定義し、 $L^{\infty}$ -ノルム $\left\|f\right\|_{L^q}$ を

$\left\|f\right\|_{L^{\infty}} := \sup_{x \in \mathbb{Z}_N}\left|f(x)\right|$

と定義する。また、 $1 \leq q \leq \infty$ に対して、関数 $f \colon \mathbb{Z}_N \to \mathbb{R}$ 全体のなす $\mathbb{R}$ -ベクトル空間*7に $L^q$ -ノルムを入れたBanach空間を $L^q(\mathbb{Z}_N)$ と表す。

参考記事：ミンコフスキーの不等式とその証明 | 高校数学の美しい物語

最後に§4で導入されている一様被覆という言葉を定義しておきましょう。

定義４ 空でない有限集合 $A, B$ と写像 $\Phi \colon A \to B$ に対して、 $\Phi$ が $B$ の $A$ による一様被覆であるとは、 $\Phi$ が全射で、任意の $b \in B$ に対して

$\displaystyle \#\Phi^{-1}(b) = \frac{\#A}{\#B}$

が成り立つときにいう。

補題 $\Phi$ が $B$ の $A$ による一様被覆であり、 $f \colon B \to \mathbb{R}$ を関数とする。このとき、

$\displaystyle \left.\mathbb{E}(f(\Phi(a))\right| a \in A) = \left.\mathbb{E}(f(b)\right|b \in B)$

が成り立つ。

証明. これは定義から

$\displaystyle \frac{1}{\#A}\sum_{a \in A}f(\Phi(a)) = \frac{1}{\#A}\frac{\#A}{\#B}\sum_{b \in B}f(b) = \frac{1}{\#B}\sum_{b \in B}f(b)$

と計算できる。 Q.E.D.

*1:題名にも書かれていますが。単に存在するとするのと無数に存在するとするのが同値であることは既にみています。等間隔に並ぶ素数を追い求めて〜グリーン・タオの定理〜 - INTEGERSの脚注。cf. 算術級数定理についての注意 - INTEGERS

*2:1770年代には知られていた？(LagrandeとWaringの研究あり) "classical" or "folklore" conjecture とのこと。

*3:素数密度零補題 - INTEGERS

*4:また、原論文では証明をThm 1.1の場合に記述し、Thm 1.2はヒントを書いて同様に示せるという立場を取っています。その通りなのですが、この企画ではThm 1.2の証明をしっかり記述します。

*5:例えば、 $f(N)=o_{k, \delta}(1)$ は $\varepsilon > 0$ に対して $k, \delta$ に依存する番号 $N_{k, \delta}(\varepsilon)$ が存在して、 $N \geq N_{k, \delta}(\varepsilon)$ ならば $\left|f(N)\right| < \varepsilon$ が成り立つことを意味する。

*6:すなわち、主張に明言されていなくても、十分大きい $N$ に対してのみ成立するものを扱うケースがあります。

*7: $\mathrm{Map}(\mathbb{Z}_N, \mathbb{R})$ と表します。各定理の主張において原論文で「 $f \in L^1(\mathbb{Z}_N)$ に対して」や「 $f \in L^{\infty}(\mathbb{Z}_N)$ に対して」と書かれている文は単に「任意の関数 $f \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{R})$ に対して」の意味で使われていると思われる箇所があります。原論文でそれらが使われている場合はそのまま使用していますが、独自に解説を付け加えている部分では記号 $\mathrm{Map}(\mathbb{Z}_N, \mathbb{R})$ を使用しています。