Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
4  
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
add comment

2 Answers

up vote 6 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|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
add comment

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|improve this answer
    
Thank you very much –  Portland Mar 1 '10 at 13:35
add comment

Your Answer

 
discard

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.