How many arrangements one rule allows

A crystal’s structure is usually reported as one arrangement of atoms per cell, and most of this collection is about what symmetry says of that arrangement. There is a second kind of question about the same object, asked when the arrangement is not unique: how many arrangements does the crystal’s own rule permit?

The rule taken here is the simplest one a lattice can impose. Every site is covered exactly once by an object occupying two neighbouring sites. The object is a dimer: a pair of sites taken together, which is a molecule lying across two positions, an ordered pair of unlike atoms in an alloy, or — on paper — a domino.

The counts are large and they are exact. Four by four has 36 arrangements. Six by six has 6,728. Eight by eight has 12,988,816, and the growth is exponential in the area, so the number itself stops being informative long before the region stops being small.

Three routes, required to agree #

The count is computed three ways, and the agreement is the point rather than the redundancy.

Enumeration. Walk the region cell by cell in reading order, carrying a mask of which of the next few sites are already covered. At each cell the choice is to be covered already, or to be covered now by a dimer reaching east or south. It is exact, and it becomes unusable at about a hundred sites.

A product of cosines. Kasteleyn, Temperley and Fisher’s formula gives a rectangle’s count as a product over two indices of a cosine expression, taken to the power of a quarter. It is a product of irrational numbers that comes out an integer, and it takes no time at all.

A determinant. Sign the edges so that every square face carries an odd number of minus signs — horizontal edges positive, vertical ones multiplied by i — and the count is the square root of the determinant of the resulting matrix. This is what the product formula is a diagonalisation of.

Kasteleyn’s signing is the interesting one. The count of coverings is a permanent, which nobody knows how to compute quickly; the determinant is the same sum with signs attached to its terms. What Kasteleyn found in 1961 is that on a planar lattice the edges can be signed so that all those term-signs come out the same, at which point the permanent and the determinant coincide and the count becomes a polynomial-time computation. The condition is that every face carry an odd number of minus signs, and it fails as soon as the graph stops being planar.

The growth per site #

Since the count grows with the area, the quantity that survives to the infinite lattice is the count to the power of one over the number of sites.

For the square lattice that limit is

$$e^{G/\pi} = 1.33851\ldots,$$

where G is Catalan’s constant. It is a strange thing to find in a combinatorial count and it is exact: it comes from the double integral the product formula becomes as the region grows.

A rule leaving this many arrangements has left no structure at all, and that is what the number is for. Nothing about the rule prefers any direction, any position or any pattern; the arrangements are not a symmetry-breaking of some ordered ground state; and the logarithm of the count per site is the quantity a calorimeter reads as entropy. That connection is the subject of the next rung, where the rule is the one ice obeys and the count is measured with a thermometer.

What the profile method is actually doing #

The enumeration deserves a sentence of its own, because it is the reason numbers of this size can be exact.

Walking the region cell by cell, the only thing that matters about everything already placed is which of the next few sites are covered. Nothing else about the arrangement can influence what comes later. So the arrangements are grouped by that state — a mask a little wider than the region — and the count is carried along in groups rather than one at a time.

The consequence is a computation whose cost grows with the area times two to the width, rather than with the number of arrangements. Twelve million coverings of an eight by eight board are counted without any of them being visited, which is what makes an exact answer available at all.

It is the same move as the transfer matrix in one dimension, and the same move that makes a group’s orbit computable without listing the orbit. The state carried forward is a boundary, and the whole art is noticing how little of the past a boundary has to remember.

Where a count is zero, and the cheapest proof #

Two cases are worth having, because they are how a count of this kind is checked against something other than itself.

An odd region has no arrangement at all — the same parity bookkeeping a lattice uses on its own translations —: dimers cover two sites each, so an odd number of sites cannot be covered. The enumeration reports zero and does not need to be told.

More interesting is a region with an even number of sites and no arrangement. Colour the lattice like a chessboard. Every dimer covers one square of each colour, so a region whose two colour classes differ in size has no covering whatever, however even its total.

An invariant that settles a question without searching is the cheapest kind of impossibility proof, and this collection meets the pattern repeatedly — parity refusing a glide two mirrors, a trace refusing a five-fold rotation, a determinant refusing a hand. The mutilated chessboard is the same move in a subject with no group in it.

The Aztec diamond, where the count is a power of two #

One region has the cleanest count in the subject. The Aztec diamond of order n is the staircase region of 2n(n + 1) sites lying within a diamond, and its number of coverings is exactly

$$2^{n(n+1)/2}.$$

Two, eight, sixty-four, one thousand and twenty-four, and so on. The formula is due to Elkies, Kuperberg, Larsen and Propp in 1992, and it is verified here by enumeration up to order six — 2,097,152 arrangements, counted rather than quoted.

The arctic circle, which arrives out of nothing #

The arrangements of a diamond are not statistically uniform, and the way they are not is the most striking thing in this essay.

Computing, for each possible domino, the fraction of arrangements containing it produces four corners where the answer is close to one and a central region where it is close to a half. The boundary between them is a circle — inscribed in the diamond, tangent to its four sides.

Nothing put the circle there. The rule is uniform, the region has no circle in it, and the arrangements are counted with no weighting whatever. What produces it is the counting alone — the overwhelming majority of arrangements have frozen corners, because a corner has so few ways of being anything else.

The result is Jockusch, Propp and Shor’s, from 1995, and its name is the arctic circle theorem: as the order grows, the fraction of the diamond that is frozen tends to 1 − π/4.

Nothing is frozen at any finite size #

The word frozen needs care, and the exact statement is better than the picture.

Asking a finite diamond which of its dominoes are certain — present in every arrangement — gives the answer none, at every order. The domino in the extreme corner occurs in a fraction

$$1 - 2^{-n}$$

of the arrangements: a half at order one, sixty-three sixty-fourths at order six, and never one. The corner is settled in the overwhelming majority of arrangements and is not settled.

So the arctic circle is a statement about a limit and not about any diamond that can be drawn, and the exact form of the approach is more informative than the limit is. It also says where the boundary is soft: at order six the transition from nearly-certain to nearly-even occupies a band several sites wide, and calling any particular site frozen requires a threshold nobody put in the problem.

That distinction is the same one this collection draws about the golden ratio in an aperiodic tiling and about the growth per site above, and it is worth naming as a habit rather than met three times as a caution. A limit is a statement about a sequence; a figure shows one term of the sequence; and a caption that reports the limit as though the term exhibited it has said something the picture does not support. The honest form is always available and is usually more interesting — here it is $1 - 2^{-n}$, which says not merely that the corner freezes but how fast, and doubling the certainty at every order is a sharper fact than the circle.

And the softness has a scale, which the limit also hides. The band over which the domino probabilities fall from nearly one to nearly a half widens as the diamond grows — like the square root of the order rather than staying a fixed number of sites — so the boundary is sharp only relative to the diamond, and never sharp in the way a boundary between two states of matter looks in a picture. A reader shown the order-six map and told “the corners are frozen” would reasonably infer a wall, and there is no wall at any size.

What this count is not #

Two distinctions, and the first is the one that separates this rung from the anchor next door.

This is not counting up to symmetry. Counting what a group cannot tell apart divides arrangements into orbits and counts the orbits, using an average of fixed points; the answers there are smaller than the raw counts and the whole difficulty is the short orbits. Here there is no group and no quotient: two arrangements differing by a translation are two arrangements. The two counts answer different questions and neither is a correction of the other.

And a count is not a probability distribution. Saying that a domino appears in a certain fraction of arrangements is a statement about counting them equally, which is a choice. A physical system at a temperature weights arrangements by energy, and nothing in this essay does. The uniform weighting is the natural one for a rule rather than a material, and it is stated rather than assumed silently.

The two extremes of the same measurement #

It is worth putting the numbers side by side. On a region of N sites, a rule with a unique solution gives one arrangement and a growth per site of exactly one. Sites chosen freely give two to the N, and a growth of two. The dimer rule gives 1.3385 per site — a long way below free, and infinitely far above unique.

That middle band is where every disordered crystal lives, and the number is the honest measure of how much a local rule has decided. It is also the reason the rule cannot be strengthened casually: a rule allowing 1.0001 arrangements per site still allows more arrangements on a mole of sites than there are atoms in the universe, and a structure determination reporting one of them would be reporting a choice rather than a fact.

Where the rule comes from, in a real crystal #

Nothing in the arithmetic needs a material, but the rule is not invented. Three situations produce it.

A molecule occupying two sites. A diatomic unit lying flat on a lattice of adsorption sites covers two of them and cannot overlap another, which is the dimer problem exactly — and it is the situation Kasteleyn and Fisher were computing for.

An ordered pair in an alloy. In a binary alloy where unlike neighbours are strongly preferred, each atom must be paired with an unlike neighbour, and the pairings are dimer coverings of the lattice.

A bond that must be somewhere, which is the ice rule with four bonds instead of one. In a structure where each site carries one bond and each bond joins two sites, the bonds form a covering. That is the shape the ice rule takes with four bonds instead of one, and it is the reason these two rungs sit on the same anchor.

In each case the count is the number of arrangements consistent with what a diffraction experiment would report, and the experiment reports the average over all of them — which is a single symmetric structure with fractional occupancies and no arrangement in it at all.

The three situations differ in one respect that the count cannot see, and it decides whether the count means anything physical. Counting arrangements equally is right when they all cost the same. The adsorbed-molecule case comes closest: a diatomic unit lying on one pair of neighbouring sites has the same energy as on any other, so the arrangements really are equiprobable and the entropy really is the logarithm of the count. The alloy case is close but not exact — a pairing has second-neighbour environments that differ slightly, so the arrangements are nearly degenerate rather than degenerate. And a bond that must be somewhere is the case where the degeneracy is a genuine theorem about the local rule rather than an approximation, which is why the ice rule and not the alloy is the standard example.

Where the arrangements are not degenerate, the count remains an upper bound and stays useful as one. A rule permitting $1.3385^N$ arrangements permits no more than that however the energies fall out, so the count bounds the residual entropy from above and bounds what a structure determination can possibly have determined. That is the reading to keep: the count says how much room the rule left, and the energies say how much of that room is occupied.

Who counted it #

Pieter Kasteleyn and, independently, Temperley and Fisher solved the dimer problem on the square lattice in 1961, in a physics literature interested in the statistical mechanics of adsorbed molecules. The signing trick is Kasteleyn’s and it is one of the small number of exactly solvable models in two dimensions, alongside Onsager’s Ising solution.

The Aztec diamond and its power of two came thirty years later, from a combinatorics that had no physical motivation at all, and the arctic circle a few years after that. The two literatures met in the middle: the dimer model is now the standard example of a system whose fluctuations are exactly computable, and the frozen-region phenomenon has been found in growth models, in random matrices and in the corner shapes of crystals grown from solution.

Why the determinant works only in the plane #

Kasteleyn’s signing is described above as the interesting route, and the reason it is interesting is not that it is clever. It is that no comparable method exists one dimension up, and the difference is a theorem rather than a gap in anybody’s ingenuity.

Counting coverings is computing a permanent — the determinant’s formula with all the minus signs removed. Determinants are cheap and permanents are not: computing a permanent is #P-complete, which is the counting analogue of NP-completeness and is if anything a stronger statement of difficulty. So a general dimer count is out of reach.

Kasteleyn’s contribution is that a planar graph can be signed so that its permanent becomes a determinant. The signing exists because a planar graph has faces, and the condition — an odd number of negative signs round each face — can be satisfied consistently exactly when the graph can be drawn without crossings. Once it is, the count is a determinant and the whole apparatus of linear algebra applies, which is where the product of cosines comes from.

In three dimensions there is no such signing, and there is no such formula. The dimer count on a cubic lattice has no closed form, its growth rate per site is known only numerically, and the problem is believed to be genuinely hard rather than merely unsolved.

That is worth carrying, because it inverts the usual expectation. The plane case here is not the easy instance of a general result; it is a special case that works for a reason — planarity — which the interesting physical case does not have.

The surface underneath the circle #

The arctic circle looks like something imposed on the picture, and there is a change of description in which it stops looking that way.

A dimer covering of a planar bipartite lattice can be turned into a height function: assign a number to each face, with the rule that crossing an edge changes the height by a fixed amount depending on whether a domino lies across it. The rule is consistent — going round any vertex returns to the starting height — and it is reversible, so a covering is a height function and counting one counts the other.

Under that translation the arrangements become discrete surfaces over the region, all with the same boundary values, and counting them equally is choosing a random surface. A random surface over a fixed boundary has a limit shape, and the shape is the solution of a variational problem: it is the surface minimising a certain energy, which is a statement of exactly the kind that produces smooth curves.

The arctic circle is where that limit surface stops being curved and becomes flat — a facet — and the four corners outside it are the four facets the boundary conditions force. So the circle is not a feature of dominoes at all; it is the edge of a facet on a minimal surface, and its being a circle is a consequence of the particular boundary the diamond imposes.

That explanation is worth having because it says what changes when the region does. A different region gives a different limit shape with different facets and a different boundary curve, and the curve is a circle only for the diamond. Nothing in the rule prefers circles.

Where the ladder goes next #

Straight to the case where the count is measurable. The arrangements a crystal keeps at absolute zero is the same computation with the ice rule in place of the dimer rule, where the growth per site is an entropy that a calorimeter reads and Pauling’s one-line estimate of it is out by two and a half per cent — a correction the exact count supplies.

The other direction is the one this field is named for. A count this large is the opposite of order without repetition: a quasicrystal has one arrangement and no period, and a dimer covering has no order and every arrangement. Between them sits everything a real material does, and the two extremes are worth having exactly because they are the ends of the same axis.