2017-03-08

ファン・デル・ヴェルデンの定理

次の有名定理の証明を解説します：

van der Waerdenの定理 (1927) 任意の正の整数 $k, m$ に対して、或る正の整数 $N(k, m)$ が存在して次が成り立つ: $N\geq N(k, m)$ なる任意の整数 $N$ に対して、 $1$ から $N$ までの整数をどのように $m$ 色に塗り分けたとしても、必ず同じ色で塗られた長さ $k$ の等差数列が存在する。

証明はたくさんありますし、短いものも知られていますが、今回は個人的に面白かった証明を採用します*1。

用語等

等差数列の初項・公差・長さ … 長さのみ馴染みがないかもしれませんが、しばしば項数と呼ばれるものです。等差数列(arithmetic progression)をAPと略記します。初項・公差・長さがそれぞれ $a, r, k$ のAPを $[a, r, k]$ と表示します。長さが $k$ のAPを $k$ -APと呼びます。

正の整数 $n$ に対し、集合 $\{1, 2, \dots, n\}$ を $[n]$ と略記します。

正の整数 $n, a$ に対して、 $[n]$ の $a$ -シフト $[n]+a$ を $\{a+1, a+2, \dots, a+n\}$ で定義します。これを区間と表現することがあります。

正の整数 $N, m$ に対し、 $[N]$ の $m$ 色塗り分けとは写像 $\mathcal{c}\colon [N] \to [m]$ のことを言います*2。要は $[m]$ の元が色で、 $i \in [N]$ に対する $\mathcal{c}(i)$ が $i$ の色です。同様に、正整数 $a$ に対して、写像 $[N]+a \to [m]$ のことを $[N]$ の $a$ -シフトの $m$ 色塗り分けとよびます。

同色 $k$ -AP … 考察中の塗り分けに対し構成する数の色が全て同じであるような長さ $k$ のAPのこと。

車輪 … $k, d, a$ を正の整数とします。このとき、半径 $k$ 、スポーク数 $d$ 、ハブ $a$ の車輪とは、 $d$ 個の $k$ -APの組 $([a, r_1, k], \dots, [a, r_d, k])$ のことを言います。各 $i=1, 2, \dots, d$ に対して、( $k-1$ )-AP $[a+r_i, r_i, k-1]$ のことをスポークと言います( $k=1$ のときはスポークなし)。

f:id:integers:20170308005919p:plain:w400

カラフルな車輪 … スポークがそれぞれ同色( $k-1$ )-APで、ハブと各スポークが全て相異なる色になっているような車輪のこと。すなわち、 $m$ 色塗り分け $\mathcal{c}$ に対して( $m > d$ )、或る相異なる色 $c_0, c_1, \dots, c_d$ が存在し、 $\mathcal{c}(a)=c_0$ , $\mathcal{c}(a+jr_i) = c_i$ が任意の $1 \leq i \leq d$ および $1 \leq j \leq k-1$ に対して成り立つ(車輪の設定は直前のものを用いた)。

f:id:integers:20170308005948p:plain:w400

戦略・証明の流れ

(再掲) van der Waerdenの定理 任意の正の整数 $k, m$ に対して、或る正の整数 $N(k, m)$ が存在して次が成り立つ: $[N(k, m)]$ の任意の $m$ 色塗り分けに対して、必ず或る同色 $k$ -APが存在する。

$N(k, m)$ で言えれば、任意の $N \geq N(k, m)$ で言えるのは主張の性質上明らかです。次の主張も自明ですが、認識しておくことは非常に重要です：

平行移動の原理 $a$ を任意の正整数とする。van der Waerdenの定理における $N(k, m)$ が存在するならば、 $[N(k, m)]$ の $a$ -シフトもその任意の $m$ 色塗り分けに対して同色 $k$ -APを持つ。

定理の証明は長さ $k$ に関する数学的帰納法で行います。つまり、同色( $k-1$ )-APの存在は仮定されているので、それを上手く用いて同色 $k$ -APを作ることができれば勝ちです。

しかし、それは簡単には実行できそうにはありません。同じ色で $k-1$ 個連続で数が等間隔に並んでくれていたとしても、そう都合よくもう一つ隣の数が同じ色をしてくれているとは限らないからです。

ただ、少し嬉しいこととして、材料になる同色( $k-1$ )-APはいくらでも用意できます。というのも、任意の正整数 $l$ を取って $[lN(k-1, m)]$ を考えれば、これを $l$ 等分した各集合は平行移動の原理によって同色( $k-1$ )-APを含む*3ので、 $l$ 個の同色( $k-1$ )-APを得ることができます。とは言っても、いくら同色( $k-1$ )-APがあってもどいつもこいつも同色 $k$ -APに延長できない可能性は否定できません。

そこで一旦同色 $k$ -APを作ることは諦めて、半径 $k$ のカラフルな車輪をスポーク数について帰納的に製造していきます(つまり証明の全体的な構造は二重帰納的！)。実はこのカラフルな車輪製造についても平行移動の原理が成り立つので、一度製造方法を習得できれば同スポーク数のカラフルな車輪はいくらでも大量に生産することが可能になります。大量のカラフルな車輪を用いてスポーク数がもう一つ多いカラフルな車輪を製造します。

その製造過程で重要になるのが「 $k$ に関する帰納法なので、 $k-1$ の場合は塗り分けの数が何であっても成立すると仮定されている」点です。

同スポーク数( $d-1$ 本とします)の大量生産されたカラフルな車輪はそれぞれ配色はバラバラなものになっているでしょう。

キートリック：それらの配色のみならず、それらを構成する数に関する情報をも含めてデータ化し、そのデータを色として管理する。そうして、あらゆるデータ(それらは高々有限個の色だ！)による塗り分けに対して帰納法の仮定を適用する。然らば、我々は等間隔に並んだ同データのカラフルな車輪を $k-1$ 個用意することが出来る！

それら選ばれし $k-1$ 個のカラフルな車輪を材料にすれば上手くスポーク数 $d$ のカラフルな車輪を作ることが出来るのです(新しいスポークは $k-1$ 個の車輪のハブ達をつなぎ合わせて作る！)。

もう少し正確に言うと、製造過程で運良く同色 $k$ -APを見つけることが出来たならばその時点で勝利なので、運悪く同色 $k$ -APを見つけることが出来なかった場合にはカラフルな車輪のスポーク数を増やすことが出来るという仕組みです。

ところが！色には限りがありますので、どれだけ数達が同色 $k$ -APを発見されるのを拒もうとも、スポーク数が $m$ に到達した時点で或るスポークはハブと同色にならざるを得ません(鳩ノ巣原理！)。つまり、そのスポークとハブからなるAPこそ同色 $k$ -APなのです！

証明

$k$ に関する数学的帰納法で証明する。 $k=1$ のときは自明である(任意の正整数は任意の塗り分けに対して同色 $1$ -AP)。そこで、 $k \geq 2$ とし、 $k-1$ のときに定理の主張が成り立つと仮定する。すなわち、任意の正整数 $m$ に対して或る正整数 $N(k-1, m)$ が存在して、任意の $[N(k-1, m)]$ の $m$ 色塗り分けに対して、 $[N(k-1, m)]$ は同色( $k-1$ )-APを含むと仮定する。

任意の正整数 $m$ を取って、以下これを固定する。或る正整数 $N(k, m)$ が存在して $[N(k, m)]$ が必ず同色 $k$ -APを含むことを示せばよい。そのために、次の主張を示す：

主張任意の正整数 $d$ に対して、或る正整数 $N_{\text{車輪}}(k-1, m, d)$ が存在して次が成立する：任意の $m$ 色塗り分けに対して、 $[N_{\text{車輪}}(k-1, m, d)]$ は

同色 $k$ -AP または
半径 $k$ 、スポーク数 $d$ のカラフルな車輪

の少なくとも一つを含む。

これは $d$ に関する帰納法で証明する。 $d=1$ の場合： $N_{\text{車輪}}(k-1, m, 1)=2N(k-1, m)$ と取れる。実際、帰納法の仮定により $[N(k-1, m)]+N(k-1, m)$ は同色( $k-1$ )-APを含むので、それをスポークとしてハブとなる数を一つ付け加えれば半径 $k$ 、スポーク数 $1$ の車輪となる。スポークの色とハブの色が等しければ同色 $k$ -APであり、異なればカラフルな車輪である。

$d-1$ で主張が成立すると仮定する。 $N_1:=N_{\text{車輪}}(k-1, m, d-1), N_2:=2N(k-1, m^dN_1^d)$ とし、 $N=N_{\text{車輪}}(k-1, m, d):=kN_1(N_2+1)$ で $d$ に対する主張が成立することを示す。 $[N]$ の $m$ 色塗り分け $\mathcal{c}\colon [N] \to [m]$ を固定する。

$[N]$ の中の $N_2$ 個の区間

$[N_1]+hkN_1, \quad h=1, \dots, N_2$

を考えよう*4。いずれかの区間が同色 $k$ -APを含んでいれば証明は完了するため、いずれの区間も同色 $k$ -APを含んでいない場合を考える。このとき、主張は平行移動の原理が成り立つものなので、各区間は半径 $k$ 、スポーク数 $d-1$ のカラフルな車輪を含む(これらの車輪は $[N_2]$ の元によって管理されていることに注意)。すなわち、任意の $h \in [N_2]$ に対して或る $a(h), r_1(h), \dots, r_{d-1}(h)\in [N_1]$ 及び相異なる $d$ 色 $c_0(h), c_1(h), \dots, c_{d-1}(h) \in [m]$ が存在して、

$\begin{cases}c(hkN_1+a(h))=c_0(h), & \\ c(hkN_1+a(h)+jr_i(h))=c_i(h) & 1 \leq j \leq k-1, 1 \leq i \leq d-1\end{cases}$

が成り立つ( $hkN_1+a(h)$ が車輪のハブで、 $[hkN_1+a(h)+r_i(h), r_i(h), k-1]$ がスポーク。ハブの色が $c_0(h)$ でスポークの色が $c_i(h)$ )。

ここで、別の塗り分け

$\begin{align}\mathcal{C}_d\colon [N_2] &\to [N_1]^d\times [m]^d \\ h &\mapsto (a(h), r_1(h), \dots, r_{d-1}(h), c_0(h), \dots, c_{d-1}(h))\end{align}$

を考える。全単射 $[N_1]^d\times [m]^d \simeq [m^dN_1^d]$ があるので、これは $m^dN_1^d$ 色塗り分けである。 $N_2$ の定義により、 $[N_2/2]+N_2/2$ は $\mathcal{C}_d$ についての同色( $k-1$ )-APを持つ。

f:id:integers:20170308012636p:plain

f:id:integers:20170308012401p:plain

それを $[b, s, k-1]$ とし、色が $(a, r_1, \dots, r_{d-1}, c_0, \dots, c_{d-1})$ であったとする。このとき、 $(a, r_1, \dots, r_{d-1}, c_0, \dots, c_{d-1})$ なる同じデータを持つようなカラフルな車輪が $k-1$ 個存在することになる。それらを用いて半径 $k$ 、スポーク数 $d$ の車輪を次のように構成する：

ハブ：　 $b_0:=(b-s)kN_1+a \in [N]$
新しいスポーク：　 $[b_0+skN_1, skN_1, k-1]$
旧スポークから作られる $d-1$ 本のスポーク(対角的に数を結ぶ)：　 $[b_0+skN_1+r_i, skN_1+r_i, k-1], \quad 1 \leq i \leq d-1$
車輪：　 $([b_0, skN_1, k], [b_0, skN_1+r_1, k], \dots, [b_0, skN_1+r_{d-1}, k])$

f:id:integers:20170308021540p:plain

f:id:integers:20170308021618p:plain

$b \geq N_2/2$ であり、 $s < N_2/2$ なので $b-s > 0$ 。また、 $b_0 < kN_1N_2+N_1$ である。スポークを構成する数についても

$b_0+j(skN_1+r_i)=(b+(j-1)s)kN_1+a+jr_i \leq kN_1N_2+N_1+(k-1)N_1=N$

なので( $b+(j-1)s$ は $[b, s, k-1]$ を構成する数なので $[N_2]$ の元であることに注意)、この車輪はちゃんと $[N]$ 内に存在する。各スポークの色を確認しよう。

新しいスポークの色：各 $1 \leq j \leq k-1$ に対して

$\displaystyle \mathcal{c}(b_0+jskN_1)=\mathcal{c}( (b+(j-1)s)kN_1+a) = c_0(b+(j-1)s) = c_0$

旧スポークから作られるスポークの色：各 $1 \leq i \leq d-1, 1 \leq j \leq k-1$ に対して

$\displaystyle \mathcal{c}(b_0+j(skN_1+r_i)) = \mathcal{c}((b+(j-1)s)kN_1+a+jr_i) = c_i(b+(j-1)s)=c_i$

よって、各スポーク一つずつは同色で塗られており、 $c_0, c_1, \dots, c_{d-1}$ は相異なる色であったので、作った車輪のスポーク同士の色は相異なることがわかった。

ハブの色 $\mathcal{c}(b_0)$ は何かは分からない。もし、あるスポークの色と同じであるならば、すなわち、 $\mathcal{c}(b_0)=c_i$ なる $0 \leq i \leq d-1$ が存在すれば、 $[b_0, skN_1+r_i, k]$ は同色 $k$ -APである。また、もし $\mathcal{c}(b_0)$ がどの $c_i$ とも相異なるのであれば、作った車輪はカラフルな車輪になっている。以上で主張が証明された。

主張より $N(k, m):=N_{\text{車輪}}(k-1, m, m)$ と取れることがわかる。実際、 $[N(k, m)]$ は任意の $m$ 色塗り分けに対して同色 $k$ -APまたは半径 $k$ 、スポーク数 $m$ のカラフルな車輪を含むが、もし後者が成立しているならば色が $m+1$ 色存在する必要があり矛盾する。よって、 $[N(k, m)]$ は必ず同色 $k$ -APを含む。 Q.E.D.

歴史

どうやらBaudet*5の予想として知られていた問題を、ArtinとSchreierとの(少なくない)コミュニケーションの後、若き数学者van der Waerdenが解決したようです*6。元々のBaudet予想は次のような形をしていると思われます*7。

Baudet予想 正の整数全体*8を二つの(或いは幾つかの)クラスに分ける。このとき、少なくとも一つのクラスは任意の長さの等差数列を含む。

この予想はBaudetの死の直前、1921年に定式化されたとする文献がありました。van der Waerdenの定理からBaudet予想が従うことはすぐ分かります。

vdWの定理 $\Longrightarrow$ Baudet予想の証明

vdWの定理を仮定して背理法によって証明する。自然数全体の $m$ 個のクラス分けであって( $m \geq 2$ )、どのクラスも「任意の長さの等差数列を含む」という性質を満たさないものがあったと仮定する。すると、どのクラスについても、そのクラスに所属する等差数列の長さは有界である*9。従って或る $k$ が存在して、どのクラスも $k$ -APを含まない。このとき、 $[N(k, m)]$ をクラス分けによって塗り分ければ、vdWの定理によって同じクラスに所属する $k$ -APが存在する。これは矛盾。 Q.E.D.

van der Waerdenは素朴な主張(=Baudet予想)を強める(=vdWの定理)ことによって帰納法による証明を可能にしたのですが、実はBaudetの予想からvdWの定理を導出することができます！*10 記号 $\mathbb{N}$ を正整数全体集合とします。

Baudet予想 $\Longrightarrow$ vdWの定理の証明

Baudet予想を仮定して背理法によって証明する。vdWの定理を否定して、或る正整数 $k, m$ 、狭義単調増大正整数列 $\{N_n\}_{n=1}^{\infty}$ 、 $[N_n]$ の $m$ 色塗り分け $\mathcal{c}_n\colon [N_n] \to [m]$ が存在して、 $[N_n]$ は $\mathcal{c}_n$ に対する同色 $k$ -APを含まないと仮定する。

鳩ノ巣原理によって、狭義単調増大正整数列 $\{n_{1j}\}_{j=1}^{\infty}$ が存在して

$\displaystyle \mathcal{c}_{n_{11}}(1)=\mathcal{c}_{n_{12}}(1)=\cdots$

が成り立つことがわかる。

再び鳩ノ巣原理によって、 $\{n_{1j}\}_{j=1}^{\infty}$ の部分狭義単調増大正整数列 $\{n_{2j}\}_{j=1}^{\infty}$ が存在して

$\displaystyle \mathcal{c}_{n_{21}}(2)=\mathcal{c}_{n_{22}}(2)=\cdots$

が成り立つことがわかる。

これを繰り返して、狭義単調増大正整数列の列

$\displaystyle \{n_{1j}\}_{j=1}^{\infty} \supset \{n_{2j}\}_{j=1}^{\infty} \supset \{n_{3j}\}_{j=1}^{\infty} \supset \cdots$

であって、任意の $i$ に対して

$\displaystyle \mathcal{c}_{n_{i1}}(i)=\mathcal{c}_{n_{i2}}(i)=\cdots$

が成り立つようなものを選択する。ここで、狭義単調増大数列 $\{n_{ii}\}_{i=1}^{\infty}$ を考えて、写像 $\mathcal{c}\colon \mathbb{N} \to [m]$ を $\mathcal{c}(i)=\mathcal{c}_{n_{ii}}(i)$ で定義する。

このとき、 $\mathbb{N}$ は $\mathcal{c}$ によって $m$ 個のクラスに分けることができるので、Baudet予想によって任意の長さの等差数列を含むクラスが存在する。つまり、或る $k$ -AP $a_1, \dots, a_k \in \mathbb{N}$ が存在して

$\mathcal{c}(a_1)=\cdots =\mathcal{c}(a_k)$

が成り立つ。任意の $i$ に対して $\mathcal{c}_{n_{ii}}\bigr|_{[i]}=\mathcal{c}\bigr|_{[i]}$ なので、 $I:=\max\{a_1, \dots, a_k\}$ とすれば

$\displaystyle \mathcal{c}_{n_{II}}(a_1)=\mathcal{c}_{n_{II}}(a_2) = \cdots = \mathcal{c}_{n_{II}}(a_k)$

となって、 $[N_{n_{II}}]$ が同色 $k$ -APを含まないという仮定に矛盾する。 Q.E.D

*1:Taoの"A quantitative ergodic theory proof of Szemerédi's theorem"のarXiv版の付録。用語や一部の議論を変更しています。

*2:全射を仮定した方が $m$ 色全部を使っていて言葉に合いますが、ここでは仮定しません。

*3:「含む」は「考えている集合の $k-1$ 個の元であって同色( $k-1$ )-APをなすものが存在する」の意味。他の場所で使用している「含む」も同様の用法。

*4:一番大きい数は $kN_1N_2+N_1$ でこれは $N$ 以下。 $hkN_1+N_1 < (h+1)kN_1+1$ なので各区間に交わりはない。

*5:Pierre Joseph Henry Baudet (1891/1/22 - 1921/12/25)はオランダ人数学者。チェロ、ピアノ、チェスなどが好きで、幾つかの言語を喋ることができたようです。

*6:彼はこの成果で数学者としての名声を得、その数年後、27歳のときに(ArtinとNoetherの講義に基づいて)代数学の有名な教科書を出版しています。

*7:正確な歴史はかなり難しそうです。van der Waerdenは論文タイトルにBaudetの名前を入れていますが(従ってBaudetへのcreditを与えたのはvan der Waerden)、Baudetについては殆ど何も知らなかった？また、Soiferの本によれば(まだちゃんと読めていません)、Ramsey以前にRamsey理論的定理を得ていたIssai Schurもこの予想にたどり着いていたようです(二つへ分ける場合)。

*8:正の整数でなければならないわけではありません。「整数全体」としても同じことが言えます。

*9: $l$ -APを含めば、 $l' < l$ なる任意の正整数 $l'$ に対する $l'$ -APも含むことになるから。