Green–Taoの定理
概要
Green–Taoの定理（Green–Tao theorem）とは、任意の正の整数 $k$ について、素数だけからなる $k$ 項の等差数列が存在する（各 $k$ について無限に多く存在する）という定理であり、B. Green と T. Tao が証明した。素数全体の上密度は $0$ なので Szemerédi の定理は直接使えないが、素数を擬似ランダムな「概素数」の集合の中に正の相対密度で置き、Szemerédi の定理を移し替える移転原理によって示された。より強く、素数の中で正の相対上密度をもつ部分集合も任意の長さの等差数列を含み、これから素数の有限色の塗り分けについての van der Waerden 型の主張が従う。
前提知識: 素数, van der Waerdenの定理, Szemerédiの定理, 素数計数関数
素数を等間隔に並べることはどこまでできるだろうか。$3,5,7$ は公差 $2$ の 3 項、$5,11,17,23,29$ は公差 $6$ の 5 項、$7,37,67,97,127,157$ は公差 $30$ の 6 項の等差数列で、どの項も素数である。公差 $210$ の
$$
199,\ 409,\ 619,\ 829,\ 1039,\ 1249,\ 1459,\ 1669,\ 1879,\ 2089
$$
は 10 項すべてが素数である。B. Green と T. Tao は 2004 年、どんな長さ $k$ についても、素数だけからなる $k$ 項の等差数列が存在することを証明した（GT08）。これが Green–Tao の定理（Green–Tao theorem）である。
正の上密度をもつ整数の集合は任意の長さの等差数列を含む（Szemerédiの定理）。しかし素数全体の上密度は $0$ なので、Szemerédi の定理は素数には直接使えない。Green と Tao は、素数を少し大きな「擬似ランダムな」集合の中に正の相対密度で埋め込み、その中で Szemerédi の定理を移し替える（移転原理）ことでこの障害を越えた。
定理の証明は長く、この記事では証明しない。この記事では定理の主張と相対密度の形を述べ、記事の中で次を証明する。素数だけからなる無限の等差数列はないこと（prop-gt-no-infinite）、素数だけからなる $k$ 項の等差数列の公差は $k$ より小さい素数をすべて約数にもち、初項が $k$ より大きければ $k$ 以下の素数もすべて約数にもつこと（prop-gt-difference・cor-gt-first-term）、素数をどう有限色に塗り分けても、ある色が任意の長さの等差数列を含むこと（cor-gt-coloring。相対密度の形から導く）、相対密度の仮定が外せないこと（ex-gt-sparse）。
主張
$k$ 項の等差数列と公差は van der Waerdenの定理 の定義「等差数列と塗り分け」の意味とする（公差は $1$ 以上）。$\mathcal P$ を素数全体の集合、$\pi(N):=\lvert\mathcal P\cap[1,N]\rvert$ を 素数計数関数 とする。
任意の $k\ge1$ について、素数だけからなる $k$ 項の等差数列が存在する。さらに、そのような等差数列は各 $k$ について無限に多くある。
$A\subset\mathcal P$ の 相対上密度 を
$$
\overline d_{\mathcal P}(A):=\limsup_{N\to\infty}\frac{\lvert A\cap[1,N]\rvert}{\pi(N)}
$$
で定める。
$A\subset\mathcal P$ が $\overline d_{\mathcal P}(A)>0$ を満たせば、任意の $k\ge1$ について、$A$ は $k$ 項の等差数列を無限に多く含む。
thm-gt-relative は GT08 Theorem 1.2 であり、この記事では証明しない。Zha23 Theorem 9.1.3（p. 285）は、$k\ge3$ を固定して「$k$ 項の等差数列を含まない $A\subset\mathcal P$ については $\lvert A\cap[1,N]\rvert/\pi(N)\to0$」という形で述べており、これは「$\overline d_{\mathcal P}(A)>0$ なら $A$ は $k$ 項の等差数列を含む」の対偶である。$A=\mathcal P$ とすると $\overline d_{\mathcal P}(\mathcal P)=1$ なので、thm-gt-relative は thm-gt-main を含む。
「任意の長さの等差数列がある」ことと「各 $k$ について $k$ 項の等差数列が無限にある」ことは同じである。実際、$K\ge k$ 項の等差数列 $a,a+d,\dots,a+(K-1)d$ からは、連続する $k$ 項を取り出して $K-k+1$ 個の異なる $k$ 項の等差数列が得られ、$K$ はいくらでも大きくとれる。
次の等差数列はどの項も素数である（各項の素数性は計算で確かめられる）。
$$
\begin{array}{c|c|c}
\text{項数} & \text{初項} & \text{公差}\\ \hline
3 & 3 & 2\\
5 & 5 & 6\\
6 & 7 & 30\\
10 & 199 & 210\\
22 & 11410337850553 & 4609098694200\\
23 & 56211383760397 & 44546738095860
\end{array}
$$
最後の 2 行は計算機の探索で見つかったもので、GT08 の序論（p. 2）は、論文の執筆時点で知られていた最長の素数の等差数列として 23 項のものを挙げている。どの行でも、次の項（たとえば $3+3\cdot2=9$、$199+10\cdot210=2299=11^2\cdot19$）は素数でない。
初等的な性質
無限の等差数列はない
$a\ge1$、$d\ge1$ を整数とする。$a,a+d,a+2d,\dots$ のすべての項が素数になることはない。
$a$ が素数でなければ初項で終わる。$a$ が素数なら、$j=a$ 番目の項 $a+ad=a(1+d)$ は $a$ と $1+d\ge2$ の積なので合成数である。$\square$
したがって thm-gt-main の「任意の有限の長さ」を「無限の長さ」に強めることはできない。これは Szemerédiの定理 でも同じで、正の上密度をもつ集合も無限の等差数列を含むとは限らない（同記事の「例と反例」の表）。
公差の素因数
$k\ge2$ とし、$a,a+d,\dots,a+(k-1)d$（$d\ge1$）がすべて素数で、$a>k$ であるとする。このとき $k$ 以下のすべての素数 $q$ は $d$ を割る。特に $d$ は $k$ 以下の素数の積で割り切れる。
$q\le k$ を素数とし、$q\nmid d$ と仮定する。$d$ は法 $q$ で可逆なので、$j=0,1,\dots,q-1$ に対する $a+jd$ は法 $q$ で互いに異なり、$q$ 個の剰余類をちょうど一回ずつとる。$q\le k$ なので、これらは数列の項であり、その中に $q$ で割り切れる項 $a+jd$ がある。その項は素数なので $a+jd=q$ でなければならないが、$a+jd\ge a>k\ge q$ なので矛盾である。よって $q\mid d$ である。異なる素数がすべて $d$ を割るので、その積も $d$ を割る。$\square$
ex-gt-examples の 10 項の例では $210=2\cdot3\cdot5\cdot7$、22 項・23 項の例でも公差は $2\cdot3\cdot5\cdots19=9699690$ や $2\cdot3\cdots23=223092870$ で割り切れる（計算で確かめられる）。長い素数の等差数列の公差が大きくなる理由の一つがこの命題である。仮定 $a>k$ は外せない：$3,5,7$ は $k=3$、$a=3$ で、公差 $2$ は $3$ で割り切れない。この場合は $q=3$ に対する項がちょうど $3$ に一致している。初項が小さい場合も、次のように完全に分かる。
$k\ge2$ とし、$a,a+d,\dots,a+(k-1)d$（$d\ge1$）がすべて素数であるとする。このとき次が成り立つ。
- $a\ge k$ である。
- $k$ より小さいすべての素数 $q$ は $d$ を割る。
- $k$ が素数で $k\nmid d$ ならば $a=k$ である。
1：$a\le k-1$ とすると、第 $a$ 項（$j=a$ の項）$a+ad=a(1+d)$ は数列に含まれ、$a\ge2$（$a$ は素数）と $1+d\ge2$ の積なので合成数であり、矛盾する。
2：$q< k$ を素数とし、$q\nmid d$ とする。prf-gt-difference と同じく、$j=0,\dots,q-1$ の項のどれかが $q$ で割り切れ、それは素数なので $q$ に等しい。しかし 1 によりその項は $a\ge k>q$ 以上であり、矛盾する。
3：$k\nmid d$ なら、同じ議論で $j=0,\dots,k-1$ の項のどれかが $k$ に等しい。各項は $a\ge k$ 以上なので、それは初項で $a=k$ である。$\square$
たとえば 5 項の $5,11,17,23,29$ は cor-gt-first-term の 3 にあたり、$a=5=k$、公差 $6$ は $5$ で割り切れない。6 項の $7,37,67,97,127,157$ では $a=7>6$ なので、prop-gt-difference により公差 $30$ は $2\cdot3\cdot5$ の倍数でなければならない。
Szemerédi の定理との関係
素数計数関数 の命題「素数の割合の極限」により $\pi(N)/N\to0$ なので、素数全体の上密度は $0$ であり、Szemerédiの定理 の密度の形は素数に使えない。有限の形でも、$[N]$ の中の素数の割合 $\pi(N)/N$ は固定した $\delta>0$ を下回っていく。Zha23 Remark 9.1.2（p. 284）は、Szemerédi の定理の定量的な評価がもっと良ければ素数の密度だけから Green–Tao の定理が従いうることを述べ、3 項の場合には Bloom と Sisask の評価 $N/(\log N)^{1+c}$ によってそれが実現したと紹介している（この記事では証明しない）。3 項の場合そのものは、1939 年に van der Corput が別の方法で示していた（GT08 p. 1）。
密度の代わりに逆数和を使う予想もある。Erdős は、$\sum_{a\in A}1/a=\infty$ を満たす正の整数の集合 $A$ は任意の長さの等差数列を含むと予想した（Zha23 Conjecture 0.2.5、p. 7。同書によれば 3 項の場合は Bloom と Sisask の評価から従うが、4 項以上では未解決である）。正の上密度をもつ集合は逆数和が発散するので、この予想は Szemerédi の定理を強めたものであり、素数については 素数の逆数和の発散 により逆数和が発散するので、予想が正しければ Green–Tao の定理が従う。Zha23 は、この予想が素数を動機としていたことを述べている（同 p. 7）。
相対密度の形 thm-gt-relative からは、van der Waerdenの定理 の素数版がすぐに得られる。
$r\ge1$ とし、素数全体を $r$ 色に塗り分ける。このとき、ある色の素数の集合は、任意の長さの等差数列を含む。
色 $i$ の素数の集合を $A_i$ とする。各 $N$ について $\sum_{i=1}^r\lvert A_i\cap[1,N]\rvert=\pi(N)$ なので、$\lvert A_i\cap[1,N]\rvert\ge\pi(N)/r$ となる $i$ がある。$N=1,2,3,\dots$ のそれぞれにそのような $i$ を 1 つ選ぶと、$i$ は有限個の値しかとらないので、ある $i_0$ が無限に多くの $N$ で選ばれる。よって $\overline d_{\mathcal P}(A_{i_0})\ge1/r>0$ であり、thm-gt-relative により $A_{i_0}$ は任意の長さの等差数列を含む。$\square$
同じ議論は van der Waerdenの定理 の注意「出典と van der Waerden の定理との関係」で、Szemerédi の定理から van der Waerden の定理を導くのに使われている。たとえば素数を $4$ で割った余り（$1$、$2$、$3$）で 3 色に塗ると、cor-gt-coloring から、$4$ で割って $1$ 余る素数か $3$ 余る素数のどちらかは任意の長さの等差数列を含む（$2$ の色は 1 元しかないので長さ $2$ 以上の等差数列を含まない）。どちらの色かはこの議論からは決まらないが、色が 1 つに決まらないことは塗り分けの論法の特徴である。
$q_1:=2$ とし、$q_{j+1}$ を $q_j^2$ より大きい最小の素数とする（素数は無限にあるので定まる）。$Q:=\{q_1,q_2,\dots\}$ は素数からなる無限集合だが、3 項の等差数列を含まない。実際 $a< b< c$ を $Q$ の元で $a+c=2b$ とすると、$c=q_l$ と書けば $b\le q_{l-1}$ なので $2b\le2q_{l-1}\le q_{l-1}^2< q_l=c< a+c$ となり矛盾する。また $q_j\ge2^{2^{j-1}}$（帰納法）より $\lvert Q\cap[1,N]\rvert\le\log_2\log_2N+1$ であり、素数計数関数 の命題「対数による下からの評価」$\pi(N)\ge\frac12\log_2N$ と合わせて $\overline d_{\mathcal P}(Q)=0$ である。これは thm-gt-relative の仮定「$\overline d_{\mathcal P}(A)>0$」を外すと、3 項の等差数列さえ含まない無限集合があることを示す。
証明の考え方
GT08 の要旨は、証明の材料を次の 3 つにまとめている。第一は Szemerédi の定理そのもの。第二は論文の主要な新しい道具である移転原理で、十分に擬似ランダムな集合（または測度）の中で正の相対密度をもつ部分集合は、任意の長さの等差数列を含むことを Szemerédi の定理から導く。第三は Goldston と Yıldırım の結果で、これを使うと素数（の大きな部分）を「概素数」（小さい素因数をもたない数）に集中した擬似ランダムな測度の中に、正の相対密度で置くことができる。Zha23 §9.1（pp. 283–285）は、素数を概素数の中に正の割合で含まれる集合とみなし、概素数がある種のパターンの個数について擬似ランダムに振る舞うことを使う、という筋を説明している。
素数は小さい素数を法として偏っている。$2$ より大きい素数はすべて奇数で、$3$ より大きい素数は $3$ で割り切れない。このため素数は、各 $n$ を確率 $1/\log n$ で独立に選んだランダムな集合とは違って見える。これを補正するのが $W$ トリックである（Zha23 Remark 9.1.4、p. 285）。$w$ を $N$ とともにゆっくり増える数とし、$W:=\prod_{p\le w}p$ とおいて、集合 $\{n:nW+1\text{ は素数}\}$ を考える。$n_0,n_0+e,\dots,n_0+(k-1)e$ がこの集合の $k$ 項の等差数列なら、$n_0W+1,(n_0+e)W+1,\dots$ は公差 $eW$ の素数の $k$ 項の等差数列なので、この集合の中で等差数列を見つければよい。この集合は固定した小さい素数を法とする偏りをもたないので、相対版の Szemerédi の定理を当てはめやすくなる。prop-gt-difference が示すとおり長い素数の等差数列の公差は小さい素数の積の倍数になるので、公差 $eW$ の形で探すのは自然である。
定量的な結果
素数定理による素朴な見積もりでは、各項が $N$ 以下の素数からなる $k$ 項の等差数列はおよそ $N^2/(\log N)^k$ の定数倍あると期待され、Hardy と Littlewood の予想からは個数が $C_kN^2/(\log N)^k$（$C_k>0$ は明示的な定数）に漸近することが従う（GT08 p. 1）。GT08 自身は下からの評価 $(\gamma(k)+o(1))N^2/(\log N)^k$（$\gamma(k)>0$ は非常に小さい定数）を得ている（同 p. 1）。その後 Green と Tao は、Green–Tao–Ziegler による Gowers ノルムの逆定理と合わせて、この個数の漸近式を得た（Zha23 の第 9 章の Further Reading、p. 305。この記事では証明しない）。
例と反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 等差数列の長さが有限 | 初項 $a$、公差 $d$ の無限等差数列の第 $a$ 項 $a(1+d)$ | 素数だけからなる等差数列がある |
| thm-gt-relative の相対上密度が正 | ex-gt-sparse の集合 $Q$ | 3 項の等差数列を含む |
| prop-gt-difference の $a>k$ | $3,5,7$（$k=3$、$d=2$） | $k$ 以下の素数はすべて公差を割る |
1 行目は prop-gt-no-infinite、2 行目は ex-gt-sparse、3 行目は prop-gt-difference の後の説明による。3 行目では $q=3$ に対する項が $3$ 自身で、証明の「その項は $q$ より大きい」という段だけが成り立たなくなっている。
関連項目
- 前提: 素数, van der Waerdenの定理, Szemerédiの定理, 素数計数関数
- 比較: Dirichletの算術級数定理, Ramsey理論
- 関連: 素数定理, Legendre予想
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
