Exact Limit Theorems for Restricted Integer Partitions

Abstract

For a set of positive integers $A$, let $p_A(n)$ denote the number of ways to write $n$ as a sum of integers from $A$, and let $p(n)$ denote the usual partition function. In the early 40s, Erdős extended the classical Hardy--Ramanujan formula for $p(n)$ by showing that $A$ has density $\alpha$ if and only if $\log p_A(n)\sim \log p(\alpha n)$. Nathanson asked if Erdős's theorem holds also with respect to $A$'s lower density, namely, whether $A$ has lower-density $\alpha$ if and only if $\log p_A(n)/\log p(\alpha n)$ has lower limit $1$. We answer this question negatively by constructing, for every $\alpha >0$, a set of integers $A$ of lower density $\alpha$, satisfying $$\underset{n\to \infty }{\mathrm{liminf}}\frac{\log p_A(n)}{\log p(\alpha n)}\ge \left(\frac{\sqrt{6}}{\pi }-o_{\alpha }(1)\right)\log (1/\alpha ).$$ We further show that the above bound is best possible (up to the $o_{\alpha }(1)$ term), thus determining the exact extremal relation between the lower density of a set of integers and the lower limit of its partition function. We also prove an analogous theorem with respect to the upper density of a set of integers, answering another question of Nathanson.