A partition piled into a corner

Every essay on partitions so far has looked at one row. A diagram turned on its side drew a partition of $n$ as rows of dots, each row no longer than the one above, and read the columns instead; the whole subject since has been about that staircase — how many there are, how large the count is, which residues it takes, what shape a random one has. The staircase is a list of numbers that never increases, laid out in one direction.

Lay the numbers out in two directions instead. A plane partition of $n$ is a grid of positive whole numbers adding up to $n$ that never increases along a row and never increases down a column. Read each number as the height of a stack of cubes standing on its square, and the grid becomes a pile of cubes pushed into the corner of a room, every cube resting on the floor or on another cube and against the walls or against other cubes. Percy MacMahon, who computed the partition table Ramanujan used, spent much of the 1910s on these piles and found that they can be counted with as much precision as the ordinary partitions — by a product that differs from Euler’s in one exponent.

An ordinary partition is a pile one row deep #

The hero figure draws a plane partition of 29: rows $5, 4, 3, 1$, then $4, 3, 2$, then $3, 2, 1$, then $1$. Every row reads downwards from left to right, and every column reads downwards from top to bottom. As cubes, the 5 is the tallest stack in the back corner, and the heights fall away towards the open side of the room. A partition in the usual sense is a plane partition with only one row, so every ordinary partition is a pile one cube deep, standing against one wall.

The extra freedom is enormous. There are 4,565 partitions of 29 and 3,759,612 plane partitions, eight hundred times as many. Counting them by listing them is possible for small $n$ and becomes hopeless quickly, and the first question is whether there is a product that does the counting, the way Euler’s product counts ordinary partitions by multiplying out one factor for each part size.

MacMahon’s product: part $k$ in $k$ colours #

There is, and it is nearly Euler’s. Euler’s product is

$$\prod_{k \ge 1} \frac{1}{1 - q^k} = \sum_{n \ge 0} p(n)\, q^n,$$

where the factor for $k$ expands to $1 + q^k + q^{2k} + \cdots$ and chooses how many parts of size $k$ to use. MacMahon’s is

$$\prod_{k \ge 1} \frac{1}{(1 - q^k)^{k}} = \sum_{n \ge 0} \mathrm{PL}(n)\, q^n,$$

the same product with the factor for $k$ repeated $k$ times. Combinatorially, it counts partitions in which a part of size $k$ comes in $k$ different colours: one colour of 1, two colours of 2, three of 3. The plane partitions of $n$ are equinumerous with these coloured partitions, and MacMahon’s proof that they are was long; a bijection that matches them one to one was found much later and is not simple either.

The figure checks the product both ways. Plane partitions are listed one at a time for every $n$ up to 12 — building each grid row by row, each row a non-increasing list no longer and no higher than the row above — and the counts are 1, 1, 3, 6, 13, 24, 48, 86, 160, 282, 500, 859 and 1,479. The coefficients of MacMahon’s product are computed exactly, to $n = 1{,}000$, from a recurrence that follows from taking its logarithm: $n\,\mathrm{PL}(n) = \sum_{k=1}^{n} \sigma_2(k)\,\mathrm{PL}(n-k)$, where $\sigma_2(k)$ is the sum of the squares of the divisors of $k$. The two lists agree on every one of the thirteen values that can be checked by listing.

Plotted on a logarithmic scale beside the ordinary partition numbers, the plane counts pull away steadily. At $n = 200$ there are 3,972,999,029,388 partitions, a 13-digit number, and the plane partitions run to 28 digits. The shapes of the two curves are what matter: the ordinary count’s logarithm grows like $\sqrt{n}$, and the plane count’s like $n^{2/3}$. Adding a second direction to the staircase does not multiply the count by a larger constant at each step. It raises the exponent.

Where the colours come from #

The colours look like a trick of algebra, a way of saying “repeat the factor $k$ times” in words. They have a geometric meaning, and it explains the product better than any manipulation of series. Number the squares of the floor of the room by their row $i$ and column $j$, starting from 1 in the corner, and give the square $(i, j)$ the weight $i + j - 1$. The corner square has weight 1, the two squares next to it have weight 2, the three squares beyond those have weight 3, and in general exactly $k$ squares have weight $k$ — they lie along the $k$-th diagonal running across the corner of the floor. A part of size $k$ in $k$ colours is a choice of one of those $k$ squares.

So MacMahon’s product can be rewritten as a product over the squares of the floor,

$$\prod_{k \ge 1} \frac{1}{(1 - q^k)^{k}} = \prod_{i \ge 1} \prod_{j \ge 1} \frac{1}{1 - q^{\,i + j - 1}},$$

and the right-hand side counts something simple: a choice of how many times to use each floor square, where using square $(i, j)$ once costs $i + j - 1$. The theorem is that these choices correspond one to one with piles of the same total. A bijection that does it was found by Abraham Hillman and Richard Grassl in 1976. It takes a pile and repeatedly removes a staircase-shaped strip of cubes that runs along the edge of the pile’s surface from one wall to the other, recording at each step the floor square where the strip turns; the strip always has exactly $i + j - 1$ cubes for that square, so the total is preserved, and the process can be run backwards. Each square of the floor thus contributes a geometric series, and the product over the floor is the count.

The same reading explains the boxes. Restrict the floor to an $a \times b$ rectangle and allow the stacks any height, and the product runs over the rectangle’s squares only; that is MacMahon’s box formula with the height $c$ sent to infinity, and the factors $(i + j + k - 1)/(i + j + k - 2)$ of the finite box are what the ceiling does to it. The weight $i + j - 1$ of a floor square is its hook length in the infinite corner — the number of squares in the hook formed by the square itself, the squares in its row beyond it towards the corner and the squares in its column — which is how the same idea reaches the counting of Young tableaux that a diagram turned on its side touched on, where the hook lengths of a single staircase divide $n!$ to give the number of ways to fill it.

Reciprocal cubes where the circle’s constant was #

The size of the ordinary partition count has a formula with a $\pi$ in it, which the size of a number with no formula traced to Hardy and Ramanujan: $p(n)$ is about $e^{\pi \sqrt{2n/3}} / (4n\sqrt{3})$. The plane partitions have a formula of the same kind, found by Edward Maitland Wright in 1931:

$$\mathrm{PL}(n) \sim \frac{\zeta(3)^{7/36}}{\sqrt{12\pi}} \left(\frac{n}{2}\right)^{-25/36} \exp\!\left(3\,\zeta(3)^{1/3} \left(\frac{n}{2}\right)^{2/3} + \zeta'(-1)\right).$$

The constant in the exponent is $\zeta(3) = 1 + 1/8 + 1/27 + \cdots$, the sum of the reciprocal cubes, and the constant $\zeta'(-1)$ in front is a value of the derivative of the same function.

Divided by Wright’s formula, the exact counts give a ratio that climbs steadily towards 1: $0.967$ at $n = 20$, $0.9888$ at 100, $0.9976$ at 1,000. The approach is from below and slow, like the leading term of Hardy and Ramanujan’s formula before its refinements; a series of corrections exists here too, and with it the ratio can be pushed much closer to 1, but the leading term already carries the whole of the growth.

The reason the constants change is a single calculation that both formulas share. The logarithm of Euler’s product near $q = 1$ is dominated by $\sum_k q^k/k \cdot 1/(1 - q^k)$, which behaves like $\zeta(2)/t$ when $q = e^{-t}$ — and $\zeta(2) = \pi^2/6$, the sum one plus a quarter plus a ninth evaluated, is where the $\pi$ of Hardy and Ramanujan comes from. MacMahon’s product has $k$ copies of each factor, so the same sum acquires an extra factor of $k$ in each term and behaves like $\zeta(3)/t^2$. A singularity of the form $1/t^2$ instead of $1/t$ is what turns $\sqrt{n}$ into $n^{2/3}$ when the coefficient is extracted, and its constant is what puts $\zeta(3)$ into the exponent. Nothing about $\zeta(3)$ is known as simply as $\zeta(2) = \pi^2/6$; Roger Apéry proved only in 1978 that it is irrational, and no closed form for it is known.

Piles that fit in a box #

MacMahon also counted the piles that fit inside a box: plane partitions with at most $a$ rows, at most $b$ columns, and no entry larger than $c$. Here the answer is a finite product, one factor for each of the box’s $abc$ cells:

$$M(a, b, c) = \prod_{i=1}^{a} \prod_{j=1}^{b} \prod_{k=1}^{c} \frac{i + j + k - 1}{i + j + k - 2}.$$

It is one of the most famous product formulas in combinatorics, and there is nothing in the definition of a plane partition to suggest that the count in a box should factor at all.

The figure counts the piles in cubical boxes by a transfer that needs no formula: list every possible row — a non-increasing list of $n$ heights between 0 and $n$ — and build the pile one row at a time, each new row standing in front of the previous one and nowhere taller. The counts are 2 for the $1 \times 1 \times 1$ box, 20 for $2 \times 2 \times 2$, 980 for $3 \times 3 \times 3$, 232,848 for $4 \times 4 \times 4$, 267,227,532 for $5 \times 5 \times 5$ and 1,478,619,421,136 for $6 \times 6 \times 6$, and MacMahon’s product gives every one of them exactly.

The growth is the surprise. A box of side $n$ holds $n^3$ cells, and a set of $n^3$ independent yes-or-no choices would number $2^{n^3}$. The piles number about $e^{0.785 n^2}$ — the logarithm of the count grows with the square of the side, with the box’s area rather than its volume. The figure divides the logarithm by $n^2$, using the formula alone beyond side 6, and watches it converge: $0.749$ at side 2, $0.778$ at 6, $0.7848$ at 80, against the limit $\tfrac{9}{2} \log 3 - 6 \log 2 = 0.78487$, which follows from the product by turning it into an integral. The reason is that a pile is determined by its surface. Inside the pile every cell is full and above it every cell is empty, so the only freedom is in the shape of the boundary between them, and the boundary is a surface of area about $n^2$.

That surface has another description. Seen from far along the diagonal of the box, the visible faces of the cubes are rhombuses of three orientations, and they tile a hexagon whose sides are $a$, $b$, $c$, $a$, $b$, $c$. Every pile gives a tiling of the hexagon by rhombuses and every such tiling comes from a pile, so MacMahon’s box formula also counts the lozenge tilings of the hexagon. The diamond that freezes its corners found the domino tilings of a diamond freezing into a fixed pattern near its corners; random lozenge tilings of a large hexagon do the same, frozen outside a circle inscribed in the hexagon and disordered inside it, which in the language of piles says that a random pile in a large box is flat against the walls and floor near the corners of the box and genuinely random only in the middle.

Every pile has a complement #

A pile in a box can be counted by its volume as well, and MacMahon’s product has a refinement in $q$ that does exactly that.

The volumes of the piles in a $4 \times 4 \times 4$ box run from 0 to 64. The distribution starts like the plane partition numbers themselves — 1 empty pile, 1 of one cube, 3 of two, 6 of three, 13 of four — because a small pile does not reach the walls of the box, and rises to a single peak of 11,408 piles at volume 32 before falling away in exact mirror image. The symmetry has a one-line reason. Fill the box with cubes, remove a pile of $v$ cubes from the corner, and what remains is a pile of $64 - v$ cubes pushed into the opposite corner, seen upside down. Every pile is paired with its complement, and so volume $v$ and volume $64 - v$ are equally common.

The coefficient that is a polynomial followed the same kind of symmetry in the $q$-analogues of the binomial coefficients, which count lattice paths by the area under them and are symmetric for the same reason: a path and its complement in the rectangle share the rectangle’s area between them. The box refinement is the three-dimensional version of that statement, and MacMahon’s $q$-product,

$$\prod_{i,j,k} \frac{1 - q^{i+j+k-1}}{1 - q^{i+j+k-2}},$$

is to piles in a box what the Gaussian binomial coefficient is to paths in a rectangle.

One dimension further, and the guess that failed #

The natural next step is a solid partition: a three-dimensional array of numbers that never increases along any of its three directions — or, as cubes, a pile in four dimensions. MacMahon guessed that the pattern of his products would continue. Ordinary partitions are counted by $\prod (1-q^k)^{-1}$, plane partitions by $\prod (1-q^k)^{-k}$, and the exponents $1, k$ look like the start of the binomial coefficients $\binom{k}{0}, \binom{k}{1}$; the next would be $\binom{k+1}{2} = k(k+1)/2$, and his guess was that solid partitions are counted by $\prod (1 - q^k)^{-k(k+1)/2}$.

A solid partition is a stack of plane partitions, each layer lying inside the layer beneath it entry by entry. That is how the figure counts them: every plane partition of size up to 12 is listed — 1,124 of them in all — and the number of ways to finish a stack whose top layer is a given plane partition, with a given number of cubes still to place, is computed once and remembered, since it depends only on that layer and that number. The counts for every $n$ up to 12 are 1, 1, 4, 10, 26, 59, 140, 307, 684, 1,464, 3,122, 6,500 and 13,426. The guess gives 1, 1, 4, 10, 26, 59 — correct for six values in a row — and then 141 where the true count is 140. From there the gap widens: 310 against 307 at 7, and 13,602 against 13,426 at 12, an overshoot of 1.31 per cent. The failure was found in 1967 by Arthur Atkin, Paul Bratley, Ian Macdonald and John McKay, by computing exactly these numbers, half a century after MacMahon proposed the guess.

There is no replacement. No product formula for solid partitions is known, and the evidence suggests none exists; their counts have been computed by heavy enumeration far beyond the range drawn here, and their growth is believed to be about $e^{c\, n^{3/4}}$ — the exponent rising again, from $1/2$ to $2/3$ to $3/4$ — with the constant $c$ known only from extrapolating those counts. The product that made the first two dimensions tractable is a coincidence of low dimension, and the six correct values were enough to persuade the best combinatorialist of his generation.

Still open: why the products exist #

MacMahon’s formulas have been proved many times, by methods that grew more powerful and more general: by symmetric functions, by Ira Gessel and Xavier Viennot’s method of non-intersecting lattice paths, which turns a pile in a box into a family of paths that never cross and its count into a determinant, and by bijections that match piles with coloured partitions. Each proof explains why one formula holds. What none has supplied is a single reason why so many counts of piles factor into products. Richard Stanley listed in 1986 ten classes of plane partitions in a box with symmetries — piles symmetric under swapping two walls, under rotating all three, under complementing, and combinations — and conjectured or collected product formulas for every one. The last of the ten counts was proved by John Stembridge in 1995, and a refinement of one of them by volume, conjectured by George Andrews and David Robbins, held out until 2011, when Christoph Koutschan, Manuel Kauers and Doron Zeilberger proved it with a computer-algebra calculation too large to check by hand. That the products exist is now settled; why they exist, in a way that would predict which other counts should factor and which, like the solid partitions, should not, is an open question about the whole subject. And the parity questions of is the partition count even half the time? can be asked of $\mathrm{PL}(n)$ as well, where they are just as open and have been studied far less.