Extender sets and multidimensional subshifts

Abstract

In this paper, we consider a $\mathbb{Z}^{d}$ extension of the well known fact that subshifts with only finitely many follower sets are sofic. As in Kass and Madden [A sufficient condition for non-soficness of higher-dimensional subshifts. Proc. Amer. Math. Soc. 141 (2013), 3803–3816], we adopt a natural $\mathbb{Z}^{d}$ analogue of a follower set called an extender set. The extender set of a finite word $w$ in a $\mathbb{Z}^{d}$ subshift $X$ is the set of all configurations of symbols on the rest of $\mathbb{Z}^{d}$ which form a point of $X$ when concatenated with $w$ . As our main result, we show that for any $d\geq 1$ and any $\mathbb{Z}^{d}$ subshift $X$ , if there exists $n$ so that the number of extender sets of words on a $d$ -dimensional hypercube of side length $n$ is less than or equal to $n$ , then $X$ is sofic. We also give an example of a non-sofic system for which this number of extender sets is $n+1$ for every $n$ . We prove this theorem in two parts. First we show that if the number of extender sets of words on a $d$ -dimensional hypercube of side length $n$ is less than or equal to $n$ for some $n$ , then there is a uniform bound on the number of extender sets for words on any sufficiently large rectangular prism; to our knowledge, this result is new even for $d=1$ . We then show that such a uniform bound implies soficity. Our main result is reminiscent of the classical Morse–Hedlund theorem, which says that if $X$ is a $\mathbb{Z}$ subshift and there exists an $n$ such that the number of words of length $n$ is less than or equal to $n$ , then $X$ consists entirely of periodic points. However, most proofs of that result use the fact that the number of words of length $n$ in a $\mathbb{Z}$ subshift is non-decreasing in <jats:tex-mat