Kneser's theorem (combinatorics)

Last updated April 10, 2021

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]

Strict inequality

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

Cardinality

Let $G$ be an abelian group. If $A$ and $B$ are nonempty finite subsets of $G$ satisfying $|A+B|<|A|+|B|$ and $H$ is the stabilizer of $A+B$ , then ${\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 $C$ is a subset of $\mathbb {N}$ , the lower asymptotic density of $C$ is the number ${\underline {d}}(C):=\liminf _{n\to \infty }{\frac {|C\cap \{1,\dots ,n\}|}{n}}$ . Kneser's theorem for lower asymptotic density states that if $A$ and $B$ are subsets of $\mathbb {N}$ satisfying ${\underline {d}}(A+B)<{\underline {d}}(A)+{\underline {d}}(B)$ , then there is a natural number $k$ such that $H:=k\mathbb {N} \cup \{0\}$ satisfies the following two conditions:

(A+B+H)\setminus (A+B)

is finite,

and

{\underline {d}}(A+B)={\underline {d}}(A+H)+{\underline {d}}(B+H)-{\underline {d}}(H).

Note that $A+B\subseteq A+B+H$ , since $0\in H$ .

Haar measure in locally compact abelian (LCA) groups

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

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

Equality in connected compact abelian groups

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

m_{*}(A+B)=m(A)+m(B)<m(G)

(1)

can be found when $G$ is the torus $\mathbb {T$ and $A$ and $B$ 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 $G$ is a connected compact abelian group with Haar measure $m,$ $A$ and $B$ are $m$ -measurable subsets of $G$ satisfying $m(A)>0,m(B)>0$ , and equation ( 1 ), then there is a continuous surjective homomorphism $\phi :G\to \mathbb {T}$ and there are closed intervals $I$ , $J$ in $\mathbb {T}$ such that $A\subseteq \phi ^{-1}(I)$ , $B\subseteq \phi ^{-1}(J)$ , $m(A)=m(\phi ^{-1}(I))$ , and $m(B)=m(\phi ^{-1}(J))$ .

Notes

1 2 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.
1 2 3 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. 165. Springer-Verlag. pp. 109–132. ISBN 0-387-94655-1. Zbl 0859.11003.

Related Research Articles

In mathematical analysis, the Haar measure assigns an "invariant volume" to subsets of locally compact topological groups, consequently defining an integral for functions on those groups.

In mathematics, specifically abstract algebra, the isomorphism theorems are theorems that describe the relationship between quotients, homomorphisms, and subobjects. Versions of the theorems exist for groups, rings, vector spaces, modules, Lie algebras, and various other algebraic structures. In universal algebra, the isomorphism theorems can be generalized to the context of algebras and congruences.

Distributions, also known as Schwartz distributions or generalized functions, are objects that generalize the classical notion of functions in mathematical analysis. Distributions make it possible to differentiate functions whose derivatives do not exist in the classical sense. In particular, any locally integrable function has a distributional derivative. Distributions are widely used in the theory of partial differential equations, where it may be easier to establish the existence of distributional solutions than classical solutions, or appropriate classical solutions may not exist. Distributions are also important in physics and engineering where many problems naturally lead to differential equations whose solutions or initial conditions are distributions, such as the Dirac delta function.

In additive number theory, the Schnirelmann density of a sequence of numbers is a way to measure how "dense" the sequence is. It is named after Russian mathematician Lev Schnirelmann, who was the first to study it.

In the mathematical field of measure theory, an outer measure or exterior measure is a function defined on all subsets of a given set with values in the extended real numbers satisfying some additional technical conditions. The theory of outer measures was first introduced by Constantin Carathéodory to provide an abstract basis for the theory of measurable sets and countably additive measures. Carathéodory's work on outer measures found many applications in measure-theoretic set theory, and was used in an essential way by Hausdorff to define a dimension-like metric invariant now called Hausdorff dimension. Outer measures are commonly used in the field of geometric measure theory.

In mathematics, the total variation identifies several slightly different concepts, related to the structure of the codomain of a function or a measure. For a real-valued continuous function f, defined on an interval [a, b] ⊂ ℝ, its total variation on the interval of definition is a measure of the one-dimensional arclength of the curve with parametric equation x ↦ f(x), for x ∈ [a, b].

In additive combinatorics, the sumset of two subsets A and B of an abelian group G is defined to be the set of all sums of an element from A with an element from B. That is,

In measure theory, an area of mathematics, Egorov's theorem establishes a condition for the uniform convergence of a pointwise convergent sequence of measurable functions. It is also named Severini–Egoroff theorem or Severini–Egorov theorem, after Carlo Severini, an Italian mathematician, and Dmitri Egorov, a Russian physicist and geometer, who published independent proofs respectively in 1910 and 1911.

In additive combinatorics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if $is small, then can be contained in a small generalized arithmetic progression.$

In number theory, zero-sum problems are certain kinds of combinatorial problems about the structure of a finite abelian group. Concretely, given a finite abelian group G and a positive integer n, one asks for the smallest value of k such that every sequence of elements of G of size k contains n terms that sum to 0.

Wigners theorem Theorem in the mathematical formulation of quantum mechanics

Wigner's theorem, proved by Eugene Wigner in 1931, is a cornerstone of the mathematical formulation of quantum mechanics. The theorem specifies how physical symmetries such as rotations, translations, and CPT are represented on the Hilbert space of states.

Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition. More abstractly, the field of additive number theory includes the study of abelian groups and commutative semigroups with an operation of addition. Additive number theory has close ties to combinatorial number theory and the geometry of numbers. Two principal objects of study are the sumset of two subsets A and B of elements from an abelian group G,

In additive number theory and combinatorics, a restricted sumset has the form

In mathematics, a Caccioppoli set is a set whose boundary is measurable and has a finite measure. A synonym is set of (locally) finite perimeter. Basically, a set is a Caccioppoli set if its characteristic function is a function of bounded variation.

In mathematics, the Pettis integral or Gelfand–Pettis integral, named after Israel M. Gelfand and Billy James Pettis, extends the definition of the Lebesgue integral to vector-valued functions on a measure space, by exploiting duality. The integral was introduced by Gelfand for the case when the measure space is an interval with Lebesgue measure. The integral is also called the weak integral in contrast to the Bochner integral, which is the strong integral.

In algebra and number theory, a distribution is a function on a system of finite sets into an abelian group which is analogous to an integral: it is thus the algebraic analogue of a distribution in the sense of generalised function.

In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some morphism to a finite monoid. Recognizable sets are useful in automata theory, formal languages and algebra.

Glossary of Lie groups and Lie algebras Wikipedia glossary

This is a glossary for the terminology applied in the mathematical theories of Lie groups and Lie algebras. For the topics in the representation theory of Lie groups and Lie algebras, see Glossary of representation theory. Because of the lack of other options, the glossary also includes some generalizations such as quantum group.

In additive combinatorics, the Ruzsa triangle inequality, also known as the Ruzsa difference triangle inequality to differentiate it from some of its variants, bounds the size of the difference of two sets in terms of the sizes of both their differences with a third set. It was proven by Imre Ruzsa (1996), and is so named for its resemblance to the triangle inequality. It is an important lemma in the proof of the Plünnecke-Ruzsa inequality.

In functional analysis, every C^*-algebra is isomorphic to a subalgebra of the C^*-algebra $of bounded linear operators on some Hilbert space H . This article describes the spectral theory of closed normal subalgebras of$

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Kneser53-1] 1 2 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.

[Kneser56-2] 1 2 3 Kneser, Martin (1956). "Summenmengen in lokalkompakten abelschen Gruppen". Math. Z. (in German). 66: 88–110. doi:10.1007/BF01186598. S2CID 120125011. Zbl 0073.01702.

[GR143-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. 165. Springer-Verlag. pp. 109–132. ISBN 0-387-94655-1. Zbl 0859.11003.

[1]

[2]

[3]

[4]