WorksMathematics
A disproof of the van Emde Boas–Kruyswijk conjecture on the Davenport constant
Abstract
The Davenport constant of a finite abelian group is the smallest positive integer such that every sequence with terms from and with length has a nontrivial zero-sum subsequence. A long-standing conjecture, first proposed by van Emde Boas and Kruyswijk in 1969, states that for all positive integers and . We disprove this conjecture for every exponent with odd. For each such , we prove that for every .
Introduction
Let with be a finite abelian group. A straightforward example shows that
Already in the 1960s, it was proved that equality holds for -groups and for groups of rank at most two. This was achieved independently by Kruiswijk and Olson. Also, already in the 1960s, a first counterexample was found showing that strict inequality may hold. Since the Davenport constant is closely connected to a variety of problems in graph theory, finite geometry, combinatorics, and factorization theory, it received wide attention in the last decades. In parallel with the study of the exact value of the Davenport constant, the structure of minimal zero-sum sequences of length was investigated. There is a wealth of literature on this topic (see [5] for an overview).
In 1969, van Emde Boas and Kruyswijk [9 §12, p. 31] proposed the following conjecture.
Conjecture 1. For all positive integers and ,
Although it was proved that for groups for odd [4], the precise value of remained open (even in case ; as late as 2018, even the value of was unknown [6 p. 606]). In spite of such results, Conjecture 1 became a prominent longstanding problem in zero-sum theory, and it was expected to hold true (see [1 Conjecture A.5], [3 Conjecture 3.5], [6 Conjecture 1], and [10 Conjecture 3]). Also several recent results seemed to support this conjecture (e.g., [11]).
Our main result disproves Conjecture 1 for every with .
Theorem 1.1. Let , where is odd. For every positive integer ,
In particular, for every .
Note that Theorem 1.1 also disproves a conjectured result on coverings (see [2 Theorem 6.6]).
Notation and terminology
We follow notation and terminology used in [3 §2]. Groups are written additively. We denote by the cyclic group of order , by the direct sum of copies of , and by the subgroup generated by .
We consider sequences over as elements of the free abelian monoid with basis . We write , where is the multiplicity of in . The element is called the trivial sequence. We write if is a subsequence of , that is, if for every . The length of is and its sum is , with . In particular, denotes a sequence of copies of , whose sum is .
The set of subsums is . We call a zero-sum sequence if , and zero-sumfree if . The maximal length of a zero-sumfree sequence over is , so . For the invariant factors of , put . Taking copies of a generator of each cyclic summand gives a zero-sumfree sequence, whence . The homocyclic assertion of [3 Conjecture 3.5] is for .
We identify with . The standard basis element has a in position and zeros elsewhere. Thus , with coefficients taken modulo . For integers , let . For a statement , the indicator is if holds and otherwise.
The proof of Theorem 1.1
Throughout this section let with odd, and put and . To prove Theorem 1.1, we construct a zero-sumfree sequence of length over .
Let be a basis of . Set
Call the th row of . For , including , the table gives the possible coefficients of in for the indicated projections onto . All coefficients are taken modulo .
| Projection of | Coefficient of |
Table 2.
For projection zero, omitting forces every row to be empty, and selecting forces every row to be full. The two sums are and , respectively. For projection , consider the counts in row , row , and the remaining row, in that order. Without the counts are , so the coefficient of is or . With the counts are . If the term omitted from row has coefficient on , the total coefficient is , giving the same two residues.
Lemma 3.1. There exist an element of order and a zero-sumfree sequence of length over such that .
Proof. Let . By the first row of (2), a subsequence of with zero projection has coefficient of in , with zero attained only by the trivial subsequence. Hence is zero-sumfree and . For , put . By the second row of (2), a subsequence summing to would require or of the additional copies of . Thus .
Let be the list consisting of , , and copies of . Its sum is . In , place in the first summand and append the terms to obtain . Then .
Put . Since is even, , and the last coordinate of has order .
We show that is zero-sumfree. A zero sum omitting must omit all by the last coordinate, and hence is trivial. A zero sum using must use exactly of the . If is omitted, the other appended terms together with sum to . This would require a subsequence of with sum , which was excluded above. The assertion follows. □
Proof of Theorem 1.1. Let generate a cyclic group of order . For each , let and let have basis . We work in the direct sum
Define elements of by
Thus has a component in every , whereas among only has a component in .
In each take a copy of the sequence in Lemma 3.1, with corresponding element . Let be the image of under the homomorphism defined by for and . Consider the sequence
Suppose a subsequence of has sum zero. Let indicate whether is selected, and let indicate whether is selected. Fix . To cancel the components of and in , the selected terms of must have projection
This is zero if . Otherwise it is , , or . By (2), the coefficient of contributed by is modulo , with . Since , the selected terms of must sum to in . Lemma 3.1 rules out and then forces the selection from to be empty. Thus the selected terms of contribute in whenever or is selected. If both are omitted, the projection onto and the coefficient of are both zero, so the selection from is empty as well.
Put . If is omitted, exactly of the sequences contribute . The total coefficient of is . Since , we must have , and the entire subsequence is empty. If is selected, each of the sequences contributes . The total coefficient of is then , which is odd and hence nonzero modulo . This proves that is zero-sumfree.
The group has rank . Each has length , so . Write with . Take copies in independent summands and copies of a basis element in each of the remaining coordinates. Their product is zero-sumfree and has length . Since , the stated bound follows. □
Remark. For clarity, we have presented Theorem 1.1 in a simpler form. Under the same hypotheses, an iterated construction gives
For some exponents the bound can be improved further. For example, when , one has
for every positive integer .
References
Center for Applied Mathematics and KL-AAGDM, Tianjin University, Tianjin 300072, P.R. China Email address: [email protected]
Department of Mathematics and Scientific Computing, University of Graz, Graz, Austria Email address: [email protected]
School of Mathematical Sciences, Tiangong University, Tianjin 300387, P.R. China Email address: [email protected]
Sino-French Institute of Nuclear Engineering and Technology, Sun Yat-Sen University, Guangzhou 510275, P.R. China Email address: [email protected]
References
- [1]N. Alon, S. Friedland and G. Kalai, Regular subgraphs of almost regular graphs, J. Combin. Theory Ser. B 37 (1984), 79–91.DOI
- [2]W. Gao and A. Geroldinger, Zero-sum problems and coverings by proper cosets, European J. Combin. 24 (2003), 531 – 549.DOI
- [3]W. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: a survey, Expo. Math. 24 (2006), 337–369.DOI
- [4]A. Geroldinger and M. Liebmann and A. Philipp, On the Davenport constant and on the structure of extremal sequences, Period. Math. Hung. 64 (2012), 213 – 225.
- [5]A. Geroldinger, D.J. Grynkiewicz, and Q. Zhong, Combinatorial Factorization Theory, Math. Surveys Monogr., vol. 296, American Mathematical Society, Providence, RI, 2026.
- [6]B. Girard, An asymptotically tight bound for the Davenport constant, J. Éc. polytech. Math. 5 (2018), 605–611.
- [9]P. van Emde Boas and D. Kruyswijk, A combinatorial problem on finite abelian groups III, Mathematisch Centrum, Amsterdam, ZW 1969-008, December 1969.
- [10]G. Wang, Disproving conjectures on the Davenport and Narkiewicz constants, arXiv:2609.29878v5 (2026).arxiv.org/abs/2609.29878
- [11]Q. Zhong, On the Characterization Problem for Krull monoids with Homocyclic Class Groups. arXiv:26010.34288arxiv.org/abs/2610.34288