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 GIf 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.

Advertisements

About Anurag Bishnoi

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.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s