# Davenport constant

In mathematics, the Davenport constant ${\displaystyle D(G)}$ of a finite abelian group ${\displaystyle G}$is defined as the smallest n, such that every sequence of elements of length n contains a non-empty sub-sequence adding up to 0. Davenport's constant belongs to the area of additive combinatorics.

## Example

• The Davenport constant for the cyclic group G = Z/n is n. To see this note that the sequence containing ${\displaystyle n-1}$ times a generator of this group contains no sub-sequence with sum 0, thus ${\displaystyle D(G)\geq n}$. On the other hand, if ${\displaystyle g_{1},g_{2},\ldots ,g_{n}}$ is a sequence of length ${\displaystyle n}$, then two of the sums ${\displaystyle 0,g_{1},g_{1}+g_{2},\ldots ,g_{1}+g_{2}+\dots +g_{n}}$ are equal, and the difference of these two sums gives a sub-sequence with sum 0.

## Properties

• For a finite abelian group
${\displaystyle G=\oplus _{i}C_{d_{i}}\ }$
with invariant factors ${\displaystyle d_{1}|d_{2}|\cdots |d_{r}}$, the sequence which consists of ${\displaystyle d_{1}-1}$ copies of ${\displaystyle (1,0,\ldots ,0)}$, ${\displaystyle d_{2}-1}$ copies of ${\displaystyle (0,1,0,\ldots ,0)}$, ${\displaystyle d_{r-1},}$ copies of ${\displaystyle (0,0,\ldots ,0,1)}$ contains no subsequence with sum 0, hence
${\displaystyle D(G)\geq M(G)=1-r+\sum _{i}d_{i}\ .}$
• It is known that D = M for p-groups and for r=1 or 2, as well as for certain groups including all groups of the form ${\displaystyle C_{2}\oplus C_{2n}\oplus C_{2nm}}$ and ${\displaystyle C_{3}\oplus C_{3n}\oplus C_{3nm}}$.
• 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.[1]
• We have ${\displaystyle D(G)\leq \exp(G)\left(1+\log {\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, ${\displaystyle G}$ its class group. Then every element ${\displaystyle \alpha \in {\mathcal {O}}}$, which factors into at least ${\displaystyle 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 muchh the lengths of different factorization of some element in ${\displaystyle {\mathcal {O}}}$ can differ.

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

## Variants

Olson's constant ${\displaystyle O(G)}$ is defined similar to the Davenport constant, however, only sequences ${\displaystyle g_{1},\ldots ,g_{n}}$ are considered, in which all elements are pairwise different. Balandraud proved that ${\displaystyle O(C_{p})}$ equals the smallest ${\displaystyle k}$, such that ${\displaystyle {\frac {k(k+1)}{2}}\geq p}$. For ${\displaystyle p>6000}$ we have ${\displaystyle O(C_{p}\oplus C_{p})=p-1+O(C_{p})}$. On the other hand if ${\displaystyle G=C_{p}^{r}}$ with ${\displaystyle r\geq p}$, then Olson's constant equals the Davenport constant.

## References

1. ^ Bhowmik & Schlage-Puchta (2007)
• Bhowmik, Gautami; Schlage-Puchta, Jan-Christoph (2007). "Davenport's constant for groups of the form Z3 + Z3 + Z3d". 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.
• 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. ISBN 978-3-7643-8961-1. Zbl 1221.20045.
• Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. 165. Springer-Verlag. ISBN 0-387-94655-1. Zbl 0859.11003.