An aperiodic chain whose peaks are all at rational positions

Two ideas usually arrive together in the story of aperiodic order, and the period-doubling chain is the clearest case of their coming apart. The first idea is that a structure can diffract in sharp peaks without being periodic: order is not periodicity. The second is how that happens. The standard account, the one quasicrystals made famous, is that the structure is a slice through a periodic structure in more dimensions. The Fibonacci chain is a line cut through a square lattice at an irrational slope, and its peaks sit at irrational positions, combinations of 1 and the golden ratio, which is the shadow of the square lattice’s second dimension.

The period-doubling chain is built by the substitution $a \to ab$, $b \to aa$. Neither a peak nor a bump used it as a control: its strongest peak grows with the square of the chain’s length, as a Bragg peak must, so its diffraction is sharp, like the Fibonacci chain’s and unlike Thue–Morse’s. That essay measured how strong the peak was and did not ask where it was.

It is at a rational position, and so is every other peak the chain has. The peaks are at the fractions $m/2^r$, all of them, with heights that depend only on the denominator, and nowhere else. The chain is aperiodic, it diffracts sharply, and it is not a slice of anything. It is a different kind of order from the Fibonacci chain’s, and the difference is visible in exactly one place, the positions of the peaks.

A chain made of periodic chains #

The substitution builds the chain by doubling: $a$, $ab$, $abaa$, $abaaabab$, and so on, each word the start of the next. There is a second description, which is the one that explains everything below. Number the letters from zero. Letter $n$ is $b$ exactly when the power of two dividing $n + 1$ is odd: $n + 1 = 2, 8, 24, 32, \ldots$ give $b$, and $n + 1 = 1, 3, 4, 5, 12, 16, \ldots$ give $a$. The two descriptions agree on the first 4,096 letters, letter by letter, and the induction that proves they agree for ever is two lines, since the substitution sends position $n$ to positions $2n$ and $2n + 1$.

Sort the sites by that power of two. The sites with $n + 1$ odd, every second site, all carry $a$. Those with $n + 1$ twice an odd number, every fourth site, all carry $b$. Those with $n + 1$ four times an odd number, every eighth site, carry $a$, and so on. Each of these layers is perfectly periodic, layer $j$ with period $2^{j+1}$, and each carries a single letter, $a$ for even $j$ and $b$ for odd.

The chain is therefore the union of infinitely many periodic chains, each filling in the gaps the previous ones left. A sequence built this way is called a Toeplitz sequence, after Otto Toeplitz, who used the construction in the 1920s. It is aperiodic because a period would have to be a multiple of every layer’s period, $2, 4, 8, \ldots$ without end. On 4,096 letters the chain has no period shorter than 2,048, while the chain with every layer from the sixth onward replaced by $a$ repeats every 64 letters.

A structure built like this is called limit-periodic. It differs from a periodic structure on a set of sites as thin as one likes, and from each such periodic structure on a set of positive density that halves with every layer added. That is a different relation to periodic order from the Fibonacci chain’s, as the approximants below make plain.

The rule is a number written in binary #

The second description is less arbitrary than it looks. Write $n + 1$ in binary. The substitution reads it from the right: doubling a position appends a zero to its binary expansion, and the letter at a position depends only on how many zeros its $n + 1$ ends in, $a$ for an even number and $b$ for an odd one. Every other digit is ignored. The chain is a function of the trailing zeros alone.

That is what makes its layers periodic. The numbers ending in exactly $j$ zeros are those whose last $j + 1$ binary digits are a one followed by $j$ zeros, and a pattern fixed in the last $j + 1$ digits recurs every $2^{j+1}$ numbers. A rule that looked at a digit further to the left, or at all of them, would make layers that are not periodic, and the next sections would not go through. The Thue–Morse chain is that case. Its letter at $n$ is the parity of the number of ones in $n$’s binary expansion, which depends on every digit, and its diffraction has no peaks except at the integers.

The same reading gives the chain’s statistics without any computation. Half of all numbers end in no zeros, a quarter in one, an eighth in two, so the density of $b$ is $\frac14 + \frac1{16} + \cdots = \frac13$, and the frequency of every longer patch is a dyadic rational too, which how often each patch occurs found as the reason the constant-length chains have so few distinct frequencies.

Where the peaks are #

The diffraction of the chain, with a unit scatterer on every $b$ site, is computed from the Fourier amplitude

$$A(k) = \lim_{N\to\infty} \frac1N \sum_{n < N,\ \text{$n$ is } b} e^{-2\pi i k n},$$

and a Bragg peak at $k$ is a non-zero limit. Because the $b$ sites are a union of layers, $A(k)$ is a sum of the layers’ amplitudes, and each layer’s amplitude is that of a periodic comb, which is known exactly. Layer $j$ is the set of $n$ with $n + 1$ a multiple of $2^j$ and not of $2^{j+1}$. At a frequency $k = m/2^r$ with $m$ odd, the comb of period $2^j$ has amplitude $2^{-j}$ if $2^j k$ is a whole number and zero otherwise. The difference of the two combs is therefore

$$A_j\!\left(\frac{m}{2^r}\right) = \begin{cases} 2^{-j-1} & j \ge r, \\ -2^{-r} & j = r - 1, \\ 0 & j < r - 1, \end{cases}$$

up to a phase from the shift by one. Summing over the odd $j$, the layers that carry $b$, the series is geometric with ratio a quarter, and it comes out the same in both cases. If $r - 1$ is odd, the negative term is included and the rest sums to a third of it. If not, only the positive terms count. Either way,

$$|A(m/2^r)| = \tfrac23 \cdot 2^{-r},$$

whatever the odd $m$. At $k = 0$ the amplitude is the density of $b$, which is $\frac14 + \frac1{16} + \cdots = \frac13$.

The measurement on a finite chain agrees with the formula at all 64 frequencies up to denominator 64, to better than $10^{-4}$ on 4,096 letters. The pattern is visibly self-similar. Half the positions between two peaks of denominator $2^r$ hold a peak of denominator $2^{r+1}$, half as high. The strongest peak after the one at zero is at $k = \frac12$, with the same amplitude as the zero peak, then two at $\frac14$ and $\frac34$, then four at the eighths.

And there are no peaks anywhere else. At a frequency that is not a fraction with a power of two below, every layer’s amplitude vanishes, so the sum does too. The finite chain shows it as a decay. At $k = \frac38$ the amplitude settles on $\frac1{12}$ by 256 letters and stays there to 65,536. At $1/\tau$, at $\sqrt2 - 1$ and at $\frac13$, it falls by two orders of magnitude or more over the same range, to about $10^{-4}$ or less in all three.

The sum also says something the figure cannot, about phases. Up to the phase from the shift by one, the amplitude at $m/2^r$ is $+\frac23 \cdot 2^{-r}$ when $r$ is odd and $-\frac23 \cdot 2^{-r}$ when $r$ is even: the sign records the parity of the exponent, because it records whether the layer that subtracts, $j = r - 1$, is one of the layers that carry $b$. A diffraction experiment measures intensities and loses the sign, so the heights in the figure are all a measurement could give. Whether the intensities alone single out this chain among all chains with peaks of the same heights, as the layer construction suggests, is a question of the kind the phase problem poses for every structure, and it is not settled here.

The frequency $\frac13$ is worth singling out, because it is rational and still not a peak. Rational is not enough. Only denominators that are powers of two appear, because only periods that are powers of two appear among the layers. A Toeplitz chain built from layers of period $3^j$ would put its peaks at the fractions $m/3^r$ instead.

All the intensity is there #

A diffraction pattern can be sharp in places and diffuse elsewhere; the Thue–Morse chain is diffuse everywhere except at the integers. Parseval’s identity settles how much of the period-doubling chain’s scattering is in its peaks. The total intensity of the $b$ sites, averaged per site, is their density, $\frac13$. The peaks carry $\frac19$ at zero and, at each denominator $2^r$, $2^{r-1}$ peaks of intensity $\frac49 \cdot 4^{-r}$, which is $\frac29 \cdot 2^{-r}$ together. Summed over every denominator that is $\frac29$, and with the zero peak it is $\frac13$.

So the peaks carry all of it. There is no diffuse background at all: the chain’s diffraction is pure point, as Dekking’s coincidence condition for substitutions predicted and the earlier essay’s growth exponent of 2.007 measured. Here it is a sum that closes, with each new denominator contributing exactly half of what the coarser ones left over.

What a diffractometer would make of it #

A crystallographer meeting this pattern would not see a chain. They would see spots at rational positions, index them on a supercell, and call it a superstructure. The question is which supercell, and the answer depends on the instrument rather than on the structure. The spots of denominator $2^r$ have intensity $\frac49 \cdot 4^{-r}$, so each generation is a quarter as strong as the one before, and generation $r$ is $4^{-(r-1)}$ of the strongest spot at $k = \frac12$. A measurement that sees spots down to $10^{-4}$ of the strongest finds every generation to $r = 7$, and indexes all it sees on a cell 128 sites long. Every fourfold gain in sensitivity adds a generation and doubles the cell, and every cell indexes every spot seen so far.

That is unlike an ordinary superstructure, where the spots say the cell and a longer measurement adds nothing new. It is also unlike an incommensurate modulation, where some spot refuses to be indexed on any cell and the need for an extra integer shows at once. A limit-periodic structure is indexable on some cell at every finite sensitivity, and on no cell at all. The evidence that a structure is limit-periodic rather than a long-period superstructure is not any single spot but the pattern of their heights, a quarter per generation, continuing past the point where a superstructure of the fitted cell would stop.

Approximants that never move their peaks #

The difference from the Fibonacci chain is clearest in the approximants. Cut the period-doubling chain off after layer $r$, replacing every later layer by $a$, and the result is periodic with period $2^r$. Its peaks lie at multiples of $2^{-r}$, which are among the chain’s own peaks. As $r$ grows, the approximant’s peak at a given dyadic position climbs toward the chain’s value, because the layers it is missing are the ones whose amplitudes are smallest. The positions never move. An approximant’s diffraction is the chain’s with the finest peaks not yet resolved, and those it has are already in the right places.

The Fibonacci chain’s approximants behave in the opposite way. An approximant of period 89, the crystal that rounds τ off to $\frac{55}{89}$, has its strongest peak at $\frac{55}{89} = 0.61798$. The chain’s is at $1/\tau = 0.61803$. The next approximant puts it at $\frac{89}{144}$, on the other side. Every approximant’s peaks are in the wrong place, by an amount that shrinks as the square of the period, and the chain’s peaks are at positions no periodic crystal has. The period-doubling chain is a limit of periodic crystals in the strongest sense: its diffraction is the union of theirs. The Fibonacci chain is a limit of periodic crystals only in the sense that their peaks converge to somewhere none of them has been.

Why no lattice can produce it #

Cut and project builds an aperiodic structure by slicing a lattice in a higher-dimensional space, and the structure’s peaks then lie on the projection of that lattice’s reciprocal lattice. For the Fibonacci chain the lattice is the square lattice, the projection of its reciprocal lattice onto the line is the set of numbers $p + q/\tau$, and that set is generated by two numbers. In general a lattice in $d$ dimensions projects to a set of peak positions generated by $d$ numbers, the Fourier module, which is the object superspace crystallography indexes with $d$ integers per peak.

The period-doubling chain’s peak positions are the dyadic rationals, all the fractions $m/2^r$. That set is not generated by any finite number of its elements: any finite set of them has a largest denominator, and everything they generate has that denominator or smaller. No lattice in any finite number of dimensions has the period-doubling chain as a slice, because no lattice’s reciprocal lattice projects onto the dyadic rationals. Indexing its peaks would need infinitely many integers.

There is still a cut-and-project description, and it is strange. Baake, Moody and Schlottmann showed that period doubling is a model set whose internal space is not a Euclidean space at all but the 2-adic integers, numbers written with infinitely many binary digits to the left. A site’s place in the 2-adic window is its $n + 1$ read as a 2-adic number, and its letter is fixed by how many zeros that number ends in. That is the layer picture in different words. The superspace of a limit-periodic chain is real, and it is not a space in which a crystallographer could draw a lattice.

What the account has to refuse #

The refused claim is the one the Fibonacci chain teaches: that sharp diffraction from an aperiodic chain means peaks at irrational positions. At $1/\tau$ the period-doubling chain’s amplitude is $6 \times 10^{-5}$ on 16,384 letters and falling, where a Bragg peak would hold a fixed height. The other tests guard the account’s pieces separately. The two constructions of the chain must agree letter by letter, the formula must match a direct sum at all 64 frequencies, and the intensities must add to the density without remainder. A slip in the layer sum, a sign in the subtracting term, for instance, would have shown up as peaks of the wrong height at every second denominator.

What the figures cannot show #

Every figure shows a finite chain, and the claims are about an infinite one. A finite chain of $N$ letters has a Fourier transform that is nowhere exactly zero and peaks of width $1/N$. The figures make the distinction by the way amplitudes behave as $N$ grows, holding or decaying, which is the operational meaning of a Bragg peak, but no finite computation proves that an amplitude decays to zero rather than to something small. The proof that there are no peaks away from the dyadic rationals is the layer sum, which gives zero exactly.

The convention matters too. The amplitudes here are those of a unit scatterer on each $b$ site. A chain with scattering lengths $f_a$ and $f_b$ on the two kinds of site has the same peak positions and heights scaled by $|f_b - f_a|$, apart from the peak at zero, which collects the average. The rational positions do not depend on the scattering, only on the arrangement.

And the figures cannot show what a real crystal with this order would look like. Limit-periodic order appears in theoretical models built from hierarchical interactions, but no crystal is established to have it in the way quasicrystals are established to have Fibonacci-like order. What this essay shows is that sharp diffraction at rational positions does not by itself mean a periodic crystal, which is a statement about inference rather than about any material.

Who worked it out #

Toeplitz sequences are named for Otto Toeplitz, and Jacobs and Keane studied them as dynamical systems in 1969. The pure point spectrum of period doubling follows from Dekking’s coincidence criterion of 1978. Its description as a model set with 2-adic internal space is due to Baake, Moody and Schlottmann, in 1998, and the explicit peak heights are worked through in Baake and Grimm’s Aperiodic Order of 2013. The layer computation, the Parseval account and the comparison of approximants are made here.

Still open: what a stacking fault does to a limit-periodic chain #

Neither a peak nor a bump found that the Thue–Morse chain, a close relative built by $a \to ab$, $b \to ba$, has no peaks except at the integers. Thue–Morse is a layer chain too, in a sense: its letter at $n$ is the parity of the number of ones in $n$’s binary expansion, which depends on every digit and not only on the trailing zeros. The question that sits between the two is what happens to period doubling’s peaks when a fraction of its layers is randomised, as a stacking fault randomises the layers of a real stack. Randomising every layer from the $r$-th on should leave the peaks of denominator below $2^r$ untouched and turn the rest into diffuse scattering, so that the diffraction becomes a crystal’s with partly filled sites, a quantity how much of the hat is a crystal measured for the hat. Whether a random choice made once per layer, rather than once per site, can produce intensity that is neither peaks nor smooth background is a computation on the same chains, and it has not been made.