Spectra of substitution systems
Questions that turn out to be related to spectra of substitution systems have arisen in various areas of pure mathematics since the late 1800s. In the 1980s, particularly following discoveries in iterated maps and quasicrystals, studies of such spectra were made in the context of number theory and dynamical systems theory. Some general principles were proposed, but a great many exceptions were always eventually found.
As suggested by the pictures in the main text, spectra such as (b) and (d) in the limit consist purely of discrete Dirac delta function peaks, while spectra such as (a) and (c) also contain essentially continuous parts. There seems to be no simple criterion for deciding from the rule what type of spectrum will be obtained. (In some cases it works to look at whether the limiting ratio of lengths on successive steps is a Pisot number.) One general result, however, is that all so-called Sturmian sequences Round[(n + 1) a + b] - Round[n a + b] with a an irrational number must yield discrete spectra. And as discussed on page 903, if a is a quadratic irrational, then such sequences can be generated by substitution systems.
For any substitution system the spectrum ϕ[i][t, ω] at step t from initial condition i is given by a linear recurrence relation in terms of the ϕ[j][t - 1, ω]. With k colors each giving a string of the same length s the recurrence relation is
Thread[Map[ϕ[#][t + 1, ω] &, Range[k] - 1] Apply[Plus, MapIndexed[Exp[ ω (Last[#2] - 1) st] ϕ[#1][t, ω] &, Range[k] - 1 /. rules, {-1}], {1}]/√s]
Some specific properties of the examples shown include:
(a) (Thue–Morse sequence) The spectrum is essentially Nest[Range[2 Length[#]] Join[#, Reverse[#]] &, {1}, t]. The main peak is at position 1/3, and in the power spectrum this peak contains half of the total. The generating function for the sequence (with 0 replaced by -1) satisfies f[z] (1 - z) f[z2], so that f[z] Product[1 - z2n, {n, 0, ∞}]. (Z transform or generating function methods can be applied directly only for substitution systems with rules such as {1 list, 0 1 - list}.) After t steps a continuous approximation to the spectrum is Product[1 - Exp[2s ω], {s, t}], which is an example of a type of product studied by Frigyes Riesz in 1918 in connection with questions about the convergence of trigonometric series. It is related to the product of sawtooth functions given by Product[Abs[Mod[2s ω, 2, -1]], {s, t}]. Peaks occur for values of ω such as 1/3 that are not well approximated by numbers of the form a/2b with small a and b.
(b) (Fibonacci-related sequence) This sequence is a Sturmian one. The maximum of the spectrum is at Fibonacci[t]. The spectrum is roughly like the markings on a ruler that is recursively divided into {GoldenRatio, 1} pieces.
(c) (Cantor set) In the limit, no single peak contains a nonzero fraction of the power spectrum. After t steps a continuous approximation to the spectrum is Product[1 + Exp[3s 2 ω], {s, t}].
(d) (Period-doubling sequence) The spectrum is (2# - (-1)# &)[1 + IntegerExponent[n, 2]], almost like the markings on a base 2 ruler.
(See also page 917.)