Hales–Jewettの定理

$[1]^1$ はただ 1 つの語 $(1)$ からなり、変数語 $(\ast)$ の組合せ直線 $\{(1)\}$ はいつも単色である。よって $\mathrm{HJ}(1,r)=1$ である。
$k=2$ とする。$j=0,1,\dots,r$ について、最初の $j$ 文字が $2$、残りの $r-j$ 文字が $1$ の語 $u_j\in[2]^r$ を考える。$[2]^r$ を $r$ 色で塗ると、$r+1$ 個の語 $u_0,\dots,u_r$ のうち 2 つ $u_i,u_j$（$i< j$）は同じ色である（鳩の巣原理）。最初の $i$ 文字が $2$、第 $i+1$ から第 $j$ 文字が $\ast$、残りが $1$ の変数語 $\tau$ をとると、$\tau(1)=u_i$、$\tau(2)=u_j$ なので $L_\tau$ は単色である。よって $\mathrm{HJ}(2,r)\le r$ である。
逆に $r\ge2$ のとき、$[2]^{r-1}$ の語を、含まれる文字 $2$ の個数（$0$ から $r-1$ までの $r$ 通り）で塗る。どの組合せ直線 $L_\tau$ でも、$\tau(2)$ は $\tau(1)$ より文字 $2$ を $\lvert V(\tau)\rvert\ge1$ 個多く含むので、$L_\tau$ は単色でない。よって $\mathrm{HJ}(2,r)>r-1$ である。$r=1$ では $\mathrm{HJ}(2,1)\ge1$ は明らかである。$\square$

$(a_i,b_i)$ を $i=1,2,\dots,n$ の順に選ぶ。$(a_j,b_j)$（$j< i$）がすでに選ばれ、$\beta_1,\dots,\beta_{i-1}$ が定まっているとする。組 $(x_1,\dots,x_{i-1},v_{i+1},\dots,v_n)$（$x_j\in[k+1]$、$v_j\in[k+1]^{N_j}$）を 文脈 とよぶと、文脈は
$$ M_i:=(k+1)^{i-1}\cdot(k+1)^{N_{i+1}+\cdots+N_n} $$
通りある。各 $c\in\{0,1,\dots,N_i\}$ に、文脈ごとの色
$$ \chi\bigl(\beta_1(x_1)\cdots\beta_{i-1}(x_{i-1})\,t^{(N_i)}_{c}\,v_{i+1}\cdots v_n\bigr) $$
を並べた $\{1,\dots,r\}$ の元の $M_i$ 個組を対応させる。この組は $r^{M_i}=N_i$ 通りしかないが、$c$ は $N_i+1$ 通りあるので、鳩の巣原理により $a< b$ で同じ組が対応するものがある。それを $(a_i,b_i)$ とすれば、$i$ についての等式がすべての文脈で成り立つ。$i$ についての等式は $(a_j,b_j)$（$j\le i$）だけで決まり、後で選ぶ $(a_j,b_j)$（$j>i$）には影響されない。$\square$

$\chi$ を $[k+1]^N$ の $r$ 色の塗り分けとし、lem-hj-shelah の $a_i< b_i$ と $\beta_i$ をとる。写像 $\Phi\colon[k+1]^n\to[k+1]^N$ を
$$ \Phi(y):=\beta_1(y_1)\beta_2(y_2)\cdots\beta_n(y_n) $$
で定め、$[k+1]^n$ の塗り分け $\chi':=\chi\circ\Phi$ を考える。
段 1（文字 $k$ と $k+1$ を区別しない）。 $y,y'\in[k+1]^n$ が第 $i$ 座標だけで異なり、$y_i=k+1$、$y'_i=k$ とする。$\Phi(y)$ と $\Phi(y')$ は第 $i$ 区画だけが異なり、それぞれ $t^{(N_i)}_{b_i}$、$t^{(N_i)}_{a_i}$ である。lem-hj-shelah を $x_j:=y_j$（$j< i$）、$v_j:=\beta_j(y_j)$（$j>i$）として使うと $\chi'(y)=\chi'(y')$ である。$y\in[k+1]^n$ の文字 $k+1$ をすべて $k$ に替えた語を $\bar y\in[k]^n$ とすると、1 座標ずつ替えていけば、この事実から $\chi'(y)=\chi'(\bar y)$ が従う。
段 2（$k$ 文字の直線を延ばす）。 $\chi'$ を $[k]^n$ に制限すると $r$ 色の塗り分けであり、$n=\mathrm{HJ}(k,r)$ なので、変数語 $\sigma\in([k]\cup\{\ast\})^n$ で $\chi'(\sigma(1))=\cdots=\chi'(\sigma(k))$ となるものがある。$\sigma$ の $\ast$ に $k+1$ を代入した語 $\sigma(k+1)\in[k+1]^n$ については $\overline{\sigma(k+1)}=\sigma(k)$ なので、段 1 から $\chi'(\sigma(k+1))=\chi'(\sigma(k))$ である。よって $\chi'$ は $\sigma(1),\dots,\sigma(k+1)$ の上で一定である。
段 3（$\Phi$ で写す）。 長さ $N$ の変数語 $\tau$ を区画ごとに次のように定める。$\sigma_i\in[k]$ なら第 $i$ 区画は $\beta_i(\sigma_i)$ とする。$\sigma_i=\ast$ なら、第 $i$ 区画は第 $1$ から第 $a_i$ 文字が $k+1$、第 $a_i+1$ から第 $b_i$ 文字が $\ast$、残りが $k$ とする。$V(\sigma)$ は空でなく $a_i< b_i$ なので、$\tau$ は少なくとも 1 つの $\ast$ を含む。定義から、すべての $x\in[k+1]$ について $\tau(x)=\Phi(\sigma(x))$ である。したがって
$$ \chi(\tau(x))=\chi'(\sigma(x))\qquad(x=1,\dots,k+1) $$
はすべて等しく、組合せ直線 $L_\tau\subset[k+1]^N$ は単色である。$\square$

$r$ を固定し、$k$ に関する帰納法で示す。$k=1$ では prop-hj-small により $\mathrm{HJ}(1,r)=1$ が存在する。$\mathrm{HJ}(k,r)$ が存在すれば、thm-hj-step により $\mathrm{HJ}(k+1,r)$ も存在する。$\square$

$\psi\colon[k]^n\to[kn]$ を $\psi(w):=w_1+w_2+\cdots+w_n$ で定める（値は $n$ 以上 $kn$ 以下）。$[kn]$ の $r$ 色の塗り分け $\chi$ に対し、$\chi\circ\psi$ は $[k]^n$ の $r$ 色の塗り分けなので、単色の組合せ直線 $L_\tau$ がある。$C:=\sum_{i\notin V(\tau)}\tau_i$、$d:=\lvert V(\tau)\rvert\ge1$ とおくと
$$ \psi(\tau(x))=C+xd\qquad(x=1,\dots,k) $$
であり、$\{C+d,C+2d,\dots,C+kd\}\subset[kn]$ は公差 $d$ の $k$ 項の等差数列で、$\chi$ について単色である。$\square$

$P=\{p_1,\dots,p_k\}$（相異なる）とし、$n:=\mathrm{HJ}(k,r)$ とおく。$\psi\colon[k]^n\to\mathbb{Z}^d$ を $\psi(w):=p_{w_1}+p_{w_2}+\cdots+p_{w_n}$ で定め、$T:=\psi([k]^n)$ とおく。$T$ の $r$ 色の塗り分け $\chi$ に対し、$\chi\circ\psi$ の単色の組合せ直線 $L_\tau$ をとる。$a:=\sum_{i\notin V(\tau)}p_{\tau_i}$、$\lambda:=\lvert V(\tau)\rvert\ge1$ とおくと
$$ \psi(\tau(x))=a+\lambda p_x\qquad(x=1,\dots,k) $$
なので、$a+\lambda P=\psi(L_\tau)\subset T$ は単色である。後半は $\mathbb{Z}^d$ の塗り分けを $T$ に制限すればよい。$\square$