21.16.01 · number-theory / partitions-circle-method

The Partition Function, Generating Functions, and the Pentagonal Number Theorem

shipped3 tiersLean: none

Anchor (Master): Apostol 1976 *Introduction to Analytic Number Theory* Ch. 14 (Euler products, the pentagonal number theorem, Jacobi triple product, Ramanujan congruences stated); Andrews 1976 *The Theory of Partitions* Ch. 1-2, 10 (Franklin's involution, the Jacobi triple product, Rogers-Ramanujan); Hardy-Wright 2008 *An Introduction to the Theory of Numbers* 6e (Oxford) Ch. XIX; Euler 1748 *Introductio in analysin infinitorum* Ch. XVI (originator of the generating function and the pentagonal recurrence); Jacobi 1829 *Fundamenta Nova* (the triple product); Hardy-Ramanujan 1918 *Proc. London Math. Soc.* (2) 17 (the asymptotic $p(n) \sim e^{\pi\sqrt{2n/3}}/(4n\sqrt 3)$, prelude to the circle method)

Intuition Beginner

How many ways can you break a whole number into a sum of positive whole numbers, if the order of the pieces does not matter? The number $4$ can be written as $4$ , as $3 + 1$ , as $2 + 2$ , as $2 + 1 + 1$ , and as $1 + 1 + 1 + 1$ : five ways. Each of these is called a partition of $4$ , and the count of them is written $p (4) = 5$ . The function $p (n)$ that records this count for every $n$ is the partition function, and it grows astonishingly fast — $p (100)$ is already more than $190$ million.

Counting partitions one number at a time is hopeless by hand for large $n$ , so we pack every count into one bookkeeping device: an infinite product. Imagine a separate "stall" for each part size. The stall for the part $1$ offers you any number of copies of $1$ ; the stall for $2$ offers any number of copies of $2$ ; and so on. Multiplying out all the stalls and collecting the term for $n$ reproduces exactly the partitions of $n$ . This product is the generating function for $p (n)$ , and it turns a counting question into algebra.

The surprise of this unit is a near-magical cancellation. When you multiply out the closely related product where each stall offers a part at most once with a plus-or-minus sign, almost everything cancels, and what survives sits only at a thin sequence of special exponents — the pentagonal numbers $1, 2, 5, 7, 12, 15, \dots$ . This is Euler's pentagonal number theorem, and it hands you a fast recurrence that computes $p (n)$ from earlier values.

Visual Beginner

A partition is drawn as a Ferrers diagram: rows of dots, one row per part, longest at the top. The partition $4 = 2 + 1 + 1$ is three rows of lengths $2, 1, 1$ . Flipping the diagram across its diagonal — turning rows into columns — produces another partition, the conjugate, and this single picture proves several counting identities at once.

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$p (n)$	$1$	$1$	$2$	$3$	$5$	$7$	$11$	$15$	$22$	$30$	$42$

The pentagonal numbers on the right are the exponents $k (3 k - 1) /2$ as $k$ runs through $1, - 1, 2, - 2, 3, - 3, \dots$ , giving $1, 2, 5, 7, 12, 15, \dots$ . Euler's theorem says the product $(1 - q) (1 - q^{2}) (1 - q^{3}) \dots$ has non-zero coefficients only at these exponents, each equal to $+ 1$ or $- 1$ .

Worked example Beginner

Compute $p (5)$ in two ways: by listing, then by Euler's recurrence.

Step 1. List the partitions of $5$ . They are $5$ ; $4 + 1$ ; $3 + 2$ ; $3 + 1 + 1$ ; $2 + 2 + 1$ ; $2 + 1 + 1 + 1$ ; and $1 + 1 + 1 + 1 + 1$ . Counting gives seven, so $p (5) = 7$ .

Step 2. Now use Euler's recurrence, which reads $p (n) = p (n - 1) + p (n - 2) - p (n - 5) - p (n - 7) + p (n - 12) + \dots,$ where the shifts $1, 2, 5, 7, 12, \dots$ are the pentagonal numbers, the signs come in the repeating pattern plus, plus, minus, minus, and any term with a negative argument is dropped. We treat $p (0) = 1$ and $p (negative) = 0$ .

Step 3. Apply it at $n = 5$ . The available shifts are $1, 2, 5$ (since $7 > 5$ ): $p (5) = p (4) + p (3) - p (0) = 5 + 3 - 1 = 7$ . This matches the direct list.

Step 4. Push one step further. At $n = 6$ : $p (6) = p (5) + p (4) - p (1) = 7 + 5 - 1 = 11$ , again matching the table.

What this tells us: the recurrence computes a count that would otherwise require exhaustively listing partitions, using only a handful of earlier values and the sparse pentagonal shifts. The hard combinatorial object $p (n)$ is governed by a simple algebraic identity.

Check your understanding Beginner

Exercise (easy, multiple choice).

The generating function for the partition function is which infinite product?

A. $(1 - q) (1 - q^{2}) (1 - q^{3}) \dots$
B. $(1 - q)^{- 1} (1 - q^{2})^{- 1} (1 - q^{3})^{- 1} \dots$
C. $(1 + q) (1 + q^{2}) (1 + q^{3}) \dots$
D. $q + q^{2} + q^{3} + \dots$

Hint

Each part size $k$ may be used any number of times. The factor for part $k$ is the geometric series $1 + q^{k} + q^{2 k} + \dots$ , which equals $(1 - q^{k})^{- 1}$ .

Answer

B. Each part size $k$ contributes a factor $1 + q^{k} + q^{2 k} + \dots = (1 - q^{k})^{- 1}$ , recording the choice of how many copies of $k$ to use; multiplying these over all $k$ gives the product in option B, whose coefficient of $q^{n}$ is $p (n)$ . Option A is Euler's product $(1 - q) (1 - q^{2}) \dots$ , the reciprocal, whose expansion is the pentagonal-number sum. Option C generates partitions into distinct parts. Option D is not a partition generating function at all.

Formal definition Intermediate+

Throughout, $q$ is a formal variable, or a complex number with $∣ q ∣ < 1$ when convergence is needed; all infinite products below converge absolutely there.

Definition (partition). A partition of a positive integer $n$ is a non-increasing sequence of positive integers $λ_{1} \geq λ_{2} \geq \dots \geq λ_{r} \geq 1$ with $\sum_{i} λ_{i} = n$ . The $λ_{i}$ are the parts. The partition function $p (n)$ is the number of partitions of $n$ , with the conventions $p (0) = 1$ (the empty partition) and $p (n) = 0$ for $n < 0$ .

Definition (generating function). The generating function of $p$ is the formal power series $\sum_{n \geq 0} p (n) q^{n}$ . Following Euler ^{[Euler 1748]}, it has the product representation $$ \sum_{n=0}^{\infty} p(n) q^n ;=; \prod_{k=1}^{\infty} \frac{1}{1 - q^k} ;=; \prod_{k=1}^{\infty}\big(1 + q^k + q^{2k} + q^{3k} + \cdots\big), $$ where the $k$ -th factor records the number of copies of the part $k$ . Selecting the term $q^{m_{k} k}$ from the $k$ -th factor and multiplying yields $q^{\sum_{k} m_{k} k}$ , so the coefficient of $q^{n}$ counts the solutions of $\sum_{k} m_{k} k = n$ in non-negative integers $m_{k}$ — exactly the partitions of $n$ .

Definition (restricted partitions). For a set $S \subseteq Z_{\geq 1}$ , the generating function for partitions with all parts in $S$ is $\prod_{k \in S} (1 - q^{k})^{- 1}$ . For partitions into distinct parts (each used at most once), the generating function is $\prod_{k \geq 1} (1 + q^{k})$ . We write $p_{odd} (n)$ for the number of partitions of $n$ into odd parts and $p_{dist} (n)$ for the number into distinct parts.

Definition (pentagonal numbers). The generalised pentagonal numbers are the integers $g_{k} = \frac{k ( 3 k - 1 )}{2}$ for $k \in Z$ ; as $k$ runs over $0, 1, - 1, 2, - 2, 3, - 3, \dots$ they take the values $0, 1, 2, 5, 7, 12, 15, 22, 26, \dots$ . The notation $(q; q)_{\infty} := \prod_{k \geq 1} (1 - q^{k})$ is the Euler function, registered in _meta/NOTATION.md together with $g_{k}$ .

Counterexamples to common slips Intermediate+

" $p (n)$ counts ordered sums (compositions)." It does not. The compositions of $4$ — ordered sums — number $2^{3} = 8$ , whereas $p (4) = 5$ . Partitions identify $3 + 1$ with $1 + 3$ .
"Distinct parts is the same as odd parts as partitions." The two counts are equal (Euler), but the partitions themselves differ: for $n = 5$ the distinct-part partitions ${5, 4 + 1, 3 + 2}$ are not the odd-part partitions ${5, 3 + 1 + 1, 1^{5}}$ . Glaisher's bijection is what matches them.
"The pentagonal number theorem has both signs at every pentagonal exponent." Each generalised pentagonal number $g_{k}$ arises from exactly one $k \in Z$ (the map $k \mapsto k (3 k - 1) /2$ is injective on $Z$ ), so the coefficient at $q^{g_{k}}$ is the single sign $(- 1)^{k}$ , not a sum of two contributions.
" $(q; q)_{\infty}^{- 1}$ converges for all $q$ ." The product converges only for $∣ q ∣ < 1$ ; on $∣ q ∣ = 1$ it has the unit circle as a natural boundary, which is the analytic obstruction the circle method must navigate when extracting the asymptotics of $p (n)$ .

Key theorem with proof Intermediate+

The signature theorem is Euler's pentagonal number theorem. Its force is that the reciprocal of the partition generating function — a product over all $k$ — collapses to a sparse signed sum supported on the pentagonal numbers, and this yields a linear recurrence computing $p (n)$ .

Theorem (Euler's pentagonal number theorem). As an identity of formal power series, $$ \prod_{k=1}^{\infty}(1 - q^k) ;=; \sum_{k=-\infty}^{\infty} (-1)^k q^{k(3k-1)/2} ;=; 1 + \sum_{k=1}^{\infty}(-1)^k\Big(q^{k(3k-1)/2} + q^{k(3k+1)/2}\Big). $$

Proof (Franklin's involution). Expanding $\prod_{k \geq 1} (1 - q^{k})$ and collecting the coefficient of $q^{n}$ , a partition of $n$ into distinct parts contributes $(- 1)^{(number of parts)}$ . Hence the coefficient of $q^{n}$ equals $D_{e} (n) - D_{o} (n)$ , where $D_{e} (n)$ and $D_{o} (n)$ count partitions of $n$ into an even, respectively odd, number of distinct parts. The theorem asserts $D_{e} (n) - D_{o} (n) = 0$ unless $n = g_{k} = k (3 k \pm 1) /2$ , in which case it is $(- 1)^{k}$ .

To prove this we construct a sign-reversing involution on the set of partitions of $n$ into distinct parts, pairing each even-length partition with an odd-length one so that the two cancel. For a partition $λ = (λ_{1} > λ_{2} > \dots > λ_{r})$ into distinct parts, let $s (λ)$ be the smallest part $λ_{r}$ , and let $ℓ (λ)$ be the length of the top staircase: the largest $j$ such that $λ_{1}, λ_{2}, \dots, λ_{j}$ are consecutive integers $λ_{1}, λ_{1} - 1, \dots, λ_{1} - j + 1$ .

Define two moves on the Ferrers diagram. Move A removes the smallest part $s$ and adds $1$ to each of the top $s$ parts (transferring the bottom row onto the staircase); it applies when $s \leq ℓ$ . Move B subtracts $1$ from each of the top $ℓ$ parts and creates a new smallest part of size $ℓ$ ; it applies when $ℓ < s$ . Each move changes the number of parts by exactly one, so it reverses the sign $(- 1)^{r}$ , and the two moves are mutually inverse, giving an involution wherever both are defined.

The involution fails to be defined exactly when the two regions overlap or collide. This happens precisely when the staircase reaches down to the smallest part, i.e. when $λ = (2 k - 1, 2 k - 2, \dots, k)$ with $s = ℓ = k$ (giving $n = k + (k + 1) + \dots + (2 k - 1) = k (3 k - 1) /2$ ), or when $λ = (2 k, 2 k - 1, \dots, k + 1)$ with $s = k + 1, ℓ = k$ and the moved cell would re-enter the staircase (giving $n = k (3 k + 1) /2$ ). In each exceptional case there is a single unpaired partition of length $k$ , contributing $(- 1)^{k}$ at $q^{g_{k}}$ . All other partitions cancel in pairs. Therefore $D_{e} (n) - D_{o} (n) = (- 1)^{k}$ if $n = k (3 k \pm 1) /2$ and $0$ otherwise ^{[Andrews 1976]}. $□$

Corollary (the recurrence for $p (n)$ ). Since $(\sum_{n} p (n) q^{n}) (\prod_{k} (1 - q^{k})) = 1$ , equating coefficients of $q^{n}$ for $n \geq 1$ and substituting the pentagonal expansion gives $$ p(n) ;=; \sum_{k \geq 1} (-1)^{k+1}\Big( p\big(n - g_k\big) + p\big(n - g_{-k}\big) \Big) ;=; p(n-1) + p(n-2) - p(n-5) - p(n-7) + \cdots, $$ the sum terminating once $g_{k} > n$ . This computes $p (n)$ in $O (n)$ additions per value.

Bridge. The pentagonal number theorem builds toward the analytic theory of the partition generating function: the same product $\prod (1 - q^{k}) = q^{- 1/24} η (τ)$ (with $q = e^{2 π i τ}$ ) is the Dedekind eta function, and the recurrence is the elementary shadow of its modularity, which appears again in 21.04.04 where theta and eta products are read as modular forms. The foundational reason the sparse identity exists is the Jacobi triple product, of which the pentagonal theorem is the specialisation $z = - 1$ , $q \to q^{3/2}$ ; this is exactly the statement that a doubly-infinite theta sum factors as a product, and it generalises the elementary sieve of distinct-versus-odd parts into the full machinery of theta functions. Putting these together, the convolution identity $(\sum p (n) q^{n}) (\sum (- 1)^{k} q^{g_{k}}) = 1$ is a Dirichlet-style inversion in the ring of formal power series, dual to the Möbius inversion of 21.11.01: there summing over divisors was inverted by $μ$ ; here summing over partitions is inverted by the pentagonal signs. The bridge is that a hard counting function is pinned down by a sparse algebraic reciprocal, and that principle reappears in the circle-method asymptotics of Hardy and Ramanujan.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove Euler's theorem that the number of partitions of $n$ into distinct parts equals the number into odd parts, by manipulating generating functions.

Hint

Write $\prod (1 + q^{k})$ and use $1 + q^{k} = (1 - q^{2 k}) / (1 - q^{k})$ . Telescope the resulting product.

Answer

The distinct-parts generating function is $\prod_{k \geq 1} (1 + q^{k})$ . Using $1 + q^{k} = \frac{1 - q ^{2 k}}{1 - q ^{k}}$ , $$ \prod_{k \geq 1}(1 + q^k) = \prod_{k \geq 1}\frac{1 - q^{2k}}{1 - q^k} = \frac{\prod_{k \geq 1}(1 - q^{2k})}{\prod_{k \geq 1}(1 - q^k)}. $$ The numerator is the product over even indices. In the denominator split the indices into even and odd: $\prod_{k} (1 - q^{k}) = \prod_{k even} (1 - q^{k}) \prod_{k odd} (1 - q^{k})$ . The even factors cancel against the numerator, leaving $\prod_{k odd} (1 - q^{k})^{- 1}$ , which is the generating function for partitions into odd parts. Equality of generating functions gives $p_{dist} (n) = p_{odd} (n)$ for all $n$ . Rubric: full credit for the telescoping cancellation and the identification of $\prod_{k odd} (1 - q^{k})^{- 1}$ as the odd-part generating function.

Exercise 4 (medium, symbolic).

State and prove Glaisher's theorem: the number of partitions of $n$ in which no part is divisible by $d$ equals the number in which no part is repeated $d$ or more times.

Hint

Generalise Exercise 3: the first count has generating function $\prod_{d ∤ k} (1 - q^{k})^{- 1}$ , the second $\prod_{k \geq 1} (1 + q^{k} + \dots + q^{(d - 1) k})$ . Use $1 + q^{k} + \dots + q^{(d - 1) k} = (1 - q^{d k}) / (1 - q^{k})$ .

Answer

The partitions of $n$ in which each part appears at most $d - 1$ times have generating function $\prod_{k \geq 1} (1 + q^{k} + \dots + q^{(d - 1) k}) = \prod_{k \geq 1} \frac{1 - q ^{d k}}{1 - q ^{k}}$ . The numerator $\prod_{k} (1 - q^{d k})$ runs over multiples of $d$ ; cancelling these against the corresponding factors of $\prod_{k} (1 - q^{k})^{- 1}$ in the denominator leaves $\prod_{d ∤ k} (1 - q^{k})^{- 1}$ , the generating function for partitions with no part divisible by $d$ . Hence the two counts coincide for every $n$ . The case $d = 2$ recovers Euler's distinct-equals-odd theorem (Exercise 3). Rubric: full credit for the finite-geometric-series factorisation and the cancellation over multiples of $d$ .

Exercise 6 (hard, symbolic).

Derive Euler's pentagonal number theorem from the Jacobi triple product by setting $z = - 1$ and $q \to q^{3/2}$ (more precisely, replacing $q^{2} \to q^{3}$ and $z \to - q^{- 1/2}$ in a suitable normalisation). Show the exponents become $k (3 k - 1) /2$ .

Hint

In $\sum_{k} q^{k^{2}} z^{k}$ , choose the substitution so that $q^{k^{2}} z^{k}$ becomes $(- 1)^{k} q^{k (3 k - 1) /2}$ . Match exponents: you need $k^{2} \cdot (new q -exponent) + k \cdot (shift) = k (3 k - 1) /2$ .

Answer

Write the triple product as $\sum_{k} Q^{k^{2}} z^{k} = \prod_{m} (1 - Q^{2 m}) (1 + Q^{2 m - 1} z) (1 + Q^{2 m - 1} z^{- 1})$ . Put $Q = q^{3/2}$ and $z = - q^{- 1/2}$ . Then $Q^{k^{2}} z^{k} = q^{3 k^{2} /2} (- 1)^{k} q^{- k /2} = (- 1)^{k} q^{(3 k^{2} - k) /2} = (- 1)^{k} q^{k (3 k - 1) /2}$ , so the right side becomes $\sum_{k} (- 1)^{k} q^{k (3 k - 1) /2}$ , the pentagonal sum. For the product side, $1 - Q^{2 m} = 1 - q^{3 m}$ ; $1 + Q^{2 m - 1} z = 1 - q^{3 (2 m - 1) /2 - 1/2} = 1 - q^{3 m - 2}$ ; and $1 + Q^{2 m - 1} z^{- 1} = 1 - q^{3 m - 1}$ . The three families of exponents $3 m, 3 m - 1, 3 m - 2$ over $m \geq 1$ enumerate every positive integer exactly once, so the product is $\prod_{n \geq 1} (1 - q^{n})$ . Equating the two sides yields $\prod_{n \geq 1} (1 - q^{n}) = \sum_{k} (- 1)^{k} q^{k (3 k - 1) /2}$ . Rubric: full credit for the exponent matching and the observation that ${3 m, 3 m - 1, 3 m - 2}$ partitions $Z_{\geq 1}$ .

Exercise 7 (hard, symbolic).

Prove that Franklin's two moves (A and B from the Key theorem) are mutually inverse wherever both are defined, and identify exactly which partitions admit neither move.

Hint

Track the smallest part $s$ and staircase length $ℓ$ before and after each move. A partition admits neither move when the smallest part is the bottom of the staircase and removing/adding would not respect distinctness.

Answer

Move A (defined when $s \leq ℓ$ ) removes the smallest part $s$ and increments the top $s$ parts by $1$ ; the result has $r - 1$ parts, its new staircase length is $\geq s$ and its new smallest part exceeds the old staircase contribution, so Move B is now defined and undoes A. Move B (defined when $ℓ < s$ ) decrements the top $ℓ$ parts and appends a new smallest part $ℓ$ ; the result has $r + 1$ parts with smallest part $ℓ \leq$ its staircase length, so Move A is defined and undoes B. Hence A and B are inverse bijections on the partitions where exactly one applies, and they reverse parity of $r$ . Neither move applies precisely when the staircase and the smallest part coincide and a move would violate distinctness: $λ = (2 k - 1, \dots, k)$ (here $s = ℓ = k$ and Move A would create a repeated part) giving $n = k (3 k - 1) /2$ , and $λ = (2 k, \dots, k + 1)$ (here $ℓ = k$ , $s = k + 1$ , and Move B's appended part would collide with the staircase) giving $n = k (3 k + 1) /2$ . These fixed points carry the surviving signs $(- 1)^{k}$ . Rubric: full credit for verifying both compositions are the identity and correctly characterising the two exceptional staircase shapes.

Exercise 8 (hard, short-answer).

Ramanujan's congruence states $p (5 n + 4) \equiv 0 (mod 5)$ for all $n \geq 0$ . Verify it for $n = 0$ and $n = 1$ , and explain in one paragraph why such congruences are statements about modular forms rather than elementary recurrences.

Hint

Check $p (4)$ and $p (9)$ . For the explanation, recall that $\sum p (n) q^{n} = q^{1/24} / η (τ)$ and that arithmetic progressions of coefficients of modular forms are controlled by Hecke operators and the structure of the relevant spaces.

Answer

For $n = 0$ : $p (4) = 5 \equiv 0 (mod 5)$ . For $n = 1$ : $p (9) = 30 \equiv 0 (mod 5)$ . Both satisfy the congruence. These divisibilities are not visible from Euler's pentagonal recurrence, which mixes residues unpredictably; they are arithmetic properties of the coefficients of $\sum p (n) q^{n} = q^{1/24} / η (τ)$ , where $η$ is the Dedekind eta function, a modular form of weight $1/2$ . Ramanujan's proof and its successors (Watson, Atkin, and the modern theory of Atkin-Lehner and Hecke operators) extract the subprogression $\sum p (5 n + 4) q^{n}$ as the coefficient sequence of an explicit modular form whose level and weight force divisibility by $5$ ; the analogous statements modulo $7$ and $11$ come from $p (7 n + 5) \equiv 0$ and $p (11 n + 6) \equiv 0$ . Rubric: full credit for both numerical checks and a correct identification of the modular-forms (eta-function / Hecke) origin of the congruences, as opposed to an elementary recurrence.

Advanced results Master

The elementary recurrence is the entry to a deep analytic and arithmetic theory. We collect the structural results: the Jacobi triple product as the parent identity, the modular interpretation through the Dedekind eta function, the Hardy-Ramanujan asymptotic, the Ramanujan congruences, and the Rogers-Ramanujan identities.

Theorem 1 (Jacobi triple product). For formal variables with $∣ q ∣ < 1$ and $z \neq = 0$ , $$ \prod_{m=1}^{\infty}(1 - q^{2m})(1 + q^{2m-1}z)(1 + q^{2m-1}z^{-1}) ;=; \sum_{k=-\infty}^{\infty} q^{k^2} z^k. $$ Specialisation $z = 1$ gives the theta series $θ (τ) = \sum_{k} q^{k^{2}}$ of 21.04.04; the substitution $z = - q^{- 1/2}$ , $q \mapsto q^{3/2}$ of Exercise 6 gives Euler's pentagonal number theorem; $z = - 1$ gives $\prod (1 - q^{2 m}) (1 - q^{2 m - 1})^{2} = \sum_{k} (- 1)^{k} q^{k^{2}}$ . The triple product is the master identity from which the generating-function identities of this chapter descend ^{[Andrews 1976]}.

Theorem 2 (modular interpretation; Dedekind eta). Setting $q = e^{2 π i τ}$ with $τ \in H$ , the Euler function is $\prod_{k \geq 1} (1 - q^{k}) = q^{- 1/24} η (τ)$ , where $η (τ) = e^{π i τ /12} \prod_{k \geq 1} (1 - e^{2 π ik τ})$ is the Dedekind eta function, a modular form of weight $1/2$ transforming by $η (- 1/ τ) = - i τ η (τ)$ and $η (τ + 1) = e^{π i /12} η (τ)$ . Consequently the partition generating function is $\sum_{n} p (n) q^{n} = q^{1/24} / η (τ)$ , a weakly holomorphic modular form of weight $- 1/2$ . The transformation law under $τ \mapsto - 1/ τ$ , dual to the theta inversion of 21.04.04, is precisely what powers the circle-method asymptotics: the dominant singularity of $1/ η$ as $q \to 1$ controls the growth of $p (n)$ .

Theorem 3 (Hardy-Ramanujan asymptotic). The partition function satisfies ^{[Hardy-Ramanujan 1918]} $$ p(n) ;\sim; \frac{1}{4n\sqrt 3}, \exp!\Big(\pi \sqrt{\tfrac{2n}{3}}\Big) \qquad (n \to \infty). $$ The proof is the prototype of the circle method: write $p (n) = \frac{1}{2 π i} \oint \frac{F ( q )}{q ^{n + 1}} d q$ with $F (q) = \prod (1 - q^{k})^{- 1}$ , deform the contour to approach the unit circle, and sum the contributions of the rational points $e^{2 π ia / c}$ , where the modular transformation of $η$ gives the local behaviour. Rademacher 1937 refined the asymptotic to a convergent exact series $p (n) = \frac{1}{π 2} \sum_{c = 1}^{\infty} A_{c} (n) c \frac{d}{d n} (\frac{s i n h ( \frac{π}{c} \frac{2}{3} ( n - \frac{1}{24} ) )}{n - 1/24})$ , with $A_{c} (n)$ a Kloosterman-type sum.

Theorem 4 (Ramanujan congruences). For all $n \geq 0$ , $$ p(5n + 4) \equiv 0 \pmod 5, \qquad p(7n + 5) \equiv 0 \pmod 7, \qquad p(11n + 6) \equiv 0 \pmod{11}. $$ These are coefficient congruences for the modular form $q^{1/24} / η (τ)$ ; the $5$ -case follows from the identity $\sum_{n \geq 0} p (5 n + 4) q^{n} = 5 \frac{( q ^{5} ; q ^{5} ) _{\infty}^{5}}{( q ; q ) _{\infty}^{6}}$ , which exhibits the factor $5$ explicitly. Ramanujan's further conjectures on powers of $5, 7, 11$ were established by Watson and Atkin; Ono 2000 and Ahlgren-Ono proved that for every prime $m \geq 5$ there exist infinitely many congruences $p (A n + B) \equiv 0 (mod m)$ , while Ahlgren-Boylan showed $5, 7, 11$ are the only primes admitting a congruence of the simplest Ramanujan shape.

Theorem 5 (Rogers-Ramanujan identities). The two identities $$ \sum_{k=0}^{\infty}\frac{q^{k^2}}{(q;q)k} = \prod{m \geq 0}\frac{1}{(1 - q^{5m+1})(1 - q^{5m+4})}, \quad \sum_{k=0}^{\infty}\frac{q^{k^2 + k}}{(q;q)k} = \prod{m \geq 0}\frac{1}{(1 - q^{5m+2})(1 - q^{5m+3})}, $$ where $(q; q)_{k} = \prod_{j = 1}^{k} (1 - q^{j})$ , equate a sum side (partitions with parts differing by at least $2$ ) with a product side (partitions into parts $\equiv \pm 1$ , resp. $\pm 2$ , modulo $5$ ). They lie beyond Euler's elementary methods and connect partition theory to the Andrews-Gordon hierarchy, affine Lie algebras (the Lepowsky-Wilson vertex-operator proof), and statistical mechanics (Baxter's hard-hexagon model).

Synthesis. Putting these together, the pentagonal number theorem is the foundational reason the elementary and analytic theories of partitions are one subject: the sparse signed reciprocal $\prod (1 - q^{k})$ is exactly the Euler function $q^{- 1/24} η (τ)$ , so the combinatorial recurrence and the circle-method asymptotic are two faces of the modularity of $η$ . The central insight is that a counting function with no closed form is nonetheless controlled at every scale — exactly, by the recurrence; asymptotically, by Hardy-Ramanujan; arithmetically, by the Ramanujan congruences — because its generating function is a modular form. This generalises the elementary distinct-equals-odd sieve into the Jacobi triple product, which is dual to the theta series of 21.04.04 and from which both the pentagonal identity and the sum-of-squares formulas descend by specialising the variable $z$ . Putting these together, the convolution inversion $(\sum p (n) q^{n}) (\sum (- 1)^{k} q^{g_{k}}) = 1$ is the partition-theoretic analogue of Möbius inversion in 21.11.01, and the bridge is that modularity, not elementary combinatorics, is the organising structure: the circle method, the congruences, and Rogers-Ramanujan all read off properties of $1/ η$ that the pentagonal theorem first made visible.

Full proof set Master

Proposition 1 (generating function identity). In $Z [[q]]$ , $\sum_{n \geq 0} p (n) q^{n} = \prod_{k \geq 1} (1 - q^{k})^{- 1}$ .

Proof. For each $k$ , $(1 - q^{k})^{- 1} = \sum_{m_{k} \geq 0} q^{m_{k} k}$ as a formal power series. The partial product $\prod_{k = 1}^{K} (1 - q^{k})^{- 1}$ is a well-defined element of $Z [[q]]$ whose coefficient of $q^{n}$ counts solutions of $\sum_{k = 1}^{K} m_{k} k = n$ in non-negative integers — partitions of $n$ into parts $\leq K$ . For fixed $n$ , no partition of $n$ uses a part exceeding $n$ , so for $K \geq n$ the coefficient of $q^{n}$ stabilises at $p (n)$ . Hence the infinite product converges in the $(q)$ -adic topology of $Z [[q]]$ to a series whose $q^{n}$ -coefficient is $p (n)$ . $□$

Proposition 2 (the recurrence is exact and finite). For $n \geq 1$ , $\sum_{k \neq = 0} (- 1)^{k} p (n - g_{k}) + p (n) = 0$ , i.e. $p (n) = \sum_{k \geq 1} (- 1)^{k + 1} (p (n - g_{k}) + p (n - g_{- k}))$ , a sum of $O (n)$ terms.

Proof. Multiply the identities $\sum_{n} p (n) q^{n} = \prod_{k} (1 - q^{k})^{- 1}$ and $\prod_{k} (1 - q^{k}) = \sum_{k \in Z} (- 1)^{k} q^{g_{k}}$ (Proposition 1 and the pentagonal theorem). Their product is $1$ , so $$ \Big(\sum_{n \geq 0} p(n) q^n\Big)\Big(\sum_{k \in \mathbb{Z}}(-1)^k q^{g_k}\Big) = 1. $$ The coefficient of $q^{n}$ on the left is $\sum_{k \in Z} (- 1)^{k} p (n - g_{k})$ . For $n = 0$ this is $p (0) = 1$ ; for $n \geq 1$ it must equal $0$ . Isolating the $k = 0$ term ( $g_{0} = 0$ , sign $+ 1$ ) gives $p (n) + \sum_{k \neq = 0} (- 1)^{k} p (n - g_{k}) = 0$ , i.e. the stated recurrence. The number of non-zero terms is the number of $k$ with $g_{k} \leq n$ , which is $O (n)$ since $g_{k} \sim 3 k^{2} /2$ . $□$

Proposition 3 (Jacobi triple product implies the pentagonal theorem). The substitution $q \mapsto q^{3/2}$ , $z \mapsto - q^{- 1/2}$ in the triple product yields $\prod_{n \geq 1} (1 - q^{n}) = \sum_{k \in Z} (- 1)^{k} q^{k (3 k - 1) /2}$ .

Proof. In $\prod_{m} (1 - Q^{2 m}) (1 + Q^{2 m - 1} z) (1 + Q^{2 m - 1} z^{- 1}) = \sum_{k} Q^{k^{2}} z^{k}$ , set $Q = q^{3/2}$ , $z = - q^{- 1/2}$ . The general term on the right is $Q^{k^{2}} z^{k} = q^{3 k^{2} /2} (- 1)^{k} q^{- k /2} = (- 1)^{k} q^{k (3 k - 1) /2}$ . On the left: $1 - Q^{2 m} = 1 - q^{3 m}$ ; $1 + Q^{2 m - 1} z = 1 - q^{(3 (2 m - 1) - 1) /2} = 1 - q^{3 m - 2}$ ; $1 + Q^{2 m - 1} z^{- 1} = 1 - q^{(3 (2 m - 1) + 1) /2} = 1 - q^{3 m - 1}$ . As $m$ ranges over $Z_{\geq 1}$ , the exponents ${3 m - 2, 3 m - 1, 3 m}$ enumerate $Z_{\geq 1}$ without repetition, so the product is $\prod_{n \geq 1} (1 - q^{n})$ . Equality of the two sides is the pentagonal number theorem. $□$

Proposition 4 (distinct-equals-odd and Glaisher, generating-function form). For each $d \geq 2$ , $\prod_{k \geq 1} (1 + q^{k} + \dots + q^{(d - 1) k}) = \prod_{d ∤ k} (1 - q^{k})^{- 1}$ .

Proof. The finite geometric sum gives $1 + q^{k} + \dots + q^{(d - 1) k} = (1 - q^{d k}) / (1 - q^{k})$ , so the left side is $\prod_{k} (1 - q^{d k}) / \prod_{k} (1 - q^{k})$ . Write $\prod_{k} (1 - q^{k}) = \prod_{d ∣ k} (1 - q^{k}) \cdot \prod_{d ∤ k} (1 - q^{k})$ and note $\prod_{d ∣ k} (1 - q^{k}) = \prod_{j} (1 - q^{d j}) = \prod_{k} (1 - q^{d k})$ . The numerator cancels the $\prod_{d ∣ k}$ factor of the denominator, leaving $\prod_{d ∤ k} (1 - q^{k})^{- 1}$ , the generating function for partitions with no part divisible by $d$ . The left side generates partitions with each part repeated at most $d - 1$ times, so the two counts agree. The case $d = 2$ is Euler's distinct-equals-odd theorem. $□$

Connections Master

The pentagonal recurrence $(\sum p (n) q^{n}) (\sum (- 1)^{k} q^{g_{k}}) = 1$ is a convolution inversion in the ring of formal power series, the partition-theoretic analogue of the Möbius inversion of 21.11.01: there the unit function $1$ is inverted by $μ$ under Dirichlet convolution; here the partition generating function is inverted by the pentagonal signs under Cauchy convolution. Both are instances of inverting a series with constant term $1$ .
The Jacobi triple product specialises at $z = 1$ to the theta series $θ (τ) = \sum_{k} q^{k^{2}}$ of 21.04.04; the pentagonal product and the sum-of-squares formulas are sibling specialisations of the same identity, and the modularity of $η$ used for partition asymptotics is dual to the theta inversion proved there by Poisson summation.
The convergence and natural-boundary behaviour of $\prod (1 - q^{k})^{- 1}$ on $∣ q ∣ < 1$ rests on the absolute-convergence criteria of 02.03.03; the $(q)$ -adic stabilisation argument of Proposition 1 and the circle-method contour deformation both depend on controlling the infinite product near the unit circle, where the series of 02.03.03 governs the tail estimates.
The generating-function bookkeeping that turns a part of size $k$ into a geometric factor $(1 - q^{k})^{- 1}$ is the same Euler-product mechanism that converts multiplicativity into $\prod_{p}$ factors in 21.04.04; partitions are the additive analogue of the multiplicative Euler product, with addition of parts replacing multiplication of prime powers.

Historical & philosophical context Master

The systematic theory of partitions begins with Euler's 1748 Introductio ^{[Euler 1748]}, where the generating-function product $\prod (1 - x^{n})^{- 1}$ first appears and where Euler states the pentagonal number theorem. Euler discovered the theorem empirically — multiplying out $\prod (1 - x^{n})$ to high order and noticing that the surviving terms sat only at the pentagonal exponents — and corresponded about it with Goldbach for years before producing a proof around 1750. The combinatorial proof by sign-reversing involution was supplied much later by Fabian Franklin in 1881 (Comptes Rendus 92), giving the bijective argument reproduced above and making the cancellation transparent rather than analytic.

Jacobi's 1829 Fundamenta Nova ^{[Jacobi 1829]} subsumed Euler's identity into the triple product, situating partition identities within the theory of elliptic and theta functions and revealing the pentagonal theorem as one specialisation among many. The analytic high point came with Hardy and Ramanujan's 1918 paper ^{[Hardy-Ramanujan 1918]}, which determined the asymptotic growth of $p (n)$ by the circle method — the contour-integral technique that extracts coefficient asymptotics from the singularities of a modular generating function — and which Rademacher later sharpened into a convergent exact formula. Ramanujan's congruences modulo $5, 7, 11$ , announced in 1919, opened the arithmetic theory of $p (n)$ , completed in the modern era by Atkin, Watson, and the modular-forms methods of Ono and Ahlgren that produced congruences for every prime modulus $m \geq 5$ .

Bibliography Master

@book{euler1748introductio,
  author    = {Euler, Leonhard},
  title     = {Introductio in analysin infinitorum},
  volume    = {1},
  publisher = {Marcum-Michaelem Bousquet},
  address   = {Lausanne},
  year      = {1748},
  note      = {Chapter XVI: De partitione numerorum}
}

@article{franklin1881pentagonal,
  author  = {Franklin, Fabian},
  title   = {Sur le d\'{e}veloppement du produit infini $(1-x)(1-x^2)(1-x^3)\cdots$},
  journal = {Comptes Rendus de l'Acad\'{e}mie des Sciences (Paris)},
  volume  = {92},
  pages   = {448--450},
  year    = {1881}
}

@book{jacobi1829fundamenta,
  author    = {Jacobi, Carl Gustav Jacob},
  title     = {Fundamenta Nova Theoriae Functionum Ellipticarum},
  publisher = {Borntr\"{a}ger},
  address   = {K\"{o}nigsberg},
  year      = {1829}
}

@article{hardyramanujan1918,
  author  = {Hardy, G. H. and Ramanujan, S.},
  title   = {Asymptotic formulae in combinatory analysis},
  journal = {Proceedings of the London Mathematical Society (2)},
  volume  = {17},
  pages   = {75--115},
  year    = {1918}
}

@book{andrews1976partitions,
  author    = {Andrews, George E.},
  title     = {The Theory of Partitions},
  series    = {Encyclopedia of Mathematics and its Applications},
  volume    = {2},
  publisher = {Addison-Wesley},
  year      = {1976}
}

@article{rademacher1937convergent,
  author  = {Rademacher, Hans},
  title   = {On the partition function $p(n)$},
  journal = {Proceedings of the London Mathematical Society (2)},
  volume  = {43},
  pages   = {241--254},
  year    = {1937}
}

@article{ahlgrenono2001congruences,
  author  = {Ahlgren, Scott and Ono, Ken},
  title   = {Congruence properties for the partition function},
  journal = {Proceedings of the National Academy of Sciences},
  volume  = {98},
  number  = {23},
  pages   = {12882--12884},
  year    = {2001}
}

Prerequisites

21.11.01
02.03.03

Tier anchors

beginner: Andrews-Eriksson 2004 *Integer Partitions* (Cambridge) Ch. 1-5 (partitions counted by hand, Ferrers diagrams, the generating-function bookkeeping); 3Blue1Brown / Mathologer 'The hardest 'What comes next?' (Euler's pentagonal numbers)' for the recurrence visualised
intermediate: Apostol 1976 *Introduction to Analytic Number Theory* (Springer UTM) Ch. 14 (partition function, generating functions, Euler's pentagonal number theorem, the recurrence for $p(n)$); Andrews 1976 *The Theory of Partitions* (Addison-Wesley, Encyclopedia of Mathematics 2) Ch. 1-2
master: Apostol 1976 *Introduction to Analytic Number Theory* Ch. 14 (Euler products, the pentagonal number theorem, Jacobi triple product, Ramanujan congruences stated); Andrews 1976 *The Theory of Partitions* Ch. 1-2, 10 (Franklin's involution, the Jacobi triple product, Rogers-Ramanujan); Hardy-Wright 2008 *An Introduction to the Theory of Numbers* 6e (Oxford) Ch. XIX; Euler 1748 *Introductio in analysin infinitorum* Ch. XVI (originator of the generating function and the pentagonal recurrence); Jacobi 1829 *Fundamenta Nova* (the triple product); Hardy-Ramanujan 1918 *Proc. London Math. Soc.* (2) 17 (the asymptotic $p(n) \sim e^{\pi\sqrt{2n/3}}/(4n\sqrt 3)$, prelude to the circle method)

References

Apostol, T. M. — Introduction to Analytic Number Theory · Springer Undergraduate Texts in Mathematics (1976). Chapter 14 develops the partition function $p(n)$, the generating function $\sum p(n) q^n = \prod (1 - q^n)^{-1}$, restricted-partition generating functions (distinct parts, odd parts, parts bounded below), Euler's pentagonal number theorem $\prod (1 - q^n) = \sum_k (-1)^k q^{k(3k-1)/2}$, the resulting recurrence for $p(n)$, the Jacobi triple product identity, and the statement of Ramanujan's congruences $p(5n+4) \equiv 0 \pmod 5$, $p(7n+5) \equiv 0 \pmod 7$, $p(11n+6) \equiv 0 \pmod{11}$.
Andrews, G. E. — The Theory of Partitions · Addison-Wesley, Encyclopedia of Mathematics and its Applications, Vol. 2 (1976; reissued Cambridge 1998). The canonical monograph: Ferrers diagrams and conjugation, generating functions for restricted partitions, Euler's distinct-equals-odd theorem and Glaisher's generalisation, Franklin's combinatorial (involution) proof of the pentagonal number theorem, the Jacobi triple product, the Rogers-Ramanujan identities, and the arithmetic of $p(n)$.
Euler, L. — Introductio in analysin infinitorum · Lausanne (1748), Vol. 1, Ch. XVI 'De partitione numerorum'. The origin of the generating-function method for partitions, the product $\prod (1 - x^n)^{-1}$, and the pentagonal number theorem, which Euler discovered empirically and later proved; the recurrence for $p(n)$ derived from it.
Jacobi, C. G. J. — Fundamenta Nova Theoriae Functionum Ellipticarum · Königsberg (1829). The Jacobi triple product identity $\prod_{n \geq 1}(1 - q^{2n})(1 + q^{2n-1}z)(1 + q^{2n-1}z^{-1}) = \sum_{k \in \mathbb{Z}} q^{k^2} z^k$, from which Euler's pentagonal number theorem and the sum-of-squares formulas follow as specialisations.
Hardy, G. H. & Ramanujan, S. — Asymptotic formulae in combinatory analysis · *Proceedings of the London Mathematical Society* (2) 17 (1918), 75-115. The asymptotic $p(n) \sim \frac{1}{4n\sqrt 3} e^{\pi \sqrt{2n/3}}$ and the convergent Hardy-Ramanujan(-Rademacher) series, obtained by the circle method applied to the generating function — the analytic continuation of this unit's elementary theory.
Hardy, G. H. & Wright, E. M. — An Introduction to the Theory of Numbers · Oxford University Press, 6th edition (2008), revised by D. R. Heath-Brown and J. H. Silverman. Chapter XIX treats partitions, generating functions, Euler's identities, the pentagonal number theorem, and the Jacobi triple product.

Estimated time

beginner: 18m
intermediate: 45m
master: 90m