ON DAVENPORT CONSTANT
BENJAMIN GIRARD

arXiv:1709.08033v2 [math.NT] 8 Apr 2018

Abstract. We prove that for every fixed integer r > 1 the Davenport constant
r ) is asymptotic to rn when n tends to infinity. An extension of this
D(Cn
theorem to a wider framework is also provided.

For every integer n > 1, let Cn be the cyclic group of order n. It is well known
that every non-trivial finite Abelian group G can be uniquely decomposed as a direct
product of cyclic groups Cn1 ⊕· · ·⊕Cnr such that 1 < n1 | · · · | nr ∈ N. The integers
r and nr - sometimes also denoted by exp(G) - appearing in this decomposition are
respectively called the rank and exponent of G. For every integer 1 6 d | exp(G),
we denote by Gd the subgroup of G consisting of all elements of order dividing d.
Any finite sequence S of ℓ elements of G will be called a sequence over G of
length |S| = ℓ. Also, we denote by σ(S) the sum of all elements in S. The sequence
S will be referred to as a zero-sum sequence whenever σ(S) = 0.
By D(G) we denote the smallest integer t > 1 such that every sequence S over G
of length |S| > t contains a non-empty zero-sum subsequence. This number, which
is called the Davenport constant, drew over the last fifty years an ever growing
interest, most notably in additive combinatorics and algebraic number theory. A
detailed account on the many aspects of this invariant can be found in [8, 10, 13, 17].
To name but one striking feature, let us recall the Davenport constant has the
following arithmetical interpretation. Given the ring of integers OK of some number field K with ideal class group G, the maximum number of prime ideals in the
decomposition of an irreducible element of OK is D(G) [22]. The importance of this
fact is best highlighted by the following generalization of the prime number theorem [17, Theorem 9.15], stating that the number F (x) of pairwise non-associated
irreducible elements in OK whose norms do not exceed x in absolute value satisfies,
x
(log log x)D(G)−1 ,
F (x) ∼ C
x→+∞
log x
with a suitable constant C > 0 depending solely on G.
We are thus naturally led to the problem of determining the exact value of D(G).
The best explicit bounds known so far are


r
X
|G|
(ni − 1) + 1 6 D(G) 6 nr 1 + log
(1)
.
nr
i=1

The lower bound follows easily from the fact that if (e1 , . . . , er ) is a basis of G such
that ord(ei ) = ni for all i ∈ J1, rK, the sequence S consisting of ni − 1 copies of ei
for each i ∈ J1, rK contains no non-empty zero-sum subsequence. The upper bound
first appeared in [7, Theorem 7.1] and was rediscovered in [16, Theorem 1]. See
also [1, Theorem 1.1] for a reformulation of the proof’s original argument as well
as an application of the Davenport constant to the study of Carmichael numbers.

D(G) has been proved to match the lower bound in (1) when G is either a pgroup [18] or has rank at most 2 [19, Corollary 1.1]. Eventhough there are infinitely
many finite Abelian groups whose Davenport constant is known to exceed this lower
bound [7, 11, 12, 15], none of the ones identified so far either have rank 3 or the form
2010 Mathematics Subject Classification: 05E15, 11B75, 11A25, 20D60, 20K01.
Sorbonne Universités, UPMC Univ Paris 06, Institut de Mathématiques de Jussieu - Paris Rive
Gauche, UMR 7586, CNRS, Univ Paris Diderot, Sorbonne Paris Cité, Case 247, 4 Place Jussieu,
75252 Paris, France, email: benjamin.girard@imj-prg.fr.
1

2

BENJAMIN GIRARD

Cnr . These two types of groups are still conjectured to have a Davenport constant
matching the lower bound in (1).
Conjecture 1. For all integers n, r > 1,
D(Cnr ) = r(n − 1) + 1.
Besides the already mentioned results settling Conjecture 1 for all r when n is a
prime power and for all n when r 6 2, note that D(Cn3 ) is known only when n = 2pα ,
with p prime and α > 1 [6, Corollary 4.3], or n = 2α 3 with α > 2 [7, Corollary 5.1],
and satisfies Conjecture 1 in both cases. To the best of our knowledge, the exact
value of D(Cnr ) is currently unknown for all pairs (n, r) such that n is not a prime
power and r > 4. In all those remaining cases, the bounds in (1) translate into
(2)

r(n − 1) + 1 6 D(Cnr ) 6 n (1 + (r − 1) log n) ,

which leaves a substantial gap to be bridged. Conjecture 1 thus remains wide open.
The aim of the present note is to clarify the behavior of D(Cnr ) for any fixed r > 1
when n goes to infinity. Our main theorem proves Conjecture 1 in the following
asymptotic sense.
Theorem 1. For every integer r > 1,
D(Cnr )

∼

n→+∞

rn.

The proof of Theorem 1 relies on a new upper bound for D(Cnr ), turning out to
be a lot sharper than the one in (2) for large values of n. So as to state it properly,
we now make the following definition.
For every integer n > 1, we denote by P (n) the greatest prime power dividing
n, with the convention P (1) = 1. In what follows, the key point will be that P (n)
tends to infinity when n does so. Indeed, denoting by (ai )i>1 the integer
Q sequence
of prime powers, let (bn )n>1 be the integer sequence defined by bn = ai 6n ai for
all n > 1. By definition, for every integer N > 1, one has P (n) > N as soon as
n > bN . Therefore, P (n) tends to infinity when n does so.
Theorem 2. For every integer r > 1, there exists a constant dr > 0 such that for
every integer n > 1,


n
r
−1 .
D(Cn ) 6 r (n − 1) + 1 + dr
P (n)
Now, since P (n) tends to infinity when n does so, Theorem 2 allows us to deduce
that, for every integer r > 1, the gap between the Davenport constant and its
conjectural value
∂(Cnr ) = D(Cnr ) − (r (n − 1) + 1)
is actually o(n). This theorem will be obtained via the inductive method, which
involves another key combinatorial invariant we now proceed to define.
By η(G) we denote the smallest integer t > 1 such that every sequence S over
G of length |S| > t contains a non-empty zero-sum subsequence S ′ | S with |S ′ | 6
exp(G). It is readily seen that D(G) 6 η(G) for every finite Abelian group G.
A natural construction shows that, for all integers n, r > 1, one has
(3)

(2r − 1)(n − 1) + 1 6 η(Cnr ).

r
Indeed, if (e1 , . . . , er ) is a basis
P of Cn , it is easily checked that the sequence S
consisting of n − 1 copies of i∈I ei for each non-empty subset I ⊆ J1, rK contains
no non-empty zero-sum subsequence of length at most n.

ON DAVENPORT CONSTANT

3

The exact value of η(Cnr ) is known to match the lower bound in (3) for all n
when r 6 2 [13, Theorem 5.8.3], and for all r when n = 2α , with α > 1 [14, Satz 1].
Besides these two results, η(Cnr ) is currently known only when r = 3 and n = 3α 5β ,
with α, β > 0 [9, Theorem 1.7], in which case η(Cn3 ) = 8n − 7, or n = 2α 3, with
α > 1 [9, Theorem 1.8], in which case η(Cn3 ) = 7n − 6. When n = 3, note that the
problem of finding η(C3r ) is closely related to the well-known cap-set problem, and
that for r > 4, the only known values so far are η(C34 ) = 39 [20], η(C35 ) = 89 [4]
and η(C36 ) = 223 [21]. For more details on this fascinating topic, see [3, 5] and the
references contained therein.
In another direction, Alon and Dubiner showed [2] that when r is fixed, η(Cnr )
grows linearly in the exponent n. More precisely, they proved that for every integer
r > 1, there exists a constant cr > 0 such that for every integer n > 1,
η (Cnr ) 6 cr (n − 1) + 1.

(4)

From now on, we will identify cr with its smallest possible value in this theorem.
On the one hand, it follows from (3) that cr > 2r − 1, for all r > 1. Since, as
already mentioned, η(Cn ) = n and η(Cn2 ) = 3n − 2 for all n > 1, it is possible to
choose c1 = 1 and c2 = 3, with equality in (4).
On the other hand, the method used in [2] yields cr 6 (cr log r)r , where c > 0 is
an absolute constant, and it is conjectured in [2] that there actually is an absolute
constant d > 0 such that cr 6 dr for all r > 1.
We can now state and prove our main technical result, which is the following.
Theorem 3. For all integers n, r > 1,
D(Cnr )

6 r (n − 1) + 1 + (cr − r)




n
−1 .
P (n)

Proof of Theorem 3. We set G = Cnr and denote by H = GP (n) the largest Sylow
subgroup of G. Since H ≃ CPr (n) is a p-group, it follows from [18] that
D(H) = r(P (n) − 1) + 1.
r
In addition, since the quotient group G/H ≃ Cn/P
(n) has rank r and exponent
n/P (n), it follows from (4) that


n
η(G/H) 6 cr
− 1 + 1.
P (n)

Now, from any sequence S over G such that

|S| > exp(G/H) (D(H) − 1) + η(G/H),
one can sequentially extract at least d = D(H) disjoint non-empty subsequences
S1′ , . . . , Sd′ | S such that σ(Si′ ) ∈ H and |Si′ | 6 exp(G/H) for every i ∈ J1, dK.
Qd
Since T = i=1 σ(Si′ ) is a sequence over H Q
of length |T | = D(H), there exists a
non-empty subsetQ
I ⊆ J1, dK such that T ′ = i∈I σ(Si′ ) is a zero-sum subsequence
of T . Then, S ′ = i∈I Si′ is a non-empty zero-sum subsequence of S.
Therefore, we have
D(G)

6
6
=

exp(G/H) (D(H) − 1) + η(G/H)


n
n
(r(P (n) − 1)) + cr
−1 +1
P (n)
P (n)


n
r(n − 1) + 1 + (cr − r)
−1 ,
P (n)

which completes the proof.



4

BENJAMIN GIRARD

Note that Theorem 3 is sharp for all n when r = 1 and for all r when n is a
prime power. Also, Theorems 1 and 2 are now direct corollaries of Theorem 3.
Proof of Theorem 2. The result follows from Theorem 3 by setting dr = cr − r. 
Proof of Theorem 1. Since P (n) tends to infinity when n does so, the desired result
follows easily from (2) and Theorem 2.

To conclude this paper, we would like to offer a possibly useful extension of
Theorem 3 to the following wider framework. Given any finite Abelian group L
and any integer r > 1, we consider the groups defined by Lrn = L ⊕ Cnr , where n > 1
is any integer such that exp(L) | n. Note that the case L = {0} brings one back to
Lrn = Cnr whose Davenport constant is already covered by Theorem 3.
Our aim in this more general context is to prove that, for every finite Abelian
group L and every integer r > 1, D(Lrn ) behaves asymptotically in the same way
it already does, according to Theorem 3, when L is trivial. To do so, we establish
the following theorem.
Theorem 4. Let L ≃ Cn1 ⊕ · · ·⊕ Cnℓ , with 1 6 n1 | · · · | nℓ ∈ N, be a finite Abelian
group. For every integer n > 1 such that exp(L) | n and every integer r > 1,


ℓ
n
n X
D(Lrn ) 6 r (n − 1) + 1 + (cℓ+r − r)
(gcd(ni , P (n)) − 1).
−1 +
P (n)
P (n) i=1

Proof of Theorem 4. We set G = Lrn and H = GP (n) . On the one hand, since
H ≃ Cn′1 ⊕ · · · ⊕ Cn′ℓ ⊕ CPr (n) , with n′i = gcd(ni , P (n)) | ni for all i ∈ J1, ℓK and
1 6 n′1 | · · · | n′ℓ | P (n), is a p-group, it follows from [18] that
D(H) =

ℓ
X

(n′i − 1) + r(P (n) − 1) + 1.

i=1

On the other hand, since the quotient group G/H has exponent n/P (n) and rank
at most ℓ + r, it follows from (4) that




n
η(G/H) 6 η C ℓ+r
6 cℓ+r
− 1 + 1.
n
P (n)
P (n)
Therefore, just like in our proof of Theorem 3, we obtain
D(G)

6

exp(G/H) (D(H) − 1) + η(G/H)

6

n
P (n)

=

ℓ
X

(n′i

!

− 1) + r(P (n) − 1)

i=1

r (n − 1) + 1 + (cℓ+r − r)



which is the desired upper bound.

+ cℓ+r




n
−1 +1
P (n)


ℓ
n X ′
n
(n − 1),
−1 +
P (n)
P (n) i=1 i



Theorem 5. For every finite Abelian group L and every integer r > 1,
D(Lrn )

∼

n→+∞
exp(L)|n

rn.

Proof of Theorem 5. We write L ≃ Cn1 ⊕ · · · ⊕ Cnℓ , with 1 6 n1 | · · · | nℓ ∈ N.
For every integer n > 1 such that exp(L) | n, one has gcd(ni , P (n)) 6 ni for all
i ∈ J1, ℓK. Since P (n) tends to infinity when n does so, the result follows easily
from (1) and Theorem 4.


ON DAVENPORT CONSTANT

5

Acknowledgements
The author is grateful to W.A. Schmid for his careful reading of the manuscript
in an earlier version.
References
[1] W.R. Alford, A. Granville and C. Pomerance There are infinitely many Carmichael
numbers, Annals of Math. 140 (3) (1994), 703-722.
[2] N. Alon and M. Dubiner A lattice point problem and additive number theory, Combinatorica
15 (1995), 301-309.
[3] Y. Edel, C. Elsholtz, A. Geroldinger, S. Kubertin and L. Rackham Zero-sum problems
in finite abelian groups and affine caps, Q. J. Math. 58 (2007), 159-186.
[4] Y. Edel, S. Ferret, I. Landjev and L. Storme The classification of the largest caps in
AG(5,3), J. Combin. Theory Ser. A 99 (2002), 95-110.
[5] J. S. Ellenberg and D. Gijswijt On large subsets of Fn
q with no three-term arithmetic
progression, Annals of Math. 185 (1) (2017), 339-343.
[6] P. van Emde Boas A combinatorial problem on finite abelian groups II, Reports ZW-1969007, Math. Centre, Amsterdam (1969).
[7] P. van Emde Boas and D. Kruyswijk A combinatorial problem on finite abelian groups
III, Reports ZW-1969-008, Math. Centre, Amsterdam (1969).
[8] W. Gao and A. Geroldinger Zero-sum problems in finite abelian groups: a survey, Expo.
Math. 24 (2006), 337-369.
[9] W. Gao, Q. H. Hou, W. A. Schmid and R. Thangadurai On short zero-sum subsequences
II, Integers 7 (2007), #A21.
[10] A. Geroldinger Additive group theory and non-unique factorizations, In A. Geroldinger
and I. Ruzsa, Combinatorial Number Theory and Additive Group Theory, Advanced Courses
in Mathematics, CRM Barcelona, Birkhäuser (2009), 1-86.
[11] A. Geroldinger, M. Liebmann and A. Philipp On the Davenport constant and on the
structure of extremal zero-sum free sequences, Period. Math. Hungar. 64 (2) (2012), 213-225.
[12] A. Geroldinger and R. Schneider On Davenport’s constant, J. Combin. Theory Ser. A
61 (1992), 147-152.
[13] A. Geroldinger and F. Halter-Koch Non-unique factorizations. Algebraic, combinatorial
and analytic theory, Pure and Applied Mathematics 278, Chapman & Hall/CRC (2006).
[14] H. Harborth Ein Extremalproblem für Gitterpunkte, J. Reine Angew. Math. 262 (1973),
356-360.
[15] M. Mazur A note on the growth of Davenport constant, Manuscripta Math. 74 (1992),
229-235.
[16] R. Meshulam An uncertainty inequality and zero subsums, Discrete Math. 84 (1990), 197200.
[17] W. Narkiewicz Elementary and analytic theory of algebraic numbers, 3rd edition, Springer
(2004).
[18] J. E. Olson A combinatorial problem on finite abelian groups I, J. Number Theory 1 (1969),
8-10.
[19] J. E. Olson A combinatorial problem on finite abelian groups II, J. Number Theory 1 (1969),
195-199.
[20] G. Pellegrino The maximal order of the spherical cap in S4,3 , Matematiche 25 (1971),
149-157.
[21] A. Potechin Maximal caps in AG(6,3), Des. Codes Cryptogr. 46 (2008), 243-259.
[22] K. Rogers A combinatorial problem in Abelian groups, Proc. Camb. Philos. Soc. 59 (1963),
559-562.

