Abstract
Let A be a finite subset of \(\mathbb{Z}^n\), which generates \(\mathbb{Z}^n\) additively. We provide a precise description of the N-fold sumsets NA for N sufficiently large, with some explicit bounds on “sufficiently large.”
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Dixmier, J.: Proof of a conjecture by Erdős and Graham concerning the problem of Frobenius. J. Number Theory 34, 198–209 (1990)
L. van den Dries, Mathematical Logic Lecture Notes, available at https://faculty .math.illinois.edu/~vddries/main.pdf
Erdős, P., Graham, R.: On a linear diophantine problem of Frobenius, Acta Arith. XX I, 399–408 (1972)
Andrew Granville and Aled Walker, A tight structure theorem for sumsets (to appear)
Khovanskii, A.G.: Newton polyhedron, Hilbert polynomial, and sums of finite sets. Funct. Anal. Appl. 26, 77–210 (1992)
Melvyn, B.: Nathanson, Sums of finite sets of integers. Amer. Math. Monthly 79, 1010–1012 (1972)
Melvyn, B.: Nathanson, Growth of sumsets in abelian semigroups. Semigroup Forum 61, 149–153 (2000)
Nathanson, Melvyn B., Ruzsa, Imre Z.: Polynomial growth of sumsets in abelian semigroups. J. Théor. Nombres Bordeaux 14, 553–560 (2002)
Mojzesz Presburger, Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt, in: Comptes Rendus du I congrès de Mathématiciens des Pays Slaves (Warsaw, 1929) (German); English translation: On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation, Hist. Philos. Logic12 (1991), 225–233
Imre Ruzsa, Sumsets and structure, in: Combinatorial Number Theory and Additive Group Theory, (A. Geroldinger and Imre Ruzsa, Eds.), Adv. Courses Math. CRM Barcelona, Birkhäuser Verlag (Basel, 2009), pp. 77–210
Savchev, Svetoslav, Chen, Fang: Long zero-free sequences in finite cyclic groups. Discrete Math. 307, 2671–2679 (2007)
Savchev, Svetoslav, Chen, Fang: An inverse problem about minimal zero-sum sequences over finite cyclic groups. J. Number Theory 177, 381–427 (2017)
Simpson, R., Tijdeman, R.: Multi-dimensional versions of a Theorem of Fine and Wilf and a formula of Sylvester. Proc. Amer. Math. Soc. 131, 1661–1671 (2003)
Sylvester, J.: Mathematical questions, with their linear solutions. Educational Times 41, 21 (1884)
Jian-Dong, Wu, Chen, Feng-Juan, Chen, Yong-Gao: On the structure of the sumsets. Discrete Math. 311, 408–412 (2011)
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to Endre Szemerédi on the occasion of his 80th birthday
A.G. was funded by the European Research Council grant agreement No. 670239, and by the Natural Sciences and Engineering Research Council of Canada (NSERC) under the Canada Research Chairs program.
G.S. was supported by Ben Green’s Simons Investigator Grant 376201.
Many thanks to Vsevolod Lev and Tyrrell McAllister for pointing us to the references [11] and [13], respectively, Mel Nathanson for many insightful and useful remarks, and especially Bjorn Poonen for providing us with a layman’s guide to Presburger’s theorem in this context and Elliot Kaplan for useful explanations and pointing.
Rights and permissions
About this article
Cite this article
Granville, A., Shakan, G. The Frobenius postage stamp problem, and beyond. Acta Math. Hungar. 161, 700–718 (2020). https://doi.org/10.1007/s10474-020-01073-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10474-020-01073-y