# Tilings of the hyperbolic plane of substitutive origin as subshifts of finite type on Baumslag–Solitar groups BS (1, n)

Nathalie Aubrun, Michael Schraudner

► To cite this version:

Nathalie Aubrun, Michael Schraudner. Tilings of the hyperbolic plane of substitutive origin as subshifts of finite type on Baumslag–Solitar groups BS (1, n). Comptes Rendus. Mathématique, 2024, 362 (G5), pp.553-580. 10.5802/crmath.571. hal-04727536

HAL Id: hal-04727536

https://hal.science/hal-04727536v1

Submitted on 9 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Comptes Rendus
Mathématique

Nathalie Aubrun and Michael Schraudner

Tilings of the hyperbolic plane of substitutive origin as subshifts of finite type on
Baumslag–Solitar groups *BS(1, n)*

Volume 362 (2024), p. 553-580

https://doi.org/10.5802/crmath.571

<figure><img src="image_2.png" /></figure>

This article is licensed under the
CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.
http://creativecommons.org/licenses/by/4.0/
Research article / *Article de recherche*
Theoretical computer science, Dynamical systems / *Informatique théorique, Systèmes dynamiques*

# Tilings of the hyperbolic plane of substitutive origin as subshifts of finite type on Baumslag–Solitar groups $BS(1, n)$

*Pavages hyperboliques engendrés par une substitution comme sous-décalages de type fini sur les groupes de Baumslag–Solitar* $BS(1, n)$

Nathalie Aubrun<sup>®</sup>,<sup>a</sup> and Michael Schraudner<sup>b</sup>

<sup>a</sup> Université Paris-Saclay, CNRS, Laboratoire Interdisciplinaire des Sciences du Numérique, 91400, Orsay, France

<sup>b</sup> Centro de Modelamiento Matemático, Universidad de Chile, Av. Blanco Encalada 2120, Piso 7, Santiago de Chile

*E-mails*: aubrun@lisn.fr (N. Aubrun), mschraudner@dim.uchile.cl (M. Schraudner)

**Abstract.** We present a technique to lift some tilings of the discrete hyperbolic plane –tilings defined by a 1D substitution– into a zero entropy subshift of finite type (SFT) on non-abelian amenable groups $BS(1, n)$ for $n \ge 2$. For well chosen hyperbolic tilings, this SFT is also aperiodic and minimal. As an application we construct a strongly aperiodic SFT on $BS(1, n)$ with a hierarchical structure, which is an analogue of Robinson’s construction on $Z^2$ or Goodman–Strauss’s on $H^2$.

**Résumé.** Nous présentons une technique pour relever certains pavages du plan hyperbolique discret, ceux définis par une substitution 1D, au sein d'un sous-décalage de type fini (SFT) d'entropie nulle sur les groupes de Baumslag–Solitar moyennables et non abéliens $BS(1, n)$ avec $n \ge 2$. Lorsque ces pavages hyperboliques sont bien choisis, on montre que ce SFT est également apériodique et minimal. En guise d'application nous construisons un SFT fortement apériodique sur $BS(1, n)$ avec une structure hiérarchique, qui est l'an analogue de la construction de Robinson sur $Z^2$ ou de celle de Goodman–Strauss sur $H^2$.

**2020 Mathematics Subject Classification.** 37B10, 20F99.

**Funding.** This work was partially supported by the ECOS-SUD project C17E08 and the ANR project CoCoGro (ANR-16-CE40-0005).

*Manuscript received 11 May 2023, revised 12 September 2023 and 18 September 2023, accepted 14 September 2023.*
## Introduction

Given a finitely generated group $G$ and a finite alphabet $\mathcal{A}$, the set $\mathcal{A}^G$ can be endowed with the prodiscrete topology. The group $G$ acts—from the left—by translation on $\mathcal{A}^G$, and a classical result states that with this topology, the set $\mathcal{A}^G$ is a compact set. Elements of $\mathcal{A}^G$ are called configurations, and can be thought of as colorings of the group $G$ with colors chosen among the finite set $\mathcal{A}$. Symbolic dynamics on $G$ studies subshifts, i.e. sets of configurations of $G$ that are both invariant under the action of $G$, and closed for the product topology. Equivalently, subshifts can be defined as sets of configurations that avoid some set of finite patterns—this set of forbidden patterns not necessarily being finite. If the set of forbidden patterns can be chosen finite, the subshift is called a subshift of finite type (SFT for short). SFTs are of particular interest for two reasons. First, because they can be used to model real-life phenomena defined through local interactions. Second, because their finite description allows to ask complexity and computability questions.

Among questions related to SFTs, an open problem is to characterize groups $G$ which admit a strongly aperiodic SFT, i.e. an SFT such that all its configurations have a trivial stabilizer. The same question for general subshifts—non SFT—has been answered positively [2, 13]. Free groups cannot possess strongly aperiodic SFTs [19], and a finitely generated and recursively presented group with an aperiodic SFT necessarily has a decidable word problem [16]. Groups that are known to admit a strongly aperiodic SFT are $\mathbb{Z}^2$ [21] and $\mathbb{Z}^d$ for $d > 2$ [10], fundamental groups of oriented surfaces [8], hyperbolic groups [9], discrete Heisenberg group [22] and more generally groups that can be written as a semi-direct product $G = \mathbb{Z}^2 \times_{\phi} H$, provided $G$ has decidable word problem [7], and amenable Baumslag–Solitar groups [11]. In [3] the authors adapt the construction of [4, 5] to get a strongly aperiodic SFT on non-amenable Baumslag–Solitar groups $BS(m, n)$. None of these two constructions are, to the best of our knowledge, minimal SFTs.

There are several techniques to produce aperiodicity inside tilings, but in the particular setting of SFTs, two of them stand out. The first goes back to Robinson [21]: the aperiodicity of Robinson's SFT follows from the hierarchical structure shared by all configurations. Indeed, in every configuration one sees different levels of squares, where all squares of a given level are arranged according to a lattice, and are gathered by four to produce a square of higher level. Since there are arbitrarily large squares, no non-trivial translation can keep the configuration unchanged. The second technique goes back to Kari [17]: a very simple aperiodic dynamical system is encoded into an SFT, so that configurations correspond to orbits of the dynamical system. Aperiodicity of the SFT comes from both the aperiodicity of the dynamical system and the clever encoding.

In this article we focus on the particular case where $G$ is a Baumslag–Solitar group. Baumslag–Solitar groups are examples of HNN extensions, a fundamental construction in combinatorial group theory that plays for instance a key role in the proof of Higman embedding theorem [18]. There are described by the two generators and one relation presentation

$$BS(m, n) := \langle a, t \mid t^{-1}a^m t = a^n \rangle,$$

where $m, n$ are two positive integers. The whole class of $BS(m, n)$ is clearly separated into two subclasses with radically different behaviors: the groups $BS(1, n)$ are solvable hence amenable, while the $BS(m, n)$ groups with $m, n > 1$ contain free subgroups and are consequently non amenable. Each of these two subclasses is also well-understood from a geometrical point of view, since it is known under which condition two $BS(m, n)$ are quasi-isometric:

* groups $BS(1, n)$ and $BS(1, n')$ are quasi-isometric if and only if $n$ and $n'$ have a common power [12] — and in this case, the two groups are even commensurable;
• groups $BS(m, n)$ and $BS(m', n')$ are quasi-isometric as soon as $2 \le m < n$ and $2 \le m' < n'$ [23].

In [14] the author adapts [17] to an expansive setting, the trinary tiling, akin to $BS(1, 3)$. Later in [4, 5] the example of aperiodic SFT that is given is a construction adapted from [17]. This SFT is proved to be weakly aperiodic — all configurations have infinite orbit — in [4] for all Baumslag–Solitar groups, and not strongly aperiodic for the non amenable ones. In [11] the authors show that this SFT is actually strongly aperiodic for amenable Baumslag–Solitar groups.

In this article, we will only consider non abelian amenable Baumslag–Solitar groups $BS(1, n)$ with $n \ge 2$. Our main result consists in a construction that allows to lift some particular tilings of the discrete hyperbolic plane — tilings defined from a 1D substitution — into an SFT on $BS(1, n)$ (Theorem 15). If the substitution is well chosen, then the SFT is moreover minimal, strongly aperiodic and has zero entropy (Propositions 24, 26 and 27). As an application, we construct a strongly aperiodic SFT on $BS(1, n)$ with a hierarchical structure, that goes back to Robinson's construction on $\mathbb{Z}^2$ [21] and Goodman-Strauss's construction on the discrete hyperbolic plane [15]. We strongly believe that this hierarchical SFT will also serve as a basis for more sophisticated constructions.

# 1. Subshifts on amenable Baumslag–Solitar groups

In this section we start with basics of symbolic dynamics on finitely generated groups. The reader shall refer to [1] for a more complete introduction. The set of non-negative integers $\{0, 1, 2, \dots\}$ is denoted $\mathbb{N}$, and $\mathbb{N}^*$ stands for $\{1, 2, \dots\}$.

## 1.1. Subshifts on finitely generated groups

In this article $\mathcal{A}$ denotes a finite set, and $G$ is a finitely generated group. The identity of $G$ is denoted $1_G$. Endowed with the prodiscrete topology, the set $\mathcal{A}^G$ is a compact and metrizable space. Elements of $\mathcal{A}^G$ are called configurations, and can be though of as colorings of the group $G$ by the finite alphabet $\mathcal{A}$. The shift map is the natural left action of $G$ on $\mathcal{A}^G$ by translation

$$ \mathcal{G}: \left( \begin{array}{c} G \times \mathcal{A}^G \rightarrow \mathcal{A}^G \\ (g, x) \rightarrow \mathcal{G}_g(x) \end{array} \right) $$

where $\mathcal{G}_g(x)$ is the configuration such that $(\mathcal{G}_g(x))_h = x_{g^{-1}h}$ for every $h \in G$. The dynamical system $(\mathcal{A}^G, \mathcal{G})$ is called a full-shift. Subshifts are subsystems of the full-shift, i.e. subsets of $\mathcal{A}^G$ that are both closed for the prodiscrete topology and invariant under the shift action. Interestingly this dynamical definition of subshifts coincides with a combinatorial one. A pattern is a finite configuration $p \in \mathcal{A}^S$, where $S$ is a finite subset of $G$ called the support of $p$. A pattern $p \in \mathcal{A}^S$ appears in a configuration $x \in \mathcal{A}^G$ if there exists a group element $g \in G$ such that $p_h = (\mathcal{G}_g(x))_h$ for every $h \in S$. Otherwise we say that $x$ avoids $p$. Given a set of patterns $\mathcal{F}$, define $X_{\mathcal{F}}$ as the set of configurations that avoid all patterns in $\mathcal{F}$. A set of configurations $Y$ is a subshift if and only if there exists some $\mathcal{F}$ such that $Y = X_{\mathcal{F}}$. A subshift of finite type — SFT for short — is a subshift for which the set of forbidden patterns $\mathcal{F}$ can be chosen finite. A sofic subshift is a subshift which is the image of an SFT under a continuous and shift commuting map — such maps are called morphisms.

Let $x \in \mathcal{A}^G$ be a configuration. The orbit of $x$ is the set of configurations $orb_{\mathcal{G}}(x) = \{\mathcal{G}_g(x) \mid g \in G\}$, and the stabilizer of $x$ is the subgroup $stab_{\mathcal{G}}(x) = \{g \in G \mid \mathcal{G}_g(x) = x\}$. A subshift $X \subseteq \mathcal{A}^G$ is weakly aperiodic if for every configuration $x \in X$, $|orb_{\mathcal{G}}(x)| = \infty$. A subshift $X \subseteq \mathcal{A}^G$ is strongly aperiodic if for every configuration $x \in X$, $stab_{\mathcal{G}}(x) = \{1_G\}$. The subshift $X$ is minimal if it does not contain a proper subshift or, equivalently, if the orbit of each configuration $x \in X$ is dense.
## 1.2. Baumslag–Solitar groups

Given two positive integers $m$ and $n$, define the finitely presented group

$$BS(m, n) := \langle a, t \mid t^{-1} a^m t = a^n \rangle,$$

known as the Baumslag–Solitar group with parameters $m, n$. In this article we are only interested in the case $m = 1$, which makes these groups solvable hence amenable. For the class of amenable Baumslag–Solitar groups, there exists a short normal form, as stated below in Proposition 1.

**Proposition 1.** Every element of $BS(1, n)$ can be uniquely written as one of the following words

* $a^j t^{-k}$ with $k \ge 0$ and $j \in \mathbb{Z}$,

* or $t^i a^j$ with $i > 0$ and $j \in \mathbb{Z}$,

* or $t^i a^j t^{-k}$ with $i > 0, k > 0$ and $n \nmid j$.

**Proof.** Using the relation $at = ta^n$, one deduces that $t^{-1}a = a^n t^{-1}$. Combining these two rewriting rules, any word on $\{a, a^{-1}, t, t^{-1}\}$ can be rewritten as some $t^i a^j t^{-k}$ with $i, k \ge 0$ and $j \in \mathbb{Z}$. If $i = 0$ or $k = 0$ then we are done. Otherwise if $i, k > 0$ and $j = nj'$, write $t^i a^j t^{-k} = t^{i-1} a^j t^{-k+1}$ and iterate the process as soon as $i, k > 0$ and $n \nmid j$.

It remains to prove uniqueness. Note that for a given $g$, all words $w$ in $a, a^{-1}, t, t^{-1}$ that represent $g$ should share the same quantity $|w|_t - |w|_{t^{-1}}$. So if $g$ can be written as $w = t^i a^j t^{-k}$ and $w' = t^i a^j t^{-k'}$ with $i, i', k, k' \ge 0$, and $j, j' \in \mathbb{Z}$, then either $i = i' = 0$ and $k = k'$, or $k = k' = 0$ and $i = i'$, or $i, k, i', k' > 0$ and $n \nmid j, n \nmid j'$ and $i - k = i' - k'$. In the two first cases, we have directly $i = i'$, $j = j'$ and $k = k'$. In the third case, assume that $i' = i + \ell$ and $k' = k + \ell$ with $\ell \ge 0$. Then necessarily $t^\ell a^i t^{-\ell} = a^j$ with $n \nmid j$ and $n \nmid j'$. This is not possible unless $\ell = 0$, so we finally get $i = i'$, $j = j'$ and $k = k'$, and the normal form is unique. $\square$

Remark that this normal form does not have minimal length: for instance the element $t^2 a^{n^2-1}$ could have been written using fewer generators as $at^2 a^{-1}$.

Consider the semi-direct product $\mathbb{Z}[\frac{1}{n}] \rtimes_f \mathbb{Z}$ given by

$$f: \left( \begin{array}{c} \mathbb{Z} \rightarrow \mathrm{Aut}(\mathbb{Z}[\frac{1}{n}]) \\ k \mapsto x \mapsto n^k \cdot x \end{array} \right).$$

Using the normal form of Proposition 1, we prove that $BS(1, n)$ and $\mathbb{Z}[\frac{1}{n}] \rtimes_f \mathbb{Z}$ are isomorphic, through

$$\Phi: \left( \begin{array}{c} BS(1, n) \rightarrow \mathbb{Z}[\frac{1}{n}] \rtimes_f \mathbb{Z} \\ t^i a^j t^{-k} \mapsto (j \cdot n^{-i}, k-i) \end{array} \right).$$

**Remark 2.** Given two arbitrary words representing the same group element, why must $\Phi$ agree? Suppose an element $g \in BS(1, n)$ can be written as $w = t^i a^{n^\alpha} j t^{-k}$ for some $\alpha \ge 1$ and $n \nmid j$. Using that $a^{n^\alpha} j = t^{-\alpha} a^j t^{\alpha}$, we deduce the word $w' = t^{i-\alpha} a^j t^{-k+\alpha}$ also represents the element $g$. And since

$$\begin{align*} \Phi(t^i a^{n^\alpha} j t^{-k}) &= (n^\alpha j \cdot n^{-i}, k-i) \\ &= (j \cdot n^{-(i-\alpha)}, (k-\alpha) - (i-\alpha)) \\ &= \Phi(t^{i-\alpha} a^j t^{-(k-\alpha)}) \\ &= \Phi(g), \end{align*}$$

we conclude that $\Phi$ is well-defined.

**Proposition 3.** The map $\Phi$ is an isomorphism.
**Proof.** We first check that $\Phi$ is a group morphism. Take $g, h$ two group elements in $G$, and assume they can be written as $g = t^i a^j t^{-k}$ and $h = t^{i'} a^{j'} t^{-k'}$. Recall that the law for the semi-direct product is $(h_1, k_1) \cdot (h_2, k_2) = (h_1 + f(k_1)(h_2), k_1 + k_2)$ for $(h_i, k_i) \in \mathbb{Z}[\frac{1}{n}] \rtimes_f \mathbb{Z}$. Then on the one hand

$$ \begin{aligned} \Phi(gh) &= \Phi(t^i a^j t^{-k} \cdot t^{i'} a^{j'} t^{-k'}) \\ &= \Phi(t^i a^j t^{i'} \cdot t^{-k} a^{j'} t^{-k'}) \\ &= \Phi(t^{i+i'} a^{jn'i'} \cdot a^{jn^k} t^{-k-k'}) \\ &= ((jn^{i'} + j'n^k) n^{-(i+i')}, k + k' - i - i') \end{aligned} $$

where the last equality comes from Remark 2, and on the other hand

$$ \begin{aligned} \Phi(g)\Phi(h) &= (j \cdot n^{-i}, k-i) \cdot (j' \cdot n^{-i'}, k'-i') \\ &= (j \cdot n^{-i} + n^{k-i} \cdot j' n^{-i'}, k + k' - i - i') \\ &= \Phi(gh), \end{aligned} $$

which proves that $\Phi$ is a group morphism.

Assume $g = t^i a^{nj+r} t^{-k}$ and $h = t^{i'} a^{nj'+r'} t^{-k'}$ and suppose $\Phi(g) = \Phi(h)$ with $0 \le r, r' < n$ — $r \ne 0$ if $i, j > 0$ and $r' \ne 0$ if $i', j' > 0$. Then

$$ ((nj+r) \cdot n^{-i}, k-i) = ((nj'+r') \cdot n^{-i'}, k'-i'), $$

which directly leads to $i = i'$, $j = j'$ and $k = k'$, hence $g = h$. $\square$

### 1.3. Structure of $BS(1, n)$

The Cayley graph of $BS(1, n)$ with generating set $\{a, t, a^{-1}, t^{-1}\}$ is made of several sheets that amalgamate $n$ by $n$, so that the global structure these sheets are arranged looks like an $(n+1)$-regular tree. Each of these sheets is quasi-isometric to the hyperbolic plane $\mathbb{H}^2$. From now on, we only consider the case $n = 2$, but the attentive reader will be convinced that the rest of the article easily transposes to the general case $n > 2$.

We call rectangle any finite subset of $BS(1, 2)$ of the form

$$ R_{k,\ell} := \{t^\ell a^i t^{-j} \mid i \in [0;(k+1) \cdot 2^{\ell-1}-1] \text{ and } j \in [0;\ell]\}. $$

These rectangles are a classical example of a Følner sequence for $BS(1, 2)$. As so, they will be used in the next section to define the topological entropy for subshifts on $BS(1, 2)$.

**Proposition 4.** The sequence $(R_{k,\ell})_{k,\ell \in \mathbb{N}}$ is a Følner sequence.

### 1.4. Entropy

The language of size $(k, \ell)$ of a subshift $X \subseteq \mathcal{A}^{BS(1,2)}$ is the set of patterns with support $R_{k,\ell}$ that appear in some configuration of $X$

$$ \mathcal{L}_{k,\ell}(X) := \{p \in \mathcal{A}^{R_{k,\ell}} \mid \exists x \in X, \exists g \in BS(1,2) \text{ s.t. } \forall h \in R_{k,\ell}, x_{gh} = p_h\}. $$

The language of a subshift $X \subseteq \mathcal{A}^{BS(1,2)}$ is given by

$$ \mathcal{L}(X) := \bigcup_{k, \ell \in \mathbb{N}} \mathcal{L}_{k, \ell}(X), $$

and is the set of globally admissible patterns; i.e. finite patterns that can be extended into a valid configuration.
<figure><img src="image_3.png" /><figcaption>**Figure 1.** The rectangle $R_{2,4}$ in $\mathcal{BS}(1,2)$. The leftmost sheet is pictured in blue, the rightmost in red. The $2^4 - 2 = 14$ sheets in between are not pictured.</figcaption></figure>

The entropy of a subshift $X \subseteq \mathcal{A}^{\mathcal{BS}(1,2)}$ is given by

$$h(X) := \lim_{k,l \to \infty} \frac{\log (\# \mathcal{L}_{k,l}(X))}{|R_{k,l}|}.$$

Since $\mathcal{BS}(1,2)$ is amenable, this limit exists and does not depend on the choice of the Følner sequence [20]. Moreover, we have that

$$h(X) = \limsup_{k,l \to \infty} \frac{\log (\# \mathcal{L}_{k,l}(X))}{|R_{k,l}|}.$$

## 2. Substitutions and their tilings

A non-deterministic substitution is $\sigma = (\mathcal{A}, R)$, with $\mathcal{A} = \{a_1, \dots, a_n\}$ a finite alphabet of size $n$ and $R \subset \mathcal{A} \times \mathcal{A}^*$ the set of rules of $\sigma$. A substitution $\sigma$ is deterministic if for every letter $a \in \mathcal{A}$, there exists only one rule $(a, \sigma(a)) \in R$. In the deterministic setting, we associate to a substitution $\sigma$ its incidence matrix $M_\sigma \in \mathcal{M}_n(\mathbb{N})$ given by $M_\sigma(i, j) = |\sigma(a_i)|_{a_j}$ the number of occurrences of $a_j$ inside the word $\sigma(a_i)$. A substitution $\sigma$ is primitive if there exists a power of $M_\sigma$ for which all the entries are positive. Perron-Frobenius theorem implies that the incidence matrix of a primitive substitution admits an expanding eigenvalue, i.e. an eigenvalue $\lambda$ which is real, greater than one and greater than the modulus of all the other eigenvalues. Similarly, and following [1], we say that a non-deterministic substitution $\sigma = (\mathcal{A}, R)$ has an expanding eigenvalue if there exists a real $\lambda > 1$ and a vector $v: \mathcal{A} \to \mathbb{R}^{**}$ such that, for every $(a, w) \in R$:

$$\lambda \cdot v(a) = \sum_{i=1}^{|w|} v(w_i).$$
<figure><img src="image_4.png" /><figcaption>**Figure 2.** An $a_i$-tile for some letter $a_i \in \mathcal{A}$ with $\sigma(a_i) = w_1 \dots w_k$.</figcaption></figure>

In the sequel we treat only the case of deterministic substitutions in order to simplify notations, but all results presented still hold for non-deterministic substitutions.

**Example 5.** The deterministic substitution given by $\sigma(a) = aab$ and $\sigma(b) = ba$ has an expanding eigenvalue $\lambda = \frac{3+\sqrt{5}}{2}$ and associated eigenvector $v = (\frac{1+\sqrt{5}}{2}, 1)$.

Let $\sigma: \mathcal{A} \to \mathcal{A}$ be a primitive substitution with an expanding eigenvalue $\lambda > 1$. The substitutive subshift $Z_\sigma \subset \mathcal{A}^\mathbb{Z}$ is a two-sided one-dimensional subshift defined by

$$Z_\sigma := \{z \in \mathcal{A}^\mathbb{Z} \mid \forall w \subset z, \exists a \in \mathcal{A} \text{ and } n \in \mathbb{N} \text{ s.t. } w \subset \sigma^n(w)\}.$$

We now describe orbits of substitutions as tilings of $\mathbb{R}^2$, as done in [1], following [8], ultimately from a remark by L. Sadun. A tile is a compact subset of $\mathbb{R}^2$ with non-empty interior. If $T$ is a set of tiles, not necessarily finite, a $T$-tiling or tiling by $T$ is a collection of translated copies of tiles which have pairwise disjoint interiors and whose union is the entire $\mathbb{R}^2$.

Let $\sigma$ be a primitive substitution with an expanding eigenvalue $\lambda > 1$ and let $v \in (\mathbb{R}^+)^{|\mathcal{A}|}$ be an associated eigenvector. For every letter $a \in \mathcal{A}$, define the a-tile in position $(x, y) \in \mathbb{R}^2$ as the square polygon with $|w| + 3$ edges pictured in Figure 2, where $\sigma(a) = w_1 \dots w_k$ (horizontal edges are curved to be more visible, but are in fact just straight lines).

**Remark 6.** The length of the top edge and the sum of lengths of bottom edges of this tile are the same. Since $M_\sigma \cdot v = \lambda \cdot v$, one has

$$\sum_{j=1}^{k} \frac{1}{\lambda} v(w_i) \cdot 2^j = \frac{2^y}{\lambda} \cdot \lambda \cdot v(a) = v(a) \cdot 2^y,$$

so that the bottom right vertex $(x + \frac{1}{\lambda}(v(w_1) + \dots + v(w_k))2^y, y - \log_2(\lambda))$ is indeed $(x + v(a) \cdot 2^y, y - \log_2(\lambda))$.

**Proposition 7 ([1, Proposition 5]).** If a primitive substitution $\sigma$ has an expanding eigenvalue, then there exists a $\sigma$-tiling.

If $\tau$ is a $\sigma$-tiling of $\mathbb{R}^2$, it can be seen as a mapping $\tau: \mathbb{R}^2 \to \mathcal{A}$ with additional properties. Since $\mathcal{A}^{\mathbb{R}^2}$ is a compact space, from any sequence of $\sigma$-tilings one can extract a sequence that converges to some mapping $f: \mathbb{R}^2 \to \mathcal{A}$.
<figure><img src="image_5.png" /><figcaption>**Figure 3.** The $\sigma$-tiles for $\sigma(a) = aab, \sigma(b) = ba$. For this substitution, $\lambda = \frac{3+\sqrt{5}}{2}$ and $v = (\frac{1+\sqrt{5}}{2}, 1)$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Figure 4.** A finite piece of a $\sigma$-tiling for $\sigma(a) = aab, \sigma(b) = ba$.</figcaption></figure>

**Proposition 8.** If $(\tau_n)_{n \in \mathbb{N}}$ is a sequence of $\sigma$-tilings of $\mathbb{R}^2$ converging to some $f : \mathbb{R}^2 \to \mathcal{A}$, then $\tau$ is a $\sigma$-tiling of $\mathbb{R}^2$.

**Proof.** Let $(\tau_n)_{n \in \mathbb{N}}$ be a sequence of $\sigma$-tilings of $\mathbb{R}^2$ converging to some $f : \mathbb{R}^2 \to \mathcal{A}$. By definition, for every $k \in \mathbb{N}$, there exists a $N_k \in \mathbb{N}$ which satisfies that

$$ \text{for every } n \ge N_k, (\tau_n)_{|[k;k]|^2} = f_{|[k;k]|^2}. $$

Define a collection $\tau$ of $\sigma$-tiles as follows: an $a_i$-tile in position $(x, y)$ is in $\tau$ iff $\tau_{N_k}$ contains an $a_i$-tile in position $(x, y)$, where

$$ k := \lceil \max(|x|, |y|, |y - \log_2(\lambda)|, |x + v_i \cdot 2^y|) \rceil. $$

One can easily check that this collection $\tau$ is a tiling of $\mathbb{R}^2$, and that $\tau$ seen as a mapping : $\mathbb{R}^2 \to \mathcal{A}$ coincide with $f$. $\square$

### 3. $\sigma$-tilings as subshifts on $BS(1, 2)$

For all this section we fix $\mathcal{A}$ a finite alphabet with at least two letters $|\mathcal{A}| \ge 2$ and $\sigma : \mathcal{A} \to \mathcal{A}^*$ a primitive substitution with an expanding eigenvalue $\lambda > 1$. We denote $M_\sigma$ the matrix associated
with $\sigma$ and $v \in (\mathbb{R}^+)^{|\mathcal{A}|}$ an eigenvector associated with $\lambda$, so that $M_\sigma \cdot v = \lambda \cdot v$. In the sequel we will need a technical additional assumption, that we now describe.

First note that for every $k \in \mathbb{N}^*$, the substitution $\sigma^k$ has expanding eigenvalue $\lambda^k > 1$ and the same eigenvector $v$. Thus choosing $k$ big enough and since $\lambda > 1$, we can have $\log_2(\lambda^k) \ge 3$. We redefine $\sigma^k$ as $\sigma$. Second, since $Cv$ also satisfy $M(Cv) = \lambda(Cv)$ for every $C > 0$, we may assume without loss of generality that $v(a) \ge 3$ for every letter $a \in \mathcal{A}$. If this holds and that moreover $\lambda \ge 8$, we say that $\sigma$ and $v$ have the unique size property.

We then introduce the notion of $\Phi(g)$-box for a group element $g \in BS(1,2)$, and list some useful properties on these boxes. If $g \in BS(1,2)$ and $g$ has normal form $g = t^i a^j t^{-k}$, the $\Phi(g)$-box is the rectangle $\Phi(g) + [0, 2^{-i}[\times] - 1,0]$ in $\mathbb{R}^2$. A $\Phi$-box is simply a $\Phi(g)$-box for some group element $g \in BS(1,2)$.

**Remark 9.** The set of the $\Phi(g)$-boxes for all elements $g$ from the same sheet of $BS(1,n)$ is a partition of $\mathbb{R}^2$.

<figure><img src="image_7.png" /></figure>

This remark is an important ingredient of the construction of Section 4. Indeed, starting from a configuration $x$, it will be enough to know the content of all $\Phi$-boxes from the same sheet to define a tiling of the plane $\mathbb{R}^2$.

**Remark 10.** For a given $\sigma$-tiling, every $\Phi(g)$-box contains exactly one among

* a vertical line of the $\sigma$-tiling;

* an horizontal line of the $\sigma$-tiling;

* a cross (intersection of a vertical and an horizontal lines) of the $\sigma$-tiling;

* a $T$ (a vertical line that start immediately below an horizontal line) of the $\sigma$-tiling;

* nothing.

**Proposition 11.** If $\sigma$ and $v$ have the unique size property, then

(1) $a$ $\sigma$-tile vertically intersects $h$ or $h+1$ $\Phi$-boxes, where $h := \lceil \log_2(\lambda) \rceil \ge 3$;

(2) for every $a \in \mathcal{A}$, the top of an $a$-tile intersects $w$ $\Phi$-boxes horizontally, where $3 \le v(a) \le w < 2v(a)$;

(3) the number of $\Phi$-boxes horizontally intersected by the bottom of an $\sigma$-tile uniquely determines the number of $\Phi$-boxes it intersects vertically.

**Proof.** The first two items are direct consequences of the definitions of $\Phi$-boxes and $\sigma$-tiles. The third one is a little bit more subtle. Assume that an $a$-tile intersects $N$ $\Phi$-boxes on its bottom. Denote $\alpha := \lceil \frac{N}{2^h} \rceil$ and $\beta := \lceil \frac{N}{2^{h+1}} \rceil$ so that $\alpha$ and $\beta$ are the unique non-negative integers such that

$$\alpha - 1 < \frac{N}{2^h} \le \alpha$$

$$\beta - 1 < \frac{N}{2^{h+1}} \le \beta.$$
Note that multiplying by 2 the line immediately above leads to $\alpha = 2\beta$. So either the a-tile vertically intersects $h$ $\Phi$-boxes, and then it horizontally intersects $\alpha$ $\Phi$-boxes on its top, or the a-tile vertically intersects $h+1$ $\Phi$-boxes, and then it horizontally intersects $\beta$ $\Phi$-boxes on its top. So the second item in Proposition 11 thus implies that

$$v(a) \leq \alpha < 2v(a)$$

$$v(a) \leq \beta < 2v(a).$$

But since $\alpha = 2\beta$, one cannot have both at the same time and only one holds, which gives the number of $\Phi$-boxes the a-tile intersects vertically. $\square$

From now on we assume $\sigma$ and $v$ have the unique size property. Define the subshift $Y_\sigma \subset \mathcal{A}^{BS(1,2)}$ as

$$Y_{\sigma} := \{ y \in \mathcal{A}^{BS(1,2)} \mid \exists \tau \text{ a } \sigma\text{-tiling s.t. } y_g = \tau(\Phi(gat)) \quad \forall g \in BS(1,2) \}.$$

One may have expected to read $y_g = \tau(\Phi(g))$ instead of $y_g = \tau(\Phi(gat))$ in the definition of $Y_\sigma$. This is due to the definition of $\Phi$-box: if a $\Phi(g)$-box can see for instance the top left corner of a $\sigma$-tile (tiles $t_1$ or $t_2$), then $gat$ — i.e. the bottom right corner of the $\Phi(g)$-box — is the only element that is certainly covered by this $\sigma$-tile in the $\sigma$-tiling.

**Proposition 12.** *The set $Y_\sigma$ is a subshift.*

**Proof.** We first prove that the set of configurations $Y_\sigma$ is $\mathfrak{S}$-invariant. Let $y \in Y_\sigma$, then there exists $\tau$ a $\sigma$-tiling of $\mathbb{R}^2$ such that $y_g = \tau(\Phi(gat))$ for every $g \in BS(1,2)$. Let $h \in BS(1,2)$ and denote $z := \mathfrak{S}_h(y)$. Then

$$ 
\begin{align*}
z_g &= (\mathfrak{S}_h(y))_g \\
&= y_{h^{-1} \cdot g} \\
&= \tau(\Phi(h^{-1} \cdot gat)) \\
&= \tau((\alpha + 2\beta x, \beta + y)) \quad \text{where } \Phi(h^{-1}) = (\alpha, \beta) \text{ and } \Phi(gat) = (x, y) \\
&= [S_{\Phi(h^{-1})}(\tau)](g),
\end{align*}
$$

where $S$ is the $\mathbb{R}^2$-action given by

$$S: \left( \begin{array}{cc} \mathbb{R}^2 \times \mathbb{R}^2 & \to \mathbb{R}^2 \\ ((\alpha, \beta), (x, y)) & \to (\alpha + 2\beta x, \beta + y) \end{array} \right).$$

Since $\tau' := S_{\Phi(h^{-1})}(\tau)$ is also a $\sigma$-tiling if $\tau$ is, we have that $z_g = \tau'(\Phi(gat))$ for every $g \in BS(1,2)$ and thus $z = \mathfrak{S}_h(y)$ is also in $Y_\sigma$.

We now check that $Y$ is closed. Take $(y_n)_{n \in \mathbb{N}}$ a sequence of configurations of $Y_\sigma$ that converges toward some $y \in \mathcal{A}^{BS(1,2)}$. Assume that for every $n \in \mathbb{N}$, $\tau_n$ is a $\sigma$-tiling such that $\tau_n(\Phi(g)) = (y_n)_g$ for every $g \in BS(1,2)$. By compactness of $\mathcal{A}^{\mathbb{R}^2}$, there exists $\phi$ an extraction such that the subsequence $(\tau_{\phi(n)})$ is converging toward some $\tau: \mathbb{R}^2 \to \mathcal{A}$. Moreover Proposition 8 implies that $\tau$ is a $\sigma$-tiling of $\mathbb{R}^2$. Define now the configuration $z \in Y$ by $\tau(\Phi(gat)) = z_g$ for every $g \in BS(1,2)$. One can check by a standard compactness argument that $y = z$. Finally the set $Y_\sigma$ is $\mathfrak{S}$-invariant and closed, hence it is a subshift. $\square$

The subshift $Y_\sigma$ is for sure effectively closed, since one can enumerate, by increasing size, the complement of the language $\mathcal{L}(Y_\sigma)$. Note also that for some substitutions $\sigma$, the subshift $Y_\sigma$ is not an SFT. This is the case for Example 13.

**Example 13.** Let $\mathcal{A} = \{0,1\}$ and $\sigma$ the length 3 substitution given by $\sigma(0) = 010$ and $\sigma(1) = 101$. This substitution has two fixpoints $\omega = (01)^2$ and $\omega' = (10)^2$, and $\sigma$ is not recognizable: $\omega = \dots010101.0101010\dots$ can be parsed either as $(010)(101).(010)(101)(010)\dots$
or as ...0)(101)(01.0)(101)(010)... and thus has two different pre-images under $\sigma$. We use this property to show that $Y_{\sigma}$ is not an SFT. By contradiction assume that $Y_{\sigma}$ is an SFT, and $\mathcal{F} \subset \mathcal{A}^{R_{m,n}}$ is a finite set of forbidden patterns that defines it: $Y_{\sigma} = X_{\mathcal{F}}$. Then for $j > n$, the identity and the element $t^j at^{-j}$ cannot be both inside a same rectangle $g \cdot R_{m,n}$.

We construct two configurations x and y in $Y_{\sigma}$, that arise from the two $\sigma$-tilings $\tau$ and $\tau'$ pictured on Figure 5 (left): the $\sigma$-tilings $\tau$ and $\tau'$ coincide on the bottom half plane $R \times \mathbb{R}^{-}$, but the choice to de-substitute the fixpoint $\omega$ immediately above that is different, so that $\tau$ and $\tau'$ never match again on the top half plane $R \times \mathbb{R}^{+}$. These two configurations x and y thus coincide on every group element $h = t^i a^j t^{-k}$ with $i > k$ and only there, see Figure 5 (middle).

<figure><img src="image_8.png" /><figcaption>**Figure 5.** The substitution given by $\sigma(0) = 010$ and $\sigma(1) = 101$ is not recognizable, hence the subshift $Y_{\sigma}$ is not SFT.</figcaption></figure>

We now fix some $j > n$, define $g := t^j at^{-j}$ and a new configuration $z \in \{0,1\}^{BS(1,2)}$ by
$$ 
\begin{cases} 
z_h := y_h & \text{if } h = g \cdot a^k \cdot t^{-\ell} \text{ for some } k \in \mathbb{Z} \text{ and } \ell \in \mathbb{N}; \\ 
z_h := x_h & \text{otherwise.} 
\end{cases} 
$$

Then this configuration $z$ belongs to the subshift $X_{\mathcal{F}}$, since every pattern $z|_{h \cdot R_{m,n}}$ that appears in $z$ also appears in either $y$, if $h = g \cdot a^k \cdot t^{-\ell}$ for some $k \in \mathbb{Z}$ and $\ell \in \mathbb{N}$, or $x$ for every other group element $h$. Nevertheless, the configuration $z$ does not belong to $Y_{\sigma}$, since a $\sigma$-tiling that would correspond to $z$ should be at the same time $\tau$ and $\tau'$, which is impossible. Hence the subshift $Y_{\sigma}$ is not SFT.

In the rest of the article, we wonder what more can be said about $Y_{\sigma}$. In Section 4, we define an SFT cover $X_{\sigma}$ for $Y_{\sigma}$. Section 5 is devoted to prove that the construction of $X_{\sigma}$ is correct. In Section 6 we then discuss dynamical properties of $Y_{\sigma}$.
### 4. An SFT on $BS(1,2)$ to encode $\sigma$-tilings

We now describe an SFT $X_\sigma$ on $BS(1,2)$ that encodes $\sigma$-tilings, i.e. an SFT cover for the subshift $Y_\sigma$. The SFT is made so that a $\sigma$-tiling corresponds to a configuration in $X_\sigma$ and vice-versa (see Theorem 15). We first define integers $h$ and $w_a$ for every letter $a \in \mathcal{A}$ by

* $h := [\log_2(\lambda)] - 1$;

* for every $a \in \mathcal{A}$, $w_a := [v(a)] - 1$.

Since we have chosen $\lambda \ge 8$, we have $h \ge 2$. Similarly since the eigenvector $v$ was chosen so that $v(a) \ge 3$ for every $a \in \mathcal{A}$, we get that $w_a \ge 2$ for every letter $a \in \mathcal{A}$.

**Description of the alphabet.** Denote $M := \max_{a \in \mathcal{A}} |\sigma(a)|$. We define a finite alphabet $\mathcal{R}$ that contains letters like $t_1(b, j, a, i)$, $m_3(a, i)$ or $b_2(a, i)$. More precisely, we consider the alphabet $\mathcal{R} = \mathcal{T} \cup \mathcal{M} \cup \mathcal{B}$, where $\mathcal{T}$ stands for top, $\mathcal{B}$ for bottom and $\mathcal{M}$ for middle, where

$$ \mathcal{T} := t_1 \cup t_2 \cup t_3 \cup t_4 $$

$$ \mathcal{M} := m_1 \cup m_2 \cup m_3 \cup m_4 \cup m_5 $$

$$ \mathcal{B} := b_1 \cup b_2 \cup b_3 $$

with

$$ \alpha := \{\alpha(b, j, a, i) : a, b \in \mathcal{A}, i, j = 1 \dots M\} $$

$$ \beta := \{\beta(a, i) : a \in \mathcal{A}, i = 1 \dots M\} $$

for $\alpha \in \{t_1, m_2\}$ and every $\beta \in \{t_2, t_3, t_4, m_1, m_3, m_4, m_5, b_1, b_2, b_3\}$. The letters $t_i, m_i, b_i$ are the pentagonal Wang tiles described below.

<figure><img src="image_9.png" /></figure>

In the case of a letter $t_1(b, j, a, i)$ or $m_2(b, j, a, i)$, we adopt the convention that $(a, i)$ is associated with the rightmost shaded area, and $(b, j)$ with the leftmost one.

**Intuition on the alphabet.** Informally, every letter in $r \in \mathcal{R}$ gives some local information about the $\sigma$-tiling encoded. Assume $x \in X_\sigma$ and $g \in BS(1,2)$ with normal form $g = t^i a^j t^{-k}$, so that $\Phi(g) = (j \cdot 2^{-i}, k - i)$. Then the letter $r = x_g$ describes what the $\Phi(g)$-box geometrically captures from the $\sigma$-tiling (which $\sigma$-tile is seen, and where it is with horizontal error $2^{k-i}$) and also tells in which position the $\sigma$-tile in from the other $\sigma$-tile immediately above it.

The letter $r$ may code the presence of a vertical line (letters $m_1, m_2$ and $b_1$), of an horizontal line (letters $t_3$ and $t_4$), of a corner (letters $t_1$ and $t_2$) or the absence of borders of $\sigma$-tiles (letters $m_3, m_4, m_5, b_2$ and $b_3$). Figure 6 should be interpreted this way: if a letter $r \in \mathcal{R}$ codes the presence of an element (corner, vertical or horizontal line), it must be located somewhere inside the green shaded area. For instance, the fact that $x_g \in t_1$ is equivalent to the presence of a top left corner somewhere in $\Phi(g) + [2^{k-i}; 2^{k-i+1}[\times] - 1; 0]$. Similarly, the fact that $x_g \in m_2$ is equivalent to the
<figure><img src="image_10.png" /><figcaption>**Figure 6.** Signification of the letter $x_g$ that appears in position $g \in BS(1,2)$ inside a configuration $x \in X_\sigma$. The black rectangle with top left corner labeled by $\Phi(g)$ is the $\Phi(g)$-box.</figcaption></figure>

presence of a vertical line $\{j \cdot 2^i + x\} \times [k-i, k-i+1]$ with $x \in [2^{k-i}; 2^{k-i+1}]$. It follows that going down — following generator $t$ — inside a configuration $x \in X_\sigma$ gives a better approximation of where $\sigma$-tiles are.

**Description of the local rules.** Denote $W := \max_{a \in \mathcal{A}} w_a + 1$. The set $\mathcal{A}_\sigma$ of allowed patterns defining $X_\sigma \subset \mathcal{R}^{BS(1,2)}$ that we describe below is actually a subset of $\mathcal{R}^{R_{3M,3}(h+1)}$. For the purpose of clarity, we do not present directly the set $\mathcal{A}_\sigma$, but instead list some local rules that describe which patterns are in $\mathcal{A}_\sigma$

(1) colors should match on edges along generators $a, a^{-1}, t$ and $t^{-1}$ — this condition is nearest neighbor;

<figure><img src="image_11.png" /></figure>

(2) the type of letter of the first coordinate ($\mathcal{T}$, $\mathcal{M}$ or $\mathcal{B}$) is uniform on the set $\{g \cdot a^k : k \in \mathbb{Z}\}$ for every $g \in BS(1,2)$ — this condition is nearest neighbor;

<figure><img src="image_12.png" /></figure>
(3) the dimensions of the connected shaded zones are bounded in coherence with the substitution $\sigma$. More precisely: there are two possible heights for shaded zones: $h$ and $h-1$, independently from the letter $a \in \mathcal{A}$ coded. The top width of a shaded zone does depend on the letter $a \in \mathcal{A}$ coded, and can only take values from $(w_a - 1)$ to $(2w_a - 1)$.

(4) the letters in $g, g\hat{t}a\hat{t}^{-1}$ and $g\hat{t}a^{-1}t^{-1}$ are synchronized:

(a) $x_g = t_1(b, j, a, i) \Rightarrow \begin{cases} x_{g\cdot\hat{t}a\hat{t}^{-1}} = t_2(a, i) \\ x_{g\cdot\hat{t}a^{-1}t^{-1}} = t_4(b, j) \end{cases}$

(b) $x_g = b_1(a, i) \Rightarrow x_{g\cdot bab^{-1}} = b_1(a, i)$ or $x_{g\cdot ta^{-1}t^{-1}} = b_1(a, i)$

(c) $x_g = b_3(a, i) \Rightarrow x_{g\cdot bab^{-1}} = b_3(a, i)$ or $x_{g\cdot ba^{-1}t^{-1}} = b_3(a, i)$

(d) $x_g = m_1(a, i) \Leftrightarrow x_{g\cdot ta^{-1}t^{-1}} = m_2(b, j, a, i)$

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

(a) $x_g = t_1(b, j, a, i) \Rightarrow \begin{cases} x_{g\cdot\hat{t}a\hat{t}^{-1}} = t_2(a, i) \\ x_{g\cdot\hat{t}a^{-1}t^{-1}} = t_4(b, j) \end{cases}$

(b) $x_g = b_1(a, i) \Rightarrow \begin{cases} x_{g\cdot bab^{-1}} = b_1(a, i) \\ \text{or} \\ x_{g\cdot ta^{-1}t^{-1}} = b_1(a, i) \end{cases}$

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

(c) $x_g = b_3(a, i) \Rightarrow \begin{cases} x_{g\cdot bab^{-1}} = b_3(a, i) \\ \text{or} \\ x_{g\cdot ba^{-1}t^{-1}} = b_3(a, i) \end{cases}$

(d) $x_g = m_1(a, i) \Leftrightarrow x_{g\cdot ta^{-1}t^{-1}} = m_2(b, j, a, i)$

(5) if a shaded area carries information $(a, i)$, then the shaded areas immediately below it must carry information $(a_1, 1), \dots, (a_{|\sigma(a)|}, |\sigma(a)|)$ in this order, with $\sigma(a) = a_1 \dots a_{|\sigma(a)|}$.

<figure><img src="image_19.png" /></figure>

We have now completely defined an SFT $X_\sigma \subset \mathcal{R}^{BS(1,2)}$. In the next section, we prove that a $\sigma$-tiling corresponds to a configuration in $X_\sigma$ and vice-versa, which is the statement of Theorem 15. The example depicted on Figures 7 and Figure 8 should help to understand configurations in $X_\sigma$.

## 5. The SFT $X_\sigma$ encodes $\sigma$-tilings

Remind that $\pi: \mathcal{R} \to \mathcal{A}$ is the mapping defined by

$$ \pi((r, (a, i))) = a $$

$$ \pi((r, (a, i)), (b, j)) = b $$

that only keeps from a letter $r \in \mathcal{R}$ the letter $a \in \mathcal{A}$ of the $a$-tile it encodes. Denote by $p_{\ell, a, i}$ the pattern with support $\{1, a, \dots, a^{\ell-1}\}$ such that

$$ (p_{\ell, a, i})_1 = (b_1, (a, i)); $$

$$ (p_{\ell, a, i})_{aj} = (b_2, (a, i)) \text{ for every } 1 \le j \le \ell - 2; $$

$$ (p_{\ell, a, i})_{a^{\ell-1}} = (b_3, (a, i)). $$
<figure><img src="image_20.png" /><figcaption>**Figure 7.** Example of a configuration $x$ in $X_\sigma$.</figcaption></figure>

The pattern $p_{\ell,a,i}$ is locally admissible if and only if $2^{h-1}(w_a - 3) + 2 \le \ell \le 2^h(2w_a - 1)$. For $\ell, m \in \mathbb{N}$, denote

$$ \mathcal{C}_{g,\ell,m} := \{g \cdot a^i t^{-j} \mid 0 \le i \le \ell-1, 0 \le j \le m\} $$

the $g$-cone of base $\ell$ and height $m$.

**Lemma 14.** Let $x$ and $y$ be two configurations in $X_\sigma$ such that $p_{\ell,a,i}$ appears in $x$ and $y$ in position $g \in BS(1,2)$. Then there exists $m \in \{h, h-1\}$ such that $x_{g'} = y_{g'}$ for every $g' \in \mathcal{C}_{g,\ell,m}$.
<figure><img src="image_21.png" /><figcaption>**Figure 8.** The configuration $x$ of Figure 7 pictured sheet by sheet this time. The $\sigma$-tiling corresponding to $x$ appears in red.</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>**Figure 9.** The pattern $p_{10,a,i}$ on the bottom of the $g$-cone $\mathscr{C}_{g,10,1}$.</figcaption></figure>
**Proof.** We only need to determine that the two configurations $x$ and $y$ coincide on some $\mathscr{C}_{g,\ell,m}$ with $m$ big enough, and the fact that $m \in \{h, h-1\}$ will immediately follow from the local rule (3) given on page 566. We distinguish between several cases that are summarized on Figure 10. With these rules we reconstruct from bottom to top the shaded areas with bottom $p_{\ell,a,i}$, by updating the value of $\ell$ at each step as stated on the picture. Since these rules are totally deterministic, and since the case $w_a - 1 \le \ell \le 2w_a - 1$ is eventually reached, we necessarily obtain a pattern with support $\mathscr{C}_{g,\ell,m}$ with only finite shaded areas on all its sheets. These shaded areas all have the same height $m$ (and $m \ge 2$ by item 2 of Proposition 11), but their top widths may differ.

<figure><img src="image_23.png" /><figcaption>**Figure 10.** The different cases to construct a shaded area starting from its bottom.</figcaption></figure>

Finally since local rules 1 and 4 force a connected shaded component to wear the same information $(a, i)$, all letters $x_{g'}$ and $y_{g'}$ for $g' \in \mathscr{C}_{g,\ell,m}$ are totally determined by the fact that pattern $p_{\ell,a,i}$ appears in $x$ and $y$ in position $g$, and the lemma is proven. $\square$

Lemma 14 ensures that a bottom pattern $p_{n,a,i}$ that appears in some position $g \in BS(1,2)$ forces the entire $g$-cone $\mathscr{C}_{g,n,h}$ or $\mathscr{C}_{g,n,h-1}$ above it.

Define $\pi: \mathcal{R} \to \mathcal{A}$ the mapping given by

$$ \pi((r, (a, i))) = a $$

$$ \pi((r, (a, i), (b, j))) = b $$

that only keeps from a letter $r \in \mathcal{R}$ the letter $a \in \mathcal{A}$ of the $a$-tile it encodes.

**Theorem 15.** If $\tau$ is a $\sigma$-tiling, then there exists a configuration $x \in X_\sigma$ such that $\tau(\Phi(gat)) = \pi(x_g)$ for all $g \in BS(1,2)$. Reciprocally, for every configuration $x \in X_\sigma$, one can associate a $\sigma$-tiling $\tau$ such that $\tau(\Phi(gat)) = \pi(x_g)$ for all $g \in BS(1,2)$.

We will prove Theorem 15 in two steps: Lemma 19 and Lemma 20. Before going into the proofs, remind that for $g \in BS(1,2)$, the $\Phi(g)$-box is the rectangle $\Phi(g) + [0, 2^{-i}[\times] - 1, 0]$ in $\mathbb{R}^2$.

**Remark 16.** The assumption that $v(a) \ge 3$ for every letter $a$ implies that at most one of the $\Phi(g)$ and $\Phi(ga)$-boxes may contain one object among vertical line, cross or $T$.

**Remark 17.** The assumption that $\log_2(\lambda) \ge 3$ implies that at most one of the $\Phi(g)$ and $\Phi(gt)$-boxes may contain one object among horizontal line, cross or $T$.
**Remark 18.** Let $g \in BS(1,2)$ and $k \in \mathbb{N}$. Then the rightmost $\frac{2^k-1}{2^k}$ part of the $\Phi(g)$-box is the leftmost $\frac{2^k-1}{2^k}$ part of the $\Phi(gt^kat^{-k})$-box.

With all these remarks in mind, we are ready to prove Theorem 15. For clarity purpose, we split the theorem into two lemmas.

**Lemma 19.** If $\tau$ is a $\sigma$-tiling, then there exists a configuration $x \in X_\sigma$ such that $\tau(\Phi(gat)) = \pi(x_g)$ for all $g \in BS(1,2)$.

**Proof of Lemma 19.** Let $\tau$ be a $\sigma$-tiling. We define a configuration $x \in \mathcal{R}^{BS(1,2)}$, and then prove that $x \in X_\sigma$. First, every group element $g \in BS(1,2)$ is associated the unique letter $x_g$ in $\mathcal{R}$ such that $\pi(x_g) = \tau(\Phi(gat))$. We now need to determine the letter $x_g \in \mathcal{R}$, i.e. the type of letter, the letter $a \in \mathcal{A}$ and the index $i$ (plus maybe another letter $b$ and another index $j$).

We first define all the $x_g$ such that $x_g \in \mathcal{T}$. To do so, for every group element $g$, we check whether the $\Phi(g)$, $\Phi(ga)$, $\Phi(gt)$ and $\Phi(gat)$-boxes are in one of the following cases (thanks to Remark 16, this list is exhaustive):

(1) if the $\Phi(g)$-box contains a cross or a $T$, and the $\Phi(gt)$-box is empty, set $x_g \in t_1$;

(2) if the $\Phi(g)$-box contains a cross or a $T$, and the $\Phi(gt)$-box contains a vertical line, set $x_g \in t_2$;

(3) if the $\Phi(g)$-box contains an horizontal line and the $\Phi(ga)$-box contains an horizontal line, set $x_g \in t_3$;

(4) if the $\Phi(g)$-box contains an horizontal line, the $\Phi(ga)$-box contains a cross or a $T$, and the $\Phi(gat)$-box is empty, set $x_g \in t_3$;

(5) if the $\Phi(g)$-box contains an horizontal line, the $\Phi(ga)$-box contains a cross or a $T$ and the $\Phi(gat)$-box contains a vertical line, set $x_g \in t_4$.

<figure><img src="image_24.png" /></figure>

From now on, no other group element $g \in BS(1,2)$ will be designated a letter from $\mathcal{T}$. We now list all group elements $g \in BS(1,2)$ that will be designated a letter from $M \setminus \{m_3\}$. Again we check whether the $\Phi(g)$, $\Phi(ga)$, $\Phi(gt)$ and $\Phi(gat)$-boxes are in one of the following cases:

(1) if the $\Phi(g)$ and $\Phi(gt)$-boxes contain a vertical line, set $x_g \in m_1$;

(2) if the $\Phi(g)$-box contains a vertical line and the $\Phi(gt)$-box is empty, set $x_g \in m_2$;

(3) if the $\Phi(g)$-box is empty and the $\Phi(ga)$ and $\Phi(gat)$-boxes contain a vertical line (note that this is equivalent to have $x_ga \in m_1$), set $x_g \in m_4$;

(4) if the $\Phi(g)$-box and $\Phi(gat)$-boxes are empty and the $\Phi(ga)$-box contains a vertical line (note that this is equivalent to have $x_ga \in m_2$), set $x_g \in m_5$.
<figure><img src="image_25.png" /></figure>

Now we force every element $g \in BS(1,2)$ which has not yet been designated a letter in $\mathcal{R}$ and which is such that some $g \cdot a^k$ has been designated a letter in $M \setminus \{m_3\}$ to get letter $m_3$ (we fill in the holes inside $M$-rows).

We finally list all group elements $g \in BS(1,2)$ that will be designated a letter from $\mathcal{B}$. Again we check whether the $\Phi(g)$, $\Phi(ga)$, $\Phi(gt)$ and $\Phi(gat)$-boxes are in one of the following cases:

(1) if the $\Phi(gt)$-box or the $\Phi(gta)$-box contains a cross, set $x_g \in b_1$;

(2) if the $\Phi(g)$ and $\Phi(ga)$-boxes are empty and the $\Phi(gt)$-box contains an horizontal line or a $T$, set $x_g \in b_2$;

(3) if the $\Phi(g)$-box is empty, the $\Phi(gt)$-box contains an horizontal line or a $T$ and the $\Phi(ga)$-box contains a vertical line, set $x_g \in b_3$.

<figure><img src="image_26.png" /></figure>

A careful observation of all possible cases treated by the three previous lists show that every element $g \in BS(1,2)$ necessarily falls into one of the cases described, so that every element $g \in BS(1,2)$ is now designated a letter from $\mathcal{R}$.

To get a configuration $x \in \mathcal{R}^{BS(1,2)}$, it only remains to assign letters from $\mathcal{A}$ and indices to shaded connected areas. They are chosen to be identical for all letters in a same shaded area. Consider one shaded area. The top left corner, of type $t_1$ or $t_2$, appears in some position $g \in BS(1,2)$. The corresponding $\Phi(g)$-box contains a top left corner of a $\sigma$-tile. Denote $a$ the corresponding letter : assign the letter $a$ to every letter in $\mathcal{R}$ belonging to the shaded area. To determine the index $i$, it is enough to look at the $\sigma$-tile immediately above in the $\sigma$-tiling. Assume it is a $a'$-tile, and that our shaded area corresponds to the index $i$ such that $\sigma(a')_i = a$: assign the index $i$ to every letter in $\mathcal{R}$ belonging to the shaded area. For letters in $t_1$ or $m_2$, the additional letter $b$ and index $j$ are chosen to be the letter and index associated with the shaded area immediately to the left.

We now check that this configuration $x \in \mathcal{R}^{BS(1,2)}$ in actually in $X_\sigma$ (local rules are listed on page 565). By construction, it is straightforward that local rules 1, 2 and 5 are respected. The definition of $\sigma$-tiles (see page 559) implies that local rule (3) is satisfied. And a careful reading of Remark 18 ensures that local rule 4 always holds. Finally, we can associate to every $\sigma$-tiling a valid configuration $x \in X_\sigma$ such that $\tau(\Phi(gat)) = \pi(x_g)$ for all $g \in BS(1,2)$, so Lemma 19 is proven. $\square$

**Lemma 20.** For every configuration $x \in X_\sigma$, one can associate a $\sigma$-tiling $\tau$ such that $\tau(\Phi(gat)) = \pi(x_g)$ for all $g \in BS(1,2)$.
Before going into the proof of Lemma 20, we focus on the left borders of the shaded areas in configurations of $X_σ$. Let $\mathcal{D}$ be the transducer depicted on Figure 11. A transition $(q, w, q')$ in $\mathcal{D}$ should be interpreted as: if a letter $q$ appears in some position $g$ in a configuration $x$ from $X_σ$, then the letter $q'$ may appear in position $g \cdot w$ in $x$.

<figure><img src="image_27.png" /><figcaption>**Figure 11.** The transducer $\mathcal{D}$ that summarizes how letters from alphabet $\mathcal{R}$ can be arranged to form the left border of shaded areas. The transition in green corresponds to the situation pictured to the right.</figcaption></figure>

We could have constructed a bigger transducer that would imply all letters from $\mathcal{R}$, but for the purpose of Lemma 20 we only need to focus on letters $t_1, t_2, m_1, m_2$ and $b_1$ since there are the only ones that may appear on the left border of a shaded area. Note that this transducer $\mathcal{D}$ is non deterministic, but for our purpose the uniqueness of the infinite path described in Proposition 21 is enough.

**Proposition 21.** Let $x$ be a configuration of $X_σ$. Let $g_0 \in \text{BS}(1,2)$ be a group element such that $x_{g_0} \in t_1 \cup t_2$. Then there exists a unique infinite path $(q_i, w_i)_{i \in \mathbb{N}}$ in the transducer $\mathcal{D}$ such that

$$x_{g_0 \cdot \Pi_{i=0}^n w_i} \in q_n$$

for every $n \in \mathbb{N}$.

**Proof.** The proof follows directly from a careful observation of the local rules, and more particularly local rule 1 (see Page 565). $\square$

Let $x \in X_σ$ and $g_0 \in \text{BS}(1,2)$ such that $x_{g_0} \in t_1 \cup t_2 \cup b_1 \cup m_1 \cup m_2$. Assume that $g_0$ has normal form $g_0 = t^i a^j t^{-k}$. Thanks to Proposition 21, there exists an infinite path $(q_i, w_i)_{i \in \mathbb{N}}$ in the transducer $\mathcal{D}$ such that

$$x_{g_0 \cdot \Pi_{i=0}^n w_i} \in q_n$$

for every $n \in \mathbb{N}$ and this path is unique. Define

$$v(x_{g_0}) := j \cdot 2^{-i} + 2^{k-i} \cdot \left( \sum_{\ell=0}^{\infty} \delta_{w_\ell}^{t\alpha} \cdot 2^{-\ell-1} \right) \in [j \cdot 2^{-i}; (j+1) \cdot 2^{k-i}]$$

to be the position of the vertical line at $g_0$ in $x$, where $\delta_q^r$ is the Kronecker symbol that equals 1 if $q = r$ and 0 otherwise.
**Proposition 22.** For a given configuration $x \in X_\sigma$ and group element $g_0 \in BS(1, 2)$, define the finite word $h \in \{ta, t\}^M$ as the label of the M first transition of the unique path given by Proposition 21. Then

$$v(x_{g_0}) = v(x_{g_0 \cdot h}).$$

**Proof.** First note that if $(q_i, w_i)_{i \in \mathbb{N}}$ is the unique infinite path in the transducer $\mathcal{D}$ for $g_0$, then $(q_{i+M}, w_{i+M})_{i \in \mathbb{N}}$ is the unique infinite path in the transducer $\mathcal{D}$ for $g_0 \cdot h$. Then, using the normal form of $g_0$ and the fact that $t^{-k}a = a^{2^k}t^{-k}$, we deduce the normal form for $g_0 \cdot h$.

$$
\begin{align*}
g_0 \cdot h &= t^i \cdot a^j \cdot t^{-k} \cdot h_0 \dots h_{M-1} \\
&= t^i \cdot a^{j+2^{k-1} \cdot \delta_{h_0}^{ta}} \cdot t^{-(k-1)} \cdot h_1 \dots h_{M-1} \\
&= t^i \cdot a^{j+2^{k-1} \cdot \delta_{h_0}^{ta} + 2^{k-2} \cdot \delta_{h_1}^{ta}} \cdot t^{-(k-2)} \cdot h_2 \dots h_{M-1} \\
&= t^i \cdot a^{j+\sum_{\ell=0}^{M-1} 2^{k-\ell-1} \cdot \delta_{h_\ell}^{ta}} \cdot t^{-(k-M)}
\end{align*}
$$

There are now two cases. If $M-k \le 0$, then we have the normal form for $g_0 \cdot h$. By definition,

$$
\begin{align*}
v(g_0 \cdot h) &= \left( j + \sum_{\ell=0}^{M-1} 2^{k-\ell-1} \cdot \delta_{h_\ell}^{ta} \right) \cdot 2^{-i} + 2^{k-M-i} \cdot \sum_{\ell=0}^{\infty} \delta_{w_{M+\ell}}^{ta} \cdot 2^{-\ell-1} \\
&= j \cdot 2^{-i} + 2^{k-i} \left( \sum_{\ell=0}^{M-1} 2^{-\ell-1} \cdot \delta_{h_\ell}^{ta} + \sum_{\ell=0}^{\infty} \delta_{w_{M+\ell}}^{ta} \cdot 2^{-M-\ell-1} \right) \\
&= j \cdot 2^{-i} + 2^{k-i} \left( \sum_{\ell=0}^{M-1} 2^{-\ell-1} \cdot \delta_{h_\ell}^{ta} + \sum_{\ell=M}^{\infty} \delta_{w_\ell}^{ta} \cdot 2^{-\ell-1} \right) \\
&= v(g_0)
\end{align*}
$$

and we are done.

If $M-k \ge 0$, then using the fact that $at^k = t^k a^{2^k}$ we get that the normal form for $g_0 \cdot h$ is this time

$$g_0 \cdot h = t^{i+M-k} \cdot a^{2^{M-k} \left( j + \sum_{\ell=0}^{M-1} 2^{k-\ell-1} \cdot \delta_{h_\ell}^{ta} \right)}$$

and thus

$$
\begin{align*}
v(g_0 \cdot h) &= 2^{M-k} \left( j + \sum_{\ell=0}^{M-1} 2^{k-\ell-1} \cdot \delta_{h_\ell}^{ta} \right) \cdot 2^{-i-M+k} + 2^{-i-M+k} \cdot \sum_{\ell=0}^{\infty} \delta_{w_{M+\ell}}^{ta} \cdot 2^{-\ell-1} \\
&= j \cdot 2^{-i} + 2^{k-i} \left( \sum_{\ell=0}^{M-1} 2^{-\ell-1} \cdot \delta_{h_\ell}^{ta} + \sum_{\ell=M}^{\infty} \delta_{w_\ell}^{ta} \cdot 2^{-\ell-1} \right) \\
&= v(g_0)
\end{align*}
$$

and the proposition is proven. □

**Proof of Lemma 20.** Let $x$ be a configuration in $X_\sigma$. We proceed in two steps

(1) every sheet of $x$ defines a $\sigma$-tiling;

(2) the $\sigma$-tiling defined by one sheet of $x$ is compatible with all the sheets.

**Step 1: every sheet of $x$ defines a $\sigma$-tiling.** Consider one sheet in $x$. Our strategy to define $\tau$ a $\sigma$-tiling is the following: we first partially describe a tiling through all its vertical lines, then using the fact we want a $\sigma$-tiling, we define horizontal lines and the type — i.e. the letter $a \in \mathcal{A}$ — of every $\sigma$-tile. In what follows we speak of absolute — horizontal or vertical — positions.

(1) Thanks to Proposition 22, every top tile $t_1(..., i \ge 2)$ or $t_2(..., i \ge 2)$ in position $g$ defines a semi-infinite vertical line: its horizontal position is completely determined and equals $v(x_g)$, while its vertical position is only known up to some error.
(2) Now that all the horizontal positions of semi-infinite vertical lines are known, we deduce the exact position of all tiles composing $\tau$ from the definition of $\sigma$-tiles (see Figure 3). Note that the type of tile $a \in \mathcal{A}$ is given by the letter $t_1$ or $t_2$ on the top left corner. An $a$-tile with left and right borders at horizontal positions $x_\ell$ and $x_r$ respectively should be at position $(x_\ell, \log_2(\frac{x_\ell-x_\ell}{v(a)}))$.

With these two conditions together, the tiling $\tau$ we get is indeed a $\sigma$-tiling.

**Step 2: all sheets define the same $\sigma$-tiling.** We need to check that two different sheets give the same $\sigma$-tiling under the construction described immediately above. This is actually ensured by local rule 4 on page 566: this condition forces left border of shaded area to be synchronized between merging sheets, hence the horizontal positions of vertical lines do not depend on the sheet chosen. $\square$

**Proposition 23.** The subshift $X_\sigma$ is an SFT cover of $Y_\sigma$, and this latter is consequently a sofic subshift.

**Proof.** This is a direct consequence of Theorem 15: the onto morphism from $X_\sigma$ to $Y_\sigma$ is the letter-to-letter morphism given by the local map $\pi$. $\square$

**6. Dynamical properties of $X_\sigma$**

**Proposition 24.** The subshift $X_\sigma$ is minimal if and only if $\log_2(\lambda)$ is irrational.

**Proof.** Assume that $\log_2(\lambda)$ is irrational. Let $x, y$ be two configurations in $X_\sigma$. We prove that the orbit of $x$ is dense in $X_\sigma$, i.e. that for every $\varepsilon > 0$, there exists some $g \in BS(1,2)$ such that $\mathfrak{S}_g(x)$ is close enough to $y$, i.e. that $d(\mathfrak{S}_g(x), y) < \varepsilon$. We fix $\varepsilon = 2^{-N}$ and we proceed in two steps. First we use that the set $\{[k \cdot \log_2(\lambda)] - k \cdot \log_2(\lambda) \mid k \in \mathbb{Z}\}$ is dense in $[0;1]$, since $\log_2(\lambda)$ has be assumed irrational. Thus by a shift $t^k$, we can synchronize the tilings $\tau_{\mathfrak{S}_{,k}(x)}$ and $\tau_y$ so that their sequences of height $h$ and height $h+1$ rows coincide at least on the ball of radius $N$. Second we use that since the substitution $\sigma$ is primitive, then the subshift $Z_\sigma$ is minimal. With a shift $t^n a^\ell t^{-n}$ we can perform an horizontal shift of $\ell 2^{-n}$ on $\tau_{\mathfrak{S}_{,k}(x)}$ so that $d(\mathfrak{S}_{t^n a^\ell t^{-n} t^k(x)}, y) < \varepsilon$ by minimality of $Z_\sigma$ as required. Thus $X_\sigma$ is minimal.

Conversely, assume $\log_2(\lambda)$ is rational and can be written as $\log_2(\lambda) = \frac{p}{q}$ with $p, q \in \mathbb{N}^*$ and $q \nmid p$ (unless $q=1$). Then with $q$ rows of $\sigma$-tiles, we get a stripe of height $p \in \mathbb{N}^*$. Assume that the top of this stripe has integer vertical coordinate $y \in \mathbb{Z}$. Then all other stripes of $q$ rows of $\sigma$-tiles have integer coordinates. Denote $\tau$ this $\sigma$-tiling, and $x \in X_\sigma$ the corresponding configuration obtained as in the proof of Lemma 19. If we consider $\tilde{h} := (h_i)_{i \in \mathbb{Z}}$ the sequence of $h$'s and $(h+1)$'s where $h_i$ is the number of $\Phi$-boxes a $\sigma$-tile intersects vertically on the $i$th row of $\tau$, we get a periodic sequence with period $H = h_1 \dots h_q$. And so $h$'s and $h+1$' have frequencies $f_h = \frac{|\{i \in \{1,q\} \mid h_i = h\}|}{q}$ and $f_{h+1} = 1 - f_h$ in $\tilde{h}$. Also since we have chosen that all stripes of $q$ rows of $\sigma$-tiles have integer coordinates, we deduce that both $h_1 = h$ and $h_q = h$.

Define $\delta := \min\{d(i \cdot \frac{p}{q}, \mathbb{N}) \mid i = 1 \dots q-1\}$. Then necessarily $\delta > 0$, otherwise $q \nmid p$. Consider $\tau'$ the $\sigma$-tiling obtained by vertically shifting $\tau$ by $+\frac{\delta}{2}$, and denote $x'$ the associated configuration in $X_\sigma$ and $\tilde{h}' := (h'_i)_{i \in \mathbb{Z}}$ the sequence of $h'$ and $h+1$' where $h'_i$ is the number of $\Phi$-boxes a $\sigma$-tile intersects vertically on the $i$th row of $\tau'$. Similarly to $\tilde{h}$, the sequence $\tilde{h}'$ is periodic with period $q$, but with $h'_1 = h+1$. So the frequencies of $h'$ and $h+1$' in $\tilde{h}$ and $\tilde{h}'$ are strictly different, thus $x'$ cannot be in the orbit of $x$. And finally the subshift $X_\sigma$ is not minimal, which terminates the proof. $\square$

**Proposition 25.** The subshift $Y_\sigma$ is strongly aperiodic if $\log_2(\lambda)$ is irrational.
<figure><img src="image_28.png" /><figcaption>**Figure 12.** Illustration of the proof that if $\log_2(\lambda)$ is rational, then $X_\sigma$ is not minimal: two $\sigma$-tilings $\tau$ and $\tau'$ that give two configurations $x$ and $x'$ both in $X_\sigma$ but not in the same orbit.</figcaption></figure>

**Proof.** Let $y \in Y_\sigma$, and assume that $h$ is a period for $y$: for every $g \in BS(1, 2)$, one has $y_g = y_{h^{-1}g}$.

If $h^{-1}$ has normal form $h^{-1} = t^\ell a^m t^{-p}$ and $gat$ has normal form $gat = t^i a^j t^{-k}$, the fact that $y_g = y_{h^{-1}g}$ is equivalent to

$$ \tau(j \cdot 2^{-i}, k-i) = \tau((j+m \cdot 2^{i-p}) 2^{p-\ell-i}, p-\ell+k-i) $$

for a certain $\sigma$-tiling $\tau$. Fix $i = j = 0$ in this equality. Then for every $k \in \mathbb{N}$, one has

$$ \tau(0, k) = \tau(m \cdot 2^{p-\ell}, p-\ell+k). $$

Since $\log_2(\lambda)$ is irrational, there exists some $k_0 \in \mathbb{N}$ such that $\tau(0, k_0)$ and $\tau(m \cdot 2^{p-\ell}, p-\ell+k_0)$ do not belong to the same horizontal row of $\sigma$-tiles. Thus two different rows of $\sigma$-tiles in $\tau$ are the same, up to an horizontal translation by $m \cdot 2^{p-\ell}$. This is possible only if the translation by $(m \cdot 2^{p-\ell}, p-\ell)$ is trivial, i.e. $h = 1$. Finally every configuration $y \in Y_\sigma$ has a trivial stabilizer, so the subshift $Y_\sigma$ is strongly aperiodic. $\square$

As an immediate consequence of Proposition 25 and Proposition 23 we get that the SFT $X_\sigma$ is also strongly aperiodic, provided $\log_2(\lambda)$ is irrational.

**Proposition 26.** The SFT $X_\sigma$ is strongly aperiodic if $\log_2(\lambda)$ is irrational.

Since $X_\sigma$ is minimal, then it has zero entropy as a direct consequence of a result by Barbieri [6].
Thanks to Lemma 14, we can also prove that the SFT $X_\sigma$ has zero entropy in the general case.

**Proposition 27.** The SFT $X_\sigma$ has zero entropy.

**Proof.** Choose $k$ and $\ell$ such that $\ell \gg h$. Recall that

$$ R_{k,\ell} := \{t^\ell a^i t^{-j} \mid i \in [0; (k+1) \cdot 2^{\ell-1}-1] \text{ and } j \in [0; \ell]\}. $$
We define three subsets of $R_{k,l}$:

$$ \text{Bottom} := \{t^l a^i t^{-j} \mid i \in [0; (k+1) \cdot 2^{l-1} - 1] \text{ and } j \in [0; k]\}; $$

$$ \text{Left} := \{t^l a^i t^{-j} \mid i \in [0; 2^{l-1} - 1] \text{ and } j \in [0; l]\}; $$

$$ \text{Right} := \{t^l a^i t^{-j} \mid i \in [k \cdot 2^{l-1}; (k+1) \cdot 2^{l-1} - 1] \text{ and } j \in [0; l]\}; $$

$$ \text{Top} := \{t^l a^i t^{-j} \mid i \in [0; (k+1) \cdot 2^{l-1} - 1] \text{ and } j \in [l-k; l]\}. $$

Denote $N := \#\text{Bottom} + \#\text{Left} + \#\text{Right} + \#\text{Top}$. Then

$$ N = 2(k+1)^2 \cdot 2^{l-1} + 2l \cdot 2^{l-1}, $$

and since $|R_{k,l}| = l \cdot (k+1) \cdot 2^{l-1}$, we get that $\lim_{k,l \to \infty} \frac{N}{|R_{k,l}|} = 0$.

Consider now a pattern $p$ with support $R_{k,l}$ that is in the language of $X_\sigma$. Then by Lemma 14 and Local rule 5, the pattern $p$ is entirely determined by $p_{\text{Bottom} \cup \text{Left} \cup \text{Right} \cup \text{Top}}$. Hence $\#\mathcal{L}_{k,l}(X_\sigma) \le |\mathcal{R}|^N$ and consequently

$$ \begin{align*} h(X_\sigma) &= \lim_{k,l \to \infty} \frac{\log(\#\mathcal{L}_{k,l}(X_\sigma))}{|R_{k,l}|} \\ &\le \lim_{k,l \to \infty} |\mathcal{R}| \frac{N}{|R_{k,l}|} \\ &= 0. \end{align*} $$

So the SFT $X_\sigma$ has zero entropy. $\square$

# 7. An application: a hierarchical strongly aperiodic SFT on $BS(1,2)$

## 7.1. Robinson hyperbolic tileset

In the classical construction of a strongly aperiodic SFT on $\mathbb{Z}^2$ [21], all valid tilings present a hierarchical structure of squares of increasing size, where the same process is repeated to obtain bigger and bigger squares: four squares of the same size are gathered to form a bigger square. The smallest squares are enforced by bumpy tiles (tiles 1 on Figure 13).

The situation is more complex on $\mathbb{H}_2$, and instead of bumpy tiles and others, we use the five shapes pictured on Figure 14. These preliminary local rules already impose strong constraints of valid tilings. The global structure of A/B/C/D/E tilings appears on Figure 15. Indeed, first remark that decorations on left and right sides of the tiles impose that horizontal rows are either composed with A/B/C or with D/E. Then a careful study of the corners show an alternation of A/B/C rows and D/E rows, and that inside an A/B/C row, B tiles necessarily appear one time in two.

On Figure 15 is pictured what would be an hyperbolic analogue of a square of level 1 in the Robinson tiling on $\mathbb{Z}^2$: on the same horizontal row, two nearest neighbor tiles B carry the top left and top right corners of the square; the bottom corners are located two rows below, but the geometry of $\mathbb{H}_2$ imposes that, between these two corners carried by tiles B, we find $5^2 - 1 = 24$ other tiles B. Figure 15 show that, contrary to the $\mathbb{Z}^2$ case, not all the B tiles carry a corner of a square. Thus we will need many more tiles than on $\mathbb{Z}^2$.

Before we go any further in the description of tiles of the hyperbolic Robinson tiling, one can already notice that constraints imposed by the five shapes of tiles are strong, and almost
<figure><img src="image_29.png" /><figcaption>**Figure 13.** On the left the six tiles from which one gets the whole Robinson's tileset, thanks to rotations and reflections. On the right a pattern made with Robinson's tileset.</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>**Figure 14.** The five shapes of tiles A, B, C, D and E on $\mathbb{H}_2$. Tile B is the only one with bumpy corners, tiles A and C have both bumpy and dented corners while tiles D and E have only dented corners.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>**Figure 15.** Location of the B tiles (in grey) in a tiling. In blue, the expected shape of a square of level 1.</figcaption></figure>
<figure><img src="image_32.png" /><figcaption>**Figure 16.** The additional decorations on tiles A/B/C/D/E to get the hyperbolic Robinson tileset, as they are presented in [15] and reproduced by kind permission of the author.</figcaption></figure>

deterministic in some sense. Denote $\sigma$ the non-deterministic substitution on the alphabet $\{A, B, C, D, E\}$ given by the rules

$$\sigma(A) = DDEDD$$

$$\sigma(B) = DDDDD$$

$$\sigma(C) = DDEDD$$

$$\sigma(D) = BCBCB \text{ or CBCBC}$$

$$\sigma(E) = CBABC.$$

A careful comparison between the orbits of this substitution $\sigma$ and the A/B/C/D/E tilings shows that an orbit of $\sigma$ can be seen as an A/B/C/D/E tiling, and vice-versa.

**Proposition 28.** To every tiling of $\mathbb{H}_2$ with tiles A/B/C/D/E, one can associate the orbit of a bi-infinite word $w \in \{A, B, C, D, E\}^\mathbb{Z}$ under the action of $\sigma$.

If we add extra decorations to the tiles A/B/C/D/E, we get new tilings of $\mathbb{H}_2$. Thanks to Proposition 28, one can think about these tilings as SFTs on orbit graphs of $\sigma$, so that the construction of Section 5 can be used.

We now enrich the basic tileset $\{A, B, C, D, E\}$ by adding decorations pictured on Figure 16 so that the description of the hyperbolic Robinson tileset is finalized.

With the enriched tileset obtained by adding decorations from Figure 16 to the A/B/C/D/E tiles, we can tile the discrete hyperbolic plane $\mathbb{H}_2$, and the structure of tilings is schematized on Figure 17.

To obtain a tileset analogue with Robinson's and Goodman-Strauss's on every $BS(1, n)$ with $n \ge 2$, it suffices to apply Theorem 15 to the $\sigma$-tilings with $\sigma$ the substitution on alphabet $\{A, B, C, D, E\}$ defined above, and to enrich the SFT $X_\sigma$ with local rules so that the hyperbolic Robinson's tiling is copied out on every sheet of $BS(1, n)$.

**Theorem 29.** For every $n \ge 2$ there exists a strongly aperiodic SFT on $BS(1, n)$ such that every configuration $x$ of the SFT carries an hyperbolic Robinson tiling on every single sheet of $x$.
<figure><img src="image_33.png" /><figcaption>**Figure 17.** Schematic view of the first levels of the hierarchy of squares enforced by the hyperbolic Robinson's tileset. hyperbolic squares of level 1, 2 and 3 are pictured in blue, green and red. The structure that appears is an hyperbolic analogue of the one visible on Figure 13.</figcaption></figure>

**Acknowledgments**

The authors are grateful to the anonymous referee for his relevant comments. The authors are thankful to Chaim Goodman-Strauss for letting us use his pictures.

**Declaration of interests**

The authors do not work for, advise, own shares in, or receive funds from any organization that could benefit from this article, and have declared no affiliations other than their research organizations.

**References**

[1] N. Aubrun, S. Barbieri and E. Moutot, “The Domino Problem is Undecidable on Surface Groups”, in *44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)*, 2019.

[2] N. Aubrun, S. Barbieri and S. Thomassé, “Realization of aperiodic subshifts and uniform densities in groups”, *Groups Geom. Dyn.* **13** (2018), no. 1, pp. 107–129.

[3] N. Aubrun, N. Bitar and S. Huriot-Tattegrain, “Strongly aperiodic SFTs on generalized Baumslag–Solitar groups”, *Ergodic Theory Dyn. Syst.* (2023).

[4] N. Aubrun and J. Kari, “Tiling Problems on Baumslag-Solitar groups”, in *Proceedings of the conference on machines, computations and universality 2013, MCU 2013* (T. Neary et al., ed.), Open Publishing Association, 2013, pp. 35–46.

[5] N. Aubrun and J. Kari, “On the domino problem of the Baumslag-Solitar groups”, *Theor. Comput. Sci.* **894** (2021), pp. 12–22. Building Bridges – Honoring Nataša Jonoska on the Occasion of Her 60th Birthday.

[6] S. Barbieri, “On the entropies of subshifts of finite type on countable amenable groups”, *Groups Geom. Dyn.* **15** (2021), no. 2, pp. 607–638.

[7] S. Barbieri and M. Sablik, “A generalization of the simulation theorem for semidirect products”, *Ergodic Theory Dyn. Syst.* **39** (2019), no. 12, pp. 3185–3206.

[8] D. B. Cohen and C. Goodman-Strauss, “Strongly aperiodic subshifts on surface groups”, *Groups Geom. Dyn.* **11** (2017), no. 3, pp. 1041–1059.

[9] D. B. Cohen, C. Goodman-Strauss and Y. Rieck, “Strongly aperiodic subshifts of finite type on hyperbolic groups”, *Ergodic Theory Dyn. Syst.* **42** (2021), no. 9, pp. 2740–2783.
[10] K. Culik and J. Kari, "An aperiodic set of Wang cubes", in *J. UCS The Journal of Universal Computer Science: Annual Print and CD-ROM Archive Edition Volume 1* • 1995 (H. Maurer, C. Calude and A. Salomaa, eds.), Springer, 1996, pp. 675–686.

[11] S. J. Esnay and E. Moutot, "Aperiodic SFTs on Baumslag-Solitar groups", *Theor. Comput. Sci.* **917** (2022), pp. 31–50.

[12] B. Farb and L. Mosher, "A rigidity theorem for the solvable Baumslag-Solitar groups", *Invent. Math.* **131** (1998), pp. 419–451.

[13] S. Gao, S. Jackson and B. Seward, "A coloring property for countable groups", *Math. Proc. Camb. Philos. Soc.* **147** (2009), pp. 579–592.

[14] C. Goodman-Strauss, "A strongly aperiodic set of tiles in the hyperbolic plane", *Invent. Math.* **159** (2004), no. 1, pp. 119–132.

[15] C. Goodman-Strauss, "A hierarchical strongly aperiodic set of tiles in the hyperbolic plane", *Theor. Comput. Sci.* **411** (2010), no. 7, pp. 1085–1093.

[16] E. Jeandel, "Aperiodic Subshifts of Finite Type on Groups", 2015, 1501.06831.

[17] J. Kari, "A small aperiodic set of Wang tiles", *Discrete Math.* **160** (1996), no. 1, pp. 259–264.

[18] R. C. Lyndon and P. E. Schupp, *Combinatorial Group Theory*, reprint of the 1977 edition, Springer, 2001.

[19] D. E. Muller and P. E. Schupp, "The theory of ends, pushdown automata, and second-order logic", *Theor. Comput. Sci.* **37** (1985), pp. 51–75.

[20] D. S. Ornstein and B. Weiss, "Entropy and isomorphism theorems for actions of amenable groups", *J. Anal. Math.* **48** (1987), no. 1, pp. 1–141.

[21] R. Robinson, "Undecidability and nonperiodicity for tilings of the plane", *Invent. Math.* **12** (1971), pp. 177–209.

[22] A. A. Şahin, M. Schraudner and I. Ugarcovici, "A strongly aperiodic shift of finite type on the discrete Heisenberg group using Robinson tilings", *Ill. J. Math.* **65** (2021), no. 3, pp. 655–686.

[23] K. Whyte, "The large scale geometry of the higher Baumslag-Solitar groups", *Geom. Funct. Anal.* **11** (2001), pp. 1327–1343.