Sharp upper bounds for the Davenport constant of finite abelian groups: the Narkiewicz–Śliwa conjecture and short zero-sum constants at rank at least three

The Davenport constant $D(G)$ of a finite abelian group $G\cong C_{n_1}\oplus\cdots\oplus C_{n_r}$ (order $n$, exponent $m$) is the least $t$ such that every sequence of $t$ elements of $G$ contains a nonempty zero-sum subsequence; it is bounded below by $M(G)=1+\sum_i(n_i-1)$. The source paper (Balasubramanian–Bhowmik, 2006/2007) proved $D(G)\le n/k+k-1$ for all integers $k\le 7$ whenever $n/m\ge k$, conjectured the same for every $k\le\sqrt n$, and recorded as open the Narkiewicz–Śliwa conjecture $D(G)\le M(G)+r-1$ and the determination of the short zero-sum constants $D_p(\mathbb{Z}_p^r)=\eta(\mathbb{Z}_p^r)$ for rank $r\ge 3$. Subsequent work: the $\sqrt n$-conjecture was proved by Bhowmik–Schlage-Puchta in 2012 ($D(G)\le m+n/m-1$ in general, $D(G)\le 2\sqrt n-1$ when $m<\sqrt n$). The surviving open core, stated here as the problem, is the sharpness of general-rank bounds: (1) prove or refute $D(G)\le M(G)+r-1$ — open even at rank 3, where $D(G)=M(G)$ itself is conjectured — and (2) determine the exact short zero-sum constants at rank $\ge 3$ (best known estimate: Alon–Dubiner's $\eta(\mathbb{Z}_p^r)\le c(r)p$, with $c(r)$ of order $(r\log r)^r$).

Background

Let $G$ be a finite abelian group, written additively, of order $n$ and exponent $m$ (the largest order of any element). Every such group decomposes uniquely as $G\cong C_{n_1}\oplus\cdots\oplus C_{n_r}$ with integers $1<n_1\mid n_2\mid\cdots\mid n_r=m$, its invariant factors; $r$ is the rank of $G$ and $C_d$ denotes the cyclic group of order $d$. By a sequence over $G$ we mean a finite unordered list of elements of $G$, repetitions allowed; a subsequence is a sub-multiset. The Davenport constant $D(G)$ is the least $t$ such that every sequence of length at least $t$ over $G$ contains a nonempty subsequence whose terms sum to $0$. It originated in algebraic number theory — Davenport introduced it in 1966 as the maximal number of prime ideals, counted with multiplicity, dividing an irreducible element in the ring of integers of a number field whose ideal class group is $G$ — and it is now a central object of zero-sum theory, the part of combinatorial number theory studying forced zero-sum configurations. The classical companion is the Erdős–Ginzburg–Ziv constant $s(G)$, the least $t$ such that every sequence of length $t$ contains a zero-sum subsequence of length exactly the exponent of $G$ (the theorem of Erdős, Ginzburg and Ziv gives $s(C_n)=2n-1$). Gao proved that the closely related constant defined in the same way except that the zero-sum subsequence must have length exactly $n=|G|$ equals $n+D(G)-1$ for every finite abelian group, so the two problems track each other. Upper bounds for $D(G)$ also have arithmetic uses: the logarithmic bound $D(G)\le m(1+\log(n/m))$, due to van Emde Boas and Kruyswijk, was one input in the proof that infinitely many Carmichael numbers (composite numbers that are Fermat pseudoprimes to every coprime base) exist.

A sequence containing $n_i-1$ copies of the $i$-th basis element has no nonempty zero-sum subsequence (such sequences are called zero-sum free), so $D(G)\ge M(G):=1+\sum_{i=1}^r(n_i-1)$; in the source paper's notation this lower bound is written $M(G)$. Olson proved $D(G)=M(G)$ for $p$-groups (groups of prime-power order), and — independently of van Emde Boas and Kruyswijk — for all groups of rank at most 2, e.g. $D(C_m\oplus C_n)=m+n-1$ for $m\mid n$. The guess $D(G)=M(G)$ for all finite abelian groups was disproved by Geroldinger and Schneider, who showed that for every rank $r\ge 4$ there are infinitely many groups with $D(G)>M(G)$; whether $D(G)=M(G)$ always holds at rank 3 is a famous open problem, settled only for special families such as $C_3\oplus C_3\oplus C_{3d}$ (Bhowmik–Schlage-Puchta).

General upper bounds are far cruder. Balasubramanian and Bhowmik (2006/2007) proved that $D(G)\le n/k+(k-1)$ for every integer $k\le 7$ whenever $n/m\ge k$ — the hypothesis is necessary, since cyclic groups have $D(G)=n$ — and conjectured the same for every $k\le\sqrt n$, noting that this would be weaker than the Narkiewicz–Śliwa conjecture $D(G)\le M(G)+r-1$ for groups of rank $r$ (as the source records it). Bhowmik and Schlage-Puchta proved this conjecture in 2012: $D(G)\le m+n/m-1$ always holds (already attained at rank 2), and $D(G)\le 2\sqrt n-1$ when $m<\sqrt n$; since $n/k+k-1$ is decreasing in $k$ on $[1,\sqrt n]$, this yields the bound for every admissible $k\le\sqrt n$.

What remains unsettled is the excess of $D(G)$ over $M(G)$ at rank $\ge 3$, quantified by two further constants. The short zero-sum constant $\eta(G)$ — written $D_p(\mathbb{Z}_p^r)$ in the source for $G=\mathbb{Z}_p^r$ — is the least $t$ such that every sequence of length $t$ over $G$ contains a zero-sum subsequence of length at most the exponent of $G$. Olson determined the rank-2 values ($\eta(C_p^2)=3p-2$, the key to the rank-2 Davenport constant); the source records $\eta(C_2^3)=8$, $\eta(C_3^3)=17$, $\eta(C_4^3)=22$. For rank $r\ge 3$ no formula is known; the theorem of Alon and Dubiner gives $\eta(\mathbb{Z}_p^r)\le c(r)p$ with $c(r)$ of order $(r\log r)^r$. Gao conjectured further that $s(G)=\eta(G)+\exp(G)-1$ for every finite abelian group (verified for many classes of groups), so $\eta$ governs the Erdős–Ginzburg–Ziv constant as well. Via the inductive method (recursively peeling off short zero-sum blocks and reducing to a quotient group), bounds for $\eta$ propagate into the best general upper bounds for $D(G)$ itself, of the shape $D(G)\le M(G)(Kr\log r)^r$ in general rank and $D(G)\le n_3+n_2+Kn_1=M(G)+O(n_1)$ at rank 3 (the source's Theorem 2), with constants inherited from Alon–Dubiner. Thus the additive question — is $D(G)-M(G)$ bounded by the rank? (Narkiewicz–Śliwa) — and the multiplicative question — what is the true rank-dependence of $\eta(\mathbb{Z}_p^r)$? — are the two surviving sharpness questions for general upper bounds on the Davenport constant after the 2012 resolution of the $n/k+k-1$ conjecture.

Problem Statement

Determine the sharp upper-bound behavior of the Davenport constant of a finite abelian group, in the two precise forms (1) and (2) below. These two components are separately posed open problems: a proof or refutation of (1) settles the additive-excess question, and an exact determination of the constants in (2) settles the short zero-sum question. Throughout, $G\cong C_{n_1}\oplus\cdots\oplus C_{n_r}$ with $1<n_1\mid n_2\mid\cdots\mid n_r$ is a finite abelian group given by its invariant factors, where $C_d$ denotes the cyclic group of order $d$, $r$ is the rank of $G$ and $n_r$ is its exponent (the largest order of any element); by a sequence over $G$ we mean a finite unordered list of elements of $G$, repetitions allowed. The Davenport constant $D(G)$ is the least $t$ such that every sequence of $t$ elements of $G$ contains a nonempty subsequence whose terms sum to $0$. Write $M(G)=1+\sum_{i=1}^r(n_i-1)$, and let $\eta(G)$ be the least $t$ such that every sequence of $t$ elements of $G$ contains a nonempty zero-sum subsequence of length at most $n_r$ (the source paper's $D_p(\mathbb{Z}_p^r)$ is $\eta(\mathbb{Z}_p^r)$).

(1) Narkiewicz–Śliwa conjecture, as recorded in the source paper. Prove or disprove that

$D(G)\;\le\;M(G)+r-1$

for every finite abelian group $G$ of rank $r$. The crucial open case is rank 3: is $D(C_{n_1}\oplus C_{n_2}\oplus C_{n_3})\le M(G)+2$ for all $n_1\mid n_2\mid n_3$? Even the stronger classical conjecture $D(G)=M(G)$ for all rank-3 groups, open since the 1960s, would imply this. A disproof consists of one explicit group $G$ together with a zero-sum-free sequence over $G$ of length $M(G)+r-1$.

(2) Short zero-sum constants at rank at least three. For each integer $r\ge 3$, determine $\eta(\mathbb{Z}_p^r)$ as a function of the prime $p$ (here $\mathbb{Z}_p^r\cong C_p^r$ is the elementary abelian group, the direct sum of $r$ copies of $C_p$). The best known general estimate is the Alon–Dubiner bound $\eta(\mathbb{Z}_p^r)\le c(r)p$ with $c(r)$ of order $(r\log r)^r$; the true rank-dependence of these constants is not known.

The two components are the surviving open core of the source paper's program and are linked rather than coincident: component (1) asks whether the excess of $D(G)$ over $M(G)$ at rank $\ge 3$ is additively bounded by the rank, while component (2) fixes the rank-dependence of the short zero-sum constants that, through the inductive method, drive every currently known general-rank upper bound for $D(G)-M(G)$ (e.g. the source's rank-3 bound $D(G)\le n_3+n_2+Kn_1$, an error term linear in $n_1$, with $K$ inherited from the Alon–Dubiner constant).

References

1. R. Balasubramanian and Gautami Bhowmik, 'Upper Bounds for the Davenport Constant', in Combinatorial Number Theory (Proceedings of the Integers Conference 2005), Walter de Gruyter, 2007, pp. 61–69, and in Integers 7(2), Paper A3 (2007); DOI 10.1515/9783110925098.61; arXiv:math/0601374, https://arxiv.org/abs/math/0601374
2. Gautami Bhowmik and Jan-Christoph Schlage-Puchta, 'Davenport's constant for groups with large exponent', Contemporary Mathematics 579, American Mathematical Society, 2012, pp. 21–31; DOI 10.1090/conm/579/11515; arXiv:1702.03403, https://arxiv.org/abs/1702.03403
3. Gautami Bhowmik and Jan-Christoph Schlage-Puchta, 'Davenport's constant for groups of the form Z_3 ⊕ Z_3 ⊕ Z_{3d}', CRM Proceedings and Lecture Notes 43, American Mathematical Society, 2007, pp. 307–326; DOI 10.1090/crmp/043/17; arXiv:math/0610416, https://arxiv.org/abs/math/0610416
4. N. Alon and M. Dubiner, 'A lattice point problem and additive number theory', Combinatorica 15 (1995), 301–309; DOI 10.1007/BF01299737, https://doi.org/10.1007/BF01299737
5. J. E. Olson, 'A combinatorial problem on finite Abelian groups, I', Journal of Number Theory 1 (1969), 8–10; DOI 10.1016/0022-314X(69)90021-3, https://doi.org/10.1016/0022-314X(69)90021-3
6. J. E. Olson, 'A combinatorial problem on finite Abelian groups, II', Journal of Number Theory 1 (1969), 195–199; DOI 10.1016/0022-314X(69)90037-7, https://doi.org/10.1016/0022-314X(69)90037-7
7. A. Geroldinger and R. Schneider, 'On Davenport's constant', Journal of Combinatorial Theory, Series A 61 (1992), 147–152; DOI 10.1016/0097-3165(92)90061-X, https://doi.org/10.1016/0097-3165(92)90061-X
8. W. Gao, 'Addition theorems for finite abelian groups', Journal of Number Theory 53 (1995), 241–246; DOI 10.1006/jnth.1995.1089, https://doi.org/10.1006/jnth.1995.1089
9. Paul Erdős, Abraham Ginzburg and Abraham Ziv, 'Theorem in the additive number theory', Bulletin of the Research Council of Israel 10F (1961), 41–43; zbMATH 0063.00009; original scan at https://www.renyi.hu/~p_erdos/1961-25.pdf
10. W. R. Alford, A. Granville and C. Pomerance, 'There are infinitely many Carmichael numbers', Annals of Mathematics (2) 139 (1994), 703–722; DOI 10.2307/2118576, https://doi.org/10.2307/2118576
11. Maciej Zakarczemny, 'Note on the Davenport's constant for finite abelian groups with rank three', arXiv:1910.10984 (2019), https://arxiv.org/abs/1910.10984
12. Benjamin Girard and Wolfgang Schmid, 'Direct zero-sum problems for certain groups of rank three', Journal of Number Theory 197 (2019), 297–316; DOI 10.1016/j.jnt.2018.08.016; arXiv:1806.07636, https://arxiv.org/abs/1806.07636
13. Benjamin Girard, 'An asymptotically tight bound for the Davenport constant', Journal de l'École polytechnique – Mathématiques 5 (2018), 605–611; DOI 10.5802/jep.79; arXiv:1709.08033, https://arxiv.org/abs/1709.08033
14. Dongchun Han, 'On Davenport constant of finite abelian groups', arXiv:1802.07196 (2018), https://arxiv.org/abs/1802.07196
15. Anamitro Biswas and Eshita Mazumdar, 'Davenport constant for finite abelian groups with higher rank', arXiv:2402.09999 (2024), https://arxiv.org/abs/2402.09999
16. Eric Naslund, 'Exponential Bounds for the Erdős–Ginzburg–Ziv Constant', arXiv:1701.04942 (2017), https://arxiv.org/abs/1701.04942
17. Jacob Fox and Lisa Sauermann, 'Erdős–Ginzburg–Ziv constants by avoiding three-term arithmetic progressions', Electronic Journal of Combinatorics 25(2) (2018), Article #2.14; DOI 10.37236/7275; arXiv:1708.09100, https://arxiv.org/abs/1708.09100
18. Gábor Hegedüs, 'A new exponential upper bound for the Erdős–Ginzburg–Ziv constant', arXiv:1712.00228 (2017), https://arxiv.org/abs/1712.00228; published under the title 'The Erdős–Ginzburg–Ziv constant and progression-free subsets', Journal of Number Theory 186 (2018), 238–247; DOI 10.1016/j.jnt.2017.10.003