van der Waerdenの定理

$r$ 色で塗り分けたとする。各 $k\ge1$ について、塗り分けを $[W(r,k)]$ に制限すると単色の $k$ 項の等差数列があるので、その色を $c_k$ とする。$c_1,c_2,\dots$ は $r$ 個の値しかとらないので、ある色 $c$ が無限に多くの $k$ で $c_k=c$ となる。任意の $\ell\ge1$ について、$c_k=c$ となる $k\ge\ell$ をとると、色 $c$ の $k$ 項の等差数列の最初の $\ell$ 項は色 $c$ の $\ell$ 項の等差数列である。$\square$

1 項の等差数列は 1 つの数 $\{a\}$ であり、いつも単色なので $W(r,1)=1$ である。
2 項の等差数列は相異なる 2 数 $\{a,a+d\}$（$d\ge1$）であり、どの相異なる 2 数も公差をその差として 2 項の等差数列をなす。$[r+1]$ を $r$ 色で塗ると、鳩の巣原理により同じ色の相異なる 2 数があり、それが単色の 2 項の等差数列である。一方 $[r]$ の各数に相異なる色を塗れば単色の 2 項の等差数列はない。したがって $W(r,2)=r+1$ である。$\square$

冒頭の塗り分け（赤 $\{1,2,5,6\}$、青 $\{3,4,7,8\}$）は $[8]$ の塗り分けで、単色の 3 項の等差数列をもたない。したがって $W(2,3)\ge9$ である。
$[9]$ を赤と青の 2 色で、単色の 3 項の等差数列がないように塗れたとして矛盾を導く。以下、「$(x,y,z)$ により」は、等差数列 $x,y,z$ が単色でないことから残りの 1 数の色が決まることを表す。
(i) $4$ と $6$ が同じ色の場合。色の名前を入れ替えて、どちらも赤としてよい。$(4,5,6)$ により $5$ は青、$(2,4,6)$ により $2$ は青、$(4,6,8)$ により $8$ は青である。すると $2,5,8$（公差 $3$）がすべて青になり、矛盾する。
(ii) $4$ と $6$ が異なる色の場合。色の名前を入れ替えて、$4$ を赤、$6$ を青としてよい。

• $5$ が赤なら：$(3,4,5)$ により $3$ は青、$(3,6,9)$ により $9$ は赤、$(1,5,9)$ により $1$ は青、$(1,2,3)$ により $2$ は赤、$(2,5,8)$ により $8$ は青、$(6,7,8)$ により $7$ は赤である。すると $5,7,9$ がすべて赤になり、矛盾する。
• $5$ が青なら：$(5,6,7)$ により $7$ は赤、$(1,4,7)$ により $1$ は青、$(1,5,9)$ により $9$ は赤、$(7,8,9)$ により $8$ は青、$(2,5,8)$ により $2$ は赤、$(2,3,4)$ により $3$ は青である。すると $1,3,5$ がすべて青になり、矛盾する。
  どの場合も矛盾するので、$W(2,3)\le9$ である。$\square$

$s$ に関する帰納法で示す。
$s=1$ の場合。 $N_1:=W(r,k)$ とおく。$[N_1]$ の $r$ 色の塗り分けには単色の $k$ 項の等差数列 $A_1=\{a,a+d,\dots,a+(k-1)d\}\subset[N_1]$ がある。$k\ge2$ なので $d\le a+(k-1)d\le N_1$ であり、焦点は $a+kd\le N_1+d\le2N_1$ を満たす。よって (β) が成り立つ。
$s$ から $s+1$ へ（$s< r$）。 $N:=N_s$ とし、$M:=W(r^{2N},k)$（仮定により存在する）、$N_{s+1}:=2NM$ とおく。$\chi$ を $[2NM]$ の $r$ 色の塗り分けとする。$j=1,\dots,M$ について、連続する $2N$ 個の数からなる 区画
$$ B_j:=\{(j-1)\cdot2N+t\mid t=1,\dots,2N\} $$
を考える。区画 $B_j$ の 模様 を、写像 $\pi_j\colon[2N]\to\{1,\dots,r\}$、$\pi_j(t):=\chi\bigl((j-1)\cdot2N+t\bigr)$ で定める。模様は $r^{2N}$ 通りしかないので、区画の番号 $j$ に模様 $\pi_j$ を割り当てることは $[M]$ の $r^{2N}$ 色の塗り分けとみなせる。$M=W(r^{2N},k)$ なので、区画の番号の $k$ 項の等差数列 $j_0,j_0+D,\dots,j_0+(k-1)D$（$D\ge1$、$j_0+(k-1)D\le M$）で、これらの区画の模様がすべて等しいものがある。$k\ge2$ なので $D\le M-1$ である。
$o:=(j_0-1)\cdot2N$ とおく。区画 $B_{j_0}$ の最初の $N$ 個の数に帰納法の仮定を使う。すなわち $[N]$ の塗り分け $t\mapsto\pi_{j_0}(t)$ を考える。

• (α) の場合：$[N]$ に $\pi_{j_0}$ について単色の $k+1$ 項の等差数列 $E$ があれば、$E$ の各数に $o$ を足した集合は $\chi$ について単色の $k+1$ 項の等差数列で、$[2NM]$ に含まれる。
• (β) の場合：$[N]$ の中の $k$ 項の等差数列 $A_i=\{a_i+md_i\mid 0\le m\le k-1\}$（$i=1,\dots,s$）で、$\pi_{j_0}$ について単色で色 $c_1,\dots,c_s$ が互いに異なり、共通の焦点 $f=a_i+kd_i\le2N$ をもつものがある。$f\le2N$ なので $o+f\in B_{j_0}$ であり、その色 $c:=\chi(o+f)=\pi_{j_0}(f)$ が定まる。
  (β) の場合で、$c=c_i$ となる $i$ があれば、$\{o+a_i+md_i\mid0\le m\le k\}$ は $\chi$ について単色の $k+1$ 項の等差数列で、$[2NM]$ に含まれる（最後の項は $o+f$）。
  残るのは、$c$ が $c_1,\dots,c_s$ のどれとも異なる場合である。$\Delta:=2ND$ とおき、
  $$ A_i':=\{o+a_i+m(d_i+\Delta)\mid0\le m\le k-1\}\quad(i=1,\dots,s),\qquad A_{s+1}':=\{o+f+m\Delta\mid0\le m\le k-1\} $$
  とおく。これらは公差 $d_i+\Delta\ge1$、$\Delta\ge1$ の $k$ 項の等差数列である。$A_i'$ の第 $m$ 項 $o+m\Delta+(a_i+md_i)$ は、区画 $B_{j_0+mD}$ の $a_i+md_i$ 番目の数であり、$B_{j_0+mD}$ の模様は $\pi_{j_0}$ に等しいので、その色は $\pi_{j_0}(a_i+md_i)=c_i$ である。同様に $A_{s+1}'$ の第 $m$ 項は区画 $B_{j_0+mD}$ の $f$ 番目の数なので、色は $\pi_{j_0}(f)=c$ である。よって $A_1',\dots,A_{s+1}'$ はそれぞれ単色で、色 $c_1,\dots,c_s,c$ は互いに異なる。これらはすべて区画 $B_{j_0},\dots,B_{j_0+(k-1)D}$ に含まれるので $[2NM]$ に含まれる。焦点は
  $$ o+a_i+k(d_i+\Delta)=o+(a_i+kd_i)+k\Delta=o+f+k\Delta $$
  と $o+f+k\Delta$ で、すべて等しい。共通の焦点 $F:=o+f+k\Delta$ は、$f\le2N$ と $j_0+kD=(j_0+(k-1)D)+D\le M+(M-1)$ から
  $$ F\le2N(j_0-1)+2N+2NkD=2N(j_0+kD)\le2N\cdot2M=2N_{s+1} $$
  を満たす。よって $N_{s+1}$ について (β) が成り立つ。$\square$

$k$ に関する帰納法で示す。$k=1,2$ では prop-van-der-waerden-theorem-small により存在する。$k\ge2$ とし、すべての $r'$ について $W(r',k)$ が存在するとする。$r\ge1$ を固定し、lem-van-der-waerden-theorem-focusing の $N_r$ をとる。$[2N_r]$ の $r$ 色の塗り分け $\chi$ を考え、その $[N_r]$ への制限に lem-van-der-waerden-theorem-focusing を使う。(α) なら単色の $k+1$ 項の等差数列がある。(β) なら、色の異なる $r$ 個の単色の $k$ 項の等差数列 $A_1,\dots,A_r$ が共通の焦点 $f\le2N_r$ をもつ。色は $r$ 個しかないので、$A_1,\dots,A_r$ の色は $r$ 色すべてを使い尽くしており、$\chi(f)$ はある $A_i$ の色に等しい。すると $A_i\cup\{f\}$ が単色の $k+1$ 項の等差数列である。いずれの場合も $[2N_r]$ に単色の $k+1$ 項の等差数列があるので、$W(r,k+1)\le2N_r$ である。これで thm-van-der-waerden-theorem-main も示された。$\square$