Improved bounds on the postage stamp problem for large numbers of stamps
Eric James Faust, Michael Tait · 2025
Read Improved bounds on the postage stamp problem for large numbers of stamps by Eric James Faust, Michael Tait (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-23627.txt.
Introduction
Eric James Faust and Michael Tait wrote a 2025 math paper on the postage stamp problem. The question asks for the smallest stamp set from which any postage up to a limit can be formed with at most a set number of stamps. For more than two stamps, sharp bounds were scarce.
They improve both the lower and upper bounds for large stamp counts. The lower bound uses chance methods with a classic limit theorem. The upper bound builds on a known design for cyclic groups. Their new range squeezes the true size hard from both sides. The result is a rare big step on a problem that looks simple and is not.
Catalog record
| CREATOR | Eric James Faust, Michael Tait |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-23627
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved bounds on the postage stamp problem for large numbers of stamps Eric James Faust, Michael Tait Abstract Let F h ( n ) F_{h}(n) denote the minimum cardinality of an additive h h -fold basis of { 1 , 2 , ⋯ , n } \{1,2,\cdots,n\} : a set S S such that any integer in { 1 , 2 , ⋯ , n } \{1,2,\cdots,n\} can be written as a sum of at most h h elements from S S . While the trivial bounds h ! n ≲ F h ( n ) h ≲ h h n h!n\;\lesssim\;F_{h}(n)^{h}\;\lesssim\;h^{h}n are well-known, comparatively little has been established for h > 2 h>2 . In this paper, we make significant improvements to both of the best-known bounds on F h ( n ) F_{h}(n) for sufficiently large h h . For the lower bound, we use a probabilistic approach along with the Berry-Esseen Theorem to improve upon the best-known asymptotic result due to Yu. We also establish the first nontrivial asymptotic upper bound on F h ( n ) F_{h}(n) by leveraging a construction for additive bases of finite cyclic groups due to Jia and Shen. In particular, we show that given any ϵ > 0 \epsilon>0 , for sufficiently large h h , we have ( 1 2 − ϵ ) h ! 2 π e n ≤ F h ( n ) h ≤ ( ( 3 2 + ϵ ) h ) h n . \left(\frac{1}{2}-\epsilon\right)h!\sqrt{2\pi e}n\;\leq\;F_{h}(n)^{h}\;\leq\;\left(\left(\frac{\sqrt{3}}{2}+\epsilon\right)h\right)^{h}n. 1 Introduction Consider a post office that has envelopes with space for up to h stamps and that wants to be able to charge any amount between 1 and n cents for postage. What denominations of stamps should they use? What is the fewest possible number of denominations needed under these constraints? To formalize these problems, we define the sumsets we are interested in as follows. Given a subset A of an abelian group \Gamma and a natural number i , define iA=\{a_{1}+\cdots+a_{i}:a_{1},\cdots,a_{i}\in A\} . For a set A , define the representation function by r_{iA}(x)=\left|\{(a_{1},\cdots,a_{i})\in A^{k}:a_{1}+\cdots+a_{i}=x\}\right|, for each x\in\Gamma . That is, r_{iA}(x) tells us how many ways there are to represent x as a sum of exactly i elements from A . The problem posed above asks for the smallest set A\subseteq\mathbb{N} such that for any x\in\{1,\cdots,n\} we have that r_{1A}(x)+\cdots+r_{hA}(x)\geq 1 . We call this the postage stamp problem . We phrase this problem in the language of additive bases . Let S be a subset of \Gamma . We say A is an additive basis of S if every s\in S is representable in at least one way as a sum of elements from A . If this can be done using at most h (not necessarily distinct) elements from A , we say A is an order- h (or h -fold) basis of S . That is, for each s\in S , there are a_{1},a_{2},\dots,a_{k}\in A with k\leq h such that a_{1}+a_{2}+\dots+a_{k}=s. Using our sumset and representation function notation, this is equivalent to saying that S\subset\bigcup_{i=1}^{h}iA, or to saying that r_{1A}(x)+\cdots+r_{hA}(x)\geq 1 for all x\in S . The postage stamp problem then asks for the smallest size of an h -fold basis of \{1,2,\cdots,n\} . Some authors consider only sums with exactly h elements. This does not make a meaningful difference to this work because we may include 0 in our set, and because we are only interested in sizes asymptotically. We define F_{h}(S) to be the minimum size of an additive basis for S . That is, F_{h}(S):=\min\{|A|\mid A\subseteq\Gamma,A\text{ is an }h\text{-fold basis of }S\}. We denote \{1,2,\dots,n\} by [n] . When \Gamma=\mathbb{Z} and S=[n] , we define F_{h}(n)=F_{h}([n]) . In this paper, we will be interested in the bounds on F_{h}(n) when n tends to infinity and h is a large constant. Notation: Throughout the paper, A\gtrsim B (resp. A\lesssim B ) means A\geq(1+o(1))B (resp. A\leq(1+o(1))B ), where the o(1) term tends to 0 as n\rightarrow\infty . We will usually omit floor and ceiling symbols throughout the paper. There were numerous early papers written on the postage stamp problem/additive bases of integers up to n including [ 22 , 24 , 11 , 18 , 20 , 16 , 17 , 19 , 12 , 23 ] . We note that some previous papers consider the dual problem: given the size of the set |S| , what is the largest n such that one can find S which is an additive basis of \{1,\cdots,n\} ; these two problems are equivalent. Other work on additive bases has an extensive history which we do not try to summarize here. We consider bases only of finite sets, though bases of the integers or natural numbers themselves are also interesting objects, leading to, for example, the famous Erdős-Turán conjecture [ 4 ] . A good history of work on F_{h}(n) and other related functions is given in Bajnok’s book [ 1 ] , particularly in Section B. We also refer the reader to [ 6 ] , which was an early paper formalizing similar problems and is one of the most well-cited papers on these topics. We first give the “trivial” upper and lower bounds on F_{h}(n) . For the upper bound, any integer up to n can be written in base n^{1/h} using at most h summands, giving the upper bound F_{h}(n)\lesssim hn^{1/h}. This fact is well-known, but a proof is given for completeness in Lemma 2.1 . For the lower bound, by the definition of an additive basis A , we have that every integer between 1 and n is representable as a sum of at most h elements from A . Then, as there are \binom{|A|+i-1}{i} ways to sum i elements of A (with possible repetition), if each integer up to n can be written as a sum of at most h elements of A , we have that \sum\limits_{i=1}^{h}\binom{|A|+i-1}{i}\geq n, implying that F_{h}(n)\gtrsim(h!n)^{1/h} . Thus, the trivial bounds are given by the following theorem. Theorem 1.1 . Let A\subseteq\mathbb{Z} be an h -fold basis of [n] . Then we have h!n\;\lesssim\;F_{h}(n)^{h}\;\lesssim\;h^{h}n. We define \underline{c_{h}}:=\liminf\limits_{n\rightarrow\infty}\frac{F_{h}(n)^{h}}{n}\quad\text{ and }\quad\overline{c_{h}}:=\limsup\limits_{n\rightarrow\infty}\frac{F_{h}(n)^{h}}{n}, which both exist by Theorem 1.1 . Therefore, we have h!\;\leq\;\underline{c_{h}}\;\leq\;\overline{c_{h}}\;\leq\;h^{h}. Most of the previous work on F_{h}(n) has considered the case that h=2 . In this case, the trivial lower bound has been gradually improved over the years beginning in 1937 by Rohrbach [ 22 ] and continuing throughout the 20th century and into the 21st century using combinatorial methods and/or Fourier analysis [ 22 , 20 , 19 , 16 , 21 , 8 , 9 , 14 , 26 ] . For the upper bound, Rohrbach conjectured that the trivial bound is tight in [ 22 ] , but this was disproved in [ 10 , 13 , 25 ] . The current best results are given by Yu’s lower bound [ 27 ] and Mrose’s upper bound [ 25 ] : 2.1810\;\leq\;\underline{c_{2}}\;\leq\;\overline{c_{2}}\;\leq\;3.5. For h>2 , less is known. In particular, for h>2 , there is no better upper bound known than the trivial \overline{c_{h}}\leq h^{h} . For lower