Random tilings · order out of pure chance
The Arctic Circle
Cover a diamond-shaped board with dominoes — and make every possible covering equally likely, each choice decided by a fair coin. Do it once on a small board and it looks like nothing. Do it on a large board and a shape appears that no one put there: the four corners freeze into solid walls of aligned tiles, the middle stays a churning jumble, and the border between them is a circle — the same circle every single time, of radius n/√2. A perfect circle, made of coin flips.
Every choice inside the shuffle is one fair coin, yet the outline holds. Nudge n upward and watch the four corners sharpen and the boundary tighten onto the circle. Toggle it off to see there is genuinely nothing drawn there — only where the tiles decide, on their own, to stop agreeing.
§1 · THE BOARDA diamond, a domino, and a coin for every choice
The board is the Aztec diamond of order n: a staircase diamond of 2n(n+1) unit squares — two squares in the top row, widening to 2n across the middle, narrowing back to two at the bottom. A domino covers two neighbouring squares. There are many ways to tile it — and the point is that we pick one uniformly at random, every legal tiling exactly as likely as every other.
Elkies, Kuperberg, Larsen & Propp proved in 1992 that the order-n diamond has exactly 2n(n+1)/2 tilings — a clean power of two, checked here against a brute-force count for n ≤ 6. The number is astronomical almost immediately (the observable universe holds about an 80-digit number of atoms), and the shuffle you just ran drew one of them with every one of the others equally likely.
§2 · THE SHUFFLEHow a run of coin flips builds a tiling
Choosing uniformly among a 600-digit number of tilings sounds impossible — you cannot list them. The trick, domino shuffling (Elkies–Kuperberg–Larsen–Propp 1992), never does. It grows the diamond one ring at a time, and at each ring three things happen, in order:
Destroy — any two dominoes sitting face-to-face, poised to collide, are removed. Slide — every surviving domino takes one step in the direction it points (horizontals move up or down, verticals move left or right). Create — the empty 2×2 squares left behind are each filled by one fair coin: heads makes them a pair of horizontals, tails a pair of verticals. That single coin, in every hole, on every ring, is the only randomness — and a short counting argument (Jockusch–Propp–Shor) shows it is exactly enough to make all 2n(n+1)/2 tilings equally likely.
Press Grow from nothing above and you are watching precisely this: the diamond widening ring by ring from a single 2×2 square, the corners settling into place first and the border resolving, out of nothing but coins, into the circle.
§3 · THE CIRCLEThe boundary no one drew
Here is the theorem, and it is genuinely strange. Fix any tolerance you like. Then for all large enough n, all but a vanishing fraction of tilings have their frozen region bounded by a curve that hugs, to within that tolerance, the circle inscribed in the diamond — radius n/√2, tangent to the four sides at their midpoints. This is the Arctic Circle Theorem (Jockusch, Propp & Shor, 1998): outside the circle the tiling is frozen — one repeating brick-wall pattern, deterministic; inside, the temperate zone, all four orientations coexist and every fair coin still matters.
Run many shuffles at a given size and average. A cell deep in a corner is covered by the same type in every sample (probability 1 — frozen); a cell in the middle is a toss-up. The boundary where certainty gives way traces the circle. Because the transition has a small finite-n width, the measured radius sits a hair off n/√2 and the fit tightens as n grows — the honest fingerprint of a limit.
1/√2 = 0.70710… for the radius; and since the circle fills π/4 of the diamond's area, the frozen corners tend to 1 − π/4 = 0.21460… of it. Two clean constants, and neither was anywhere in the rules. All that was ever specified was every tiling equally likely; the circle, and π itself, are what that assumption looks like from far enough away.
§4 · THE FIELDThe circle was only the edge
The theorem in §3 tells you where the freeze ends — a circle — and nothing about the churn inside it. But there is more, and it is exact. Two years before the arctic circle was proved, Cohn, Elkies & Propp (1996) worked out the whole interior: at every point of the temperate zone, the exact limiting proportion of each of the four orientations. Not a circle bolted onto a jumble — a smooth field of odds, defined everywhere, of which the circle is merely the contour where the odds run out.
Write the position as (x,y) with the diamond scaled to |x|+|y| ≤ 1, so the arctic circle is x²+y² = ½. The chance that the domino covering a spot points north (gold, the top corner's type) is, in the limit,
PN(x,y) = ½ + 1⁄π · arctan( (2y−1) ⁄ √(1 − 2x² − 2y²) )
and south, east, west are the same formula turned a quarter-turn: PS(x,y)=PN(−x,−y), PE(x,y)=PN(−y,x), PW(x,y)=PN(y,−x). At the dead centre all four read ¼ — a fair four-way toss. Now watch the square root. On the arctic circle 1 − 2x² − 2y² hits zero, the fraction inside the arctan blows up, and PN snaps to 1 in the north cap and 0 everywhere else on the rim. The arctic circle is not a separate fact — it is the exact level set where this one smooth field saturates. Where the odds reach a certainty, the ground freezes.
Colour every spot by the four odds at once: full gold where a north tile is certain, full red / blue / violet in the other three caps, and a smooth blend of all four through the middle (dead centre is the muddy even mix). Predicted is the Cohn–Elkies–Propp formula drawn straight. Measured is the same picture built the only honest way — from a stack of real random tilings, the very same shuffler as up top. Flip between them: inside the circle they are the same picture. An approaches a circle became a matches an exact field, everywhere inside it. The rms the panel reports scores the exact field against the tally averaged over small position-bins — a single cell is one coin out of the stack and far too noisy on its own, but the density is a large-scale fact, so the fair question is whether it holds patch by patch.
The single-type views make the saturation plain: pick north and the field is bright only in the top cap and fades to nothing by the rim, the bright region's edge sitting exactly on the circle. The measured picture is coarser (it is a finite board of n, not the infinite limit) and a little grainy in the corners, where a single stubborn tiling can still disagree — but across the interior the exact odds and the honest tally land on top of each other, to within the rms the panel reports.
The page and the checks run the same sampler
(arctic-core.mjs) and the same exact field (cep-density.mjs).
research/arctic-circle/verify.mjs confronts the sampler with, in order: the
exact tiling count 2n(n+1)/2 by an independent
brute-force enumeration (n ≤ 6); the uniformity of the
shuffle by a χ² test over every tiling (n = 1,2,3 — all
64 tilings of order 3 equally likely); the corner structure
(each frozen corner one type, the centre all four); and the circle — radius fitted to
n/√2 with a residual that shrinks with n, and the
frozen fraction descending toward 1 − π/4. Then
research/arctic-circle/verify-density.mjs settles the field of §4: it checks the four exact
densities sum to 1 and read ¼ at the centre, that
PN saturates to 0/1 on the circle, and —
the real test — that the Cohn–Elkies–Propp formula matches the sampler across the whole
interior (rms ≈ 0.012 over hundreds of position-bins), with the
north/south/east/west assignment shown to be the unique best fit among all
24 relabellings. The counts and the centre value are exact; the circle and the
field are limit facts, checked as seeded Monte-Carlo approaches to the limit — never dressed up
as exact finite-n equalities.
§5 · REFERENCESSources
- N. Elkies, G. Kuperberg, M. Larsen & J. Propp, "Alternating-Sign Matrices and Domino Tilings (Parts I & II)," Journal of Algebraic Combinatorics 1 (1992), 111–132 and 219–234 — the domino-shuffling algorithm and the exact count 2n(n+1)/2.
- W. Jockusch, J. Propp & P. Shor, "Random Domino Tilings and the Arctic Circle Theorem," arXiv:math/9801068 (1998) — the north/south/east/west formulation used here, and the arctic circle of radius n/√2 (convergence in probability).
- H. Cohn, N. Elkies & J. Propp, "Local Statistics for Random Domino Tilings of the Aztec Diamond," Duke Mathematical Journal 85 (1996), 117–166 (arXiv:math/0008243) — Theorem 1, the exact limiting placement density PN(x,y)=½+1⁄πarctan((2y−1)/√(1−2x²−2y²)) inside the temperate zone, drawn live in §4.
- J. Propp, "Generalized Domino-Shuffling," Theoretical Computer Science 303 (2003), 267–301 — the weighted generalisation and a careful account of the algorithm.
§6 · NEARBY GROUNDWhere else order falls out of chance
Another sharp threshold hiding in pure randomness: open each site of a grid with probability p, and at one exact p a spanning cluster appears. Both pages are about a crisp geometric fact — a circle, a critical density — emerging from independent coin flips with no crispness in them. Turing Patterns →
Spots and stripes that no one places, formed because two diffusing chemicals go unstable together. Here the pattern is a frozen brick wall bounded by a circle; there it is an emergent wavelength — both are structure that is a property of the rule, not of any choice inside it. The Sandpile →
Drop sand grain by grain and a fractal of hard geometric regions self-organises, with sharp boundaries no one drew. The Abelian sandpile and the Aztec diamond are cousins: local rules, global shapes, and a limit picture that is exactly computable.