Benjamin Girard
email: benjamin.girard@imj-prg.fr.

AN ASYMPTOTICALLY TIGHT BOUND FOR THE DAVENPORT CONSTANT

Keywords: 2010 Mathematics Subject Classification. 05E15, 11B30, 11B75, 11A25, 20D60, 20K01 Additive combinatorics, zero-sum sequences, Davenport constant, finite Abelian groups

is asymptotic to rn when n tends to infinity. An extension of this theorem is also provided.

For every integer n 1, let C n 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

C n1 ⊕ • • • ⊕ C nr such that 1 < n 1 | • • • | n r ∈ N.
The integers r and n r 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 d | exp(G), we denote by G d 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 [START_REF] Cziszter | Geroldinger The interplay of invariant theory with multiplicative ideal theory and with arithmetic combinatorics, in Multiplicative ideal theory and factorization theory[END_REF][START_REF] Gao | Geroldinger Zero-sum problems in finite abelian groups: a survey[END_REF][START_REF]Geroldinger Additive group theory and non-unique factorizations[END_REF][START_REF] Geroldinger | Halter-Koch Non-unique factorizations. Algebraic, combinatorial and analytic theory[END_REF][START_REF] Narkiewicz | Elementary and analytic theory of algebraic numbers[END_REF].

To name but one striking feature, let us recall the Davenport constant has the following arithmetical interpretation. Given the ring of integers O K of some number field K with ideal class group G, the maximum number of prime ideals in the decomposition of an irreducible element of O K is D(G) [START_REF] Rogers | A combinatorial problem in Abelian groups[END_REF]. The importance of this fact is best highlighted by the following generalization of the prime number theorem [START_REF] Narkiewicz | Elementary and analytic theory of algebraic numbers[END_REF]Theorem 9.15], stating that the number F (x) of pairwise non-associated irreducible elements in O K 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 [START_REF] Geroldinger | Halter-Koch Non-unique factorizations. Algebraic, combinatorial and analytic theory[END_REF]Chapter 9.1] and [START_REF] Kaczorowski | On the distribution of irreducible algebraic integers[END_REF]Theorem 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 (n i -1) + 1 D(G) n r 1 + log |G| n r .
The lower bound follows easily from the fact that if (e 1 , . . . , e r ) is a basis of G such that ord(e i ) = n i for all i ∈ 1, r , the sequence S consisting of n i -1 copies of e i for each i ∈ 1, r contains no non-empty zero-sum subsequence. The upper bound first appeared in [9, Theorem 7.1] and was rediscovered in [20, Theorem 1]. See also [START_REF] Alford | Pomerance There are infinitely many Carmichael numbers[END_REF]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 [START_REF] Olson | A combinatorial problem on finite abelian groups I[END_REF] or has rank at most 2 [START_REF] Olson | A combinatorial problem on finite abelian groups II[END_REF]Corollary 1.1]. Even though there are infinitely many finite Abelian groups whose Davenport constant is known to exceed this lower bound [START_REF] Van Emde Boas | Kruyswijk A combinatorial problem on finite abelian groups III[END_REF][START_REF] Geroldinger | On the Davenport constant and on the structure of extremal zero-sum free sequences[END_REF][START_REF] Geroldinger | On Davenport's constant[END_REF][START_REF] Mazur | A note on the growth of Davenport's constant[END_REF], none of the ones identified so far either have rank 3 or the form C r n . Since the late sixties, these two types of groups have been conjectured to have a Davenport constant matching the lower bound in [START_REF] Alford | Pomerance There are infinitely many Carmichael numbers[END_REF]. This open problem was first raised in [9, pages 13 and 29] and can be found formally stated as a conjecture in [START_REF] Gao | Geroldinger Zero-sum problems in finite abelian groups: a survey[END_REF]Conjecture 3.5]. See also [START_REF] Alon | Kalai Regular subgraphs of almost regular graphs[END_REF]Conjecture A.5] and [10, Theorem 6.6] for connections with graph theory and covering problems.

Conjecture 1. For all integers n, r 1,

D(C r n ) = 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 2, note that D(C 3 n ) is known only when n = 2p α , with p prime and α 1 [8, Corollary 4.3], or n = 2 α 3 with α 2 [9, Corollary 1.5], and satisfies Conjecture 1 in both cases. To the best of our knowledge, the exact value of D(C r n ) 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 The aim of the present note is to clarify the behavior of D(C r n ) 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(C r n ) ∼ n→+∞ rn.
The proof of Theorem 1 relies on a new upper bound for D(C r n ), turning out to be a lot sharper than the one in [START_REF] Alon | Dubiner A lattice point problem and additive number theory[END_REF] 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 d r 0 such that for every integer n 1,

D(C r n ) r (n -1) + 1 + d r 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 (a n ) n 1 be the sequence defined for every integer n 1 by

a n = p∈P p ⌊ log n log p ⌋ ,
we easily notice that, for every integer N 1, one has P (n) > N as soon as n > a 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 D(C r n ) -(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 ′ | exp(G). It is readily seen that D(G) η(G) for every finite Abelian group G.

A natural construction shows that, for all integers n, r 1, one has [START_REF] Alon | Kalai Regular subgraphs of almost regular graphs[END_REF] (2 r -1)(n -1) + 1 η(C r n ). Indeed, if (e 1 , . . . , e r ) is a basis of C r n , it is easily checked that the sequence S consisting of n -1 copies of i∈I e i for each non-empty subset I ⊆ 1, r contains no non-empty zero-sum subsequence of length at most n. 3 ) is closely related to the well-known cap-set problem, and that for r 4, the only known values so far are η(C 43 ) = 39 [START_REF] Pellegrino | The maximal order of the spherical cap in S 4[END_REF], η(C 5 3 ) = 89 [START_REF] Edel | The classification of the largest caps in AG(5, 3)[END_REF] and η(C 63 ) = 223 [START_REF]Potechin Maximal caps in AG(6, 3)[END_REF]. For more details on this fascinating topic, see [START_REF] Edel | Zero-sum problems in finite abelian groups and affine caps[END_REF][START_REF] Ellenberg | Gijswijt On large subsets of F n q with no three-term arithmetic progression[END_REF] and the references contained therein.

The exact value of η(C

In another direction, Alon and Dubiner showed [START_REF] Alon | Dubiner A lattice point problem and additive number theory[END_REF] that when r is fixed, η(C r n ) grows linearly in the exponent n. More precisely, they proved that for every integer r 1, there exists a constant c r > 0 such that for every integer n 1, ( 4)

η (C r n ) c r (n -1) + 1.
From now on, we will identify c r its smallest possible value in this theorem.

On the one hand, it follows from (3) that c r 2 r -1, for all r 1. Since, as already mentioned, η(C n ) = n and η(C 2 n ) = 3n -2 for all n 1, it is possible to choose c 1 = 1 and c 2 = 3, with equality in (4).

On the other hand, the method used in [START_REF] Alon | Dubiner A lattice point problem and additive number theory[END_REF] yields c r (cr log r) r , where c > 0 is an absolute constant, and it is conjectured in [START_REF] Alon | Dubiner A lattice point problem and additive number theory[END_REF] that there actually is an absolute constant d > 0 such that c r d r 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(C r n ) r (n -1) + 1 + (c r -r) n P (n) -1 .
Proof of Theorem 3. We set G = C r n and denote by

H = G P (n) the largest Sylow subgroup of G. Since H ≃ C r P (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 ≃ C r n/P (n) has exponent n/P (n) and rank at most r, it follows from (4) that is a zero-sum subsequence of T . Then, S ′ = i∈I S ′ i is a non-empty zero-sum subsequence of S.

η(G/H) c r n P (n) -1 + 1.
Therefore, we have

D(G) exp(G/H) (D(H) -1) + η(G/H) n P (n) (r(P (n) -1)) + c r n P (n) -1 + 1 = r(n -1) + 1 + (c r -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.

Proof of Theorem 2. The result follows from Theorem 3 by setting d r = c r -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 L r n = L ⊕ C r n , where n 1 is any integer such that exp(L) | n. Note that if L is the trivial group, then L r n ≃ C r n 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(L r n ) 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 ≃ C n1 ⊕ • • •⊕ C n ℓ , with 1 < n 1 | • • • | n ℓ ∈ N,
be a finite Abelian group. For every integer n 1 such that exp(L) | n and every integer r 1,

D(L r n ) r (n -1) + 1 + (c ℓ+r -r) n P (n) -1 + n P (n) ℓ i=1
(gcd(n i , P (n)) -1).

Proof of Theorem 4. We set G = L r n and H = G P (n) . On the one hand, since

H ≃ C n ′ 1 ⊕ • • • ⊕ C n ′ ℓ ⊕ C r P (n) , with n ′ i = gcd(n i , P (n)) | n i for all i ∈ 1, ℓ and 1 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) η C ℓ+r For every integer n 1 such that exp(L) | n, one has gcd(n i , P (n)) n i for all i ∈ 1, ℓ . Since P (n) tends to infinity when n does so, the result follows easily from (1) and Theorem 4.

  (2) r(n -1) + 1 D(C r n ) n (1 + (r -1) log n) , which leaves a substantial gap to be bridged. Conjecture 1 thus remains wide open.

  r n ) is known to match the lower bound in (3) for all n when r 2 [14, Theorem 5.8.3], and for all r when n = 2 α , with α 1 [17, Satz 1]. Besides these two results, η(C r n ) is currently known only when r = 3 and n = 3 α 5 β , with α, β 0 [12, Theorem 1.7], in which case η(C 3 n ) = 8n -7, or n = 2 α 3, with α 1 [12, Theorem 1.8], in which case η(C 3 n ) = 7n -6. When n = 3, note that the problem of finding η(C r

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 | exp(G/H) for every i ∈ 1, d (see for instance [14, Lemma 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 ⊆ 1, d such that T ′ = i∈I σ(S ′ i )

1 =Theorem 5 . 5 .

 155 same argument we used in our proof of Theorem 3 yieldsD(G) exp(G/H) (D(H) -1) + η(Gr (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. For every finite Abelian group L and every integer r 1, We writeL ≃ C n1 ⊕ • • • ⊕ C n ℓ , with 1 < n 1 | • • • | n ℓ ∈ N.

Acknowledgements

The author is grateful to W.A. Schmid for his careful reading of the manuscript in an earlier version.