Thresholds for zero-sums with small cross numbers in abelian groups

Abstract

For an additive group $\Gamma$ the sequence $S=(g_1,\dots ,g_t)$ of elements of $\Gamma$ is a zero-sum sequence if $g_1+\cdots +g_t=0_{\Gamma }$. The cross number of $S$ is defined to be the sum ${\sum }_{i=1}^{k}1/|g_i|$, where $|g_i|$ denotes the order of $g_i$ in $\Gamma$. Call $S$ good if it contains a zero-sum subsequence with cross number at most 1. In 1993, Geroldinger proved that if $\Gamma$ is abelian then every length $|\Gamma |$ sequence of its elements is good, generalizing a 1989 result of Lemke and Kleitman that had proved an earlier conjecture of Erdős and Lemke. In 1989 Chung re-proved the Lemke and Kleitman result by applying a theorem of graph pebbling, and in 2005, Elledge and Hurlbert used graph pebbling to re-prove and generalize Geroldinger's result. Here we use probabilistic theorems from graph pebbling to derive a threshold version of Geroldinger's theorem for abelian groups of a certain form. Specifically, we prove that if $p_1,\dots ,p_d$ are (not necessarily distinct) primes and ${\Gamma }_k$ has the form ${\prod }_{i=1}^d{\mathbb{Z}}_{p_i^k}$ then there is a function $\tau =\tau (k)$ (which we specify in Theorem 4) with the following property: if $t-\tau \to \infty$ as $k\to \infty$ then the probability that $S$ is good in ${\Gamma }_k$ tends to 1.

Theorems corrected and proofs added