Davenport constant

Template:More citations needed In mathematics, the Davenport constant Template:Math is an invariant of a group studied in additive combinatorics, quantifying the size of nonunique factorizations. Given a finite abelian group Template:Mvar, Template:Math 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}$ is Template:Mvar. To see this, note that the sequence of a fixed generator, repeated Template:Math times, contains no subsequence with sum Template:Math. Thus Template:Math. 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 Template:Math.Template:Sfn

Properties

• Consider a finite abelian group Template:Math , where the Template:Math 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 "Template:Math copies of Template:Math, Template:Math copies of Template:Math, etc." contains no subsequence with sum Template:Math.

• Template:Math for p-groups or for Template:Math.
• Template:Math for certain groups including all groups of the form Template:Math and Template:Math.
• There are infinitely many examples with Template:Mvar at least Template:Math where Template:Mvar does not equal Template:Mvar; it is not known whether there are any with Template:Math.
• Let $\exp (G)$ be the exponent of Template:Mvar. 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, Template:Mvar its class group. Then every element $\alpha \in 𝒪$, which factors into at least Template:Math 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 Template:Math uses the same definition, but requires the elements of $\{g_n{\}}_{n=1}^N$ to be distinct.

• Balandraud proved that Template:Math equals the smallest Template:Mvar such that $\frac{k(k+1)}{2}\ge p$.
• For Template:Math we have

$O(C_p\oplus C_p)=p-1+O(C_p)$.

On the other hand, if Template:Math with Template:Math, then Olson's constant equals the Davenport constant.

References

• Template:Cite book

External links

• Template:Springer
• Template:MathWorld