# Local generation of tilings: the even bicolor Wang tilesets

Mathieu Hoyrup, Tom Favereau

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

## To cite this version:

Mathieu Hoyrup, Tom Favereau. Local generation of tilings: the even bicolor Wang tilesets. 2025. [https://arxiv.org/abs/2501.04876](https://arxiv.org/abs/2501.04876).

HAL Id: hal-04876051

https://inria.hal.science/hal-04876051v1

Preprint submitted on 9 Jan 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Local generation of tilings: the even bicolor Wang tilesets

Tom Favereau* and Mathieu Hoyrup†

November 13, 2024

Abstract

In this article, we apply the techniques developed in our previous article "Local generation of tilings", in which we introduced two definitions capturing the intuitive idea that some subshifts admit a procedure that can generate any tiling and working in a local way. We classify all the Wang tilesets with two colors in which each tile has an even number of each color.

Contents

<table><tr><td>1</td><td>Introduction</td><td>3</td></tr><tr><td>2</td><td>Background</td><td>3</td></tr><tr><td>2.1</td><td>Group actions</td><td>3</td></tr><tr><td>2.2</td><td>Symbolic dynamics</td><td>4</td></tr><tr><td>2.3</td><td>Dynamical properties</td><td>5</td></tr><tr><td>2.4</td><td>Local generation</td><td>5</td></tr><tr><td>2.5</td><td>Symmetry group</td><td>6</td></tr><tr><td>3</td><td>Subshifts that do not belong to L<sup>0</sup></td><td>7</td></tr><tr><td>3.1</td><td>Ramified subshift</td><td>7</td></tr><tr><td>3.2</td><td>Applications</td><td>8</td></tr><tr><td>3.3</td><td>First case: all the corners</td><td>8</td></tr><tr><td>3.4</td><td>Second case: missing corners</td><td>11</td></tr><tr><td>4</td><td>Subshifts that do not belong to L<sup>1</sup></td><td>14</td></tr><tr><td>5</td><td>Subshifts that belong to L<sup>0</sup></td><td>17</td></tr><tr><td>5.1</td><td>Corners and 2 even tiles</td><td>17</td></tr><tr><td>5.2</td><td>Corners and 3 even tiles</td><td>19</td></tr></table>

<footnote>*École des Mines de Nancy</footnote>

<footnote>†Université de Lorraine, CNRS, Inria, LORIA, Nancy, 54000, France</footnote>
<table>
  <tbody>
    <tr>
      <td>6</td>
      <td>Classification of the even bicolor tilesets</td>
      <td>20</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Even tilesets of size 1</td>
      <td>22</td>
    </tr>
    <tr>
      <td>6.1.1</td>
      <td>No corner</td>
      <td>22</td>
    </tr>
    <tr>
      <td>6.1.2</td>
      <td>One corner</td>
      <td>22</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Even tilesets of size 2</td>
      <td>22</td>
    </tr>
    <tr>
      <td>6.2.1</td>
      <td>No corner (first case)</td>
      <td>22</td>
    </tr>
    <tr>
      <td>6.2.2</td>
      <td>No corner (second case)</td>
      <td>22</td>
    </tr>
    <tr>
      <td>6.2.3</td>
      <td>One corner + one even tile</td>
      <td>23</td>
    </tr>
    <tr>
      <td>6.2.4</td>
      <td>Two opposite corners</td>
      <td>23</td>
    </tr>
    <tr>
      <td>6.2.5</td>
      <td>Two adjacent corners</td>
      <td>23</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>Even tilesets of size 3</td>
      <td>23</td>
    </tr>
    <tr>
      <td>6.3.1</td>
      <td>No corner</td>
      <td>23</td>
    </tr>
    <tr>
      <td>6.3.2</td>
      <td>One corner + two even tiles (first case)</td>
      <td>23</td>
    </tr>
    <tr>
      <td>6.3.3</td>
      <td>One corner + two even tiles (second case)</td>
      <td>24</td>
    </tr>
    <tr>
      <td>6.3.4</td>
      <td>Two adjacent corners + one even tile</td>
      <td>24</td>
    </tr>
    <tr>
      <td>6.3.5</td>
      <td>Two opposite corners + one even tile</td>
      <td>24</td>
    </tr>
    <tr>
      <td>6.3.6</td>
      <td>Three corners</td>
      <td>24</td>
    </tr>
    <tr>
      <td>6.4</td>
      <td>Even tilesets of size 4</td>
      <td>24</td>
    </tr>
    <tr>
      <td>6.4.1</td>
      <td>No corner</td>
      <td>25</td>
    </tr>
    <tr>
      <td>6.4.2</td>
      <td>One corner + three even tiles</td>
      <td>25</td>
    </tr>
    <tr>
      <td>6.4.3</td>
      <td>Two adjacents corners + two even tiles (first case)</td>
      <td>25</td>
    </tr>
    <tr>
      <td>6.4.4</td>
      <td>Two adjacent corners + two even tiles (second case)</td>
      <td>25</td>
    </tr>
    <tr>
      <td>6.4.5</td>
      <td>Two adjacent corners + two even tiles (third case)</td>
      <td>25</td>
    </tr>
    <tr>
      <td>6.4.6</td>
      <td>Two opposite corners + two even tiles (first case)</td>
      <td>26</td>
    </tr>
    <tr>
      <td>6.4.7</td>
      <td>Two opposite corners + two even tiles (second case)</td>
      <td>26</td>
    </tr>
    <tr>
      <td>6.4.8</td>
      <td>Three corners + one even tile</td>
      <td>26</td>
    </tr>
    <tr>
      <td>6.4.9</td>
      <td>Four corners</td>
      <td>26</td>
    </tr>
    <tr>
      <td>6.5</td>
      <td>Even tilesets of size 5</td>
      <td>26</td>
    </tr>
    <tr>
      <td>6.5.1</td>
      <td>One corner + four even tiles</td>
      <td>26</td>
    </tr>
    <tr>
      <td>6.5.2</td>
      <td>Two adjacent corners + three even tiles</td>
      <td>27</td>
    </tr>
    <tr>
      <td>6.5.3</td>
      <td>Two opposite corners + three even tiles</td>
      <td>27</td>
    </tr>
    <tr>
      <td>6.5.4</td>
      <td>Three corners + two even tiles (first case)</td>
      <td>27</td>
    </tr>
    <tr>
      <td>6.5.5</td>
      <td>Three corners + two even tiles (second case)</td>
      <td>27</td>
    </tr>
    <tr>
      <td>6.5.6</td>
      <td>Four corners + one even tile</td>
      <td>28</td>
    </tr>
    <tr>
      <td>6.6</td>
      <td>Even tilesets of size 6</td>
      <td>28</td>
    </tr>
    <tr>
      <td>6.6.1</td>
      <td>Two adjacent corners + four even tiles</td>
      <td>28</td>
    </tr>
    <tr>
      <td>6.6.2</td>
      <td>Two opposite corners + four even tiles</td>
      <td>28</td>
    </tr>
    <tr>
      <td>6.6.3</td>
      <td>Three corners + three even tiles</td>
      <td>28</td>
    </tr>
    <tr>
      <td>6.6.4</td>
      <td>Four corners + two even tiles (first case)</td>
      <td>29</td>
    </tr>
    <tr>
      <td>6.6.5</td>
      <td>Four corners + two even tiles (second case)</td>
      <td>29</td>
    </tr>
    <tr>
      <td>6.7</td>
      <td>Even tilesets of size 7</td>
      <td>29</td>
    </tr>
  </tbody>
</table>
<table><tr><td>6.7.1</td><td>Three corners + four even tiles</td><td>29</td></tr><tr><td>6.7.2</td><td>Four corners + three even tiles</td><td>29</td></tr><tr><td>6.8</td><td>Even tileset of size 8</td><td>29</td></tr><tr><td>6.8.1</td><td>All the even tiles</td><td>30</td></tr></table>

## Acknowledgements

30

# 1 Introduction

In [FH24], we have introduced two classes of subshifts, $\mathcal{L}^0 \subseteq \mathcal{L}^1$, that are intended to capture the intuitive idea that certain subshifts admit a procedure that can generate all their tilings in a local way.

In the present article, we classify all the Wang tilesets consisting of bicolor tiles having an even number of each color, according to these classes. Although there are 255 such non-empty tilesets, their symmetries reduce that number to 36 equivalence classes. We find that 13 of them belong to $\mathcal{L}^0$, 8 do not belong to $\mathcal{L}^0$ and 7 do not belong to $\mathcal{L}^1$ (the other 8 equivalence classes of tilesets contain a tile that cannot be used in a tiling, therefore they induce the same subshift as a smaller tileset). We conjecture that the 8 classes of tilesets that do not belong to $\mathcal{L}^0$ do not belong to $\mathcal{L}^1$ either.

The article is organized as follows. In Section 2, we recall the notions of local generations introduced in [FH24]. Section 3 gathers the tilesets that do not belong to $\mathcal{L}^0$. The tilesets that do not belong to $\mathcal{L}^1$ are presented in Section 4. In Section 5, we show that all the other tilesets belong to $\mathcal{L}^0$. Section 6 summarizes the results by listing all the equivalence classes of even bicolor Wang tilesets, and their classification w.r.t. the classes $\mathcal{L}^0$ and $\mathcal{L}^1$.

# 2 Background

Let us first recall the classical definitions needed for this article.

## 2.1 Group actions

For $d \ge 1$, $(\mathbb{Z}^d, +, 0)$ is an abelian group. A $\mathbb{Z}^d$-action on a set $E$ is a homomorphism from $\mathbb{Z}^d$ to the group of bijections from $E$ to $E$ with the composition operation. We also say that $E$ is a $\mathbb{Z}^d$-set. The result of applying the image of $p \in \mathbb{Z}^d$ under the homomorphism to $e \in E$ is written as $p \cdot e \in E$. A continuous $\mathbb{Z}^d$-action on a topological space $X$ is a homomorphism from $\mathbb{Z}^d$ to the group of homeomorphisms from $X$ to $X$ with the composition operation. We also say that $X$ is a $\mathbb{Z}^d$-space. A $\mathbb{Z}^d$-space $Y$ is a factor of a $\mathbb{Z}^d$-space $X$ if there exists a continuous surjective map $f: X \to Y$ that commutes with the actions: $p \cdot f(x) = f(p \cdot x)$. $f$ is called a factor map. If $f$ is a homeomorphism, then $f$ is a conjugacy and $X$ and $Y$ are conjugate.
A $\mathbb{Z}^e$-space $Y$ is a **weak factor** of a $\mathbb{Z}^d$-space $X$ if there exists a continuous surjective map $f: X \to Y$ and a group homomorphism $\varphi: \mathbb{Z}^e \to \mathbb{Z}^d$ such that $p \cdot f(x) = f(\varphi(p) \cdot x)$. If $f$ is a homeomorphism and $\varphi$ is an isomorphism, then $X$ and $Y$ are **weakly conjugate** (see [FH24, Definition 3.2]).

## 2.2 Symbolic dynamics

If $A$ is a finite alphabet and $E$ is countable, then $A^E$ is endowed with the Cantor topology, which is the product of the discrete topology on $A$. This makes $A^E$ a compact metrizable space. The **shift action** on $A^{\mathbb{Z}^d}$ is the continuous $\mathbb{Z}^d$-action defined, for $p \in \mathbb{Z}^d$ and $x \in A^{\mathbb{Z}^d}$, by $p \cdot x = y$ where $y(q) = x(p+q)$. A $\mathbb{Z}^d$-**subshift** is a compact set $X \subseteq A^{\mathbb{Z}^d}$ which is shift-invariant, i.e. satisfies $\sigma^p(X) = X$ for all $p \in \mathbb{Z}^d$. A $\mathbb{Z}^d$-**fullshift** is $A^{\mathbb{Z}^d}$ for some finite alphabet $A$. If $H$ is a subgroup of $\mathbb{Z}^d$, then a configuration $x \in A^{\mathbb{Z}^d}$ is $H$-**periodic** if $x(p+h) = x(p)$ for all $p \in \mathbb{Z}^d$ and $h \in H$. The $H$-**periodic shift** over $\Sigma$ is the subshift $X_H \subseteq \Sigma^{\mathbb{Z}^d}$ defined as the set of all the $H$-periodic configurations.

Let $d \ge 1$ and $\Sigma$ a finite alphabet. We endow $\mathbb{Z}^d$ with the metric $d(p, q) = \max_i |p_i - q_i|$, where $p = (p_1, \dots, p_d)$ and $q = (q_1, \dots, q_d)$. For $F \subseteq \mathbb{Z}^d$, $\text{diam}(F) = \max_{p,q \in F} d(p, q)$, which is $\infty$ if $F$ is infinite. For $F, G \subseteq \mathbb{Z}^d$, $d(F, G) = \min_{p \in F, q \in G} d(p, q)$. We will often consider the **cubes** $S_n = [0, n-1]^d$ and $Q_n = [-n, n]^d$, for $n \in \mathbb{N}$.

Let $F \subseteq \mathbb{Z}^d$ be any set. An **F-pattern** is an element $\pi \in \Sigma^F$. A **pattern** is an $F$-pattern for some $F$, which is called the **domain** of $\pi$ and is denoted by $\text{dom}(\pi)$. A pattern $\pi'$ extends a pattern $\pi$ if $\text{dom}(\pi) \subseteq \text{dom}(\pi')$ and $\pi'(p) = \pi(p)$ for all $p \in \text{dom}(\pi)$. A **finite pattern** is an $F$-pattern for some finite $F \subseteq \mathbb{Z}^d$. If $\pi, \pi'$ are patterns with disjoint domains $F, F'$ respectively, then $\pi \cup \pi'$ is the pattern with domain $F \cup F'$ extending $\pi$ and $\pi'$. A **configuration** is an element $x \in \Sigma^{\mathbb{Z}^d}$.

If $\pi$ is a pattern, then $[\pi]$ is the set of configurations extending $\pi$. The set $\Sigma^{\mathbb{Z}^d}$ is endowed with the topology generated by the sets $[\pi]$ where $\pi$ is a finite pattern. As already mentioned, the space $\Sigma^{\mathbb{Z}^d}$ is endowed with the **shift action**, which is the continuous $\mathbb{Z}^d$-action $p \cdot x = y$ where $y(q) = x(p+q)$. We will often write $\sigma^p(x) := p \cdot x$. The shift also acts on patterns: if $\pi$ is an $F$-pattern, then $\sigma^p(\pi)$ is the $F'$-pattern $\pi'$ where $F' = F - p$ and $\pi'(q) = \pi(p+q)$ for $q \in F'$. If $p \in \mathbb{Z}^d$ and $x$ is a configuration, then we say that a pattern $\pi$ **appears at position $p$ in $x$** if $\sigma^p(x)$ extends $\pi$.

A **subshift** is a closed subset $X$ of $\Sigma^{\mathbb{Z}^d}$ which is **shift-invariant**, i.e. satisfies $\sigma^p(X) = X$ for all $p \in \mathbb{Z}^d$. We fix a subshift $X \subseteq \Sigma^{\mathbb{Z}^d}$. All the subsequent notions are relative to $X$, but we do not mention $X$ which will always be clear from the context. A **valid configuration** is an element $x \in X$. A **valid pattern** is a pattern appearing in some valid configuration, at any position or equivalently at the origin. Two disjoint regions $F, G \subseteq \mathbb{Z}^d$ are **independent** if for every valid $F$-pattern $\pi$ and every valid $G$-pattern $\pi'$, $\pi \cup \pi'$ is valid.

A **subshift of finite type (SFT)** is the subshift induced by a finite set $P$ of finite patterns, called forbidden patterns, and defined as the set of configurations in which no $\pi \in$
P appears. Let C be a finite set of colors. A **Wang tile** over C associates to each edge of the unit square a color in C. A **Wang tileset** over C is a set T of Wang tiles over C. It induces a $\mathbb{Z}^2$-subshift of finite type $X_T \subseteq T^{\mathbb{Z}^2}$ which is the set of configurations in which neighbor cells have the same color on their common edge.

## 2.3 Dynamical properties

We recall classical dynamical properties of subshifts, that can be found in [Fur67] or [dV13].

**Definition 2.1.** A subshift $X \subseteq \Sigma^{\mathbb{Z}^d}$ is **transitive** if for every pair of valid finite patterns $\pi, \pi'$, there exists $p \in \mathbb{Z}^d$ such that $\pi \cup \sigma^p(\pi')$ is a valid pattern; in other words, $\pi$ and $\pi'$ appear in a common configuration.

A subshift $X \subseteq \Sigma^{\mathbb{Z}^d}$ is **strongly irreducible** if there exists $n \in \mathbb{N}$ such that all regions $F, G \subseteq \mathbb{Z}^d$ satisfying $d(F, G) \ge n$ are independent.

A subshift $X \subseteq \Sigma^{\mathbb{Z}^d}$ is **mixing** if for every $m \in \mathbb{N}$ there exists $n \in \mathbb{N}$ such that all regions $F, G \subseteq \mathbb{Z}^d$ satisfying $\text{diam}(F) \le m$, $\text{diam}(G) \le m$ and $d(F, G) \ge n$ are independent.

A subshift $X \subseteq \Sigma^{\mathbb{Z}^d}$ is **weakly mixing** if $X \times X$ is transitive, equivalently if for every $n \in \mathbb{N}$, there exists $p \in \mathbb{Z}^d$ such that $Q_n$ and $p+Q_n$ are independent.

The equivalent definition of weak mixing was proved in [FH24].

One has the following chain of implications:

strongly irreducible $\implies$ mixing $\implies$ weakly mixing $\implies$ transitive.

## 2.4 Local generation

We recall the notions of local generation introduced in [FH24].

**Definition 2.2 (The class $\mathcal{L}^0$).** Let $d \ge 1$. We define $\mathcal{L}_d^0$ as the smallest class of subshifts containing the $\mathbb{Z}^d$-fullshifts, the periodic $\mathbb{Z}^d$-shifts and the countable $\mathbb{Z}^d$-subshifts, and which is closed under finite products and factors. Let $\mathcal{L}^0 = \bigsqcup_{d \ge 1} \mathcal{L}_d^0$.

Let $A, B$ be finite alphabets, $E, F$ be countable sets and $f: A^E \to B^F$ be continuous w.r.t. the product topologies. To each $q \in F$ is associated $W_f(q) \subseteq E$, which is the minimal region on which the values of any $x \in A^E$ determine the value of $f(x)$ at $q$.

**Definition 2.3 (Narrow function).** Let $r \in \mathbb{N}$. A continuous function $f: A^E \to B^F$ is **r-narrow** if for all $q \in F$, $|W_f(q)| \le r$. We say that $f$ is **narrow** if it is $r$-narrow for some $r \in \mathbb{N}$.

Note that a function is 0-narrow if and only if it is constant. The identity $f: A^E \to A^E$ is 1-narrow. The composition of two narrow functions is narrow.

We come to the second notion of local generation. Let $\Sigma$ be finite and $F$ be countable.
**Definition 2.4** (The class $\mathcal{L}^1$). A compact set $X \subseteq \Sigma^F$ belongs to $\mathcal{L}^1$ if it is a countable union of images of narrow functions, i.e. $X = \bigcup_{n \in \mathbb{N}} X_n$ where $X_n = \text{im}(f_n)$ and $f_n : A_n^{\mathbb{N}} \to X$ is $r_n$-narrow.

The second notion of local generation is a relaxation of the first one [FH24, Propositions 2.4 and 4.10].

**Proposition 2.1.** One has $\mathcal{L}^0 \subsetneq \mathcal{L}^1$.

## 2.5 Symmetry group

We are going to analyze bicolor Wang tilesets. There are $2^4 = 16$ possible tiles, so $2^{16} - 1 = 65535$ possible tilesets (excluding the empty tileset). We can reduce the number of cases by observing that there is a group of order 32 acting on bicolor tilesets, such that two tilesets that are equivalent under this group action induce weakly conjugate subshifts, so we only need to consider one representative for each equivalence class. A computer program shows that there are 2890 equivalence classes. This number is still large for a systematic classification, so in this article we only consider the **even bicolor tilesets**, which only use tiles having an even number of edges of each color. There are 8 even tiles, which we draw using wires instead of colors for aesthetic reasons: $\square$, $\square$, $\square$, $\square$, $\square$, $\square$, $\square$, $\square$. There $2^8 - 1 = 255$ even non-empty tilesets, and a computation shows that there are 36 equivalence classes under the symmetry group action.

Let us describe the symmetry group. It contains:

* Eight geometric transformations:

- Rotations by 0, 90, 180 or 270 degrees,

- Reflections across the horizontal, vertical or one of the diagonal axes,

* Chromatic transformations:

- Complementation of the colors on the horizontal edges, or on the vertical edges, or both,

* Combinaison of a geometric and a chromatic transformation.

The geometric transformations are elements of the dihedral group $D_4$, which is the symmetry group of the square. The chromatic transformations are elements of the Klein group $K_4 = \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$. These two types of transformations do not commute, but $K_4$ is a normal subgroup of $G$ so $G$ is a semidirect product $K_4 \times_{\phi} D_4$ for some homomorphism $\phi : D_4 \to \text{Aut}(K_4)$, therefore $G$ has order $|D_4| \times |K_4| = 8 \times 4 = 32$. The homomorphism $\phi$ sends the rotation by 90 degrees to the permutation between horizontal and vertical color complementations, and sends reflections to the identity. It corresponds
to the fact that a rotation followed by a horizontal color complementation equals a vertical color complementation followed by the rotation, and that a reflection and a color complementation commute.

**Proposition 2.2.** For every bicolor tileset $T$ and every $g \in G$, $T$ and $g \cdot T$ induce weakly conjugate subshifts.

*Proof.* Each geometric $g$ transformation induces a geometric equivalence as in Example 3.2 in [FH24]. Each chromatic transformation induces a conjugacy. These two types of transformations generate the group and weak conjugacy between subshifts is transitive, so every group element induces a weak conjugacy between subshifts. $\square$

# 3 Subshifts that do not belong to $\mathcal{L}^0$

We first recall the main technique developed in [FH24] to show that a two-dimensional subshift does not belong to $\mathcal{L}^0$, and then apply it to the even bicolor tilesets.

## 3.1 Ramified subshift

We recall the following notions introduced in [FH24], where they are discussed in more details.

If $F \subseteq \mathbb{Z}^2$ and $r \in \mathbb{N}$, then let $\mathcal{N}(F, r) = \{p : \exists q \in F, d(p, q) \le r\}$ be the $r$-neighborhood of $F$.

**Definition 3.1 (Graft).** Let $X$ be a $\mathbb{Z}^2$-subshift, $F \subseteq \mathbb{Z}^2$, $\pi$ an $F$-pattern, $x \in X$ and $r \in \mathbb{N}$. We say that $\pi$ can be **r-grafted into** $x$ **at position** $p \in \mathbb{Z}^2$ if there exists $y \in X$ that coincides with $x$ outside $\mathcal{N}(p + F, r)$ and such that $\pi$ appears at position $p$ in $y$, i.e. $y(p + q) = \pi(q)$ for $q \in F$.

**Definition 3.2 (Ramification).** Let $X$ be a $\mathbb{Z}^2$-subshift. A ramification is a configuration $x \in X$ together with $r \in \mathbb{N}$, $u, v \in \mathbb{Z}^2$ and $F \subseteq \mathbb{Z}^2$ such that for all $\lambda, \mu \in \mathbb{Z}$ with $\mu > 0$, the $F$-pattern appearing at position $\mu u + \lambda v$ in $x$ cannot be $r$-grafted into $x$ at position $\lambda v$. We say that $x$ is an $(r, v)$-ramification.

Say that two vectors $v_1, v_2 \in \mathbb{Z}^2$ are **independent** if $\lambda_1 v_1 + \lambda_2 v_2 = 0$ implies $\lambda_1 = \lambda_2 = 0$, for $\lambda_1, \lambda_2 \in \mathbb{Z}$.

**Definition 3.3 (Ramified subshift).** A $\mathbb{Z}^2$-subshift $X$ is **ramified** if for every $r \in \mathbb{N}$ there exist infinitely many pairwise independent vectors $v$ such that $X$ admits a ramification of radius $r$ and support $v$.

If $r < r'$, then an $(r', v)$-ramification is also an $(r, v)$-ramification so, in order to show that $X$ is ramified, it is sufficient to build a sequence $(v_r)_{r \in \mathbb{N}}$ of pairwise independent vectors such that $X$ admits an $(r, v_r)$-ramification for each $r$.
Remark 3.1 (Subshift of a ramified subshift). As observed in [FH24, Remark 5.1] if $T$ is a Wang tileset and $X_T$ has ramifications that can all be built using a proper subset of tiles $R \subsetneq T$, then for each tileset $S$ such that $R \subseteq S \subseteq T$, $X_S$ is ramified as well.

If a subshift is ramified, then it is not strongly irreducible. Actually, showing the lack of strong irreducibility will always be the first step when building ramifications.

The main technique to prove that a subshift is not in $\mathcal{L}^0$ is Theorem 5.1 in [FH24].

**Theorem 3.1** (An obstruction to being in $\mathcal{L}^0$). Let $X$ be a $\mathbb{Z}^2$-subshift. If $X$ is ramified and weakly mixing, then $X \notin \mathcal{L}^0$.

## 3.2 Applications

There are exactly 8 equivalence classes of even bicolor tilesets to which Theorem 3.1 can be applied.

**Theorem 3.2.** The subshifts induced by the following tilesets are ramified and mixing, therefore do not belong to $\mathcal{L}^0$:

$$ T_1 = \Box \Box \Box \Box \qquad (\text{Class 6.4.7}) $$

$$ T_2 = \Box \Box \Box \Box \qquad (\text{Class 6.5.3}) $$

$$ T_3 = \Box \Box \Box \Box \qquad (\text{Class 6.5.5}) $$

$$ T_4 = \Box \Box \Box \Box \qquad (\text{Class 6.5.6}) $$

$$ T_5 = \Box \Box \Box \Box \Box \qquad (\text{Class 6.6.2}) $$

$$ T_6 = \Box \Box \Box \Box \Box \qquad (\text{Class 6.6.3}) $$

$$ T_7 = \Box \Box \Box \Box \Box \qquad (\text{Class 6.6.4}) $$

$$ T_8 = \Box \Box \Box \Box \Box \Box \qquad (\text{Class 6.7.1}) $$

We do not know whether these subshifts belong to $\mathcal{L}^1$ and leave it as an open question (see Section 4 for further discussion).

We do not need a specific argument for each one of the 8 tilesets listed above, but an argument for the 2 tilesets $T_4$ and $T_7$ containing the corners $\Box$, $\Box$, $\Box$ and $\Box$, and an argument for the other 6.

## 3.3 First case: all the corners

We prove Theorem 3.2 for the following tilesets:

$$ T_4 = \Box \Box \Box \Box \Box \qquad (\text{Class 6.5.6}) $$

$$ T_7 = \Box \Box \Box \Box \Box \Box \qquad (\text{Class 6.6.4}) $$
We start by showing that the subshift $X_{T_7}$ is ramified.

First, $X_{T_7}$ is not strongly irreducible: a diagonal $D_r := \{(x, x) : 0 \le x \le r\}$ filled with the tile $\Box$ entirely determines the lower triangle $\{(x, y) : 0 \le x \le r, 0 \le y \le x\}$ and in particular the cell $C_r := (r, 0)$ (see Figure 1). Therefore, $D_r$ and $C_r$ are not independent and $d(D_r, C_r) = \lceil \frac{r}{2} \rceil$ can be arbitrarily large.

<figure><img src="image_3.png" /><figcaption>Figure 1: $X_{T_7}$ is not strongly irreducible: the purple and green regions are not independent, and can be taken arbitrarily far from each other.</figcaption></figure>

We then create ramifications illustrated in Figure 2, showing that $X_{T_7}$ is ramified. It is clear from the picture that $(r, v)$-ramifications can be built for any $r$ and any $v = (n, 1)$ if $n$ is sufficiently large. We assume that the picture is self-explanatory and does not need a formal argument.

These ramifications do not use the tile $\Box$, i.e. belong to $X_{T_4}$ which is therefore ramified as well by Remark 3.1.

<figure><img src="image_4.png" /><figcaption>Figure 2: A ramification in $X_{T_4}$ and $X_{T_7}$: the content of a red cell cannot be grafted in a green cell without changing the content of the corresponding purple region. The distance $r$ between the purple and green regions can be made arbitrary large by increasing the number of stairs. The vector $v$ between two consecutive green cells can take value $(n, 1)$ for any sufficiently large $n$. One has $u = (0, -1)$ and $F = \{(0, 0)\}$</figcaption></figure>

We now prove that both subshifts are mixing, by showing that any finite pattern can be extended to a finite pattern with white boundary.

**Lemma 3.1.** For both $T_4$ and $T_7$, any valid pattern on $[0, n-1]^2$ can be extended to a valid pattern on $[-2n, 2n-1]^2$ whose boundary is completely white.
*Proof.* Let us first show the result for $X_{T_4}$. Let $\pi$ be a valid $[0, n-1]^2$-pattern. We first extend $\pi$ to a valid $[0, 2n-1]^2$-pattern whose right and upper boundaries are white.

Let $u_0 \in \{0, 1\}^n$ be the upper boundary of $\pi$. We inductively define $u_i, \dots, u_n \in \{0, 1\}^n$ as follows. Let $i < n$ and assume that $u_i$ has been defined. Decompose $u_i$ as a concatenation of the strings 11, 01 and 0, with possibly a single string 1 at the beginning, and note that the decomposition is unique because these strings are not suffixes of each other, so starting from the end of $u_i$, the choice is always unique. Then define $u_{i+1}$ from $u_i$ by replacing 11 with 00, 01 with 10, 0 with 0, and the possible 1 at the beginning with 0. Several observations can be made: the string 11 can appear only in $u_0$; the position of the rightmost 1 in $u_i$ is strictly increasing in $i$, so $u_n = 0^n$.

We can define a $[0, n-1] \times [n, 2n-1]$-pattern whose lower boundary is $u_0$, such that row $n+i$ has lower boundary $u_i$ and upper boundary $u_{i+1}$ (in particular the upper boundary of the pattern is $u_n$, i.e. it is white), and whose right boundary is white (see Figure 3).

<figure><img src="image_5.png" /><figcaption>Figure 3: Filling the row between $u_i$ and $u_{i+1}$.</figcaption></figure>

In the same way, we can define a $[n, 2n-1] \times [0, n-1]$-pattern whose left-boundary is the right-boundary of $\pi$ and whose right and upper boundaries are white (apply the same technique up to a symmetry across the diagonal).

Then fill the rectangle $[n, 2n-1]^2$ with white tiles. We obtain a $[0, 2n-1]^2$-pattern extending $\pi$, whose right and upper boundaries are white. We then copy symmetric versions of this pattern to fill $[-2n, 2n-1]^2$ (see Figure 4), which is possible because applying a symmetry to each tile yields a tile that belongs to the tileset.

<figure><img src="image_6.png" /><figcaption>Figure 4: Extending $\pi$.</figcaption></figure>

Observe that the same construction can be applied to $X_{T_7}$, because $T_7$ contains $T_4$ and has the same symmetries. $\square$

Finally, the following argument applies to both $X_{T_4}$ and $X_{T_7}$. For $m \in \mathbb{N}$, let $n = 4m+1$. Let $F, G \subseteq \mathbb{Z}^2$ be squares of side length $m$ satisfying $d(F, G) \ge n$. If $\pi, \pi'$ are valid
patterns on $F$ and $G$ respectively, then by Lemma 3.1 they can be extended on the larger squares $\mathcal{N}(F, 2m)$ and $\mathcal{N}(G, 2m)$ to valid patterns with white boundaries. These larger squares are disjoint, so one can fill the rest of the plane with white cells, yielding a valid configuration and shows that $F$ and $G$ are independent. Therefore, both tilesets are mixing.

## 3.4 Second case: missing corners

We now prove Theorem 3.2 for the other tilesets:

$$ T_1 = \Box \Box \Box \Box \qquad (\text{Class 6.4.7}) $$

$$ T_2 = \Box \Box \Box \Box \Box \qquad (\text{Class 6.5.3}) $$

$$ T_3 = \Box \Box \Box \Box \Box \qquad (\text{Class 6.5.5}) $$

$$ T_5 = \Box \Box \Box \Box \Box \Box \qquad (\text{Class 6.6.2}) $$

$$ T_6 = \Box \Box \Box \Box \Box \Box \qquad (\text{Class 6.6.3}) $$

$$ T_8 = \Box \Box \Box \Box \Box \Box \Box \qquad (\text{Class 6.7.1}) $$

Note that all these tilesets contain $T_1$ and are contained in $T_8$.

Figure 5 illustrates that $X_{T_8}$ is not strongly irreducible. The only tile having a black left edge and a white upper edge is $\Box$, therefore a diagonal made of this tile forces the lower triangle to be filled with the same tile.

<figure><img src="image_7.png" /><figcaption>Figure 5: The subshifts are not strongly irreducible: the purple diagonal and the green cell are not independent.</figcaption></figure>

This lack of strong irreducibility can be turned into ramifications, illustrated in Figure 6. These ramifications only use the tiles from $T_1$, so all the tilesets are ramified by Remark 3.1.

We finally show that all these tilesets induce mixing subshifts. We need two different arguments, depending on whether the tilesets contain $\Box$, presented as Lemmas 3.2 and 3.3 below.

**Lemma 3.2.** The tilesets $T_1 = \Box \Box \Box \Box$ and $T_3 = \Box \Box \Box \Box \Box$ induce mixing subshifts.

*Proof.* Let $S_n = [0, n-1]^2$. We show that if $|p| \ge 7n$, then $S_n$ and $p+S_n$ are independent. Let $p = (i, j)$, there are two cases: either $|j| \ge 3n$ or $|j| < 3n$. The argument is illustrated in Figure 7.
<figure><img src="image_8.png" /><figcaption>Figure 6: A ramification: the content of a red cell cannot be grafted in a green cell without changing the content of the corresponding purple region. The distance $r$ between the purple and green regions can be made arbitrary large by increasing the number of stairs. The vector $v$ between two consecutive green cells can take value $(n, 1)$ for any sufficiently large $n$. One has $u = (0, -1)$ and $F = \{(0, 0)\}$</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 7: Extending a pattern $\pi$ from a square to an infinite strip with white boundaries</figcaption></figure>

First assume that $|j| \ge 3n$, i.e. $p+S_n$ is vertically far from $S_n$. Any valid $S_n$-pattern $\pi$ can be extended to a valid pattern on the horizontal strip $\mathbb{Z} \times [-n, 2n-1]$ whose upper and lower boundaries are white (see Figure 7a). An important point is that the two tilesets considered here do not allow two adjacent horizontal edges to be black, because there is no way of placing matching tiles above them. Therefore, the upper and lower boundaries of $\pi$ cannot contain two consecutive black edges, which enables one to make stairs grow out of these boundaries. Therefore, any valid pattern $\pi'$ on $p+S_n$ can be extended to a valid pattern on $\mathbb{Z} \times [j-n, j+2n-1]$ in a similar way. As $|j| \ge 3n$, these strips are disjoint and we can fill the other cells with the white tile, yielding a valid configuration extending $\pi \cup \pi'$, so $S_n$ and $p+S_n$ are independent.

Now assume that $|j| < 3n$, which implies $|i-j| \ge |i|-|j| > 4n$. Any valid $S_n$-pattern $\pi$
can be extended to a valid pattern on the diagonal strip $D = \{(k,l) : |k-l| \le 2n\}$ with white boundaries (see Figure 7b). Therefore, any valid pattern $\pi'$ on $p+S_n$ can be extended to a valid pattern on $p+D = \{(k,l) : |k-i-l+j| \le 2n\}$. The strips $D$ and $p+D$ are disjoint, because $4n < |i-j| \le |(k-i)-(l-j)| + |k-l|$, so $(k,l)$ cannot belong both to $D$ and $p+D$. Again, one can fill all the other cells with the white tile, yielding a valid extension of $\pi \cup \pi'$, so $S_n$ and $p+S_n$ are independent.

Note that the extensions do not use the tile $\square$, so they apply to both tilesets. $\square$

We now give an argument for the tilesets containing $\square$.

**Lemma 3.3.** If a bicolor tileset contains $T_2 = \square \sqcup \square \sqcup \square \sqcup \square$, then it induces a mixing subshift.

*Proof.* Let again $S_n = [0, n-1]^2$. We show that if $|p| \ge 3n$, then $S_n$ and $S_n$ are independent. Let $p = (i, j)$, there are two cases: $|i| \ge 3n$ or $|j| \ge 3n$. The argument is illustrated in Figure 8.

<figure><img src="image_10.png" /><figcaption>Figure 8: Extending a pattern $\pi$ from a square to an infinite strip with white boundaries</figcaption></figure>

First assume that $|j| \ge 3n$, i.e. that $p+S_n$ is vertically far from $S_n$. A valid $S_n$-pattern $\pi$ can be first extended using $T_2$ to a valid pattern on $[0, n-1] \times [-n, 2n-1]$-pattern whose upper and lower boundaries are white, and then extended using $T_2$ to a valid pattern on the horizontal strip $\mathbb{Z} \times [-n, 2n-1]$ whose upper and lower boundaries are white (see Figure 8a. Therefore, $S_n$ and $p+S_n$ are independent because valid patterns on these squares can be extended to valid patterns on two disjoint horizontal strips, which can be jointly extended by using the white tile on the other cells.

Now assume that $|i| \ge 3n$, i.e. $p+S_n$ is horizontally far from $S_n$. A symmetric construction can be made to extend a valid $S_n$-pattern to a valid pattern on the vertical strip $[-n, 2n-1] \times \mathbb{Z}$ with white left and right boundaries (consider a symmetry across the diagonal and note that it preserves $T_2$, see Figure 8b), so the same argument shows that $S_n$ and $p+S_n$ are independent. $\square$
# 4 Subshifts that do not belong to $\mathcal{L}^1$

The main technique to prove that a subshift does not belong to $\mathcal{L}^1$ is Theorem 6.1 from [FH24]. It involves $\overline{\mathbb{Z}}$, which is the one-dimensional SFT on the alphabet $\{\Box, \blacksquare\}$ with forbidden pattern $\blacksquare$.

**Theorem 4.1** (An obstruction to being in $\mathcal{L}^1$). Let $X$ be a $\mathbb{Z}^d$-subshift. If $X$ is weakly mixing and $\overline{\mathbb{Z}}$ is a weak factor of $X$, then $X \notin \mathcal{L}^1$.

Among the 36 equivalence classes of even bicolor tilesets, there are exactly 6 classes to which Theorem 4.1 can be applied, and therefore do not belong to $\mathcal{L}^1$. There is a 7th even bicolor tileset to which Theorem 4.1 cannot be applied because it is not weakly mixing, but which is not in $\mathcal{L}^1$ by a similar argument (see below).

In Theorem 3.2 we identified tilesets that do not belong to $\mathcal{L}^0$. We expect that they do not belong to $\mathcal{L}^1$ either, but have not been able to prove it so far. The technique used in this section, namely Theorem 4.1, cannot be applied to them because they are all mixing and Proposition 3.4 in [FH24] prevents $\overline{\mathbb{Z}}$ from being a weak factor of a mixing subshift, because $\overline{\mathbb{Z}}$ is neither periodic nor mixing.

**Theorem 4.2.** The subshifts induced by the following tilesets are weakly mixing and weak factor to $\overline{\mathbb{Z}}$; therefore, they do not belong to $\mathcal{L}^1$:

$$T_1 = \Box \Box \Box \Box \qquad (\text{Class 6.4.2})$$

$$T_2 = \Box \Box \Box \Box \qquad (\text{Class 6.4.4})$$

$$T_3 = \Box \Box \Box \Box \Box \qquad (\text{Class 6.5.1})$$

$$T_4 = \Box \Box \Box \Box \Box \qquad (\text{Class 6.5.2})$$

$$T_5 = \Box \Box \Box \Box \Box \qquad (\text{Class 6.5.4})$$

$$T_6 = \Box \Box \Box \Box \Box \Box \qquad (\text{Class 6.6.1})$$

The subshift induced by the following tileset does not belong to $\mathcal{L}^1$:

$$T_7 = \Box \Box \Box \Box \qquad (\text{Class 6.4.3})$$

The proof is separated in several statements.

**Lemma 4.1.** The subshifts induced by tilesets $T_1$ to $T_7$ weak factor to $\overline{\mathbb{Z}}$.

*Proof.* Let $T$ be one of those tilesets except $T_5$. Let $f: X_T \to \{\Box, \blacksquare\}^{\mathbb{Z}}$ extract the first row of a configuration and replace the tiles $\Box$ and $\Box$ by $\Box$ and the other tiles by $\blacksquare$ (note that $T_2$ and $T_7$ do not contain $\Box$, in which case only $\Box$ is replaced by $\Box$). Let $\varphi: \overline{\mathbb{Z}} \to \mathbb{Z}^2$ be the homomorphism sending $p$ to $(p, 0)$. One has $\sigma^p \circ f = f \circ \sigma^{\varphi(p)}$, so $f$ is a weak factor map. Its image is contained in $X_{\overline{\mathbb{Z}}}$ because the only tiles in $T$ that can be put at the left
of $\Box$ or $\Box\Box$ is one of these two tiles, so in the output of $f$, the only tile that can appear on the left of the white tile is the white tile. Finally, $f$ is surjective because there exists a configuration in $X_T$ whose first row is:

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

and the image of such a configuration has a dense orbit in $X_{\mathbb{Z}}$ (the first picture applies to any $T$ except $T_7$, to which the second picture applies).

Let now $T = T_5$. Let $f : X_T \to \{\Box, \Box\}^{\mathbb{Z}}$ extract the diagonal and replace any non-white tile by $\Box$. Let $\varphi : \mathbb{Z} \to \mathbb{Z}^2$ send $p$ to $(p, p)$. One has $\sigma^p \circ f = f \circ \sigma^{\varphi(p)}$ so $f$ is a weak factor map. Its image is contained in $X_{\mathbb{Z}}$, because one easily checks that in a configuration $x \in X_T$, if the white appears at position $(p, p)$ then it also appears at position $(p-1, p-1)$, so $f$ does not produce the forbidden pattern. Finally $f$ is surjective because $X_T$ contains the following configuration:

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

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

We now prove that $T_1, T_3, T_4$ and $T_6$ induce weakly mixing subshifts, because they contain $T_1$.

**Lemma 4.2.** Any bicolor tileset that contains $T_1 = \Box\Box\Box\Box$ induces a weakly mixing subshift.

*Proof.* Any valid $S_n$-pattern can be extended to a valid pattern on $[-n, +\infty)^2 \setminus [n, +\infty)^2$ whose boundary is white, as illustrated in Figure 9. Let $\pi$ and $\pi'$ be valid patterns on $S_n$.

<figure><img src="image_14.png" /><figcaption>Figure 9: Extending a pattern $\pi$ from $S_n$ to $[-n, +\infty)^2 \setminus [n, +\infty)^2$.</figcaption></figure>

and $(2n, 2n) + S_n$ respectively. They can be extended to valid pattern $\xi$ and $\xi'$ on the disjoint regions $[-n, +\infty)^2 \setminus [n, +\infty)^2$ and $[n, +\infty)^2 \setminus [3m, +\infty)^2$ respectively, which have white boundaries. The rest of the plane can be filled with white tiles, yielding a valid configuration extending $\pi$ and $\pi'$. Therefore, $S_n$ and $(2n, 2n) + S_n$ are independent. $\square$
We briefly explain why $T_2$ and $T_5$ induce weakly mixing subshifts.

For $T_2 = \Box \Box \Box \Box$, we claim that the lower half-plane $A := \mathbb{Z} \times (-\infty, 0]$ and the upper half-plane $B := \mathbb{Z} \times [3, +\infty)$ are independent. Any valid pattern on either of these regions has a boundary which contains at most one black edge. It can be extended to the next row so that the extended pattern has a white boundary. The two extended patterns match and cover $\mathbb{Z}^2$, yielding a common valid extension of the original patterns. It implies that $S_m$ and $(0, m+2)+S_m$ are independent, because they are contained in $(0, m-1)+A$ and $(0, m-1)+B$ respectively.

For $T_5 = \Box \Box \Box \Box \Box$, we claim that the lower-right half-plane $A := \{(i, j) : j \le i\}$ and the upper-left half-plane $B := \{(i, j) : j \ge i+5\}$ are independent. Any valid pattern on $A$ can be extended to a valid pattern on $\{(i, j) : j \le i+2\}$ with a white boundary, using only the tiles $\Box$, $\Box$ and $\Box$. By symmetry of the tileset and of $A$ and $B$ across the diagonal, any valid pattern on $B$ can be extended to a valid pattern on $\{(i, j) : j \ge i+3\}$ with a white boundary. These two patterns match and cover $\mathbb{Z}^2$, yielding a common valid extension of the original patterns. It implies that $S_m$ and $(0, 2m+3)+S_m$ are independent, because they are contained in $(0, m-1)+A$ and $(0, m-1)+B$ respectively.

The subshift induced by $T_7 = \Box \Box \Box \Box$ is not weakly mixing. We do not prove it because we do not need it, but the problem is that in a valid configuration, either all the occurrences of $\Box$ appear in even cells and all the occurrences of $\Box$ appear odd cells, or the converse holds (the parity of a cell $(i, j)$ is $i+j \bmod 2$). Therefore, two different cells are never independent.

However, $X_{T_7}$ weak factors to a $\mathbb{Z}^2$-subshift $Y$ which is weakly mixing, and weak factors to $\mathbb{Z}$ as well.

We could prove the result directly with the subshift $X$ induced by $T_7$, but it is much easier to understand the argument on the following subshift $Z$ which is conjugate to $X$. $Z$ is a subshift on $\{\Box, \blacksquare\}$ which has the white configuration, the black configuration and for each sequence $(n_j)_{j \in \mathbb{Z}}$ satisfying $|n_{j+1} - n_j| = 1$, the configuration whose cell $(i, j)$ is white if $i < n_j$ and black otherwise. In other words, $Z$ is the two-dimensional SFT on $\{0, 1\}$ with forbidden patterns $10, \underset{0}{1}0, \underset{1}{0}0$ and $\underset{0}{0}1$, and a typical configuration is a zigzag separating a black region on the right from a white region on the left. The conjugacy map $F: Z \to X$ intuitively replaces each black square by a black boundary and shifts the configuration by $(\frac{1}{2}, \frac{1}{2})$. More formally, the rule underlying $F$ is shown in Figure 10. We let the reader

<figure><img src="image_15.png" /><figcaption>Figure 10: A tile in $T_7$ is determined by the 4 input bits assigned to its corners
check that this rule is correct, i.e. only outputs tiles in $T_7$.</figcaption></figure>
As $X_{T_7}$, $Z$ is not weakly mixing. However, it weak factors to a weakly mixing $\mathbb{Z}^2$-subshift $Z_0$ which itself weak factors to $\mathbb{Z}$.

Let $Z_0$ be obtained as $Z$, but using sequence $(n_j)_{j \in \mathbb{Z}}$ satisfying the relaxed condition $|n_{j+1} - n_j| \le 1$. The weak factor map: $Z \to Z_0$ converts a sequence $(n_j)_{j \in \mathbb{Z}}$ to the sequence $n'_j = \lfloor \frac{n_{2j}}{2} \rfloor$, and the homomorphism is $\varphi(p) = 2p$.

As in Lemma 4.1 the function $g: Z_0 \to \mathbb{Z}$ that extracts the first row is a weak factor map via $\varphi(p) = (p, 0)$.

$Z_0$ is weakly mixing because $S_m$ and $(0, 2m-1) + S_m$ are independent. If $\pi$ and $\xi$ are valid patterns on these two regions and $a \in [0, m]$ is the first positions of a black tile on row $m-1$ in $\pi$ ($a = m$ if there is no black tile) and $b \in [0, m]$ is the first position of a black tile on row $2m-1$ of $\xi$ ($b = m$ if there is no black tile), then we can define a sequence $n_i$ for $m-1 \le i \le 2m-1$ with $n_{m-1} = a$, $n_{2m-1} = b$ and $|n_{i+1} - n_i| \le 1$ for $m-1 \le i < 2m-1$, simply because $|b-a| \le m = (2m-1) - (m-1)$. From this sequence we can build a valid extension of $\pi \cup \xi$.

# 5 Subshifts that belong to $\mathcal{L}^0$

We now present the even bicolor tilesets that belong to $\mathcal{L}^0$. We only give details for the more difficult cases. The simpler ones will be briefly described in Section 6. For instance, we will see that all the even bicolor tilesets of size at most 3 induce subshifts that belong to $\mathcal{L}^0$ (when they are non-empty).

We first recall Theorem 7.1 from [FH24], which will help establishing the results.

**Theorem 5.1** ($\mathcal{L}^0$ and higher power presentations). Let $a \in \mathbb{Z}^d$ have positive coordinates and $X$ be a $\mathbb{Z}^d$-subshift. One has

$$X \in \mathcal{L}^0 \iff [X]_a \in \mathcal{L}^0.$$

## 5.1 Corners and 2 even tiles

There are two equivalence classes of tilesets consisting of the 4 corners and 2 even tiles. We saw one of them (Class 6.6.4) in Theorem 3.2 where we showed that the induced subshift is not in $\mathcal{L}^0$. On the contrary, the other class induces a subshift in $\mathcal{L}^0$. A representative is shown in Figure 11 (Class 6.6.5).

<figure><img src="image_16.png" /><figcaption>Figure 11: The corners and 2 even tiles</figcaption></figure>

Let $T$ be the complete even bicolor tileset and let $F: \{0, 1\}^{\mathbb{Z}^2} \to X_T$ be the factor map from Section 7.3.1 in [FH24] (assign the input bits to the points of the grid, and if bits $a$
and $b$ are assigned to the endpoints of an edge, then assign color $a+b \pmod 2$ to that edge). Let $S \subseteq T$ be the tileset shown in Figure 11. Observe that it is obtained from $T$ by removing the tiles whose horizontal edges are both black. Therefore, $X_S$ is the image by $F$ of the SFT $X \subseteq \{0,1\}^{Z^2}$ with 4 forbidden patterns $\frac{a}{c}\frac{b}{d}$ with $a \neq b$ and $c \neq d$.

We show that $X \in \mathcal{L}^0$, which implies that $X_S \in \mathcal{L}^0$ as $X_S$ is a factor of $X$. We define a continuous function $G: \{0,1\}^{Z^2} \to X$, which leaves every valid configuration unchanged, and corrects the invalid ones ($G$ is a retraction). The function $G$ applies local rules that are periodic with periods (4, 0) and (0, 5), so the (4, 5)-higher power presentation of $X$ is a factor of the (4, 5)-higher power presentation of the fullshift, which is a fullshift, implying that $X \in \mathcal{L}^0$ (Theorem 5.1).

Let $R = [0,4] \times [0,5]$ and $\partial R = (\{0,4\} \times [0,5]) \cup ([0,4] \times \{0,5\})$ be its boundary. The function $G$ works in two steps, i.e., $G$ is a composition $G = G_2 \circ G_1$:

1. First step: $G_1$ replaces, at every position $p = (4x, 5y)$, a possible pattern $\frac{b}{d}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}$ with $b \neq c$ or $d \neq e$ by the pattern $\frac{b}{d}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}$ (the box indicates the origin position in the pattern, and $\bar{a} = 1-a$),

2. Second step: $G_2$ replaces, at every position $p = (4x, 5y)$, a possible $R$-pattern $\pi$ containing a forbidden pattern, by a valid pattern that coincides with $\pi$ on its boundary $\partial R$.

The next result implies that $G$ does not affect the valid configurations.

**Lemma 5.1.** The patterns $\frac{b}{d}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}$ with $b \neq c$ or $d \neq e$ are invalid.

*Proof.* Assume that $c \neq b$, the case $e \neq d$ is symmetric. For any pattern $\frac{x_0}{a}\frac{x_1}{a}\frac{x_2}{a}\frac{x_3}{a}\frac{x_4}{a}$ with $x_0 = b$ and $x_4 = c$, there exists $i < 4$ such that $x_i \neq x_{i+1}$, so it contains a forbidden pattern $\frac{x_i}{a}\frac{x_{i+1}}{a}$ or $\frac{x_i}{a}\frac{x_{i+1}}{a}$. $\square$

We now show that $G_2$ is well-defined.

**Lemma 5.2.** Let $\pi$ be an $R$-pattern such that no pattern $\frac{b}{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}$ appears in $\pi$ at position $(0,0)$ and no pattern $\frac{a}{d}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}\bar{a}$ appears in $\pi$ at position $(0,5)$.

There exists a valid $R$-pattern $\pi'$ that coincides with $\pi$ on its boundary $\partial R$.

*Proof.* For $j \in \{1,2,3\}$, let $s_j$ and $t_j$ be the starting symbol and ending symbol of row number $j$ in $\pi$. The row number $j$ of $\pi'$ will be made of a block of $s_j$'s followed by a block of $t_j$'s. We need to choose where the transition occurs (if $s_j = t_j$, then there is no transition and the row is constant).

For $j=1$, we choose a transition to avoid forbidden patterns in $[0,4] \times [0,1]$: either $s_1 = t_1$, in which case row 1 is constant and no forbidden pattern can appear, or $s_1 \neq t_1$, in
which case the assumption implies that there exists $i < 4$ such that $\pi(i, 0) = \pi(i + 1, 0)$. We then make the transition happen between $i$ and $i + 1$, i.e. the row 1 of $\pi'$ is $s_i^{i+1}t_i^{4-i}$.

For $j = 3$, we apply a symmetric argument to avoid forbidden patterns in $[0, 4] \times [4, 5]$. We finally fill row $j = 2$. If $s_2 = t_2$ then again, row 2 is constant. If $s_2 \neq t_2$, then we need to make the transition happen at a position which is different from the possible transitions occurring in rows 1 and 3. It is always possible, because there are 3 possible positions. $\square$

After applying $G$, the $R$-patterns appearing at positions $(4x, 5y)$ contain no forbidden pattern. In $\mathbb{Z}^2$, any $2 \times 2$ square is contained in some block $(4x, 5y) + R$ because they overlap, so the configuration $G(x)$ does not contain any forbidden pattern.

A configuration obtained by applying this local generation procedure to a random grid of bits is shown in Figure 12.

<figure><img src="image_17.png" /><figcaption>Figure 12: A random tiling using the even bicolor tiles except $\square$ and $\square$</figcaption></figure>

## 5.2 Corners and 3 even tiles

The tileset $S$ containing all the even tiles except the black tile $\square$ (Figure 13, Class 6.7.2), induces a subshift that belongs to $\mathcal{L}^0$:

<figure><img src="image_18.png" /><figcaption>Figure 13: The corners and 3 even tiles</figcaption></figure>

As in the previous section, let $T$ be the tileset containing all the even bicolor tiles. Let $R = [0, 2] \times [0, 3]$ and $[X_S]_{(2,3)}$ the (2,3)-higher power presentation of $X_S$. It turns out that all the boundaries of the valid $R$-patterns from $X_T$, which are exactly the ones in which the black color appears an even number of times, are also boundaries of valid $R$-patterns from $X_S$. In other words, it is possible to change the content of an $R$-pattern
from $X_T$ so that the new pattern has the same boundary, and does not contain the black tile $\Box$ (see Lemma 5.3 below). Therefore, $[X_S]_{(2,3)}$ is a factor of $[X_T]_{(2,3)}$, with a factor map that replaces each $R$-pattern containing $\Box$ by an $R$-pattern with the same boundary and without the forbidden tile. Therefore, one has:

$$X_T \in \mathcal{L}^0 \implies [X_T]_{(2,3)} \in \mathcal{L}^0 \implies [X_S]_{(2,3)} \in \mathcal{L}^0 \implies X_S \in \mathcal{L}^0.$$

**Lemma 5.3.** Every $R$-pattern made of even bicolor tiles has the same boundary as a $R$-pattern made of even bicolor tiles and avoiding the black tile $\Box$.

*Proof.* As explained in Section 5.1, an $R$-pattern from the even tileset can be obtained by assigning bits to the corners, which form a $4 \times 5$ grid. The tile $\Box$ corresponds to the patterns $\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}$ and $\begin{smallmatrix} 1 & 0 \\ 0 & 1 \end{smallmatrix}$. There is a way to correct a $4 \times 5$ grid filled with bits in order to remove these patterns while leaving the bits on the boundary unchanged, as illustrated in Figure 14. The idea is that after correction, each $2 \times 2$ square will contain 2 horizontally or vertically adjacent cells with the same bit. The corresponding $R$-pattern made of even tiles will then have the same boundary as the original one and will not contain the tile $\Box$. □

<figure><img src="image_19.png" /><figcaption>Figure 14: Correction rule: copying the content of boundary cells to inner cells, as indicated by the arrows, removes the forbidden patterns $\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}$ and $\begin{smallmatrix} 1 & 0 \\ 0 & 1 \end{smallmatrix}$.</figcaption></figure>

A configuration obtained by applying the local generation procedure to a random grid of bits is shown in Figure 15.

# 6 Classification of the even bicolor tilesets

We summarize the classification of the even bicolor tilesets.

We recall that there are 36 equivalence classes of such tilesets under the symmetry group action, that 8 of them are not minimal, i.e. induce the same subshift as smaller tileset, so only 28 equivalence classes of tilesets need to be considered. Table 1 shows a tileset for each one of these 28 equivalence classes. Table 2 shows the 8 equivalence classes of non-minimal tilesets, with one tileset per class.

For the subshifts that do not belong to $\mathcal{L}^0$, we do not know whether they belong to $\mathcal{L}^1$, although we expect that it is not the case.
<table><caption>Table 2: The other even bicolor tilesets</caption><thead><tr><th>Empty subshift</th><th>Unused tile</th></tr></thead><tbody><tr><td>☐<br>☐☐</td><td>☐☐<br>☐☐<br>☐☐<br>☐☐<br>☐☐<br>☐☐<br>☐☐<br>☐☐<br>☐☐</td></tr></tbody></table>

## 6.1 Even tilesets of size 1

There are 8 even tilesets of size 1, divided in 2 equivalence classes.

### 6.1.1 No corner

In $\mathcal{L}^0$. There is one constant tiling.

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

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

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

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

### 6.1.2 One corner

There is no tiling.

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

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

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

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

## 6.2 Even tilesets of size 2

There are $\binom{8}{2} = 28$ even tilesets of size 2, divided in 5 equivalence classes.

### 6.2.1 No corner (first case)

In $\mathcal{L}^0$. There are 2 tilings. It is conjugate to $\{0, 1\}$ with the trivial action $(i, j) \cdot x = x$.

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

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

### 6.2.2 No corner (second case)

In $\mathcal{L}^0$. A configuration using the first tileset is a configuration of the $\mathbb{Z}$-fullshift over $\{0, 1\}$, copied on each row. It is therefore conjugate to $\{0, 1\}^{\mathbb{Z}^2/(0,1)\mathbb{Z}}$.

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

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

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

<figure><img src="image_33.png" /></figure>
### 6.2.3 One corner + one even tile

In $\mathcal{L}^0$. The corner cannot be used, the induced subshifts are the same as in Class 6.1.1.

□□

□□

□□

□□

□□

□□

□□

□□

□□

□□

□□

□□

□□

□□

□□

□□

### 6.2.4 Two opposite corners

In $\mathcal{L}^0$. There are 2 configurations, the subshift is conjugate to $Z^2/H$ where $H = \{(x, y) \in Z^2 : x + y = 0 \mod 2\}$, equivalently to $\{0, 1\}$ with the action $(i, j) \cdot a = a + i + j \mod 2$.

□□

□□

### 6.2.5 Two adjacent corners

There is no tiling.

□□

□□

□□

□□

## 6.3 Even tilesets of size 3

There are $\binom{8}{3} = 56$ even tilesets of size 3, divided in 6 equivalence classes.

### 6.3.1 No corner

In $\mathcal{L}^0$. The subshift is the union of two subshifts from Class 6.2.2.

□□□

□□□□

□□□□

□□□□

### 6.3.2 One corner + two even tiles (first case)

In $\mathcal{L}^0$. The subshift is countable: it contains the two uniform configurations made of $□$ or $□□$ and each other configuration is completely determined by one position of the tile $□$.

□□□

□□□

□□□

□□□

□□□□

□□□□

□□□□

□□□□
### 6.3.3 One corner + two even tiles (second case)

In $\mathcal{L}^0$. The corner cannot be used, the induced subshifts are the same as in Class 6.2.2.

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

### 6.3.4 Two adjacent corners + one even tile

In $\mathcal{L}^0$. The corners cannot be used, the induced subshifts are the same as in Class 6.1.1.

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

### 6.3.5 Two opposite corners + one even tile

In $\mathcal{L}^0$. The configurations using the first tileset are (1, -1)-periodic, and the subshift is a factor of the (1, -1)-periodic shift $P$ over {0, 1}. The map $f: P \to X$ works in two steps. First, the function $f_1: P \to P$ removes the pattern 11. It is defined by $f_1(x)_{i,j} = 1 \iff x_{i-1,j}x_{i,j} = 01$. $f_1$ is a factor map and $\text{im}(f_1)$ is the set of (1, -1)-periodic configurations avoiding the pattern 11. Next, $f_2: \text{im}(f_1) \to X$ assigns color $x_{i,j}$ to the left edge of cell $(i, j)$, which uniquely determines the configuration. The composition $f = f_2 \circ f_1$ is the sought factor map.

□□□

□□□

□□□

□□□

□□□

□□□

□□□

□□□

### 6.3.6 Three corners

In $\mathcal{L}^0$. Only the two opposite corners can be used, the induced subshifts are the same as in Class 6.2.4.

□□□

□□□

□□□

□□□

## 6.4 Even tilesets of size 4

There are $\binom{8}{4} = 70$ even tilesets of size 4, divided in 9 equivalence classes.
### 6.4.1 No corner

In $\mathcal{L}^0$. This tileset is the set of all tiles whose opposite edges have the same color. There is a conjugacy $f : \{0,1\}^{\mathbb{Z}^2/(1,0)\mathbb{Z}} \times \{0,1\}^{\mathbb{Z}^2/(0,1)\mathbb{Z}} \to X$. On input $(x,y)$, each cell $(i,j)$ is assigned color $x_{i,j}$ to its left and right edge and $y_{i,j}$ to its lower and upper edge. Note that $x_{i,j}$ only depends on $j$ and $y_{i,j}$ only depends on $i$.

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

### 6.4.2 One corner + three even tiles

Not in $\mathcal{L}^1$ (Theorem 4.2).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

### 6.4.3 Two adjacents corners + two even tiles (first case)

Not in $\mathcal{L}^1$ (Theorem 4.2).

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

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

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

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

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

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

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

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

### 6.4.4 Two adjacent corners + two even tiles (second case)

Not in $\mathcal{L}^1$ (Theorem 4.2).

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

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

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

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

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

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

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

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

### 6.4.5 Two adjacent corners + two even tiles (third case)

In $\mathcal{L}^0$. The corners cannot be used, the induced subshifts are the same as in Class 6.2.2.

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

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

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

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

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

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

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

<figure><img src="image_74.png" /></figure>
### 6.5.2 Two adjacent corners + three even tiles

Not in $\mathcal{L}^1$ (Theorem 4.2).

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

### 6.5.3 Two opposite corners + three even tiles

Not in $\mathcal{L}^0$ (Theorem 3.2).

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

### 6.5.4 Three corners + two even tiles (first case)

Not in $\mathcal{L}^1$ (Theorem 4.2).

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

### 6.5.5 Three corners + two even tiles (second case)

Not in $\mathcal{L}^0$ (Theorem 3.2).

<figure><img src="image_78.png" /></figure>
<figure><img src="image_79.png" /></figure>

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

### 6.5.6 Four corners + one even tile

Not in $\mathcal{L}^0$ (Theorem 3.2).

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

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

## 6.6 Even tilesets of size 6

There are $\binom{8}{6} = 28$ even tilesets of size 6, divided in 5 equivalence classes.

### 6.6.1 Two adjacent corners + four even tiles

Not in $\mathcal{L}^1$ (Theorem 4.2).

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

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

### 6.6.2 Two opposite corners + four even tiles

Not in $\mathcal{L}^0$ (Theorem 3.2).

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

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

### 6.6.3 Three corners + three even tiles

Not in $\mathcal{L}^0$ (Theorem 3.2).

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

<figure><img src="image_88.png" /></figure>
### 6.8.1 All the even tiles

In $\mathcal{L}^0$ (Section 7.3.1 in [FH24]).

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

## Acknowledgments

We thank Guilhem Gamard, Emmanuel Jeandel, Julien Provillard and Alexis Terrassin for interesting discussions on the subject.

## References

[dV13] J. de Vries. *Elements of Topological Dynamics*. Mathematics and Its Applications. Springer Netherlands, 2013.

[FH24] Tom Favereau and Mathieu Hoyrup. *Local generation of tilings*. Preprint, 2024.

[Fur67] Harry Furstenberg. *Disjointness in ergodic theory, minimal sets, and a problem in diophantine approximation*. *Mathematical systems theory*, 1(1):1–49, Mar 1967.

[LM95] Douglas Lind and Brian Marcus. *An Introduction to Symbolic Dynamics and Coding*. Cambridge University Press, 1995.