Davenport constant#Variants

• The Davenport constant for the cyclic group $G\; =\; \backslash mathbb\; Z/n\backslash mathbb\; Z$ is {{mvar|n}}. To see this, note that the sequence of a fixed generator, repeated {{math|n − 1}} times, contains no subsequence with sum {{math|0}}. Thus {{math|D(G{{hairsp}}) ≥ n}}. On the other hand, if $\backslash \{g\_k\backslash \}\_\{k=1\}^n$ is an arbitrary sequence, then two of the sums in the sequence $\backslash left\backslash \{\backslash sum\_\{k=1\}^K\{g\_k\}\backslash right\backslash \}\_\{K=0\}^n$ are equal. The difference of these two sums also gives a subsequence with sum {{math|0}}.{{Sfn|Geroldinger|2009|p=24}}

• Consider a finite abelian group {{math|1=G = ⊕{{sub|i}} C{{sub|d{{sub|i}}}}}}{{hairsp}}, where the {{math|d{{sub|1}} {{!}} d{{sub|2}} {{!}} ... {{!}} d{{sub|r}}}} are invariant factors. Then

::$D(G)\; \backslash ge\; M(G)\; =\; 1-r+\backslash sum\_i\{d\_i\}.$

: The lower bound is proved by noting that the sequence "{{math|d{{sub|1}} − 1}} copies of {{math|(1, 0, ..., 0)}}, {{math|d{{sub|2}} − 1}} copies of {{math|(0, 1, ..., 0)}}, etc." contains no subsequence with sum {{math|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|$\backslash mathbb\{z\}$₃⊕$\backslash mathbb\{z\}$₃⊕$\backslash mathbb\{z\}$_3d}}|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}}

• {{math|1=D = M}} for p-groups or for {{math|1=r {{hairsp}}= 1, 2}}.
• {{math|1=D = M}} for certain groups including all groups of the form {{math|C{{sub|2}} ⊕ C{{sub|2n}} ⊕ C{{sub|2nm}}}} and {{math|C{{sub|3}} ⊕ C{{sub|3n}} ⊕ C{{sub|3nm}}}}.
• There are infinitely many examples with {{mvar|r}} at least {{math|4}} where {{mvar|D}} does not equal {{mvar|M}}; it is not known whether there are any with {{math|1=r = 3}}.
• Let $\backslash exp(G)$ be the exponent of {{mvar|G}}. Then

::$\backslash frac\{D(G)\}\{\backslash exp(G)\}\; \backslash leq\; 1+\backslash log\backslash left(\backslash frac$

The original motivation for studying Davenport's constant was the problem of non-unique factorization in number fields. Let $\backslash mathcal\{O\}$ be the ring of integers in a number field, {{mvar|G}} its class group. Then every element $\backslash alpha\backslash in\backslash mathcal\{O\}$, which factors into at least {{math|D(G{{hairsp}})}} non-trivial ideals, is properly divisible by an element of $\backslash mathcal\{O\}$. This observation implies that Davenport's constant determines by how much the lengths of different factorization of some element in $\backslash mathcal\{O\}$ can differ.{{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}}{{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.{{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}}

Olson's constant {{math|O(G{{hairsp}})}} uses the same definition, but requires the elements of $\backslash \{g\_n\backslash \}\_\{n=1\}^N$ to be distinct.{{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}}

• Balandraud proved that {{math|O(C{{sub|p}}{{hairsp}})}} equals the smallest {{mvar|k}} such that $\backslash frac\{k(k+1)\}\{2\}\; \backslash geq\; p$.
• For {{math|p > 6000}} we have

::$O(C\_p\backslash oplus\; C\_p)\; =\; p-1+O(C\_p)$.

: On the other hand, if {{math|1=G = C{{su|b={{hairsp}}p|p= r}}}} with {{math|r ≥ p}}, then Olson's constant equals the Davenport constant.{{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}}

{{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}}

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

Category:Sumsets