Approximating the Hard Square Entropy Constant with Probabilistic\n Methods

2010/11/09 by Ronnie Pavlov, Pavlov, Ronnie · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Advanced Mathematical Theories and Applications #Cellular Automata and Applications #Dynamical Systems (math.DS) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.1011.1983

openalex publication_date 2010/11/09 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28

Abstract

For any two-dimensional nearest neighbor shift of finite type X and any\ninteger n > 0, one can define the horizontal strip shift H_n(X) to be the set\nof configurations on Z x 1,...,n which do not contain any forbidden\ntransitions for X. It is always the case that the sequence h(H_n(X))/n of\nnormalized topological entropies of the strip shifts approaches h(X), the\ntopological entropy of X. In this paper, we use probabilistic methods from\ninteracting particle systems to show that for the two-dimensional hard square\nshift H, in fact h(H_n+1(H)) - h(H_n(H)) also approaches h(H), and the rate\nof convergence is at least exponential. A consequence of this is that h(H) is\ncomputable to any tolerance 1/n in time polynomial in n. We also give an\nexample of a two-dimensional block gluing nearest neighbor shift of finite type\nY for which h(H_n+1(Y)) - h(H_n(Y)) does not even approach a limit.\n

Citations

• The undecidability of the domino problem

Cited by

• Independent Set Enumeration and Estimation of Related Constants of Grid Graphs and Their Variants

Related

• Hard Core entropy: lower bounds
• Approximating entropy for a class of zz² Markov Random Fields and\n pressure for a class of functions on zz² shifts of finite type
• On spatial entropy and periodic entropies of Two-dimensional Shifts of Finite Type
• Entropy on regular trees
• Entropy for symbolic dynamics with overlapping alphabets