×

Random \(\mathbb{Z}^d\)-shifts of finite type. (English) Zbl 1369.37023

This article considers (multidimensional) subshifts of finite type by fixing a size \(n\), then forbidding each pattern of size \(n\), uniformly and independently (according to some parameter \(\alpha\)), and finally letting \(n\) go to infinity. It is shown that such systems are nonempty if and only if \(\alpha\) is bigger than the inverse of the alphabet cardinality. In this case they admit many periodic configurations; typical topological and periodic entropies are also computed, which give evidence that typical subshifts do not have any of the pathological properties that make symbolic dynamics so different in higher dimension than in dimension one. This work generalizes [the first author, Ann. Probab. 40, No. 2, 648–694 (2012; Zbl 1269.37009)] in two ways: by considering any dimension, and also by expliciting convergence rates of entropies.

MSC:

37B50 Multi-dimensional shifts of finite type, tiling dynamics (MSC2010)
37B10 Symbolic dynamics
37H10 Generation, random and stochastic difference and differential equations

Citations:

Zbl 1269.37009
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] E. Abbe, On the concentration of the number of solutions of random satisfiability formulas,, Random Structures Algorithms, 45, 362 (2014) · Zbl 1373.68300 · doi:10.1002/rsa.20501
[2] D. Achlioptas, On the solution-space geometry of random constraint satisfaction problems,, Random Structures Algorithms, 38, 251 (2011) · Zbl 1217.68156 · doi:10.1002/rsa.20323
[3] D. Achlioptas, Rigorous location of phase transitions in hard optimization problems,, Nature, 435, 759 (2005) · doi:10.1038/nature03602
[4] D. Achlioptas, The threshold for random k-SAT is \(2^k\log 2-O(k)\),, J. Amer. Math. Soc., 17, 947 (2004) · Zbl 1093.68075 · doi:10.1090/S0894-0347-04-00464-3
[5] R. Berger, The undecidability of the domino problem,, Mem. Amer. Math. Soc. No., 66 (1966) · Zbl 0199.30802
[6] R. Bowen, <em>Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms</em>,, Second revised edition (2008) · Zbl 1172.37001
[7] M. Boyle, Lower entropy factors of sofic systems,, Ergodic Theory and Dynamical Systems, 3, 541 (1983) · Zbl 0529.28014 · doi:10.1017/S0143385700002133
[8] M. Boyle, Multidimensional sofic shifts without separation and their factors,, Trans. Amer. Math. Soc., 362, 4617 (2010) · Zbl 1207.37011 · doi:10.1090/S0002-9947-10-05003-8
[9] R. Burton, Non-uniqueness of measures of maximal entropy for subshifts of finite type,, Ergodic Theory Dynam. Systems, 14, 213 (1994) · Zbl 0807.58023 · doi:10.1017/S0143385700007859
[10] M. Denker, <em>Ergodic Theory on Compact Spaces</em>,, Lecture Notes in Mathematics (1976) · Zbl 0328.28008
[11] N. J. Fine, Uniqueness theorems for periodic functions,, Proc. Amer. Math. Soc., 16, 109 (1965) · Zbl 0131.30203 · doi:10.1090/S0002-9939-1965-0174934-9
[12] E. Friedgut, Sharp thresholds of graph properties, and the k-sat problem,, With an appendix by Jean Bourgain, 12, 1017 (1999) · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7
[13] G. Grimmett, <em>Percolation</em>,, Second edition (1999) · Zbl 0926.60004 · doi:10.1007/978-3-662-03981-6
[14] M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems,, Invent. Math., 176, 131 (2009) · Zbl 1168.37002 · doi:10.1007/s00222-008-0161-7
[15] M. Hochman, A characterization of the entropies of multidimensional shifts of finite type,, Ann. of Math. (2), 171, 2011 (2010) · Zbl 1192.37022 · doi:10.4007/annals.2010.171.2011
[16] M. S. Keane, Ergodic theory and subshifts of finite type,, in Ergodic Theory, 35 (1989) · Zbl 0755.58033
[17] B. Kitchens, <em>Symbolic Dynamics. One-Sided, Two-Sided and Countable State Markov Shifts</em>,, Universitext (1998) · Zbl 0892.58020 · doi:10.1007/978-3-642-58822-8
[18] W. Krieger, On the subsystems of topological Markov chains,, Ergodic Theory and Dynamical Systems, 2, 195 (1982) · Zbl 0508.54032 · doi:10.1017/S0143385700001516
[19] F. Krząkała, Gibbs states and the set of solutions of random constraint satisfaction problems,, Proc. Natl. Acad. Sci. USA, 104, 10318 (2007) · Zbl 1190.68031 · doi:10.1073/pnas.0703685104
[20] S. J. Lightwood, Morphisms from non-periodic \(\mathbb Z^2\)-subshifts. I. Constructing embeddings from homomorphisms,, Ergodic Theory Dynam. Systems, 23, 587 (2003) · Zbl 1031.37017 · doi:10.1017/S014338570200130X
[21] S. J. Lightwood, Morphisms from non-periodic \(\mathbb Z^2\) subshifts. II. Constructing homomorphisms to square-filling mixing shifts of finite type,, Ergodic Theory Dynam. Systems, 24, 1227 (2004) · Zbl 1069.37011 · doi:10.1017/S0143385704000276
[22] D. Lind, A zeta function for \(\mathbbZ^d\)-actions,, in Ergodic Theory of \(\mathbbZ^d\) Actions (Warwick, 1993 (1996) · Zbl 0881.58052 · doi:10.1017/CBO9780511662812.019
[23] D. Lind, <em>An Introduction to Symbolic Dynamics and Coding</em>,, Cambridge University Press (1995) · Zbl 1106.37301 · doi:10.1017/CBO9780511626302
[24] D. A. Lind, The entropies of topological Markov shifts and a related class of algebraic integers,, Ergodic Theory Dynam. Systems, 4, 283 (1984) · Zbl 0546.58035 · doi:10.1017/S0143385700002443
[25] B. Marcus, Factors and extensions of full shifts,, Monatsh. Math., 88, 239 (1979) · Zbl 0432.54036 · doi:10.1007/BF01295238
[26] K. McGoff, Random subshifts of finite type,, Ann. Probab., 40, 648 (2012) · Zbl 1269.37009 · doi:10.1214/10-AOP636
[27] M. Morse, Symbolic Dynamics,, Amer. J. Math., 60, 815 (1938) · JFM 64.0798.04 · doi:10.2307/2371264
[28] W. Parry, Intrinsic Markov chains,, Trans. Amer. Math. Soc., 112, 55 (1964) · Zbl 0127.35301 · doi:10.1090/S0002-9947-1964-0161372-1
[29] A. Quas, Entropy gaps and locally maximal entropy in \(\mathbb Z^d\) subshifts,, Ergodic Theory Dynam. Systems, 23, 1227 (2003) · Zbl 1039.37008 · doi:10.1017/S0143385702001761
[30] D. Ruelle, <em>Thermodynamic Formalism. The Mathematical Structures of Equilibrium Statistical Mechanics</em>,, Second edition (2004) · Zbl 1062.82001 · doi:10.1017/CBO9780511617546
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.