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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/30 08:11 UTC 版)

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

定理

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

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

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

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

となる。

弱い形の定理

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

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

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

$|A+B|=|A|=|A|+|B|-1\geq |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 をb₂-b₁ の形の元から生成される G の部分群とする。 B の元 b₀ を1つとれば H は $b-b_{0}(b\in B)$ の形の要素をすべて含むから $|B|\leq |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},\ldots ,a_{k}\in A$ がとれる。 また $0=b-b\in H$ より A + H = A であるが、 B が空でないことから $|A|<|G|$ より A + H は G とは一致せず、特に H も G とは一致しない。よって H は G の非自明な部分群であり

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

が成り立つ。

次に

$a_{1}+b_{2}-b_{1}\not \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\not \in A-e(g\not \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|\geq |A(e)+B(e)|$

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

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

が成り立つ。

ところで

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

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

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

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

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

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

参考文献

• 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