Two counts that agree for no visible reason

The product that hides every partition ended with a warning. The product side of the subject produces conjectures, it said: restrict the parts, restrict the factors, compare two functions, and equalities turn up that no bijection was looking for. The standard example was named and not developed. It is the pair of identities Leonard Rogers found in 1894, Srinivasa Ramanujan rediscovered without proof around 1913, and Issai Schur found independently in 1917 — and it is the most famous case in the subject of two counts that agree for no visible reason.

The first identity, in words: the number of ways to write $n$ as a sum of whole numbers that differ from each other by at least two equals the number of ways to write $n$ as a sum of whole numbers that each leave $1$ or $4$ on division by $5$. Order does not matter in either count, and in the second the same number may be used repeatedly. Neither condition mentions the other. One is about gaps, and one is about remainders.

The six partitions of ten, twice #

On the left, the partitions of $10$ into parts at least two apart: $10$, $9 + 1$, $8 + 2$, $7 + 3$, $6 + 4$, and $6 + 3 + 1$. There cannot be four parts, since the smallest four parts two apart are $1 + 3 + 5 + 7 = 16$. On the right, the partitions of $10$ into parts from $\{1, 4, 6, 9, 11, \ldots\}$: $9 + 1$, $6 + 4$, $6 + 1 + 1 + 1 + 1$, $4 + 4 + 1 + 1$, $4$ with six ones, and ten ones. Six and six.

Look for a matching and the difficulty is immediate. The left column is made of few, large, spread-out parts; the right is full of repeated ones and fours. The two share the partitions $9 + 1$ and $6 + 4$, which satisfy both conditions, and then nothing else. A matching would have to pair $10$ with one of the ones-heavy partitions on the right, and $6 + 3 + 1$ with another, by some rule that works for every $n$ — and no simple such rule has ever been found.

Every number, both identities #

The counts can be carried much further than any list, by counting rather than listing. For $n = 20$ both are $31$; for $n = 30$, $117$; for $n = 40$, $374$. The figure checks equality at every $n$ up to $40$.

There is a second identity of exactly the same kind: partitions with parts differing by at least two and no part equal to $1$ are as numerous as partitions into parts leaving $2$ or $3$ on division by $5$. At $n = 40$ both are $237$. Change the modulus and the magic is gone. Partitions into parts leaving $1$ or $5$ on division by $6$ — a condition that looks just as natural — part company with the gap-two partitions at $n = 4$, where there are two of the first kind ($4$ and $3 + 1$) and one of the second ($1 + 1 + 1 + 1$). The identities are a fact about five, not about moduli in general.

The staircase inside a gap-two partition #

One side of each identity can be counted by a construction, and the construction is a relative of the Durfee square that measured the corner of a random partition. Take a partition whose parts differ by at least two, with $k$ parts. The smallest such partition is $(2k-1) + (2k-3) + \cdots + 3 + 1$, a staircase whose total is $k^2$. Subtract that staircase from the parts, row by row.

What remains is an ordinary partition into at most $k$ parts — the gaps of at least two between the original parts become gaps of at least zero, which is no condition at all. The step reverses: add the staircase back to any partition into at most $k$ parts and the result has gaps of at least two. So gap-two partitions of $n$ with $k$ parts correspond exactly to ordinary partitions of $n - k^2$ into at most $k$ parts. Partitions into at most $k$ parts are counted, by turning the diagram over, by the same numbers as partitions into parts of size at most $k$, whose generating function is $1/((1-q)(1-q^2)\cdots(1-q^k))$. So the gap-two partitions are counted by

$$\sum_{k \ge 0} \frac{q^{k^2}}{(1-q)(1-q^2)\cdots(1-q^k)}.$$

The second identity has its own staircase. With no part equal to $1$ allowed, the smallest gap-two partition with $k$ parts is $2k + (2k-2) + \cdots + 4 + 2$, which totals $k(k+1)$, and subtracting it again leaves an ordinary partition into at most $k$ parts. So the second identity’s gap side is $\sum_k q^{k^2+k}/((1-q)\cdots(1-q^k))$ — the same shape with the staircase shifted by one dot a row.

It is worth expanding the first few terms by hand, because the agreement is visible there and so is its fragility. The $k = 0$ term is $1$. The $k = 1$ term, $q/(1-q)$, contributes one partition of every positive $n$ — the single part $n$. The $k = 2$ term, $q^4/((1-q)(1-q^2))$, starts at $n = 4$ and contributes $1, 1, 2, 2, 3, 3, \ldots$ for $n = 4, 5, 6, 7, 8, 9$: the two-part partitions with a gap of two. The $k = 3$ term starts at $n = 9$. Adding them, the counts for $n = 0$ to $9$ are $1, 1, 1, 1, 2, 2, 3, 3, 4, 5$. On the product side, the allowed parts below ten are $1, 4, 6, 9$, and the partitions using them give $1, 1, 1, 1, 2, 2, 3, 3, 4, 5$ as well. Every coefficient agrees, and each agrees for a different-looking reason.

The other side is easier still: partitions into parts from a set of allowed sizes are counted by a product with one factor per allowed size, here $\prod 1/\big((1 - q^{5j+1})(1 - q^{5j+4})\big)$. So the first identity says

$$\sum_{k \ge 0} \frac{q^{k^2}}{(1-q)(1-q^2)\cdots(1-q^k)} \;=\; \prod_{j\ge0} \frac{1}{(1-q^{5j+1})(1-q^{5j+4})},$$

and that is the form in which Rogers found it. A sum indexed by the number of parts on one side, a product indexed by the allowed sizes on the other, and the whole difficulty is that there is no reason for them to be equal that either side can see.

The counts also grow at a rate the product determines. The number of all partitions grows like $e^{\pi\sqrt{2n/3}}$, and allowing only two of every five part sizes cuts the exponent by the square root of two-fifths: the Rogers–Ramanujan counts grow like $e^{2\pi\sqrt{n/15}}$. At $n = 40$ there are $374$ partitions of each kind, against $37{,}338$ partitions in all. The gap-two side cannot see that rate either; it comes out of the product, and a reader looking only at partitions with spread-out parts would have no way to guess that their number is controlled by the number five.

A history of rediscovery #

The identities have an odd history, and it is part of why they became famous. Rogers published them in 1894, in a paper on the expansion of infinite products that nobody read. Ramanujan found them again, apparently independently, and sent them to Hardy without proof; Hardy passed them to Percy MacMahon, who printed them in his Combinatory Analysis of 1916, in the partition form stated above, as identities that had been checked numerically and not proved. Then in 1917 Ramanujan, looking through old volumes of the Proceedings of the London Mathematical Society, came across Rogers’s paper and found his conjectures proved there more than twenty years earlier. The same year Issai Schur, cut off from British journals by the war, found and proved them a third time. Rogers and Ramanujan published a joint, simplified proof in 1919. The identities carry both names because the first discoverer was forgotten and the second could not prove them — and the third, Schur, is usually left out of the name altogether.

Why nobody can see it #

Both sides count something, so there must be a bijection — a matching of the partitions on the left with those on the right, for each $n$. There is, but finding it took until 1981, when Adriano Garsia and Stephen Milne constructed one using an involution principle: a general method for converting a proof by cancellation of signed terms into a matching. Their bijection is explicit and extraordinarily complicated; following it on a single partition of a moderate number takes pages. Igor Pak showed in 2003 that no bijection of a certain natural geometric kind can exist, which goes some way to explaining why the simple one everybody looked for was never found.

The proofs that everyone uses are not bijective at all. Rogers’s own proof and Schur’s are manipulations of power series; George Andrews found a dozen more, and a proof by Andrews and Rodney Baxter published in 1989 was motivated by physics. Each proof sees the identity from a different side and none makes it obvious. It belongs to a small class of statements in combinatorics — easy to state, easy to check, proved many ways — whose truth is not explained by any known proof, in the sense that a reader who follows every step still could not have predicted the answer.

The contrast is with identities that turning a diagram over does settle. Partitions into distinct parts are as numerous as partitions into odd parts, and a direct matching exists: split each even part in half repeatedly, or merge pairs of equal parts. That identity is visible. Rogers–Ramanujan is not, and the difference is not one of difficulty but of kind.

One modulus up #

Basil Gordon found in 1961 that the Rogers–Ramanujan identities are the first members of an infinite family, one for each odd modulus.

At modulus $5$ the condition “parts differ by at least two” can be restated as: for every whole number $j$, the parts equal to $j$ and to $j + 1$ together number at most one. Gordon’s generalisation relaxes one to $k - 1$ and moves the modulus to $2k + 1$. For $k = 3$: partitions in which each pair of consecutive sizes $j, j+1$ appears at most twice in total, and with at most $i - 1$ ones, are as numerous as partitions into parts avoiding $0$ and $\pm i$ modulo $7$. The figure lists every partition up to $30$ and counts both kinds for $i = 1, 2, 3$; they agree in every cell. Andrews found the power-series form of Gordon’s identities, and they are known together as the Andrews–Gordon identities.

The continued fraction Ramanujan sent Hardy #

The two sides of the identities have a ratio, and the ratio is where Ramanujan’s name became attached. Divide the second identity’s product by the first’s and multiply by $q^{1/5}$, and the result is a continued fraction:

$$R(q) = \cfrac{q^{1/5}}{1 + \cfrac{q}{1 + \cfrac{q^2}{1 + \cfrac{q^3}{1 + \cdots}}}}.$$

In his first letter to G. H. Hardy in 1913, Ramanujan stated, among dozens of other results and without proof, that

$$R\!\left(e^{-2\pi}\right) = \sqrt{\frac{5 + \sqrt 5}{2}} - \frac{1 + \sqrt 5}{2}.$$

Hardy later recalled that these formulas defeated him completely, that he had never seen anything remotely like them, and that they had to be true, because nobody could have had the imagination to invent them. The figure computes the continued fraction and the product ratio at once, finds them equal across the range, and matches Ramanujan’s value at $e^{-2\pi}$ to fourteen decimal places.

The value is an algebraic number built from $\sqrt 5$ and $(1 + \sqrt 5)/2 = \varphi$, and the continued fraction levels off near $1/\varphi = 0.618$ as $q$ approaches one — since at $q = 1$ it becomes $1/(1 + 1/(1 + \cdots))$, the golden ratio’s own continued fraction. Five appears in the subject once more, in Ramanujan’s congruences: the number of all partitions of $5k + 4$ is always divisible by five. That is a different phenomenon about a different count, and the same modular arithmetic of level five lies under both. The golden ratio is in the identities because five is: $R(q)$ is a modular function of level five, and its fifth power satisfies an equation Felix Klein had studied in connection with the symmetries of the icosahedron, the solid whose coordinates need $\sqrt 5$. The partition identity about remainders on division by five, the pentagon, and the icosahedron are three appearances of one arithmetic.

Hard hexagons, and a second life #

In 1980 the physicist Rodney Baxter solved exactly a model of a gas of particles on a triangular lattice in which no two particles may be neighbours — the hard hexagon model — and found that its solution needed the Rogers–Ramanujan identities, which he did not at first recognise. The gap condition is the key: particles that may not sit next to each other are, in one dimension, parts that must differ by at least two. The identities then turned up in the theory of affine Lie algebras, where James Lepowsky and Robert Wilson showed in the early 1980s that they describe the structure of certain representations, and later in conformal field theory. A statement found by expanding power series by hand in 1894 is now a statement about the symmetries of physical systems at a phase transition.

That second life is the best evidence for the essay’s title. When a coincidence is explained by structures from three different subjects, none of which was invented to explain it, the coincidence is not an accident of small numbers. It is a fact whose reason lies deeper than the partitions it is stated in.

What the lists cannot show #

They cannot show every $n$. The figures check the identities at every $n$ up to $40$, and Gordon’s up to $30$. That the counts agree for all $n$ is the theorem; a finite check is consistent with a first disagreement at $n = 41$, and the only reason to believe there is none is the proof.

They cannot show a bijection. The two columns of the first figure are drawn side by side, and the absence of a visible matching between them is exactly the point; the Garsia–Milne matching exists and is far too elaborate to draw.

And they cannot show the modular structure. That $R(q)$ is a modular function, and that its special values are algebraic, is the reason Ramanujan’s value is what it is. The figure confirms the value numerically; it does not show why a continued fraction built from partition counts should take algebraic values at points like $e^{-2\pi}$.

Still open: a matching that explains #

Every proof of the Rogers–Ramanujan identities establishes that the counts agree, and several now construct a matching. None produces a matching simple enough to be the reason — a rule a reader could apply to $6 + 3 + 1$ and see at once which partition into ones, fours and sixes it corresponds to, and why. Whether such a rule exists, or whether the identities are true for reasons that no matching can express simply, is not settled. Pak’s theorem rules out one natural family of candidates; it does not rule out every possibility, and the search is one of the long-standing aesthetic problems of combinatorics.

Gaps against remainders #

Partitions of $n$ into parts differing by at least two are exactly as numerous as partitions into parts leaving $1$ or $4$ on division by $5$, and with no part $1$, as numerous as partitions into parts leaving $2$ or $3$. The figures check both at every $n$ to forty, and show the same test failing at once modulo six. Subtracting a staircase of $k^2$ dots turns a gap-two partition with $k$ parts into an ordinary one, which gives one side as $\sum q^{k^2}/((1-q)\cdots(1-q^k))$; the other side is a product over the allowed remainders.

Gordon’s theorem extends the pair to every odd modulus, checked here modulo seven. The ratio of the two products is a continued fraction whose values Ramanujan found to be algebraic, involving $\sqrt5$ and the golden ratio. And the identities reappeared in the exact solution of a physical model and in the theory of Lie algebras — while a simple matching between the two kinds of partition has still never been found.

When two unrelated-looking counts agree at every number, the agreement is information — and when no simple matching explains it, the explanation usually lives in a larger structure than the one the counts were stated in.