Approximating the hard square entropy constant with probabilistic methods

For any two-dimensional nearest neighbor shift of finite type X and any integer n≥1, one can define the horizontal strip shift Hn(X) to be the set of configurations on Z×{1,…,n} which do not contain any forbidden pairs of adjacent letters for X. It is always the case that the sequence htop(Hn(X))/n of normalized topological entropies of the strip shifts converges to htop(X), the topological entropy of X. In this paper, we combine ergodic theoretic techniques with methods from percolation theory and interacting particle systems to show that for the two-dimensional hard square shift H, the sequence htop(Hn+1(H))−htop(Hn(H)) also converges to htop(H), and that the rate of convergence is at least exponential. As a corollary, we show that htop(H) is computable to any tolerance e in time polynomial in 1/e. We also show that this phenomenon is not true in general by defining a block gluing two-dimensional nearest neighbor shift of finite type Y for which htop(Hn+1(Y))−htop(Hn(Y)) does not even approach a limit.