The average is the same wherever it is taken

Two questions have been asked about the Fibonacci chain in this collection already, and both are about the chain as a whole: how many distinct blocks of each length it contains, and how far one must walk before a given block reappears.

A measurement asks something narrower. It is made on a finite window, at a place nobody chose deliberately, and it returns the frequency of something in that window. The question is whether the answer belongs to the chain or to the window — and for an aperiodic chain, whose local arrangements differ from place to place, the question is not rhetorical.

The measurement #

Fix a block — the pair LS, say — and a window length. Slide a window of that length along a long piece of the chain, and at each position count how many times the block occurs inside it. Divide by the length to get a frequency.

Those frequencies vary from position to position. What is measured here is the largest departure from the frequency the whole chain has, taken over every position the window can take — the worst case, not the average, because the average hides exactly the effect being asked about.

Then repeat at a ladder of window lengths, from sixty-four to four thousand, and see how the worst error falls.

The answer, and the comparison that gives it meaning #

On the Fibonacci chain the worst error falls as one over the length. Fitted over the ladder, the exponent is −1.01.

That number means nothing until it is set against an alternative, and the alternative is a shuffle: the same letters in the same proportions, in a random order, from a fixed seed. On the shuffle the exponent is −0.53.

One half is what a random arrangement gives, and the reason is a random walk: each position of the window is a fresh sample, the count fluctuates as the square root of the number of samples, and the frequency’s error is that divided by the length — one over the square root.

So the chain is not merely better than random; it is better by a whole power. To know a frequency to a part in a thousand needs a window of a thousand tiles in the chain and a million in the shuffle.

Bounded discrepancy, which is the sharper statement #

Multiplying the error by the length gives a quantity that is easier to interpret: the departure of the count from what the frequency would predict.

On the chain that product hovers between 0.55 and 0.89 across the whole ladder — it does not grow. The count of a block in a window is within a bounded distance of the frequency times the length, however long the window is, and the bound is smaller than one occurrence.

That property has a name — bounded discrepancy — and for sequences of this kind it is a theorem rather than an observation. What is measured here is an instance of it, at seven window lengths on one block, with the constant reported.

On the shuffle the same product grows: 8 at length 64, 51 at length 4096. That is the random walk again, and it is the contrast that makes the chain’s boundedness worth stating.

What this does and does not say about aperiodicity #

It is tempting to read bounded discrepancy as a signature of the chain’s aperiodic order, and it is half of one.

A periodic chain has it too. Measuring the same quantity on LSLS repeated gives a product of essentially zero at every window length: a periodic sequence’s counts are exact up to one period, which is the smallest possible discrepancy. So bounded discrepancy does not distinguish an aperiodic chain from a crystal.

What it distinguishes is order from disorder. The chain and the shuffle have identical letter frequencies and identical compositions, and they differ by a whole power in how quickly a window’s answer settles. That is a measurement of order, and it is the sense in which the Fibonacci chain is much more like a crystal than like a random sequence.

This collection has made the same point from several other directions — order is not periodicity, and a diffraction pattern with sharp peaks needs order and not repetition — and the discrepancy measurement is the same statement about local statistics rather than about a transform.

Why the window’s position does not matter #

The frequency being measured is a property of the chain, and the reason no position of the window is special is worth naming, because it is a structural fact rather than an accident of the sample.

Every block that occurs in the chain occurs everywhere in it — within a bounded multiple of its own length of any point, which is the repetitivity this collection measured earlier. So no region of the chain is missing any of the local arrangements, and a window anywhere sees the same repertoire.

The stronger statement, that the frequencies converge to the same values wherever the window is placed, is unique ergodicity, and it is a theorem about the systems these chains generate. The measurement here is consistent with it and does not establish it: seven window lengths on one chain cannot rule out a chain whose frequencies fail to converge somewhere further along.

Where the constant comes from #

The bound on the discrepancy is not a universal number. It depends on the block being counted and on the chain, and for a chain of this kind it depends on the continued fraction of the slope that generates it.

The Fibonacci chain’s slope is the golden ratio, whose continued fraction is the slowest-converging one there is — all ones. That is the best case for bounded discrepancy: the constant is smallest for the slope hardest to approximate by rationals, which is the reverse of the intuition that a nearly-rational slope should behave more like a periodic sequence.

Nearly-rational is exactly the bad case. A slope very close to a rational produces long stretches that look periodic and then a correction, and the correction is where the discrepancy accumulates. The golden ratio, being furthest from every rational in the relevant sense, never accumulates one.

This collection has that same number appearing in three gaps and never four and in the repetitivity constant, and it is the same underlying fact each time: the continued fraction controls how evenly the chain distributes.

What a diffraction pattern makes of it #

The reason this matters outside the arithmetic is that a diffraction pattern is an average over a window, and how fast the average settles decides whether the peaks are sharp.

A Bragg peak is a sum of terms that are all in phase, so its intensity grows as the square of the number of tiles contributing. A feature that is not a genuine peak grows more slowly — as the number of tiles, for a random arrangement — and this collection uses exactly that growth test to separate a peak from a bump.

Bounded discrepancy is what makes the first case possible. If the count of a local arrangement in a window departed from its frequency by an amount growing with the window, the phases would not stay aligned and the peak would not grow quadratically. The chain’s discrepancy is bounded, so they do, and the diffraction is sharp.

The shuffle’s is not, and its diffraction is diffuse — the same distinction this collection’s disorder essays make about a crystal with a perfect lattice and a disordered occupation. Sharpness is a statement about how quickly local averages settle, in both cases.

The same measurement on a different chain #

Running the ladder on other substitution chains gives a rough sorting worth reporting, though this essay measures only two sequences carefully.

A chain generated by a substitution whose inflation factor is a Pisot number — the golden ratio is one — has bounded discrepancy for the same reason its diffraction is sharp: the conjugate of the inflation factor is small, so the errors introduced at each level of the substitution shrink instead of accumulating.

A chain whose inflation factor is not Pisot does not. Its discrepancy grows, slowly, and its diffraction is correspondingly less sharp. This collection has the arithmetic of which factors are Pisot already, and the connection to discrepancy is the same statement in another vocabulary: what decides both is whether the conjugate lies inside the unit circle.

Measuring that carefully would need a longer ladder and several chains, and this essay does not. What it does is establish the method on the case where the answer is known, and name the direction the generalisation runs in.

Why the worst case rather than the average #

A choice was made in the measurement and it is worth defending, because the alternative would have looked better and said less.

Averaging the error over window positions would give a smaller number and a cleaner-looking convergence, and it would also hide exactly the effect in question: whether some placement of the window gives a badly wrong answer. A measurement is made at one position, not averaged over all of them, so the worst case is the relevant statistic.

The same choice arises in near-symmetry and in the fleet’s own gates, and it goes the same way each time: report what the worst case does, because a claim about a measurement is a claim about the one that was made.

It also makes the exponents harder rather than easier to fit, since a worst case over positions is noisier than an average. Getting −1.01 and −0.53 out of the noisy statistic rather than the smooth one is a stronger result than the numbers suggest.

The measurement’s own limits #

Three, and each of them bounds what the numbers above establish.

One block. The measurement is made on a single two-letter block. Different blocks have different constants, and a block long enough to be rare in the window lengths used would be measured badly.

Seven lengths. An exponent fitted over a range of sixty-four to four thousand is a fit over less than two decades, which is enough to separate −1 from −½ and not enough to distinguish −1 from −0.95.

One realisation of the shuffle. The comparison uses a single shuffled sequence from a fixed seed. Its exponent is a fitted −0.53, and another seed would give something near but not equal to that. The seed is fixed so that the figure’s numbers do not move between builds, and the honest statement is that one shuffle gives one estimate of a random walk’s exponent.

A window is a measurement, and so is a crystal #

The framing this essay uses — an answer belongs to the window or to the object — is not particular to aperiodic chains, and it is worth setting beside two cases from elsewhere in the collection.

A diffraction experiment measures over a coherent region rather than over a crystal, and the region’s size decides how finely reciprocal space can be sampled: a finite block holds one wavevector per cell and nothing between. That is the same restriction as a window’s, in the transform.

A structure refinement measures an average over the cells within that region, and reports it as a structure. Where the cells differ from one another — as in a disordered occupation — the reported structure is the average and no cell is like it.

In both cases the question is whether the finite measurement converges to a property of the infinite object, and how fast. For a periodic crystal the answer is immediate, since one cell contains everything. For an aperiodic chain it is the discrepancy measurement above. For a disordered crystal it is a statistical convergence with an exponent of one half — the same random-walk exponent the shuffle gives here, which is not a coincidence but the same argument.

What is exact and what is fitted #

The counts are exact — integers, from a sliding window over a word constructed by substitution — and so are the frequencies, which are ratios of integers.

The exponents are fitted, by a straight line through the logarithms, and they are the only quantities here that are not exact. Reporting them as −1.01 and −0.53 rather than as −1 and −½ is the point: the fitted values are what the measurement produced, and the theoretical values are what they are being compared with.

The distinction is the same one this collection makes about every measured quantity. A bounded discrepancy is a theorem; a fitted exponent of −1.01 over seven window lengths is evidence that the code implements the situation the theorem is about.

Every measurement on this page is made on a long piece of one word, generated by the substitution L → LS, S → L rather than sampled from anything, and the shuffle it is compared against is that same word’s letters in a different order — the same two symbols in the same proportions, and none of the structure. That is what makes the comparison a comparison: nothing that a count of letters can see distinguishes the two sequences, so anything the measurement separates is a fact about arrangement.

The number the chain and the crystal share #

One quantity comes out the same for the Fibonacci chain and for a periodic chain, and it is the one worth ending on.

The frequency of the block LS in the chain is 1/τ², where τ is the golden ratio, and it is an irrational number — which a periodic chain’s frequencies never are. But the rate at which a window’s estimate approaches it is the same rate a periodic chain’s estimate approaches its own rational frequency: one over the window length, from a bounded discrepancy.

So the aperiodic chain’s frequencies are irrational and are measured as easily as a crystal’s. That is the whole content of calling such a chain ordered, and it is why a quasicrystal’s diffraction pattern has peaks as sharp as a crystal’s while its structure has no repeating unit at all.

The shuffle has rational frequencies — the proportion of L in a finite shuffle is a ratio of counts — and they are measured worse. Rationality of the answer and ease of measuring it are unrelated, which is a small thing to notice and is the sort of thing that makes the aperiodic case worth measuring rather than assuming.

What the pictures cannot show #

The limit is not drawn. Every quantity here is measured at a finite window on a finite piece of the chain. The statement that a frequency exists — that the sequence of window estimates converges — is a statement about an infinite object, and no measurement establishes it.

The worst case is a maximum over sampled positions. The windows are taken at a stride rather than at every position, so what is reported is the worst over the positions visited. A finer stride would find a slightly larger worst case and the same exponent.

Nothing here is a two-dimensional tiling. The analogous question for a Penrose tiling — how fast a patch frequency measured in a finite region converges — has the same shape and a harder answer, and this collection has not measured it. What survives from the one-dimensional case is the framing: a measurement on a finite window is a measurement of the window unless something bounds the discrepancy, and what bounds it is the order.

The quantity has a classical name #

The measurement here is a discrepancy in the sense the term is used outside this subject, and connecting it to that literature says exactly which chains have the property.

The chain is a coding of an irrational rotation. Each tile’s position in the chain corresponds to a point of an orbit stepping round a circle by a fixed irrational amount, and a block’s frequency in a window is the proportion of the first so many orbit points landing in a particular arc.

How evenly an orbit fills the circle is the discrepancy of the sequence, a quantity studied since Weyl. For a general irrational the discrepancy grows slowly and without bound — logarithmically, typically — so the error in a frequency falls slightly more slowly than one over the window.

Boundedness is the special case, and it holds exactly when the rotation’s continued fraction has bounded partial quotients. The golden ratio’s are all ones, the smallest they can be, so the Fibonacci chain sits at the extreme of the good behaviour rather than merely inside it.

Which means the exponent measured here is not shared by every quasiperiodic chain. A chain built from a slope with occasional large partial quotients has stretches over which it behaves almost periodically with the wrong period, and its worst-case error over a window is correspondingly larger. The chain measured here is the best case, and knowing that is what keeps the number from being read as a general fact about aperiodic order.

What the exponent costs in practice #

The difference between the two exponents sounds like a technicality and it is a statement about how much material a measurement needs.

Take a target precision of one per cent in some frequency. On the chain, an error falling as one over the length reaches it at a window of about a hundred tiles. On the shuffle, an error falling as one over the square root reaches it at about ten thousand.

A factor of a hundred in sample size, for the same answer to the same precision — and at one part in a thousand it becomes a factor of a thousand.

So the ordered chain is not merely tidier; it is cheaper to measure. Any quantity that is an average over the structure — a composition, a bond-length distribution, an intensity — settles in a small region of a quasiperiodic material and needs a large region of a disordered one.

And that is the practical content of long-range order without repetition. A crystal gives the answer in one cell. A random arrangement demands a large sample. A quasicrystal is nearer the first than the second, and this measurement is how much nearer.