×

Representation of finite abelian group elements by subsequence sums. (English) Zbl 1214.11034

Let \(G\) be a finite abelian group. Hamidoune conjectures that if \(W=w_1\cdot\dots\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 \(\sigma(W)\equiv 0 \pmod {|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=\sum_{i=1}^nw_is_i\), with \(s_1\cdot\dots\cdot s_n\) a subsequence of \(S\). The authors 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 states that if \(S\) is a sequence over \(G\) with \(|S|\geq |G|+D(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\). The authors 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 they use to also improve the previously mentioned result of Gao by showing that the hypothesis \(|S|\geq |G|+D(G)-1\)can be relaxed to \(|S|\geq |G|+d^*(G)\), where \(d^*(G)=\sum_{i=1}^r (n_i-1)\). They also use this method to derive a variation of Hamidoune’s conjecture valid when at least \(d^*(G)\) of the \(w_i\) are relatively prime to \(|G|\).

MSC:

11B75 Other combinatorial number theory
20K01 Finite abelian groups
PDF BibTeX XML Cite
Full Text: DOI arXiv Numdam EuDML

References:

[1] Sukumar das Adhikari and Purusottam Rath, Davenport constant with weights and some related questions. Integers 6 (2006), A30, 6 pp (electronic). · Zbl 1107.11018
[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. · Zbl 1210.11031
[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. · Zbl 1069.11007
[5] Y. Caro, Zero-sum problems—a survey. Discrete Math. 152 (1996), no. 1-3, 93-113. · Zbl 0856.05068
[6] P. Erdős, A. Ginzburg and A. Ziv, Theorem in Additive Number Theory. Bull. Res. Council Israel 10F (1961), 41-43. · Zbl 0063.00009
[7] W. Gao, Addition theorems for finite abelian groups. J. Number Theory 53 (1995), 241-246. · Zbl 0836.11007
[8] W. Gao and A. Geroldinger, On Long Minimal Zero Sequences in Finite Abelian Groups. Periodica Math. Hungar. 38 (1999), no. 3, 179-211. · Zbl 0980.11014
[9] W. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: A survey. Expositiones Mathematicae, 24 (2006), no. 4, 337-369. · Zbl 1122.11013
[10] W. Gao and W. Jin, Weighted sums in finite cyclic groups. Discrete Math. 283 (2004), no. 1-3, 243-247. · Zbl 1052.11014
[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. · Zbl 1113.11002
[12] A. Geroldinger and R. Schneider, On Davenport’s Constant. J. Combin. Theory, Ser. A 61 (1992), no. 1, 147-152. · Zbl 0759.20008
[13] S. Griffiths, The Erdős-Ginzberg-Ziv theorem with units. To appear in Discrete math. · Zbl 1206.11032
[14] D. J. Grynkiewicz, A Weighted Erdős-Ginzburg-Ziv Theorem. Combinatorica 26 (2006), no. 4, 445-453. · Zbl 1121.11018
[15] D. J. Grynkiewicz, Quasi-periodic Decompositions and the Kemperman Structure Theorem, European J. Combin. 26 (2005), no. 5, 559-575. · Zbl 1116.11081
[16] D. J. Grynkiewicz, On a Partition Analog of the Cauchy-Davenport Theorem. Acta Math. Hungar. 107 (2005), no. 1-2, 161-174. · Zbl 1102.11016
[17] D. J. Grynkiewicz, On a conjecture of Hamidoune for subsequence sum., Integers 5 (2005), no. 2, A7, 11 pp. (electronic). · Zbl 1098.11019
[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). · Zbl 1084.05073
[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).
[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. · Zbl 1045.11072
[22] Y. O. Hamidoune, On weighted sequence sums. Comb. Prob. Comput. 4 (1995), 363-367. · Zbl 0848.20049
[23] Y. O. Hamidoune, On weighted sums in abelian groups. Discrete Math. 162 (1996), 127-132. · Zbl 0872.11016
[24] T. Hungerford, Algebra. Springer-Verlag, New York, 1974. · Zbl 0293.12001
[25] J. H. B. Kemperman, On Small Sumsets in an Abelian Group. Acta Math. 103 (1960), 63-88. · Zbl 0108.25704
[26] M. Kneser, Abschätzung der asymptotischen Dichte von Summenmengen. Math. Z. 58 (1953), 459-484. · Zbl 0051.28104
[27] M. Kneser, Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen. Math. Z. 64 (1955), 429-434. · Zbl 0064.04305
[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. · Zbl 1157.11040
[30] M. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics 165, Springer-Verlag, New York, 1996. · Zbl 0859.11003
[31] J. E. Olson, An addition theorem for finite abelian groups. J. Number Theory 9 (1977), no. 1, 63-70. · Zbl 0351.20032
[32] O. Ordaz and D. Quiroz, Representation of group elements as subsequences sums. Discrete Mathematics 308 (2008), no. 15, 3315-3321. · Zbl 1143.20032
[33] T. Tao and V. Vu, Additive Combinatorics. Cambridge Studies in Advanced Mathematics 105, Cambridge University Press, Cambridge, 2006. · Zbl 1127.11002
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.