# Davenport constant

In mathematics, the Davenport constant D(G) is an invariant of a group studied in additive combinatorics, quantifying the size of nonunique factorizations. Given a finite abelian group G is defined as the smallest number, such that every sequence of elements of that length contains a non-empty sub-sequence adding up to 0. In symbols, this is[1]

${\displaystyle D(G)=\min {\left(\left\{N:\forall \left(\{g_{n}\}_{n=1}^{N}\in G^{N}\right)\left(\exists \{n_{k}\}_{k=1}^{K}\ni \sum _{k=1}^{K}{g_{n_{k}}}=0\right)\right\}\right)}}$.

## Example

• The Davenport constant for the cyclic group G = 𝕫/(n) is n. To see this note that the sequence of a fixed generator, repeated n-1 times, contains no sub-sequence with sum 0. Thus D(G) ≥ n. On the other hand, if ${\displaystyle \{g_{k}\}_{k=1}^{n}}$ is an arbitrary sequence, then two of the sums in the sequence ${\displaystyle \left\{\sum _{k=1}^{K}{g_{k}}\right\}_{K=0}^{n}}$ are equal. The difference of these two sums also gives a sub-sequence with sum 0.[2]

## Properties

• Consider a finite abelian group G=⊕iCdi, where the d1|d2|…|dr are invariant factors. Then
${\displaystyle D(G)\geq M(G)=1-r+\sum _{i}{d_{i}}}$.

The lower bound is proved by noting that the sequence "d1-1 copies of (1, 0, …, 0), d2-1 copies of (0, 1, …, 0), etc." contains no subsequence with sum 0.[3]

• D=M for p-groups or for r∈{1,2}.[clarification needed]
• D=M for certain groups including all groups of the form C2C2nC2nm and C3C3nC3nm.
• There are infinitely many examples with r at least 4 where D does not equal M; it is not known whether there are any with r = 3.[3]
• Let ${\displaystyle \exp {(G)}}$be the exponent of G. Then[4]
${\displaystyle {\frac {D(G)}{\exp {(G)}}}\leq 1+\log {\left({\frac {|G|}{\exp {(G)}}}\right)}}$.

## Applications

The original motivation for studying Davenport's constant was the problem of non-unique factorization in number fields. Let ${\displaystyle {\mathcal {O}}}$ be the ring of integers in a number field, G its class group. Then every element ${\displaystyle \alpha \in {\mathcal {O}}}$, which factors into at least D(G) non-trivial ideals, is properly divisible by an element of ${\displaystyle {\mathcal {O}}}$. This observation implies that Davenport's constant determines by how much the lengths of different factorization of some element in ${\displaystyle {\mathcal {O}}}$ can differ.[5][citation needed]

The upper bound mentioned above plays an important role in Ahlford, Granville and Pomerance's proof of the existence of infinitely many Carmichael numbers.[4]

## Variants

Olson's constant O(G) uses the same definition, but requires the elements of ${\displaystyle \{g_{n}\}_{n=1}^{N}}$to be pairwise different.[6]

• Balandraud proved that O(Cp) equals the smallest k, such that ${\displaystyle {\frac {k(k+1)}{2}}\geq p}$.
• For p>6000, we have
${\displaystyle O(C_{p}\oplus C_{p})=p-1+O(C_{p})}$.

On the other hand, if G=Cr
p
with r ≥ p, then Olson's constant equals the Davenport constant.[7]

## References

1. ^ Geroldinger, Alfred (2009). "Additive group theory and non-unique factorizations". In Geroldinger, Alfred; Ruzsa, Imre Z. Combinatorial number theory and additive group theory. Advanced Courses in Mathematics CRM Barcelona. Elsholtz, C.; Freiman, G.; Hamidoune, Y. O.; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Sólymosi, J.; Stanchescu, Y. With a foreword by Javier Cilleruelo, Marc Noy and Oriol Serra (Coordinators of the DocCourse). Basel: Birkhäuser. pp. 1–86. doi:10.1007/978-3-7643-8962-8. ISBN 978-3-7643-8961-1. Zbl 1221.20045.
2. ^ Geroldinger 2009, p. 24.
3. ^ a b Bhowmik, Gautami; Schlage-Puchta, Jan-Christoph (2007). "Davenport's constant for groups of the form 𝕫3⊕𝕫3⊕𝕫3d" (PDF). In Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József. Additive combinatorics. CRM Proceedings and Lecture Notes. 43. Providence, RI: American Mathematical Society. pp. 307–326. ISBN 978-0-8218-4351-2. Zbl 1173.11012.
4. ^ a b W. R. Alford; Andrew Granville; Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers" (PDF). Annals of Mathematics. 139 (3): 703–722. doi:10.2307/2118576. JSTOR 2118576.
5. ^ Olson, John E. (1969-01-01). "A combinatorial problem on finite Abelian groups, I". Journal of Number Theory. 1 (1): 8–10. doi:10.1016/0022-314X(69)90021-3. ISSN 0022-314X.
6. ^ Nguyen, Hoi H.; Vu, Van H. (2012-01-01). "A characterization of incomplete sequences in vector spaces". Journal of Combinatorial Theory, Series A. 119 (1): 33–41. doi:10.1016/j.jcta.2011.06.012. ISSN 0097-3165.
7. ^ Ordaz, Oscar; Philipp, Andreas; Santos, Irene; Schmidt, Wolfgang A. (2011). "On the Olson and the Strong Davenport constants" (PDF). Journal de Théorie de Nombres de Bordeaux. 23 (3): 715–750. doi:10.5802/jtnb.784 – via NUMDAM.