Representation of finite abelian group elements by subsequence sums

David J. Grynkiewicz; Luz E. Marchan; Oscar Ordaz

doi:10.5802/jtnb.689

David J. Grynkiewicz ¹ ; Luz E. Marchan ² ; Oscar Ordaz ³

¹ Institut für Mathematik und Wissenschaftliches Rechnen Karl-Franzens-Universität Graz Heinrichstraße 36 8010 Graz, Austria.
² Departamento de Matemáticas Decanato de Ciencias y Tecnologías Universidad Centroccidental Lisandro Alvarado Barquisimeto, Venezuela.
³ Departamento de Matemáticas y Centro ISYS Facultad de Ciencias Universidad Central de Venezuela Ap. 47567 Caracas 1041-A, Venezuela.

Journal de théorie des nombres de Bordeaux, Tome 21 (2009) no. 3, pp. 559-587.

Abstract (VO)
Résumé

Let $G ≅ C_{n_{1}} \oplus ... \oplus C_{n_{r}}$ be a finite and nontrivial abelian group with $n_{1} | n_{2} | ... | n_{r}$ . A conjecture of Hamidoune says that if $W = w_{1} \cdot ... \cdot w_{n}$ is a sequence of integers, all but at most one relatively prime to $| G |$ , and $S$ is a sequence over $G$ with $| S | \geq | W | + | G | - 1 \geq | G | + 1$ , the maximum multiplicity of $S$ at most $| W |$ , and $σ (W) \equiv 0 mod | G |$ , then there exists a nontrivial subgroup $H$ such that every element $g \in H$ can be represented as a weighted subsequence sum of the form $g = \underset{i = 1}{\sum^{n}} w_{i} s_{i}$ , with $s_{1} \cdot ... \cdot s_{n}$ a subsequence of $S$ . We give two examples showing this does not hold in general, and characterize the counterexamples for large $| W | \geq \frac{1}{2} | G |$ .

A theorem of Gao, generalizing an older result of Olson, says that if $G$ is a finite abelian group, and $S$ is a sequence over $G$ with $| S | \geq | G | + 𝔻 (G) - 1$ , then either every element of $G$ can be represented as a $| G |$ -term subsequence sum from $S$ , or there exists a coset $g + H$ such that all but at most $| G / H | - 2$ terms of $S$ are from $g + H$ . We establish some very special cases in a weighted analog of this theorem conjectured by Ordaz and Quiroz, and some partial conclusions in the remaining cases, which imply a recent result of Ordaz and Quiroz. This is done, in part, by extending a weighted setpartition theorem of Grynkiewicz, which we then use to also improve the previously mentioned result of Gao by showing that the hypothesis $| S | \geq | G | + 𝔻 (G) - 1$ can be relaxed to $| S | \geq | G | + d^{*} (G)$ , where $d^{*} (G) = \underset{i = 1}{\sum^{r}} (n_{i} - 1)$ . We also use this method to derive a variation on Hamidoune’s conjecture valid when at least $d^{*} (G)$ of the $w_{i}$ are relatively prime to $| G |$ .

Soit $G ≅ C_{n_{1}} \oplus ... \oplus C_{n_{r}}$ un groupe abélien fini non trivial avec $n_{1} | n_{2} | ... | n_{r}$ . Une conjecture d’Hamidoune dit que si $W = w_{1} \cdot ... \cdot w_{n}$ est une suite d’entiers, tous, sauf au plus un, premiers à $| G |$ , et $S$ une suite d’éléments de $G$ avec $| S | \geq | W | + | G | - 1 \geq | G | + 1$ , la multiplicité maximale de $S$ au plus $| W |$ , et $σ (W) \equiv 0 mod | G |$ , alors il existe un sous-groupe non trivial $H$ tel que tout élément $g \in H$ peut être représenté par une somme pondérée de la forme $g = \underset{i = 1}{\sum^{n}} w_{i} s_{i}$ , avec $s_{1} \cdot ... \cdot s_{n}$ une sous-suite de $S$ . Nous donnons deux exemples qui montrent que cela n’est pas vrai en général, et nous caractérisons les contre-exemples pour les grands $| W | \geq \frac{1}{2} | G |$ .

Un théorème de Gao, généralisant un résultat plus ancien d’Olson, dit que si $G$ est un groupe abélien fini, et $S$ une suite d’éléments de $G$ avec $| S | \geq | G | + 𝔻 (G) - 1$ , alors, soit tout élément de $G$ peut être représenté par une sous-somme de $S$ à $| G |$ termes, soit il existe une classe $g + H$ telle que tous sauf au plus $| G / H | - 2$ termes de $S$ sont dans $g + H$ . Nous établissons quelques cas très spéciaux d’un analogue pondéré de ce théorème, conjecturé par Ordaz et Quiroz, et quelques conclusions partielles dans les autres cas, qui impliquent un résultat récent d’Ordaz et Quiroz. Cela est fait, en partie, en étendant un théorème de Grynkiewicz sur les partitions pondérées, que nous utilisons également pour améliorer le résultat de Gao cité précédemment en montrant que l’hypothèse $| S | \geq | G | + 𝔻 (G) - 1$ peut être affaiblie en $| S | \geq | G | + d^{*} (G)$ , où $d^{*} (G) = \underset{i = 1}{\sum^{r}} (n_{i} - 1)$ . Nous utilisons aussi cette méthode pour déduire une variante de la conjecture d’Hamidoune valide si au moins $d^{*} (G)$ des $w_{i}$ sont premiers à $| G |$ .

MR Zbl

DOI : 10.5802/jtnb.689

Classification : 11B75, 20K01
Keywords: zero-sum problem, Davenport constant, weighted subsequence sums, setpartition,

d^{*} (G)

Affiliations des auteurs :

David J. Grynkiewicz ¹ ; Luz E. Marchan ² ; Oscar Ordaz ³

¹ Institut für Mathematik und Wissenschaftliches Rechnen Karl-Franzens-Universität Graz Heinrichstraße 36 8010 Graz, Austria.
² Departamento de Matemáticas Decanato de Ciencias y Tecnologías Universidad Centroccidental Lisandro Alvarado Barquisimeto, Venezuela.
³ Departamento de Matemáticas y Centro ISYS Facultad de Ciencias Universidad Central de Venezuela Ap. 47567 Caracas 1041-A, Venezuela.

@article{JTNB_2009__21_3_559_0,
     author = {David J. Grynkiewicz and Luz E. Marchan and Oscar Ordaz},
     title = {Representation of finite abelian group elements by subsequence sums},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {559--587},
     publisher = {Universit\'e Bordeaux 1},
     volume = {21},
     number = {3},
     year = {2009},
     doi = {10.5802/jtnb.689},
     mrnumber = {2605534},
     zbl = {1214.11034},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.689/}
}

TY  - JOUR
AU  - David J. Grynkiewicz
AU  - Luz E. Marchan
AU  - Oscar Ordaz
TI  - Representation of finite abelian group elements by subsequence sums
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2009
SP  - 559
EP  - 587
VL  - 21
IS  - 3
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.689/
DO  - 10.5802/jtnb.689
LA  - en
ID  - JTNB_2009__21_3_559_0
ER  -

%0 Journal Article
%A David J. Grynkiewicz
%A Luz E. Marchan
%A Oscar Ordaz
%T Representation of finite abelian group elements by subsequence sums
%J Journal de théorie des nombres de Bordeaux
%D 2009
%P 559-587
%V 21
%N 3
%I Université Bordeaux 1
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.689/
%R 10.5802/jtnb.689
%G en
%F JTNB_2009__21_3_559_0

David J. Grynkiewicz; Luz E. Marchan; Oscar Ordaz. Representation of finite abelian group elements by subsequence sums. Journal de théorie des nombres de Bordeaux, Tome 21 (2009) no. 3, pp. 559-587. doi : 10.5802/jtnb.689. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.689/

Bibliographie
Cité par

[1] Sukumar das Adhikari and Purusottam Rath, Davenport constant with weights and some related questions. Integers 6 (2006), A30, 6 pp (electronic). | MR | Zbl

[2] Sukumar das Adhikari and Yong-Gao Chen, Davenport constant with weights and some related questions II. J. Combin. Theory Ser. A 115 (2008), no. 1, 178–184. | MR

[3] N. Alon, A. Bialostocki and Y. Caro, The extremal cases in the Erdős-Ginzburg-Ziv Theorem. Unpublished.

[4] A. Bialostocki, P. Dierker, D. J. Grynkiewicz, and M. Lotspeich, On Some Developments of the Erdős-Ginzburg-Ziv Theorem II. Acta Arith. 110 (2003), no. 2, 173–184. | MR | Zbl

[5] Y. Caro, Zero-sum problems—a survey. Discrete Math. 152 (1996), no. 1–3, 93–113. | MR | Zbl

[6] P. Erdős, A. Ginzburg and A. Ziv, Theorem in Additive Number Theory. Bull. Res. Council Israel 10F (1961), 41–43. | Zbl

[7] W. Gao, Addition theorems for finite abelian groups. J. Number Theory 53 (1995), 241–246. | MR | Zbl

[8] W. Gao and A. Geroldinger, On Long Minimal Zero Sequences in Finite Abelian Groups. Periodica Math. Hungar. 38 (1999), no. 3, 179–211. | MR | Zbl

[9] W. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: A survey. Expositiones Mathematicae, 24 (2006), no. 4, 337–369. | MR | Zbl

[10] W. Gao and W. Jin, Weighted sums in finite cyclic groups. Discrete Math. 283 (2004), no. 1-3, 243–247. | MR | Zbl

[11] A. Geroldinger and F. Halter-Koch, Non-unique factorizations: Algebraic, combinatorial and analytic theory. Pure and Applied Mathematics (Boca Raton) 278. Chapman & Hall/CRC, Boca Raton, FL, 2006. | MR | Zbl

[12] A. Geroldinger and R. Schneider, On Davenport’s Constant. J. Combin. Theory, Ser. A 61 (1992), no. 1, 147–152. | MR | Zbl

[13] S. Griffiths, The Erdős-Ginzberg-Ziv theorem with units. To appear in Discrete math. | MR

[14] D. J. Grynkiewicz, A Weighted Erdős-Ginzburg-Ziv Theorem. Combinatorica 26 (2006), no. 4, 445–453. | MR | Zbl

[15] D. J. Grynkiewicz, Quasi-periodic Decompositions and the Kemperman Structure Theorem, European J. Combin. 26 (2005), no. 5, 559–575. | MR | Zbl

[16] D. J. Grynkiewicz, On a Partition Analog of the Cauchy-Davenport Theorem. Acta Math. Hungar. 107 (2005), no. 1–2, 161–174. | MR | Zbl

[17] D. J. Grynkiewicz, On a conjecture of Hamidoune for subsequence sum., Integers 5 (2005), no. 2, A7, 11 pp. (electronic). | MR | Zbl

[18] D. J. Grynkiewicz and R. Sabar, Monochromatic and zero-sum sets of nondecreasing modified diameter. Electron. J. Combin. 13 (2006), no. 1, Research Paper 28, 19 pp. (electronic). | MR | Zbl

[19] D. J. Grynkiewicz, Sumsets, Zero-sums and Extremal Combinatorics. Ph. D. Dissertation, Caltech (2005).

[20] D. J. Grynkiewicz, A Step Beyond Kemperman’s Stucture Theorem. Preprint (2007). | MR

[21] Y. O. Hamidoune and A. Plagne, A new critical pair theorem applied to sum-free sets in abelian groups. Comment. Math. Helv. 79 (2004), no. 1, 183–207. | MR | Zbl

[22] Y. O. Hamidoune, On weighted sequence sums. Comb. Prob. Comput. 4 (1995), 363–367. | MR | Zbl

[23] Y. O. Hamidoune, On weighted sums in abelian groups. Discrete Math. 162 (1996), 127–132. | MR | Zbl

[24] T. Hungerford, Algebra. Springer-Verlag, New York, 1974. | MR | Zbl

[25] J. H. B. Kemperman, On Small Sumsets in an Abelian Group. Acta Math. 103 (1960), 63–88. | MR | Zbl

[26] M. Kneser, Abschätzung der asymptotischen Dichte von Summenmengen. Math. Z. 58 (1953), 459–484. | MR | Zbl

[27] M. Kneser, Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen. Math. Z. 64 (1955), 429–434. | MR | Zbl

[28] S. Lang, Algebra. Third edition, Yale University, New Haven, CT, 1993.

[29] V. Lev, Critical pairs in abelian groups and Kemperman’s structure theorem. Int. J. Number Theory 2 (2006), no. 3, 379–396. | MR | Zbl

[30] M. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics 165, Springer-Verlag, New York, 1996. | MR | Zbl

[31] J. E. Olson, An addition theorem for finite abelian groups. J. Number Theory 9 (1977), no. 1, 63–70. | MR | Zbl

[32] O. Ordaz and D. Quiroz, Representation of group elements as subsequences sums. Discrete Mathematics 308 (2008), no. 15, 3315–3321. | MR | Zbl

[33] T. Tao and V. Vu, Additive Combinatorics. Cambridge Studies in Advanced Mathematics 105, Cambridge University Press, Cambridge, 2006. | MR | Zbl

Réka András; Kálmán Cziszter; Mátyás Domokos; István Szöllősi The Directed Cayley Diameter and the Davenport Constant, Recent Progress in Ring and Factorization Theory, Volume 477 (2025), p. 1 | DOI:10.1007/978-3-031-75326-8_1
Siao Hong; Kevin Zhao On the zero-sum subsequences of modular restricted lengths, Discrete Mathematics, Volume 347 (2024) no. 6, p. 19 (Id/No 113967) | DOI:10.1016/j.disc.2024.113967 | Zbl:1542.11018
A. Lemos; B. K. Moriya; A. O. Moura; A. T. Silva On the number of weighted zero-sum subsequences, Periodica Mathematica Hungarica, Volume 87 (2023) no. 2, pp. 366-373 | DOI:10.1007/s10998-023-00533-6 | Zbl:1538.11076
David J. Grynkiewicz Iterated sumsets and setpartitions, The Ramanujan Journal, Volume 52 (2020) no. 3, pp. 499-518 | DOI:10.1007/s11139-019-00155-y | Zbl:1477.11018
Abílio Lemos; Allan de Oliveira Moura; Anderson T. Silva; B. K. Moriya On the number of fully weighted zero-sum subsequences, International Journal of Number Theory, Volume 15 (2019) no. 5, pp. 1051-1057 | DOI:10.1142/s179304211950057x | Zbl:1459.11073
David J. Grynkiewicz Iterated sumsets and Olson's generalization of the Erdős-Ginzburg-Ziv theorem, Discrete mathematics days 2018. Extended abstracts of the 11th “Jornadas de matemática discreta y algorítmica” (JMDA), Sevilla, Spain, June 27–29, 2018, Amsterdam: Elsevier, 2018, pp. 29-34 | DOI:10.1016/j.endm.2018.06.006 | Zbl:1437.11028
David J. Grynkiewicz Iterated sumsets and subsequence sums, Journal of Combinatorial Theory. Series A, Volume 160 (2018), pp. 136-167 | DOI:10.1016/j.jcta.2018.06.003 | Zbl:1451.11107
M. Domokos Degree bound for separating invariants of abelian groups, Proceedings of the American Mathematical Society, Volume 145 (2017) no. 9, pp. 3695-3708 | DOI:10.1090/proc/13534 | Zbl:1372.13004
Weidong Gao; David J. Grynkiewicz; Xingwu Xia On $n$ -sums in an abelian group, Combinatorics, Probability and Computing, Volume 25 (2016) no. 3, pp. 419-435 | DOI:10.1017/s0963548315000255 | Zbl:1372.11031
Paul Baginski; Alfred Geroldinger; David J. Grynkiewicz; Andreas Philipp Products of two atoms in Krull monoids and arithmetical characterizations of class groups., European Journal of Combinatorics, Volume 34 (2013) no. 8, pp. 1244-1268 | DOI:10.1016/j.ejc.2013.05.008 | Zbl:1309.20050
David J. Grynkiewicz; Andreas Philipp; Vadim Ponomarenko Arithmetic-progression-weighted subsequence sums, Israel Journal of Mathematics, Volume 193 (2013), pp. 359-398 | DOI:10.1007/s11856-012-0119-8 | Zbl:1316.11010
David J. Grynkiewicz The Partition Theorem II, Structural Additive Theory, Volume 30 (2013), p. 229 | DOI:10.1007/978-3-319-00416-7_15
David J. Grynkiewicz; Luz Elimar Marchan; Oscar Ordaz A weighted generalization of two theorems of Gao, The Ramanujan Journal, Volume 28 (2012) no. 3, pp. 323-340 | DOI:10.1007/s11139-011-9350-x | Zbl:1320.11019
David J. Grynkiewicz Note on a conjecture of Graham, European Journal of Combinatorics, Volume 32 (2011) no. 8, pp. 1336-1344 | DOI:10.1016/j.ejc.2011.06.004 | Zbl:1262.11007
Huanhuan Guan; Pingzhi Yuan; Xiangneng Zeng Normal sequences over finite abelian groups, Journal of Combinatorial Theory. Series A, Volume 118 (2011) no. 4, pp. 1519-1524 | DOI:10.1016/j.jcta.2010.11.009 | Zbl:1243.11014

Cité par 15 documents. Sources : Crossref, zbMATH