クネーザーの定理 (組み合わせ論)

加法的組合せ論におけるクネーザーの定理（Kneser's theorem）は群の部分集合の加法的性質に関する定理で、整数列のシュニレルマン密度に関するマンの定理（シュニレルマン密度の記事を参照）に対応する定理である。 マルティン・クネーザーによって（整数列の下極限密度に関する定理と共に）1953年から1956年にかけて証明され、Kempermanによって下のわかりやすい形にまとめられた。

定理

G をアーベル群、A, B を G の空でない有限部分集合とする。

$H=\{h\in G|h+(A+B)=(A+B)\}$

とおく（この H は G の部分群である）。 $|A|+|B|\le |G|$ ならば

$|A+B|\ge |A+H|+|B+H|-|H|\ge |A|+|B|-|H|$

となる。

弱い形の定理

$|A+B|\ge |A|+|B|-|H|$

となる G の非自明な部分群 H が存在することは比較的簡単に証明できる。 $|B|$ に関する数学的帰納法で証明する。

$|B|=1$ のとき、どのような部分群 H をとっても

$|A+B|=|A|=|A|+|B|-1\ge |A|+|B|-|H|$

である。

$|B|>1$ として、定理が $|B^{\prime }|<|B|$ となるような空でない有限部分集合 $A^{\prime },B^{\prime }$ に対して成り立つとする。 任意の $a_1\in A,b_1,b_2\in B$ に対して

$a_1+b_2-b_1\in A$

が成り立つとする。このとき H をテンプレート:Math の形の元から生成される G の部分群とする。 B の元 b₀ を1つとれば H は $b-b_0(b\in B)$ の形の要素をすべて含むから $|B|\le |H|$ かつ $a_1\in A,b_{1,2}-b_{1,1}+b_{2,2}-b_{2,1}+\cdots +b_{k,2}-b_{k,1}\in H$ に対して

$a_1+b_{1,2}-b_{1,1}+b_{2,2}-b_{2,1}+\cdots +b_{k,2}-b_{k,1}=a_2+b_{2,2}-b_{2,1}+\cdots +b_{k,2}-b_{k,1}=\cdots =a_k\in A$

となる $a_2,\dots ,a_k\in A$ がとれる。 また $0=b-b\in H$ より A + H = A であるが、 B が空でないことから $|A|<|G|$ より A + H は G とは一致せず、特に H も G とは一致しない。よって H は G の非自明な部分群であり

$|A+B|\ge |A|\ge |A|+|B|-|H|$

が成り立つ。

次に

$a_1+b_2-b_1\in ̸A$

が成り立つ $a_1\in A,b_1,b_2\in B$ がとれるとする。 $e=b_1-a_1$とおく。

$b_1=a_1-e\in A-e$

かつ

$b_2=g-e\in ̸A-e(g\in ̸A)$

となる。そこで

$A(e)=A\cup (B+e),B(e)=B\cap (A-e)$

とおく。

$A(e)+B(e)\subset (A+B)\cup ((B+e)+(A-e))=A+B$ より

$|A+B|\ge |A(e)+B(e)|$

が成り立つ。また$g\in B\mathrm{\setminus }B(e)=B\mathrm{\setminus }(A-e)$ ならば $g+e\in (B+e)\mathrm{\setminus }A=A(e)\mathrm{\setminus }A$ となることから $|B|-|B(e)|\le |A(e)|-|A|$ つまり

$|A(e)|+|B(e)|\ge |A|+|B|$

が成り立つ。

ところで

$b_2=g-e\in ̸A-e(g\in ̸A)$

より $b_2\in ̸B(e)$ だから $|B(e)|<|B|$ である。よって帰納法の仮定より

$|A(e)+B(e)|\ge |A(e)|+|B(e)|-|H|$

となる G の非自明部分群 H がとれる。上記の不等式を使って

$|A+B|\ge |A(e)+B(e)|\ge |A(e)|+|B(e)|-|H|\ge |A|+|B|-|H|$

がいえる。よって帰納法により弱い形の定理が証明される。

参考文献

• テンプレート:Cite book
• テンプレート:Cite book