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

Abstract

Denote by $\mathfrak{s}({\mathbb{F}}_p^d)$ the Erd{\H o}s--Ginzburg--Ziv constant of ${\mathbb{F}}_p^d$, that is, the minimum $s$ such that every sequence of $s$ vectors in ${\mathbb{F}}_p^d$ contains $p$ vectors whose sum is zero. Let $\mathfrak{w}({\mathbb{F}}_p^d)$ be the maximum size of a sequence of vectors $v_1,\dots ,v_s\in {\mathbb{F}}_p^d$ such that, for all integers ${\alpha }_1,\dots ,{\alpha }_s\ge 0$ with sum $p$, we have ${\alpha }_1{v}_1+\dots +{\alpha }_s{v}_s\ne 0$ unless ${\alpha }_i=p$ for some $i$. In 1995, Alon--Dubiner proved that $\mathfrak{s}({\mathbb{F}}_p^d)$ grows linearly in $p$ when $d$ is fixed. In this work, we determine the constant of linearity: for fixed $d$ and growing $p$, we show that $\mathfrak{s}({\mathbb{F}}_p^d)=(1+o(1))\mathfrak{w}({\mathbb{F}}_p^d)p$. Furthermore, for every prime $p$ and every $d$, we show that $\mathfrak{w}({\mathbb{F}}_p^d)\le \left(\genfrac{}{}{0ex}{}{2d-1}{d}\right)+1$. In particular, $\mathfrak{s}({\mathbb{F}}_p^d)\le 4^{d}p$ for all sufficiently large $p$ and fixed $d$.

55 pages, final version published in Discrete Analysis

Cited by in corpus (1)

• Zero subsums in vector spaces over finite fields