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

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

定理

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

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

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

${\displaystyle |A+B|\geq |A+H|+|B+H|-|H|\geq |A|+|B|-|H|}$

となる[5]。

弱い形の定理

${\displaystyle |A+B|\geq |A|+|B|-|H|}$

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

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

${\displaystyle |A+B|=|A|=|A|+|B|-1\geq |A|+|B|-|H|}$

である。

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

${\displaystyle a_{1}+b_{2}-b_{1}\in A}$

が成り立つとする。このとき H をb₂-b₁ の形の元から生成される G の部分群とする。 B の元 b₀ を1つとれば H は ${\displaystyle b-b_{0}(b\in B)}$ の形の要素をすべて含むから ${\displaystyle |B|\leq |H|}$ かつ ${\displaystyle 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}$ に対して

${\displaystyle 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}$

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

${\displaystyle |A+B|\geq |A|\geq |A|+|B|-|H|}$

が成り立つ。

次に

${\displaystyle a_{1}+b_{2}-b_{1}\not \in A}$

が成り立つ ${\displaystyle a_{1}\in A,b_{1},b_{2}\in B}$ がとれるとする。 ${\displaystyle e=b_{1}-a_{1}}$とおく。

${\displaystyle b_{1}=a_{1}-e\in A-e}$

かつ

${\displaystyle b_{2}=g-e\not \in A-e(g\not \in A)}$

となる。そこで

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

とおく。

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

${\displaystyle |A+B|\geq |A(e)+B(e)|}$

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

${\displaystyle |A(e)|+|B(e)|\geq |A|+|B|}$

が成り立つ。

ところで

${\displaystyle b_{2}=g-e\not \in A-e(g\not \in A)}$

より ${\displaystyle b_{2}\not \in B(e)}$ だから ${\displaystyle |B(e)|<|B|}$ である。よって帰納法の仮定より

${\displaystyle |A(e)+B(e)|\geq |A(e)|+|B(e)|-|H|}$

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

${\displaystyle |A+B|\geq |A(e)+B(e)|\geq |A(e)|+|B(e)|-|H|\geq |A|+|B|-|H|}$

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

脚注

1. Kneser, Martin (1953). “Abschätzungen der asymptotischen Dichte von Summenmengen” (German). Mathematische Zeitschrift / 58: 459-484. doi:10.1007/BF01174162. MR0056632. 
2. ^ Kneser, Martin (1955). “Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen” (German). Mathematische Zeitschrift 61: 429-434. doi:10.1007/BF01181357. 
3. Kneser, Martin (1956). “Summenmengen in lokalkompakten abelschen Gruppen” (German). Mathematische Zeitschrift 66: 88-110. doi:10.1007/BF01186598. 
4. Kemperman, J. H. B. (1960). “On small sumsets in an abelian group”. Acta Mathematica 103: 63-88. doi:10.1007/BF02546525. MR0110747. 
5. Tao & Vu 2010, Theorem 5.5 および Nathanson 1996, Theorem 4.3
6. Nathanson 1996, Theorem 4.1

参考文献

• Tao, Terence; Vu, Van H. (2010). Additive Combinatorics. Cambridge studies in advanced mathematics. 105. Cambridge: Cambridge University Press. ISBN 978-0-521-17012-3 
• Nathanson, Melvyn B. (1996). Additive Number Theory, Inverse Problems and Geometry of Sumsets. Graduate Texts in Mathematics. 165. Cambridge: Springer Verlag. ISBN 978-0-521-17012-3