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

記号を一つ用意する．正整数$n$に対して，$[1,n]$と書いたら，正整数の列$\{1,2,\dots,n\}$とする．
さて，van der Waerdenの定理
「任意の正整数 $l$, $r$に対して正整数$N(l,r)$が存在して，$\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(l,m)}$: 任意の$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',\dots, x_m')\in [0,l]^m$が$l$同値とは，

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

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