Davenport constant

Template:Short description Template:More citations needed 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 Template:Nowrap $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\{N:\mathrm{\forall }(\{g_n{\}}_{n=1}^N\in G^N)(\mathrm{\exists }\{n_k{\}}_{k=1}^K:\sum _{k=1}^K{g}_{n_k}=0)\}.$

Example

• The Davenport constant for the cyclic group $G=\mathbb{Z}/n\mathbb{Z}$ Template:Nowrap To see this, note that the sequence of a fixed generator, repeated $n-1$ times, contains no subsequence with sum 0. Thus $D(G)\ge 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 Template:Nowrap

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)\ge 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-group|Template:Mvar-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)}\le 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 $𝒪$ be the ring of integers in a number field, $G$ its class group. Then every element $\alpha \in 𝒪$, which factors into at least $D(G)$ non-trivial ideals, is properly divisible by an element of $𝒪$. This observation implies that Davenport's constant determines by how much the lengths of different factorization of some element in $𝒪$ can differ.Template: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.

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}\ge 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\ge p$, then Olson's constant equals the Davenport constant.

References

• Template:Cite book

External links

• Template:Springer
• Template:MathWorld