Article Contents
Article Contents

# Random $\mathbb{Z}^d$-shifts of finite type

• In this work we consider an ensemble of random $\mathbb{Z}^d$-shifts of finite type ($\mathbb{Z}^d$-SFTs) and prove several results concerning the behavior of typical systems with respect to emptiness, entropy, and periodic points. These results generalize statements made in [26] regarding the case $d=1$.
Let $\mathcal{A}$ be a finite set, and let $d \geq 1$. For $n$ in $\mathbb{N}$ and $\alpha$ in $[0,1]$, define a random subset $\omega$ of $\mathcal{A}^{[1,n]^d}$ by independently including each pattern in $\mathcal{A}^{[1,n]^d}$ with probability $\alpha$. Let $X_{\omega}$ be the (random) $\mathbb{Z}^d$-SFT built from the set $\omega$. For each $\alpha \in [0,1]$ and $n$ tending to infinity, we compute the limit of the probability that $X_{\omega}$ is empty, as well as the limiting distribution of entropy of $X_{\omega}$. Furthermore, we show that the probability of obtaining a nonempty system without periodic points tends to zero.
For $d>1$, the class of $\mathbb{Z}^d$-SFTs is known to contain strikingly different behavior than is possible within the class of $\mathbb{Z}$-SFTs. Nonetheless, the results of this work suggest a new heuristic: typical $\mathbb{Z}^d$-SFTs have similar properties to their $\mathbb{Z}$-SFT counterparts.
Mathematics Subject Classification: Primary: 37B50; Secondary: 37B10, 37H99.

 Citation:

•  [1] E. Abbe and A. Montanari, On the concentration of the number of solutions of random satisfiability formulas, Random Structures Algorithms, 45 (2014), 362-382.doi: 10.1002/rsa.20501. [2] D. Achlioptas, A. Coja-Oghlan and F. Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, Random Structures Algorithms, 38 (2011), 251-268.doi: 10.1002/rsa.20323. [3] D. Achlioptas, A. Naor and Y. Peres, Rigorous location of phase transitions in hard optimization problems, Nature, 435 (2005), 759-764.doi: 10.1038/nature03602. [4] D. Achlioptas and Y. Peres, The threshold for random k-SAT is $2^k\log 2-O(k)$, J. Amer. Math. Soc., 17 (2004), 947-973.doi: 10.1090/S0894-0347-04-00464-3. [5] R. Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. No., 66 (1966), 72pp. [6] R. Bowen, Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms, Second revised edition, With a preface by David Ruelle, Edited by Jean-René Chazottes, Lecture Notes in Mathematics, 470, Springer-Verlag, Berlin, 2008. [7] M. Boyle, Lower entropy factors of sofic systems, Ergodic Theory and Dynamical Systems, 3 (1983), 541-557.doi: 10.1017/S0143385700002133. [8] M. Boyle, R. Pavlov and M. Schraudner, Multidimensional sofic shifts without separation and their factors, Trans. Amer. Math. Soc., 362 (2010), 4617-4653.doi: 10.1090/S0002-9947-10-05003-8. [9] R. Burton and J. E. Steif, Non-uniqueness of measures of maximal entropy for subshifts of finite type, Ergodic Theory Dynam. Systems, 14 (1994), 213-235.doi: 10.1017/S0143385700007859. [10] M. Denker, C. Grillenberger and K. Sigmund, Ergodic Theory on Compact Spaces, Lecture Notes in Mathematics, Vol. 527, Springer-Verlag, Berlin-New York, 1976. [11] N. J. Fine and H. S. Wilf, Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc., 16 (1965), 109-114.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, J. Amer. Math. Soc., 12 (1999), 1017-1054.doi: 10.1090/S0894-0347-99-00305-7. [13] G. Grimmett, Percolation, Second edition, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 321, Springer-Verlag, Berlin, 1999.doi: 10.1007/978-3-662-03981-6. [14] M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176 (2009), 131-167.doi: 10.1007/s00222-008-0161-7. [15] M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math. (2), 171 (2010), 2011-2038.doi: 10.4007/annals.2010.171.2011. [16] M. S. Keane, Ergodic theory and subshifts of finite type, in Ergodic Theory, Symbolic Dynamics, and Hyperbolic Spaces (Trieste, 1989), Oxford Sci. Publ., Oxford Univ. Press, New York, 1991, 35-70. [17] B. Kitchens, Symbolic Dynamics. One-Sided, Two-Sided and Countable State Markov Shifts, Universitext, Springer-Verlag, Berlin, 1998.doi: 10.1007/978-3-642-58822-8. [18] W. Krieger, On the subsystems of topological Markov chains, Ergodic Theory and Dynamical Systems, 2 (1982), 195-202.doi: 10.1017/S0143385700001516. [19] F. Krząkała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and L. Zdeborová, Gibbs states and the set of solutions of random constraint satisfaction problems, Proc. Natl. Acad. Sci. USA, 104 (2007), 10318-10323.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 (2003), 587-609.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 (2004), 1227-1260.doi: 10.1017/S0143385704000276. [22] D. Lind, A zeta function for $\mathbbZ^d$-actions, in Ergodic Theory of $\mathbbZ^d$ Actions (Warwick, 1993-1994), London Math. Soc. Lecture Note Ser., 228, Cambridge Univ. Press, Cambridge, 1996, 433-450.doi: 10.1017/CBO9780511662812.019. [23] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995.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 (1984), 283-300.doi: 10.1017/S0143385700002443. [25] B. Marcus, Factors and extensions of full shifts, Monatsh. Math., 88 (1979), 239-247.doi: 10.1007/BF01295238. [26] K. McGoff, Random subshifts of finite type, Ann. Probab., 40 (2012), 648-694.doi: 10.1214/10-AOP636. [27] M. Morse and G. A. Hedlund, Symbolic Dynamics, Amer. J. Math., 60 (1938), 815-866.doi: 10.2307/2371264. [28] W. Parry, Intrinsic Markov chains, Trans. Amer. Math. Soc., 112 (1964), 55-66.doi: 10.1090/S0002-9947-1964-0161372-1. [29] A. Quas and A. A. Şahin, Entropy gaps and locally maximal entropy in $\mathbb Z^d$ subshifts, Ergodic Theory Dynam. Systems, 23 (2003), 1227-1245.doi: 10.1017/S0143385702001761. [30] D. Ruelle, Thermodynamic Formalism. The Mathematical Structures of Equilibrium Statistical Mechanics, Second edition, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2004.doi: 10.1017/CBO9780511617546.