2012年4月12日木曜日

Graham-Rothschildの定理の証明(1)

昨日の,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な修正.

0 件のコメント: