How often each patch occurs

Every patch comes back establishes that a patch appearing anywhere in an aperiodic chain appears within a bounded distance of everywhere. The average is the same wherever it is taken goes further: the proportion of a long window occupied by any given patch converges, and to the same limit wherever the window was cut. Both are statements that a frequency exists.

Neither says what it is, and the number is available.

It is an eigenvector. A substitution acts on letters and produces a matrix whose Perron eigenvector gives the letter frequencies — the standard first computation of the subject. It also acts on blocks of any fixed length, producing a larger matrix over a larger alphabet, and that matrix’s Perron eigenvector gives the frequency of every block. Nothing else is needed, the arithmetic is the arithmetic of a single eigenvector, and the answer is exact in the way that matters: an algebraic number in the field the inflation factor generates.

The substitution acting on blocks #

The construction is short and worth writing out, because the only place it could go wrong is the bookkeeping.

Take the distinct blocks of length n that occur in the chain. There are n + 1 of them for the Fibonacci chain — that is n plus one and no fewer, the defining property of a Sturmian word — and for other substitutions there are more.

A block w sits somewhere in the chain, so it has a definite image under the substitution. Apply σ to the whole block: the first letter becomes a word of |σ(w₀)| letters, and each position of that word is the start of a new block of length n inside the image. Reading them off gives the blocks that w produces, and how many times each.

Two details make it work rather than nearly work. The image is long enough. A block of length n has an image of at least n letters for any substitution that lengthens, so a window of n starting at any of the first |σ(w₀)| positions is entirely inside it. And the blocks read off are in the language: they occur in the chain, because the image of a block that occurs is a stretch of chain. Both are asserted rather than assumed, and a block appearing that is not in the enumerated set stops the build.

The result is a non-negative integer matrix, and the matrix is primitive — some power is strictly positive — which is what makes the Perron–Frobenius theorem apply and the eigenvector unique and positive.

Two routes, and neither knows about the other #

The frequencies are computed a second time by the crudest possible method: build a chain of a hundred and twenty thousand letters, slide a window of length n along it, and count.

There is nothing in common between the two computations. One is power iteration on a matrix of integers derived from the substitution rule; the other is a loop over a string that never mentions a matrix. They agree to about four parts in a million on a chain of a hundred thousand letters, and to four parts in ten thousand on a chain of a thousand — and the improvement is the point. A pair of numbers that agree once could agree for a reason having nothing to do with either being right. A discrepancy that falls by two orders of magnitude when the chain is lengthened by two is the ergodic theorem being watched rather than cited.

There is a second check available and it is stronger. The block matrix has its own Perron eigenvalue, and that eigenvalue comes out equal to the letter matrix’s — the golden ratio, to nine places, for every block length. A chain inflates at one rate whatever length of window is being counted, and a block matrix that had an inflation factor of its own would be a block matrix built wrongly.

What a letter frequency already said, and what it did not #

The letter case is the whole construction at n = 1, and it is worth doing first because it makes visible how little is being added.

The Fibonacci substitution’s matrix is two by two with entries one and one, one and zero. Its Perron eigenvalue is the golden ratio and its eigenvector, normalised, is (1/τ, 1/τ²) — so long tiles occupy 0.618034 of the chain and short ones 0.381966, and the ratio of the two frequencies is the inflation factor itself. That is the standard first fact of the subject and it is what the smallest quasicrystal reports.

What the letter frequencies do not say is anything about arrangement. Two chains with identical letter frequencies can have completely different sets of blocks — a periodic chain LSLSLS… and the Fibonacci chain have the same letters in nearly the same proportion and nothing else in common. The block frequencies are where the arrangement lives, and they are the same computation done on a larger alphabet, which is the economical thing about this construction: nothing new is needed, only a bigger matrix.

Three values, and only three #

Now the fact this essay exists for.

The Fibonacci chain has n + 1 blocks of length n, so at length nine there are ten of them. Their frequencies take three distinct values. At length twelve there are thirteen blocks and their frequencies take two distinct values. At no length whatever do they take four.

That is not a small-numbers accident and it is not a fact about substitutions. It is three gaps and never four, arriving in a question that looks nothing like it.

The frequencies are the gaps #

The Fibonacci chain is a cut of a rotation. Mark the points α, 2α, 3α, … around a circle of circumference one with α = 1/τ², cut the circle into two arcs, and write down which arc each point lands in: the resulting word is the Fibonacci word, and this collection builds it that way.

Under that correspondence a block of length n is a condition on n consecutive points of the orbit, which is a condition on where the first point is — and the set of starting positions giving one particular block is an arc. The arcs for different blocks are disjoint and cover the circle. So the frequency of a block is the length of its arc.

The arcs are exactly the pieces the first n + 1 points of the orbit cut the circle into. And the three-distance theorem says those pieces take at most three lengths.

The two lists agree at every length tested, digit for digit. One of them is an eigenvector of a matrix of integer counts derived from a substitution rule; the other is a sort of a list of fractional parts of multiples of an irrational number. They have the golden ratio in common and nothing else, and they produce the same three numbers.

What the numbers turn out to be #

The eigenvector returns decimals, and the decimals are recognisable.

0.618034, 0.381966, 0.236068, 0.145898, 0.090170, 0.055728 — every value that appears at any block length is a negative power of the golden ratio, and at any one length the three exponents that appear are consecutive.

That is not something the matrix announces. The block matrix at length nine is ten by ten, its entries are ones and zeros, and its Perron eigenvector is a list of ten numbers; nothing in that computation mentions the golden ratio except through the eigenvalue. The exponents are found afterwards, by matching each value against τ⁻ᵏ for k up to thirty, and a value that matched nothing would be reported as unmatched rather than rounded into place.

The reason is again the arcs, and it is the reason τ is the case where this is cleanest. The continued fraction of τ is all ones, which makes every remainder in the expansion exactly the next power of 1/τ — so the gaps the rotation leaves at any stage are three successive powers, with the largest being the sum of the other two, which is the golden ratio’s defining relation showing up as the three-distance theorem’s own conclusion. There is no room between consecutive powers for a fourth value.

Where the two values come from #

The three-distance theorem’s bound is three; its degenerate case is two, and the degenerate case happens when the points are as evenly spread as a rotation can make them — which is at the denominators of the continued fraction’s convergents.

For the golden rotation the convergent denominators are the Fibonacci numbers. So the block lengths at which only two frequencies occur should be one less than a Fibonacci number: 1, 2, 4, 7, 12, 20.

They are, exactly. That is a prediction with a shape rather than a table: it says which lengths, not how many, and it comes from the continued fraction of the rotation number rather than from anything in the substitution. The chain’s most arithmetic property and its most combinatorial one are the same property.

And the golden ratio is the extreme case for a reason. Its continued fraction is all ones, which is the slowest possible convergence and the most even possible spreading, and that is the sense in which τ is the “most irrational” number. The silver chain, whose continued fraction is all twos, has its degenerate lengths at the Pell numbers instead, and the pattern shifts accordingly.

The chain the other Sturmian rotation gives #

The silver chain — L → LLS, S → L, with inflation factor 1 + √2 — is the cut of a rotation whose continued fraction is all twos, and it behaves the same way for the same reason with different numbers.

Its block frequencies never exceed three values either, and its degenerate lengths sit at the Pell numbers rather than the Fibonacci ones, because the Pell numbers are the denominators of that continued fraction’s convergents. Neither the substitution nor the block matrix knows anything about continued fractions; the pattern is visible only because the same computation is run on both chains and the two answers are set side by side.

This is the sense in which a Sturmian chain is a rotation wearing different clothes. Everything combinatorial about it — the complexity n + 1, the balance property, the three frequencies, which lengths are degenerate — is a restatement of an arithmetic fact about one irrational number, and which irrational number it is decides all of them at once.

Where the bound stops holding #

A bound is only interesting if something violates it, so the same computation is run on a chain that is not a cut of a rotation.

The substitution A → B, B → AAAB has trace one and determinant −3, so its inflation factor is (1 + √13)/2 and its algebraic conjugate lies outside the unit circle — it is not Pisot, which is what decides whether the chain diffracts sharply. Its blocks of length seven have five distinct frequencies.

So three is a fact about Sturmian words and not about substitutions, and the machinery is the same machinery in both cases. The constant-length chains go the other way: Thue–Morse and the period-doubling chain have at most two values at every length, because their frequencies are dyadic rationals and there are very few of those with small denominators.

Three chains, three behaviours, one eigenvector routine.

What the frequencies refuse #

The last is the one that would have been easiest to omit and is the one that catches a real error. A chain of finite length has blocks near its end that occur once, and a frequency computed from a chain too short for the window being counted is a measurement of where the chain was cut off. The check is to count the blocks at two different chain lengths and require the set to be the same; where it is not, the window is longer than the chain can support and the row is refused rather than reported.

Where the exactness stops #

Computed here: the block substitution and its matrix for five chains and every block length to twelve; the Perron eigenvector of each by power iteration with its residual reported; the same frequencies by counting over chains of up to a hundred and twenty thousand letters; the gaps of the golden rotation to twenty-one points; and the comparison between the two.

The eigenvector is numerical and the statement it supports is not. Power iteration converges to a vector, and what is reported is that vector together with the residual ‖Mv − λv‖, which sits at the last bits of a double. What is exact is the matrix — it is a table of integers, built by reading windows out of strings — and the fact that its Perron eigenvector’s entries lie in the field generated by λ. Writing them as exact algebraic numbers is possible and is not done; the frequencies are reported as decimals with their agreement stated.

One dimension. Everything here is a chain. The same construction runs in two dimensions — patches of a Penrose tiling, the substitution acting on collared tiles — and the matrices get large quickly. How many patches of each size counts them in the plane; how often each occurs, in the plane, is a bigger computation and is not this one.

The tolerance that decides “distinct” is a choice, and it is a formality. Counting how many different frequency values occur means deciding when two decimals are the same number, and that is a threshold. It is set at one part in ten million, and the values it separates are apart by amounts of the order of the frequencies themselves — the closest pair at any length tested differs in the second decimal place. So the count of distinct values would be the same at any threshold between about 10⁻¹² and 10⁻². Where a threshold has that much room round it, saying so is more honest than pretending it is not there.

A frequency is not a probability. Nothing here is random. The chain is one fixed sequence, the frequency of a block is a limit of a proportion along it, and no ensemble is being averaged over. That the limits behave like a probability distribution — non-negative, summing to one — is a theorem about unique ergodicity rather than an assumption smuggled in with the word.

Who found it, and in which subject #

The block substitution and its eigenvector are folklore in symbolic dynamics; the three-distance theorem is older and was proved several times over — Steinhaus posed it, Sós, Surányi and Świerczkowski each proved it around 1958 — in a subject with no crystals anywhere near it.

The connection was made in the other direction from the one this essay travels. Sturmian sequences were studied as codings of rotations from Morse and Hedlund’s work in the 1940s, and their combinatorial properties — complexity n + 1, balance, the three frequencies — were understood as facts about rotations. When quasicrystals arrived in 1984 the one-dimensional model was recognised as exactly that object, and forty years of combinatorics on words became available at once.

Which is worth knowing as a matter of practice as well as history: the questions a physicist asks about a Fibonacci chain have almost always been answered, under other names, by people who were not thinking about matter.

Where the ladder goes next #

Back, to the theorem that says a frequency exists at all: the average is the same wherever it is taken, where unique ergodicity is measured rather than assumed.

Sideways, to the same three numbers seen as gaps: three gaps, and never four, and to the count these frequencies are a refinement of, how many patches of each size.

And on, to what the inflation factor decides once the frequencies are known: which inflation factors exist, where being Pisot is what separates a chain with sharp diffraction from one without — and where the chain with five frequency values turns up again, for the same reason.