# Uniformly at Random

## The Erdos-Ginzburg-Ziv Theorem

with one comment

Here we present a proof of the Erdos-Ginzburg-Ziv Theorem. We shall deduce this result using the Cauchy-Davenport Theorem, which in turn can be derived from Noga Alon’s Combinatorial Nullstellensatz. We begin by stating without proof the Combinatorial Nullstellensatz.

Combinatorial Nullstellensatz. Let $f$ be a polynomial over a field $K$ in the variables ${\bf x} = (x_1,\ldots,x_n)$. Suppose that the total degree of $f$ is $\sum_{i=1}^n d_i$ and that the coefficient in $f$ of $\prod_{i=1}^n x_i^{d_i}$ is non-zero. For $i = 1,\ldots,n$, let $L_i$ be a set of $d_i + 1$ elements of $K$. Then there exists ${\bf t} \in L_1 \times \cdots \times L_n$ such that $f({\bf t}) \neq 0$.

We wish to deduce the following classical theorem, following the proof of Noga Alon in his paper “Combinatorial Nullstellensatz”.

Theorem (Cauchy-Davenport). Let $p$ be a prime and let $A,B$ be subsets of $Z_p$. Then either $A+B = Z_p$ or $|A+B| \geq |A|+|B|-1$.

Proof. We first observe that if $|A|+|B| > p$, then for every $c \in Z_p$ we have $|A|+|c-B| > p$, so that $A \cap (c-B)$ is non-empty. This implies that $c$ can be written as the sum of elements $b \in B$ and $c-b \in A$. Since this holds for all $c \in Z_p$ we have $A+B = Z_p$, as required.

Suppose now that $|A|+|B| \leq p$ and that $|A+B| \leq |A|+|B|-2$, contrary to the claimed result. Let $C$ be any subset of $Z_p$ of size $|A|+|B|-2$ containing $A+B$. Define a polynomial $f(x,y) = \prod_{c \in C} (x+y-c)$. Clearly, $f(a,b)=0$ for all $(a,b) \in A \times B$. Moreover, the coefficient of $x^{|A|-1}y^{|B|-1}$ in $f$ equals ${|A|+|B|-2 \choose |A|-1}$, and is therefore non-zero in $Z_p$, since $|A|+|B|-2 < p$. Applying the Combinatorial Nullstellensatz to $f$, we conclude that there exists $(a,b) \in A \times B$ such that $f(a,b) \neq 0$, contradicting our earlier observation. This contradiction establishes the desired result.

This result can also be proved directly by induction on the size of $B$. Using the Cauchy-Davenport Theorem we now show the following result, following the presentation of Alon and Dubiner.

Theorem (Erdos-Ginzburg-Ziv). Let $n\geq 2$ be an integer. For any sequence $a_1,\ldots,a_{2n-1}$ of (not necessarily distinct) elements of $Z_n$, there exists a set $I \subseteq \{1,\ldots,2n-1\}$ of size $n$ such that $\sum_{i\in I} a_i = 0$ (in $Z_n$).

Proof. The proof is by induction on the number of primes in the prime factorization of $n$. Suppose that the result holds for prime $n$ and now consider $n = pm$ for some prime $p$ and some integer $m > 1$. Consider any $2p-1$ element subsequence of $a_1,\ldots,a_{2pm-1}$; by the claimed result for prime values, this $2p-1$ element subsequence contains $p$ elements whose sum is a multiple of $p$. We can therefore remove this $p$ element subsequence and repeat the argument to obtain disjoint sets $I_1,\ldots,I_{2m-1} \subseteq \{1,\ldots,2pm-1\}$ such that for $i=1,\ldots,m$, $|I_i| = p$ and $\sum_{j\in I_i} a_j$ is a multiple of $p$. For $i=1,\ldots,2m-1$, define $a_i' = \sum_{j\in I_i} a_j/p$. We now apply the induction hypothesis to the sequence $a_1',\ldots,a_{2m-1}'$ to conclude that there exists $J \subseteq \{1,\ldots,2m-1\}$ of size $m$ such that $\sum_{j\in J} a_j'$ is a multiple of $m$. This implies that if $I = \cup_{j\in J} I_j$, then $|I| = pm = n$ and $\sum_{i\in I} a_i$ is a multiple of $pm = n$, as required.

It remains now to establish the base case of the induction, namely the case when $n$ equals a prime $p$. Suppose that $a_1 \leq \cdots \leq a_{2p-1}$. If for some $i$ we have $a_i = a_{i+p-1}$, then $a_i = \cdots = a_{i+p-1}$ so that $a_i + \cdots + a_{i+p-1} = pa_i$ is a multiple of $p$ and we are done. Suppose then that for $i=1,\ldots,p-1$, $a_i \neq a_{i+p-1}$, and define sets $A_i = \{a_i,a_{i+p-1}\}$. By repeated application of the Cauchy-Davenport Theorem, we see that $|A_1 + \cdots + A_{p-1}| = p$. Thus every element of $Z_p$ can be written as a sum of exactly $p-1$ elements of our sequence. In particular, $-a_{2p-1}$ can be so written, so that $a_{2p-1}$, taken together with the $p-1$ elements of our sequence that sum to $-a_{2p-1}$, gives a $p$ element subsequence whose sum is 0 in $Z_p$, as required. This completes the proof.

Written by uncudh

January 25, 2009 at 3:29 am

Posted in math

Tagged with