Partition Numbers: Seeing Patterns Others Couldn't
How Ramanujan stared at a handwritten table of partition numbers and saw divisibility patterns nobody else had noticed
In 1918 Ramanujan looked at a handwritten table of partition numbers computed by Percy MacMahon and noticed three exact divisibility patterns that no one else had seen. This lesson walks through what a partition is, how Ramanujan's eye caught the patterns, and why the congruences he found became a launching point for modern analytic number theory.
Partition Numbers: Seeing Patterns Others Couldn't
In a small set of rooms at Trinity College Cambridge, in the late winter of 1918, Srinivasa Ramanujan sat with a long handwritten table spread across his desk. The table had been built up by Major Percy MacMahon, a retired British army officer turned combinatorialist, working at his desk for months on end. It listed, for every whole number from one to two hundred, the count of ways that number could be split into a sum of smaller whole numbers. The numbers in the right hand column grew at a frightening pace. By two hundred the count was nearly four trillion. Ramanujan ran his finger down a single column. Within a few sittings he announced three rules nobody had spotted in the twenty years the table had existed. MacMahon, who had written every number in the table by hand, checked the rules row by row. They held. The story of how Ramanujan saw what no one else had seen begins with the simplest possible question.
What Is a Partition
Take the number four. In how many ways can you write it as a sum of positive whole numbers, if order does not matter?
- 4
- 3 + 1
- 2 + 2
- 2 + 1 + 1
- 1 + 1 + 1 + 1
That is all of them. Five ways. Mathematicians write this fact as p(4) = 5, where p is the partition function. Partitions are one of the simplest objects you can define in all of mathematics. A child can understand the question. And yet the partition function is one of the most difficult sequences to compute in closed form, and the story of how it was finally understood runs straight through the mind of Srinivasa Ramanujan.
The Numbers Grow Fast
The partition function starts quietly. p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7, p(6) = 11. But it does not stay quiet. By p(10) the value is already 42. By p(50) it is 204,226. By p(100) it is 190,569,292. By p(200), the value is 3,972,999,029,388. The numbers grow roughly like the exponential of the square root of n, and there is no simple formula that gives you the next value from the previous ones. Unlike the Fibonacci numbers, which have a clean recurrence, the partition function has to be built up the hard way: either by listing the partitions directly, which is combinatorially enormous, or by working with a generating function, which is a power series whose coefficients are exactly the p(n).