EGZ theorem (Erdos-Ginzburg-Ziv) - MathOverflow

EGZ theorem (Erdos-Ginzburg-Ziv)

2010-02-28T22:58:36Z

Erdos, Ginzburg and Ziv prove the following: Let $n \geq 1$¸ $a_1,\ldots, a_{2n-1}\in \mathbb{Z}$. There exist $i_1,\ldots , i_n$ such that: $$a_{i_1} + \cdots + a_{i_n} \equiv 0 \pmod{n}$$ Is there a proof that doesn't use Chevalley-Warning theorem (or a variant of its proof)?

Answer by Gjergji Zaimi for EGZ theorem (Erdos-Ginzburg-Ziv)

2010-02-28T23:12:19Z

The original proof used Cauchy-Davenport lemma. Several proofs are given in this article of Alon-Dubiner (The proofs deal only with the case when $n$ is prime, but deducing the general case is straightforward from there). Note that the ideas behind most of these proofs could be interpreted as special cases of the more powerful theorem that is commonly known as "Combinatorial Nullstellensatz" (proven by N. Alon, see here). The keyword for results like these is "Zero-sum Ramsey theory".

ETA: You might also find the paper by Olson, "A combinatorial problem in finite abelian groups", Journal of Number Theory (1969) Vol.1 very interesting. It proves a generalization of EGZ theorem for finite abelian p-groups (I think this was one of the first among many other generalizations).

Answer by Hailong Dao for EGZ theorem (Erdos-Ginzburg-Ziv)

2010-03-01T01:45:49Z

Here is what I remember from a proof I came up with long time ago (it appeared in some competitions). I am sure it is known, but since the proof is short, I will put it here:

The statement can be reduced to the case $n=p$ is prime. Now it will follow from the following:

Lemma: Let $2\leq i\leq p$ and consider any set $A$ of elements $ a_1,\cdots, a_{2i-1} \in \mathbb F_p$ such that no $i$ of them are the same. Let $S$ be the set of all sums of $i$ elements of $A$. Then $|S|\geq i$.

Proof: Induction on $i$, the case $i=2$ is easy. Suppose the result is true for $p>i=k\geq 2$. Consider the set $A'$ of $2k+1$ elements $\{a_1,\cdots,a_{2k-1},b,c\}$ , WLOG we may assume that $b,c$ represent the two most frequently appeared elements in $A'$. By assumption $b\neq c$.

The set $\{a_1,\cdots,a_{2k-1}\}$ satisfies the condition that any frequency is less than $k$, otherwise there will be $3$ elements appearing at least $k$ times in $A'$, impossible. By induction we can choose $k$ subsets of $k$ elements with sums are distinct $s_1,\cdots, s_{k}\in \mathbb F_p$. Let $B=\{b+s_1,\cdots, b+s_{k}\}$ and $C=\{c+s_1,\cdots, c+s_{k}\}$ , obviously $|B|=|C|=k$. We will be done by showing $B \neq C$. If so, then by summing all the elements in each set one gets $k(b-c)=0$, impossible. QED.

Applying the lemma for $i=p$, note that if there are $p$ identical elements then their sum is $0$.

By the way, I asked some question on generalizations of this theorem, and get really good answers here.