In mathematics, the Davenport constant D ( G ) of a finite abelian group G is defined as the smallest D, such that every sequence of elements of length n contains a non-empty sub-sequence adding up to 0. Davenport's constant belongs to the area of additive combinatorics.
The Davenport constant for the cyclic group G = Z/n is n. To see this note that the sequence containing n − 1 times a generator of this group contains no sub-sequence with sum 0, thus D ( G ) ≥ n . On the other hand, if g 1 , g 2 , … , g n is a sequence of length n , then two of the sums 0 , g 1 , g 1 + g 2 , … , g 1 + g 2 + ⋯ + g n are equal, and the difference of these two sums gives a sub-sequence with sum 0.For a finite abelian groupwith
invariant factors
d 1 | d 2 | ⋯ | d r , the sequence which consists of
d 1 − 1 copies of
( 1 , 0 , … , 0 ) ,
d 2 − 1 copies of
( 0 , 1 , 0 , … , 0 ) ,
d r − 1 , copies of
( 0 , 0 , … , 0 , 1 ) contains no subsequence with sum 0, hence
D ( G ) ≥ M ( G ) = 1 − r + ∑ i d i . It is known that D = M for p-groups and for r=1 or 2, as well as for certain groups including all groups of the form C 2 ⊕ C 2 n ⊕ C 2 n m and C 3 ⊕ C 3 n ⊕ C 3 n m .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.We have D ( G ) ≤ exp ( G ) ( 1 + log | G | exp ( G ) ) The original motivation for studying Davenport's constant was the problem of non-unique factorization in number fields. Let O be the ring of integers in a number field, G its class group. Then every element α ∈ O , which factors into at least D ( G ) non-trivial ideals, is properly divisible by an element of O . This observation implies that Davenport's constant determines by how muchh the lengths of different factorization of some element in 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.
Olson's constant O ( G ) is defined similar to the Davenport constant, however, only sequences g 1 , … , g n are considered, in which all elements are pairwise different. Balandraud proved that O ( C p ) equals the smallest k , such that k ( k + 1 ) 2 ≥ p . For p > 6000 we have O ( C p ⊕ C p ) = p − 1 + O ( C p ) . On the other hand if G = C p r with r ≥ p , then Olson's constant equals the Davenport constant.
