Today, I met up with a new kind of problem: I got a result which was easy enough so that posting it on arXiv would have been preposterous, yet I knew quite a few people who didn’t have any answer to it (for their defense, they didn’t spend much time thinking about it). A quick search didn’t show me anything, and I’m quite convinced that nobody has ever written it down.
What do you do with an easy solution to a not very profound question? I could have asked the question on MathOverflow before, but doing so now would be very silly since I already got the answer! I don’t want to post it on arXiv, because I’m not sure the arXiv really consists in hosting PDFs that essentially boil down to “a short note that could have been an exercise”.
So, what did I choose? To post it on my blog, obviously!
Here are a few acknowledgements for this specific note: all my thanks to Ville Salo for the very useful emails, to Léo Paviet Salomon for banging his head with me while trying to crack this thing, and to everybody from the RNDJCEDSAPSDCEGSY (in particular Benjamin) for the very nice discussions!
Preliminaries
In this post, I prove a computational characterization of the minimality of subshifts: deciding minimality is a \(\Pi^0_2\)-complete decision problem. At first, I thought that such a question would obviously have already been solved by somebody, but I couldn’t find such a thing anywhere, so maybe it hasn’t? In any case, I spent a bit of time over the last few days trying to prove \(\Pi^0_2\)-hardness: so, in case anybody’s wondering, here’s how I did it!
I obviously have no claim on this result whatsoever, and I don’t think it would be very wise to cite me or this blog post as a bibliographic reference. Were I to need it in the future I would probably mention it as “folklore”; and hopefully there will come a day when somebody will take pen to paper, write a book containing a proof and give us a proper reference.
Anyway. For the purpose of this post, let me provide a few definitions in case you stumbled upon this page without knowing what it was about. Though let me be honest: these are very succinct, and are in no way a proper introduction to computability on subshifts.
Subshifts
Given \(\Z^d\) the discrete space of dimension \(d\), and \(A\) a finite alphabet, a configuration is a coloring \(x : \Z^d \to A\) that colors each position of \(\Z^d\) with a symbol of \(A\). A pattern is a coloring \(w : D \to A\) of a finite domain \(D \subseteq \Z^d\). Abusing notations, we denote \(A^* = \{w : D \to A \mid D \subseteq_f \Z^d \}\) the set of all finite patterns. We say that a pattern \(w : D \to A\) appears in a configuration \(x \in A^{\Z^d}\) (denoted \(w \sqsubseteq x\)) if there exists a position \(i \in \Z^d\) such that \(x|_{i+D} = w\).
In this context, a family (potentially infinite) of forbidden patterns \(\mathcal{F}\) defines a subshift, i.e. a set of colorings of the plane
\[ X_\mathcal{F} = \{ x \in A^{\Z^d} \mid \forall w \in \mathcal{F}, w \not \sqsubseteq x \}. \]
Given a subshift \(X \subseteq A^{\Z^d}\), the set of finite patterns that appear in \(X\) defines the language \(\mathcal{L}(X)\) of the subshift: \(\mathcal{L}(X) = \{ w \in A^* \mid \exists x \in X, w \sqsubseteq x \}\). A subshift \(X \subseteq A^{\Z^d}\) is said to be of finite type (SFT) if there exists a finite family \(\mathcal{F}\) such that \(X = X_\mathcal{F}\). It is said to be effective if there exists a recursively computable family \(\mathcal{F}\) such that \(X = X_\mathcal{F}\).
In what follows, I am interested in the minimality of subshifts. A subshift \(X_\mathcal{F}\) is said to be minimal if it contains no proper non-empty subshift, i.e. if for every \(w \in \mathcal{L}(X_\mathcal{F})\), \(X_{\mathcal{F} \cup \{w\}} = \emptyset\).
The arithmetical hierarchy
A decision problem is a function \(f : \N \to \{ True, False \}\) that maps inputs of an encoded problem to a boolean answer. The class of decision problems can be classified into \(\Sigma^0_n\), \(\Pi^0_n\) and \(\Delta^0_n\), of which I define here the first levels.
\(\Delta^0_0\) is the class of decidable decision problems, i.e. problems for which there exists a computable function that answers it (typically: is an integer given as input a prime number?). Then:
- \(\Sigma^0_1\) is the class of computably enumerable problems, i.e. problems \(f\) for which there exists a computable function \(g\) such that \(f(n) = True \iff \exists m \in \N,\ g(m,n) = True\).
- \(\Pi^0_1\) is the class of co-computably enumerable problems, i.e. problems \(f\) for which there exists a computable function \(g\) such that \(f(n) = True \iff \forall m \in \N,\ g(m,n) = True\).
And of course, this hierarchy can be defined recursively. In particular, this post focuses on the class \(\Pi^0_2\) of problems \(f\) for which there exists a computable function \(g\) such that:
\[ f(n) = True \iff \forall p, \exists q,\ g(p,q,n) = True \]
The result
Let us define the following decision problem Minimality:
The decision problem Minimality is defined as follows:
- Input: A finite family of forbidden patterns \(\mathcal{F}\);
- Output: Is the subshift \(X_\mathcal{F}\) minimal?
We can now state the main result of this blog entry:
In dimension \(d \geq 2\), Minimality is \(\Pi^0_2\)-complete.
The fact that Minimality belongs in \(\Pi^0_2\) is straightforward. In the rest of this post, we focus on the converse: proving that Minimality is \(\Pi^0_2\)-hard.
Hardness in dimension \(d=1\)
Let us prove an intermediary result:
The following decision problem is \(\Pi_2^0\)-complete:
- Input: a computably enumerable family of one-dimensional forbidden patterns \(\mathcal{F}\);
- Output: is the \(\Z\) effective subshift \(X_\mathcal{F}\) minimal?
We focus on \(\Pi^0_2\)-hardness, and reduce to the following problem: given as input a deterministic Turing machine \(\mathcal{M}\) that outputs at every steps “clicks” and “clacks”, does the machine output infinitely many “clicks” on the empty word?
Let \(\mathcal{M}\) be such a machine; without loss of generality, assume that \(\mathcal{M}\) outputs “clack” infinitely often: if it does not, replace \(\mathcal{M}\) by the machine \(\mathcal{M}’\) that does one step of computation of \(\mathcal{M}\) every two steps, and outputs “clack” every other two. To \(\mathcal{M}\), we associate an effective \(\Z\) subshift \(X\) that will be minimal if and only if \(\mathcal{M}\) outputs “click” infinitely many times.
Let \(s \in \{click, clack\}^\N\) be the sequence of clicks and clacks that \(\mathcal{M}\) outputs on the empty word. Note that the sequence \(s\) is computable. To this sequence, we associate the following subshift \(X\) (said to be Toeplitz):
- First, define \( \dots * s_0 * s_0 * s_0 * s_0 * s_0 * \dots\) the bi-infinite words in which one position out of two is \(s_0\), the first output of the machine \(\mathcal{M}\). We then proceed recursively.
- Replace the symbols \(*\) in the previous words in the following way: one position out of two, write \(s_1\), the second output of the machine \(\mathcal{M}\); and leave \(*\) symbols every other one. So you get bi-infinite words of the form \(\dots s_1 s_0 * s_0 s_1 s_0 * s_0 s_1 s_0 * s_0 s_1 s_0 * \dots\).
- And iterate.
In other words, considering the bi-infinite ruler sequence, replace every integer \(n\) by the corresponding value \(s_n\). This set of words defines an effective subshift \(X\). There is a slight difference, though: in the bi-infinite Toeplitz configurations of \(X\), there may exist (at most once per configuration) a position of infinite level; and for such positions, both configurations in which this position is colored “click” and “clack” exist.
As the machine outputs “clack” infinitely often, configurations having “clack” at a position of infinite level belong in the orbit closure of every other configuration. Then:
- If \(\mathcal{M}\) outputs “click” infinitely many times, then a configuration having “click” at the position of infinite level belongs in the orbit closure of all the others, and the subshift \(X\) is minimal.
- If \(\mathcal{M}\) outputs “click” finitely many times, there exists a time \(N\) after which “click” no longer appears in \(s\). Then, by forbidding the finite patterns allowing positions of level \(\geq N\) to be colored “click” in the subshift \(X\), we obtain a strict subshift of \(X\) (as configurations that contain “click” at a position of infinite level are now forbidden) that is non-empty.
All in all, \(X\) is minimal if and only if \(\mathcal{M}\) outputs “click” infinitely many times. This concludes the proof.
Hardness in dimension \(d \geq 2\)
Let me recall a simulation theorem from [Durand & Romashchenko, 2020, Theorem 7]:
Given an effective \(\Z\) subshift \(X_1\), there exists a \(\Z^2\) SFT \(X_2\) such that:
- Denoting \(X_1^\uparrow = \{ x \in A^{\Z^2} \mid \exists y \in X_1, \forall i,j \in \Z, x_{i,j} = y_j \}\) the vertical extension of \(X_1\), then \(X_1^\uparrow\) is a factor of \(X_2\);
- \(X_2\) is minimal if and only if \(X_1\) is minimal.
Basically, this theorem is a minimal version of the fixpoint-based construction. We can then complete the proof of our theorem:
By [Durand & Romashchenko, 2020, Theorem 7], we obtain that Minimality of SFTs in dimension \(d \geq 2\) reduces to the minimality problem for \(\Z\) effective subshifts, which is \(\Pi^0_2\)-hard. This concludes the proof.