Jump to content

Kneser's theorem (combinatorics)

From Wikipedia, the free encyclopedia

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.

Strict inequality

[edit]

If is an abelian group and is a subset of , the group is the stabilizer of .

Cardinality

[edit]

Let be an abelian group. If and are nonempty finite subsets of satisfying and is the stabilizer of , then

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

[edit]

The main result of Kneser's 1953 article[1] is a variant of Mann's theorem on Schnirelmann density.

If is a subset of , the lower asymptotic density of is the number . Kneser's theorem for lower asymptotic density states that if and are subsets of satisfying , then there is a natural number such that satisfies the following two conditions:

is finite,

and

Note that , since .

Haar measure in locally compact abelian (LCA) groups

[edit]

Let be an LCA group with Haar measure and let denote the inner measure induced by (we also assume is Hausdorff, as usual). We are forced to consider inner Haar measure, as the sumset of two -measurable sets can fail to be -measurable. Satz 1 of Kneser's 1956 article[2] can be stated as follows:

If and are nonempty -measurable subsets of satisfying , then the stabilizer is compact and open. Thus is compact and open (and therefore -measurable), being a union of finitely many cosets of . Furthermore,

Equality in connected compact abelian groups

[edit]

Because connected groups have no proper open subgroups, the preceding statement immediately implies that if is connected, then for all -measurable sets and . Examples where

(1)

can be found when is the torus and and are intervals. Satz 2 of Kneser's 1956 article[2] says that all examples of sets satisfying equation (1) with non-null summands are obvious modifications of these. To be precise: if is a connected compact abelian group with Haar measure and are -measurable subsets of satisfying , and equation (1), then there is a continuous surjective homomorphism and there are closed intervals , in such that , , , and .

Notes

[edit]
  1. ^ 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.
  2. ^ 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.
  3. ^ Geroldinger & Ruzsa (2009, p. 143)
  4. ^ 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

[edit]