Davenport constant

This article needs additional citations for verification. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (May 2013) (Learn how and when to remove this template message)

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 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 ${\displaystyle 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 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=⊕_iC_di, where the d₁|d₂|...|d_r 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 "d₁-1 copies of (1, 0, ..., 0), d₂-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 C₂⊕C_2n⊕C_2nm and C₃⊕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.^[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(C_p) 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=C^r
_p with r ≥ p, then Olson's constant equals the Davenport constant.^[7]

References[]