On Erdős's Method for Bounding the Partition Function

Abstract

For fixed $m$ and $R\subseteq \{0,1,\dots ,m-1\}$, take $A$ to be the set of positive integers congruent modulo $m$ to one of the elements of $R$, and let $p_A(n)$ be the number of ways to write $n$ as a sum of elements of $A$. Nathanson proved that $\log p_A(n)\le (1+o(1))\pi \sqrt{2n|R|/3m}$ using a variant of a remarkably simple method devised by Erdős in order to bound the partition function. In this short note we describe a simpler and shorter proof of Nathanson's bound.

To appear in Amer. Math. Monthly