The size of a number with no formula

The partition counts start $1, 2, 3, 5, 7, 11, 15, 22, 30, 42$ and reach $190{,}569{,}292$ at $n = 100$. The pentagonal recurrence computes any of them exactly and says nothing about their size, in the same way that adding up a column of figures tells nobody what the total looks like as a function of the column’s length.

The size is known, and precisely:

$$p(n) \sim \frac{1}{4n\sqrt{3}} \, \exp\!\left(π \sqrt{\tfrac{2n}{3}}\right).$$

What the formula is saying, and what it is not #

An asymptotic statement is about a ratio. It says the quotient of the two sides tends to one, which is compatible with the difference between them being enormous and growing.

That is not a caveat to be filed away; at the sizes anybody computes it is the dominant fact. At $n = 100$ the estimate gives about $199$ million against a true value of about $191$ million: a ratio of $0.96$, and an error of nine million — nine times $p(60)$, and vastly larger than every partition count anybody could list by hand. The formula is excellent and its error is astronomical, and both statements are about the same pair of numbers.

The shape of the growth #

Before the constant, the shape. The exponent contains $\sqrt{n}$, not $n$, and that single feature decides everything about how partition counts behave.

A function like $2^n$ grows exponentially: taking logarithms gives a straight line in $n$. A polynomial gives a logarithm proportional to $\log n$. Partitions sit between: $\log p(n)$ grows like $\sqrt{n}$, so $p(n)$ eventually outgrows every polynomial and is eventually outgrown by every exponential.

The intuition for the square root is worth having, and a rough version is available with no analysis. A partition of $n$ into distinct parts can use at most about $\sqrt{2n}$ parts, since the smallest sum of $m$ distinct parts is $m(m+1)/2$ — the triangular numbers, which is where the square root enters. So the number of parts, and the size of the largest part, both live at the scale $\sqrt{n}$ rather than $n$, and a count over choices of that many things at that scale produces an exponential in $\sqrt{n}$. Getting the constant $π\sqrt{2/3}$ takes a great deal more.

Ramanujan’s letter, and what was in it #

The formula came out of a collaboration that started with a letter, and the letter is part of why the result is told the way it is.

Ramanujan wrote to Hardy from Madras in 1913 with pages of results, most stated without proof and several wrong in ways that took work to see. Hardy’s judgement — that they must be true because nobody would have the imagination to invent them — is the famous line, and the partition asymptotic is the clearest case of the collaboration that followed: Ramanujan supplied the shape and the constant, Hardy supplied the contour integral that made it a theorem, and the correction terms came from both.

What makes the story more than an anecdote is the arithmetic Ramanujan was doing to find the formula. He had a table of $p(n)$ — MacMahon had computed it to two hundred — and the constants $π\sqrt{2/3}$ and $4\sqrt{3}$ were extracted from that table by somebody looking at numbers. The congruences of the next rung came out of the same table by the same method, and they are the more startling of the two discoveries, because a growth rate is the sort of thing a table might suggest and a divisibility pattern is not.

Where the formula comes from #

The generating function has been treated so far as formal bookkeeping. To get the asymptotic it has to be treated as a function of a complex variable, and everything follows from how it behaves near the boundary of the unit disc.

Inside that disc the product converges, and $p(n)$ can be recovered from it by a contour integral around a circle just inside the boundary. As the circle is pushed outward the function blows up — most violently at $q = 1$, less so at $q = -1$, less again at the cube roots of unity, and so on. The size of $p(n)$ is decided by how violently, and where.

Near $q = 1$ the growth is governed by a transformation law: the function satisfies a relation exchanging $q$ with a variable that measures approach to $1$ from the other side, so its explosion is not merely observed but computed exactly. That law is the modularity of the Dedekind eta function, and it is what Hardy and Ramanujan had that Euler did not.

The method — integrate over a circle, cut it into arcs near the roots of unity, estimate each arc — is the circle method, and it was invented here. It has since been the standard tool for counting problems of this shape, from sums of powers to representations by quadratic forms.

Ramanujan’s arrival, and Rademacher’s correction #

Hardy and Ramanujan published the asymptotic in 1918. Their paper does more than the formula above: it gives a series of correction terms, each involving a root of unity, and shows that summing the first few and rounding to the nearest whole number gives the exact value of $p(n)$ for $n$ well into the hundreds.

That already contradicts the title of this essay, and the contradiction was completed by Rademacher in 1937. He modified the series so that it converges — Hardy and Ramanujan’s diverges if pushed too far, and is a marvellous approximation rather than an identity — and the result is an exact expression:

$p(n)$ equals an infinite convergent series, every term of which is written in closed form.

So there is a formula. It is not a closed formula, and the distinction is worth keeping: the series has a term for each whole number, each term involves a sum of roots of unity and a hyperbolic function, and computing $p(n)$ from it needs about $\sqrt{n}$ terms. It is the fastest known method for a single large value, and it is what any modern computation of $p(10^6)$ uses.

The word “exact” is doing real work there and is worth pausing on. A convergent series of transcendental terms summing to a whole number is a strange object: every term is irrational, no partial sum is the answer, and the answer is nevertheless an integer that the partial sums close in on fast enough for rounding to be safe after a predictable number of terms. That combination — an integer written as an infinite sum of irrational pieces — is what a modular symmetry buys, and it is the same phenomenon as a class number or a dimension coming out of an analytic formula.

Subexponential, and why that matters elsewhere #

Growth like $\exp(c\sqrt{n})$ is unfamiliar enough to be worth placing beside the rates a reader already has.

It is far larger than any polynomial: $p(n)$ passes $n^{10}$ well before $n = 400$, and eventually passes $n^k$ for every $k$. It is far smaller than any exponential: $p(n)/1.01^n$ tends to zero. In between, it is the natural rate for counting problems where the objects have about $\sqrt{n}$ pieces of about $\sqrt{n}$ size — which is the situation the diagrams of the first rung make visible, since a Ferrers diagram of $n$ dots that is neither very tall nor very wide is about $\sqrt{n}$ on a side.

The same rate turns up in several other places for the same reason. The number of ways to factor an integer into ordered factors, the number of Young tableaux of a given size, the number of ways of writing a number as a sum of distinct parts — all of them are $\exp(c\sqrt{n})$ for their own $c$, and in each case the $\sqrt{n}$ comes from a constraint that limits how many pieces there can be.

That is worth knowing as a diagnostic. When a count comes out at $\exp(c\sqrt{n})$, something is limiting the number of pieces to about $\sqrt{n}$, and finding what it is usually explains the constant as well.

The comparison worth making #

The prime counting function is the other place in this collection where an exact count has no closed form and a precise asymptotic, and the two cases differ in an instructive way.

For primes the asymptotic $x/\log x$ is easy to state, hard to prove, and the error term is the deepest open problem in the subject. For partitions the asymptotic is harder to state, was proved within a few years of being conjectured, and the error is completely understood — because Rademacher turned the asymptotic into an identity.

The difference is in the objects. Partitions are governed by a generating function with a transformation law; the primes are governed by one whose behaviour on a critical line nobody can pin down. Where a modular symmetry is available, asymptotics become exact; where it is not, they remain estimates with contested error terms.

Reading an asymptotic honestly #

Three habits keep an asymptotic from being over-read, and this collection tries to hold to all three.

Say which quantity tends to what. “$p(n) \sim f(n)$” means $p(n)/f(n) \to 1$. It does not mean the difference is small, and it does not mean the relative error is small at any particular $n$ — only that it eventually is. A statement with no $n$ attached is not a claim about the value anybody wants.

Give the accuracy at a size somebody will use. The ratios in the figures are there because they are the numbers a reader can act on: a four per cent error at a hundred is a usable estimate, and a reader who was shown only the two curves lying on top of each other on a logarithmic axis would think it was better than that.

Say what the error term is when it is known and say that it is not known when it is not. Here it is known completely, because Rademacher’s series is exact and truncating it gives a bound. That is unusually good fortune. For the prime counting function the corresponding question is open, and this collection’s essay on it says so at length.

The three together are what separates an estimate that can be used inside a proof from a curve that looks convincing. An asymptotic with no error control is a heuristic, and a heuristic that has been drawn on a logarithmic scale is a heuristic that looks like a theorem.

What a good estimate is worth #

There is a fair objection to all of this: the recurrence computes $p(n)$ exactly and cheaply, so what is an approximation for?

Three things. It gives the shape — the fact that $\log p(n)$ grows like $\sqrt n$ is what makes partitions comparable with other combinatorial families, and no table of values supplies it. It gives values at sizes no recurrence reaches, since computing all the earlier values is itself the cost of the recurrence. And it is a statement about all $n$, so it can be used inside other proofs, which a table cannot.

The last of those is the real answer. An asymptotic formula is a lemma; a table is data. Any argument that needs to bound the number of partitions of $n$ in the middle of a longer proof — and there are many, in statistical mechanics, in representation theory, in the analysis of algorithms — needs a formula rather than a list. The same is true of the bounds on how many Latin squares there are, where the exact counts stop at eleven and every general statement about the family rests on the estimates instead.

What the pictures cannot show #

Every figure here stops at a hundred, and every claim is about the limit. The ratios drawn — $0.87$, $0.91$, $0.93$, $0.94$ — are consistent with a limit of one and equally consistent with a limit of $0.97$; nothing in the drawing distinguishes them. What the drawing establishes is that the estimate is in the right range and improving, and the theorem is what says where it is going.

The logarithmic scale is the other thing to be careful about, and it is a general hazard. On a log scale a five per cent error is invisible, and two curves that differ by nine million lie on top of each other. That is why the ratios are tabulated beside the plot rather than left to the eye: the picture shows the shape, the numbers show the accuracy, and either alone would mislead.

Nothing here draws the circle method. It is a contour integral in the complex plane whose integrand is a function with an essential singularity at every root of unity, and the arcs whose contributions are estimated are chosen by a delicate argument about which roots matter at which size. That is several essays’ worth of machinery in another field, and this one quotes its output and says so.

What the constant is made of #

The two constants in the formula deserve a sentence each, because both are recognisable and neither is arbitrary.

The $π\sqrt{2/3}$ in the exponent comes from the behaviour of the generating function near $q = 1$, and specifically from the value $π^2/6$ — the sum of the reciprocals of the squares, which turns up here as the leading term in the logarithm of the product as $q$ approaches one along the real axis. So the same constant that answers the Basel problem sets the growth rate of partitions, by way of $\sqrt{2 \cdot π^2/6}$, and the appearance of $π$ in a counting problem with no circle in it has exactly that provenance.

The $4n\sqrt{3}$ in the denominator comes from the width of the arc near $q = 1$ that contributes and from the Gaussian-shaped integral over it — the same kind of computation that puts a square root in front of every central limit estimate. Neither constant would be guessable from the first fifty values of $p(n)$, and Ramanujan guessed both.

Where the ladder goes next #

The counts have been treated as sizes throughout this rung. They also have arithmetic: $p(4) = 5$, $p(9) = 30$, $p(14) = 135$, and every one of those is divisible by five. So is every $p(5k+4)$, without exception, and there are matching statements for seven and eleven. Ramanujan found them by reading a table, and the explanation — a way of splitting the partitions of $5k+4$ into five equal classes — was found forty years later.