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)\geq 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=\oplus _{i}C_{d_{i}}$, where the $d_{1}|d_{2}|\dots |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 consisting of $d_{1}$ copies of $(1,0,\dots ,0)$, $d_{2}$ copies of $(0,1,\dots ,0)$, etc., contains no subsequence with sum 0.
• $D=M$ for p-groups or when $r$ is 1 or 2.
• $D=M$ for certain groups including all groups of the form $C_{2}\oplus C_{2n}\oplus C_{2nm}$ and $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$.
• 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_{p}^{r}$ with $r\geq p$, then Olson's constant equals the Davenport constant.

References

• Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. Vol. 165. Springer-Verlag. ISBN 978-0-387-94655-9. Zbl 0859.11003.

External links

• "Davenport constant", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Hutzler, Nick. "Davenport Constant". MathWorld.