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

ファン・デル・ヴェルデンの定理（ファン・デル・ヴェルデンのていり）とは、等差数列に関する次の主張である。

「任意の自然数 k, l に対して、自然数 n(k, l) が存在して、連続する n(k, l) 個の自然数をどのように k 色に塗り分けても、同色で長さが l の等差数列が存在する」

証明

出典：^[1] ^[2]

集合Cに含まれる元が全て同じ色で塗られているとき、Cは単色であるということにする。 L 、D、Nは1以上の整数で、a,s₁,s₂,…,s_Dは正の整数であるとする。　L,D,a,s₁,s₂,...,s_D,0以上D以下の整数kに対して、集合P(k)を次で定める。

P(k)=\{a+Ls_{1}+Ls_{2}+\cdots +Ls_{k}+i_{k+1}s_{k+1}+i_{k+2}s_{k+2}+\cdots +i_{D}s_{D}|i_{j}=0,1,2,...,L-1(j=k+1,k+2,...,D)\}

MinN(L,D,N)を次の条件を満たす最小の正の整数であるとする:

条件:「区間[1,MinN(L,D,N)]に含まれる整数をN色でいかなる方法で塗り分けても、a,s₁,s₂,...,s_Dが存在して、0以上D以下である任意の整数kに対して、P(k)は区間[1,MinN(L,D,N)]に含まれており、P(k)は単色である（なお、pとqが異なっており、xがP(p)に含まれ、yがP(q)に含まれているとき、xとyは必ずしも同じ色で塗られている必要はない）」

MinN(L,1,N)の存在を示せば、ファン・デル・ヴェルデンの定理が示されたことになるということに注意せよ。目的はMinN(L,D,N)を上から評価することである。証明は帰納法による。任意のNに対してMin(1,1,N)が存在することは自明である。以下の1.と2.を示せば良い。ここでは、区間Aの長さを、Aに含まれる整数の個数とする。

1. 与えられたL,Dと任意のnに対して、MinN(L,D,n)は存在するとする。ちなみにこのとき、MinN(L,d,n) (d=1,…,D)も存在する。また、 $M={\mathrm {M} inN}(L,D,n)$ とする。次の不等式が成り立つ。

{\mathrm {M} inN}(L,D+1,n)\leq M*{\mathrm {M} inN}(L,1,n^{M})

<証明> I = [1 , M*MinN(L,1,n^M)]とする。区間Iに含まれる整数をn色で塗り分けたとする。Iを長さMのMinN(L,1,n^M)個の区間に分割する。長さMの各区間はn^M色のうちの1色で塗られていると見なすことが出来る。MinNの定義より、我々は等間隔で並んだL+1個の長さMの区間を見つけることが出来、その中で最も右の1個を除いたL個の区間は同じ色で塗られている。Mの定義より、a,s_1,s_2,…,s_Dが存在して、P(k) (k=0,1,…,D) は区間[1,M]に含まれており、P(k)は単色である。s_{D+1}を上述の長さMの区間どうしの間隔とすれば良い。

2. あるLと任意のD、任意のnに対してMinN(L,D,n)は存在するとする。このとき、次のようにMinN(L+1,1,n)を上から評価することができる。

{\mathrm {M} inN}(L+1,1,n)\leq 2{\mathrm {M} inN}(L,n,n)

<証明> I=[1,2MinN(L,n,n)]とする。Iをn色で塗り分ける。このときa,s_1,…,s_nが存在して、P(k) (k=0,1,…,n)は[1,MinN(L,n,n)]に含まれており、P(k)は単色である。鳩ノ巣原理により、u,v (u<v; u,vは0以上n以下の整数)が存在して、

a+Ls_{1}+Ls_{2}+\cdots +Ls_{u}

と

a+Ls_{1}+Ls_{2}+\cdots +Ls_{v}

は同じ色で塗られている。したがって、

(a+L*(s_{1}+\cdots +s_{u}))+x*(s_{u+1}+\cdots +s_{v})(x=0,1,...,L-1,L)

は全て同一色で塗られている。また、 $(a+L*(s_{1}+\cdots +s_{u}))+(L+1)*(s_{u+1}+\cdots +s_{v})$ はIに含まれている。よって、2.が示された。

参考文献

^ Graham, R. L.; Rothschild, B. L. (1974). “A short proof of van der Waerden's theorem on arithmetic progressions”. Proc. American Math. Soc. 42 (2): 385–386. doi:10.1090/S0002-9939-1974-0329917-8.
^ Van der Waerden's theorem

『数論の3つの真珠』（ア・ヤ・ヒンチン著、蟹江幸博訳・解説、日本評論社）p.10
[1] p.5

[Graham1974-1] Graham, R. L.; Rothschild, B. L. (1974). “A short proof of van der Waerden's theorem on arithmetic progressions”. Proc. American Math. Soc. 42 (2): 385–386. doi:10.1090/S0002-9939-1974-0329917-8.

[en:Van_der_Waerden's_theorem-2] Van der Waerden's theorem

[1]

[2]

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

証明

関連項目

参考文献