グリーン・タオの定理

この章の道すじ。 完全な証明は専門誌で67ページあり、高校までの数学ではたどれない。手で証明できるのは、終わらない列が無いこと（手順1〜4）までである。長い列がありそうな理由は数えて確かめ、セメレディの定理と移し替えは、何をつないだのかを図でつかむ。

言葉と記号

等差数列は、同じ数ずつ増えていく数の列である（等差数列の一般項）。増える量を公差といい、$d$と書く。最初の数を初項といい、この定理では$p$で表す。

並ぶ個数を長さといい、$k$で表す。公式の$p+jd$は初項に公差を$j$回足した数で、$j=0$が初項そのものなので、$k$項あれば$j$は$k-1$で終わる。

$\forall$は「どんな〜でも」、$\exists$は「〜がある」と読む記号である。形は、Allの頭文字Aを上下に、Existの頭文字Eを左右に返したものと覚えるとよい。$d\ge 1$は公差が1以上という条件で、これが無いと5, 5, 5, …のように同じ数が並ぶだけの列まで数えてしまう。

公式は左から順に読む。先に長さ$k$を言われ、その長さに合わせて初項$p$と公差$d$を選ぶ。長さごとに別の列を答えてよい、というところが大事である。

終わらない列は作れない

「いくらでも長い」と「無限に長い」は違う。前者は、どの長さを言われても、その長さの列がどこかにあるという主張だ。後者は1本の列が切れずに続くという主張で、こちらは誤りである。

証明は短い。初項$p$、公差$d$の列が、どこまでも素数だけで続くと仮定する。番号$j$には好きな数を入れてよいので、初項と同じ数を入れてみる。

1. 列の番号$j$の項を書く

   $$p+jd$$

2. $j$に初項の$p$を代入する

   $$p+p\times d$$

3. 共通の$p$でくくる（$5+5\times 6=5\times (1+6)$と同じ計算）

   $$p+pd=p(1+d)$$

4. $p$は2以上、$1+d$も2以上なので、この項は2つの数の積で、素数ではない。仮定と矛盾する

   $$p(1+d)\text{は素数でない}$$

長さ$k$の列では番号が$k-1$まであるので、初項$p$が$k-1$以下だと、手順3の項が列の中に入ってしまう。だから素数だけの列の初項は、いつも長さ$k$以上である。

図で見当をつける

なぜ長い列がありそうなのか。手がかりは素数定理である。$x$以下の素数はおよそ$x/\ln x$個ある、つまり整数の$\ln x$個に1個が素数だという定理で、$\ln x$は対数の一種だ。

1のあとに0が$n$個並ぶ数$10^n$では、$\ln 10^n$が約$2.3n$になる。だから$10^n$の近くでは、整数のおよそ$2.3n$個に1個が素数だと見積もれる。$n=6$なら$2.3\times 6=13.8$で、100万の近くでは約14個に1個にあたる。

そこで、素数を「ときどき当たるくじ」とみなしてみる。これは証明ではなく、グリーンとタオも論文の冒頭で触れる、見当をつけるための計算である。$N$以下の範囲で長さ$k$の列を作るなら、候補は$p+(k-1)d\le N$を満たす初項と公差の組で、その数は、横に$p$、縦に$d$をとった三角形の面積くらいある。

$N=10^n$とする。1つの項が当たる見込みは$\frac{1}{2.3n}$で、$k$個の項が別々に当たるとすれば、この見込みを$k$回掛ける。それを組の数に掛けると、全部当たる組の数の見積もりになる。

$$\frac{N^2}{2(k-1)}\times {\left(\frac{1}{2.3n}\right)}^k$$

$N=10^6$、$k=5$を入れてみる。組の数は$10^{12}÷8=1.25\times 10^{11}$で、$13.8^5$は約50万なので、当たる組は$1.25\times 10^{11}÷500000$、つまり約25万個になる。

$N$を10倍にすると、組の数は100倍になる。一方、見込みの$\frac{1}{2.3n}$は$n$が$n+1$に変わるだけなので、$n$が大きいほどほとんど下がらない。だから$k$をいくつに決めても、$N$を大きくすれば見積もりはいくらでも大きくなる。

この見積もりと、筆者が100万以下の素数で全部の組を計算機で調べた個数を比べる。長い列の途中の部分も1本に数えた。

長さ$k$	見積もり	数えた個数
3	約9,500万	157,300,309
4	約460万	17,636,879
5	約25万	1,495,343
6	約1.4万	227,456
7	約870	25,018
8	約54	5,222
9	約3	984
10	約0.2	145

長さが伸びるほど、数えた個数は見積もりを大きく上回る。長さ10では見積もりが1個に満たないのに、145個もあった。くじの計算は控えめすぎるのである。

外れる大きな理由は、公差を選ぶと小さな素数の倍数を列から追い出せることにある。公差2なら3項に1つは3の倍数になるが、公差6なら、初項が3の倍数でない限り3の倍数は1つも現れない。

公差を割り切らない素数$q$の段には$q$項ごとに印が並び、公差を割り切る素数の段からは印が消える（初項もその素数の倍数なら全部に付く）。印の付いた項はその素数自身でなければ素数でないので、長い列には公差に小さな素数を入れておく必要がある。

ここまでの計算は、列がありそうだと言うだけである。では、どうすれば「ある」と言い切れるのか。

言い切るための3つの部品

1つ目の部品は、素数を一度忘れた定理である。

1から$N$までの整数から、決まった割合$\delta$（デルタ）以上の数を選ぶ。どう選んでも、$N$が十分大きければ長さ$k$の等差数列が必ず含まれる。これがセメレディの定理である。

3項の等差数列を作らないように選ぶと、すぐに行き詰まる。計算機で全部調べると、最大は1〜9で5個（56%）、1〜27で11個（41%）、1〜81で22個（27%）で、範囲が広いほど割合は下がる。セメレディの定理は、範囲を広げればこの割合がどんな$\delta$よりも小さくなることを、どの長さの列についても保証している。

ところが、素数はこの定理の条件を満たさない。$N$以下の整数の中で素数が占める割合は、$N=10$の40%から$N=10^8$の5.8%まで落ち、さらに下がり続ける。

そこで2人は、比べる相手を替えた。2つ目の部品は、小さな素数で割り切れない数（ほぼ素数）の中で素数の割合を考えることで、ここにゴールドストンとユルドゥルムの計算を使う。タオは2006年の講演論文の注で、素数を、整数の中で割合0の集まりとしてではなく、ほぼ素数の中で割合が0より大きい集まりとして見ている、と説明している。

小さな素数の倍数を順に取り除くことを、ふるうという。

ふるう素数を増やすと素数でない数が減り、残りの中の素数の割合が上がる。2〜400を3までふるう（2と3の倍数を除く）と132個が残り、そのうち76個（57.6%）が素数になる。

範囲$N$を広げるなら、ふるう素数の上限も広げたい。そこで筆者の簡単な模型として、上限を$N$の4乗根（4回掛けると$N$になる数）に決めて数えてみる。$N=10^4$なら上限は10で、$N=10^8$なら100である。

全部の整数の中の割合が半分以下に落ちるあいだ、残りの中の割合は53.6%から47.9%へしか動かない。$N$をもっと大きくしても、計算上は約44.5%に近づくだけで0には向かわない。これなら、決まった割合$\delta$の話に持ち込めそうに見える。

ただし、4乗根という上限は筆者が説明のために選んだもので、論文の値ではない。本物の証明では、数の集まりの代わりに、ほぼ素数に大きな重みを置く式を使う。

残る壁は、セメレディの定理が「全部の整数の中」の話だという点だ。3つ目の部品で2人が新しく示したのは、舞台を「十分でたらめに見える集合」に替えても同じ結論が成り立つ、という移し替え（transference principle）である。でたらめに見えるとは、ある数がほぼ素数であることと別の数がほぼ素数であることが、ほとんど無関係に起きるという意味にあたる。

証明の骨組みを式で見る

$A$を1から$N$までの整数の集合の一部とし、$|A|$をその個数とする。$N$が$\delta$と$k$で決まる数$N_0(\delta ,k)$以上のとき、セメレディの定理は次の形に書ける。$⟹$は「ならば」という記号である。

$$|A|\ge \delta N⟹\text{長さ}k\text{の列がある}$$

移し替えでは、$N$の代わりに、十分でたらめに見える集合$S$の個数$|S|$を使う。ここでも$N$は十分大きいとする。$A\subset S$は「$A$は$S$に含まれる」という記号である。

$$\begin{array}{rl}& A\subset S,|A|\ge \delta |S|\\ & ⟹\text{長さ}k\text{の列がある}\end{array}$$

難所は、この移し替えの証明にあり、高校までの数学では追えない。素数を表す関数を「規則的な部分」と「でたらめな部分」に分け、でたらめな部分は列の個数にほとんど響かないこと、規則的な部分はセメレディの定理で扱えることを示す。

公差の話は、証明の中にも現れる。論文の$W$トリックでは、小さな素数を全部掛けた$W$を取り、$Wn+1$の形の素数だけを考える。番号$n$が公差$r$で進むと、もとの数は公差$Wr$で進む。

$$W(n+jr)+1=(Wn+1)+j(Wr)$$

$W=6$、$n=1$、$r=5$なら、7, 37, 67, 97, 127（公差30）である。小さな素数の倍数を最初から追い出すこの一手を、2人は脚注で「トリックのように見えるが、実際には極めて大事な特徴」と呼んでいる。

論文の定理は、どの長さの列も無限にあるという形で述べられている。個数は下限までで、見積もりの形$N^2/(\ln N{)}^k$の定数まで含めて数えたのは、そのあとのグリーン、タオ、タマル・ツィーグラーの論文である。

定理が答えないことも多い。第一に、見つけ方を教えない。2人の短い覚え書きが証明から取り出したのは、長さ$k$の列がこの数より手前に必ずあるという上限で、次の塔の形をしている。一番上は正確には$O(k)$（$k$の定数倍まで）と書かれ、100$k$で足りるだろうと添えられている。

$$2^{2^{2^{2^{2^{2^{2^{100k}}}}}}}$$

この塔は、探す範囲の上限としては大きすぎて役に立たない。

第二に、隣り合う素数だけの列については何も言わない。5, 11, 17, 23, 29のあいだにも7, 13, 19という素数がある。第三に、差が2の素数の組（双子素数）のような決まった形の組が無限にあるかどうかについて、論文は「前進をもたらさない」と明言している。