Erdös-Ginzburg-Ziv theorem

EGZ theorem

If $m$ is a positive integer and $a_1,\ldots,a_{2m-1}$ is a sequence of elements from the cyclic group $\mathbb{Z}_m$, then there exists a set $I\subseteq \{1,\ldots,2m-1\}$ of cardinality $m$ such that $\sum_{i\in I}a_i=0$. This theorem was first shown in [a5].

Related theorems.

Looking at a sequence of $ m - 1 $ zeros and $ m - 1 $ ones one sees that $ 2m - 1 $ 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 $ G $ is an Abelian group, then $ { \mathop{\rm EGZ}\nolimits} ( G ) $ is the minimum integer $ e $ such that every sequence $ a _{1} \dots a _{e} $ of elements from $ G $ contains a subsequence of cardinality $ o ( G ) $, the order of $ G $, that adds up to $ 0 $. It can be proven that $ { \mathop{\rm EGZ}\nolimits} ( G ) \leq {2o ( G ) - 1} $ and equality holds if and only if $ G = \mathbf Z _{m} $. This result and the observation above led to the following two directions of investigation:

i) To find bounds, or possibly determine, $ { \mathop{\rm EGZ}\nolimits} ( G ) $ for groups other than $ \mathbf Z _{m} $ in terms of $ o ( G ) $ 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 $ e = e ( G,k ) $ such that every sequence $ a _{1} \dots a _{e} $ of elements from $ G $ contains a subsequence of cardinality $ o ( G ) $ that adds up to $ 0 $, provided one knows that there are at least $ k $ 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). Along a different line, J.E. Olson extended the definition of the $ { \mathop{\rm EGZ}\nolimits} ( G ) $ constant to non-Abelian groups and proved that $ { \mathop{\rm EGZ}\nolimits} ( G ) \leq {2o ( G ) - 1} $ 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 [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 [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 $ 0 $ and $ 1 $, then its proof follows from the pigeon hole principle (cf. Dirichlet principle), hence the theorem can be viewed as a generalization of this principle. Consequently, since Ramsey theory (cf. also 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 [a1] five proofs for the EGZ theorem have been given. In all these proofs it is assumed that $ m $ 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, 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 of an Abelian $ p $- group, determined by Olson. Let $ G $ be a finite Abelian group. The Davenport constant of $ G $, denoted by $ D ( G ) $, is the minimal $ d $ such that every sequence of $ d $ elements from $ G $ contains a subsequence that adds up to $ 0 $.

Generalizations and analogues.

Clearly, if $ G $ is cyclic of order $ m $, then $ D ( G ) = m $. An interesting relation between $ D ( G ) $ and the EGZ theorem is Weidong's generalization of the EGZ theorem: Let $ a _{1} \dots a _{s} $ be a sequence of elements from an Abelian group $ G $. If $ s = o ( G ) + D ( G ) - 1 $, then there exists a set $ I \subseteq \{ 1 \dots s \} $ of cardinality $ o ( G ) $ such that $ \sum _ {i \in I} a _{i} = 0 $.

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

Conjecture 1.

Let $ m $ and $ s $ be positive integers. If $ a _{1} \dots a _{s} $ is a sequence of elements from the cyclic group $ \mathbf Z _{m} $, then it contains at least $ \binom{ {\lceil {s/2} \rceil}}{m} + \binom{ {\lfloor {s/2} \rfloor}}{m} $ subsequences of $ m $ elements that add up to $ 0 $.

If one takes $ s = 2m - 1 $ in this conjecture, then the EGZ theorem follows.

Conjecture 2.

Let $ m $ be a positive integer and let $ b _{1} \dots b _{m} $ be a sequence of elements from the cyclic group $ \mathbf Z _{m} $ whose sum is $ 0 $. If $ a _{1} \dots a _ {2m - 1} $ is a sequence of elements from $ \mathbf Z _{m} $, then it contains a subsequence $ a _ {k ( 1 )} \dots a _ {k ( m )} $ such that the sequence $ b _{1} \dots b _{m} $ can be reordered $ b _ {j ( 1 )} \dots b _ {j ( m )} $ such that $ \sum ^{m} _ {i = 1} a _ {k ( i )} b _ {j ( i )} = 0 $.

If one takes $ b _{i} = 1 $, $ i = 1 \dots m $, in this conjecture, then the EGZ theorem follows.

Conjecture 1 was proven by M. Kisin for $ m = p ^ \alpha $ and $ m = p ^ \alpha q $, where $ p $ and $ q $ are distinct prime numbers and $ \alpha \geq1 $. In [a7], Z. Füredi and D.J. Kleitman confirmed Conjecture 1 asymptotically for every positive integer $ m $. Conjecture 2 can be easily proven for $ m $ 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 $ p $ is a prime and $ a _{1} \dots a _ {4p - 3} $ is a sequence of elements from the group $ \mathbf Z _{p} \oplus \mathbf Z _{p} $, then there exists a subsequence of $ p $ elements whose elements add up to $ ( 0,0 ) $.

A sequence containing only the elements $ ( 0,0 ) $, $ ( 0,1 ) $, $ ( 1,0 ) $, and $ ( 1,1 ) $, where each element appears $ p - 1 $ times, implies that $ 4p - 3 $ can not be replaced by a smaller number.

Zero-sum Ramsey theory.

This theory was first introduced in [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 [a2] and [a4]. The following theorem from zero-sum Ramsey theory, proved in [a6] and [a8], generalizes in the sense of the EGZ theorem the folkloristic fact that in every $ 2 $- colouring of the edges of a complete graph there is always a monochromatic spanning tree: If each edge $ e $ of the complete graph $ K _ {m + 1} $( cf. also Graph theory) is assigned an element from the cyclic group $ \mathbf Z _{m} $, say $ c ( e ) $, then there exists a spanning tree $ T $ of $ K _ {m + 1} $ with edges $ e _{1} \dots e _{m} $ such that $ \sum ^{m} _ {i = 1} c ( e _{i} ) = 0 $.

References

[a1]	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
[a2]	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
[a3]	A. Bialostocki, P. Dierker, "Zero-sum Ramsey theorems" Congressus Numerantium , 70 : 1 (1990) pp. 19–130
[a4]	Y. Caro, "Zero-sum problems: a survey" Discrete Math. , 152 (1996) pp. 93–113
[a5]	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
[a6]	Z. Füredi, D. Kleitman, "On zero trees" J. Graph Th. , 16 (1992) pp. 107–120
[a7]	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
[a8]	L. Schrijver, P. Seymour, "A simpler proof and generalization of the zero-trees theorem" J. Combin. Th. A , 58 (1991) pp. 301–305