2017-09-12

等間隔に並ぶ素数を追い求めて〜グリーン・タオの定理〜

等間隔に並ぶ素数を追い求めて

素数のもつ秩序。それは人類に幾度となく驚きと喜びを与えてくれました。そして、これからも与え続けてくれることでしょう。

素数の秩序に関する人類の最初の大きな勝利は素数定理

$\displaystyle \pi(x) \sim \frac{x}{\log x}, \quad x \to \infty$

を発見し、証明したことだと思います。

素数の分布は高度に非自明で、一見すると何の法則性も見出せないように思えます。にも関わらず、このようにシンプルな漸近挙動を示すのは驚きです。

素数定理についての文献は日本語を含めて相当数存在しますし、このブログでもまとめています*1。

素数定理が証明されてから100年のときを経て、人類は次の大勝利を収めました。

Green-Taoの定理です*2。

素数は疎らに分布しているように見えますが、

$3, \ 5, \ 7$

は等間隔に並んでいます。等間隔に並んでいる素数は他にもあるでしょうか？

等間隔に並ぶ素数に興味があるので、等差数列の初項および公差は指定しない代わりにその項数(長さと呼ぶ)に着目します。上記例は長さ $3$ です。

頑張って探すと等間隔に並ぶ素数たちが見つかります。幾つかの例を眺めてみましょう：

長さ $5$

$5, \ 11, \ 17, \ 23, \ 29$

長さ $6$

$7, \ 37, \ 67, \ 97, \ 127, \ 157$

長さ $7$

$7, \ 157, \ 307, \ 457, \ 607, \ 757, \ 907$

長さ $10$

$199, \ 409, \ 619, \ 829, \ 1039, \ 1249, \ 1459, \ 1669, \ 1879, \ 2089$

素数は大きくなればなるほどどんどん出現しにくくなります*3。等間隔に並ぶことは殆どなくなっていくのではないかという直感があります。

続いて、コンピュータを用いた記録を見てみましょう。直後に紹介するGreen-Taoの定理が証明された当時の記録はMarkus Frind, Paul Underwood, Paul Joblingによって2004年に発見された長さ $23$ の素数からなる等差数列です：

$\begin{align}&56211383760397, \ 100758121856257, \ 145304859952117, \ 189851598047977, \ \\ &234398336143837, \ 278945074239697, \ 323491812335557, \ 368038550431417, \ \\ &412585288527277, \ 457132026623137, \ 501678764718997, \ 546225502814857, \ \\ &590772240910717, \ 635318979006577, \ 679865717102437, \ 724412455198297, \ \\ &768959193294157, \ 813505931390017, \ 858052669485877, \ 902599407581737, \ \\ &947146145677597, \ 991692883773457, \ 1036239621869317\end{align}$

長さの世界記録は $26$ で、2010年4月12日にBenoît Perichonによって次の素数からなる等差数列が発見されました：

$\begin{align}&43142746595714191, \ 48425980631694091, \ 53709214667673991, \ \\ &58992448703653891, \ 64275682739633791, \ 69558916775613691, \ \\ &74842150811593591, \ 80125384847573491, \ 85408618883553391, \ \\ &90691852919533291, \ 95975086955513191, \ 101258320991493091, \ \\ &106541555027472991, \ 111824789063452891, \ 117108023099432791, \ \\ &122391257135412691, \ 127674491171392591, \ 132957725207372491, \ \\ &138240959243352391, \ 143524193279332291, \ 148807427315312191, \ \\ &154090661351292091, \ 159373895387271991, \ 164657129423251891, \ \\ &169940363459231791, \ 175223597495211691\end{align}$

長さ $26$ ではもっと大きいものが見つかっており、2015年にBryan Littleによって次の素数からなる等差数列が発見されています：

$\begin{align}&161004359399459161, \ 171649260008631991, \ 182294160617804821, \ \\ &192939061226977651, \ 203583961836150481, \ 214228862445323311, \ \\ &224873763054496141, \ 235518663663668971, \ 246163564272841801, \ \\ &256808464882014631, \ 267453365491187461, \ 278098266100360291, \ \\ &288743166709533121, \ 299388067318705951, \ 310032967927878781, \ \\ &320677868537051611, \ 331322769146224441, \ 341967669755397271, \ \\ &352612570364570101, \ 363257470973742931, \ 373902371582915761, \ \\ &384547272192088591, \ 395192172801261421, \ 405837073410434251, \ \\ &416481974019607081, \ 427126874628779911\end{align}$

最高の眺めですね。コンピュータを使っても長さ $27$ 以上の素数からなる等差数列は現状見つかっていません。

にも関わらず、にも関わらず

Ben GreenとTerence Taoは次の定理を証明しました(2004年証明、2008年出版)：

定理 (Green-Tao)
素数のみから構成される任意の長さの等差数列が存在する。

これは人類の至宝です。

コンピュータを使っても長さ $26$ の素数からなる等差数列を見つけ出すことは至難の技なのです。

ところが、Green-Taoの定理は「どんな長さであっても等間隔に並ぶ素数達が存在する」と言っています。

世界中の誰も見たことがないし、生きている間に見ることはできないだろうけれど、それでも１億個の、１兆個の、いや、例えいくつであっても、等間隔に並んだ素数達が必ず存在するというのです。

これが人類の知能・数学の力です。

あれだけ規則性がないように見える素数達が、あれだけ複雑に見える素数達が、まさかここまで美しい秩序をもっていたなんて。。。

それを私達が知ることができるなんて。。。。

これ以上言葉にしようとしても出てくるのは涙だけなので書けません。

ただ、私が生きているうちにこの秩序が成り立つことを証明してくださったGreenとTao、および彼らが証明に至ることを可能にする先駆的な仕事をした研究者達には感謝の気持ちしかありません。特別に敬意を表したいと思います。

特に関係する数学者達

Pierre Joseph Henry Baudet (1891/1/22 – 1921/12/25)

Bartel Leendert van der Waerden (1903/2/2 – 1996/1/12)

Pál Turán (1910/8/18 – 1976/9/26) Erdősと28の共著論文を書いている。

Paul Erdős (1913/3/26 – 1996/9/20) Wolf賞受賞(1983/4)

Klaus Friedrich Roth (1925/10/29 – 2015/11/10) Fields賞受賞(1958)

Hillel Furstenberg*4 (1935/9/29 – ) Wolf賞受賞(2006/7)

Endre Szemerédi (1940/8/21 – ) Abel賞受賞(2012)

Daniel Goldston (1954/1/4 – ) Cole賞受賞(2014)

Cem Yalçın Yıldırım (1961/7/4 – ) Cole賞受賞(2014)

Timothy Gowers (1963/11/20 – ) 国際数学五輪金メダル(1981)。Fields賞受賞(1998)

Terence Tao (1975/7/17 – ) 国際数学五輪金メダル(1988)。Fields賞受賞(2006年)

Ben Green (1977/2/27 – ) Gowersの弟子*5。

しかし、です。

素数が確かにこの美しい秩序を持つ

と確信していいのは証明を理解した者のみです。特に、この定理は主張を理解することは簡単ですし、有用性も低く感じられるため、証明にこそ意義があります。というわけで、証明の解説を行います。

Heuristicな議論

証明の前にGreen-Taoの定理の主張が正しいであろうと感じることのできるheuristicな議論があるのでそれを見てみましょう*6。

$N$ 以下の正整数で構成される長さ $k$ の等差数列は初項を $a_1$ , 公差を $d > 0$ とすると最大の項は

$a_k=a_1+(k-1)d$

なので、「初項が $a_1$ であるような $N$ 以下の正整数で構成される長さ $k$ の等差数列」の公差 $d$ としては

$\displaystyle 1 \leq d \leq \left[ \frac{N-a_1}{k-1}\right]$

があり得えます(1対1対応)。従って、「 $N$ 以下の正整数で構成される長さ $k$ の等差数列」の個数は $N$ が $k$ よりも十分大きければ

$\displaystyle \sum_{n=1}^N\left[\frac{N-n}{k-1}\right] \geq \sum_{n=1}^N\left(\frac{N-n}{k-1}-1\right)=\frac{N(N-1)}{2(k-1)}-N\geq \frac{N^2}{3(k-1)}$

と下から評価できます。素数定理の観点から $N$ 以下の正整数が素数である確率は $1/\log N$ であると考えれば、与えられた「 $N$ 以下の正整数で構成される長さ $k$ の等差数列」の全て項が素数である確率は $1/\log^kN$ となります。よって、「 $N$ 以下の素数で構成される長さ $k$ の等差数列」の個数は

$\displaystyle O_k\left( \frac{N^2}{\log^kN} \right)$

だけ存在し、 $N \to \infty$ とすれば素数のみからなる長さ $k$ の等差数列がいくらでも多く存在するだろうということがわかりました。

つまり、ある意味では、Green-Taoの定理が成立することは驚くことではないということになります*7。

素数からなる長さ $3$ の等差数列が無数に存在することはvan der Corputによって解析的整数論的な手法により1939年に証明されていました。Green-Taoの定理から、各 $k$ に対して素数からなる長さ $k$ の等差数列が無数に存在することは簡単に従います*8。

van der Waerden から Szemerédi、そして Green-Tao へ

Green-Taoの定理の証明はいきなり素数に関する解析を行って証明されるわけではありません。まずは等差数列に関する一般的定理*9を証明することから始まります。

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$ の等差数列が存在する。

van der Waerdenの定理の証明は既に解説しています：
integers.hatenablog.com

この定理は確かに与えられた長さの等差数列の存在をいう定理ですが、ここからGreen-Taoの定理を導出することはできません。

例えば、 $N\geq N_{\text{vdW}}(k, 2)$ なる $N$ をとって、 $1$ から $N$ を

素数ならば赤色
素数でなければ青色

というルールで塗り分けたとしましょう。このとき、van der Waerdenの定理によって同じ色で塗られた長さ $k$ の等差数列の存在が保証されますが、色を指定することはできません。

青色の方には $2$ 以外の偶数がいるのでいくらでも等差数列を作ることができます。従って、色を指定できない以上、赤色である素数の方で等差数列が出来ることをvan der Waerdenの定理のみから保証することはできません。

Szemerédiの定理

そうすると、色の指定が出来たらいいなあという思いが湧いてきますが、それを実現するのがSzemerédiの定理です：

Szemerédiの定理 (1975) $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$ の等差数列を含む。

これは数学の歴史における一つの大結果です。

まず、van der Waerdenの定理を包含する定理であることを確認しましょう。実際、Szemerédiの定理が正しいと仮定すると

$N_{\text{vdW}}(k, m) := N_{\text{SZ}}(k, 1/m)$

とできることがわかります。というのも、 $N \geq N_{\text{SZ}}(k, 1/m)$ なる整数 $N$ に対して $1, \dots, N$ を $m$ 色で塗り分けた際、鳩ノ巣原理によって或る色が存在して、その色で塗られた数達の $1, \dots, N$ における個数の割合は $1/m$ 以上になります。従って、Szemerédiの定理によって同色の長さ $k$ の等差数列が存在することがわかります。

van der Waerdenの定理では色の指定をすることが出来ませんでしたが、Szemerédiの定理は $N$ が十分大きいとき、考察中の集合の個数の割合が $\delta$ 以上でありさえすれば必ず所望の長さの等差数列が存在するといっているのです。

Szemerédiの定理は強力な定理ですが、Green-Taoの定理を導くことはできません。というのも、素数密度零補題より

$\displaystyle \lim_{N \to \infty}\frac{\pi(N)}{N} = 0$

なので、 $N_{\text{SZ}}(k, \delta)$ が大きすぎると密度 $\delta$ を保証することができないからです。素数が自然数全体の中に占める割合が $0$ であるということがSzemerédiの定理をもってしても到達できない理由なのです。

van der WaerdenからSzemerédiの間に48年の期間が空いていますが、この間に行われた関連する研究は膨大な量にのぼります。

一つの先駆的な仕事がErdős-Turánの仕事です：

integers.hatenablog.com

Szemerédiの定理の $k=1, 2$ の場合は自明ですが、 $k=3$ の場合が上の記事で紹介したErdős-Turánの予想に他なりません。この予想はRothによって解決されました：

K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 245−252.

integers.hatenablog.com

Erdős-Turánの予想は多数の別証明が与えられましたが、Erdős-Turánの予想の拡張*10となるSzemerédiの定理の $k=4$ の場合をSzemerédiが解決しています：

E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hunger. 20 (1969), 89−104.

Szemerédiの定理の解決

その後 $k=4$ の場合も幾つかの別証明が得られていますが、Szemerédiは1975年に彼の名前を世に轟かせる大定理を証明するに至ったのです：

E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith. 27 (1975), 299−345.

彼の証明はSzemerédi正則化補題と呼ばれる非常に応用性の高いグラフ理論的ツールとvan der Waerdenの定理を用いた組合せ論的な手法です。Szemerédiの定理は幾つかの別証明が得られており、

1977年のFurstenbergによるエルゴード理論による証明：

H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204−256.

2001年のGowersによる組合せ論＋Fourier解析による証明：

T. Gowers, A new proof of Szemerédi's theorem, GAFA 11 (2001), 465−588.

　
そして、

2006年のTaoによるFurstenbergのエルゴード理論的証明を基にした有限演算による定量的かつ初等的証明：

T. Tao, A quantitative ergodic theory proof of Szemerédi’s theorem, The electronic Journal of Combinatorics 13, (2006), 1−49.

などがあります*11。

Taoによればこれらは次のような共通する証明の構造をもっています：

或る $A$ という対象がある。
$A$ には或るランダム性と構造という概念を定義することができる。
$A$ を(構造化部分)+(誤差項)に分ける構造定理を示す。誤差項はランダムな部分。
誤差項を取り除く一般化von Neumann定理及び構造化部分に関する構造化回帰定理を証明する。

Taoの別証明はそれまでに得られた別証明のテクニックを流用しつつ*12、上の構造を見通しよく初等的に組み立てたものになっていますが、そこまで洗練することによって次のステップに進むことができるようになりました。

ちなみに、複数の異なるアプローチによる別証明があり、多数の分野の数学が結びつくことから、TaoはSzemerédiの定理のことをロゼッタストーンと呼んでいたそうです。

そしてGreen−Taoの定理へ

Szemerédiの定理のままではGreen-Taoの定理を導くことは出来なかったわけですが、GreenとTaoは論文

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

において、Tao(2006)のテクニック*13に基づいてSzemerédiの定理の変形・拡張版を証明しています*14。そうして、変形・拡張版を用いることによって素数に関する未解決問題を陥落させることができたという流れだったのです(この適用の部分でGoldston-Yıldırım等の解析的整数論の研究成果を使う必要があります)。

ヒント的なコメントをしておくと、密度が零であっても十分にランダム(擬ランダムと呼んでいる)な集合であれば等差数列を保証できるということが彼らの発見です(ランダムさが構造を生み出す！)。そして、素数の集合が擬ランダムであることを証明します*15。

ちなみに、変形・拡張版の証明はSzemerédiの定理をベースとしてSzemerédiの定理の証明と同様の手法でより効力を強めるという感じの証明なので、Szemerédiの定理を前提知識として使います。

というわけで、以下の二つの論文

T. Tao, A quantitative ergodic theory proof of Szemerédi’s theorem, The electronic Journal of Combinatorics 13, (2006), 1–49.

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

を読むことによってGreen−Taoの定理の証明を理解することができることがわかりました。

それでは、次の記事から等間隔に並ぶ素数を追い求めた旅を始めましょう*16。

未解決問題

最後に未だに解かれていない難問を紹介してこの記事を終えようと思います。

Erdős-Turán予想 正整数列 $\{a_n\}_{n=1}^{\infty}$ ( $a_1 < a_2 < \cdots$ )が条件

$\displaystyle \sum_{n=1}^{\infty}\frac{1}{a_n} = \infty$

を満たせば、この数列は任意の長さの等差数列を含む。

素数列の場合は逆数和が発散するため*17、Erdős-Turán予想はGreen-Taoの定理よりも強い予想であることがわかります。

ちなみに、この予想が1936年の論文でなされたとする文献もあるのですが、そこには書かれていません。

Erdős conjecture on arithmetic progressions - Wikipedia

によれば1976年のErdősの"To the memory of my lifelong friend and collaborator Paul Turán"という講演でこの予想に3000ドルの懸賞金が懸けられたようです。また、今は5000ドルだとも書かれています。

時代が次の天才の出現を求めています。

*1:以下の記事を参照してください： integers.hatenablog.com integers.hatenablog.com

*2:「素数の秩序」というテーマに限ったからといって素数定理とGreen-Taoの定理のみが人類の勝利というわけではないですが、私の個人的見解としてご了承ください。

*3:後述の素数密度零補題。

*4:彼は学部生時代に美しい素数の無限性証明を発見しています。 integers.hatenablog.com

*5:Cole賞、Wolf賞、Abel賞、Fields賞ほどは知名度はないかもしれませんが、Greenはクレイ研究賞、サレム賞、SASTRAラマヌジャン賞、ヨーロッパ数学会賞、シルヴェスター・メダルなど多数の受賞歴があります。

*6:ここの議論は小木曽先生の記事混沌の中の秩序-素数列をめぐってを参考にしました。

*7:とは言っても当然厳密な証明ではなく、素数の確率解釈から予期されることが実際に成立しているということは驚くべきことでもあります。

*8:与えられた素数からなる等差数列の長さを無限には延長できません。例えば $199, 409, 619, 829, 1039, 1249, 1459, 1669$ と長さ $8$ の等差数列を見つけたとき、更に $1879$ 、 $2089$ と伸びますが、永遠に伸びる訳ではなく、次の $2299$ は素数ではありません。素数のみからなる長さ $k$ の等差数列が有限個与えられたとしましょう。これらの等差数列を延長できるだけ延長しきります。そうして延長された長さの最大値を $l$ としたとき、Green-Taoの定理によって長さ $l+1$ の素数のみからなる等差数列をとってきてそれの一部分として得られる長さ $l$ の等差数列を考えれば、これは与えられたどの等差数列とも異なります。これで無限性が言えました。