Cauchy-Davenport's theorem

The Cauchy-Davenport , English Cauchy-Davenport theorem , named after the mathematicians Augustin-Louis Cauchy and Harold Davenport , is a mathematical theorem that the transition area between Additive number theory , Ramsey theory and group theory consulted and gave rise to a number of further investigations. The sentence deals with questions of power to subsets of cyclic groups of primary group order .

Formulation of the sentence

The sentence can be stated as follows:

Let a prime number be given and, in addition, two non-empty subsets and the associated subset in the cyclic group . ${\displaystyle p}$ ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle A,B\subseteq \mathbb {Z} _{p}}$ ${\displaystyle A+B:=\{a+b\mid a\in A\;,\;b\in B\}}$

Then the inequality holds

${\displaystyle |A+B|\geq \min \left(p,|A|+|B|-1\right)}$.

Associated sentences

The environment of Cauchy-Davenport's theorem includes numerous results and not least four theorems that are associated with the names of mathematicians Martin Kneser , Henry B. Mann , Paul Erdős , Abraham Ginzburg , Abraham Ziv and Noga Alon .

Kneser's sentence

This theorem by Martin Kneser ( English Kneser's theorem ) from 1955 has numerous applications in additive number theory and includes in particular Cauchy-Davenport's theorem. It can be specified as follows:

Let an Abelian group be given , which should not only consist of the neutral element , and in it two non-empty finite subsets as well as the associated subset . ${\displaystyle (G,+)}$ ${\displaystyle A,B\subseteq G}$ ${\displaystyle A+B:=\{a+b\mid a\in A\;,\;b\in B\}}$

It should

${\displaystyle |A|+|B|\leq |G|}$

be valid.

Then there is a real subgroup with ${\displaystyle H<G}$

${\displaystyle |A+B|\geq |A|+|B|-|H|}$.

Mann's sentence

This sentence, which can be found (for example) in Henry B. Mann's monograph Addition theorems: The Addition Theorems of Group Theory and Number Theory from 1965, deals with questions of power to subsets of any group and also contains a basic estimate :

Let a (not necessarily Abelian!) Group be given and within it two subsets and the associated subset . ${\displaystyle (G,\cdot )}$ ${\displaystyle A,B\subseteq G}$ ${\displaystyle A\cdot B:=\{a\cdot b\mid a\in A\;,\;b\in B\}}$

Then applies

${\displaystyle A\cdot B=G}$or . ${\displaystyle |A|+|B|\leq |G|}$

Proof of Mann's theorem

Mann's sentence is based on a simple train of thought:

In case there is an element . This forms the subset ${\displaystyle A\cdot B\neq G}$ ${\displaystyle c_{0}\in G\setminus {A\cdot B}}$

${\displaystyle c_{0}\cdot B^{-1}=\{c_{0}\cdot b^{-1}\mid b\in B\}}$

and concludes that

${\displaystyle A\cap {c_{0}\cdot B^{-1}}=\emptyset }$

must apply, because if there was one that followed immediately , but this is impossible. ${\displaystyle b\in B}$ ${\displaystyle c_{0}\cdot b^{-1}\in A}$ ${\displaystyle c_{0}=\left(c_{0}\cdot b^{-1}\right)\cdot b\in {A\cdot B}}$

With this disjointness it then immediately follows

${\displaystyle |A|+|B|=|A|+|c_{0}\cdot B^{-1}|=|A\;{\dot {\cup }}\;{c_{0}\cdot B^{-1}}|\leq |G|}$.

Combinatorial zero set

The combinatorial zero set , English Combinatorial Zero Set [sic!] , Which Noga Alon published in 1999, is - as the name suggests - closely related to Hilbert's zero set and can be directly derived from it. In combinatorics and related areas, it entails a number of subsequent theorems - especially Cauchy-Davenport's theorem - and can be represented as follows:

A natural number and a field plus the polynomial ring are given . ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle K}$ ${\displaystyle K[x_{1},x_{2},\ldots ,x_{n}]}$

A natural number and a polynomial of degree are also given , whereby among the monomials of there should be one of the form with and . ${\displaystyle d\in \mathbb {N} _{0}}$ ${\displaystyle f\in K[x_{1},x_{2},\ldots ,x_{n}]}$ ${\displaystyle d}$ ${\displaystyle f}$ ${\displaystyle a_{t_{1},t_{2},\ldots ,t_{n}}\cdot x_{1}^{t_{1}}x_{2}^{t_{2}}\cdots x_{n}^{t_{n}}}$ ${\displaystyle d=t_{1}+t_{2}+\cdots +t_{n}}$ ${\displaystyle a_{t_{1},t_{2},\ldots ,t_{n}}\neq 0}$

Finally, let finite sets with . ${\displaystyle S_{1},S_{2}\ldots ,S_{n}\subseteq K}$ ${\displaystyle |S_{1}|\geq {t_{1}+1},|S_{2}|\geq {t_{2}+1},\ldots ,|S_{n}|\geq {t_{n}+1}}$

Then:

There are elements with . ${\displaystyle s_{1}\in S_{1},s_{2}\in S_{2}\ldots ,s_{n}\in S_{n}}$ ${\displaystyle f(s_{1},s_{2},\ldots ,s_{n})\neq 0}$

Theorem from Erdős-Ginzburg-Ziv

(This sentence English Erdős-Ginzburg-Ziv theorem ) vorlegten the Erdős, Ginzburg and Ziv in 1961 and proved with the help of the set of Cauchy-Davenport, states the following:

For every natural number and for every finite sequence of (not necessarily different ) whole numbers given to it, there is a subsequence whose sum is divisible by . ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle \left(a_{i}\right)_{i=1,\dots ,{2n-1}}}$ ${\displaystyle 2n-1}$ ${\displaystyle \left(a_{i_{k}}\right)_{k=1,\dots ,n}}$ ${\displaystyle \sum _{k=1}^{n}a_{i_{k}}}$ ${\displaystyle n}$

See also

• Related article "Restricted sumset" (Wikipedia)
• Related article "Zero-sum problem" (Wikipedia)
• List of a selection of works on the Cauchy-Davenport theorem

literature

• Noga Alon: Combinatorial Zero Set . In: Combinatorics, Probability and Computing . tape 8 , 1999, p. 7-29 ( MR1684621 ).
• P. Erdős, A. Ginzburg, A. Ziv: Theorem in the additive number theory . In: Bulletin of the Research Council of Israel. Section F . 10F, 1961, pp. 41-43 ( MR3618568 ).
• Stasys Jukna : Extremal Combinatorics (=  Texts in Theoretical Computer Science ). 2nd Edition. Springer Verlag , Heidelberg, Dordrecht, London, New York 2011, ISBN 978-3-642-17363-9 ( MR2865719 ).
• Martin Kneser: Estimation of the asymptotic density of sum sets . In: Mathematical Journal . tape 58 , 1953, pp. 459-484 ( MR0056632 ).
• Martin Kneser: A sentence about abelian groups with applications to the geometry of numbers . In: Mathematical Journal . tape 61 , 1955, pp. 429-434 ( MR0068536 ).
• Henry B. Mann: Addition theorems: The Addition Theorems of Group Theory and Number Theory (=  Interscience Publishers Tracts . Band 18 ). Interscience Publishers John Wiley & Sons, New York, London, Sydney 1965 ( MR0181626 ).
• Harald Niederreiter , Arne Winterhof : Applied Number Theory . Springer Verlag , Cham 1976, ISBN 978-3-319-22320-9 , doi : 10.1007 / 978-3-319-22320-6 ( MR3364863 ).
• Hans Schwerdtfeger : Introduction to Group Theory . Noordhoff International Publishing, Leyden 1976, ISBN 90-286-0495-2 ( MR0435190 ).

Remarks

1. ↑ such subsets contained in an abelian group is called also sum amount ( English sumset ). Sum sets in Abelian groups are an essential part of additive number theory. ${\displaystyle A+B}$
2. ↑ With denotes the power of a set . Is a finite set , then is the number of elements contained in . ${\displaystyle |X|}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle |X|}$ ${\displaystyle X}$
3. ↑ Abraham Ziv, formerly Abraham Zubkowski, born March 6, 1940, died March 5, 2013, was an Israeli mathematician; see. Article about Ziv in the English language Wikipedia !
4. ↑ The sentence presented here is the weakened version of a stronger sentence that Martin Kneser provided in an earlier work in 1953.
5. ↑ According to Schwerdtfeger, Mann presented this estimate as early as 1952. In view of the simplicity of the basic idea behind it, it is obvious to assume that this estimate was also found and used by other mathematicians before.
6. ↑ In a group, inversion and left translation are always bijections .
7. ↑ Alon presented his "Combinatorial Zero Set " as early as 1995, at the conference on discrete mathematics in Mátraháza , which took place on October 22nd. - 28.10.1995 took place there.
8. ↑ What is meant here is the neutral element of the Abelian group . ${\displaystyle (K,+)}$

Individual evidence

1. ↑ ^{a b} Stasys Jukna: Extremal Combinatorics. 2011, p. 232 ff., P. 363 ff.
2. ^ Henry B. Mann: Addition theorems: The Addition Theorems of Group Theory and Number Theory. 1965, p. 1 ff.
3. ^ Niederreiter / Winterhof: Applied Number Theory. 2015, p. 383 ff.
4. ↑ Niederreiter / Winterhof, op.cit., P. 384
5. ↑ Jukna, op. Cit., Pp. 363-364
6. ↑ ^{a b} Mann, op.cit., P. 1
7. ^ ^{A b} Hans Schwerdtfeger: Introduction to Group Theory. 1976, p. 58
8. ^ Noga Alon: Combinatorial Zero Set , Combin. Probab. Comput. 8 (1999), pp. 7-29
9. ↑ Jukna, op.cit., P. 228 ff., P. 229
10. ↑ Jukna, op.cit., P. 233