The structure of higher sumsets

Lev, Vsevolod

doi:10.1090/proc/16128

The structure of higher sumsets
HTML articles powered by AMS MathViewer

by Vsevolod F. Lev PDF

Proc. Amer. Math. Soc. 150 (2022), 5165-5177 Request permission

Abstract:

Merging together a result of Nathanson from the early 70s and a recent result of Granville and Walker, we show that for any finite set $A$ of integers with $\min (A)=0$ and $\gcd (A)=1$ there exist two sets, the “head” and the “tail”, such that if $m\ge \max (A)-|A|+2$, then the $m$-fold sumset $mA$ consists of the union of the head, the appropriately shifted tail, and a long block of consecutive integers separating them. We give sharp estimates for the length of the block, and find all those sets $A$ for which the bound $\max (A)-|A|+2$ cannot be substantially improved.

References

N. Alon, Subset sums, J. Number Theory 27 (1987), no. 2, 196–205. MR 909836, DOI 10.1016/0022-314X(87)90061-8
G. A. Freĭman, Inverse problems of additive number theory. VI. On the addition of finite sets. III, Izv. VysŠ. Učebn. Zaved. Matematika 1962 (1962), no. 3 (28), 151–157 (Russian). MR 0152486
Jacques Dixmier, Proof of a conjecture by Erdős and Graham concerning the problem of Frobenius, J. Number Theory 34 (1990), no. 2, 198–209. MR 1042493, DOI 10.1016/0022-314X(90)90150-P
A. Granville and G. Shakan, The Frobenius postage stamp problem, and beyond, Acta Math. Hungar. 161 (2020), no. 2, 700–718. MR 4131939, DOI 10.1007/s10474-020-01073-y
Andrew Granville and Aled Walker, A tight structure theorem for sumsets, Proc. Amer. Math. Soc. 149 (2021), no. 10, 4073–4082. MR 4305964, DOI 10.1090/proc/15608
Vsevolod F. Lev, Optimal representations by sumsets and subset sums, J. Number Theory 62 (1997), no. 1, 127–143. MR 1430006, DOI 10.1006/jnth.1997.2012
Vsevolod F. Lev, The structure of multisets with a small number of subset sums, Astérisque 258 (1999), xiii, 179–186 (English, with English and French summaries). Structure theory of set addition. MR 1701196
Leo Moser and Peter Scherk, Advanced Problems and Solutions: Solutions: 4466, Amer. Math. Monthly 62 (1955), no. 1, 46–47. MR 1528921, DOI 10.2307/2308028
Melvin B. Nathanson, Sums of finite sets of integers, Amer. Math. Monthly 79 (1972), 1010–1012. MR 304305, DOI 10.2307/2318072
John E. Olson, On the sum of two sets in a group, J. Number Theory 18 (1984), no. 1, 110–120. MR 734442, DOI 10.1016/0022-314X(84)90047-7
J. L. Ramírez Alfonsín, The Diophantine Frobenius problem, Oxford Lecture Series in Mathematics and its Applications, vol. 30, Oxford University Press, Oxford, 2005. MR 2260521, DOI 10.1093/acprof:oso/9780198568209.001.0001
Svetoslav Savchev and Fang Chen, Long zero-free sequences in finite cyclic groups, Discrete Math. 307 (2007), no. 22, 2671–2679. MR 2351696, DOI 10.1016/j.disc.2007.01.012
Jian-Dong Wu, Feng-Juan Chen, and Yong-Gao Chen, On the structure of the sumsets, Discrete Math. 311 (2011), no. 6, 408–412. MR 2799890, DOI 10.1016/j.disc.2010.11.014
Pingzhi Yuan, On the index of minimal zero-sum sequences over finite cyclic groups, J. Combin. Theory Ser. A 114 (2007), no. 8, 1545–1551. MR 2360686, DOI 10.1016/j.jcta.2007.03.003