Kneser's theorem (combinatorics): Difference between revisions

Revision as of 22:28, 7 June 2020

Latest revision as of 18:23, 9 April 2021

(2 intermediate revisions by 2 users not shown)

Line 1:

{{short description|One of several related theorems regarding the sizes of certain sumsets in abelian groups}}

In the branch of mathematics known as [[additive combinatorics]], '''Kneser's theorem''' can refer to one of several related theorems regarding the sizes of certain [[sumset]]s in [[abelian group]]s. These are named after [[Martin Kneser]], who published them in 1953<ref name = Kneser53>{{cite journal | first=Martin | last=Kneser | title=Abschätzungen der asymptotischen Dichte von Summenmengen | language=German | journal=[[Math. Z.]] | volume=58 | year=1953 | pages=459–484 | doi=10.1007/BF01174162 | zbl=0051.28104 | s2cid=120456416 }}

</ref> and 1956.<ref name = Kneser56>{{cite journal | first=Martin | last=Kneser | title=Summenmengen in lokalkompakten abelschen Gruppen | language=German | journal=[[Math. Z.]] | volume=66 | year=1956 | pages=88–110 | doi=10.1007/BF01186598 | zbl=0073.01702 | s2cid=120125011 }}

</ref> They may be regarded as extensions of the [[Cauchy–Davenport theorem]], which also concerns sumsets in groups but is restricted to groups whose [[Order (group theory)|order]] is a [[prime number]].<ref name=GR143>{{harvtxt|Geroldinger|Ruzsa|2009|p=143}}</ref>

Line 13:

Let <math> G </math> be an [[abelian group]]. If <math> A </math> and <math> B </math> are nonempty finite subsets of <math> G </math> satisfying <math> |A + B| < |A| + |B| </math> and <math> H </math> is the stabilizer of <math> A + B </math>, then <math>\begin{align} |A+B| &= |A+H| + |B+H| - |H|. \end{align} </math>

This statement is a corollary of the statement for LCA groups below, obtained by specializing to the case where the ambient group is discrete. A self-contained proof is provided in Nathanson's textbook.<ref> {{cite book | first=Melvyn B. | last=Nathanson | authorlinkauthor-link = Melvyn B. Nathanson | title=Additive Number Theory: Inverse Problems and the Geometry of Sumsets | volume=165 | series=[[Graduate Texts in Mathematics]] | publisher=[[Springer-Verlag]] | year=1996 | isbn=0-387-94655-1 | zbl=0859.11003 | pages=109–132 }} </ref>.

===Lower asymptotic density in the natural numbers===

Line 40:

can be found when <math> G </math> is the torus <math> \mathbb T:= \mathbb R/\mathbb Z </math> and <math> A </math> and <math> B </math> are intervals. Satz 2 of Kneser's 1956 article<ref name=Kneser56/> says that all examples of sets satisfying equation ({{EquationNote|1}}) with non-null summands are obvious modifications of these. To be precise: if <math> G </math> is a connected compact abelian group with Haar measure <math> m, </math> <math> A </math> and <math> B </math> are <math> m </math>-measurable subsets of <math> G </math> satisfying <math> m(A)>0, m(B)>0 </math>, and equation ({{EquationNote|1}}), then there is a continuous surjective homomorphism <math> \phi: G \to \mathbb T </math> and there are closed intervals <math> I </math>, <math> J </math> in <math> \mathbb T </math> such that <math>A \subseteq \phi^{-1}(I)</math>, <math>B \subseteq \phi^{-1}(J)</math>, <math>m(A) = m (\phi^{-1}(I))</math>, and <math> m(B) = m(\phi^{-1}(J))</math>.

==Notes==

Line 46 ⟶ 45:

==References==

* {{cite book | editor1-last=Geroldinger | editor1-first=Alfred | editor2-last=Ruzsa | editor2-first=Imre Z. | editor2-link = Imre Z. Ruzsa | others=Elsholtz, C.; Freiman, G.; Hamidoune, Y. O.; Hegyvári, N.; Károlyi, G.; Nathanson, M.; [[József Solymosi|Solymosi, J.]]; Stanchescu, Y. With a foreword by Javier Cilleruelo, Marc Noy and Oriol Serra (Coordinators of the DocCourse) | title=Combinatorial number theory and additive group theory | series=Advanced Courses in Mathematics CRM Barcelona | ___location=Basel | publisher=Birkhäuser | year=2009 | isbn=978-3-7643-8961-1 | zbl=1177.11005|ref=harv }}

*{{cite book | first=David | last=Grynkiewicz| title=Structural Additive Theory | volume=30| series=[[Developments in Mathematics]] | publisher=[[Springer Science+Business Media|Springer]] | year=2013 | isbn=978-3-319-00415-0 | zbl=1368.11109 | pages=61 |ref=Grynk }}

* {{citation | first1=Terence | last1=Tao | author1-link=Terence Tao | first2=Van H. | last2=Vu | title=Additive Combinatorics | year=2010 | publisher=[[Cambridge University Press]] | place=[[Cambridge]] | isbn=978-0-521-13656-3 | zbl=1179.11002 }}