# Three characterizations of a self-similar aperiodic 2-dimensional subshift

Sébastien Labbé  Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400,
Talence, France<EMAIL_ADDRESS>
###### Abstract.

The goal of this chapter is to illustrate a generalization of the Fibonacci
word to the case of 2-dimensional configurations on $\mathbb{Z}^{2}$. More
precisely, we consider a particular subshift of $\mathcal{A}^{\mathbb{Z}^{2}}$
on the alphabet $\mathcal{A}=\\{0,\dots,18\\}$ for which we give three
characterizations: as the subshift $\mathcal{X}_{\phi}$ generated by a
2-dimensional morphism $\phi$ defined on $\mathcal{A}$; as the Wang shift
$\Omega_{\mathcal{U}}$ defined by a set $\mathcal{U}$ of 19 Wang tiles; as the
symbolic dynamical system
$\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}}$ representing the
orbits under some $\mathbb{Z}^{2}$-action $R_{\mathcal{U}}$ defined by
rotations on $\mathbb{T}^{2}$ and coded by some topological partition
$\mathcal{P}_{\mathcal{U}}$ of $\mathbb{T}^{2}$ into 19 polygonal atoms. We
prove their equality
$\Omega_{\mathcal{U}}=\mathcal{X}_{\phi}=\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}}$
by showing they are self-similar with respect to the substitution $\phi$.

This chapter provides a transversal reading of results divided into four
different articles obtained through the study of the Jeandel-Rao Wang shift.
It gathers in one place the methods introduced to desubstitute Wang shifts and
to desubstitute codings of $\mathbb{Z}^{2}$-actions by focussing on a simple
2-dimensional self-similar subshift. SageMath code to find marker tiles and
compute the Rauzy induction of $\mathbb{Z}^{2}$-rotations is provided allowing
to reproduce the computations.

###### Key words and phrases:

aperiodic and subshift and Sturmian and tiling and substitution and self-
similar and SFT and Markov partition and self-induced and coding of rotations
and Rauzy induction and polyhedron exchange transformation

###### 2010 Mathematics Subject Classification:

Primary 37B50; Secondary 52C23, 28D05

The author acknowledges financial support from the Agence Nationale de la
Recherche through the projects CODYS (ANR-18-CE40-0007) and PARADIS
(ANR-18-CE23-0007-01).

##  1\. Introduction

The rule $s:a\mapsto ab,b\mapsto a$ defines a morphism on the monoid
$\\{a,b\\}^{*}$. The succesive application of this morphism on the letter $a$
defines longer and longer words covering the negative and non-negative
integers:

$\begin{array}[]{r|l}s^{0}(a)&s^{0}(a)\\\ s^{1}(a)&s^{1}(a)\\\
s^{2}(a)&s^{2}(a)\\\ s^{3}(a)&s^{3}(a)\\\ s^{4}(a)&s^{4}(a)\\\
s^{5}(a)&s^{5}(a)\\\
\end{array}\qquad=\qquad\begin{array}[]{r|l}\underline{a}&a\\\
\underline{ab}&ab\\\ a\underline{ba}&aba\\\ aba\underline{ab}&abaab\\\
abaaba\underline{ba}&abaababa\\\ abaababaaba\underline{ab}&abaababaabaab\\\
\end{array}$

The letters that change from line to line are underlined. It is an interesting
exercise to show that at the limit, we obtain
$\lim_{n\to\infty}s^{2n}(a)|s^{2n}(a)=\widetilde{F}ba|F$ and
$\lim_{n\to\infty}s^{2n+1}(a)|s^{2n+1}(a)=\widetilde{F}ab|F$ where $F$ is the
well-known right-infinite Fibonacci word [Ber80]. The rule $s$ can be seen as
a substitution that we may apply on the biinfinite words $x=\widetilde{F}ba|F$
and $y=\widetilde{F}ab|F$ and we observe that $s(x)=y$ and $s(y)=x$. Thus
$s^{2}(x)=x$ and $s^{2}(y)=y$ and we say that $x$ and $y$ are fixed points of
$s^{2}$. The set of finite words that appear in $x=s^{2}(x)$ defines a
language

$\mathcal{L}_{s}=\\{\varepsilon,a,b,aa,ab,ba,aab,aba,baa,bab,aaba,\dots\\}\subset\\{a,b\\}^{*}$

and a subshift

$\mathcal{X}_{s}=\\{u\in\\{a,b\\}^{\mathbb{Z}}\colon\text{the finite words
that appear in }u\text{ are in }\mathcal{L}_{s}\\}.$

The subshift $\mathcal{X}_{s}$ contains $x$, $y$, all shifts of $x$ and $y$,
and much more. Indeed, $\mathcal{X}_{s}$ is a Sturmian shift which is an
uncountable set. The reader will find detailed information on Sturmian
sequences in [Lot02, Chapter 2] and [Fog02, Chapter 6]. In particular,
$\mathcal{X}_{s}$ is aperiodic, that is, none of the sequences in
$\mathcal{X}_{s}$ is periodic.

It is known since the early work of Morse and Hedlund in [MH40] and Coven and
Hedlund in [CH73] that the 1-dimensional subshift $\mathcal{X}_{s}$, being a
Sturmian subshift, has many equivalent characterizations:

  * •

as the subshift generated by the 1-dimensional substitution $s$;

  * •

as the subshift on $\\{a,b\\}$ having exactly $n+1$ factors of length $n$ and
such that the ratio of the frequency of the two letters is
$\frac{1+\sqrt{5}}{2}$;

  * •

as the symbolic representation of a rotation on the $1$-dimensional torus
$\mathbb{T}=\mathbb{R}/\mathbb{Z}$ through a partition into two intervals.

The goal of this chapter is to illustrate a generalization of the above to the
case of 2-dimensional configurations on $\mathbb{Z}^{2}$. More precisely, we
consider a particular subshift of $\llbracket 0,18\rrbracket^{\mathbb{Z}^{2}}$
for which we give three characterizations:

  * •

as the subshift $\mathcal{X}_{\phi}$ generated by the 2-dimensional morphism
$\phi$ defined on the alphabet $\mathcal{A}=\llbracket 0,18\rrbracket$ by the
rule

(1) $\begin{array}[]{ll}\phi:&\llbracket 0,18\rrbracket\to\llbracket
0,18\rrbracket^{*^{2}}\\\\[5.69054pt]
&\left\\{\footnotesize\begin{array}[]{llll}0\mapsto\left(17\right),&1\mapsto\left(16\right),&2\mapsto\left(15,\,11\right),&3\mapsto\left(13,\,9\right),\\\
4\mapsto\left(17,\,8\right),&5\mapsto\left(16,\,8\right),&6\mapsto\left(15,\,8\right),&7\mapsto\left(14,\,8\right),\\\
8\mapsto\left(\begin{array}[]{r}6\\\
14\end{array}\right),&9\mapsto\left(\begin{array}[]{r}3\\\
17\end{array}\right),&10\mapsto\left(\begin{array}[]{r}3\\\
16\end{array}\right),&11\mapsto\left(\begin{array}[]{r}2\\\
14\end{array}\right),\\\ 12\mapsto\left(\begin{array}[]{rr}7&1\\\
15&11\end{array}\right),&13\mapsto\left(\begin{array}[]{rr}6&1\\\
14&11\end{array}\right),&14\mapsto\left(\begin{array}[]{rr}7&1\\\
13&9\end{array}\right),&15\mapsto\left(\begin{array}[]{rr}6&1\\\
12&9\end{array}\right),\\\ 16\mapsto\left(\begin{array}[]{rr}5&1\\\
18&10\end{array}\right),&17\mapsto\left(\begin{array}[]{rr}4&1\\\
13&9\end{array}\right),&18\mapsto\left(\begin{array}[]{rr}2&0\\\
14&8\end{array}\right).\end{array}\right.\end{array}$

  * •

as the Wang shift $\Omega_{\mathcal{U}}$, that is, the set of valid
configuration $\mathbb{Z}^{2}\to\llbracket 0,18\rrbracket$ of the plane,
defined by the following set $\mathcal{U}$ of 19 Wang tiles:

  * •

as the symbolic dynamical system
$\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}}$ representing the
orbits under the $\mathbb{Z}^{2}$-action $R_{\mathcal{U}}$ defined by
rotations on $\mathbb{T}^{2}$ and coded by the topological partition
$\mathcal{P}_{\mathcal{U}}$ of $\mathbb{T}^{2}$:

$\begin{array}[]{c}\mathcal{P}_{\mathcal{U}}=\end{array}\begin{array}[]{c}\includegraphics{SageOutputs/partition-
PU.pdf}\end{array}\quad\begin{array}[]{l}R_{\mathcal{U}}^{\boldsymbol{n}}({\boldsymbol{x}})={\boldsymbol{x}}+\varphi^{-2}{\boldsymbol{n}}\end{array}$

The reader may observe that while increasing the dimension from 1 to 2, we
replaced the second characterization of the Fibonacci subshift
$\mathcal{X}_{s}$ based on the factor complexity by the notion of Wang shift
or more generally subshift of finite type (SFT). It may seem counter-intuitive
since the Fibonacci subshift is aperiodic and 1-dimensional SFT always contain
a periodic configuration [LM95], but this is not a contradiction in higher
dimension since there exist aperiodic 2-dimensional SFTs [Ber66].

We show that $\Omega_{\mathcal{U}}$ and
$\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}}$ are self-similar.
The tools used in the proofs are completely different in each case: based on
the notion of marker tiles in the former case and on Rauzy induction of
$\mathbb{Z}^{2}$-rotations in the latter. It turns out that the
$2$-dimensional morphism describing the self-similarities is $\phi$ in both
cases.

######  Theorem 1.1.

Let $\phi:\llbracket 0,18\rrbracket\to\llbracket 0,18\rrbracket^{*^{2}}$ be
defined in Equation (1). The following hold:

  1. (i)

The Wang shift $\Omega_{\mathcal{U}}\subset\llbracket
0,18\rrbracket^{\mathbb{Z}^{2}}$ is self-similar satisfying
$\Omega_{\mathcal{U}}=\overline{\phi(\Omega_{\mathcal{U}})}^{\sigma}$,

  2. (ii)

The subshift
$\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}}\subset\llbracket
0,18\rrbracket^{\mathbb{Z}^{2}}$ is self-similar satisfying
$\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}}=\overline{\phi(\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}})}^{\sigma}$.

The equality of the three subshifts follows as $\mathcal{X}_{\phi}$ is the
unique nonempty subshift $X\subset\llbracket 0,18\rrbracket^{\mathbb{Z}^{2}}$
such that $X=\overline{\phi(X)}^{\sigma}$ (see Exercise 3.3).

######  Corollary 1.2.

The three subshifts are equal:
$\mathcal{X}_{\phi}=\Omega_{\mathcal{U}}=\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}}$.

The 2-dimensional subshift $\Omega_{\mathcal{U}}$ was introduced in [Lab19]
and discovered during the study of the substitutive structure [Lab21c] of the
Jeandel-Rao Wang shift [JR15]. Its description as the coding of a toral
$\mathbb{Z}^{2}$-action was presented in [Lab21a] and its substitutive
structure was further developed in [Lab21b]. This chapter provides a
transversal reading of results divided in four different articles and gathers
the methods introduced by focussing on the self-similar subshift hidden in the
Jeandel-Rao Wang shift. Thus we avoid the difficulty raised by the Jeandel-Rao
Wang shift itself which is not a minimal subshift, has a long preperiod in its
substitutive description and needs the definition of other tools including the
shear-conjugacy.

Structure of the chapter. Section 2 gathers preliminary notions on topological
dynamical systems, subshifts and shifts of finite type and $d$-dimensional
languages. In Section 3, we define a $2$-dimensional self-similar subshift
$\mathcal{X}_{\phi}$ from a $2$-dimensional substitution $\phi$ defined on
19-letter alphabet. We show that $\mathcal{X}_{\phi}$ is aperiodic. In Section
4, we introduce a Wang shift $\Omega_{\mathcal{U}}$ defined from a set
$\mathcal{U}$ of 19 Wang tiles and we show using the notion of marker tiles
that it is self-similar and $\Omega_{\mathcal{U}}=\mathcal{X}_{\phi}$. In
Section 5, we introduce a $2$-dimensional subshift defined as the symbolic
representation of a toral $\mathbb{Z}^{2}$-rotation using a partition of
$\mathbb{R}^{2}/\mathbb{Z}^{2}$ into 19 polygons. We show that it is also
self-similar and equal to $\mathcal{X}_{\phi}$.

Algorithms to find marker tiles and compute the Rauzy induction of
$\mathbb{Z}^{2}$-rotations are provided as well as the SageMath code to
reproduce the computations.

Acknowledgments. The author is thankful to Jana Lepšová for her careful
reading of a preliminary version of this chapter.

##  2\. Preliminaries

###  2.1. Topological dynamical systems

Most of the notions introduced here can be found in [Wal82]. A dynamical
system is a triple $(X,G,T)$, where $X$ is a topological space, $G$ is a
topological group and $T$ is a continuous function $G\times X\to X$ defining a
left action of $G$ on $X$: if $x\in X$, $e$ is the identity element of $G$ and
$g,h\in G$, then using additive notation for the operation in $G$ we have
$T(e,x)=x$ and $T(g+h,x)=T(g,T(h,x))$. In other words, if one denotes the
transformation $x\mapsto T(g,x)$ by $T^{g}$, then $T^{g+h}=T^{g}T^{h}$. In
this work, we consider the Abelian group $G=\mathbb{Z}\times\mathbb{Z}$.

If $Y\subset X$, let $\overline{Y}$ denote the topological closure of $Y$ and
let $T(Y):=\cup_{g\in G}T^{g}(Y)$ denote the $T$-closure of $Y$.
Alternatively, we also use the notation $\overline{Y}^{T}=T(Y)$ to denote the
$T$-closure of $Y$. A subset $Y\subset X$ is $T$-invariant if $T(Y)=Y$. A
dynamical system $(X,G,T)$ is called minimal if $X$ does not contain any
nonempty, proper, closed $T$-invariant subset. The left action of $G$ on $X$
is free if $g=e$ whenever there exists $x\in X$ such that $T^{g}(x)=x$.

Let $(X,G,T)$ and $(Y,G,S)$ be two dynamical systems with the same topological
group $G$. A homomorphism $\theta:(X,G,T)\to(Y,G,S)$ is a continuous function
$\theta:X\to Y$ satisfying the commuting property that
$S^{g}\circ\theta=\theta\circ T^{g}$ for every $g\in G$. A homomorphism
$\theta:(X,G,T)\to(Y,G,S)$ is called an embedding if it is one-to-one, a
factor map if it is onto, and a topological conjugacy if it is both one-to-one
and onto and its inverse map is continuous. If $\theta:(X,G,T)\to(Y,G,S)$ is a
factor map, then $(Y,G,S)$ is called a factor of $(X,G,T)$ and $(X,G,T)$ is
called an extension of $(Y,G,S)$. Two dynamical systems are topologically
conjugate if there is a topological conjugacy between them.

A measure-preserving dynamical system is defined as a system
$(X,G,T,\mu,\mathcal{B})$, where $\mu$ is a probability measure defined on the
Borel $\sigma$-algebra $\mathcal{B}$ of subsets of $X$, and $T^{g}:X\to X$ is
a measurable map which preserves the measure $\mu$ for all $g\in G$, that is,
$\mu(T^{g}(B))=\mu(B)$ for all $B\in\mathcal{B}$. The measure $\mu$ is said to
be $T$-invariant. In what follows, when it is clear from the context, we omit
the Borel $\sigma$-algebra $\mathcal{B}$ of subsets of $X$ and write
$(X,G,T,\mu)$ to denote a measure-preserving dynamical system.

The set of all $T$-invariant probability measures of a dynamical system
$(X,G,T)$ is denoted by $\mathcal{M}^{T}(X)$. A $T$-invariant probability
measure on $X$ is called ergodic if for every set $B\in\mathcal{B}$ such that
$T^{g}(B)=B$ for all $g\in G$, we have that $B$ has either zero or full
measure. A dynamical system $(X,G,T)$ is uniquely ergodic if it has only one
invariant probability measure, i.e., $|\mathcal{M}^{T}(X)|=1$. One can prove
that a uniquely ergodic dynamical system is ergodic. A dynamical system
$(X,G,T)$ is said strictly ergodic if it is uniquely ergodic and minimal.

Let $(X,G,T,\mu,\mathcal{B})$ and
$(X^{\prime},G,T^{\prime},\mu^{\prime},\mathcal{B}^{\prime})$ be two measure-
preserving dynamical systems. We say that the two systems are isomorphic if
there exist measurable sets $X_{0}\subset X$ and $X^{\prime}_{0}\subset
X^{\prime}$ of full measure (i.e., $\mu(X\setminus X_{0})=0$ and
$\mu^{\prime}(X^{\prime}\setminus X^{\prime}_{0})=0$) with
$T^{g}(X_{0})\subset X_{0}$, $T^{\prime g}(X^{\prime}_{0})\subset
X^{\prime}_{0}$ for all $g\in G$ and there exists a map $\phi:X_{0}\to
X^{\prime}_{0}$, called an isomorphism, that is one-to-one and onto and such
that for all $A\in\mathcal{B}^{\prime}(X^{\prime}_{0})$,

  * •

$\phi^{-1}(A)\in\mathcal{B}(X_{0})$,

  * •

$\mu(\phi^{-1}(A))=\mu^{\prime}(A)$, and

  * •

$\phi\circ T^{g}(x)=T^{\prime g}\circ\phi(x)$ for all $x\in X_{0}$ and $g\in
G$.

The role of the set $X_{0}$ is to make precise the fact that the properties of
the isomorphism need to hold only on a set of full measure.

###  2.2. Subshifts and shifts of finite type

In this section, we introduce multidimensional subshifts, a particular type of
dynamical systems [LM95, §13.10], [Sch01, Lin04, Hoc16]. Let $\mathcal{A}$ be
a finite set, $d\geq 1$, and let $\mathcal{A}^{\mathbb{Z}^{d}}$ be the set of
all maps $x:\mathbb{Z}^{d}\to\mathcal{A}$, equipped with the compact product
topology. An element $x\in\mathcal{A}^{\mathbb{Z}^{d}}$ is called
configuration and we write it as
$x=(x_{\boldsymbol{m}})=(x_{\boldsymbol{m}}:{\boldsymbol{m}}\in\mathbb{Z}^{d})$,
where $x_{\boldsymbol{m}}\in\mathcal{A}$ denotes the value of $x$ at
${\boldsymbol{m}}$. The topology on $\mathcal{A}^{\mathbb{Z}^{d}}$ is
compatible with the metric defined for all configurations
$x,x^{\prime}\in\mathcal{A}^{\mathbb{Z}^{d}}$ by
$\mathrm{dist}(x,x^{\prime})=2^{-\min\left\\{\|{\boldsymbol{n}}\|\,:\,x_{\boldsymbol{n}}\neq
x^{\prime}_{\boldsymbol{n}}\right\\}}$ where
$\|{\boldsymbol{n}}\|=|n_{1}|+\dots+|n_{d}|$. The shift action
$\sigma:{\boldsymbol{n}}\mapsto\sigma^{\boldsymbol{n}}$ of the additive group
$\mathbb{Z}^{d}$ on $\mathcal{A}^{\mathbb{Z}^{d}}$ is defined by

(2)
$(\sigma^{\boldsymbol{n}}(x))_{\boldsymbol{m}}=x_{{\boldsymbol{m}}+{\boldsymbol{n}}}$

for every $x=(x_{\boldsymbol{m}})\in\mathcal{A}^{\mathbb{Z}^{d}}$ and
${\boldsymbol{n}}\in\mathbb{Z}^{d}$. If
$X\subset\mathcal{A}^{\mathbb{Z}^{d}}$, let $\overline{X}$ denote the
topological closure of $X$ and let
$\overline{X}^{\sigma}:=\\{\sigma^{\boldsymbol{n}}(x)\mid x\in
X,{\boldsymbol{n}}\in\mathbb{Z}^{d}\\}$ denote the shift-closure of $X$. A
subset $X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ is shift-invariant if
$\overline{X}^{\sigma}=X$. A closed, shift-invariant subset
$X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ is a subshift. If
$X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ is a subshift we write
$\sigma=\sigma^{X}$ for the restriction of the shift action (2) to $X$. When
$X$ is a subshift, the triple $(X,\mathbb{Z}^{d},\sigma)$ is a dynamical
system and the notions presented in the previous section hold.

A configuration $x\in X$ is periodic if there is a nonzero vector
${\boldsymbol{n}}\in\mathbb{Z}^{d}\setminus\\{{\boldsymbol{0}}\\}$ such that
$x=\sigma^{\boldsymbol{n}}(x)$ and otherwise it is nonperiodic. We say that a
nonempty subshift $X$ is aperiodic if the shift action $\sigma$ on $X$ is
free.

For any subset $S\subset\mathbb{Z}^{d}$ let
$\pi_{S}:\mathcal{A}^{\mathbb{Z}^{d}}\to\mathcal{A}^{S}$ denote the projection
map which restricts every $x\in\mathcal{A}^{\mathbb{Z}^{d}}$ to $S$. A pattern
is a function $p\in\mathcal{A}^{S}$ for some finite subset
$S\subset\mathbb{Z}^{d}$. To every pattern $p\in\mathcal{A}^{S}$ corresponds a
subset $\pi_{S}^{-1}(p)\subset\mathcal{A}^{\mathbb{Z}^{d}}$ called cylinder. A
nonempty set $X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ is a subshift if and only
if there exists a set $\mathcal{F}$ of forbidden patterns such that

(3)
$X=\\{x\in\mathcal{A}^{\mathbb{Z}^{d}}\mid\pi_{S}\circ\sigma^{\boldsymbol{n}}(x)\notin\mathcal{F}\text{
for every }{\boldsymbol{n}}\in\mathbb{Z}^{d}\text{ and
}S\subset\mathbb{Z}^{d}\\},$

see [Hoc16, Prop. 9.2.4]. A subshift $X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ is
a subshift of finite type (SFT) if there exists a finite set $\mathcal{F}$
such that (3) holds. In this article, we consider shifts of finite type on
$\mathbb{Z}\times\mathbb{Z}$, that is, the case $d=2$.

###  2.3. $d$-dimensional word

In this section, we recall the definition of $d$-dimensional word that
appeared in [CKR10] and we keep the notation $u\odot^{i}v$ they proposed for
the concatenation.

We denote by $\\{{\boldsymbol{e}}_{k}|1\leq k\leq d\\}$ the canonical basis of
$\mathbb{Z}^{d}$ where $d\geq 1$ is an integer. If $i\leq j$ are integers,
then $\llbracket i,j\rrbracket$ denotes the interval of integers
$\\{i,i+1,\dots,j\\}$. Let
${\boldsymbol{n}}=(n_{1},\dots,n_{d})\in\mathbb{N}^{d}$ and $\mathcal{A}$ be
an alphabet. We denote by $\mathcal{A}^{{\boldsymbol{n}}}$ the set of
functions

$u:\llbracket 0,n_{1}-1\rrbracket\times\cdots\times\llbracket
0,n_{d}-1\rrbracket\to\mathcal{A}.$

An element $u\in\mathcal{A}^{\boldsymbol{n}}$ is called a $d$-dimensional word
of shape ${\boldsymbol{n}}=(n_{1},\dots,n_{d})\in\mathbb{N}^{d}$ on the
alphabet $\mathcal{A}$. We use the notation
$\textsc{shape}(u)={\boldsymbol{n}}$ when necessary. The set of all finite
$d$-dimensional words is
$\mathcal{A}^{*^{d}}=\\{\mathcal{A}^{\boldsymbol{n}}\mid{\boldsymbol{n}}\in\mathbb{N}^{d}\\}$.
A $d$-dimensional word of shape
${\boldsymbol{e}}_{k}+\sum_{i=1}^{d}{\boldsymbol{e}}_{i}$ is called a domino
in the direction ${\boldsymbol{e}}_{k}$. When the context is clear, we write
$\mathcal{A}$ instead of $\mathcal{A}^{(1,\dots,1)}$. When $d=2$, we represent
a $d$-dimensional word $u$ of shape $(n_{1},n_{2})$ as a matrix with Cartesian
coordinates:

$u=\left(\begin{array}[]{ccc}u_{0,n_{2}-1}&\dots&u_{n_{1}-1,n_{2}-1}\\\
\dots&\dots&\dots\\\ u_{0,0}&\dots&u_{n_{1}-1,0}\end{array}\right).$

Let ${\boldsymbol{n}},{\boldsymbol{m}}\in\mathbb{N}^{d}$ and
$u\in\mathcal{A}^{\boldsymbol{n}}$ and $v\in\mathcal{A}^{\boldsymbol{m}}$. If
there exists an index $i$ such that $n_{j}=m_{j}$ for all
$j\in\\{1,\dots,d\\}\setminus\\{i\\}$, then the concatenation of $u$ and $v$
in the direction ${\boldsymbol{e}}_{i}$ is defined: it is the $d$-dimensional
word $u\odot^{i}v$ of shape
$(n_{1},\dots,n_{i-1},n_{i}+m_{i},n_{i+1},\dots,n_{d})\in\mathbb{N}^{d}$ given
as

$(u\odot^{i}v)({\boldsymbol{a}})=\begin{cases}u({\boldsymbol{a}})&\text{if}\quad
0\leq a_{i}<n_{i},\\\
v({\boldsymbol{a}}-n_{i}{\boldsymbol{e}}_{i})&\text{if}\quad n_{i}\leq
a_{i}<n_{i}+m_{i}.\end{cases}$

The following equation illustrates the concatenation of $2$-dimensional words
in the direction ${\boldsymbol{e}}_{2}$:

$\left(\begin{array}[]{ccccc}4&5\\\
10&5\end{array}\right)\odot^{2}\left(\begin{array}[]{ccccc}3&10\\\ 9&9\\\
0&0\\\ \end{array}\right)=\left(\begin{array}[]{ccccc}3&10\\\ 9&9\\\ 0&0\\\
4&5\\\ 10&5\end{array}\right)$

whereas

$\left(\begin{array}[]{ccccc}3&10\\\ 9&9\\\ 0&0\\\
\end{array}\right)\odot^{2}\left(\begin{array}[]{ccccc}4&5\\\
10&5\end{array}\right)=\left(\begin{array}[]{ccccc}4&5\\\ 10&5\\\ 3&10\\\
9&9\\\ 0&0\end{array}\right)$

and in the direction ${\boldsymbol{e}}_{1}$:

$\left(\begin{array}[]{ccccc}2&8&7\\\ 7&3&9\\\ 1&1&0\\\ 6&6&7\\\
7&4&3\end{array}\right)\odot^{1}\left(\begin{array}[]{ccccc}3&10\\\ 9&9\\\
0&0\\\ 4&5\\\ 10&5\end{array}\right)=\left(\begin{array}[]{ccccc}2&8&7&3&10\\\
7&3&9&9&9\\\ 1&1&0&0&0\\\ 6&6&7&4&5\\\ 7&4&3&10&5\end{array}\right).$

Let ${\boldsymbol{n}},{\boldsymbol{m}}\in\mathbb{N}^{d}$ and
$u\in\mathcal{A}^{\boldsymbol{n}}$ and $v\in\mathcal{A}^{\boldsymbol{m}}$. We
say that $u$ occurs in $v$ at position ${\boldsymbol{p}}\in\mathbb{N}^{d}$ if
$v$ is large enough, i.e.,
${\boldsymbol{m}}-{\boldsymbol{p}}-{\boldsymbol{n}}\in\mathbb{N}^{d}$ and

$v({\boldsymbol{a}}+{\boldsymbol{p}})=u({\boldsymbol{a}})$

for all ${\boldsymbol{a}}=(a_{1},\dots,a_{d})\in\mathbb{N}^{d}$ such that
$0\leq a_{i}<n_{i}$ with $1\leq i\leq d$. If $u$ occurs in $v$ at some
position, then we say that $u$ is a $d$-dimensional subword or factor of $v$.

###  2.4. $d$-dimensional language

A subset $L\subseteq\mathcal{A}^{*^{d}}$ is called a $d$-dimensional language.
The factorial closure of a language $L$ is

$\overline{L}^{Fact}=\\{u\in\mathcal{A}^{*^{d}}\mid u\text{ is a
$d$-dimensional subword of some }v\in L\\}.$

A language $L$ is factorial if $\overline{L}^{Fact}=L$. All languages
considered in this contribution are factorial. Given a configuration
$x\in\mathcal{A}^{\mathbb{Z}^{d}}$, the language $\mathcal{L}(x)$ defined by
$x$ is

$\mathcal{L}(x)=\\{u\in\mathcal{A}^{*^{d}}\mid u\text{ is a $d$-dimensional
subword of }x\\}.$

The language of a subshift $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ is
$\mathcal{L}_{X}=\cup_{x\in X}\mathcal{L}(x)$. Conversely, given a factorial
language $L\subseteq\mathcal{A}^{*^{d}}$ we define the subshift

$\mathcal{X}_{L}=\\{x\in\mathcal{A}^{\mathbb{Z}^{d}}\mid\mathcal{L}(x)\subseteq
L\\}.$

A $d$-dimensional subword $u\in\mathcal{A}^{*^{d}}$ is allowed in a subshift
$X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ if $u\in\mathcal{L}_{X}$ and it is
forbidden in $X$ if $u\notin\mathcal{L}_{X}$. A language
$L\subseteq\mathcal{A}^{*^{d}}$ is forbidden in a subshift
$X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ if $L\cap\mathcal{L}_{X}=\varnothing$.

Exercise 2.1 Let $x:\mathbb{Z}^{d}\to\\{0,1\\}$ be the configuration defined
by $x({\boldsymbol{n}})=\|{\boldsymbol{n}}\|_{1}\bmod 2\quad\text{ for every
}{\boldsymbol{n}}\in\mathbb{Z}^{d}.$ Describe $\mathcal{L}(x)$. How many
elements are in the subshift $\mathcal{X}_{\mathcal{L}(x)}$?

###  2.5. $d$-dimensional morphisms

In this section, we generalize the definition of $d$-dimensional morphisms
[CKR10] to the case where the domain and codomain are different as in the case
of $S$-adic systems [BD14].

Let $\mathcal{A}$ and $\mathcal{B}$ be two alphabets. Let
$L\subseteq\mathcal{A}^{*^{d}}$ be a factorial language. A function
$\omega:L\to\mathcal{B}^{*^{d}}$ is a $d$-dimensional morphism if for every
$i$ with $1\leq i\leq d$, and every $u,v\in L$ such that $u\odot^{i}v$ is
defined and $u\odot^{i}v\in L$, we have that the concatenation
$\omega(u)\odot^{i}\omega(v)$ in direction ${\boldsymbol{e}}_{i}$ is defined
and

$\omega(u\odot^{i}v)=\omega(u)\odot^{i}\omega(v).$

Note that the left-hand side of the equation is defined since $u\odot^{i}v$
belongs to the domain of $\omega$. A $d$-dimensional morphism
$L\to\mathcal{B}^{*^{d}}$ is thus completely defined from the image of the
letters in $\mathcal{A}$, so we sometimes denote a $d$-dimensional morphism as
a rule $\mathcal{A}\to\mathcal{B}^{*^{d}}$ when the language $L$ is
unspecified.

The next lemma can be deduced from the definition. It says that when $d\geq 2$
every $d$-dimensional morphism defined on the whole set
$L=\mathcal{A}^{*^{d}}$ is uniform. We say that a $d$-dimensional morphism
$\omega:L\to\mathcal{B}^{*^{d}}$ is uniform if there exists a shape
${\boldsymbol{n}}\in\mathbb{N}^{d}$ such that
$\omega(a)\in\mathcal{B}^{\boldsymbol{n}}$ for every letter $a\in\mathcal{A}$.
These are called block-substitutions in [Fra18].

######  Lemma 2.1.

If $d\geq 2$, every $d$-dimensional morphism
$\omega:\mathcal{A}^{*^{d}}\to\mathcal{B}^{*^{d}}$ is uniform.

Therefore, to consider non-uniform $d$-dimensional morphisms when $d\geq 2$,
we need to restrict the domain to a strict subset
$L\subsetneq\mathcal{A}^{*^{d}}$. In [CKR10] and [Moz89, p.144], they consider
the case $\mathcal{A}=\mathcal{B}$ and they restrict the domain of
$d$-dimensional morphisms to the language they generate.

Given a language $L\subseteq\mathcal{A}^{*^{d}}$ of $d$-dimensional words and
a $d$-dimensional morphism $\omega:L\to\mathcal{B}^{*^{d}}$, we define the
image of the language $L$ under $\omega$ as the language

$\overline{\omega(L)}^{Fact}=\\{u\in\mathcal{B}^{*^{d}}\mid u\text{ is a
$d$-dimensional subword of }\omega(v)\text{ with }v\in
L\\}\subseteq\mathcal{B}^{*^{d}}.$

Observe that some element of $\overline{\omega(L)}^{Fact}$ do not have a
preimage under $\omega$.

Let $L\subseteq\mathcal{A}^{*^{d}}$ be a factorial language and
$\mathcal{X}_{L}\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ be the subshift
generated by $L$. A $d$-dimensional morphism $\omega:L\to\mathcal{B}^{*^{d}}$
can be extended to a continuous map
$\omega:\mathcal{X}_{L}\to\mathcal{B}^{\mathbb{Z}^{d}}$ in such a way that the
origin of $\omega(x)$ is at zero position in the word
$\omega(x_{\boldsymbol{0}})$ for all $x\in\mathcal{X}_{L}$. More precisely,
the image under $\omega$ of the configuration $x\in\mathcal{X}_{L}$ is

$\omega(x)=\lim_{n\to\infty}\sigma^{f(n)}\omega\left(\sigma^{-n{\boldsymbol{1}}}(x|_{\llbracket-n{\boldsymbol{1}},n{\boldsymbol{1}}\llbracket})\right)\in\mathcal{B}^{\mathbb{Z}^{d}}$

where ${\boldsymbol{1}}=(1,\dots,1)\in\mathbb{Z}^{d}$,
$f(n)=\textsc{shape}\left(\omega(\sigma^{-n{\boldsymbol{1}}}(x|_{\llbracket-n{\boldsymbol{1}},{\boldsymbol{0}}\llbracket}))\right)$
for all $n\in\mathbb{N}$ and
$\llbracket{\boldsymbol{m}},{\boldsymbol{n}}\llbracket={\llbracket
m_{1},n_{1}-1\rrbracket}\times\cdots\times{\llbracket
m_{d},n_{d}-1\rrbracket}$.

In general, the closure under the shift of the image of a subshift
$X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ under $\omega$ is the subshift

$\overline{\omega(X)}^{\sigma}=\\{\sigma^{\boldsymbol{k}}\omega(x)\in\mathcal{B}^{\mathbb{Z}^{d}}\mid{\boldsymbol{k}}\in\mathbb{Z}^{d},x\in
X\\}\subseteq\mathcal{B}^{\mathbb{Z}^{d}}.$

Now we show that $d$-dimensional morphisms preserve minimality of subshifts.

######  Lemma 2.2.

Let $\omega:X\to\mathcal{B}^{\mathbb{Z}^{d}}$ be a $d$-dimensional morphism
for some $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$. If $X$ is a minimal
subshift, then $\overline{\omega(X)}^{\sigma}$ is a minimal subshift.

###### Proof.

Let $\varnothing\neq Z\subseteq\overline{\omega(X)}^{\sigma}$ be a closed
shift-invariant subset. We want to show that
$\overline{\omega(X)}^{\sigma}\subseteq Z$. Let
$u\in\overline{\omega(X)}^{\sigma}$. Thus $u=\sigma^{\boldsymbol{k}}\omega(x)$
for some ${\boldsymbol{k}}\in\mathbb{Z}^{d}$ and $x\in X$. Since
$Z\neq\varnothing$, there exists $z\in Z$. Thus
$z=\sigma^{{\boldsymbol{k}}^{\prime}}\omega(x^{\prime})$ for some
${\boldsymbol{k}}^{\prime}\in\mathbb{Z}^{d}$ and $x^{\prime}\in X$. Since $X$
is minimal, there exists a sequence $({\boldsymbol{k}}_{n})_{n\in\mathbb{N}}$,
${\boldsymbol{k}}_{n}\in\mathbb{Z}^{d}$, such that
$x=\lim_{n\to\infty}\sigma^{{\boldsymbol{k}}_{n}}x^{\prime}$. For some other
sequence $({\boldsymbol{h}}_{n})_{n\in\mathbb{N}}$,
${\boldsymbol{h}}_{n}\in\mathbb{Z}^{d}$, we have

$u=\sigma^{\boldsymbol{k}}\omega(x)=\sigma^{\boldsymbol{k}}\omega\left(\lim_{n\to\infty}\sigma^{{\boldsymbol{k}}_{n}}x^{\prime}\right)=\sigma^{\boldsymbol{k}}\lim_{n\to\infty}\sigma^{{\boldsymbol{h}}_{n}}\omega\left(x^{\prime}\right)=\lim_{n\to\infty}\sigma^{{\boldsymbol{k}}+{\boldsymbol{h}}_{n}-{\boldsymbol{k}}^{\prime}}z.$

Since $Z$ is closed and shift-invariant, it follows that $u\in Z$. ∎

Exercise 2.2 We consider the $2$-dimensional morphism $\phi$ defined in
Equation (1) on the alphabet $\mathcal{A}=\llbracket 0,18\rrbracket$. Compute
$\phi(u)$ for each 2-dimensional word $u$ below $\left(\begin{array}[]{c}13\\\
\end{array}\right),\quad\left(16,\,8\right),\quad\left(\begin{array}[]{c}6\\\
11\\\ \end{array}\right),\quad\left(\begin{array}[]{cc}7&1\\\
13&9\end{array}\right)$ except one for which the image $\phi(u)$ is not well-
defined.

Exercise 2.3 Let $\omega:X\to\mathcal{B}^{\mathbb{Z}^{d}}$ be a
$d$-dimensional morphism for some $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$.
Prove that if $X$ is a subshift, then $\overline{\omega(X)}^{\sigma}$ is a
subshift.

##  3\. Aperiodic self-similar subshifts

###  3.1. Self-similar subshifts

In this section, we consider languages and subshifts defined from morphisms
leading to self-similar structures. In this situation, the domain and codomain
of morphisms are defined over the same alphabet. Formally, we consider the
case of $d$-dimensional morphisms $\mathcal{A}\to\mathcal{B}^{*^{d}}$ where
$\mathcal{A}=\mathcal{B}$.

The definition of self-similarity depends on the notion of expansiveness. It
avoids the presence of lower-dimensional self-similar structure by having
expansion in all directions.

######  Definition 3.1.

We say that a $d$-dimensional morphism
$\omega:\mathcal{A}\to\mathcal{A}^{*^{d}}$ is expansive if for every
$a\in\mathcal{A}$ and $K\in\mathbb{N}$, there exists $m\in\mathbb{N}$ such
that

$\min(\textsc{shape}(\omega^{m}(a)))>K.$

######  Definition 3.2.

A subshift $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ is self-similar if there
exists an expansive $d$-dimensional morphism
$\omega:\mathcal{A}\to\mathcal{A}^{*^{d}}$ such that
$X=\overline{\omega(X)}^{\sigma}$.

Respectively, a language $L\subseteq\mathcal{A}^{*^{d}}$ is self-similar if
there exists an expansive $d$-dimensional morphism
$\omega:\mathcal{A}\to\mathcal{A}^{*^{d}}$ such that
$L=\overline{\omega(L)}^{Fact}$.

Self-similar languages and subshifts can be constructed by iterative
application of a morphism $\omega$ starting with the letters. The language
$\mathcal{L}_{\omega}$ defined by an expansive $d$-dimensional morphism
$\omega:\mathcal{A}\to\mathcal{A}^{*^{d}}$ is

$\mathcal{L}_{\omega}=\\{u\in\mathcal{A}^{*^{d}}\mid u\text{ is a
$d$-dimensional subword of }\omega^{n}(a)\text{ for some
}a\in\mathcal{A}\text{ and }n\in\mathbb{N}\\}.$

It satisfies
$\mathcal{L}_{\omega}=\overline{\omega(\mathcal{L}_{\omega})}^{Fact}$ and thus
is self-similar. The substitutive shift
$\mathcal{X}_{\omega}=\mathcal{X}_{\mathcal{L}_{\omega}}$ defined from the
language of $\omega$ is a self-similar subshift since
$\mathcal{X}_{\omega}=\overline{\omega(\mathcal{X}_{\omega})}^{\sigma}$ holds.

Figure 1.  Building a configuration of the positive quadrant with $\phi$. We
compute $(\phi^{n}(14))_{n\in\mathbb{N}}$ for the first values of
$n\in\\{0,1,2,3,4,5,6\\}$. The gray rectangles surround patterns seen two step
before in the application of $\phi$. The limit
$\lim_{n\to\infty}\phi^{2n}(14)$ defines a configuration of the positive
quadrant $\mathbb{N}^{2}$ and similarly for the limit
$\lim_{n\to\infty}\phi^{2n+1}(14)$. Figure 2. Building a configuration of
$\mathbb{Z}^{2}$ with $\phi$. We compute
$(\phi^{n}\leavevmode\hbox{\set@color$\left(\begin{smallmatrix}9&14\\\
1&6\end{smallmatrix}\right)$})_{n\in\mathbb{N}}$ for the first values of
$n\in\\{0,1,2,3,4,5\\}$. The gray rectangles surround patterns seen two step
before in the application of $\phi$. The limit
$\lim_{n\to\infty}\phi^{2n}\leavevmode\hbox{\set@color$\left(\begin{smallmatrix}9&14\\\
1&6\end{smallmatrix}\right)$}$ defines a configuration of $\mathbb{Z}^{2}$ and
similarly for the limit
$\lim_{n\to\infty}\phi^{2n+1}\leavevmode\hbox{\set@color$\left(\begin{smallmatrix}9&14\\\
1&6\end{smallmatrix}\right)$}$.

Let $\phi:\llbracket 0,18\rrbracket\to\llbracket 0,18\rrbracket^{*^{2}}$ be
the $2$-dimensional morphism defined in Exercise 2.5. At Figure 1, we compute
the sequence of $2$-dimensional words $(\phi^{n}(14))_{n\in\mathbb{N}}$ for
the first values of $n$. Since 14 appears in the lower left corner of
$\phi^{2}(14)$, the limit $\lim_{n\to\infty}\phi^{2n}(14)$ is well-defined and
it defines a configuration of the positive quadrant $\mathbb{N}^{2}$.

This procedure can be done in each of the four quadrants. At Figure 2, we
compute the sequence of $2$-dimensional words
$(\phi^{n}\left(\begin{smallmatrix}9&14\\\
1&6\end{smallmatrix}\right))_{n\in\mathbb{N}}$ for the first values of $n$.
The limits

$\displaystyle x$
$\displaystyle=\lim_{n\to\infty}\phi^{2n}\left(\begin{smallmatrix}9&14\\\
1&6\end{smallmatrix}\right)$ $\displaystyle y$
$\displaystyle=\lim_{n\to\infty}\phi^{2n+1}\left(\begin{smallmatrix}9&14\\\
1&6\end{smallmatrix}\right)$

are well-defined and define two configurations of $\mathbb{Z}^{2}$. They
satisfy $\phi(x)=y$ and $\phi(y)=x$. This implies that the configurations $x$
and $y$ are fixed points of $\phi^{2}$ since $\phi^{2}(x)=x$ and
$\phi^{2}(y)=y$.

Exercise 3.1 Prove that $\phi$ defined in Exercise 2.5 is expansive.

Exercise 3.2 Prove that $\mathcal{X}_{\phi}\neq\varnothing$.

Exercise 3.3 Reproduce the computations of the Figure 1 and Figure 2 in
SageMath using the slabbe package. Note that $2$-dimensional words are encoded
using Cartesian-like coordinates instead of matrix-like coordinates.` `

Exercise 3.4 The language of horizontal and vertical dominoes that we see in
Figure 1 and Figure 2 obtained from the morphism $\phi$ are
$H=\left\\{\begin{array}[]{l}\left(\begin{smallmatrix}0&3\end{smallmatrix}\right),\left(\begin{smallmatrix}1&2\end{smallmatrix}\right),\left(\begin{smallmatrix}1&3\end{smallmatrix}\right),\left(\begin{smallmatrix}1&6\end{smallmatrix}\right),\left(\begin{smallmatrix}2&0\end{smallmatrix}\right),\left(\begin{smallmatrix}2&4\end{smallmatrix}\right),\left(\begin{smallmatrix}3&7\end{smallmatrix}\right),\left(\begin{smallmatrix}4&1\end{smallmatrix}\right),\left(\begin{smallmatrix}5&1\end{smallmatrix}\right),\\\
\left(\begin{smallmatrix}6&1\end{smallmatrix}\right),\left(\begin{smallmatrix}6&5\end{smallmatrix}\right),\left(\begin{smallmatrix}7&1\end{smallmatrix}\right),\left(\begin{smallmatrix}8&16\end{smallmatrix}\right),\left(\begin{smallmatrix}9&14\end{smallmatrix}\right),\left(\begin{smallmatrix}10&12\end{smallmatrix}\right),\left(\begin{smallmatrix}10&14\end{smallmatrix}\right),\left(\begin{smallmatrix}11&17\end{smallmatrix}\right),\\\
\left(\begin{smallmatrix}12&9\end{smallmatrix}\right),\left(\begin{smallmatrix}13&9\end{smallmatrix}\right),\left(\begin{smallmatrix}14&8\end{smallmatrix}\right),\left(\begin{smallmatrix}14&11\end{smallmatrix}\right),\left(\begin{smallmatrix}14&13\end{smallmatrix}\right),\left(\begin{smallmatrix}14&18\end{smallmatrix}\right),\left(\begin{smallmatrix}15&8\end{smallmatrix}\right),\\\
\left(\begin{smallmatrix}15&11\end{smallmatrix}\right),\left(\begin{smallmatrix}16&8\end{smallmatrix}\right),\left(\begin{smallmatrix}16&13\end{smallmatrix}\right),\left(\begin{smallmatrix}16&15\end{smallmatrix}\right),\left(\begin{smallmatrix}17&8\end{smallmatrix}\right),\left(\begin{smallmatrix}17&13\end{smallmatrix}\right),\left(\begin{smallmatrix}18&10\end{smallmatrix}\right)\end{array}\right\\}$
and $V=\left\\{\begin{array}[]{l}\left(\begin{smallmatrix}8\\\
0\end{smallmatrix}\right),\left(\begin{smallmatrix}8\\\
1\end{smallmatrix}\right),\left(\begin{smallmatrix}9\\\
1\end{smallmatrix}\right),\left(\begin{smallmatrix}11\\\
1\end{smallmatrix}\right),\left(\begin{smallmatrix}16\\\
2\end{smallmatrix}\right),\left(\begin{smallmatrix}16\\\
3\end{smallmatrix}\right),\left(\begin{smallmatrix}13\\\
4\end{smallmatrix}\right),\left(\begin{smallmatrix}13\\\
5\end{smallmatrix}\right),\left(\begin{smallmatrix}14\\\
6\end{smallmatrix}\right),\left(\begin{smallmatrix}17\\\
6\end{smallmatrix}\right),\\\ \left(\begin{smallmatrix}15\\\
7\end{smallmatrix}\right),\left(\begin{smallmatrix}0\\\
8\end{smallmatrix}\right),\left(\begin{smallmatrix}9\\\
8\end{smallmatrix}\right),\left(\begin{smallmatrix}11\\\
8\end{smallmatrix}\right),\left(\begin{smallmatrix}1\\\
9\end{smallmatrix}\right),\left(\begin{smallmatrix}10\\\
9\end{smallmatrix}\right),\left(\begin{smallmatrix}1\\\
10\end{smallmatrix}\right),\left(\begin{smallmatrix}1\\\
11\end{smallmatrix}\right),\left(\begin{smallmatrix}10\\\
11\end{smallmatrix}\right),\left(\begin{smallmatrix}6\\\
12\end{smallmatrix}\right),\\\ \left(\begin{smallmatrix}4\\\
13\end{smallmatrix}\right),\left(\begin{smallmatrix}7\\\
13\end{smallmatrix}\right),\left(\begin{smallmatrix}18\\\
13\end{smallmatrix}\right),\left(\begin{smallmatrix}2\\\
14\end{smallmatrix}\right),\left(\begin{smallmatrix}6\\\
14\end{smallmatrix}\right),\left(\begin{smallmatrix}12\\\
14\end{smallmatrix}\right),\left(\begin{smallmatrix}7\\\
15\end{smallmatrix}\right),\left(\begin{smallmatrix}13\\\
15\end{smallmatrix}\right),\left(\begin{smallmatrix}18\\\
15\end{smallmatrix}\right),\\\ \left(\begin{smallmatrix}3\\\
16\end{smallmatrix}\right),\left(\begin{smallmatrix}14\\\
16\end{smallmatrix}\right),\left(\begin{smallmatrix}17\\\
16\end{smallmatrix}\right),\left(\begin{smallmatrix}3\\\
17\end{smallmatrix}\right),\left(\begin{smallmatrix}14\\\
17\end{smallmatrix}\right),\left(\begin{smallmatrix}5\\\
18\end{smallmatrix}\right)\end{array}\right\\}$ Prove that $H$ and $V$ are
exactly the dominoes that appear in $\mathcal{L}_{\phi}$, that is,
$(\mathcal{A}\odot^{1}\mathcal{A})\cap\mathcal{L}_{\phi}=H\text{ and
}(\mathcal{A}\odot^{2}\mathcal{A})\cap\mathcal{L}_{\phi}=V$ where
$\mathcal{A}=\llbracket 0,18\rrbracket$ is the alphabet on which the morphism
$\phi$ is defined.

Exercise 3.5 Is the $2\times 2$ word $\left(\begin{smallmatrix}1&2\\\
10&14\end{smallmatrix}\right)$ in the set $\mathcal{L}_{\phi}$?

Exercise 3.6 List the 50 elements of the set
$\mathcal{A}^{(2,2)}\cap\mathcal{L}_{\phi}$.

Exercise 3.7 Describe the 8 periodic points of $\phi$, i.e. the configurations
$x\in\mathcal{A}^{\mathbb{Z}^{2}}$ such that $\phi^{k}(x)=x$ for some $k\geq
1$.

###  3.2. $d$-dimensional recognizability

The definition of recognizability dates back to the work of Host, Quéffelec
and Mossé [Mos92]. The definition introduced below is based on work of Berthé
et al. [BSTY19] on the recognizability in the case of $S$-adic systems where
more than one substitution is involved.

######  Definition 3.3 (recognizable).

Let $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ and
$\omega:X\to\mathcal{B}^{\mathbb{Z}^{d}}$ be a $d$-dimensional morphism. If
$y\in\overline{\omega(X)}^{\sigma}$, i.e.,
$y=\sigma^{\boldsymbol{k}}\omega(x)$ for some $x\in X$ and
${\boldsymbol{k}}\in\mathbb{Z}^{d}$, where $\sigma$ is the $d$-dimensional
shift map, we say that $({\boldsymbol{k}},x)$ is an $\omega$-representation of
$y$. We say that it is centered if $y_{\boldsymbol{0}}$ lies inside of the
image of $x_{\boldsymbol{0}}$, i.e., if
${\boldsymbol{0}}\leq{\boldsymbol{k}}<\textsc{shape}(\omega(x_{\boldsymbol{0}}))$
coordinate-wise. We say that $\omega$ is recognizable in
$X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ if each
$y\in\mathcal{B}^{\mathbb{Z}^{d}}$ has at most one centered
$\omega$-representation $({\boldsymbol{k}},x)$ with $x\in X$.

######  Lemma 3.4.

Let $\omega:X\to Y$ be some $d$-dimensional morphism between two subshifts $X$
and $Y$.

  1. (1)

If $Y$ is aperiodic, then $X$ is aperiodic.

  2. (2)

If $X$ is aperiodic and $\omega$ is recognizable in $X$, then
$\overline{\omega(X)}^{\sigma}$ is aperiodic.

###### Proof.

If $X$ contains a periodic configuration $x$, then $\omega(x)\in Y$ is
periodic.

(ii) Let $y\in\overline{\omega(X)}^{\sigma}$. Then, there exist
${\boldsymbol{k}}\in\mathbb{Z}^{d}$ and $x\in X$ such that
$({\boldsymbol{k}},x)$ is a centered $\omega$-representation of $y$, i.e.,
$y=\sigma^{\boldsymbol{k}}\omega(x)$. Suppose by contradiction that $y$ has a
nontrivial period
${\boldsymbol{p}}\in\mathbb{Z}^{d}\setminus{\boldsymbol{0}}$. Since
$y=\sigma^{\boldsymbol{p}}y=\sigma^{{\boldsymbol{p}}+{\boldsymbol{k}}}\omega(x)$,
we have that $({\boldsymbol{p}}+{\boldsymbol{k}},x)$ is an
$\omega$-representation of $y$. Since $\omega$ is recognizable, this
representation is not centered. Therefore there exists
${\boldsymbol{q}}\in\mathbb{Z}^{d}\setminus{\boldsymbol{0}}$ such that
$y_{\boldsymbol{0}}$ lies in the image of
$x_{\boldsymbol{q}}=(\sigma^{\boldsymbol{q}}x)_{\boldsymbol{0}}$. Therefore
there exists ${\boldsymbol{k}}^{\prime}\in\mathbb{Z}^{d}$ such that
$({\boldsymbol{k}}^{\prime},\sigma^{\boldsymbol{q}}x)$ is a centered
$\omega$-representation of $y$. Since $\omega$ is recognizable, we conclude
that ${\boldsymbol{k}}={\boldsymbol{k}}^{\prime}$ and
$x=\sigma^{\boldsymbol{q}}x$. Then $x\in X$ is periodic which is a
contradiction. ∎

In general, $\omega(X)$ is not closed under the shift which implies that
$\omega$ is not onto $Y$. This motivates the following definition.

######  Definition 3.5.

Let $X$, $Y$ be two subshifts and $\omega:X\to Y$ be a $d$-dimensional
morphism. If $Y=\overline{\omega(X)}^{\sigma}$, then we say that $\omega$ is
onto up to a shift.

Exercise 3.8 Let $\phi:\llbracket 0,18\rrbracket\to\llbracket
0,18\rrbracket^{*^{2}}$ be the morphism defined in Exercise 2.5. Find periodic
configurations $x,y\in\llbracket 0,18\rrbracket^{\mathbb{Z}^{2}}$ and
${\boldsymbol{k}}\in\mathbb{Z}^{2}$ such that • $({\boldsymbol{k}},x)$ is a
$\phi$-representation of $y$, • $({\boldsymbol{k}},x)$ is a centered
$\phi$-representation of $y$, • $({\boldsymbol{k}},x)$ is a
$\phi$-representation of $y$ which is not centered.

Exercise 3.9 Does there exist a configuration $y\in\llbracket
0,18\rrbracket^{\mathbb{Z}^{2}}$ that has more than one centered
$\phi$-representation $({\boldsymbol{k}},x)$ with $x\in\llbracket
0,18\rrbracket^{\mathbb{Z}^{2}}$?

###  3.3. Aperiodicity, primitivity and minimality of self-similar subshifts

The next proposition is well-known, see [Sol98, Mos92], who showed that
recognizability and aperiodicity are equivalent for primitive substitutive
sequences. We state and prove only one direction (the easy one) of the
equivalence which does not need the notion of primitivity.

######  Proposition 3.6.

Let $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ be a self-similar subshift
satisfying $\overline{\omega(X)}^{\sigma}=X$ for some expansive
$d$-dimensional morphism $\omega:\mathcal{A}\to\mathcal{A}^{\mathbb{Z}^{d}}$.
If $\omega$ is recognizable in $X$, then $X$ is aperiodic.

###### Proof.

Suppose that there exists a periodic configuration $y\in X$ with period
${\boldsymbol{p}}\in\mathbb{Z}^{d}\setminus\\{(0,0)\\}$ satisfying
$\sigma^{\boldsymbol{p}}y=y$. Since $\omega$ is expansive, let
$m\in\mathbb{N}$ such that the shape of the image of every letter
$a\in\mathcal{A}$ by $\omega^{m}$ is large enough, that is,
$\textsc{shape}(\omega^{m}(a))>{\boldsymbol{p}}$ for every letter
$a\in\mathcal{A}$. By hypothesis, every $y\in X$ has an
$\omega$-representation. Recursively, there exists an
$\omega^{m}$-representation $({\boldsymbol{k}},x)$ of $y$ satisfying
$y=\sigma^{\boldsymbol{k}}\omega^{m}(x)$. We may assume that it is centered
since $X$ is shift-invariant. By definition of centered representation, for
every ${\boldsymbol{u}}\in\mathbb{Z}^{d}$ such that
${\boldsymbol{0}}\leq{\boldsymbol{u}}<\textsc{shape}(\omega^{m}(x_{\boldsymbol{0}}))$,
$({\boldsymbol{u}},x)$ is a centered $\omega^{m}$-representation of
$\sigma^{\boldsymbol{u}}\omega^{m}(x)=\sigma^{{\boldsymbol{u}}-{\boldsymbol{k}}}y$.
By the choice of $m$, there exists ${\boldsymbol{u}}\in\mathbb{Z}^{d}$ such
that
${\boldsymbol{0}}\leq{\boldsymbol{u}}<\textsc{shape}(\omega^{m}(x_{\boldsymbol{0}}))$
and
${\boldsymbol{0}}\leq{\boldsymbol{u}}+{\boldsymbol{p}}<\textsc{shape}(\omega^{m}(x_{\boldsymbol{0}}))$.
Therefore $({\boldsymbol{u}},x)$ is a centered $\omega^{m}$-representation of
$\sigma^{\boldsymbol{u}}\omega^{m}(x)=\sigma^{{\boldsymbol{u}}-{\boldsymbol{k}}}y$
and $({\boldsymbol{u}}+{\boldsymbol{p}},x)$ is a centered
$\omega^{m}$-representation of
$\sigma^{{\boldsymbol{u}}+{\boldsymbol{p}}}\omega^{m}(x)=\sigma^{{\boldsymbol{u}}+{\boldsymbol{p}}-{\boldsymbol{k}}}y=\sigma^{{\boldsymbol{u}}-{\boldsymbol{k}}}\sigma^{\boldsymbol{p}}y=\sigma^{{\boldsymbol{u}}-{\boldsymbol{k}}}y$.
Therefore, $\omega^{m}$ is not recognizable which implies that $\omega$ is not
recognizable which is a contradiction. We conclude that there is no periodic
configuration $y\in X$. ∎

Substitutive shifts obtained from expansive and primitive morphisms are
interesting for their properties. As in the one-dimensional case, we say that
$\omega$ is primitive if there exists $m\in\mathbb{N}$ such that for every
$a,b\in\mathcal{A}$ the letter $b$ occurs in $\omega^{m}(a)$.

######  Lemma 3.7.

Let $\omega:\mathcal{A}\to\mathcal{A}^{*^{d}}$ be an expansive and primitive
$d$-dimensional morphism. Then $\mathcal{X}_{\omega}$ is minimal, i.e., it
contains no nonempty proper subshift.

###### Proof.

The substitutive shift of $\omega$ is well-defined since $\omega$ is expansive
and it is minimal since $\omega$ is primitive using standard arguments [Que10,
§5.2]. ∎

######  Lemma 3.8.

Let $\omega:\mathcal{A}\to\mathcal{A}^{*^{d}}$ be an expansive and primitive
$d$-dimensional morphism. Let $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ be a
nonempty subshift such that $X=\overline{\omega(X)}^{\sigma}$. Then
$\mathcal{X}_{\omega}\subseteq X$.

###### Proof.

The language of $X$ is also self-similar satisfying
$\mathcal{L}(X)=\overline{\omega(\mathcal{L}(X))}^{Fact}$. Recursively,
$\mathcal{L}(X)=\overline{\omega^{m}(\mathcal{L}(X))}^{Fact}$ for every $m\geq
1$. Thus there exists a letter $a\in\mathcal{A}$ such that for all $m\geq 1$,
the $d$-dimensional word $\omega^{m}(a)$ is in the language $\mathcal{L}(X)$.
From the primitivity of $\omega$, there exists $m\geq 1$ such that
$\omega^{m}(a)$ contains an occurrence of every letter of the alphabet
$\mathcal{A}$. Therefore every letter is in $\mathcal{L}(X)$ and the
$d$-dimensional word $\omega^{m}(a)$ is in the language $\mathcal{L}(X)$ for
all letters $a\in\mathcal{A}$ and all $m\geq 1$. So we conclude that
$\mathcal{L}_{\omega}\subseteq\mathcal{L}(X)$ and
$\mathcal{X}_{\omega}\subseteq X$. ∎

Recall that
$\mathcal{X}_{\omega}=\overline{\omega(\mathcal{X}_{\omega})}^{\sigma}$. Thus
from Lemma 3.7 and Lemma 3.8, when $\omega$ is expansive and primitive, then
$\mathcal{X}_{\omega}$ is the smallest nonempty subshift
$X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ satisfying
$X=\overline{\omega(X)}^{\sigma}$. The next result provides sufficient
conditions for the unicity of the subshift $X$ satisfying
$X=\overline{\omega(X)}^{\sigma}$.

Let $G_{\omega}=(V,E)$ be the directed graph whose vertices are
$V=\mathcal{A}^{(2,\dots,2)}$ and whose edges are $\\{(u,v)\in V\times V\mid
v\text{ is a factor of }\omega(u)\\}$. Let $\textsc{seeds}(\omega)\subset V$
be the set of vertices that belong to a cycle of $G_{\omega}$.

######  Lemma 3.9.

Let $\omega:\mathcal{A}\to\mathcal{A}^{*^{d}}$ be an expansive and primitive
$d$-dimensional morphism. If
$\textsc{seeds}(\omega)\subset\mathcal{L}_{\omega}$, then
$\mathcal{X}_{\omega}$ is the unique nonempty subshift such that
$X=\overline{\omega(X)}^{\sigma}$.

###### Proof.

Assume that $X=\overline{\omega(X)}^{\sigma}$ for some $\varnothing\neq
X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$. From Lemma 3.8, we have
$\mathcal{X}_{\omega}\subseteq X$.

Let $z\in\mathcal{L}(X)$. Since $\omega$ is expansive, let $m\in\mathbb{N}$
such that the image of every letter $a\in\mathcal{A}$ by $\omega^{m}$ is
larger than $z$, that is, $\textsc{shape}(\omega^{m}(a))\geq\textsc{shape}(z)$
for all $a\in\mathcal{A}$. We have
$z\in\mathcal{L}(X)=\mathcal{L}\left(\omega^{m}(\mathcal{L}(X))\right)$. By
the choice of $m$, $z$ can not overlap more than two blocks $\omega^{m}(a)$ in
the same direction. Then, there exists a word $u\in\mathcal{L}(X)$ of shape
$(2,\dots,2)$ such that $z$ is a subword of $\omega^{m}(u)$. We have $u\in V$.
Since $u\in\mathcal{L}(X)$ and $X$ is self-similar, there exists a sequence
$(u_{k})_{k\in\mathbb{N}}$ with $u_{k}\in V$ for all $k\in\mathbb{N}$ such
that

$\cdots\rightarrow u_{k+1}\rightarrow u_{k}\rightarrow\cdots\rightarrow
u_{1}\rightarrow u_{0}=u$

is a left-infinite path in the graph $G_{\omega}$. Since $V$ is finite, there
exist some $k,k^{\prime}\in\mathbb{N}$ with $k<k^{\prime}$ such that
$u_{k}=u_{k^{\prime}}$. Thus $u_{k}\in\textsc{seeds}(\omega)$ and $u$ is a
subword of $\omega^{k}(u_{k})$. From the hypothesis, we have
$\textsc{seeds}(\omega)\subset\mathcal{L}_{\omega}$ so that
$u_{k}\in\mathcal{L}_{\omega}$. Since $\omega$ is primitive, there exists
$\ell$ such that $u_{k}$ is a subword of $\omega^{\ell}(a)$ for every
$a\in\mathcal{A}$. Therefore, $z$ is a subword of $\omega^{m+k+\ell}(a)$ for
every $a\in\mathcal{A}$. Then $z\in\mathcal{L}_{\omega}$ and
$\mathcal{L}(X)\subseteq\mathcal{L}_{\omega}$. Thus
$X\subseteq\mathcal{X}_{\omega}$. ∎

Exercise 3.10 Let $\phi:\llbracket 0,18\rrbracket\to\llbracket
0,18\rrbracket^{*^{2}}$ be the morphism defined in Exercise 2.5. (1) Prove
that $\phi$ is recognizable in $\mathcal{X}_{\phi}$. (2) Prove that
$\mathcal{X}_{\phi}$ is aperiodic. (3) Prove that $\phi$ is primitive. (4)
Prove that $\mathcal{X}_{\phi}$ is minimal.

Exercise 3.11 Prove that there exists a unique nonempty subshift
$X\subset\llbracket 0,18\rrbracket^{*^{2}}$ such that
$X=\overline{\phi(X)}^{\sigma}$. Conclude that $X=\mathcal{X}_{\phi}$.

###  3.4. Markers

The goal of this section is to prove Theorem 3.13 which says that we can
desubstitute a subshift provided that its alphabet contains a subset of
markers. Markers are such that they appear on non-consecutive layers in the
configurations of the subshift, see Definition 3.10. The results are stated
for arbitrary dimension since their proofs are independent of the dimension,
but we will use them in the 2-dimensional case afterwards.

We now define the notion of markers for subshifts
$X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ and prove that their presence allows to
desubstitute uniquely the configurations in $X$ using a $d$-dimensional
morphism. Originally, those results were proved for $d=2$ in order to
desubstitute configurations from Wang shifts, see [Lab19] and [Lab21c]. It
turns out that the notion of markers is more general and the results holds in
general subshifts $X\subset\mathcal{A}^{\mathbb{Z}^{d}}$.

Recall that if $w:\mathbb{Z}^{d}\to\mathcal{A}$ is a configuration and
$a\in\mathcal{A}$ is a letter, then $w^{-1}(a)\subset\mathbb{Z}^{d}$ is the
set of positions where the letter $a$ appears in $w$.

######  Definition 3.10.

Let $\mathcal{A}$ be an alphabet and $X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ be
a subshift. A nonempty subset $M\subset\mathcal{A}$ is called markers in the
direction ${\boldsymbol{e}}_{i}$, with $i\in\\{1,\dots,d\\}$, if positions of
the letters of $M$ in any configuration are nonadjacent $(d-1)$-dimensional
layers orthogonal to ${\boldsymbol{e}}_{i}$, that is, for all configurations
$w\in X$ there exists $P\subset\mathbb{Z}$ such that the positions of the
markers satisfy

$w^{-1}(M)=P{\boldsymbol{e}}_{i}+\sum_{k\neq
i}\mathbb{Z}{\boldsymbol{e}}_{k}\quad\text{ with }\quad 1\notin P-P$

where $P-P=\\{b-a\mid a\in P,b\in P\\}$ is the set of differences between
elements of $P$.

Note that it follows from the definition that a subset of markers is a proper
subset of $\mathcal{A}$ as the case $M=\mathcal{A}$ is impossible.

Proving that a subset $M\subset\mathcal{A}$ is a subset of markers uses very
local observations, namely the set of dominoes in the language of the
subshift. It leads to the following criterion.

######  Lemma 3.11.

Let $\mathcal{A}$ be an alphabet and $X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ be
a subshift. A nonempty subset $M\subset\mathcal{A}$ is a subset of markers in
the direction ${\boldsymbol{e}}_{i}$ if and only if

$M\odot^{i}M,\qquad M\odot^{k}(\mathcal{A}\setminus
M),\qquad(\mathcal{A}\setminus M)\odot^{k}M$

are forbidden in $X$ for every $k\in\\{1,\dots,d\\}\setminus\\{i\\}$.

###### Proof.

Suppose that $M\subset\mathcal{A}$ is a subset of markers in the direction
${\boldsymbol{e}}_{i}$. For any configuration $w\in X$, there exists
$P\subset\mathbb{Z}$ such that $w^{-1}(M)=P{\boldsymbol{e}}_{i}+\sum_{k\neq
i}\mathbb{Z}{\boldsymbol{e}}_{k}$ with $1\notin P-P$. In any configuration
$w\in X$ such that $w(p)\in M$, then $w(p\pm{\boldsymbol{e}}_{k})\in M$ also
belongs to $M$ for every $k\neq i$. Therefore,
$M\odot^{k}(\mathcal{A}\setminus M)$ and $(\mathcal{A}\setminus M)\odot^{k}M$
are forbidden in $X$ for every $k\neq i$. Moreover, the fact that $1\notin
P-P$ implies that $M\odot^{k}M$ is forbidden in $X$.

Conversely, suppose that $M\odot^{i}M$, $M\odot^{k}(\mathcal{A}\setminus M)$
and $(\mathcal{A}\setminus M)\odot^{k}M$ are forbidden in $X$ for every $k\neq
i$. The last two conditions implies that in any configuration $w\in X$ such
that $w(p)\in M$, then $w(p\pm{\boldsymbol{e}}_{k})\in M$ also belongs to $M$
for every $k\neq i$. Therefore letters in $M$ appears as complete layers in
$w$, that is, $w^{-1}(M)=P{\boldsymbol{e}}_{i}+\sum_{k\neq
i}\mathbb{Z}{\boldsymbol{e}}_{k}$ for some $P\subset\mathbb{Z}$. Since
$M\odot^{i}M$ is forbidden in $X$, it means that the layers are nonadjacent,
or equivalently, $1\notin P-P$. We conclude that $M$ is a subset of markers in
the direction ${\boldsymbol{e}}_{i}$. ∎

The existence of a subset of markers allows to desubstitute a subshift by
“merging” each marker to the letter on its right (or on its left). This
procedure creates substitution with a specific form sending a letter on a a
letter or a domino. In the next lemma, we provide a sufficient condition for
such substitutions to be recognizable.

######  Lemma 3.12.

Let $d\geq 1$ and $i$ such that $1\leq i\leq d$. Let
$\omega:\mathcal{B}\to\mathcal{A}^{\mathbb{Z}^{d}}$ be a $d$-dimensional
morphism such that the image of letters are letters or dominoes in the
direction ${\boldsymbol{e}}_{i}$. If $\omega|_{\mathcal{B}}$ is injective and
there exists a subset $M\subset\mathcal{A}$ such that

(4) $\omega(\mathcal{B})\subseteq(\mathcal{A}\setminus
M)\cup\left((\mathcal{A}\setminus M)\odot^{i}M\right),$

or

(5) $\omega(\mathcal{B})\subseteq(\mathcal{A}\setminus
M)\cup\left(M\odot^{i}(\mathcal{A}\setminus M)\right),$

then $\omega$ is recognizable in $\mathcal{B}^{\mathbb{Z}^{d}}$.

If $a\odot^{i}b$ is a domino in the direction ${\boldsymbol{e}}_{i}$, we say
that $a$ is on the left position and $b$ is on the right position in the
domino.

###### Proof.

Let $({\boldsymbol{k}},x)$ and $({\boldsymbol{k}}^{\prime},x^{\prime})$ be two
centered $\omega$-representations of $y\in\mathcal{A}^{\mathbb{Z}^{d}}$ with
${\boldsymbol{k}},{\boldsymbol{k}}^{\prime}\in\mathbb{Z}^{d}$ and
$x,x^{\prime}\in\mathcal{B}^{\mathbb{Z}^{d}}$. We want to show that they are
equal.

Since the image of a letter under $\omega$ is a letter or a domino in the
direction ${\boldsymbol{e}}_{i}$, then
${\boldsymbol{k}},{\boldsymbol{k}}^{\prime}\in\\{{\boldsymbol{0}},{\boldsymbol{e}}_{i}\\}$.
If $y_{\boldsymbol{0}}\in M$, then $y_{\boldsymbol{0}}$ appears as the left or
right part of a domino and thus
${\boldsymbol{k}}={\boldsymbol{k}}^{\prime}={\boldsymbol{e}}_{i}$ if Equation
(4) holds or ${\boldsymbol{k}}={\boldsymbol{k}}^{\prime}={\boldsymbol{0}}$ if
Equation (5) holds.

Suppose now that $y_{\boldsymbol{0}}\in\mathcal{A}\setminus M$. If Equation
(4) holds, then ${\boldsymbol{k}}={\boldsymbol{k}}^{\prime}={\boldsymbol{0}}$.
Suppose that Equation (5) holds. By contradiction, suppose that
${\boldsymbol{k}}\neq{\boldsymbol{k}}^{\prime}$ and assume without lost of
generality that ${\boldsymbol{k}}={\boldsymbol{0}}$ and
${\boldsymbol{k}}^{\prime}={\boldsymbol{e}}_{i}$. This means that
$\omega(x^{\prime}_{\boldsymbol{0}})=y_{-{\boldsymbol{e}}_{i}}\odot^{i}y_{\boldsymbol{0}}$
is a domino in the direction ${\boldsymbol{e}}_{i}$. Since
$y_{\boldsymbol{0}}\in\mathcal{A}\setminus M$, we must have that
$y_{-{\boldsymbol{e}}_{i}}\in M$ is a marker on the left. This is impossible
as
$\omega(x_{-{\boldsymbol{e}}_{i}})=y_{-{\boldsymbol{e}}_{i}}\in\mathcal{A}\setminus
M$ or
$\omega(x_{-{\boldsymbol{e}}_{i}})=y_{-2{\boldsymbol{e}}_{i}}\odot^{i}y_{-{\boldsymbol{e}}_{i}}\in
M\odot^{i}(\mathcal{A}\setminus M)$. Therefore, we must have
${\boldsymbol{k}}={\boldsymbol{k}}^{\prime}$ and
$\omega(x)=\omega(x^{\prime})$.

Suppose by contradiction that $x\neq x^{\prime}$. Let
${\boldsymbol{a}}=(a_{1},\dots,a_{d})\in\mathbb{Z}^{d}$ be some minimal vector
with respect to $\|{\boldsymbol{a}}\|_{\infty}$ such that
$x_{\boldsymbol{a}}\neq x^{\prime}_{\boldsymbol{a}}$. Injectivity of $\omega$
implies that $\omega(x_{\boldsymbol{a}})$ and
$\omega(x^{\prime}_{\boldsymbol{a}})$ must have different shapes. Suppose
without lost of generality that $\omega(x_{\boldsymbol{a}})\in\mathcal{A}$ and
$\omega(x^{\prime}_{\boldsymbol{a}})=b\odot^{i}c\in\mathcal{A}\odot^{i}\mathcal{A}$.
We need to consider two cases: $a_{i}\geq 0$ and $a_{i}<0$.

Suppose $a_{i}\geq 0$. We must have that Equation (4) holds. We have
$\omega(x_{\boldsymbol{a}})=b\in\mathcal{A}\setminus M$ and $c\in M$. But then
$\omega(x_{{\boldsymbol{a}}+{\boldsymbol{e}}_{i}})=c$ or
$\omega(x_{{\boldsymbol{a}}+{\boldsymbol{e}}_{i}})=c\odot^{i}d$ for some
$c\in\mathcal{A}\setminus M$ and $d\in\mathcal{A}$ which is a contradiction.

Suppose $a_{i}<0$. We must have that Equation (5) holds. We have
$\omega(x_{\boldsymbol{a}})=c\in\mathcal{A}\setminus M$ and $b\in M$. But then
$\omega(x_{{\boldsymbol{a}}-{\boldsymbol{e}}_{i}})=b$ or
$\omega(x_{{\boldsymbol{a}}+{\boldsymbol{e}}_{i}})=d\odot^{i}b$ for some
$b\in\mathcal{A}\setminus M$ and $d\in\mathcal{A}$ which is a contradiction.
We conclude that $x=x^{\prime}$. ∎

The presence of markers allows to desubstitute uniquely the configurations of
a subshift. There is even a choice to be made in the construction of the
substitution. We may construct the substitution in such a way that the markers
are on the left or on the right in the image of letters that are dominoes in
the direction ${\boldsymbol{e}}_{k}$. We make this distinction in the
statement of the following result which was stated in the context of Wang
shifts in [Lab19] and [Lab21c].

######  Theorem 3.13.

Let $\mathcal{A}$ be an alphabet and $X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ be
a subshift. If there exists a subset $M\subset\mathcal{A}$ of markers in the
direction
${\boldsymbol{e}}_{i}\in\\{{\boldsymbol{e}}_{1},\dots,{\boldsymbol{e}}_{d}\\}$,
then

  1. (i)

(markers on the right) there exists an alphabet $\mathcal{B}_{R}$, a subshift
$Y\subset\mathcal{B}_{R}^{\mathbb{Z}^{d}}$ and a $2$-dimensional morphism
$\omega_{R}:Y\to X$ such that

$\omega_{R}(\mathcal{B}_{R})\subseteq(\mathcal{A}\setminus
M)\cup\left((\mathcal{A}\setminus M)\odot^{i}M\right)$

which is recognizable and onto up to a shift and

  2. (ii)

(markers on the left) there exists an alphabet $\mathcal{B}_{L}$, a subshift
$Y\subset\mathcal{B}_{L}^{\mathbb{Z}^{d}}$ and a $2$-dimensional morphism
$\omega_{L}:Y\to X$ such that

$\omega_{L}(\mathcal{B}_{L})\subseteq(\mathcal{A}\setminus
M)\cup\left(M\odot^{i}(\mathcal{A}\setminus M)\right)$

which is recognizable and onto up to a shift.

###### Proof.

We do only the proof of (i) when the markers are on the right, since one case
can be deduced from the other using symmetry.

Since $X$ is a subshift, there exists a language $F\subset\mathcal{A}^{*^{d}}$
such that $X$ is the set of configurations of $\mathcal{A}^{\mathbb{Z}^{d}}$
without any occurrence of pattern from $F$. Notice that since $M$ is a set of
markers in the direction ${\boldsymbol{e}}_{i}$, we may assume
$M\odot^{i}M\subset F$. Let $P\subset\mathcal{A}\odot^{i}\mathcal{A}$ and
$Q\subset\mathcal{A}$ be the following sets:

$\displaystyle P$ $\displaystyle=\left((\mathcal{A}\setminus
M)\odot^{i}M\right)\setminus F,$ $\displaystyle Q$
$\displaystyle=\left\\{u\in\mathcal{A}\setminus M\,\middle|\,\text{ there
exists }v\in\mathcal{A}\setminus M\text{ such that }u\odot^{i}v\notin
F\right\\}.$

We choose some ordering of their elements with indices starting from zero:

$\displaystyle P$ $\displaystyle=\\{p_{0},\dots,p_{|P|-1}\\},$ $\displaystyle
Q$ $\displaystyle=\\{q_{0},\dots,q_{|Q|-1}\\}.$

We construct the alphabet $\mathcal{B}=\left\\{0,1,\dots,|Q|+|P|-1\right\\}$
and define the rule $\omega$ by

(6) $\begin{array}[]{rccl}\omega:&\mathcal{B}&\to&\mathcal{A}^{*^{d}}\\\
&j&\mapsto&\begin{cases}q_{j}&\text{ if }0\leq j<|Q|,\\\ p_{j-|Q|}&\text{ if
}|Q|\leq j<|Q|+|P|.\\\ \end{cases}\end{array}$

We want to show that $\omega$ extends to a map from a set of configurations to
$X$ which is onto up to a shift. Let $x\in X$ be a configuration which can be
seen as a function $x:\mathbb{Z}^{d}\to\mathcal{A}$. Consider the set
$x^{-1}(M)\subset\mathbb{Z}^{d}$ of positions of markers in $x$. From the
definition of markers in the direction ${\boldsymbol{e}}_{i}$, markers appear
in nonadjacent hyperplane orthogonal to ${\boldsymbol{e}}_{i}$ in the
configuration $x$. Formally, there exists a set $H\subset\mathbb{Z}$ such that
$x^{-1}(M)=\mathbb{Z}^{i-1}\times H\times\mathbb{Z}^{d-i}$ and $1\notin H-H$.
Since $1\notin H-H$, there exists a strictly increasing sequence
$(a_{k})_{k\in\mathbb{Z}}$ such that $\mathbb{Z}\setminus H=\\{a_{k}\mid
k\in\mathbb{Z}\\}$. We assume that $a_{0}=0$ if $0\in\mathbb{Z}\setminus H$
and $a_{0}=-1$ if $0\in H$ which makes the sequence $(a_{k})_{k\in\mathbb{Z}}$
uniquely defined.

In order to define the preimage of $x$ under $\omega$, it is convenient to
represent $x$ fiber by fiber. For every ${\boldsymbol{m}}\in\mathbb{Z}^{d-1}$,
let $x_{\boldsymbol{m}}:\mathbb{Z}\to\mathcal{A}$, be the sequence such that

$x(n_{1},\dots,n_{i-1},n_{i},n_{i+1},\dots,n_{d})=x_{(n_{1},\dots,n_{i-1},n_{i+1},\dots,n_{d})}(n_{i})$

for every
${\boldsymbol{n}}=(n_{1},\dots,n_{i-1},n_{i},n_{i+1},\dots,n_{d})\in\mathbb{Z}^{d}$.
For every ${\boldsymbol{m}}\in\mathbb{Z}^{d-1}$, let
$y_{\boldsymbol{m}}:\mathbb{Z}\to\mathcal{B}$ be defined as

$\begin{array}[]{rccl}y_{\boldsymbol{m}}:&\mathbb{Z}&\to&\mathcal{B}\\\
&k&\mapsto&\begin{cases}j&\text{ if }a_{k}+1\in H\text{ and
}x_{\boldsymbol{m}}(a_{k})=q_{j},\\\ j&\text{ if }a_{k}+1\notin H\text{ and
}x_{\boldsymbol{m}}(a_{k})\odot^{i}x_{\boldsymbol{m}}(a_{k}+1)=p_{j-|Q|},\end{cases}\end{array}$

The function $y_{\boldsymbol{m}}$ is well-defined. Indeed, let
$k\in\mathcal{A}$ and ${\boldsymbol{m}}\in\mathbb{Z}^{d-1}$. If $a_{k}+1\in
H$, then $x_{\boldsymbol{m}}(a_{k}+1)\in\mathcal{A}\setminus M$ and
$y_{\boldsymbol{m}}(k)=x_{\boldsymbol{m}}(a_{k})\in Q$. Also if $a_{k}+1\notin
H$, then $x_{\boldsymbol{m}}(a_{k})\in\mathcal{A}\setminus M$ and
$x_{\boldsymbol{m}}(a_{k}+1)\in M$. Since $x\in X$, then
$x_{\boldsymbol{m}}(a_{k})\odot^{i}x_{\boldsymbol{m}}(a_{k}+1)\notin F$ and
therefore $x_{\boldsymbol{m}}(a_{k})\odot^{i}x_{\boldsymbol{m}}(a_{k}+1)\in
P$. We define the configuration $y:\mathbb{Z}^{d}\to\mathcal{B}$ by its fibers
constructed above

$y(n_{1},\dots,n_{i-1},n_{i},n_{i+1},\dots,n_{d})=y_{(n_{1},\dots,n_{i-1},n_{i+1},\dots,n_{d})}(n_{i})$

for every
${\boldsymbol{n}}=(n_{1},\dots,n_{i-1},n_{i},n_{i+1},\dots,n_{d})\in\mathbb{Z}^{d}$.

We may now finish the proof of surjectivity. If $0\in H$, then the
configuration $x$ is exactly the image under $\omega$ of the configuration
$y\in\mathcal{B}^{\mathbb{Z}^{d}}$ that we constructed: $x=\omega(y)$. If
$0\notin H$, then the configuration $x$ is a shift of the image under $\omega$
of the configuration $y\in\mathcal{B}^{\mathbb{Z}^{d}}$:
$x=\sigma^{{\boldsymbol{e}}_{i}}\omega(y)$. Let

$Y=\omega^{-1}(X)=\\{y\in\mathcal{B}^{\mathbb{Z}^{d}}\mid\omega(y)\in X\\}$

making $\omega:Y\to X$ a continuous map which is onto up to a shift. Notice
that the subset $Y$ is closed since $\omega$ is continuous and $X$ is closed.
Moreover, $Y$ is shift-invariant since for all $y\in Y$ and
${\boldsymbol{n}}\in\mathbb{Z}^{d}$ there exists
${\boldsymbol{k}}\in\mathbb{Z}^{d}$ such that
$\omega(\sigma^{\boldsymbol{n}}(y))=\sigma^{\boldsymbol{k}}(\omega(y))$
meaning that $\sigma^{\boldsymbol{n}}(y)\in Y$. Thus $Y$ is a subshift.

The function $\omega$ is of the form

$\omega(\mathcal{B})\subseteq(\mathcal{A}\setminus
M)\cup\left((\mathcal{A}\setminus M)\odot^{i}M\right)$

and its restriction on $\mathcal{B}$ is injective by construction. Therefore,
we conclude from Lemma 3.12 that $\omega$ is recognizable in
$\mathcal{B}^{\mathbb{Z}^{d}}$. ∎

Remark that if $X$ is an effective subshift one may also show that $Y$ is an
effective subshift. Moreover if $X$ is a Wang shift, then $Y$ is a Wang shift
and the Wang tiles defining $Y$ can be obtained from the Wang tiles defining
$X$ together with some fusion operation. This is what was done in [Lab19] and
[Lab21c].

Exercise 3.12 Using the value of $H$ and $V$ from Exercise 3.1, prove that
$\\{0,1,2,3,4,5,6,7\\}$ is a subset of markers for the direction
${\boldsymbol{e}}_{2}$ in the subshift $\mathcal{X}_{\phi}$.

Exercise 3.13 Using the value of $H$ and $V$ from Exercise 3.1, prove that
$\left\\{0,1,8,9,10,11\right\\}$, $\left\\{2,3,6,12,14,16,17\right\\}$,
$\left\\{4,5,7,13,15,18\right\\}$ are subsets of markers for the direction
${\boldsymbol{e}}_{1}$ in the subshift $\mathcal{X}_{\phi}$.

Exercise 3.14 Using $M=\\{0,1,2,3,4,5,6,7\\}$ as subset of markers for the
direction ${\boldsymbol{e}}_{2}$, find an alphabet $\mathcal{B}$, a subshift
$Y\subset\mathcal{B}^{\mathbb{Z}^{2}}$ and a 2-dimensional morphism
$\alpha:\mathcal{B}\to\llbracket 0,18\rrbracket^{*^{2}}$ such that
$\alpha(\mathcal{B})\subseteq(\llbracket 0,18\rrbracket\setminus
M)\cup\left((\llbracket 0,18\rrbracket\setminus M)\odot^{2}M\right)$ which
extends to a recognizable continuous map $\alpha:Y\to\mathcal{X}_{\phi}$ which
is onto up to a shift.

Exercise 3.15 Use one of the subsets $M$ of markers for the direction
${\boldsymbol{e}}_{1}$ found in Exercise 3.4 to find an alphabet
$\mathcal{C}$, a subshift $Y^{\prime}\subset\mathcal{C}^{\mathbb{Z}^{2}}$ and
a 2-dimensional morphism $\xi:\mathcal{C}\to\llbracket 0,18\rrbracket^{*^{2}}$
such that $\xi(\mathcal{C})\subseteq(\llbracket 0,18\rrbracket\setminus
M)\cup\left((\llbracket 0,18\rrbracket\setminus M)\odot^{1}M\right)$ which
extends to a recognizable continuous map $\xi:Y^{\prime}\to\mathcal{X}_{\phi}$
which is onto up to a shift.

##  4\. Wang shifts

A Wang tile is a tuple of four colors $(a,b,c,d)\in I\times J\times I\times J$
where $I$ is a finite set of vertical colors and $J$ is a finite set of
horizontal colors, see [Wan61, Rob71]. A Wang tile is represented as a unit
square with colored edges:

$a$$b$$c$$d$

For each Wang tile $\tau=(a,b,c,d)$, let $\textsc{right}(\tau)=a$,
$\textsc{top}(\tau)=b$, $\textsc{left}(\tau)=c$, $\textsc{bottom}(\tau)=d$
denote respectively the colors of the right, top, left and bottom edges of
$\tau$.

Figure 3. The set $\mathcal{U}=\\{u_{0},\dots,u_{18}\\}$ of 19 Wang tiles
introduced in [Lab19]. Each tile is identified uniquely by an index from the
set $\\{0,1,\dots,18\\}$ written at the center each tile.

Let $\mathcal{T}=\\{t_{0},\dots,t_{m-1}\\}$ be a set of Wang tiles as the one
shown in Figure 3. A configuration $x:\mathbb{Z}^{2}\to\\{0,\dots,m-1\\}$ is
valid with respect to $\mathcal{T}$ if it assigns a tile in $\mathcal{T}$ to
each position of $\mathbb{Z}^{2}$ so that contiguous edges of adjacent tiles
have the same color, that is,

(7) $\displaystyle\textsc{right}(t_{x({\boldsymbol{n}})})$
$\displaystyle=\textsc{left}(t_{x({\boldsymbol{n}}+{\boldsymbol{e}}_{1})})$
(8) $\displaystyle\textsc{top}(t_{x({\boldsymbol{n}})})$
$\displaystyle=\textsc{bottom}(t_{x({\boldsymbol{n}}+{\boldsymbol{e}}_{2})})$

for every ${\boldsymbol{n}}\in\mathbb{Z}^{2}$ where
${\boldsymbol{e}}_{1}=(1,0)$ and ${\boldsymbol{e}}_{2}=(0,1)$. A finite
pattern which is valid with respect to $\mathcal{U}$ is shown in Figure 4.

Figure 4. The finite $5\times 5$ pattern on the left is valid with respect to
$\mathcal{U}$ since it respects Equations (7) and (8) which we can verify on
the tiling shown on the right.

Let $\Omega_{\mathcal{T}}\subset\\{0,\dots,m-1\\}^{\mathbb{Z}^{2}}$ denote the
set of all valid configurations with respect to $\mathcal{T}$, called the Wang
shift of $\mathcal{T}$. To a configuration $x\in\Omega_{\mathcal{T}}$
corresponds a tiling of the plane $\mathbb{R}^{2}$ by the tiles $\mathcal{T}$
where the unit square Wang tile $t_{x({\boldsymbol{n}})}$ is placed at
position ${\boldsymbol{n}}$ for every ${\boldsymbol{n}}\in\mathbb{Z}^{2}$, as
in Figure 4. Together with the shift action $\sigma$ of $\mathbb{Z}^{2}$,
$\Omega_{\mathcal{T}}$ is a SFT of the form (3) since there exists a finite
set of forbidden patterns made of all horizontal and vertical dominoes of two
tiles that do not share an edge of the same color. This definition of Wang
shifts allows to use the concepts of languages, $2$-dimensional morphisms,
recognizability introduced in the previous sections.

A configuration $x\in\Omega_{\mathcal{T}}$ is periodic if there exists
${\boldsymbol{n}}\in\mathbb{Z}^{2}\setminus\\{0\\}$ such that
$x=\sigma^{\boldsymbol{n}}(x)$. A set of Wang tiles $\mathcal{T}$ is periodic
if there exists a periodic configuration $x\in\Omega_{\mathcal{T}}$.
Originally, Wang thought that every set of Wang tiles $\mathcal{T}$ is
periodic as soon as $\Omega_{\mathcal{T}}$ is nonempty [Wan61]. This statement
is equivalent to the existence of an algorithm solving the _domino problem_ ,
that is, taking as input a set of Wang tiles and returning yes or no whether
there exists a valid configuration with these tiles. Berger, a student of
Wang, later proved that the domino problem is undecidable and he also provided
a first example of an aperiodic set of Wang tiles [Ber66]. A set of Wang tiles
$\mathcal{T}$ is aperiodic if the Wang shift $\Omega_{\mathcal{T}}$ is a
nonempty aperiodic subshift. This means that in general one can not decide the
emptiness of a Wang shift $\Omega_{\mathcal{T}}$. This illustrates that the
behavior of $d$-dimensional SFTs when $d\geq 2$ is much different than the
one-dimensional case where emptiness of a SFT is decidable [LM95]. Note that
another important difference between $d=1$ and $d\geq 2$ is expressed in terms
of the possible values of entropy of $d$-dimensional SFTs, see [HM10].

The goal of this section is to prove Theorem 1.1 (i), i.e., that the Wang
shift $\Omega_{\mathcal{U}}\subset\\{0,\dots,18\\}^{\mathbb{Z}^{2}}$ defined
by the set of Wang tiles $\mathcal{U}$ shown in Figure 3 is self-similar where
the self-similarity is given by the $2$-dimensional morphism $\phi$ defined in
Equation (1).

Exercise 4.1 Find a valid $7\times 7$ tiling with the set $\mathcal{U}$ of
Wang tiles.

###  4.1. Markers in the context of Wang tilings

A tiling with the tiles from the set $\mathcal{U}$ is shown in Figure 5. It
illustrates that there exists a subset $M\subset\mathcal{U}$ of tiles such
that each horizontal row of tiles in the tiling is using either tiles from $M$
or from $\mathcal{U}\setminus M$. Moreover, the horizontal lines using tiles
from $M$ are nonadjacent. If these conditions are satisfied for all
configurations in $\Omega_{\mathcal{U}}$, then $M$ is a subset of markers in
the direction ${\boldsymbol{e}}_{2}$.

Figure 5.  A $5\times 10$ tiling with tiles from the set $\mathcal{U}$. The
tiles labeled from 0 to 7 (shown with yellow background) are marker tiles for
the direction ${\boldsymbol{e}}_{2}$ in the Wang shift $\Omega_{\mathcal{U}}$
since they always appear on nonadjacent rows.

In this section we propose an algorithm to find and prove that a subset of
tiles is a subset of markers in a Wang shift. We use Lemma 3.11 which provides
a way to prove that a subset of Wang tiles is a subset of markers and
searching for them. To use it in the context of Wang shifts and more generally
in the context of SFTs, we need the following definition.

######  Definition 4.1 (surrounding of radius $r$).

Let $X=\textsc{SFT}(\mathcal{F})\subset\mathcal{A}^{\mathbb{Z}^{2}}$ be a
shift of finite type for some finite set $\mathcal{F}$ of forbidden patterns.
A $2$-dimensional word $u\in\mathcal{A}^{\boldsymbol{n}}$, with
${\boldsymbol{n}}=(n_{1},n_{2})\in\mathbb{N}^{2}$, admits a surrounding of
radius $r\in\mathbb{N}$ if there exists
$w\in\mathcal{A}^{{\boldsymbol{n}}+2(r,r)}$ such that $u$ occurs in $w$ at
position $(r,r)$ and $w$ contains no occurrences of forbidden patterns from
$\mathcal{F}$.

If a word admits a surrounding of radius $r\in\mathbb{N}$, it does not mean it
is in the language of the SFT. But if it admits no surrounding of radius $r$
for some $r\in\mathbb{N}$, then for sure it is not in the language of the SFT.
We state the following lemma in the context of Wang tiles.

######  Lemma 4.2.

Let $\mathcal{T}$ be a set of Wang tiles and
$u\in\mathcal{T}^{\boldsymbol{n}}$ be a rectangular pattern seen as a
$2$-dimensional word with ${\boldsymbol{n}}=(n_{1},n_{2})\in\mathbb{N}^{2}$.
If $u$ is allowed in $\Omega_{\mathcal{T}}$, then for every $r\in\mathbb{N}$
the word $u$ has a $\mathcal{T}$-surrounding of radius $r$.

Equivalently the lemma says that if there exists $r\in\mathbb{N}$ such that
$u$ has no $\mathcal{T}$-surrounding of radius $r$, then $u$ is forbidden in
$\Omega_{\mathcal{T}}$ and this is how we use Lemma 4.2 to find markers. We
propose Algorithm 1 to compute markers from a Wang tile set and a chosen
surrounding radius so that the computation terminates. If the algorithm finds
nothing, then maybe there are no markers or maybe one should try again after
increasing the surrounding radius. We prove in the next lemma that if the
output is nonempty, it contains a subset of markers.

Algorithm 1 Find markers. If no markers are found, one should try increasing
the radius $r$.

1:$\mathcal{T}$ is a set of Wang tiles; $i\in\\{1,2\\}$ is a direction
${\boldsymbol{e}}_{i}$; $r\in\mathbb{N}$ is some radius.

2:function FindMarkers($\mathcal{T}$, $i$, $r$)

3: $j\leftarrow 3-i$

4: $D_{j}\leftarrow\left\\{(u,v)\in\mathcal{T}^{2}\mid\text{ domino
}u\odot^{j}v\text{ admits a $\mathcal{T}$-surrounding of radius $r$}\right\\}$

5: $U\leftarrow\\{\\{u\\}\mid u\in\mathcal{T}\\}$ $\triangleright$ Suggestion:
use a union-find data structure

6: for all $(u,v)\in D_{j}$ do

7: Merge the sets containing $u$ and $v$ in the partition $U$.

8: $D_{i}\leftarrow\left\\{(u,v)\in\mathcal{T}^{2}\mid\text{ domino
}u\odot^{i}v\text{ admits a $\mathcal{T}$-surrounding of radius $r$}\right\\}$

9: return $\\{\text{set }M\text{ in the partition }U \mid\left(M\times
M\right)\cap D_{i}=\varnothing\\}$

10:The output contains zero, one or more subsets of markers in the direction
${\boldsymbol{e}}_{i}$.

######  Lemma 4.3.

If there exists $r\in\mathbb{N}$ and $i\in\\{1,2\\}$ such that the output of
$\textsc{FindMarkers}(\mathcal{T},i,r)$ contains a set $M$, then
$M\subset\mathcal{T}$ is a subset of markers in the direction
${\boldsymbol{e}}_{i}$.

###### Proof.

Suppose that $i=2$, the case $i=1$ being similar. The output set $M$ is
nonempty since it was created from the union of nonempty sets (see lines 4-6
in Algorithm 1). Using Lemma 4.2, lines 3 to 6 imply that
$M\odot^{1}(\mathcal{T}\setminus M)$ and $(\mathcal{T}\setminus M)\odot^{1}M$
are forbidden in $\Omega_{\mathcal{T}}$. The lines 7 and 8 imply that
$M\odot^{2}M$ is forbidden in $\Omega_{\mathcal{T}}$. Then we deduce from
Lemma 3.11 that $M\subset\mathcal{T}$ is a subset of markers in the direction
${\boldsymbol{e}}_{2}$. ∎

We believe that if a set of Wang tiles $\mathcal{T}$ has a subset of markers
in the direction ${\boldsymbol{e}}_{i}$ then there exists a surrounding radius
$r\in\mathbb{N}$ such that $\textsc{FindMarkers}(\mathcal{T},i,r)$ outputs
this set of markers, so that Lemma 4.3 is in fact a _if and only if_ but we do
not proivde a proof of that here. The fact that there is no upper bound for
the surrounding radius is related to the undecidability of the domino problem.
In practice, in the study of Jeandel-Rao tilings done in [Lab21c], a
surrounding radius of 1, 2 or 3 was enough.

Exercise 4.2 Using the set $\mathcal{U}$ of Wang tiles defined in Figure 3,
compute the sets of horizontal and vertical dominoes that admit a
$\mathcal{U}$-surrounding of radius 2: $\displaystyle D_{1}$
$\displaystyle=\left\\{(u,v)\in\mathcal{U}^{2}\mid u\odot^{1}v\text{ admits a
$\mathcal{U}$-surrounding of radius $2$}\right\\},$ $\displaystyle D_{2}$
$\displaystyle=\left\\{(u,v)\in\mathcal{U}^{2}\mid u\odot^{2}v\text{ admits a
$\mathcal{U}$-surrounding of radius $2$}\right\\}.$

Exercise 4.3 Use the function FindMarkers defined in Algorithm 1 with a
surrounding radius $2$ to show that the subset
$M=\left\\{\raisebox{-12.80373pt}{ \includegraphics{figures/markers-for-
Ucal.pdf} }\right\\}$ of $\mathcal{U}$ is a subset of markers for the
direction ${\boldsymbol{e}}_{2}$ in $\Omega_{\mathcal{U}}$.

###  4.2. Fusion of Wang tiles

Recall that a magma is a set $\mathcal{I}$ equipped with a binary operation
$\bullet$ such that for all $a,b\in\mathcal{I}$, the result of the operation
$a\bullet b$ is also in $\mathcal{I}$. If the operation $\bullet$ is
associative and has an identity, then $\mathcal{I}$ is a monoid and the
operation $\bullet$ can be omitted and represented as concatenation. But, in
the general context of fusion of Wang tiles defined below where $\mathcal{I}$
is the set of horizontal or vertical colors, we can not assume that the
operation $\bullet$ is associative.

The fusion operation on Wang tiles is defined on pair of tiles sharing an edge
in a tiling according to Equations 7 and 8. Let $(\mathcal{I},\bullet)$ and
$(\mathcal{J},\bullet)$ be two magmas and let
$\\{A,C,Y,W\\}\subset\mathcal{I}$ be some vertical colors and
$\\{B,D,X,Z\\}\subset\mathcal{J}$ be some horizontal colors. We define two
binary operations $\boxbar$ and $\boxminus$ on Wang tiles as

if $A=Y$

and

if $B=Z$.

If $A\neq Y$, the operation $\boxbar$ is not defined. Similarly, if $B\neq Z$,
the operation $\boxminus$ is not defined. For the Wang tiles considered in
this contribution, the operation $\bullet$ is associative so we always denote
it implicitly by concatenation of colors.

In what follows, we propose algorithms and results that works for both
operations $\boxbar$ and $\boxminus$. It is thus desirable to have a common
notation to denote both, so we define

$u\boxslash^{1}v=u\boxbar v\qquad\text{ and }\qquad u\boxslash^{2}v=u\boxminus
v.$

If $u\boxslash^{i}v$ is defined for some $i\in\\{1,2\\}$, it means that tiles
$u$ and $v$ can appear at position ${\boldsymbol{n}}$ and
${\boldsymbol{n}}+{\boldsymbol{e}}_{i}$ in a tiling for some
${\boldsymbol{n}}\in\mathbb{Z}^{d}$. For each $i\in\\{1,2\\}$, one can define
a new set of tiles from two sets $\mathcal{T}$ and $\mathcal{S}$ of Wang tiles
as

$\mathcal{T}\boxslash^{i}\mathcal{S}=\\{u\boxslash^{i}v\text{ defined }\mid
u\in\mathcal{T},v\in\mathcal{S}\\}.$

Exercise 4.4 Using the set $D_{2}$ of dominoes that admits a
$\mathcal{U}$-surrounding of radius $2$ computed in Exercise 4.1 and the
subset $M\subset\mathcal{U}$ of markers for the direction
${\boldsymbol{e}}_{2}$ in $\Omega_{\mathcal{U}}$ computed in Exercise 4.1,
compute the set of fusion tiles: $\\{u\boxminus v\mid(u,v)\in D_{2}\text{ and
}v\in M\\}.$ What is the meaning of this set?

###  4.3. Desubstitution of Wang shifts

In Theorem 3.13, we proved that the presence of markers allows to desubstitute
uniquely the configurations of a subshift on $\mathbb{Z}^{d}$. In case of Wang
shifts, we show in this section that the preimage is also a Wang shift and we
may construct the preimage set of Wang tiles using the fusion operation
defined in the previous section. We also propose an algorithm to find the
desubstitution of Wang shifts when there exists a subset of marker tiles.

Figure 6.  A $5\times 10$ tiling with tiles from the set $\mathcal{U}$ is
shown on the left. The tiles labeled from 0 to 6 (shown with yellow
background) are marker tiles for the direction ${\boldsymbol{e}}_{2}$ since
they appear on nonadjacent rows. It can be desubstituted as a $5\times 6$
pattern with tiles from the set $\mathcal{V}$ using a substitution
$\alpha_{0}$. Each marker tile (yellow background) is glued with its below
tile (green background) to form a new Wang tile (blue background) using the
fusion operation $\boxminus$. The remaining tiles are kept the same (green
background) but get new indices in the set $\mathcal{V}$. This process is
uniquely defined since the substitution $\alpha_{0}$ is recognizable.

Before stating the result, let us see how the markers allow to desubstitute
tilings. In Figure 6. we observe that markers $M$ computed in Exercise 4.1
appear as nonadjacent rows in the Wang shift $\Omega_{\mathcal{U}}$. Therefore
the row above (and below) a row of markers is made of nonmarker tiles. Let us
consider the row below. The idea is to collapse that row with the row of
markers just above. Each tile is being collapsed with the above marker tile
using the fusion of tiles. The set of tiles that we obtain through this
process is exactly the set computed in Exercise 4.2.

Therefore to build a configuration in $\Omega_{\mathcal{U}}$, it is sufficient
to build a tiling with another set $\mathcal{V}$ of Wang tiles obtained from
the set $\mathcal{U}$ after removing the markers and adding the tiles obtained
from the fusion operation. One may also remove the tile which always appear
below of a marker tile. One may recover some configuration in
$\Omega_{\mathcal{U}}$ by applying a $2$-dimensional morphism
$\alpha_{0}:\mathcal{V}\to\mathcal{U}^{*^{2}}$ which replaces the merged tiles
by their associated equivalent vertical dominoes and keeps the remaining tiles
invariant, see Figure 6. It turns out that this decomposition is unique. The
creation of the set $\mathcal{V}$ from $\mathcal{U}$ gives the intuition on
the construction of Algorithm 2 which follows the same recipe and takes any
set of Wang tiles with markers as input.

We now state the result that if a set of Wang tiles $\mathcal{T}$ has a subset
of marker tiles, then there exists another set $\mathcal{S}$ of Wang tiles and
a nontrivial recognizable $2$-dimensional morphism
$\Omega_{\mathcal{S}}\to\Omega_{\mathcal{T}}$ that is onto up to a shift.
Thus, every Wang tiling by $\mathcal{T}$ is up to a shift the image under a
nontrivial $2$-dimensional morphism $\omega$ of a unique Wang tiling in
$\Omega_{\mathcal{S}}$. The $2$-dimensional morphism is essentially
$1$-dimensional as we show in the next theorem.

######  Theorem 4.4.

[Lab19, Lab21c] Let $\mathcal{T}$ be a set of Wang tiles and let
$\Omega_{\mathcal{T}}$ be its Wang shift. If there exists a subset
$M\subset\mathcal{T}$ of markers in the direction ${\boldsymbol{e}}_{i}$ for
$i\in\\{1,2\\}$, then

  1. (1)

there exists a set of Wang tiles $\mathcal{S}_{R}$ and a $2$-dimensional
morphism $\omega_{R}:\Omega_{\mathcal{S}_{R}}\to\Omega_{\mathcal{T}}$ such
that

$\omega_{R}(\mathcal{S}_{R})\subseteq(\mathcal{T}\setminus
M)\cup\left((\mathcal{T}\setminus M)\odot^{i}M\right)$

which is recognizable and onto up to a shift and

  2. (2)

there exists a set of Wang tiles $\mathcal{S}_{L}$ and a $2$-dimensional
morphism $\omega_{L}:\Omega_{\mathcal{S}_{L}}\to\Omega_{\mathcal{T}}$ such
that

$\omega_{L}(\mathcal{S}_{L})\subseteq(\mathcal{T}\setminus
M)\cup\left(M\odot^{i}(\mathcal{T}\setminus M)\right)$

which recognizable and onto up to a shift.

There exists a surrounding radius $r\in\mathbb{N}$ such that $\omega_{R}$ and
$\omega_{L}$ are computed using Algorithm 2.

###### Proof.

The existence of the recognizable $2$-dimensional morphism which is onto up to
a shift was done in Theorem 3.13. We only need to prove that the preimage of
$\Omega_{\mathcal{T}}$ is a Wang shift. The proof of this fact can be found in
[Lab19] and [Lab21c]. It follows the line of Algorithm 2. ∎

Algorithm 2 Find a recognizable desubstitution of $\Omega_{\mathcal{T}}$ from
markers

1:$\mathcal{T}$ is a set of Wang tiles; $M\subset\mathcal{T}$ is a subset of
markers; $i\in\\{1,2\\}$ is a direction $e_{i}$; $r\in\mathbb{N}$ is a
surrounding radius; $s\in\\{\textsc{left},\textsc{right}\\}$ determines
whether the image of merged tiles is in $M\odot^{i}(\mathcal{T}\setminus M)$
(markers on the left) or in $(\mathcal{T}\setminus M)\odot^{i}M$ (markers on
the right).

2:function FindSubstitution($\mathcal{T}$, $M$, $i$, $r$, $s$)

3: $D\leftarrow\left\\{(u,v)\in\mathcal{T}^{2}\mid\text{ domino
}u\odot^{i}v\text{ admits a $\mathcal{T}$-surrounding of radius $r$}\right\\}$

4: if $s=\textsc{left}$ then

5: $P\leftarrow\left\\{(u,v)\in D\mid u\in M\text{ and
}v\in\mathcal{T}\setminus M\right\\}$

6: $K\leftarrow\left\\{v\in\mathcal{T}\setminus M\mid\text{ there exists
}u\in\mathcal{T}\setminus M\text{ such that }(u,v)\in D\right\\}$

7: else if $s=\textsc{right}$ then

8: $P\leftarrow\left\\{(u,v)\in D\mid u\in\mathcal{T}\setminus M\text{ and
}v\in M\right\\}$

9: $K\leftarrow\left\\{u\in\mathcal{T}\setminus M\mid\text{ there exists
}v\in\mathcal{T}\setminus M\text{ such that }(u,v)\in D\right\\}$

10: $K\leftarrow\textsc{Sort}(K)$, $P\leftarrow\textsc{Sort}(P)$
$\triangleright$ lexicographically on the indices of tiles

11: $\mathcal{S}\leftarrow K\cup\\{u\boxslash^{i}v\mid(u,v)\in P\\}$
$\triangleright$ defines uniquely indices of tiles in $\mathcal{S}$ from $0$
to $|\mathcal{S}|-1$.

12: return $\mathcal{S}$,
$\omega:\Omega_{\mathcal{S}}\to\Omega_{\mathcal{T}}:\begin{cases}u\boxslash^{i}v\quad\mapsto\quad
u\odot^{i}v&\text{ if }(u,v)\in P\\\ u\quad\mapsto\quad u&\text{ if }u\in
K.\end{cases}$

13:$\mathcal{S}$ is a set of Wang tiles;
$\omega:\Omega_{\mathcal{S}}\to\Omega_{\mathcal{T}}$ is recognizable and onto
up to a shift.

In the definition of $\omega$ in Algorithm 2, given two Wang tiles $u$ and $v$
such that $u\boxslash^{i}v$ is defined for $i\in\\{1,2\\}$, the map

$u\boxslash^{i}v\quad\mapsto\quad u\odot^{i}v$

can be seen as a decomposition of Wang tiles:

or

whether $i=1$ or $i=2$ and where $A=Y$ and $B=Z$. The reader may wonder how
the substitution decides the color $A$ (color $B$ if $i=2$) from its input
tiles. The answer is that Algorithm 2 is performing a desubstitution.
Therefore the two tiles sharing the vertical side with letter $A$ are known
from the start and the algorithm just creates a new tile $(W,BX,C,DZ)$ and
claims that it will always get replaced by the two tiles with shared edge with
color $A$.

Exercise 4.5 Using the function FindSubstitution defined in Algorithm 2 with
the subset $M\subset\mathcal{U}$ of markers for the direction
${\boldsymbol{e}}_{2}$ computed in Exercise 4.1, construct a set of tiles
$\mathcal{V}$ and a recognizable $2$-dimensional morphism
$\alpha_{0}:\Omega_{\mathcal{V}}\to\Omega_{\mathcal{U}}$ which is onto up to a
shift and such that $\alpha_{0}(u)\in\mathcal{U}\setminus M\quad\text{ or
}\quad\alpha_{0}(u)\in(\mathcal{U}\setminus M)\odot^{2}M.$

###  4.4. Self-similarity of the Wang shift $\Omega_{\mathcal{U}}$ defined by
19 tiles

We prove that $\Omega_{\mathcal{U}}$ is self-similar by executing the function
FindMarkers on the set of Wang tiles $\mathcal{U}$ followed by
FindSubstitution and repeating this process until we obtain a set of Wang
tiles which is equivalent to the original one (two steps are needed). Each
time FindMarkers finds at least one subset of markers using a surrounding
radius of size at most 2. Thus using Theorem 4.4, we find a desubstitution of
tilings with FindSubstitution. The proof is done in SageMath [Sag20] using
slabbe optional package [Lab20].

The following result was shown in [Lab19] where it was also proved that
$\Omega_{\mathcal{U}}$ is aperiodic and minimal. In [Lab21c], it was later
shown that the set $\Omega_{\mathcal{U}}$ describes the internal self-similar
structure hidden in Jeandel-Rao aperiodic tilings [JR15]. One of its
consequence is that the Wang shift $\Omega_{\mathcal{U}}$ provides another
description for the substitutive subshift $\mathcal{X}_{\phi}$, see Exercise
4.4.

###### Proof of Theorem 1.1 (i).

In this proof, we show there exist sets of Wang tiles $\mathcal{V}$ and
$\mathcal{W}$ together with their associated Wang shifts
$\Omega_{\mathcal{V}}$ and $\Omega_{\mathcal{W}}$ and there exist two
recognizable $2$-dimensional morphisms $\alpha_{0}$ and $\alpha_{1}$ and a
bijection $\alpha_{2}$:

$\Omega_{\mathcal{U}}\xleftarrow{\alpha_{0}}\Omega_{\mathcal{V}}\xleftarrow{\alpha_{1}}\Omega_{\mathcal{W}}\xleftarrow{\alpha_{2}}\Omega_{\mathcal{U}}$

that are onto up to a shift, i.e.,
$\overline{\alpha_{0}(\Omega_{\mathcal{V}})}^{\sigma}=\Omega_{\mathcal{U}}$,
$\overline{\alpha_{1}(\Omega_{\mathcal{W}})}^{\sigma}=\Omega_{\mathcal{V}}$
and $\alpha_{2}(\Omega_{\mathcal{U}})=\Omega_{\mathcal{W}}$.

First we define the set $\mathcal{U}$ of Wang tiles in SageMath:

`
$\mathcal{U}=\left\{\raisebox{-42.67912pt}{\includegraphics{SageOutputs/U-tiles.pdf}}\right\}$
We desubstitute $\mathcal{U}$ with the set $\{0,1,2,3,4,5,6,7\}$ of markers in
the direction ${\boldsymbol{e}}_{2}$: ` We obtain
$\alpha_{0}:\Omega_{\mathcal{V}}\to\Omega_{\mathcal{U}}$ given as a rule of
the form  $\begin{array}[]{ll}\alpha_{0}:&\llbracket
0,20\rrbracket\to\llbracket 0,18\rrbracket^{*^{2}}\\\\[5.69054pt]
&\left\\{\begin{array}[]{llll}0\mapsto\left(8\right),&1\mapsto\left(9\right),&2\mapsto\left(11\right),&3\mapsto\left(13\right),\\\
4\mapsto\left(14\right),&5\mapsto\left(15\right),&6\mapsto\left(16\right),&7\mapsto\left(17\right),\\\
8\mapsto\left(\begin{array}[]{r}0\\\
8\end{array}\right),&9\mapsto\left(\begin{array}[]{r}1\\\
9\end{array}\right),&10\mapsto\left(\begin{array}[]{r}1\\\
10\end{array}\right),&11\mapsto\left(\begin{array}[]{r}1\\\
11\end{array}\right),\\\ 12\mapsto\left(\begin{array}[]{r}6\\\
12\end{array}\right),&13\mapsto\left(\begin{array}[]{r}4\\\
13\end{array}\right),&14\mapsto\left(\begin{array}[]{r}7\\\
13\end{array}\right),&15\mapsto\left(\begin{array}[]{r}2\\\
14\end{array}\right),\\\ 16\mapsto\left(\begin{array}[]{r}6\\\
14\end{array}\right),&17\mapsto\left(\begin{array}[]{r}7\\\
15\end{array}\right),&18\mapsto\left(\begin{array}[]{r}3\\\
16\end{array}\right),&19\mapsto\left(\begin{array}[]{r}3\\\
17\end{array}\right),\\\ 20\mapsto\left(\begin{array}[]{r}5\\\
18\end{array}\right).\end{array}\right.\end{array}$ and the set $\mathcal{V}$
of 21 Wang tiles
$\mathcal{V}=\left\\{\raisebox{-42.67912pt}{\includegraphics{SageOutputs/V-tiles.pdf}}\right\\}.$
The set of tiles $\mathcal{V}$ has three subsets of markers for the direction
${\boldsymbol{e}}_{1}$. We desubstitute $\mathcal{V}$ with the subset of
markers $\\{0,1,2,8,9,10,11\\}$: ` We obtain
$\alpha_{1}:\Omega_{\mathcal{W}}\to\Omega_{\mathcal{V}}$ given as a rule of
the form  $\begin{array}[]{ll}\alpha_{1}:&\llbracket
0,18\rrbracket\to\llbracket 0,20\rrbracket^{*^{2}}\\[5.69054pt]
&\left\{\begin{array}[]{llll}0\mapsto\left(6\right),&1\mapsto\left(7\right),&2\mapsto\left(15\right),&3\mapsto\left(16\right),\\
4\mapsto\left(18\right),&5\mapsto\left(19\right),&6\mapsto\left(3,\,1\right),&7\mapsto\left(4,\,0\right),\\
8\mapsto\left(5,\,0\right),&9\mapsto\left(5,\,2\right),&10\mapsto\left(6,\,0\right),&11\mapsto\left(7,\,0\right),\\
12\mapsto\left(12,\,9\right),&13\mapsto\left(13,\,9\right),&14\mapsto\left(14,\,9\right),&15\mapsto\left(15,\,8\right),\\
16\mapsto\left(16,\,11\right),&17\mapsto\left(17,\,11\right),&18\mapsto\left(20,\,10\right).\end{array}\right.\end{array}$
and the set $\mathcal{W}$ of 19 Wang tiles
$\mathcal{W}=\left\{\raisebox{-42.67912pt}{\includegraphics{SageOutputs/W-tiles.pdf}}\right\}.$
It turns out that $\mathcal{U}$ and $\mathcal{W}$ are equivalent. The proof
can be done using graph isomorphisms: ` The bijection vert between the
vertical colors, the bijection horiz between the horizontal colors and
bijection $\alpha_{2}$ from $\mathcal{U}$ to $\mathcal{W}$ is computed as
follows: ` We obtain the morphism
$\alpha_{2}:\Omega_{\mathcal{U}}\to\Omega_{\mathcal{W}}$ given as a rule of
the form  $\begin{array}[]{ll}\alpha_{2}:&\llbracket
0,18\rrbracket\to\llbracket 0,18\rrbracket^{*^{2}}\\[5.69054pt]
&\left\{\begin{array}[]{llll}0\mapsto\left(1\right),&1\mapsto\left(0\right),&2\mapsto\left(9\right),&3\mapsto\left(6\right),\\
4\mapsto\left(11\right),&5\mapsto\left(10\right),&6\mapsto\left(8\right),&7\mapsto\left(7\right),\\
8\mapsto\left(3\right),&9\mapsto\left(5\right),&10\mapsto\left(4\right),&11\mapsto\left(2\right),\\
12\mapsto\left(17\right),&13\mapsto\left(16\right),&14\mapsto\left(14\right),&15\mapsto\left(12\right),\\
16\mapsto\left(18\right),&17\mapsto\left(13\right),&18\mapsto\left(15\right).\end{array}\right.\end{array}$
We may check that $\alpha_{0}\circ\alpha_{1}\circ\alpha_{2}=\phi$ where the
variable Phi was created in Exercise 3.1: ` We conclude that
$\Omega_{\mathcal{U}}=\overline{\alpha_{0}(\Omega_{\mathcal{V}})}^{\sigma}=\overline{\alpha_{0}\alpha_{1}(\Omega_{\mathcal{W}})}^{\sigma}=\overline{\alpha_{0}\alpha_{1}\alpha_{2}(\Omega_{\mathcal{U}})}^{\sigma}=\overline{\phi(\Omega_{\mathcal{U}})}^{\sigma}$.
∎ In the proof, we used Knuth’s dancing links algorithm [Knu00] because it is
faster at this particular task than the MILP solver Gurobi [GO20] or the SAT
solvers Glucose [AS18] as we can see below: ` Note that for other tasks like
finding a valid tiling of a $n\times n$ square with Wang tiles, the Glucose
SAT solver [AS18] based on MiniSAT [SE05] is faster [Lab18] than Knuth’s
dancing links algorithm or MILP solvers. Exercise 4.6 Using the value of $H$
and $V$ from Exercise 3.1, prove that $\Omega_{\mathcal{U}}\neq\varnothing$.
Exercise 4.7 Building on Exercise 3.3 and Exercise 4.4, prove that
$\Omega_{\mathcal{U}}=\mathcal{X}_{\phi}$. Exercise 4.8 Prove the self-
similarity of $\Omega_{\mathcal{U}}$ by using first markers in the direction
${\boldsymbol{e}}_{1}$ in the set $\mathcal{U}$ and then using markers in the
direction ${\boldsymbol{e}}_{2}$.

##  5. Coding of toral $\mathbb{Z}^{2}$-rotations

In this section, we consider the dynamical system
$(\mathbb{T}^{2},\mathbb{Z}^{2},R_{\mathcal{U}})$ defined on the 2-dimensional
torus $\mathbb{T}^{2}=(\mathbb{R}/\mathbb{Z})^{2}$ by the continuous
$\mathbb{Z}^{2}$-action

$\begin{array}[]{rccl}R_{\mathcal{U}}:&\mathbb{Z}^{2}\times\mathbb{T}^{2}&\to&\mathbb{T}^{2}\\
&({\boldsymbol{n}},{\boldsymbol{x}})&\mapsto&{\boldsymbol{x}}+\varphi^{-2}{\boldsymbol{n}}\end{array}$

where $\varphi=\frac{1+\sqrt{5}}{2}$. We define a symbolic representation of
that dynamical system using a well-chosen partition
$\mathcal{P}_{\mathcal{U}}$ of $\mathbb{T}^{2}$ that was introduced in
[Lab21a] where it was proved to be a Markov partition for the dynamical system
$(\mathbb{T}^{2},\mathbb{Z}^{2},R_{\mathcal{U}})$. We use the index
$\mathcal{U}$ to be consistent with the notations used in [Lab21a]. As
illustrated in Figure 7, the partition $\mathcal{P}_{\mathcal{U}}$ can be
defined from the following 8 segments in $\mathbb{R}^{2}$:

$\displaystyle(1,\varphi^{2})\to(0,\varphi^{2})\to(\varphi,0)\to(\varphi,1),$
$\displaystyle(1,1)\to(0,1)\to(1,0)\to(1,1),$
$\displaystyle\left(\frac{1}{\varphi^{2}},2\right)\to\left(1+\frac{1}{\varphi^{2}},1\right)\to\left(1+\frac{1}{\varphi^{2}},2\right).$

Figure 7.  The partition $\mathcal{P}_{\mathcal{U}}$ of $\mathbb{T}^{2}$ can
be constructed from 8 segments in $\mathbb{R}^{2}$ (left) and their images
under the group of translations $\mathbb{Z}^{2}$ (right). Figure 8.  The
polygonal partition $\mathcal{P}_{\mathcal{U}}$ of $\mathbb{T}^{2}$ with
indices in the set $\llbracket 0,18\rrbracket$. The coding of the shifted
lattice ${\boldsymbol{p}}+\frac{1}{\varphi^{2}}\mathbb{Z}^{2}$ by the
partition defines a configuration in $\llbracket
0,18\rrbracket^{\mathbb{Z}^{2}}$. In the figure, the points
${\boldsymbol{p}}+\frac{1}{\varphi^{2}}(m,n)$ are shown in white with
${\boldsymbol{p}}=(0.1357,0.2938)$ for each $m\in\llbracket 0,5\rrbracket$ and
$n\in\llbracket 0,7\rrbracket$ and are coded by a $2$-dimensional word of
shape $(6,8)$.

The translations of the 8 segments under the group of translation
$\mathbb{Z}^{2}$ splits the torus $\mathbb{T}^{2}$ into 19 polygonal regions
indexed with integers from the set $\llbracket 0,18\rrbracket$. The coding by
the partition $\mathcal{P}_{\mathcal{U}}$ of the orbit of a starting point in
$\mathbb{T}^{2}$ by the $\mathbb{Z}^{2}$-action of $R_{\mathcal{U}}$ defines a
configuration $w\in\llbracket 0,18\rrbracket^{\mathbb{Z}^{2}}$, see Figure 8.
The topological closure of the set of all such configurations is the symbolic
dynamical system $\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}}$
corresponding to $\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}$ (see Lemma 5.7).
It turns out that $\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}}$ is
a subshift as it is also closed under the shift $\sigma$ by integer
translations.

The goal of the next sections is to prove that the symbolic dynamical system
$\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}}$ is self-similar
where the self-similarity is given by the $2$-dimensional morphism $\phi$
defined in Equation (1) (Theorem 1.1 (ii)).

Exercise 5.1 Figure 8 provides the construction of a 2-dimensional word of
shape $(6,8)$. Using the same construction, extend that pattern by one unit in
all directions to obtain a word of shape $(8,10)$.

###  5.1. Toral $\mathbb{Z}^{2}$-rotations and polygon exchange
transformations (PETs)

Let $\Gamma$ be a lattice in $\mathbb{R}^{2}$, i.e., a discrete subgroup of
the additive group $\mathbb{R}^{2}$ with $2$ linearly independent generators.
This defines a $2$-dimensional torus ${\boldsymbol{T}}=\mathbb{R}^{2}/\Gamma$.
By analogy with the rotation $x\mapsto x+\alpha$ on the circle
$\mathbb{R}/\mathbb{Z}$ for an $\alpha\in\mathbb{R}$, we use the terminology
of rotation (sometimes also called translation) to denote the following
$\mathbb{Z}^{2}$-action defined on a 2-dimensional torus.

######  Definition 5.1.

Let ${\boldsymbol{T}}=\mathbb{R}^{2}/\Gamma$ where $\Gamma$ is a lattice in
$\mathbb{R}^{2}$. For some
${\boldsymbol{\alpha}},{\boldsymbol{\beta}}\in{\boldsymbol{T}}$, we consider
the dynamical system $({\boldsymbol{T}},\mathbb{Z}^{2},R)$ where
$R:\mathbb{Z}^{2}\times{\boldsymbol{T}}\to{\boldsymbol{T}}$ is the continuous
$\mathbb{Z}^{2}$-action on ${\boldsymbol{T}}$ defined by

$R^{\boldsymbol{n}}({\boldsymbol{x}}):=R({\boldsymbol{n}},{\boldsymbol{x}})={\boldsymbol{x}}+n_{1}{\boldsymbol{\alpha}}+n_{2}{\boldsymbol{\beta}}$

for every ${\boldsymbol{n}}=(n_{1},n_{2})\in\mathbb{Z}^{2}$. We say that the
$\mathbb{Z}^{2}$-action $R$ is a toral $\mathbb{Z}^{2}$-rotation or a
$\mathbb{Z}^{2}$-rotation on ${\boldsymbol{T}}$ which defines a dynamical
system $({\boldsymbol{T}},\mathbb{Z}^{2},R)$.

It is practical to represent a toral $\mathbb{Z}^{2}$-rotation in terms of
polygon exchange transformations [Hoo13, Sch14].

######  Definition 5.2.

[AKY19] Let $X$ be a polygon together with two topological partitions of $X$
into polygons

$X=\bigcup_{k=0}^{N}P_{k}=\bigcup_{k=0}^{N}Q_{k}$

such that for each $k$, $P_{k}$ and $Q_{k}$ are translation equivalent, i.e.,
there exists ${\boldsymbol{v}}_{k}\in\mathbb{R}^{2}$ such that
$P_{k}=Q_{k}+{\boldsymbol{v}}_{k}$. A polygon exchange transformation (PET) is
the piecewise translation on $X$ defined for ${\boldsymbol{x}}\in P_{k}$ by
$T({\boldsymbol{x}})={\boldsymbol{x}}+{\boldsymbol{v}}_{k}$. The map is not
defined for points ${\boldsymbol{x}}\in\bigcup_{k=0}^{N}\partial P_{k}$.

Figure 9. A polygon exchange transformation defined on the triangle with
vertices $(0,0)$, $(0,1)$ and $(1,0)$.

A PETs can be quite complicated. For example, a polygon exchange
transformation is shown in Figure 9. In this chapter, we consider pairs of
commuting PETs that are much simpler given by the exchanges of two rectangles,
see Figure 10.

Figure 10. The $\mathbb{Z}^{2}$-action $R_{\mathcal{U}}$ can be seen as a pair
of commuting polygon exchange transformations on the unit square $[0,1)^{2}$.

A $\mathbb{Z}^{2}$-rotation $R$ on a torus ${\boldsymbol{T}}$ can be
decomposed into two commuting maps as follows:

$R^{\boldsymbol{n}}=R^{n_{1}{\boldsymbol{e}}_{1}+n_{2}{\boldsymbol{e}}_{2}}=R^{n_{1}{\boldsymbol{e}}_{1}}\circ
R^{n_{2}{\boldsymbol{e}}_{2}}=\left(R^{{\boldsymbol{e}}_{1}}\right)^{n_{1}}\circ\left(R^{{\boldsymbol{e}}_{2}}\right)^{n_{2}}.$

where each map $R^{{\boldsymbol{e}}_{1}}$ and $R^{{\boldsymbol{e}}_{2}}$ can
be seen as polygon exchange transformation defined by the exchange of at most
$4$ pieces on a fundamental domain of ${\boldsymbol{T}}$ having for shape a
parallelogram. We state this as a lemma because we use this connection two
times in the proof of Theorem 1.1 (ii).

######  Lemma 5.3.

Let $\Gamma=\ell_{1}\mathbb{Z}\times\ell_{2}\mathbb{Z}$ be a lattice in
$\mathbb{R}^{2}$ and its rectangular fundamental domain
$D=[0,\ell_{1})\times[0,\ell_{2})$. For every
${\boldsymbol{\alpha}}=(\alpha_{1},\alpha_{2})\in D$, the dynamical system
$(\mathbb{R}^{2}/\Gamma,\mathbb{Z},{\boldsymbol{x}}\mapsto{\boldsymbol{x}}+{\boldsymbol{\alpha}})$
is measurably conjugate to the dynamical system $(D,\mathbb{Z},T)$ where
$T:D\to D$ is the polygon exchange transformation shown in Figure 11.

Figure 11. The polygon exchange transformation $T$ of the rectangle
$[0,\ell_{1})\times[0,\ell_{2})$ as defined on the figure can be seen as a
toral rotation by the vector $(\alpha_{1},\alpha_{2})$ on the torus
$\mathbb{R}^{2}/(\ell_{1}\mathbb{Z}\times\ell_{2}\mathbb{Z})$.

###### Proof.

It follows from the fact that toral rotations and such polygon exchange
transformations are the Cartesian product of circle rotations and exchange of
two intervals. The fact that a rotation on a circle can be seen as a exchange
of two intervals is well-known as noticed for example in [Rau77]. ∎

Exercise 5.2 Recall that
$R_{\mathcal{U}}^{\boldsymbol{n}}({\boldsymbol{x}})={\boldsymbol{x}}+\varphi^{-2}{\boldsymbol{n}}$
is a $\mathbb{Z}^{2}$-action defined on $\mathbb{T}^{2}$ where
$\varphi=\frac{1+\sqrt{5}}{2}$. Prove that the maps
$R_{\mathcal{U}}^{{\boldsymbol{e}}_{1}}$ and
$R_{\mathcal{U}}^{{\boldsymbol{e}}_{2}}$ can be expressed as polygon exchange
transformations on the unit square $[0,1)\times[0,1)$ as in Figure 10.

###  5.2. Symbolic dynamical systems for toral $\mathbb{Z}^{2}$-rotations

Let $\Gamma$ be a lattice in $\mathbb{R}^{2}$ and
${\boldsymbol{T}}=\mathbb{R}^{2}/\Gamma$ be a $2$-dimensional torus. Let
$({\boldsymbol{T}},\mathbb{Z}^{2},R)$ be the dynamical system given by a
$\mathbb{Z}^{2}$-rotation $R$ on ${\boldsymbol{T}}$. For some finite set
$\mathcal{A}$, a topological partition of ${\boldsymbol{T}}$ is a finite
collection $\{P_{a}\}_{a\in\mathcal{A}}$ of disjoint open sets
$P_{a}\subset{\boldsymbol{T}}$ such that
${\boldsymbol{T}}=\bigcup_{a\in\mathcal{A}}\overline{P_{a}}$. If
$S\subset\mathbb{Z}^{2}$ is a finite set, we say that a pattern
$w\in\mathcal{A}^{S}$ is allowed for $\mathcal{P},R$ if

(9) $\bigcap_{{\boldsymbol{k}}\in
S}R^{-{\boldsymbol{k}}}(P_{w_{\boldsymbol{k}}})\neq\varnothing.$

Let $\mathcal{L}_{\mathcal{P},R}$ be the collection of all allowed patterns
for $\mathcal{P},R$. The set $\mathcal{L}_{\mathcal{P},R}$ is the language of
a subshift $\mathcal{X}_{\mathcal{P},R}\subseteq\mathcal{A}^{\mathbb{Z}^{2}}$
defined as follows, see [Hoc16, Prop. 9.2.4],

$\mathcal{X}_{\mathcal{P},R}=\{x\in\mathcal{A}^{\mathbb{Z}^{2}}\mid\pi_{S}\circ\sigma^{\boldsymbol{n}}(x)\in\mathcal{L}_{\mathcal{P},R}\text{
for every }{\boldsymbol{n}}\in\mathbb{Z}^{2}\text{ and finite subset
}S\subset\mathbb{Z}^{2}\}.$

######  Definition 5.4.

We call $\mathcal{X}_{\mathcal{P},R}$ the symbolic dynamical system
corresponding to $\mathcal{P},R$.

For each $w\in\mathcal{X}_{\mathcal{P},R}\subset\mathcal{A}^{\mathbb{Z}^{2}}$
and $n\geq 0$ there is a corresponding nonempty open set

$D_{n}(w)=\bigcap_{\|{\boldsymbol{k}}\|\leq
n}R^{-{\boldsymbol{k}}}(P_{w_{\boldsymbol{k}}})\subseteq{\boldsymbol{T}}.$

The closures $\overline{D}_{n}(w)$ of these sets are compact and decrease with
$n$, so that
$\overline{D}_{0}(w)\supseteq\overline{D}_{1}(w)\supseteq\overline{D}_{2}(w)\supseteq\dots$.
It follows that $\cap_{n=0}^{\infty}\overline{D}_{n}(w)\neq\varnothing$. In
order for points in $\mathcal{X}_{\mathcal{P},R}$ to correspond to points in
${\boldsymbol{T}}$, this intersection should contain only one point. This
leads to the following definition.

######  Definition 5.5.

A topological partition $\mathcal{P}$ of ${\boldsymbol{T}}$ gives a symbolic
representation of $({\boldsymbol{T}},\mathbb{Z}^{2},R)$ if for every
$w\in\mathcal{X}_{\mathcal{P},R}$ the intersection
$\cap_{n=0}^{\infty}\overline{D}_{n}(w)$ consists of exactly one point
${\boldsymbol{x}}\in{\boldsymbol{T}}$. We call $w$ a symbolic representation
of ${\boldsymbol{x}}$.

In general, the existence of an atom of the partition of the torus
${\boldsymbol{T}}$ which is invariant only under the trivial translation is a
sufficient condition for the partition to give a symbolic representation of a
minimal $\mathbb{Z}^{2}$-rotation on ${\boldsymbol{T}}$.

######  Lemma 5.6.

[Lab21a, Lemma 3.4] Let $({\boldsymbol{T}},\mathbb{Z}^{2},R)$ be a minimal
dynamical system and $\mathcal{P}=\{P_{0},P_{1},...,P_{r-1}\}$ be a
topological partition of ${\boldsymbol{T}}$. If there exists an atom $P_{i}$
which is invariant only under the trivial translation in ${\boldsymbol{T}}$,
then $\mathcal{P}$ gives a symbolic representation of
$({\boldsymbol{T}},\mathbb{Z}^{2},R)$.

###### Proof.

Let $\mathcal{A}=\{0,1,\dots,r-1\}$. Let
$w\in\mathcal{X}_{\mathcal{P},R}\subset\mathcal{A}^{\mathbb{Z}^{2}}$. As
already noticed, the closures $\overline{D}_{n}(w)$ are compact and decrease
with $n$, so that
$\overline{D}_{0}(w)\supseteq\overline{D}_{1}(w)\supseteq\overline{D}_{2}(w)\supseteq\dots$.
It follows that $\cap_{n=0}^{\infty}\overline{D}_{n}(w)\neq\varnothing$.

We show that $\cap_{n=0}^{\infty}\overline{D}_{n}(w)$ contains at most one
element. Let ${\boldsymbol{x}},{\boldsymbol{y}}\in{\boldsymbol{T}}$. We assume
${\boldsymbol{x}}\in\cap_{n=0}^{\infty}\overline{D}_{n}(w)$ and we want to
show that ${\boldsymbol{y}}\notin\cap_{n=0}^{\infty}\overline{D}_{n}(w)$ if
${\boldsymbol{x}}\neq{\boldsymbol{y}}$. Let $P_{i}\subset{\boldsymbol{T}}$ for
some $i\in\mathcal{A}$ be an atom which is invariant only under the trivial
translation. Since ${\boldsymbol{x}}\neq{\boldsymbol{y}}$,
$\overline{P_{i}}\setminus(\overline{P_{i}}-({\boldsymbol{y}}-{\boldsymbol{x}}))$
contains an open set $O$. Since $({\boldsymbol{T}},\mathbb{Z}^{2},R)$ is
minimal, any orbit
$\{R^{\boldsymbol{k}}{\boldsymbol{x}}\mid{\boldsymbol{k}}\in\mathbb{Z}^{2}\}$
is dense in ${\boldsymbol{T}}$. Therefore, there exists
${\boldsymbol{k}}\in\mathbb{Z}^{2}$ such that
$R^{\boldsymbol{k}}{\boldsymbol{x}}\in O\subset\accentset{\circ}{P_{i}}$. Also
${\boldsymbol{x}}\in\cap_{n=0}^{\infty}\overline{D}_{n}(w)\subset
R^{-{\boldsymbol{k}}}\overline{P_{w_{\boldsymbol{k}}}}$ which implies
$R^{\boldsymbol{k}}{\boldsymbol{x}}\in\overline{P_{w_{\boldsymbol{k}}}}$. Thus
$\overline{P_{w_{\boldsymbol{k}}}}\cap\accentset{\circ}{P_{i}}\neq\varnothing$
which implies that $P_{w_{\boldsymbol{k}}}=P_{i}$ and $w_{\boldsymbol{k}}=i$
since $\mathcal{P}$ is a topological partition. Thus

$\cap_{n=0}^{\infty}\overline{D}_{n}(w)\subset
R^{-{\boldsymbol{k}}}\overline{P_{w_{\boldsymbol{k}}}}=R^{-{\boldsymbol{k}}}\overline{P_{i}}.$

The fact that $R^{\boldsymbol{k}}{\boldsymbol{x}}\in O$ also means that
$R^{\boldsymbol{k}}{\boldsymbol{x}}\notin\overline{P_{i}}-({\boldsymbol{y}}-{\boldsymbol{x}})$
which can be rewritten as
$R^{\boldsymbol{k}}{\boldsymbol{y}}\notin\overline{P_{i}}$ or
${\boldsymbol{y}}\notin R^{-{\boldsymbol{k}}}\overline{P_{i}}$ and we conclude
that ${\boldsymbol{y}}\notin\cap_{n=0}^{\infty}\overline{D}_{n}(w)$. Thus
$\mathcal{P}$ gives a symbolic representation of
$({\boldsymbol{T}},\mathbb{Z}^{2},R)$. ∎

The set

$\Delta_{\mathcal{P},R}:=\bigcup_{{\boldsymbol{n}}\in\mathbb{Z}^{2}}R^{\boldsymbol{n}}\left(\bigcup_{a\in\mathcal{A}}\partial
P_{a}\right)\subset{\boldsymbol{T}}$

is the set of points whose orbit under the $\mathbb{Z}^{2}$-action of $R$
intersect the boundary of the topological partition
$\mathcal{P}=\{P_{a}\}_{a\in\mathcal{A}}$. From Baire Category Theorem [LM95,
Theorem 6.1.24], the set ${\boldsymbol{T}}\setminus\Delta_{\mathcal{P},R}$ is
dense in ${\boldsymbol{T}}$.

A topological partition $\mathcal{P}=\{P_{a}\}_{a\in\mathcal{A}}$ of
${\boldsymbol{T}}=\mathbb{R}^{2}/\Gamma$ is associated to a coding map

$\begin{array}[]{rccl}\textsc{Code}:&{\boldsymbol{T}}\setminus\left(\bigcup_{a\in\mathcal{A}}\partial
P_{a}\right)&\to&\mathcal{A}\\ &{\boldsymbol{x}}&\mapsto&a\quad\text{ if and
only if }\quad{\boldsymbol{x}}\in P_{a}.\end{array}$

For every starting point
${\boldsymbol{x}}\in{\boldsymbol{T}}\setminus\Delta_{\mathcal{P},R}$, the
coding of its orbit under the $\mathbb{Z}^{2}$-action of $R$ is a
configuration
$\textsc{Config}^{\mathcal{P},R}_{{\boldsymbol{x}}}\in\mathcal{A}^{\mathbb{Z}^{2}}$
defined by

$\textsc{Config}^{\mathcal{P},R}_{{\boldsymbol{x}}}({\boldsymbol{n}})=\textsc{Code}(R^{\boldsymbol{n}}({\boldsymbol{x}})).$

for every ${\boldsymbol{n}}\in\mathbb{Z}\times\mathbb{Z}$.

######  Lemma 5.7.

The symbolic dynamical system $\mathcal{X}_{\mathcal{P},R}$ corresponding to
$\mathcal{P},R$ is the topological closure of the set of configurations:

$\mathcal{X}_{\mathcal{P},R}=\overline{\left\{\textsc{Config}^{\mathcal{P},R}_{\boldsymbol{x}}\mid{\boldsymbol{x}}\in{\boldsymbol{T}}\setminus\Delta_{\mathcal{P},R}\right\}}.$

###### Proof.

($\supseteq$) Let
${\boldsymbol{x}}\in{\boldsymbol{T}}\setminus\Delta_{\mathcal{P},R}$. The
patterns appearing in the configuration
$\textsc{Config}^{\mathcal{P},R}_{\boldsymbol{x}}$ are in
$\mathcal{L}_{\mathcal{P},R}$. Thus
$\textsc{Config}^{\mathcal{P},R}_{\boldsymbol{x}}\in\mathcal{X}_{\mathcal{P},R}$.
The topological closure of such configurations is in
$\mathcal{X}_{\mathcal{P},R}$ since $\mathcal{X}_{\mathcal{P},R}$ is
topologically closed.

($\subseteq$) Let $w\in\mathcal{A}^{S}$ be a pattern with finite support
$S\subset\mathbb{Z}^{2}$ appearing in $\mathcal{X}_{\mathcal{P},R}$. Then
$w\in\mathcal{L}_{\mathcal{P},R}$ and from Equation (9) there exists
${\boldsymbol{x}}\in{\boldsymbol{T}}\setminus\Delta_{\mathcal{P},R}$ such that
${\boldsymbol{x}}\in\bigcap_{{\boldsymbol{k}}\in
S}R^{-{\boldsymbol{k}}}(P_{w_{\boldsymbol{k}}})$. The pattern $w$ appears in
the configuration $\textsc{Config}^{\mathcal{P},R}_{\boldsymbol{x}}$. Any
configuration in $\mathcal{X}_{\mathcal{P},R}$ is the limit of a sequence
$(w_{n})_{n\in\mathbb{N}}$ of patterns covering a ball of radius $n$ around
the origin, thus equal to some limit
$\lim_{n\to\infty}\textsc{Config}^{\mathcal{P},R}_{{\boldsymbol{x}}_{n}}$ with
${\boldsymbol{x}}_{n}\in{\boldsymbol{T}}\setminus\Delta_{\mathcal{P},R}$ for
every $n\in\mathbb{N}$. ∎

Exercise 5.3 Prove that $\mathcal{P}_{\mathcal{U}}$ gives a symbolic
representation of the dynamical system
$(\mathbb{T}^{2},\mathbb{Z}^{2},R_{\mathcal{U}})$.

###  5.3. Factor map

An important consequence of the fact that a partition $\mathcal{P}$ gives a
symbolic representation of the dynamical system
$({\boldsymbol{T}},\mathbb{Z}^{2},R)$ is the existence of a factor map
$f:\mathcal{X}_{\mathcal{P},R}\to{\boldsymbol{T}}$ which commutes the
$\mathbb{Z}^{2}$-actions. In the spirit of [LM95, Prop. 6.5.8] for
$\mathbb{Z}$-actions, we have the following proposition whose proof can be
found in [Lab21a].

######  Proposition 5.8.

[Lab21a, Prop. 5.1] Let $\mathcal{P}$ give a symbolic representation of the
dynamical system $({\boldsymbol{T}},\mathbb{Z}^{2},R)$. Let
$f:\mathcal{X}_{\mathcal{P},R}\to{\boldsymbol{T}}$ be defined such that $f(w)$
is the unique point in the intersection
$\cap_{n=0}^{\infty}\overline{D}_{n}(w)$. The map $f$ is a factor map from
$(\mathcal{X}_{\mathcal{P},R},\mathbb{Z}^{2},\sigma)$ to
$({\boldsymbol{T}},\mathbb{Z}^{2},R)$ such that $R^{\boldsymbol{k}}\circ
f=f\circ\sigma^{\boldsymbol{k}}$ for every
${\boldsymbol{k}}\in\mathbb{Z}^{2}$. The map $f$ is one-to-one on
$f^{-1}({\boldsymbol{T}}\setminus\Delta_{\mathcal{P},R})$.

Using the factor map, one can prove the following lemma.

######  Lemma 5.9.

[Lab21a, Lemma 5.2] Let $\mathcal{P}$ give a symbolic representation of the
dynamical system $({\boldsymbol{T}},\mathbb{Z}^{2},R)$. Then

  1. (i)

if $({\boldsymbol{T}},\mathbb{Z}^{2},R)$ is minimal, then
$(\mathcal{X}_{\mathcal{P},R},\mathbb{Z}^{2},\sigma)$ is minimal,

  2. (ii)

if $R$ is a free $\mathbb{Z}^{2}$-action on ${\boldsymbol{T}}$, then
$\mathcal{X}_{\mathcal{P},R}$ aperiodic.

Of course, Lemma 5.9 does not hold if $\mathcal{P}$ does not give a symbolic
representation of $({\boldsymbol{T}},\mathbb{Z}^{2},R)$.

Exercise 5.4 Prove that
$(\mathcal{X}_{\mathcal{P}_{\mathcal{U}},R_{\mathcal{U}}},\mathbb{Z}^{2},\sigma)$
is minimal and aperiodic.

###  5.4. Induced $\mathbb{Z}^{2}$-actions

Renormalization schemes also known as _Rauzy induction_ were originally
defined for dynamical systems including interval exchange transformations
(IET) [Rau79]. A natural way to generalize it to higher dimension is to
consider polygon exchange transformations [Hoo13, AKY19] or even polytope
exchange transformations [Sch14, Sch11] where only one map is considered. But
more dimensions also allow to induce two or more (commuting) maps at the same
time.

In this section, we define the induction of $\mathbb{Z}^{2}$-actions on a sub-
domain. We consider the torus ${\boldsymbol{T}}=\mathbb{R}^{2}/\Gamma$ where
$\Gamma$ is a lattice in $\mathbb{R}^{2}$. Let
$({\boldsymbol{T}},\mathbb{Z}^{2},R)$ be a minimal dynamical system given by a
$\mathbb{Z}^{2}$-action $R$ on ${\boldsymbol{T}}$. For every
${\boldsymbol{n}}\in\mathbb{Z}^{2}$, the toral translation
$R^{{\boldsymbol{n}}}$ can be seen as a pair of polygon exchange
transformations on a fundamental domain of ${\boldsymbol{T}}$.

Let $W\subset{\boldsymbol{T}}$ be a set. The set of return times of
${\boldsymbol{x}}\in{\boldsymbol{T}}$ to the window $W$ under the
$\mathbb{Z}^{2}$-action $R$ is the subset of $\mathbb{Z}\times\mathbb{Z}$
defined as:

$\delta_{W}({\boldsymbol{x}})=\{{\boldsymbol{n}}\in\mathbb{Z}\times\mathbb{Z}\mid
R^{\boldsymbol{n}}({\boldsymbol{x}})\in W\}.$

######  Definition 5.10.

Let $W\subset{\boldsymbol{T}}$. We say that the $\mathbb{Z}^{2}$-action $R$ is
Cartesian on $W$ if the set of return times $\delta_{W}({\boldsymbol{x}})$ can
be expressed as a Cartesian product, that is, for all
${\boldsymbol{x}}\in{\boldsymbol{T}}$ there exist two strictly increasing
sequences
$r_{\boldsymbol{x}}^{(1)},r_{\boldsymbol{x}}^{(2)}:\mathbb{Z}\to\mathbb{Z}$
such that

$\delta_{W}({\boldsymbol{x}})=r_{\boldsymbol{x}}^{(1)}(\mathbb{Z})\times
r_{\boldsymbol{x}}^{(2)}(\mathbb{Z}).$

We always assume that the sequences are shifted in such a way that

$r_{\boldsymbol{x}}^{(i)}(n)\geq 0\iff n\geq 0\qquad\text{ for }i\in\{1,2\}.$

In particular, if ${\boldsymbol{x}}\in W$ then
$(0,0)\in\delta_{W}({\boldsymbol{x}})$, and therefore
$r_{\boldsymbol{x}}^{(1)}(0)=r_{\boldsymbol{x}}^{(2)}(0)=0$.

When the $\mathbb{Z}^{2}$-action $R$ is Cartesian on
$W\subset{\boldsymbol{T}}$, we say that the tuple

(10) $(r_{\boldsymbol{x}}^{(1)}(1),r_{\boldsymbol{x}}^{(2)}(1))$

is the first return time of a starting point
${\boldsymbol{x}}\in{\boldsymbol{T}}$ to $W\subset{\boldsymbol{T}}$ under the
action $R$. When the $\mathbb{Z}^{2}$-action $R$ is Cartesian on
$W\subset{\boldsymbol{T}}$, we may consider its return map on $W$ and we prove
in the next lemma that this induces a $\mathbb{Z}^{2}$-action on $W$.

######  Lemma 5.11.

If the $\mathbb{Z}^{2}$-action $R$ is Cartesian on $W\subset{\boldsymbol{T}}$,
then the map $\widehat{R}|_{W}:\mathbb{Z}^{2}\times W\to W$ defined by

$(\widehat{R}|_{W})^{\boldsymbol{n}}({\boldsymbol{x}}):=\widehat{R}|_{W}({\boldsymbol{n}},{\boldsymbol{x}})=R^{(r_{\boldsymbol{x}}^{(1)}(n_{1}),r_{\boldsymbol{x}}^{(2)}(n_{2}))}({\boldsymbol{x}})$

for every ${\boldsymbol{n}}=(n_{1},n_{2})\in\mathbb{Z}^{2}$ and
${\boldsymbol{x}}\in W$ is a well-defined $\mathbb{Z}^{2}$-action on $W$.

We say that $\widehat{R}|_{W}$ is the induced $\mathbb{Z}^{2}$-action of the
$\mathbb{Z}^{2}$-action $R$ on $W$.

###### Proof.

Let ${\boldsymbol{x}}\in W$. We have that

$\widehat{R}|_{W}({\boldsymbol{0}},{\boldsymbol{x}})=R^{(r_{\boldsymbol{x}}^{(1)}(0),r_{\boldsymbol{x}}^{(2)}(0))}({\boldsymbol{x}})=R^{(0,0)}({\boldsymbol{x}})={\boldsymbol{x}}.$

Firstly, using

$r_{\boldsymbol{x}}^{(i)}(k+n)=r_{R^{{\boldsymbol{e}}_{i}\cdot
r_{\boldsymbol{x}}^{(i)}(n)}({\boldsymbol{x}})}(k)+r_{\boldsymbol{x}}^{(i)}(n),$

and skipping few details, we get

$\widehat{R}|_{W}(k{\boldsymbol{e}}_{i}+n{\boldsymbol{e}}_{i},{\boldsymbol{x}})=\widehat{R}|_{W}\left(k{\boldsymbol{e}}_{i},\left(\widehat{R}|_{W}(n{\boldsymbol{e}}_{i},{\boldsymbol{x}})\right)\right).$

Secondly, using the fact that

$r_{\boldsymbol{x}}^{(1)}(k_{1})=r_{\boldsymbol{y}}^{(1)}(k_{1})$

whenever
$y=R^{(0,r_{\boldsymbol{x}}^{(2)}(k_{2}))}{\boldsymbol{x}}=\widehat{R}|_{W}(k_{2}{\boldsymbol{e}}_{2},{\boldsymbol{x}})$,
we obtain

$\displaystyle\widehat{R}|_{W}({\boldsymbol{k}},{\boldsymbol{x}})$
$\displaystyle=R^{(r_{\boldsymbol{x}}^{(1)}(k_{1}),r_{\boldsymbol{x}}^{(2)}(k_{2}))}({\boldsymbol{x}})=R^{(r_{\boldsymbol{x}}^{(1)}(k_{1}),0)}R^{(0,r_{\boldsymbol{x}}^{(2)}(k_{2}))}({\boldsymbol{x}})$
$\displaystyle=R^{(r_{\boldsymbol{x}}^{(1)}(k_{1}),0)}\widehat{R}|_{W}(k_{2}{\boldsymbol{e}}_{2},{\boldsymbol{x}})=\widehat{R}|_{W}\left(k_{1}{\boldsymbol{e}}_{1},\widehat{R}|_{W}(k_{2}{\boldsymbol{e}}_{2},{\boldsymbol{x}})\right).$

Therefore, for every ${\boldsymbol{k}},{\boldsymbol{n}}\in\mathbb{Z}^{2}$, we
have

$\displaystyle(\widehat{R}|_{W})^{{\boldsymbol{k}}+{\boldsymbol{n}}}({\boldsymbol{x}})$
$\displaystyle=(\widehat{R}|_{W})^{(k_{1}+n_{1}){\boldsymbol{e}}_{1}}(\widehat{R}|_{W})^{(k_{2}+n_{2}){\boldsymbol{e}}_{2}}({\boldsymbol{x}})$
$\displaystyle=(\widehat{R}|_{W})^{k_{1}{\boldsymbol{e}}_{1}}(\widehat{R}|_{W})^{n_{1}{\boldsymbol{e}}_{1}}(\widehat{R}|_{W})^{k_{2}{\boldsymbol{e}}_{2}}(\widehat{R}|_{W})^{n_{2}{\boldsymbol{e}}_{2}}({\boldsymbol{x}})$
$\displaystyle=(\widehat{R}|_{W})^{k_{1}{\boldsymbol{e}}_{1}}(\widehat{R}|_{W})^{(n_{1},k_{2})}(\widehat{R}|_{W})^{n_{2}{\boldsymbol{e}}_{2}}({\boldsymbol{x}})$
$\displaystyle=(\widehat{R}|_{W})^{k_{1}{\boldsymbol{e}}_{1}}(\widehat{R}|_{W})^{k_{2}{\boldsymbol{e}}_{2}}(\widehat{R}|_{W})^{n_{1}{\boldsymbol{e}}_{1}}(\widehat{R}|_{W})^{n_{2}{\boldsymbol{e}}_{2}}({\boldsymbol{x}})$
$\displaystyle=(\widehat{R}|_{W})^{\boldsymbol{k}}(\widehat{R}|_{W})^{\boldsymbol{n}}({\boldsymbol{x}}),$

which shows that $\widehat{R}|_{W}$ is a $\mathbb{Z}^{2}$-action on $W$. ∎

A consequence of the lemma is that the induced $\mathbb{Z}^{2}$-action
$\widehat{R}|_{W}$ is generated by two commutative maps

$(\widehat{R}|_{W})^{{\boldsymbol{e}}_{1}}({\boldsymbol{x}})=R^{(r_{\boldsymbol{x}}^{(1)}(1),0)}({\boldsymbol{x}})\quad\text{
and
}\quad(\widehat{R}|_{W})^{{\boldsymbol{e}}_{2}}({\boldsymbol{x}})=R^{(0,r_{\boldsymbol{x}}^{(2)}(1))}({\boldsymbol{x}})$

which are the first return maps of $R^{{\boldsymbol{e}}_{1}}$ and
$R^{{\boldsymbol{e}}_{2}}$ to $W$:

$(\widehat{R}|_{W})^{{\boldsymbol{e}}_{1}}({\boldsymbol{x}})=\widehat{R^{{\boldsymbol{e}}_{1}}}|_{W}({\boldsymbol{x}})\quad\text{
and
}\quad(\widehat{R}|_{W})^{{\boldsymbol{e}}_{2}}({\boldsymbol{x}})=\widehat{R^{{\boldsymbol{e}}_{2}}}|_{W}({\boldsymbol{x}}).$

Recall that the first return map $\widehat{T}|_{W}$ of a dynamical system
$(X,T)$ maps a point ${\boldsymbol{x}}\in W\subset X$ to the first point in
the forward orbit of $T$ lying in $W$, i.e.

$\widehat{T}|_{W}({\boldsymbol{x}})=T^{r({\boldsymbol{x}})}({\boldsymbol{x}})\quad\text{
where
}r({\boldsymbol{x}})=\min\{k\in\mathbb{Z}_{>0}:T^{k}({\boldsymbol{x}})\in
W\}.$

From Poincaré’s recurrence theorem, if $\mu$ is a finite $T$-invariant measure
on $X$, then the first return map $\widehat{T}|_{W}$ is well defined for
$\mu$-almost all ${\boldsymbol{x}}\in W$. When $T$ is a rotation on a torus,
if the subset $W$ is open, then the first return map is well-defined for every
point ${\boldsymbol{x}}\in W$. Moreover if $W$ is a polygon, then the first
return map $\widehat{T}|_{W}$ is a polygon exchange transformation. An
algorithm to compute the induced transformation
$\widehat{T}|_{W}=\widehat{R^{{\boldsymbol{e}}_{i}}}|_{W}$ of the sub-action
$R^{{\boldsymbol{e}}_{i}}$ is provided in [Lab21b].

Exercise 5.5 Let
$T({\boldsymbol{x}})={\boldsymbol{x}}+(\frac{1}{3},\frac{1}{2})$ be a
$\mathbb{Z}$-action defined on $\mathbb{T}^{2}$. Let $W\subset\mathbb{T}^{2}$
be the triangle with vertices $(0,0)$, $(1,0)$ and $(0,1)$. Prove that
$\widehat{T}|_{W}$ is the PET defined in Figure 9. Reproduce in SageMath the
computations of $\widehat{T}|_{W}$ shown below and verify that it produces the
same result.` `

Exercise 5.6 Recall that
$R_{\mathcal{U}}({\boldsymbol{n}},{\boldsymbol{x}})={\boldsymbol{x}}+\varphi^{-2}{\boldsymbol{n}}$
is a $\mathbb{Z}^{2}$-action defined on $\mathbb{T}^{2}$ where
$\varphi=\frac{1+\sqrt{5}}{2}$. Let
$W_{0}=(0,1)\times(0,\varphi^{-1})+\mathbb{Z}^{2}$ be a subset of
$\mathbb{T}^{2}$. • Prove that the action $R_{\mathcal{U}}$ is Cartesian on
$W_{0}$. • Prove that $\widehat{R_{\mathcal{U}}}|_{W_{0}}:\mathbb{Z}^{2}\times
W_{0}\to W_{0}$ is a well-defined induced $\mathbb{Z}^{2}$-action. • Describe
$\widehat{R_{\mathcal{U}}^{{\boldsymbol{e}}_{1}}}|_{W_{0}}$ and
$\widehat{R_{\mathcal{U}}^{{\boldsymbol{e}}_{2}}}|_{W_{0}}$ as polygon
exchange transformations on $W_{0}$. Compare with the result obtained in
SageMath as follows:` • Describe $\widehat{R_{\mathcal{U}}}|_{W_{0}}$ as a
toral $\mathbb{Z}^{2}$-rotation on $\mathbb{R}^{2}/\Gamma_{1}$ with
$\Gamma_{1}=\mathbb{Z}\times(\varphi^{-1}\mathbb{Z})$. `

###  5.5. Toral partitions induced by toral $\mathbb{Z}^{2}$-rotations

For IETs, the interval on which we define the Rauzy induction is usually given
by one of the atom of the partition which defines the IET itself. In our
setting, it is not the case. The partition that we use carries more
information than the natural partition which allows to define the
$\mathbb{Z}^{2}$-rotation $R$ as a pair of polygon exchange transformations.
The partition is a refinement of the natural partition involving well-chosen
sloped lines.

Let $\Gamma$ be a lattice in $\mathbb{R}^{2}$ and
${\boldsymbol{T}}=\mathbb{R}^{2}/\Gamma$ be a $2$-dimensional torus. Let
$({\boldsymbol{T}},\mathbb{Z}^{2},R)$ be the dynamical system given by a
$\mathbb{Z}^{2}$-rotation $R$ on ${\boldsymbol{T}}$. Assuming the
$\mathbb{Z}^{2}$-rotation $R$ is Cartesian on a window
$W\subset{\boldsymbol{T}}$, then there exist two strictly increasing sequences
$r_{\boldsymbol{x}}^{(1)},r_{\boldsymbol{x}}^{(2)}:\mathbb{Z}\to\mathbb{Z}$
such that

$(r,s)=\left(r_{\boldsymbol{x}}^{(1)}(1),r_{\boldsymbol{x}}^{(2)}(1)\right)$

is the first return time of a starting point
${\boldsymbol{x}}\in{\boldsymbol{T}}$ to the window $W$ under the action $R$,
see Equation (10). It allows to define the return word map as

$\begin{array}[]{rccl}\textsc{ReturnWord}:&W&\to&\mathcal{A}^{*^{2}}\\
&{\boldsymbol{x}}&\mapsto&\left(\begin{array}[]{ccc}\textsc{Code}(R^{(0,s-1)}{\boldsymbol{x}})&\cdots&\textsc{Code}(R^{(r-1,s-1)}{\boldsymbol{x}})\\
\cdots&\cdots&\cdots\\
\textsc{Code}(R^{(0,0)}{\boldsymbol{x}})&\cdots&\textsc{Code}(R^{(r-1,0)}{\boldsymbol{x}})\end{array}\right)\end{array},$

where $r,s\geq 1$ both obviously depend on ${\boldsymbol{x}}$.

The image $\mathcal{L}=\textsc{ReturnWord}(W)\subset\mathcal{A}^{*^{2}}$ is a
language called the set of return words. We identify each return word in
$\mathcal{L}$ to a letter $b$ of an alphabet $\mathcal{B}$ in such a way that
$\mathcal{L}=\{w_{b}\}_{b\in\mathcal{B}}$. When the return time to $W$ is
bounded, the set of return words $\mathcal{L}$ is finite and the alphabet
$\mathcal{B}$ is finite. The example that we consider in this chapter are such
that the return time is bounded, but this is not true in general.

######  Remark 5.12.

The way the enumeration of $\mathcal{L}$ is done influences the substitutions
which are obtained afterward. To obtain a canonical ordering when the words
are 1-dimensional, we use the total order $(\mathcal{L},\prec)$ defined by
$u\prec v$ if $|u|<|v|$ or $|u|=|v|$ and $u<_{lex}v$.

The induced partition of $\mathcal{P}$ by the action of $R$ on the sub-domain
$W$ is a topological partition of $W$ defined as the set of preimage sets
under ReturnWord:

$\widehat{\mathcal{P}}|_{W}=\{\textsc{ReturnWord}^{-1}(w_{b})\}_{b\in\mathcal{B}}.$

This yields the induced coding on $W$

$\begin{array}[]{rccl}\textsc{Code}|_{W}:&W&\to&\mathcal{B}\\
&{\boldsymbol{y}}&\mapsto&b\quad\text{ if and only if
}\quad{\boldsymbol{y}}\in\textsc{ReturnWord}^{-1}(w_{b}).\end{array}$

A natural substitution comes out of this induction procedure:

(11) $\begin{array}[]{rccl}\omega:&\mathcal{B}&\to&\mathcal{A}^{*^{2}}\\
&b&\mapsto&w_{b}.\end{array}$

The partition $\widehat{\mathcal{P}}|_{W}$ of $W$ can be effectively computed
by the refinement of the partition $\mathcal{P}$ with translated copies of the
sub-domain $W$ under the action of $R$. In [Lab21b], we propose an algorithm
to compute the induced partition $\widehat{\mathcal{P}}|_{W}$ and substitution
$\omega$. An implementation of it in SageMath is provided in the optional
package slabbe [Lab20] and is used below on an example. The next result shows
that the coding of the orbit under the $\mathbb{Z}^{2}$-rotation $R$ is the
image under the 2-dimensional substitution $\omega$ of the coding of the orbit
under the $\mathbb{Z}^{2}$-action $\widehat{R}|_{W}$.

######  Lemma 5.13.

If the $\mathbb{Z}^{2}$-action $R$ is Cartesian on a window
$W\subset{\boldsymbol{T}}$, then $\omega$ is a $2$-dimensional morphism, and
for every ${\boldsymbol{x}}\in W$ we have

$\textsc{Config}^{\mathcal{P},R}_{{\boldsymbol{x}}}=\omega\left(\textsc{Config}^{\widehat{\mathcal{P}}|_{W},\widehat{R}|_{W}}_{{\boldsymbol{x}}}\right).$

###### Proof.

Let ${\boldsymbol{x}}\in W$. By hypothesis, there exist $P,Q\subset\mathbb{Z}$
such that the set of returns times satisfies
$\delta_{W}({\boldsymbol{x}})=P\times Q$ and we may write
$P=\{r_{i}\}_{i\in\mathbb{Z}}$ and $Q=\{s_{j}\}_{j\in\mathbb{Z}}$ as
increasing sequences such that $r_{0}=s_{0}=0$. Therefore,
$\textsc{Config}^{\mathcal{P},R}_{{\boldsymbol{x}}}$ may be decomposed into a
lattice of rectangular blocks. More precisely, for every $i,j\in\mathbb{Z}$,
the following block is the image of a letter under $\omega$:

$\displaystyle\left(\begin{array}[]{ccc}\textsc{Code}(R^{(r_{i},s_{j+1}-1)}{\boldsymbol{x}})&\cdots&\textsc{Code}(R^{(r_{i+1}-1,s_{j+1}-1)}{\boldsymbol{x}})\\
\cdots&\cdots&\cdots\\
\textsc{Code}(R^{(r_{i},s_{j})}{\boldsymbol{x}})&\cdots&\textsc{Code}(R^{(r_{i+1}-1,s_{j})}{\boldsymbol{x}})\end{array}\right)$
$\displaystyle\qquad=\textsc{ReturnWord}(R^{(r_{i},s_{j})}{\boldsymbol{x}})=w_{b_{ij}}=\omega(b_{ij})$