Combinatorics Seminar - Spring '21

When: Sunday, May 16, 10am

Where: Schreiber 309

Speaker: Asaf Cohen Antonir, Tel Aviv University

Title: Exact Limit Theorems for Restricted Integer Partitions


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, Erdos 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 Erdos'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

$$ \liminf_{n \mapsto \infty}\frac{\log p_A(n)}{\log p(\alpha n)} \geq \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.

Joint work with Asaf Shapira.