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

加法的組合せ論におけるクネーザーの定理（Kneser's theorem）は群の部分集合の加法的性質に関する定理で、整数列のシュニレルマン密度に関するマンの定理（シュニレルマン密度の記事を参照）に対応する定理である。
マルティン・クネーザーによって（整数列の下極限密度に関する定理と共に）1953年から1956年にかけて証明され、Kempermanによって下のわかりやすい形にまとめられた。
定理.
"G" をアーベル群、"A", "B" を "G" の空でない有限部分集合とする。
とおく（この "H" は "G" の部分群である）。
formula_2 ならば
となる。
弱い形の定理.
となる "G" の非自明な部分群 "H" が存在することは比較的簡単に証明できる。
formula_5 に関する数学的帰納法で証明する。
formula_6 のとき、どのような部分群 "H" をとっても
である。
formula_8 として、定理が formula_9 となるような空でない有限部分集合 formula_10 に対して成り立つとする。
任意の formula_11 に対して
が成り立つとする。このとき "H" を の形の元から生成される "G" の部分群とする。
"B" の元 "b"0 を1つとれば "H" は formula_13 の形の要素をすべて含むから
formula_14
かつ
formula_15 に対して
となる formula_17 がとれる。
また formula_18 より "A" + "H" = "A" であるが、 "B" が空でないことから formula_19 より
"A" + "H" は "G" とは一致せず、特に "H" も "G" とは一致しない。よって "H" は "G" の非自明な部分群であり
が成り立つ。
次に
が成り立つ formula_11 がとれるとする。
formula_23とおく。
かつ
となる。そこで
とおく。
formula_27 より
が成り立つ。またformula_29 ならば formula_30 となることから formula_31 つまり
が成り立つ。
ところで
より formula_34 だから formula_35 である。よって帰納法の仮定より
となる "G" の非自明部分群 "H" がとれる。上記の不等式を使って
がいえる。よって帰納法により弱い形の定理が証明される。