Search the site
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, 21 no. 3 (2009), p. 559-587
Article: subscription required
Class. Math.: 11B75, 20K01
Keywords: zero-sum problem, Davenport constant, weighted subsequence sums, setpartition, $\mathsf {d}^*(G)$
Résumé - Abstract
Let $G\cong C_{n_1}\oplus \ldots \oplus C_{n_r}$ be a finite and nontrivial abelian group with $n_1|n_2|\ldots |n_r$. A conjecture of Hamidoune says that if $W=w_1\cdot \ldots \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|\ge |W|+|G|-1\ge |G|+1$, the maximum multiplicity of $S$ at most $|W|$, and $\sigma (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}{\overset{n}{\sum }}w_is_i$, with $s_1\cdot \ldots \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|\ge \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|\ge |G|+\mathbb{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$. 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|\ge |G|+\mathbb{D}(G)-1$ can be relaxed to $|S|\ge |G|+\mathsf {d}^*(G)$, where $\mathsf {d}^*(G)=\underset{i=1}{\overset{r}{\sum }}(n_i-1)$. We also use this method to derive a variation on Hamidoune’s conjecture valid when at least $\mathsf {d}^*(G)$ of the $w_i$ are relatively prime to $|G|$.
Bibliography
[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 2378862 | Zbl pre05232001
[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 2008084 | Zbl 1069.11007
[5] Y. Caro, Zero-sum problems—a survey. Discrete Math. 152 (1996), no. 1–3, 93–113. MR 1388634 | 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. MR 1348762 | 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. MR 1756238 | 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. MR 2313123 | Zbl 1122.11013
[10] W. Gao and W. Jin, Weighted sums in finite cyclic groups. Discrete Math. 283 (2004), no. 1-3, 243–247. MR 2061498 | 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. MR 2194494 | Zbl 1113.11002
[12] A. Geroldinger and R. Schneider, On Davenport’s Constant. J. Combin. Theory, Ser. A 61 (1992), no. 1, 147–152. MR 1178393 | Zbl 0759.20008
[13] S. Griffiths, The Erdős-Ginzberg-Ziv theorem with units. To appear in Discrete math. MR 2459367 | Zbl pre05499821
[14] D. J. Grynkiewicz, A Weighted Erdős-Ginzburg-Ziv Theorem. Combinatorica 26 (2006), no. 4, 445–453. MR 2260848 | Zbl 1121.11018
[15] D. J. Grynkiewicz, Quasi-periodic Decompositions and the Kemperman Structure Theorem, European J. Combin. 26 (2005), no. 5, 559–575. MR 2126639 | 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. MR 2148942 | Zbl 1102.11016
[17] D. J. Grynkiewicz, On a conjecture of Hamidoune for subsequence sum., Integers 5 (2005), no. 2, A7, 11 pp. (electronic). MR 2192085 | 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). MR 2212501 | 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).
arXiv | MR 2573603 | Zbl pre05666966
[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 2031705 | Zbl 1045.11072
[22] Y. O. Hamidoune, On weighted sequence sums. Comb. Prob. Comput. 4 (1995), 363–367. MR 1377556 | Zbl 0848.20049
[23] Y. O. Hamidoune, On weighted sums in abelian groups. Discrete Math. 162 (1996), 127–132. MR 1425783 | Zbl 0872.11016
[24] T. Hungerford, Algebra. Springer-Verlag, New York, 1974. MR 600654 | Zbl 0293.12001
[25] J. H. B. Kemperman, On Small Sumsets in an Abelian Group. Acta Math. 103 (1960), 63–88. MR 110747 | Zbl 0108.25704
[26] M. Kneser, Abschätzung der asymptotischen Dichte von Summenmengen. Math. Z. 58 (1953), 459–484. MR 56632 | Zbl 0051.28104
[27] M. Kneser, Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen. Math. Z. 64 (1955), 429–434. MR 68536 | 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. MR 2264598 | 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. MR 1477155 | Zbl 0859.11003
[31] J. E. Olson, An addition theorem for finite abelian groups. J. Number Theory 9 (1977), no. 1, 63–70. MR 437657 | Zbl 0351.20032
[32] O. Ordaz and D. Quiroz, Representation of group elements as subsequences sums. Discrete Mathematics 308 (2008), no. 15, 3315–3321. MR 2423413 | Zbl 1143.20032
[33] T. Tao and V. Vu, Additive Combinatorics. Cambridge Studies in Advanced Mathematics 105, Cambridge University Press, Cambridge, 2006. MR 2289012 | Zbl 1127.11002