Feeds:
Posts

## More on partition asymptotics

In the previous post we described a fairly straightforward argument, using generating functions and the saddle-point bound, for giving an upper bound

$\displaystyle p(n) \le \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)$

on the partition function $p(n)$. In this post I’d like to record an elementary argument, making no use of generating functions, giving a lower bound of the form $\exp C \sqrt{n}$ for some $C > 0$, which might help explain intuitively why this exponential-of-a-square-root rate of growth makes sense.

The starting point is to think of a partition of $n$ as a Young diagram of size $n$, or equivalently (in French coordinates) as a lattice path from somewhere on the y-axis to somewhere on the x-axis, which only steps down or to the right, such that the area under the path is $n$. Heuristically, if the path takes a total of $L$ steps then there are about $2^L$ such paths, and if the area under the path is $n$ then the length of the path should be about $O(\sqrt{n})$, so this already goes a long way towards explaining the exponential-of-a-square-root behavior.

Let $p(n)$ denote the partition function, which describes the number of ways to write $n$ as a sum of positive integers, ignoring order. In 1918 Hardy and Ramanujan proved that $p(n)$ is given asymptotically by
$\displaystyle p(n) \approx \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)$.
This is a major plot point in the new Ramanujan movie, where Ramanujan conjectures this result and MacMahon challenges him by agreeing to compute $p(200)$ and comparing it to what this approximation gives. In this post I’d like to describe how one might go about conjecturing this result up to a multiplicative constant; proving it is much harder.