n plus one, and no fewer

Every argument for aperiodicity on this site so far has been an argument about how the thing was made. The Fibonacci chain never repeats because its tile ratio is irrational; a Penrose tiling never repeats because its inflation factor is; a cut-and-project set never repeats because the strip’s slope is. Each is correct, and each requires knowing the recipe.

There is a measurement that does not.

Slide a window of length n along the chain and count how many different things it ever shows. Call the answer p(n). It is a count of distinct blocks of tiles — nothing else — and it can be made by somebody handed the sequence with no idea where it came from.

What the count does when the chain repeats #

If a chain has period q then a window longer than q sees the same q blocks over and over, one for each starting phase. So p(n) stops growing, permanently, at or before q.

That is the easy direction and it suggests the hard one. Marston Morse and Gustav Hedlund proved the converse in 1938, and it is much stronger than the obvious statement:

If p(n) ≤ n for even a single value of n, the chain is eventually periodic.

Not “if p stops growing” — a single failure to exceed the window length, at one length, forces periodicity everywhere. The consequence, taken the other way round, is the one this essay is about: an aperiodic chain has p(n) ≥ n + 1 for every n, without exception, and the chains that achieve exactly n + 1 are as close to periodic as a non-periodic sequence is permitted to get.

Two windows of length one, because there are two tile lengths. Three of length two, not four — SS never occurs, and that single missing block is what pins the whole chain to the minimum. Every extra length adds exactly one new block and forbids all the others.

The comparison that makes the number mean something #

A count of five is small or large depending on what it is next to. So the same measurement is made on chains built four other ways.

The periodic control is the one that matters. A chain of period seven has p(7) = 7, which is ≤ 7, so Morse–Hedlund fires and reports it periodic with period at most seven — correctly, and as a proof rather than an observation. That is the direction of the theorem a finite measurement can actually use.

The random control shows what “no structure” looks like: p(n) = 2ⁿ, every block occurring, until the chain is too short to contain them all. Between 2ⁿ and n + 1 is the whole range of possibilities, and the aperiodic chains of interest sit at the very bottom of it.

Three constructions, one minimum #

The three chains achieving n + 1 are worth naming individually, because their agreement is not a coincidence and is not a definition.

The Fibonacci chain comes from a substitution: a long tile becomes long-short, a short tile becomes long.

The silver chain comes from a different substitution: long becomes long-long-short, short becomes long, with the silver ratio 1 + √2 as its inflation factor instead of the golden ratio.

The projected chain comes from cut and project: integer lattice points inside a strip of irrational slope, projected onto the strip’s direction, with no substitution anywhere.

All three give p(n) = n + 1. That is the class of Sturmian sequences, and the theorem behind the agreement — every Sturmian sequence is a mechanical word from some irrational slope, and vice versa — is why the substitution chains and the projection chains keep turning out to be the same objects. This site has met that fact twice before, in the equality of the substitution and projection constructions and in the extra dimension that makes a chain periodic again. Here it appears as a shared value of one counted number.

The chains behind all of this are generated rather than sampled: the substitution is applied until the word runs past forty-six thousand tiles, and every count above is taken over the whole of it. A count over a short chain is a count of what the chain had room for, which is the failure mode the random control on this page exhibits — it doubles until it runs out of length and then flattens, and the flattening is an artefact of the sample rather than a property of the sequence.

The second test, which agrees and shares no code #

There is an independent characterisation of the same class, and running both is the point.

A chain is balanced when any two windows of the same length contain counts of the long tile differing by at most one. It is a statement about how evenly the tiles are spread, with nothing at all to say about how many arrangements occur — a chain could in principle be very even and very various, or lumpy and monotonous.

The two tests select the same chains. Exactly the chains with p(n) = n + 1 are the balanced ones, which is a theorem — and which is here a measurement made twice, by procedures with no code in common, agreeing on seven chains.

The Thue–Morse chain is the useful failure here: it is genuinely aperiodic, so it passes the test that matters, and it is neither minimal nor balanced, so it fails both of these. Aperiodicity is one property and being Sturmian is a much stronger one, and a measurement that conflated them would report the same verdict for both chains.

That is the kind of agreement this site’s habit is built around, and it is worth being precise about what it is worth. It does not prove the theorem. It does establish that a bug producing wrong window counts would have to produce a matching bug in a completely different sliding-count routine to escape notice, which is not a thing bugs generally do.

The blocks that never occur are the local rules #

A low window count is the same statement as a long list of forbidden blocks, and reading it that way connects this measurement to an argument the aperiodic field has already had.

At length two there are four possible blocks and the Fibonacci chain shows three: SS never occurs, because a short tile is produced only from a long one and always arrives with a long tile beside it. At length three there are eight possible and four occur, so four are forbidden. At each length the chain admits exactly one more block than the length, and forbids everything else — and the number forbidden grows like 2ⁿ while the number permitted grows like n.

That is what a local rule is. Matching rules and what actually forces aperiodicity is about exactly this trade: a decoration on tiles that forbids certain local arrangements, in the hope that the forbidding leaves only aperiodic possibilities. The window count is the same information gathered from the other end — instead of stating the rules and asking what they allow, it takes the chain and reads off what it never does.

The essay that argued the rules do not by themselves force aperiodicity has a sharp form here. Forbidding SS does not produce the Fibonacci chain. The periodic chain LLSLSLS forbids SS too, and so does LS repeated, and so do infinitely many others. A finite list of forbidden blocks defines a set of sequences, and the Fibonacci chain is one member of a set that contains periodic sequences as well. What the substitution supplies, and the forbidding does not, is which member.

Low complexity is therefore necessary and nowhere near sufficient, and the same asymmetry appears in the plane: Penrose’s matching rules famously do force aperiodicity, and that is a hard theorem about a particular decoration rather than a consequence of the tiles being restrictive. Counting windows tells a reader how restricted a structure is. It does not tell them that the restriction is doing any forcing.

What a finite measurement can and cannot conclude #

The asymmetry here is sharp and it is the reason this essay is careful.

A measurement can prove periodicity. Observing p(n) ≤ n at one length is a proof, by the theorem, that the chain is eventually periodic with period at most p(n). The periodic control is caught this way, at n = 7.

A measurement cannot prove aperiodicity. Observing p(n) = n + 1 for n up to twelve is entirely consistent with a chain of period four hundred, whose complexity would not flatten until well past anything measured. What the essays here have is the construction proving aperiodicity and the measurement agreeing with it — and the agreement is a check on the construction rather than a substitute for it.

Every count is checked for having settled. A factor count on a finite word is a lower bound: a block might occur first at position ten million. So every count here is made twice, once on the whole chain and once on its first half, and only lengths where the two agree are reported. On a chain of forty-six thousand tiles that leaves plenty of room, and the rows where it does not are dropped rather than drawn.

The random control is not random. It is a fixed pseudo-random stream, so that a figure drawn twice is the same figure — the fleet’s rule about generators being functions of their arguments. What it is standing in for is a chain with no long-range order at all, and its behaviour is 2ⁿ until it runs out of length, which is the honest ceiling.

Where this puts the quasicrystals #

The counting reframes a claim that has been made several times on this site in a form that is now measurable rather than rhetorical.

Order is not periodicity argues that a chain can be completely determined, completely non-random, and never repeat. In the language of this essay: it has linear complexity and unbounded complexity at once. Linear, because p(n) grows like a constant times n rather than exponentially, which is what “determined” means quantitatively. Unbounded, because it never flattens, which is what “never repeats” means.

Periodic chains have bounded complexity. Random chains have exponential complexity. The quasicrystalline middle is exactly the linear band, and the Fibonacci chain is at its lower edge.

And it explains why quasicrystal diffraction is sharp. A structure whose local arrangements are this restricted has patch frequencies that converge — every block of length n occurs at a definite rate — and that is what a sharp Bragg peak needs. The connection is not proved here and the essays that measure diffraction measure it rather than deciding it; what the count supplies is the reason to expect the measurement to come out that way.

Where the exactness stops #

The counts are exact and the conclusions are bounded. Every number reported is an exact count of distinct substrings of a specific finite word, at a length where the count has been shown to have settled.

The theorem is quoted, not proved. Morse–Hedlund is used in the direction that catches the periodic control, and its statement is given rather than derived. The same for the equivalence of Sturmian, balanced and mechanical, which is Coven and Hedlund’s, 1973.

Nothing here is two-dimensional. A Penrose tiling has a patch-counting function too, and it grows like n² rather than like n — the plane has more room for arrangements than the line. That computation is not made here, and the essays’ claims about Penrose tilings continue to rest on their construction rather than on any count.

A chain is not a crystal. These are one-dimensional sequences of two tile lengths, which is where the arithmetic is short enough to be checked completely, and the rule the site holds itself to applies: the exact machinery is for periodic patterns in the plane, and everything about aperiodic structures here is a measurement with its limits stated.

Who found it, and when #

Marston Morse and Gustav Hedlund published Symbolic dynamics in 1938, where the complexity function and the periodicity criterion appear together. Their motivation was geodesics on surfaces of negative curvature, not tilings, and the sequences they were studying were codings of trajectories.

Sturmian sequences are older than the name, going back to work of Jean Bernoulli III in 1772 on the fractional parts of multiples of an irrational, and to Christoffel and to Markov in the nineteenth century. Morse and Hedlund named them in 1940 after Jacques Charles François Sturm, whose connection to them is indirect at best.

The three-way equivalence — minimal complexity, balanced, mechanical — was completed by Ethan Coven and Hedlund in 1973. The chains here satisfy all three, and the essay’s figures measure two of them.

Quasicrystals arrived independently and forty years later. When Shechtman’s diffraction pattern appeared in 1984, the mathematics of low-complexity sequences was decades old and belonged to symbolic dynamics; the two literatures took some time to notice each other. The word quasiperiodic is used in both with meanings that do not quite coincide, which is a hazard for a reader crossing between them.

What the growth rate is a measure of #

The complexity function has been read here as a count at each length. Its rate of growth is a quantity in its own right, it has a standard name, and it puts the three chains of this essay at one end of a scale whose other end this collection has already measured.

The topological entropy of a chain is the limit of log p(n) / n — how fast the count grows, on a logarithmic scale, per unit of window length. For a chain with p(n) = n + 1 the logarithm grows like log n and the ratio goes to zero. For the random control, p(n) = 2ⁿ and the entropy is log 2.

So the Sturmian chains have zero entropy, and that is the sharpest statement of what “ordered but not periodic” means: they are as far from random as a non-periodic chain can be, in a measure that makes the comparison exact rather than rhetorical.

It also connects this measurement to the counting essays. The count of arrangements a local rule allows is the same quantity for a two-dimensional rule — a growth per site, obtained as a limit — and the dimer rule’s 1.3385 and the ice rule’s 1.5 are entropies in the same sense. A rule leaving that much freedom has positive entropy; a Sturmian chain has none.

And that is why the chains are the right model for a quasicrystal and the local rules are not. A structure with positive entropy has exponentially many arrangements and no particular one; a structure with zero entropy has, in the limit, essentially one. Sharp diffraction needs the second.

The same question in the plane, which is open #

The Morse–Hedlund criterion is a complete answer in one dimension, and the corresponding statement in two is a conjecture — which is worth recording, because it is the kind of gap a reader would not expect.

Count the distinct m × n rectangular patches a two-dimensional configuration shows, and call it P(m, n). Nivat’s conjecture says that if P(m, n) ≤ mn for some pair m, n, the configuration is periodic in at least one direction. It is the exact analogue of the one-dimensional statement, with mn in place of n.

It is not proved. Partial results exist — the conjecture is known under stronger hypotheses, and it is known that some bound of that shape forces periodicity — and the general case has been open since the 1990s. The three-dimensional analogue is false, with counterexamples known, so the conjecture is specific to the plane rather than a pattern that continues.

That is worth setting beside this essay’s own asymmetry. In one dimension a measurement can prove periodicity and cannot prove aperiodicity; in two dimensions it is not known whether a measurement can prove periodicity at all. The line is where the counting is a theorem, and everything this collection says about complexity is said there for that reason.

Where this ladder goes #

The count says how many arrangements occur. The next rung asks a question the count cannot answer: how far apart two copies of the same arrangement can be.

Three chains here share the value n + 1 exactly, so the complexity cannot distinguish them at all. Their return gaps can, and the answer turns out to be governed by the continued fraction of the underlying slope — which is where the golden ratio stops being one irrational among many and becomes the specific one that makes patches come back soonest.

That is worth anticipating, because the two measurements pull in opposite directions and a reader could reasonably expect one to determine the other. The window count says how various a chain is; the return gap says how evenly that variety is distributed along it. A chain can be minimal in the first sense and badly behaved in the second, and the next rung’s figures show four chains that are identical under the first measurement and differ by a factor of ten under the second.