Kneser's theorem (combinatorics)

Kneser's theorem (combinatorics) 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 sumsets in abelian groups. These are named after Martin Kneser, who published them in 1953[1] and 1956.[2] They may be regarded as extensions of the Cauchy–Davenport theorem, which also concerns sumsets in groups but is restricted to groups whose order is a prime number.[3] 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.

Contents 1 Strict inequality 1.1 Cardinality 1.2 Lower asymptotic density in the natural numbers 1.3 Haar measure in locally compact abelian (LCA) groups 2 Equality in connected compact abelian groups 3 Notes 4 References Strict inequality If {displaystyle G} is an abelian group and {displaystyle C} is a subset of {displaystyle G} , the group {displaystyle H(C):={gin G:g+C=C}} is the stabilizer of {displaystyle C} .

Cardinality Let {displaystyle G} be an abelian group. If {displaystyle A} and {displaystyle B} are nonempty finite subsets of {displaystyle G} satisfying {displaystyle |A+B|<|A|+|B|} and {displaystyle H} is the stabilizer of {displaystyle A+B} , then {displaystyle {begin{aligned}|A+B|&=|A+H|+|B+H|-|H|.end{aligned}}} 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.[4] Lower asymptotic density in the natural numbers The main result of Kneser's 1953 article[1] is a variant of Mann's theorem on Schnirelmann density. If {displaystyle C} is a subset of {displaystyle mathbb {N} } , the lower asymptotic density of {displaystyle C} is the number {displaystyle {underline {d}}(C):=liminf _{nto infty }{frac {|Ccap {1,dots ,n}|}{n}}} . Kneser's theorem for lower asymptotic density states that if {displaystyle A} and {displaystyle B} are subsets of {displaystyle mathbb {N} } satisfying {displaystyle {underline {d}}(A+B)<{underline {d}}(A)+{underline {d}}(B)} , then there is a natural number {displaystyle k} such that {displaystyle H:=kmathbb {N} cup {0}} satisfies the following two conditions: {displaystyle (A+B+H)setminus (A+B)} is finite, and {displaystyle {underline {d}}(A+B)={underline {d}}(A+H)+{underline {d}}(B+H)-{underline {d}}(H).} Note that {displaystyle A+Bsubseteq A+B+H} , since {displaystyle 0in H} . Haar measure in locally compact abelian (LCA) groups Let {displaystyle G} be an LCA group with Haar measure {displaystyle m} and let {displaystyle m_{*}} denote the inner measure induced by {displaystyle m} (we also assume {displaystyle G} is Hausdorff, as usual). We are forced to consider inner Haar measure, as the sumset of two {displaystyle m} -measurable sets can fail to be {displaystyle m} -measurable. Satz 1 of Kneser's 1956 article[2] can be stated as follows: If {displaystyle A} and {displaystyle B} are nonempty {displaystyle m} -measurable subsets of {displaystyle G} satisfying {displaystyle m_{*}(A+B)0,m(B)>0} , and equation (1), then there is a continuous surjective homomorphism {displaystyle phi :Gto mathbb {T} } and there are closed intervals {displaystyle I} , {displaystyle J} in {displaystyle mathbb {T} } such that {displaystyle Asubseteq phi ^{-1}(I)} , {displaystyle Bsubseteq phi ^{-1}(J)} , {displaystyle m(A)=m(phi ^{-1}(I))} , and {displaystyle m(B)=m(phi ^{-1}(J))} .

Notes ^ Jump up to: a b Kneser, Martin (1953). "Abschätzungen der asymptotischen Dichte von Summenmengen". Math. Z. (in German). 58: 459–484. doi:10.1007/BF01174162. S2CID 120456416. Zbl 0051.28104. ^ Jump up to: a b c Kneser, Martin (1956). "Summenmengen in lokalkompakten abelschen Gruppen". Math. Z. (in German). 66: 88–110. doi:10.1007/BF01186598. S2CID 120125011. Zbl 0073.01702. ^ Geroldinger & Ruzsa (2009, p. 143) ^ Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. Vol. 165. Springer-Verlag. pp. 109–132. ISBN 0-387-94655-1. Zbl 0859.11003. References Geroldinger, Alfred; Ruzsa, Imre Z., eds. (2009). Combinatorial number theory and additive group theory. Advanced Courses in Mathematics CRM Barcelona. Elsholtz, C.; Freiman, G.; Hamidoune, Y. O.; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Solymosi, J.; Stanchescu, Y. With a foreword by Javier Cilleruelo, Marc Noy and Oriol Serra (Coordinators of the DocCourse). Basel: Birkhäuser. ISBN 978-3-7643-8961-1. Zbl 1177.11005. Grynkiewicz, David (2013). Structural Additive Theory. Developments in Mathematics. Vol. 30. Springer. p. 61. ISBN 978-3-319-00415-0. Zbl 1368.11109. Tao, Terence; Vu, Van H. (2010), Additive Combinatorics, Cambridge: Cambridge University Press, ISBN 978-0-521-13656-3, Zbl 1179.11002 Categories: Theorems in combinatoricsSumsets