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

Kevin  McGoff; Ronnie  Pavlov

doi:10.3934/jmd.2016.10.287

Article Contents

2016, Volume 10: 287-330. Doi: 10.3934/jmd.2016.10.287

This issue Previous Article The entropy of Lyapunov-optimizing measures of some matrix cocycles Next Article An Urysohn-type theorem under a dynamical constraint

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

Kevin McGoff^1, and
Ronnie Pavlov^2,

1.
Department of Mathematics and Statistics, The University of North Carolina at Charlotte, 9201 University City Blvd., Charlotte, NC 28223
2.
Department of Mathematics, University of Denver, 2280 S. Vine St., Denver, CO 80208

Received: July 31, 2014

Revised: December 31, 2015

Published: June 2016

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 37B50; Secondary: 37B10, 37H99.

Citation:

Related Papers

Cited by

References

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