The terms that cancel almost everything

The product that counts partitions has $1/(1-q^k)$ in it. Turn each factor upside down and multiply out $\prod (1 - q^k)$ instead, and something completely unreasonable happens.

Expanding the product means choosing, from each factor, either $1$ or $-q^k$. A choice of factors to take the $-q^k$ from is a set of distinct part sizes, and the sign is minus one to the power of how many were chosen. So the coefficient of $q^n$ is

$$E(n) - O(n),$$

the number of partitions of $n$ into an even number of distinct parts, minus the number into an odd number.

At $n = 12$ there are fifteen partitions into distinct parts. The claim is that seven have an even number of parts and eight have an odd number, so the coefficient is $-1$. At $n = 6$ there are four, split two and two, and the coefficient is zero. That is a very peculiar thing for two counts to do.

Peculiar because there is no reason for it in the definition. $E(n)$ and $O(n)$ are counts of two collections that have nothing to do with each other beyond both being partitions into distinct parts; each grows quickly and erratically; and their difference is nevertheless zero at every number that is not one of a thin sequence. At $n = 20$ the two counts are $32$ and $32$; at $n = 21$ they are $38$ and $38$; at $n = 22$ they are $45$ and $44$, because twenty-two is pentagonal. Two large numbers agreeing exactly, over and over, is the shape of a theorem hiding behind a definition.

The theorem #

$$\prod_{k \ge 1} (1 - q^k) = \sum_{k = -\infty}^{\infty} (-1)^k q^{k(3k-1)/2} = 1 - q - q^2 + q^5 + q^7 - q^{12} - q^{15} + \cdots$$

The exponents are the generalised pentagonal numbers: $k(3k-1)/2$ as $k$ runs over all the integers, positive and negative, giving $1, 2, 5, 7, 12, 15, 22, 26$ and so on. Every other coefficient is zero.

Euler found this by expanding the product by hand — a long, careful piece of arithmetic — and stated it as a conjecture in 1741. He proved it about ten years later, and described the delay in print, which is unusual and worth respecting: he had a formula he was certain of and no argument for it, and said so.

Franklin’s pairing #

The proof that everybody now uses is Franklin’s, from 1881, and it is a sign-reversing involution: an operation that pairs each partition with another of opposite parity, so that the two cancel in $E(n) - O(n)$, applied to every partition except a handful that it cannot touch.

Take a partition of $n$ into distinct parts, written in descending order. Two features of it matter:

• $s$, the smallest part;
• $σ$, the length of the staircase running down from the top — the number of leading parts that decrease by exactly one each time.

The move is then:

• If $s \le σ$: remove the smallest part and add one to each of the top $s$ parts. The number of parts goes down by one.
• If $s > σ$: subtract one from each of the top $σ$ parts and lay them down as a new smallest part. The number of parts goes up by one.

Either way the total is unchanged, the parts stay distinct, and the number of parts changes by exactly one — so parity flips and the two partitions cancel. Doing the move twice returns the original, which is what makes it a pairing rather than a shuffle. Every one of those claims is checked in the figures, on every distinct-part partition of the number drawn.

The partitions the move cannot touch #

The move fails in exactly two situations, and they are the theorem.

It fails when the staircase is the whole partition and the smallest part is exactly $σ$ — the partition $2σ-1, 2σ-2, \dots, σ$ — because removing the smallest part and adding one to the top $s = σ$ parts would need $σ$ parts above it and there are only $σ - 1$. That partition sums to $σ(3σ-1)/2$.

It fails when the staircase is the whole partition and the smallest part is $σ + 1$ — the partition $2σ, 2σ-1, \dots, σ+1$ — because shaving the top $σ$ parts and laying down a new part of size $σ$ would collide with the part already equal to $σ+1$ after shaving. That partition sums to $σ(3σ+1)/2$.

So the survivors are staircases, one for each $σ$, at exactly the pentagonal numbers, each contributing $(-1)^σ$ because it has $σ$ parts. Everything else cancels. That is the whole proof.

Euler’s ten years #

The history is worth a paragraph because it is unusually well documented and unusually honest.

Euler expanded the product by hand far enough to be sure of the pattern, wrote to Goldbach about it in 1741, and said plainly that he could not prove it. He kept using it — the recurrence for $p(n)$ above was available to him immediately, and he computed partition counts with it — while continuing to describe it as conjectural. The proof came around 1750, by a manipulation of series rather than by any pairing of partitions.

That sequence of events is the ordinary shape of the subject and is worth seeing once: a pattern found by computation, used with care while unproved and labelled as unproved, and settled later by a different technique than the one that found it. This collection’s warning about small cases is the other half of the same lesson — a pattern in the first twenty coefficients is evidence and not a theorem, and Euler’s own conduct is the model for what to do with evidence.

Franklin’s proof arrived a hundred and thirty years after the theorem, and it is the one in every textbook now because it explains rather than verifies. Euler’s manipulation shows the identity is true; Franklin’s pairing shows which partitions survive and why, and the answer — staircases — is a fact about partitions that the algebra never mentions.

Reading the coefficient at a small number #

The general statement is easier to trust after one case is done by hand, and six is the right size for it.

The partitions of six into distinct parts are $6$, $5+1$, $4+2$ and $3+2+1$. Two have an odd number of parts and two have an even number, so the coefficient is zero. Franklin’s move should therefore pair all four off, and it does:

• $6$ has smallest part $6$ and staircase length $1$, so $s > σ$: shave one from the top part and lay down a new part of size one, giving $5+1$.
• $5+1$ has smallest part $1$ and staircase length $1$, so $s \le σ$: remove the smallest part and add one to the top part, giving $6$ again.
• $4+2$ has smallest part $2$ and staircase length $1$, so $s > σ$: shave the top, lay down a one, giving $3+2+1$.
• $3+2+1$ has smallest part $1$ and staircase length $3$, so $s \le σ$: remove the one, add one to the top part, giving $4+2$.

Two pairs, each with lengths differing by one, and nothing left over. At twelve the same run leaves $5+4+3$ standing, because the move applied to it would need a fourth part above the staircase and there is none.

Working an example that way is also the check that the description of the move above is the move being run. The figures assert the properties — parity flips, applying twice returns the original, the result is again a partition of the same number into distinct parts — over every partition at every parameter any essay uses, and a description that had drifted from the code would fail those assertions rather than sit quietly in the prose.

Why “pentagonal” #

The numbers $1, 5, 12, 22, 35$ count dots in nested pentagons — one dot, then a pentagon of five, then twelve, each shell adding another ring — in the same way that $1, 4, 9, 16$ count dots in nested squares. Every square is a stack of odd numbers makes the square case visible; the pentagonal case is the same construction with a different shape and a formula of $k(3k-1)/2$.

The other family, $2, 7, 15, 26$, comes from putting $k$ negative in the same formula, which is why they are called generalised pentagonal numbers rather than a second sequence.

Whether the pentagons explain anything is a fair question and the honest answer is no. Franklin’s proof produces the number $σ(3σ \pm 1)/2$ as the size of a staircase, and nothing in it draws a pentagon. The name records where the sequence was first met rather than why it appears here, which is a common pattern with named sequences and is worth saying rather than implying a connection that is not used.

What it is for #

The theorem is not a curiosity: it is the fastest elementary way to compute $p(n)$, and that is how every partition count in this collection was produced.

Multiply both sides of the product identity by the partition generating function. Since $\prod(1-q^k)$ and $\prod 1/(1-q^k)$ are reciprocals, their product is $1$, and reading off the coefficient of $q^n$ for $n > 0$ gives

$$p(n) - p(n-1) - p(n-2) + p(n-5) + p(n-7) - p(n-12) - \cdots = 0,$$

that is,

$$p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + \cdots$$

with the numbers subtracted being the pentagonal numbers and the signs in pairs. Since the pentagonal numbers below $n$ number about $\sqrt{8n/3}$, computing $p(n)$ costs about $\sqrt{n}$ additions given the earlier values — so all the values up to $n$ cost about $n^{3/2}$ operations altogether.

That is a striking economy. The obvious way to compute $p(n)$ is to expand a product of $n$ series, and the pentagonal recurrence replaces that with a handful of additions, because almost every term of the product cancels. The cancellation is not a curiosity about the coefficients; it is the reason the count is computable at all.

A special case of something larger #

The theorem is the smallest member of a family, and knowing that changes how it looks.

Jacobi’s triple product identity says that for suitable $z$ and $q$,

$$\prod_{k \ge 1} (1 - q^{2k})(1 + z q^{2k-1})(1 + z^{-1} q^{2k-1}) = \sum_{m = -\infty}^{\infty} z^m q^{m^2}.$$

A product of three infinite products on the left, a sum over all the integers on the right, and the pentagonal number theorem is what it becomes at one particular substitution. So the collapse this essay is about is not special to partitions; it is one specialisation of an identity whose natural home is the theory of theta functions.

That reframing explains something the elementary account leaves mysterious. The exponents in the sum on the right are $m^2$ — squares, symmetric about zero — and the pentagonal numbers are what those become after the substitution rescales them. The two-sided sum over all integers, positive and negative, which looks like an artificial device in the statement of Euler’s theorem, is completely natural there.

It also connects the subject to products that encode counting elsewhere: Euler’s other famous product, over the primes, is the same instinct applied to multiplication rather than to addition, and both were his.

The same device elsewhere #

An operation that pairs terms of opposite sign and is its own inverse is one of the most productive tools in combinatorics, and this collection now has several instances of it.

A determinant that counts trees is the same shape: the signed sum over permutations is cut down to the trees by a pairing that cancels everything else, and the path-counting lemma beside it pairs crossing paths with swapped ones. Inclusion and exclusion is the shape at its simplest. And the alternating property of the determinant itself is the pairing applied one level down.

What makes Franklin’s the classic example is that the pairing is almost total. Most sign-reversing involutions leave a substantial set of fixed points, and the answer is a count of them. Here the fixed points number zero or one, so the answer is zero or one, and a product of infinitely many series with infinitely many terms collapses to nearly nothing.

What the pictures cannot show #

The bar chart draws sixteen or twenty-six coefficients. The theorem is about all of them, and no drawing settles that — what the figure does is compute the coefficients by expanding the product and check each against what the theorem says it should be, which is a verification over the range drawn.

The involution is checked more thoroughly than it is drawn. At each parameter the figures run Franklin’s move on every partition of that number into distinct parts, assert that the result is again such a partition, assert that the number of parts changes by exactly one, and assert that applying the move twice returns the original. What is drawn is the handful the move cannot touch. So the picture shows the residue and the assertions cover the mechanism, which is the right division: the mechanism is a claim about every partition and the residue is what a reader wants to see.

The two failing cases are described in words above and are the part a figure would help most with. Drawing them means drawing a staircase, the move that would be attempted, and the collision that stops it — three panels for each of two cases, on a page that already has six figures. It is a reasonable thing to want and this essay does not have it.

Where the ladder goes next #

The recurrence computes $p(n)$ exactly and says nothing about its size. $p(100)$ is $190{,}569{,}292$; $p(1000)$ has twenty-four digits. That is the same division of labour the prime counting function lives under — an exact method that computes and an asymptotic that explains — and in both subjects the two were found a century and a half apart. What governs that growth is not the recurrence but the product read as an actual function of a complex variable, and the answer — Hardy and Ramanujan’s, in 1918 — has a square root in the exponent and a $\pi$ in front of it.