View source for Erdös-Ginzburg-Ziv theorem

''EGZ theorem''

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e1101001.png" /> is a positive integer and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e1101002.png" /> is a sequence of elements from the [[Cyclic group|cyclic group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e1101003.png" />, then there exists a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e1101004.png" /> of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e1101005.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e1101006.png" />. This theorem was first shown in [[#References|[a5]]].

==Related theorems.==
Looking at a sequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e1101007.png" /> zeros and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e1101008.png" /> ones one sees that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e1101009.png" /> cannot be replaced by a smaller number. This motivates the definition of the Erdös–Ginzburg–Ziv constant for an arbitrary Abelian group, as follows. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010010.png" /> is an [[Abelian group|Abelian group]], then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010011.png" /> is the minimum integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010012.png" /> such that every sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010013.png" /> of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010014.png" /> contains a subsequence of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010015.png" />, the order of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010016.png" />, that adds up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010017.png" />. It can be proven that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010018.png" /> and equality holds if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010019.png" />. This result and the observation above led to the following two directions of investigation:

i) To find bounds, or possibly determine, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010020.png" /> for groups other than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010021.png" /> in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010022.png" /> and other group invariants. Recent results in this direction were obtained by Y. Caro and Weidong Gao.

ii) To find or estimate the minimum integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010023.png" /> such that every sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010024.png" /> of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010025.png" /> contains a subsequence of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010026.png" /> that adds up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010027.png" />, provided one knows that there are at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010028.png" /> distinct elements in the sequence. Recent results in this direction are due to A. Bialostocki, P. Dierker, Y.O. Hamidoune, and M. Lotspeich. A breakthrough in this direction was achieved after the recent proof of the long standing Erdös–Heilbronn conjecture (cf. also [[Erdös–Heilbronn problem|Erdös–Heilbronn problem]]). Along a different line, J.E. Olson extended the definition of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010029.png" /> constant to non-Abelian groups and proved that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010030.png" /> still holds.

==Outline of developments.==
There are several reasons why this theorem has recently (1996) drawn much attention.

Quite unexpectedly, N. Alon and M. Dubiner [[#References|[a1]]] have shown that the theorem follows from several deeper results in algebra and number theory, establishing interesting links.

The theorem has many possible generalizations, some of which have been proved and others are easy to state as fundamental open problems, see [[#References|[a4]]] and the conjectures below.

The theorem motivated the development of what is called a zero-sum Ramsey theory: If the sequence in the theorem consists only of the elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010032.png" />, then its proof follows from the pigeon hole principle (cf. [[Dirichlet principle|Dirichlet principle]]), hence the theorem can be viewed as a generalization of this principle. Consequently, since Ramsey theory (cf. also [[Ramsey theorem|Ramsey theorem]]) is a development of the pigeon hole principle, there is a clear motivation to develop from the EGZ theorem a zero-sum Ramsey theory along the lines of traditional Ramsey theory. While in Ramsey theory one looks for monochromatic configurations, in zero-sum Ramsey theory the colours are elements of a group and one looks for zero-sum configurations. Zero-sum Ramsey theory generalizes many results of the traditional Ramsey theory and leaves many open problems.

==Proofs.==
In [[#References|[a1]]] five proofs for the EGZ theorem have been given. In all these proofs it is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010033.png" /> is a prime number, since the transition to a non-prime is a simple induction. The original proof is based on the Cauchy–Davenport theorem from elementary additive number theory; two other proofs use the [[Fermat little theorem|Fermat little theorem]], along with a counting argument and a lemma concerning permanents, respectively. A fourth proof uses the Chevalley–Warning theorem about zeros of polynomials over a finite field. Most interesting is the proof that uses knowledge of the [[Davenport constant|Davenport constant]] of an Abelian <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010034.png" />-group, determined by Olson. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010035.png" /> be a finite Abelian group. The Davenport constant of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010036.png" />, denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010037.png" />, is the minimal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010038.png" /> such that every sequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010039.png" /> elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010040.png" /> contains a subsequence that adds up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010041.png" />.

==Generalizations and analogues.==
Clearly, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010042.png" /> is cyclic of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010043.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010044.png" />. An interesting relation between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010045.png" /> and the EGZ theorem is Weidong's generalization of the EGZ theorem: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010046.png" /> be a sequence of elements from an Abelian group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010047.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010048.png" />, then there exists a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010049.png" /> of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010050.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010051.png" />.

The following two conjectures are other possible generalizations of the EGZ theorem.

===Conjecture 1.===
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010052.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010053.png" /> be positive integers. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010054.png" /> is a sequence of elements from the cyclic group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010055.png" />, then it contains at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010056.png" /> subsequences of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010057.png" /> elements that add up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010058.png" />.

If one takes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010059.png" /> in this conjecture, then the EGZ theorem follows.

===Conjecture 2.===
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010060.png" /> be a positive integer and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010061.png" /> be a sequence of elements from the cyclic group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010062.png" /> whose sum is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010063.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010064.png" /> is a sequence of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010065.png" />, then it contains a subsequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010066.png" /> such that the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010067.png" /> can be reordered <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010068.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010069.png" />.

If one takes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010070.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010071.png" />, in this conjecture, then the EGZ theorem follows.

Conjecture 1 was proven by M. Kisin for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010072.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010073.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010074.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010075.png" /> are distinct prime numbers and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010076.png" />. In [[#References|[a7]]], Z. Füredi and D.J. Kleitman confirmed Conjecture 1 asymptotically for every positive integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010077.png" />. Conjecture 2 can be easily proven for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010078.png" /> prime. Both conjectures illustrate the general difficulty that exists in this area for handling the non-prime case.

There are many related problems to the EGZ theorem. The following conjecture was raised by H. Harborth and some progress was made by Alon and Dubiner. It illustrates that certain problems are open, even for primes.

===Conjecture 3.===
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010079.png" /> is a prime and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010080.png" /> is a sequence of elements from the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010081.png" />, then there exists a subsequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010082.png" /> elements whose elements add up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010083.png" />.

A sequence containing only the elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010084.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010085.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010086.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010087.png" />, where each element appears <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010088.png" /> times, implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010089.png" /> can not be replaced by a smaller number.

==Zero-sum Ramsey theory.==
This theory was first introduced in [[#References|[a3]]]. Today it includes many results on zero-sum Ramsey numbers for graphs. Recent developments by Bialostocki, P. Erdös, H. Lefmann, and D. Schaal deal with zero-sum solutions to systems of equations and inequalities over the integers. Surveys of this can be found in [[#References|[a2]]] and [[#References|[a4]]]. The following theorem from zero-sum Ramsey theory, proved in [[#References|[a6]]] and [[#References|[a8]]], generalizes in the sense of the EGZ theorem the folkloristic fact that in every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010090.png" />-colouring of the edges of a complete graph there is always a monochromatic spanning tree: If each edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010091.png" /> of the complete graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010092.png" /> (cf. also [[Graph theory|Graph theory]]) is assigned an element from the cyclic group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010093.png" />, say <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010094.png" />, then there exists a spanning tree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010095.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010096.png" /> with edges <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010097.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010098.png" />.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  N. Alon,   M. Dubiner,   "Zero-sum sets of prescribed size"  D. Miklós (ed.)  V.T. Sós (ed.)  T. Szönyi (ed.) , ''Combinatorics, Paul Erdös is Eighty'' , ''Bolyai Society Mathematical Studies'' , '''1''' , Keszthely (Hungary)  (1993)  pp. 33–50</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A. Bialostocki,   "Zero-sum trees: a survey of results and open problems"  N.W. Sauer (ed.)  R.E. Woodrow (ed.)  B. Sands (ed.) , ''Finite and Infinite Combinatorics in Sets and Logic'' , ''Nato ASI Ser.'' , Kluwer Acad. Publ.  (1993)  pp. 19–29</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Bialostocki,   P. Dierker,   "Zero-sum Ramsey theorems"  ''Congressus Numerantium'' , '''70''' :  1  (1990)  pp. 19–130</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  Y. Caro,   "Zero-sum problems: a survey"  ''Discrete Math.'' , '''152'''  (1996)  pp. 93–113</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  P. Erdös,   A. Ginzburg,   A. Ziv,   "A theorem in additive number theory"  ''Israel Research and Development Nat. Council Bull., Sect. F'' , '''10'''  (1961)  pp. 41–43</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  Z. Füredi,   D. Kleitman,   "On zero trees"  ''J. Graph Th.'' , '''16'''  (1992)  pp. 107–120</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  Z. Füredi,   D. Kleitman,   "The minimal number of zero sums"  D. Miklós (ed.)  V.T. Sós (ed.)  T. Szönyi (ed.) , ''Combinatorics, Paul Erdös is Eighty'' , ''Bolyai Society Mathematical Studies'' , '''1''' , Keszthely (Hungary)  (1993)  pp. 159–172</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  L. Schrijver,   P. Seymour,   "A simpler proof and generalization of the zero-trees theorem"  ''J. Combin. Th. A'' , '''58'''  (1991)  pp. 301–305</TD></TR></table>