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.

Advertisements

Written by uncudh

January 25, 2009 at 3:29 am

Posted in math

Tagged with

One Response

Subscribe to comments with RSS.

  1. […] As a concluding remark, the result can be generalized that in a group of 2n – 1 numbers, there is always a subset of n numbers whose sum is divisible by n. This is known as the Erdos-Ginzburg-Ziv Theorem and is a bit more complicated to prove. You can read a proof of it here. […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: