Zero-Sums

The origins of graph pebbling reside in combinatorial number theory and group theory. A sequence of elements of a finite group $G$ is called a zero-sum sequence if it sums to the identity of $G$. A simple pigeonhole argument (on the sequence of partial sums) proves the following statement.

Pigeonhole Fact.   Any sequence of $|G|$ elements of a finite group $G$ contains a nonempty zero-sum subsequence.

In fact, a subsequence of consecutive terms can be guaranteed by the pigeonhole argument. Furthermore, one can instead stipulate that the zero-sum subsequence has at most $N$ terms, where $N=N(G)$ is the exponent of $G$ (i.e. the maximum order of an element of $G$) and this is best possible.

EGZ Theorem

Initiated in 1956 by Erdos [Erd1], the study of zero-sum sequences has a long history with many important applications in number theory and group theory. In 1961 Erdos, Ginzburg, and Ziv [EGZ] proved the following theorem.

EGZ Theorem.   Every sequence of $2|G|-1$ elements of a cyclic group $G$ contains a nonempty zero-sum subsequence of length exactly |G|.

In 1969 van Emde Boas and Kruyswijk [EmKr] proved that any sequence of $N(1+\log(|G|/N))$ elements of a finite abelian group contains a nonempty zero-sum sequence. In 1994 Alford et al. [AGP] used this result and modified Erdos's arguments to prove that there are infinitely many Carmichael numbers.

Davenport's Constant

Much of the recent study has involved finding Davenport's constant $D(G)$, defined to be the smallest $D$ such that every sequence of $D$ elements contains a nonempty zero-sum subsequence [Ols]. There are a wealth of results on this problem [Car, Gao, GaGe, GaTh, GeSc, Sun] and its variations [GaJi, Nat].

Pebbling Birth

In 1989 Kleitman and Lemke [LeKl], and independently Chung [Chu], proved the following theorem (originally stated number-theoretically), strengthening the Pigeonhole Fact. Let $\mathbb{Z}_n$ denote the cyclic group of order $n$, and let $|g|$ denote the order of an element $g$ in the group to which it belongs.

KLC Theorem.   For every sequence $(g_k)_{k=1,\ldots,n}$ of $n$ elements from $\mathbb{Z}_n$, there is a zero-sum subsequence $(g_k)_{k \in K}$ such that $\displaystyle{\sum_{k \in K} \frac{1}{|g_k|} \leq 1.}$

For a sequence $S$ the sum $\sum_{g \in S} 1/|g|$ is known as the cross number of $S$ and is an important invariant in factorization theory. Guaranteeing cross number at most $1$ strengthens the extension of the Pigeonhole Fact that $|K| \leq N(G)$, and shows that equality holds if and only if every $|g_k|=N$. The concept of pebbling in graphs arose from an attempt by Lagarias and Saks to give an alternative (and more natural and structural) proof than that of Kleitman and Lemke; it was Chung who carried out their idea. See also [Den] for another extension of this result.

Kleitman and Lemke then conjectured that the KLC Theorem holds for all finite groups. For a subgroup $H$ of $G$ call a sequence of elements of $G$ an $H$-sum sequence if its elements sum to an element of $H$. In [ElHu, Ger] is proved the following theorem (the methods of [ElHu] use graph pebbling).

GEH Theorem.   Let $H$ be a subgroup of a finite abelian group $G$ with $|G|/|H| = n$. For every sequence $(g_k)_{k=1,\ldots,n}$ of $n$ elements from $G$ there is an $H$-sum subsequence $(g_k)_{k \in K}$ such that $\displaystyle{\sum_{k \in K} \frac{1}{|g_k|} \leq \frac{1}{|\sum_{k \in K}g_k|}}.$

The case $H=\{e\}$ here gives the KLC Theorem for finite abelian groups, strengthening the van Emde Boas and Kruyswijk result [EmKr]. Kleitman and Lemke also conjectured that the GEH Theorem holds for all finite groups, and verified their conjecture for all dihedral groups (see [LeKl]). For other nonabelian groups, it has been shown recently to hold for the nonabelian solvable group of order $21$ (see [ElHu]).

Olson's Conjecture

It would be interesting to see whether graph pebbling methods can shed light on the Davenport constant for finite abelian groups. In this regard, one of the most pressing questions is as follows. Write $G=\prod_{i=1}^r \mathbb{Z}_{n_i}$, where $1 < n_1 | n_2 | \cdots | n_r$. Then $r=r(G)$ is the rank of $G$. It is natural to guess that $D(G)=\sum_{i=1}^r n_i-r+1 = 1+\sum_{i=1}^r(n_i-1)$. from pigeonhole intuition. This was conjectured By Olson in [Ols] and is true by the KLC Theorem for rank $1$ groups. Moreover, it was proven in [Ols] for rank $2$ groups and $p$-groups as well. However, it was proven in [EmKr, GeSc] that the conjecture is false for some groups each rank at least $4$. What remains open is the instance of rank $3$.

Applications

There are applications in factorization theory [Cha] and graph theory [AFK].

References

N. Alon, S. Friedland, and G. Kalai Regular subgraphs of almost regular graphs J. Combin. Theory Ser. B 37 (1984), 79--91

W. R. Alford, A. Granville and C. Pomerance There are infinitely many Carmichael numbers Annals Math. Ser. 2 139 (1994), no. 3, 703--722

Y. Caro Zero-sum problems--a survey Discrete Math 152 (1996), 93--113

S. Chapman On the Davenport constant, the cross number, and theor application in factorization theory Zero-dimensional commutative rings, Lecture notes in Pure Appl. Math 171 (1997), 119--128

P. van Emde Boas and D. Kruyswijk A combinatorial problem on finite Abelian groups III Report ZW-1969-007, Math. Centre, Amsterdam

P. Erdos On pseudoprimes and Carmichael numbers Publ. Math. Debrecen 4 (1956), 201--206

P. Erdos, A. Ginzburg and A. Ziv A theorem in additive number theory Bull. Res. Council Israel 10F (1961), 41--43

W. Gao On Davenport's constant of finite Abelian groups with rank three Discrete Math. 222 (2000), 111--124

W. Gao and A. Geroldinger Zero-sum problems and coverings by proper cosets Euro. J. Combin. 24 (2003), 531--549

W. Gao and X. Jin Weighted sums in finite cyclic groups Discrete Math. 283 (2004), 243--247

W. Gao and R. Thangadurai On the structure of sequences with forbidden zero-sum subsequences Colloq. Math. 98 (2003), 213--222

A. Geroldinger On a conjecture of Kleitman and Lemke J. Number Theory 44 (1993), 60--65

A Geroldinger and R. Schneider On Davenport's Constant J. Combin. Theory Ser. A 61 (1992), 147--152

M. Nathanson Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Graduate Texts in Mathematics; 165), Springer-Verlag, New York (1996), 48--51

J. Olson A combinatorial problem on finite Abelian groups I J. Number Theory 1 (1969), 8--10

Z. Sun Unification of zero-sum problems, subset sums and covers of Z Elec. Res. Announce. Amer. Math. Soc. 9 (2003), 51--60