ファン・デル・ヴェルデンの定理
鳩ノ巣原理により、u,v (u<v; u,vは0以上n以下の整数)が存在して、
a + L s 1 + L s 2 + ⋯ + L s u {\displaystyle a+Ls_{1}+Ls_{2}+\cdots +Ls_{u}}
と
a + L s 1 + L s 2 + ⋯ + L s v {\displaystyle a+Ls_{1}+Ls_{2}+\cdots +Ls_{v}}
は同じ色で塗られている。したがって、
( a + L ∗ ( s 1 + ⋯ + s u ) ) + x ∗ ( s u + 1 + ⋯ + s v ) ( x = 0 , 1 , . . . , L − 1 , L ) {\displaystyle (a+L*(s_{1}+\cdots +s_{u}))+x*(s_{u+1}+\cdots +s_{v})(x=0,1,...,L-1,L)}
は全て同一色で塗られている。また、 ( a + L ∗ ( s 1 + ⋯ + s u ) ) + ( L + 1 ) ∗ ( s u + 1 + ⋯ + s v ) {\displaystyle (a+L*(s_{1}+\cdots +s_{u}))+(L+1)*(s_{u+1}+\cdots +s_{v})} はIに含まれている。よって、2.が示された。
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 = M i n N ( L , D , n ) {\displaystyle M={\mathrm {M} inN}(L,D,n)} とする。次の不等式が成り立つ。
M i n N ( L , D + 1 , n ) ≤ M ∗ M i n N ( L , 1 , n M ) {\displaystyle {\mathrm {M} inN}(L,D+1,n)\leq M*{\mathrm {M} inN}(L,1,n^{M})}
<証明> I = [1 , M*MinN(L,1,n^M)]とする。
出典:
集合Cに含まれる元が全て同じ色で塗られているとき、Cは単色であるということにする。 L 、D、Nは1以上の整数で、a,s1,s2,...,sDは正の整数であるとする。 L,D,a,s1,s2,...,sD,0以上D以下の整数kに対して、集合P(k)を次で定める。
P ( k ) = { a + L s 1 + L s 2 + ⋯ + L s k + i k + 1 s k + 1 + i k + 2 s k + 2 + ⋯ + i D s D | i j = 0 , 1 , 2 , . . . , L − 1 ( j = k + 1 , k + 2 , . . . , D ) } {\displaystyle 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,s1,s2,...,sDが存在して、0以上D以下である任意の整数kに対して、P(k)は区間[1,MinN(L,D,N)]に含まれており、P(k)は単色である(なお、pとqが異なっており、xがP(p)に含まれ、yがP(q)に含まれているとき、xとyは必ずしも同じ色で塗られている必要はない)」