インテジャーズ

インテジャーズ

数、特に整数に関する記事。

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

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

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

  • … スポークがそれぞれ同色(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

戦略・証明の流れ

(再掲) 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-1)-APを量産することが出来ても各々の色はバラバラでしょう。それらを上手く束ねればを作ることができるかもしれません。

実際には、スポーク数について帰納的に製造していきます(つまり証明の全体的な構造は二重帰納的!)。実はこの製造についても平行移動の原理が成り立つので、一度製造方法を習得できれば同スポーク数のはいくらでも大量に生産することが可能になります。大量のを用いてスポーク数がもう一つ多いを製造します。

その製造過程で重要になるのが「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]及び相異なるdc_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を2つの(或いは幾つかの)クラスに分ける。このとき、少なくとも1つのクラスは任意の長さの等差数列を含む。

この予想は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)はオランダ人数学者。チェロ、ピアノ、チェスなどが好きで、幾つかの言語を喋ることができたようです。

f:id:integers:20170502155200j:plain

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

*7:歴史を正確に知るにはかなり本気で調査する必要がありそうです。Van der Waerdenは論文タイトルにBaudetの名前を入れていますが、Baudetについては殆ど何も知らなかった?

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

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

*10:従って、Baudet予想とVan der Waerdenの定理は同値です。驚きました。