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

on the partition function . In this post I’d like to record an elementary argument, making no use of generating functions, giving a lower bound of the form for some , 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 as a Young diagram of size , 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 . Heuristically, if the path takes a total of steps then there are about such paths, and if the area under the path is then the length of the path should be about , so this already goes a long way towards explaining the exponential-of-a-square-root behavior.

We can make this argument into a rigorous lower bound as follows. Consider lattice paths beginning at and ending at where is a positive integer to be determined later. Suppose that the steps of the lattice paths alternate between paths of the form (down, right, right, down) and (right, down, down, right), which means that is even. Then the area under the path is exactly the area of the right triangle it approximates, which is , and the number of such paths is exactly . This gives

whenever , so we get a lower bound of the form where , quite a bit worse than the correct value . This bound generalizes to all values of with only a small loss in the exponent because is nondecreasing (since the lattice path can continue along the line for awhile at the end before hitting the x-axis).

One reason this construction can’t produce a very good bound is that the partitions we get this way do not resemble the “typical” partition, which (as proven by Vershik and explained by David Speyer here) is a suitably scaled version of the curve

.

whereas our partitions resemble the curve . With a more convex curve we can afford to make the path longer while fixing the area under it.

So let’s remove the restriction that our curve resemble as follows. Rather than count directly, we will count , so the number of lattice paths with area at most . Since is increasing, it must be at least times this count. And we have much more freedom to pick a path now that we only need to bound its area rather than find it exactly. We can now take the path to be any Dyck path from to , of which there are

where denotes the Catalan numbers and the asymptotic can be derived from Stirling’s approximation. The area under a Dyck path is at most , which gives the lower bound

and hence, when (so that ),

which (ignoring polynomial factors) is of the from where , a substantial improvement over the previous bound. Although we are now successfully in a regime where our counts include paths of a typical shape, we’re overestimating the area under them, so the bound is still not as good as it could be.