2012年4月11日水曜日

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回ほどに分けて述べてみたい.主張は一般化されているが,そうすると意外なことに,証明はずっと簡潔になる.

0 件のコメント: