Convex geometry and the Erdős-Ginzburg-Ziv problem

The Erdős-Ginzburg-Ziv theorem states that if $x_1,\dots,x_{2n-1}$ is a sequence of elements of the group $\mathbb Z/n\mathbb Z$, then there is a subsequence of length $n$ that sums to 0. Equivalently, given $2n-1$ (not necessarily distinct) integers, it is possible to choose $n$ of them such that their average is also an integer. The bound is best possible, as can be seen by taking $n-1$ copies of 0 and $n-1$ copies of 1.

When $n$ is prime, the theorem can be deduced from the Cauchy-Davenport theorem, as follows. One notes first that if at least $n$ of the numbers are the same, then the result is trivial. Otherwise, it is not hard to show that after reordering, one can assume that $x_{2i-1}\ne x_{2i}$ for $i=1,2,\dots,n-1$. If that is the case, then set $E_i=\{0,x_{2i}-x_{2i-1}\}$, and observe that every element of
$$x_1+x_3+\dots+x_{2n-1}+E_1+E_2+\dots+E_{n-1}$$
is a sum of a subsequence of length $n$. However, by the Cauchy-Davenport theorem (or indeed just the easier special case where one of the sets has size 2) and induction, the set $E_1+\dots+E_{n-1}$ has size at least $n$, so it is all of $\mathbb Z/n\mathbb Z$, and the result follows. The result for composite $n$ can be deduced from this by a product argument.

It is natural to ask what happens in other Abelian groups, and in particular in the group $(\mathbb Z/n\mathbb Z)^d$. The Erdős-Ginzburg-Ziv constant of $G=(\mathbb Z/n\mathbb Z)^d$, denoted by $\mathfrak s(G)$ is defined to be the minimal $s$ such that every sequence of length $s$ of elements of $G$ has a subsequence of length $n$ that sums to 0. Reiher has shown that when $d=2$, $\mathfrak s(G)=4n-3$, which is best possible because of the example consisting of $n$ copies of each of $(0,0), (1,0), (0,1)$ and $(1,1)$), which is a natural generalization of the example when $d=1$. Essentially the same example gives a lower bound of $2^d(n-1)+1$ for general $d$, and it is tempting to conjecture that that is sharp, but that is false, since Edel has proved a lower bound of $2.139^dn$.

In the other direction, Alon and Dubiner have obtained an upper bound of $(Cd\log d)^dn$. The aim of this paper is to close the gap between the exponential dependence on $d$ in the lower bound and the more factorial-like dependence in the upper bound. It gives an upper bound of $4^dp$ when $d$ is fixed and $p$ is a sufficiently large prime, so it shows that the true dependence is exponential.

The proof of this result is at least as interesting as the result itself. Its starting point is the following observation, which can be found in a paper of Gao and Geroldinger. Suppose that one can find a set $\{v_1,\dots,v_m\}$ of vectors in $(\mathbb Z/p\mathbb Z)^d$ with the property that if $a_1,\dots,a_m$ are positive integers such that $\sum_ia_i=p$ and $\sum_ia_iv_i=0$, then one of the $a_i$ must equal $p$ (and hence the rest are 0). In that case, we know immediately that the Erdős-Ginzburg-Ziv constant of $(\mathbb Z/p\mathbb Z)^d$ is at least $(p-1)m+1$, since if we take $p-1$ copies of each $v_i$, then no $p$ vectors add up to 0. Gao and Geroldinger conjectured that the converse holds: that is, that the Erdős-Ginzburg-Ziv constant of $(\mathbb Z/p\mathbb Z)^d$ is precisely $(p-1)m+1$, where $m$ is the largest size of a set of vectors with the above property. The author calls this largest size the weak Erdős-Ginzburg-Ziv constant of $(\mathbb Z/p\mathbb Z)^d$, and denotes it by $\mathfrak w(\mathbb Z/p\mathbb Z)^d$.

The paper does not prove this conjecture exactly, but it comes close, showing that the two bounds differ by a factor $1+o(1)$ for fixed $d$ and $p$ tending to infinity. In order to prove this, the author defines objects that he calls convex flags: very roughly, they are ensembles of polytopes that are joined together in ways that are required to satisfy certain conditions. An example of a convex flag is simply the set of all faces of all dimensions of a convex polytope, but the definition is more general than this. The paper develops a theory of convex flags, proving analogues of various results about polytopes, including Helly’s theorem, and uses it to deduce the approximate equivalence.

It then remains to obtain an upper bound for the weak Erdős-Ginzburg-Ziv constant. An upper bound of $4^d-1$ had already been obtained by Naslund using the slice-rank method: in this paper a slightly improved bound of $\binom{2d-1}d+1$ is obtained, also using polynomial methods.