Davenport constant
In mathematics, the Davenport constant of a finite abelian group is defined as the smallest n, 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.
Example
- The Davenport constant for the cyclic group G = Z/n is n. To see this note that the sequence containing times a generator of this group contains no sub-sequence with sum 0, thus . On the other hand, if is a sequence of length , then two of the sums 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 , the sequence which consists of copies of , copies of , copies of contains no subsequence with sum 0, hence
- 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 and .
- 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]
- We have
Applications
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, its class group. Then every element , which factors into at least non-trivial ideals, is properly divisible by an element of . This observation implies that Davenport's constant determines by how muchh the lengths of different factorization of some element in 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 is defined similar to the Davenport constant, however, only sequences are considered, in which all elements are pairwise different. Balandraud proved that equals the smallest , such that . For we have . On the other hand if with , then Olson's constant equals the Davenport constant.
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) [1994], "Davenport constant", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
- Hutzler, Nick. "Davenport Constant". MathWorld.