Examples of Substitution Systems and Their Factors

Michael Baake and Franz Gähler Fakultät für Mathematik Universität Bielefeld Postfach 100131 33501 Bielefeld Germany

             mbaake@math.uni-bielefeld.de
             gaehler@math.uni-bielefeld.de

Uwe Grimm Department of Mathematics and Statistics The Open University Walton Hall Milton Keynes MK7 6AA United Kingdom

                 uwe.grimm@open.ac.uk

Abstract

The theory of substitution sequences and their higher-dimensional analogues is intimately connected with symbolic dynamics. By systematically studying the factors (in the sense of dynamical systems theory) of a substitution dynamical system, one can reach a better understanding of spectral and topological properties. We illustrate this point of view by means of some characteristic examples, including a rather universal substitution in one dimension as well as the squiral and the table tilings of the plane.

Dedicated to Jean-Paul Allouche on the occasion of his 60th birthday

1 Introduction

Closed subshifts over finite alphabets are much studied dynamical systems [37, 34]. Their understanding in one dimension is a cornerstone of the theory of (symbolic) dynamical systems, while systems in higher dimensions show many new phenomena [46]. It is probably fair to say that in the latter case, despite great effort, the open questions still prevail. The class of linearly repetitive symbolic dynamical systems (over finite alphabets) is special also in the sense that they possess finitely many (non-periodic) factors (up to isomorphism [24]), where the term ‘factor’ refers to symbolic dynamical systems that are the image of a homomorphism which commutes with the shift action (and not to finite subwords).

Nevertheless, the factors are rarely used explicitly to unravel (details of) the structure of the dynamical system. For certain aspects, however, they carry relevant information, and can be employed both for structural insight and for concrete calculations. This is particularly true for the spectral theory of symbolic dynamics. The latter comes in two flavors. The traditional point of view is via the dynamical spectrum [41], which analyzes the induced shift action on the Hilbert space of square integrable functions on the shift space (relative to an invariant probability measure). An alternative approach works with the diffraction spectrum [31, 48, 11] of a typical sequence in the space, which was originally motivated by the physical process of kinematic diffraction [22]. Its relevance increased with the discovery of quasicrystals by Shechtman et al. [47], particularly for systems with pure point (or Bragg) diffraction. Recent evidence [49] suggests that also continuous spectral components are practically relevant.

It is well understood by now that (and how) the two types of spectra are equivalent in the pure point case [36, 48, 17], while it has long been known that the dynamical spectrum is generally richer in the presence of continuous components [25, 13]. Nevertheless, in many of the classic examples, the complete dynamical spectrum can be reconstructed from the diffraction spectrum of the system and of some of its factors. This can be made more precise for systems of symbolic dynamics as well as for Delone dynamical systems with finite local complexity [12]. We will see examples of this type below, selected from the class of substitution systems with integer inflation factor; see [28, 26, 27, 35, 29] for background material.

Yet another, and rather recent, aspect is the topological structure of tiling spaces; see [45] and references therein. Here, the substitution or the inflation structure can effectively be used to calculate the Čech cohomology, for instance via the methods introduced in [7]. This provides concrete results, but their (geometric) interpretation is still difficult. This is another instance where the careful inspection of the factors can help to understand the detailed structure of the cohomology groups. We will explain this in some detail for a recently analyzed example, the so-called squiral tiling of the plane [30, 14].

Our approach in this article is example-oriented, wherefore we opted for a somewhat informal presentation, in the interest of better readability. We assume the reader to be familiar with the basic concepts of (symbolic) dynamics, compare [37, 43], and with some results from their spectral theory, see [41] for more. We begin with an example in one dimension that is deliberately designed to have interesting factors, and a rather rich spectrum as a result of this. We continue with some remarks on substitution factors with maximal pure point spectrum, before we embark on a more detailed analysis of the squiral tiling [30, 14] and its substitution factors. This is followed by a similar (though still somewhat preliminary) analysis of the classic table tiling [42].

2 A fun example: The ‘universal’ morphism

Undeniably, the best studied substitution rule (on the binary alphabet {a, b}) is given by ϱ_{F} : a ↦ ab, b ↦ a and known as the Fibonacci substitution (or morphism). It defines a unique hull 𝕏_{F} ⊂ {a, b}^{ℤ} that is strictly ergodic as a dynamical system under the action of the (two-sided) shift; see [6, 41, 40, 15] and references therein. It has pure point dynamical as well as pure point diffraction spectrum. In a similar way, one can treat all (repetitive) Sturmian sequences, a common feature being that they can all be described as model sets (also known as cut and project sets); see [38] as well as [40] for a survey. The equivalence of the two types of spectra is well understood for systems of this kind [36, 17, 18].

The relation between the dynamical and the diffraction spectrum is more complicated in the presence of continuous spectral components. This was first pointed out in [25] for the example of the Thue-Morse substitution, where the dynamical spectrum is richer. In particular, a substantial part of the pure point spectrum does not show up in the diffraction measure of the Thue-Morse chain, while it can be recovered from the diffraction of the period doubling chain. The hull of the latter is a factor of the Thue-Morse system [45, 10]. An analogous phenomenon was described in [13] for a system with close-packed dimers on ℤ, and is known to also occur for the Rudin-Shapiro chain [15]. The purpose of this section is to illustrate these connections with a single substitution rule that entails a mixed spectrum and possesses most of the above examples as factors.

Let us consider the alphabet {a, b, c, d, ā, b̄, c̄, d̄} and define the primitive substitution

ϱ : \begin{matrix}a & ↦ & ab̄ & ā & ↦ & āb \\ b & ↦ & ad̄ & b̄ & ↦ & ād \\ c & ↦ & cd̄ & c̄ & ↦ & c̄d \\ d & ↦ & cb̄ & d̄ & ↦ & c̄b \end{matrix}  (1)

which results in a unique hull, for instance via the two-sided sequence

w = … ab̄c̄bc̄dad̄c̄dcb̄ab̄c̄b|ab̄ādābcb̄ābad̄cd̄ād …

which is a fixed point under ϱ^{2} with legal seed b|a. The corresponding hull 𝕏 is obtained as the closure of the two-sided shift orbit of w in the product topology. Before we comment on the spectral structure, let us identify some relevant factors.

Upon identifying letters with their barred copies, one obtains the quaternary Rudin-Shapiro substitution [6, 41]

ϱ_{RS} : a ↦ ab , b ↦ ad , c ↦ cd , d ↦ cb ,

with induced fixed point w_{RS} of ϱ_{RS}^{2}, with legal seed b|a. This leads to the classic binary Rudin-Shapiro chain via the map φ defined by φ(a) = φ(b) = 1 and φ(c) = φ(d) = ¯1. For complexity results, we refer to [5]. The corresponding hulls fail to be palindromic [1, 8], which has interesting consequences for the spectral theory of associated Schrödinger operators. For further results on palindromic systems, we refer to [2] and references therein.

The binary and the quaternary Rudin-Shapiro hulls are mutually locally derivable (MLD); see [9] and references therein for the concept. In the symbolic setting, MLD just means that there are sliding block maps with local support [35] in both directions of the derivation. The non-trivial direction of this claim follows from the observation that ¯1¯1¯1¯1 is the longest 1-free subword of the binary image and has the unique preimage dcdc under φ. This determines the two cosets of ℤ modulo 2 that are occupied by the letters a, c and b, d, respectively. Due to repetitivity, the subword ¯1¯1¯1¯1 occurs with bounded gaps, wherefore this defines a local derivation rule. Consequently, both define dynamical systems with the same spectrum, which is known to comprise the pure point part ℤ[\frac{1}{2}] and an absolutely continuous component, the latter being Lebesgue measure with multiplicity 2; see [41] for details.

Let us go one step back, and define a sliding block map on 𝕏_{RS} that is induced by

\begin{matrix}χ(ab) = χ(cd) = A , χ(ad) = χ(cb) = B , \\ χ(ba) = χ(dc) = C , χ(da) = χ(bc) = D . \end{matrix}

Its action on 𝕏_{RS} is given by u ↦ u_{χ} with u_{χ}(i) := χ(u(i)u(i + 1)). This way, one induces the primitive substitution

ϱ_{T} : A ↦ AC , B ↦ AD , C ↦ BD , D ↦ BC ,

which shows a Toeplitz structure (see below) that is somewhat similar to that of the paper folding substitution; compare [3, 4, 15].

Let w_{T} be the fixed point of ϱ_{T}^{2} with legal seed C|A, which is the image of w_{RS} under the sliding block map induced by χ. This bi-infinite word leads to a partition of ℤ into four subsets Λ_{α} = {i ∈ ℤ | w_{T}(i) = α} for α ∈ {A, B, C, D}. The fixed point property then results in the equations

\begin{aligned}Λ_{A} & = 4ℤ , Λ_{B} = 4ℤ + 2 , \\ Λ_{C} & = (8ℤ + 1) ∪ (16ℤ + 11) ∪ (4Λ_{C} + 3) , \\ Λ_{D} & = (8ℤ + 5) ∪ (16ℤ + 3) ∪ (4Λ_{D} + 3) , \end{aligned}

where Λ_{A} ∪ Λ_{B} = 2ℤ and Λ_{C} ∪ Λ_{D} = 2ℤ + 1 was used to simplify the relations. Due to the decoupling, one can calculate the solutions via iteration, which gives

\begin{aligned}Λ_{C} & = \{−1\} ∪ ⋃_{n≥0}(2 · 4^{n+1}ℤ + (2 · 4^{n} − 1)) ∪ ⋃_{n≥1}(4^{n+1}ℤ + (3 · 4^{n} − 1)), \\ Λ_{D} & = ⋃_{n≥0}(2 · 4^{n+1}ℤ + (6 · 4^{n} − 1)) ∪ ⋃_{n≥1}(4^{n+1}ℤ + (4^{n} − 1)). \end{aligned}

Note that the singleton set {−1} has to be added to Λ_{C} because it is not contained in any of the lattice cosets (although it is in the 2-adic closure of either of the four unions). The only other fixed point of ϱ_{T}^{2} differs from w_{T} precisely in w_{T}(−1). It can thus be described by moving the singleton set {−1} from Λ_{C} to Λ_{D}. Our explicit coordinatization is a result of a coincidence in the sense of Dekking [23]. It implies that ϱ_{T} defines a dynamical system with pure point dynamical spectrum, which is ℤ[\frac{1}{2}]. The latter coincides with the pure point part of the spectrum of the Rudin-Shapiro system. This also follows from standard results; compare [26] and references therein.

Returning to the original substitution ϱ of Eq. (1) and mapping all ordinary letters to 1 and all barred ones to ¯1 = −1, one induces the Thue-Morse (or Prouhet-Thue-Morse) substitution

ϱ_{TM} : 1 ↦ 1¯1 , ¯1 ↦ ¯11 ,

formulated on the alphabet {1, ¯1}; compare [6] for background. Our original fixed point w is mapped to w_{TM} = ϱ_{TM}^{2}(w_{TM}) with legal seed 1|1. The dynamical spectrum of the corresponding hull 𝕏_{TM} under the shift action comprises a pure point part (namely ℤ[\frac{1}{2}]) and a singular continuous one, the latter leading to an explicit representation as a Riesz product [32, 41, 10].

Defining the sliding block map ψ on 𝕏_{TM} via ψ(w)(i) = −w(i)w(i + 1), one induces another classic substitution,

ϱ_{pd} : 1 ↦ 1¯1 , ¯1 ↦ 11 ,

which is known as the period doubling substitution; compare [6]. The image of w_{TM} under ψ is w_{pd} = ϱ_{pd}^{2}(w_{pd}), with legal seed ¯1|1. A coordinatization of w_{pd} via a partition of ℤ can be done in a similar way as discussed above for ϱ_{T}; compare [20]. Via the corresponding diffraction measure, this provides an alternative way to show that ℤ[\frac{1}{2}] is the dynamical spectrum of the associated dynamical system. It exhausts the pure point part of the dynamical spectrum of the Thue-Morse system.

Having analyzed these (selected) factors of our original substitution ϱ, we can conclude that the latter has mixed spectrum with all three spectral types being present. The maximal equicontinuous (or Kronecker) factor is the dyadic solenoid 𝕊_{2}^{1}, which also emerges via the ‘torus parametrization’ of the period doubling chain or the maximal model set factor of the Rudin-Shapiro chain. Let us explain this type of connection in a little more detail.

3 Substitution factors with maximal pure point spectrum

The Thue-Morse dynamical system has a dynamical spectrum of mixed type, with pure point and singular continuous components. As was pointed out in [25], the diffraction spectrum only detects part of it. In fact, it only shows the trivial part of the pure point spectrum, ℤ, while the rest is missing (or hidden). However, the period doubling system is a factor that is pure point, with dynamical spectrum ℤ[\frac{1}{2}], so that the diffraction of Thue-Morse together with that of period doubling covers the entire dynamical spectrum of Thue-Morse.

In fact, the period doubling system is a factor that lies between Thue-Morse and its Kronecker factor, the latter being the dyadic solenoid 𝕊_{2}^{1} [26, 45]. This happens to be the ‘torus’ for the period doubling system in the language of model sets [18], and the mapping from period doubling to the solenoid is 1-to-1 almost everywhere [20, 18].

The system of close-packed dimers on the line [13] provides an example where the dynamical spectrum has pure point and absolutely continuous components, as does Rudin-Shapiro. In both cases, the dynamical spectrum is richer, but the ‘missing’ parts again can be recovered from the analysis of a single factor. A similar situation shows up in many other examples, though not in all. Still, it is worth looking at this relation in some more detail.

A natural generalization of the Thue-Morse substitution, in the spirit of [33], is

ϱ_{gTM}^{(k,ℓ)} : \begin{matrix}a & ↦ & a^{k}b^{ℓ} \\ b & ↦ & b^{k}a^{ℓ} \end{matrix}

with k, ℓ ∈ ℕ, where k = ℓ = 1 is the classic TM substitution. The substitution matrix reads (\begin{matrix}k & ℓ \\ ℓ & k \end{matrix}), with eigenvalues k ± ℓ. This two-parameter family of constant length substitutions shares many properties with its classic ancestor; see [10] for a detailed analysis. In particular, there is a sliding block map that works for the entire family, and induces a maximal model set factor of substitution type. The latter is a generalization of the period doubling substitution, namely

ϱ_{gpd}^{(k,ℓ)} : \begin{matrix}a & ↦ & ub \\ b & ↦ & ua \end{matrix}

with the finite word u = b^{k−1}ab^{ℓ−1}. This is a constant length substitution with a coincidence in the sense of Dekking [23], and hence a model set [35]. This factor then has a torus parametrization [18] which is an almost everywhere 1-to-1 map onto a one-dimensional dyadic solenoid, which we denote by 𝕊_{2}^{1} as before.

Let us now discuss some two-dimensional examples, which are considerably more complex.

4 The squiral tiling and its factors

The squiral tiling appears in [30, Fig. 10.1.4], where it was constructed as a simple example for a tiling of the plane by one prototile (and its mirror image) with infinitely many edges. It is obtained from the primitive inflation rule

(2)

which has the (linear) integer inflation factor 3. When one distinguishes the two chiralities, it is obvious that the (colored) tiling is equivalent (in the sense of mutual local derivability [21, 9]) to a coloring of the square lattice that emerges from the block substitution

(3)

This block substitution is bijective and of constant length in the terminology of [26]. In this formulation, it was analyzed in detail in [14]. A larger patch is shown in Figure 1.

Figure 1: A square-shaped patch of the squiral tiling with full D_{4}-symmetry, as obtained from the block substitution (3). For this figure, the reference point of the prototiles is placed in their centers, so that the patch is the central part of a fixed point under the corresponding block substitution.

It follows from standard arguments [26, 27] that the dynamical spectrum of the squiral contains ℤ[\frac{1}{3}] × ℤ[\frac{1}{3}] as its pure point part. Moreover, the analysis of [14] shows that the remaining part of the spectrum is purely singular continuous. The corresponding diffraction measure is explicitly known, and can be represented as a two-dimensional Riesz product.

As the tiling is bijective [26], the block substitution (3) commutes with the exchange of the two colors. This implies that the hull of the squiral is also invariant under the exchange of the colors: with every tiling in the hull, also the tiling with inverted colors is in the hull. This is the deeper reason why the projection onto the underlying two-dimensional 3-adic solenoid 𝕊_{3}^{2} is at least 2-to-1, so that the (dynamical or diffraction) spectrum cannot be pure point. In particular, the squiral tiling cannot originate from a model set.

Our next step therefore is to find a factor in which pairs of tilings with inverted colors are identified. This is achieved with a sliding block map, which maps 2 × 2-blocks of tiles to some new symbols. The squiral tiling admits 14 distinct legal 2 × 2-patterns, as only the two blocks with four equal symbols are not allowed. In the following block map (in which we write the two colors as 1 and ¯1 = −1), pairs of blocks with inverted colors are identified, but nothing else,

\begin{matrix}± [\begin{matrix}1 & 1 \\ ¯1 & 1 \end{matrix}] ↦ a, ± [\begin{matrix}1 & 1 \\ 1 & ¯1 \end{matrix}] ↦ b, ± [\begin{matrix}1 & ¯1 \\ 1 & 1 \end{matrix}] ↦ c, ± [\begin{matrix}¯1 & 1 \\ 1 & 1 \end{matrix}] ↦ d, \\ ± [\begin{matrix}1 & 1 \\ ¯1 & ¯1 \end{matrix}] ↦ e, ± [\begin{matrix}1 & ¯1 \\ 1 & ¯1 \end{matrix}] ↦ f, ± [\begin{matrix}1 & ¯1 \\ ¯1 & 1 \end{matrix}] ↦ g. \end{matrix}  (4)

It is easy to see that any tiling in the image lifts to exactly two squiral tilings. There is one position where we can chose whether the lift has a 1 or a ¯1 there; all other tiles in the lift are then determined. Our factor map is therefore uniformly 2-to-1 on the entire hull of all squiral tilings. This is completely analogous to the hull of the (generalized) Thue-Morse chains from above, which project uniformly 2-to-1 to the hull of the (generalized) period doubling chains, under a similar sliding block map [10].

The block map (4) induces a primitive substitution on the tilings in the factor space,

\begin{matrix}a ↦ [\begin{matrix}g & g & a \\ d & c & g \\ a & b & g \end{matrix}] , b ↦ [\begin{matrix}f & f & b \\ d & c & g \\ a & b & g \end{matrix}] , c ↦ [\begin{matrix}f & f & c \\ d & c & e \\ a & b & e \end{matrix}] , d ↦ [\begin{matrix}g & g & d \\ d & c & e \\ a & b & e \end{matrix}] , \\ e ↦ [\begin{matrix}g & g & e \\ d & c & e \\ a & b & e \end{matrix}] , f ↦ [\begin{matrix}f & f & f \\ d & c & g \\ a & b & g \end{matrix}] , g ↦ [\begin{matrix}g & g & g \\ d & c & g \\ a & b & g \end{matrix}] . \end{matrix}  (5)

Obviously, the resulting tilings have a Toeplitz structure; compare [3]. They contain latticeperiodic subsets, which implies that they are model sets [35]. As such, they necessarily have pure point dynamical and diffraction spectra; compare [36]. In turn, the squiral tilings, whose hull is a 2-to-1 cover of a pure point factor, cannot have pure point spectrum. In fact, with suitable scattering strengths (+1 and −1 on the two symbols), their diffraction spectrum is purely singular continuous [14].

The tilings generated by the substitution (5) form the maximal model set factor of the squiral tiling, which we henceforth call F_{max}. This factor, in turn, has a two-dimensional, 3-adic solenoid 𝕊_{3}^{2} as factor, onto which it projects 1-to-1 almost everywhere via the torus parametrization of general model sets [18]. We shall now analyze in more detail the set of tilings where this projection fails to be 1-to-1.

For this purpose, we note that the level-n supertiles of the substitution (5) have the following block structure

\begin{matrix}a ↦ [\begin{matrix}G & a \\ X & G^{T} \end{matrix} ] , b ↦ [\begin{matrix}F & b \\ X & G^{T} \end{matrix} ] , c ↦ [\begin{matrix}F & c \\ X & E^{T} \end{matrix} ] , d ↦ [\begin{matrix}G & d \\ X & E^{T} \end{matrix} ] , \\ e ↦ [\begin{matrix}G & e \\ X & E^{T} \end{matrix} ] , f ↦ [\begin{matrix}F & f \\ X & G^{T} \end{matrix} ] , g ↦ [\begin{matrix}G & g \\ X & G^{T} \end{matrix} ] , \end{matrix}  (6)

where X is a square block of dimension (3^{n} − 1) (which is the same for all seven symbols), F and G are rows with entries f and g, while E^{T} and G^{T} are columns with entries e and g, respectively.

We can now arrange two supertiles such that the separating line between them passes near the origin. Two blocks X are then separated by a line in which all symbols are the same. There are four possibilities, two with a horizontal and two with a vertical separation line,

[\begin{matrix}X \\ F \\ X \end{matrix}] , [\begin{matrix}X \\ G \\ X \end{matrix}] , [X E^{T} X] , [X G^{T} X] .  (7)

Taking together all ways in which the boundaries of the supertiles can tend to infinity as the supertile order is increased, we obtain four one-dimensional model sets, two of which are arranged horizontally, and two vertically. Projected to 𝕊_{3}^{2}, the translation orbits of the horizontal pair project to a single translation orbit of a one-dimensional sub-solenoid of type 𝕊_{3}^{1}, and so do the translation orbits of the vertical pair.

If a quartet of infinite order supertiles is placed such that the common corner remains near the origin, the following configurations are obtained,

\begin{matrix}[\begin{matrix}X & E^{T} & X \\ G & a & F \\ X & G^{T} & X \end{matrix}] , [\begin{matrix}X & E^{T} & X \\ F & b & G \\ X & G^{T} & X \end{matrix}] , [\begin{matrix}X & G^{T} & X \\ F & c & G \\ X & E^{T} & X \end{matrix}] , [\begin{matrix}X & G^{T} & X \\ G & d & F \\ X & E^{T} & X \end{matrix}] , \\ [\begin{matrix}X & E^{T} & X \\ G & e & G \\ X & E^{T} & X \end{matrix}] , [\begin{matrix}X & G^{T} & X \\ F & f & F \\ X & G^{T} & X \end{matrix}] , [\begin{matrix}X & G^{T} & X \\ G & g & G \\ X & G^{T} & X \end{matrix}] . \end{matrix}  (8)

Each of these configurations represents a translation orbit in F_{max}, and all these orbits are projected to a single orbit in 𝕊_{3}^{2}. The configurations shown in (8) form the seeds of the seven fixed points of the substitution (5).

This structure of the hull is in line with the Artin-Mazur dynamical zeta function [44] of the substitution action on the hull of F_{max}. On the one hand, the zeta function is defined in terms of the periodic points in the hull under the substitution,

ζ(z) = exp (∑_{m=1}^{∞} \frac{a_{m}}{m} z^{m}) = ∏_{m=1}^{∞}(1 − z^{m})^{−c_{m}},  (9)

where a_{m} is the number of points in the hull that are invariant under an m-fold substitution. Likewise, the exponents c_{m} in the Euler product are the cycle numbers, which follow from the a_{m} via

c_{m} = \frac{1}{m} ∑_{d|m} μ(\frac{d}{m})a_{d},

where d runs through the divisors of m and μ denotes the Möbius function of elementary number theory; see [37, Ch. 6.4] for a detailed exposition. Note that if the hull consists of several components for which the periodic points can be counted separately, the total zeta function is obtained as the product of the partial zeta functions. In our case, according to the analysis above, F_{max} consists of one copy of 𝕊_{3}^{2}, two extra copies of one-dimensional solenoids 𝕊_{3}^{1} (above those points where the projection to 𝕊_{3}^{2} is 2-to-1), and four extra fixed points above the origin of 𝕊_{3}^{2}.

This structure of the hull and the dynamical zeta function can be confirmed by computing the dynamical zeta function by a second method, which is a by-product of the computation of the Čech cohomology of the hull via the Anderson-Putnam complex [7]. The Čech cohomology of the hull of a primitive substitution tiling is obtained as the direct limit of the substitution action on the Čech cohomology of a finite CW-complex that approximates the tiling space. Let A^{(m)} be the matrix of the substitution action on the m-th cochain group of the approximant complex. The zeta function is then given by [7, Thm. 9.1] as

ζ(z) = \frac{∏_{k odd} det(1 − zA^{(d−k)})}{∏_{k even} det(1 − zA^{(d−k)})} = \frac{∏_{k odd} ∏_{i}(1 − zλ_{i}^{(d−k)})}{∏_{k even} ∏_{i}(1 − zλ_{i}^{(d−k)})} ,  (10)

where the latter equality holds if all A^{(m)} are diagonalizable, with eigenvalues λ_{i}^{(m)}. Note that, instead of the action on the cochain groups, one can also take the action on the cohomology (with rational coefficients), as the extra terms in (10) cancel between numerator and denominator.

For the cohomology of the squiral tiling, we obtain

H^{2} = ℤ[\frac{1}{9}] ⊕ ℤ[\frac{1}{3}]^{2} ⊕ ℤ^{6}, H^{1} = ℤ[\frac{1}{3}]^{2}, H^{0} = ℤ,  (11)

while the factor F_{max} leads to

H^{2} = ℤ[\frac{1}{9}] ⊕ ℤ[\frac{1}{3}]^{2} ⊕ ℤ^{2} ⊕ ℤ_{2}, H^{1} = ℤ[\frac{1}{3}]^{2}, H^{0} = ℤ.  (12)

In particular, the cohomology of F_{max} contains torsion. Taking into account the eigenvalues with which the substitution acts on the cohomology, the zeta functions become

ζ_{sq}(z) = \frac{(1 − 3z)^{2}}{(1 − z)(1 − 9z)(1 − 3z)^{2}(1 − z)^{3}(1 + z)^{3}} = \frac{1}{(1 − z)(1 − 9z)(1 − z^{2})^{3}} , (13)

with fixed point numbers a_{m}^{(sq)} = 9^{m} + 4 + 3 · (−1)^{m}, and

\begin{aligned}ζ_{F_{max}}(z) & = \frac{(1 − 3z)^{2}}{(1 − z)(1 − 9z)(1 − 3z)^{2}(1 − z)^{2}} = \frac{1}{(1 − z)^{3}(1 − 9z)} \\ & = \frac{(1 − 3z)^{2}}{(1 − z)(1 − 9z)} · (\frac{1 − z}{1 − 3z} )^{2} · \frac{1}{(1 − z)^{4}} , \end{aligned}  (14)

with a_{m}^{(F_{max})} = 9^{m} +3. In the second line of (14), we have already expressed the zeta function of F_{max} as a product of the zeta function for 𝕊_{3}^{2} (where a_{m}^{(2)} = (3^{m} − 1)^{2}) the square of the zeta function for 𝕊_{3}^{1} (with a_{m}^{(1)} = 3^{m} − 1; compare sequence A024023 of [39]) and the zeta function for four extra fixed points. The corresponding zeta functions follow from [16]. Alternatively, since solenoids are inverse limit spaces, the cohomology can also be computed with the method from [7]. The zeta function of F_{max} clearly reflects the structure of F_{max} already determined earlier. In contrast, the zeta function of the squiral cannot be interpreted so easily.

There is a large number of further factors between F_{max} and the solenoid 𝕊_{3}^{2}. We have systematically studied those factors which can be obtained by identifying some of the seven symbols of the substitution (5), while still giving rise to a consistent substitution. Such identifications of symbols induce identifications of certain tilings projecting to the same point on 𝕊_{3}^{2}.

Under the identification of symbols f = g, pairs of tilings that project to the same point of the vertical sub-solenoid are identified, so that the splitting of preimages above that sub-solenoid is closed. What remains is a split horizontal sub-solenoid, and four extra fixed points. The cohomology group H^{2} loses the torsion part, and one term ℤ[\frac{1}{3}] is replaced by ℤ. Closing the splitting of the horizontal sub-solenoid with the identification e = g is completely analogous. Under the identification e = f = g, both 1d sub-solenoid splittings are closed. Only four extra orbits above the origin remain, and H^{2} = ℤ[\frac{1}{9}] ⊕ ℤ^{4}. From here, there are many ways to make further identifications. With each such identification, the multiplicity of the projection to the origin of 𝕊_{3}^{2} is reduced by 1, and so is the exponent of the ℤ^{k} term in H^{2}. An example of a smallest factor above 𝕊_{3}^{2} is obtained with the identifications a = b = c = d and e = f = g, with H^{2} = ℤ[\frac{1}{9}] ⊕ ℤ. Instead of closing the horizontal split solenoid right after the vertical one, it is also possible to begin with one or two of the identifications a = b and c = d. In such an operation, the exponent of the ℤ^{k} term of H^{2} drops by 1. Examples of MLD classes of the different factors are listed in Table 1.

5 The table tiling

Infinite legal patterns generated by the block substitution

0 ↦ [\begin{matrix}1 & 0 \\ 3 & 0 \end{matrix}]  1 ↦ [\begin{matrix}0 & 2 \\ 1 & 1 \end{matrix}]  2 ↦ [\begin{matrix}2 & 1 \\ 2 & 3 \end{matrix}]  3 ↦ [\begin{matrix}3 & 3 \\ 0 & 2 \end{matrix}]  (15)

are MLD to the well-known table tilings with mixed spectrum [42]. The geometric inflation rule is explained in Figure 2, and a larger patch is shown in Figure 3. Frettlöh [28] has independently shown that the table tilings cannot be described as model sets. Indeed, from the substitution (15), one can see that the four supertiles differ in every place, which is a generalisation of the bijectivity property. As a consequence, table tilings that consist of a single infinite order supertile occur in groups of four, which are pairwise different at every position, and which all project to the same point in the underlying solenoid 𝕊_{2}^{2}. This means that the projection to 𝕊_{2}^{2} is 4-to-1 almost everywhere. In such a situation, the spectrum must indeed be mixed, and the tiling space cannot be MLD to the hull of a model set.

multiplicity H^{2}  name / identifications
2-to-1 a.e. ℤ[\frac{1}{9}] ⊕ ℤ[\frac{1}{3}]^{2} ⊕ ℤ^{6}  squiral
v,h,4  ℤ[\frac{1}{9}] ⊕ ℤ[\frac{1}{3}]^{2} ⊕ ℤ^{2} ⊕ ℤ_{2} F_{max}
v,4  ℤ[\frac{1}{9}] ⊕ ℤ[\frac{1}{3}] ⊕ ℤ^{3}  f = g
v,3  ℤ[\frac{1}{9}] ⊕ ℤ[\frac{1}{3}] ⊕ ℤ^{2}  f = g, a = b or c = d
v,2  ℤ[\frac{1}{9}] ⊕ ℤ[\frac{1}{3}] ⊕ ℤ^{1}  f = g, a = b, c = d
h,4  ℤ[\frac{1}{9}] ⊕ ℤ[\frac{1}{3}] ⊕ ℤ^{3}  e = g
h,3  ℤ[\frac{1}{9}] ⊕ ℤ[\frac{1}{3}] ⊕ ℤ^{2}  e = g, a = d or b = c
h,2  ℤ[\frac{1}{9}] ⊕ ℤ[\frac{1}{3}] ⊕ ℤ^{1}  e = g, a = d, b = c
4  ℤ[\frac{1}{9}] ⊕ ℤ^{4}  e = f = g
3  ℤ[\frac{1}{9}] ⊕ ℤ^{3}  e = f = g, a = b
2  ℤ[\frac{1}{9}] ⊕ ℤ^{2}  e = f = g, a = b = c
1  ℤ[\frac{1}{9}] ⊕ ℤ^{1}  e = f = g, a = b = c = d

Table 1: Topology of the squiral hull and its various substitution factors. In the left column, we indicate the set on which the projection to 𝕊_{3}^{2} is not 1-to-1; labels v or h mean that there are vertical or horizontal sub-solenoids of type 𝕊_{3}^{1} where the projection is 2-to-1, and an integer denotes the extra degeneracy (beyond the 1d and 2d solenoids) of the projection to the origin of 𝕊_{3}^{2}. In the second column, the cohomology group H^{2} is given. In all cases, H^{1} = ℤ[\frac{1}{3}]^{2} and H^{0} = ℤ. For the factors of F_{max}, examples for identifications of the symbols of F_{max} are given in the last column. Especially for the smaller factors, there are usually many choices of identifications that yield equivalent factors.

Figure 2: Geometric inflation rule for the table tiling.

What can be said about possible model set factors? In the case of the Thue-Morse and squiral tilings, we have seen that there exist maximal model set factors, onto which the projection has uniform multiplicity. For the table tiling, such a factor with uniform multiplicity cannot exist, which can be seen as follows.

For such a factor to exist, the multiplicity of the projection to 𝕊_{2}^{2} must be divisible by four everywhere. However, there are 10 different pairs of tiles sharing a vertical edge, and 10 pairs sharing a horizontal edge, so that for tilings which consist of a pair of infinite order supertiles, sharing a vertical or a horizontal line, the projection to 𝕊_{2}^{2} is 10-to-1. As a consequence, any

Figure 3: A patch of the table tiling in the form of a level-6 supertile.

projection to a model set factor must identify all 10 tilings in such a group of 10, and thus cannot have constant multiplicity.

This does not exclude the existence of model set factors between the table and the solenoid 𝕊_{2}^{2}, however. Such a factor can still have a projection to the solenoid with a nontrivial multiplicity at the corners of infinite order supertiles.

The table tiling admits 24 legal 2×2-patterns, all of which are seeds for one of the 24 fixed points under the square of the substitution. These patterns are the following,

\begin{matrix}[\begin{matrix}0 & 2 \\ 0 & 2 \end{matrix}] & [\begin{matrix}0 & 2 \\ 1 & 0 \end{matrix}] & [\begin{matrix}0 & 2 \\ 2 & 1 \end{matrix}] & [\begin{matrix}1 & 0 \\ 3 & 1 \end{matrix}] & [\begin{matrix}1 & 1 \\ 3 & 3 \end{matrix}] & [\begin{matrix}1 & 3 \\ 3 & 0 \end{matrix}] & [\begin{matrix}2 & 0 \\ 1 & 1 \end{matrix}] & [\begin{matrix}2 & 1 \\ 1 & 3 \end{matrix}] \\ [\begin{matrix}2 & 3 \\ 0 & 2 \end{matrix}] & [\begin{matrix}2 & 3 \\ 1 & 0 \end{matrix}] & [\begin{matrix}2 & 3 \\ 2 & 1 \end{matrix}] & [\begin{matrix}3 & 0 \\ 0 & 2 \end{matrix}] & [\begin{matrix}3 & 0 \\ 1 & 0 \end{matrix}] & [\begin{matrix}3 & 0 \\ 2 & 1 \end{matrix}] & [\begin{matrix}3 & 1 \\ 2 & 3 \end{matrix}] & [\begin{matrix}3 & 3 \\ 2 & 0 \end{matrix}] \\ [\begin{matrix}0 & 2 \\ 2 & 0 \end{matrix}] & [\begin{matrix}1 & 3 \\ 3 & 1 \end{matrix}] & [\begin{matrix}2 & 0 \\ 0 & 2 \end{matrix}] & [\begin{matrix}3 & 1 \\ 1 & 3 \end{matrix}] & [\begin{matrix}0 & 2 \\ 1 & 1 \end{matrix}] & [\begin{matrix}1 & 0 \\ 3 & 0 \end{matrix}] & [\begin{matrix}2 & 1 \\ 2 & 3 \end{matrix}] & [\begin{matrix}3 & 3 \\ 0 & 2 \end{matrix}] \end{matrix}

We have found two sliding block maps which induce a primitive substitution on the resulting factor. In the first map, the 16 patches of the first two rows map to 0 and the remaining eight patches from the third row to 1. This factor map induces a block substitution

ℓ ↦ [\begin{matrix}0 & ℓ \\ 1 & 0 \end{matrix}]  (16)

on the alphabet {0, 1}, with ℓ ∈ {0, 1}. The new substitution rule is primitive and admits two fixed points (with legal seed [ \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ] or [ \begin{matrix}0 & 1 \\ 0 & 0 \end{matrix} ] and reference point in its center, so that the fixed point covers ℤ^{2}). The substitution obviously has a Toeplitz structure, so that each legal tiling it generates forms a model set, with pure point spectrum; compare [35, 29]. The two fixed points project to the same point in 𝕊_{2}^{2}, so that there are two translation orbits of tilings which project to a single translation orbit in 𝕊_{2}^{2}.

Another (larger) factor is obtained if the first 16 patches are mapped to 0, the first 4 patches in the third row to 1, and the remaining 4 patches to 2. The induced substitution on the alphabet {0, 1, 2} is

0 ↦ [\begin{matrix}2 & 1 \\ 1 & 2 \end{matrix}] ,  1 ↦ [\begin{matrix}2 & 0 \\ 1 & 2 \end{matrix}] ,  2 ↦ [\begin{matrix}2 & 2 \\ 1 & 2 \end{matrix}] .  (17)

Again, the substitution is primitive and has a Toeplitz structure, implying that also this factor is a model set, with pure point spectrum [35, 29]. There are three fixed points under the square of the substitution, with seeds [ \begin{matrix}1 & 2 \\ ℓ & 1 \end{matrix} ] (ℓ = 1, 2, 3), which project to the same point on 𝕊_{2}^{2}, so that there are three translation orbits of tilings which project to a single translation orbit on the solenoid. Everywhere else, the projection is 1-to-1.

The interpretation of the zeta function turns out to be more difficult if the projection to the solenoid fails to be 1-to-1 almost everywhere. For the table tiling, we obtain as Čech cohomology

H^{2} = ℤ[\frac{1}{4}] ⊕ ℤ[\frac{1}{2}]^{4} ⊕ ℤ^{3} ⊕ ℤ_{2}, H^{1} = ℤ[\frac{1}{2}]^{2}, H^{0} = ℤ,  (18)

while the dynamical zeta fuction reads

ζ_{table}(z) = \frac{(1 − 2z)^{2}}{(1 − 4z)(1 − 4z^{2})^{2}(1 − z)^{2}(1 − z^{2})} .  (19)

The corresponding fixed point counts are a_{m} = 4^{n} + 3 + (−1)^{n}(1 + 2^{n+1}). It is natural to compare this to the zeta function of 𝕊_{2}^{2},

ζ_{𝕊_{2}^{2}}(z) = \frac{(1 − 2z)^{2}}{(1 − 4z)(1 − z)} ,  (20)

which follows once again from [16] and codes the fixed point counts a_{m}^{(2)} = (2^{n} −1)^{2}; compare sequences A000225 and A060867 of [39]. At this stage, however, it is far from obvious how the fixed point counts of the table shall be mapped to those of the solenoid, under a map which is 4-to-1 almost everywhere.

6 Acknowledgement

It is a pleasure to thank Jean-Paul Allouche for many fruitful discussions and for his support over the years. Moreover, we are grateful to Natalie Frank, Aernout van Enter and Daniel Lenz for helpful discussions on the example from Section 2, which took place during a meeting at BIRS in November 2011. This work was supported by the German Research Council (DFG), within the CRC 701.

References

[1] J.-P. Allouche, Schrödinger operators with Rudin-Shapiro potentials are not palindromic, J. Math. Phys. 38 (1997) 1843–1848.

[2] J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity, Theor. Comput. Science 292 (2003) 9–31. Available at

http://arxiv.org/abs/math/0106121.

[3] J.-P. Allouche and R. Bacher, Toeplitz sequences, paperfolding, Hanoi towers and progression-free sequences of integers, Ens. Math. 38 (1992) 315–327.

[4] J.-P. Allouche and M. Mendès France, Automatic sequences, in F. Axel and D. Gratias, eds., Beyond Quasicrystals, Springer, 2000, pp. 293–367.

[5] J.-P. Allouche and J. Shallit, Complexité des suites de Rudin-Shapiro généralisées, J. Théorie Nombres de Bordeaux 5 (1993) 283–302.

[6] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.

[7] J. E. Anderson and I. F. Putnam, Topological invariants for substitution tilings and their associated C^{∗}-algebras, Ergodic Th. & Dynam. Syst. 18 (1998) 509–537.

[8] M. Baake, A note on palindromicity, Lett. Math. Phys. 49 (1999) 217–227. Available at

http://arxiv.org/abs/math-ph/9907011.

[9] M. Baake, A guide to mathematical quasicrystals, in J.-B. Suck, M. Schreiber and P. Häussler, eds., Quasicrystals – An Introduction to Structure, Physical Properties and Applications, Springer, 2002, pp. 17–48. Available at

http://arxiv.org/abs/math-ph/9901014.

[10] M. Baake, F. Gähler, and U. Grimm, Spectral and topological properties of a family of generalised Thue-Morse sequences, J. Math. Phys. 53 (2012) 032701. Available at

http://arxiv.org/abs/1201.1423.

[11] M. Baake and U. Grimm, Kinematic diffraction from a mathematical viewpoint, Z. Kristallogr. 226 (2011) 711–725. Available at http://arxiv.org/abs/1105.0095.

[12] M. Baake, D. Lenz, and A. C. D. van Enter, Diffraction versus dynamical spectra for uniquely ergodic systems with finite local complexity, in preparation.

[13] M. Baake and A. C. D. van Enter, Close-packed dimers on the line: Diffraction versus dynamical spectrum, J. Stat. Phys. 143 (2011) 88–101. Available at

http://arxiv.org/abs/1011.1628.

[14] M. Baake and U. Grimm, Squirals and beyond: Substitution tilings with singular continuous spectrum, Ergodic Th. & Dynam. Syst., to appear. Available at

http://arxiv.org/abs/1205.1384.

[15] M. Baake and U. Grimm, Aperiodic Order: A Mathematical Invitation, Cambridge University Press, in preparation.

[16] M. Baake, E. Lau, and V. Paskunas, A note on the dynamical zeta function of general toral endomorphisms, Monatsh. Math. 161 (2010) 33–42. Available at

http://arxiv.org/abs/0810.1855.

[17] M. Baake and D. Lenz, Dynamical systems on translation bounded measures: Pure point dynamical and diffraction spectra, Ergodic Th. & Dynam. Syst. 24 (2004) 1867–1893.

Available at http://arxiv.org/abs/math/0302231.

[18] M. Baake, D. Lenz, and R. V. Moody, Characterization of model sets by dynamical systems, Ergodic Th. & Dynam. Syst. 27 (2007) 341–382. Available at

http://arxiv.org/abs/math/0511648.

[19] M. Baake and R. V. Moody (eds.), Directions in Mathematical Quasicrystals, CRM Monograph Series, Vol. 13, AMS, 2000.

[20] M. Baake and R. V. Moody, Weighted Dirac combs with pure point diffraction, J. reine angew. Math. (Crelle) 573 (2004) 61–94. Available at

http://arxiv.org/abs/math/0203030.

[21] M. Baake, M. Schlottmann, and P. D. Jarvis, Quasiperiodic patterns with tenfold symmetry and equivalence with respect to local derivability, J. Phys. A: Math. Gen. 24 (1991) 4637–4654.

[22] J. M. Cowley, Diffraction Physics, 3rd ed., North-Holland, 1995.

[23] F. M. Dekking, The spectrum of dynamical systems arising from substitutions of constant length, Z. Wahrscheinlichkeitsth. verw. Geb. 41 (1978) 221–239.

[24] F. Durand, Linearly recurrent subshifts have a finite number of non-periodic subshift factors, Ergodic Th. & Dynam. Syst. 20 (2000) 1061–1078. Available at

http://arxiv.org/abs/0807.4430.

[25] A. C. D. van Enter and J. Miȩkisz, How should one define a weak crystal? J. Stat. Phys. 66 (1992) 1147–1153.

[26] N. P. Frank, Multi-dimensional constant-length substitution sequences, Topol. Appl. 152 (2005) 44–69.

[27] N. P. Frank, Spectral theory of bijective substitution sequences, MFO Reports 6 (2009) 752–756.

[28] D. Frettlöh, Nichtperiodische Pflasterungen mit ganzzahligem Inflationsfaktor, PhD thesis, Univ. Dortmund, 2002.

[29] D. Frettlöh and B. Sing, Computing modular coincidences for substitution tilings and point sets, Discr. Comput. Geom. 37 (2007) 381–407. Available at

    http://arxiv.org/abs/math/0601067.

[30] B. Grünbaum and G. C. Shephard, Tilings and Patterns, Freeman, 1987.

[31] A. Hof, On diffraction by aperiodic structures, Commun. Math. Phys. 169 (1995) 25–43.

[32] S. Kakutani, Strictly ergodic symbolic dynamical systems, in L. M. LeCam, J. Neyman, and E. L. Scott, eds., Proc. 6th Berkeley Symposium on Math. Statistics and Probability, Univ. of California Press, 1972, pp. 319–326.

[33] M. Keane, Generalized Morse sequences, Z. Wahrscheinlichkeitsth. verw. Geb. 10 (1968) 335–353.

[34] B. P. Kitchens, Symbolic Dynamics, Springer, 1998.

[35] J.-Y. Lee and R. V. Moody, Lattice substitution systems and model sets, Discr. Comput.

    Geom. 25 (2001) 173–201. Available at http://arxiv.org/abs/math/0002019.

[36] J.-Y. Lee, R. V. Moody, and B. Solomyak, Pure point dynamical and diffraction spectra, Ann. H. Poincaré 3 (2002) 1003–1018. Available at

    http://arxiv.org/abs/0910.4809.

[37] D. A. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, 1995.

[38] R. V. Moody, Model sets: A survey, in F. Axel, F. Dénoyer and J. P. Gazeau, eds., From Quasicrystals to More Complex Systems, EDP Sciences and Springer, 2000, pp.

    145–166. Available at http://arxiv.org/abs/math/0002020.

[39] The On-Line Encyclopedia of Integer Sequences, http://oeis.org/.

[40] N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, LNM 1794, Springer, 2002.

[41] M. Queffélec, Substitution Dynamical Systems – Spectral Analysis, LNM 1294, 2nd ed., Springer, 2010.

[42] E. A. Robinson, On the table and the chair, Indag. Math. 10 (1999) 581–599.

[43] E. A. Robinson, Symbolic dynamics and tilings of ℝ^{d}, Proc. Sympos. Appl. Math. 60 (2004) 81–119.

[44] D. Ruelle, Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval, CRM Monograph Series, vol. 4, AMS, 1994.

[45] L. Sadun, Topology of Tiling Spaces, AMS, 2008.

[46] K. Schmidt, Dynamical Systems of Algebraic Origin, Birkhäuser, 1995.

[47] D. Shechtman, I. Blech, D. Gratias, and J. W. Cahn, Metallic phase with long-range orientational order and no translational symmetry, Phys. Rev. Lett. 53 (1984) 1951– 1953.

[48] M. Schlottmann, Generalised model sets and dynamical systems, in [19], pp. 143–159.

[49] R. L. Withers, Disorder, structured diffuse scattering and the transmission electron microscope, Z. Krist. 220 (2005) 1027–1034.

2010 Mathematics Subject Classification: Primary 37B10; Secondary 37B50, 52C23, 55N05. Keywords: symbolic dynamics, factor system, aperiodic order, topological invariant.

Received August 15 2012; revised version received December 10 2012. Published in Journal of Integer Sequences, March 2 2013.

Return to Journal of Integer Sequences home page.