# 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.

Note by Levi Walker
2 months, 1 week ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
• Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Really cool! @Levi Walker

You know you can try explaining Riemann's hypothesis in great detail.

I read the wiki on Brilliant and Wikipedia but they don't satisfy me...

- 2 months, 1 week ago

Thank you! I've actually been thinking of doing something like that. It's only a matter of time :D

- 2 months, 1 week ago

No problem!

I'll be eagerly waiting...

P.S. You're welcome for reminding you about thinking of doing something like the Riemann hypothesis.

- 2 months, 1 week ago