The pentagonal number theorem

Here's a strange fact:

$\displaystyle\prod_{k=1}^\infty (1-x^k) = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} + \cdots = 1 + \displaystyle\sum_{a=1}^\infty (-1)^a x^{a(3a \pm 1)/2}$

There's a pattern here, but it's hard to spot. Terms like $x^n$ will only appear when $n = \frac{a(3a \pm 1)}{2}$, where $a$ is an integer greater than 0. This means that if we continued this expansion we would run across terms like $x^{35}, x^{40}, x^{51}...$, but in order to know this for certain we need to prove that this pattern exists.

To get started, we should forget about the righthand side of the equations above and just focus on the left. We have the expression $(1-x)(1-x^2)(1-x^3)\cdots$ for all powers of $x$. Multiplying this out will give us every multiplicative combination of $1, x, x^2, \dots$ possible as a result. Thinking in reverse, we can ask about how terms like $x^n$ may arise from this. Since $x^n$ must come from some multiplicative combinations of $1, x, x^2, \dots$, we know that $n$ must come from an additive combination of $1, 2, 3, \dots$ (since $x^a x^b = x^{a+b}$).

$x^5 = x^{1+4} = x^{2+3}$ $x^6 = x^{1+5} = x^{2+4} = x^{1+2+3}$ $x^7 = x^{1+6} = x^{2+5} = x^{3+4} = x^{1+2+4}$

A breakdown of $n$ into smaller parts added together is known as a partition. Here, we're dealing specifically with partitions into distinct parts. If we apply this reasoning to $(1-x)(1-x^2)(1-x^3)\cdots$ by keeping track of the signs, we will see a neat pattern: terms of the form $x^a$ will be negative, $x^{a+b}$ will be positive, $x^{a+b+c}$ will be negative, and the pattern continues. This means that "odd" partitions will have negative coefficients while "even" partitions have positive coefficients. It follows that the coefficients of all terms on the right will have this form.

$(\text{\# of even partitions of n} - \text{\# of odd partitions of n}) \cdot x^n$

Which means that all of the numbers which show up in $1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} + \cdots$ must have an imbalance of even and odd partitions into distinct parts; otherwise they will have a coefficient of $0$. 5 and 7 have one more even partition than odd ones, while 12 and 15 have one more odd partition than even ones.

Why is it that the number of even and odd partitions balance out for most numbers except the ones equal to $a(3a\pm 1)/2$? It has to do with how partitions can be found from other partitions. Consider 6, which partitions into 6, 5 + 1, 4 + 2, and 3 + 2 + 1. Starting from the first partition, 6, we can create a new partition by "shaving" one off the top of it to make 5 + 1. Likewise we can do this for the other two. To make this argument clearer, we can visualize partitions with dots on a hidden grid, known as a Ferrers diagram. Here are all the partitions of 6 represented by Ferrers diagrams.

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet & \bullet \end{array} \qquad \begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & & & & \end{array} \qquad \begin{array}{c}\bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & & \end{array} \qquad \begin{array}{c}\bullet & \bullet & \bullet \\ \bullet & \bullet & \\ \bullet & & \end{array}$

We can see that 6 has just as many odd partitions as it does even, so $x^6$ doesn't appear in the expansion. Since there are an equal number of even and odd partitions, it makes sense to ask if there's a one-to-one mapping between them. One possible scheme comes from a "shaving" method, where the largest parts of a partition are "shaved" by 1. This works, as moving from 6 to 5 + 1 changes the partition from odd to even. Likewise, moving from 4 + 2 to 3 + 2 + 1 changes an even partition into an odd one.

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet & \color{#D61F06}{\bullet} \end{array} \longleftrightarrow \begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet \\ \color{#D61F06}{\bullet} & & & & \end{array}$

$\begin{array}{c}\bullet & \bullet & \bullet & \color{#D61F06}{\bullet} \\ \bullet & \bullet & & \end{array} \longleftrightarrow \begin{array}{c}\bullet & \bullet & \bullet \\ \bullet & \bullet & \\ \color{#D61F06}{\bullet} & & \end{array}$

Under this scheme, 5 + 1 doesn't map to 4 + 2 because the shaving operation doesn't change the number of rows. However, 6 doesn't map to 3 + 2 + 1 either since the shaving operation can only add one new row in a Ferrers diagram at a time. Larger partitions such as 5 + 4 will have both parts shaved to yield 4 + 3 + 2.

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \color{#D61F06}{\bullet} \\ \bullet & \bullet & \bullet & \color{#D61F06}{\bullet} & \end{array} \longleftrightarrow \begin{array}{c}\bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \\ \color{#D61F06}{\bullet} & \color{#D61F06}{\bullet} & & \end{array}$

Since this scheme is supposed to be a one-to-one map between partitions, we can ask about doing this in reverse. The partition 5 + 3 + 1, for example, has no way of shaving off the top that works. 4 + 3 + 1 + 1 is disallowed since every part must be distinct, and 2 + 3 + 4 is disallowed since it doesn't change the oddness of the partition. Instead, 6 + 3 is the only partition which works under this mapping.

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & & \\ \color{#D61F06}{\bullet} & & & & \end{array} \longleftrightarrow \begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet & \color{#D61F06}{\bullet} \\ \bullet & \bullet & \bullet & & & \end{array}$

The key benefit to having a one-to-one mapping is that we can think of partitions as existing in pairs of even and odd partitions. If every odd partition of $n$ can be paired with an even partition of $n$, then the expansion of $(1-x)(1-x^2)(1-x^3)\cdots$ will not have an $x^n$ term. This means that the shave mapping doesn't work for some $n$.

There are some pathological partitions that don't work under this scheme.

$\begin{array}{c}\bullet & \bullet & \bullet \\ \bullet & \bullet & \end{array} \longleftrightarrow \times$ $\begin{array}{c}\bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \end{array} \longleftrightarrow \times$

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \\ \bullet & \bullet & \bullet & & \end{array} \longleftrightarrow \times$

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \bullet & \\ \bullet & \bullet & \bullet & \bullet & & \end{array} \longleftrightarrow \times$

If you were to count them up, you'll notice right away what the pattern is. Since these partitions do not map to anything, their terms in the expansion of $(1-x)(1-x^2)(1-x^3)\cdots$ won't fully cancel out to $0$. Let's generalize this pattern. These partitions are made up of squares of length $a$ and triangles with base length $a$ or $a-1$.

$\begin{array} {ccc} \bullet & \bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \bullet & \\ \bullet & \bullet & \bullet & \bullet & & \\ \newline = \\ \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet + \bullet & \bullet & \bullet \\ \bullet & \bullet & \\ \bullet & & \end{array}$

All the possible $n$ where this can happen is then just a sum of the number of dots in each shape.

$n = a^2 + \frac{a(a+1)}{2} \quad \text{and} \quad n = a^2 + \frac{(a-1)a}{2}$

We can conveniently combine both cases into one equation.

$n = a^2 + \frac{a(a \pm 1)}{2}$

$n = \frac{a(3a \pm 1)}{2}$

So the only terms that will show up in the expansion of $(1-x)(1-x^2)(1-x^3)\cdots$ will have an exponent with the form $\frac{a(3a \pm 1)}{2}$. Their sign depends on the "leftover" pathological partition, which is negative when the partition (a) is odd and positive when the partition (a) is even. Putting this all together gives us the pentagonal number theorem.

The pentagonal number theorem $\displaystyle\prod_{k=1}^\infty (1-x^k) = 1 + \displaystyle\sum_{a=1}^\infty (-1)^a x^{a(3a \pm 1)/2}$

Historically, the pentagonal number theorem was conjectured by Euler, but he failed to find a proof of it for several years. He did eventually find it, but to me his proof felt really unnatural and hard to follow. Instead, I presented a simpler proof by the mathemtician Fabian Franklin.