betaFeedback

WorksMathematics

A disproof of the van Emde Boas–Kruyswijk conjecture on the Davenport constant

Abstract

The Davenport constant D(G)D(G) of a finite abelian group GG is the smallest positive integer ℓ\ell such that every sequence SS with terms from GG and with length ∣S∣≥ℓ|S| \ge \ell has a nontrivial zero-sum subsequence. A long-standing conjecture, first proposed by van Emde Boas and Kruyswijk in 1969, states that D(Cnr)=r(n−1)+1D(C_n^r)=r(n-1)+1 for all positive integers nn and rr. We disprove this conjecture for every exponent n=2kn=2k with k≥3k\ge3 odd. For each such nn, we prove that D(Cnr)>r(n−1)+1D(C_n^r)>r(n-1)+1 for every r≥8n−7r\ge 8n-7.

Introduction

Let G=Cn1⊕⋯⊕CnrG=C_{n_1}\oplus\cdots\oplus C_{n_r} with 1<n1∣⋯∣nr1<n_1\mid\cdots\mid n_r be a finite abelian group. A straightforward example shows that

D∗(G):=1+∑i=1r(ni−1)≤D(G).(1)D^*(G):=1+\sum_{i=1}^{r}(n_i-1)\le D(G). \tag*{(1)}

Already in the 1960s, it was proved that equality holds for pp-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 D(G)D(G) 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 nn and rr,

D(Cnr)=r(n−1)+1.D(C_n^r)=r(n-1)+1.

Although it was proved that D(G)>D∗(G)D(G)>D^*(G) for groups G=C2⊕C2n4G=C_2\oplus C_{2n}^4 for odd n≥3n\ge3 [4], the precise value of D(Cnr)D(C_n^r) remained open (even in case r=3r=3; as late as 2018, even the value of D(C46)D(C_4^6) 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 n≥6n\ge6 with n≡2(mod4)n\equiv2\pmod{4}.

Theorem 1.1. Let n=2kn=2k, where k≥3k\ge3 is odd. For every positive integer rr,

D(Cnr)≥r(n−1)+1+⌈r8n−7⌉.D(C_n^r)\ge r(n-1)+1+\left\lceil\frac{r}{8n-7}\right\rceil.

In particular, D(Cnr)>r(n−1)+1D(C_n^r)>r(n-1)+1 for every r≥8n−7r\ge8n-7.

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 CnC_n the cyclic group of order nn, by CnrC_n^r the direct sum of rr copies of CnC_n, and by ⟨g⟩\langle g\rangle the subgroup generated by gg.

We consider sequences over GG as elements of the free abelian monoid F(G)\mathcal{F}(G) with basis GG. We write S=g1⋅…⋅gℓ=∏g∈Ggvg(S)S=g_1\cdot\ldots\cdot g_\ell=\prod_{g\in G}g^{v_g(S)}, where vg(S)v_g(S) is the multiplicity of gg in SS. The element 1=1F(G)1=1_{\mathcal{F}(G)} is called the trivial sequence. We write R∣SR\mid S if RR is a subsequence of SS, that is, if vg(R)≤vg(S)v_g(R)\leq v_g(S) for every g∈Gg\in G. The length of SS is ∣S∣=ℓ|S|=\ell and its sum is σ(S)=g1+⋯+gℓ\sigma(S)=g_1+\cdots+g_\ell, with σ(1)=0\sigma(1)=0. In particular, gmg^m denotes a sequence of mm copies of gg, whose sum is mgmg.

The set of subsums is Σ(S)={σ(R):R∣S, R≠1}\Sigma(S)=\{\sigma(R):R\mid S,\ R\neq1\}. We call SS a zero-sum sequence if σ(S)=0\sigma(S)=0, and zero-sumfree if 0∉Σ(S)0\notin\Sigma(S). The maximal length of a zero-sumfree sequence over GG is d(G)d(G), so D(G)=1+d(G)D(G)=1+d(G). For the invariant factors 1<n1∣⋯∣nr1<n_1\mid\cdots\mid n_r of GG, put d∗(G)=∑i=1r(ni−1)d^*(G)=\sum_{i=1}^r(n_i-1). Taking ni−1n_i-1 copies of a generator of each cyclic summand gives a zero-sumfree sequence, whence d(G)≥d∗(G)d(G)\geq d^*(G). The homocyclic assertion of [3 Conjecture 3.5] is d(Cnr)=d∗(Cnr)=r(n−1)d(C_n^r)=d^*(C_n^r)=r(n-1) for n,r≥3n,r\geq3.

We identify CnrC_n^r with (Z/nZ)r(\mathbb{Z}/n\mathbb{Z})^r. The standard basis element eie_i has a 11 in position ii and zeros elsewhere. Thus (x1,…,xr)=∑i=1rxiei(x_1,\ldots,x_r)=\sum_{i=1}^r x_i e_i, with coefficients taken modulo nn. For integers a≤ba\leq b, let [a,b]={a,a+1,…,b}[a,b]=\{a,a+1,\ldots,b\}. For a statement PP, the indicator 1P1_P is 11 if PP holds and 00 otherwise.

The proof of Theorem 1.1

Throughout this section let n=2kn=2k with k≥3k\geq3 odd, and put b=n−1b=n-1 and R=8n−7R=8n-7. To prove Theorem 1.1, we construct a zero-sumfree sequence of length Rb+1Rb+1 over CnRC_n^R.

Let e1,e2,e3,fe_1,e_2,e_3,f be a basis of Cn4C_n^4. Set

z=e1+e2+e3+(1−3k)f,V=z⋅∏i=13eik−1(ei+f)k.z=e_1+e_2+e_3+(1-3k)f,\qquad V=z\cdot\prod_{i=1}^{3}e_i^{k-1}(e_i+f)^k.

Call eik−1(ei+f)ke_i^{k-1}(e_i+f)^k the iith row of VV. For A∣VA\mid V, including A=1A=1, the table gives the possible coefficients of ff in σ(A)\sigma(A) for the indicated projections onto ⟨e1,e2,e3⟩\langle e_1,e_2,e_3\rangle. All coefficients are taken modulo nn.

Projection of σ(A)\sigma(A)Coefficient of ff
000, 10,\ 1
ei−ej (i≠j)e_i-e_j\ (i\neq j)k, k+1k,\ k+1

Table 2.

For projection zero, omitting zz forces every row to be empty, and selecting zz forces every row to be full. The two sums are 00 and ff, respectively. For projection ei−eje_i-e_j, consider the counts in row ii, row jj, and the remaining row, in that order. Without zz the counts are (1,n−1,0)(1,n-1,0), so the coefficient of ff is kk or k+1k+1. With zz the counts are (0,n−2,n−1)(0,n-2,n-1). If the term omitted from row jj has coefficient ϵ∈{0,1}\epsilon\in\{0,1\} on ff, the total coefficient is 1−3k+(k−ϵ)+k=1−k−ϵ1-3k+(k-\epsilon)+k=1-k-\epsilon, giving the same two residues.

Lemma 3.1. There exist an element h∈Cn5h\in C_n^5 of order kk and a zero-sumfree sequence TT of length 5b−15b-1 over Cn5C_n^5 such that −h∉Σ(T)-h\notin\Sigma(T).

Proof. Let W=V⋅fn−3W=V\cdot f^{n-3}. By the first row of (2), a subsequence of WW with zero projection has coefficient of ff in [0,n−2][0,n-2], with zero attained only by the trivial subsequence. Hence WW is zero-sumfree and −f∉Σ(W)-f\notin\Sigma(W). For i≠ji\neq j, put cij=c_{ij}= ei−ej+(k−1)fe_i-e_j+(k-1)f. By the second row of (2), a subsequence summing to cijc_{ij} would require n−1n-1 or n−2n-2 of the additional copies of ff. Thus cij∉Σ(W)c_{ij}\notin\Sigma(W).

Let c1,…,cn−1c_1,\ldots,c_{n-1} be the list consisting of c12c_{12}, c23c_{23}, c31c_{31} and n−4n-4 copies of −f-f. Its sum is (3(k−1)−(n−4))f=(k+1)f(3(k-1)-(n-4))f=(k+1)f. In Cn4⊕CnC_n^4\oplus C_n, place WW in the first summand and append the n−1n-1 terms (cj,1)(c_j,1) to obtain TT. Then ∣T∣=(3b+1)+(n−3)+(n−1)=5b−1|T|=(3b+1)+(n-3)+(n-1)=5b-1.

Put h=(−(k+1)f,2)h=(-(k+1)f,2). Since k+1k+1 is even, kh=0kh=0, and the last coordinate of hh has order kk.

We show that T⋅hT\cdot h is zero-sumfree. A zero sum omitting hh must omit all (cj,1)(c_j,1) by the last coordinate, and hence is trivial. A zero sum using hh must use exactly n−2n-2 of the (cj,1)(c_j,1). If (cj,1)(c_j,1) is omitted, the other appended terms together with hh sum to (−cj,0)(-c_j,0). This would require a subsequence of WW with sum cjc_j, which was excluded above. The assertion follows. □

Proof of Theorem 1.1. Let uu generate a cyclic group of order nn. For each j∈[1,n−1]j\in[1,n-1], let Pj≅Cn3P_j\cong C_n^3 and let Aj≅Cn3A_j\cong C_n^3 have basis aj,1,aj,2,aj,3a_{j,1},a_{j,2},a_{j,3}. We work in the direct sum

G=⟨u⟩⊕⨁j=1n−1(Pj⊕Aj).G=\langle u\rangle\oplus\bigoplus_{j=1}^{n-1}(P_j\oplus A_j).

Define nn elements g0,g1,…,gn−1g_0,g_1,\ldots,g_{n-1} of GG by

g0=(k+1)u+∑j=1n−1(aj,2−aj,1),g_0=(k+1)u+\sum_{j=1}^{n-1}(a_{j,2}-a_{j,1}),
gj=(k+1)u+(aj,3−aj,2)(1≤j≤n−1).g_j=(k+1)u+(a_{j,3}-a_{j,2})\qquad(1\le j\le n-1).

Thus g0g_0 has a component in every AjA_j, whereas among g1,…,gn−1g_1,\ldots,g_{n-1} only gjg_j has a component in AjA_j.

In each PjP_j take a copy TjT_j of the sequence in Lemma 3.1, with corresponding element hjh_j. Let VjV_j be the image of VV under the homomorphism Cn4→GC_n^4\to G defined by ei↦aj,ie_i\mapsto a_{j,i} for 1≤i≤31\le i\le3 and f↦hj+uf\mapsto h_j+u. Consider the sequence

S=g0g1⋯gn−1∏j=1n−1TjVj.S=g_0g_1\cdots g_{n-1}\prod_{j=1}^{n-1}T_jV_j.

Suppose a subsequence of SS has sum zero. Let x∈{0,1}x\in\{0,1\} indicate whether g0g_0 is selected, and let yj∈{0,1}y_j\in\{0,1\} indicate whether gjg_j is selected. Fix jj. To cancel the components of g0g_0 and gjg_j in AjA_j, the selected terms of VjV_j must have projection

x(aj,1−aj,2)+yj(aj,2−aj,3).x(a_{j,1}-a_{j,2})+y_j(a_{j,2}-a_{j,3}).

This is zero if x=yj=0x=y_j=0. Otherwise it is aj,1−aj,2a_{j,1}-a_{j,2}, aj,2−aj,3a_{j,2}-a_{j,3}, or aj,1−aj,3a_{j,1}-a_{j,3}. By (2), the coefficient of hj+uh_j+u contributed by VjV_j is k1x+yj>0+ϵjk1_{x+y_j>0}+\epsilon_j modulo nn, with ϵj∈{0,1}\epsilon_j\in\{0,1\}. Since khj=0kh_j=0, the selected terms of TjT_j must sum to −ϵjhj-\epsilon_jh_j in PjP_j. Lemma 3.1 rules out ϵj=1\epsilon_j=1 and then forces the selection from TjT_j to be empty. Thus the selected terms of TjVjT_jV_j contribute kuku in ⟨u⟩\langle u\rangle whenever g0g_0 or gjg_j is selected. If both are omitted, the projection onto AjA_j and the coefficient of hj+uh_j+u are both zero, so the selection from VjV_j is empty as well.

Put m=∑j=1n−1yjm=\sum_{j=1}^{n-1}y_j. If g0g_0 is omitted, exactly mm of the sequences TjVjT_jV_j contribute kuku. The total coefficient of uu is (k+1)m+km≡m(modn)(k+1)m+km\equiv m\pmod n. Since 0≤m<n0\le m<n, we must have m=0m=0, and the entire subsequence is empty. If g0g_0 is selected, each of the n−1n-1 sequences TjVjT_jV_j contributes kuku. The total coefficient of uu is then (k+1)(m+1)+k(n−1)(k+1)(m+1)+k(n-1), which is odd and hence nonzero modulo n=2kn=2k. This proves that SS is zero-sumfree.

The group GG has rank R=8(n−1)+1=8n−7R=8(n-1)+1=8n-7. Each TjVjT_jV_j has length (5b−1)+(3b+1)=8b(5b-1)+(3b+1)=8b, so ∣S∣=8(n−1)b+n=Rb+1|S|=8(n-1)b+n=Rb+1. Write r=qR+sr=qR+s with 0≤s<R0\le s<R. Take qq copies in independent summands and bb copies of a basis element in each of the remaining ss coordinates. Their product is zero-sumfree and has length q(Rb+1)+sb=rb+qq(Rb+1)+sb=rb+q. Since D(Cnr)=1+d(Cnr)D(C_n^r)=1+d(C_n^r), 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

D(Cnr)≥r(n−1)+1+⌊r−15n/2−1⌋D(C_n^r) \ge r(n-1)+1+\left\lfloor\frac{r-1}{5n/2-1}\right\rfloor

For some exponents the bound can be improved further. For example, when n=6n=6, one has

D(C6r)≥5r+1+⌊r−19⌋D(C_6^r) \ge5r+1+\left\lfloor\frac{r-1}{9}\right\rfloor

for every positive integer rr.

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. [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. [2]W. Gao and A. Geroldinger, Zero-sum problems and coverings by proper cosets, European J. Combin. 24 (2003), 531 – 549.DOI
  3. [3]W. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: a survey, Expo. Math. 24 (2006), 337–369.DOI
  4. [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. [5]A. Geroldinger, D.J. Grynkiewicz, and Q. Zhong, Combinatorial Factorization Theory, Math. Surveys Monogr., vol. 296, American Mathematical Society, Providence, RI, 2026.
  6. [6]B. Girard, An asymptotically tight bound for the Davenport constant, J. Éc. polytech. Math. 5 (2018), 605–611.
  7. [9]P. van Emde Boas and D. Kruyswijk, A combinatorial problem on finite abelian groups III, Mathematisch Centrum, Amsterdam, ZW 1969-008, December 1969.
  8. [10]G. Wang, Disproving conjectures on the Davenport and Narkiewicz constants, arXiv:2609.29878v5 (2026).arxiv.org/abs/2609.29878
  9. [11]Q. Zhong, On the Characterization Problem for Krull monoids with Homocyclic Class Groups. arXiv:26010.34288arxiv.org/abs/2610.34288

Paper details

vlnc:W_nqm5fggq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents