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.

  • $\begingroup$ I guess you know that it just means the language converges, and are looking for something more specific? $\endgroup$
    – Ville Salo
    Mar 27, 2023 at 17:37
  • $\begingroup$ 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 $\endgroup$
    – Ville Salo
    Mar 27, 2023 at 17:39
  • $\begingroup$ @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. $\endgroup$ Mar 28, 2023 at 10:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ville Salo
    Mar 28, 2023 at 10:41
  • $\begingroup$ Ok, I see your edit now. This is a bit more answerable already. $\endgroup$
    – Ville Salo
    Mar 28, 2023 at 10:45

1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$ Mar 28, 2023 at 12:24
  • $\begingroup$ 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? $\endgroup$ Mar 28, 2023 at 12:26
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Ville Salo
    Mar 28, 2023 at 12:39
  • $\begingroup$ Okay, thanks again. $\endgroup$ Mar 28, 2023 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.