Davenport constant

In mathematics, the Davenport constant $D (G)$ is an invariant of a group studied in additive combinatorics, quantifying the size of nonunique factorizations. Given a finite abelian group $G$ is defined as the smallest number, such that every sequence of elements of that length contains a non-empty sub-sequence adding up to 0. In symbols, this is[1]

D(G)=\min {\left(\left\{N:\forall \left(\{g_{n}\}_{n=1}^{N}\in G^{N}\right)\left(\exists \{n_{k}\}_{k=1}^{K}\ni \sum _{k=1}^{K}{g_{n_{k}}}=0\right)\right\}\right)}

.

Example

The Davenport constant for the cyclic group $G=\mathbb {Z} /n\mathbb {Z}$ is $n$ . To see this note that the sequence of a fixed generator, repeated $n -1$ times, contains no sub-sequence with sum $0$ . Thus $D (G) \geq n$ . On the other hand, if $\{g_{k}\}_{k=1}^{n}$ is an arbitrary sequence, then two of the sums in the sequence $\left\{\sum _{k=1}^{K}{g_{k}}\right\}_{K=0}^{n}$ are equal. The difference of these two sums also gives a sub-sequence with sum $0$ .[2]

Properties

Consider a finite abelian group $G =\oplus i C d i$ , where the $d 1 | d 2 |...| d r$ are invariant factors. Then

D(G)\geq M(G)=1-r+\sum _{i}{d_{i}}

.

The lower bound is proved by noting that the sequence " $d 1 -1$ copies of $(1, 0, ..., 0)$ , $d 2 -1$ copies of $(0, 1, ..., 0)$ , etc." contains no subsequence with sum $0$ .[3]

$D = M$ for p-groups or for $r \in{1,2}$ .
$D = M$ for certain groups including all groups of the form $C 2 \oplus C 2 n \oplus C 2 nm$ and $C 3 \oplus C 3 n \oplus C 3 nm$ .
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$ .[3]
Let $\exp {(G)}$ be the exponent of $G$ . Then[4]

{\frac {D(G)}{\exp {(G)}}}\leq 1+\log {\left({\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 much the lengths of different factorization of some element in ${\mathcal {O}}$ can differ.[5]

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 $\{g_{n}\}_{n=1}^{N}$ to be pairwise different.[6]

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 r p$ with $r \geq p$ , then Olson's constant equals the Davenport constant.[7]

gollark: I could somehow build time delayed commands into the reminder system.

gollark: That could be a cool feature for my bot!

gollark: Newer-generation ones are actually moderately usable. My laptop's one from some years ago runs Minecraft fine.

gollark: So similar writing style (punctuation/grammar quirks/word choice/common constructions/etc.), discussion of similar topics, similar timezone/activity times, similar knowledge or implied knowledge, sort of thing.

gollark: There are lots of ways to make alts obvious; take what you should do to hide an alt, and do the opposite.

References

Geroldinger, Alfred (2009). "Additive group theory and non-unique factorizations". In Geroldinger, Alfred; Ruzsa, Imre Z. (eds.). 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. doi:10.1007/978-3-7643-8962-8. ISBN 978-3-7643-8961-1. Zbl 1221.20045.CS1 maint: ref=harv (link)
Geroldinger 2009, p. 24.
Bhowmik, Gautami; Schlage-Puchta, Jan-Christoph (2007). "Davenport's constant for groups of the form $𝕫 3 \oplus𝕫 3 \oplus𝕫 3 d$ " (PDF). In Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József (eds.). 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.
W. R. Alford; Andrew Granville; Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers" (PDF). Annals of Mathematics. 139 (3): 703–722. doi:10.2307/2118576. JSTOR 2118576.
Olson, John E. (1969-01-01). "A combinatorial problem on finite Abelian groups, I". Journal of Number Theory. 1 (1): 8–10. Bibcode:1969JNT.....1....8O. doi:10.1016/0022-314X(69)90021-3. ISSN 0022-314X.
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. ISSN 0097-3165.
Ordaz, Oscar; Philipp, Andreas; Santos, Irene; Schmidt, Wolfgang A. (2011). "On the Olson and the Strong Davenport constants" (PDF). Journal de Théorie des Nombres de Bordeaux. 23 (3): 715–750. doi:10.5802/jtnb.784 – via NUMDAM.

Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. 165. Springer-Verlag. ISBN 978-0-387-94655-9. Zbl 0859.11003.

External links

"Davenport constant", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
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.

[1] Geroldinger, Alfred (2009). "Additive group theory and non-unique factorizations". In Geroldinger, Alfred; Ruzsa, Imre Z. (eds.). 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. doi:10.1007/978-3-7643-8962-8. ISBN 978-3-7643-8961-1. Zbl 1221.20045.CS1 maint: ref=harv (link)

[FOOTNOTEGeroldinger200924-2] Geroldinger 2009, p. 24.

[:0-3] Bhowmik, Gautami; Schlage-Puchta, Jan-Christoph (2007). "Davenport's constant for groups of the form $𝕫 3 \oplus𝕫 3 \oplus𝕫 3 d$ " (PDF). In Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József (eds.). 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.

[Alford1994-4] W. R. Alford; Andrew Granville; Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers" (PDF). Annals of Mathematics. 139 (3): 703–722. doi:10.2307/2118576. JSTOR 2118576.

[5] Olson, John E. (1969-01-01). "A combinatorial problem on finite Abelian groups, I". Journal of Number Theory. 1 (1): 8–10. Bibcode:1969JNT.....1....8O. doi:10.1016/0022-314X(69)90021-3. ISSN 0022-314X.

[6] 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. ISSN 0097-3165.

[7] Ordaz, Oscar; Philipp, Andreas; Santos, Irene; Schmidt, Wolfgang A. (2011). "On the Olson and the Strong Davenport constants" (PDF). Journal de Théorie des Nombres de Bordeaux. 23 (3): 715–750. doi:10.5802/jtnb.784 – via NUMDAM.