Hostname: page-component-76fb5796d-r6qrq Total loading time: 0 Render date: 2024-04-26T12:19:54.872Z Has data issue: false hasContentIssue false

Extender sets and multidimensional subshifts

Published online by Cambridge University Press:  02 October 2014

NIC ORMES
Affiliation:
Department of Mathematics, University of Denver, 2280 S. Vine Street, Denver, CO 80208, USA email normes@du.edu, rpavlov@du.edu
RONNIE PAVLOV
Affiliation:
Department of Mathematics, University of Denver, 2280 S. Vine Street, Denver, CO 80208, USA email normes@du.edu, rpavlov@du.edu

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 $n$, and we present an example (due to Martin Delacourt) which shows that this monotonicity does not hold for numbers of extender sets (or follower sets) of words of length $n$.

Type
Research Article
Copyright
© Cambridge University Press, 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Hochman, M.. On the dynamics and recursive properties of multidimensional symbolic systems. Invent. Math. 176 (2009), 131167.Google Scholar
Kass, S. and Madden, K.. A sufficient condition for non-soficness of higher-dimensional subshifts. Proc. Amer. Math. Soc. 141 (2013), 38033816.Google Scholar
Lind, D. and Marcus, B.. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, 1995.CrossRefGoogle Scholar
Morse, M. and Hedlund, G. A.. Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940), 142.Google Scholar
Pavlov, R.. A class of nonsofic multidimensional shift spaces. Proc. Amer. Math. Soc. 141 (2013), 987996.Google Scholar
Pytheas Fogg, N.. Substitutions in Dynamics, Arithmetics and Combinatorics (Lecture Notes in Mathematics, 1794). Springer, Berlin, 2002.CrossRefGoogle Scholar