How many patches of each size

A Sturmian sequence has exactly n + 1 blocks of length n — the smallest a non-periodic sequence can have, and the sharpest available statement of what “ordered without repeating” means in one dimension.

The two-dimensional version of the same measurement is a count of patches: how many different neighbourhoods of a given size a tiling contains. It has no theorem as clean as n + 1 attached to it, and it separates the three kinds of order just as decisively.

The measurement #

The definition has to be pinned down before the counts mean anything, because there are several reasonable ones and they give different numbers.

A patch of radius r about a vertex is the set of vertices within r of it, written relative to that vertex. Two vertices have the same patch when those sets agree. The radius is quoted in edge lengths, so the measurement does not depend on how far the tiling has been inflated — each inflation divides the edge by the golden ratio, and quoting radii in edges is what makes two sample sizes comparable at all.

Count the distinct patches at each radius, and:

A periodic tiling has one patch type. Every vertex of a triangular lattice has the same surroundings as every other, at every radius, for ever — that is what periodicity means when it is said in terms of neighbourhoods. The count does not grow because there is nothing for it to grow into.

Random points have almost as many patches as patches. No two neighbourhoods coincide, so the count runs up to the number examined and saturates only because the sample runs out. It does not quite reach it, and the shortfall is worth a sentence: forty-seven of the 2,134 centres have no neighbour within one edge length at all, so their patches are all the same empty one and they collapse into a single type. That is the only coincidence in the whole random row, and it is an artefact of the radius rather than any order in the points.

A Penrose tiling has 62 at radius one, 82 at one and a half, 184 at two. The count grows without bound and stays far below the number of patches examined — three thousand vertices produce a few hundred kinds.

That is the two-dimensional statement of order without repetition: endlessly various, and not arbitrary. A crystal is the degenerate case at one end and a gas is the degenerate case at the other, and everything this collection’s aperiodic essays are about lives in the space between them.

The check the measurement needs most #

A patch census on too small a sample returns the number of centres and looks exactly like a result. So it is run twice, on two patch sizes.

At radii one, one and a half and two the two samples agree exactly — 62, 82 and 184 — so those numbers describe the tiling. At radii three and four the larger patch finds more, so those are lower bounds and are quoted as such.

Only the settled rows are measurements. The unsettled ones are the sample speaking, and the difference is invisible without the second run.

Reading the three rows #

The table is worth going along slowly, because each row is a different kind of object and the differences are the point.

One, at every radius. The periodic control’s row is the flattest possible line, and it is worth noticing that it is not merely small but constant. A periodic tiling with several vertex orbits would have a count equal to the number of orbits, again constant. What periodicity means, in this language, is that the complexity is bounded — and that is a theorem in one dimension (Morse and Hedlund: a sequence is eventually periodic exactly when its complexity is bounded) whose two-dimensional analogue is a famously open problem.

Sixty-two, eighty-two, a hundred and eighty-four. The Penrose row grows and the growth accelerates with radius, which is what a polynomial of degree two does.

Two thousand and eighty-eight, immediately. The random row’s first entry is within forty-six of the 2,134 centres examined, so the count has saturated at radius one and there is nothing left for it to measure. That is what makes it the right control: it fails at the smallest radius rather than eventually. The forty-six missing types are the forty-seven isolated points described above, which share one empty patch between them and so cost forty-six. At radius one and a half the row reaches 2,134 exactly and stays there for every larger radius — a count of the sample, and not of anything in it.

Reading the three rows together is what the table is for, and reading any one of them alone is misleading. The periodic row alone says only that a lattice is dull. The random row alone says only that a computer can generate distinct neighbourhoods, which nobody doubted. What is worth knowing is that the middle row is not near either of them and is not near the midpoint between them either: at radius two it stands at 184 against a bound of one on one side and 2,134 on the other, which is under a tenth of a percent of the way across. The interesting object is very much closer to the crystal than to the gas, and that is the quantitative form of a statement the pictures on this page make only qualitatively. It is also why the growth rate matters more than any single entry — 184 is small, and the fact that it will pass any bound eventually is what rules out a crystal, while the fact that it does so polynomially is what rules out a gas.

The gap between the second and third rows is the whole subject. A Penrose tiling has vastly more structure than a crystal and vastly less freedom than a random arrangement, and the census is the shortest way to make that quantitative.

Nickel’s eight vertex types #

The number at radius one has a classical name, and comparing them is instructive.

A Penrose rhomb tiling has eight distinct vertex configurations — the arrangements of rhombs that can meet at a point, traditionally named after the shapes they make: sun, star, ace, deuce, jack, queen, king and the two-tile one. That is a count of tile arrangements up to rotation.

The census here reports sixty-two at radius one, which is a different number for two reasons that are both worth stating. Rotations are not divided out, and the tiling’s ten orientations multiply most types accordingly. And a patch of radius one edge is not a vertex configuration: it contains the neighbours at distance one, which in a rhomb tiling is not the same set as the corners of the tiles meeting at the vertex — a rhomb’s short diagonal is under one edge and its long one is over.

Sixty-two is a measurement of a stated thing and eight is a measurement of a different stated thing. Neither is the “right” count, and the reason to say so is that the temptation to reconcile them is strong and reconciling them requires changing what is being counted.

Why it grows, and how fast #

The growth has a reason and the reason is the inflation.

A Penrose tiling is built by subdividing tiles and rescaling, and a patch of radius r in the inflated tiling is decided by a patch of radius about r/φ in the one before. So the number of patch types at radius r is bounded by the number at r/φ times a constant, which makes the growth polynomial rather than exponential — the count of patch types in a self-similar tiling grows like r², the same order as the number of vertices a patch contains.

That is the two-dimensional analogue of the linear growth of a Sturmian sequence’s complexity, and the exponent has the same meaning: the complexity grows like the volume of the patch, so the number of patch types per unit area is bounded. A random set fails that — its complexity grows like the number of centres, which is the sample size — and a periodic set is the degenerate case where the growth is zero.

This collection has the one-dimensional versions of all three: Sturmian at n + 1, a periodic word at a constant, and a random word at 2ⁿ.

What a physicist gets from the number #

The count is not only a classification device. Two of its consequences are experimental.

A finite number of local environments means a finite number of atomic sites. In a crystal there are as many kinds of site as the Wyckoff positions allow — a handful — and every atom of a given kind sits in an identical environment, which is why a crystal has sharp spectroscopic lines. In a quasicrystal there are many kinds of environment and their number grows with the radius considered, so the local environments are various and the spectroscopic lines broaden. The census is a prediction about linewidths.

And a bounded number per unit area means the variety is not disorder. A glass also has many local environments, and its number grows like the sample size — the random row. A quasicrystal’s does not. That distinction is what “quasicrystal” means in the laboratory as opposed to on paper, and it is measurable by exactly this count applied to a real structure model.

The practical difficulty is that the census needs the structure, and getting the structure is the hard part. What an experiment supplies is the diffraction pattern, and the route from there to a patch census runs through a structure solution.

What it does not say #

Three things this measurement is regularly asked for and does not give.

It does not prove aperiodicity. A count of patch types being large is consistent with a very large period. What proves a Penrose tiling non-periodic is the inflation argument — a translation symmetry would survive inflation and shrink without bound — and no census can substitute for it.

It does not distinguish two tilings of the same kind. All Penrose tilings of a given type have the same patches: any patch appearing in one appears in every other, which is the local indistinguishability that makes “the” Penrose tiling a reasonable phrase for uncountably many different tilings. So the census is a measurement of the family and cannot tell its members apart.

It does not settle how much of a patch is needed to locate a vertex in the tiling. A related and sharper question is whether some finite radius pins down a vertex’s position in the tiling completely — and the answer is no, for the same reason as local indistinguishability: every patch, however large, occurs in infinitely many places. That is repetitivity, and it is the statement the census’s growth is compatible with rather than a consequence of.

And it says nothing about diffraction. A tiling can have low complexity and diffuse scattering, or high complexity and sharp peaks; what decides that is the inflation factor being a Pisot number, and complexity does not see it.

The one-dimensional shadow of the same question #

Everything above has a one-dimensional counterpart in this collection, and the shapes line up exactly.

The plane’s version has no n + 1. There is no known analogue of the Morse–Hedlund theorem in two dimensions — whether a bounded patch complexity forces periodicity is open, and is called Nivat’s conjecture. Partial results exist for small bounds and the general statement is not known.

That is a genuinely unusual position for this collection to be in. Almost every count here is settled: seventeen groups, thirty-two classes, eleven tilings, five solids. The two-dimensional complexity question is one where the obvious statement is not known to be true, and the measurement above cannot help with it — a census reports what a tiling has, and the conjecture is about what a bound would force.

What the round trip checked, and how #

The periodic control must have a bounded count. A triangular lattice has one patch type at every radius, and if the measurement reported otherwise it would be measuring floating-point noise rather than geometry.

The Penrose count must exceed the periodic one, at the largest radius measured, or the measurement is not separating the cases it exists to separate.

Some radius must settle between the two sample sizes, or nothing measured is a property of the tiling.

Only vertices well inside the disc may be centres. A patch that runs off the edge of the sample is a patch of the sample, and admitting one inflates every count — most of all the periodic control’s, whose interior patches are so few that a single boundary patch would double its number. The margin is subtracted before any counting happens.

And the random control must saturate, which is the positive control at the other end: a measurement that could not distinguish random points from a tiling would be reporting nothing.

Where the exactness stops #

This measurement has a tolerance and it is the only one in this essay’s machinery. The Penrose vertices are produced by repeated floating-point inflation, so two coordinates that should be equal differ in the last bits; patches are compared after rounding to four decimal places in units of the edge. That is a threshold, it is stated, and everything else in this collection’s aperiodic work — the tile ratios, the substitution matrices — is exact by comparison.

Rotations are not quotiented out. A Penrose tiling’s patches come in ten orientations and a triangular lattice’s in six, so counting up to rotation would divide most counts by ten and change no comparison. Leaving them in keeps the controls comparable and inflates every number by roughly the same factor.

The controls are matched on count and density and not on everything. The triangular lattice has the Penrose patch’s edge length and fills the same disc; the random points have its number in the same disc. They are not matched on the minimum separation, which a random set does not have, and a control that were would be a different experiment — comparing a quasicrystal with a hard-disc liquid rather than with points.

The radii are small. Two edge lengths is a patch of a dozen vertices, and the interesting asymptotics are at radii the sample cannot reach. What is measured here is the beginning of a growth curve, and the polynomial claim above is quoted from the inflation argument rather than fitted to these points.

And the counts are of vertices, not of tiles. A patch of tiles carries more information than a patch of vertices — it knows which rhomb is which — so a tile census would give larger numbers. The vertex census is used because a uniform tiling is recoverable from its vertices and a Penrose one very nearly is, and because vertices are what a point-set detector takes.

The construction, and how expensive it is #

The Penrose patch every figure here draws is grown by inflation: ten Robinson triangles in a wheel, each subdivided into smaller ones, seven times over. Nothing about the tiling is laid out; the subdivision rule is stated once and applied.

The census itself is deliberately naive. For every vertex, look at every other vertex, keep the near ones, sort them, and compare the sorted lists. That is quadratic in the number of vertices and takes about half a second at three thousand of them — fast enough that no cleverness is warranted, and slow enough to explain why the radii stop where they do. A radius of six edges on a patch large enough to settle would be a search over tens of thousands of points, and the settling is what the measurement needs rather than the radius.

The naivety is also what makes the comparison fair. The same routine is run on the Penrose patch, on the triangular lattice and on the random points, with the same margin, the same rounding and the same rule for which vertices may be centres. A faster method specialised to one of the three would have been a different measurement of each.

Where the ladder goes next #

The complexity thread has now counted blocks in a sequence, measured how far away the next copy of a patch is, and counted patches in the plane. What none of them settles is what any of it scatters — and that question, unlike these, has an answer that separates the Fibonacci chain from a random one by an exponent rather than by a count.

Eight, at the smallest radius of all #

The census begins at radius one and there is a row below it worth having, because it is the one number in this subject that people quote from memory.

Count the ways the tiles can meet at a single vertex. Not a neighbourhood of some radius — just the tiles sharing one corner, with their angles adding to a full turn.

There are eight, and they have names: the sun, with five tiles of one kind around a point; the star, its counterpart; and six others. Every vertex of every Penrose tiling is one of those eight, and no ninth arrangement occurs however far the tiling is extended.

So the sequence starts at eight and reaches sixty-two one step out. That jump is the whole character of the object. A periodic tiling would have stayed at one; a random set would have started large. This one starts small, because the matching rules leave few options at a point, and then multiplies, because the options at a point can be combined in many ways further out.

The count keeps growing and grows slowly. It rises without bound — which is what makes the tiling non-periodic — and it stays polynomially small in the radius rather than exponential, which is what makes it ordered. Between those two behaviours there is nothing else for the sequence to do.

Every Penrose tiling contains every patch #

There is a companion statement to the census which is stronger than anything it measures, and it explains why measuring one tiling was legitimate in the first place.

Any patch occurring somewhere occurs everywhere. If a patch appears in one Penrose tiling, it appears in every Penrose tiling — infinitely often, at bounded gaps. So the census above is not a census of this tiling; it is a census of all of them at once, which is why the numbers are worth quoting.

And yet the tilings are genuinely different. There are uncountably many Penrose tilings of the plane, no two of them related by any translation or rotation. They are distinct objects and there is a continuum of them.

No finite observation separates two of them. A patch seen in one is present in the other, so any measurement made on a bounded region gives the same answer for both. Distinguishing them requires seeing all of the plane at once.

Which is a peculiar situation and the correct one for a physical model. A quasicrystal is a material, and a material is examined locally. That the tilings are uncountably many is a fact about the mathematics; that they are locally indistinguishable is why the mathematics describes a substance at all.