## The Erdos-Ginzburg-Ziv Theorem

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 be a polynomial over a field in the variables . Suppose that the total degree of is and that the coefficient in of is non-zero. For , let be a set of elements of . Then there exists such that .

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

**Theorem** (Cauchy-Davenport). Let be a prime and let be subsets of . Then either or .

*Proof*. We first observe that if , then for every we have , so that is non-empty. This implies that can be written as the sum of elements and . Since this holds for all we have , as required.

Suppose now that and that , contrary to the claimed result. Let be any subset of of size containing . Define a polynomial . Clearly, for all . Moreover, the coefficient of in equals , and is therefore non-zero in , since . Applying the Combinatorial Nullstellensatz to , we conclude that there exists such that , contradicting our earlier observation. This contradiction establishes the desired result.

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

**Theorem** (Erdos-Ginzburg-Ziv). Let be an integer. For any sequence of (not necessarily distinct) elements of , there exists a set of size such that (in ).

*Proof*. The proof is by induction on the number of primes in the prime factorization of . Suppose that the result holds for prime and now consider for some prime and some integer . Consider any element subsequence of ; by the claimed result for prime values, this element subsequence contains elements whose sum is a multiple of . We can therefore remove this element subsequence and repeat the argument to obtain disjoint sets such that for , and is a multiple of . For , define . We now apply the induction hypothesis to the sequence to conclude that there exists of size such that is a multiple of . This implies that if , then and is a multiple of , as required.

It remains now to establish the base case of the induction, namely the case when equals a prime . Suppose that . If for some we have , then so that is a multiple of and we are done. Suppose then that for , , and define sets . By repeated application of the Cauchy-Davenport Theorem, we see that . Thus every element of can be written as a sum of exactly elements of our sequence. In particular, can be so written, so that , taken together with the elements of our sequence that sum to , gives a element subsequence whose sum is 0 in , as required. This completes the proof.

[…] 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. […]

Monday puzzle: divisible by 3 - Mind Your DecisionsAugust 26, 2013 at 3:59 am