On the Olson and the Strong Davenport constants

Ordaz, Oscar; Philipp, Andreas; Santos, Irene; Schmid, Wolfgang A.

Journal de théorie des nombres de Bordeaux, Tome 23 (2011) no. 3, pp. 715-750.

Soit $S$ un sous-ensemble d’un groupe abélien fini, noté additivement. Si $0$ n’est pas une sous-somme (non vide) de $S$, on dit que $S$ est un ensemble sans sous-somme nulle. Nous examinons la cardinalité maximale d’un ensemble sans sous-somme nulle, c’est-à-dire la (petite) constante d’Olson. Nous déterminons la cardinalité maximale d’un tel ensemble pour plusieurs types de groupes ; en particulier, les $p$-groupes dont le rang est suffisament grand relativement à l’exposant et plus particulièrement tous les groupes dont l’exposant est au plus $5$. Nous obtenons ces résultats comme des cas particuliers de résultats plus généraux, donnant des bornes inférieures pour la cardinalité d’un ensemble sans sous-somme nulle pour des groupes variés. Nous examinons la qualité de ces bornes en considérant des cas explicites, avec l’aide d’un ordinateur. De plus, nous examinons une notion très proche de la constante d’Olson : la cardinalité maximale d’un ensemble minimal de somme nulle, c’est-à-dire la constante de Davenport forte. En particulier, nous déterminons la valeur de cette constante pour les $p$-groupes élémentaires dont le rang est au plus $2$, en utilisant des résultats récents sur la constante d’Olson.

A subset $S$ of a finite abelian group, written additively, is called zero-sumfree if the sum of the elements of each non-empty subset of $S$ is non-zero. We investigate the maximal cardinality of zero-sumfree sets, i.e., the (small) Olson constant. We determine the maximal cardinality of such sets for several new types of groups; in particular, $p$-groups with large rank relative to the exponent, including all groups with exponent at most five. These results are derived as consequences of more general results, establishing new lower bounds for the cardinality of zero-sumfree sets for various types of groups. The quality of these bounds is explored via the treatment, which is computer-aided, of selected explicit examples. Moreover, we investigate a closely related notion, namely the maximal cardinality of minimal zero-sum sets, i.e., the Strong Davenport constant. In particular, we determine its value for elementary $p$-groups of rank at most $2$, paralleling and building on recent results on this problem for the Olson constant.

[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. | MR | Zbl

[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.

[5] S. T. Chapman, M. Freeze, and W. W. Smith, Minimal zero-sequences and the strong Davenport constant. Discrete Math. 203 (1999), 271–277. | MR | Zbl

[6] Ch. Delorme, A. Ortuño, and O. Ordaz, Some existence conditions for barycentric subsets. Rapport de Recherche $N^o$ 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. | MR | Zbl

[8] J.-M. Deshouillers and G. Prakash, Large zero-free subsets of $\mathbb{Z}/p\mathbb{Z}$. Manuscript.

[9] P. Erdős and H. Heilbronn, On the addition of residue classes $modp$. Acta Arith. 9 (1964), 149–159. | MR | Zbl

[10] M. Freeze, W. D. Gao, and A. Geroldinger, The critical number of finite abelain groups. J. Number Theory 129 (2009), 2766–2777. | MR | Zbl

[11] W. D. Gao and A. Geroldinger, On long minimal zero sequences in finite abelian groups. Period. Math. Hungar 38 (1999), 179–211. | MR | Zbl

[12] W. D. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: a survey. Expo. Math. 24 (2006), 337–369. | MR | Zbl

[13] W. D. Gao, A. Geroldinger, and D. J. Grynkiewicz, Inverse zero-sum problems III. Acta Arith. 141 (2010), 103–152. | MR | Zbl

[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. | MR | Zbl

[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. | MR

[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. | Numdam | MR

[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. | MR | Zbl

[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.

[19] R. K. Guy, Unsolved problems in number theory, third edition. Problem Books in Mathematics, Springer-Verlag, New York, 2004. | MR | Zbl

[20] Y. O. Hamidoune and G. Zémor, On zero-free subset sums. Acta Arith. 78 (1996), 143–152. | MR | Zbl

[21] H. H. Nguyen, E. Szemerédi, and V. H. Vu, Subset sums modulo a prime. Acta Arith. 131 (2008), 303–316. | MR | Zbl

[22] H. H. Nguyen and V. H. Vu, Classification theorems for sumsets modulo a prime. J. Combin. Theory Ser. A 116 (2009), 936–959. | MR | Zbl

[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. | MR | Zbl

[25] J. E. Olson, Sums of sets of group elements. Acta Arith. 28 (1975/76), 147–156. | MR | Zbl

[26] O. Ordaz and D. Quiroz, On zero free sets. Divulg. Mat. 14 (2006), 1–10. | MR | Zbl

[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. | MR | Zbl

[29] W. A. Schmid, Inverse zero-sum problems II. Acta Arith. 143 (2010), 333–343. | MR | Zbl

[30] J. C. Subocz G., Some values of Olson’s constant. Divulg. Mat. 8 (2000), 121–128. | MR | Zbl

[31] E. Szemerédi, On a conjecture of Erdős and Heilbronn. Acta Arith. 17 (1970), 227–229. | MR | Zbl

[32] P. Yuan, On the index of minimal zero-sum sequences over finte cyclic groups. J. Combin. Theory Ser. A 114 (2007), 1545–1551. | MR | Zbl