Davenport constant

In mathematics, the Davenport constant ${\displaystyle D(G)}$ is an invariant of a group studied in additive combinatorics, quantifying the size of nonunique factorizations. Given a finite abelian group ${\displaystyle G}$, ${\displaystyle 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^[1]

${\displaystyle 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 ${\displaystyle G=\mathbb {Z} /n\mathbb {Z} }$ is ${\displaystyle n}$. To see this, note that the sequence of a fixed generator, repeated ${\displaystyle n-1}$ times, contains no subsequence with sum 0. Thus ${\displaystyle D(G)\geq 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 subsequence with sum 0.^[2]

Properties

• Consider a finite abelian group ${\displaystyle G=\oplus _{i}C_{d_{i}}}$, where the ${\displaystyle d_{1}|d_{2}|\dots |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 consisting of ${\displaystyle d_{1}}$ copies of ${\displaystyle (1,0,\dots ,0)}$, ${\displaystyle d_{2}}$ copies of ${\displaystyle (0,1,\dots ,0)}$, etc., contains no subsequence with sum 0.^[3]
• ${\displaystyle D=M}$ for p-groups or when ${\displaystyle r}$ is 1 or 2.
• ${\displaystyle D=M}$ 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 ${\displaystyle r}$ at least 4 where ${\displaystyle D}$ does not equal ${\displaystyle M}$; it is not known whether there are any with ${\displaystyle r=3}$.^[3]
• Let ${\displaystyle \exp(G)}$ be the exponent of ${\displaystyle 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, ${\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 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 ${\displaystyle O(G)}$ uses the same definition, but requires the elements of ${\displaystyle \{g_{n}\}_{n=1}^{N}}$ to be distinct.^[6]

• 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.^[7]