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',\, d'$が存在して，$C(a'+xd')$は $[1,l]$の$l$同値類上定数，ということ）．

すると，或る$a,\, d_1,\dots, d_r$が存在して$\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}ld_i) = C(a+\sum_{i=1}^v ld_i) \] となるものが存在する（$a, a+\sum_{i=1}^k ld_i$, ($k=1,\dots,r$）の$r+1$個の値に対して， その色（$C$で写した値）が$r$個しかないので重複が生じる）．

よって， \[ C\left(\left(a+\sum_{i=1}^u ld_i\right) + x\left(\sum_{i=u+1}^v d_i\right)\right) \] は$x\in [0,r]$に対して定数．（なので，$a'=(a+\sum_{i=1}^u ld_i)$, $d'=\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章冒頭にも分かりやすく解説されている．