Kneser's theorem (combinatorics): Difference between revisions

Revision as of 22:02, 30 March 2013

Latest revision as of 18:23, 9 April 2021

(20 intermediate revisions by 10 users not shown)

Line 1:

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

In mathematics,the inbranch theof fieldmathematics ofknown as [[additive combinatorics]], '''Kneser's theorem''', namedcan afterrefer [[Martinto Kneser]],one isof aseveral statementrelated abouttheorems regarding the sizes of certain [[Sumset|set additionsumset]]s in [[finiteabelian 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. ZeitschrZ.]] | volume=58 | year=1953 | pages=459–484 | doi=10.1007/BF01174162 | zbl=0051.28104 | s2cid=120456416 }}

</ref>

</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>

The first three statements deal with sumsets whose size (in various senses) is strictly smaller than the sum of the size of the summands. The last statement deals with the case of equality for Haar measure in connected compact abelian groups.

==Statement==

Let ''G'' be a non-trivial [[abelian group]] and ''A'', ''B'' finite non-empty subsets. If |''A''| + |''B''| ≤ |''G''| then there is a finite subgroup ''H'' of ''G'' such that<ref>{{harvnb|Tao|Vu|2010|loc=pg. 200, Theorem 5.5}}</ref>

==Strict inequality==

:<math>\begin{align} |A+B| &\ge |A+H| + |B+H| - |H| \\ &\ge |A| + |B| - |H|. \end{align} </math>

If <math> G </math> is an abelian group and <math> C </math> is a subset of <math> G </math>, the group <math> H(C):= \{g\in G : g + C = C\} </math> is the ''stabilizer'' of <math> C </math>.

The subgroup ''H'' can be taken to be the ''stabiliser'' of ''A''+''B''

===Cardinality===

:<math> H = \lbrace g \in G : g + (A+B) = (A+B) \rbrace. </math>

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 | author-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===

The main result of Kneser's 1953 article<ref name=Kneser53/> is a variant of [[Mann's theorem]] on [[Schnirelmann density]].

If <math> C </math> is a subset of <math>\mathbb N</math>, the ''lower asymptotic density'' of <math>C</math> is the number <math>\underline{d}(C) := \liminf_{n\to\infty} \frac{|C \cap \{1,\dots, n\}|}{n}</math>. Kneser's theorem for lower asymptotic density states that if <math>A</math> and <math>B</math> are subsets of <math>\mathbb N</math> satisfying <math>\underline{d}(A+B) < \underline{d}(A) + \underline{d}(B)</math>, then there is a natural number <math>k</math> such that <math>H:=k \mathbb N \cup \{0\}</math> satisfies the following two conditions:

:<math> (A+B+H)\setminus (A+B) </math> is finite,

and

:<math> \underline{d}(A+B) = \underline{d}(A+H) + \underline{d}(B+H) - \underline{d}(H). </math>

Note that <math> A+B \subseteq A+B+H </math>, since <math> 0\in H </math>.

===Haar measure in locally compact abelian (LCA) groups===

Let <math> G </math> be an LCA group with [[Haar measure]] <math> m </math> and let <math> m_* </math> denote the [[inner measure]] induced by <math> m </math> (we also assume <math> G </math> is Hausdorff, as usual). We are forced to consider inner Haar measure, as the sumset of two <math> m </math>-measurable sets can fail to be <math> m </math>-measurable. Satz 1 of Kneser's 1956 article<ref name=Kneser56/> can be stated as follows:

If <math> A </math> and <math> B </math> are nonempty <math>m</math>-measurable subsets of <math> G </math> satisfying <math> m_*(A + B) < m(A) + m(B) </math>, then the stabilizer <math> H:=H(A+B) </math> is compact and open. Thus <math> A+B </math> is compact and open (and therefore <math> m </math>-measurable), being a union of finitely many cosets of <math> H </math>. Furthermore, <math>m(A+B) = m(A+H) + m(B+H) - m(H). </math>

==Equality in connected compact abelian groups==

Because connected groups have no proper open subgroups, the preceding statement immediately implies that if <math> G </math> is connected, then <math> m_*(A + B) \geq \min\{m(A) + m(B), m(G)\} </math> for all <math> m </math>-measurable sets <math> A </math> and <math> B </math>. Examples where

{{NumBlk|:|<math>m_*(A+B) = m(A) + m(B) < m(G) </math>|{{EquationRef|1}}}}

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 15 ⟶ 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}}

* {{cite book | first=Melvyn B. | last=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 }}

*{{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 }}

[[Category:Theorems in combinatorics]]

[[Category:Sumsets]]

{{combin-stub}}