Every patch comes back

A periodic chain answers “where does this patch occur again?” before the question is finished: one period along, and again, and again for ever. That is what periodicity is.

An aperiodic chain has no such answer available, and it is not obvious that it has any answer at all. A block of tiles might occur once and never again; it might occur at wildly irregular intervals; it might occur only in some far-off stretch and never near where a reader happens to be standing.

None of that happens, and what does happen is sharp enough to measure.

Every block occurs infinitely often, at gaps taking a handful of values, and the largest gap grows no faster than the block’s own length. That last property has a name — linear repetitivity — and it is the quantitative form of what these essays have been calling long-range order.

The measurement #

For each length n, take every block of that length occurring in the chain, list the positions where it occurs, and record the largest gap between consecutive occurrences. Then take the worst over all blocks of that length. Call it R(n).

The gaps are Fibonacci numbers. Not approximately: the largest gap for a block of length n is always exactly a Fibonacci number, because the positions at which a block recurs are governed by the same recursion that built the chain. A block of length 4 has a worst gap of 8; extend to length 5 and it becomes 13; the sequence of worst gaps steps up through the Fibonacci numbers as n passes each one.

The ratio R(n)/n stays below three. So a reader standing anywhere in the chain, looking at any patch of size n, is guaranteed to meet that same patch again within 3n tiles. There is no stretch of the chain, however far out, where the pattern goes quiet.

Why this is stronger than it sounds #

Three separate things could go wrong for an aperiodic sequence, and none of them does here.

A patch could occur finitely often. Then the chain would have a beginning in a way a crystal does not — some feature belonging to one region and nowhere else. Every block of the Fibonacci chain occurs infinitely often, which is the property called recurrence.

A patch could occur only in one direction. The chain here is built from a starting letter and grown to the right, so a fair worry is that the measurement is about a half-infinite word with a distinguished end. It is not: the same measurement made on a stretch taken from the middle of a much longer chain gives the same gaps, because the recurrence structure is inherited from the substitution rather than from the seed. The projected chains have no seed at all — they are cut from a lattice that extends both ways — and give the same constants.

The gaps could grow faster than linearly. A patch of size n might have to wait n² tiles, or 2ⁿ. Then the chain would be uniform in the limit and effectively disordered at any scale a person could look at. The gaps here grow like n.

The patches could be distributed unevenly along the chain. Even with bounded gaps, one stretch could be much richer than another. That is exactly what the balance property rules out, and the two measurements together say the structure is uniform in both senses.

Taken together they are a large part of why a quasicrystal diffracts sharply rather than diffusely — a point the essays that measure the diffraction report as a measurement and this one supplies structure for. A Bragg peak needs the atoms to be arranged with well-defined long-range frequencies, and linear repetitivity is what makes those frequencies converge, at a rate that does not depend on where the counting started. It is not on its own enough to produce the peaks, which is the subject of a section below.

Why the gaps are Fibonacci numbers #

The staircase in the measurement is not decoration; it is the substitution showing through.

A block of length n recurs on the scale of the smallest inflation step that contains it. The chain is built by repeatedly inflating, so it is composed of blocks of Fibonacci length nested inside each other; a patch that fits inside a block of length F occurs wherever that block occurs, and blocks of length F recur at the spacing of the next inflation level. The worst gap is therefore a Fibonacci number, it holds while n ranges over a run of lengths fitting the same level, and it steps when n outgrows it.

That also explains the sawtooth’s height. Consecutive Fibonacci numbers have ratio approaching φ, so a gap of Fₖ₊₂ against a window of about F_k gives a ratio of about φ², which is 2.618. Every spike in the figure sits just above that number, and the one value above it — three, at a window of a single tile — is the special case where a single short tile waits for the block LSL to pass.

The same computation on the silver chain gives a different constant, four, and its worst gaps are 4, 10 and 24 — twice the Pell numbers 2, 5 and 12, which are to its substitution what the Fibonacci numbers are to the golden one. The mechanism is identical and the arithmetic is the substitution’s own.

The same complexity, different repetitivity #

The previous rung ended with three chains that the window count cannot tell apart: all of them have p(n) = n + 1 exactly, at every measured length. The return gap has no such difficulty.

The slope’s continued fraction is what decides it. Writing a slope as a continued fraction gives the sequence of partial quotients, and a large partial quotient means the projection produces a long run of one tile length — a stretch of the chain that is locally almost periodic, and inside which any patch containing the other tile has to wait.

• The golden slope has every partial quotient equal to one. Its constant is three, the smallest of the four.
• The silver slope has every partial quotient equal to two. Its constant is three and a half.
• A slope with a partial quotient of five reaches six and a half.
• A slope with a partial quotient of thirty reaches nearly thirty-two, a factor of ten worse than the golden slope, on a chain whose window counts are letter-for-letter identical in the count.

So the golden ratio is not one irrational among many. Where the golden ratio comes from derives it from the inflation of a Penrose tiling, and which inflation factors exist shows which algebraic numbers can play that role at all. This is a third reason for it, and a different kind: among all irrational slopes, the one whose continued fraction is all ones is the worst-approximable number there is, and worst-approximable is exactly the condition for the tightest return gaps.

What a bounded return gap is worth to a crystal #

The measurements above are about sequences. There is a reason to care about them that is about materials, and it is worth stating carefully because the connection is suggestive rather than proved.

A structure grows by adding atoms at its surface, deciding locally where the next one goes. Which faces a crystal shows works that argument for a periodic crystal, where every site the surface presents has been seen before and the rule for filling it is the same everywhere. An aperiodic structure has no such guarantee in general: the surface could present an arrangement that has never occurred, with no precedent for what goes next.

Linear repetitivity is exactly the statement that this does not happen. Every arrangement of size n has occurred already, within 3n tiles, and occurs again within 3n more. The growing surface is never in unfamiliar territory, and the frequency with which each local environment occurs is the same everywhere along the chain.

The materials bear this out and do not prove it. The icosahedral alloys that can be grown to near-perfection are the ones built on the golden ratio, which is the slope with the tightest return gaps; the ones built on less well-approximable ratios are harder to grow well. Whether that is cause or coincidence is not settled, and this site’s rule about not claiming what the machinery decides applies with force — nothing here computes anything about an alloy.

What is claimed is the arithmetic. A chain whose slope has a partial quotient of thirty has patches waiting ten times as long to recur as the same-sized patches in the golden chain, with an identical window count. If local environment and its recurrence matter to how a structure assembles, then two structures indistinguishable by the previous rung’s measurement differ by a factor of ten in the quantity that would.

Same patches, different chains #

There is a second question in the neighbourhood and it is worth separating, because the answer is different and equally strange.

Two Fibonacci chains built with different offsets — the strip shifted perpendicular to itself — are different sequences. They differ in infinitely many places, and no amount of sliding one along makes it match the other.

And yet every patch of one occurs in the other, at the same frequencies. Any finite stretch a reader can examine has an exact copy somewhere in the other chain. That is local indistinguishability, and it is the property the freedom a crystal has not is about: the offset is a genuine degree of freedom producing genuinely distinct structures that no local measurement can separate.

Repetitivity is what makes that concrete. Since every patch of size n recurs in the first chain within 3n tiles, and the two chains share their patch language exactly, a copy of any patch is always nearby in either chain. The two are different everywhere and the same anywhere.

What is measured, and over how much #

The gaps are exact counts on a finite chain. The Fibonacci measurement runs over forty-six thousand tiles and the projected ones over eight thousand, and every reported gap is the largest actually observed between consecutive occurrences.

A block occurring only once is excluded from the statistic rather than counted as an infinite gap. At the end of any finite word every block eventually occurs for the last time, and treating that final stretch as a gap would measure the word’s length instead of the chain’s structure. What is measured is the gaps between actual pairs of occurrences.

“Linear repetitivity” is a statement about the limit and this is a measurement. That R(n)/n stays below three for n up to ten does not prove it stays bounded for ever; the theorem that Sturmian chains with bounded partial quotients are linearly repetitive is the thing that does, and it is quoted here rather than proved. The measurement’s job is to catch an implementation that disagrees with it.

The constants depend on how the slope was truncated. A continued fraction written with a finite number of terms is a rational, and a rational slope gives a periodic chain. The slopes here are truncated far past the window lengths measured, so the chains behave as their infinite versions do over the range examined — but the constants are constants of the truncation, and a longer measurement on a truncated slope would eventually see the period.

Who found it, and when #

The idea that a tiling should be repetitive is built into the definition of a quasicrystal from the beginning; the term of art is that the structure has finite local complexity and is repetitive, both of which are needed before the diffraction theory applies.

Linear repetitivity as a sharp condition was studied by Jean-Marc Lagarias and Peter Pleasants around 2003, who showed it is in a precise sense the strongest form of order a non-periodic set can have — sets that are linearly repetitive are exactly those that behave, for the purposes of counting patches, as though they were periodic. Their result is that linearly repetitive sets are “ideal” quasicrystals, and that the ideal ones are rarer than had been assumed.

The continued-fraction connection is much older, and belongs to the theory of Diophantine approximation rather than to crystallography. That the golden ratio is the hardest number to approximate by rationals is Hurwitz’s, from 1891; the connection between a slope’s partial quotients and the behaviour of the sequence it generates is the standard theory of Sturmian words, developed by Morse and Hedlund and by Coven and Hedlund.

The physical corollary was noticed in the 1980s. Materials with a golden-ratio structure — the icosahedral aluminium alloys — turned out to be the ones that could be grown to high perfection, and the connection to the arithmetic of the ratio was made early and is still not entirely settled. What is clear is that the arithmetic makes a difference to how uniform the structure is, and uniformity is what a growing crystal needs.

Where this ladder goes #

Two rungs of this anchor have measured two numbers, and between them they replace the qualitative statement “long-range order without periodicity” with two quantities that a reader can check against a chain they were handed.

The window count says how various the structure is: n + 1, the minimum an aperiodic chain can manage, and it does not distinguish irrational slopes.

The return gap says how evenly that variety is laid out: bounded by three times the window length for the golden slope, and by ten times that for a slope with one bad partial quotient.

Both are one-dimensional, both are measurements rather than decisions, and both are stated here with the limits of the finite word they were taken on. The same two quantities exist for a Penrose tiling in the plane — where the window count grows like n² rather than n — and computing them is a different piece of machinery than this site has, so no claim is made about them here.

What repetitivity does not buy #

The properties measured here are strong, and it is worth being exact about how far they reach, because there is a claim in the neighbourhood that is very commonly made and is false.

Linear repetitivity does not imply sharp diffraction. The tempting statement — every patch comes back at bounded gaps, the frequencies converge uniformly, therefore the transform is a set of peaks — has a counterexample that is as well studied as the chain on this page.

The Thue–Morse chain is the counterexample. Build it by starting from a single tile and repeatedly replacing each tile by itself followed by its opposite. The result is aperiodic, its patch counts grow linearly, every patch occurs infinitely often with bounded gaps, and its patch frequencies converge uniformly — it satisfies everything measured above.

Its diffraction has no Bragg peaks at all beyond the trivial one at the origin. What it has instead is a singular continuous component: intensity that is concentrated on a set of measure zero and is nevertheless not a sum of point masses, so it neither forms spots nor spreads out as an ordinary diffuse background.

So the properties on this page are necessary and not sufficient. A chain whose patches recurred at unbounded gaps could not diffract sharply, which is why the measurement matters; a chain whose patches recur at bounded gaps still might not, which is why it is not the whole story. What separates Fibonacci from Thue–Morse is not repetitivity but the construction: the Fibonacci chain is a cut through a two-dimensional lattice, and it is that internal periodicity — periodicity in a space of higher dimension — that produces the peaks.

The honest summary is that this essay measures the order and not the diffraction. They are different properties of the same object, the first implies constraints on the second, and only the projection construction settles it.

Which slopes have this property #

The measurement here is made on one chain, and the general statement explains why that chain gives the tidiest possible answer.

A Sturmian chain is built from an irrational slope, and its combinatorics are governed by that slope’s continued fraction — the sequence of integers $[0; a_1, a_2, a_3, \dots]$ whose convergents are the best rational approximations to it. The Fibonacci chain’s slope is the golden ratio, whose continued fraction is all ones, and the Fibonacci numbers in the measurement above are its denominators.

The chain is linearly repetitive exactly when those integers are bounded. If some $a_i$ is very large, the slope is very well approximated by a rational at that stage, and the chain behaves like a periodic chain of that period over a long stretch — long enough that a patch not occurring in the repeating block waits far longer than its own length to reappear. Let the $a_i$ grow without bound and the waiting time grows without bound relative to the patch, and linear repetitivity fails.

So the property measured here is not shared by all aperiodic chains, nor even by all Sturmian ones. It belongs to the slopes of bounded type, which is a set of measure zero among the irrationals — almost every slope produces a chain whose patches sometimes wait much longer than three times their length.

And all ones is the smallest the integers can be, so the golden ratio is the extreme case in the direction of good behaviour: the hardest number to approximate by rationals, and therefore the chain whose repetitivity constant is as small as a Sturmian chain’s can be. The bound of three is not a typical figure that happens to have been measured on a convenient example. It is the best any chain of this kind achieves.