Namespaces
Variants
Actions

Difference between revisions of "Davenport constant"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
For a finite [[Abelian group|Abelian group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d1100101.png" />, Davenport's constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d1100102.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d1100103.png" /> is the smallest positive integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d1100104.png" /> such that for any sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d1100105.png" /> of not necessarily distinct elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d1100106.png" /> there is a non-empty subsequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d1100107.png" /> with sum zero (i.e., there is some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d1100108.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d1100109.png" />).
+
<!--
 +
d1100101.png
 +
$#A+1 = 29 n = 0
 +
$#C+1 = 29 : ~/encyclopedia/old_files/data/D110/D.1100010 Davenport constant
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
It is reported in [[#References|[a7]]] that in 1966 H. Davenport proposed the problem of finding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001010.png" /> in the following connection. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001011.png" /> be an algebraic number field (cf. also [[Algebraic number|Algebraic number]]; [[Field|Field]]) with ring of integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001012.png" /> and ideal class group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001013.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001014.png" /> is the maximal number of prime ideals (counted with multiplicity) which can divide an irreducible element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001015.png" />. This is the reason why <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001016.png" /> is a crucial invariant in the theory of non-unique factorizations [[#References|[a2]]].
+
{{TEX|auto}}
 +
{{TEX|done}}
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001017.png" /> denote the [[Cyclic group|cyclic group]] with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001018.png" /> elements and suppose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001019.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001020.png" /> and with rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001021.png" />. Then
+
For a finite [[Abelian group|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 $).
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001022.png" /></td> </tr></table>
+
It is reported in [[#References|[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|Algebraic number]]; [[Field|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 [[#References|[a2]]].
  
In the left-hand inequality, equality holds for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001023.png" />-groups and for groups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001024.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001025.png" /> (proved independently by J.E. Olson [[#References|[a7]]] and D. Kruyswijk [[#References|[a3]]]; cf. also [[P-group|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001026.png" />-group]]). However, the left-hand inequality can be strict [[#References|[a4]]], [[#References|[a5]]]. For the right-hand inequality, cf. [[#References|[a6]]]. It is still (1996) an open question whether the left-hand inequality can be strict for groups of rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001027.png" /> or for groups of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001028.png" />.
+
Let  $  C _ {n} $
 +
denote the [[Cyclic group|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
  
The problem of determining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110010/d11001029.png" /> belongs to the area of zero-sum sequences, a subfield of [[Additive number theory|additive number theory]], respectively additive [[Group|group]] theory. For related problems cf. [[#References|[a1]]] and the literature cited there.
+
$$
 +
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 [[#References|[a7]]] and D. Kruyswijk [[#References|[a3]]]; cf. also [[P-group| $  p $-
 +
group]]). However, the left-hand inequality can be strict [[#References|[a4]]], [[#References|[a5]]]. For the right-hand inequality, cf. [[#References|[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|additive number theory]], respectively additive [[Group|group]] theory. For related problems cf. [[#References|[a1]]] and the literature cited there.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  P. van Emde Boas,  D. Kruyswijk,  "A combinatorial problem on finite abelian groups III"  ''Report Math. Centre'' , '''ZW–1969–008'''  (1969)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A. Geroldinger,  R. Schneider,  "On Davenport's constant"  ''J. Combin. Th. A'' , '''61'''  (1992)  pp. 147–152</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M. Mazur,  "A note on the growth of Davenport's constant"  ''Manuscr. Math.'' , '''74'''  (1992)  pp. 229–235</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R. Meshulam,  "An uncertainty inequality and zero subsums"  ''Discrete Math.'' , '''84'''  (1990)  pp. 197–200</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J.E. Olson,  "A combinatorial problem on finite abelian groups I–II"  ''J. Number Th.'' , '''1'''  (1969)  pp. 8–10; 195–199</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  P. van Emde Boas,  D. Kruyswijk,  "A combinatorial problem on finite abelian groups III"  ''Report Math. Centre'' , '''ZW–1969–008'''  (1969)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A. Geroldinger,  R. Schneider,  "On Davenport's constant"  ''J. Combin. Th. A'' , '''61'''  (1992)  pp. 147–152</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M. Mazur,  "A note on the growth of Davenport's constant"  ''Manuscr. Math.'' , '''74'''  (1992)  pp. 229–235</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R. Meshulam,  "An uncertainty inequality and zero subsums"  ''Discrete Math.'' , '''84'''  (1990)  pp. 197–200</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J.E. Olson,  "A combinatorial problem on finite abelian groups I–II"  ''J. Number Th.'' , '''1'''  (1969)  pp. 8–10; 195–199</TD></TR></table>

Latest revision as of 17:32, 5 June 2020


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