Graham-Rothschildの定理の証明（１）

昨日の，Graham-Rothschildの定理は，「任意の正整数$l$, $m$について$S(l,m)$が成立する」というものだった．言い換えると，或る$a,d_1,\dots ,d_m(>0)$が存在して， $$[1,l{]}^m\ni (x_1,\dots ,x_m)\mapsto a+\sum _{i=1}^m{x}_i{d}_i\in [1,N(l,m,r)]\stackrel{C}{⟶}[1,r]$$ は$[1,l{]}^m/{\sim }_l$を経由する，という主張である．証明は二重帰納法で，今日はまず$m$についての議論．

主張1：$S(l,m)$が或る$m\ge 1$で成立すれば$S(l,m+1)$も成立．

証明：正整数$r$を任意にとって固定する．$M=N(l,m,r)$, $M^{\prime }=N(l,1,r^M)$と置く．$C:[1,M{M}^{\prime }]\to [1,r]$が与えられたとする．（$N(l,m+1,r)=N(l,m,r)N(l,1,r^M)$としたい）． $$C^{\prime }:[1,M^{\prime }]\to [1,r^M]$$ を，$C^{\prime }(k)=C^{\prime }(k^{\prime })\iff C(kM-j)=C(k^{\prime }M-j)$, $0\le \mathrm{\forall }j\le M$と定義する． 帰納法の仮定から，或る$a^{\prime },d^{\prime }$が存在して$C^{\prime }(a^{\prime }+x{d}^{\prime })$は$x\in [0,l-1]$で定数となる．

$S(l,m)$は区間$[a^{\prime }M+1,(a^{\prime }+1)M]$にも適用できる．また，$M=N(l,m,r)$のとり方から，$a,d_1,\dots ,d_m(>0)$で $$\{a+\sum _{i=1}^m{x}_i{d}_i|x_i\in [0,l]\}\subset [a^{\prime }M+1,(a^{\prime }+1)M],$$ かつ$C(a+\sum _{i=1}^m{x}_i{d}_i)$は$l$同値類上定数，となるものが存在する．すると， $$d_i^{\prime }=d_i,(i\in [1,m]),d_{m+1}^{\prime }=d^{\prime }M$$ とすれば，$S(l,m+1)$が成立する．

9:00後記：TeXnicalな修正．