加法的組合せ論 におけるクネーザーの定理（Kneser's theorem）は群 の部分集合 の加法的性質に関する定理で、整数列のシュニレルマン密度 に関するマンの定理（シュニレルマン密度の記事を参照）に対応する定理である。
マルティン・クネーザー によって（整数列の下極限密度に関する定理と共に）1953年から1956年にかけて証明され[ 1] [ 2] [ 3] [ 4]
G をアーベル群 、A , B を G の空でない有限部分集合とする。
H
=
{
h
∈
G
|
h
+
(
A
+
B
)
=
(
A
+
B
)
}
{\displaystyle H=\lbrace h\in G|h+(A+B)=(A+B)\rbrace }
とおく（この H は G の部分群 である）。
|
A
|
+
|
B
|
≤
|
G
|
{\displaystyle |A|+|B|\leq |G|}
|
A
+
B
|
≥
|
A
+
H
|
+
|
B
+
H
|
−
|
H
|
≥
|
A
|
+
|
B
|
−
|
H
|
{\displaystyle |A+B|\geq |A+H|+|B+H|-|H|\geq |A|+|B|-|H|}
となる[ 5]
|
A
+
B
|
≥
|
A
|
+
|
B
|
−
|
H
|
{\displaystyle |A+B|\geq |A|+|B|-|H|}
となる G の非自明な部分群 H が存在することは比較的簡単に証明できる[ 2] [ 6]
|
B
|
{\displaystyle |B|}
数学的帰納法 で証明する。
|
B
|
=
1
{\displaystyle |B|=1}
H をとっても
|
A
+
B
|
=
|
A
|
=
|
A
|
+
|
B
|
−
1
≥
|
A
|
+
|
B
|
−
|
H
|
{\displaystyle |A+B|=|A|=|A|+|B|-1\geq |A|+|B|-|H|}
である。
|
B
|
>
1
{\displaystyle |B|>1}
|
B
′
|
<
|
B
|
{\displaystyle |B^{\prime }|<|B|}
A
′
,
B
′
{\displaystyle A^{\prime },B^{\prime }}
a
1
∈
A
,
b
1
,
b
2
∈
B
{\displaystyle a_{1}\in A,b_{1},b_{2}\in B}
a
1
+
b
2
−
b
1
∈
A
{\displaystyle a_{1}+b_{2}-b_{1}\in A}
が成り立つとする。このとき H をb 2 -b 1 G の部分群とする。
B の元 b 0 を1つとれば H は
b
−
b
0
(
b
∈
B
)
{\displaystyle b-b_{0}(b\in B)}
|
B
|
≤
|
H
|
{\displaystyle |B|\leq |H|}
a
1
∈
A
,
b
1
,
2
−
b
1
,
1
+
b
2
,
2
−
b
2
,
1
+
⋯
+
b
k
,
2
−
b
k
,
1
∈
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}
a
1
+
b
1
,
2
−
b
1
,
1
+
b
2
,
2
−
b
2
,
1
+
⋯
+
b
k
,
2
−
b
k
,
1
=
a
2
+
b
2
,
2
−
b
2
,
1
+
⋯
+
b
k
,
2
−
b
k
,
1
=
⋯
=
a
k
∈
A
{\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}
となる
a
2
,
…
,
a
k
∈
A
{\displaystyle a_{2},\ldots ,a_{k}\in A}
0
=
b
−
b
∈
H
{\displaystyle 0=b-b\in H}
A + H = A であるが、 B が空でないことから
|
A
|
<
|
G
|
{\displaystyle |A|<|G|}
A + H は G とは一致せず、特に H も G とは一致しない。よって H は G の非自明な部分群であり
|
A
+
B
|
≥
|
A
|
≥
|
A
|
+
|
B
|
−
|
H
|
{\displaystyle |A+B|\geq |A|\geq |A|+|B|-|H|}
が成り立つ。
次に
a
1
+
b
2
−
b
1
∉
A
{\displaystyle a_{1}+b_{2}-b_{1}\not \in A}
が成り立つ
a
1
∈
A
,
b
1
,
b
2
∈
B
{\displaystyle a_{1}\in A,b_{1},b_{2}\in B}
e
=
b
1
−
a
1
{\displaystyle e=b_{1}-a_{1}}
b
1
=
a
1
−
e
∈
A
−
e
{\displaystyle b_{1}=a_{1}-e\in A-e}
かつ
b
2
=
g
−
e
∉
A
−
e
(
g
∉
A
)
{\displaystyle b_{2}=g-e\not \in A-e(g\not \in A)}
となる。そこで
A
(
e
)
=
A
∪
(
B
+
e
)
,
B
(
e
)
=
B
∩
(
A
−
e
)
{\displaystyle A(e)=A\cup (B+e),B(e)=B\cap (A-e)}
とおく。
A
(
e
)
+
B
(
e
)
⊂
(
A
+
B
)
∪
(
(
B
+
e
)
+
(
A
−
e
)
)
=
A
+
B
{\displaystyle A(e)+B(e)\subset (A+B)\cup ((B+e)+(A-e))=A+B}
|
A
+
B
|
≥
|
A
(
e
)
+
B
(
e
)
|
{\displaystyle |A+B|\geq |A(e)+B(e)|}
が成り立つ。また
g
∈
B
∖
B
(
e
)
=
B
∖
(
A
−
e
)
{\displaystyle g\in B\backslash B(e)=B\backslash (A-e)}
g
+
e
∈
(
B
+
e
)
∖
A
=
A
(
e
)
∖
A
{\displaystyle g+e\in (B+e)\backslash A=A(e)\backslash A}
|
B
|
−
|
B
(
e
)
|
≤
|
A
(
e
)
|
−
|
A
|
{\displaystyle |B|-|B(e)|\leq |A(e)|-|A|}
|
A
(
e
)
|
+
|
B
(
e
)
|
≥
|
A
|
+
|
B
|
{\displaystyle |A(e)|+|B(e)|\geq |A|+|B|}
が成り立つ。
ところで
b
2
=
g
−
e
∉
A
−
e
(
g
∉
A
)
{\displaystyle b_{2}=g-e\not \in A-e(g\not \in A)}
より
b
2
∉
B
(
e
)
{\displaystyle b_{2}\not \in B(e)}
|
B
(
e
)
|
<
|
B
|
{\displaystyle |B(e)|<|B|}
|
A
(
e
)
+
B
(
e
)
|
≥
|
A
(
e
)
|
+
|
B
(
e
)
|
−
|
H
|
{\displaystyle |A(e)+B(e)|\geq |A(e)|+|B(e)|-|H|}
となる G の非自明部分群 H がとれる。上記の不等式を使って
|
A
+
B
|
≥
|
A
(
e
)
+
B
(
e
)
|
≥
|
A
(
e
)
|
+
|
B
(
e
)
|
−
|
H
|
≥
|
A
|
+
|
B
|
−
|
H
|
{\displaystyle |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 
