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

\(n\)-fold sumsetcomplete sequenceiterated sumsetKemperman structure theoremOlsonpartition theoremsubsequence sumsubsumsumsetzero-sum

Mathematics Subject Classification ID

Additive bases, including sumsets (11B13) Other combinatorial number theory (11B75) 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.

Review text

Let \(G\) be an abelian group (finite or not) and let \(A\subseteq G\) be a finite set such that the difference set \(A-A = \{a_1-a_2 : a_1,a_2 \in A\}\) generates \(G\). Also, let \(n\ge 3\) be an integer, the sumset \(nA = \{ a_1+\dots+a_n : a_1,\dots, a_n \in A \}\) has zero stabilizer and \[ |nA| < (|A|+1)n - 3 \,.\tag{1} \] The paper is devoted to study the structure of sets satisfying (1) and the author gives a complete description of such sets. After that he applies this inverse result to generalize a theorem of \textit{J. E. Olson} [J. Number Theory 9, 63--70 (1977; Zbl 0351.20032)] which is in turn a refinement of the famous Erdős-Ginzburg-Ziv theorem [\textit{P. Erdős} et al., Bull. Res. Council Israel 10F, 41--43 (1961; Zbl 0063.00009)], in several directions. For example, consider a sequence \(S\) of some elements of \(G\), \(|S|\ge n+|G|-1\), where \(1\le n\) be the maximal multiplicity in the sequence \(S\). Suppose that for every proper subgroup \(H\) and \(\alpha \in G\) there are at least \(|G/H|-1\) terms of \(S\) lying outside the coset \(H+\alpha\). If \(n\ge \exp (G)\), then any element of \(G\) can be expressed as a sum of several elements of \(S\).

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

• 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
• 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?)
• 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 critical pair theory in abelian groups: beyond Chowla's theorem
• On the Olson and the strong Davenport constants
• Representation of finite abelian group elements by subsequence sums
• Two addition theorems
• Zero-sum problems in finite Abelian groups: a survey

Cited in

(11)

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

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)