MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|cite|improve this question
Good question, but I have to comment that I find the proof using Chevalley-Warning (the only one I know) to be extremely beautiful. – Pete L. Clark Feb 28 '10 at 23:07
up vote 7 down vote accepted

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).

share|cite|improve this answer
Very useful, thanks Gjergji. – Portland Feb 28 '10 at 23:30
See also the chapter on Algebraic Methods in Tao and Vu's Additive Combinatorics, for a detailed discussion about the combinatorial nullstellensatz, and many similar applications. – Thomas Bloom Mar 1 '10 at 14:45
The polynomial method proof can also be interpreted as an application of a result of Alon-Furedi, which doesn't follow from Combinatorial Nullstellensatz, and is equivalent to a result in Coding Theory. See, and Here's the argument, let $f = \sum x_i$ and $g = \sum a_i x_i$, where $a_i$'s are the $2p - 1$ numbers modulo $p$, then $(1 - f^{p - 1})(1 - g^{p-1})$ has degree $2p - 2$ and hence at least one non-zero in $\{0, 1\}^{2p-1}$ besides the origin, by the Alon-Furedi theorem. – Anurag Dec 9 '15 at 17:46

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.

share|cite|improve this answer
Thank you very much – Portland Mar 1 '10 at 13:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.