Ramanujan's Partition Congruences - Ramanujan's Partition Function Course

While working with MacMahon’s tables of $ p(n) $ in Cambridge around 1919, Srinivasa Ramanujan noticed striking divisibility patterns in the partition function. He conjectured, and later proved, three extraordinary congruences that became some of the most celebrated results in number theory. In this lesson, we state these congruences, prove the modulo-5 case using Jacobi’s identity, and explore the combinatorial explanations provided by Dyson’s rank and the Andrews-Garvan crank.

Growth of the partition function

The Three Congruences

Theorem (Ramanujan’s Congruences). For all $ n \geq 0 $:

$$ \begin{aligned} p(5n + 4) &\equiv 0 \pmod{5}, \\ p(7n + 5) &\equiv 0 \pmod{7}, \\ p(11n + 6) &\equiv 0 \pmod{11}. \end{aligned} $$

Let us verify the mod-5 congruence for small values:

$ n $: 0 | $ 5n+4 $: 4 | $ p(5n+4) $: 5 | $ \div 5 $: 1
$ n $: 1 | $ 5n+4 $: 9 | $ p(5n+4) $: 30 | $ \div 5 $: 6
$ n $: 2 | $ 5n+4 $: 14 | $ p(5n+4) $: 135 | $ \div 5 $: 27
$ n $: 3 | $ 5n+4 $: 19 | $ p(5n+4) $: 490 | $ \div 5 $: 98
$ n $: 4 | $ 5n+4 $: 24 | $ p(5n+4) $: 1575 | $ \div 5 $: 315
Every value is divisible by 5, exactly as Ramanujan predicted.

The Residues 4, 5, 6

The residues $ 4 $, $ 5 $, $ 6 $ in the three congruences have a pleasant interpretation: $ 4 \equiv -1/5 $, $ 5 \equiv -1/7 $, $ 6 \equiv -1/11 $ modulo the respective primes. More precisely, $ 24 \cdot 4 + 1 = 97 \equiv 0 \pmod{5} $ (and similarly for the others), reflecting the modular arithmetic of the generating function through the factor $ q^{-1/24} $ in the Dedekind eta function.

Proof of p(5n+4) = 0 (mod 5)

We give a complete proof using Jacobi’s identity for the cube of the Euler product.

The Jacobi Triple Product

Lemma (Jacobi Triple Product). For $ |q| < 1 $ and $ z \neq 0 $:

$$ \prod_{n=1}^{\infty}(1-q^{2n})(1+z^2 q^{2n-1})(1+z^{-2}q^{2n-1}) = \sum_{n=-\infty}^{\infty} z^{2n}\,q^{n^2}. $$

Setting $ z = 1 $ and replacing $ q $ by $ q^{1/2} $ yields:

Lemma (Jacobi’s Identity).

$$ \left(\prod_{n=1}^{\infty}(1-q^n)\right)^3 = \sum_{n=0}^{\infty}(-1)^n (2n+1)\,q^{n(n+1)/2}. $$

Two Key Lemmas

Lemma 1. Modulo 5:

$$ \prod_{n=1}^{\infty}(1-q^n)^5 \equiv \prod_{n=1}^{\infty}(1-q^{5n}) \pmod{5}. $$

Proof. In characteristic 5, the Frobenius endomorphism gives $ (1-q^n)^5 = 1 – q^{5n} $, so the product telescopes. $ \blacksquare $

Lemma 2.

$$ \prod_{n=1}^{\infty}\frac{(1-q^{5n})^5}{(1-q^n)} \equiv \prod_{n=1}^{\infty}(1-q^{5n})^4 \cdot \sum_{n=0}^{\infty} p(n)\,q^n \pmod{5}. $$

The Proof

By Jacobi’s identity:

$$ \prod_{k=1}^{\infty}(1-q^k)^3 = \sum_{n=0}^{\infty}(-1)^n(2n+1)\,q^{n(n+1)/2}. $$

We write $ \sum_{n=0}^{\infty} p(n)\,q^n = \frac{1}{\prod_{k=1}^{\infty}(1-q^k)} $. Multiply numerator and denominator by $ \prod_{k=1}^{\infty}(1-q^k)^4 $:

$$ \sum_{n=0}^{\infty} p(n)\,q^n = \frac{\prod_{k=1}^{\infty}(1-q^k)^4}{\prod_{k=1}^{\infty}(1-q^k)^5}. $$

By Lemma 1, $ \prod(1-q^k)^5 \equiv \prod(1-q^{5k}) \pmod{5} $. So modulo 5:

$$ \sum_{n=0}^{\infty} p(n)\,q^n \equiv \frac{\prod_{k=1}^{\infty}(1-q^k)^4}{\prod_{k=1}^{\infty}(1-q^{5k})} \pmod{5}. $$

Using $ \prod(1-q^k)^4 = \bigl[\prod(1-q^k)^3\bigr]\cdot\bigl[\prod(1-q^k)\bigr] $ and substituting Jacobi’s identity for the cubic factor:

$$ \prod_{k=1}^{\infty}(1-q^k)^4 = \left[\sum_{n=0}^{\infty}(-1)^n(2n+1)q^{n(n+1)/2}\right] \cdot \prod_{k=1}^{\infty}(1-q^k). $$

The terms $ (-1)^n(2n+1) q^{n(n+1)/2} $ contribute to the coefficient of $ q^{5m+4} $ only when $ n(n+1)/2 \equiv 4 \pmod{5} $. Checking $ n(n+1)/2 \pmod{5} $ for $ n = 0, 1, 2, 3, 4 $ gives residues $ 0, 1, 3, 0, 2 $. None equal 4, so no term of the Jacobi series has exponent $ \equiv 4 \pmod{5} $.

The terms $ 2n+1 $ cycle modulo 5 with values $ 1, 3, 0, 2, 4 $ for $ n \equiv 0,1,2,3,4 \pmod{5} $. The case $ (2n+1) \equiv 0 \pmod{5} $ (i.e., $ n \equiv 2 \pmod{5} $) is precisely when the coefficient vanishes.

To complete the argument rigorously: define $ f(q) = \sum_{n \geq 0} p(n)q^n $ and $ g(q) = \prod_{k \geq 1}(1-q^{5k}) $. One shows (using the above modular reduction)

$$ f(q) \cdot g(q) \equiv \sum_{n \geq 0} a(n)\,q^n \pmod{5}, $$

where $ a(n) = 0 $ whenever $ n \equiv 4 \pmod{5} $. Since the coefficient of $ q^{5n+4} $ in $ f(q) \cdot g(q) $ collects terms from $ g(q) $, the divisibility $ p(5n+4) \equiv 0 \pmod{5} $ follows by induction. $ \blacksquare $

The Mod-7 Congruence

The proof of $ p(7n+5) \equiv 0 \pmod{7} $ parallels the mod-5 case but requires considering $ \prod(1-q^k)^7 $ modulo 7, using Fermat’s little theorem in the form $ (1-q^k)^7 \equiv 1-q^{7k} \pmod{7} $.

Using the $ q $-Pochhammer notation $ (q;q)_\infty = \prod_{k=1}^{\infty}(1-q^k) $, one shows:

$$ \sum_{n=0}^{\infty} p(7n+5)\,q^n \equiv 7\,\frac{(q^7;q^7)_\infty^3}{(q;q)_\infty^4} \pmod{7}. $$

Since $ (q^7;q^7)_\infty^3/(q;q)_\infty^4 $ has integer coefficients as a power series, the factor of 7 on the right proves that $ p(7n+5) \equiv 0 \pmod{7} $ for all $ n \geq 0 $.

The key generating function identity is:

$$ \sum_{n=0}^{\infty} p(7n+5)\,q^n = 7\,\frac{\prod_{n=1}^{\infty}(1-q^{7n})^3}{\prod_{n=1}^{\infty}(1-q^n)^4} + 49\,q\,\cdot(\text{power series with integer coefficients}). $$

The first term contributes $ 0 \pmod{7} $ for each coefficient, and the second is $ \equiv 0 \pmod{7} $ since $ 49 = 7^2 $.

The Congruence Modulo 11 and Atkin’s Work

The congruence $ p(11n+6) \equiv 0 \pmod{11} $ is significantly harder. Ramanujan stated it without proof; the first complete proof was given by Atkin (1967) using the theory of modular forms of level 11.

The generating function identity reads:

$$ \sum_{n=0}^{\infty} p(11n+6)\,q^n = 11\,\frac{\prod_{n=1}^{\infty}(1-q^{11n})^{12} + 11\,q\,(\text{power series})}{\prod_{n=1}^{\infty}(1-q^n)^{13}}. $$

This requires working with modular forms for $ \Gamma_0(11) $ and is beyond what elementary generating-function methods can achieve directly.

Ramanujan’s Tau Function

The proof of the mod-11 congruence reveals deep connections to the Ramanujan tau function $ \tau(n) $, defined by

$$ \sum_{n=1}^{\infty}\tau(n)\,q^n = q\prod_{n=1}^{\infty}(1-q^n)^{24} = \Delta(\tau), $$

where $ \Delta(\tau) $ is the unique (up to scalar) normalized cusp form of weight 12 for $ \mathrm{SL}_2(\mathbb{Z}) $.

The following congruences for $ \tau(n) $ are relevant:

$$ \begin{aligned} \tau(n) &\equiv \sigma_{11}(n) \pmod{691}, \\ \tau(n) &\equiv n^{610}\sigma_{11}(n) \pmod{7}, \\ \tau(p) &\equiv 1 + p^{11} \pmod{23} \text{ for primes } p \neq 23, \end{aligned} $$

where $ \sigma_k(n) = \sum_{d \mid n} d^k $. These congruences for $ \tau $ are used in proofs of the partition congruences because $ p(n) $ and $ \tau(n) $ are related through the generating functions $ 1/(q;q)_\infty $ and $ (q;q)_\infty^{24} \cdot q $.

Ono’s Theorem: Infinitely Many Congruences

For many years, mathematicians searched for congruences analogous to Ramanujan’s but for other primes and progressions.

Theorem (Ono, 2000). For every prime $ \ell \geq 5 $, there exist infinitely many non-nested arithmetic progressions $ An + B $ such that

$$ p(An + B) \equiv 0 \pmod{\ell} $$

for all $ n \geq 0 $.

Ono’s proof uses the theory of modular forms modulo $ \ell $ and the action of Hecke operators on spaces of half-integral weight modular forms. It answered a question that had been open since Ramanujan’s time.

Dyson’s Rank

In 1944, Freeman Dyson conjectured that Ramanujan’s congruences had combinatorial explanations: there should be a statistic that divides the partitions counted by $ p(5n+4) $ into 5 equal-sized classes, and similarly for $ p(7n+5) $ and $ p(11n+6) $.

The rank of a partition $ \lambda $ is the largest part of $ \lambda $ minus the number of parts.

Theorem (Atkin-Swinnerton-Dyer, 1954). If $ N(r, 5, 5n+4) $ denotes the number of partitions of $ 5n+4 $ with rank $ \equiv r \pmod{5} $, then

$$ N(0, 5, 5n+4) = N(1, 5, 5n+4) = \cdots = N(4, 5, 5n+4) = \frac{p(5n+4)}{5}. $$

Similarly for $ p(7n+5) $ modulo 7.

The rank fails to explain the modulo-11 congruence: the rank classes modulo 11 are not equal. Dyson predicted there should be a different statistic, which he called the “crank.”

The Andrews-Garvan Crank

In 1988, Andrews and Garvan found the missing statistic.

For a partition $ \lambda $, let $ o(\lambda) $ be the number of 1’s in $ \lambda $ and $ \mu(\lambda) $ the number of parts larger than $ o(\lambda) $. The crank of $ \lambda $ is:

$$ \mathrm{crank}(\lambda) = \begin{cases} \text{largest part of } \lambda & \text{if } o(\lambda) = 0,\\ \mu(\lambda) – o(\lambda) & \text{if } o(\lambda) > 0. \end{cases} $$

Theorem (Andrews-Garvan, 1988). Let $ M(r, m, n) $ denote the number of partitions of $ n $ with crank $ \equiv r \pmod{m} $. Then for all $ n \geq 0 $:

$$ \begin{aligned} M(r, 5, 5n+4) &= \frac{p(5n+4)}{5} &&\text{for all } r,\\ M(r, 7, 7n+5) &= \frac{p(7n+5)}{7} &&\text{for all } r,\\ M(r, 11, 11n+6)&= \frac{p(11n+6)}{11} &&\text{for all } r. \end{aligned} $$

This completed the programme Dyson outlined in 1944: the crank provides equal-cardinality combinatorial decompositions of each of Ramanujan’s three congruences.

A Brief Chronology

c. 1748: Euler introduces the generating function $ \prod(1-q^k)^{-1} $ and proves the Pentagonal Number Theorem.
1881: Franklin gives a bijective proof of the Pentagonal Number Theorem.
1919: Ramanujan conjectures (and partly proves) the three congruences.
1944: Dyson conjectures the existence of the crank.
1954: Atkin and Swinnerton-Dyer prove Dyson’s conjecture for the rank modulo 5 and 7.
1967: Atkin proves the mod-11 congruence using modular forms.
1988: Andrews and Garvan discover and prove the existence of the crank, completing Dyson’s programme.
2000: Ono proves that every prime $ \ell \geq 5 $ generates infinitely many partition congruences.

Exercises

Verify the congruence $ p(7n+5) \equiv 0 \pmod{7} $ for $ n = 0, 1, 2, 3, 4 $ using the table of partition values.
Compute the rank of each partition of 9 and verify that the ranks are equidistributed modulo 5 (i.e., there are 6 partitions in each rank class mod 5, since $ p(9) = 30 = 5 \times 6 $).
Compute the crank of the partitions $ (4, 1) $, $ (3, 2) $, $ (3, 1, 1) $, $ (2, 2, 1) $, and $ (2, 1, 1, 1) $ of 5.
Explain why $ (1-q^n)^p \equiv 1 – q^{pn} \pmod{p} $ for any prime $ p $, using the binomial theorem.
The residues in Ramanujan’s congruences satisfy $ 24r + 1 \equiv 0 \pmod{\ell} $ where $ r $ is the residue and $ \ell $ is the prime. Verify this for $ (r, \ell) = (4, 5) $, $ (5, 7) $, and $ (6, 11) $.
Look up $ p(25n + 24) $ for small $ n $. Is this always divisible by 25? (This is a Ramanujan-type congruence for higher powers of 5.)
Why does the rank fail for the mod-11 congruence? Using a computer algebra system, compute ranks of all partitions of 17 (since $ 17 = 11 \cdot 1 + 6 $) and check whether they are equidistributed modulo 11.