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)?
$\begingroup$
$\endgroup$
4
-
10$\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. ClarkCommented Feb 28, 2010 at 23:07
-
$\begingroup$ For $n=p$, where $p$ is prime, we can consider the following sum $F(a_1,\ldots,a_{2p-1})=\sum_{A}s(A)^{p-1}$, where $A$ runs over all $p$-element subsets of $\{a_1,a_2,\ldots,a_{2p-1}\}$. It can be verified that all coefficents of $F$ as polynomial of $a_i$'s are zero modulo $p$. On the other hand, if the claim of the theorem is false, then $F(a_1,\ldots,a_{2p-1})\equiv\binom{2p-1}{p-1}\not\equiv 0\pmod p$. This is not an application of Chevalley-Warning, but in the same spirit, I think. (Here $s(A)$ is the sum of elenebts of $A$) $\endgroup$– richrowCommented Jul 25, 2020 at 13:18
-
$\begingroup$ Well, Ithink that this verification isn't really difficult (the coefficient of $\prod_{i=1}^{m}a_i^{k_i}$, where $\sum_{i=1}^{m}k_i=p-1$ is $\frac{(p-1)!}{k_1!\ldots k_m!}\cdot\binom{2p-1-m}{p-m}$ which is zero modulo $p$). $\endgroup$– richrowCommented Jan 7, 2021 at 11:07
-
$\begingroup$ The other way, probably, is taking derivatives. For any sequence $i_1,\ldots,i_{p-1}\in\{1,2,\ldots,2p-1\}$ consider $\left(\prod_{k=1}^{p-1}\frac{\partial}{\partial a_{i_k}}\right)F$. If i'm not mistaken this equals $(p-1)!\cdot\binom{2p-1-m}{p-m}$ ($(p-1)!$ times the number of $p$-element subsets containing $\{i_1,\ldots,i_{p-1}\}$). However, I think that both approaches are basically the same. $\endgroup$– richrowCommented Jan 7, 2021 at 11:07
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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).
answered Feb 28, 2010 at 23:12
-
$\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$ Commented Mar 1, 2010 at 14:45
-
1$\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$– AnuragCommented Dec 9, 2015 at 17:46
$\begingroup$
$\endgroup$
0
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.
answered Mar 1, 2010 at 1:45