グリーン・タオの定理1　グラハム・ロスチャイルドの定理

こんにちは,itouです.
グリーン・タオの定理(著:関真一朗)を買ったので,内容を少しまとめます.
この本では以下の定理を理解することが最終目的です.

このような整数からなる集合がどのような場合に等差数列(やその一般化)を含むかという問題をAPラムゼー問題といいます.(APはArithmetic Progressionの頭文字)

まず,以下の定理が第一歩です.

もし${\mathbb{Z}}_{>0}\mathrm{\setminus }\mathbb{P}$が任意の長さの等差数列を含まないならば,ファン・デル・ヴェルデンの定理よりグリーン・タオの定理が証明されますが,実際はそうではありません.(いくらでも長い素数砂漠が存在することから${\mathbb{Z}}_{>0}\mathrm{\setminus }\mathbb{P}$は任意の長さの公差1の等差数列を含むので)
ファン・デル・ヴェルデンの定理は任意の等差数列を含む部分集合がどれか教えてくれないのです.これを克服するのがセメレディの定理です.ハイパーグラフ除去補題(第4章)⇒有限版多次元セメレディの定理(第2章)⇒多次元セメレディの定理(第2章)⇒セメレディの定理(第2章)という関係があります.つまりハイパーグラフ除去補題を示せばいい(第4章)のですがいきなりそれは難しいので,今回はファン・デル・ヴェルデンの定理の一般化であるグラハム・ロスチャイルドの定理を解説します.これはいわば一般化された等差数列についてのファン・デル・ヴェルデンの定理です.注:この定理はグリーン・タオの定理の証明に使われません.準備運動というわけです.

記号について

通常と違い,$[a,b]$は$a$以上$b$以下の整数の集合を指します.また,$[N]=[1,N]$とします.等差数列$(a{)}_n$と集合$\{a_1,a_2,\cdots ,a_n\}$を同一視します.等差数列の元の個数を長さということがあります.

本題

次のような同値関係を導入します.

少し説明しておきます.
同値類とは同値関係によって集合を分類したものです.左から数えて最後に$k$が現れるのを$j$番目とすると,
$j=0$のときの同値類は集合$[0,k-1{]}^d$です.(元の個数は$k^d$個でそのような同値類は1個)
$j=1$のときの同値類は$\{k,\underset{\text{[0,k-1]の元が}d-1\text{個}}{\underbrace{\cdots \cdots \cdots \cdots }}\}$($\cdots$の部分は$k-1$以下の非負整数が並ぶ)の形の元全体の集合です.(そのような同値類はただ1つある.)

同様に$j$のときの同値類は$\{\underset{\text{[0,k]の元が}j-1\text{個}}{\underbrace{\cdots \cdots \cdots \cdots }},k,\underset{\text{[0,k-1]の元が}d-j\text{個}}{\underbrace{\cdots \cdots \cdots \cdots }}\}$の形の元であって,左の$\cdots$の部分が一致しているような元全体の集合です.(元の個数は$k^{d-i}$個でそのような同値類は$(k+1{)}^{j-1}$個ある.)

このように$[0,k{]}^d$を$1+1+(k+1)+(k+1{)}^2+\cdots +(k+1{)}^{d-1}$個の集合に分類しておきます.

以下の同値関係$～$は$k$同値とします.

記号がいっぱい出てきたので整理しましょう.$d$は次元,$m$は分割の個数,$r$たちは公差です.
$$\begin{array}{c}\begin{array}{r}\{b+\sum _{j\in [d]}{a}_j{r}_j\in [N]:(a_1,\dots ,a_d)\in A\}\end{array}\hfill \end{array}$$
とは$d$次元の等差数列です.(1次元の等差数列がふつうの等差数列です.)等差数列の長さは同値類$A$の元の個数に対応します.($r$たちの値によっては異なる$(a_1,\dots ,a_d)$に対して同じ値であることもあり得るのではと指摘されました.等差数列の長さは最大で$\mathrm{♯}A$です)$k$は$a_j$の上限で,これより大きくなることはできません.$(a_1,\dots ,a_d)$たちはいわばインデックスで,$(a_1,\dots ,a_d)$たちが同値類$A$の中を動き回ることで数列が作られます.$b+\sum _{j\in [d]}k{r}_j\le N$という条件は,これら等差数列の元の中でも一番大きいもの($a_j\le k$なので)が$N$以下であるようにしたいということです.そのための$N$の条件が$N\ge N_{GR}(k,d,m)$です.そして$[0,k{]}^d$という空間を$k$同値によって分類し,任意の同値類$A$の元すべてから等差数列の集合を作ると,それは分割のどれかに入ります.それがどの部分集合なのか明示されていないことに注意して下さい.まるで鳩ノ巣原理ですね.(実は証明には鳩ノ巣原理が出てきます.)

証明の方針

正整数$k,d$を固定し任意の$m$に対し上の主張が成立することを$GR(k,d)$と表すことにします.$k,d$についての二重帰納法で示します.つまり仮定から別のうまい分割を構成します.

ステップ１$GR(k,d)\Rightarrow GR(k+1,1)$ を示す

まず,任意の$d\in {\mathbb{Z}}_{>0}$に対して$GR(1,d)$が成立することは$[0,1{]}^d$の任意の２元が互いに1同値でないことより分かります.($N_{GR}(1,d,m)=d+1$とすればよい)

さて,$k$を固定します.以下任意の$d$に対し$GR(k,d)$の成立を仮定します.任意の$m$に対して$N_{GR}(k+1,1,m)=2N_{GR}(k,m,m)$を取ることで,$GR(k,d)\Rightarrow G(k+1,1)$ を示します.$M=N_{GR}(k,m,m)$とします.
$N\ge 2M$を満たす$N$と任意の分割$[N]=C_1\cup \dots \cup C_m$をとり,それから分割$[M]=\bigcup _{i\in [m]}(C_i\cap [M])$をとります.仮定より$[M]$の分割に対して$GR(k,m)$を適用できて,

が成立します.ここで
$$\begin{array}{c}\begin{array}{r}b+\sum _{j\in [p]}k{r}_j(p\in [0,m])\end{array}\hfill \end{array}$$

の形の元を考えます.換言すれば,

$\underset{p\text{個}}{\underbrace{(k,\cdots ,k}},\underset{m-p\text{個}}{\underbrace{0,\cdots ,0)}}\in [0,k{]}^m$
に対する等差数列を考えます.$p$は$0$以上$m$以下なのでこのような等差数列は$m+1$個あり,すべて互いに異なる同値類の元です.分割$[N]=C_1\cup \dots \cup C_m$は$m$個の部分集合を考えていたのでした.よって,鳩ノ巣原理より,
$$\begin{array}{}\text{(1)}& & b+\sum _{j\in [s]}k{r}_j\in C_I \text{(2)}& & b+\sum _{j\in [t]}k{r}_j\in C_I\end{array}$$

が成り立つような$s,t\in [0,m](s<t)$および$I\in [m]$が存在します.このとき,任意の$l\in [0,k]$に対して,

$$\begin{array}{}\text{(3)}& & b+\sum _{j\in [s]}k{r}_j+l\sum _{j\in [s+1,t]}{r}_j\in C_I\end{array}$$

であることを示します.
$l\in [0,k-1]$のとき,

$\underset{s\text{個}}{\underbrace{(k,\cdots ,k}},\underset{t-s\text{個}}{\underbrace{l,\cdots ,l}},\underset{m-t\text{個}}{\underbrace{0,\cdots ,0)}}l\in [0,k-1]$
という元たちはすべて互いに$k$同値なので仮定と$\text{1}$より従います.
$l=k$のときは$\text{2}$から従います.
これで$\text{3}$が示されました.なぜ$\text{3}$の形の元を考えたのでしょうか.
それは,

$$\begin{array}{}\text{(3)}& & b+\sum _{j\in [s]}k{r}_j+l\sum _{j\in [s+1,t]}{r}_j\in C_I\end{array}$$
(再掲)この式の
$$\begin{array}{rl}& b+\sum _{j\in [s]}k{r}_j\end{array}$$
の部分を初項,
$$\begin{array}{rl}& \sum _{j\in [s+1,t]}{r}_j\end{array}$$
の部分を公差とみることで,$k+1$,次元$1$(つまり等差数列の長さが$k+1$)のときに帰着できるからなのです.
次元が1なので,$k+1$同値の同値類は二つしかありません.
つまり,$\{l:l\in [0,k]\}$と$\{k+1\}$です.

$$\begin{array}{rl}& b+\sum _{j\in [s]}k{r}_j+(k+1)\sum _{j\in [s+1,t]}{r}_j\end{array}$$
が$N$以下であることを確かめましょう.
$$\begin{array}{rl}& b+\sum _{j\in [s]}k{r}_j+(k+1)\sum _{j\in [s+1,t]}{r}_j\\ & =(b+\sum _{j\in [t]}k{r}_j)+\sum _{j\in [s+1,t]}{r}_j\\ \text{(4)}& & \le M+M\le N\end{array}$$

$\{(l)|l\in [0,k]\}$については$\text{3}$と$\text{4}$より,
$k+1$のときは等差数列の元が一つしかありませんから,この等差数列(というか一つの数)が分割のどれかに含まれることは明らかで,$\text{4}$と合わせて分かりました.

よって,$GR(k,d)\Rightarrow GR(k+1,1)$ が示されました.

ステップ2 $GR(k+1,d)\Rightarrow GR(k+1,d+1)$を示す

$GR(k+1,d)$が成り立つと仮定します.
$N_1=N_{GR}(k+1,d,m),N_2=N_{GR}(k+1,1,m^{N_1})$とします.このとき,$N_{GR}(k+1,d+1,m)=N_1{N}_2$を取れることを示します.
ステップ1と同様に,仮定から別の分割を構成していきます.

$N\ge N_1{N}_2$を満たす$N$と分割$[N]=C_1\cup \dots \cup C_m$を任意にとります.
$[N_1{N}_2]$を
$$\begin{array}{r}[N_1{N}_2]=\bigcup _{h\in [N_2]}([N_1]+(h-1)N_1)\end{array}$$
という$N_2$個の区間に分割します.
以下の通り.
図1

上の図で各行は$[N_1]+(h-1)N_1(h\in [N_2])$と表されます.
上の色分けにおいて$N_2$は各行の色分けの総数$m^{N_1}$より大きいので,ある色分けが存在して,その色分けに対応する$h\in [N_2]$が複数存在します.このことを使って逆に$[N_2]$を分割しましょう.

写像$c:[N]\to [m]$を$c(a)=$「$a\in C_i$なる番号$i$」として定義し,写像$\mathbf{\text{c}}:[N_2]\to [m{]}^{N_1}$を
$$\begin{array}{r}\mathbf{\text{c}}(h)=(c(1+(h-1)N_1),c(2+(h-1)N_1),\cdots ,c(N_1+(h-1)N_1))\end{array}$$
で定義します.

このとき,$[N_2]$の分割

$$\begin{array}{r}[N_2]=\bigcup _{\mathbf{j}\in [m{]}^{N_1}}({\mathbf{\text{c}}}^{-1}(\mathbf{j}))\end{array}$$
が得られます.

よって,$N_2$の定義から$b^{\prime }+(k+1)r^{\prime }\le N_2$を満たす$b^{\prime },r^{\prime }\in {\mathbb{Z}}_{>0}$,$\mathbf{\text{i}}=(i_1,\cdots ,i_{N_1})\in [m{]}^{N_1}$が存在して,
$$\begin{array}{r}\{b^{\prime }+a{r}^{\prime }:a\in [0,k]\}\subset {\mathbf{\text{c}}}^{-1}(\mathbf{\text{i}}))\end{array}$$
が成り立ちます.
図2

$N_1$は$m$よりも十分大きいので,$i_j$の中には同じものが複数含まれうることに注意して下さい.

従って
各$l\in [N_1]$に対して
$$\begin{array}{}\text{(5)}& \{l+(b^{\prime }+a{r}^{\prime }-1)N_1:a\in [0,k]\}\subset C_{i_l}\end{array}$$
であることが分かります.

ここまで来たらもう少しです.最後にある$L\in [N_1]$が存在して$C_{i_L}$の中に所望の$(k+1,d+1)$の等差数列が含まれることを確認しましょう.

ここで以下の補題を示します.

$GR(k+1,d)$は平行移動の原理を満たすので,$N_1$の定義より区間$[N_1]+(b^{\prime }-1)N_1$に対して$GR(k+1,d)$を適用することで(ここでようやく仮定を使います)
$$\begin{array}{r}(b^{\prime }-1)N_1+1\le b+\sum _{j\in [d]}{a}_j{r}_j\le b^{\prime }{N}_1,(a_1,\cdots a_d)\in [0,k+1{]}^d\end{array}$$

を満たす$b,r_1,\cdots r_d$が存在し,$[0,k+1{]}^d$の$(k+1)$同値に関する各同値類$A$ごとに$i(A)\in [m]$があって

$$\begin{array}{}\text{(6)}& \{b+\sum _{j\in [d]}{a}_j{r}_j:(a_1,\dots ,a_d)\in A\}\subset C_{i(A)}\end{array}$$

が成立します.このとき,
$$\begin{array}{rl}& b+\sum _{j\in [d]}(k+1)r_j+(k+1)r^{\prime }{N}_1\\ & =b^{\prime }{N}_1+(k+1)r^{\prime }{N}_1\\ \text{(7)}& & \le N_1{N}_2\le N\end{array}$$
であることに注意して,$[0,k+1{]}^{d+1}$の$(k+1)$同値に関する任意の同値類$A^{\prime }$に対して$i^{\prime }(A^{\prime })\in [m]$が存在し,

$$\begin{array}{}\text{(8)}& \{b+\sum _{j\in [d]}{a}_j{r}_j+a_{d+1}{r}^{\prime }{N}_1:(a_1,\dots ,a_d,a_{d+1})\in A^{\prime }\}\subset C_{i^{\prime }(A^{\prime })}\end{array}$$
が成り立つことを確認しましょう.$A^{\prime }$は$[0,k+1{]}^d$の$(k+1)$同値に関する同値類を用いて$A^{\prime }=A\times [0,k]$と表されるか,第$(d+1)$成分が$k+1$であるような1元集合です.後者の場合は自明(同値類の元が1つ,つまり等差数列の長さが1だから)なので,前者の場合を考えます.$(a_1,\cdots ,a_d)\in A$
を固定するとき,$\text{5}$により,
$$\begin{array}{}\text{(9)}& \{b+\sum _{j\in [d]}{a}_j{r}_j+a_{d+1}{r}^{\prime }{N}_1:a_{d+1}\in [0,k]\}\subset C_{i_L}\end{array}$$
が成り立ちます.ただし$L=b+\sum _{j\in [d]}{a}_j{r}_j-(b^{\prime }-1)N_1\in [N_1]$です.

$A^{\prime }=A\times [0,k]$でしたから,$A^{\prime }$は$A$の元に$(d+1)$番目の元を付け加えて作ったのでした.$\text{9}$はそのようにして作った$A^{\prime }$から作った等差数列がすべて同じ$[N]$の分割の部分集合に入ると言っています.
ここで,以下のことに気をつけてください.

$a_{d+1}=0$のときを考えます.(いま$(a_1,\dots ,a_d)\in A$を固定していることに注意)
$$\begin{array}{r}\{b+\sum _{j\in [d]}{a}_j{r}_j:(a_1,\dots ,a_d)\in A\}\subset C_{i(A)}\end{array}$$
$$\begin{array}{r}\{b+\sum _{j\in [d]}{a}_j{r}_j+a_{d+1}{r}^{\prime }{N}_1:a_{d+1}\in [0,k]\}\subset C_{i_L}\end{array}$$

上の2つの集合にはともに固定した$(a_1,\dots ,a_d)$に対し
$$\begin{array}{r}b+\sum _{j\in [d]}{a}_j{r}_j\end{array}$$
が含まれています.よって,上の囲み枠より,$i(A)=i_L$です.
最後に$(a_1,\dots ,a_d)$を動かしますが,$L$は$(a_1,\dots ,a_d)$に依存していました.$\mathrm{♯}A$個の$(a_1,\dots ,a_d)$について,$i_L$が同じになります.

結局,つねに$i^{\prime }(A^{\prime })=i(A)=i_L$ととれることが分かりました.以上より$GR(k+1,d+1)$が成立します.

感想

二重帰納法とか出てきて楽しかったです.$N_{GR}(k,d,m)$がどのような整数になるんでしょうか.ちなみにこの内容は本書で3ページくらいです.先は長いですね.

謝辞

ここまで読んで下さりありがとうございました。誤植等指摘お願いいたします。

訂正記録

2024/04/14:$k$同値の例,誤植を訂正
2024/04/17:$k$同値の同値類の個数の誤りを訂正,等差数列の長さについての指摘を反映,最後の$i^{\prime }(A^{\prime })=i(A)=i_L$を得る議論を修正.