「クネーザーの定理 (組み合わせ論)」の版間の差分
North land (会話 | 投稿記録) m Category:エポニムを追加 (HotCat使用) |
|||
1行目: | 1行目: | ||
[[加法的組合せ論]]におけるクネーザーの定理(Kneser's theorem)は[[群]]の[[部分集合]]の加法的性質に関する定理で、整数列の[[シュニレルマン密度]]に関するマンの定理(シュニレルマン密度の記事を参照)に対応する定理である。 |
[[加法的組合せ論]]におけるクネーザーの定理(Kneser's theorem)は[[群]]の[[部分集合]]の加法的性質に関する定理で、整数列の[[シュニレルマン密度]]に関するマンの定理(シュニレルマン密度の記事を参照)に対応する定理である。 |
||
[[マルティン・クネーザー]]によって(整数列の下極限密度に関する定理と共に)1953年から1956年にかけて証明され<ref>{{cite journal | first=Martin | last=Kneser | title=Abschätzungen der asymptotischen Dichte von Summenmengen | language=German | journal=Mathematische Zeitschrift /| volume=58 | year=1953 | pages=459-484 | doi=10.1007/BF01174162 | |
[[マルティン・クネーザー]]によって(整数列の下極限密度に関する定理と共に)1953年から1956年にかけて証明され<ref>{{cite journal | first=Martin | last=Kneser | title=Abschätzungen der asymptotischen Dichte von Summenmengen | language=German | journal=Mathematische Zeitschrift /| volume=58 | year=1953 | pages=459-484 | doi=10.1007/BF01174162 | mr=0056632 }}</ref><ref name="Kneser1955">{{cite journal | first=Martin | last=Kneser | title=Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen | language=German | journal=Mathematische Zeitschrift | volume=61 | year=1955 | pages=429-434 | doi=10.1007/BF01181357 | MR0068536 }}</ref><ref name="Kneser1956">{{cite journal | first=Martin | last=Kneser | title=Summenmengen in lokalkompakten abelschen Gruppen | language=German | journal=Mathematische Zeitschrift | volume=66 | year=1956 | pages=88-110 | doi=10.1007/BF01186598 | MR0081438 }}</ref>、Kempermanによって下のわかりやすい形にまとめられた<ref>{{cite journal | first=J. H. B. | last=Kemperman | title=On small sumsets in an abelian group | journal=Acta Mathematica | volume=103 | year=1960 | pages=63-88 | doi=10.1007/BF02546525 | mr=0110747 }}</ref>。 |
||
== 定理 == |
== 定理 == |
2020年1月25日 (土) 18:20時点における版
加法的組合せ論におけるクネーザーの定理(Kneser's theorem)は群の部分集合の加法的性質に関する定理で、整数列のシュニレルマン密度に関するマンの定理(シュニレルマン密度の記事を参照)に対応する定理である。 マルティン・クネーザーによって(整数列の下極限密度に関する定理と共に)1953年から1956年にかけて証明され[1][2][3]、Kempermanによって下のわかりやすい形にまとめられた[4]。
定理
G をアーベル群、A, B を G の空でない有限部分集合とする。
とおく(この H は G の部分群である)。 ならば
となる[5]。
弱い形の定理
となる G の非自明な部分群 H が存在することは比較的簡単に証明できる[2][6]。 に関する数学的帰納法で証明する。
のとき、どのような部分群 H をとっても
である。
として、定理が となるような空でない有限部分集合 に対して成り立つとする。 任意の に対して
が成り立つとする。このとき H をb2-b1 の形の元から生成される G の部分群とする。 B の元 b0 を1つとれば H は の形の要素をすべて含むから かつ に対して
となる がとれる。 また より A + H = A であるが、 B が空でないことから より A + H は G とは一致せず、特に H も G とは一致しない。よって H は G の非自明な部分群であり
が成り立つ。
次に
が成り立つ がとれるとする。 とおく。
かつ
となる。そこで
とおく。
より
が成り立つ。また ならば となることから つまり
が成り立つ。
ところで
より だから である。よって帰納法の仮定より
となる G の非自明部分群 H がとれる。上記の不等式を使って
がいえる。よって帰納法により弱い形の定理が証明される。
脚注
- ^ Kneser, Martin (1953). “Abschätzungen der asymptotischen Dichte von Summenmengen” (German). Mathematische Zeitschrift / 58: 459-484. doi:10.1007/BF01174162. MR0056632.
- ^ a b 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.
- ^ Kneser, Martin (1956). “Summenmengen in lokalkompakten abelschen Gruppen” (German). Mathematische Zeitschrift 66: 88-110. doi:10.1007/BF01186598.
- ^ Kemperman, J. H. B. (1960). “On small sumsets in an abelian group”. Acta Mathematica 103: 63-88. doi:10.1007/BF02546525. MR0110747.
- ^ Tao & Vu 2010, Theorem 5.5 および Nathanson 1996, Theorem 4.3
- ^ 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