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.
The page and the checks run the same sampler
(arctic-core.mjs). research/arctic-circle/verify.mjs confronts it 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. The first two are exact; the last
is a limit theorem, and it is checked as a seeded Monte-Carlo approach to the limit — never
dressed up as an exact finite-n equality.
§4 · 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 — the exact limiting placement densities inside the temperate zone.
- J. Propp, "Generalized Domino-Shuffling," Theoretical Computer Science 303 (2003), 267–301 — the weighted generalisation and a careful account of the algorithm.
§5 · 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.