In
mathematics, the Davenport constantD(G ) is an
invariant of a
group studied in
additive combinatorics, quantifying the size of nonunique factorizations. Given a
finiteabelian groupG, 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[1]
Example
The Davenport constant for the
cyclic group is n. To see this, note that the sequence of a fixed
generator, repeated n − 1 times, contains no subsequence with sum 0. Thus D(G ) ≥ n. 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 sum 0.[2]
The lower bound is
proved by noting that the sequence "d1 − 1 copies of (1, 0, ..., 0), d2 − 1 copies of (0, 1, ..., 0), etc." contains no subsequence with sum 0.[3]
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 , 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.[5][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.[4]
Variants
Olson's constant O(G ) uses the same definition, but requires the elements of to be distinct.[6]
Balandraud proved that O(Cp ) equals the smallest k such that .
For p > 6000 we have
.
On the other hand, if G = Cr p with r ≥ p, then Olson's constant equals the Davenport constant.[7]
^Nguyen, Hoi H.; Vu, Van H. (2012-01-01). "A characterization of incomplete sequences in vector spaces". Journal of Combinatorial Theory, Series A. 119 (1): 33–41.
arXiv:1112.0754.
doi:
10.1016/j.jcta.2011.06.012.
ISSN0097-3165.