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 finite 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

1. Bhowmik & Schlage-Puchta (2007)

• Bhowmik, Gautami; Schlage-Puchta, Jan-Christoph (2007). "Davenport's constant for groups of the form Z₃ + Z₃ + Z_3d". 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.