Explicit convergence constants and higher-dimensional extensions for hard-square strip-entropy approximation

The hard square shift $\mathcal H$ (binary configurations of $\mathbb Z^2$ with no two adjacent 1s, i.e. lattice independent sets) has topological entropy $h$ equal to the logarithm of the hard square entropy constant $\kappa\approx 1.5030481$, for which no closed form is known. Pavlov proved that the successive differences $h_{n+1}-h_n$ of the entropies of horizontal strips of height $n$ converge to $h$ at least exponentially fast — via a site-dependent stochastic-domination argument and disagreement percolation dominated by subcritical site percolation at $p=1/2$ — and consequently that $h$ is computable in polynomial time, though by a polynomial of non-explicit degree. Two parts of the problem posed at the end of that paper remain open: (1) give explicit numerical constants $A,B>0$ with $|(h_{n+1}-h_n)-h|\le Ae^{-Bn}$ for all $n$, which would also make the polynomial-time complexity of computing $h$ explicit and could sharpen rigorous bounds on $\kappa$; and (2) determine whether the analogous slab-entropy differences converge, at any provable rate, for the $\mathbb Z^d$ hard square shift with $d\ge 3$, where $p_c(\mathbb Z^d)<1/2$ breaks the percolation argument. The third question raised there — extending the method to broader classes of $\mathbb Z^2$ shifts of finite type — has been substantially resolved by subsequent work.

Background

A shift of finite type (SFT) is the set $X$ of all configurations of a finite alphabet over the integer lattice $\mathbb Z^d$ that avoid a fixed finite list of forbidden local patterns; in a nearest-neighbor SFT the forbidden patterns are pairs of letters at adjacent sites. Its topological entropy $h^{top}(X)$ is the exponential growth rate, per site, of the number of distinct patterns that appear in points of $X$ on large boxes. For $d=1$ this entropy is elementary to compute — it is the logarithm of the largest eigenvalue (the Perron eigenvalue, given by the Perron–Frobenius theory of nonnegative matrices) of a finite 0–1 transition matrix — but for $d\ge 2$ no such formula exists: the entropies of $\mathbb Z^d$ SFTs realize essentially arbitrary right-recursively-enumerable real numbers (Hochman and Meyerovitch), hence are in general uncomputable, and closed-form values are known for only a handful of models.

The standard way to approximate a two-dimensional entropy is by strips. For a nearest-neighbor $\mathbb Z^2$ SFT $X$, let $H_n(X)$ be the set of configurations on the horizontal strip $\mathbb Z\times\{1,\dots,n\}$ that avoid all forbidden adjacent pairs; $H_n(X)$ is itself a one-dimensional SFT whose alphabet is the set of legal height-$n$ columns, and its entropy $h_n(X)$ is again a Perron-eigenvalue computation. A Fekete-type subadditivity argument gives $h_n(X)/n\to h^{top}(X)$, and strip transfer matrices have long been used to bound two-dimensional entropies numerically (Engel; Calkin and Wilf). The prototypical model is the hard square shift $\mathcal H$: binary configurations of $\mathbb Z^2$ in which no two adjacent sites both hold a 1 — equivalently, configurations encoding independent sets (sets of lattice sites, the 1s, with no two adjacent) of the square lattice. Writing $h=h^{top}(\mathcal H)$, the constant $\kappa=e^h$ is the hard square entropy constant, the exponential growth rate of the number of independent sets in $n\times n$ grids; corner-transfer-matrix computations (Baxter) give $\kappa\approx 1.5030481$, and no closed form is known. Numerical strip studies had long suggested an empirical curiosity: $h_n/n$ appears to converge to $h$ only at a linear rate in $n$, while the successive differences $h_{n+1}-h_n$ appear to converge to $h$ exponentially fast.

Pavlov proved this acceleration rigorously: $h_{n+1}-h_n\to h$ with rate at least exponential, and consequently $h$ is computable to any tolerance $\varepsilon$ in time polynomial in $1/\varepsilon$ — striking, given the general uncomputability of $\mathbb Z^2$ SFT entropies. The proof is probabilistic rather than combinatorial. It analyzes the measure of maximal entropy of $\mathcal H$ (the shift-invariant probability measure whose entropy equals $h^{top}$; for $\mathcal H$ it is unique and coincides with the Gibbs measure of the hard-core lattice gas at activity 1, under which each locally admissible completion of a region is equally likely). Two ingredients carry the argument. First, a site-dependent partial order on configurations comes with a stochastic-domination theorem (two measures comparable in this order admit a monotone coupling). Second, disagreement percolation (a technique introduced by van den Berg and Maes and applied to the hard-core lattice gas by van den Berg and Steif): two copies of a Gibbs measure can be coupled so that the set of sites where they disagree is stochastically dominated by site percolation — in which each lattice site is independently declared open with probability $p$ — so that disagreement probabilities are bounded by percolation connection probabilities. For $\mathcal H$ the relevant density is exactly $p=1/2$, and the critical probability $p_c(\mathbb Z^2)$ of site percolation (the open-site density separating almost-sure absence from presence of an infinite connected open cluster) exceeds $1/2$, so classical sharpness theorems of percolation — for which Duminil-Copin and Tassion give a modern proof — provide exponential decay of connection probabilities, $P_p(0\leftrightarrow\partial[-n,n]^2)<Ae^{-Bn}$ for every $p<p_c$, but with entirely non-explicit constants $A,B$. This non-explicitness propagates through the whole argument: the theorem yields some $A,B$ for the strip convergence and some polynomial for the computation time, but no numerical values. The same paper also shows that the strip-difference phenomenon is not automatic: there exists a block-gluing $\mathbb Z^2$ SFT (any two square patterns can be glued into a configuration of the shift once separated by a gap of comparable size) whose strip-entropy differences do not converge at all.

Two limitations of the method define the open problem. First, effectivity: Pavlov notes that explicit constants in the percolation decay at $p=1/2$ would suffice to make the rate explicit, that elementary path-counting gives such constants only for $p<1/4$, and that the case $p=1/2$ resisted the available techniques. Second, dimension: for $d\ge 3$ one has $p_c(\mathbb Z^d)<1/2$ (Campanino and Russo for $d=3$), so the disagreement bound at $p=1/2$ is no longer subcritical and the proof collapses. The subsequent literature developed the program in other directions — extending the method to broader classes of systems via the disagreement condition of van den Berg and Maes (the total-variation distance between one-site conditional distributions must stay below $p_c$), strong spatial mixing assumptions (conditional distributions depend on far-away data with exponentially decaying strength), and combinatorial conditions such as topological strong spatial mixing — but left both the explicit-constants question and the higher-dimensional question untouched.

Problem Statement

The problem is the effective and dimension-robust completion of the exponential strip-entropy convergence theorem for the hard square model. It has two linked components, both targeting the same convergence statement $h_{n+1}-h_n\to h$.

Component 1 (explicit constants, $d=2$). Give explicit numerical values of $A,B>0$ such that

$\left|(h_{n+1}-h_n)-h\right|\le Ae^{-Bn}\quad\text{for all }n\ge 1,$

where $h_n$ is the topological entropy of the height-$n$ horizontal strip shift $H_n(\mathcal H)$ of the $\mathbb Z^2$ hard square shift $\mathcal H$ — a one-dimensional shift of finite type whose entropy is taken per unit horizontal length, i.e. per column of $n$ sites, so that $h_n/n\to h$ — and $h=h^{top}(\mathcal H)$. Any rigorous method is admissible; the source observes that explicit decay constants for site percolation on $\mathbb Z^2$ at $p=1/2$ would suffice for the existing proof. Such constants would additionally convert the known non-effective polynomial-time computability of $h$ into one with an explicit polynomial bound, and could sharpen rigorous interval bounds on the hard square entropy constant.

Component 2 (higher dimensions). For the $\mathbb Z^d$ hard square shift $\mathcal H^{(d)}$ (binary configurations of $\mathbb Z^d$ with no two adjacent 1s) with $d\ge 3$, let $H^{(d)}_n$ be its restriction to the slab $\mathbb Z^{d-1}\times\{1,\dots,n\}$, a $\mathbb Z^{d-1}$ shift of finite type with topological entropy $h^{(d)}_n$ per site of the base lattice $\mathbb Z^{d-1}$ (each base site carries a column of $n$ sites of $\mathbb Z^d$), so that $h^{(d)}_n/n\to h^{top}(\mathcal H^{(d)})$. Determine whether $h^{(d)}_{n+1}-h^{(d)}_n\to h^{top}(\mathcal H^{(d)})$, and if so whether the convergence can be taken exponential in $n$. A rigorous refutation — a proof that the slab-entropy differences fail to converge, or converge to a value other than $h^{top}(\mathcal H^{(d)})$, for some $d\ge 3$ — would settle this component in the negative.

A complete answer resolves both components. The third question raised alongside these in the source — whether the method extends to a larger class of $\mathbb Z^2$ shifts of finite type — has been substantially resolved by subsequent work and is therefore not part of this problem's completion boundary.

References

1. Ronnie Pavlov, Approximating the hard square entropy constant with probabilistic methods, The Annals of Probability 40(6), 2362–2399, 2012. DOI: 10.1214/11-AOP681, https://doi.org/10.1214/11-aop681 (arXiv:1011.1983, https://arxiv.org/abs/1011.1983)
2. Brian Marcus and Ronnie Pavlov, Approximating entropy for a class of $\mathbb Z^2$ Markov random fields and pressure for a class of functions on $\mathbb Z^2$ shifts of finite type, Ergodic Theory and Dynamical Systems 33(1), 186–220, 2013. DOI: 10.1017/S0143385711000824, https://doi.org/10.1017/s0143385711000824 (arXiv:1009.3063, https://arxiv.org/abs/1009.3063)
3. Brian Marcus and Ronnie Pavlov, Computing bounds for entropy of stationary $\mathbb Z^d$ Markov random fields, SIAM Journal on Discrete Mathematics 27(3), 1544–1558, 2013. DOI: 10.1137/120887382, https://doi.org/10.1137/120887382 (arXiv:1204.2612, https://arxiv.org/abs/1204.2612)
4. Brian Marcus and Ronnie Pavlov, An integral representation for topological pressure in terms of conditional probabilities, Israel Journal of Mathematics 207(1), 395–433, 2015. DOI: 10.1007/s11856-015-1178-4, https://doi.org/10.1007/s11856-015-1178-4 (arXiv:1309.1873, https://arxiv.org/abs/1309.1873)
5. Raimundo Briceño, The topological strong spatial mixing property and new conditions for pressure approximation, Ergodic Theory and Dynamical Systems 38(5), 1658–1696, 2018. DOI: 10.1017/etds.2016.107, https://doi.org/10.1017/etds.2016.107 (arXiv:1411.2289, https://arxiv.org/abs/1411.2289)
6. Raimundo Briceño and Ronnie Pavlov, Strong spatial mixing in homomorphism spaces, SIAM Journal on Discrete Mathematics 31(3), 2110–2137, 2017. DOI: 10.1137/16M1066178, https://doi.org/10.1137/16M1066178 (arXiv:1510.01453, https://arxiv.org/abs/1510.01453)
7. Stefan Adams, Raimundo Briceño, Brian Marcus, and Ronnie Pavlov, Representation and poly-time approximation for pressure of $\mathbb Z^2$ lattice models in the non-uniqueness region, Journal of Statistical Physics 162(4), 1031–1067, 2016. DOI: 10.1007/s10955-015-1433-4, https://doi.org/10.1007/s10955-015-1433-4 (arXiv:1508.06590, https://arxiv.org/abs/1508.06590)
8. C. Evans Hedges and Ronnie Pavlov, Computability of pressure for subshifts on countable amenable groups, Nonlinearity 38(7), 075013, 2025. DOI: 10.1088/1361-6544/addd58, https://doi.org/10.1088/1361-6544/addd58 (arXiv:2408.04787, https://arxiv.org/abs/2408.04787)
9. J. van den Berg and J. E. Steif, Percolation and the hard-core lattice gas model, Stochastic Processes and their Applications 49(2), 179–197, 1994. DOI: 10.1016/0304-4149(94)90132-5, https://doi.org/10.1016/0304-4149(94)90132-5
10. J. van den Berg and C. Maes, Disagreement percolation in the study of Markov fields, The Annals of Probability 22(2), 749–763, 1994. DOI: 10.1214/aop/1176988728, https://doi.org/10.1214/aop/1176988728
11. M. Campanino and L. Russo, An upper bound on the critical percolation probability for the three-dimensional cubic lattice, The Annals of Probability 13(2), 478–491, 1985. DOI: 10.1214/aop/1176993004, https://doi.org/10.1214/aop/1176993004
12. Hugo Duminil-Copin and Vincent Tassion, A new proof of the sharpness of the phase transition for Bernoulli percolation on $\mathbb Z^d$, L'Enseignement Mathématique 62(1), 199–206, 2016. DOI: 10.4171/lem/62-1/2-12, https://doi.org/10.4171/lem/62-1/2-12
13. Michael Hochman and Tom Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Annals of Mathematics 171, 2011–2038, 2010. DOI: 10.4007/annals.2010.171.2011, https://doi.org/10.4007/annals.2010.171.2011
14. R. J. Baxter, Planar lattice gases with nearest-neighbor exclusion, Annals of Combinatorics 3(2–4), 191–203, 1999. DOI: 10.1007/BF01608783, https://doi.org/10.1007/BF01608783
15. Neil J. Calkin and Herbert S. Wilf, The number of independent sets in a grid graph, SIAM Journal on Discrete Mathematics 11(1), 54–60, 1998. DOI: 10.1137/S089548019528993X, https://doi.org/10.1137/s089548019528993x
16. Konrad Engel, On the Fibonacci number of an $m\times n$ lattice, The Fibonacci Quarterly 28(1), 72–78, 1990. DOI: 10.1080/00150517.1990.12429523, https://doi.org/10.1080/00150517.1990.12429523
17. Kai Liang, Independent set enumeration and estimation of related constants of grid graphs and their variants, arXiv:2507.04007, 2025. https://arxiv.org/abs/2507.04007
18. Yotam Svoray, The algebraicity problem for hard-core entropy constants on the discrete hypertori, arXiv:2608.28332, 2026. https://arxiv.org/abs/2608.28332
19. Silvère Gangloff, Benjamin Hellouin de Menibus, and Piotr Oprocha, Short-range and long-range order: a transition in block-gluing behavior in Hom shifts, Journal d'Analyse Mathématique 158(1), 21–64, 2026. DOI: 10.1007/s11854-025-0396-x, https://doi.org/10.1007/s11854-025-0396-x (arXiv:2211.04075, https://arxiv.org/abs/2211.04075)
20. Ville Salo and Ilkka Törmä, Two block gluing constructions, arXiv:2605.31237, 2026. https://arxiv.org/abs/2605.31237