The diamond that freezes its corners

Signs that make a determinant count turned the number of domino tilings of a board into a determinant, and found that the count of a large square board grows like a fixed number of choices per square: the number of tilings of an $n \times n$ board, raised to the power $1/n^2$, climbs towards $e^{G/\pi} \approx 1.3385$, where $G$ is Catalan’s constant. It climbed from below, because squares on the edge have fewer neighbours than squares inside, and the edge is a vanishing share of a large board. The boundary looked like a correction that disappears in the limit.

This essay is about a board where it does not disappear. Take the squares lying inside a diamond — a staircase of rows of lengths $2, 4, 6, \ldots, 2n, 2n, \ldots, 4, 2$ — and count its domino tilings. The answer is exactly $2^{n(n+1)/2}$, and since the diamond has $2n(n+1)$ squares, the number of choices per square is $2^{1/4} \approx 1.1892$ at every size. A square board of the same area has exponentially more tilings, and the gap does not close as the boards grow. The boundary, which is a vanishing share of the squares, decides the count of the whole. Hall’s condition is satisfied by both regions and says nothing about the difference; it is a question about how many matchings, not whether.

The picture is the reason. Every tiling of this diamond is equally likely to have been drawn, and nothing in the rule distinguishes the corners from the middle; yet the four corners are filled with solid brickwork, one orientation each, and the disorder is confined to a disc. The squares in the corners have, in effect, no choice at all. The rest of this essay is about why, about the procedure that drew the picture, and about the circle.

Eight tilings and a power of two #

The region is called the Aztec diamond, a name Noam Elkies, Greg Kuperberg, Michael Larsen and James Propp gave it in 1992 for the stepped outline of its edge. Its order-$n$ member has rows of lengths $2, 4, \ldots, 2n$ climbing to the middle and descending again, so it is the set of unit squares lying entirely inside the tilted square $|x| + |y| \le n + 1$.

Order 1 is a two-by-two block, with two tilings. Order 2 has twelve squares and eight tilings, all drawn in the figure. Order 3 has 64, order 4 has 1,024, and the sequence continues $2^{15}, 2^{21}, 2^{28}, 2^{36}, 2^{45}$. Each of those was computed the way the previous essay computed rectangles: the diamond is a flat bipartite graph with no holes, so the one-minus-sign-per-square rule applies, and the signed determinant counts the tilings. The figure’s counts are the determinants, and the powers of two are what they came out to. A determinant can count other things on the same kind of graph — spanning trees are the classical case — but the powers of two are particular to this region, and no determinant explains them by inspection.

The exponents $1, 3, 6, 10, 15, \ldots$ are the triangular numbers $n(n+1)/2$, so each diamond has exactly $2^n$ times as many tilings as the one before. Elkies, Kuperberg, Larsen and Propp gave four proofs that this holds for every order. One of them goes through alternating sign matrices — square arrays with entries 0, 1 and $-1$ whose non-zero entries alternate in sign along every row and column — and another, the one used to draw every random tiling in this essay, is a procedure that grows the diamond one order at a time by $n$ coin tosses. The count is then simply the number of ways the coins can fall, provided the procedure reaches every tiling once.

Fewer choices inside a different boundary #

The square board’s rate of 1.3385 choices per square and the diamond’s 1.1892 can be set side by side.

The two-by-two board is both the smallest square and the smallest diamond, so the two sequences start at the same point. After that they part. A square board of 36 squares already has 1.251 choices per square; the diamond of 40 squares has 1.1892. By 196 squares the square is at 1.311 and the diamond is still at 1.1892, as it is at every order. The difference is exponential in the area. In the limit the ratio of the rates is $1.3385/1.1892 \approx 1.126$ per square, and even at the finite sizes where the square board is still well below its limit, a square board of 1,024 squares has more than $10^{45}$ times as many tilings as a diamond of the same area would.

This is unlike most counting problems, where the shape of a large region matters only through its area. The number of ways to colour a region’s squares, or to place non-attacking pieces, is governed by what happens deep inside, and the boundary contributes a correction proportional to its length — negligible for a large region. Domino tilings are different because a domino links squares, and the links propagate: fixing the dominoes along one edge constrains the next row, which constrains the next, and on the right kind of edge the constraint runs all the way in. The staircase edge of the diamond is the right kind. Along it, Thurston’s height function — a number attached to each corner of the squares that records how the dominoes lean, introduced in the previous essay as the reason two-by-two turns connect all tilings — is forced to change as steeply as it ever can, and that steepness is passed inward until it runs out of force at the circle.

A procedure that draws a tiling by tossing coins #

To see the frozen corners one needs a way of choosing a tiling uniformly at random from $2^{820}$ of them, and listing them is out of the question. The method used for every random tiling here is domino shuffling, from the same 1992 paper.

Each domino carries a direction — north, south, east or west — determined by its orientation and by the colour of the square it starts on, and the four directions are the four colours in every figure. To pass from order $n-1$ to order $n$:

1. Place the old tiling in the centre of the larger diamond.
2. Delete every pair of dominoes that are about to slide through each other — a south-moving domino directly above a north-moving one, or an east-moving one directly left of a west-moving one.
3. Slide every remaining domino one square in its direction.
4. Fill the holes. What is left uncovered always falls into two-by-two blocks, and each block is filled with two horizontal or two vertical dominoes by tossing a fair coin.

That the holes are always two-by-two blocks, and that a sliding domino never lands on another or outside the diamond, is part of the theorem; the figures check both at every step of every tiling they draw. The step drawn in the figure deletes one colliding pair, slides four dominoes and creates eight in four new blocks.

Two things follow. If every tiling of order $n-1$ is equally likely before the step, every tiling of order $n$ is equally likely after it — the coins are fair and the correspondence between coins and tilings is exact. And the dominoes balance: a diamond of order $n$ holds $n(n+1)$ of them, so if a step deletes $d$ pairs and fills $c$ blocks, then $n(n+1) = n(n-1) - 2d + 2c$ and $c - d = n$ exactly. Each step makes $n$ more coin tosses than it undoes — one, then four, in the step drawn above — and following the coins backwards turns that into the factor $2^n$: the procedure is at the same time a sampler and a proof of the count. Before this essay relied on it, the sampler was run 80,000 times at order 2 and 128,000 times at order 3, and it produced each of the 8 and each of the 64 tilings within the fluctuation expected of a fair draw. One of the first versions failed that check — the frequencies at order 3 ranged from 0.58 to 1.65 times the fair share — and the fault lay in the pseudo-random numbers, not the procedure: a poor source of coin tosses, whose low bits repeat with a short period, was enough to bias the tilings. The check exists for exactly that reason.

The sampler is fast. Growing the order-40 diamond in the hero figure takes a few milliseconds, and order 200, with 40,200 dominoes, about a second. That is far faster than the alternative most random sampling uses, a wandering chain that visits states in proportion to their weight — repeatedly turning random two-by-two blocks of dominoes — which reaches the uniform distribution only after a long and hard-to-bound mixing time. Shuffling is exact after $n$ steps.

The frozen corners #

With a sampler in hand, the question of what a typical tiling looks like can be answered by looking. In the hero figure each colour is one of the four directions, and in each corner of the diamond one direction fills everything: horizontal bricks moving north at the top, south at the bottom, vertical bricks moving west and east at the sides. These are the brickworks forced by the staircase edges, extended as far inward as they go.

To make “frozen” a measurement rather than an impression, call a square frozen if every domino within two squares of it lies in the same direction as its own. On the order-100 tiling in the figure, 22.7% of the squares are frozen by that test. The circle inscribed in the diamond — the circle touching the middle of each side — leaves 22.2% of the diamond outside it. The two descriptions agree square by square on 97.2% of the diamond. The disagreement lies in a ragged band along the circle, a few squares wide, where the brickwork breaks up into disorder.

William Jockusch, James Propp and Peter Shor proved in 1995 that this is no accident of one sample: as the order grows, with probability approaching 1 the boundary between the frozen and disordered parts of a random tiling, rescaled to a diamond of fixed size, approaches the inscribed circle. They named it the arctic circle theorem — outside the circle the tiling is frozen; inside it, temperate.

The circle as the order grows #

A single sample at a single size cannot show convergence, so the figure below draws several at each of eight orders.

The share of the diamond outside the circle is a property of the region and converges to $1 - \pi/4 \approx 0.2146$: a circle inscribed in a square of side $s$ has area $\pi s^2/4$, a share $\pi/4$ of the square, and the diamond is a square turned on its corner. The frozen share is a property of the random tiling, and it comes to within two percentage points of the same number from above, since squares just inside the circle are very nearly frozen too and some of them pass the test. The disagreement between the two falls from 19% at order 10 to 2.4% at order 200.

That decline is slower than it might be. The band where frozen turns into disorder is a few squares wide at order 100 and does not get much wider at order 200, but it does get wider, and its width is known: Kurt Johansson showed in 2005 that the boundary fluctuates on a scale of $n^{1/3}$, with the fluctuations described by the same Airy process that governs the longest climb in a random shuffle of a deck. A band of width $n^{1/3}$ round a circle of radius proportional to $n$ covers a share $n^{1/3}/n = n^{-2/3}$ of the diamond, which goes to zero but slowly. At the four points where the circle touches the sides, the fluctuations are larger still, of order $n^{1/2}$, and the samples show the brickwork reaching furthest there.

A shape decided by a variational principle #

The circle is one instance of a general phenomenon. A random domino tiling of any large region has a limit shape: rescaled, its local statistics converge to a deterministic profile, in the way the Ferrers diagram of a random partition converges to a fixed curve. Henry Cohn, Richard Kenyon and James Propp proved in 2001 that the profile is the one that maximises an entropy integral over the region, subject to the boundary.

The quantity being maximised is the logarithm of the number of tilings, written as a sum of local contributions. Each patch of a tiling has a tilt — a measure of how far its dominoes lean towards one orientation, read from Thurston’s height function — and the number of ways of tiling a patch with a given tilt is about $e^{\sigma A}$ for an area $A$, with $\sigma$ depending only on the tilt. The entropy $\sigma$ is largest, $G/\pi$, when the tilt is zero, and that maximum is the 1.3385 choices per square of the large square board: a flat boundary lets the whole interior sit at zero tilt. It falls to zero at the extreme tilts, where only one brickwork is possible, and those are the frozen corners.

The diamond’s staircase edges force the extreme tilt along all four sides. The tiling cannot jump from there to zero tilt at once, because tilt is a slope and a slope that changes abruptly costs more entropy than it gains. The optimal profile therefore stays frozen out to a curve and then relaxes gradually towards zero in the middle; solving the variational problem for the diamond gives the circle. The total, frozen corners and all, averages out to exactly $\tfrac14 \log 2$ per square — the diamond’s $2^{1/4}$.

This also explains what the edge that is as big as the ball found from a different direction: whether a boundary matters is not decided by how big it is. Here the boundary is a vanishing share of the squares, and it fixes a fifth of the diamond and costs the whole region an exponential factor of its count, because the constraint it imposes is carried inward by the dominoes themselves.

Other regions, other curves #

The circle is specific to the diamond, and it is a rare case where a random growth’s limit is known exactly; the shape a random ball grows into under random travel times is not known for any natural law, though it is computed to be within a few per cent of a circle. For a hexagon tiled by lozenges — three orientations of a rhombus, the tiling that looks like a pile of cubes seen at an angle — the arctic curve is the ellipse inscribed in the hexagon, found by Cohn, Larsen and Propp in 1998. For other regions the curves are algebraic, and Kenyon and Andrei Okounkov showed in 2007 that for polygonal regions of the right kind they are always algebraic curves of a degree that the number of sides determines. A square board, the region of the previous essay, has no frozen region in the limit at all: its boundary admits zero tilt, and the interior takes it.

That gives a sharp way of saying what the two essays together measured. The count of tilings is a determinant on every flat region. How that determinant grows — 1.3385 per square, or 1.1892, or anything between — is decided by the boundary, through the entropy each tilt allows, and the decision is visible in a single random sample as the shape of its frozen parts.

Still open: the corners where the curve touches #

The arctic circle theorem describes where the boundary lies; much of what happens on it is understood only for special shapes. At a generic point of the circle the fluctuations are governed by the Airy process, but at the four points where the circle touches the sides of the diamond the frozen region pinches down to nothing, and the local behaviour there — described by a different limiting process, the GUE minor process — has been worked out for the Aztec diamond and for some lozenge tilings, not for domino tilings of general regions.

The variational principle also leaves the question of regions whose limit shapes have more than one disordered part, or have “gas” bubbles — regions where the entropy is positive but the tilings are rigid in a different way — which appear when the weights on the dominoes are periodic rather than uniform. The two-periodic Aztec diamond, with dominoes weighted in a checkerboard pattern of two values, has a frozen region, a disordered region and a third, smoother region inside; its boundaries and fluctuations have been computed exactly only in the last fifteen years, and for general periodic weights they remain an open problem.

What the coins could not see #

The procedure that drew every picture here used fair coins and no knowledge of the diamond’s shape beyond the rule for which squares are inside it. It never chose to freeze anything. That a fifth of the squares come out in solid brickwork is a fact about how many tilings there are of each kind, not about any preference built into the procedure: there are simply far more tilings with frozen corners than without, so many more that a uniformly random tiling has them with overwhelming probability. The count of $2^{n(n+1)/2}$, exact at every order, and the circle, exact in the limit, are the same fact seen from the two ends — the total number of choices, and where in the diamond they are made.