Davenport constant

In mathematics, the Davenport constant $D(G)$ of a finite abelian group $G$ 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 $n-1$ times a generator of this group contains no sub-sequence with sum 0, thus $D(G)\geq n$ . On the other hand, if $g_{1},g_{2},\ldots ,g_{n}$ is a sequence of length $n$ , then two of the sums $0,g_{1},g_{1}+g_{2},\ldots ,g_{1}+g_{2}+\dots +g_{n}$ are equal, and the difference of these two sums gives a sub-sequence with sum 0.

Properties

For a finite abelian group

G=\oplus _{i}C_{d_{i}}\

with invariant factors

d_{1}|d_{2}|\cdots |d_{r}

, the sequence which consists of

d_{1}-1

copies of

(1,0,\ldots ,0)

d_{2}-1

copies of

(0,1,0,\ldots ,0)

d_{r-1},

copies of

(0,0,\ldots ,0,1)

contains no subsequence with sum 0, hence

D(G)\geq M(G)=1-r+\sum _{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}\oplus C_{2n}\oplus C_{2nm}$ and $C_{3}\oplus C_{3n}\oplus C_{3nm}$ .
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 $D(G)\leq \exp(G)\left(1+\log {\frac {|G|}{\exp(G)}}\right)$

Applications

The original motivation for studying Davenport's constant was the problem of non-unique factorization in number fields. Let ${\mathcal {O}}$ be the ring of integers in a number field, $G$ its class group. Then every element $\alpha \in {\mathcal {O}}$ , which factors into at least $D(G)$ non-trivial ideals, is properly divisible by an element of ${\mathcal {O}}$ . This observation implies that Davenport's constant determines by how muchh the lengths of different factorization of some element in ${\mathcal {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},\ldots ,g_{n}$ are considered, in which all elements are pairwise different. Balandraud proved that $O(C_{p})$ equals the smallest $k$ , such that ${\frac {k(k+1)}{2}}\geq p$ . For $p>6000$ we have $O(C_{p}\oplus C_{p})=p-1+O(C_{p})$ . On the other hand if $G=C_{p}^{r}$ with $r\geq p$ , 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 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) [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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.