×

On the Olson and the strong Davenport constants. (English. French summary) Zbl 1252.11011

Let \(G\) be a finite abelian group. Define \(O(G)\) as the least \(n\), such that every set \(S\subseteq G\) with \(|S|=n\) contains a non-empty subset \(T\) adding up to 0, and \(SD(G)\) largest \(n\), such that there exists a set \(S\) which does not contain a non-empty subset \(T\neq S\) adding up to 0. We clearly have \(O(G)-1\leq SD(G)\leq O(G)\), and equalities can occur on both sides. In the present work lower bounds for these invariants are found, which allow for the precise determination of \(O(G)\) and \(SD(G)\) for a large number of groups.
Since the notion of zero-sum free sets does not behave well under group homomorphisms, the authors first generalize \(SD\) to measure the size of zero-sum free sequences with not too much repetition. They then give recursive lower bounds involving specific subgroups. These bounds require tricky constructions. Although these results are too technical to be stated here, they are quite general and shall certainly be applied to a variety of other problems as well.
As applications the authors show that if \(G=\bigoplus_{i=1}^t \mathbb{Z}_{n_i}\) with \(n_1|n_2|\dots|n_t\), then \(SD(G)-\sum_{i=1}^t (n_i-1)\) can become arbitrary large, which is certainly striking. They also determine \(SD(G)\) for \(G=\mathbb{Z}_p, \mathbb{Z}_p^2\), \(p\) a sufficiently large prime, and all groups of exponent \(\leq 5\).

MSC:

11B30 Arithmetic combinatorics; higher degree uniformity
11B50 Sequences (mod \(m\))
11P70 Inverse problems of additive number theory, including sumsets
PDFBibTeX XMLCite
Full Text: DOI arXiv EuDML

References:

[1] P. Baginski, The strong Davenport constant and the Olson constant. Unpublished manuscript, 2005.
[2] G. Bhowmik and J.-Ch. Schlage-Puchta, An improvement on Olson’s constant for \(\mathbb{Z}_p \oplus \mathbb{Z}_p\). Acta Arith. 141 (2001), 311-319. · Zbl 1213.11041
[3] G. Bhowmik and J.-Ch. Schlage-Puchta, Additive combinatorics and geometry of numbers. Manuscript.
[4] É. Balandraud, An addition theorem and maximal zero-sumfree sets in \(\mathbb{Z}/p\mathbb{Z} \). Israel J. Math, to appear. · Zbl 1287.11013
[5] S. T. Chapman, M. Freeze, and W. W. Smith, Minimal zero-sequences and the strong Davenport constant. Discrete Math. 203 (1999), 271-277. · Zbl 0944.20013
[6] Ch. Delorme, A. Ortuño, and O. Ordaz, Some existence conditions for barycentric subsets. Rapport de Recherche \(N^o\textbf{990} \), LRI, Paris-Sud, Orsay, France. 1995.
[7] Ch. Delorme, I. Márquez, O. Ordaz, and A. Ortuño, Existence conditions for barycentric sequences. Discrete Math. 281 (2004), 163-172. · Zbl 1080.20020
[8] J.-M. Deshouillers and G. Prakash, Large zero-free subsets of \(\mathbb{Z}/p\mathbb{Z} \). Manuscript. · Zbl 1247.11129
[9] P. Erdős and H. Heilbronn, On the addition of residue classes \(~\@mod \;p\). Acta Arith. 9 (1964), 149-159. · Zbl 0156.04801
[10] M. Freeze, W. D. Gao, and A. Geroldinger, The critical number of finite abelain groups. J. Number Theory 129 (2009), 2766-2777. · Zbl 1214.11113
[11] W. D. Gao and A. Geroldinger, On long minimal zero sequences in finite abelian groups. Period. Math. Hungar 38 (1999), 179-211. · Zbl 0980.11014
[12] W. D. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: a survey. Expo. Math. 24 (2006), 337-369. · Zbl 1122.11013
[13] W. D. Gao, A. Geroldinger, and D. J. Grynkiewicz, Inverse zero-sum problems III. Acta Arith. 141 (2010), 103-152. · Zbl 1213.11178
[14] W. D. Gao, I. Z. Ruzsa, and R. Thangadurai, Olson’s constant for the group \(\mathbb{Z}_p \oplus \mathbb{Z}_p\). J. Combin. Theory Ser. A 107 (2004), 49-67. · Zbl 1107.11014
[15] A. Geroldinger, Additive group theory and non-unique factorizations. In: Combinatorial Number Theory and Additive Group Theory, pages 1-86, Advanced Course Math. CRM Barcelona, Birkhäuser Verlag, Basel, 2009. · Zbl 1221.20045
[16] A. Geroldinger, D. Grynkiewicz, and W. A. Schmid, The catenary degree of Krull monoids I. J. Théor. Nombres Bordeaux 23 (2011), 137-169. · Zbl 1253.11101
[17] A. Geroldinger and F. Halter-Koch, Non-Unique Factorizations. Algebraic, Combinatorial and Analytic Theory. Pure and Applied Mathematics, vol. 278, Chapman & Hall/CRC, 2006. · Zbl 1113.11002
[18] A. Geroldinger, M. Liebmann, and A. Philipp, On the Davenport constant and on the structure of extremal zero-sum free sequences. Period. Math. Hung., to appear. · Zbl 1263.11038
[19] R. K. Guy, Unsolved problems in number theory, third edition. Problem Books in Mathematics, Springer-Verlag, New York, 2004. · Zbl 0474.10001
[20] Y. O. Hamidoune and G. Zémor, On zero-free subset sums. Acta Arith. 78 (1996), 143-152. · Zbl 0863.11016
[21] H. H. Nguyen, E. Szemerédi, and V. H. Vu, Subset sums modulo a prime. Acta Arith. 131 (2008), 303-316. · Zbl 1136.11016
[22] H. H. Nguyen and V. H. Vu, Classification theorems for sumsets modulo a prime. J. Combin. Theory Ser. A 116 (2009), 936-959. · Zbl 1196.11048
[23] H. H. Nguyen and V. H. Vu, An asymptotic characterization for incomplete sets in vector spaces. Submitted.
[24] J. E. Olson, An addition theorem modulo \(p\). J. Combin. Theory 5 (1968), 45-52. · Zbl 0174.05202
[25] J. E. Olson, Sums of sets of group elements. Acta Arith. 28 (1975/76), 147-156. · Zbl 0318.10035
[26] O. Ordaz and D. Quiroz, On zero free sets. Divulg. Mat. 14 (2006), 1-10. · Zbl 1217.20033
[27] Ch. Reiher, A proof of the theorem according to which every prime number possesses Property B. Submitted.
[28] S. Savchev and F. Chen, Long zero-free sequemces in finite cyclic groups. Discrete Math. 307 (2007), 2671-2679. · Zbl 1148.20038
[29] W. A. Schmid, Inverse zero-sum problems II. Acta Arith. 143 (2010), 333-343. · Zbl 1219.11151
[30] J. C. Subocz G., Some values of Olson’s constant. Divulg. Mat. 8 (2000), 121-128. · Zbl 0973.11025
[31] E. Szemerédi, On a conjecture of Erdős and Heilbronn. Acta Arith. 17 (1970), 227-229. · Zbl 0222.10055
[32] P. Yuan, On the index of minimal zero-sum sequences over finte cyclic groups. J. Combin. Theory Ser. A 114 (2007), 1545-1551. · Zbl 1128.11011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.