Avoshifts

Let $\Sigma$ be a finite set called the alphabet and $G$ a discrete group. A subshift of finite type or SFT $X\subset\Sigma^{G}$ is a set closed under the shift maps $\sigma_{g}(x)_{h}=gx_{h}=x_{g^{-1}h}$, and which is defined by removing exactly the points $x\in\Sigma^{G}$ whose orbit hits a particular clopen set $F$, or equivalently contain a forbidden pattern from a finite set.

It is well-known that one-dimensional SFTs (the case $G=\mathbb{Z}$) behave in a much nicer and uniform way than multidimensional SFTs ($G=\mathbb{Z}^{d},d\geq 2$). As two examples of nice dynamical properties that hold in one dimension, topologically transitive subshifts of finite type in one dimension have a unique measure of maximal entropy and have dense periodic points (these fail for general subshifts of finite type, but in completely manageable ways). Furthermore, SFTs (and even their subshift factors called sofic shifts) can be algorithmically compared for equality and inclusion. See e.g. the standard reference [16].

In higher dimensions, even under strong irreducibility (a strong mixing/niceness assumption), subshifts may have multiple measures of maximal entropy [7], $\mathbb{Z}^{3}$-SFTs are not known to have dense periodic points (see e.g. [9]), and it is not even possible to algorithmically tell whether a given subshift of finite type is empty [4]. For this reason, a recurring endeavor in the field of symbolic dynamics is to try to find classes of multidimensional subshifts which capture some of the interesting phenomena from the two-dimensional setting, but where at least some properties are decidable or otherwise understandable.

Group shifts – groups where the elements are points of the subshift, and group operations are continuous and shift-commuting – are the most successful such a class. They are of finite type when the shift group $G$ is polycyclic [31]. They have dense periodic points at least on abelian groups [12]. They also of course have a ``most uniform'' measure, namely the Haar measure. Many of their basic properties (inclusions, and even some dynamical properties) are decidable [3]. An extensive theory of group shifts (with emphasis on the abelian case) is developed in [31].

In [25], the author introduced the so-called $k$-TEP subshifts. They share some properties of group shifts and one-dimensional SFTs: there is a natural measure (the measure that ``samples patterns uniformly on convex sets''). They have dense periodic points, and there are also some decidable properties, for example inclusion is easily seen to be decidable for this class.¹¹1The last results are not explicitly stated in [25], but are obvious corollaries of results proved therein; in any case, they follow from the results proved in the present paper.

Different mixing assumptions can have useful implications also in higher dimensions (even if usually not as nice as in one dimension). Strong irreducibility implies dense periodic points at least for two-dimensional SFTs [14, 15]. Two stronger mixing properties are the existence of a safe symbol, and the more general topological strong spatial mixing. Here, we say $0\in\Sigma$ is a safe symbol for an SFT $X$ if turning a non-$0$ symbol to $0$ in a valid configuration can never introduce a forbidden pattern, for the latter property see Definition 4.8. All SFTs in these classes dense periodic points, and thus their languages and inclusion are decidable.

In the present paper, we define a new class of subshifts called avoshifts. This class is defined with respect to a family of subsets of the acting shift group $G$, and the definition is that if a partial configuration $x\in\Sigma^{C}$ (with $C$ in the specified class of shapes) extends to a complete configuration of the subshift, then the set of valid extensions to the identity element is determined by a finite subpattern of the configuration, which is bounded as a function of $x$, but not necessarily $C$.

We consider the class of avoshifts for a quite restricted²²2This is a good thing – the smaller the class of shapes, the larger the class of avoshifts. class of shapes called inductive intervals. With this choice, avoshifts generalize (cellwise quasi-)group shifts, $k$-TEP subshifts (on $\mathbb{Z}^{d}$ with the standard convex geometry). It also covers all SFTs with a safe symbol, and topological strong spatial mixing in fact precisely coincides with the avo property for the class of all possible shapes. Inductive intervals make sense on any polycyclic group, and depend on the chosen subnormal series.

The following is our main ``practical'' result.

Avofactors are factors that can be expressed as projections from a product that satisfies a similar property as that defining avoshifts. This includes all factors given by algebraic maps between group shifts.

The first five results (see below for a discussion of the sixth) were previously known for group shifts (at least for abelian groups). The first is proved in [13, 31] (in the former on $\mathbb{Z}$, in the latter for general polycyclic groups), the second and third are from [12], and the fourth and fifth are from [3].

An important takeaway are that avoshifts on polycyclic groups satisfy the basic decidability properties, and SFTness, of group shifts. Notably, our proof of these results uses the group structure ``only once'', and the only fact used is ``equal extension counts'' (see Section 3.1 for the definition) for all finite patterns of the same shape, which is trivially true for (cellwise quasi)group shifts. For group shifts, both [12, 3] strongly use Wang's algorithm [32], which is based on the density of periodic points. Avoshifts do not have dense periodic points, and our methods are not related to Wang's algorithm in any obvious way.

The fact that avoshifts are of finite type does not seem to generalize beyond polycyclic groups [24], but the other properties are really consequences of the uniform avo property (meaning the set of valid extensions of $x\in\Sigma^{C}$ to the identity element is determined by a subpattern which is bounded as a function of $C$ and $x$), which in the case of polycyclic groups and inductive intervals is automatic. We illustrate this by giving an avoshift proof of the well-known fact that SFTs on free groups have decidable languages and decidable inclusion, by showing that SFTs are characterized by the uniform avo property on the tree convex sets from [25].

The sixth property in Theorem 1.1 means that there is a finite set of forbidden patterns such that for $C\subset G$ in the family, configurations that are locally legal on $C$ are globally legal (similarly to the main property of $k$-TEP subshifts described in the first bullet point of [25, Theorem 1.1]). This is closely tied with the uniform avo property.

We also make the following two observations that may be of interest despite not having decidability implications: The topological Markov property [1] is equivalent to being avo for the class of cofinite sets (Proposition 4.12). The property of being topologically $k$-mixing for all $k$ can be stated equivalently as being uniformly SFT on the sets of cardinality $n$ for all $n$.

A lengthy discussion of practicality of these methods, possible extensions of the theory, and future work is included in Section 10.

We have $0\in\mathbb{N}$. We denote the power set of a set $S$ by $\mathcal{P}(S)$. A subset (not necessarily proper) is written $A\subset B$. A finite subset is written $A\Subset B\iff A\subset B\wedge|A|<\infty$. We write $\mathbb{Z}_{k}$ for the cyclic group on $k$ elements, for $k$ finite. By $\vec{0}$ we denote the zero vector of $\mathbb{Z}^{d}$ for any $d$.

Throughout, $G$ will denote a group. Our groups are for the most part finitely generated and countable. The identity element is denoted by $e_{G}$ or just $e$. We typically think of $G$ as acting on itself by left translation. We consider the group to carry a generating set (usually called $S$ when a name is needed, but this symbol is not reserved for this purpose) and the resulting left-invariant word metric (typically called $d$). The ball of radius $n$ or $n$-ball is $\mathcal{B}_{n}=\{g\in G\;:\;d(e_{G},g)\leq n\}$. Specifically this is the metric closed ball of radius $n$ around the identity element, but $g\mathcal{B}_{n}$ is the metric ball around the element $g$ so we do not need special notation for it. We usually have in mind the right Cayley graph $\textrm{Cay}(G,S)$ with nodes $G$ and edges $(g,gs)$ for $s\in S$. Subsets of $G$ are sometimes called areas or shapes. For $A,B\subset G$ we write $d(A,B)=\min\{d(a,b)\;:\;a\in A,b\in B\}$.

An alphabet is a finite (discrete) set $\Sigma$. A subshift is $X\subset\Sigma^{G}$ which is topologically closed ($\Sigma^{G}$ having the product topology) and closed under the shift or translation action of $G$ defined by formula $gx_{h}=x_{g^{-1}h}$, where in turn $x_{h}$ is the notation for indexing $x$ at $h$. Note that $\Sigma^{G}$ is compact, and thus so are subshifts.

The subsets $\mathcal{P}(G)$ also carry the standard Fell topology (through identification of a set $S\subset G$ with its indicator function in $\{0,1\}^{G}$, this is the same as the topology used for subshifts). Subsets of $G$ are also considered as an ordered set with inclusion as the order, and $S_{i}\nearrow S$ means $\forall i:S_{i}\subset S_{i+1}\wedge\bigcup_{i}S_{i}=S$.

In this paper, we use the terminology that a point is always an element of $\Sigma^{G}$ for a group $G$, a configuration is any element of $\Sigma^{D}$ where $D\subset G$ for some group $G$ (possibly a point, possibly $D\subsetneq G$), and a pattern is a configuration $x\in\Sigma^{D}$ whose domain $D$ is finite. We sometimes use the term ``finite pattern'' (meaning pattern), and ``partial configuration'' (meaning configuration) for emphasis, and a point is sometimes referred to as a ``complete configuration''. A $D$-pattern is pattern with domain $D$. We mostly use $x,y,z$ to refer to points and configurations, and $P,Q,R$ to refer to patterns.

If $x\in\Sigma^{D}$ and $C\subset D$, we write restriction as $x|C\in\Sigma^{C}$, as we tend to have non-trivial formulas for the sets $C$ that we prefer not to have in a subscript. If $X\subset\Sigma^{D}$, $X|C=\{x|C\;:\;x\in X\}$. We say a configuration $x\in\Sigma^{C}$ is a subconfiguration of $y\in\Sigma^{D}$ if $C\subset D$ and $y|C=x$. If $C$ is the set of elements of $D$ at some distance from the origin, we also call $x$ a prefix of $y$. We say two configurations $x\in\Sigma^{C},y\in\Sigma^{D}$ agree on $B\subset C\cap D$ if $x|B=y|B$.

For a symbol $a\in\Sigma$ and $g\in G$, write $a^{g}$ for the pattern $P\in\Sigma^{\{g\}}$ with $P_{g}=a$. We sometimes identify $a$ with the pattern $a^{e}$. For two patterns $P\in\Sigma^{C},Q\in\Sigma^{D}$ write $P\sqcup Q$ for the pattern $R\in\Sigma^{C\cup D}$ defined by $R|C=P,R|D=Q$, when such a pattern exists. If $P\in\Sigma^{D}$ and $g\in G$, then $gP\in\Sigma^{gD}$ is the configuration defined by $gP_{gh}=P_{h}$ (equivalently $gP_{h}=P_{g^{-1}h}$, so shifting a point $x\in\Sigma^{G}$ is a special case of this definition). The empty pattern is the unique pattern with domain $\emptyset$.

We say $x$ occurs or appears in $y$ if $gx$ is a subconfiguration of $y$ for some $g\in G$; equivalently we say $y$ contains $x$. We denote this by $x\sqsubset y$. We write $x\sqsubset X$ (and use the previous three terms as well) if $x\sqsubset y$ for some $y\in X$. We write $\mathscr{L}(X)=\{P\;:\;P\sqsubset X\}$ for the language of $X$. Note that the empty pattern is in the language of $X$ if and only $X$ is nonempty.

A subshift of finite type or SFT is $X\subset\Sigma^{G}$ defined by $X=\{x\in\Sigma^{G}\;:\;\forall g\in G:gx\notin C\}$, where $C\subset\Sigma^{G}$ is clopen. A clopen set is finite union of cylinders $[P]=\{x\in A^{G}\;:\;x|D=P\}$ where $P:D\to A$ for $D\Subset G$ (the notation means finite subset). The patterns $P$ giving the cylinders comprising $F$ are called the forbidden patterns. A window for an SFT $X\subset\Sigma^{G}$ is any $M\Subset G$ such that there is a set of defining forbidden patterns whose domains are contained in $M$. A window size is any $m$ such that $\mathcal{B}_{m}$ is a window. Note that on a group, we can always pick $M$ to be the same for all the finitely many forbidden patterns, but it will be necessary later (when we later talk about being SFT on a subset of the group) to allow for the forbidden patterns to have different domains.

If $M\Subset G$ and $X\subset\Sigma^{G}$ is a subshift, the $M$-SFT approximation of $X$ is the SFT $Y\subset\Sigma^{G}$ defined by

Equivalently, this is the set of configurations defined by forbidding precisely the patterns $P\in\Sigma^{M}$ which do not appear in $X$.

Suppose a group $G$ and a subshift $X\subset\Sigma^{G}$ are clear from context. Then we say a configuration $x\in\Sigma^{C}$ is globally valid or globally legal if $x\in X|C$. In the case where $X$ is an SFT, and $\mathscr{P}$ is a defining set of forbidden patterns, then $x\in\Sigma^{C}$ is locally $\mathscr{P}$-valid or locally $\mathscr{P}$-legal if no $P\in\mathscr{P}$ appears in $x$ (with $\mathscr{P}$ omitted if clear from context). Globally valid configurations are of course locally valid, and locally valid points (complete configurations) are globally valid.

If $X\subset\Sigma^{G}$ is a subshift and $x\in\Sigma^{D}$ for $D\subset G$, then the follower set $\mathcal{F}(x,E)=\mathcal{F}_{X}(x,E)$ is the set of configurations $z\in\Sigma^{E}$ such that for some $y\in X$ we have $y|D=x\wedge y|E=z$, or equivalently $x\sqcup z\in X|D\cup E$ (and $\sqcup$ is well-defined). We refer to configurations $z\sqcup x\in X|D\cup E$ as the extensions of $x$ to $E$. If $E$ is a singleton (indeed even if $E=\{g\}\neq\{e\}$), we may simply write the unique element of $\Sigma$ in this place to refer to an extension.

We say a subshift $X\subset\Sigma^{G}$ is topologically mixing if for any nonempty open $U,V\subset X$, for any large enough $g$ (in word norm) there is a point $x\in X$ with $x\in U,gx\in V$. More generally topological $k$-mixing means for any nonempty open $U_{1},\ldots,U_{k}$ there exists $n$ such that for any $(g_{1},g_{2},\ldots,g_{k})\in G^{k}$ with $d(g_{i},g_{j})>n$ for $i\neq j$, there exists $x\in X$ such that $g_{i}x\in U_{i}$ for all $i$. In the introduction we used the term mixing/gluing property; by this we refer to notions that in some (intuitive, informal) sense generalize the idea of topological mixing.

If $X,Y\subset\Sigma^{G}$ are subshifts, a conjugacy is a shift-commuting homeomorphism $\phi:X\to Y$, and we say $X$ and $Y$ are conjugate in this case. A factor map is a shift-commuting continuous surjection $\phi:X\to Y$ and we say $X$ covers $Y$ or $Y$ is a factor of $X$ in this case. A factor of an SFT is called sofic (note that in this paper, a factor is always a subshift).

If $\Sigma$ itself is a finite group, then a subshift $X\subset\Sigma^{G}$ is called a group shift if it is closed under the operations obtained from those of $\Sigma$ by applying them cellwise. Group shifts are up to conjugacy the same as subshifts on which one can define a group structure by shift-invariant continuous operations [13, 26, 28]. More generally, for any universal algebraic structure on $\Sigma$, we can talk about subshifts with this structure by applying the operations cellwise.

We begin with the precise definition of an avoshift. This is given for general groups and families of subsets of groups.

Note that to say $B$ is $C$-determining is a bit of an abuse of language: $C$-determining means that $B$ determines the possible continuations of (patterns with domain) $C$ to the identity, not that $B$ determines $C$ in any way. We use this terminology as it is concise, and hopefully not too confusing.

We call these inductive intervals because they are defined inductively, and we prove most of their properties by induction.

Another convenient way of expressing that $X$ is $C$-avo is through follower sets.

Note that $e_{G}$ does not really play a special role in the definition of the avo property, since $X$ is always a subshift, and thus if $B\Subset C$ satisfies $\mathcal{F}(x|C,e_{G})=\mathcal{F}(x|B,e_{G})$ for all $x\in X$, then equivalently $\mathcal{F}(x|gC,g)=\mathcal{F}(x|gB,g)$ for all $g\in G$. Sometimes it simplifies life not to have to translate things back to the origin, and we use the preposition ``at'' as follows:

By the previous lemma, $\mathcal{F}(x|C,e_{G})=\mathcal{F}(x|B,e_{G})$ for $B\Subset C$ implies that $\mathcal{F}(x|C,e_{G})=\mathcal{F}(x|D,e_{G})$ for all $B\subset D\subset C$. We obtain the following immediate consequence:

We call such $D$ intermediate sets. It is useful to observe that if $X$ is $C$-avo, then, since the determining set $B$ can be any sufficiently large finite intermediate set, we may simply take $B$ to be the set of elements in $C$ which are at distance $n$ from the identity in the group, for any sufficient $n$. Any $n$ such that $C\cap\mathcal{B}_{n}$ is $C$-determining is called an avoradius for $C$ (the term ``radius'' comes from the theory of cellular automata, see Proposition 4.10). This allows us to express the following notion, which plays a key role later in the paper.

In other words, if we have a configuration with domain $C\in\mathcal{C}$ that is globally valid, then to know the set of its legal continuations to $e_{G}$, it suffices to look at the subpattern on $C\cap\mathcal{B}_{n}$, where $n$ does not depend on $C$.

The following characterization of the avo property is mainly used to explain the name, and to point out a connection to a well-known property of SFTs in one dimension, namely that the shift map being open characterizes one-sided SFTs [20, Theorem 1]. For $C\subset G\setminus\{e_{G}\}$, write $\dot{C}=C\cup\{e_{G}\}$.

Here, the set $X|D\subset\Sigma^{D}$ is topologized by the relative topology inherited from the product topology on $\Sigma^{D}$.

The forward direction of the following result (that avoshifts are of finite type) is based on the classical proof of Kitchens for group shifts being subshifts of finite type [13].

The direction that all SFTs are avo is specific to dimension $1$ (or rather, it generalizes naturally to free groups, see Theorem 7.7). As avoshifts have nice computational properties, no decidability-theoretically useful notion of avoshift can cover all SFTs in higher dimensions. The direction that avoshifts are SFT on the other hand generalizes to all polycyclic groups, as we will see.

Note that the previous lemma implies that even in the case of $\mathbb{Z}$, avoshifts need not have dense periodic points, and may have any number of measures of maximal entropy (though not in the topologically mixing case).

Our first example are the group shifts. The proof should again should remind the reader of Kitchens' argument [13] that group shifts are of finite type.

Recall that group shifts are cellwiseable [13, 26] meaning up to conjugacy the operations of the group can be taken cellwise (the term is from [30]). Thus, this lemma indeed applies to all group shifts up to conjugacy. Quasigroup shifts are not cellwiseable [26], so in the case of quasigroups the assumption that the alphabet itself is a quasigroup may be crucial.

Our next example are the $k$-TEP subshifts. In [25] these are defined in high generality (with respect to any ``$S$-UCP translation-invariant convexoid $\mathcal{C}$'' on the shift group $G$), but we restrict here to the Euclidean case. Let $S\Subset\mathbb{Z}^{d}$, and let $\mathscr{P}\subset\Sigma^{S}$ be a set of patterns. A corner of $S$ is any $s\in S$ such that there exists a linear functional $\ell:\mathbb{R}^{d}\to\mathbb{R}$ such that $\ell(s)>\ell(t)$ for all $t\in S\setminus s$.

Let $\mathcal{D}$ be the family of all intersections of real convex sets with $\mathbb{Z}^{d}$, and let $\mathcal{C}$ be the set of all $C\in\mathcal{D}$ such that $\vec{0}\notin C$ and $C\cup\{\vec{0}\}\in\mathcal{D}$.

Next we consider the topological strong spatial mixing property [5], which generalizes the previous proposition.

Briceño defines this in the case of $\mathbb{Z}^{d}$ in [5], but the definition makes sense in any group. He does not state that $U,V,S$ are disjoint, but this does not change the definition.

The following is related to Lemma 3.11 where one-sided intervals were used to characterize SFTs. Here $\mathcal{C}$ is the set of inductive intervals that are restricted to being negative in one axis (as we will see when we give the general definition). The proposition shows that in the two-dimensional case, this does not lead to $X$ being an avoshift for the two-sided version of $\mathcal{C}$.

Here, a cellular automaton is a shift-commuting continuous function $f:\Sigma^{\mathbb{Z}^{d}}\to\Sigma^{\mathbb{Z}^{d}}$. A neighborhood is $N\Subset\mathbb{Z}^{d}$ such that $x\mapsto f(x)_{\vec{0}}$ is a function of $x|N$ (which always exists by continuity). The function $x|N\mapsto f(x)_{\vec{0}}$ is called a local rule for $f$. A cellular automaton is reversible if it is bijective (this is equivalent to any of the following: injectivity, being a homeomorphism, or having a cellular automaton inverse $f^{-1}$).