# Weakly and Strongly Aperiodic Subshifts of Finite Type on Baumslag-Solitar
Groups

###### Abstract

We study the periodicity of subshifts of finite type (SFT) on Baumslag-Solitar
groups. We show that for residually finite Baumslag-Solitar groups there exist
both strongly and weakly-but-not-strongly aperiodic SFTs. In particular, this
shows that unlike $\mathbb{Z}^{2}$, but like $\mathbb{Z}^{3}$, strong and weak
aperiodic SFTs are different classes of SFTs in residually finite BS groups.
More precisely, we prove that a weakly aperiodic SFT on BS(m,n) due to Aubrun
and Kari is, in fact, strongly aperiodic on BS(1,n); and weakly but not
strongly aperiodic on any other BS(m,n). In addition, we exhibit an SFT which
is weakly but not strongly aperiodic on BS(1,n); and we show that there exists
a strongly aperiodic SFT on BS(n,n).

## Introduction

The use of tilings as a computational model was initiated by Wang in the 60s
[20] as a tool to study specific classes of logical formulas. His model
consists in square tiles with colors on each side, that can be placed next to
each other if the colors match. Wang studied the tilings of the discrete
infinite plane ($\mathbb{Z}^{2}$) with these tiles, now called Wang tiles; a
similar model exists to tile the infinite line ($\mathbb{Z}$) with two-sided
dominoes. Wang realized that a key property of these tilings was the notion of
periodicity. At the time, it was already known that if a set of dominoes tiled
$\mathbb{Z}$, it was always possible to do it in a periodic fashion, and Wang
suspected that it was the same for Wang tiles on $\mathbb{Z}^{2}$. However, a
few years later, one of his students, Berger, proved otherwise by providing a
set of Wang tiles that tiled the plane but only aperiodically [5]. Numerous
aperiodic sets of Wang tiles have been provided by many since then (see for
example [18, 14, 13]).

The model of Wang tiles is actually equivalent to tilings using an arbitrary
finite alphabet with adjacency rules, and it has become a part of symbolic
dynamics, a more general way to encode a smooth dynamical system into symbolic
states and trajectories. This approach by discretization (see [10] for a
comprehensive historiography) is itself part of the field of discrete
dynamical systems. In this broader context, it is interesting to study the set
of all possible tilings for a given finite list of symbols and adjacency
rules, called a Subshift of Finite Type (SFT). $\mathbb{Z}$-SFTs have been
studied extensively, and many of their properties are known (see for example
[15]). $\mathbb{Z}^{d}$-SFTs (for $d\geq 2$) seem to be much more complex, as
many results from the unidimensional case cannot be directly transcribed to
higher dimensions. In recent years, the even wider class of SFTs built over
Cayley graphs of groups has been attracting more and more attention [6, 12,
1].

In this broader setting, many questions about periodicity are still open [6].
For example there are many groups for which we do not know if there exists a
non-empty SFT with only aperiodic configurations (called an aperiodic SFT).
Another relevant question is the relation between two notions of aperiodicity,
weak and strong aperiodicity: the first one requires all configurations to
have infinitely many distinct translates; the second one that no configuration
has any period whatsoever. They are equivalent for SFTs over $\mathbb{Z}$ or
$\mathbb{Z}^{2}$, but this is not the case for other groups (notably
$\mathbb{Z}^{3}$), and for many the relation is not even known.

Baumslag-Solitar groups of parameters $m$ and $n$, commonly denoted by
$BS(m,n)$, initially gathered interest in symbolic dynamics because of their
simple description and rich properties. Notably, their domino problem is
undecidable [3]; and Aubrun and Kari built a weakly aperiodic SFT in order to
prove it. Their proof is essentially sketched in the general case, where it
encodes piecewise affine maps, as it is done on $\mathbb{Z}^{2}$ in [14]. Only
the $BS(2,3)$ case is detailed in their paper; and an explicit period is
provided for a given configuration, which shows that the resulting SFT,
although weakly aperiodic, is not strongly aperiodic.

In the present paper, after a few definitions (Section 1); we thoroughly
reintroduce Aubrun and Kari’s construction in the general case, and provide a
precise proof of its weak aperiodicity by encoding piecewise linear maps
(Section 2) (although Aubrun and Kari sketched the proof for encoding
piecewise affine maps, only piecwise linear ones are needed for the
aperiodicity result). Then, we show that the resulting SFT is weakly but not
strongly aperiodic on any $BS(m,n)$ (Section 2.2) (as sketched in [3]); except
on $BS(1,n)$ where, with some extra work, we prove that it is strongly
aperiodic (Section 2.4). Then, using a different technique based on
substitutions on words, we exhibit a weakly but not strongly aperiodic SFT on
$BS(1,n)$ (Section 3). Finally, by using tools from group theory and a theorem
by Jeandel [12], we build a strongly aperiodic SFT on any $BS(n,n)$ (Section
4). These new results are summarized in the following table (in bold):

Group | Strongly aperiodic SFT | Weakly-not-strongly aperiodic SFT
---|---|---
$\mathbb{Z}^{2}$ | Yes (Berger [5]) | No (Folklore)
$BS(1,n)$ |  Yes, adapted from Aubrun-Kari (Section 2.4) |  Yes, using substitutions (Section 3)
$BS(n,n)$ |  Yes, using a theorem by Jeandel (Section 4) | Yes (Section 2.2, Aubrun-Kari [3])
$BS(m,n)$ | ? | Yes (Section 2.2, Aubrun-Kari [3])

The end result is that any residually finite Baumslag-Solitar group $BS(m,n)$
with $|m|\geq 2$ or $|n|\geq 2$ has a strongly aperiodic SFT and a weakly but
not strongly aperiodic SFT. The remaining question is whether a general
$BS(m,n)$ admits a strongly aperiodic SFT, when not in the $|m|=|n|$, $|m|=1$
or $|n|=1$ cases.

##  1 Definitions

###  1.1 Baumslag-Solitar groups

A group $G$ is said to be _finitely generated_ if it has a presentation
$G=\langle S\mid R\rangle$ with $S$ finite. Given a presentation $\langle
S\mid R\rangle$ of a group $G$, its (right) _Cayley graph_ is the graph
$\Gamma_{G}=(G,E_{\Gamma})$ whose vertices are the elements of $G$ and the
edges are of the form $(g,gs)$ with $g\in G$ and $s\in S\cup S^{-1}$ a
generator of $G$ or its inverse.

A group $G$ is said to be _residually finite_ if for any $g\in G$ that is not
the identity, there is a normal subgroup $N\vartriangleleft G$ of finite index
such that $g\notin N$.

The groups we are interested in in this paper are the _Baumslag-Solitar
groups_. They are defined, using two _nonzero_ integers $m,n$ as parameters,
by the presentation

$BS(m,n)=\langle a,b\mid ba^{m}b^{-1}=a^{n}\rangle.$

######  Proposition 1.1 (Meskin [16]).

$BS(m,n)$ is residually finite $\Leftrightarrow$ $|m|=1$ or $|n|=1$ or
$|m|=|n|$.

###  1.2 Subshifts and tilings

In a general sense, a _dynamical system_ is a set $S$ endowed with a topology
$U$ and on which a group acts; if $\mathbb{Z}$ acts on it by the iteration of
a function $f$, we may write $(S,U,f)$ instead of $(S,U,\mathbb{Z})$. Two
dynamical systems $(S,U,G)$ and $(T,V,G)$ are _conjugate_ if there exists a
continuous bijection $\phi\colon S\rightarrow T$ so that for any $s\in S$ and
any $g\in G$, $\phi(g\cdot s)=g\cdot\phi(s)$ (where $G$ acts, respectively, on
$S$ and on $T$).

Let $\mathcal{A}$ be a finite alphabet. Let $G$ be a finitely generated group
with presentation $\langle S\mid R\rangle$ and neutral element $e$. Let
$x\in\mathcal{A}^{G}$ and $g,h\in G$: $G$ naturally acts on the left on
$\mathcal{A}^{G}$ by $(g\cdot x)_{h}=x_{g^{-1}h}$. The set $\mathcal{A}^{G}$,
when endowed with the product topology $t$ and this action, forms a compact
dynamical system $(\mathcal{A}^{G},t,\cdot)$ called the _full shift_ over $G$.
We call $x\in\mathcal{A}^{G}$ a _configuration_.

A _pattern_ $p$ is a finite configuration $p\in\mathcal{A}^{P_{p}}$ where
$P_{p}\subset G$ is finite. We say that a pattern $p\in\mathcal{A}^{P_{p}}$
_appears_ in a configuration $x\in\mathcal{A}^{G}$ – or that $x$ _contains_
$p$ – if there exists $g\in G$ such that for every $h\in P_{p}$, $(g\cdot
x)_{h}=p_{h}$, in this case we write $p\sqsubset x$.

The _subshift_ associated to a set of patterns ${\mathcal{F}}$, called set of
_forbidden patterns_ , is defined by

$X_{\mathcal{F}}=\\{x\in\mathcal{A}^{G}\mid\forall
p\in\mathcal{F},p\not\sqsubset x\\}$

that is, $X_{\mathcal{F}}$ is the set of all configurations that do not
contain any pattern from ${\mathcal{F}}$. Note that there can be several sets
of forbidden patterns defining the same subshift $X$. A subshift can
equivalently be defined as a closed set under both the topology and the
$G$-action.
If $X=X_{\mathcal{F}}$ with ${\mathcal{F}}$ finite, then $X$ is called a
_Subshift of Finite Type_ , SFT for short.

Let $X$ be a subshift on a group $G$ and $x\in X$. The _orbit_ of $x$ is
${Orb_{G}(x)=\\{g\cdot x\mid g\in G\\}}$ and its _stabilizer_
$Stab_{G}(x)=\\{g\in G\mid g\cdot x=x\\}$. We say that $x$ is a _strongly
periodic configuration_ if $|Orb_{G}(x)|<+\infty$, and that $x$ is a _weakly
periodic configuration_ if $Stab_{G}(x)\neq\\{e\\}$. If no configuration in
$X$ is strongly periodic and the subshift is non-empty, then the subshift is
said to be _weakly aperiodic_. If no configuration in $X$ is weakly periodic
and the subshift is non-empty, then the subshift is said to be _strongly
aperiodic_.

A particular class of SFTs is obtained by considering Wang tiles over the
Cayley graph of the group. This can be done for any finitely generated group,
and it turns out that any SFT can be encoded into an equivalent set of Wang
tiles. In order to make the definitions shorter, we limit ourselves to the
definition of Wang tiles over $BS(m,n)$. A _Wang tileset_ is a particular SFT
where the alphabet is a set of _Wang tiles_ $\tau$, which are tuples of colors
of the form
$s=(t_{1}^{s},\dots,t_{m}^{s},l^{s},r^{s},b_{1}^{s},\dots,b_{n}^{s})$. To make
notations easier, we denote:

$\displaystyle s(\text{top}_{1})$ $\displaystyle=t_{1}^{s}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \vdots$ $\displaystyle
s(\text{top}_{m})$ $\displaystyle=t_{m}^{s}$ $\displaystyle s(\text{left})$
$\displaystyle=l^{s}$ $\displaystyle s(\text{right})$ $\displaystyle=r^{s}$
$\displaystyle s(\text{bottom}_{1})$ $\displaystyle=b_{1}^{s}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \vdots$ $\displaystyle
s(\text{bottom}_{n})$ $\displaystyle=b_{n}^{s}$

Figure 1: A Wang tile of $BS(m,n)$

A _tiling_ is then a configuration $T\in\tau^{BS(m,n)}$ over the group using
the alphabet $\tau$. We say that a tiling is _valid_ if the colors of
neighboring tiles match. That is, for any $g\in BS(m,n)$ and $T_{g}$ the
associated tile at position $g$, we must have:

$\displaystyle T_{g}(\text{right})$ $\displaystyle=T_{ga^{m}}(\text{left})$
$\displaystyle T_{g}(\text{top}_{k})$
$\displaystyle=T_{ga^{k-l}b}(\text{bottom}_{l})$

for any $k\in\\{1,\dots,m\\}$ and $l\in\\{1,\dots,n\\}$.

Figure 2: Illustration of the neighbor rules for $BS(2,2)$.

See Fig. 2 for an illustration of these rules.
The set of all valid tilings for a tileset $\tau$ forms an SFT $X^{\tau}$,
since the tileset gives a finite number of local constraints based on a finite
alphabet. In general, it is not necessarily simpler to consider Wang tilesets
instead of local constraints on the Cayley graph; however, in [3] the
construction heavily uses the visual representation of tiles with numbers on
the top and bottom that encode a multiplication by a real number, and this
article will do the same.

###  1.3 Substitutions

Let $\mathcal{A}^{*}$ be the set of (finite) words over $\mathcal{A}$. A
_substitution_ (or morphism) is a map
$s\colon\mathcal{A}\rightarrow\mathcal{A}^{*}$. We say it is _uniform_ of size
$n\in\mathbb{N}$ if for every $a\in\mathcal{A},|s(a)|=n$. The substitution $s$
can be extended to $\mathcal{A}^{*}$ by applying it to each letter of the word
and concatenating the resulting words. We can also extend $s$ to
$\mathcal{A}^{\mathbb{N}_{0}}$ (resp. $\mathcal{A}^{\mathbb{N}}$) by doing the
same, concatenating infinitely many words, the first letter of the first word
being at position $0$ (resp. $1$). Finally, $s$ can be extended to _pointed_
biinfinite words (so on $\mathcal{A}^{\mathbb{Z}}$ in a certain way) as
illustrated in Fig. 3.

Figure 3: How a substitution is applied to a biinfinite word: $y=s(x)$ with
$s$ a uniform substitution of size $n$

For $a\in\mathcal{A}$ with $s(a)=aw$ with $w\in\mathcal{A}^{*}$, we define the
_positive infinite iteration_ of $s$ on $a$:

$\overrightarrow{{s}^{\omega}}(a)=a\leavevmode\nobreak\ w\leavevmode\nobreak\
s(w)\leavevmode\nobreak\ s^{2}(w)\cdots\in\mathcal{A}^{\mathbb{N}_{0}}.$

In the same way, we define the _negative infinite iteration_ of $s$ on $a$:

$\overleftarrow{\leavevmode\nobreak\ {}^{\omega}s}(a)=\cdots
s^{2}(w)\leavevmode\nobreak\ s(w)\leavevmode\nobreak\ w\leavevmode\nobreak\
a\in\mathcal{A}^{\mathbb{Z}^{-}}.$

For a word $u$ (possibly biinfinite), we define its factor complexity

$P_{u}(n)=|\\{w\in\mathcal{A}^{n}\mid w\sqsubset u\\}|$

where $w\sqsubset u$ indicates that $w$ is a subword of $u$. The factor
complexity of a biinfinite word is bounded if and only if that word is
periodic [7], that is, if it is made of the same finite word concatenated
infinitely many times.

A _fixpoint_ of a substitution $s$ is a (possibly biinfinite) word $u$ such
that $s(u)=u$.

##  2 On a construction by Aubrun and Kari

In [3], Aubrun and Kari provide a weakly aperiodic Wang tileset on Baumslag-
Solitar groups, with a proof focusing on the specific case of $BS(2,3)$, for
which they also present a period for one specific configuration, implying that
the corresponding Wang tileset is not strongly aperiodic.

A more general version of the construction can be found in [4]. We repeat most
of it here for the sake of completeness, since we study that construction in
more details to obtain additional results: we will show that it yields a
weakly but not strongly aperiodic SFT on any $BS(m,n)$ with $|m|\neq 1$ and
$|n|\neq 1$, and a strongly aperiodic SFT on any $BS(1,n)$.

###  2.1 Aubrun and Kari’s construction

Aubrun and Kari’s construction works by encoding orbits of piecewise affine
maps applied to real numbers. We will only apply their construction for
piecewise linear maps, and begin this section with the necessary definitions.

####  2.1.1 Definitions

######  Definition 2.1 ((Representation by a sequence)).

Let $i\in\mathbb{Z}$. We say that a binary biinfinite sequence
$(x_{k})_{k\in\mathbb{Z}}\in\\{i,i+1\\}^{\mathbb{Z}}$ _represents_ a real
number $x\in[i,i+1]$ if there exists a growing sequence of intervals
$I_{1}\subset I_{2}\subset\dots\subseteq\mathbb{Z}$ of size at least
$1,2,\dots$ such that:

$\lim\limits_{k\to+\infty}\dfrac{\sum_{j\in I_{k}}x_{j}}{|I_{k}|}=x.$

Note that if $(x_{k})_{k\in\mathbb{Z}}$ is a representation of $x$, all the
shifted sequences $(x_{l+k})_{k\in\mathbb{Z}}$ for every $l\in\mathbb{Z}$ are
also representations of $x$. Note that a sequence $(x_{k})_{k\in\mathbb{Z}}$
can a priori represent several distinct real numbers since different choices
of interval sequences may make it converge to different points. A sequence
always represents at least one real number by compactness of $[i,i+1]$.

Then, we define a generalization of piecewise linear maps: multiplicative
systems. The main difference with piecewise linear maps is that points may
have several images as definition intervals of different pieces might overlap.

######  Definition 2.2 (Multiplicative system).

A _multiplicative system_ is a finite set of non-zero linear maps

$\mathcal{S}=\\{f_{1}:I_{1}\rightarrow
I^{\prime}_{1},\ldots,f_{k}:I_{k}\rightarrow I^{\prime}_{k}\\}$

with $I_{i}$ and $I^{\prime}_{i}$ closed intervals of $\mathbb{R}$. Its
_inverse_ is defined to be

$\mathcal{S}^{-1}=\\{f_{1}^{-1}:I^{\prime}_{1}\rightarrow
I_{1},\ldots,f_{k}^{-1}:I^{\prime}_{k}\rightarrow I_{k}\\}.$

The _image_ of $x\in\bigcup_{i}I_{i}$ is the set

$\mathcal{S}(x)=\\{y\in\bigcup_{j}I^{\prime}_{j}\mid\exists i,f_{i}(x)=y\\}.$

The _$k$ -th iteration_ of $\mathcal{S}$ on $x\in\bigcup_{i}I_{i}$ is then:

$\begin{cases}\\{y\in\mathbb{R}\mid\exists
i_{1},\ldots,i_{k},f_{i_{k}}\circ\cdots\circ f_{i_{1}}(x)=y\\}&\text{if
}k>0\\\ x&\text{if }k=0\\\ \\{y\in\mathbb{R}\mid\exists
i_{-1},\ldots,i_{-k},f^{-1}_{i_{-k}}\circ\cdots\circ
f^{-1}_{i_{-1}}(x)=y\\}&\text{if }k<0\\\ \end{cases}.$

Note that if none of the intervals overlap, $\mathcal{S}$ can be represented
as a piecewise linear function and the definition of inverse and iteration
coincide with the usual ones.

######  Definition 2.3 ((Immortal and periodic points)).

Let $\mathcal{S}=\\{f_{1}:I_{1}\rightarrow
I^{\prime}_{1},\ldots,f_{k}:I_{1}\rightarrow I^{\prime}_{k}\\}$ be a
multiplicative system. The real $x\in\mathbb{R}$ is _immortal_ if for all
$k\in\mathbb{Z}$,

$\mathcal{S}^{k}(x)\cap\bigcup_{i}I_{i}\neq\emptyset$

A _periodic point_ for this system is a point $x\in\mathbb{R}$ such that there
exists $k\in\mathbb{N}^{*}$ such that

$x\in\mathcal{S}^{k}(x).$

######  Definition 2.4 ((Level)).

The _level_ of $g\in BS(m,n)$ is the set $\mathcal{L}_{g}=\\{ga^{k}\mid
k\in\mathbb{Z}\\}$.

When considering a tiling of $BS(m,n)$, given a line of tiles located between
levels $\mathcal{L}_{g}$ and $\mathcal{L}_{gb^{-1}}$, we talk about the upper
side of the line to refer to level $\mathcal{L}_{g}$, and the lower side of
the line to refer to level $\mathcal{L}_{gb^{-1}}$.

######  Definition 2.5 ((Height)).

The _height_ of $g\in BS(m,n)$ is, for any way of writing it as a word in
$\\{a,b,a^{-1},b^{-1}\\}^{*}$, its number of $b$’s minus its number of
$b^{-1}$’s; it is denoted as $||g||_{b}$.

Since the only basic relation in $BS(m,n)$ uses one $b$ and one $b^{-1}$, all
writings of $g$ as a word give the same height. Furthermore, it is actually
the height of all elements in its level.

######  Definition 2.6 ((Multiplying tileset)).

A set of tiles $\tau$ _multiplies_ by $q\in\mathbb{Q}$ if for any tile
$(t_{1},\dots,t_{m},l,r,b_{1},\dots,b_{n})\in\tau$ (see Fig. 1 for the
notation),

$q\frac{t_{1}+\cdots+t_{m}}{m}+l=\frac{b_{1}+\cdots+b_{n}}{n}+r.$ (1)

Let $\tau$ be a tileset multiplying by $q\in\mathbb{Q}$. If we consider a line
of $N$ tiles of $\tau$ next to each other without tiling errors (as defined in
Section 1.2), as left and right colors match, we can average Eq. 1:

$qt+\frac{l}{N}=b+\frac{r}{N}.$ (2)

where $t$ is the average of the top labels of the line and $b$ the average of
the bottom ones. Therefore, if an infinite line has its upper side
representing $x\in\mathbb{R}$ and its lower side representing
$y\in\mathbb{R}$, taking the limit of Eq. 2 on a well chosen sequence of
intervals gives:

$qx=y.$

Hence the name of _multiplying tileset_ for $\tau$.

####  2.1.2 A multiplying tileset

Let us define, in a fashion similar to [3], a couple of useful functions to
build a multiplying tileset. Let
$\alpha_{m,n}:\\{a,b,a^{-1},b^{-1}\\}^{*}\rightarrow\mathbb{R}$ (or just
$\alpha$ when $m$ and $n$ are clear) be defined by the recursion:

$\displaystyle\begin{cases}\alpha(\varepsilon)=0\text{ where
}\varepsilon\text{ is the empty word}\\\
\alpha(wb)=\alpha(wb^{-1})=\alpha(w)\\\
\alpha(wa)=\alpha(w)+\left(\frac{n}{m}\right)^{||w||_{b}}\\\
\alpha(wa^{-1})=\alpha(w)-\left(\frac{n}{m}\right)^{||w||_{b}}.\end{cases}$

The map $\alpha$ can be extended to elements of $BS(m,n)$, due to the fact
that $\alpha(uba^{m}b^{-1}v)=\alpha(ua^{n}v)$ for any pair of words $u$ and
$v$ in $\\{a,b,a^{-1},b^{-1}\\}^{*}$: $\alpha(g)$ is then $\alpha(w)$ for any
word representing $g$ in the group.

Now, we define $\Phi:BS(m,n)\rightarrow\mathbb{R}^{2}$ as follows:

$\Phi(g)=\left(\alpha(g),||g||_{b}\right).$

The function $\Phi$ can be seen as a projection of every element of $BS(m,n)$
on the euclidean plane $\mathbb{R}^{2}$.

Finally, let $\lambda:BS(m,n)\rightarrow\mathbb{R}$ be defined as

$\lambda(g)=\frac{1}{m}\left(\frac{m}{n}\right)^{||g||_{b}}\alpha(g).$

Let $q\in\mathbb{Q}$ and $I$ an interval, let

$\displaystyle t_{j}(g,x)$
$\displaystyle:=\lfloor\left(m\lambda(g)+j\right)x\rfloor-\lfloor\left(m\lambda(g)+(j-1)\right)x\rfloor\text{\leavevmode\nobreak\
\leavevmode\nobreak\ for }j=1\dots m$ $\displaystyle b_{j}(g,x)$
$\displaystyle:=\lfloor\left(n\lambda(g)+j\right)qx\rfloor-\lfloor\left(n\lambda(g)+(j-1)\right)qx\rfloor\text{\leavevmode\nobreak\
\leavevmode\nobreak\ for }j=1\dots n$ $\displaystyle l(g,x)$
$\displaystyle:=\frac{1}{m}q\lfloor m\lambda(g)x\rfloor-\frac{1}{n}\lfloor
n\lambda(g)qx\rfloor$ $\displaystyle r(g,x)$
$\displaystyle:=\frac{1}{m}q\lfloor\left(m\lambda(g)+m\right)x\rfloor-\frac{1}{n}\lfloor\left(n\lambda(g)+n\right)qx\rfloor$

Then, we define the tileset $\tau_{q,I}$ as:

$\tau_{q,I}=\\{(t_{1}(g,x),\ldots,t_{m}(g,x),l(g,x),r(g,x),b_{1}(g,x),\ldots,b_{m}(g,x))\mid
g\in BS(m,n),x\in I\\}.$

Figure 4: One tile from the tileset $\tau_{q,I}$.

One can show that Eq. 1 holds for these tiles.

######  Proposition 2.1 ([4, Proposition 6]).

Let $a\in\mathbb{Z}$, for any $I\subseteq[a,a+1]$, $\tau_{q,I}$ is a tileset
that multiplies by $q$.

Let us define the _balanced representation of $x$_, which is the biinfinite
sequence defined for any $z\in\mathbb{R}$ by

$B_{j}(x,z)=\left\lfloor(z+j)x\right\rfloor-\left\lfloor(z+j-1)x\right\rfloor.$

Note that $B_{j}(x,z)$ does not depends on $z$, and can only take two values:
$\lfloor x\rfloor$ or $\lfloor x\rfloor+1$.

######  Proposition 2.2.

Let $q\in\mathbb{Q},a\in\mathbb{Z}$ and $I\subseteq[a,a+1]$. The upper side of
any tile in $\tau_{q,I}$ is of the form

$B_{j}(x,m\lambda(g)),B_{j+1}(x,m\lambda(g)),\ldots,B_{j+m}(x,m\lambda(g));$

for $x\in I,j\in\mathbb{Z},g\in BS(m,n)$. In particular, its labels are in
$\\{a,a+1\\}$. The lower side is of the form

$B_{j}(qx,m\lambda(gb^{-1})),B_{j+1}(qx,m\lambda(gb^{-1})),\ldots,B_{j+n}(qx,m\lambda(gb^{-1})).$

###### Proof.

Rewriting the top labels using balanced representation yields

$B_{j}(x,m\lambda(g)),B_{j+1}(x,m\lambda(g)),\ldots,B_{j+m}(x,m\lambda(g)).$

Since each $B_{j}(x,m\lambda(g))$ is either $\lfloor x\rfloor$ or $\lfloor
x\rfloor+1$, and $x\in[a,a+1]$, one obtains labels in $\\{a,a+1\\}$. For the
bottom side, note that $\lambda(gb^{-1})=\frac{n}{m}\lambda(g)$, which gives
labels

$B_{j}(qx,m\lambda(gb^{-1})),B_{j+1}(qx,m\lambda(gb^{-1})),\ldots,B_{j+n}(qx,m\lambda(gb^{-1})).$

∎

For our purpose we need to have a finite tileset, because subshifts use a
finite alphabet.

######  Proposition 2.3.

Let $a\in\mathbb{Z}$, for any $I\subseteq[a,a+1]$ the tileset $\tau_{q,I}$ is
finite.

###### Proof.

Proposition 2.2 gives us that there are finitely many top and bottom labels.
It remains to prove that there are also finitely many left and right labels.

First of all, one can check that $\lambda(ga^{m})=\lambda(g)+1$, and so
$l(ga^{m},x)=r(g,x)$. Consequently, we simply have to prove that $l$ lies in a
finite set. Let $q=\frac{q_{1}}{q_{2}}$ with $q_{1},q_{2}\in\mathbb{Z}$, and
write

$l(g,x)=\frac{nq\lfloor m\lambda(g)x\rfloor-m\lfloor
n\lambda(g)qx\rfloor}{mn}=\frac{nq_{1}\lfloor m\lambda(g)x\rfloor-
mq_{2}\lfloor n\lambda(g)qx\rfloor}{mnq_{2}}.$

Since its numerator is an integer bounded by $-nq_{1}=:k_{1}$ from below and
$mq_{2}=:k_{2}$ from above using usual inequalities on the floor function, we
have that for any $g\in BS(m,n),x\in I$, $l(g,x)$ is in the finite set

$\left\\{\frac{k_{1}}{mnq_{2}},\frac{k_{1}+1}{mnq_{2}},\ldots,\frac{k_{2}}{mnq_{2}}\right\\}.$

∎

Thanks to the multiplying property of $\tau_{q,[a,a+1]}$, we can use it to
encode multiplicative systems in such a way that non-empty tilings corresponds
to immortal points of the system. If we modify the tileset a little bit, we
can encode multiplying systems defined on other intervals than $[a,a+1].$

######  Theorem 2.4.

Let $\mathcal{S}=\\{f_{1},\ldots,f_{N}\\}$ be a multiplicative system with

$\displaystyle f_{i}:$ $\displaystyle I_{i}\rightarrow\mathbb{R}$
$\displaystyle x\mapsto q_{i}x,$

$q_{i}\in\mathbb{Q}$ and $I_{i}$ interval with rational bounds included in
some $[a_{i},a_{i}+1],a_{i}\in\mathbb{Z}$. We can explicitly and
algorithmically build an SFT $Y_{\mathcal{S}}$ with the following properties:

  1. 1.

any top of a line of tiles in a configuration $y\in Y_{\mathcal{S}}$
represents at least one real $x\in\bigcup_{i}I_{i}$.

  2. 2.

if the top of a line of tiles represents a real $x\in\bigcup_{i}I_{i}$, then
the bottom of that line represents a real in $\mathcal{S}(x)$;

  3. 3.

$Y_{\mathcal{S}}\neq\emptyset$ if and only if $\mathcal{S}$ has an immortal
point;

###### Proof.

We build a tileset $\tau$ performing the computation by the linear functions
$f_{i}:[a_{i},a_{i}+1]\rightarrow\mathbb{R}$; i.e. the linear maps with bigger
intervals than the ones defining $\mathcal{S}$. In order to encode the
multiplication correctly, one cannot simply take the union of all
$\tau_{i}:=\tau_{q_{i},[a_{i},a_{i}+1]}$, because tiles coming from different
$f_{i}$ could be mixed on a single line. In order to ”synchronize” the
computations on every line, we create a product alphabet with the left and
right colors of the tiles, and the number of the current function being used.
This ensures that one line can have tiles from only one of the
$\tau_{q_{i},[a_{i},a_{i}+1]}$. Formally,

$\tau=\left\\{(t_{1},\dots,t_{m},(l,i),(r,i),b_{1},\dots,b_{n})\mid(t_{1},\dots,t_{m},l,r,b_{1},\dots,b_{n})\in\tau_{q_{i},[a_{i},a_{i}+1]}\right\\}.$

This way, we can interpret any line of a tiling by $\tau$ as being ”of color”
$i$ for some $i\in\\{1,\dots,N\\}$.

Next, we restrict the intervals of reals that can be represented in each line
of the SFT. Let us write
$I_{i}=[a_{i}+\frac{d_{1}^{i}}{e_{1}^{i}},a_{i}+1-\frac{d_{2}^{i}}{e_{2}^{i}}]$,
for each $i$. $Y_{\mathcal{S}}$ will be $X^{\tau}$ with the following
additional local constraints: on each line of color $i$, we force the upper
side labels to respect

•every $e_{1}^{i}$ consecutive labels must contain at least $d_{1}^{i}$ labels
$a_{i}+1$; (3) •every $e_{2}^{i}$ consecutive labels must contain at least
$d_{2}^{i}$ labels $a_{i}$. (4)

Recall that the top labels of any line of color $i$ only has labels $a_{i}$
and $a_{i}+1$ by definition of $\tau_{i}$. From this, we can also deduce

•every $e_{1}^{i}$ consecutive labels must contain at most
$e_{1}^{i}-d_{1}^{i}$ labels $a_{i}$; •every $e_{2}^{i}$ consecutive labels
must contain at most $e_{2}^{i}-d_{2}^{i}$ labels $a_{i}+1$.

Since these constraints are on $e_{1}^{i}$ or $e_{2}^{i}$ consecutive labels,
and any other constraint from the $\tau_{i}$’s is on neighboring tiles,
$Y_{\mathcal{S}}$ is an SFT.

First, assume that $Y_{\mathcal{S}}$ is non-empty and contains some
configuration $y$. Then, the sequence at the top of each level
$\mathcal{L}_{b^{k}},k\in\mathbb{Z}$ represents at least one real $x_{k}$,
since it is a sequence made of at most two integers. Thanks to the multiplying
property of each $\tau_{i}$ (Proposition 2.1), and the fact that the local
rules of every line impose that any real represented belongs to an interval
$I_{i}$, $(x_{k})_{k\in\mathbb{Z}}$ is an infinite orbit of $\mathcal{S}$.
Indeed, consider a real $x$ represented by the upper side of a line of color
$i$. We prove that $x\in
I_{i}=[a+\frac{d_{1}}{e_{1}},a+1-\frac{d_{2}}{e_{2}}]$ (we drop the $i$ in
this paragraph to make notations lighter). Let us write
$(J_{l})_{l\in\mathbb{N}}$ the intervals from Definition 2.1 (denoted as
$(I_{i})$ there) on which we compute the mean for the represented real, and
let $r_{l}$ denote the proportion of $a$’s over $(a+1)$’s in the line
representing $x$ restricted to $J_{l}$. Thanks to the two conditions Eq. 3 and
Eq. 4 (and the two we deduced), we have, for all $l$ in $\mathbb{N}$,

$\frac{d_{2}}{e_{2}-d_{2}}\leq r_{l}\leq\frac{e_{1}-d_{1}}{d_{1}}.$ (5)

Moreover, since $x$ is the limit of the means computed on each $J_{l}$, one
can show that

$x=\lim_{l\rightarrow\infty}a+\frac{1}{1+r_{l}}.$

Using the left inequality of Eq. 5 gives that

$\frac{1}{1+r_{l}}\leq\frac{e_{2}-d_{2}}{e_{2}}=1-\frac{d_{2}}{e_{2}}.$

So

$x\leq a+1-\frac{d_{2}}{e_{2}}.$

Similarly, the right inequality of Eq. 5 gives

$x\geq a+\frac{d_{1}}{e_{1}},$

and so $x\in I_{i}$. This notably ensures Item 1 and, by the use of the
$\tau_{i}$’s, Item 2.

Now, assume that $S$ has an immortal point $x$. Then there exists a sequence
$(i_{k})_{k\in\mathbb{Z}}\in\\{1,\dots,N\\}^{\mathbb{Z}}$ such that if we
define

$x_{k}=\begin{cases}x&\text{if }k=0\\\
f_{i_{k-1}}(x_{k-1})=q_{i_{k-1}}x_{k-1}&\text{if }k>0\\\
f^{-1}_{i_{k}}(x_{k+1})=\frac{1}{q_{i_{k}}}x_{k+1}&\text{if }k<0\\\
\end{cases},$

then for all $k\in\mathbb{Z},x_{k}\in\bigcup_{i}I_{i}$. For every $g\in
BS(m,n)$, we place at $g$ a tile from the tileset $\tau_{i_{k}}$ with
$k=-||g||_{b}$, with colors:

$\displaystyle t_{j}:t_{j}(g,x_{k})$
$\displaystyle=\lfloor\left(m\lambda(g)+j\right)x_{k}\rfloor-\lfloor\left(m\lambda(g)+(j-1)\right)x_{k}\rfloor\text{\leavevmode\nobreak\
\leavevmode\nobreak\ for }j=1\dots m$ $\displaystyle b_{j}:b_{j}(g,x_{k})$
$\displaystyle=\lfloor\left(n\lambda(g)+j\right)q_{i_{k}}x_{k}\rfloor-\lfloor\left(n\lambda(g)+(j-1)\right)q_{i_{k}}x_{k}\rfloor\text{\leavevmode\nobreak\
\leavevmode\nobreak\ for }j=1\dots n$ $\displaystyle l:l(g,x_{k})$
$\displaystyle=\left(\frac{1}{m}q_{i_{k}}\lfloor
m\lambda(g)x_{k}\rfloor-\frac{1}{n}\lfloor
n\lambda(g)q_{i_{k}}x_{k}\rfloor,\leavevmode\nobreak\ i_{k}\right)$
$\displaystyle r:r(g,x_{k})$
$\displaystyle=\left(\frac{1}{m}q_{i_{k}}\lfloor\left(m\lambda(g)+m\right)x_{k}\rfloor-\frac{1}{n}\lfloor\left(n\lambda(g)+n\right)q_{i_{k}}x_{k}\rfloor,\leavevmode\nobreak\
i_{k}\right)$

These tiles are obviously from the tileset $\tau$. Recall that we have

$\lambda(ga^{m})=\lambda(g)+1,$ (6)

$\lambda(gb)=\frac{m}{n}\lambda(g).$

And therefore,

$\displaystyle l(ga^{m},x_{k})$ $\displaystyle=\left(\frac{1}{m}q\lfloor
m\lambda(ga^{m})x_{k}\rfloor-\frac{1}{n}\lfloor
n\lambda(ga^{m})qx_{k}\rfloor,\leavevmode\nobreak\ i_{k}\right)$
$\displaystyle=\left(\frac{1}{m}q_{i_{k}}\lfloor
m(\lambda(g)+1)x_{k}\rfloor-\frac{1}{n}\lfloor
n(\lambda(g)+1)q_{i_{k}}x_{k}\rfloor,\leavevmode\nobreak\
i_{k}\right)=r(g,x_{k}),$

and for any $j\in\\{1,\dots,m\\},p\in\\{1,\dots,n\\}$,

$\displaystyle b_{p}(ga^{j-p}b,x_{-||ga^{j-p}b||_{b}})$
$\displaystyle=\left\lfloor\left(n\lambda(ga^{j-p}b)+p\right)q_{i_{-||ga^{j-p}b||_{b}}}x_{-||ga^{j-p}b||_{b}}\right\rfloor-\left\lfloor\left(n\lambda(ga^{j-p}b)+(p-1)\right)q_{i_{-||ga^{j-p}b||_{b}}}x_{-||ga^{j-p}b||_{b}}\right\rfloor$
$\displaystyle=\left\lfloor\left(n\frac{m}{n}\lambda(ga^{j-p})+p\right)q_{i_{-||g||_{b}-1}}x_{-||g||_{b}-1}\right\rfloor-\left\lfloor\left(n\frac{m}{n}\lambda(ga^{j-p})+(p-1)\right)q_{i_{-||g||_{b}-1}}x_{-||g||_{b}-1}\right\rfloor$
$\displaystyle=\left\lfloor\left(m(\lambda(g)+\frac{j-p}{m})+p\right)q_{i_{-||g||_{b}-1}}x_{-||g||_{b}-1}\right\rfloor-\left\lfloor\left(m(\lambda(g)+\frac{j-p}{m})+(p-1)\right)q_{i_{-||g||_{b}-1}}x_{-||g||_{b}-1}\right\rfloor$
$\displaystyle=\left\lfloor\left(m\lambda(g)+j\right)q_{i_{-||g||_{b}-1}}x_{-||g||_{b}-1}\right\rfloor-\left\lfloor\left(m\lambda(g)+(j-1)\right)q_{i_{-||g||_{b}-1}}x_{-||g||_{b}-1}\right\rfloor$
$\displaystyle=\left\lfloor\left(m\lambda(g)+j\right)x_{-||g||_{b}}\right\rfloor-\left\lfloor\left(m\lambda(g)+(j-1)\right)x_{-||g||_{b}}\right\rfloor$
$\displaystyle=t_{j}(g,x_{-||g||_{b}})$

It remains to show that the labels at the top of every line follow the
conditions (3) and (4). Fix some $g\in BS(m,n)$ and consider the level
$\mathcal{L}_{g}$. Fix $k=-||g||_{b}$, denote $x:=x_{k}$, $i:=i_{k}$ and drop
the $i$ in the other variables to simplify notations. For $j\in\mathbb{Z}$, we
write $w_{j}$ for the label at position $j$ of the considered level, with
$t_{1}(g,x_{k})$ being position $1$. Remark that

$w_{j}=\lfloor\left(m\lambda(g)+j\right)x\rfloor-\lfloor\left(m\lambda(g)+(j-1)\right)x\rfloor$

holds for all $j\in\mathbb{Z}$ thanks to Eq. 6. Assume that $x\geq
a+\frac{d_{1}}{e_{1}}$. Let us write $N_{j_{0}}$ the number of labels $a$ that
appear in the word $u=w_{j_{0}+1}w_{j_{0}+2}\cdots w_{j_{0}+e_{1}}$. If we sum
all the labels of $u$, we have on the one hand

$\sum_{j=j_{0}+1}^{j_{0}+e_{1}}w_{j}=N_{j_{0}}a+(e_{1}-N_{j_{0}})(a+1)=e_{1}(a+1)-N_{j_{0}}.$

And on the other hand,

$\sum_{j=j_{0}+1}^{j_{0}+e_{1}}w_{j}=\lfloor\left(m\lambda(g)+j_{0}+e_{1}\right)x\rfloor-\lfloor\left(m\lambda(g)+j_{0}\right)x\rfloor.$

Therefore,

$e_{1}(a+1)-N_{j_{0}}>\left(m\lambda(g)+j_{0}+e_{1}\right)x-1-\left(m\lambda(g)+j_{0}\right)x=e_{1}x-1\geq
e_{1}a+d_{1}-1,$

which can be rearranged to

$N_{j_{0}}\leq e_{1}-d_{1},$

which implies (3). In the same way, if we assume $x\leq
a+1-\frac{d_{2}}{e_{2}}$, we can show $N_{j_{0}}\geq d_{2}$, which is exactly
(4). This shows Item 3. ∎

######  Remark 2.5.

Instead of considering a multiplicative system with rational bounds for the
intervals, one can dilate them and encode a dilated system with integer
bounds, which is equivalent to the original. For instance, instead of using a
linear function $f$ on $[a+\frac{d_{1}}{e_{1}},a+1-\frac{d_{2}}{e_{2}}]$, one
can consider that function $f$ multiplied by $e_{1}e_{2}$, on
$[ae_{1}e_{2}+d_{1}e_{2},ae_{1}e_{2}+e_{1}e_{2}-d_{2}e_{1}]$ which has integer
bounds. However, although this would yield a shorter proof, the results would
only hold through some sort of conjugation, and we wanted to effectively build
a Wang tileset for any multiplicative system.

Note that we only build a multiplying tileset in the current paper. Aubrun and
Kari provided the details of the encoding of any finite set of affine maps
into a tileset of $BS(m,n)$ in [4].

###  2.2 A weakly aperiodic SFT on $BS(m,n)$

The SFT $Y_{\mathcal{S}}$ previously defined on a given $BS(m,n)$ is also
linked to the periodicity of $\mathcal{S}$.

######  Theorem 2.6.

If $\mathcal{S}$ has no periodic point, then $Y_{\mathcal{S}}$ is a weakly
aperiodic SFT.

###### Proof.

We prove the contrapositive.

Assume that $Y_{S}$ has a strongly periodic configuration $y$, i.e.
$|Orb_{BS(m,n)}(y)|=i$ with $i\in\mathbb{N}$. In particular, each set
$\\{ga^{k}g^{-1}\cdot y\mid k\in\mathbb{Z}\\}$ is finite of cardinality lesser
than $i$, and therefore for every $g\in BS(m,n)$, there exists $k_{g}\leq i$
such that $ga^{k_{g}}g^{-1}\cdot y=y$. If we define $p=i!$, we obtain that for
all $g\in BS(m,n)$, $ga^{p}g^{-1}\cdot y=y$.

Let $g\in BS(m,n)$. Let $h\in\mathcal{L}_{g}$, i.e. there exists some
$k\in\mathbb{Z}$ so that $h=ga^{k}$. Then

$\displaystyle y_{h}$ $\displaystyle=(ga^{p}g^{-1}\cdot y)_{h}$
$\displaystyle=y_{ga^{-p}g^{-1}h}$ $\displaystyle=y_{ga^{k-p}}$
$\displaystyle=y_{ha^{-p}}$

which means that the level $\mathcal{L}_{g}$ is $p$-periodic.

Therefore any level is $p$-periodic, and consequently represents a unique
rational number $\frac{c}{p}$. Since the alphabet of $Y_{\mathcal{S}}$ is
finite, there are only finitely many different such rationals. Consequently,
there exist two levels $\mathcal{L}_{gb^{l}}$ and $\mathcal{L}$ with $l>0$
that represent the same rational number $x$. By the multiplicative property of
$Y_{\mathcal{S}}$,

$x\in\mathcal{S}^{l}(x),$

which means that $x$ is a periodic point for $\mathcal{S}$. ∎

The consequence of this theorem is that, to obtain a weakly aperiodic SFT on
$BS(m,n)$, we only need to explicitly build a multiplicative system with an
immortal point but no periodic points. For the rest of this section, let

$\displaystyle f_{1}\colon[\frac{1}{3},1]$
$\displaystyle\rightarrow[\frac{2}{3},2]$ $\displaystyle x$
$\displaystyle\mapsto 2x$

$\displaystyle f_{2}\colon[1,2]$
$\displaystyle\rightarrow[\frac{1}{3},\frac{2}{3}]$ $\displaystyle x$
$\displaystyle\mapsto\frac{1}{3}x$

and

$\mathcal{S}_{0}=\\{f_{1},f_{2}\\}.$

It is easy to see that this system has immortal points (in fact, all points of
$[\frac{1}{3},2]$ are immortal).

######  Proposition 2.7.

$\mathcal{S}_{0}$ has immortal points.

Additionally, since $2$ and $3$ are relatively prime:

######  Proposition 2.8.

$\mathcal{S}_{0}$ has no periodic points.

######  Corollary 2.9.

$Y_{\mathcal{S}_{0}}$ is non-empty and weakly aperiodic.

However, this construction does not avoid weakly periodic configurations when
$m$ and $n$ are not 1, as already remarked by Aubrun and Kari.

######  Proposition 2.10.

For any $m,n>1$, $Y_{\mathcal{S}_{0}}$ on $BS(m,n)$ contains a weakly periodic
tiling, with period $p=bab^{-1}aba^{-1}b^{-1}a^{-1}$.

To prove it, we need the following lemma:

######  Lemma 2.11.

Let $p=bab^{-1}aba^{-1}b^{-1}a^{-1}$. For any $g\in BS(m,n)$,
$\alpha(pg)=\alpha(g)$.

###### Proof.

Since $||p||_{b}=0$, using the definition of $\alpha$ it is easy to show that
$\alpha(pg)=\alpha(p)+\alpha(g)$ by recurrence on the length of $g$. Then,
$\alpha(p)=\frac{n}{m}+1-\frac{n}{m}-1=0$. ∎

###### Proof of Proposition 2.10.

We happen to have built a periodic configuration already: the one from the
proof of Theorem 2.4.

Indeed, let $x$ be any real in $[\frac{1}{3},2]$, since they are all immortal
for $\mathcal{S}_{0}$. Then there exists a sequence
$(i_{k})_{k\in\mathbb{Z}}\in\\{1,2\\}^{\mathbb{Z}}$ such that if we define

$x_{k}=\begin{cases}x&\text{if }k=0\\\
f_{i_{k-1}}(x_{k-1})=q_{i_{k-1}}x_{k-1}&\text{if }k>0\\\
f^{-1}_{i_{k}}(x_{k+1})=\frac{1}{q_{i_{k}}}x_{k+1}&\text{if }k<0\\\
\end{cases},$

then for all $k\in\mathbb{Z},x_{k}\in[\frac{1}{3},2]$. For every $g\in
BS(m,n)$, we place at $g$ a tile from the tileset $\tau_{i_{k}}$ with
$k=-||g||_{b}$, with colors:

$\displaystyle t_{j}:t_{j}(g,x_{k})$
$\displaystyle=\lfloor\left(m\lambda(g)+j\right)x_{k}\rfloor-\lfloor\left(m\lambda(g)+(j-1)\right)x_{k}\rfloor\text{\leavevmode\nobreak\
\leavevmode\nobreak\ for }j=1\dots m$ $\displaystyle b_{j}:b_{j}(g,x_{k})$
$\displaystyle=\lfloor\left(n\lambda(g)+j\right)q_{i_{k}}x_{k}\rfloor-\lfloor\left(n\lambda(g)+(j-1)\right)q_{i_{k}}x_{k}\rfloor\text{\leavevmode\nobreak\
\leavevmode\nobreak\ for }j=1\dots n$ $\displaystyle l:l(g,x_{k})$
$\displaystyle=\left(\frac{1}{m}q_{i_{k}}\lfloor
m\lambda(g)x_{k}\rfloor-\frac{1}{n}\lfloor
n\lambda(g)q_{i_{k}}x_{k}\rfloor,\leavevmode\nobreak\ i_{k}\right)$
$\displaystyle r:r(g,x_{k})$
$\displaystyle=\left(\frac{1}{m}q_{i_{k}}\lfloor\left(m\lambda(g)+m\right)x_{k}\rfloor-\frac{1}{n}\lfloor\left(n\lambda(g)+n\right)q_{i_{k}}x_{k}\rfloor,\leavevmode\nobreak\
i_{k}\right)$

We already checked that the resulting tiling $y$ was in $Y_{\mathcal{S}_{0}}$,
see the proof of Theorem 2.4. It remains to show that the tiles at $g$ and at
$pg$ are the same for all $g\in BS(m,n)$, to conclude that $p^{-1}\cdot y=y$,
or equivalently that $p$ is a period of $y$. This is actually surprisingly
easily, considering that for any $g\in BS(m,n)$, $||pg||_{b}=||g||_{b}$ so
they use the same integer $k$ and the same real $x_{k}$; and
$\lambda(g)=\lambda(pg)$, see Lemma 2.11. The tiles have the same labels as a
consequence of this.

The $y$ consequently defined is $p$-periodic. The only thing left to show is
that $p$ is a nontrivial element of $BS(m,n)$ as long as $m,n>1$. Since it is
freely reduced and does not contain $ba^{m}b^{-1}$ or $b^{-1}a^{n}b$ as
subwords, and since $BS(m,n)$ is a HNN extension $\mathbb{Z}*_{\alpha}$ with
$\alpha\colon m\mathbb{Z}\rightarrow n\mathbb{Z}$, we can apply Britton’s
Lemma: $p$ cannot be the neutral element.

Therefore $Y_{\mathcal{S}_{0}}$ contains a configuration with a nontrivial
period, and consequently is not strongly aperiodic. ∎

###  2.3 A deeper understanding of the configurations

We first present additional results on this tileset $Y_{\mathcal{S}_{0}}$ of
$BS(m,n)$. Most of the ideas present in this section were already present in
[11] in the context of tilings of the plane.

For a given line $\mathcal{L}_{g}$, we define the sequence
$u_{g}:=(y_{ga^{i}})_{i\in\mathbb{Z}}$ to be the sequence of digits on the
line $\mathcal{L}_{g}$ (its origin depending on $g$).

Let $f$ be the following bijective continuous map:

$\displaystyle f\colon$
${}^{\textstyle{[\frac{1}{3},2]}}\Big{/}_{\textstyle{\frac{1}{3}\sim
2}}\rightarrow^{\textstyle{[\frac{1}{3},2]}}\Big{/}_{\textstyle{\frac{1}{3}\sim
2}}$ $\displaystyle f(x)=$
$\displaystyle\begin{cases}f_{1}(x)=2x&\quad\text{if }x\in(\frac{1}{3},1)\\\
f_{2}(x)=\frac{1}{3}x&\quad\text{if }x\in(1,2)\\\ \overline{2}&\quad\text{if
}x=1\\\ \frac{2}{3}&\quad\text{if }x=\overline{2}\end{cases}$

$f$ is strongly related to $\mathcal{S}_{0}$ because for any
$x\in[\frac{1}{3},2]$, for any $k\in\mathbb{Z}$,

$^{\textstyle{{\mathcal{S}_{0}}^{k}(x)}}\Big{/}_{\textstyle{\frac{1}{3}\sim
2}}=f^{k}(x).$ (7)

due to the fact that for our particular
$\mathcal{S}_{0},{\mathcal{S}_{0}}^{k}(x)\subseteq[\frac{1}{3},2]$.

An easy consequence is the following:

######  Lemma 2.12.

Let $y\in Y_{\mathcal{S}_{0}}$. Let $g\in BS(m,n)$. Let $x\in[\frac{1}{3},2]$
be a real represented by $u_{g}$; then $u_{gb^{-1}}$ represents $f(x)$ (which
means either $\frac{1}{3}$ or $2$ if $f(x)=\overline{2}$).

###### Proof.

$u_{g}$ represents at least one such $x$ because of Item 1 of Theorem 2.4. The
rest is due to Item 2 of Theorem 2.4 and Eq. 7. ∎

It turns out that with our choice of multiplicative system $\mathcal{S}_{0}$,
any line can represent only one real number. We need several lemmas to prove
this; all inspired by [11].

######  Lemma 2.13.

Let $\phi$ be defined as follows:

$\phi\colon^{\textstyle{[\frac{1}{3},2]}}\Big{/}_{\textstyle{\frac{1}{3}\sim
2}}\rightarrow^{\textstyle{[0,1]}}\Big{/}_{\textstyle{0\sim 1}}$
$\phi(x)=\dfrac{\log(x)+\log(3)}{\log(2)+\log(3)}\mod 1$

$\phi$ is a correctly defined mapping that conjugates the dynamical systems
$(^{\textstyle{[\frac{1}{3},2]}}\Big{/}_{\textstyle{\frac{1}{3}\sim 2}},t,f)$
and $(^{\textstyle{[0,1]}}\Big{/}_{\textstyle{0\sim 1}},t^{\prime},\phi\circ
f\circ\phi^{-1})$, where $t$ and $t^{\prime}$ are the usual topologies on the
considered sets.

###### Proof.

Since the action considered on
${}^{\textstyle{[0,1]}}\Big{/}_{\textstyle{0\sim 1}}$ is $\phi\circ
f\circ\phi^{-1}$, one only needs to check that $\phi$ is bijective and
continuous to conclude that it yields a conjugation.

$\phi$ is clearly continuous everywhere except on $\overline{2}$; there, one
can check that the left and right limits both lead to $\phi(\overline{2})=0$
which is correctly defined.

$\phi^{-1}$ is defined by $\Phi(y)=\frac{6^{y}}{3}$ except with collapsed
images for $0$ and $1$. ∎

######  Lemma 2.14.

The map $r:=\phi\circ f\circ\phi^{-1}$ can be considered a rotation of
irrational angle $\frac{\log(2)}{\log(2)+\log(3)}$ when identifying
${}^{\textstyle{[0,1]}}\Big{/}_{\textstyle{0\sim 1}}$ and $\mathbb{S}^{1}$.

###### Proof.

For every $\alpha\in\phi((\frac{1}{3},1))$,

$\displaystyle\phi\circ f\circ\phi^{-1}(\alpha)$
$\displaystyle=\phi(2\phi^{-1}(\alpha))$
$\displaystyle=\dfrac{\log(2)+\log(\phi^{-1}(\alpha))+\log(3)}{\log(2)+\log(3)}\text{
mod }1$ $\displaystyle=\alpha+\dfrac{\log(2)}{\log(2)+\log(3)}\text{ mod }1.$

Similarly, for every $\alpha\in\phi((1,2))$, one has

$\displaystyle\phi\circ f\circ\phi^{-1}(\alpha)$
$\displaystyle=\phi(\dfrac{1}{3}\phi^{-1}(\alpha))$
$\displaystyle=\dfrac{\log(\phi^{-1}(\alpha))}{\log(2)+\log(3)}\text{ mod }1$
$\displaystyle=\alpha+\dfrac{\log(2)}{\log(2)+\log(3)}\text{ mod }1.$

Finally, $\phi\circ
f\circ\phi^{-1}(0)=\phi(f(\overline{2}))=\phi(\frac{2}{3})=\frac{\log(2)}{\log(2)+\log(3)}$.
∎

We now have the tools to prove the following key lemma:

######  Lemma 2.15.

(Uniqueness of representation) For any $y\in Y_{\mathcal{S}_{0}}$, for any
$g\in BS(m,n)$, the sequence $u_{g}=(y_{ga^{i}})_{i\in\mathbb{Z}}$ represents
a unique real number.

###### Proof.

Assume that $u_{g}$ represents two distinct reals $x$ and
$z\in[\frac{1}{3},2]$. They cannot be $\frac{1}{3}$ and $2$ because $u_{g}$
uses only digits in $\\{0,1\\}$ or in $\\{1,2\\}$. Therefore they also are
distinct reals in
${}^{\textstyle{[\frac{1}{3},2]}}\Big{/}_{\textstyle{\frac{1}{3}\sim 2}}$.

For any $k\in\mathbb{Z}$, notice that $f^{k}(x)=\phi^{-1}\circ
r^{k}\circ\phi(x)$ and same for $z$, from Lemma 2.13. We will study the
behavior of $\phi(x)$ and $\phi(z)$ under iterations of $r$.

The angle $\frac{\log(2)}{\log(2)+\log(3)}$, of which $r$ is a rotation by
Lemma 2.14, is irrational. As a consequence, the sets
$\\{r^{k}\circ\phi(x)\mid k\in\mathbb{N}\\}$ and $\\{r^{k}\circ\phi(z)\mid
k\in\mathbb{N}\\}$ are both dense in $\mathbb{S}^{1}$.

We introduce $d_{arc}(e^{2i\pi\theta},e^{2i\pi\psi})=m(\psi-\theta)\in[0,1)$
for $\theta,\psi\in\mathbb{R}$, where $m(\psi-\theta)$ is the only real in
$[0,1)$ congruent to $\psi-\theta$ mod $1$. We call $d_{arc}$ the _oriented
arc distance_ (measured counterclockwise) between two elements of
$\mathbb{S}^{1}$. It is not a distance per se since it is not symmetric and
has no triangular inequality, but its basic properties will suffice here.
Since $r$ is a rotation, it is easy to check that it preserves $d_{arc}$.
Hence we have that $\forall
k\in\mathbb{N},d_{arc}(r^{k}\circ\phi(x),r^{k}\circ\phi(z))$ is constant equal
to some $c\in[0,1[$. Up to considering
$d_{arc}(r^{k}\circ\phi(z),r^{k}\circ\phi(x))$ instead, and doing the
following reasoning by swapping $x$ and $z$, we can assume that
$c\leq\frac{1}{2}$.

Let us split $\mathbb{S}^{1}$ between $A=\phi((\frac{1}{3},1))$,
$B=\phi([1,2))$, and $\\{\phi(2)\\}=\\{\phi(\frac{1}{3})\\}=\\{0\\}$. We want
to show that there is some $l\in\mathbb{N}$ for which $r^{l}\circ\phi(x)\in B$
and $r^{l}\circ\phi(z)\in A$.

By density of $\\{r^{k}\circ\phi(x)\mid k\in\mathbb{Z}\\}$, there exists some
$k_{0}\in\mathbb{N}$ such that $d_{arc}(r^{k_{0}}\circ\phi(x),0)<c$ and
$r^{k_{0}}\circ\phi(x)\in B$. We cannot have $r^{k_{0}}\circ\phi(z)=0$ without
contradicting the previous inequality, hence it is either in $A$ or in $B$.
But if it was in $B$, then the arc from $r^{k_{0}}\circ\phi(x)$ to
$r^{k_{0}}\circ\phi(z)$ would contain all of $A$. This is not possible because
$|A|_{d_{arc}}>\frac{1}{2}\geq c$.

Hence there exists $l=k_{0}\in\mathbb{N}$ such that $r^{l}\circ\phi(x)\in B$
and $r^{l}\circ\phi(z)\in A$.

Figure 5: Preservation of the oriented arc distance $d_{arc}$ by $r$ and
intersection of the arc $\left(r^{l}\circ\phi(x),r^{l}\circ\phi(z)\right)$ and
the boundary between $A$ and $B$.

Since $r^{l}=\phi\circ f^{l}\circ\phi^{-1}$, and considering the definitions
of $A$ and $B$, $f^{l}(z)\in(\frac{1}{3},1)$ and $f^{l}(x)\in[1,2)$. This
would cause $f^{l}(z)$ to be represented by a sequence of $0$’s and $1$’s
(with an infinite number of $0$’s) and $f^{l}(x)$ by a sequence of $1$’s and
$2$’s. However, the SFT $Y_{\mathcal{S}_{0}}$ is built such that a line
contains only elements in $\\{0,1\\}$ or $\\{1,2\\}$, but not both (see proof
of Theorem 2.4): this is a contradiction.

Therefore, $x$ and $z$ must be equal, hence the uniqueness of the real number
represented by a given sequence. ∎

Using previous results, we are now able to prove for $BS(m,n)$ that the real
represented by the sequence $u_{g}$ only depends on $||g||_{b}$, its “depth”
in the Cayley graph.

######  Lemma 2.16.

Let $y\in Y_{\mathcal{S}_{0}}$, and $e$ the identity of $BS(m,n)$. Let $x$ be
the unique real represented by the sequence $u_{e}$. Then for every $g\in
BS(m,n)$, $u_{g}$ represents $f^{-||g||_{b}}(x)$ (with a choice between
$\frac{1}{3}$ and $2$, possibly different for different $g$’s, if the
resulting value is $\overline{2}$).

###### Proof.

We prove the result by reasoning on words $w\in\\{a,b,a^{-1},b^{-1}\\}^{*}$,
by induction on their length. Note that we have no need of proving that
different $w$’s representing the same $g$ yield the same result, since this is
guaranteed by Lemma 2.15.

The result is true for $g=e$.

Suppose the result is true for words of length $n\in\mathbb{N}_{0}$. Let $w$
be a word of length $n$. Then:

  * •

$u_{wa}$ and $u_{wa^{-1}}$ represent the same real as $u_{w}$ since they are
the same sequence up to an index shift;

  * •

$u_{wb^{-1}}$ represents $f(f^{-||w||_{b}}(x))$ due to Lemma 2.12 and the
induction hypothesis, which is $f^{-||wb^{-1}||_{b}}(x)$;

  * •

suppose $u_{wb}$ represents $y$; then $u_{w}$ represents $f(y)$ due to Lemma
2.12. Then we have, by induction, $y=f^{-||w||_{b}-1}(x)=f^{-||wb||_{b}}(x)$.

∎

######  Remark 2.17.

The previous proof heavily relies on the fact that $f$ is a bijection on
${}^{\textstyle{[\frac{1}{3},2]}}\Big{/}_{\textstyle{\frac{1}{3}\sim 2}}$, and
that we do not have to differentiate between $\frac{1}{3}$ and $2$ there.

###  2.4 A strongly aperiodic SFT on $BS(1,n)$

If $m$ or $n$ is equal to 1, then the previous weak period of Proposition 2.10
does not work anymore – it is a trivial element. In fact, we prove in this
section that for $BS(1,n)$, $Y_{\mathcal{S}_{0}}$ is strongly aperiodic.

One key property of $BS(1,n)$ is that there is a simple quasi-normal form for
all its elements.

######  Lemma 2.18.

(Quasi-normal form in $BS(1,n)$) For every $g\in BS(1,n)$, there are integers
$k,m\in\mathbb{N}_{0}$ and $l\in\mathbb{Z}$ such that ${g=b^{-k}a^{l}b^{m}}$.

###### Proof.

From the definition of $BS(1,n)$, we have that $ba=a^{n}b$ (1),
$ba^{-1}=a^{-n}b$ (2), $ab^{-1}=b^{-1}a^{n}$ (3) and
$a^{-1}b^{-1}=b^{-1}a^{-n}$ (4). Consequently, taking an element of $BS(1,n)$
as a word $w$ written with $a$ and $b$, we can:

  * •

Move each positive power of $b$ to the right of the word using (1) and (2)
repeatedly;

  * •

Move each negative power of $b$ to the left of the word using (3) and (4)
repeatedly;

so that we finally get a form for the word $w$ which is: $b^{-k}a^{l}b^{m}$
with $k,m\in\mathbb{N}_{0}$ and $l\in\mathbb{Z}$. ∎

######  Remark 2.19.

A general normal form – the same, with $k$ imposed to be minimal – can be
obtained from Britton’s Lemma. The form obtained here is _not_ unique
($a=b^{-1}a^{n}b$ for instance), but we use it because it admits a simple
self-contained proof, and it is enough for what follows: the sum $m-k$ is
constant for all writings of a given group element, hence we name it “quasi-
normal”.

###### Proof.

Indeed, suppose we have
$b^{-k}a^{l}b^{m}=b^{-k^{\prime}}a^{l^{\prime}}b^{m^{\prime}}$. Then

$\displaystyle b^{-k}a^{l}$
$\displaystyle=b^{-k^{\prime}}a^{l^{\prime}}b^{-(m-m^{\prime})}$
$\displaystyle=b^{-k^{\prime}-(m-m^{\prime})}a^{l^{\prime}n^{m-m^{\prime}}}$

Hence we get
$a^{l^{\prime}n^{m-m^{\prime}}-l}=b^{-k+k^{\prime}+m-m^{\prime}}$. Since it is
clear that $a^{i}=b^{j}$ if and only if $i=j=0$ in $BS(1,n)$, we obtain
$m-k-(m^{\prime}-k^{\prime})=0$ which is what we wanted. ∎

This quasi-normal form is the only thing that missed to prove the following.

######  Theorem 2.20.

For every $n\geq 2$, the Baumslag-Solitar group $BS(1,n)$ admits a strongly
aperiodic SFT.

###### Proof.

Let $y\in Y_{\mathcal{S}_{0}}$, and $g\in Stab_{BS(1,n)}(y)$. Using Lemma
2.18, we can write $g=b^{-k}a^{l}b^{m}$ with
$k,m\in\mathbb{N}_{0},l\in\mathbb{Z}$.

Let $x$ be the real represented by $u_{e}$. By Lemma 2.16, $u_{g}$ represents
$f^{k-m}(x)$. Since $g\in Stab_{BS(1,n)}(y)$, $u_{g}=u_{e}$ and so
$f^{k-m}(x)=x$ by the uniqueness of the representation from Lemma 2.15. The
aperiodicity of $f$ then implies that $k=m$.

Let us assume $l\neq 0$. Then $g=b^{-k}a^{l}b^{k}$ and
$g^{n}=b^{-k}(a^{n})^{l}b^{k}$. We can reduce $g^{n}$ to
$b^{-k+1}a^{l}b^{k-1}$ using the relation $a^{n}=bab^{-1}$. More generally, we
notice that for any positive integer $i$, iterating the process $i$ times, we
obtain that $g^{n^{i}}=b^{-k+i}a^{l}b^{k-i}\in Stab_{BS(1,n)}(y)$.

Since for all $i$, $g^{n^{i}}\in Stab_{BS(1,n)}(y)$, we can obtain a
contradiction with an argument similar to Prop 6. of [3]. We have
$b^{j}a^{l}b^{-j}\in Stab_{BS(1,n)}(y)$ for any $j\geq-k$. This means that
$u_{b^{j}}=u_{b^{j}a^{l}}$ hence $u_{b^{j}}$ is a $l$-periodic sequence. We
have a finite number of said sequences, since they can only use digits among
$\\{0,1,2\\}$. Consequently, there are $j_{1}\neq j_{2}$ such that the two
levels $\mathcal{L}_{b^{j_{1}}}$ and $\mathcal{L}_{b^{j_{2}}}$ read the same
sequence (up to index translation). These two levels represent respectively
$f^{j_{1}}(x)$ and $f^{j_{2}}(x)$ due to Lemma 2.16, and since the two
sequences on these levels are the same, $f^{j_{1}}(x)=f^{j_{2}}(x)$. This
equality contradicts the fact that $f$ has no periodic point, since we had
$j_{1}\neq j_{2}$.

As a consequence, any non-trivial $g\in{BS(1,n)}$ cannot be in
$Stab_{BS(1,n)}(x)$, and we finally get that $Stab_{BS(1,n)}(x)=\\{e\\}$:
$Y_{\mathcal{S}_{0}}$ is strongly aperiodic. ∎

Following Theorem 2.20, a question remains: is the strong aperiodicity of
Aubrun and Kari’s SFT a property of the group $BS(1,n)$ itself, or does it
only arise on carefully chosen SFTs, as $Y_{\mathcal{S}_{0}}$? Is this because
$BS(1,n)$ behaves like $\mathbb{Z}^{2}$ and all its weakly aperiodic SFTs are
also strongly aperiodic, or does Aubrun and Kari’s construction happen to be
“too much aperiodic”? It turns out that the latter is the correct answer, as
we build in the following section an SFT on $BS(1,n)$ that is weakly but not
strongly aperiodic.

##  3 A weakly but not strongly aperiodic SFT on $BS(1,n)$

Our weakly but not strongly aperiodic SFT will work by encoding specific
substitutions into $BS(1,n)$. Indeed, the Cayley graph of $BS(1,n)$ is very
similar to orbit graphs of uniform substitutions (see for example [9, 2] for a
definition of orbit graphs and another example of a Cayley graph similar to an
orbit graph). In this section, we find a set of substitutions that are easy to
encode in $BS(1,n)$ (Section 3.1), and show how to do it (Section 3.2).

###  3.1 The substitutions $\sigma_{i}$

Let $\mathcal{A}=\\{0,1\\}$. For $r\in\\{0,\dots,n-1\\}$, let
$\sigma_{r}:\mathcal{A}\rightarrow\mathcal{A}^{n}$ be the following
substitution:

$\sigma_{r}:\begin{cases}0\mapsto 0^{n-r-1}10^{r}\\\ 1\mapsto
0^{n}\end{cases}.$

We may also write $\sigma=\sigma_{0}$ and call the other ones the _shifts_ of
$\sigma$.

Note that, for $c\in\\{0,1\\}$ and $i\in\\{0,\dots,n-1\\}$,
$\sigma_{r}(c)_{i}=0$ if and only if $c=0$ and $i=n-r-1$ (starting to count
from $0$ the indices of the word $\sigma_{r}(c)$).

All $\sigma_{r}(0)$ are cyclic permutations of the same finite word. Denote
$\rho$ the _shift action_ on a biinfinite word $u$, i.e.
${\rho^{j}(u)}_{i}=u_{i+j}$, as a way to write the action of $\mathbb{Z}$ on
$\\{0,1\\}^{\mathbb{Z}}$.

######  Lemma 3.1.

For any biinfinite word $u\in\mathcal{A}^{\mathbb{Z}}$, any
$i,r\in\\{0,\dots,n-1\\}$ and $j\in\mathbb{Z}$,

$(\sigma_{r}\circ\rho^{j}(u))_{i}=\sigma_{r}(u_{j})_{i}=(\sigma_{r}(u))_{nj+i}.$

###### Proof.

For $i\in\\{0,\dots,n-1\\}$, $\sigma_{r}(\rho^{j}(u))_{i}$ depends on the
letter of $\rho^{j}(u)$ at position $0$ only, that is $u_{j}$ (See Fig. 6),
hence
$\sigma_{r}(\rho^{j}(u))_{i}=\sigma_{r}(\rho^{j}(u)_{0})_{i}=\sigma_{r}(u_{j})_{i}.$

Similarly, the letter $(\sigma_{r}(u))_{nj+i}$ does not depend on the totality
of $u$ but only on $u_{j}$: it is the $i$th letter of $\sigma_{r}(u_{j})$. ∎

Figure 6: Illustration of Lemma 3.1.

######  Lemma 3.2.

For any $r\in\\{0,\dots,n-1\\}$,

$\sigma_{r}=\rho^{r}\circ\sigma.$

###### Proof.

Let $u\in\mathcal{A}^{\mathbb{Z}}$. Let $i,r\in\\{0,\dots,n-1\\}$ and
$j\in\mathbb{Z}$.

$\sigma(u)_{nj+i}=\begin{cases}0&\quad\text{if }i\neq n-1\\\
\sigma_{r}(u)_{nj+i-r}&\quad\text{if }i=n-1\\\ \end{cases}$

Considering that if $i\neq n-1$, $\sigma_{r}(u)_{nj+i-r}=0$, we conclude that
we always have $\sigma(u)_{nj+i}=\sigma_{r}(u)_{nj+i-r}$, and so
$\sigma_{r}=\rho^{r}\circ\sigma$. ∎

######  Lemma 3.3.

For $n\geq 3$, $\sigma_{1}$ has a unique fixpoint. For $n=2$, $\sigma_{1}$ has
no fixpoint but ${\sigma_{1}}^{2}$ has two fixpoints.

###### Proof.

Proposition 4 from [19] characterizes biinfinite fixpoints of substitutions.
In the present case of $\sigma_{1}$, [19] states that $w=\sigma_{1}(w)$ if and
only if $w=y.x$ with $x=\overrightarrow{{\sigma_{1}}^{\omega}}(c)$ and
$y=\overleftarrow{\leavevmode\nobreak\ {}^{\omega}\sigma_{1}}(c^{\prime})$
with $\sigma_{1}(c)=cv$ and $\sigma_{1}(c^{\prime})=uc^{\prime}$,
$u,v\in\\{0,1\\}^{*}$, $c,c^{\prime}\in\\{0,1\\}$. Notice that
$\sigma_{1}(0)=0^{n-2}10$ and $\sigma_{1}(1)=0^{n}$, for $n\geq 3$, so the
only choice for $c$ and $c^{\prime}$ is $c=c^{\prime}=0$. Then $\sigma_{1}$
has a fixpoint that is $\overleftarrow{\leavevmode\nobreak\
{}^{\omega}\sigma_{1}}(0).\overrightarrow{{\sigma_{1}}^{\omega}}(0)$ and which
is unique.

For $n=2$ the same reasoning concludes that $\sigma_{1}$ has no fixpoint.
However, since ${\sigma_{1}}^{2}(0)=0010$ and ${\sigma_{1}}^{2}(1)=1010$, the
same reasoning also yields that ${\sigma_{1}}^{2}$ has two fixpoints that are
$\overleftarrow{\leavevmode\nobreak\
{}^{\omega}({\sigma_{1}}^{2})}(0).\overrightarrow{{({\sigma_{1}}^{2})}^{\omega}}(0)$
and $\overleftarrow{\leavevmode\nobreak\
{}^{\omega}({\sigma_{1}}^{2})}(0).\overrightarrow{{({\sigma_{1}}^{2})}^{\omega}}(1)$.
∎

######  Lemma 3.4.

For every $k\in\mathbb{N}$ and every $i_{1},\dots,i_{k}\in\\{0,\dots,n-1\\}$,
the fixpoints of $s=\sigma_{i_{k}}\circ\dots\circ\sigma_{i_{1}}$ are
aperiodic.

###### Proof.

To prove the aperiodicity of a fixpoint $w$ of $s$ (in the case where such a
fixpoint exists), we follow a proof from [17], simplified for our specific
case.

First, let us show that the two subwords $00$ and $01$ can be found in $w$.

  * •

For $00$, let us define
$s^{\prime}=\sigma_{i_{k-1}}\circ\dots\circ\sigma_{i_{1}}$. Then, by
definition, $w=\sigma_{i_{k}}(s^{\prime}(w))$ (by convention $s^{\prime}(w)=w$
if $k=1$). We are going to prove that $s^{\prime}(w)$ always contains a $1$.
As a consequence, $w=\sigma_{i_{k}}(s^{\prime}(w))$ contains $00$ because
$\sigma_{i_{k}}(1)=0^{n}$. Suppose
$s^{\prime}(w)=\makebox[8.99994pt][c]{.\hfil.\hfil.}000\makebox[8.99994pt][c]{.\hfil.\hfil.}$.
If $k=1$, it means that
$w=\makebox[8.99994pt][c]{.\hfil.\hfil.}000\makebox[8.99994pt][c]{.\hfil.\hfil.}$,
but then $s(w)\neq w$ so this is impossible. If $k=2$, then
$s^{\prime}=\sigma_{i_{1}}$ so the only way to have
$s^{\prime}(w)=\makebox[8.99994pt][c]{.\hfil.\hfil.}000\makebox[8.99994pt][c]{.\hfil.\hfil.}$
is to have
$w=\makebox[8.99994pt][c]{.\hfil.\hfil.}111\makebox[8.99994pt][c]{.\hfil.\hfil.}$,
but again $s(w)\neq w$. If $k\geq 3$, let us define
$t=\sigma_{i_{k-3}}\circ\dots\circ\sigma_{i_{1}}$. With this notation,
$w=\sigma_{i_{k}}\circ\sigma_{i_{k-1}}\circ\sigma_{i_{k-2}}(t(w))$. The
assumption
$s^{\prime}(w)=\makebox[8.99994pt][c]{.\hfil.\hfil.}000\makebox[8.99994pt][c]{.\hfil.\hfil.}$
causes
$\sigma_{i_{k-2}}(t(w))=\makebox[8.99994pt][c]{.\hfil.\hfil.}111\makebox[8.99994pt][c]{.\hfil.\hfil.}$.
However, this is impossible since
$\makebox[8.99994pt][c]{.\hfil.\hfil.}111\makebox[8.99994pt][c]{.\hfil.\hfil.}$
has no antecedent by $\sigma_{i_{k}-2}$. Therefore $s^{\prime}(w)$ must
contain a $1$ and we can find $00$ in $w$.

  * •

For $01$, the only way for $w$ not to contain $01$ is to be of the form
$w=\makebox[8.99994pt][c]{.\hfil.\hfil.}000\makebox[8.99994pt][c]{.\hfil.\hfil.}$,
$w=\makebox[8.99994pt][c]{.\hfil.\hfil.}111\makebox[8.99994pt][c]{.\hfil.\hfil.}$
or
$w=\makebox[8.99994pt][c]{.\hfil.\hfil.}1100\makebox[8.99994pt][c]{.\hfil.\hfil.}$.
But it is clear that
${s(\makebox[8.99994pt][c]{.\hfil.\hfil.}000\makebox[8.99994pt][c]{.\hfil.\hfil.})\neq\makebox[8.99994pt][c]{.\hfil.\hfil.}000\makebox[8.99994pt][c]{.\hfil.\hfil.}}$,
${s(\makebox[8.99994pt][c]{.\hfil.\hfil.}111\makebox[8.99994pt][c]{.\hfil.\hfil.})\neq\makebox[8.99994pt][c]{.\hfil.\hfil.}111\makebox[8.99994pt][c]{.\hfil.\hfil.}}$
and
${s(\makebox[8.99994pt][c]{.\hfil.\hfil.}1100\makebox[8.99994pt][c]{.\hfil.\hfil.})\neq\makebox[8.99994pt][c]{.\hfil.\hfil.}1100\makebox[8.99994pt][c]{.\hfil.\hfil.}}$
hence none of them can be fixpoints.

Hence $s(00)$ and $s(01)$ can also be found in $w$ since $s(w)=w$. From this,
we build by induction infinitely many words with two possible right
extensions. We have $s(00)\neq s(01)$; consider the largest prefix on which
they agree, call it $u_{2}$, with $|u_{2}|>1$. Then both $u_{2}0$ and $u_{2}1$
can be found in $w$. Hence $s(u_{2}0)$ and $s(u_{2}1)$ can also be found in
$w$. We have $s(u_{2}0)\neq s(u_{2}1)$; consider the largest prefix on which
they agree, call it $u_{3}$, with $|u_{3}|>|u_{2}|$. Then both $u_{3}0$ and
$u_{3}1$ can be found in $w$. Hence $s(u_{3}0)$ and $s(u_{3}1)$ can also be
found in $w$.

By induction, we can build subwords of $w$ as large as we want that have two
choices for their last letter. Hence the factor complexity of $w$ is
unbounded, and so $w$ is aperiodic (see Section 1.3). ∎

###  3.2 Encoding substitutions in $BS(1,n)$

We now show how to encode such substitutions in SFTs of the group $BS(1,n)$
given by a tileset. We define the tileset $\tau_{\sigma}$ on
$BS(1,n),n\in\mathbb{N},n\geq 2$, to be the set of tiles shown on Fig. 7 for
all $c\in\\{0,1\\}$ and $i\in\\{0,\dots,n-1\\}$. Remark that a tile is
uniquely defined by the couple $(c,i)$.

Figure 7: Tiles of $\tau_{\sigma}$: left and right colors are identical and
equal to $i$, top color is $c$ and bottom colors are equal to
$\sigma_{i}(c)_{0},\dots,\sigma_{i}(c)_{n-1}$.

This tileset will be the weakly but not strongly aperiodic tileset we are
looking for. Lemmas 3.3 and 3.4 study the words that can appear on levels
$\mathcal{L}_{g}$ of the tiling, by looking at the fixpoints of $\sigma_{1}$.
They prove that no biinfinite word can be both a fixpoint for the
$\sigma_{i}$’s and a periodic word, forbidding one direction of periodicity
for any configuration we will encode with our tileset. This naturally leads to
the following proposition:

######  Proposition 3.5.

No configuration of $X^{\tau_{\sigma}}$ can be $a^{k}$-periodic for any
$k\in\mathbb{N}$.

###### Proof.

Suppose that there is a configuration $x$ of $X^{\tau_{\sigma}}$ such that for
any ${g\in{BS(1,n)}}$, ${x_{a^{k}\cdot g}=x_{g}}$ ($a^{k}$-periodicity). Call
$w:=(x_{a^{j}})_{j\in\mathbb{Z}}$ the biinfinite word based on level
$\mathcal{L}_{e}$. $w$ is $k$-periodic by $a^{k}$-periodicity of the
configuration $x$. But $w$ is also $nk$-periodic. Hence
$(x_{ba^{j}})_{j\in\mathbb{Z}}$ is $k$-periodic. Indeed, by construction, when
applying the correct substitution $\sigma_{i}$ to $x_{ba^{j}}$ and
$x_{ba^{j+k}}$, one obtains the words $x_{a^{nj}}\dots x_{a^{nj+n-1}}$ and
$x_{a^{nj+nk}}\dots x_{a^{nj+nk+n-1}}$ which are one and the same by
$nk$-periodicity of $w$. Since there is only one preimage for a word by
$\sigma_{i}$, $x_{ba^{j}}=x_{ba^{j+k}}$. By the same argument, one can show
that for any integer $l>0$, $(x_{b^{l}a^{j}})_{j\in\mathbb{Z}}$ must be
$k$-periodic. However, these biinfinite sequences only use digits among
$\\{0,1,2\\}$ so there is a finite number of such sequences. In particular,
two of these sequences are the same. Since one is obtained from the other by
applying the correct succession of $\sigma_{i}$’s, we get a periodic sequence
that is a fixpoint of some $s=\sigma_{i_{N}}\circ\dots\circ\sigma_{i_{1}}$ for
some $i_{1},\dots,i_{N}\in\\{0,\dots,n-1\\}$. This contradicts Lemma 3.4. ∎

######  Lemma 3.6.

There exists a weakly periodic configuration in $X^{\tau_{\sigma}}$ for $n\geq
3$.

###### Proof.

We define $w$ the unique fixpoint of $\sigma_{1}$ obtained thanks to Lemma
3.3.

Let $f(k)=\lfloor\frac{k}{n}\rfloor$ be the function that maps $k$ to the
quotient in the euclidean division of $k$ by $n$ and $r(k)$ its remainder. We
also define $F(k)=f(k+1)$ and $R(k)=r(k+1)$. This means that $nF(k)+R(k)=k+1$,
$F(ln)=l+\lfloor\frac{1}{n}\rfloor=l$, but also
$F(k+n)=\lfloor\frac{k+1+n}{n}\rfloor=F(k)+1$, and consequently
$F^{m}(k+n^{m})=F^{m}(k)+1$.

####  $X^{\tau_{\sigma}}$ is nonempty

We define a configuration $x$ describing which tile $(c_{g},i_{g})$ (a tile
being uniquely defined by such a couple) is assigned to $g$, i.e.
$x_{g}=(c_{g},i_{g})$, using the quasi-normal form $g=b^{-k}a^{l}b^{m}$. Then,
we check that $x$ does verify the adjacency rules. Define
$x\in{\tau_{\sigma}}^{BS(1,n)}$ by

$\begin{cases}x_{b^{-k}a^{l}}:=(w_{l},1)\\\
x_{b^{-k}a^{l}b^{m}}:=(w_{F^{m}(l)},R\circ F^{m-1}(l))$ for $m>0.\end{cases}$

Remember that Lemma 2.18 states that any $g\in BS(1,n)$ can be written
$b^{-k_{1}}a^{l_{1}}b^{m_{1}}$. Suppose it has a second form
$b^{-k_{2}}a^{l_{2}}b^{m_{2}}$ with $k_{2}>k_{1}$ up to exchanging the
notations (were they equal, it is easy to prove the two forms would be the
same). Then $b^{k_{1}-k_{2}}a^{l_{2}}b^{m_{2}-m_{1}}=a^{l_{1}}$, that is,
$b^{k_{1}-k_{2}}a^{l_{2}-l_{1}n^{k_{2}-k_{1}}}b^{m_{2}-m_{1}}=e$. This means
that $k_{2}-k_{1}=m_{2}-m_{1}>0$ and $l_{2}=l_{1}n^{k_{2}-k_{1}}$. With that,
we prove our $x$ is well-defined. $k_{2}>k_{1}$ causes $m_{2}>0$ in order to
have $k_{2}-k_{1}=m_{2}-m_{1}>0$. Consequently,

$\displaystyle x_{b^{-k_{2}}a^{l_{2}}b^{m_{2}}}$
$\displaystyle=(w_{F^{m_{2}}(l_{2})},R\circ F^{m_{2}-1}(l_{2}))$
$\displaystyle=(w_{F^{m_{1}+k_{2}-k_{1}}(l_{1}n^{k_{2}-k_{1}})},R\circ
F^{m_{1}+k_{2}-k_{1}-1}(l_{1}n^{k_{2}-k_{1}}))$
$\displaystyle=(w_{F^{m_{1}}(l_{1})},R\circ F^{m_{1}-1}(l_{1}))$
$\displaystyle=x_{b^{-k_{1}}a^{l_{1}}b^{m_{1}}}$

with a variation on the second to last line if $m_{1}=0$: we have $R\circ
F^{k_{2}-k_{1}-1}(l_{1}n^{k_{2}-k_{1}})=R(l_{1}n)=1$.

Now, we prove that $x\in X^{\tau_{\sigma}}$. Let $g=b^{-k}a^{l}b^{m}$.

  * •

If $m>0$, we have

$\displaystyle x_{ga}(\text{left})$
$\displaystyle=x_{b^{-k}a^{l+n^{m}}b^{m}}(\text{left})$ $\displaystyle=R\circ
F^{m-1}(l+n^{m})$ $\displaystyle=R(F^{m-1}(l)+n)$ $\displaystyle=R\circ
F^{m-1}(l)$ $\displaystyle=x_{g}(\text{right}).$

  * •

If $m=0$, we have

$\displaystyle x_{ga}(\text{left})$
$\displaystyle=x_{b^{-k}a^{l+1}}(\text{left})$ $\displaystyle=1$
$\displaystyle=x_{g}(\text{right}).$

Let $j\in\\{0,\dots,n-1\\}$. We have

$\displaystyle x_{ga^{-j}b}(\text{bottom}_{j+1})$
$\displaystyle=x_{b^{-k}a^{l-jn^{m}}b^{m+1}}(\text{bottom}_{j+1})$
($g=b^{-k}a^{l}b^{m}$) $\displaystyle=\sigma_{R\circ
F^{m}(l-jn^{m})}(w_{F^{m+1}(l-jn^{m})})_{j}$ (by definition of $x$)
$\displaystyle=\sigma_{R\circ F^{m}(l-jn^{m})}(w)_{nF^{m+1}(l-jn^{m})+j}$
$\displaystyle(\lx@cref{creftype~refnum}{lemma:exponentindex})$
$\displaystyle=\sigma(w)_{nF^{m+1}(l-jn^{m})+j+R\circ F^{m}(l-jn^{m})}$
$\displaystyle(\lx@cref{creftype~refnum}{lemma:remainder})$
$\displaystyle=\sigma(w)_{F^{m}(l-jn^{m})+j+1}$ $\displaystyle\text{(by
definition of }F\text{ and }R\text{)}$
$\displaystyle=\sigma_{1}(w)_{F^{m}(l-jn^{m})+j}$
$\displaystyle(\lx@cref{creftype~refnum}{lemma:remainder})$
$\displaystyle=w_{F^{m}(l-jn^{m})+j}$ (since $w$ is a fixpoint of
$\sigma_{1}$) $\displaystyle=w_{F^{m}(l)}$
$\displaystyle(F^{m}(l-jn^{m})=F^{m}(l)-j)$ $\displaystyle=x_{g}(\text{top})$

Consequently, $x$ describes a valid configuration of $X^{\tau_{\sigma}}$: all
adjacency conditions are verified.

####  $x$ is $b$-periodic

With the definition of $x$, it is easy to check that for any $g\in BS(1,n)$,
$x_{bg}=x_{g}$. Hence it is a weakly periodic configuration. ∎

We can now obtain our second main theorem:

######  Theorem 3.7.

The tileset $\tau_{\sigma}$ forms a weakly aperiodic but not strongly
aperiodic SFT on $BS(1,n),n\in\mathbb{N},n\geq 2$.

###### Proof.

First, in the $n\geq 3$ case, there is a weakly periodic configuration in
$X^{\tau_{\sigma}}$, see Lemma 3.6. Hence it is not a strongly aperiodic SFT.

In the $n=2$ case, we define $u$ and $v$ the two fixpoints of
${\sigma_{1}}^{2}$ (Lemma 3.3 again) and remark that $v=\sigma_{1}(u)$ and
$u=\sigma_{1}(v)$. We define a configuration $x\in{\tau_{\sigma}}^{BS(1,n)}$
by:

$x_{b^{-k}a^{l}}:=\begin{cases}(u_{l},1)$ if $k+m\equiv 0$ mod $2\\\
(v_{l},1)$ if $k+m\equiv 1$ mod $2\end{cases}$
$x_{b^{-k}a^{l}b^{m}}:=\begin{cases}(u_{F^{m}(l)},R\circ F^{m-1}(l))$ for
$m>0$ if $k+m\equiv 0$ mod $2\\\ (v_{F^{m}(l)},R\circ F^{m-1}(l))$ for $m>0$
if $k+m\equiv 1$ mod $2\end{cases}$

and we use the same notations as in the proof of Lemma 3.6. The reasoning is
also the same, except instead of using $w$ an alternation appears between $u$
and $v$ in all the equations. As a consequence, the configuration is
$b^{2}$-periodic instead of $b$. Once again, $X^{\tau_{\sigma}}$ is
consequently not strongly aperiodic.

Now, using Proposition 3.5, and since all powers of $a$ are of infinite order
in ${BS(1,n)}$, we get that for any valid configuration $x$ of
$\tau_{\sigma}$, $|Orb_{BS(1,n)}(x)|=+\infty$, for any $n\geq 2$. Hence no
configuration of $\tau_{\sigma}$ is strongly periodic, and so the SFT is
weakly aperiodic. ∎

##  4 A strongly aperiodic SFT on $BS(n,n)$

This section is a mere assembly of known results, that we think are worth
gathering in the context of the current paper. It uses a theorem from [12]
seen as an extension of the construction presented in [14]. The idea behind
that theorem is that $G\times\mathbb{Z}$ admits a strongly aperiodic SFT as
soon as $G$ can encode piecewise affine functions. This is reflected by the
$PA^{\prime}$ condition described in [12] and restated below.

######  Definition 4.1.

Let $k\in\mathbb{N}$. Let $\mathcal{F}=\\{f_{i}\colon P_{i}\rightarrow
P_{i}^{\prime}\mid i\in\\{0,\dots,k\\}\\}$ be a finite set of piecewise affine
rational homeomorphisms, where each $P_{i}$ and $P_{i}^{\prime}$ is a finite
union of bounded rational polytopes of $\mathbb{R}^{n}$. Let
$D=\bigcap_{i=1}^{k}P_{i}\cap\bigcap_{i=1}^{k}P_{i}^{\prime}$ be the common
domain of all functions of $\mathcal{F}$ and their inverses.

Let $S_{\mathcal{F}}$ be the closure of the set $\\{f_{i},{f_{i}}^{-1}\mid
i\in\\{1,\dots,k\\}\\}$ under composition. We define $G_{\mathcal{F}}$, the
group $\\{f|_{D}\mid f\in S_{\mathcal{F}}\\}$.

A finitely generated group $G$ is $PA^{\prime}$-recognizable if there exists a
finite set $\mathcal{F}$ of piecewise affine rational homeomorphisms such
that:

(A) $G\cong G_{\mathcal{F}}$;

(B) $\forall t\in D,\forall g\in\mathcal{F},[\forall
f\in\mathcal{F},g(f(t))=f(t)]\Rightarrow g=Id$.

######  Theorem 4.1 ([12], Th. 7).

If $G$ is an infinite finitely generated $PA^{\prime}$-recognizable group,
then $\mathbb{Z}\times G$ admits a strongly aperiodic SFT.

We need two additional propositions to obtain the desired result on $BS(n,n)$:

######  Proposition 4.2 ([6], Prop. 9 & 10).

If $G$ is a finitely generated group and $H$ is a finitely generated subgroup
of $G$ of finite index, then we have the following:

$H$ admits a weakly aperiodic SFT $\Leftrightarrow$ $G$ admits a weakly
aperiodic SFT

$H$ admits a strongly aperiodic SFT $\Leftrightarrow$ $G$ admits a strongly
aperiodic SFT.

The following proposition is known, but we include a self-contained proof.

######  Proposition 4.3.

$BS(n,n)$ admits $\mathbb{Z}\times\mathbb{F}_{n}$ as a subgroup of finite
index, where $\mathbb{F}_{n}$ is the free group of order $n$.

###### Proof.

Let $H$ be the subgroup of $BS(n,n)$ generated by
$\\{a^{n}\\}\cup\\{a^{i}ba^{-i}\mid i\in\\{0,\dots,n-1\\}\\}$. First, $H$ is
normal in $BS(n,n)$. We prove that $aHa^{-1}\subseteq H$ by verifying it on
its generators: the only verification needed is
$aa^{n-1}ba^{-(n-1)}a^{-1}=a^{n}ba^{-n}=ba^{n}a^{-n}=b$. Similarly,
$a^{-1}Ha\subseteq H$; and finally, $bHb^{-1}\subseteq H$ (same for $b^{-1}$)
since $b\in H$. Second, $H$ is isomorphic to $\mathbb{Z}\times\mathbb{F}_{n}$
through the following isomorphism (denoting $g_{0},\dots,g_{n-1}$ the
generators of $\mathbb{F}_{n}$ and $\varepsilon$ its identity):

$\displaystyle\phi\colon$ $\displaystyle\mathbb{Z}\times\mathbb{F}_{n}$
$\displaystyle\longrightarrow$ $\displaystyle H$
$\displaystyle(1,\varepsilon)$ $\displaystyle\longmapsto$ $\displaystyle
a^{n}$ $\displaystyle(0,g_{i})$ $\displaystyle\longmapsto$ $\displaystyle
a^{i}ba^{-i}$

It is a morphism by construction, which is correctly defined since the only
basic relation of $\mathbb{Z}\times\mathbb{F}_{n}$, that is
$(1,\varepsilon)\cdot(0,g_{i})=(0,g_{i})\cdot(1,\varepsilon)$, is preserved in
$H$:
$a^{n}a^{i}ba^{-i}=a^{i}a^{n}ba^{-i}=a^{i}ba^{n}a^{-i}=a^{i}ba^{-i}a^{n}$.
Said morphism is surjective, because $H$ is generated by $a^{n}$ and
$\\{a^{i}ba^{-i}\mid i\in\\{0,\dots,n-1\\}\\}$. Finally, it is also injective:
let $g=(k,w)\in\mathbb{Z}\times\mathbb{F}_{n}$, with
$w=(g_{i_{1}})^{e_{1}}\dots(g_{i_{N}})^{e_{N}}$ where the $e_{l}$ are in
$\\{-1,+1\\}$.

$\phi(g)=e\Leftrightarrow a^{nk}a^{i_{1}}b^{e_{1}}a^{-i_{1}}a^{i_{2}}\dots
a^{-i_{N-1}}a^{i_{N}}b^{e_{N}}a^{-i_{N}}=e$

This form is a canonical form in $H$: any word in $H$ can be uniquely written
as such. Indeed, any word in $H$ is a succession of generators of it,
$a^{i_{k}}b^{e_{k}}a^{-i_{k}}$ and $a^{n}$. But $a^{n}$ commutes with all the
other generators due to the relation of $BS(n,n)$, so such a form is always
attainable. To prove it is unique, it is enough to prove it for $e$: suppose
we have some $a^{nk}a^{i_{1}}b^{e_{1}}a^{-i_{1}}a^{i_{2}}\dots
a^{-i_{N-1}}a^{i_{N}}b^{e_{N}}a^{-i_{N}}=e$. First, realize that no relation
in $BS(n,n)$ allows to reduce the total power of $a$ in a word, causing $k=0$
necessarily. Then, consider the resulting word
$a^{i_{1}}b^{e_{1}}a^{i_{2}-i_{1}}\dots a^{i_{N}-i_{N-1}}b^{e_{N}}a^{-i_{N}}$
in $BS(n,n)$: it cannot be reduced in $BS(n,n)$ since all powers of $a$
between two $b$’s are of absolute value smaller than $n$.

As a consequence, the previous equality is true only when $k=0$ and
$w=\varepsilon$. Hence the injectivity of the map.

Moreover, any element of $BS(n,n)$ can be written in a form that much
resembles the one mentioned above:

$a^{p}a^{nk}a^{i_{1}}b^{e_{1}}a^{-i_{1}}\dots a^{i_{N}}b^{e_{N}}a^{-i_{N}}$

with $p\in\\{0,\dots,n-1\\}$. To do so, first move all $a^{n}$’s in the
rightmost power of $a$ in the word, to the leftmost part of the word. Ensure
that $-i_{N}$, the remaining power, is in $\\{-n+1,\dots,-1,0\\}$. Then force
$a^{i_{N}}$ to appear on the left of the $b$ itself to the left of
$a^{-i_{N}}$, and call $-i_{N-1}$ the remaining power of $a$ (it is in
$\\{-(n-1),\dots,-1,0\\}$ up to moving another $a^{n}$ to the leftmost part of
the word) before another $b$ to the left. Repeat this operation until there is
no $b$ to the left of the power of $a$ you consider, and split this final
$a^{K}$ into $a^{p}a^{nk}a^{i_{1}}$.

As a consequence,
$BS(n,n)/H=\\{\overline{e},\overline{a},\dots,\overline{a^{n-1}}\\}\cong\mathbb{Z}/n\mathbb{Z}$.
Hence $H$ is of finite index in $BS(n,n)$. ∎

######  Theorem 4.4.

For every $n\geq 2$, $BS(n,n)$ admits a strongly aperiodic SFT.

###### Proof.

First, finitely generated subgroups of compact groups of matrices on integers
are $PA^{\prime}$-recognizable (see [12], Proposition 5.12). $\mathbb{F}_{2}$,
the free group of order $2$, is isomorphic to a subgroup of
$SL_{2}(\mathbb{Z})$ (see [8, Lemma 2.3.2]), hence it is
$PA^{\prime}$-recognizable. It is also known (see [8, Corollary D.5.3]) that
$\mathbb{F}_{n}$ is a subgroup of $\mathbb{F}_{2}$; so it is isomorphic to a
subgroup of $SL_{2}(\mathbb{Z})$ and $PA^{\prime}$-recognizable too. Therefore
by Theorem 4.1 $\mathbb{Z}\times\mathbb{F}_{n}$ admits a strongly aperiodic
SFT. Using Proposition 4.2 and Proposition 4.3, we obtain that $BS(n,n)$
admits a strongly aperiodic SFT. ∎

## Conclusion

Baumlag-Solitar groups $BS(m,n)$ are residually finite if and only if $|m|=1$,
$|m|=1$ or $|m|=|n|$ (Proposition 1.1). Gathering results from Theorem 2.20,
Theorem 3.7 and Theorem 4.4, and considering that $BS(-m,-n)\cong
BS(-m,n)\cong BS(m,-n)\cong BS(m,n)$, we obtain the following:

######  Theorem 4.5.

Residually finite Baumslag-Solitar groups $BS(m,n)$ with $|m|\geq 2$ or
$|n|\geq 2$ admit both stronly and weakly-not-strongly aperiodic SFTs.

For non-residually finite Baumslag-Solitar groups, the existence of strongly
aperiodic STF is still an open question.

In Section 3, we showed how to encode a particular set of substitutions into a
tiling of $BS(1,n)$. An interesting question related to combinatorics on words
would be to characterize the sets of substitutions that can be encoded using
our technique. It is clear that the nature of $BS(1,n)$ impose some conditions
on these substitutions, and it would be of independent interest to obtain a
self-contained condition on the substitutions and study their properties.

## Acknowledgments

The authors would like to thank Nathalie Aubrun for the interest she sparked
about tilesets on the Baumslag-Solitar groups and the help she provided to
understand her joint work with Jarkko Kari. They also thank Silvère Gangloff
for pointing them to [11] that provided the missing piece to prove Lemma 2.15;
Jarkko Kari for his questions, that led to the writing of Section 3; and
Pierre Guillon for his many remarks and useful suggestions that made the paper
much more readable, even if it delayed a bit its publication.

The first author would like to thank Michael Schraudner and his PhD students
Álvaro Bustos and Hugo Maturana, under whose supervision Section 4 was
conceived as part of an internship, for their numerous insights in the proof
of said theorem.

This publication was made possible through the support of the ID#61466 grant
from the John Templeton Foundation, as part of the “The Quantum Information
Structure of Spacetime (QISS)” Project (qiss.fr). The opinions expressed in
this publication are those of the author(s) and do not necessarily reflect the
views of the John Templeton Foundation

## References

  * [1] N. Aubrun, S. Barbieri, and E. Jeandel.  About the domino problem for subshifts on groups.  In Trends in Mathematics, pages 331–389. Springer International Publishing, 2018.
  * [2] N. Aubrun, S. Barbieri, and E. Moutot.  The Domino Problem is Undecidable on Surface Groups.  In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), volume 138 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1–46:14, Dagstuhl, Germany, 2019\.
  * [3] N. Aubrun and J. Kari.  Tiling Problems on Baumslag-Solitar groups.  In MCU’13, pages 35–46, 2013.
  * [4] N. Aubrun and J. Kari.  Addendum to “Tilings problems on Baumslag-Solitar groups”.  Jan 2021.  arXiv: 2101.12470.
  * [5] R. Berger.  The Undecidability of the Domino Problem.  PhD thesis, Harvard University, 1964.
  * [6] D. Carroll and A. Penland.  Periodic points on shifts of finite type and commensurability invariants of groups.  New York Journal of Mathematics, 21, 2015.
  * [7] J. Cassaigne and F. Nicolas.  Factor complexity, pages 163–247.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2010.
  * [8] T. Ceccherini-Silberstein and M. Coornaert.  Cellular Automata and Groups.  Springer Monographs in Mathematics. Springer Berlin Heidelberg, 2010.
  * [9] D. Cohen and C. Goodman-Strauss.  Strongly aperiodic subshifts on surface groups.  Groups, Geometry, and Dynamics, 11(3):pp. 1041–1059, 2017.
  * [10] E. Coven and Z. Nitecki.  On the genesis of symbolic dynamics as we know it.  Colloquium Mathematicum, 110, 12 2006.
  * [11] B. Durand, G. Gamard, and A. Grandjean.  Aperiodic tilings and entropy.  In Developments in Language Theory, pages 166–177. Springer International Publishing, 2014.
  * [12] E. Jeandel.  Aperiodic Subshifts of Finite Type on Groups.  ArXiv e-prints, Jan. 2015.
  * [13] E. Jeandel and M. Rao.  An aperiodic set of 11 Wang tiles.  Advances in Combinatorics, Jan 2021.
  * [14] J. Kari.  On the undecidability of the tiling problem.  In Current Trends in Theory and Practice of Computer Science (SOFSEM), pages 74–82, 2008.
  * [15] D. A. Lind and B. Marcus.  An Introduction to Symbolic Dynamics and Coding.  Cambridge University Press, New York, NY, USA, 1995.
  * [16] S. Meskin.  Nonresidually Finite One-Relator Groups.  Transactions of the American Mathematical Society, 164:pp. 105–114, 1972.
  * [17] J.-J. Pansiot.  Decidability of periodicity for infinite words.  RAIRO - Theoretical Informatics and Applications, 20(1):pp. 43–46, 1986.
  * [18] R. M. Robinson.  Undecidability and nonperiodicity for tilings of the plane.  Inventiones Mathematicae, 12:pp. 177–209, 1971.
  * [19] J. Shallit and M.-w. Wang.  On two-sided infinite fixed points of morphisms.  In G. Ciobanu and G. Păun, editors, Fundamentals of Computation Theory, pages 488–499, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.
  * [20] H. Wang.  Proving theorems by pattern recognition II.  Bell System Technical Journal, 40(1-3):pp. 1–41, 1961.