Lower bounds for multidimensional zero sums (Q558239): Difference between revisions

Let \(f(n,d)\) denote the least integer such that for any choice of \(f(n,d)\) elements in \({\mathbb Z}_n^d\) contains a subset of size \(n\) whose sum is zero. \textit{H. Harborth} [J. Reine Angew. Math. 262/263, 356--360 (1973; Zbl 0268.05008)] showed that \((n-1)2^d+1\leq f(n,d)\leq (n-1)n^d+1\). \textit{N. Alon} and \textit{M. Dubiner} [Combinatorica 15, 301--309 (1995; Zbl 0838.11020)] improved the upper bound to \(c_d n\). In this nice paper, the author improves the lower bound to \(1.125^{\lfloor d/3\rfloor}(n-1)2^d+1\) for all \(d\geq 3\) and odd \(n\geq 3\). The proof is based on an example of nine vectors in \({\mathbb Z}_3^2\), first used by Harborth to show that \(f(3,3)\geq 19\), which are now treated as vectors in \({\mathbb Z}_n^3\). The author proves a lemma showing that if \(n\geq 3\) is odd, and if any \(n\) vectors from Harborth's set add to \(0\in {\mathbb Z}_n^3\), then one necessarily needs to take the same vector \(n\) times. The proof of this statement is elementary but intricate, and the author's result follows easily from the above lemma. A few immediate corollaries are also presented.