Graham-Rothschildの定理の証明（２・完結）

昨日に引き続き，Graham-Rothschildの定理の証明の続き．次の主張2により証明が完結すると同時に，特別な場合としてvan der Waerdenの定理も従う．

主張2: $S(l,m)$が任意の$m\ge 1$で成立すれば，$S(l+1,1)$も成立．

証明：正整数$r$を任意にとって固定する． $$C:[1,2N(l,r,r)]\to [1,r]$$ が与えられたとする．（$N(l,r,r)$は$S(l,r)$が正しいという仮定から存在す る．$N(l+1,1,r)$の候補として$2N(l,r,r)$をとりたい．証明すべきことは， 任意の$r$に対して$N(l+1,1,r)$が存在して，任意の $C:[1,N(l+1,1,r)]\to [1,r]$に対して，ある$a^{\prime },d^{\prime }$が存在して，$C(a^{\prime }+x{d}^{\prime })$は $[1,l]$の$l$同値類上定数，ということ）．

すると，或る$a,d_1,\dots ,d_r$が存在して$\mathrm{\forall }{x}_i\in [0,l]$, $(i=1,\dots ,r)$に対して

• $a+\sum _{i=1}^r{x}_i{d}_i\le N(l,r,r)$,
• $C(a+\sum _{i=1}^r{x}_i{d}_i)$は$l$同値類に対して定数．

鳩ノ巣原理より，或る$u,v\in [0,r]$で$u<v$であり， $$C(a+\sum _{i=1}^{u}l{d}_i)=C(a+\sum _{i=1}^{v}l{d}_i)$$ となるものが存在する（$a,a+\sum _{i=1}^{k}l{d}_i$, ($k=1,\dots ,r$）の$r+1$個の値に対して， その色（$C$で写した値）が$r$個しかないので重複が生じる）．

よって， $$C((a+\sum _{i=1}^{u}l{d}_i)+x\left(\sum _{i=u+1}^v{d}_i\right))$$ は$x\in [0,r]$に対して定数．（なので，$a^{\prime }=(a+\sum _{i=1}^{u}l{d}_i)$, $d^{\prime }=\sum _{i=u+1}^v{d}_i$としたい）． また $$a+(l+1)\sum _{i=u+1}^v{d}_i\le 2N(l,r,r).$$ よって$S(l+1,1)$が成立する．これで主張2が示された．

さて$S(1,1)$は自明に成立するから，上の二つの主張から，任意の$l,m\ge 1$に対して$S(l,m)$が成立，つまりGraham-Rothschildの定理が示された．また， van der Waerdenの定理は$S(l,1)$に他ならない．

Graham-Rothschildの定理の原論文は，Proceedings of AMSで公開されている．また，M. Einsiedler and T. Ward, Ergodic Theory: With a View Towards Number Theory (Graduate Texts in Mathematics)の7章冒頭にも分かりやすく解説されている．