Improved bounds on the postage stamp problem for large numbers of stamps

Let Fₕ(n) denote the minimum cardinality of an additive { h-fold basis} of \1,2,⋯,n\: a set S such that any integer in \1,2,⋯, n\ can be written as a sum of at most h elements from S. While the trivial bounds h!n \; \; Fₕ(n)ʰ \; \; hʰ n are well-known, comparatively little has been established for $h>2$. In this paper, we make significant improvements to both of the best-known bounds on Fₕ(n) for sufficiently large 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ₕ(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$, for sufficiently large h, we have \[ (1/2-ε)h!√2πe n\; ≤ \; F_h(n)^h \; ≤ \; (({√3}{2}+ε)h)^h n. \]