A facet with no energy in it

How many arrangements one rule allows counts dimer coverings of a square region: a purely local rule, an enormous exact number, and a growth rate per site that is the useful quantity. This essay asks the same kind of question on the triangular lattice, where the answer is prettier and where something happens that the square case does not show.

The object is a stack of cubes.

One object under three descriptions #

Push unit cubes into the corner of a room, against two walls and a floor, so that no cube overhangs. The pile is completely described by the height of each column: an array π[i][j] of whole numbers, weakly decreasing along every row and every column, bounded above by however tall the box is. That is a plane partition in an a × b × c box.

Now look at the pile along the body diagonal of the cubes — the [111] direction, which is the direction a crystallographer looks down to see a close-packed layer edge-on. Each of the three cube-face orientations projects to a rhombus with sixty-degree angles, and the three rhombi are distinguishable by which way they lean. What is on the page is a tiling of a hexagon by three kinds of lozenge.

The hexagon does not depend on the pile. A pile in an a × b × c box always shows exactly ab + bc + ca faces, however the cubes are arranged, because raising a column hides a face of one orientation and exposes a face of another. So every pile in the box gives a tiling of the same hexagon, and the correspondence runs both ways: a lozenge tiling of the hexagon determines the heights, so it determines the pile.

There is a third description and it is the one that makes counting possible. Follow the boundaries between rhombi of two of the three orientations and they form a family of paths crossing the hexagon, never touching. Counting non-intersecting paths is a determinant, which is the Lindström–Gessel–Viennot lemma; counting them column by column is a transfer matrix. This essay uses the second, because a transfer matrix can be constrained cell by cell and a determinant cannot as easily, and constraining cells is what the second half of this needs.

The count, and the count again #

MacMahon found the number in 1916 and it is a closed form of startling simplicity:

N(a,b,c) = ∏ᵢ ∏ⱼ ∏ₖ (i + j + k − 1) / (i + j + k − 2)

with i running to a, j to b and k to c. Every factor is a ratio of small integers, the whole product is a whole number, and nothing about the derivation is visible in it. A one-cube box gives two — the empty pile and the single cube. A two-cube box gives twenty. A three-cube box gives nine hundred and eighty.

A formula that opaque is exactly the kind this collection refuses to quote, so it is computed here in exact integer arithmetic and computed a second time by a completely different route. The transfer matrix keeps one number per possible row of the array: the states are the weakly decreasing sequences of length b with entries in 0…c, and the transition from one row to the next is the condition that the second lies under the first. Building the array a row at a time and summing at the end gives the count with no formula in it at all.

They agree everywhere, and the agreement is a test rather than a formality: a version of the product with its indices shifted by one is also a ratio of integer products, also comes out a whole number, and gives eight instead of twenty on the smallest interesting box. A formula that produces integers is not thereby the right formula, which is why the check is against a second computation rather than against plausibility.

A symmetry the algorithm cannot see #

Before leaving the count there is one property of it worth pulling out, because it is a symmetry argument in a place where symmetry is not obviously present, which is the kind of thing this collection is about.

N(a,b,c) is symmetric in its three arguments. A box that is two by three by four holds exactly as many piles as one that is four by three by two, or three by four by two, or any of the six orderings.

From the hexagon that is nearly a triviality. The three numbers are the three pairs of opposite sides, and permuting them rotates the picture by a third of a turn or reflects it — operations the hexagon has, since its symmetry group is the twelve-element one. A tiling goes to a tiling, so the counts must agree. From MacMahon’s product it is also immediate, because i + j + k does not care in which order the three indices are supplied.

From the array of heights it is not obvious at all, and from the transfer matrix it is invisible. In that description the three numbers do completely different jobs: a is the number of rows the machine steps through, b is the length of each row, and c is the bound on the entries. The number of states the machine has to carry is the number of weakly decreasing sequences of length b with entries in 0…c, which is a binomial coefficient in b and c and does not mention a — so the six runs for one box’s six orderings hold different numbers of states and do different amounts of work. Sixteen of the twenty boxes up to four a side have runs of at least two different sizes.

So requiring the six to agree is a real test of the machine rather than a tautology about the code, and it is the third independent thing the count is checked against: a closed form, a shifted closed form that must disagree, and its own symmetry group.

This is the shape of a symmetry argument in general and it is worth naming. A symmetry of an object is a statement that two apparently different descriptions of it are descriptions of one thing, and the useful consequence is always that some quantity computed from the descriptions must come out the same. Here the object is the hexagon, the descriptions are the six ways of choosing which pair of sides is which, and the quantity is a count. That is exactly the pattern of counting what a group cannot tell apart, with the roles reversed: there the group is used to compress a count, and here a count is used to check that the group is really acting.

There is a small warning attached, and it is the same one that turns up whenever a symmetry is checked numerically. The array of heights breaks the hexagon’s symmetry: it singles out one of the three directions as “up” and the other two as the index ranges, so a picture drawn from the array looks three-fold symmetric at best and the six-fold symmetry of the hexagon is not visible in the data structure at all. That is a choice of description, not a property of the object, and it is the same phenomenon as a cell being a choice — the description has less symmetry than the thing described, and every conclusion has to be checked for whether it belongs to the object or to the spelling.

The average pile #

Here is what the square-lattice case does not show, and it is the reason this essay exists.

Because the count is exact, so is every conditional count. The number of piles in which π[i][j] is at least k is the same transfer matrix run with one cell restricted, so the probability of that event — over the uniform distribution on all piles in the box — is a ratio of two exact integers. Summing over k gives the exact expected height at that position, and the same data give the exact spread.

Doing it cell by cell would be a separate run per cell. There is a better way, and it is the standard one: a forward pass gives, for each row of the array, the number of ways to build everything above it, and a backward pass gives the number of ways to finish below it. Their product is the number of piles whose row i is exactly that row, and the distribution of every cell in every row falls out of one sweep.

The mean is not a smooth mound. It is nearly flat at the corner against the walls, nearly flat at zero at the far corner, and it falls steeply across a band in between. The spread tells the same story more sharply: small where the mean is flat, large in the band.

That is a facet meeting a rounded region. It is the shape of an equilibrium crystal — flat faces where the surface is locked to a lattice plane, curved regions between them — which which faces a crystal shows computes from surface energies by Wulff’s construction. Here there are no surface energies. Every pile is counted once, no configuration is preferred, and the shape comes out of the counting.

Why counting produces a shape #

The mechanism is worth stating because it is not obvious that counting should produce anything but a blur.

Near the corner against the walls, a pile is boxed in: the height is bounded above by the box and below by the ordering, and the two bounds nearly meet. There are very few ways for that corner to be anything other than full, so almost every pile has it full, and the average is dragged to the ceiling. The same happens at the far corner with the floor.

In the middle there is room, and the number of ways to be at any particular height is comparable across a range of heights. The average sits in the middle of that range and the spread is large.

So the flat regions are where the counting has no freedom and the rounded region is where it has plenty. The entropy is not uniform across the shape, and the shape is where the entropy is. That is the same statement as the physical one — a facet is a piece of surface with no configurational entropy and a rounded region is one with a lot — with the energy left out.

The boundary between the two regions has a name and a limit. As the box grows, the curve along which the spread collapses tends to the ellipse inscribed in the hexagon, touching each of its six sides — the arctic curve, from the arctic circle theorem for the Aztec diamond, which is the same phenomenon in the dimer setting the previous rung counted. What is computed here is the finite version: the spread at each position, for boxes up to six a side, and the fact that the corner settles while the middle does not.

Nothing in a finite box is frozen, and it matters to say so. Every cell takes every value in some pile — the empty pile and the full pile are both in the count — so an account claiming a corner is “always full” would be false as written. The correct finite statement is about spread, the limit statement is about a curve, and the module refuses the frozen version explicitly so that the essay cannot drift into it.

The entropy, and what it is per #

The count itself runs away: two, twenty, nine hundred and eighty, then six figures, nine, thirteen, and twenty-two digits by the time the box is eight cubes a side. A number like that is not informative on its own, and the quantity that is informative is the one the dimer essay uses: the logarithm per unit of the thing being arranged.

The per-rhombus figure rises through the small boxes and settles near a quarter of a nat. That it settles at all is the point: the number of arrangements grows exponentially in the area, so the entropy per rhombus tends to a constant, and a constant entropy density is what makes a random arrangement thermodynamically real rather than a curiosity.

This is where the argument touches quasicrystals, and it is worth being careful about how far it goes. The random-tiling picture of a quasicrystal says that a quasiperiodic structure need not be held together by matching rules that force it — which is what matching rules do — but can instead be stabilised at finite temperature by the entropy of a large family of nearly-equivalent tilings. A structure with a positive entropy density and a free energy minimised at a particular average orientation of the tiles is quasiperiodic on average without any tiling being forced.

The lozenge count is the cleanest exactly solvable member of that family. It is not itself quasiperiodic — a hexagon tiled by rhombi is a picture of a cubic crystal, not of a quasicrystal — but it is where the arithmetic of the picture can be done exactly, and the qualitative facts it establishes are the ones the general argument needs: that the entropy density is positive, that it depends on the average slope of the surface, and that a region of fixed slope can have zero entropy while its neighbour has a lot.

Three things this does not say #

It does not compute a free energy. Everything above weights every pile equally, which is the infinite-temperature limit with no interaction between cubes. A real crystal weights configurations by energy, and the shape it takes minimises free energy rather than maximising entropy. What this shows is that the entropy alone already produces a facet-and-rounded-region shape, so a facet is not evidence of an energetic preference — which is a warning rather than a result, and the same warning permission is not presence gives elsewhere.

It does not establish the arctic curve. The limit shape is a theorem — Cohn, Larsen and Propp’s, from 1998 — and this collection does not prove it. What is computed is the finite spread at each position, and the observation that the quiet region grows and sharpens. That is consistent with the theorem and is not a demonstration of it.

And it is one lattice. The three rhombus orientations come from the three cube-face orientations, which is a fact about the cubic lattice seen down [111]. The corresponding question on other lattices has other answers, most of them without a product formula, and the reason this case is exactly solvable is that the paths do not intersect — a structure that fails as soon as the local rule is anything more complicated.

What a crystallographer gets from a pile of cubes #

Two things, and the second is the one worth carrying.

The first is a worked example of a height function, which is the tool for turning a tiling problem into a surface problem. A lozenge tiling is a monotone surface; a dimer covering is a surface too, with a different slope convention; the ice-rule configurations of the arrangements a crystal keeps at absolute zero have one as well. Once a tiling has a height function, questions about the tiling become questions about the shape of a surface, and the exact statistics above are simply the statistics of that surface.

The second is a caution about reading shapes. A crystal that grows with flat faces and rounded corners looks like a crystal whose faces are energetically preferred, and often it is one. But the same shape comes out of a uniform count over configurations with no preference anywhere in it, because flatness is what a surface does where it has no room to fluctuate. Before attributing a facet to an energy, it is worth knowing that the entropy on its own can produce one — and this is the case small enough to see the whole of that happening.