Every partition, hidden in a product

Turning a diagram on its side proves several things about partitions and stops well short of counting them. There are $77$ partitions of $12$ and $190{,}569{,}292$ of $100$, and no rearrangement of dots produces those numbers — any more than rearranging the ways of cutting a polygon produces the Catalan numbers. What produces them is a product.

Write down one factor for each possible part size:

$$\frac{1}{1-q} \cdot \frac{1}{1-q^2} \cdot \frac{1}{1-q^3} \cdots$$

and multiply it out. The coefficient of $q^n$ is the number of partitions of $n$.

Why the product counts #

Each factor is a geometric series in disguise:

$$\frac{1}{1-q^k} = 1 + q^k + q^{2k} + q^{3k} + \cdots$$

so the factor for part size $k$ offers a choice: use no $k$’s, or one, or two, and so on. Multiplying the factors together means choosing one term from each, and the product of those choices is $q^{\text{total}}$ where the total is what the chosen parts add up to.

A partition of $n$ is exactly a choice of how many ones, how many twos, how many threes — with the total coming to $n$. So the number of ways to get $q^n$ out of the product is the number of partitions of $n$, and the coefficient counts them because multiplication is what “one choice from each” means.

That is the whole argument, and it is worth noticing what kind of argument it is. Nothing was approximated and no limit was taken; a coefficient of $q^{12}$ is decided by the first twelve factors, since a part larger than $12$ cannot appear. Every coefficient is a finite computation, which is what makes the infinite product legitimate as bookkeeping rather than as analysis.

Formal, and then analytic #

A power series used this way is formal: it is a sequence of coefficients with a convenient notation, and questions of convergence do not arise, because nothing is ever evaluated at a number. A polynomial that counts makes the same point about finite sequences, and this is the infinite version.

The series does converge, for $|q| < 1$, and that fact is not needed here and is needed badly later. The function it converges to is closely related to the Dedekind eta function, and its behaviour near the boundary circle is where the asymptotic formula for $p(n)$ comes from — the subject of the fourth rung of this ladder. For now the product is a device for organising a count, and the count is exact.

Euler’s identity, twice #

The first rung proved a theorem by folding diagrams: as many partitions into odd parts as into distinct parts. The product proves it in three lines, and the two proofs are worth having side by side.

$$\prod_{k \ge 1} (1 + q^k) = \prod_{k \ge 1} \frac{1-q^{2k}}{1-q^k} = \prod_{k \ge 1} \frac{1}{1-q^{2k-1}}.$$

The first step is the factorisation $1 + x = (1-x^2)/(1-x)$, applied to every factor. The second is cancellation: the numerators are the even-indexed denominators, so what survives in the denominator is the odd ones. The left-hand product counts partitions into distinct parts — each factor offers “use this part or do not” — and the right-hand product counts partitions into odd parts.

The bijective proof and the algebraic proof answer different questions. Glaisher’s bijection matches up the two collections, so it can be run on a particular partition and produces a particular partner; the algebra says the counts agree and offers no partner at all. Neither subsumes the other, and a subject with only one of the two is much poorer than one with both.

What else the product can say #

The device generalises immediately, and that is its main advantage over any argument about dots.

Parts of bounded size. Using only parts up to $m$ — the restriction a bounded staircase imposes elsewhere in this collection — means a finite product $\prod_{k \le m} 1/(1-q^k)$. Its coefficients count partitions with no part larger than $m$ — which, by conjugation, is also the number with at most $m$ parts. Two restrictions that look different are one restriction on the product side, since turning the diagram over exchanges them.

Parts from any set. Restrict the parts to a set $S$ and the product runs over $S$. Partitions into primes, into squares, into parts congruent to $1$ modulo $4$ — all are one line, and none has a diagram argument. Whether the resulting count has any pleasant form is a separate question, and usually the answer is no; what the product guarantees is that the count is expressible, not that it is nice.

Parts used a bounded number of times. Using each part at most twice replaces $1/(1-q^k)$ by $1 + q^k + q^{2k}$. A pleasant consequence: using each part at most twice is the same count as using no part divisible by three, by the same cancellation trick as Euler’s identity, with $3$ in place of $2$.

Distinct parts with a sign. Attaching a minus sign to each factor gives $\prod (1 - q^k)$, whose coefficients are the number of partitions into an even number of distinct parts minus the number into an odd number. Almost all of those coefficients turn out to be zero, which is the next rung and the strangest fact on this ladder.

Identities the product finds and diagrams do not #

Once counting is algebra, identities can be discovered by manipulating products rather than by having an idea about dots, and some of the results are startling enough that no amount of staring at diagrams would have suggested them.

The Rogers–Ramanujan identities are the standard example. The first says: the number of partitions of $n$ in which no two parts are equal or consecutive equals the number of partitions of $n$ into parts leaving remainder $1$ or $4$ on division by $5$. The second replaces those with parts at least $2$ and remainders $2$ or $3$.

At $n = 9$ the first says there are five of each, and both lists are short enough to write out. Partitions with no two parts equal or consecutive: $9$, $8+1$, $7+2$, $6+3$, $5+3+1$. Partitions into parts leaving remainder $1$ or $4$ on division by five — so parts drawn from $1, 4, 6, 9, 11, \dots$: $9$, $6+1+1+1$, $4+4+1$, $4+1+1+1+1+1$, and $1$ nine times. Five each, and no visible reason.

Both identities are statements about products: a sum of certain series equals a product over an arithmetic progression. They were found by Rogers in 1894, ignored, rediscovered by Ramanujan, and proved in a form anybody accepted only after that — and the modulus five appearing here and again in the congruences of the last rung of this ladder is not a coincidence, though saying exactly what it is takes modular forms.

What the example shows about method is this: the product side of the subject produces conjectures. A restriction on parts becomes a restriction on factors, two restrictions can be compared as functions, and equalities turn up that no bijection was looking for. Bijective proofs of the Rogers–Ramanujan identities exist and are hard; the identities themselves came from the algebra.

The recurrence hiding inside #

The exact values of $p(n)$ in the figures are not computed by expanding the product, which would be slow. They come from a recurrence, and the recurrence comes from the signed product above:

$$p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + \cdots$$

with the numbers subtracted being the generalised pentagonal numbers — $1, 2, 5, 7, 12, 15, \dots$ — and the signs in pairs. That is the fastest elementary way to compute $p(n)$, it needs about $\sqrt{n}$ terms per value, and its derivation is the pentagonal number theorem of the next rung.

So the ladder’s structure here is worth stating plainly: the product is the definition that makes everything else possible, the pentagonal theorem is what makes the product computable, and the asymptotic formula is what happens when the product is treated as an actual function rather than as bookkeeping. Each rung uses the one below as machinery.

Where it came from #

Euler introduced this device in the 1740s, and partitions were the problem that forced it. He was answering questions posed by Naudé — in how many ways can fifty be written as a sum of seven distinct numbers — and the method he invented for them became one of the central techniques of the subject.

The distance between the two rungs is a fair measure of what generating functions bought. Rung one can prove that conjugation is an involution and that odd matches distinct, using pictures anybody can follow. It cannot compute $p(50)$, cannot express “partitions into primes”, and cannot state — never mind prove — an identity whose two sides are restrictions with no bijection between them. Euler’s product does all three, at the cost of leaving the objects behind entirely.

Where the counting is not by product #

Two facts about partitions resist this treatment, and knowing which is which keeps the tool from being oversold.

Anything about the shape of an individual partition. The Durfee square, the conjugate, the largest part — these are properties of a partition, and a coefficient is a count with all the individual partitions summed away. A generating function that tracks a statistic needs a second variable: $\prod 1/(1 - z q^k)$ with $z$ marking the number of parts, for instance, and the coefficient of $z^m q^n$ then counts partitions of $n$ into exactly $m$ parts. That works, and it is how the rank of the last rung is handled, but it is a different object with two variables in it.

Anything asking which partitions have a property. The product counts; it does not exhibit. When a bijection between two collections is wanted rather than an equality of counts, the product is silent, and one has to be built by hand.

Two variables, and what they track #

The product can be made to carry more than a count, and the device for it is one extra variable.

Write $\prod_k 1/(1 - z q^k)$ and expand. Choosing $q^{jk}$ from the factor for part size $k$ now comes with $z^j$ attached, so the exponent of $z$ records how many parts were used altogether. The coefficient of $z^m q^n$ is therefore the number of partitions of $n$ into exactly $m$ parts, and setting $z = 1$ collapses it back to $p(n)$.

That one move covers most of what the subject asks for. Marking parts of a particular size, marking the largest part, marking the number of distinct part sizes — each is a variable inserted in a different place, and each turns a single sequence of coefficients into a table of them. The rank of the fifth rung, which explains a divisibility, is exactly this: a second variable tracking the largest part minus the number of parts, and the resulting two-variable product is what makes the classes it defines countable.

The cost is that expressions stop being pretty and start being work. A one-variable product can be manipulated by hand — the Euler identity above took three lines — and a two-variable one usually cannot. This is the standing trade in the subject: more information tracked, less algebra available.

What is being multiplied, exactly #

A last word on rigour, because the manipulations above look cavalier and are not.

A formal power series is a function from the whole numbers to the whole numbers, written with $q$’s as position markers. Adding and multiplying them is defined by the usual formulas, and both are finite operations on each coefficient — the coefficient of $q^n$ in a product involves only the coefficients up to $n$ in each factor. An infinite product is legitimate when each coefficient stabilises after finitely many factors, which is the case here because the factor for part size $k$ contributes nothing below $q^k$.

So every equation in this essay is an equation between sequences of integers, verified coefficient by coefficient, and the figures do exactly that verification over the range they draw. Nothing converges, nothing is evaluated, and no analysis is used. The analysis comes later, and when it does it is a genuinely different argument about a genuinely different object — the function these coefficients happen to define inside the unit circle.

What the pictures cannot show #

The figures print coefficients, which are the ends of the computation rather than the computation. Multiplying out twelve infinite series is a page of arithmetic and the figure shows a row of numbers; what it does establish is that two independent routes to those numbers agree, which is the check worth making. The product is expanded factor by factor, the recurrence is run separately, and every coefficient is asserted equal.

An infinite product cannot be drawn at all, and the honest reading of “the coefficient of $q^{12}$ is decided by the first twelve factors” is that nothing infinite ever enters a particular coefficient. The infinitude is in the statement rather than in any computation, which is exactly the sense in which the series is formal.

The last limitation is about scale. Every figure here stops before twenty, and the interesting behaviour of $p(n)$ — the growth rate, the congruences — is invisible at that size. Nothing in the coefficients $1, 1, 2, 3, 5, 7, 11, 15, 22, 30$ suggests that every fifth one from the fifth is divisible by five, and nothing suggests the square root in the exponent of the asymptotic formula. Both are visible only when far more values are computed than a table can hold, which is what the last two rungs of this ladder are for.

Where the ladder goes next #

Attaching a minus sign to every factor gives a product whose expansion ought to be a mess: infinitely many terms of both signs, with no reason for anything to simplify. What comes out instead is almost entirely zeroes, with a solitary $+1$ or $-1$ at the numbers $1, 2, 5, 7, 12, 15$ and their successors. Euler found it by expanding by hand and could not prove it for ten years, and the proof, when it came, is a way of pairing partitions off so that the pairs cancel.