Namespaces
Variants
Actions

Davenport constant

From Encyclopedia of Mathematics
Jump to: navigation, search


For a finite Abelian group $ G $, Davenport's constant $ D ( G ) $ of $ G $ is the smallest positive integer $ d $ such that for any sequence $ S = ( g _ {1} \dots g _ {d} ) $ of not necessarily distinct elements of $ G $ there is a non-empty subsequence $ S ^ \prime \subseteq S $ with sum zero (i.e., there is some $ \emptyset \neq I \subseteq \{ 1 \dots d \} $ with $ \sum _ {i \in I } g _ {i} = 0 $).

It is reported in [a7] that in 1966 H. Davenport proposed the problem of finding $ D ( G ) $ in the following connection. Let $ K $ be an algebraic number field (cf. also Algebraic number; Field) with ring of integers $ R $ and ideal class group $ G $. Then $ D ( G ) $ is the maximal number of prime ideals (counted with multiplicity) which can divide an irreducible element of $ R $. This is the reason why $ D ( G ) $ is a crucial invariant in the theory of non-unique factorizations [a2].

Let $ C _ {n} $ denote the cyclic group with $ n $ elements and suppose $ G = C _ {n _ {1} } \oplus \dots \oplus C _ {n _ {r} } $ with $ 1 < n _ {1} | \dots | n _ {r} $ and with rank $ r ( G ) = r $. Then

$$ 1 + \sum _ {i = 1 } ^ { r } ( n _ {i} - 1 ) \leq D ( G ) \leq n _ {r} \left ( 1 + { \mathop{\rm log} } { \frac{\left | G \right | }{n _ {r} } } \right ) . $$

In the left-hand inequality, equality holds for $ p $- groups and for groups $ G $ with $ r ( G ) \leq 2 $( proved independently by J.E. Olson [a7] and D. Kruyswijk [a3]; cf. also $ p $- group). However, the left-hand inequality can be strict [a4], [a5]. For the right-hand inequality, cf. [a6]. It is still (1996) an open question whether the left-hand inequality can be strict for groups of rank $ 3 $ or for groups of the form $ G = C _ {n} ^ {r} $.

The problem of determining $ D ( G ) $ belongs to the area of zero-sum sequences, a subfield of additive number theory, respectively additive group theory. For related problems cf. [a1] and the literature cited there.

References

[a1] N. Alon, M. Dubiner, "Zero-sum sets of prescribed size" D. Miklós (ed.) V.T. Sós (ed.) T. Szönyi (ed.) , Combinatorics, Paul Erdös is Eighty , Bolyai Society Mathematical Studies , 1 , Keszthely (Hungary) (1993) pp. 33–50
[a2] S. Chapman, "On the Davenport's constant, the cross number and their application in factorization theory" , Lecture Notes in Pure and Appl. Math. , 171 , M. Dekker (1995) pp. 167–190
[a3] P. van Emde Boas, D. Kruyswijk, "A combinatorial problem on finite abelian groups III" Report Math. Centre , ZW–1969–008 (1969)
[a4] A. Geroldinger, R. Schneider, "On Davenport's constant" J. Combin. Th. A , 61 (1992) pp. 147–152
[a5] M. Mazur, "A note on the growth of Davenport's constant" Manuscr. Math. , 74 (1992) pp. 229–235
[a6] R. Meshulam, "An uncertainty inequality and zero subsums" Discrete Math. , 84 (1990) pp. 197–200
[a7] J.E. Olson, "A combinatorial problem on finite abelian groups I–II" J. Number Th. , 1 (1969) pp. 8–10; 195–199
How to Cite This Entry:
Davenport constant. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Davenport_constant&oldid=46585
This article was adapted from an original article by A. Geroldinger (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article