# American Institute of Mathematical Sciences

September  2019, 39(9): 5085-5103. doi: 10.3934/dcds.2019206

## Shifts of finite type and random substitutions

 1 Fakultät für Mathematik, Universität Bielefeld, Postfach 100131, 33501 Bielefeld, Germany 2 Department of Mathematical and Statistical Sciences, 632 CAB, University of Alberta, Edmonton, AB, T6G 2G1, Canada

Received  May 2018 Revised  January 2019 Published  May 2019

We prove that every topologically transitive shift of finite type in one dimension is topologically conjugate to a subshift arising from a primitive random substitution on a finite alphabet. As a result, we show that the set of values of topological entropy which can be attained by random substitution subshifts contains the logarithm of all Perron numbers and so is dense in the positive real numbers. We also provide an independent proof of this density statement using elementary methods.

Citation: Philipp Gohlke, Dan Rust, Timo Spindeler. Shifts of finite type and random substitutions. Discrete & Continuous Dynamical Systems - A, 2019, 39 (9) : 5085-5103. doi: 10.3934/dcds.2019206
##### References:
 [1] M. Baake and U. Grimm, Aperiodic Order. Volume 1: A Mathematical Invitation, vol. 149 of Encyclopedia Math. Appl., Cambridge Univ. Press, 2013. doi: 10.1017/CBO9781139025256. [2] M. Baake, T. Spindeler and N. Strungaru, Diffraction of compatible random substitutions in one dimension, Indag. Math. (N.S.), 29 (2018), 1031-1071. doi: 10.1016/j.indag.2018.05.008. [3] F. M. Dekking and R. W. J. Meester, On the structure of Mandelbrot's percolation process and other random Cantor sets, J. Stat. Phys., 58 (1990), 1109-1126. doi: 10.1007/BF01026566. [4] R. Diestel, Graph Theory, vol. 173 of Graduate Texts in Mathematics, 5th edition, Springer, Berlin, 2017. doi: 10.1007/978-3-662-53622-3. [5] T. Fernique and N. Ollinger, Combinatorial substitutions and sofic tilings, Proceedings of JAC, (2010), 100-110. [6] N. P. Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, vol. 1794 of Lecture Notes in Math., Springer-Verlag, 2002. doi: 10.1007/b13861. [7] F. Gähler and E. Miro, Topology of the random fibonacci tiling space, Acta Phys. Pol. A, 126 (2014), 564-567. [8] C. Godrèche and J. M. Luck, Quasiperiodicity and randomness in tilings of the plane, J. Stat. Phys., 55 (1989), 1-28. doi: 10.1007/BF01042590. [9] P. Gohlke, On a family of semi-compatible random substitutions, Masters Thesis, Bielefeld University, 2017. [10] C. Goodman-Strauss, Matching rules and substitution tilings, Annals of Mathematics, 147 (1998), 181-223. doi: 10.2307/120988. [11] O. D. Jones, Large deviations for supercritical multitype branching processes, J. Appl. Probab., 41 (2004), 703-720. doi: 10.1239/jap/1091543420. [12] D. Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Th. Dynam. Syst., 4 (1984), 283-300. doi: 10.1017/S0143385700002443. [13] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge Univ. Press, 1995. doi: 10.1017/CBO9780511626302. [14] M. Moll, On a family of random noble means substitutions, Ph.D. Thesis, Bielefeld University, URL http://pub.uni-bielefeld.de/publication/2637807. [15] M. Moll, Diffraction of random noble means words, J. Stat. Phys., 156 (2014), 1221-1236. doi: 10.1007/s10955-014-1047-2. [16] J. Nilsson, On the entropy of a family of random substitutions, Monatsh. Math., 168 (2012), 563-577. doi: 10.1007/s00605-012-0401-1. [17] J. Peyrière, Substitutions aléatoires itérés, Sémin. Théor. Nombres, 1–9, URL http://www.jstor.org/stable/44166375. [18] M. Queffélec, Substitution Dynamical Systems–Spectral Analysis, vol. 1294 of Lecture Notes in Mathematics, 2nd edition, Springer-Verlag, Berlin, 2010. doi: 10.1007/978-3-642-11212-6. [19] G. Rozenberg and A. Salomaa, The mathematical theory of L systems, Advances in Information Systems Science, Plenum Press, New York, 6 (1976), 161–206. [20] D. Rust and T. Spindeler, Dynamical systems arising from random substitutions, Indag. Math. (N.S.), 29 (2018), 1131-1155. doi: 10.1016/j.indag.2018.05.013.

show all references

##### References:
 [1] M. Baake and U. Grimm, Aperiodic Order. Volume 1: A Mathematical Invitation, vol. 149 of Encyclopedia Math. Appl., Cambridge Univ. Press, 2013. doi: 10.1017/CBO9781139025256. [2] M. Baake, T. Spindeler and N. Strungaru, Diffraction of compatible random substitutions in one dimension, Indag. Math. (N.S.), 29 (2018), 1031-1071. doi: 10.1016/j.indag.2018.05.008. [3] F. M. Dekking and R. W. J. Meester, On the structure of Mandelbrot's percolation process and other random Cantor sets, J. Stat. Phys., 58 (1990), 1109-1126. doi: 10.1007/BF01026566. [4] R. Diestel, Graph Theory, vol. 173 of Graduate Texts in Mathematics, 5th edition, Springer, Berlin, 2017. doi: 10.1007/978-3-662-53622-3. [5] T. Fernique and N. Ollinger, Combinatorial substitutions and sofic tilings, Proceedings of JAC, (2010), 100-110. [6] N. P. Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, vol. 1794 of Lecture Notes in Math., Springer-Verlag, 2002. doi: 10.1007/b13861. [7] F. Gähler and E. Miro, Topology of the random fibonacci tiling space, Acta Phys. Pol. A, 126 (2014), 564-567. [8] C. Godrèche and J. M. Luck, Quasiperiodicity and randomness in tilings of the plane, J. Stat. Phys., 55 (1989), 1-28. doi: 10.1007/BF01042590. [9] P. Gohlke, On a family of semi-compatible random substitutions, Masters Thesis, Bielefeld University, 2017. [10] C. Goodman-Strauss, Matching rules and substitution tilings, Annals of Mathematics, 147 (1998), 181-223. doi: 10.2307/120988. [11] O. D. Jones, Large deviations for supercritical multitype branching processes, J. Appl. Probab., 41 (2004), 703-720. doi: 10.1239/jap/1091543420. [12] D. Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Th. Dynam. Syst., 4 (1984), 283-300. doi: 10.1017/S0143385700002443. [13] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge Univ. Press, 1995. doi: 10.1017/CBO9780511626302. [14] M. Moll, On a family of random noble means substitutions, Ph.D. Thesis, Bielefeld University, URL http://pub.uni-bielefeld.de/publication/2637807. [15] M. Moll, Diffraction of random noble means words, J. Stat. Phys., 156 (2014), 1221-1236. doi: 10.1007/s10955-014-1047-2. [16] J. Nilsson, On the entropy of a family of random substitutions, Monatsh. Math., 168 (2012), 563-577. doi: 10.1007/s00605-012-0401-1. [17] J. Peyrière, Substitutions aléatoires itérés, Sémin. Théor. Nombres, 1–9, URL http://www.jstor.org/stable/44166375. [18] M. Queffélec, Substitution Dynamical Systems–Spectral Analysis, vol. 1294 of Lecture Notes in Mathematics, 2nd edition, Springer-Verlag, Berlin, 2010. doi: 10.1007/978-3-642-11212-6. [19] G. Rozenberg and A. Salomaa, The mathematical theory of L systems, Advances in Information Systems Science, Plenum Press, New York, 6 (1976), 161–206. [20] D. Rust and T. Spindeler, Dynamical systems arising from random substitutions, Indag. Math. (N.S.), 29 (2018), 1131-1155. doi: 10.1016/j.indag.2018.05.013.
Graph $G_{A}$ of the SFT $X_{A}$ in Example 5.8
Graph $G$ with labelled edges for Example 5.11
 [1] Kevin McGoff, Ronnie Pavlov. Random $\mathbb{Z}^d$-shifts of finite type. Journal of Modern Dynamics, 2016, 10: 287-330. doi: 10.3934/jmd.2016.10.287 [2] Bing Li, Tuomas Sahlsten, Tony Samuel. Intermediate $\beta$-shifts of finite type. Discrete & Continuous Dynamical Systems - A, 2016, 36 (1) : 323-344. doi: 10.3934/dcds.2016.36.323 [3] Dominik Kwietniak. Topological entropy and distributional chaos in hereditary shifts with applications to spacing shifts and beta shifts. Discrete & Continuous Dynamical Systems - A, 2013, 33 (6) : 2451-2467. doi: 10.3934/dcds.2013.33.2451 [4] Anthony Quas, Terry Soo. Weak mixing suspension flows over shifts of finite type are universal. Journal of Modern Dynamics, 2012, 6 (4) : 427-449. doi: 10.3934/jmd.2012.6.427 [5] Marcelo Sobottka. Topological quasi-group shifts. Discrete & Continuous Dynamical Systems - A, 2007, 17 (1) : 77-93. doi: 10.3934/dcds.2007.17.77 [6] Felix X.-F. Ye, Hong Qian. Stochastic dynamics Ⅱ: Finite random dynamical systems, linear representation, and entropy production. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-26. doi: 10.3934/dcdsb.2019122 [7] Christopher Hoffman. Subshifts of finite type which have completely positive entropy. Discrete & Continuous Dynamical Systems - A, 2011, 29 (4) : 1497-1516. doi: 10.3934/dcds.2011.29.1497 [8] Rafael Alcaraz Barrera. Topological and ergodic properties of symmetric sub-shifts. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4459-4486. doi: 10.3934/dcds.2014.34.4459 [9] Katrin Gelfert. Lower bounds for the topological entropy. Discrete & Continuous Dynamical Systems - A, 2005, 12 (3) : 555-565. doi: 10.3934/dcds.2005.12.555 [10] Jaume Llibre. Brief survey on the topological entropy. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3363-3374. doi: 10.3934/dcdsb.2015.20.3363 [11] Manfred Denker, Yuri Kifer, Manuel Stadlbauer. Thermodynamic formalism for random countable Markov shifts. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 131-164. doi: 10.3934/dcds.2008.22.131 [12] Manfred Denker, Yuri Kifer, Manuel Stadlbauer. Corrigendum to: Thermodynamic formalism for random countable Markov shifts. Discrete & Continuous Dynamical Systems - A, 2015, 35 (1) : 593-594. doi: 10.3934/dcds.2015.35.593 [13] Dongkui Ma, Min Wu. Topological pressure and topological entropy of a semigroup of maps. Discrete & Continuous Dynamical Systems - A, 2011, 31 (2) : 545-556. doi: 10.3934/dcds.2011.31.545 [14] Piotr Oprocha, Paweł Potorski. Topological mixing, knot points and bounds of topological entropy. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3547-3564. doi: 10.3934/dcdsb.2015.20.3547 [15] Boris Hasselblatt, Zbigniew Nitecki, James Propp. Topological entropy for nonuniformly continuous maps. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 201-213. doi: 10.3934/dcds.2008.22.201 [16] Michał Misiurewicz. On Bowen's definition of topological entropy. Discrete & Continuous Dynamical Systems - A, 2004, 10 (3) : 827-833. doi: 10.3934/dcds.2004.10.827 [17] Wolfgang Krieger, Kengo Matsumoto. Markov-Dyck shifts, neutral periodic points and topological conjugacy. Discrete & Continuous Dynamical Systems - A, 2019, 39 (1) : 1-18. doi: 10.3934/dcds.2019001 [18] Kengo Matsumoto. On the Markov-Dyck shifts of vertex type. Discrete & Continuous Dynamical Systems - A, 2016, 36 (1) : 403-422. doi: 10.3934/dcds.2016.36.403 [19] Jean-Pierre Conze, Y. Guivarc'h. Ergodicity of group actions and spectral gap, applications to random walks and Markov shifts. Discrete & Continuous Dynamical Systems - A, 2013, 33 (9) : 4239-4269. doi: 10.3934/dcds.2013.33.4239 [20] Yujun Zhu. Preimage entropy for random dynamical systems. Discrete & Continuous Dynamical Systems - A, 2007, 18 (4) : 829-851. doi: 10.3934/dcds.2007.18.829

2017 Impact Factor: 1.179

## Tools

Article outline

Figures and Tables