AMS :: Proceedings of the American Mathematical Society

On word complexity and topological entropy of random substitution subshifts
HTML articles powered by AMS MathViewer

Proc. Amer. Math. Soc. 152 (2024), 4361-4377

DOI: https://doi.org/10.1090/proc/16893

Published electronically: August 23, 2024

HTML | PDF | Request permission

Abstract:

We consider word complexity and topological entropy for random substitution subshifts. In contrast to previous work, we do not assume that the underlying random substitution is compatible. We show that the subshift of a primitive random substitution has zero topological entropy if and only if it can be obtained as the subshift of a deterministic substitution, answering in the affirmative an open question of Rust and Spindeler [Indag. Math. (N.S.) 29 (2018), pp. 1131–1155]. For constant length primitive random substitutions, we develop a systematic approach to calculating the topological entropy of the associated subshift. Further, we prove lower and upper bounds that hold even without primitivity. For subshifts of non-primitive random substitutions, we show that the complexity function can exhibit features not possible in the deterministic or primitive random setting, such as intermediate growth, and provide a partial classification of the permissible complexity functions for subshifts of constant length random substitutions.

References

Michael Baake, Timo Spindeler, and Nicolae Strungaru, Diffraction of compatible random substitutions in one dimension, Indag. Math. (N.S.) 29 (2018), no. 4, 1031–1071. MR 3826513, DOI 10.1016/j.indag.2018.05.008
V. Berthé and M. Rigo, editors, Combinatorics, Automata and Number Theory, Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2010.
Sébastien Ferenczi, Complexity of sequences and dynamical systems, Discrete Math. 206 (1999), no. 1-3, 145–154. Combinatorics and number theory (Tiruchirappalli, 1996). MR 1665394, DOI 10.1016/S0012-365X(98)00400-2
C. Godrèche and J. M. Luck, Quasiperiodicity and randomness in tilings of the plane, J. Statist. Phys. 55 (1989), no. 1-2, 1–28. MR 1003500, DOI 10.1007/BF01042590
Philipp Gohlke, Inflation word entropy for semi-compatible random substitutions, Monatsh. Math. 192 (2020), no. 1, 93–110. MR 4087473, DOI 10.1007/s00605-020-01380-0
P. Gohlke, A. Mitchell, D. Rust, and T. Samuel, Measure theoretic entropy of random substitution subshifts, Ann. Henri Poincaré 24 (2023), no. 1, 277–323. MR 4533524, DOI 10.1007/s00023-022-01212-x
Philipp Gohlke, Dan Rust, and Timo Spindeler, Shifts of finite type and random substitutions, Discrete Contin. Dyn. Syst. 39 (2019), no. 9, 5085–5103. MR 3986321, DOI 10.3934/dcds.2019206
Philipp Gohlke and Timo Spindeler, Ergodic frequency measures for random substitutions, Studia Math. 255 (2020), no. 3, 265–301. MR 4142755, DOI 10.4064/sm181026-14-8
David Koslicki, Substitution Markov chains with applications to molecular evolution, ProQuest LLC, Ann Arbor, MI, 2012. Thesis (Ph.D.)–The Pennsylvania State University. MR 3067958
Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092, DOI 10.1017/CBO9780511626302
Eden Delight Miro, Dan Rust, Lorenzo Sadun, and Gwendolyn Tadeo, Topological mixing of random substitutions, Israel J. Math. 255 (2023), no. 1, 123–153. MR 4619530, DOI 10.1007/s11856-022-2406-3
Andrew Mitchell and Alex Rutar, Multifractal analysis of measures arising from random substitutions, Comm. Math. Phys. 405 (2024), no. 3, Paper No. 63, 44. MR 4709102, DOI 10.1007/s00220-023-04895-3
Marston Morse and Gustav A. Hedlund, Symbolic Dynamics, Amer. J. Math. 60 (1938), no. 4, 815–866. MR 1507944, DOI 10.2307/2371264
Johan Nilsson, On the entropy of a family of random substitutions, Monatsh. Math. 168 (2012), no. 3-4, 563–577. MR 2993964, DOI 10.1007/s00605-012-0401-1
Jean-Jacques Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, Automata, languages and programming (Antwerp, 1984) Lecture Notes in Comput. Sci., vol. 172, Springer, Berlin, 1984, pp. 380–389 (French, with English summary). MR 784265, DOI 10.1007/3-540-13345-3_{3}4
Martine Queffélec, Substitution dynamical systems—spectral analysis, 2nd ed., Lecture Notes in Mathematics, vol. 1294, Springer-Verlag, Berlin, 2010. MR 2590264, DOI 10.1007/978-3-642-11212-6
Dan Rust, Periodic points in random substitution subshifts, Monatsh. Math. 193 (2020), no. 3, 683–704. MR 4153337, DOI 10.1007/s00605-020-01458-9
Dan Rust and Timo Spindeler, Dynamical systems arising from random substitutions, Indag. Math. (N.S.) 29 (2018), no. 4, 1131–1155. MR 3826518, DOI 10.1016/j.indag.2018.05.013
T. Spindeler, On Spectral Theory of Compatible Random Inflation Systems, Ph. D. Thesis, Bielefeld University, 2017.
David Josiah Wing, Notions of Complexity in Substitution Dynamical Systems, ProQuest LLC, Ann Arbor, MI, 2011. Thesis (Ph.D.)–Oregon State University. MR 2912181