1 Introduction
Given a (large) collection of objects, it is somewhat natural to wonder which members within this family are typical. One way to formalize the idea of a typical object, in a topological sense, is the notion of a dense
$G_\delta $
set: a countable intersection of open dense sets. Properties satisfied by every element in a dense
$G_\delta $
set are called generic properties. Recall that a set is residual if it contains a dense
$G_\delta $
set. In a dynamical systems context, where the collection of objects is a family of (dynamical) systems, the study of generic properties has taken many forms over the years and it has produced a wide range of results. The first results in this direction appeared as early as the 1940s with the works of Oxtoby and Ulam [Reference Oxtoby and Ulam19], asserting that a generic volume-preserving homeomorphism of a cube is ergodic. Halmos [Reference Halmos13–Reference Halmos15], in 1944, showed that a generic, measure-preserving transformation is weakly mixing; and four years later, Rohlin [Reference Rohlin22] proved that such a transformation is not strongly mixing—by showing that strongly mixing transformations are not generic. These two latter results combined means (indirectly) that there exist weakly mixing systems that are not strongly mixing, constituting the first evidence of the existence of such systems. Multiple other results have been found, for example, [Reference Akin, Hurley and Kennedy2, Reference Bezugly, Dooley and Kwiatkowski4, Reference Glasner12].
This kind of questions has been studied in the space of transformations over spaces conjugated to Cantor sets as well. For instance, Kechris and Rosendal [Reference Kechris and Rosendal18] found in 2007 that the homeomorphism group of the Cantor space has but one generic conjugacy class. This result was quite surprising, since the variety of dynamics on the Cantor space is large and, in comparison, this generic class is rather ‘small’. The implication is that generic properties of Cantor systems are fairly degenerated. In 2008, a description of this system was provided by Akin, Glasner and Weiss [Reference Akin, Glasner and Weiss1]. About the same time, Hochman [Reference Hochman16] established a series of results for transitive and totally transitive homeomorphisms of the Cantor space. In particular, he showed that in this space, generic, totally transitive transformations have zero topological entropy.
In this article, we are concerned with the space
$\mathcal {S}^d$
of all
$\mathbb {Z}^d$
-shifts, that is, the union of all shift spaces
$\mathcal {A}^{\mathbb {Z}^d}$
, with the union running through all finite alphabets
$\mathcal {A} \subset \mathbb {Z}$
. This space is typically endowed with the Hausdorff metric and we keep this tradition here. For
$d=1$
, numerous genericity results have been obtained. In 1971, Sigmund [Reference Sigmund24] showed that the set of subshifts with zero topological entropy is residual in the space
$\mathcal {A}^{\mathbb {Z}}$
. Sigmund’s result was extended by Frisch and Tamuz [Reference Frisch and Tamuz8] to shifts spaces
$\mathcal {A}^G$
, where G is an amenable group. Moreover, in this setting, they showed that for any c, shifts with entropy c are generic in the space of shifts with entropy at least c.
In a recent development, Pavlov and Schmieding [Reference Pavlov and Schmieding20] showed in 2023 that in
$S^1$
, generic shifts are precisely those whose descriptive graphs satisfy a simple combinatorial property: no cycle in the graph has both incoming and outgoing edges. This description implies that a generic shift in
$S^1$
is a countable shift of finite type that is the union of finitely many orbits that are bi-asymptotic to periodic orbits. The consequences of this characterization are many, notably, all known results about the structure of generic shifts can be recovered from this characterization. In particular, they easily recover Sigmund’s result: generically, a shift has zero entropy.
As often occurs, the situation changes dramatically when considering multidimensional dynamics. In the case of shift spaces, see for instance [Reference Berger3, Reference Callard and de Menibus5, Reference Durand, Romashchenko and Shen7, Reference Hochman and Meyerovitch17, Reference Robinson21]. Thus, it is not surprising that a characterization of generic shifts in
$\mathcal {S}^d$
,
$d\geq 2$
, becomes a heavy task. In [Reference Pavlov and Schmieding20], the authors left open the question of generic shifts in the space of shifts on groups different from
$\mathbb {Z}$
. Observe that understanding isolated points (if there are any) is a reasonable first approach to generic properties, as every residual set must contain them. Our present work addresses this problem and provides a characterization of such points by the means of the notions of maximal subsystems and outcasts: (i) a (non-empty) subsystem is maximal if it is a proper subsystem and it is not contained in any other proper subsystem; (ii) a (non-empty) subsystem is an outcast if it is a proper subsystem and it is not contained in a maximal subsystem.
Theorem A. A
$\mathbb {Z}^d$
-shift is isolated in
$\mathcal {S}^d$
if and only if it is of finite type, it has finitely many maximal subsystems and contains no outcast.
This characterization suggests the existence of isolated points with infinitely many subsystems, which does not occur in
$S^1$
. In §3.3, we exhibit such a system using the well-known Robinson shift [Reference Robinson21]. As the construction is quite involved and the example is not essential for the remainder of the paper, we do not provide all the technical details. We address this example to specialists and we leave the interested reader to find details, for instance, in [Reference Gangloff10, Reference Robinson21]. The characterization in Theorem A allows to recover Pavlov and Schmieding’s, Corollary 3.29. We further explore structural implications of the conditions on maximal subsystems through what we call maximality type, that is, a shift has maximality type
$n\in \mathbb {N}_0\cup \{\infty \}$
if it contains exactly n maximal subsystems. We use this notion to follow Hochman, Pavlov and Schmieding, and others, to study isolated points in the space of transitive shifts—in
$S^1$
, those points do not even exist. In particular, we found that transitive shifts have maximality type either 0 or 1. Furthermore, we characterize isolated points in this space.
Theorem B. In the space
$\mathcal {T}^d$
of transitive
$\mathbb {Z}^d$
-shifts, a shift of finite type is isolated if it has maximality type 1 or if it is minimal. Furthermore, a non-finite type shift X with maximality type 1 is isolated if and only if it is contained in a shift of finite type Z such that
$Z \backslash X$
is not dense in Z.
We also provide, in §5.2.3, an example of a transitive shift that is not of finite type and is isolated. This implies in particular that minimality is not a generic property, in contrast to the one-dimensional case. We find as well that strong mixing-type properties, such as block gluing, imply that the shift has maximality type 0.
These results exhibit a tight relation between maximal subsystems and the topological structure of shift spaces, and genericity might be understood in these terms. Note that although we do not consider other groups than
$\mathbb {Z}^d$
, we expect our result to be generalizable to other groups without particular difficulty.
We identify two approaches to the study of genericity:
-
(1) computing the closure of the set of isolated points, which is challenging. However, we provide here examples of shifts that are not in this closure, and examples of non-isolated shifts that are in it;
-
(2) computing the Cantor–Bendixon rank of the space of
$\mathbb {Z}^d$
-shifts to shed some additional light on the topological structure of this space. Here, we show that the rank is infinite, but a precise computation remains an open question.
In this second direction, using properties of the well-known
$\times 2\times 3$
system on the circle, we build examples of shifts proving the following theorem.
Theorem C. For all
$d> 1$
, the Cantor–Bendixson rank of the space of
$\mathbb {Z}^d$
-shifts is infinite.
In the first direction, the strategy would be to better understand the structure of subsystems of isolated shifts and, more generally, how the maximality type affects this structure. We may find some rigidity there which must be satisfied also by shifts in the closure of the set of isolated points.
The text is organized as follows. Section 2 contains some background definitions and elements of constructions for some examples presented after. In §3, we prove the characterization of isolated points in the space of
$\mathbb {Z}^d$
-shifts. Section 5 is devoted to transitive shifts. In §4, we prove that every shift can be written as a union of a sequence of shifts of maximality type
$1$
and a shift of maximality type
$0$
. We also prove some properties of this decomposition that will be useful in the following section. In §6, we consider the question of the closure of isolated points and prove that the Cantor–Bendixson rank is infinite. Finally, §7 presents questions that we leave open.
2 Background
2.1 Shifts
2.1.1 Elementary definitions
For any finite set
$\mathcal {A}\subset \mathbb {Z}$
and integer
$d \ge 1$
, the set
$\mathcal {A}^{\mathbb {Z}^d}$
is called the d-dimensional full shift on alphabet
$\mathcal {A}$
. Elements in this set are maps
${x:\mathbb {Z}^d\to \mathcal {A}}$
that we call d-dimensional configurations. For such a configuration x, the value of x for
$\textbf {v}\in \mathbb {Z}^d$
is denoted by
$x_{\textbf {v}}$
. For two configurations
$x,y$
, we set
$$ \begin{align*}\delta(x,y) := 2^{ - \inf \{\lVert\textbf{n}\rVert_{\infty}\mid\textbf{n} \in \mathbb{Z}^d : x_{\textbf{n}} \neq y_{\textbf{n}}\}},\end{align*} $$
where
$\lVert \textbf {v}\rVert _\infty =\max _{k\leq d}|v_k|$
for every
$\textbf {v}$
in
$\mathbb {Z}^d$
. For a configuration x and a shift Y, we denote by
$\delta (x,Y)$
the number
$\min _{y\in Y}\delta (x,y)$
.
We denote by
$\sigma _d$
the
$\mathbb {Z}^d$
-action on
$\mathcal {A}^{\mathbb {Z}^d}$
such that for all
$\textbf {u},\textbf {v} \in \mathbb {Z}$
and x, a d-dimensional configuration,
$\sigma _d^{\textbf {u}} (x)_{\textbf {v}} = x_{\textbf {u}+\textbf {v}}$
.
In the following, we simplify the notation
$\sigma _d$
into
$\sigma $
, as it will be clear from the configuration it applies to, which action it designates.
A d-dimensional shift is a compact (for the topology induced by the metric
$\delta $
) subset X of
$\mathcal {A}^{\mathbb {Z}^d}$
such that for all
$\textbf {u} \in \mathbb {Z}^d$
,
$\sigma ^{\textbf {u}}(X) \subset X$
. A pattern on a finite set
$\mathcal {A}$
is a map
$p: \mathbb {U} \rightarrow \mathcal {A}$
, of a domain
$\mathbb {U}$
of
$\mathbb {Z}^d$
. The domain
$\mathbb {U}$
is called the support of p. For every
$n\in \mathbb {N}$
, we set 
and 
. A pattern is called finite when its support is finite. In the remainder of the text, we assume that patterns are finite, unless stated otherwise. We say that a pattern p on support
$\mathbb {U}$
appears in a configuration x if there is some
$\textbf {u} \in \mathbb {Z}^d$
such that for all
$\textbf {v} \in \mathbb {U}$
,
$x_{\textbf {v} + \textbf {u}} = p(\textbf {v})$
. We denote this by
$p\sqsubset x$
. We say that p is globally admissible for a shift X when it appears in at least one configuration of X. For a shift X, and
$\mathbb {U}$
a subset of
$\mathbb {Z}^d$
, we denote by
$\mathscr {L}_{\mathbb {U}}(X)$
the set of patterns on
$\mathbb {U}$
that are globally admissible for X. The language of X is the set, denoted by
$\mathscr {L}(X)$
, defined as the union of the sets
$\mathscr {L}_{\mathbb {U}}(X)$
, where
$\mathbb {U}$
runs over all finite subsets of
$\mathbb {Z}^d$
. We endow the set
$\mathscr {L}(X)$
, as well as any
$\mathcal {L}_{\mathbb {U}}(X)$
where
$\mathbb {U}$
is infinite, with the prodiscrete topology.
For any finite set of patterns
$\mathcal {F}$
on the same alphabet
$\mathcal {A}$
, let us denote by
$X_{\mathcal {F}}$
the shift on alphabet
$\mathcal {A}$
obtained by forbidding the patterns of
$\mathcal {F}$
:
$$ \begin{align*} X_{\mathcal{F}} = \{x \in X : \text{ for all } p \in \mathcal{F}, p \not \sqsubseteq x\}. \end{align*} $$
Patterns in
$\mathcal {F}$
are called forbidden patterns (for
$X_{\mathcal {F}}$
), while a pattern that is not in
$\mathcal {F}$
is called an allowed pattern (for
$X_{\mathcal {F}}$
).
We say that a shift X is of finite type when there exists a finite set
$\mathcal {F}$
such that
$X = X_{\mathcal {F}}$
. For every configuration x, we denote by
$\mathcal {O}(x)$
the set
$\{\sigma ^{\textbf {u}}(x) : \textbf {u} \in \mathbb {Z}^d\}$
and call it the orbit of x.
For two shifts
$X,X'$
on alphabets
$\mathcal {A},\mathcal {A}'$
, we denote by
$X \times X'$
the shift on alphabet
$\mathcal {A} \times \mathcal {A}'$
such that:
$$ \begin{align*} X \times X' = \{z : \text{ there exists } x \in X, x' \in X', \text{ for all } \textbf{u} \in \mathbb{Z}^d, z_{\textbf{u}} = (x_{\textbf{u}},x^{\prime}_{\textbf{u}})\}. \end{align*} $$
A subsystem of X is simply a non-empty closed subset of this shift that is invariant by the shift action. We say that X is minimal when its only subsystem is X itself. We say that it is transitive when there exists some
$x \in X$
such that
$\overline {\mathcal {O}(x)} = X$
.
A map
$\varphi :X\to Y$
, where
$X,Y$
are two d-dimensional shifts, is called a conjugacy when it is a homeomorphism such that for all
$\boldsymbol {u} \in \mathbb {Z}^d$
,
$\varphi \circ \sigma _d^{\boldsymbol {u}} = \sigma _d^{\boldsymbol {u}} \circ \varphi $
.
2.1.2 The space
$\mathcal {S}^d$
of d-dimensional shifts
From now on, we denote by
$\mathcal {S}^d$
the set of all d-dimensional shifts. For any two shifts,
$X,Z$
, we set
$$ \begin{align*}\delta_H(X,Z) := \max \Big(\sup_{x \in X} \inf_{z \in Z} \delta(x,z), \sup_{z \in Z} \inf_{x \in X} \delta(z,x)\Big).\end{align*} $$
The function
$\delta _H$
is a metric and it is called the Hausdorff metric. In the following, we will use the straightforward fact that a sequence of shifts
$(X_n)_{n \ge 0}$
converges towards X for the metric
$\delta _H$
if and only if for all finite subsets
$\mathbb {U}$
of
$\mathbb {Z}^d$
, there exists m such that for all
$n \ge m$
,
$\mathscr {L}_{\mathbb {U}}(X_n) = \mathscr {L}_{\mathbb {U}}(X)$
.
2.2 Constructions
In this section, we present some elements often used in constructions of higher dimensional shifts, and used as well in the present article.
2.2.1 Constructions by layers
A general paradigm for construction of higher dimensional shifts is that of layers. By adding a layer to a shift X, we mean considering a shift Y included in
$X \times Z$
, where Z is a shift called the added layer. When X and Z are shifts of finite type and there is a finite set of patterns
$\mathcal {F}$
such that Y is the set of configurations in
$X \times Z$
in which no pattern of
$\mathcal {F}$
appears, then Y is also of finite type. We say that a layer is accessory when for all
$x \in X$
, there is a unique configuration
$z\in Z$
such that
$(x,z)$
is in Y.
2.2.2 Robinson shift
Another element often used in constructions is a shift due to R. Robinson [Reference Robinson21]. As this construction is quite involved and long to unpack, and since we use it in constructions that serve as examples and not in the proofs of core results, we will refer to a past work of the first author [Reference Gangloff10] and to the original article [Reference Robinson21] for details about this construction and keep its exposition relatively informal.
We denote this shift by
$X_R$
. It can be described in terms of layers. Its alphabet is the following set of symbols and their rotations by angles
${\pi }/{2}$
,
$\pi $
or
${3\pi }/{2}$
(colour figures are available online):
where i and j can be
$0$
or
$1$
. The corner symbols with
$0$
at the center are referred to as blue corners and the ones with
$1$
at the center are referred to as red corners. The shift
$X_R$
is defined by a set of forbidden patterns that can be derived from the following rules.
-
(1) Outgoing and incoming arrows must correspond for two adjacent symbols. For instance, the following patterns are respectively forbidden (left) and allowed (right):
-
(2) In every
$2 \times 2$
square pattern (meaning a pattern on a translate of
$\{0,1\}^2$
), there is a blue corner and the presence of a blue corner in a position
$\textbf {u} \in \mathbb {Z}^2$
forces the presence of a blue corner on positions
$\textbf {u}+(0,2), \textbf {u}-(0,2), \textbf {u}+(2,0)$
and
$\textbf {u}-(2,0)$
. -
(3) The value i is transmitted horizontally, meaning that two consecutive positions
$(n,m)$
and
$(n+1,m)$
have the same i, while the value j is transmitted vertically. -
(4) On a six arrows symbol or a five arrows symbol, for instance the respective patterns:
we have
$i \neq j$
.
As a consequence,
$X_R$
is a shift of finite type.
Finite supertiles—In any configuration of
$X_R$
, the blue corners cause the presence of some particular square patterns that are called supertiles, which themselves cause larger supertiles that are similar to the first ones, etc. Let us define these supertiles formally, by induction. For all
$n\in \mathbb {N}$
, we denote by
$St_{sw} (n)$
,
$St_{sw} (n)$
,
$St_{sw}(n)$
and
$St_{sw}(n)$
the south west, south east, north west and north east supertiles of order n, respectively. For
$n=0$
, these supertiles are defined as follows:
For all
$n\in \mathbb {N}$
, the support of the supertile
$St_{sw}(n+1)$
(respectively
$St_{se} (n+1)$
,
$St_{nw} (n+1)$
,
$St_{ne} (n+1)$
) is set as
$\mathbb {U}^{(2)}_{2^{n+2}-1}$
. These supertiles are constructed as follows.
-
(1) For
$\textbf {u}\kern1.4pt{=}\kern1.4pt(2^{n+1}\kern1.4pt{-}\kern1.4pt 1,2^{n+1}\kern1.4pt{-}\kern1.4pt 1)$
, the symbols
$St_{sw} (n\kern1.4pt{+}\kern1.4pt 1) _{\textbf {u}}$
,
$St_{se} (n\kern1.4pt{+}\kern1.4pt 1) _{\textbf {u}}$
,
${St_{nw} (n+1)_{\textbf {u}}}$
,
$St_{ne} (n+1) _{\textbf {u}}$
are respectively.
-
(2) The restriction to
$\mathbb {U}^{(2)}_{2^{n+1}-1}$
(respectively
$(2^{n+1},0)+\mathbb {U}^{(2)}_{2^{n+1}-1}$
,
$(0,2^{n+1})+\mathbb {U}^{(2)}_{2^{n+1}-1}$
,
$(2^{n+1}, 2^{n+1})+\mathbb {U}^{(2)}_{2^{n+1}-1}$
) is
$St_{sw}(n)$
(respectively
$St_{se} (n)$
,
$St_{nw} (n)$
,
$St_{ne} (n)$
). -
(3) Each of the other positions (forming a cross whose centre is at the centre of the square) is filled with one symbol among the following, up to rotation (they are uniquely determined by their neighbouring symbols):
An example of a supertile is displayed in Figure 1.
The south west supertile of order two (some 0s and 1s are omitted for clarity) (colour online).
Infinite supertiles—Let x be a configuration in
$X_R$
and consider the equivalence relation
$\sim _x$
on
$\mathbb {Z}^2$
defined by
$\textbf {i} \sim _x \textbf {j} \Leftrightarrow $
there is a finite supertile in x on a support that contains
$\textbf {i}$
and
$\textbf {j}$
. An infinite order supertile is an infinite pattern whose support is an equivalence class of this relation. Each configuration satisfies one of the following:
-
(i) it has a unique infinite order supertile on support
$\mathbb {Z}^2$
; -
(ii) it has two infinite order supertiles separated by an infinite row
$\mathbb {Z} \times \{m\}$
or a column
$\{m\} \times \mathbb {Z}$
with only three-arrows symbols or only four-arrows symbols on it. In such a configuration, there might be some finite n such that order n supertiles in one of the infinite supertiles might not be aligned with the order n supertiles in the other (whereas in a configuration that satisfies condition (i) or (iii), order n supertiles are aligned with respect to all infinite supertiles). -
(iii) It has four infinite order supertiles, separated by an infinite cross, that is,
${\mathbb {C}_{m,n} := \mathbb {Z} \times \{m\} \bigcup \{n\} \times \mathbb {Z}}$
for some
$m,n \in \mathbb {Z}$
, such that
$(m,n)$
is superimposed with a red corner, a six-arrows symbol or a five-arrows symbol. In any case, the symbols on
$\mathbb {C}_{m,n} \backslash \{(m,n)\}$
are uniquely determined by their surrounding symbols.
Minimal version—Note that
$X_R$
is not a minimal shift. The main reason is that provided a configuration of type (ii), any configuration obtained from it by shifting one of its infinite supertiles relative to the other is also in
$X_R$
. There are patterns across the infinite line separating the infinite supertile that do not appear in every configuration of
$X_R$
. However, it is possible to add a layer to
$X_R$
so that in configurations that satisfy condition (ii), the supertiles of the same (finite) order across the infinite row or column are aligned and the obtained shift is a minimal shift of finite type. Roughly speaking, the idea is to use the accessory layer to send ‘signals’ between supertiles forcing them to be aligned. This is a standard technique and a detailed construction can be found in [Reference Gangloff10], for instance. We denote this shift by
$X_R^{+}$
.
Additional terminology—Provided a configuration of
$X_R$
, for each supertile of order n, the position in
$\mathbb {Z}^2$
of the central symbol is called a site of order n. We call a cell of order n the subset of
$\mathbb {Z}^2$
enclosed by sites of order
$2n+1$
at the centre of which there is another site. We call the cytoplasm of a cell of order n the set of positions in this cell that do not belong to any cell of smaller order. The border of a cell is the set of its elements that does not have four neighbours in it. A free column (respectively row) of a cell
$\mathbb {C}$
is a subset of the form
$(\mathbb {Z} \times \{m\})\cap \mathbb {C}$
(respectively
$(\{m\}\times \mathbb {Z})\cap \mathbb {C}$
) that does not intersect a cell of smaller order.
Subsystems of
$X_R$
—We denote by
$X_{R}^{\infty }$
the set of configurations that satisfy condition (i) or (iii). It is a minimal shift. Furthermore, for all n, we denote by
$X_R^n$
the subsystem of
$X_R$
obtained by enforcing, in configurations satisfying condition (ii), the order
$k \le n$
supertiles across the separating row or column to be aligned. It is straightforward that
$X_R^n$
is of finite type for all n, that the sequence
$(X_R^n)_n$
is strictly decreasing and that
$$ \begin{align*}\bigcap_n X_R^n = X_R^{\infty}.\\[-19pt]\end{align*} $$
For the remainder of the text, we denote by
$\textbf {e}_1, \ldots , \textbf {e}_d$
the canonical basis of
$\mathbb {Z}^d$
.
2.2.3 Encoding finite alphabets into
$\mathbb {Z}$
In the text, we provide examples of shifts on some alphabets
$\mathcal {A} \not \subset \mathbb {Z}$
. For each one of these, we implicitly re-encode the shift so that the alphabet is included in
$\mathbb {Z}$
. By re-encoding, we mean the following: consider X a shift on alphabet
$\mathcal {A}$
, and
$\phi : \mathcal {A} \rightarrow \mathcal {A}'$
a bijection. The re-encoded shift is the image of X by the map
$x \mapsto (\phi (x_{\boldsymbol {u}}))_{\boldsymbol {u} \in \mathbb {Z}^d}$
.
3 Characterization of isolated points in
$\mathcal {S}^d$
To investigate generic shifts in higher dimension, the approach we have taken is to first understand isolated points in
$\mathcal {S}^d$
. We characterize these points in the present section and this characterization will help us prove that the closure of the set of isolated shifts is not
$\mathcal {S}^d$
. The characterization is as in Theorem A: a shift is isolated if and only if it is of finite type, it has finitely many maximal subsystems and each of its subsystems is included in a maximal subsystem. We prove it in §3.2 and, as an application, we recover the characterization in one dimension formulated by R. Pavlov and S. Schmieding. Using a construction based on the Robinson shift, we construct a shift with finitely many maximal subsystems, but infinitely many subsystems (§3.3). We remark that such a system does not exist in the space of
$\mathbb {Z}$
-shifts.
To the best of our knowledge, the notion of maximal subsystem involved naturally in the characterization of isolated shifts has not been studied elsewhere. We devote §3.4 to the study of this notion in and of itself. Section 3.1 contains auxiliary results on topology that are useful in the present section.
3.1 Auxiliary results
Results presented throughout this subsection are elementary, but proofs are included for completeness.
Lemma 3.1. Let
$(X_n)_{n\ge 0}$
be a sequence of shifts in
$\mathcal {S}^d$
such that for all
$n \ge 0$
,
$X_{n+1} \subset X_n$
and set
$X_{\infty }:= \bigcap _n X_n$
. Then,
$X_n$
converges to
$X_{\infty }$
for the Hausdorff topology.
Proof. Let us assume, in contrast, that there exists
$\epsilon>0$
and infinitely many integers n such that there exists
$x_n \in X_n$
with
$\delta (x_n,X_{\infty }) \ge \epsilon $
. By compactness, we can assume that
$x_n$
converges to a point
$x \in X$
. Furthermore, since
$(X_n)_{n \ge 0}$
is non-increasing,
$x \in X_n$
for all n and thus
$x \in X_{\infty }$
. However, because the distance
$\delta $
is a continuous function,
$\delta (x,X_{\infty }) \ge \epsilon $
, which is a contradiction.
The following is straightforward.
Lemma 3.2. Consider three shifts
$X' \subset X \subset Z$
. We have
$\delta _H(X',Z) \ge \delta _H(X,Z)$
.
For
$\epsilon> 0$
, we denote by
$B_{\epsilon }(x,X)$
the set of configurations
$z \in X$
such that
$\delta (x,z) < \epsilon $
. We say that a sequence of shifts
$(X_n)_{n\geq 0}$
is non-decreasing (respectively non-increasing) if for all n, it holds that
$X_n\subseteq X_{n+1}$
(respectively
$X_{n+1}\subseteq X_n$
).
Lemma 3.3. Consider a shift
$X_{\infty }$
and a non-decreasing sequence of shifts
$(X_n)_{n \ge 0}$
such that
$X_{\infty } = \bigcup _n X_n$
. Then,
$X_n$
converges to
$X_{\infty }$
.
Proof. If it were not the case, there would be some
$\epsilon>0$
and a subsequence
$(n_k)_{k\in \mathbb {N}}$
such that for all k, we have
$\delta _H(X_{n_k},X_\infty ) \ge \epsilon $
, and by Lemma 3.2, we have that for all n,
$\delta _H(X_n,X_{\infty }) \ge \epsilon $
. For all n, since
$X_n \subset X_{\infty }$
, there exists an element
$x_n$
of
$X_{\infty }$
such that
$B_{\epsilon }(x_n,X_{\infty })$
is contained in
$X_{\infty } \backslash X_n$
. By compactness, we can assume that
$x_n \rightarrow x \in X_{\infty }$
. Therefore,
$B_{\epsilon /2}(x,X_{\infty })$
does not intersect any
$X_n$
, which contradicts the fact that
$X_{\infty }$
is the union of the sets
$X_n$
.
Lemma 3.4. Let X be a shift and let
$U \subset X$
be such that
$\sigma ^{\textbf {u}}(U) \subset U$
for all
$\textbf {u} \in \mathbb {Z}^d$
. The set
$\overline {U}$
is a shift.
Proof. Let
$x \in \overline {U}$
. There exists a sequence of elements
$x_n$
of U that converges to x. Because U is invariant under the action of the shift, for all
$\textbf {v}\in \mathbb {Z}^d$
,
$\sigma ^{\textbf {v}}(x_n) \in U$
. By continuity of
$\sigma ^{\textbf {v}}$
, for all
$\textbf {v}\in \mathbb {Z}^d$
,
$\sigma ^{\textbf {v}}(x_n)$
converges to
$\sigma ^{\textbf {v}}(x)$
, which is thus in
$\overline {U}$
.
3.2 Characterization of isolated points in
$\mathcal {S}^d$
This section is decomposed into three subsections: first, we prove that isolated shifts are all of finite type (§3.2.1); second, we exhibit a relation with maximal subsystems (§3.2.2); then, we formulate the characterization of isolated shifts in
$\mathcal {S}^d$
in §3.2.3.
3.2.1 Isolated shifts are of finite type
First, we show that any isolated shift is a shift of finite type and that for any shift of finite type X, there is a neighbourhood of X that contains only subsystems of X.
Lemma 3.5. For all
$d \ge 1$
, isolated shifts in
$\mathcal {S}^d$
are of finite type.
Proof. Let X be an isolated shift and assume it is not of finite type. Let
$\mathcal {F}$
be a set of forbidden patterns such that
$X = X_{\mathcal {F}}$
. For all
$n \ge 1$
, we consider the shift
$X_n := X_{\mathcal {F}_n}$
, where
$\mathcal {F}_n$
is the set of patterns in
$\mathcal {F}$
that appear in a pattern on 
. By definition, the sequence
$(X_n)_{n \ge 0}$
is non-increasing and takes infinitely many values; otherwise, the sequence would be ultimately constant, and X would be equal to some
$X_n$
and thus be of finite type. We only have left to prove that
$X_n$
converges to X, and this is a direct consequence of Lemma 3.1.
Reciprocally, a shift of finite type is not necessarily isolated.
Example 3.6. For any alphabet
$\mathcal {A}$
such that
$|\mathcal {A}| \ge 2$
, the full shift on
$\mathcal {A}$
is not isolated in
$\mathcal {S}^d$
. Indeed, for all
$n \ge 0$
, set
$X_n := X_{\{p_n\}}$
, where
$p_n : \mathbb {B}_n^d \rightarrow \mathcal {A}$
is constant with value a. The sequence
$(X_n)_{n\ge 0}$
converges towards the full shift on alphabet
$\mathcal {A}$
.
However, we have information about the systems contained in a close enough neighbourhood of a shift of finite type.
Lemma 3.7. A shift
$X \in \mathcal {S}^d$
is of finite type if and only if there exists
$\epsilon>0$
such that for all
$Z \in \mathcal {S}^d$
, if
$\delta _H(Z,X) < \epsilon $
, then
$Z \subset X$
.
Proof. (
$\Rightarrow $
) There is a finite set of patterns
$\mathcal {F}$
such that
$X = X_{\mathcal {F}}$
. There exists n such that the supports of these patterns are all contained in some translate of
$\mathbb {B}_n^d$
. Therefore, the ball around X of diameter
$2^{-n}$
for the metric
$\delta _H$
contains only shifts whose languages have empty intersection with
$\mathcal {F}$
, meaning that they are subsystems of X. (
$\Leftarrow $
) If X is not of finite type, then for all
$\epsilon $
, there is some
$Z \in \mathcal {S}^d$
such that
$\delta _H(Z,X) < \epsilon $
and Z is not contained in X. To see this, it is sufficient to consider the sequence
$(X_n)$
such that for all n,
$X_n$
is defined by forbidding the patterns that are on some support
$\mathbb {U}$
amongst the first n subsets of an enumeration of all finite subsets of
$\mathbb {Z}^d$
and that are not in
$\mathscr {L}_{\mathbb {U}}(X)$
.
Lemma 3.8. Consider a shift of finite type X. Every subsystem of X has a neighborhood whose elements are all subsystems of X.
Proof. The proof is similar to the direction
$(\Rightarrow )$
in the proof of Lemma 3.7.
3.2.2 Maximal subsystems
After the observations made in the last section, it is natural to search for a characterization of isolated shifts in terms of their subsystems. As a matter of fact, we have the following proposition.
Proposition 3.9. If a shift of finite type has finitely many subsystems, then it is isolated.
Proof. Let us consider a shift of finite type X that has finitely many subsystems. As a consequence of Lemma 3.7, there is a neighbourhood of X that contains only subsystems of X. Since by hypothesis there are finitely many of them, there is a neighbourhood of X that only contains X, meaning that it is isolated.
In the same vein, we have the following lemma that will be useful below.
Lemma 3.10. Every subsystem of a shift of finite type X having a finite number of subsystems is isolated.
Proof. As a consequence of Lemma 3.8, every subsystem of X has a neighbourhood that consists only of subsystems of X, meaning that it is finite. Since a shift with finite neighbourhood is isolated, this yields the statement.
Remark 3.11. Lemma 3.10 implies that if a shift of finite type has finitely many subsystems, all its subsystems are of finite type.
One may observe that the proof of Proposition 3.9 can be generalized to shifts of finite type that has a finite collection
$\mathcal {C}$
of strict subsystems with the property that every strict subsystem is contained in an element of
$\mathcal {C}$
. This suggest the following definition.
Definition 3.12. Let X be a shift. We say that a subsystem Z of X is maximal when it is different from X and if
$Z' \supset Z$
is another subsystem different from Z, then
$Z' = X$
. We say that a subsystem of X is an outcast if it is not contained in a maximal subsystem.
Then, we can formulate the following proposition.
Proposition 3.13. If a shift of finite type has finitely many maximal subsystems and no outcast, then it is isolated.
Proof. Consider a shift X as in the statement of the proposition. Any shift Z close enough to X for the Hausdorff distance is a subsystem of X and thus, included in a maximal subsystem or equal to X. All subsystems different from X are at distance larger than the minimum of
$ \delta _H(Z',X)$
, where
$Z'$
is maximal (this comes from Lemma 3.2) that is positive. Hence, X is isolated.
Remark 3.14. The hypotheses in Proposition 3.13 are satisfied by shifts of finite type that have finitely many subsystems. Proposition 3.9 is thus a consequence of Proposition 3.13.
We also use the following notation.
Notation 3.15. Let X be a shift. We denote by
$\mathcal {M}(X)$
the set of maximal subsystems of X, and by
$\mathcal {S}(X)$
the set of its strict subsystems.
Lemma 3.16. Let
$Z_1,Z_2$
be two different maximal subsystems of a shift X. We have
${Z_1\cup Z_2=X}$
.
Proof. Suppose it is not the case. Then, since
$Z_1$
and
$Z_2$
are different,
$Z_1$
is strictly included in
$Z_1\cup Z_2$
that is also different from X by hypothesis. This implies that
$Z_1$
is not a maximal subsystem of X.
Proposition 3.17. If a shift of finite type has infinitely many maximal subsystems, then it is not isolated.
Proof. Let X be a shift. Let
$(Z_n)_{n\ge 0}$
be a sequence of maximal subsystems, set
${K := \bigcap _n Z_n}$
and, for all n, set
$$ \begin{align*}K_n := \bigcup_{k=0}^n \overline{(X \backslash Z_k )}.\end{align*} $$
It is straightforward that K is a shift. This is also the case for
$K_n$
for all n. Indeed, for all k,
$X \backslash Z_k$
is invariant by the shift because
$Z_k$
is. As a consequence of Lemma 3.4,
$\overline {(X \backslash Z_k )}$
is a shift, thus
$K_n$
is a shift. Furthermore,
$(K_n)$
is a non-decreasing sequence whose union contains
$X \backslash K$
. Indeed, this union contains the union of the sets
$X \backslash Z_k$
, which is equal to
$X \backslash K$
. Therefore, the sets
$K_n$
, together with K, cover X. By this, for all n, there exists m such that for all
$l \ge m$
, the Hausdorff distance between
$K \bigcup K_l$
and X is smaller than
$2^{-n}$
(this comes from Lemma 3.3). We only have left to prove that
$(K_n)$
is not ultimately constant. By Lemma 3.16, for all
$n \neq m$
,
$Z_n \bigcup Z_m = X$
. This means that
$Z_m \supset X \backslash Z_n$
and thus
$Z_m \supset \overline {X \backslash Z_n}$
. This implies that for all n,
$Z_{n+1}$
contains
$K_n$
and thus
$K \bigcup K_n$
. If
$(K_n)$
was ultimately constant, this would contradict the fact that
$Z_{n+1}$
is maximal and thus not equal to X.
The following is straightforward.
Lemma 3.18. Consider Z an outcast of a shift X. Every
$Z' \in \mathcal {S}(X)$
containing Z is also an outcast.
Lemma 3.19. Consider Z an outcast of a shift X. For every
$x \in X \backslash Z$
and every
$\epsilon>0$
, there exists an outcast
$Z'$
of X such that
$\delta (x,Z') < \epsilon $
and
$Z \subset Z'$
.
Proof. Fix
$x \in X \backslash Z$
. Assume that there exists
$\epsilon> 0$
such that for every
$Z' \in \mathcal {S}(X)$
with
$Z \subset Z'$
,
$\delta (x,Z') \ge \epsilon $
. This implies that the distance between x and the set
$$ \begin{align*} \overline{\bigcup_{\underset{Z" \supset Z}{Z" \in \mathcal{S}(X)}} Z"}\end{align*} $$
is at least
$\epsilon $
. As a consequence, this set is different from X and this means that it is maximal, which is not possible. This implies that there exists
$Z' \in \mathcal {S}(X)$
such that
$Z \subset Z'$
and
$\delta (x,Z') < \epsilon $
. Then, by Lemma 3.18,
$Z'$
is also an outcast of X.
Proposition 3.20. If Z is an outcast of a shift X, then there exists a strictly increasing sequence
$(Z_n)_{n\in \mathbb {N}}$
of shifts such that
$Z_0 = Z$
and
$\overline {\bigcup _{n\ge 0}Z_n}=X$
.
Proof. Set
$Z_0=Z$
and suppose that
$Z_0, \ldots , Z_{n-1}$
have already been constructed for
$n \ge 1$
and
$\delta _H(Z_{n-1},X) < 2^{-n-1}$
. There exists a finite set
$S_n \subset X$
such that every point of X is at a distance strictly less than
$2^{-n-1}$
to a point in
$S_n$
. Using Lemma 3.19 multiple times, we obtain an outcast
$Z_n$
of X containing
$Z_{n-1}$
such that for all
$x \in S_n$
,
$\delta (x,Z_n) < 2^{-n-1}$
. As a consequence, the Hausdorff distance between X and
$Z_n$
is less than
$2^{-n}$
. Since
$Z_n$
is an outcast, it is different from X. By construction, the sequence
$(Z_n)_n$
is non-decreasing and
$\overline {\bigcup _{n\ge 0}Z_n}=X$
. Since for every n,
$Z_n$
is different from X, it is possible to extract from
$(Z_n)$
another sequence
$(Z^{\prime }_n)_n$
such that
$Z^{\prime }_0 = Z$
which is strictly increasing and such that
$\overline {\bigcup _{n\ge 0}Z^{\prime }_n}=X$
.
A straightforward consequence of this is the following proposition.
Proposition 3.21. If a shift has an outcast, then it is not isolated.
3.2.3 Characterization of isolated shifts
The results in the previous section suggest the following definition.
Definition 3.22. We say that a shift satisfies the condition
$(\star )$
when it has finitely many maximal subsystems and no outcasts.
Theorem A is a reformulation of the following theorem.
Theorem 3.23. A shift is isolated if and only if it satisfies the condition
$(\star )$
and is of finite type.
From this, we can recover the characterization of isolated shifts in
$\mathcal {S}^1$
. First, we introduce some notation and definitions.
Notation 3.24. For a one-dimensional shift X and
$n\in \mathbb {N}$
, we denote by
$G_{X,n}$
the directed graph with vertex set 
and where there is an edge from
$w_0 \cdots w_{n-1}$
to
$w_1 \cdots w_{n}$
, whenever 
.
Definition 3.25. A directed graph has the no-middle-cycle property if it contains no middle cycle, meaning a cycle c that has both an incoming edge (that connects a vertex not in c to a vertex in c) and an outgoing edge (that connects a vertex in c to a vertex not in c).
Remark 3.26. Observe that if
$G_{X,n}$
has the no-middle-cycle property, then for all
$m\ge n$
,
$G_{X,m}$
has the no-middle-cycle property as well.
Definition 3.27. A one-dimensional shift X is said to have the no-middle-cycle property when there exists an integer n for which
$G_{X,n}$
has the no-middle-cycle property.
For any finite directed graph G, we denote by
$X_G$
the one-dimensional shift whose alphabet is the vertex set of G and is defined by forbidden patterns
$ab$
, where there is no edge in G from a to b. Following R. Pavlov and S. Schmieding, we call barbell a finite directed graph composed of exactly two cycles and a directed path which departs from a vertex of one cycle and ends at a vertex of the other one.
Lemma 3.28. For any finite directed graph G,
$X_G$
is isolated in
$\mathcal {S}^1$
if and only if G has the no-middle-cycle property. In this case, it has finitely many subsystems.
Proof.
$(\Leftarrow )$
If G satisfies the no-middle-cycle property, then every configuration is in some
$X_H$
, where H is a cycle or a barbell in G, and every subsystem is a finite union of such shifts. Thus,
$X_G$
has finitely many subsystems. Since it is also of finite type, it is isolated in
$\mathcal {S}_1$
.
$(\Rightarrow )$
Let us assume that G does not satisfy the no-middle-cycle property. Denote by
$X_n$
the subsystem of
$X_G$
obtained by forbidding a configuration that contains the concatenation of n times the same middle cycle. The shifts
$X_n$
,
$n \ge 0$
, are all distinct and converge towards
$X_G$
, which is thus not isolated.
Corollary 3.29. (R. Pavlov, S. Schmieding)
A one-dimensional shift is isolated in
$\mathcal {S}^1$
if and only if it has the no-middle-cycle property.
Proof. Consider a one-dimensional shift X and for every integer n, denote by
$X_n$
the shift
$X_{G_{X,n}}$
and we apply Lemma 3.28.
$(\Rightarrow )$
If X does not satisfy the no-middle-cycle property, then since each
$X_n$
is not isolated, X is also not isolated.
$(\Leftarrow )$
If X has the no-middle-cycle property, then one of the shifts
$X_n$
has this property as well, and thus
$X_n$
has finitely many subsystems (Lemma 3.28). Since
$X\subset X_n$
, we can apply Lemma 3.10 and conclude that X is isolated.
3.3 Finitely many subsystems are not necessary
If a shift has finitely many subsystems, then it satisfies the
$(\star )$
property. One could wonder if the converse is true. Although it is the case for
$d=1$
(Lemma 3.28), we prove here that it is false in the case when
$d \ge 2$
.
We provide here an example of shift of finite type isolated in
$\mathcal {S}^2$
that has infinitely many subsystems. This example can be generalized straightforwardly to all the spaces
$\mathcal {S}^d$
,
$d \ge 2$
. A formal proof of this statement would be quite involved due to the elements used in its construction. Since it is not essential to the purpose of the present paper, we only present here elements of the construction and the main arguments. We use the terminology introduced in §2.2.
We construct a shift of finite type X that has a unique maximal subsystem, infinitely many subsystems and such that all of its strict subsystems are included in the maximal subsystem. This shift X is then isolated. We construct this shift by adding several layers, one by one, to the shift
$X_R^{+}$
. These layers are as follows.
-
(1) We refer to the first of these layers as the colour layer. The elements of its alphabet are red and blue. For all cells, the colour is constant over the union of its border and its cytoplasm. If a cell has a border, then this colour is blue.
-
(2) The second layer has alphabet
$\{0,1,2,\square \}$
and is described as follows: for each cell not included in a cell whose cytoplasm or border is coloured in blue (for simplicity, we call this a maximal cell), the positions in its border which have a neighbour in a free column or a free row of this cell are superimposed with a symbol in
$\{0,1,2\}$
, and every other position is superimposed with
$\square $
. We add an accessory layer that makes all the sequences of symbols written on an edge of the border equal (read from left to right for the vertical edges and from top to bottom for horizontal ones) and makes this common word on letters
$0,1$
only or on
$2$
only. An accessory layer is added such that for any maximal cell of order n whose border reads w, the border of any adjacent order n maximal cell reads
$r_n(w)$
, where
$r_n$
is some fixed cyclic permutation (for a more precise description of this, see [Reference Gangloff10]). The set of possible words w has cardinal
$p_n := 2^{2^n}+1$
and we can associate this set with
$\mathbb {Z}/p_n\mathbb {Z}$
in such a way that
$r_n(w) = r_n(w)+1$
for all w. -
(3) The third layer is on alphabet
$\{0,1,\square \}$
. A position is superimposed with a symbol in
$\{0,1\}$
if and only if it is in the border of a cell strictly contained in a maximal cell. This symbol is constant over the border. Inside an order n maximal cell, for any
$k\le n$
, it holds that the symbol on the border of any order
$k-1$
cell is 1 if and only if it is the north west cell within a cell that has order k and border symbol 1 or has order n. -
(4) The fourth layer is also on alphabet
$\{0,1,\square \}$
. A position is superimposed with a symbol in
$\{0,1\}$
if and only if it is in a free column of a maximal cell. This symbol is constant over a free column. On the extremities of a free column, the symbol in the current layer is equal to that on the border position adjacent to it in Layer 2, or
$0$
if this symbol is a
$2$
. -
(5) We add a last layer with alphabet
$\{0,1,\square \}$
and defined as follows: a position has a symbol in
$\{0,1\}$
if and only if it is in the border of a cell strictly contained in a maximal cell. Within a maximal cell, order n cells all have the same symbol on their borders. In positions where Layer 3 has a 1 and one of the neighbouring positions has either a 0 or a 1 on Layer 4, the same symbol (as in Layer 4) is placed in the current layer.
With the aid of accessory layers we make X a shift of finite type, using a similar strategy as that used to make
$X_R^+$
a shift of finite type—accessory layers ‘transmit’ information to force the desired patterns.
Consider the subsystem Z of X that consists in configurations in which the red colour does not appear. It is maximal because any configuration with the red colour has a dense orbit. To prove this, consider any pattern p in the language of the shift X and any configuration
$x \in X$
in which the red colour appears, and prove that p appears in x. There are two possibilities: the colour red appears in p or not. Let us consider these two cases separately.
-
• If the colour red appears in p. In this case, p can be completed into a pattern q over a supertile centred on a cell in which the rules of X are not broken. Within the set of patterns on this supertile, q is determined by the sequence
$w_0(q) , \ldots , w_k(q)$
, where k is the largest order of a cell in the supertile and
$w_i(q)$
is the word in Layer 2 on the top border of the rightmost topmost cell of order i in the supertile. This supertile is of order
$2k+1$
by definition and it is known that it appears periodically in x in both direction with period
$4^{2k+1}$
. Furthermore, because of the last accessory layer described in point 2 above, for two adjacent of these supertiles that support a maximal order k cell, denoting by
$q'$
and
$q"$
the patterns appearing in x on the left one and the right one, respectively, the sequence
$(w_0(q"), \ldots , w_k(q"))$
is the image of
$(w_0(q'), \ldots , w_k(q'))$
by the following function from
$\mathbb {Z}/p_0 \mathbb {Z} \times \cdots \times \mathbb {Z}/p_k \mathbb {Z}$
to itself: Because the numbers are all co-prime (Goldbach’s theorem on Fermat numbers) and co-prime with
$$ \begin{align*}(w_0 , \ldots , w_k) \mapsto (w_0 + 4^{2k+1} , \ldots , w_k +1).\end{align*} $$
$2$
, this is a cyclic permutation. Because one can find in x arbitrarily long sequences of adjacent supertiles as above, q appears in x and so does p.
-
• If the colour red does not appear in p. Then, p can be completed into a pattern q over a cell in which the rules of X are not broken. Among all the valid patterns over the same cell, q is determined by the word on the top part of the border in Layer 2. Within the configuration x, this word takes all the possible values, because of the last accessory layer described in point 2 above. Therefore, q appears in x and so does p.
We just have proved that all the configurations in which the red colour appear have a dense orbit in X. For this reason, every subsystem of X is included in Z which is the only maximal subsystem. As a consequence of Theorem 3.23, X is isolated.
Furthermore, it is straightforward that Z has infinitely many subsystems, because the set of configurations that hold a certain fixed sequence of Layer 3 symbols
$\{0,1\}$
on cells of order n is a shift and that for two different sequences, these two shifts are disjoint. Moreover, for every sequence this shift is not empty. Thus, X has infinitely many subsystems.
3.4 Properties of shifts in relation with maximal subsystems
In this section, we address some natural questions about maximal subsystems and the
$(\star )$
property.
Definition 3.30. For all shift X, we refer to the cardinality of
$\mathcal {M}(X)$
as the maximality type of X.
We will see in this section that every element of
$\mathbb {N} \cup \{\infty \}$
is the maximality type of at least one shift (Proposition 3.34).
3.4.1 The maximality type is invariant under conjugacy
Observe that having a conjugacy between two sets amounts, in particular, to having a bijection of subsystems that preserves the inclusion relation. Thus, if X and Y are conjugates, the maximal subsystems of X (if any) are sent to the maximal subsystems of Y, and vice versa. This observation yields the following proposition.
Proposition 3.31. All conjugates of a shift have the same maximality type.
3.4.2 Realization of all numbers of maximal subsystems
Lemma 3.32. Let X be a shift that is the union of shifts
$Z_n = K \sqcup M_n $
,
$n\ge 0$
, where K is a shift and for all
$n\ge 0$
,
$M_n$
is a minimal shift such that:
-
•
$(M_m = M_n) \Rightarrow (m=n)$
; -
•
$Z_n \rightarrow K$
.
Then, the maximal subsystems of X are the shifts
$\bigcup _{n \neq m} Z_n$
,
$m \ge 0$
.
Proof. Fix some integer m. The set
$L_m := (\bigcup _{n \neq m} Z_n )$
is a shift since it is shift-invariant and closed because
$Z_n \rightarrow K = \bigcap _m Z_m$
. Observe that
$L_m$
is disjoint from
$M_m$
and, as a consequence,
$L_m = X \backslash M_m$
, which makes this shift a maximal subsystem of X (since
$M_n$
is minimal). Every proper subsystem of X is contained in some
$L_m$
, which means that the maximal subsystems of X are exactly the sets
$L_m$
,
$m\ge 0$
.
Example 3.33. Consider the following alphabet.
Define the two-dimensional configuration
$x_+$
made only with the cross symbol and for all
$n\in \mathbb {N}$
, define the two-dimensional configurations
$x_n$
as follows.
-
(1) The cross symbol
appears in positions in
$ \mathbb {N}_{n} :=(2n+1)\mathbb {Z}^2$
. -
(2) The vertical symbol
appears in positions in
$$ \begin{align*}\mathbb{G}^v_{n}:= \{((2n+1)k,l) : k,l \in \mathbb{Z} \}\backslash \mathbb{N}_{n}.\end{align*} $$
-
(3) The horizontal symbol
appears in positions in
$$ \begin{align*}\mathbb{G}^h_{n}:= \{(k,(2n+1)l) : k,l \in \mathbb{Z} \}\backslash \mathbb{N}_{n}.\end{align*} $$
-
(4) On each of the translates of
$\mathbb {U}_{2(n-1)}^2$
that do not intersect
$\mathbb {G}^v_{n}$
,
$\mathbb {G}^h_{n,}$
nor
$\mathbb {N}_{n,}$
, the pattern is of the following form.
appears in positions in 
appears in positions in 
appears in positions in 
Figure 2 illustrates this definition. Define the two-dimensional shift X as the closure of the following set:
$$ \begin{align*}\mathcal{O}(x_+) \cup \bigg(\bigcup_n \mathcal{O}(x_n)\bigg).\end{align*} $$
Observe that in these configurations, the occurrence of a corner symbol 
in position
$(i,j)$
forces that at position
$(i-1,j+1)$
, either the same corner symbol or a cross symbol occurs. The same holds for the rotations 
, 
and 
of 
. Using this, it is possible to define 
, where the set
$\mathcal {P}$
consists of the following
$2\times 2$
patterns:
Different configurations of X.
and their rotations. We leave it to the reader to check that
$X=X_{\mathcal {F}}$
, which means that the shift X is of finite type.
Denote by
$K :=X \backslash \bigcup _n \mathcal {O}(x_n)$
. Then, X satisfies the conditions of Lemma 3.32, where
$Z_n := \mathcal {O}(x_n) \cup K$
for all n.
Proposition 3.34. For all
$n \in \mathbb {N} \cup \{+\infty \}$
, and for all
$d > 1$
, there is a d-dimensional shift of finite type that has exactly n maximal subsystems.
Proof. The shift presented in Example 3.33 has infinitely many maximal subsystems, because it satisfies the conditions of Lemma 3.32. For any integer n, it is sufficient to see that the disjoint union of n shifts, each one consisting in a single periodic orbit, is of finite type and has exactly n maximal subsystems.
3.4.3 Maximality and minimality
It is natural to wonder whether there is a relation between maximal and minimal subsystems. We present two results in this direction.
Proposition 3.35. If a shift X has a subsystem Z such that
$\overline {X \backslash Z}$
is a minimal shift, then Z is a maximal subsystem of X.
Proof. Indeed, consider any point
$x \in X \backslash Z$
. Since
$\overline {\mathcal {O}(x)} = \overline {X \backslash Z}$
, then
$Z \bigcup \overline {\mathcal {O}(x)} = X$
. Therefore, all the shifts that contain Z are equal to Z or X.
Notation 3.36. For a shift X of maximality type
$1$
, we denote by
$M(X)$
the sole maximal subsystem of X and by
$R(X)$
the elements of X that are not in
$M(X)$
.
Proposition 3.37. Provided a shift X and Z a subsystem of X, if every strict subsystem of Z is included in
$\overline {X \backslash Z}$
, then
$\overline {X \backslash Z}$
is either a maximal subsystem of X or equal to X.
This is the case if Z is a minimal subsystem of X for instance.
Proof. If Z is equal to the closure of the union of the elements of
$\mathcal {S}(Z)$
, then
$\overline {X \backslash Z}$
must contain Z and is equal to X. Otherwise, Z is necessarily of maximality type
$1$
. The closure of
$X\backslash Z$
contains the maximal subsystem of Z by hypothesis. So in any case,
${X \backslash (\overline {X \backslash Z})\subset R(Z)}$
. If the closure of
$X \backslash Z$
is not X, then the orbit of any element outside of it is dense in Z. This implies that
$\overline {X \backslash Z}$
is a maximal subsystem of X.
Remark 3.38. In particular, if X has maximality type 0, then for every strict subsystem Z, if
$\overline {X \backslash Z} \neq X$
, there exists another subsystem
$Z'$
such that
$Z' \not \subset \overline {X \backslash Z}$
.
3.4.4 Maximal subsystems of a shift of finite type are of finite type.
Proposition 3.39. Consider any set of patterns
$\mathcal {F}$
such that
$X:= X_{\mathcal {F}} \neq \emptyset $
. If Z is a maximal subsystem of X, then there exists a pattern
$p \notin \mathcal {F}$
such that
$Z = X_{\mathcal {F} \cup \{p\}}$
.
Proof. Consider the set
$\mathcal {P}$
of patterns on the alphabet of X that are not in the language of Z. This set must contain
$\mathcal {F}$
. Since Z is different from X, it cannot be equal to
$\mathcal {F}$
. Let us proceed ad absurdum and suppose that for all
$p \in \mathcal {P} \backslash \mathcal {F}$
,
$X_{\mathcal {F} \cup \{p\}} = X$
. Then, for all finite subsets
$\mathcal {Q} \subset \mathcal {P}$
that contain
$\mathcal {F}$
,
$X_{\mathcal {Q}} = X_{\mathcal {F}}$
. Set
$(p_n)_{n \in \mathbb {N}}$
an enumeration of the elements of
$\mathcal {P}$
,
$\mathcal {P}_n :=\{p_1,\ldots ,p_n\}\cup \mathcal {F}$
and
$X_n :=X_{\mathcal {P}_n}$
. Therefore, since
$X_{n}$
converges to Z when
${n \rightarrow \infty} $
, we have
$Z = X$
, which is impossible. Thus, there exists
$p \in \mathcal {P} \backslash \mathcal {F}$
such that
${X_{\mathcal {F} \cup \{p\}} \neq X}$
. Since
$Z \subset X_{\mathcal {F} \cup \{p\}}$
and Z is maximal, we have
$Z = X_{\mathcal {F} \cup \{p\}}$
.
Corollary 3.40. If X is a shift of finite type, each of its maximal subsystems is also of finite type.
Corollary 3.41. For every shift X,
$\mathcal {M}(X)$
is countable.
3.4.5 Additivity of types relative to disjoint union
The following is straightforward, but we include a proof to illustrate how maximal subsystems of a disjoint union arise.
Proposition 3.42. Let
$X,Z$
be non-minimal shifts with empty intersection and let
$m,n$
be the maximality type of
$X,Z$
, respectively. Then, the maximality type of
$X \cup Z$
is
$n+m$
. If X is minimal and Z is not minimal,
$X \cup Z$
is of type
$n+1$
. If both X and Z are minimal,
$X \cup Z$
has type
$2$
.
Proof. Let us consider the first case. It is sufficient to see that given two disjoint shifts X and Z, the subsystems of
$X \cup Z$
of the following form are maximal: (i)
$X\cup M$
, where M is a maximal subsystem of Z if Z is not minimal and equal to Z otherwise; (ii)
$N\cup Z$
, where N is a maximal subsystem of X if X is not minimal and equal to X otherwise. Any other strict subsystem of
$X \cup Z$
is of the form
$N\cup M$
, where N (respectively M) is a subsystem of X (respectively Z) or empty. Thus, such a subsystem is included in a subsystem as described above. Hence, they are the only maximal subsystems.
4 Maximality decomposition
We prove in this section that every non-minimal shift can be written as the union of two parts: a union of shifts that are transitive shifts of maximality type
$1$
or minimal; a set that is empty or a non-minimal shift having maximality type
$0$
(§4.1). We then prove that this decomposition is unique in a certain sense (§4.2). This will be useful in §6.2.
4.1 Definition and properties
Lemma 4.1. Consider a shift X and Z a maximal subsystem of X. If
$Z \cap \overline {X \backslash Z} = \emptyset $
, then
$\overline {X \backslash Z}$
is minimal. Otherwise,
$\overline {X \backslash Z}$
is transitive of maximality type
$1$
.
Proof. Since Z is maximal, then for all
$x \in X \backslash Z$
,
$\overline {\mathcal {O}(x)}$
contains
$X \backslash Z$
and since it is closed, it also contains
$\overline {X \backslash Z}$
. In the first case,
$X \backslash Z$
must be closed, and the argument above implies that it is minimal. In the second case,
$Z \cap \overline {X \backslash Z}$
is the unique maximal subsystem of
$\overline {X \backslash Z}$
and
$\overline {X \backslash Z}$
is transitive.
Notation 4.2. For every shift X, we set
$\mathcal {T}(X) := \{ \overline {X \backslash Z} : Z \in \mathcal {M}(X)\}$
,
$\mathcal {E}(X):= \overline {\bigcup _{T \in \mathcal {T}(X)} T} $
and
$\mathcal {K}(X):= \overline {X \backslash \mathcal {E}(X)}$
.
Remark 4.3. In the particular case where X is minimal,
$\mathcal {T}(X) = \mathcal {E}(X) = \emptyset $
and
${\mathcal {K}(X) = X}$
.
Lemma 4.4. For every shift X,
$X = \mathcal {K}(X) \cup \mathcal {E}(X)$
. We will refer to this equality as the maximality decomposition of X. Furthermore,
$\mathcal {K}(X)$
is a subset of
$\bigcap _{Z \in \mathcal {M}(X)} Z$
.
Proof. The first assertion is a direct consequence of the definition of
$\mathcal {K}(X)$
. The second one comes from the fact that for all maximal subsystems Z of X,
$X \backslash (\overline {X \backslash Z})$
is a subset of Z.
Lemma 4.5. For every shift X and
$Z \in \mathcal {M}(X)$
, we have
$$ \begin{align*} \overline{X \backslash Z} \subset \bigcap_{\underset{Z' \neq Z}{Z' \in \mathcal{M}(X)}} Z'.\\[-19pt]\end{align*} $$
Proof. This is a direct consequence of Lemma 3.16.
The following lemma is straightforward.
Lemma 4.6. Consider a shift X and K another shift such that
$X = K \cup \mathcal {E}(X)$
. Then,
$\mathcal {K}(X) \subset K$
.
Lemma 4.7. Whenever X is not minimal, if
$\mathcal {K}(X)$
is not empty, it is a shift that has maximality type
$0$
and is not minimal.
Proof. Assume that
$\mathcal {K}(X)$
is not empty. Let us assume ad absurdum that
$\mathcal {K}(X)$
has at least one maximal subsystem. For all
$Z \in \mathcal {M}(\mathcal {K}(X))$
,
$\mathcal {K}(X) \backslash Z$
is included in
$\mathcal {E}(X)$
. Otherwise,
$Z \cup \mathcal {E}(X)$
would be a maximal subsystem of X and this is impossible because
$\overline {X \backslash (Z \cup \mathcal {E}(X))}$
is not contained in
$\mathcal {E}(X)$
. Since
$\mathcal {E}(X)$
is closed, we have
$\overline {\mathcal {K}(X)} \backslash Z \subset \mathcal {E}(X)$
. This implies that
$\mathcal {E}(\mathcal {K}(X)) \subset \mathcal {E}(X)$
. Therefore, since
$X = \mathcal {K}(X) \cup \mathcal {E}(X) = \mathcal {K}^2(X) \cup \mathcal {E}(\mathcal {K}(X)) \cup \mathcal {E}(X)$
,
$X = \mathcal {K}^2(X)\cup \mathcal {E}(X)$
. By Lemma 4.6,
$\mathcal {K}^2(X)$
contains
$\mathcal {K}(X)$
. However, this is impossible because
$\mathcal {K}^2(X)$
is contained in every maximal subsystem of
$\mathcal {K}(X)$
. Assume that
$\mathcal {K}(X)$
is minimal. By Proposition 3.35,
$\mathcal {E}(X)$
is a maximal subsystem of X. By definition,
$\mathcal {K}(X)$
is thus included in
$\mathcal {E}(X)$
. This implies that
$\mathcal {E}(X) = X$
and that
$\mathcal {K}(X)$
is empty.
Lemma 4.8. For every shift X and
$T \in \mathcal {T}(X)$
, T is minimal or transitive with maximality type
$1$
.
Proof. This is a direct consequence of definitions and Lemma 4.1.
Lemma 4.9. Consider a shift X. For all
$T,T' \in \mathcal {T}(X)$
, if
$T \subset T'$
, then
$T=T'$
. Furthermore, for all
$T \in \mathcal {T}(X)$
,
$T \not \subset \mathcal {K}(X)$
. Furthermore, if
$\mathcal {T}(X)$
is infinite, and
$(T_k)_{k \ge 1}$
is an enumeration of its elements (recall that
$\mathcal {M}(X)$
, and thus
$\mathcal {T}(X)$
, is countable [Corollary 3.41]), then for all
$m \ge 1$
, we have
$$ \begin{align*}T_m \not \subset \bigcap_k \overline{\bigcup_{l \ge k} T_{l}}.\end{align*} $$
Proof.
-
(1) Consider T and
$T'$
two elements of
$\mathcal {T}(X)$
such that
$T \subset T'$
. Denote by
$Z,Z'$
maximal subsystems of X such that
$T= \overline {X\backslash Z}$
and
$T' = \overline {X \backslash Z'}$
. Assume ad absurdum that
$T \neq T'$
. This implies that
$Z \neq Z'$
. We know by Lemma 4.5 that
$T'$
is contained in Z, and thus T is contained in Z, which is impossible. -
(2) Assume that for some
$T \in \mathcal {T}(X)$
,
$T \subset \mathcal {K}(X)$
. Consider a Z maximal subsystem of X such that
$T = \overline {X\backslash Z}$
. We know (Lemma 4.4) that
$\mathcal {K}(X)$
is contained in all the maximal subsystems of X. Therefore, T is contained in Z. Again, this is impossible. -
(3) The last point is proved in a similar way, as the set
$\bigcap _k \overline {\bigcup _{l \ge k} T_{l}}$
is contained in every maximal subsystem of X.
4.2 Uniqueness
Theorem 4.10. Consider a shift X, K a set and
$\mathcal {T}$
a set of shifts such that: (i) every element of
$\mathcal {T}$
is minimal or transitive with maximality type
$1$
; (ii) K is empty or a shift of maximality type 0 and not minimal; (iii)
$X = K \cup \overline {\bigcup _{T\in \mathcal {T}} T}$
; (iv) if
$T \subset T'$
for
${T,T' \in \mathcal {T}}$
, then
$T=T'$
; (v) for all
$T \in \mathcal {T}$
,
$T \not \subset K$
. (vi) if
$|\mathcal {T}|= \infty $
, denoting by
$T_1,T_2, \ldots $
the elements of
$\mathcal {T}$
, for all m, we have
$$ \begin{align*}T_m \not \subset \bigcap_k \overline{\bigcup_{l \ge k} T_{l}}.\end{align*} $$
Then, the maximal subsystems of X are subsystems of the form
$$ \begin{align*}K \bigcup \overline{\bigg(\bigcup_{\underset{T' \in \mathcal{T}}{T' \neq T}} T'\bigg)} \bigcup M(T),\end{align*} $$
where
$T \in \mathcal {T}$
. Furthermore,
$\mathcal {T}(X) = \mathcal {T}$
and
$\mathcal {K}(X) \subset K$
.
For a minimal shift T, we use the convention
$M(T) = \emptyset $
.
Proof. For every
$T \in \mathcal {T}$
, denote by
$S(T)$
the set
$$ \begin{align*}K \bigcup \overline{\bigg(\bigcup_{\underset{T' \in \mathcal{T}}{T' \neq T}} T'\bigg)}\bigcup M(T).\end{align*} $$
The set
$X \backslash S(T)$
contains
$R(T)$
because of properties (iv), (v) and (vi). Because of the property (iii),
$X \backslash S(T)$
is contained in T. Since it does not contain any element of
$M(T)$
,
$X \backslash S(T) = R(T)$
. This implies that
$S(T)$
is maximal. Consider some strict subsystem Z of X. If there is some
$T \in \mathcal {T}$
that is not contained in Z, then
$Z \subset S(T)$
. If Z contains every
$T \in \mathcal {T}$
, then
$K \neq \emptyset $
. Thus,
$Z \cap K$
is a strict subsystem of K or is empty, and because of property (ii), Z is not maximal. We have proved that the maximal subsystems of X are the shifts
$S(T)$
,
$T \in \mathcal {T}$
. Along the way, we have proved that for all
$T \in \mathcal {T}$
,
${X \backslash S(T) = R(T)}$
and thus
$\overline {X \backslash S(T)} = T$
. This implies that
$\mathcal {T}(X) = \mathcal {T}$
. From Lemma 4.6, we have that
$\mathcal {K}(X) \subset K$
.
5 Isolated points in the space of transitive shifts
M. Hochman, and R. Pavlov and S. Schmieding have studied the effects of transitivity on genericity. It is natural to wonder how our characterization in §3 is affected by transitivity, and more generally by transitivity-like properties. For this, we will consider how these kind of properties affect the structure of the set of subsystems.
We denote by
$\mathcal {T}^d$
the space of transitive d-dimensional shifts.
5.1 The number of maximal subsystems of a transitive shift
Lemma 5.1. A shift X is transitive if and only if
$$ \begin{align*}X \neq \bigcup_{Z \in \mathcal{S}(X)} Z.\\[-19pt]\end{align*} $$
Proof.
$(\Rightarrow )$
If X is transitive, then there exists
$x \in X$
such that
$\overline {\mathcal {O}(x)} = X$
. As a consequence, there is no
$Z \in \mathcal {S}(X)$
such that
$x \in Z$
, thus, x does not belong to the union of the elements of
$\mathcal {S}(X)$
.
$(\Leftarrow )$
Reciprocally, if the union of the elements of
$\mathcal {S}(X)$
is different from X, then consider x in X outside of this union. The set
$\overline {\mathcal {O}(x)}$
cannot be an element of
$\mathcal {S}(X)$
, thus, it must be equal to X. This means that X is transitive.
Theorem 5.2. The maximality type of a transitive shift is either
$0$
or
$1$
.
Proof. Let X be a transitive shift. If X is minimal, then its maximality type is 0. From now on, we assume that X is not minimal. Consider the shift
$Z \subset X$
that is equal to the closure of the union of all the strict subsystems of X. If Z is different from X, then Z is the only maximal subsystem of X, for every other subsystem is included in it. When Z is equal to X, no strict subsystem
$Z'$
can be maximal. Indeed, assume there is such a
$Z'$
. Since there exists some
$x \in X$
whose orbit is dense in X, for each
$Z"$
strict subsystem of X,
$Z' \cup Z"$
is a strict subsystem and thus must be contained in
$Z'$
, which implies that
$Z" \subset Z'$
. This means that Z is not equal to X, which is a contradiction.
5.2 Characterization of isolated points in
$\mathcal {T}^d$
In this section, we provide a characterization of isolated points in the space of transitive shifts. It is straightforward that, since
$\mathcal {T}^d \subset \mathcal {S}^d$
, if a transitive shift is isolated in
$\mathcal {S}^d$
, it is also isolated in
$\mathcal {T}^d$
. We will see in §5.2.3 that there are isolated shifts in
$\mathcal {T}^d$
that are not isolated in
$\mathcal {S}^d$
.
We analyse separately shifts that have maximality type 0 (§5.2.2) and those that have maximality type 1 (§5.2.1). Both cases combined yield the claims in Theorem B.
5.2.1 Maximality type 1
Lemma 5.3. If
$X\in \mathcal {T}^d$
has maximality type 1, then every strict subsystem of X is contained in its maximal subsystem.
Proof. Denote by Z the maximal subsystem. It is sufficient to prove that for all
$x \in X \backslash Z$
,
$\overline {\mathcal {O}(x)} = X$
. Let
$x \in X \backslash Z$
. We have then
$Z \cup \overline {\mathcal {O}(x)} = X$
; otherwise Z would not be maximal. Since X is transitive, there exists
$z \in X$
such that
$\overline {\mathcal {O}(z)} = X$
and this implies that
$z \in X \backslash Z$
. As a consequence,
$z \in \overline {\mathcal {O}(x)}$
and
$\overline {\mathcal {O}(x)} = X$
.
Lemma 5.3 and Theorem 3.23 have as a consequence the following corollary.
Corollary 5.4. A transitive shift of finite type X that has maximality type 1 is isolated in
$\mathcal {S}^d$
and in
$\mathcal {T}^d$
.
Remark 5.5. Observe that maximality type 0 does not imply transitivity, because a union of full shifts on disjoint alphabets
$\mathcal {A}_1,\mathcal {A}_2$
such that
$|\mathcal {A}_1|> 1$
or
$|\mathcal {A}_2|> 1$
is of maximality type 0, but it is not transitive. However, is there a shift of maximality type 0 that is not a union of transitive shifts? Similarly, a maximality type
$1$
shift is not necessarily transitive, because the disjoint union of a maximality type
$0$
shift and a maximality type
$1$
shift has maximality type
$1$
, and cannot be transitive.
Example 5.6. We provide an example of a transitive shift with maximality type
$1$
. Let
$\textbf {u}=(\textbf {u}_1,\textbf {u}_2)\in \mathbb {Z}^2$
and let
$\overline {\mathcal {O}(x)}$
be a bi-dimensional shift, where x is the configuration such that
$x_{\textbf {u}}$
is equal to:
$\uparrow $
if
$\textbf {u}_2> 0$
;
$\downarrow $
if
$\textbf {u}_2 < 0$
;
$\rightarrow $
if
$\textbf {u}_2 = 0$
and
$\textbf {u}_1> 0$
;
$\leftarrow $
if
$\textbf {u}_2 = 0$
and
$\textbf {u}_1 < 0$
; otherwise, it is equal to
$\square $
. This shift is of finite type, transitive and has a unique maximal subsystem, which is the set of configurations in which the symbol
$\square $
does not appear.
Proposition 5.7. A transitive shift X of maximality type 1 that is not of finite type is isolated in
$\mathcal {T}^d$
if and only if there exists a shift of finite type Z such that
$X \subset Z$
and
$Z \backslash X$
is not dense in Z.
Proof.
$(\Leftarrow )$
In this case, we have that
$\overline {Z\setminus X}$
does not intersect
$R(X)$
; otherwise, we would have that
$ X \subset \overline {Z\setminus X}$
, since
$Z\setminus X$
is invariant under
$\sigma $
. Using the trivial inclusion
$Z \setminus X \subset \overline {Z\setminus X}$
and taking the union with
$X\subset \overline {Z\backslash X}$
, we get
$Z = X \cup (X\backslash Z) \subset \overline {Z\backslash X}$
. Since
$\overline {Z\backslash X} \subset Z$
, we get that
$\overline {Z\setminus X}=Z$
, which contradicts the hypothesis that
$Z\setminus X$
is not dense in Z. Let us assume ad absurdum that there is a sequence
$(x_n)_{n\ge 0}$
such that
${\overline {\mathcal {O}(x_n)} \rightarrow X}$
and for all n,
$\overline {\mathcal {O}(x_n)} \neq X$
. Since Z is of finite type, by application of Lemma 3.8, we can assume that for all n,
$\overline {\mathcal {O}(x_n)} \subset Z$
. Denote by
$X'$
the unique maximal subsystem of X. Since
$\overline {\mathcal {O}(x_n)} \neq X$
, we have that either
$X_n := \overline {\mathcal {O}(x_n)} \subset \overline {Z \backslash X} \cup X'$
or
$X_n$
strictly contains X. If there were infinitely many integers n such that
$X_n$
strictly contains X,
$\overline {Z\backslash X}$
would then have non-empty intersection with
$R(X)$
, which is not true. Therefore, we can assume that for all n,
$\overline {\mathcal {O}(x_n)} \subset \overline {Z \backslash X} \cup X'$
. Hence, by taking the limit,
$X \subset \overline {Z \backslash X} \cup X'$
, which is impossible.
$(\Rightarrow )$
Suppose now that for all Z shifts of finite type that contains X,
$Z \backslash X$
is dense in Z. Denote by
$(Z_n)_{n\ge 0}$
a non-increasing sequence of shifts of finite type that converges towards X. For all n, there exists a sequence of points
$(x_{m,n})_{m\ge 0}$
in
$Z_n \backslash X$
that converges to some point in
$R(X)$
. Observe that
$\mathcal {S}(Z_1)$
is compact, thus, we can assume without loss of generality that
$\overline {\mathcal {O}(x_{m,n})}$
converges when
$m \rightarrow +\infty $
. The limit, which we denote by
$\Lambda _n$
, must contain X and is contained in
$Z_n$
. We can assume without loss of generality, again because
$\mathcal {S}(Z_1)$
is compact, that
$(\Lambda _n)_n$
converges. Since
$X \subset \Lambda _n \subset Z_n$
for all n and
$Z_n \rightarrow X$
,
$\Lambda _n$
converges towards X. This implies that there is a sequence of points
$(z_n)_{n\ge 0}$
such that
$\overline {\mathcal {O}(z_n)} \rightarrow X$
. This means that X is not isolated in
$\mathcal {T}^d$
.
Example 5.8. An example of (non-finite type) transitive shift of maximality type
$1$
and not isolated in
$\mathcal {T}^d$
is the sunny-side-up, which has alphabet
$\{0,1\}$
and whose configurations are those that contain at most one symbol
$1$
. Indeed, it has a unique subsystem, which is thus maximal, whose only element is the constant configuration with value
$0$
. This shift is the limit of the orbit closures of configurations in which
$1$
symbols appear periodically in both directions with period n.
5.2.2 Maximality type 0
Lemma 5.9. Consider a minimal shift X and a sequence of shifts
$(X_n)_{n\ge 0}$
such that
${X_n \rightarrow X}$
. For every sequence of shifts
$(Z_n)_{n\ge 0}$
such that for all n,
$Z_n \subset X_n$
, we have that
${Z_n \rightarrow X}$
.
Proof. It is sufficient to see that the limit of any convergent subsequence of
$(Z_n)$
has to be a subsystem of X; therefore, it is equal to X.
Proposition 5.10. Let X be a transitive shift that has maximality type 0. Then, X is isolated in
$\mathcal {T}^d$
if and only if it is a minimal shift of finite type.
Proof. Consider a transitive shift X that has maximality type 0.
(1) If X is minimal.
-
(a) If X is not of finite type. Consider a set
$\mathcal {F}$
such that
$X = X_{\mathcal {F}}$
and a sequence of patterns
$(p_n)_{n \ge 0}$
such that
$\mathcal {F} = \{p_0, p_1 , \ldots \}$
. Then, set
$X_n = X_{\mathcal {F}_n}$
, where
${\mathcal {F}_n = \{p_0 , \ldots , p_n\}}$
. Then we have
$X_n \rightarrow X$
and for all n,
$X_{n+1} \subset X_n$
and
$X_n \neq X$
. We have then that for all n, there exists a configuration
$x_n \in X_n$
with
$x_n \notin X$
. Thus, for all n,
$\overline {\mathcal {O}(x_n)} \neq X$
and
$\overline {\mathcal {O}(x_n)} \rightarrow X$
, by an application of Lemma 5.9. We conclude that X is not isolated in
$\mathcal {T}^d$
. -
(b) If X is of finite type. In this case, since it has no strict subsystem, by Theorem 3.23, it is isolated in
$\mathcal {S}^d$
and thus in
$\mathcal {T}^d$
.
(2) If X is not minimal. Let
$x \in X$
such that
$\overline {\mathcal {O}(x)} = X$
. By hypothesis, the closure of the union of all elements of
$\mathcal {S}(X)$
is equal to X. Therefore, there exists a sequence of points
$(x_n)_{n\ge 0}$
such that for all n,
$\overline {\mathcal {O}(x_n)}$
is a strict subsystem of X and such that
$x_n \rightarrow x$
. We claim that
$\overline {\mathcal {O}(x_n)} \rightarrow X$
. Let us prove that for all
$\epsilon> 0$
, there exists some n such that the Hausdorff distance between
$\overline {\mathcal {O}(x_n)}$
and X is smaller than
$\epsilon $
. Since
$\mathcal {O}(x)$
is dense in X, there exists a finite subset S of
$\mathcal {O}(x)$
such that
$\delta _H(S,X) < \epsilon /2$
. Since
$x_n \rightarrow x$
, by continuity, there exists n and a subset
$S_n$
of
$\overline {\mathcal {O}(x_n)}$
such that
$\delta _H(S_n,S) < \epsilon /2$
. Consequently,
$\delta _H(\overline {\mathcal {O}(x_n)},X) < \epsilon $
.
Proposition 5.11. Let X be a transitive, infinite shift. If the set of its periodic points is dense, then X has maximality type 0.
Proof. In this case, there exists a strictly increasing sequence of shifts different from X that converges towards X. Therefore, these shifts are not included in any maximal subsystem. By Lemma 5.3, X cannot have maximality type 1. Since X is transitive, Theorem 5.2 implies that it has maximality type 0.
Example 5.12. By the means of Proposition 5.11, we have that every full shift has maximality type
$0$
and, thus, it is not isolated in
$\mathcal {T}^d$
.
5.2.3 Example of a non-finite type shift isolated in
$\mathcal {T}^d$
We provide an example of a transitive shift of maximality type 1 that is isolated in
$\mathcal {T}^2$
and is not of finite type, which implies that it is not isolated in
$\mathcal {S}^2$
. This example can be easily adapted to construct shifts isolated in
$\mathcal {T}^d$
,
$d>2$
, which are not of finite type.
Denote by
$\mathbb {N}^*$
the set of positive integers. We denote by x the configuration such that
$x_{(0,0)} = \square $
; for all
$k> 0$
(respectively
$k< 0$
),
$x_{(0,k)} = \uparrow $
(respectively
$\downarrow $
); for all
$k>0$
(respectively
$k < 0$
),
$x_{(k,0)} = \rightarrow $
(respectively
$\leftarrow $
); the restriction of x to any set
${( \pm \mathbb {N}^*) \times ( \pm \mathbb {N}^*)}$
is a pattern over an infinite supertile of the Robinson shift
$X_R$
.
The shift
$Z:= \overline {\mathcal {O}(x)} \bigcup X_R^{\infty }$
is a subsystem of
$X:= \overline {\mathcal {O}(x)} \bigcup X_R$
, which is of finite type. Furthermore, Z is clearly a transitive shift whose maximality type is
$1$
. Moreover,
$X \backslash Z$
is not dense in X, because no configuration in it contains the symbol
$\square $
. The shift Z is not of finite type because it is the limit of a decreasing sequence
$X_n$
of shifts of finite type, where
$X_n = \overline {\mathcal {O}(x)} \bigcup X_R^n$
. By Proposition 5.7, Z is a transitive shift that has maximality type
$1$
, and it is isolated and not of finite type.
5.3 Other dynamical properties
Denote by
$\mathcal {M}^d$
the space of minimal d-dimensional shifts.
Proposition 5.13. A minimal shift X is isolated in
$\mathcal {M}^d$
if and only if it has a neighbourhood in
$\mathcal {S}^d$
in which every shift contains X.
Proof.
$(\Leftarrow )$
Suppose that there is a sequence of shifts
$(X_n)_{n\ge 0}$
in
$\mathcal {S}^d$
that converges towards X and such that
$X_n$
does not contain X, for all n. This means that
$X_n$
contains another minimal shift
$Z_n \neq X$
. By Lemma 5.9,
$Z_n \rightarrow X$
and, therefore, X is not isolated in
$\mathcal {M}^d$
.
$(\Rightarrow )$
Reciprocally, if X is not isolated in
$\mathcal {M}^d$
, there is a sequence of different minimal shifts that converges to X, and since they are minimal, none of these shifts can contain X.
Recall that we denote by
$||.||_{\infty }$
the norm on
$\mathbb {Z}^d$
such that
$||\textbf {u}||_{\infty } = \max _{k \le d} |\textbf {u}_k|$
, for all
$\textbf {u} \in \mathbb {Z}^d$
. The Hausdorff distance between two finite subsets
$\mathbb {U}$
and
$\mathbb {V}$
of
$\mathbb {Z}^d$
is
$$ \begin{align*}\max \big( \max_{\textbf{u} \in \mathbb{U}} \min_{\textbf{v} \in \mathbb{V}} ||\textbf{u}-\textbf{v}||_{\infty} , \max_{\textbf{v} \in \mathbb{V}} \min_{\textbf{u} \in \mathbb{U}} ||\textbf{u}-\textbf{v}||_{\infty}\big).\end{align*} $$
Definition 5.14. Let
$f: \mathbb {N} \rightarrow \mathbb {N}$
be a map. We say that a shift X is
$f(n)$
-block gluing when for all n, for all patterns
$p,q$
with support
$\mathbb {B}_n^d$
, and for all
$\textbf {u} \in \mathbb {Z}^d$
such that the Hausdorff distance between
$\mathbb {B}_n^d$
and
$\textbf {u} + \mathbb {B}_n^d$
is at least
$n+f(n)$
, there exists a configuration
$x \in X$
such that
$x_{\mathbb {B}_n^d} = p$
and
$x_{\textbf {u} + \mathbb {B}_n^d} = q$
.
Proposition 5.15. An
$f(n)$
-block gluing shift, where
$f(n) = o(\log (n))$
, has maximality type 0.
Proof. It is known that a shift that is
$o(\log (n))$
-block gluing has a dense set of periodic points (see for instance [Reference Gangloff and Sablik11]). Furthermore, for every f,
$f(n)$
-block gluing implies transitivity. If the shift is finite, then it is of maximality type 0. If it is infinite, then Proposition 5.11 applies and implies that the shift is of maximality type 0.
Question 5.16. What are the possible maximality types for shifts that are strictly
$f(n)$
-block gluing, where f is linear? For mixing shifts?
6 The topological structure of
$\mathcal {S}^d$
when
$d \ge 2$
A natural approach to genericity for higher-dimensional shifts is to compute the closure of the set of isolated shifts and, in particular, its complement in
$\mathcal {S}^d$
, especially because isolated points form a generic set contained in all other generic set when
$d=1$
(see §6.1). As this question is quite difficult, we only provide some observations in this direction. Another way is to compute the Cantor–Bendixson rank of
$\mathcal {S}^d$
. We prove in §6.2 that this rank is infinite. We then prove in §6.2.4 that the closure of the set of maximality type
$\infty $
shifts is included in the Cantor–Bendixson residue.
6.1 On the closure of the set of isolated shifts
Denote by
$\mathcal {I}^d$
the set of isolated shifts in
$\mathcal {S}^d$
. The question of interest is the following.
Question 6.1. How to characterize the set
$\overline {\mathcal {I}^d}$
?
The answer is not trivial:
$\overline {\mathcal {I}^d}$
is not equal to
$\mathcal {I}^d$
and not equal to
$\mathcal {S}^d$
(this was already proved in [Reference Doucha6, Theorem 3.1]), because of the following examples.
Example 6.2. Any infinite full shift is in
$\overline {\mathcal {I}^d}$
because it is the limit of a sequence of finite shifts and a finite shift is isolated. However, a full shift has no maximal subsystem and has strict subsystems, and therefore is not isolated in
$\mathcal {S}^d$
.
Example 6.3. The shift
$X_R$
has no isolated subsystem and is thus not in
$\overline {\mathcal {I}_d}$
. We leave the proof to the reader.
Example 6.4. Every transitive subsystem Z of
$X_R$
is not isolated in
$\mathcal {T}^d$
. The reason is that for any shift of finite type X that contains Z,
$X\backslash Z$
is dense in X (Proposition 5.7 applies). Hence, the set of isolated points of
$\mathcal {T}^d$
is not dense in
$\mathcal {T}^d$
.
6.2 On the Cantor–Bendixson rank of
$\mathcal {S}^d$
6.2.1 Definition
We recall the definition of the Cantor–Bendixson rank. For every topological space X, denote by
$X'$
the set of non-isolated points in X, called the derived set of X.
Definition 6.5. For every ordinal number
$\alpha $
, the
$\alpha $
th Cantor–Bendixson derivative of X is the set
$X^{(\alpha )}$
defined as follows:
$X^{(0)} = X$
; for all
$\alpha $
,
$X^{(\alpha +1)} = {X^{(\alpha )}}'$
;
$X^{(\unicode{x3bb} )} = \bigcap _{\alpha < \unicode{x3bb} } X^{(\alpha )}$
, where
$\unicode{x3bb} $
is a limit ordinal. The Cantor–Bendixson rank of X is the least ordinal
$\alpha $
such that
$X^{(\alpha +1)} = X^{(\alpha )}$
. We call the Cantor–Bendixson residue the set
$X^{(\alpha )}$
, where
$\alpha $
is the Cantor–Bendixon rank of X.
For all d and n, we denote by
$\mathcal {S}_n^d$
the set
$(\mathcal {S}^d)^{(n)}$
.
6.2.2 The shift associated with the
${}\times 2\times 3$
system on the circle
Using a symbolic encoding of the well-known
${}\times 2 \times 3$
system on the circle, we first prove that there is at least one isolated point in
${\mathcal {S}^d}' = \mathcal {S}^d \backslash \mathcal {I}^d$
.
Notation 6.6. We denote by
$X_0$
the shift on alphabet
$\mathbb {Z}/6\mathbb {Z}$
defined as the set of configurations x in
$(\mathbb {Z}/6\mathbb {Z})^{\mathbb {Z}^2}$
such that for all
$\textbf {u}\in \mathbb {Z}^2$
, there exist
$\epsilon _1 \in \{0,1\}$
and
${\epsilon _2 \in \{0,1,2\}}$
such that
$x_{\textbf {u} + \textbf {e}_1} = 2 x_{\textbf {u}} + \epsilon _1$
and
$x_{\textbf {u} + \textbf {e}_2} = 3 x_{\textbf {u}} + \epsilon _2$
.
Note that this shift is identical to that defined in [Reference Rudolph23]. The following lemma can be checked case by case.
Lemma 6.7. For all
$k,l \in \mathbb {Z}/6\mathbb {Z}$
, there exists a unique pattern q in 
such that
$q_{(0,0)} = k$
and
$q_{(1,1)}=l$
.
The following theorem is well known.
Theorem 6.8. (Furstenberg [Reference Furstenberg9])
The only infinite subset of the circle
$\mathbb {T}^1$
, which is closed and invariant for the maps
$x \mapsto 2x$
and
$x \mapsto 3x$
is
$\mathbb {T}^1$
itself.
Notation 6.9. For all
$n \in \mathbb {N}$
, set
$\textbf {u}^n :=(n,n)$
. We denote by
$\unicode{x3bb} $
the function
$\mathscr {L}_{\mathbb {N}^2}(X_0) \rightarrow \mathbb {T}^1$
such that for all
$p \in \mathscr {L}_{\mathbb {N}^2}(X_0)$
,
$\unicode{x3bb} (p)$
is the point
$x \in \mathbb {T}^1$
whose representation in base
$6$
is
$(p_{\boldsymbol {u}^n})_n$
.
Lemma 6.10. The map
$\unicode{x3bb} $
is surjective and continuous. Furthermore, for all
$x \in \mathbb {T}^1$
,
$|\unicode{x3bb} ^{-1}(\{x\})\}| = 2$
if x is of the form
$m/6^l$
, for some
$m,l\in \mathbb {N}$
, and
$|\unicode{x3bb} ^{-1}(\{x\})| = 1$
otherwise.
Proof. Continuity is straightforward. Surjectivity is obtained from repeated application of Lemma 6.7 and the shift map. The rest of the statement comes from the definition of
$\unicode{x3bb} $
.
Lemma 6.11. For a bi-dimensional shift X, if
$\mathscr {L}_{\mathbb {N}^2}(X)$
is finite, then X is finite. Furthermore, considering two shifts
$X \subset Z$
, if
$\mathscr {L}_{\mathbb {N}^2}(X) = \mathscr {L}_{\mathbb {N}^2}(Z)$
, then
$Z=X$
.
Proof. Suppose that
$\mathscr {L}_{\mathbb {N}^2}(X)$
is finite. For every
$p \in \mathscr {L}_{\mathbb {N}^2}(X)$
,
$(p_{|(n,n) + \mathbb {N}^2})_n$
is an ultimately periodic sequence. As a consequence, the sequence
$(\sigma ^{(n,n)}(X))_n$
converges towards a finite shift. However, it is constant with value X; therefore, X is finite. Consider now
$Z \subset X$
such that
$\mathscr {L}_{\mathbb {N}^2}(X) = \mathscr {L}_{\mathbb {N}^2}(Z)$
. To prove that
$Z=X$
, it suffices to prove that for all
$x \in X$
and all n, there exists a configuration z in Z such that z coincides with x on
$(-n,-n) + \mathbb {N}^2$
. Indeed, in this case, x is in the closure of Z, and thus in Z. Let
$x \in X$
and
$n\in \mathbb {N}$
. By hypothesis, there exists
$z \in Z$
such that
$\sigma ^{(n,n)}(x)$
and z coincide on
$\mathbb {N}^2$
. Therefore, x and
$\sigma ^{(-n,-n)}(z) \in Z$
coincide on
$(-n,-n) + \mathbb {N}^2$
. This ends the proof.
Proposition 6.12. All the strict subsystems of
$X_0$
are finite.
Proof. Consider a subsystem X of
$X_0$
. Denote by Z the set of restrictions of elements of X to
$\mathbb {N}^2$
. Since
$\unicode{x3bb} $
is continuous, and that by definition of
$X_0$
, for all
$p \in \mathscr {L}_{\mathbb {N}^2}(X_0)$
,
$\unicode{x3bb} (\sigma ^{\textbf {e}_1}(x)) = 2\unicode{x3bb} (p) $
and
$\unicode{x3bb} (\sigma ^{\textbf {e}_2}(p)) = 3\unicode{x3bb} (p) $
, the set
$\unicode{x3bb} (Z)$
is invariant for the maps
${x \mapsto 2x}$
and
$x \mapsto 3x$
. By Theorem 6.8, there are two possibilities. If the set
$\unicode{x3bb} (Z)$
is finite, since
$|\unicode{x3bb} ^{-1}(\{x\})| \le 2$
for all
$x \in \mathbb {T}^1$
, then Z is finite and by Lemma 6.11, X is also finite. Otherwise, as a consequence of Theorem 6.8,
$\unicode{x3bb} (Z)$
must be equal to
$\mathbb {T}^1$
and since for all
$x \in \mathbb {T}^1$
that is not of the form
$m/6^l$
,
$|\unicode{x3bb} ^{-1}(\{x\})| = 1$
, Z contains a subset that is dense in
$\mathscr {L}_{\mathbb {N}^2}(X_0)$
. Since it is closed, it must be equal to
$\mathscr {L}_{\mathbb {N}^2}(X_0)$
. Again, because of Lemma 6.11,
$X = X_0$
. Therefore, if X is different from
$X_0$
, then X is finite.
Remark 6.13. As a consequence, the shift
$X_0$
has maximality type 0.
Notation 6.14. For all
$d \ge 0$
and X a bi-dimensional shift, we denote by
$\mathcal {E}^{d}(X)$
the
$(d+2)$
-dimensional shift such that for all
$k \ge 3$
and for all
$x \in \mathcal {E}^{d}(X)$
,
$\sigma ^{\textbf {e}_k}(x) = x$
and, denoting by P the set of elements of
$\mathbb {Z}^d$
whose kth coordinate is 0 for all
$k \ge 3$
,
$\mathscr {L}_P (\mathcal {E}^{d}(X)) = X_0$
.
Theorem 6.15. For all
$d \ge 0$
,
$\mathcal {E}^{d}(X_0)$
is isolated in
$\mathcal {S}^{d+2} \backslash \mathcal {I}^{d+2}$
.
Proof. Since strict subsystems of
$X_0$
are finite, it is straightforward that strict subsystems of
$\mathcal {E}^{d}(X_0)$
are also finite for all
$d \ge 0$
. Since a finite shift is isolated, all the subsystems of
$\mathcal {E}^{d}(X_0)$
are isolated. Since
$\mathcal {E}^{d}(X_0)$
is of finite type, it has a neighbourhood that contains only isolated points in
$\mathcal {S}^{d+2}$
. Therefore,
$\mathcal {E}^{d}(X_0)$
is isolated in
$\mathcal {S}^{d+2} \backslash \mathcal {I}^{d+2}$
.
6.2.3 The Cantor–Bendixson rank of the shifts space is infinite
In this subsection, we prove Theorem C from §1 as Theorem 6.20. For this purpose, we first prove some technical lemmas on which the proof of Theorem 6.20 relies, making this proof simpler.
Lemma 6.16. The set
$\mathcal {I}^d$
is invariant under disjoint unions.
Proof. Indeed, the disjoint union of two shifts of finite type is also of finite type. Furthermore, if X and Z are two disjoint isolated shifts, the maximal subsystems of
$X \cup Z$
are of the form
$X \cup M$
or
$N \cup Z$
, where N and M are maximal subsystems of X and Z, respectively. Therefore,
$X \cup Z$
has a finite number of maximal subsystems. Since every subsystem of
$X \cup Z$
is the union of a subsystem of X and a subsystem of Z, every subsystem of
$X \cup Z$
is included in one of its maximal subsystems. The result follows from Theorem 3.23.
For all
$n> 0$
, we denote by
$\mathcal {D}_{n}^d$
the set of isolated points in
$\mathcal {S}_n^d$
whose subsystems are all shifts of finite type. Also, set
$\mathcal {C}_n^d := \bigcup _{k=0}^n \mathcal {D}_k^d$
. In particular,
$\mathcal {D}_0^d = \mathcal {C}_0^d$
is the set of shifts in
$\mathcal {I}^d$
whose subsystems are all of finite type. Thus, every finite shift is in this set. Denote as well the lexicographic order on
$\mathbb {N}^2$
by
$<_{\texttt {lex}}$
, which is defined as follows: for
$(k,l),(m,n) \in \mathbb {N}^2$
,
$(k,l) <_{\texttt {lex}} (m,n)$
if and only if (
$k < m$
or (
$k=m$
and
$l < n$
)).
Lemma 6.17. For all
$n \ge 1$
and
$0 \le m \le n$
, we have the following property denoted by
$P_{n,m}$
. For every
$X \in \mathcal {S}_m^d$
and
$Z \in \mathcal {S}_n^d$
such that
$X \cap Z = \emptyset $
, if
$m=0$
, we have
$X \cup Z \in \mathcal {S}_n^d$
; otherwise, we have
$X \cup Z \in \mathcal {S}_{n+1}^d$
.
Proof. We prove this by induction on
$(n,m) \in (\mathbb {N} \times \mathbb {N}) \backslash (\mathbb {N} \times \{0\})$
following the lexicographic order. Fix
$(n,m) \in (\mathbb {N} \times \mathbb {N}) \backslash (\mathbb {N} \times \{0\})$
and assume that the property
$P_{k,l}$
is true for all
$(k,l) <_{\texttt {lex}} (m,n)$
. Fix
$X \in \mathcal {S}_m^d$
and
$Z \in \mathcal {S}_n^d$
such that
$X \cap Z = \emptyset $
. There exists a sequence
$(Z_r)_r$
of shifts in
$\mathcal {S}_{n-1}^d$
such that
$Z_r \rightarrow Z$
and for all r,
$Z_r \neq Z$
. Case
$\boldsymbol {m = 0}$
. For all r,
$X \cup Z_r$
is in
$\mathcal {S}_{n-1}^d$
: if
$n=1$
, this is trivial; otherwise, this comes from the induction hypothesis. Since
$X \cup Z_r \rightarrow X \cup Z$
and for all r we have
$X \cup Z_r \neq X \cup Z$
, this implies that
$X \cup Z \in \mathcal {S}_n^d$
. Case
$\boldsymbol {m> 0}$
. In this case, consider any sequence
$(X_r)$
in
$\mathcal {S}_0^d$
that converges towards X. Then by induction, for all r, we have
$X_r \cup Z \in \mathcal {S}_n^d$
. Since
$X_r \cup Z \rightarrow X \cup Z$
and for all r,
$X_r \cup Z \neq X \cup Z$
, this implies that
$X \cup Z \in \mathcal {S}_{n+1}^d$
.
Lemma 6.18. Let
$X,Z$
be two shifts of finite type whose subsystems are all of finite type and let U (respectively V) be a neighbourhood of X (respectively Z) that consists of subsystems of X (respectively Z). The set W of shifts of the form
$M \cup N$
, where
$M \in U$
and
$N \in V$
, is a neighbourhood of
$X \cup Z$
.
Proof. Consider a shift of the form
$M \cup N$
, where
$M \in U$
and
$N \in V$
. Since
$M \in U$
and
$N \in V$
, they are subsystems of X and Z, respectively, and thus by hypothesis, they are of finite type. Since X and Z are disjoint, M and N are also disjoint. Therefore,
$M \cup N$
is a shift of finite type. Set
$\epsilon _0 < \min _{x \in M} \min _{z \in N} \delta (x,z)$
such that every shift that is at distance less than
$\epsilon _0$
from
$M \cup N$
is a subsystem of
$M \cup N$
and every shift at a distance less than
$\epsilon _0$
from M (respectively N) is in U (respectively V). Consider a shift Y such that
$\delta _H(Y,M \cup N) < \epsilon _0$
. This implies that Y is a subsystem of
$M \cup N$
and can be written as
$Y = (Y \cap M) \cup (Y \cap N)$
. Both
$Y \cap M$
and
$Y \cap N$
are shifts, and since
$\delta _H(Y,M \cup N) < \epsilon _0$
and
$\epsilon _0 < \min _{x \in M} \min _{z \in N} \delta (x,z)$
, they are at a distance less than
$\epsilon _0$
from M and N, respectively. Indeed, consider
$x \in M$
. Since
$\delta _H(Y,M \cup N) < \epsilon _0$
, there exists
$y \in Y$
such that
$\delta (x,y) \le \epsilon _0$
. Since
$\epsilon _0 < \min _{x \in M} \min _{z \in N} \delta (x,z)$
, we have
$y \in Y \cap M$
. Since
$Y \cap M \subset M$
, this is enough to conclude that
$\delta _H(Y\cap M , M) \le \epsilon _0$
. Similarly, we have
$\delta _H(Y\cap N , N) \le \epsilon _0$
. Thus,
$Y\cap M$
is in U and
$Y\cap N$
is in V. This implies that Y is in W.
Lemma 6.19. For all
$n \ge 1$
,
$0 \le m \le n$
, we have the following property denoted by
$Q_{n,m}$
. For every
$X \in \mathcal {D}_{m}^{d}$
and
$Z \in \mathcal {D}_{n}^{d}$
such that
$X \cap Z = \emptyset $
, if
$m =0$
, the shift
$X \cup Z$
is in
$\mathcal {D}^d_{n}$
; otherwise, it is in
$\mathcal {D}^d_{n+1}$
.
Proof. Again we prove this by induction on
$(n,m) \in (\mathbb {N} \times \mathbb {N}) \backslash (\mathbb {N} \times \{0\})$
following the lexicographic order. Fix
$(n,m) \in (\mathbb {N} \times \mathbb {N})\backslash (\mathbb {N} \times \{0\})$
and assume that the property
$Q_{k,l}$
is true for all
$(k,l) <_{\texttt {lex}} (n,m)$
. Take
$X \in \mathcal {D}_m^d$
and
$Z \in \mathcal {D}_n^d$
such that
$X \cap Z$
is empty. Observe that the subsystems of
$X\cup Z$
are its non-empty subsets of the form
$M \cup N$
, where M (respectively N) is empty or a subsystem of X (respectively Z). Since the disjoint union of two shifts of finite type is of finite type, all the subsystems of
$X \cup Z$
are of finite type. Case
$\boldsymbol {m = 0}$
. The shift
$X \cup Z$
is in
$\mathcal {S}_{n}^d$
by Lemma 6.17. We have left to prove that
$X \cup Z$
is isolated in
$\mathcal {S}_{{n}}^d$
, meaning that it has a neighbourhood W such that
$W\backslash \{X\cup Z\} \subset \mathcal {C}_{{n-1}}^d$
. Since Z is of finite type and isolated in
$\mathcal {S}_{{n}}^d$
, there exists a neighbourhood U of Z that consists of subsystems of Z that are in
$\mathcal {C}_{{n-1}}^d$
. Denote by W the set of subsystems of
$X \cup Z$
of the form
$X \cup N$
, where
$N \in {U}$
. Since X is isolated in
$\mathcal {S}_0^d$
, by Lemma 6.18, the set W is a neighbourhood of
$X \cup Z$
. Any element of W different from
$X \cup Z$
is the disjoint union of a shift in
$\mathcal {C}_{n-1}^d$
and a shift in
$\mathcal {C}_{0}^d$
. For
$n> 1$
, this implies that every element of W different from
$X \cup Z$
is in
$\mathcal {C}_{n-1}^d$
. In the case
$n = 1$
, every element of W different from
$X \cup Z$
is the union of two shifts in
$\mathcal {I}^d$
, which is in
$\mathcal {I}^d$
. Since the subsystems of both of these shifts are all of finite type and that the disjoint union of two shifts of finite type is of finite type, every element of W is in
$\mathcal {C}_0^d$
. Case
$\boldsymbol {m> 0}$
. The shift
$X \cup Z$
is in
$\mathcal {S}_{n+1}^d$
by Lemma 6.17. We have left to prove that
$X \cup Z$
is isolated in
$\mathcal {S}_{n+1}^d$
, meaning that it has a neighbourhood W such that
$W\backslash \{X\cup Z\} \subset \mathcal {C}_n^d$
. Since X (respectively Z) is of finite type and isolated in
$\mathcal {S}_{m}^d$
(respectively
$\mathcal {S}_{n}^d$
), there exists a neighbourhood U (respectively V) of X (respectively Z) such that
$U \backslash \{X\}$
(respectively
$V \backslash \{Z\}$
) consists of subsystems of X (respectively Z) that are in
$\mathcal {C}_{m-1}^d$
(respectively
$\mathcal {C}_{n-1}^d$
). Denote by W the set of subsystems of
$X \cup Z$
of the form
$M \cup N$
, where
$M \in U$
and
$N \in V$
. By Lemma 6.18, the set W is a neighbourhood of
$X \cup Z$
. Any element of W different from
$X \cup Z$
is the disjoint union of a shift in
$\mathcal {D}_k^d$
with a shift in
$\mathcal {D}_l^d$
, where
$k < m$
and
$l {\le } n$
, or
$k \le m$
and
$l < n$
. In any case, by induction, we can deduce that any element of W different from
$X \cup Z$
is in
$\mathcal {C}_n^d$
.
For any d-dimensional shift X and any integer
$n \ge 0$
, we denote by
$\mathcal {G}_n(X)$
the shift
$X \times Z_n$
, where
$Z_n$
is the d-dimensional shift on alphabet 
whose elements are the constant configurations with value in 
.
Theorem 6.20. (Theorem C)
The Cantor–Bendixson rank of
$\mathcal {S}^d$
,
$d>1$
, is infinite.
Proof. We already know from Theorem 6.15 that
$\mathcal {E}^d(X_0) \in \mathcal {D}^{d+2}_{{1}}$
for all
$d \ge 0$
. By Lemma 6.19, for all
$n \ge 1$
,
$\mathcal {G}_n(\mathcal {E}^d(X_0)) \in \mathcal {D}^{d+2}_{{n}}$
. Thus, for all n, the set of isolated points in
$\mathcal {S}^d_{n}$
is not empty. This implies that the Cantor–Bendixson rank of
$\mathcal {S}^d$
is infinite.
6.2.4 Type
$\infty $
shifts are in the Cantor–Bendixson residue
Proposition 6.21. The set of maximality type
$\infty $
shifts is included in the Cantor–Bendixson residue. Furthermore, it has empty interior.
Proof. Consider any shift X that has maximality type
$\infty $
. Denote by
$T_k, k \in \mathbb {N}$
, the elements of
$\mathcal {T}(X)$
.
-
(1) Using Theorem 4.10, for all
$k \in \mathbb {N}$
, the set
$\mathcal {K}(X) \cup (\bigcup _{n \neq k} T_n )$
is also of maximality type
$\infty $
and this sequence converges towards X by Lemma 4.4. As a consequence, the set of maximality type
$\infty $
shifts has no isolated point. This implies that the closure of this set is contained in the Cantor–Bendixson residue. -
(2) Again by Theorem 4.10, for all n, the set
$\mathcal {K}(X) \cup (\bigcup _{k=0}^n T_k)$
has maximality type
$n+1$
and this sequence converges to X. Thus, X is the limit of a sequence of finite maximality type shifts. Since this is true for all X, the set of maximality type
$\infty $
shifts has empty interior.
Remark 6.22. A direct consequence is that the closure of this set is also in the Cantor–Bendixson residue.
7 Open questions
We conclude our discussion with some open questions.
7.1 Main questions
The most relevant questions are the following.
Question 7.1. What is the closure of the set of isolated shifts in
$\mathcal {S}^d$
?
We expect that the systems in this closure satisfy some conditions in terms of the structure of the subsystems set; however, these conditions are not apparent. Another important question is as follows.
Question 7.2. What is the Cantor–Bendixson rank of
$\mathcal {S}^d$
?
We conjecture the following.
Conjecture 7.3. The Cantor–Bendixson rank of the space of d-dimensional shifts is
$\omega $
for all
$d> 1$
. Furthermore, the Cantor–Bendixson residue is the closure of the set of shifts having maximality type infinity. The shifts that are not in this residue are those that can be written as a finite union of shifts of finite type and are the limit of their minimal subsystems.
Another strategy to understand the topological structure of
$\mathcal {S}^d$
is to begin with understanding the structure of the subsystems of shifts of finite type outside of full shifts.
Question 7.4. What are the shifts of finite type in
$\mathcal {S}^d$
whose set of (transitive) subsystems is a perfect set?
7.2 Relations between the notions introduced
The main outcome of our study is a battery of concepts that may be studied independently. A better understanding of these concepts could be useful to understand genericity for higher dimensional shifts: the notion of maximal subsystem and the maximality type; certain properties of shifts in relation to isolated shifts (having only isolated subsystems or no isolated subsystems at all), or the shifts that have a neighbourhood in which each element contains it, the shifts that satisfy the
$(\star )$
property. One could, for instance, wonder about the possible maximality types for systems in each of the classes described, or the closure and interior of these classes. Characterize systems whose subsystems are all in a certain class or whose neighbourhood has only systems in a given class. Which of these classes have non-empty intersection?
7.3 Properties of isolated shifts
Questions that could lead to a better understanding of isolated points of
$\mathcal {S}^d$
are of interest. In particular, we suspect that isolated points have low complexity.
Question 7.5. Do isolated points in
$\mathcal {T}^d$
have zero entropy?
Another way is to explore the limit structures of subsystems in the set of isolated shifts.
Question 7.6. Is there a decreasing infinite sequence of shifts
$(X_n)_{n\ge 0}$
such that
$X_0$
is of finite type and for all n,
$X_{n+1}$
is the unique maximal subsystem of
$X_n$
? If so, what are the properties of
$\bigcap _n X_n$
?
7.4 Transitivity and maximality type
We have proved that a transitive shift has maximality type
$0$
or
$1$
. However, we know that not all shifts of maximality type
$0$
or
$1$
are transitive. Is it possible to distinguish how non-transitivity of shifts with maximality type
$\ge 2$
differs from the non-transitivity of those that have maximality type
$0$
or
$1$
?
Acknowledgements
We thank Mathieu Sablik for pointing us in the direction of Pavlov and Schmieding’s article, and the fruitful conversations about it. We also thank Nicanor Carrasco for the idea that the Robinson shift is not isolated, on which this article is based. The second author is supported by the National Agency for Research Development (ANID)/Scholarship Program/DOCTORADO BECAS CHILE/2019 - 72200562; by the ANR ‘Difference’ project (ANR-20-CE40-0002); by the CIMI LabEx ‘Computability of asymptotic properties of dynamical systems’ project (ANR-20-CE48-0002).
