Improved bounds for zero-sum cycles in ${\mathbb{Z}}_p^d$

Abstract

For a finite Abelian group $(\hat{I}“,+)$, let $n(\hat{I}“)$ denote the smallest positive integer $n$ such that for each labelling of the arcs of the complete digraph of order $n$ using elements from $\hat{I}“$, there exists a directed cycle such that the total sum of the arc-labels along the cycle equals $0$. Alon and Krivelevich initiated the study of the parameter $n(\cdot )$ on cyclic groups and proved that $n({\mathbb{Z}}_q)=O(q\log q)$. Studying the prototypical case when $\hat{I}“={\mathbb{Z}}_p^d$ is a power of a cyclic group of prime order, Letzter and Morrison recently showed that $n({\mathbb{Z}}_p^d)\le O(pd(\log d{)}^2)$ and that $n({\mathbb{Z}}_2^d)\le O(d\log d)$. They then posed the problem of proving an (asymptotically optimal) upper bound of $n({\mathbb{Z}}_p^d)\le O(pd)$ for all primes $p$ and $d\in \mathbb{N}$. In this paper, we solve this problem for $p=2$ and improve their bound for all primes $p\ge 3$ by proving $n({\mathbb{Z}}_2^d)\le 5d$ and $n({\mathbb{Z}}_p^d)\le O(pd\log d)$. While the first bound determines $n({\mathbb{Z}}_2^d)$ up to a multiplicative error of $5$, the second bound is tight up to a $\log d$ factor. Moreover, our result shows that a tight bound of $n({\mathbb{Z}}_p^d)=\hat{I}˜(pd)$ for arbitrary $p$ and $d$ would follow from a (strong form) of the well-known conjecture of Jaeger, Linial, Payan and Tarsi on additive bases in ${\mathbb{Z}}_p^d$. Along the way to proving these results, we establish a generalization of a hypergraph matching result by Haxell in a matroidal setting. Concretely, we obtain sufficient conditions for the existence of matchings in a hypergraph whose hyperedges are labelled by the elements of a matroid, with the property that the edges in the matching induce a basis of the matroid. We believe that these statements are of independent interest.

6 Pages