## Classification of sofic projective subdynamics of multidimensional shifts of finite type

HTML articles powered by AMS MathViewer

- by Ronnie Pavlov and Michael Schraudner PDF
- Trans. Amer. Math. Soc.
**367**(2015), 3371-3421

## Abstract:

Motivated by Hochman’s notion of subdynamics of a $\mathbb {Z}^d$ subshift (2009), we define and examine the projective subdynamics of $\mathbb {Z}^d$ shifts of finite type (SFTs) where we restrict not only the action but also the phase space. We show that any $\mathbb {Z}$ sofic shift of positive entropy is the projective subdynamics of a $\mathbb {Z}^2$ ($\mathbb {Z}^d$) SFT, and that there is a simple condition characterizing the class of zero-entropy $\mathbb {Z}$ sofic shifts which are not the projective subdynamics of any $\mathbb {Z}^2$ SFT. We define notions of stable and unstable subdynamics in analogy with the notions of stable and unstable limit sets in cellular automata theory, and discuss how our results fit into this framework. One-dimensional strictly sofic shifts of positive entropy admit both a stable and an unstable realization, whereas $\mathbb {Z}$ SFTs only allow for stable realizations and a particular class of zero-entropy proper $\mathbb {Z}$ sofics only allows for an unstable realization. Finally, we prove that the union of finitely many $\mathbb {Z}^k$ subshifts, all of which are realizable in $\mathbb {Z}^d$ SFTs, is again realizable when it contains at least two periodic points, that the projective subdynamics of $\mathbb {Z}^2$ SFTs with the uniform filling property (UFP) are always stable, thus sofic, and we exhibit a class of non-sofic $\mathbb {Z}$ subshifts which are not the projective subdynamics of any $\mathbb {Z}^d$ SFT.## References

- N. Aubrun and M. Sablik,
*Simulation of recursively enumerable subshifts by two dimensional SFT and a generalization*, preprint. - Paul Balister, Béla Bollobás, and Anthony Quas,
*Entropy along convex shapes, random tilings and shifts of finite type*, Illinois J. Math.**46**(2002), no. 3, 781–795. MR**1951240** - Alexis Ballier, Pierre Guillon, and Jarkko Kari,
*Limit sets of stable and unstable cellular automata*, Fund. Inform.**110**(2011), no. 1-4, 45–57. MR**2868073**, DOI 10.3233/FI-2011-527 - Robert Berger,
*The undecidability of the domino problem*, Mem. Amer. Math. Soc.**66**(1966), 72. MR**216954** - Mike Boyle, Ronnie Pavlov, and Michael Schraudner,
*Multidimensional sofic shifts without separation and their factors*, Trans. Amer. Math. Soc.**362**(2010), no. 9, 4617–4653. MR**2645044**, DOI 10.1090/s0002-9947-10-05003-8 - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein,
*Introduction to algorithms*, 2nd ed., MIT Press, Cambridge, MA; McGraw-Hill Book Co., Boston, MA, 2001. MR**1848805** - Bruno Durand, Andrei Romashchenko, and Alexander Shen,
*Fixed-point tile sets and their applications*, J. Comput. System Sci.**78**(2012), no. 3, 731–764. MR**2900032**, DOI 10.1016/j.jcss.2011.11.001 - N. Pytheas Fogg,
*Substitutions in dynamics, arithmetics and combinatorics*, Lecture Notes in Mathematics, vol. 1794, Springer-Verlag, Berlin, 2002. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. MR**1970385**, DOI 10.1007/b13861 - Enrico Formenti and Petr Kůrka,
*Subshift attractors of cellular automata*, Nonlinearity**20**(2007), no. 1, 105–117. MR**2285107**, DOI 10.1088/0951-7715/20/1/007 - Michael Hochman,
*On the dynamics and recursive properties of multidimensional symbolic systems*, Invent. Math.**176**(2009), no. 1, 131–167. MR**2485881**, DOI 10.1007/s00222-008-0161-7 - Lyman Porter Hurd,
*The application of formal language theory to the dynamical behavior of cellular automata*, ProQuest LLC, Ann Arbor, MI, 1988. Thesis (Ph.D.)–Princeton University. MR**2636496** - Aimee Johnson, Steve Kass, and Kathleen Madden,
*Projectional entropy in higher dimensional shifts of finite type*, Complex Systems**17**(2007), no. 3, 243–257. MR**2373706** - Jarkko Kari,
*Rice’s theorem for the limit sets of cellular automata*, Theoret. Comput. Sci.**127**(1994), no. 2, 229–254. MR**1275817**, DOI 10.1016/0304-3975(94)90041-8 - P. Kurka,
*Topological dynamics of one-dimensional cellular automata*, Encyclopedia of Complexity and System Sciences Part 20, Springer-Verlag (2009), 9246–9268. - Douglas Lind and Brian Marcus,
*An introduction to symbolic dynamics and coding*, Cambridge University Press, Cambridge, 1995. MR**1369092**, DOI 10.1017/CBO9780511626302 - Alejandro Maass,
*On the sofic limit sets of cellular automata*, Ergodic Theory Dynam. Systems**15**(1995), no. 4, 663–684. MR**1346395**, DOI 10.1017/S0143385700008609 - Alejandro Maass,
*Some coded systems that are not unstable limit sets of cellular automata*, Cellular automata and cooperative systems (Les Houches, 1992) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 396, Kluwer Acad. Publ., Dordrecht, 1993, pp. 433–449. MR**1267985** - Raphael M. Robinson,
*Undecidability and nonperiodicity for tilings of the plane*, Invent. Math.**12**(1971), 177–209. MR**297572**, DOI 10.1007/BF01418780 - E. Arthur Robinson Jr. and Ayşe A. Şahin,
*Mixing properties of nearly maximal entropy measures for $\textbf {Z}^d$ shifts of finite type*. part 1, Colloq. Math.**84/85**(2000), no. part 1, 43–50. Dedicated to the memory of Anzelm Iwanik. MR**1778838**, DOI 10.4064/cm-84/85-1-43-50 - M. Schraudner,
*One-dimensional projective subdynamics of uniformly mixing $\mathbb {Z}^D$ shifts of finite type*, Ergodic Theory Dynam. Systems., published online July 3, 2014, DOI 10.1017/etds.2014.2. - Thomas Ward,
*Automorphisms of $\mathbf Z^d$-subshifts of finite type*, Indag. Math. (N.S.)**5**(1994), no. 4, 495–504. MR**1307966**, DOI 10.1016/0019-3577(94)90020-5

## Additional Information

**Ronnie Pavlov**- Affiliation: Department of Mathematics, University of British Columbia, 1984 Mathematics Road, Vancouver, British Columbia V6T 1Z2, Canada
- MR Author ID: 845553
- Email: rpavlov@du.edu
**Michael Schraudner**- Affiliation: Centro de Modelamiento Matemático, Universidad de Chile, Av. Blanco Encalada 2120, Santiago, Chile
- Email: mschraudner@dim.uchile.cl
- Received by editor(s): January 4, 2012
- Received by editor(s) in revised form: May 6, 2013
- Published electronically: November 4, 2014
- Additional Notes: The second author was partially supported by Basal project CMM, Universidad de Chile, by FONDECYT projects 3080008 and 1100719 and by CONICYT Proyecto Anillo ACT 1103.
- © Copyright 2014 by the authors
- Journal: Trans. Amer. Math. Soc.
**367**(2015), 3371-3421 - MSC (2010): Primary 37B50; Secondary 37B10, 37B40
- DOI: https://doi.org/10.1090/S0002-9947-2014-06259-4
- MathSciNet review: 3314811