# The aperiodic Domino problem in higher dimension

Benjamin Hellouin de Menibus, Antonin Callard

► To cite this version:

Benjamin Hellouin de Menibus, Antonin Callard. The aperiodic Domino problem in higher dimension. 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Mar 2022, Marseille, France. pp.1-15, 10.4230/LIPIcs.STACS.2022.18 . hal-03573476

HAL Id: hal-03573476

https://hal.science/hal-03573476

Submitted on 14 Feb 2022

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# The aperiodic Domino problem in higher dimension

Antonin Callard ✉ ID

Université Paris-Saclay, ENS Paris-Saclay, Département Informatique, 91190 Gif-sur-Yvette, France

Benjamin Hellouin de Menibus<fnref n="1" /> ✉ ID

Université Paris-Saclay, CNRS, Laboratoire Interdisciplinaire des Sciences du Numérique, 91400 Orsay, France

## Abstract

The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this paper, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift.

[8] proved that this problem is co-recursively enumerable ($Π_0^1$-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic ($Σ_1^1$-complete), in higher dimension: $d \ge 4$ in the finite type case, $d \ge 3$ for sofic and effective subshifts. The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity.

This complexity jump is surprising for two reasons: first, it separates 2- and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large.

**2012 ACM Subject Classification** Theory of computation → Models of computation; Theory of computation → Problems, reductions and completeness

**Keywords and phrases** Subshift, periodicity, aperiodicity, domino problem, subshift of finite type, sofic subshift, effective subshift, tilings, computability

**Acknowledgements** The authors are grateful to the three referees for their many remarks and improvements. The first author is grateful to the *Excellence* group for being such cheerful co-interns and friends.

<footnote n="1">¹ Corresponding author</footnote>
# 1 Introduction

Subshifts are sets of colorings (or *configurations*) defined by a family of forbidden patterns. The seminal computational problem on multidimensional subshifts is the *Domino Problem*: given a subshift of finite type (SFT), does it contain a configuration? It was proved undecidable on $Z^2$ in [2, 19] from the construction of *aperiodic SFTs* (SFTs which contain only (strongly) aperiodic colorings, i.e. colorings with no non-zero period) in which universal computation is embedded. Many similar undecidability results used different SFTs and embeddings to control the structure and properties of their configurations [10, 5, 1, 21, 5] or to characterise the set of possible values of some parameters by computability conditions [12, 15, 4]. These results all rely on the existence of purely aperiodic SFTs on $Z^d$ for $d \ge 2$ (see [14, Section 1.2] for more details), and show that multidimensional SFTs can be considered as geometrical computational models.

In contrast, topological or geometrical restrictions may lower the “natural” complexity of a problem (compare e.g. [12] with [6] or [18]) by breaking our ability to embed computation. In particular, finding the border where the difficulty jump occurs gives a fine understanding of the effect of the restriction [7].

Given the importance of aperiodicity for computation embedding, it is natural to ask the aperiodic version of the Domino problem (**AD**): *given as input a subshift X, does it contain an aperiodic coloring?* It is not difficult to see that this problem is harder than the Domino problem, i.e. co-r.e.($\Pi_1^0$)-hard in dimension 2 and higher; however, the natural upper bound is much higher, outside the arithmetical hierarchy.

This question was (to the best of our knowledge) first explored in [8]: the authors proved that **AD** is $\Pi_1^0$-complete for $Z^2$ subshifts$^2$. It is an example of problem whose computational complexity is low because of geometrical reasons specific to the two-dimensional case: starting from an aperiodic configuration, we can regroup breaks of periods into concentric balls whose size is controlled by a computable function ([8, Theorem 1]).

In this paper, we study the computational complexity of this problem in higher dimension, where this geometrical property no longer holds (see [8, Section 4] for a counter example). We build an embedding for universal computation that proves that this problem is in a much higher undecidability class – $\Sigma_1^1$-complete, its natural upper bound – in sofic subshifts for $d \ge 3$ and in subshifts of finite type for $d \ge 4$.

Our paper is structured as follows.

- In Section 2, we provide definitions for subshifts and the relevant complexity classes;

- In Section 3, we prove that **AD** is $\Sigma_1^1$-complete on $Z^d$ ($d \ge 3$) sofic subshifts;

- In Section 4, we adapt the previous proof to $Z^d$ ($d \ge 4$) subshifts of finite type;

- In Section 5, we make a side remark relating the existence of an aperiodic configuration in SFTs with their complexity.

We summarize the complexity of **AD** in the following table (new results are highlighted):

<table><thead><tr><th>Dimension / type</th><th>finite type</th><th>sofic</th><th>effective</th></tr></thead><tbody><tr><td>2D</td><td>$\Pi_1^0$-complete</td><td>$\Pi_1^0$-complete</td><td>$\Pi_1^0$-complete</td></tr><tr><td>3D</td><td>open</td><td>$\Sigma_1^1$-complete</td><td>$\Sigma_1^1$-complete</td></tr><tr><td>4D+</td><td>$\Sigma_1^1$-complete</td><td>$\Sigma_1^1$-complete</td><td>$\Sigma_1^1$-complete</td></tr></tbody></table>

<footnote n="2">² on SFTs, but as [8, Theorem 1] applies to any $Z^2$ subshift, the result also holds for $Z^2$ effective subshifts.</footnote>
Considering the effect of the dimension on the difficulty of AD, we find a border between the dimensions where the complexity of the problem is lowered by geometric properties and the dimensions where computability considerations dominate.

For sofic and effective subshifts, this border lies between dimensions 2 and 3. For SFTs on $Z^3$, we conjecture that AD is in the arithmetical hierarchy for reasons that are specific to SFTs, and provide a few pointers in conclusion. This would be a candidate for a dimension-separating property between 3 and 4 dimensional SFTs. In both cases, we do not know of any other natural problem with a complexity jump in such high dimensions.

# 2 Definitions and notations

## 2.1 Subshifts

For a more detailed introduction, we refer the reader to [3, Chapter 9].

Let $\Sigma$ be a finite alphabet of colors and $d$ a dimension. A configuration is a coloring $c: Z^d \to \Sigma$, and the value of $c$ at position $i$ is denoted $c_i$. A pattern is a coloring $w: D \to \Sigma$ of a finite domain $D = \text{dom}(w) \subseteq Z^2$. We say that a pattern $w$ appears in a configuration $x$ and write $w \sqsubseteq x$ if $w_j = x_{i+j}$ for some $i \in Z^d$ and all $j \in D$. Given a configuration $x$ and a vector $t \in Z^d$, denote $\sigma^t(x)$ the shift of $x$ by $t$: for any $i \in Z^d$, $\sigma^t(x)_i = x_{i-t}$.

► **Definition 1 (Periodicity).** 1. In a configuration $x \in \Sigma^{Z^d}$, a vector $p \in Z^d$ is broken at position $i$ if $x_{i+p} \neq x_i$.

2. A configuration $x \in \Sigma^{Z^d}$ is (strongly) aperiodic if every vector $p \in Z^d$ is broken in $x$.

In the following definition, $\Sigma$ is equipped with the discrete topology and $\Sigma^{Z^d}$ with the product topology. $\Sigma^{Z^d}$ is then a Cantor space.

► **Definition 2 (Subshifts).** A subshift is a closed and $\sigma$-invariant subset of $Z^d$. Equivalently, there is a family of forbidden patterns $\mathcal{F}$ such that

$$X = X_{\mathcal{F}} := \{ x \in \Sigma^{Z^d} : \forall w \in \mathcal{F}, w \not\subseteq x \}$$

Two distinct families of forbidden patterns may define the same subshift.

► **Definition 3 (Classes of subshifts).** A subshift $Y \subseteq \Sigma^{Z^d}$ is:

1. of finite type (SFT) if it can be defined by a finite family of forbidden patterns.

2. sofic if there exists an SFT $X \subseteq \Sigma^{Z^d}$ and a projection $\pi: \Sigma' \to \Sigma$ such that $Y = \pi(X)$.

3. effective if it can be defined by a recursively enumerable family of forbidden patterns.

SFTs are of course sofic and sofic subshifts are effective. On the other direction, effective subshifts are projections of higher-dimensional sofic subshifts; this is a consequence of [10], later improved in the subshift case in [5, 1]. More precisely, $X^\uparrow \subseteq \Sigma^{Z^{d+k}}$ is a $(d+k)$-dimensional lift of a subshift $X \subseteq \Sigma^{Z^d}$ if its configurations are configurations of $X$ repeated along the $k$ additional dimensions. Then:

► **Theorem 4 ([5, 1]).** For any $Z^d$ effective subshift $X$, its $(d+1)$-dimensional lifts are sofic.

## 2.2 Hierarchy of undecidability

Many-one reductions define a preorder on decision problems ("$P_1$ is easier than $P_2$"), so we can define hierarchies according to "how far" a problem is from being computable.
4 The aperiodic Domino problem in higher dimension

Arithmetical hierarchy

Starting from recursively enumerable ($\Sigma_1^0$) and co-recursively enumerable ($\Pi_1^0$) problems, the arithmetical hierarchy progressively defines higher levels of undecidability.

**Definition 5 (Arithmetical hierarchy).** For a decision problem $P: \mathbb{N} \to \{0,1\}$ and $m \ge 1$,
1. $P \in \Sigma_m^0$ if there is a computable relation $R(n, k_1, \dots, k_m)$ such that

$$P(n) = 1 \Leftrightarrow \exists k_1, \forall k_2, \exists k_3, \dots R(n, k_1, \dots, k_m).$$

2. $P \in \Pi_m^0$ if this definition holds when swapping $\forall$ and $\exists$ quantifiers.

$P$ is arithmetical if it belongs to a level of this hierarchy.

As $\Sigma_m^0 \cup \Pi_m^0 \subseteq \Sigma_{m+1}^0 \cap \Pi_{m+1}^0$, this indeed defines a hierarchy. For more details, we refer the reader to [20, Chapter 4].

Analytical hierarchy

Above the arithmetical hierarchy, the analytical hierarchy allows for second-order quantifications on sets. Here we need only the first level.

**Definition 6 (Class $\Sigma_1^1$).** A decision problem $P: \mathbb{N} \to \{0,1\}$ is $\Sigma_1^1$ if there exists an arithmetical relation $R$ such that

$$P(n) = 1 \Leftrightarrow \exists f \in 2^{\mathbb{N}}, R^f(n)$$

in which $R^f$ denotes the relation $R$ with $f$ given as an oracle.

All arithmetical sets are $\Sigma_1^1$. In terms of computational power, $\Sigma_1^1$ sets are (a lot) harder than arithmetical sets: to make an analogy between computability and topology, if $\Sigma_1^0$ sets correspond to the open sets, then $\Sigma_1^1$ sets are not even Borel. For more details, see [17, Chapter IV.2]. A typical example of a $\Sigma_1^1$-complete problem is the following:

**Theorem 7 (State Recurrence [9, Corollary 6.2]).** The problem of State Recurrence (SR): Input: A nondeterministic Turing machine (NTM) $M$, and one of its states $q_0$.

Output: Is there a run of $M$ on the empty input $\varepsilon$ in which $q_0$ is visited infinitely often? is a $\Sigma_1^1$-complete problem.

2.3 The aperiodic Domino (AD) problem and its complexity

**Definition 8 (Aperiodic Domino problem (AD)).**

Input: An effective family of $d$-dimensional patterns.

Output: Is there an aperiodic configuration in the effective subshift $X_F$?

We consider variations of AD depending on the type of input subshift (SFT, sofic, effective).

There are natural lower and upper bounds on the complexity of AD that do not depend on the input type:

**Proposition 9.** AD is $\Pi_1^0$-hard for $\mathbb{Z}^d$ subshifts ($d \ge 2$).

**Proof.** We reduce the Domino problem to AD. Let $Y$ be a $\mathbb{Z}^d$-SFT with only aperiodic configurations (see e.g. [19]). For any $\mathbb{Z}^d$ subshift $X$, the cartesian product $X \times Y$ has the same type (SFT, sofic, effective), has only aperiodic configurations, and is non-empty if and only if $X$ is non-empty. ◀
More generally, a position $i$ is of level $\ell$ if it has minimal period $2^{\ell+1}$ (cells at positions $i+k2^{\ell+1}$ all have the same value). In a configuration of $X_T$, there may exist at most one position $i$ which does not have a level (i.e. it is not $2^{\ell+1}$ periodic for any $\ell$): we say that level$_z(i) = \infty$. Given as input a finite pattern of size between $2^n$ and $2^{n+1}$, one can compute all levels $\ell \le n - 1$.

## $T_M : \mathbb{Z}$-Toeplitzification of sequences of states of $M$

**Definition 13 (Toeplitzification of a set of sequences).** Given a set of sequences $A \subseteq \Sigma^N$, we define the corresponding Toeplitzified subshift $T_A$ on the alphabet $\Sigma \times \{\to, \leftarrow\}$ as:

$$ T_A = \left\{ (x, z) \in (\Sigma \times \{\to, \leftarrow\})^\mathbb{Z} : \begin{array}{l} z \in X_T, \exists (a_n)_{n \in \mathbb{N}} \in A, \\ \forall i \in \mathbb{Z}, \text{level}_z(i) = \ell \in \mathbb{N} \implies x_i = a_\ell \end{array} \right\} $$

Note that a position of infinite level may be marked with any symbol of $\Sigma$. We cannot force this symbol without breaking the next lemma.

Now take $\Sigma = Q$, the set of states of $M$, and define $S_M$ as the set of sequences $(s_t)_{t \in \mathbb{N}}$ on the alphabet $\Sigma$ such that there exists a non-terminating run of $M$ from the empty input whose state at time $t$ is $s_t$. Let $T_M := T_{S_M}$ be its Toeplitzification.

**Lemma 14.** $T_M$ is a $\mathbb{Z}$ effective subshift.

**Proof.** This stems from the fact that the set of prefixes of $S_M$ is computable: for any $n \ge 0$, we can enumerate all oracles of non-determinism of $M$ of size $\le n$ and compute $S_n$, the set of finite prefixes of length $n$ in $S_M$.

Consider the following algorithm that defines a family of forbidden patterns. For all $n$:

- Compute the globally admissible patterns of $X_T$ of size $2^n + 1$; (Note that the language of patterns of $X_T$ is computable: it is both recursively and co-recursively enumerable.)

- Compute $S_n$;

- Forbid all patterns $(u, v) \in (\Sigma \times \{\to, \leftarrow\})^{2^n+1}$, except if $v$ is a pattern in $X_T$ and there exists a prefix $(s_t)_{0 \le t \le n} \in S_n$ such that:

$$ \forall i, j \in \mathbb{Z}, (\text{level}_v(i) = \text{level}_v(j) \le n) \implies u_i = u_j = s_{\text{level}_v(i)}. $$

This procedure defines an effective subshift $E$. We prove $E = T_M$. Indeed:

$E \subseteq T_M$ Take $(u, v) \in E$ and $(u^n, v^n) = (x, z)[-2^n, 2^n]$. By definition of $E$, there exists a finite prefix $s^n \in S_n$ such that for any positions $i, j$ with $\text{level}_{v^n}(i) = \text{level}_{v^n}(j) = \ell$, we have $u_i^n = u_j^n = s_\ell$. This sequence of prefixes is increasing, so it converges towards some sequence $s \in S_M$. Then for any $i, j \in \mathbb{Z}$ such that $\text{level}_v(i) = \text{level}_v(j) = \ell < +\infty$, we have $x_i = x_j = s_\ell$. So $(x, z) \in T_M$.

$T_M \subseteq E$ No pattern forbidden in the algorithm appears in any configuration of $T_M$. ◀

## 3.2 $Y_3$: the desired $\mathbb{Z}^3$ subshift

We create a subshift $Y_3$ which contains an aperiodic configuration if and only if there exists a run of $M$ on the empty word which visits $q_0$ infinitely often. As one might expect, each configuration of $Y_3$ contains the lift of a configuration of $T_M$ corresponding to a run of $M$. We then add lines to make it aperiodic if and only if $q_0$ appears infinitely often.

However, every decision of breaking periods must occur locally at every level, without the ability to know whether the future number of visits of $q_0$ is finite or infinite. Otherwise compactness would create issues: as visits of $q_0$ can occur arbitrarily late, a position of finite
level could be tricked to “believe” that $q_0$ is visited infinitely often in the future. That is why we will break periods whose size depend on the level of the positions in the Toeplitz structure.

### Effective 2D subshifts: $Y_2 \xrightarrow{\leftarrow}$ and $Y_2 \xrightarrow{\rightarrow}$

A configuration of $Y_2 \xrightarrow{\leftarrow}$ is composed of three layers:

- Layer 1 & 2: it contains a $\mathbb{Z}^2$ lift of a configuration $x' \in T_M$. That is, $\forall i, j: x_{i,j} = x'_i$.

- Layer 3: on the alphabet $\{\blacksquare, \square\}$. For every $\ell$ and in every column of level $\ell$ containing $(q_0, \rightarrow)$ on Layers 1 and 2, Layer 3 contains regularly placed $\blacksquare$ cells separated by $2^\ell - 1$ $\square$ cells. Every other cell contains $\square$ on Layer 3.

Formally, $Y_2 \xrightarrow{\leftarrow}$ can be written as:

$$ \left\{ \begin{array}{l} x \in (\Sigma \times \{\rightarrow, \leftarrow\} \times \{\blacksquare, \square\})^{\mathbb{Z}^2} : \exists x' \in T_M, \pi_{1,2}(x) \text{ is a } \mathbb{Z}^2 \text{ lift of } x', \\ \phantom{x \in (\Sigma \times \{\rightarrow, \leftarrow\} \times \{\blacksquare, \square\})^{\mathbb{Z}^2} : \exists} \exists z \in X_T, \pi_2(x) \text{ is a } \mathbb{Z}^2 \text{ lift of } z, \\ \\ \forall i, j \in \mathbb{Z}, \\ x_{i,j} = (\cdot, \cdot, \blacksquare) \implies \forall j', x_{i,j'} = (q_0, \rightarrow, \cdot) \\ x_{i,j} = (q_0, \rightarrow, \cdot) \text{ and level}_z(i) = \ell \in \mathbb{N} \implies \exists j', \forall j'', x_{i,j''} = (\cdot, \cdot, \blacksquare) \iff 2^\ell | (j'' - j') \\ x_{i,j} = (q_0, \rightarrow, \cdot) \text{ and level}_z(i) = \infty \implies |\{j' : x_{i,j'} = (\cdot, \cdot, \blacksquare)\}| \le 1 \end{array} \right. $$

Its counterpart $Y_2 \xrightarrow{\rightarrow}$ is defined similarly by replacing $\rightarrow$ by $\leftarrow$ in the previous definition. It is clear that both $Y_2 \xrightarrow{\rightarrow}$ and $Y_2 \xrightarrow{\leftarrow}$ are effective $\mathbb{Z}^2$ subshifts.

### Issues with the position of infinite level

Note that $\blacksquare$ symbols break increasingly large periods as levels in the Toeplitz structure increase: by compactness, a position of infinite level can break periods of every size by itself.

This explains why this construction requires two additional dimensions to $T_M$ instead of one: each position in $Y_3$ will be periodic in one dimension, and breaks periods in the other. This way, the single position of infinite level may break horizontal or vertical periods, but not both.

### Sofic 3D subshifts: $Y_3 \xrightarrow{\rightarrow}$ and $Y_3 \xrightarrow{\leftarrow}$

By Theorem 4, every $d$-dimensional effective subshift can be lifted into a $d+1$-dimensional sofic subshift. Using this result, we lift $Y_2 \xrightarrow{\rightarrow}$ and $Y_2 \xrightarrow{\leftarrow}$ into 3D sofic subshifts $Y_3 \xrightarrow{\rightarrow}$ and $Y_3 \xrightarrow{\leftarrow}$:

$$ Y_3 \xrightarrow{\rightarrow} \{x \in (\Sigma \times \{\rightarrow, \leftarrow\} \times \{\blacksquare, \square\})^{\mathbb{Z}^3} : \exists x' \in Y_2 \xrightarrow{\rightarrow}, \forall i, k \in \mathbb{Z}, \forall j' \in \mathbb{Z}, x_{i,j',k} = x'_{i,k}\} $$

$$ Y_3 \xrightarrow{\leftarrow} \{x \in (\Sigma \times \{\rightarrow, \leftarrow\} \times \{\blacksquare, \square\})^{\mathbb{Z}^3} : \exists x' \in Y_2 \xrightarrow{\leftarrow}, \forall i, j \in \mathbb{Z}, \forall k' \in \mathbb{Z}, x_{i,j,k'} = x'_{i,j}\} $$

Note that the lifts are not made along the same coordinates: a position with $\blacksquare$ in $Y_2 \xrightarrow{\rightarrow}$ lifts into a line directed by $(0, 1, 0)$ in $Y_3 \xrightarrow{\rightarrow}$, and a position with $\blacksquare$ in $Y_2 \xrightarrow{\leftarrow}$ lifts into a line directed by $(0, 0, 1)$ in $Y_3 \xrightarrow{\leftarrow}$.

### Sofic 3D subshift: $Y_3$

We obtain $Y_3$ by "fusing" the two previous subshifts. Formally,

$$ Y_3 = \{x \in (\Sigma \times \{\rightarrow, \leftarrow\} \times \{\blacksquare, \square\} \times \{\blacksquare, \square\})^{\mathbb{Z}^3} : \pi_{1,2,3}(x) \in Y_3 \xrightarrow{\rightarrow} \text{ and } \pi_{1,2,4}(x) \in Y_3 \xrightarrow{\leftarrow}\} $$
<figure><img src="image_2.png" /><figcaption>Figure 1 A configuration of $Y_3$. To the left of each slice $(i, \cdot, \cdot)$ is its level $\ell$ and the values on Layers 1 and 2. We highlight two slices of level 2: at the front, marked by $(q_0, \leftarrow)$ with horizontal lines; at the back, marked by $(q_0, \rightarrow)$ with vertical lines.</figcaption></figure>

Since $Y_3 \xrightarrow{\leftarrow}$ and $Y_3 \xrightarrow{\rightarrow}$ are sofic, their cartesian product $Y_3 \xrightarrow{\leftarrow} \times Y_3 \xrightarrow{\rightarrow}$ is also sofic. $Y_3$ is the projection on Layers 1, 2, 3, 6 of $Y_3 \xrightarrow{\leftarrow} \times Y_3 \xrightarrow{\rightarrow}$ with the additional local condition that the first two layers coincide (i.e. $\pi_{1,2}(x) = \pi_{4,5}(x)$), so it is sofic as well.

### ▷ Claim 15. A configuration of $Y_3$:

1. breaks every periodicity vector $(n, \cdot, \cdot)$ for $n \ge 1$.

2. every slice $(i, \cdot, \cdot)$ containing $(q_0, \rightarrow)$ on the first two layers and corresponding to the lift of a single position of level $\ell \in [0, +\infty)$ in $T_M$, is periodic with periods $(0, 1, 0)$ and $(0, 0, 2^\ell)$ but breaks every period $(\cdot, \cdot, n)$ for $1 \le n < 2^\ell$. The same is true with $(q_0, \leftarrow)$ with vectors $(0, 2^\ell, 0)$ and $(0, 0, 1)$.

*Proof.* 1. the Toeplitzification of alternating $\rightarrow$ and $\leftarrow$ is aperiodic, so Layer 2 breaks all vectors $(n, \cdot, \cdot)$ for $n \ge 1$.

2. Layer 1 and 2 are lifted along the last two dimensions, so they cannot break any such vectors. Layer 3 is lifted along the second dimension so it is (0, 1, 0)-periodic, and breaks the required vectors from the last condition in the definition of $Y_2 \xrightarrow{\rightarrow}$. Layer 4 is $\square$ everywhere since it is not marked by $(q_0, \leftarrow)$.

$\triangleleft$

## 3.3 Proof of the reduction $RS \le AD$

**Lemma 16.** A configuration in $Y_3$ is aperiodic if, and only if, it corresponds to a run of $M$ in which $q_0$ occurs infinitely often.

*Proof.* Using Claim 15,

Let $y \in Y_3$ be a configuration corresponding to a run of $M$ that visit $q_0$ infinitely often.

If $(q_0, \rightarrow)$ appears at a level $\ell$, all vectors $(0, \cdot, n)$ for $1 \le n < 2^\ell$ are broken on Layer 3;

Similarly for $(q_0, \leftarrow)$ and vectors $(0, n, \cdot)$ on Layer 4.

Therefore all vectors $(0, \cdot, \cdot)$ are broken at some level, and vectors $(n, \cdot, \cdot)$ are always broken for $n \ge 1$, so $y$ is an aperiodic configuration.
Let $y \in Y_3$ be a configuration corresponding to a run of $\mathcal{M}$ that does not visit $q_0$ after some time $N \in \mathbb{N}$. Let $a_\infty \in \Sigma \times \{\to, \leftarrow\}$ be the value on Layers 1 and 2 of the single position of infinite level in $z$, if it exists.

- If $a_\infty \neq (q_0, \leftarrow)$, positions marked by $(q_0, \leftarrow)$ must be of level $\le N$, so $y$ is periodic of period $(0, 2^N, 0)$.

- Similarly, if $a_\infty \neq (q_0, \to)$, then $y$ is periodic of period $(0, 0, 2^N)$.

All in all, $y$ is not aperiodic.

**Case** $d > 3$. We lift the previous construction and fill the additional dimensions with aperiodicity. More precisely, in the construction of $Y_3$, one of the dimension is always aperiodic, and the two others may or may not be periodic. Let $A$ be the $\mathbb{Z}^d$ lift of any $\mathbb{Z}^{d-2}$ aperiodic sofic subshift $(d-2 \ge 2)$, and $Y_d$ the $\mathbb{Z}^d$ lift of $Y_3$. The cartesian product $A \times Y_d$ is aperiodic if and only if $Y_3$ is.

## 4 $\Sigma_1^1$-completeness for $\mathbb{Z}^d$ SFTs, $d \ge 4$

**▶ Theorem 17.** If $d \ge 4$, AD for $\mathbb{Z}^d$ SFTs is a $\Sigma_1^1$-complete problem.

As above, we prove $\Sigma_1^1$-hardness for $d=4$, and the result extends to $d > 4$.

### 4.1 Outline of the proof

This proof has the same structure as Theorem 11 with some adaptations for $\mathbb{Z}^4$ SFTs. We reduce to the problem **SR**: given $\mathcal{M}$ and $q_0$, we create an SFT $X_4$ that contains an aperiodic configuration if and only if $\mathcal{M}$ admits a run from the empty word which visits $q_0$ infinitely often. To do this, we use repeated lines along two dimensions (3 and 4) to break all periods up to a length controlled by a computation embedded in the configuration.

1. In Section 4.2, we build $X_T^2$, a $\mathbb{Z}^2$ version of the Toeplitz structure $X_T$;

2. In Section 4.3, we build auxiliary SFTs $X_3^\to$ and $X_3^\leftarrow$ (counterparts to $Y_2^\to$ and $Y_2^\leftarrow$);

3. In Section 4.4, we build $X_4$ and prove the reduction.

The main difference is that the finite type case requires an additional dimension to embed computations and some construction lines (dimensions 1 and 2). Remember that the subshift $T_\mathcal{M}$ of $\mathbb{Z}$ Toeplitzified sequences of states of runs of $\mathcal{M}$ is effective; instead, we define an aperiodic $\mathbb{Z}^2$ version $T_\mathcal{M}^2$ that is sofic and aperiodic. Since $T_\mathcal{M}^2$ is the projection of an aperiodic $\mathbb{Z}^2$ SFT, we then add, as in the previous case, two additional dimensions in which this SFT can be periodic or aperiodic, since the position of infinite level can break periods uncontrollably along at most one dimension.

Furthermore, to control the length of the vectors being broken, we need to measure distances between lines (as in $Y_3$). With SFTs, copying a distance from one dimension to another can only be done with diagonals. Therefore, instead of *lines* to break periods, we use a more complex *diagonal* SFT $D$ that we embed in slices $(i, \cdot, \cdot, \cdot)$ only on dimensions 2 and 3 (on symbols $\to$) or 2 and 4 (on symbols $\leftarrow$). This way, the computation embedded in the first two dimensions can control the length of the broken periodicity vectors.

### 4.2 $T_\mathcal{M}^2$: $\mathbb{Z}^2$ Toeplitz corresponding to state sequences of $\mathcal{M}$

#### Binary Toeplitz structure

In this section, we use a $\mathbb{Z}^2$ subshift $X_T^2$ on the alphabet $\{\Gamma, \bar{\Gamma}, \underline{\Gamma}, \Gamma, \bar{\Gamma}, \underline{\Gamma}\}$ whose structure is a two-dimensional analog of $X_T$.
<figure><img src="image_3.png" /><figcaption>Figure 3 A configuration of $D$.</figcaption></figure>

In other words, $T_A^2$ superimposes the structure of a $\mathbb{Z}$ Toeplitzification with the $\mathbb{Z}^2$ structure $X_T^2$ we define above. As before, we denote $T_M^2 := T_{S_M}^2$ where $S_M$ of the set of sequences of states corresponding to runs of $M$.

**Lemma 20.** $T_M^2$ is a non-empty sofic subshift.

**Proof.** $T_M^2$ is non-empty as arrows in $T_M$ can be aligned with corners in $X_T^2$: arrows of level $\ell$ as well as columns of level $\ell$ have period $2^\ell$. For soficness:

- Layers 1 and 2 are $\mathbb{Z}^2$ lifts of configurations of $T_M$, which is an effective subshift (Lemma 14). By Theorem 4, Layers 1 and 2 form a sofic subshift;

- Layer 3 is composed of configurations of $X_T^2$, which is a sofic subshift;

- the additional condition defining $T_M^2$ (synchronizing Layers 2 and 3) is of finite type. ◀

## 4.3 Auxiliary $\mathbb{Z}^2$ and $\mathbb{Z}^3$ SFTs

### The diagonal SFT $D$

The diagonal SFT $D$ is defined by adjacent matching patterns on the alphabet $\Sigma_D$:

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

A configuration of $D$ containing two parallel black lines is in fact periodic and consists of repeated squares. $D$ also contains configurations with 0 or 1 black line.

### $\mathbb{Z}^3$ SFTs $X_3 \to$ and $X_3 \xrightarrow{\cdot}$

This section is written for $X_3 \to$; it applies to $X_3 \xrightarrow{\cdot}$ by flipping the arrows and corners. As $T_M^2$ is a 3-layer sofic subshift, it is the projection of some 4-layer $\mathbb{Z}^2$ SFT $X_2$. To create $X_3 \to$, we lift $X_2$ then add an additional layer for $D$:

- Layers 1 to 4: $\mathbb{Z}^3$ lift of $X_2$. In other words, $\pi_{1,2,3}(X_2)$ is a $\mathbb{Z}^3$ lift of $T_M^2$;

- Layer 5: each slice $(i, \cdot, \cdot)$ contains a configuration $d^i \in D$. If the slice has $(q_0, \to)$ on its first two layers, then the configuration $d^i$ is “synchronized” with the underlying configuration of $T_M^2$ on Layer 3, that is: vertical lines $|$ in $d^i$ only appear on Layer 5 at positions marked by corners $\uparrow, \downarrow$ on Layer 3. Otherwise, the slice on Layer 5 is left blank.
<figure><img src="image_5.png" /><figcaption>■ **Figure 4** A configuration of $X_3$. The horizontal plane contains a configuration $x \in X_T^2$, and the slice of level 2 marked by $(q_0, \rightarrow)$ contains a configuration of $D$ “synchronised” with the squares of $x$.</figcaption></figure>

See Figure 4 for a visual help. Formally, if $\Sigma_X$ and $\Sigma_D$ are the alphabets of $X_2$ and $D$:

$$ X_3 = \left\{ x \in (\Sigma_X \times \Sigma_D)^{\mathbb{Z}^3} : \begin{array}{l} \exists y \in X_2, \forall i, j, k \in \mathbb{Z}, \pi_{1,2,3,4}(x_{i,j,k}) = y_{i,j} \\ \forall i \in \mathbb{Z}, \exists d^i \in D, \forall j, k \in \mathbb{Z}, \pi_5(x_{i,j,k}) = d_{j,k}^i \\ \forall i, j, k \in \mathbb{Z}, \pi_{1,2}(x_{i,j,k}) \neq (q_0, \rightarrow) \implies \pi_5(x_{i,j,k}) = \square \\ \pi_5(x_{i,j,k}) \in \{\Box, \Box\} \iff \pi_3(x_{i,j,k}) \in \{\Gamma, \Box\} \end{array} \right\} $$

As there exists at most a single square of infinite level in $X_T^2$, there exists at most a single slice $(i, \cdot, \cdot)$ of infinite level in $X_3$.

On every slice marked by $\rightarrow$, the configuration of $D$ breaks all periods smaller than its squares, and the size of the squares is controlled by the level of the slice in $T_M$. Therefore:

▷ Claim 21. A configuration of $X_3$:

1. breaks every periodicity vector $(n, \cdot, \cdot)$ and $(\cdot, n, \cdot)$ for $n \ge 1$.

2. for every slice $(i, \cdot, \cdot)$ containing $(q_0, \rightarrow)$ on the first two layers and corresponding to a column of level $\ell$ in $X_T^2$, Layer 5 breaks every vector $(\cdot, \cdot, n)$ for $1 \le n < 2^\ell$.

**Proof.** **1.** $X_2$ is aperiodic because $X_T^2$ is also aperiodic, so all vectors $(n, \cdot, \cdot)$ and $(\cdot, n, \cdot)$ are broken for $n \ge 1$.

**2.** For a slice $(i, \cdot, \cdot)$ of level $\ell$, the distance along $(0, 1, 0)$ between two consecutive lines in Layer 3 (ie. in $X_T^2$) is exactly $2^\ell$ (see. Section 4.2, point 3 in the list of properties of configurations in $X_T^2$). So, Layer 5 breaks every smaller period in this direction. ▷
## 4.4 $\mathbb{Z}^4$ SFT $X_4$ and proof of the reduction

### Creation of $X_4$

Similarly to $Y_3$ (Section 3.2), we build $X_4$ by “fusing together” $X_3 \xrightarrow{\cdot, \cdot} \cdot$ and $X_3 \xrightarrow{\cdot, \cdot} \cdot$. Formally:

$$X_4 = \{x \in (\Sigma_X \times \Sigma_D \times \Sigma_D)^{\mathbb{Z}^4} : \exists x \xrightarrow{\cdot, \cdot} \in X_3, \exists x \xrightarrow{\cdot, \cdot} \in X_3, \\ \forall i, j, k, l \in \mathbb{Z}, \pi_{1,2,3,4,5}(x_{i,j,k,l}) = x_{i,j,l} \text{ and } \pi_{1,2,3,4,6}(x_{i,j,k,l}) = x_{i,j,k}\}$$

▷ Claim 22. $X_4$ is an SFT.

Proof. Both $X_3 \xrightarrow{\cdot, \cdot}$ and $X_3 \xrightarrow{\cdot, \cdot}$ are SFTs, since $X_2$ is an SFT.

▷

### Reduction RS $\leq$ AD

**Lemma 23.** There exists an aperiodic configuration in $X_4$ if and only if there exists a run of $M$ in which $q_0$ occurs infinitely often.

**Proof.** This is the same proof as for Lemma 16, except that vectors along the first two dimensions are broken by the Toeplitz structure on layer 3. Otherwise, Layers 5 and 6 break every vector $(0, 0, \cdot, \cdot)$ if and only if the run visits $q_0$ infinitely often.

◀

This concludes the proof of Theorem 17.

## 5 Complexity and aperiodic configurations

The complexity function of a $\mathbb{Z}^d$ subshift $X$ is $N_X(n) = \#\{w \in \Sigma^{[0,n-1]^d} : \exists x \in X, w \subseteq x\}$. In this section, we see that subshifts of high complexity are expected to have aperiodic configurations.

**Definition 24 (Dimensional entropy).** Define $h_k(X)$, the entropy of dimension $k$, as:

$$h_k(X) = \limsup_{n \to +\infty} \frac{\log N_X(n)}{n^k} \in [0, +\infty]$$

[8, Theorem 10] proves that a $\mathbb{Z}^2$ subshift $X$ with no aperiodic configurations is almost topologically conjugated to (i.e. “nearly behaves as”) a $\mathbb{Z}$ subshift of the same type. In particular, $h_1(X) = +\infty$ is only possible when $X$ contains an aperiodic configuration.

[11, Corollary 13] entails that $h_d(X) > 0$ for a $\mathbb{Z}^d$ SFT implies the existence of aperiodic configurations in any dimension. We improve this result as follows:

**Proposition 25.** Let $X$ be a $\mathbb{Z}^d$ SFT or sofic subshift. If $h_{d-1}(X) = +\infty$, then there exists an aperiodic configuration in $X$.

**Proof.** Let $X' \subseteq \Sigma'^{\mathbb{Z}^d}$ be a SFT cover of $X$: $\pi(X') = X$ for $\pi$ a letter-to-letter projection. W.l.o.g., assume $X'$ is defined by adjacency constraints. Consider all patterns on $[[0, n-1]]^d$ admissible in $X'$: they have exactly $N_X(n)$ different projections by $\pi$, but the number $N_{X'}^b(n)$ of different patterns on the boundary of $[[0, n-1]]^d$ is at most $\Sigma'^{2dn^{d-1}}$. As $\log N_X(n)/n^{d-1}$ is unbounded, there exists some $n$ such that:

$$2d(\log \Sigma') < \frac{\log N_X(n)}{n^{d-1}} \iff \Sigma'^{2dn^{d-1}} < N_X(n) \implies N_{X'}^b(n) < N_X(n)$$

By the pigeonhole principle, there exists a pattern $b$ on the boundary admissible in $X'$ that can be extended on the cube in two different admissible patterns $b^+, b^-$ such that
14 The aperiodic Domino problem in higher dimension

$\pi(b^+) \neq \pi(b^-)$. Consider a configuration $x' \in X'$ in which $b^+$ appears. If $\pi(x')$ is not already aperiodic, swapping $b^+$ for $b^-$ in $x'$ at a some arbitrary position leads to a configuration $\pi(x'') \in X$ which is aperiodic. ◄

Proposition 25 is tight: the $Z^d$-lift of a $Z^{d-1}$ SFT ($d \ge 3$) is periodic by definition, and can have arbitrarily high entropy of dimension ($d-1$). We conjecture that Proposition 25 holds for all subshifts even in dimension $d > 2$.

Proposition 25 shows that **AD** is a problem that is only relevant for low complexity subshifts, which is where its full computational complexity “lies”. Indeed, the problem of deciding whether $h_{d-1}(X) = +\infty$ is $\Pi_3^0$ (it is equivalent to $\forall k \exists n N_X(n) > k$, and $N_X(n)$ is a $\Pi_1^0$ integer), which is much easier than the $\Sigma_1^1$-completeness of **AD** on $Z^3$ sofic subshifts.

6 Open problems

The main remaining question is, of course, the case of $Z^3$ SFTs. The method we developed above to prove $\Sigma_1^1$-completeness in the case of $Z^3$ sofic subshifts cannot be applied. Indeed, embedding computations in an SFT requires at least two aperiodic dimensions; and we need two other dimensions (because of the positions of level $\infty$) which can be periodic or aperiodic.

We conjecture that aperiodic configurations in $Z^3$ SFTs behave similarly as in $Z^2$ subshifts: each $Z^3$ SFT containing aperiodic configurations seems to have “centers” of aperiodicity, i.e. concentric zones in which periods are broken. The distance from the center might depend on the length of the vector, $|\Sigma|$ and the size of the largest forbidden pattern.

However, there seem to be important differences. First, for $Z^3$-SFT, not all aperiodic configurations have a center of aperiodicity in their orbit closure: this center may be in an unrelated aperiodic configuration. Second, results of [8] are valid for all $Z^2$ subshifts, but our conjecture must be specific to $Z^3$ SFTs, and a proof requires SFT-specific techniques.

Considering subshifts on more general groups (other than $Z^d$), there is an active research theme looking for conditions on groups which make the Domino problem undecidable. In this context, we would like to obtain conditions that make $\mathbf{AD} \Pi_1^0$- or $\Sigma_1^1$-complete.

References

1 Nathalie Aubrun and Mathieu Sablik. Simulation of effective subshifts by two-dimensional subshifts of finite type. *Acta Applicandae Mathematicae*, 126:35-63, 2013. doi:10.1007/s10440-013-9808-5.

2 Robert Berger. *The Undecidability of the Domino Problem*. Number 66 in *Memoirs of the American Mathematical Society*. American Mathematical Society, 1966.

3 Valérie Berthé and Michel Rigo. *Combinatorics, Words and Symbolic Dynamics*. Number 159 in *Encyclopedia of Mathematics and its Applications*. Cambridge University Press, 2016. doi:10.1017/CBO9781139924733.

4 Antonin Callard and Pascal Vanier. Computational Characterization of Surface Entropies for $Z^2$ Subshifts of Finite Type. In *48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)*, volume 198 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 122:1-122:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.122.

5 Bruno Durand, Andrei E. Romashchenko, and Alexander Shen. Effective closed subshifts in 1D can be implemented in 2D. In *Andreas Blass, Nachum Dershowitz, and Wolfgang Reisig, editors, Fields of Logic and Computation, Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday*, volume 6300 of *Lecture Notes in Computer Science*, pages 208-226. Springer, 2010. doi:10.1007/978-3-642-15025-8_12.
6 Shmuel Friedland. On the entropy of $Z^d$ subshifts of finite type. *Linear Algebra and its Applications*, 252(1):199-220, 1997. doi:https://doi.org/10.1016/0024-3795(95)00676-1.

7 Silvère Gangloff and Benjamin Hellouin de Menibus. Effect of quantified irreducibility on the computability of subshift entropy. *Discrete & Continuous Dynamical Systems - A*, 39(4):1975-2000, 2019. doi:10.3934/dcds.2019083.

8 Anaël Grandjean, Benjamin Hellouin de Menibus, and Pascal Vanier. Aperiodic points in $Z^2$-subshifts. In *45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)*, volume 107 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 128:1-128:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.128.

9 David Harel. Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness. *Journal of the ACM*, 33(1):224-248, 1986. doi:10.1145/4904.4993.

10 Michael Hochman. On the dynamics and recursive properties of multidimensional symbolic systems. *Inventiones mathematicae*, 176:131-167, 2008. doi:10.1007/s00222-008-0161-7.

11 Michael Hochman. On the automorphism groups of multidimensional shifts of finite type. *Ergodic Theory and Dynamical Systems*, 30:809-840, 2009. doi:10.1017/S0143385709000248.

12 Michael Hochman and Tom Meyerovitch. A characterization of the entropies of multidimensional shifts of finite type. *Annals of Mathematics*, 171(3):2011-2038, 2010. doi:10.4007/annals.2010.171.2011.

13 Konrad Jacobs and Michael Keane. 0-1-sequences of Toeplitz type. *Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete*, 13(2):123-131, 1969. doi:10.1007/BF00537017.

14 Emmanuel Jeandel and Pascal Vanier. *The Undecidability of the Domino Problem*, pages 293-357. Springer, 2020. doi:10.1007/978-3-030-57666-0_6.

15 Tom Meyerovitch. Growth-type invariants for $Z^d$ subshifts of finite type and arithmetical classes of real numbers. *Inventiones mathematicae*, 184:567-589, 2011. doi:10.1007/s00222-010-0296-1.

16 Shahar Mozes. Tilings, substitution systems and dynamical systems generated by them. *Journal d'Analyse Mathématique*, 53(1):139-186, 1989. doi:10.1007/BF02793412.

17 Piergiorgio Odifreddi. *Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers*. Elsevier, 1989.

18 Ronnie Pavlov and Michael Schraudner. Entropies realizable by block gluing $Z^d$ shifts of finite type. *Journal d'Analyse Mathématique*, 126(1):113-174, 2015. doi:10.1007/s11854-015-0014-4.

19 Raphael M. Robinson. Undecidability and nonperiodicity for tilings of the plane. *Inventiones mathematicae*, 12:177-209, 1971. doi:10.1007/BF01418780.

20 Robert I. Soare. *Turing Computability: Theory and Applications*. Theory and Applications of Computability. Springer, 1st edition, 2016. doi:10.1007/978-3-642-31933-4.

21 Linda Brown Westrick. Seas of squares with sizes from a $\Pi_1^0$ set. *Israel Journal of Mathematics*, 222:431-462, 2017. doi:10.1007/s11856-017-1596-6.