Misplaced Pages

Davenport constant

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Olson's constant)
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Davenport constant" – news · newspapers · books · scholar · JSTOR (May 2013) (Learn how and when to remove this message)

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, D(G ) 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

D ( G ) = min { N : ∀ ( { g n } n = 1 N ∈ G N ) ( ∃ { n k } k = 1 K : ∑ k = 1 K g n k = 0 ) } . {\displaystyle 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\}.}

Example

  • The Davenport constant for the cyclic group G = Z / n Z {\displaystyle 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 subsequence with sum 0. Thus D(G ) ≥ n. On the other hand, if { g k } k = 1 n {\displaystyle \{g_{k}\}_{k=1}^{n}} is an arbitrary sequence, then two of the sums in the sequence { ∑ k = 1 K g k } K = 0 n {\displaystyle \left\{\sum _{k=1}^{K}{g_{k}}\right\}_{K=0}^{n}} are equal. The difference of these two sums also gives a subsequence with sum 0.

Properties

D ( G ) ≥ M ( G ) = 1 − r + ∑ i d i . {\displaystyle D(G)\geq M(G)=1-r+\sum _{i}{d_{i}}.}
The lower bound is proved by noting that the sequence "d1 − 1 copies of (1, 0, ..., 0), d2 − 1 copies of (0, 1, ..., 0), etc." contains no subsequence with sum 0.
  • D = M for p-groups or for r  = 1, 2.
  • D = M for certain groups including all groups of the form C2 ⊕ C2n ⊕ C2nm and C3 ⊕ C3n ⊕ C3nm.
  • 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.
  • Let exp ⁡ ( G ) {\displaystyle \exp(G)} be the exponent of G. Then
D ( G ) exp ⁡ ( G ) ≤ 1 + log ⁡ ( | G | exp ⁡ ( G ) ) . {\displaystyle {\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 O {\displaystyle {\mathcal {O}}} be the ring of integers in a number field, G its class group. Then every element α ∈ O {\displaystyle \alpha \in {\mathcal {O}}} , which factors into at least D(G ) non-trivial ideals, is properly divisible by an element of O {\displaystyle {\mathcal {O}}} . This observation implies that Davenport's constant determines by how much the lengths of different factorization of some element in O {\displaystyle {\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 ) uses the same definition, but requires the elements of { g n } n = 1 N {\displaystyle \{g_{n}\}_{n=1}^{N}} to be distinct.

  • Balandraud proved that O(Cp ) equals the smallest k such that k ( k + 1 ) 2 ≥ p {\displaystyle {\frac {k(k+1)}{2}}\geq p} .
  • For p > 6000 we have
O ( C p ⊕ C p ) = p − 1 + O ( C p ) {\displaystyle O(C_{p}\oplus C_{p})=p-1+O(C_{p})} .
On the other hand, if G = C
 p with r ≥ p, then Olson's constant equals the Davenport constant.

References

  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.
  2. Geroldinger 2009, p. 24.
  3. ^ Bhowmik, Gautami; Schlage-Puchta, Jan-Christoph (2007). "Davenport's constant for groups of the form z {\displaystyle \mathbb {z} } 3⊕ z {\displaystyle \mathbb {z} } 3⊕ z {\displaystyle \mathbb {z} } 3d" (PDF). In Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József (eds.). Additive combinatorics. CRM Proceedings and Lecture Notes. Vol. 43. Providence, RI: American Mathematical Society. pp. 307–326. ISBN 978-0-8218-4351-2. Zbl 1173.11012.
  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. S2CID 36303975 – via NUMDAM.

External links

Category: