21
$\begingroup$

Erdős, Ginzburg and Ziv prove the following: Let $n \geq 1$ and $a_1,\ldots, a_{2n-1}\in \mathbb{Z}$. There exist distinct $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 the Chevalley–Warning theorem (or a variant of its proof)?

$\endgroup$
  • 8
    $\begingroup$ Good question, but I have to comment that I find the proof using Chevalley-Warning (the only one I know) to be extremely beautiful. $\endgroup$ – Pete L. Clark Feb 28 '10 at 23:07
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Bloom Mar 1 '10 at 14:45
  • $\begingroup$ 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 arxiv.org/abs/1404.7793, and arxiv.org/abs/1508.06020. 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. $\endgroup$ – Anurag Dec 9 '15 at 17:46
8
$\begingroup$

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 when $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 $\left|S\right|\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 appearing 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 whose sums $s_1,\cdots, s_{k}\in \mathbb F_p$ are distinct. Let $B=\{b+s_1,\cdots, b+s_{k}\}$ and $C=\{c+s_1,\cdots, c+s_{k}\}$, obviously $\left|B\right|=\left|C\right|=k$. We will be done by showing $B \neq C$. If not, 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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