## The Erdős-Ginzburg-Ziv theorem

Let $S = (a_1, \dots, a_n)$ be  a sequence of integers (not necessarily distinct). Then there exists a subsequence of $S$ the sum of whose elements is divisible by $n$

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 $S = (g_1, \dots, g_n)$ be a sequence of elements of an abelian group $(G, +, 0)$ of order $n$. Then there exists a non-empty subsequence of $S$ that sums up to $0$

Proof. Define $s_1 = g_1$, $s_2 = g_1 + g_2$, $\dots$, $s_n = g_1 + \dots + g_n$. Say none of the $s_i$‘s are zero. Since there are $n - 1$ non-zero elements in $G$, we must have $s_i = s_j$ for some $i < j$ by the pigeonhole principle. Hence $s_j - s_i = \sum_{k = i+1}^j a_k = 0$.

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 $2n - 1$ integers, $n$ of them must have their sum divisible by $n$. In fact, the original paper  implicitly proves the following more general result.

Theorem 2 (EGZ). Let $S = (g_1, \dots, g_{2n-1})$ be a sequence of elements of an abelian group $(G, +, 0)$ of order $n$. Then there exists a non-empty subsequence of $S$ that sums up to $0$ and has size $n$

There is an induction step in the paper which shows that it suffices to prove Theorem 2 in the special case when $G$ is the cyclic group of prime order $p$, i.e., $G \cong (\mathbb{F}_p, + , 0)$ where $\mathbb{F}_p$ is the finite field of order $p$. 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 $P_1, \dots, P_r \in \mathbb{F}_q[t_1, \dots, t_n]$. For $1 \leq i \leq n$, let $A_i \subseteq \mathbb{F}_q$ and put $A = \prod_{i = 1}^n A_i \subseteq \mathbb{F}_q^n$. If $\sum (q -1) \deg P_i < \sum (|A_i| - 1)$, then $P_i$‘s can’t have a unique common zero in $A$

Proof. Let $P = \prod (1 - P_i^{q-1})$. Say all $P_i$‘s have a common zero $a \in A$. Then $P(a) \neq 0$, so $P$ is a non-zero polynomial of degree $d = \sum (q - 1)\deg P_i < \sum (|A_i| - 1)$. Thus, by Alon-Furedi it has at least $\mathfrak{m}(|A_1|, \dots, |A_n|; \sum |A_i| - d) \geq 2$ non-zeros in $A$, which gives us at least two common zeros of $P_i$‘s.

We are now ready to prove the EGZ theorem for $G \cong \mathbb{F}_p$. Let $a_1, \ldots, a_{2p - 1}$ be elements of $\mathbb{F}_p$. Let $f = \sum a_i t_i$ and $g = \sum t_i$ be two polynomials in $\mathbb{F}_p[t_1, \dots, t_{2p-1}]$. Then $(0, \dots, 0)$ is a common zero of $f$ and $g$ and since $\deg f + \deg g = 2p - 2 < 2p-1$, there exists another common zero $x = (x_1, \dots, x_{2p-1})$ in $\{0, 1\}^{2p-1}$. Let $i_1, \dots, i_k$, be all the positions where $x_i$ is equal to $1$. Then $f(x) = 0$ gives us $a_{i_1} + \dots + a_{i_k} = 0$ and $g(x) = 0$ gives us $k \equiv 0 \pmod{p}$. Since $0 < k < 2p$, we must have $k = p$. $\blacksquare$

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 $(G, +, 0)$ satisfies the EGZ property if any sequence of $2|G| - 1$ elements of $G$ contains a subsequence of length $|G|$ that sums up to $0$.

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

Proof. Say $|N| = n$ and $|G/N| = r$. Let $S = (g_1, \dots, g_{2nr - 1})$ be a sequence of elements of $G$.
Since $G/N$ satisfies the EGZ property, from the elements $g_1 + N, \dots, g_{2r - 1} + N$ of $G/N$ we can choose $r$ which sum to the identity of $G/N$. By renaming the elements say $g_1 + N, \dots, g_r + N$ are those elements, i.e., $(g_1 + \dots + g_r) + N = N$, or equivalently we have $h_1 = g_1 + \dots + g_r \in N$. Now look at the first $2r - 1$ elements of the remaining $2nr - 1 - r$ elements of $S$ and repeat the argument to get $h_2 = g_{r+1} + \dots + g_{2r} \in N$. We can repeat this procedure till we have $h_{2n - 1} = g_{(2n - 2)r + 1} + \dots + g_{(2n - 1)r} \in N$.
Since $N$ satisfies the EGZ property, after renaming $h_i$‘s, we have $h_1 + \dots + h_n = 0$. By plugging in the values of $h_1, \dots, h_n$ in terms of the elements of $S$ we obtain $nr$ elements of $G$ that sum up to $0$.

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.

Currently a maths PhD student at Ghent University working in the Incidence Geometry research group. I am broadly interested in combinatorics, finite geometry and group theory.
This entry was posted in Combinatorics, Polynomial Method and tagged , , , . Bookmark the permalink.

### 7 Responses to The Erdős-Ginzburg-Ziv theorem

1. gaurish says:

[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 $a_1,a_2,\ldots , a_{n^2+1}$ of $n^2+1$ real numbers contains either an increasing subsequence of length $n+1$ or a decreasing subsequence of length $n+1$.”
(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?

• gaurish says:

According to Brualdi, R. A. (pp. 76, Introduction to Combinatorics, 5th ed), this is restatement of:
“It is always possible to choose at least $n$ points with increasing abscissae and either monotonously increasing or monotonously decreasing ordinates. ”
See the two paragraphs between equation 6 and 7 of the paper.

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

• gaurish says:

There is a typo in my comment, it should be $\sqrt{n}$ instead of $n$. 🙂

• gaurish says:

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.