American Institute of Mathematical Sciences

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

Shifts of finite type and random substitutions

Philipp Gohlke 1, , Dan Rust 1, and  Timo Spindeler 2,

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.

Keywords: Random substitutions, shifts of finite type, topological entropy.
Mathematics Subject Classification: Primary: 37B10, 37A50; Secondary: 37B40, 52C23.
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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[5]

T. Fernique and N. Ollinger, Combinatorial substitutions and sofic tilings, Proceedings of JAC, (2010), 100-110. Google Scholar

[6]

N. P. Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, vol. 1794 of Lecture Notes in Math., Springer-Verlag, 2002. doi: 10.1007/b13861. Google Scholar

[7]

F. Gähler and E. Miro, Topology of the random fibonacci tiling space, Acta Phys. Pol. A, 126 (2014), 564-567. Google Scholar

[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. Google Scholar

[9]

P. Gohlke, On a family of semi-compatible random substitutions, Masters Thesis, Bielefeld University, 2017.Google Scholar

[10]

C. Goodman-Strauss, Matching rules and substitution tilings, Annals of Mathematics, 147 (1998), 181-223. doi: 10.2307/120988. Google Scholar

[11]

O. D. Jones, Large deviations for supercritical multitype branching processes, J. Appl. Probab., 41 (2004), 703-720. doi: 10.1239/jap/1091543420. Google Scholar

[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. Google Scholar

[13] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge Univ. Press, 1995. doi: 10.1017/CBO9780511626302. Google Scholar
[14]

M. Moll, On a family of random noble means substitutions, Ph.D. Thesis, Bielefeld University, URL http://pub.uni-bielefeld.de/publication/2637807.Google Scholar

[15]

M. Moll, Diffraction of random noble means words, J. Stat. Phys., 156 (2014), 1221-1236. doi: 10.1007/s10955-014-1047-2. Google Scholar

[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. Google Scholar

[17]

J. Peyrière, Substitutions aléatoires itérés, Sémin. Théor. Nombres, 1–9, URL http://www.jstor.org/stable/44166375.Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[5]

T. Fernique and N. Ollinger, Combinatorial substitutions and sofic tilings, Proceedings of JAC, (2010), 100-110. Google Scholar

[6]

N. P. Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, vol. 1794 of Lecture Notes in Math., Springer-Verlag, 2002. doi: 10.1007/b13861. Google Scholar

[7]

F. Gähler and E. Miro, Topology of the random fibonacci tiling space, Acta Phys. Pol. A, 126 (2014), 564-567. Google Scholar

[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. Google Scholar

[9]

P. Gohlke, On a family of semi-compatible random substitutions, Masters Thesis, Bielefeld University, 2017.Google Scholar

[10]

C. Goodman-Strauss, Matching rules and substitution tilings, Annals of Mathematics, 147 (1998), 181-223. doi: 10.2307/120988. Google Scholar

[11]

O. D. Jones, Large deviations for supercritical multitype branching processes, J. Appl. Probab., 41 (2004), 703-720. doi: 10.1239/jap/1091543420. Google Scholar

[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. Google Scholar

[13] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge Univ. Press, 1995. doi: 10.1017/CBO9780511626302. Google Scholar
[14]

M. Moll, On a family of random noble means substitutions, Ph.D. Thesis, Bielefeld University, URL http://pub.uni-bielefeld.de/publication/2637807.Google Scholar

[15]

M. Moll, Diffraction of random noble means words, J. Stat. Phys., 156 (2014), 1221-1236. doi: 10.1007/s10955-014-1047-2. Google Scholar

[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. Google Scholar

[17]

J. Peyrière, Substitutions aléatoires itérés, Sémin. Théor. Nombres, 1–9, URL http://www.jstor.org/stable/44166375.Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

Figure 1.  Graph $ G_{A} $ of the SFT $ X_{A} $ in Example 5.8
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Graph $ G $ with labelled edges for Example 5.11
Figure Options

Download full-size image

Download as PowerPoint slide

[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, 2019, 24 (8) : 4341-4366. doi: 10.3934/dcdsb.2019122
[7]

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
[8]

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
[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

2018 Impact Factor: 1.143

Tools

Metrics

  • PDF downloads (59)
  • HTML views (144)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences