*Let be a sequence of integers (not necessarily distinct). Then there exists a subsequence of the sum of whose elements is divisible by . *

This is one of the first problems I saw when learning the pigeonhole principle. And it’s a good exercise to try it yourself by taking the pigeonhole principle as a hint. For our purpose, it’s best stated and proved in the following form.

**Theorem 1.** Let be a sequence of elements of an abelian group of order . Then there exists a non-empty subsequence of that sums up to .

**Proof. **Define , , , . Say none of the ‘s are zero. Since there are non-zero elements in , we must have for some by the pigeonhole principle. Hence .

In 1961, Erdős, Ginzburg and Ziv proved an interesting similar looking result which later became one of the pioneering results in the field of additive combinatorics/combinatorial number theory/arithmetic combinatorics. It says that given a sequence of integers, of them must have their sum divisible by . In fact, the original paper implicitly proves the following more general result.

**Theorem 2 (EGZ). **Let * be a sequence of elements of an abelian group of order . Then there exists a non-empty subsequence of that sums up to and has size . *

There is an induction step in the paper which shows that it suffices to prove Theorem 2 in the special case when is the cyclic group of prime order , i.e., where is the finite field of order . In this post I will discuss the proof of this prime case using the Alon-Furedi theorem, which was originally discovered by Clark, Forrow and Schmitt in Warning’s Second Theorem with Restricted Variables and then rediscovered by me and potu. The proof is quite similar to the 1989 proof by C. Bailey and R.B. Richter which used the famous Chevalley-Warning theorem, but instead we use a generalisation of CW; the so-called Restricted-Variable Chevalley-Warning theorem due to David Brink that follows directly from Alon-Furedi. I believe that this is a more natural proof than the one that uses Chevalley-Warning.

**Theorem 3 (RV CW).** Let . For , let and put . If , then ‘s can’t have a unique common zero in .

**Proof. **Let . Say all ‘s have a common zero . Then , so is a non-zero polynomial of degree . Thus, by Alon-Furedi it has at least non-zeros in , which gives us at least two common zeros of ‘s.

We are now ready to prove the EGZ theorem for . Let be elements of . Let and be two polynomials in . Then is a common zero of and and since , there exists another common zero in . Let , be all the positions where is equal to . Then gives us and gives us . Since , we must have .

For the sake of completeness, let’s give the induction argument also which will completely prove Theorem 2. We say that a finite abelian group satisfies the EGZ property if any sequence of elements of contains a subsequence of length that sums up to .

* Lemma 4. Let be a finite abelian group and a subgroup of . *If both and satisfy the EGZ property, then also satisfies the EGZ property.

**Proof. **Say and . Let be a sequence of elements of .

Since satisfies the EGZ property, from the elements of we can choose which sum to the identity of . By renaming the elements say are those elements, i.e., , or equivalently we have . Now look at the first elements of the remaining elements of and repeat the argument to get . We can repeat this procedure till we have .

Since satisfies the EGZ property, after renaming ‘s, we have . By plugging in the values of in terms of the elements of we obtain elements of that sum up to .

Lemma 4 along with the fundamental theorem of finite abelian groups now proves the theorem. In fact, one can prove a similar lemma for non-abelian groups and use it to prove EGZ for all solvable groups, as was done by B. Sury in this paper. For more discussion on this result, see these notes by Pete or any standard textbook on additive combinatorics/combinatorial number theory. Also see this famous paper by Alon and Dubiner that discusses several proofs of this result.

[Regarding pigeonhole principle] Recently I did a course on Combinatorics (at UG level), and found the following theorem by Erdős and Szekeres interesting:

“Every sequence of real numbers contains either an increasing subsequence of length or a decreasing subsequence of length .”

(if interested, can see pp. 5 of original paper: http://www.math-inst.hu/~p_erdos/1935-01.pdf)

Indeed, this is another famous problem demonstrating the power of pigeonhole principle. Are you sure about the reference though? Or is it in some other Erdős Szekeres paper?

According to Brualdi, R. A. (pp. 76, Introduction to Combinatorics, 5th ed), this is restatement of:

“It is always possible to choose at least points with increasing abscissae and either monotonously increasing or monotonously decreasing ordinates. ”

See the two paragraphs between equation 6 and 7 of the paper.

Ah, great. Thanks for that information then. I didn’t know that this is the paper where this problem originated.

There is a typo in my comment, it should be instead of . 🙂

This paper is again in news, “The Erdős Szekeres polygon problem – Solved asymptotically by Andrew Suk.”, URL: http://wp.me/pdu8v-3nX

Indeed. I found out about it from Gil’s blogpost too.

Looks quite interesting.

Pingback: Introduction to polynomial method | Anurag's Math Blog