{{more citations needed|date=May 2013}} In mathematics, the '''Davenport constant''' <math>D(G)</math> is an invariant of a group studied in additive combinatorics, quantifying the size of nonunique factorizations. Given a finite {{nowrap|abelian group <math>G</math>,}} <math>D(G)</math> is defined as the smallest number such that every sequence of elements of that length contains a non-empty subsequence adding up to 0. In symbols, this is<ref>{{cite book|title=Combinatorial number theory and additive group theory|url=https://archive.org/details/combinatorialnum00gero_991|url-access=limited|last=Geroldinger|first=Alfred|publisher=Birkhäuser|others=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)|year=2009|isbn=978-3-7643-8961-1|editor1-last=Geroldinger|editor1-first=Alfred|series=Advanced Courses in Mathematics CRM Barcelona|location=Basel|pages=[https://archive.org/details/combinatorialnum00gero_991/page/n7 1]–86|chapter=Additive group theory and non-unique factorizations|zbl=1221.20045|editor2-last=Ruzsa|editor2-first=Imre Z.|editor2-link=Imre Z. Ruzsa|doi=10.1007/978-3-7643-8962-8}}</ref> :<math>D(G) = \min\left\{ N : \forall\left(\{g_n\}_{n=1}^N \in G^N\right)\left(\exists\{n_k\}_{k=1}^K : \sum_{k=1}^K{g_{n_k}} = 0\right) \right\}.</math>

==Example== * The Davenport constant for the cyclic group <math>G = \mathbb Z/n\mathbb Z</math> {{nowrap|is <math>n</math>.}} To see this, note that the sequence of a fixed generator, repeated <math>n-1</math> times, contains no subsequence with sum 0. Thus <math>D(G)\ge n</math>. On the other hand, if <math>\{g_k\}_{k=1}^n</math> is an arbitrary sequence, then two of the sums in the sequence <math>\left\{\sum_{k=1}^K{g_k}\right\}_{K=0}^n</math> are equal. The difference of these two sums also gives a subsequence with {{nowrap|sum 0.{{Sfn|Geroldinger|2009|p=24}}}}

==Properties== * Consider a finite abelian group <math>G=\oplus_i C_{d_i}</math>, where the <math>d_1|d_2|\dots|d_r</math> are invariant factors. Then <math display=block>D(G) \ge M(G) = 1-r+\sum_i{d_i}.</math> The lower bound is proved by noting that the sequence consisting of <math>d_1</math> copies of <math>(1,0,\dots,0)</math>, <math>d_2</math> copies of <math>(0,1,\dots,0)</math>, etc., contains no subsequence with sum 0.<ref name=":0">{{cite book|title=Additive combinatorics|last1=Bhowmik|first1=Gautami|last2=Schlage-Puchta|first2=Jan-Christoph|publisher=American Mathematical Society|year=2007|isbn=978-0-8218-4351-2|editor1-last=Granville|editor1-first=Andrew|editor1-link=Andrew Granville|series=CRM Proceedings and Lecture Notes|volume=43|location=Providence, RI|pages=307–326|chapter=Davenport's constant for groups of the form <math>z_3\oplus z_3\oplus z_{3d}</math>|zbl=1173.11012|editor2-last=Nathanson|editor2-first=Melvyn B.|editor3-last=Solymosi|editor3-first=József|editor3-link= József Solymosi |chapter-url=http://math.univ-lille1.fr/~bhowmik/files/333d.pdf}}</ref> *<math>D=M</math> for {{mvar|p}}-groups or when <math>r</math> is 1 or 2. *<math>D=M</math> for certain groups including all groups of the form <math>C_2\oplus C_{2n}\oplus C_{2nm}</math> and <math>C_3\oplus C_{3n}\oplus C_{3nm}</math>. * There are infinitely many examples with <math>r</math> at least 4 where <math>D</math> does not equal <math>M</math>; it is not known whether there are any with <math>r=3</math>.<ref name=":0" /> * Let <math>\exp(G)</math> be the exponent of <math>G</math>. Then<ref name="Alford1994" /> <math display=block>\frac{D(G)}{\exp(G)} \leq 1+\log\left(\frac{|G|}{\exp(G)}\right).</math>

==Applications== The original motivation for studying Davenport's constant was the problem of non-unique factorization in number fields. Let <math>\mathcal{O}</math> be the ring of integers in a number field, <math>G</math> its class group. Then every element <math>\alpha\in\mathcal{O}</math>, which factors into at least <math>D(G)</math> non-trivial ideals, is properly divisible by an element of <math>\mathcal{O}</math>. This observation implies that Davenport's constant determines by how much the lengths of different factorization of some element in <math>\mathcal{O}</math> can differ.<ref>{{Cite journal|date=1969-01-01|title=A combinatorial problem on finite Abelian groups, I|journal=Journal of Number Theory|language=en|volume=1|issue=1|pages=8–10|doi=10.1016/0022-314X(69)90021-3|issn=0022-314X|last1=Olson|first1=John E.|bibcode=1969JNT.....1....8O|doi-access=free}}</ref>{{Citation needed|date=August 2018}}

The upper bound mentioned above plays an important role in Ahlford, Granville and Pomerance's proof of the existence of infinitely many Carmichael numbers.<ref name="Alford1994">{{cite journal|author=W. R. Alford|author2=Andrew Granville|author3-link=Carl Pomerance|author3=Carl Pomerance|year=1994|title=There are Infinitely Many Carmichael Numbers|url=http://www.math.dartmouth.edu/~carlp/PDF/paper95.pdf|journal=Annals of Mathematics|volume=139|issue=3|pages=703–722|doi=10.2307/2118576|jstor=2118576|author2-link=Andrew Granville|author-link=W. R. (Red) Alford}}</ref>

==Variants== Olson's constant <math>O(G)</math> uses the same definition, but requires the elements of <math>\{g_n\}_{n=1}^N</math> to be distinct.<ref>{{Cite journal|date=2012-01-01|title=A characterization of incomplete sequences in vector spaces|journal=Journal of Combinatorial Theory, Series A|language=en|volume=119|issue=1|pages=33–41|doi=10.1016/j.jcta.2011.06.012|issn=0097-3165|last1=Nguyen|first1=Hoi H.|last2=Vu|first2=Van H.|arxiv=1112.0754}}</ref>

* Balandraud proved that <math>O(C_p)</math> equals the smallest <math>k</math> such that <math>\frac{k(k+1)}{2} \geq p</math>. * For <math>p>6000</math> we have <math display=block>O(C_p\oplus C_p) = p-1+O(C_p).</math> On the other hand, if <math>G=C_p^r</math> with <math>r\ge p</math>, then Olson's constant equals the Davenport constant.<ref>{{Cite journal|last1=Ordaz|first1=Oscar|last2=Philipp|first2=Andreas|last3=Santos|first3=Irene|last4=Schmidt|first4=Wolfgang A.|date=2011|title=On the Olson and the Strong Davenport constants|url=http://www.numdam.org/article/JTNB_2011__23_3_715_0.pdf|journal= Journal de Théorie des Nombres de Bordeaux|volume=23|issue=3|pages=715–750|via=NUMDAM|doi=10.5802/jtnb.784|s2cid=36303975}}</ref>

==References== {{Reflist}} *{{cite book|first=Melvyn B.|last=Nathanson|title=Additive Number Theory: Inverse Problems and the Geometry of Sumsets|volume=165|series=Graduate Texts in Mathematics|publisher=Springer-Verlag|year=1996|isbn=978-0-387-94655-9|zbl=0859.11003}}

==External links== * {{springer|title=Davenport constant|id=p/d110010}} * {{MathWorld | title=Davenport Constant | id=DavenportConstant | author=Hutzler, Nick }}

Category:Sumsets