Radoの定理(分割正則性)

$J_s:=I_1\cup\cdots\cup I_{s-1}$ とおく。列条件により、$s\ge2$ について有理数 $q_{sj}$（$j\in J_s$）で $\sum_{j\in I_s}c_j=\sum_{j\in J_s}q_{sj}c_j$ となるものがある。$s=1$ では $J_1=\emptyset$ で $\sum_{j\in I_1}c_j=0$ である。すべての $q_{sj}$ の分母の公倍数である正の整数を $c$ とし、$\mu_{sj}:=cq_{sj}\in\mathbb{Z}$、$p:=\max\{1,\max_{s,j}\lvert\mu_{sj}\rvert\}$ とおく。すると $s=1,\dots,t$ について $c\sum_{j\in I_s}c_j=\sum_{j\in J_s}\mu_{sj}c_j$ である。

$S$ を $y_1,\dots,y_t$ の生成する $(t,p,c)$-集合とし、$j\in I_u$ について $x_j:=cy_u-\sum_{s=u+1}^{t}\mu_{sj}y_s$ とおく。$\lvert\mu_{sj}\rvert\le p$ なので $x_j\in R_u\subset S$ である。和の順序を入れ替えると（$j\in I_u$ と $s>u$ の組は、$s$ を固定すると $j\in J_s$ の全体を動く）$$Ax=\sum_{u=1}^t\sum_{j\in I_u}c_jx_j=\sum_{s=1}^t y_s\Bigl(c\sum_{j\in I_s}c_j-\sum_{j\in J_s}\mu_{sj}c_j\Bigr)=0$$ である。$\square$

段 1（各段が単色）。$p,c,r$ を固定し、次の主張を $t'$ についての帰納法で示す：ある $N_{t'}$ があって、$[N_{t'}]$ の任意の $r$ 色の塗り分けについて、$y_1,\dots,y_{t'}$ の生成する $(t',p,c)$-集合で、$[N_{t'}]$ に含まれ、各段が単色なものがある。$t'=1$ では $N_1:=c$、$y_1:=1$ とすればよい。$t'\ge2$ とし、$t'-1$ で $N_{t'-1}=:n$ として成り立つとする。$\Lambda:=p(t'-1)n$、$M:=W(r,2\Lambda+1)$、$N_{t'}:=cMn$ とおく。$[N_{t'}]$ の塗り分け $\chi$ に対し、$[M]$ の塗り分け $i\mapsto\chi(ci)$ に van der Waerden の定理を使うと、$b,D\ge1$ で $\{b+jD\mid0\le j\le2\Lambda\}\subset[M]$ が $\chi(c\,\cdot)$ について単色なものがある。$[n]$ の塗り分け $\chi'(i):=\chi(cDi)$ に帰納法の仮定を使い、$z_1,\dots,z_{t'-1}$ の生成する $(t'-1,p,c)$-集合で $[n]$ に含まれ各段が $\chi'$ について単色なものをとる。$y_1:=b+\Lambda D$、$y_{s+1}:=cDz_s$（$1\le s\le t'-1$）とおく。第 $u\ge2$ 段の元は $cy_u+\sum_{s>u}\lambda_sy_s=cD\bigl(cz_{u-1}+\sum_{s>u}\lambda_sz_{s-1}\bigr)$ で、括弧の中は $z$ の集合の第 $u-1$ 段の元なので、色は $\chi'$ のその段の色に等しく、値は $cDn\le cMn$ 以下の正の整数である。第 1 段の元は $$cy_1+\sum_{s=2}^{t'}\lambda_sy_s=c\Bigl(b+\bigl(\Lambda+\textstyle\sum_{s=1}^{t'-1}\lambda_{s+1}z_s\bigr)D\Bigr)$$ である。$cz_s$ は $z$ の集合の元なので $z_s\le n$ であり、$\bigl\lvert\sum\lambda_{s+1}z_s\bigr\rvert\le p(t'-1)n=\Lambda$ である。よって括弧の中は $b+jD$（$0\le j\le2\Lambda$）の形で、第 1 段は単色であり、値は $cM$ 以下である。

段 2（同じ色の段を選ぶ）。$t':=r(t-1)+1$ とし、塗り分けを $[N_{t'}]$ に制限して段 1 の $y_1,\dots,y_{t'}$ をとる。$t'$ 個の段の色は $r$ 通りなので、ある色の段が $t$ 個以上ある。その番号を $u_1<\cdots< u_t$ とし、$y'_v:=y_{u_v}$ とおく。$y'$ の生成する $(t,p,c)$-集合の第 $v$ 段の元 $cy'_v+\sum_{w>v}\lambda_wy'_w$ は、$s=u_w$ の係数を $\lambda_w$、それ以外の $s>u_v$ の係数を $0$ とすれば $y$ の集合の第 $u_v$ 段の元である。よって $y'$ の集合は同じ色の段の和集合に含まれ、単色である。$\square$

各行に分母の公倍数を掛けて、$A$ の成分は整数としてよい（解は変わらず、各行を $0$ でない数倍しても列の間の 1 次関係は変わらないので、列条件をみたすかどうかも変わらない）。素数 $p$ ごとに、$\chi_p$ について単色の解 $x$ をとり、その色を $c_p$ とする。$x_j=p^{e_j}u_j$（$p\nmid u_j$）と書き、$e_j$ のとる相異なる値を $\eta_1<\cdots<\eta_t$、$I_s:=\{j\mid e_j=\eta_s\}$ とおく。順序付きの分割 $(I_1,\dots,I_t)$ は有限通りしかないので、無限個の素数からなる集合 $Q$ で、$p\in Q$ について同じ分割が現れるものがある。この分割が列条件をみたすことを示す。

$s$ を固定し、$J_s:=I_1\cup\cdots\cup I_{s-1}$、$V:=\operatorname{span}_{\mathbb{Q}}\{c_j\mid j\in J_s\}$（$s=1$ なら $V=\{0\}$）、$w:=\sum_{j\in I_s}c_j$ とおく。$w\notin V$ と仮定すると、$\mathbb{Q}^m$ 上の線形形式で $V$ 上で $0$、$w$ で $1$ となるものがあり、その係数の分母を払えば、$v\in\mathbb{Z}^m$ で $v\cdot c_j=0$（$j\in J_s$）かつ $v\cdot w\ne0$ となるものが得られる（$\cdot$ は標準内積）。$p\in Q$ を $p>\lvert v\cdot w\rvert$ にとる。$Ax=0$ と $v$ の内積をとると $\sum_{j}(v\cdot c_j)x_j=0$ で、$j\in J_s$ の項は消える。残りの $j$ では $e_j\ge\eta_s$ なので両辺を $p^{\eta_s}$ で割ると、$j\in I_s$ では $x_j/p^{\eta_s}=u_j\equiv c_p$、$I_s$ より後の $j$ では $x_j/p^{\eta_s}\equiv0\pmod p$ だから、$c_p\,(v\cdot w)\equiv0\pmod p$ を得る。$p\nmid c_p$ なので $p\mid v\cdot w$ となり、$0<\lvert v\cdot w\rvert< p$ に反する。よって $w\in V$ である。$s=1$ では $V=\{0\}$ なので $w=0$ である。これは列条件にほかならない。$\square$