A chain with no mirror has mirrors everywhere

A chain’s windows have been counted three ways before. n plus one, and no fewer counted how many different windows of each length a chain can show, and found that the Fibonacci chain shows $n + 1$, the fewest any aperiodic chain can manage. Every patch comes back measured how soon each window recurs. How often each patch occurs found each window’s frequency as an entry of an eigenvector. None of the three asked the question a crystallographer asks first of any pattern: which of those windows are symmetric?

In a chain of tiles the only symmetry a window can have, besides a translation, is a mirror: a window that reads the same from right to left as from left to right. A palindrome, in other words. The Fibonacci chain as a whole has no mirror. There is no point about which the infinite chain reflects onto itself, for the same reason it has no translation: order is not periodicity, and a mirror of the whole chain would pin down its structure as rigidly as a period would. But a palindrome is a mirror that holds only locally, over a stretch of the chain, and the question is how many of those it has, and how they are spread.

The answer is exactly one of each even length and exactly two of each odd length, for ever, and that pattern belongs to the Sturmian chains and to nothing else. The windows of a chain with no mirror are organised around mirrors as rigidly as their count is.

A local mirror at every scale #

The picture at the head of this essay is a stretch of the chain with every long palindrome marked. Each arc spans a window that reads the same in both directions, and each tick is where a mirror would stand if the chain ended at the arc’s feet. Some arcs are short and close together, and some span most of the stretch drawn. They overlap freely, because two windows can each be symmetric about different centres. Longer mirrors are rarer, and none is infinite. Wherever a palindrome ends, the letters beyond its two ends differ, and that pair of letters is where the chain’s lack of a global mirror becomes visible.

Every window of the Fibonacci chain, palindrome or not, also has its reversal among the chain’s windows. The chain’s collection of windows is closed under reversal, which is the statement that a mirror maps the chain onto a chain with exactly the same patches, although not onto itself. That is what makes the palindromes possible at all. A chain whose windows were not closed under reversal could have long palindromes only by accident, and the random chain below does not.

One, two, one, two #

Counting the palindromes of each length among the chain’s windows gives the palindromic complexity, $P(n)$. It sits beside the ordinary complexity $p(n)$, the number of distinct windows of length $n$, and it is measured the same way: every window of the chain is listed, and the distinct palindromes of each length are counted.

For the Fibonacci chain the count is two, one, two, one, and so on without end. The two palindromes of length one are the letters L and S. The one of length two is LL, since two short tiles never touch. The two of length three are LSL and SLS, the one of length four is SLLS, the two of length five are LSLSL and LLSLL, and the one of length six is LSLLSL. Each longer palindrome contains shorter ones at its centre, so the list is a set of nested mirrors: SLLS has LL at its middle, and LSLLSL has SLLS. At every length up to thirty the number found on half the chain equals the number found on all of it, so no palindrome was missed for want of length.

The silver-ratio chain, built by a different substitution, and a chain made by cutting and projecting a lattice at the golden slope show exactly the same pattern, two and one alternately at every length. These three are Sturmian chains, the chains with exactly $n + 1$ windows of each length. Droubay and Pirillo proved in 1999 that the one–two pattern of palindromes characterises them among aperiodic chains.

The controls show how special the pattern is. The Thue–Morse chain has two palindromes of each length up to four, then none of any odd length and two or four of each even length. Period-doubling has none of any even length past two, and three or four of each odd length. A periodic chain of period seven settles to exactly one palindrome of each length, because it has genuine mirrors whose palindromes are infinite. A pseudo-random chain has more palindromes than any of them at short lengths, sixteen or thirty-two, and then runs out almost at once. Its windows are not closed under reversal, and a long palindrome in it is a coincidence the chain is too short to contain.

Why one and two: a reflection of a circle has two fixed points #

The one–two pattern has a picture behind it, and it is the picture three gaps, and never four drew. A Sturmian chain is the record of a line of irrational slope crossing a lattice, and equivalently of a point stepping round a circle by a fixed irrational fraction $\alpha$ of a turn, writing L or S according to which arc it lands in. The window of length $n$ that starts at a given place in the chain is decided by where on the circle the point starts. The $n + 1$ points $0, -\alpha, -2\alpha, \dots, -n\alpha$ cut the circle into $n + 1$ arcs, one for each window, which is the $n + 1$ of the window count read geometrically.

Reversing a window corresponds to reflecting the circle. The windows are closed under reversal because the arcs, taken together, are carried onto themselves by a reflection of the circle: the set of cutting points is symmetric about a suitable axis. A palindrome is a window equal to its own reversal, so it is an arc that the reflection carries onto itself. An arc can be carried onto itself only if it contains one of the reflection’s fixed points in its interior, and a reflection of a circle has exactly two fixed points, at opposite ends of its axis.

So the count comes down to whether each fixed point lies inside an arc or on one of the cutting points, and parity decides it. The reflection pairs up the cutting points, except any cutting point that is itself fixed. When $n$ is even there are $n + 1$ cutting points, an odd number, so at least one must lie at a fixed point of the reflection. That fixed point is used up as a cutting point, only the other one lies inside an arc, and there is one palindrome. When $n$ is odd there are $n + 1$ cutting points, an even number, and for an irrational $\alpha$ neither fixed point is a cutting point. Both lie inside arcs, and there are two.

The argument uses nothing about the Fibonacci chain beyond its being a rotation of a circle by an irrational angle. That is why the silver-ratio chain and every other Sturmian chain obey the same count, and why a periodic chain, whose rotation is rational, can break it: its cutting points eventually coincide and the count settles to one. It also explains why the palindromes nest. The arc containing a fixed point at length $n + 2$ lies inside the arc containing it at length $n$, and the longer palindrome contains the shorter one at its centre.

The identity that makes it rigid #

The one–two pattern is not an independent fact about the Fibonacci chain. It follows from the chain’s window count by an identity that holds for any chain whose windows are closed under reversal:

$$P(n) + P(n + 1) \;\le\; p(n + 1) - p(n) + 2 .$$

The palindromes of two neighbouring lengths are bounded by the number of new windows the length step creates, plus two. The argument, due to Baláži, Masáková and Pelantová, runs through the graph whose vertices are the windows of length $n$ and whose edges are those of length $n + 1$. A palindrome of odd length sits at a branching point that the reversal maps to itself, and a palindrome of even length on an edge that the reversal maps to itself. A graph with $\Delta p(n)$ extra branches has only so many self-reverse places, and the bound counts them.

For a Sturmian chain $p(n + 1) - p(n) = 1$ at every length, so the right side is three, and the one–two pattern gives exactly three on the left. The Fibonacci chain uses every palindrome the identity allows it. That is a strong statement, and it is not true of every chain with the same kind of order. Thue–Morse has more new windows at each step, so its bound is higher, and its palindromes fall short of the bound at most lengths. The shortfall is exactly the mirrors Thue–Morse’s windows could have had and do not. Period-doubling, a different chain again, meets its bound at every length, with larger and changing numbers on both sides. So the equality is not a property of Sturmian chains alone, and the one–two pattern is: it is the equality evaluated at the smallest window growth an aperiodic chain can have. Period-doubling shows what the equality looks like at a larger growth. Its windows multiply faster than the Fibonacci chain’s, and its palindromes keep pace with them exactly, three or four of every odd length and none of any even length past two, so that every self-reverse place the graph of its windows offers is occupied. It is as rich in mirrors as its window count allows, which is a different chain reaching the same extremal condition from a different complexity.

As many palindromes as letters #

A second way to see the same rigidity reads the chain from its start rather than by length. Add letters one at a time and ask, after each, how many distinct palindromes the letters so far contain. Each new letter can create at most one palindrome never seen before, and it can only be the longest palindrome that ends at the new letter. So a word of $N$ letters contains at most $N$ distinct non-empty palindromes. A word that attains this on every prefix is called rich.

The Fibonacci chain is rich: across the first fifteen hundred letters, every single letter completes a palindrome that has not occurred before. So do the other two Sturmian chains, and so does period-doubling, which the identity already suggested, since for chains closed under reversal richness and the equality in the identity are the same condition. Thue–Morse loses one potential palindrome in about seven letters, two hundred and twelve in the first fifteen hundred. The random chain has stopped gaining after a few dozen letters and gains only rarely after that.

Richness says something about how the chain is built. A letter that completes no new palindrome is one whose longest mirrored ending was already a window somewhere earlier: the chain has repeated a mirror structure without extending it. A rich chain never does. Every step along the Fibonacci chain extends its mirror structure, which is a strange property for a chain with no mirror, and it is the mirror image of the property the window count expresses: each step along the chain in length adds exactly one new window.

Where the mirrors stand #

Counting palindromes says how many kinds of mirror the chain has. It does not say how they are spread along it, and a reader might suspect that long mirrors cluster in a few favoured places. They do not.

For each length $n$ the census finds every centre along four thousand positions of the chain at which a palindrome of at least $n$ tiles stands, and the widest gap between consecutive ones. On the Fibonacci chain the gap is about one and a half tiles for mirrors of two, four for mirrors of eight, ten and a half for mirrors of thirty-two: it grows in proportion to the mirror’s own size. So a mirror of any size is never far away, measured in its own length. It is the mirror version of linear repetitivity, which says the same of every window, and it follows from it, since every palindrome is a window and every window recurs within a bounded multiple of its length.

The density of mirror centres falls in step. Of the four thousand positions examined, counting both the positions on letters and those between them, 76 per cent are centres of a palindrome at least two tiles long, 47 per cent of one at least four, 29 per cent of one at least eight, 18 per cent of one at least sixteen and 11 per cent of one at least thirty-two. Each doubling of the mirror’s size keeps about sixty-two per cent of the centres, close to the reciprocal of the golden ratio, although a ratio measured over five doublings on one stretch of chain is a pattern and not a law. Even a mirror thirty-two tiles wide stands at one position in nine.

Thue–Morse behaves the same way, with a gap of exactly $n$ for mirrors of $n$. The periodic chain is different in kind. It has true mirrors, so palindromes of any length stand at two fixed centres in every period, and the gap stops growing at three and a half tiles. The random chain’s long mirrors thin out much faster than their length grows, and none of more than about sixteen tiles occurs at all in four thousand positions.

A mirror everywhere is not a mirror #

It is tempting to conclude from all this that the Fibonacci chain is mirror-symmetric after all, in some averaged sense: every window has its mirror image somewhere in the chain, mirrors of every size stand everywhere, and every letter extends the mirror structure. The census refuses the conclusion.

The refusal rests on the gaps. A mirror of the whole chain would be a palindrome of infinite length, and the chain would then have mirrors of every size at one fixed centre. The periodic chain does have that, and its gap stops growing. In the Fibonacci chain the gap between mirrors of size $n$ keeps growing with $n$, so no single centre carries mirrors of every size, and the local mirrors never assemble into a global one. What the chain has instead is the property that the symmetry of an average describes from the other side: the collection of its patches is mirror-symmetric, while no individual arrangement of them is. In a quasicrystal every local symmetry of this kind recurs, which is why a five-fold axis seen in a diffraction pattern tells so little about whether any atom of the structure sits on one.

Still open: palindromes in the plane #

A palindrome is a local mirror of a chain. The plane analogue is a patch of a tiling carried onto itself by a reflection or a rotation about its own centre. The Penrose tiling is full of patches with five-fold rotational symmetry, and how many patches of each size counted its patches without asking which were symmetric. Whether the symmetric patches of a two-dimensional quasiperiodic tiling obey a rigid count like the one–two pattern, and whether some tilings are rich in the corresponding sense, extending their local symmetry at every step, is the plane question this chain answers in one dimension. The counting is the same kind of computation, run on patches instead of windows, and it has not been run here.