The pentagonal number theorem

Here's a strange fact:

k=1(1xk)=1xx2+x5+x7x12x15+x22+x26+=1+a=1(1)axa(3a±1)/2 \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 xnx^n will only appear when n=a(3a±1)2 n = \frac{a(3a \pm 1)}{2}, where aa is an integer greater than 0. This means that if we continued this expansion we would run across terms like x35,x40,x51...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 (1x)(1x2)(1x3) (1-x)(1-x^2)(1-x^3)\cdots for all powers of xx. Multiplying this out will give us every multiplicative combination of 1,x,x2,1, x, x^2, \dots possible as a result. Thinking in reverse, we can ask about how terms like xnx^n may arise from this. Since xnx^n must come from some multiplicative combinations of 1,x,x2,1, x, x^2, \dots, we know that nn must come from an additive combination of 1,2,3,1, 2, 3, \dots (since xaxb=xa+bx^a x^b = x^{a+b} ).

x5=x1+4=x2+3 x^5 = x^{1+4} = x^{2+3} x6=x1+5=x2+4=x1+2+3x^6 = x^{1+5} = x^{2+4} = x^{1+2+3} x7=x1+6=x2+5=x3+4=x1+2+4x^7 = x^{1+6} = x^{2+5} = x^{3+4} = x^{1+2+4}

A breakdown of nn 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 (1x)(1x2)(1x3) (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 xax^a will be negative, xa+bx^{a+b} will be positive, xa+b+cx^{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.

(# of even partitions of n# of odd partitions of n)xn (\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 1xx2+x5+x7x12x15+x22+x26+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 00. 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±1)/2a(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 x6x^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 nn can be paired with an even partition of nn, then the expansion of (1x)(1x2)(1x3) (1-x)(1-x^2)(1-x^3)\cdots will not have an xnx^n term. This means that the shave mapping doesn't work for some nn.

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 (1x)(1x2)(1x3) (1-x)(1-x^2)(1-x^3)\cdots won't fully cancel out to 00. Let's generalize this pattern. These partitions are made up of squares of length aa and triangles with base length aa or a1a-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 nn where this can happen is then just a sum of the number of dots in each shape.

n=a2+a(a+1)2andn=a2+(a1)a2 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=a2+a(a±1)2 n = a^2 + \frac{a(a \pm 1)}{2}

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

So the only terms that will show up in the expansion of (1x)(1x2)(1x3) (1-x)(1-x^2)(1-x^3)\cdots will have an exponent with the form a(3a±1)2 \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 k=1(1xk)=1+a=1(1)axa(3a±1)/2 \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

No vote yet
1 vote

  Easy Math Editor

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. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Yajat Shamji - 2 months, 1 week ago

Log in to reply

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

Levi Walker - 2 months, 1 week ago

Log in to reply

No problem!

I'll be eagerly waiting...

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

Yajat Shamji - 2 months, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...