Journal de l’École polytechnique. Mathématiques

Emmanuel Militon

Conjugacy class of homeomorphisms and distortion elements in groups of homeomorphisms

David Lannes

Guy Métivier

The shoreline problem for the one-dimensional shallow water and Green-Naghdi equations

Benjamin Girard

Benjamin Girard
An asymptotically tight bound for the Davenport constant
Tome 5 (2018), p. 605-611.
<http://jep.cedram.org/item?id=JEP_2018__5__605_0>
© Les auteurs, 2018.
Certains droits réservés.
Cet article est mis à disposition selon les termes de la licence
CREATIVE COMMONS ATTRIBUTION – PAS DE MODIFICATION 3.0 FRANCE.
http://creativecommons.org/licenses/by-nd/3.0/fr/
L’accès aux articles de la revue « Journal de l’École polytechnique — Mathématiques »
(http://jep.cedram.org/), implique l’accord avec les conditions générales d’utilisation
(http://jep.cedram.org/legal/).
Publié avec le soutien
du Centre National de la Recherche Scientifique
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.cedram.org/
Tome 5, 2018, p. 605–611 DOI: 10.5802/jep.79
AN ASYMPTOTICALLY TIGHT BOUND FOR
THE DAVENPORT CONSTANT
by Benjamin Girard
Abstract. — We prove that for every integer r > 1 the Davenport constant D(Crn) is asymptotic
to rn when n tends to infinity. An extension of this theorem is also provided.
Résumé (Une borne asymptotiquement optimale pour la constante de Davenport)
Nous prouvons que pour tout entier r > 1, la constante de Davenport D(Crn) est équivalente
à rn lorsque n tend vers l’infini. Nous proposons aussi une extension de ce théorème.
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 appearing in this decomposition are respectively called the rank
and the exponent of G. The latter is denoted by exp(G). For the trivial group, the
rank is 0 and the exponent is 1. 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 inter-
est, most notably in additive combinatorics and algebraic number theory. A detailed
account on the many aspects of this invariant can be found in [4, 11, 13, 14, 21].
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 de-
composition of an irreducible element of OK is D(G) [26]. The importance of this
fact is best highlighted by the following generalization of the prime number theorem
2010 Mathematics Subject Classification. — 05E15, 11B30, 11B75, 11A25, 20D60, 20K01.
Keywords. — Additive combinatorics, zero-sum sequences, Davenport constant, finite Abelian
groups.
e-ISSN: 2270-518X http://jep.cedram.org/
606 B. Girard
[21, Th. 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,
F (x) ∼
x→+∞
C
x
log x
(log log x)D(G)−1,
with a suitable constant C > 0 depending solely on G (see [14, Chap. 9.1] and [18,
Th. 1.1] for sharper and more general results).
We are thus naturally led to the problem of determining the exact value of D(G).
The best explicit bounds known so far are
(1)
r∑
i=1
(ni − 1) + 1 6 D(G) 6 nr
(
1 + log
|G|
nr
)
.
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 [9, Th. 7.1] and was rediscovered in [20, Th. 1]. See also [1, Th. 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 p-
group [22] or has rank at most 2 [23, Cor. 1.1]. Even though there are infinitely many
finite Abelian groups whose Davenport constant is known to exceed this lower bound
[9, 15, 16, 19], none of the ones identified so far either have rank 3 or the form Crn. Since
the late sixties, these two types of groups have been conjectured to have a Davenport
constant matching the lower bound in (1). This open problem was first raised in [9,
p. 13&29] and can be found formally stated as a conjecture in [11, Conj. 3.5]. See
also [3, Conj. A.5] and [10, Th. 6.6] for connections with graph theory and covering
problems.
Conjecture 1. — For all integers n, r > 1,
D(Crn) = 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(C3n) is known only when n = 2pα,
with p prime and α > 1 [8, Cor. 4.3], or n = 2α3 with α > 2 [9, Cor. 1.5], and satisfies
Conjecture 1 in both cases. To the best of our knowledge, the exact value of D(Crn)
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(Crn) 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(Crn) for any fixed
r > 1 when n goes to infinity. Our main theorem proves Conjecture 1 in the following
asymptotic sense.
J.É.P. — M., 2018, tome 5
An asymptotically tight bound for the Davenport constant 607
Theorem 1. — For every integer r > 1,
D(Crn) ∼
n→+∞
rn.
The proof of Theorem 1 relies on a new upper bound for D(Crn), 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.
Theorem 2. — For every integer r > 1, there exists a constant dr > 0 such that for
every integer n > 1,
D(Crn) 6 r (n− 1) + 1 + dr
( n
P (n)
− 1
)
.
The relevance of this bound to the study of the Davenport constant is due to the
fact that the arithmetic function P (n) tends to infinity when n does so. Indeed, if we
denote by P the set of prime numbers and let (an)n>1 be the sequence defined for
every integer n > 1 by
an =
∏
p∈P
pblogn/log pc,
we easily notice that, for every integer N > 1, one has P (n) > N as soon as n > aN .
Now, since P (n) tends to infinity when n does so, Theorem 2 allows us to de-
duce that, for every integer r > 1, the gap between the Davenport constant and its
conjectural value
D(Crn)− (r (n− 1) + 1)
is actually o(n). This theorem will be obtained via the inductive method, which in-
volves 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 η(Crn).
Indeed, if (e1, . . . , er) is a basis of Crn, 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.
The exact value of η(Crn) is known to match the lower bound in (3) for all n when
r 6 2 [14, Th. 5.8.3], and for all r when n = 2α, with α > 1 [17, Satz 1]. Besides these
two results, η(Crn) is currently known only when r = 3 and n = 3α5β , with α, β > 0
[12, Th. 1.7], in which case η(C3n) = 8n − 7, or n = 2α3, with α > 1 [12, Th. 1.8], in
which case η(C3n) = 7n − 6. When n = 3, note that the problem of finding η(Cr3) is
closely related to the well-known cap-set problem, and that for r > 4, the only known
values so far are η(C43 ) = 39 [24], η(C53 ) = 89 [6] and η(C63 ) = 223 [25]. For more
details on this fascinating topic, see [5, 7] and the references contained therein.
J.É.P. — M., 2018, tome 5
608 B. Girard
In another direction, Alon and Dubiner showed [2] that when r is fixed, η(Crn)
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,
(4) η (Crn) 6 cr(n− 1) + 1.
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 η(C2n) = 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 first technical result, which is the following.
Theorem 3. — For all integers n, r > 1,
D(Crn) 6 r (n− 1) + 1 + (cr − r)
( n
P (n)
− 1
)
.
Proof of Theorem 3. — We set G = Crn and denote by H = GP (n) the largest Sylow
subgroup of G. Since H ' CrP (n) is a p-group, it follows from [22] that
D(H) = r(P (n)− 1) + 1.
In addition, since the quotient group G/H ' Crn/P (n) has exponent n/P (n) and rank
at most r, it follows from (4) that
η(G/H) 6 cr
( n
P (n)
− 1
)
+ 1.
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
S′1, . . . , S
′
d | S such that σ(S′i) ∈ H and |S′i| 6 exp(G/H) for every i ∈ J1, dK (see
for instance [14, Lem. 5.7.10]). Since T =
∏d
i=1 σ(S
′
i) is a sequence over H of length
|T | = D(H), there exists a non-empty subset I ⊆ J1, dK such that T ′ =
∏
i∈I σ(S
′
i) is a
zero-sum subsequence of T . Then, S′ =
∏
i∈I S
′
i is a non-empty zero-sum subsequence
of S.
Therefore, we have
D(G) 6 exp(G/H) (D(H)− 1) + η(G/H)
6
n
P (n)
(r(P (n)− 1)) + cr
( n
P (n)
− 1
)
+ 1
= r(n− 1) + 1 + (cr − r)
( n
P (n)
− 1
)
,
which completes the proof. 
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.
J.É.P. — M., 2018, tome 5
An asymptotically tight bound for the Davenport constant 609
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 our
theorems to the following wider framework. Given any finite Abelian group L and
any integer r > 1, we consider the groups defined by Lrn = L ⊕ Crn, where n > 1 is
any integer such that exp(L) | n. Note that if L is the trivial group, then Lrn ' Crn
whose Davenport constant is already covered by Theorems 1-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
would if L were trivial. To do so, we establish the following extension of Theorem 3.
Theorem 4. — Let L ' Cn1 ⊕· · ·⊕Cn` , with 1 < n1 | · · · | n` ∈ N, be a finite Abelian
group. For every integer n > 1 such that exp(L) | n and every integer r > 1,
D(Lrn) 6 r (n− 1) + 1 + (c`+r − r)
( n
P (n)
− 1
)
+
n
P (n)
∑̀
i=1
(gcd(ni, P (n))− 1).
Proof of Theorem 4. — We set G = Lrn and H = GP (n). On the one hand, since
H ' Cn′1 ⊕ · · · ⊕ Cn′` ⊕ C
r
P (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 [22] that
D(H) =
∑̀
i=1
(n′i − 1) + r(P (n)− 1) + 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
η(G/H) 6 η
(
C`+rn/P (n)
)
6 c`+r
( n
P (n)
− 1
)
+ 1.
Therefore, the same argument we used in our proof of Theorem 3 yields
D(G) 6 exp(G/H) (D(H)− 1) + η(G/H)
6
n
P (n)
(∑̀
i=1
(n′i − 1) + r(P (n)− 1)
)
+ c`+r
( n
P (n)
− 1
)
+ 1
= r (n− 1) + 1 + (c`+r − r)
( n
P (n)
− 1
)
+
n
P (n)
∑̀
i=1
(n′i − 1),
which is the desired upper bound. 
Theorem 4 now easily implies the following generalization of Theorem 1.
Theorem 5. — For every finite Abelian group L and every integer r > 1,
D(Lrn) ∼
n→+∞
exp(L)|n
rn.
J.É.P. — M., 2018, tome 5
610 B. Girard
Proof of Theorem 5. — We write L ' Cn1 ⊕ · · · ⊕ Cn` , with 1 < 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. 
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 & C. Pomerance – “There are infinitely many Carmichael numbers”,
Ann. of Math. (2) 139 (1994), no. 3, p. 703–722.
[2] N. Alon & M. Dubiner – “A lattice point problem and additive number theory”, Combinatorica
15 (1995), no. 3, p. 301–309.
[3] N. Alon, S. Friedland & G. Kalai – “Regular subgraphs of almost regular graphs”, J. Combin.
Theory Ser. B 37 (1984), no. 1, p. 79–91.
[4] K. Cziszter, M. Domokos & A. Geroldinger – “The interplay of invariant theory with multi-
plicative ideal theory and with arithmetic combinatorics”, in Multiplicative ideal theory and
factorization theory, Springer Proc. Math. Stat., vol. 170, Springer, 2016, p. 43–95.
[5] Y. Edel, C. Elsholtz, A. Geroldinger, S. Kubertin & L. Rackham – “Zero-sum problems in finite
abelian groups and affine caps”, Q. J. Math. 58 (2007), no. 2, p. 159–186.
[6] Y. Edel, S. Ferret, I. Landjev & L. Storme – “The classification of the largest caps in AG(5, 3)”,
J. Combin. Theory Ser. A 99 (2002), no. 1, p. 95–110.
[7] J. S. Ellenberg & D. Gijswijt – “On large subsets of Fnq with no three-term arithmetic progres-
sion”, Ann. of Math. (2) 185 (2017), no. 1, p. 339–343.
[8] P. van Emde Boas – “A combinatorial problem on finite abelian groups. II”, Tech. Report ZW-007,
Math. Centrum Amsterdam Afd. Zuivere Wisk., 1969.
[9] P. van Emde Boas & D. Kruyswijk – “A combinatorial problem on finite abelian groups. III”, Tech.
Report ZW-008, Math. Centrum Amsterdam Afd. Zuivere Wisk., 1969.
[10] W. Gao & A. Geroldinger – “Zero-sum problems and coverings by proper cosets”, European
J. Combin. 24 (2003), no. 5, p. 531–549.
[11] , “Zero-sum problems in finite abelian groups: a survey”, Exposition. Math. 24 (2006),
no. 4, p. 337–369.
[12] W. D. Gao, Q. H. Hou, W. A. Schmid & R. Thangadurai – “On short zero-sum subsequences. II”,
Integers 7 (2007), article #A21.
[13] A. Geroldinger – “Additive group theory and non-unique factorizations”, in Combinatorial
number theory and additive group theory, Adv. Courses Math. CRM Barcelona, Birkhäuser
Verlag, Basel, 2009, p. 1–86.
[14] A. Geroldinger & F. Halter-Koch – Non-unique factorizations. Algebraic, combinatorial and
analytic theory, Pure and Applied Mathematics, vol. 278, Chapman & Hall/CRC, Boca Raton,
FL, 2006.
[15] A. Geroldinger, M. Liebmann & A. Philipp – “On the Davenport constant and on the structure
of extremal zero-sum free sequences”, Period. Math. Hungar. 64 (2012), no. 2, p. 213–225.
[16] A. Geroldinger & R. Schneider – “On Davenport’s constant”, J. Combin. Theory Ser. A 61
(1992), no. 1, p. 147–152.
[17] H. Harborth – “Ein Extremalproblem für Gitterpunkte”, J. reine angew. Math. 262/263
(1973), p. 356–360.
[18] J. Kaczorowski – “On the distribution of irreducible algebraic integers”, Monatsh. Math. 156
(2009), no. 1, p. 47–71.
[19] M. Mazur – “A note on the growth of Davenport’s constant”, Manuscripta Math. 74 (1992),
no. 3, p. 229–235.
[20] R. Meshulam – “An uncertainty inequality and zero subsums”, Discrete Math. 84 (1990), no. 2,
p. 197–200.
J.É.P. — M., 2018, tome 5
An asymptotically tight bound for the Davenport constant 611
[21] W. Narkiewicz – Elementary and analytic theory of algebraic numbers, third ed., Springer Mono-
graphs in Math., Springer-Verlag, Berlin, 2004.
[22] J. E. Olson – “A combinatorial problem on finite Abelian groups. I”, J. Number Theory 1 (1969),
p. 8–10.
[23] , “A combinatorial problem on finite Abelian groups. II”, J. Number Theory 1 (1969),
p. 195–199.
[24] G. Pellegrino – “The maximal order of the spherical cap in S4,3”, Matematiche 25 (1971),
p. 149–157.
[25] A. Potechin – “Maximal caps in AG(6, 3)”, Des. Codes Cryptogr. 46 (2008), no. 3, p. 243–259.
[26] K. Rogers – “A combinatorial problem in Abelian groups”, Math. Proc. Cambridge Philos. Soc.
59 (1963), p. 559–562.
Manuscript received 20th February 2018
accepted 25th June 2018
Benjamin Girard, Sorbonne Université, Université Paris Diderot, CNRS, Institut de Mathématiques
de Jussieu - Paris Rive Gauche, IMJ-PRG
F-75005, Paris, France
E-mail : benjamin.girard@imj-prg.fr
Url : https://webusers.imj-prg.fr/~benjamin.girard/
J.É.P. — M., 2018, tome 5


An asymptotically tight bound for the Davenport constant

Hoel Queffelec

Alistair Savage

Oded Yacobi

An equivalence between truncations of categorified quantum groups and Heisenberg categories

Roger Casals

Ailsa Keating

Ivan Smith

Sylvain Courte

Symplectomorphisms of exotic discs

Raf Cluckers

Immanuel Halupczok

Integration of functions of motivic exponential class, uniform in all non-archimedean local fields of characteristic zero

Anne de Roton

Small sumsets in $\protect \mathbb{R}$:  full continuous $3k-4$ theorem, critical sets

Not a member yet

Conjugacy class of homeomorphisms and distortion elements in groups of homeomorphisms

The shoreline problem for the one-dimensional shallow water and Green-Naghdi equations

An asymptotically tight bound for the Davenport constant

An equivalence between truncations of categorified quantum groups and Heisenberg categories

Symplectomorphisms of exotic discs

Integration of functions of motivic exponential class, uniform in all non-archimedean local fields of characteristic zero

Small sumsets in \protect \mathbb{R}: full continuous $3k-4$ theorem, critical sets

From the Kähler-Ricci flow to moving free boundaries and shocks

Infinite random planar maps related to Cauchy processes

Motivic realizations of singularity categories and vanishing cycles

312

324