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}{\longrightarrow} [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'=N(l,1,r^M)$と置く．$C:[1,MM']\to [1,r]$が与えられたとする．（$N(l,m+1,r) = N(l,m,r)N(l,1,r^M)$としたい）． \[ C':[1,M']\to [1,r^M] \] を，$C'(k)=C'(k')\Leftrightarrow C(kM-j) = C(k'M-j)$, $0\le \forall j\le M$と定義する． 帰納法の仮定から，或る$a',\, d'$が存在して$C'(a'+xd')$は$x\in [0,l-1]$で定数となる．

$S(l, m)$は区間$[a'M+1, (a'+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'M+1, (a'+1)M], \] かつ$C(a+\sum_{i=1}^{m}x_i d_i)$は$l$同値類上定数，となるものが存在する．すると， \[ d_i' =d_i,\, (i\in[1,m]),\, d_{m+1}'=d'M \] とすれば，$S(l, m+1)$が成立する．

9:00後記：TeXnicalな修正．