Iterated sumsets and subsequence sums

DOI10.1016/J.JCTA.2018.06.003MaRDI QIDQ1671777zbMATH OpenOpenAlexWikidataFDO

Authors David J. Grynkiewicz

Publication date 7 September 2018

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.09285

zbMATH Keywords

zero-sumsumsetcomplete sequencepartition theoremsubsequence sumsubsum\(n\)-fold sumsetiterated sumsetKemperman structure theoremOlson

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Additive bases, including sumsets (11B13) Inverse problems of additive number theory, including sumsets (11P70)

Abstract: Let $GcongmathbbZ/m_{1}mathbbZimesldotsimesmathbbZ/m_{r}mathbbZ$ be a finite abelian group with $m_{1}midldotsmid{m}_r=exp(G)$. The Kemperman Structure Theorem characterizes all subsets $A,,BsubseteqG$ satisfying $|A+B|<|A|+|B|$ and has been extended to cover the case when $|A+B|leq|A|+|B|$. Utilizing these results, we provide a precise structural description of all finite subsets $AsubseteqG$ with $|nA|leq(|A|+1)n-3$ when $ngeq3$ (also when $G$ is infinite), in which case many of the pathological possibilities from the case $n=2$ vanish, particularly for large $ngeqexp(G)-1$. The structural description is combined with other arguments to generalize a subsequence sum result of Olson asserting that a sequence $S$ of terms from $G$ having length $|S|geq2|G|-1$ must either have every element of $G$ representable as a sum of $|G|$-terms from $S$ or else have all but $|G/H|-2$ of its terms lying in a common $H$-coset for some $HleqG$. We show that the much weaker hypothesis $|S|geq|G|+exp(G)$ suffices to obtain a nearly identical conclusion, where for the case $H$ is trivial we must allow all but $|G/H|-1$ terms of $S$ to be from the same $H$-coset. The bound on $|S|$ is improved for several classes of groups $G$, yielding optimal lower bounds for $|S|$. We also generalize Olson's result for $|G|$-term subsums to an analogous one for $n$-term subsums when $ngeqexp(G)$, with the bound likewise improved for several special classes of groups. This improves previous generalizations of Olson's result, with the bounds for $n$ optimal.

Recommendations

• Iterated sumsets and Olson's generalization of the Erdős-Ginzburg-Ziv theorem
• Iterated sumsets and setpartitions
• scientific article; zbMATH DE number 5014481
• Subset sums in abelian groups
• A step beyond Kemperman's structure theorem

Cites work

• scientific article; zbMATH DE number 5014481 (Why is no real title available?)
• scientific article; zbMATH DE number 933467 (Why is no real title available?)
• scientific article; zbMATH DE number 3102822 (Why is no real title available?)
• A generalization of Kneser's addition theorem
• A step beyond Kemperman's structure theorem
• Addition theorems for finite abelian groups
• Additive combinatorics
• An addition theorem for finite abelian groups
• Combinatorial number theory and additive group theory. With a foreword by Javier Cilleruelo, Marc Noy and Oriol Serra (Coordinators of the DocCourse)
• Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
• Non-unique factorizations. Algebraic, combinatorial and analytic theory
• On a partition analog of the Cauchy-Davenport Theorem
• On small sumsets in an abelian group
• On the Olson and the strong Davenport constants
• On the critical pair theory in abelian groups: beyond Chowla's theorem
• Representation of finite abelian group elements by subsequence sums
• Two addition theorems
• Zero-sum problems in finite Abelian groups: a survey

Cited in

(11)

• A single set improvement to the \(3k - 4\) theorem
• Representing sequence subsums as sumsets of near equal sized sets
• On the Erdös-Ginzburg-Ziv theorem
• Extended inverse theorems for restricted sumset in integers
• Iterated sumsets and setpartitions
• On consecutive subset sums
• Iterated sumsets and Olson's generalization of the Erdős-Ginzburg-Ziv theorem
• scientific article; zbMATH DE number 2197931 (Why is no real title available?)
• Counting MSTD sets in finite abelian groups
• Subsequence summation and the \(m\) function
• Stability result for sets with \(3A \neq \mathbb{Z}_5^n\)

This page was built for publication: Iterated sumsets and subsequence sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1671777)