van der Waerdenの定理，Graham-Rothschildの定理

記号を一つ用意する．正整数$n$に対して，$[1,n]$と書いたら，正整数の列$\{1,2,\dots ,n\}$とする．
さて，van der Waerdenの定理
「任意の正整数 $l$, $r$に対して正整数$N(l,r)$が存在して，$\mathrm{\forall }C:[1,N(l,r)]\to [1,r]$に 対して正整数$a,d$が存在して，$C(a+xd)$, $x=1,\dots ,l$は一定値」
という主張がある．つまり，$C$は区間$[1,N(l,r)]$を$r$個の色に塗り分けていると思えば，同じ色の有限等差数列$a+xd$, ($x=1,\dots ,l$)が存在するというものである．

この証明は，例えば，ア・ヤ・ヒンチン著，蟹江訳の「 数論の3つの真珠 (はじめよう数学) に載っているのだが，比較的複雑なものである．

主張を一般化（高次元化）した，Graham-Rothschildの定理というものがあって，次の主張$S(l,m)$が任意の正整数$l,m$に対して成立することを主張する：
「$\mathbf{S}\mathbf{(}\mathbf{l}\mathbf{,}\mathbf{m}\mathbf{)}$: 任意の$r$に対して，或る$N(l,m,r)$が存在して次を満たす：任意の $C:[1,N(l,m,r)]\to [1,r]$に対して，或る$a,d_1,\dots ,d_m(>0)$が存在して，$C(a+\sum _{i=1}^m{x}_i{d}_i)$は，$[1,l{]}^m$の各$l$同値類上で定数」，
ここで，$l$同値というのは，次のように定義される：
$(x_1,\dots ,x_m),(x_1^{\prime },\dots ,x_m^{\prime })\in [0,l{]}^m$が$l$同値とは，

• 全ての$i=1,\dots ,m$に対して，$x_i<l$, $x_i^{\prime }<l$であるか，もしくは
• 最後に$l$が現れる所まで成分が一致している，つまり，
• ある$k$に対して$x_k=x_k^{\prime }=l$, かつ，
• $x_j<l$, $x_j^{\prime }<l$（$k<j\le m$）かつ
• $x_i=x_i^{\prime }$ （$1\le i\le k$）．

このとき$(x_1,\dots ,x_m){\sim }_l(x_1^{\prime },\dots ,x_m^{\prime })$と書く．
この証明を，2回ほどに分けて述べてみたい．主張は一般化されているが，そうすると意外なことに，証明はずっと簡潔になる．