Thresholds for Zero-Sums with Small Cross Numbers
in Abelian Groups

In this paper we move from guaranteeing the result with absolute certainty to achieving the result with high probability, using the pebbling theorems of Section 3 to yield sharp thresholds for the existence of zero sums with small cross number. In this section, we give a short non-technical introduction to the ideas present, so that we can state our results. We will then revisit these topics in detail in later sections, giving formal definitions to the undefined, and explaining the subtleties that arise.

We describe a randomized version of our sequences, explain how to use pebbling to study zero-sum sequences to pebbling in Section 2.3, and transfer these more traditional tools to the randomized world via the random pebbling model and theorems in Section 3.

Consider a finite abelian group ${\Gamma}$, and pick a sequence from ${\Gamma}$ at random – that is, we select a sequence $(a_{1},\ldots,a_{t})$ with equal probability among all sequences of the same length; we denote this probability space by ${\cal S}({\Gamma},t)$. How large must $t$ be to make it more-likely-than-not that our randomly selected sequence contains a zero-sum subsequence? How large should $t$ to make it likely that our randomly sequence is good?

With this goal in mind, we select our sequence of length $t$ uniformly from ${\Gamma}$ and consider the event ${\mathbb{E}}_{{\Gamma}}(t)$ containing all such good sequences. Formally, we will examine the function

We will use Bachmann-Landau notation to describe the asymptotics of functions. In this paper we prove the following theorem.

Given functions $f$ and $g$, we will write that $f\ll g$, or equivalently $f\in{\operatorname{o}}(g)$ whenever $\lim_{n\to\infty}\frac{f(n)}{g(n)}=0$. A function $t(n)$ is a threshold for event $E_{n}$ if in the sequence of probability spaces ${\cal D}(G_{n},f(n))$ the probability of event $E_{n}$ tends to $1$ whenever $f(n)\gg t(n)$, and the probability of event $E_{n}$ tends to $0$ whenever $f\ll t(n)$. We further call $t(n)$ a sharp threshold if whenever $f(n)\geq(1+\varepsilon)t(n)$ the probability of $E_{n}$ tends to $1$, and whenever $f(n)\leq(1-\varepsilon)t(n)$ the probability of $E_{n}$ tends to $0$. Often, for ${\cal G}=(G_{i})_{i\in{\mathbb{N}}}$, one writes $\tau({\cal G})$ for the set of threshold functions for the relevant sequence of events $E_{n}$. We will refer to any threshold function that has not been shown to be sharp as a weak threshold (this is sometimes called a coarse threshold in the literature).

These thresholds have the origins in the physical phase transitions that we see in nature, where the physical properties of a state of matter transform dramatically when crossing some critical temperature threshold. There is a long history and tradition of determining thresholds for random events in both pebbling (for solvability and other events) and random graphs (for connectivity, Hamiltonicity, the existence of a giant component, and many other events). By determining the asymptotics of ${{\bf P}_{\nicefrac{{1}}{{2}}}}({\Gamma})$, we are equivalently identifying the order of magnitude of the functions in $\tau({\Gamma})$.

We note that in the case that our groups are a sequence cyclic groups of increasing powers of a fixed prime $p$, Theorem 4 is improved via the stronger threshold result for pebbling paths due to Bushaw and Kettle (Theorem 9); we record this simplest case of Theorem 4 below.

Here we are given a graph $G$ with vertices $V(G)$, edges $E(G)$, and a cost function ${\sf w}:E(G){\rightarrow}{\mathbb{Z}}^{+}$ (the positive integers). If no edge costs are specified, we default to constant cost 2 everywhere. We denote the path $P_{n}=v_{1}v_{2}\cdots v_{n}$ to have $n$ vertices $v_{i}$ ($i\leq n$) and $n-1$ edges $v_{i}v_{i+1}$ ($i<n$). In general, we reserve the letter $n=n(G)$ to denote the number of vertices of a graph $G$.

The Cartesian product $G\Box H$ of two graphs $G$ and $H$ has vertex set $V(G\Box H)=V(G)\times V(H)$ and edge set $E(G\Box H)=\{(u,v_{1})(u,v_{2})\mid u\in V(G),v_{1}v_{2}\in E(H)\}\cup\{(u_{1},v)(u_{2},v)\mid u_{1}u_{2}\in E(G),v\in V(H)\}$. For example, $P_{2}\Box P_{2}$ is isomorphic to the $4$-cycle $C_{4}$. We may also recursively define the sequence of $d$-cubes ${\cal Q}=(Q^{1},Q^{2},\ldots,Q^{d},\ldots)$ by $Q^{1}=P_{2}$ and $Q^{d}=Q^{1}\Box Q^{d-1}=\Box_{i=1}^{d}P_{2}$. More general $d$-dimensional grids are defined similarly as a product of $d$ paths: $\Box_{i=1}^{d}P_{n_{i}}$, and for any graph $G$ we can define $G^{d}=\Box_{i=1}^{d}G$. The sequence of graphs of interest to us in Section 3 is ${\cal P}^{d}=(P_{1}^{d},P_{2}^{d},\ldots,P_{k}^{d},\ldots)$.

We are also given a configuration of pebbles, modeled by a function $C:V(G){\rightarrow}{\mathbb{N}}$ (the non-negative integers), by which $C(v)$ indicates the number of pebbles on vertex $v$. The size of $C$ is defined to be $|C|=\sum_{v}C(v)$; i.e. the total number of pebbles on $G$. Additionally, the edges of $G$ are weighted by a cost function ${\sf w}:E(G){\rightarrow}{\mathbb{N}}^{+}$. Finally, we are given a target vertex $r$ to which we are challenged to place a pebble, starting from $C$, via a sequence of pebbling steps, which we now describe.

Suppose that $e=uv\in E(G)$ and $C(u)\geq{\sf w}(e)$. Then the pebbling step $u\mapsto v$ removes ${\sf w}(e)$ pebbles from $u$ and adds one pebble to $v$. Thus, after such a step, the resulting configuration $C^{\prime}$ has $C^{\prime}(u)=C(u)-{\sf w}(e)$, $C^{\prime}(v)=C(v)+1$, and $C^{\prime}(x)=C(x)$ otherwise. We say that $C$ is $r$-solvable if it is possible to win this challenge, and $r$-unsolvable otherwise. For example, suppose $r=v_{1}$ in $P_{n}$, set ${\sf w}(v_{i}v_{i+1})=w_{i}$ for each $1\leq i<n$, and let $t=\prod_{i=1}^{n-1}w_{i}$. It is straightforward to show by induction that (a) the configuration with $t-1$ pebbles on $v_{n}$ and 0 elsewhere is $r$-unsolvable, while (b) any configuration of size $t$ is $r$-solvable.

Thus we are led to define the rooted pebbling number ${\pi}(G,r)$ of a weighted graph $G$ to be the minimum number of pebbles $t$ such that every size $t$ configuration is $r$-solvable. From the above we have ${\pi}(P_{n},v_{1})=\prod_{i=1}^{n-1}w_{i}$. Next we define the pebbling number of $G$ as ${\pi}(G)=\max_{r}{\pi}(G,r)$. Any configuration of this size is therefore $r$-solvable for every possible target $r$. Again, it is fairly evident that ${\pi}(P_{n})={\pi}(P_{n},v_{1})$.

Since one can read the proof of Theorem 2 in [6, 10], we only sketch the main idea and connection through an example.

Suppose that we are given $45$ integers, including $32$, $-11$, $31$, $51$, $42$, $-24$, $48$, $75$ and $-15$. We envision the lattice $L$ of divisors of $45$ (having relation $a\prec b$ when $a|b$), but think of $L$ as a graph $G$. In particular, $G$ has vertices $v_{a}$ for each divisor $a$ of $45$, with edges between $v_{a}$ and $v_{b}$ if (1) $a|b$ and (2) $c\in\{a,b\}$ whenever $a|c$ and $c|b$. Notice that $G$ is isomorphic to the $2\times 1$ grid $P_{3}\Box P_{2}$ because $45=3^{2}\cdot 5^{1}$. The edges of $G$ are then weighted so that the edge $e=v_{a}v_{b}$, where $a|b$, has cost ${\sf w}(e)=b/a$.

Numbers like $32$, $-11$, and $31$ will be placed as labeled pebbles at vertex $v_{1}$ because the are relatively prime to $45$; i.e. their ${\sf gcd}$ with $45$ equals $1$. More generally, each number $m$ is placed as a labeled pebbled at vertex $v_{k}$, where $k={\sf gcd}(m,45)$. What this placement guarantees is that each pebble by itself satisfies local versions of both properties of interest. That is, with respect to vertex $v_{15}$, for example, the pebble labeled $30$ is $0\pmod{15}$ and $1/|30|\leq 1/|15|$.

Given any three pebbles at $v_{1}$, such as $32$, $-11$, and $31$, Theorem 3 guarantees that we can find a subset of them, namely $32$ and $-11$, that is a zero-sum modulo $3$. Thus we remove them all from $v_{1}$, create a new pebble labeled $\{32,-11\}$, and place the new pebble at $v_{3}$. This represents a pebbling step from $v_{1}$ to $v_{3}$ because ${\sf w}(v_{1}v_{3})=3$. Also, this new pebble satisfies the local properties at $v_{3}$ because ${\sf gcd}(32-11,45)=3$ and $1/|32|+1/|-11|\leq 3(1/|1|)=1/|3|$. From the summation (not the orders) perspective, the pebble $\{32,-11\}$ acts like a pebble with label $21$ — we think of $21$ as the nickname of $\{32,-11\}$.

Now, since the pebbles $51$, $42$, $-24$, and $48$ are also at $v_{3}$, we can use Theorem 3 on these four pebbles and the newly arrived “$21$” to find a subset, such as $51$, $48$, and $21$, that sums to zero modulo $5$ (which results in zero modulo $15$ because they are each zero modulo $3$ already). Thus we remove them all from $v_{3}$, create a new pebble nestedly labeled $\{51,48,\{32,-11\}\}$, and place the new pebble at $v_{15}$. This represents a pebbling step from $v_{3}$ to $v_{15}$ because ${\sf w}(v_{3}v_{15})=5$. Also, this new pebble satisfies the local properties at $v_{15}$ because ${\sf gcd}(51+48+21,45)=15$ and $1/|51|+1/|48|+1/|21|\leq 5(1/|3|)1/|15|$. The new pebble has nickname $51+48+21=120$.

Finally, since the pebbles $75$ and $-15$ are also at $v_{15}$, we can use Theorem 3 on these two pebbles and the newly arrived “$120$” to find a subset, such as $75$, $-15$, and $120$, that sums to zero modulo $3$ (which results in zero modulo $45$ because they are each zero modulo $15$ already). Thus we remove them all from $v_{15}$, create a new pebble nestedly labeled $\{75,-15,\{51,48,\{32,-11\}\}\}$, and place the new pebble at $v_{45}$. This represents a pebbling step from $v_{15}$ to $v_{45}$ because ${\sf w}(v_{15}v_{45})=3$. Also, this new pebble satisfies the local properties at $v_{45}$ because ${\sf gcd}(75-15+120,45)=45$ and $1/|51|+1/|48|+1/|120|\leq 3(1/|45|)=1/|15|$.

The realization that the local properties at $v_{45}$ are equivalent to the sought-after original properties yields the solution $\{75,-15,51,48,32,-11\}$.

The above gives a sense of how Lagarias-Saks pebbling models the sequential construction of a zero-sum sequence with small cross number. Chung then used retracts to reduce the pebbling problem on divisor lattices (i.e. products of paths) to a similar pebbling problem on cubes (i.e. products of edges), subsequently finding the appropriate pebbling number of cubes. The consequence of these results is what proves Theorem 2 and, essentially, Theorem 3. There are extra wrinkles to the general abelian group case, involving a specialized representation of them and using Ferrer’s diagrams of partitions and their duals. Furthermore, the technique actually results in the following generalization. For an additive group ${\Gamma}$ with subgroup ${\sf H}$, the sequence $g_{1},\ldots,g_{t}$ of elements of ${\Gamma}$ is an ${\sf H}$-sum sequence if $g_{1}+\cdots+g_{t}\in{\sf H}$.

It should be noted that, while Chung’s method takes advantage of writing a cyclic group as ${\Gamma}=\prod_{i=1}^{d}{\mathbb{Z}}_{p_{i}^{k_{i}}}$, where $p_{1},\ldots,p_{d}$ are distinct primes, Theorem 6 allows for any number of these primes to be identical. In this more general case the graph $G({\Gamma})$ corresponding to the lattice $L=L({\Gamma})$ is not always the divisor lattice of $\prod_{i=1}^{d}p_{i}^{k_{i}}$; instead it is always the product of paths: $G({\Gamma})=\Box_{i=1}^{d}P_{k_{i}+1}$.

We fix a number of pebbles (or sequence length) $t$, and assume that our host graph $G$ (or group $\Gamma$) has order $n$. We select an initial configuration of $t$ pebbles (sequence elements) uniformly at random among all size $t$ configurations; there are $\binom{n+t-1}{t}$ such configurations. We denote this probability space by $\mathcal{D}_{G,t}$ ($\mathcal{D}_{{\Gamma},t}$). It is worth noting that this is not the same distribution that one gets by placing each of $t$ pebbles onto the graph at random – in this latter scheme, large piles of pebbles are much more likely. Throughout, we remain interested in the configuration model. We further note that this is in line with the random model for sequences discussed earlier, where we selected a length $t$ sequence uniformly among all length $t$ sequences in ${\Gamma}$.

With our probability space in place, we can now begin to make precise our leading question “How many pebbles are necessary to make it likely that our random initial configuration is solvable?” In particular, we define the quantity ${{\bf P}_{\nicefrac{{1}}{{2}}}}(G)$¹¹1It may seem like our choice of $\nicefrac{{1}}{{2}}$ is arbitrary; however, as we’ll be focused on cases where our probabilities are either very near 0 or very near 1, this choice will make no difference to the remainder of the work. Any choice of $p\in(0,1)$ would yield identical theorems.. Again, this is precisely in line with to our earlier ${{\bf P}_{\nicefrac{{1}}{{2}}}}(\cdot)$ definitions in the introduction.

While determining ${{\bf P}_{\nicefrac{{1}}{{2}}}}(G)$ for any particular graph is an interesting problem, it is also a very hard one. Here, we focus here on sequences of graphs. That is, given some infinite sequence of graphs ${\cal G}=\left(G_{i}\right)_{i\in{\mathbb{N}}}$, what can we say about the asymptotics of ${{\bf P}_{\nicefrac{{1}}{{2}}}}(G_{n})$ as a function of $n$? We again use the the language of thresholds to describe our results.

As an example, let $K_{n}$ denote the complete graph on $n$ vertices: every pair of vertices is adjacent. When our sequence of graphs is the sequence of complete graphs ${\cal K}=\left(K_{n}\right)_{n\in{\mathbb{N}}}$ with uniform edge weights ${\sf w}(e)=2$, then we find ourselves in a situation similar to Feller’s Birthday problem (page 33 of [12]) – our configuration is solvable if either we have a pebble on every vertex or if there are two pebbles on any one vertex (since one pebble’s sacrifice will allow the survivor to travel to any vertex at all). The unsolvable $t$-configurations are thus the ones with $t$ pebbles distributed injectively to the $n$ vertices; there are $\binom{n}{t}$ such $t$-configurations, and so the probability that a random configuration is solvable is $1-\binom{n}{t}\big{/}\binom{n+t-1}{t}$. It is straightforward to show that this probability tends to $1$ when $t(n)=c(n)\sqrt{n}$ with $c(n)\to\infty$, and that it approaches $0$ if $c(n)\to 0$; this shows that $\sqrt{n}$ is a threshold for ${\cal K}$, though it does not show that this threshold is sharp. (The only difference between pebbling and birthdays is that in Feller’s problem the people are labeled, whereas here the pebbles are unlabeled.)

In [2], the authors prove the existence of weak thresholds for monotone families of multisets. Because the family of unsolvable configurations is monotone (closed under removing pebbles), they obtain the following theorem.

As a concrete example, the sequence of papers [7, 2, 20] produced ever-sharpening estimates on the (${\sf w}=2$) pebbling threshold for the sequence of paths, leading to the following result.

Note that, since the constant $c$ in the exponent is a multiplicative factor, Theorem 8 does not yield a weak threshold (although Theorem 8 guarantees the existence of such a threshold). Such a threshold was established in a sharp form in [4].

One can view an $n$-dimensional grid as a product of paths, and so the above results for paths can be seen as the first step toward establishing thresholds for grids of fixed dimension. A weak threshold was established in [4], in the somewhat more general setting where pebbling moves in different grid directions can have different costs (we note that the $O(1)$ term in the exponent here as opposed to the $o(1)$ term in the previous theorem is the subtle difference causing one to be weak and one to be sharp.

At another extreme, if instead one takes a product of ‘$P_{2}$’s with increasing dimension we find the sequence of $d$-cubes, ${\cal Q}$. Several groups studied thresholds for pebbling $d$-cubes, culminating in the following theorem.

In this case, Theorem 11 translates into the following bounds on the threshold for ${\mathbb{Z}}_{2}^{d}$.

We end this section with a concrete example of Theorem 4; we believe that this gives an instructive look at the result in the case of a relatively small group of simple form.