Davenport constant
# 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, D(G ) is defined as the smallest number such that every sequence of elements of that length contains a non-empty subsequence adding up to 0. In symbols, this is

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

## Example

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

## Properties

* Consider a finite abelian group G = $⊕_i$ $C_{di}$ , where the $d_1$ | $d_2$ | ... | $d_r$ are invariant factors. Then

       $D(G)\geq M(G)=1-r+\sum _{i}{d_{i}}.$
    The lower bound is proved by noting that the sequence $"d_1$ − 1 copies of (1, 0, ..., 0), $d_2$ − 1 copies of (0, 1, ..., 0), etc." contains no subsequence with sum 0.
* D = M for p-groups or for r  = 1, 2.
* D = M for certain groups including all groups of the form $C_2$ ⊕ $C_{2n}$ ⊕ $C_{2nm}$ and $C_3$ ⊕ $C_{3n}$ ⊕ $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.
* Let $\exp(G)$ be the exponent of G. Then

       ${\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 ${\mathcal {O}}$ be the ring of integers in a number field, G its class group. Then every element $\alpha \in {\mathcal {O}}$, which factors into at least D(G ) non-trivial ideals, is properly divisible by an element of ${\mathcal {O}}$. This observation implies that Davenport's constant determines by how much the lengths of different factorization of some element in ${\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 O(G ) uses the same definition, but requires the elements of $\{g_{n}\}_{n=1}^{N}$ to be distinct.

* Balandraud proved that $O(C_p$ ) equals the smallest k such that ${\frac {k(k+1)}{2}}\geq p$.
* For p > 6000 we have

       $O(C_{p}\oplus C_{p})=p-1+O(C_{p})$.
    On the other hand, if G = $C^r$ $_p$ with r ≥ p, then Olson's constant equals the Davenport constant.
