Davenport constant

In mathematics, the Davenport constant of a group determines how large a sequence of elements can be without containing a subsequence of elements which sum to zero. Its determination is an example of a zero-sum problem.

In general, a f inite abelian group G is considered. The Davenport constant D(G) is the smallest integer d such that every sequence of elements of G of length d contains a non-empty subsequence with sum equal to the zero element of G.[1]

Examples

The Davenport constant for the cyclic group G = Z/n is n.
If G is a p-group,

\( G = \oplus_i C_{p^{e_i}} \ \)

then

\( D(G) = 1 + \sum_i \left({p^{e_i} - 1}\right) \ . \)

Properties

For a finite abelian group

\( G = \oplus_i C_{d_i} \ \)

with invariant factors \( d_1 | d_2 | \cdots | d_r \), it is possible to find a sequence of \(\sum_i(d_i-1) \) elements without a zero sum subsequence, so

\(D(G) \ge M(G) = 1-r + \sum_i d_i \ . \)

It is known that D = M for p-groups and for r=1 or 2.
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.[1]

References

Bhowmik & Schlage-Puchta (2007)

Bhowmik, Gautami; Schlage-Puchta, Jan-Christoph (2007). "Davenport's constant for groups of the form Z3 + Z3 + Z3d". In Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József. Additive combinatorics. CRM Proceedings and Lecture Notes 43. Providence, RI: American Mathematical Society. pp. 307–326. ISBN 978-0-8218-4351-2. Zbl 1173.11012.
Geroldinger, Alfred (2009). "Additive group theory and non-unique factorizations". In Geroldinger, Alfred; Ruzsa, Imre Z. Combinatorial number theory and additive group theory. Advanced Courses in Mathematics CRM Barcelona. Elsholtz, C.; Freiman, G.; Hamidoune, Y. O.; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Sólymosi, J.; Stanchescu, Y. With a foreword by Javier Cilleruelo, Marc Noy and Oriol Serra (Coordinators of the DocCourse). Basel: Birkhäuser. pp. 1–86. ISBN 978-3-7643-8961-1. Zbl 1221.20045.
Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics 165. Springer-Verlag. ISBN 0-387-94655-1. Zbl 0859.11003.

External links

Hazewinkel, Michiel, ed. (2001), "Davenport constant", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
Hutzler, Nick, "Davenport Constant", MathWorld.

Mathematics Encyclopedia