Namespaces
Variants
Actions

Difference between revisions of "Erdös-Ginzburg-Ziv theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex done)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
{{TEX|done}}
 +
 
''EGZ 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]]].
+
If $m$ is a positive integer and $a_1,\ldots,a_{2m-1}$ is a sequence of elements from the [[Cyclic group|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 [[#References|[a5]]].
  
 
==Related theorems.==
 
==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:
+
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|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, <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.
+
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 <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.
+
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|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.==
 
==Outline of developments.==
Line 17: Line 43:
 
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 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.
+
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|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.==
 
==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" />.
+
In [[#References|[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|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 $  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.==
 
==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" />.
+
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.
 
The following two conjectures are other possible generalizations of the EGZ theorem.
  
 
===Conjecture 1.===
 
===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" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e110/e110100/e11010059.png" /> in this conjecture, then the EGZ theorem follows.
+
 
 +
If one takes $  s = 2m - 1 $
 +
in this conjecture, then the EGZ theorem follows.
  
 
===Conjecture 2.===
 
===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" />.
+
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 <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.
+
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 [[#References|[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.
 
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.===
 
===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" />.
+
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 <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.
+
 
 +
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.==
 
==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" />.
+
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 $  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|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====
 
====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>
 
<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>

Latest revision as of 17:25, 28 January 2020


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
How to Cite This Entry:
Erdös-Ginzburg-Ziv theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Erd%C3%B6s-Ginzburg-Ziv_theorem&oldid=22381
This article was adapted from an original article by A. Bialostocki (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article