# 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 and Continuous Dynamical Systems, 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 and Continuous Dynamical Systems, 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 and Continuous Dynamical Systems, 2013, 33 (6) : 2451-2467. doi: 10.3934/dcds.2013.33.2451 [4] Azmeer Nordin, Mohd Salmi Md Noorani. Counting finite orbits for the flip systems of shifts of finite type. Discrete and Continuous Dynamical Systems, 2021, 41 (10) : 4515-4529. doi: 10.3934/dcds.2021046 [5] Kazuhiro Kawamura. Mean dimension of shifts of finite type and of generalized inverse limits. Discrete and Continuous Dynamical Systems, 2020, 40 (8) : 4767-4775. doi: 10.3934/dcds.2020200 [6] 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 [7] Marcelo Sobottka. Topological quasi-group shifts. Discrete and Continuous Dynamical Systems, 2007, 17 (1) : 77-93. doi: 10.3934/dcds.2007.17.77 [8] Felix X.-F. Ye, Hong Qian. Stochastic dynamics Ⅱ: Finite random dynamical systems, linear representation, and entropy production. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 4341-4366. doi: 10.3934/dcdsb.2019122 [9] Christopher Hoffman. Subshifts of finite type which have completely positive entropy. Discrete and Continuous Dynamical Systems, 2011, 29 (4) : 1497-1516. doi: 10.3934/dcds.2011.29.1497 [10] Silvère Gangloff. Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type. Discrete and Continuous Dynamical Systems, 2022, 42 (2) : 931-988. doi: 10.3934/dcds.2021143 [11] Katrin Gelfert. Lower bounds for the topological entropy. Discrete and Continuous Dynamical Systems, 2005, 12 (3) : 555-565. doi: 10.3934/dcds.2005.12.555 [12] Jaume Llibre. Brief survey on the topological entropy. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3363-3374. doi: 10.3934/dcdsb.2015.20.3363 [13] Rafael Alcaraz Barrera. Topological and ergodic properties of symmetric sub-shifts. Discrete and Continuous Dynamical Systems, 2014, 34 (11) : 4459-4486. doi: 10.3934/dcds.2014.34.4459 [14] Dongkui Ma, Min Wu. Topological pressure and topological entropy of a semigroup of maps. Discrete and Continuous Dynamical Systems, 2011, 31 (2) : 545-557 . doi: 10.3934/dcds.2011.31.545 [15] Piotr Oprocha, Paweł Potorski. Topological mixing, knot points and bounds of topological entropy. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3547-3564. doi: 10.3934/dcdsb.2015.20.3547 [16] Manfred Denker, Yuri Kifer, Manuel Stadlbauer. Thermodynamic formalism for random countable Markov shifts. Discrete and Continuous Dynamical Systems, 2008, 22 (1&2) : 131-164. doi: 10.3934/dcds.2008.22.131 [17] Manfred Denker, Yuri Kifer, Manuel Stadlbauer. Corrigendum to: Thermodynamic formalism for random countable Markov shifts. Discrete and Continuous Dynamical Systems, 2015, 35 (1) : 593-594. doi: 10.3934/dcds.2015.35.593 [18] Timothy Chumley, Renato Feres. Entropy production in random billiards. Discrete and Continuous Dynamical Systems, 2021, 41 (3) : 1319-1346. doi: 10.3934/dcds.2020319 [19] Boris Hasselblatt, Zbigniew Nitecki, James Propp. Topological entropy for nonuniformly continuous maps. Discrete and Continuous Dynamical Systems, 2008, 22 (1&2) : 201-213. doi: 10.3934/dcds.2008.22.201 [20] Michał Misiurewicz. On Bowen's definition of topological entropy. Discrete and Continuous Dynamical Systems, 2004, 10 (3) : 827-833. doi: 10.3934/dcds.2004.10.827

2020 Impact Factor: 1.392