Schurの定理(和のない集合)

第 1 式は $k$ に関する帰納法で示す。$k=0$ では両辺が $1$ である。$k-1$ で成り立てば
$$ T_k=k\cdot(k-1)!\sum_{i=0}^{k-1}\frac1{i!}+1=k!\sum_{i=0}^{k-1}\frac1{i!}+\frac{k!}{k!}=k!\sum_{i=0}^{k}\frac1{i!} $$
である。次に $e=\sum_{i=0}^\infty\frac1{i!}$ より、$k\ge1$ のとき
$$ k!\,e-T_k=\sum_{i=k+1}^\infty\frac{k!}{i!}=\frac1{k+1}+\frac1{(k+1)(k+2)}+\cdots<\sum_{j=1}^\infty\frac1{(k+1)^j}=\frac1k\le1 $$
であり、左辺は正である。$T_k$ は整数なので $T_k=\lfloor k!\,e\rfloor$ である。$\square$

$k$ に関する帰納法で示す。頂点 $v$ を 1 つ選ぶ。$v$ に接続する辺は $T_k=kT_{k-1}+1$ 本ある。どの色も $v$ で高々 $T_{k-1}$ 本しか使われないとすると、辺の本数は高々 $kT_{k-1}< T_k$ となって矛盾するので、ある色 $c$ の辺が $v$ で $T_{k-1}+1$ 本以上使われる（鳩の巣原理）。それらの辺の $v$ でない端点の集合を $W$ とすると、$|W|\ge T_{k-1}+1\ge2$ である。
$W$ の 2 頂点 $w,w'$ を結ぶ辺が色 $c$ なら、$v,w,w'$ は 3 辺がすべて色 $c$ の三角形である。そのような辺がないとする。$k=1$ なら色は $c$ しかなく、$|W|\ge2$ なので $W$ の中に辺があり、それは色 $c$ であって矛盾する。$k\ge2$ なら、$W$ の中の辺は $c$ 以外の $k-1$ 色以下で塗られているので、$W$ の $T_{k-1}+1$ 個の頂点に帰納法の仮定を使えば、同じ色の三角形がある。$\square$

$\chi\colon[N]\to\{1,\dots,k\}$ を塗り分けとする。$0,1,\dots,N$ を頂点とする完全グラフを考え、$i\ne j$ を結ぶ辺を色 $\chi(|i-j|)$ で塗る（$1\le|i-j|\le N$ なので色は定まる）。lem-schur-sumfree-tk により $N+1\ge\lfloor k!\,e\rfloor+1=T_k+1$ なので、lem-schur-sumfree-triangle により 3 辺が同じ色の三角形がある。その頂点を $i< j< l$ とし、
$$ x:=j-i,\qquad y:=l-j,\qquad z:=l-i $$
とおく。$x,y,z\in[N]$ であり、辺 $ij$、$jl$、$il$ の色がそれぞれ $\chi(x),\chi(y),\chi(z)$ で等しい。$x+y=z$ なので、これは単色の解である。後半は $S(k)$ の定義から従う。$\square$

$\{1,4\}$ と $\{2,3\}$ はどちらも和のない集合である（$1+1=2$、$1+4=5$、$4+4=8$、$2+2=4$、$2+3=5$、$3+3=6$ はどれも同じ組に入らない）。
$[5]$ を赤と青の 2 色で、単色の解がないように塗れたとする。色の名前を入れ替えて $1$ を赤としてよい。$1+1=2$ なので $2$ は青である。$2+2=4$ なので $4$ は赤である。$1+3=4$ で $1,4$ が赤なので $3$ は青である。すると $5$ は、$1+4=5$（$1,4$ は赤）から赤でなく、$2+3=5$（$2,3$ は青）から青でもない。これは矛盾である。$\square$

$[N]=A_1\cup\cdots\cup A_k$ を和のない集合への分割とする。$i=1,\dots,k$ について $A_i':=A_i\cup\{a+2N+1\mid a\in A_i\}$ とおき、$A_{k+1}':=\{N+1,N+2,\dots,2N+1\}$ とおく。これらは $[3N+1]$ の分割である（$A_i'$ の後半は $2N+2$ から $3N+1$ までの数を分け合う）。
$A_{k+1}'$ の 2 数の和は $2N+2$ 以上で、$A_{k+1}'$ の最大の数 $2N+1$ を超えるので、$A_{k+1}'$ は和のない集合である。$A_i'$（$i\le k$）の中に $x+y=z$ があるとする。$x,y$ がともに後半（$2N+2$ 以上）なら $z\ge4N+4>3N+1$ となり不可能である。$x,y$ がともに前半（$N$ 以下）なら $z\le2N$ なので $z$ も前半であり、$x,y,z\in A_i$ となって $A_i$ が和のない集合であることに反する。$x$ が前半、$y=b+2N+1$（$b\in A_i$）が後半なら、$z=(x+b)+2N+1$ は後半なので $z=c+2N+1$（$c\in A_i$）と書け、$x+b=c$ となって再び矛盾する。よって $A_i'$ も和のない集合である。
$S(1)=1$（$\{1\}$ は和のない集合で、$\{1,2\}$ は $1+1=2$ を含む）なので、$S(k)\ge\frac{3^k-1}2$ は $k$ に関する帰納法で $S(k+1)\ge3\cdot\frac{3^k-1}{2}+1=\frac{3^{k+1}-1}{2}$ から従う。$\square$

$G:=(\mathbb{Z}/p\mathbb{Z})^\times$ を法 $p$ の既約剰余類の乗法群とする（位数 $p-1$）。$G$ は可換なので、$\varphi(g):=g^m$ は群準同型 $\varphi\colon G\to G$ であり、その像を $H$ とする。$H$ は $G$ の部分群で、準同型定理により $|G|=|\ker\varphi|\cdot|H|$ である。$\ker\varphi$ は体 $\mathbb{Z}/p\mathbb{Z}$ での多項式 $t^m-1$ の根の集合なので、$|\ker\varphi|\le m$ である。したがって $H$ の剰余類の個数 $r:=|G|/|H|=|\ker\varphi|$ は $m$ 以下である。
$H$ の剰余類 $g_1H,\dots,g_rH$ は $G$ を分割する。$[p-1]$ の各数 $n$ に、$n$ の剰余類 $n\bmod p$ が属する $g_iH$ の番号 $i$ を割り当てると、$[p-1]$ の $r$ 色の塗り分けが得られる。$p-1>S(m)\ge S(r)$ なので、単色の解 $x+y=z$（$x,y,z\in[p-1]$、同じ $g_iH$ に属する）がある。$x\equiv g_iu^m$、$y\equiv g_iv^m$、$z\equiv g_iw^m\pmod p$ となる整数 $u,v,w$（$p$ で割り切れない）をとると、$g_i(u^m+v^m)\equiv g_iw^m\pmod p$ であり、$g_i$ は法 $p$ で可逆なので $u^m+v^m\equiv w^m\pmod p$ である。
最後の括弧内の主張は、thm-schur-sumfree-main により $S(m)\le\lfloor m!\,e\rfloor-1$ であることから従う。$\square$