Exponential Lower Bounds on the Generalized Erdős-Ginzburg-Ziv Constant

Abstract

For a finite abelian group $G$, the generalized Erdős--Ginzburg--Ziv constant ${\mathsf{s}}_k(G)$ is the smallest $m$ such that a sequence of $m$ elements in $G$ always contains a $k$-element subsequence which sums to zero. If $n=\exp (G)$ is the exponent of $G$, the previously best known bounds for ${\mathsf{s}}_{kn}(C_n^r)$ were linear in $n$ and $r$ when $k\ge 2$. Via a probabilistic argument, we produce the exponential lower bound \[ \mathsf s_{2n}(C_n^r) > \frac{n}{2}[1.25 - O(n^{-3/2})]^r \] for $n>0$. For the general case, we show \[ \mathsf s_{kn}(C_n^r) > \frac{kn}{4}\Big(1+\frac{1}{ek} + O\Big(\frac{1}{n}\Big)\Big)^r. \]

5 pages

References in corpus (2)

• Progression-free sets in Z_4^n are exponentially small
• Exponential Bounds for the Erdős-Ginzburg-Ziv Constant

Cited by in corpus (2)

• On generalized Erdős-Ginzburg-Ziv constants for ${\mathbb{Z}}_2^d$
• Improved lower bound on generalized Erdos-Ginzburg-Ziv constants