# Approximation of subshifts in Hausdorff distance

I have recently been interested in some questions which stem from taking subshifts which converge to a limiting subshift in the Hausdorff metric.

More specifically, given an alphabet $$\mathcal{A}$$, I consider $$\mathcal{A}^{\mathbb{Z}^d}$$ as a dynamical system with a natural action from $$\mathbb{Z}^d$$. When I say subshift, I mean a nonempty closed subset $$\Omega\subseteq \mathcal{A}^{\mathbb{Z}^d}$$ which is invariant under the induced action. I'm interested in conditions of when a sequence of subshifts, $$\{ \Omega_n \}_{n=1}^\infty$$, converge to a limiting subshift in the Hausdorff metric?

Is anyone familiar with references dealing with this sort of questions? I am wondering if there are pages giving conditions for this or estimates on the rate of convergence for the study of specific subshifts?

Later edit

For example, studying an aperiodic subshift, $$\Omega_\infty$$, by a sequence of periodic ones converging to it? And learning properties of the limit subshift by the approximating ones.

• I guess you know that it just means the language converges, and are looking for something more specific? Mar 27, 2023 at 17:37
• This (space of subshifts under Hausdorff metric) is a pretty standard object, here's a generic paper that talks about it arxiv.org/abs/2203.15159 Mar 27, 2023 at 17:39
• @VilleSalo I am aware of that criterion. But I was wondering of examples and methods of approximation. The paper you linked to talks about genericity, which I suspect is not a constructive way to obtain approximations. Mar 28, 2023 at 10:19
• Yes it was pretty much just an arbitrary paper where I know this concept appears explicitly by name. It is not clear to me what you are looking for exactly, so I figured it's better than nothing. There is a canonical way to obtain approximations: Take the SFT approximation where you explicitly require that the patterns in a particular domain must come from the said subshift. For any subshift, this converges in Hausdorff metric. Mar 28, 2023 at 10:41
• Ok, I see your edit now. This is a bit more answerable already. Mar 28, 2023 at 10:45

## 1 Answer

Let $$X \subset A^{\mathbb{Z}^d}$$ be a subshift. So $$A$$ a discrete finite set, $$A^{\mathbb{Z}^d}$$ carries the product topology; $$X$$ is topologically closed in this topology; for all $$\vec v \in \mathbb{Z}^d$$ we have $$X = \sigma_{\vec v}(X)$$ where $$\sigma_{\vec v}(x)_{\vec u} = x_{\vec v + \vec u}$$.

Given finite $$N \subset \mathbb{Z}^d$$, and $$Z \subset A^{\mathbb{Z}^d}$$, write $$Z|_N$$ for $$\{z|_N \;|\; z \in Z\}$$. Write $$O(x) = \{\sigma_{\vec v}(x) \;|\; \vec v \in \mathbb{Z}^d\}$$ for the orbit of a point, and the orbit closure $$\overline{O(x)}$$ is the closure of the orbit.

Given finite $$N \subset \mathbb{Z}^d$$, the $$N$$-SFT approximation $$X^N$$ is the SFT with forbidden patterns those $$P \in A^N$$ that do not appear in $$X$$, i.e. $$X^N$$ is the subshift of all $$y$$ such that $$P \notin O(y)|_N$$ for all $$P \notin X|_N$$. Note that $$X|_N = X^N|_N$$, namely the $$X \subset X^N$$ and by definition any $$N$$-pattern appearing in $$X^N$$ appears in $$X$$ as well.

A subshift is periodic if the subgroup of $$\mathbb{Z}^d$$ containing those $$\vec v \in \mathbb{Z}^d$$ such that $$\sigma_{\vec v}$$ stabilizes $$X$$ pointwise has full rank. A point $$x \in A^{\mathbb{Z}^d}$$ is periodic if its orbit closure $$\overline{O(x)}$$ is periodic. A subshift is aperiodic if it has no periodic points. If $$X, Y \subset A^{\mathbb{Z}^d}$$ and $$N \subset \mathbb{Z}^2$$ is finite, we say $$X$$ is $$N$$-dense in $$Y$$ if $$Y|_N \subset X|_N$$, i.e. $$N$$-patterns appearing in points of $$Y$$ can be found also in points of $$X$$.

Theorem. A subshift $$X \subset A^{\mathbb{Z}^d}$$ has a sequence of periodic subshifts converging to it in Hausdorff metric iff for all $$N$$, the $$N$$th SFT approximation of $$X$$ has $$N$$-dense periodic points in $$X$$ (i.e. periodic points of $$X^N$$ are $$N$$-dense in $$X$$).

Proof. Suppose first that $$X$$ is the limit of periodic subshifts $$X_i$$. Let $$N \subset \mathbb{Z}^d$$ be any finite set and consider the SFT approximation $$X^N$$. Suppose for a contradiction that $$X^N$$ does not have $$N$$-dense periodic points in $$X$$. This means that some pattern $$P \in A^N$$ appears in $$X$$ but not in any periodic point of $$X^N$$. Take $$i$$ sufficiently large so that $$X_i|_N = X|_N = X^N|_N$$. Then $$X_i$$ contains a point $$x$$ with $$x|_N = P$$. Since $$X_i|_N = X^N|_N$$, we have $$X_i \subset X^N$$, so $$x \in X^N$$. But then $$x$$ is a periodic point in $$X^N$$ containing the pattern $$P$$, a contradiction.

Suppose then that the $$N$$-SFT approximation of $$X$$ has $$N$$-dense periodic points for all finite sets $$N$$. Let $$N$$ be arbitrary, and for each $$P \in X|_N$$ pick an arbitrary periodic point $$y_P \in X^N$$ with $$y_P|_N$$ = P. Then $$\bigcup_{P \in X|_N} \overline{O(y_P)}$$ is a finite (thus periodic) subshift which clearly agrees with the language of $$X$$ in $$N$$. Square.

For a one-dimensional subshift $$X \subset A^{\mathbb{Z}}$$, say it is chain-transitive if for any $$\epsilon > 0$$ and any $$x, y \in X$$, there exists a sequence of points $$x = x_1, x_2, ..., x_k = y$$ such that $$d(\sigma(x_i), x_{i+1}) < \epsilon$$ for all $$i$$. It is transitive if for any $$\epsilon > 0$$ and $$x, y$$ there exist $$z \in X$$ and $$n > 0$$ such that $$d(z, x) < \epsilon$$ and $$d(\sigma^n(z), y) < \epsilon$$.

Theorem. If $$X \subset A^{\mathbb{Z}}$$ is chain-transitive, then it is the limit of periodic subshifts in Hausdorff metric.

Proof. It suffices to show that the $$N$$-SFT approximation of $$X$$ has $$N$$-dense periodic points in $$X$$. For this it suffices to show that the $$N$$-SFT approximation has dense periodic points. For this, observe that if $$X$$ is chain-transitive, then the $$N$$-SFT approximation is transitive for any $$N$$ (this requires a little proof, but it's kind of well known). It is well known that transitive $$\mathbb{Z}$$-SFTs have dense periodic points. Square.

Corollary. Every minimal $$\mathbb{Z}$$-subshift is the limit of periodic subshifts in Hausdorff metric.

Proof. Minimal obviously implies chain-transitive (even transitive). Square.

Let's also show that the corollary fails badly in two dimensions.

Theorem. Two-dimensional SFTs can be aperiodic and minimal.

Proof. This is classical, perhaps first explicitly stated and proved in Mozes, Shahar, Aperiodic tilings, Invent. Math. 128, No. 3, 603-611 (1997). ZBL0879.52011. . Square.

Lemma. Minimal SFTs are isolated point in the space of subshifts under the Hausdorff metric.

Proof. If $$X$$ is a minimal SFT with forbidden patterns contained in $$N$$, and $$Y$$ is sufficiently close to it in Hausdorff metric, then $$Y \subset X$$ since $$Y|_N = X|_N$$ and $$X$$ is equal to its $$N$$th SFT approximation. Since $$X$$ is minimal, $$Y = X$$. Square.

Theorem. There exists a minimal aperiodic two-dimensional subshift which is not a limit of periodic subshifts in Hausdorff metric.

Proof. Let $$X$$ be a two-dimensional aperiodic minimal SFT. By the previous lemma it is isolated, so any sufficiently good approximation is aperiodic. Square.

• Thank you for your answer. This is a result I suspected should hold, and was the motive behind some of my past questions. Thanks for clearing this. Mar 28, 2023 at 12:24
• Perhaps as an additional question, Is the approximation always 'essentially' by SFT's? I mean the underlying metric is usually the big ball metric which is an ultra-metric, which I think implies the Hausdorff metric is also an ultra-metric. For that reason, can every approximating sequence of subshifts be a replaced by a sequence of SFT's with the same distance from the limit? Mar 28, 2023 at 12:26
• Yes in the sense that if $X$ is a subshift, and $X_i \longrightarrow X$ are arbitrary subshifts which are not equal to $X$, then there exist subshifts of finite type $Y_i$ such that $d(X_i, X) = d(Y_i, X)$ (here I assume the Hausdorff metric is defined with one of the usual underlying metrics that only look at positions where configurations differ). Namely take a very large $N$ that witnesses the difference between $X_i$ and $X$ and take the $N$-SFT approximation of $X_i$. Mar 28, 2023 at 12:39
• Okay, thanks again. Mar 28, 2023 at 12:40