Kneserの定理(加法的組合せ論)

1. $0\in S(X)$ で、$g,h\in S(X)$ なら $X+(g-h)=(X+g)-h=X-h$ であり、$X=X+h$ の両辺から $h$ を引くと $X-h=X$ なので $g-h\in S(X)$ である。$X+S(X)=\bigcup_{g\in S(X)}(X+g)=X$ である。$L\subset S(X)$ なら $X+L=X$ で、逆に $X+L=X$ なら $g\in L$ について $X+g\subset X$ かつ $X-g\subset X$ なので $X+g=X$ である。
2. $x\in X$ なら $x+L\subset X+L=X$ なので、$X=\bigcup_{x\in X}(x+L)$ である。相異なる剰余類は交わらず、どれも $\lvert L\rvert$ 個の元からなる。
3. $x_0\in X$ を 1 つとると、$g\in S(X)$ について $x_0+g\in X$ なので $S(X)\subset X-x_0$ である。
4. $g\in S(X)$ なら $(X+Y)+g=(X+g)+Y=X+Y$ である。$\square$

1 は主定理と $\lvert A+H\rvert\ge\lvert A\rvert$、$\lvert B+H\rvert\ge\lvert B\rvert$ による。2：$H=\{0\}$ なら 1 から $\lvert A+B\rvert\ge\lvert A\rvert+\lvert B\rvert-1$ となり仮定に反する。$A+B$ が $H$ の剰余類の和集合であることは lem-kn-stabilizer の 2 による。$\square$

$u\in X\cap Y$、$v\in X\cup Y$ とする。$v\in Y$ なら $u\in X$ より $u+v\in X+Y$、$v\in X$ なら $u\in Y$ より $u+v=v+u\in X+Y$ である。個数の等式は包除原理である。$\square$

群 $G$ も動かして、$N:=\lvert A+B\rvert+\lvert A\rvert$ についての帰納法で示す。$N$ より小さい値をもつすべての組（どのアーベル群の中の組でもよい）で主張が成り立つとする。$H:=S(A+B)$ とおく。
段階 1：$H\neq\{0\}$ の場合．$\varphi\colon G\to G/H$ を自然な準同型とする。$\varphi(g)+\varphi(A+B)=\varphi(A+B)$ なら $g+(A+B)+H=(A+B)+H$ で、$A+B$ は $H$ で周期的なので $g+(A+B)=A+B$、すなわち $g\in H$ である。よって $S(\varphi(A)+\varphi(B))=\{0\}$ である。$\lvert H\rvert\ge2$ より $\lvert\varphi(A+B)\rvert=\lvert A+B\rvert/\lvert H\rvert< \lvert A+B\rvert$ で、$\lvert\varphi(A)\rvert\le\lvert A\rvert$ なので、帰納法の仮定を $\varphi(A),\varphi(B)\subset G/H$ に当てられて、$\lvert\varphi(A)+\varphi(B)\rvert\ge\lvert\varphi(A)\rvert+\lvert\varphi(B)\rvert-1$ を得る。rem-kn-quotient によりこれは主張と同値である。
段階 2：$H=\{0\}$、$\lvert A\rvert=1$ の場合．$\lvert A+B\rvert=\lvert B\rvert=\lvert A\rvert+\lvert B\rvert-1$ である。
段階 3：$H=\{0\}$、$\lvert A\rvert\ge2$ の場合の準備．示すべきことは $\lvert A+B\rvert\ge\lvert A\rvert+\lvert B\rvert-1$ である。相異なる $a,a'\in A$ をとる。lem-kn-stabilizer の 4 から $S(B)\subset S(A+B)=\{0\}$ なので $a'-a\notin S(B)$ で、$b+a'-a\notin B$ となる $b\in B$ がある。$B$ を $B-b+a$ に取り替えても、$A+B$ が平行移動されるだけで、$N$・$H$・示すべき不等式は変わらない。取り替えた後は $a\in A\cap B$、$a'\notin B$ なので
$$ \emptyset\neq A\cap B\subsetneq A $$
である。以下、結論が成り立たない、すなわち
$$ \lvert A+B\rvert\le\lvert A\rvert+\lvert B\rvert-2 $$
と仮定して矛盾を導く。この仮定を (0) と呼ぶ。
段階 4：条件 (S)．$A+B$ の空でない部分集合 $C$ と $L:=S(C)$（有限群である）について、
$$ \lvert C\rvert+\lvert L\rvert\ge\lvert A\cap B\rvert+\lvert(A\cup B)+L\rvert $$
を考え、これを条件 (S) と呼ぶ。$C_0:=(A\cap B)+(A\cup B)$ は lem-kn-etransform により $A+B$ に含まれ、組 $(A\cap B,A\cup B)$ の $N$ の値 $\lvert C_0\rvert+\lvert A\cap B\rvert$ は $N$ より小さい。帰納法の仮定から、$L_0:=S(C_0)$ について
$$ \lvert C_0\rvert\ge\lvert(A\cap B)+L_0\rvert+\lvert(A\cup B)+L_0\rvert-\lvert L_0\rvert\ge\lvert A\cap B\rvert+\lvert(A\cup B)+L_0\rvert-\lvert L_0\rvert $$
なので、$C_0$ は (S) をみたす。(S) をみたす $C$ のうち $\lvert S(C)\rvert$ が最小のものをとり、$L:=S(C)$ とおく。$L=\{0\}$ なら $\lvert A+B\rvert\ge\lvert C\rvert\ge\lvert A\cap B\rvert+\lvert A\cup B\rvert-1=\lvert A\rvert+\lvert B\rvert-1$ となり (0) に反するので、$L\neq\{0\}$ である。
段階 5：1 つの剰余類．$S(A+B)=\{0\}$ なので $A+B$ は $L$ で周期的でなく、$x+y+L\not\subset A+B$ となる $x\in A$、$y\in B$ がある。$Q:=x+y+L$ とおく。$C$ は $L$ で周期的なので、$C$ と $Q$ が交われば $Q\subset C\subset A+B$ となるから、$C\cap Q=\emptyset$ である。
$$ A_1:=A\cap(x+L),\quad B_1:=B\cap(y+L),\quad A_2:=A\cap(y+L),\quad B_2:=B\cap(x+L) $$
とおく。$x\in A_1$、$y\in B_1$ である。$A_i,B_i$ がともに空でない $i$ について、$A_i+B_i\subset Q$ なので $C_i:=C\cup(A_i+B_i)$ は $A+B$ の部分集合で、和集合は交わらない。$L_i:=S(A_i+B_i)$ とおく。
(a) $L_i\subsetneq L$ かつ $S(C_i)=L_i$ である。実際、$g\in L_i$ と $z\in A_i+B_i$ について $z,z+g\in Q$ なので $g\in L$ である。$L_i=L$ なら $A_i+B_i$ は $Q$ の空でない $L$ で周期的な部分集合なので $Q$ に等しく、$Q\not\subset A+B$ に反する。次に、$L$ の剰余類 $Q'$ と $C_i$ の共通部分は、$Q'\subset C$ なら $Q'$、$Q'=Q$ なら $A_i+B_i$、それ以外は空である。$g\in S(C_i)$ なら $C_i\cap(Q+g)=(C_i\cap Q)+g$ は剰余類 $Q+g$ の空でない真部分集合なので $Q+g=Q$、すなわち $g\in L$ で、$(A_i+B_i)+g=A_i+B_i$ から $g\in L_i$ である。逆に $C$ は $L$ で、したがって $L_i$ で周期的なので、$L_i\subset S(C_i)$ である。
(b) 次の不等式が成り立つ。
$$ \lvert(A\cup B)+L\rvert-\lvert(A\cup B)+L_i\rvert< \lvert L\rvert-\lvert A_i+L_i\rvert-\lvert B_i+L_i\rvert $$
これを (1) とする。実際、$\lvert L_i\rvert< \lvert L\rvert$ と $L$ の最小性から $C_i$ は (S) をみたさず、$\lvert C_i\rvert+\lvert L_i\rvert< \lvert A\cap B\rvert+\lvert(A\cup B)+L_i\rvert$ である。これと $C$ の (S) を合わせると、(1) の左辺は $\lvert C\rvert+\lvert L\rvert-\lvert C_i\rvert-\lvert L_i\rvert=\lvert L\rvert-\lvert A_i+B_i\rvert-\lvert L_i\rvert$ より小さい。組 $(A_i,B_i)$ の $N$ の値は、$A_i+B_i\subset(A+B)\setminus C$ と $\lvert A_i\rvert\le\lvert A\rvert$ から $N$ より小さく、帰納法の仮定から $\lvert A_i+B_i\rvert\ge\lvert A_i+L_i\rvert+\lvert B_i+L_i\rvert-\lvert L_i\rvert$ である。
(c) (1) の左辺の読み方：$L_i\subset L$ なので、$L$ の剰余類 $Q'$ について $((A\cup B)+L_i)\cap Q'=((A\cup B)\cap Q')+L_i$ であり、$(A\cup B)\cap Q'\neq\emptyset$ なら $Q'\subset(A\cup B)+L$ である。よって (1) の左辺は、$A\cup B$ と交わる各剰余類 $Q'$ についての $\lvert Q'\setminus(((A\cup B)\cap Q')+L_i)\rvert$ の和で、とくに $0$ 以上である。
段階 6：$A_2,B_2\neq\emptyset$ と $x+L\neq y+L$．$B_2=\emptyset$ なら $(A\cup B)\cap(x+L)=A_1$ で、(c) から $i=1$ の (1) の左辺は $\lvert L\rvert-\lvert A_1+L_1\rvert$ 以上となり、(1) に反する。$A_2=\emptyset$ なら $(A\cup B)\cap(y+L)=B_1$ で、同様に左辺は $\lvert L\rvert-\lvert B_1+L_1\rvert$ 以上となり反する。よって $A_2,B_2\neq\emptyset$ で、(1) は $i=1,2$ で成り立つ。$x+L=y+L$ なら $A_1=A_2$、$B_1=B_2$ で $(A\cup B)\cap(x+L)=A_1\cup B_1$ なので、左辺は $\lvert L\rvert-\lvert A_1+L_1\rvert-\lvert B_1+L_1\rvert$ 以上となり、(1) に反する。よって $x+L\neq y+L$ である。
段階 7：数え上げ．(c) から (1) の右辺は正である。$\lvert L\rvert$、$\lvert A_i+L_i\rvert$、$\lvert B_i+L_i\rvert$ はどれも $\lvert L_i\rvert$ の倍数なので（lem-kn-stabilizer の 2）、
$$ \lvert L\rvert\ge\lvert A_i+L_i\rvert+\lvert B_i+L_i\rvert+\lvert L_i\rvert\ge\lvert A_i\rvert+\lvert B_i\rvert+\lvert L_i\rvert $$
である。これを (2) とする。$U:=(x+L)\setminus(A_1\cup B_2)$、$V:=(y+L)\setminus(A_2\cup B_1)$ とおくと、$U,V$ は異なる剰余類にあって交わらず、$A\cup B$ とも交わらず、$(A\cup B)+L$ に含まれる。よって $\lvert(A\cup B)+L\rvert\ge\lvert A\cup B\rvert+\lvert U\rvert+\lvert V\rvert$ である。また $C$ と $A_i+B_i$ は $A+B$ の交わらない部分集合なので $\lvert C\rvert\le\lvert A+B\rvert-\lvert A_i+B_i\rvert$ である。$C$ の (S) と (0)、(b) の帰納法の不等式から
$$ \lvert L\rvert\ge\lvert A\cap B\rvert+\lvert A\cup B\rvert+\lvert U\rvert+\lvert V\rvert-\lvert A+B\rvert+\lvert A_i+B_i\rvert>\lvert U\rvert+\lvert V\rvert+\lvert A_i\rvert+\lvert B_i\rvert-\lvert L_i\rvert $$
である。これを (3) とする（$\lvert A\cap B\rvert+\lvert A\cup B\rvert-\lvert A+B\rvert\ge2$、$\lvert A_i+B_i\rvert\ge\lvert A_i\rvert+\lvert B_i\rvert-\lvert L_i\rvert$ による）。(2) と (3) を $i=1,2$ について足して 2 で割ると
$$ 2\lvert L\rvert>\lvert U\rvert+\lvert V\rvert+\lvert A_1\rvert+\lvert A_2\rvert+\lvert B_1\rvert+\lvert B_2\rvert $$
を得る。一方 $x+L=U\cup A_1\cup B_2$、$y+L=V\cup A_2\cup B_1$ なので、右辺は $2\lvert L\rvert$ 以上であり、矛盾する。$\square$

$H:=S(A+B)$ は位数 $p$ の群の部分群なので、Lagrangeの定理 により $H=\{0\}$ か $H=\mathbb{F}_p$ である。$H=\mathbb{F}_p$ なら $A+B=A+B+\mathbb{F}_p=\mathbb{F}_p$ で $\lvert A+B\rvert=p$ である。$H=\{0\}$ なら主定理は $\lvert A+B\rvert\ge\lvert A\rvert+\lvert B\rvert-1$ である。$\square$

$H:=S(A+B)$ とする。$H=\mathbb{Z}/n\mathbb{Z}$ なら $A+B=\mathbb{Z}/n\mathbb{Z}$ である。$H$ が真部分群なら、生成元は $H$ に入らないので $B\cap H=\{0\}$ で、$B\setminus\{0\}\subset(B+H)\setminus H$ である。$0\in B$ より $H\subset B+H$ なので $\lvert B+H\rvert\ge\lvert H\rvert+\lvert B\rvert-1$ となり、主定理から
$$ \lvert A+B\rvert\ge\lvert A+H\rvert+\lvert B+H\rvert-\lvert H\rvert\ge\lvert A\rvert+\lvert B\rvert-1 $$
である。$\square$

$S(A+B)$ は有限群（lem-kn-stabilizer の 3）なので、その元はすべて有限位数で、$S(A+B)=\{0\}$ である。主定理から結論が従う。$\square$