Kneser's theorem (combinatorics) - Alchetron, the free social encyclopedia

In mathematics, Kneser's theorem is an inequality among the sizes of certain sumsets in abelian groups. It belongs to the field of additive combinatorics, and is named after Martin Kneser, who published it in 1953. It may be regarded as an extension of the Cauchy–Davenport theorem, which also concerns sumsets in groups but is restricted to groups whose order is a prime number.

Statement

Let G be an abelian group and A, B finite non-empty subsets. If |A| + |B| ≤ |G| then there is a finite subgroup H of G such that

| A + B | ≥ | A + H | + | B + H | − | H | ≥ | A | + | B | − | H | .

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

H = { g ∈ G : g + ( A + B ) = ( A + B ) } .

References

Kneser's theorem (combinatorics) Wikipedia

(Text) CC BY-SA