Davenport constant

In mathematics, the Davenport constant is an invariant of a group studied in additive combinatorics, quantifying the size of nonunique factorizations. Given a finite 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

Example

The Davenport constant for the cyclic group To see this, note that the sequence of a fixed generator, repeated times, contains no subsequence with sum 0. Thus. On the other hand, if is an arbitrary sequence, then two of the sums in the sequence are equal. The difference of these two sums also gives a subsequence with

Properties

Consider a finite abelian group, where the are invariant factors. Then The lower bound is proved by noting that the sequence consisting of copies of, copies of, etc., contains no subsequence with sum 0.
for -groups or when is 1 or 2.
for certain groups including all groups of the form and.
There are infinitely many examples with at least 4 where does not equal ; it is not known whether there are any with.
Let be the exponent of. Then

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, its class group. Then every element, which factors into at least 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.
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 uses the same definition, but requires the elements of to be distinct.

Balandraud proved that equals the smallest such that.
For we have On the other hand, if with, then Olson's constant equals the Davenport constant.