Davenport constant

Example

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.

Properties

For a finite abelian group

with 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 ) )

Applications

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.

Variants

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.