For two-dimensional hard constraints (shifts of finite type) such as the even and charge(3) parity constraints on Z2\mathbb{Z}^2, corner transfer matrix (CTM) computations yield extremely precise estimates and, for cell-local models, rigorous lower bounds. Chan and Rechnitzer (2014) proved the one-sided inequality κcharge(3)≥κeven\kappa_{\mathrm{charge}(3)}\ge\kappa_{\mathrm{even}} and conjectured, on the basis of estimates agreeing to eight significant digits, that the two growth rates are equal; their certified-upper-bound and stable-bond-state-lower-bound programs for these models were left open. Their own 2014-2018 follow-up resolved the upper-bound problem only for cell-local models (hard squares, non-attacking kings, read/write isolated memory) and explicitly does not apply to the even model, whose bond-state transfer matrices lack irreducibility; no rigorous upper bound of comparable quality exists for the charge(3) model, and no rigorous lower bound of comparable quality has been certified directly (the only rigorous lower bound is the one inherited from the proved inequality κcharge(3)≥κeven\kappa_{\mathrm{charge}(3)}\ge\kappa_{\mathrm{even}}, which is not of comparable quality). The open problem is to determine these two capacities rigorously: prove or disprove κcharge(3)=κeven\kappa_{\mathrm{charge}(3)}=\kappa_{\mathrm{even}} on Z2\mathbb{Z}^2, and construct certified lower and upper bounds for both capacities of a quality comparable to what is now available for the hard-squares family.

Background

A two-dimensional constraint (a shift of finite type) is a set of configurations of symbols on the vertices of the square lattice Z2\mathbb{Z}^2 determined by a finite set of local rules; it models what can be stored on a two-dimensional medium. Its capacity is the asymptotic number of storable bits per site: if ZNZ_N is the number of admissible configurations on a region with NN sites, the growth rate is κ=lim⁡N→∞ZN1/N\kappa=\lim_{N\to\infty}Z_N^{1/N} and the capacity is log⁡2κ\log_2\kappa. Unlike in one dimension, where κ\kappa is the dominant eigenvalue of a finite transfer matrix, computing κ\kappa for two-dimensional constraints is notoriously hard, and exact growth rates are known for only a handful of models (for general two-dimensional shifts of finite type even non-emptiness — the question of whether a given finite set of square tile types can tile the plane, known as Berger's domino problem — is undecidable, so each capacity result must exploit specific structure). The best-studied example is the hard-squares (exclusion) model — independent sets on the square grid, where occupied sites may not be adjacent — whose growth rate is approximately 1.50304808247533226431.5030480824753322643.

The source paper, Chan and Rechnitzer (IEEE Transactions on Information Theory, 2014), analysed several constraint families: the exclusion model just described; qq-colouring models (nearest-neighbour vertices must receive different colours of {0,…,q−1}\{0,\dots,q-1\}); and two parity-type constraints on {⊕,⊖}\{\oplus,\ominus\}-valued spins that are not cell-local vertex models. The even constraint requires that along any horizontal or vertical line, any two consecutive ⊖\ominus spins are separated by an even number of ⊕\oplus spins; the charge(3) constraint requires that the signed sum of spins (+1+1 for ⊕\oplus, −1-1 for ⊖\ominus) along any finite horizontal or vertical segment lies between −3-3 and +3+3. Both can be reformulated as local constraints on states attached to the bonds (edges) of the lattice, which is what makes them amenable to transfer-matrix analysis.

The computational engine is Baxter's corner transfer matrix (CTM) formalism — matrices that build the partition function quadrant by quadrant — combined with the corner transfer matrix renormalisation group (CTMRG) iteration of Nishino and Okunishi, which truncates the CTM spectra to keep the computation finite. Chan and Rechnitzer combined finite-size CTM solutions with the classical strip bounds of Calkin and Wilf (lower bounds via Rayleigh quotients of strip transfer matrices, upper bounds via transfer matrices on strips with cylindrical boundary conditions) to produce rigorous lower bounds and high-precision estimates: κeven≥1.357587502184123\kappa_{\mathrm{even}}\ge1.357587502184123, with the estimate of κcharge(3)\kappa_{\mathrm{charge}(3)} agreeing to the eight computable digits. They proved (Theorem 5) the one-sided inequality κcharge(3)≥κeven\kappa_{\mathrm{charge}(3)}\ge\kappa_{\mathrm{even}}, by exhibiting a subset of charge(3) configurations in bijection with the bond-state (pp-ii) formulation of the even model, and gave a non-rigorous 'tartan' entropy argument (decomposing charge configurations into regions obeying the even, fully-packed-dimer (κ=eCatalan/π≈1.33852\kappa=e^{\mathrm{Catalan}/\pi}\approx1.33852), and 'elbow' (κ≤1.333521\kappa\le1.333521) constraints, all of lower growth rate, with only subexponentially many parity patterns) for the reverse inequality; this underlies Conjecture 1, that the two growth rates are equal. Two technical obstacles were left open for these models: the power-method lower-bound computation is numerically unstable for the bond-state charge formulation, so no rigorous lower bound for κcharge(3)\kappa_{\mathrm{charge}(3)} was obtained; and the authors' later upper-bound machinery (Calkin–Wilf cylindrical bound plus the Collatz–Wielandt formula — the classical result that for a nonnegative matrix TT and positive vector vv, the dominant eigenvalue is bounded above by max⁡i(Tv)i/vi\max_i (Tv)_i/v_i — fed with a CTM/CTMRG eigenvector ansatz) requires irreducible transfer matrices and so, as they stated explicitly, does not apply to the even model. That follow-up work (preprint 2014, journal 2018) succeeded spectacularly for the cell-local models — hard squares, non-attacking kings, and read/write isolated memory — reducing the gap between rigorous upper and lower bounds by four to six orders of magnitude and determining the hard-squares growth rate to about eighteen digits (1.503048082475332264…1.503048082475332264\dots), but no rigorous upper bounds of comparable quality exist for the even and charge(3) constraints, no rigorous lower bound of comparable quality obtained directly from the charge(3) bond-state formulation exists (the bound inherited from κcharge(3)≥κeven≥1.357587502184123\kappa_{\mathrm{charge}(3)}\ge\kappa_{\mathrm{even}}\ge1.357587502184123 is not of comparable quality), and the equality conjecture remains unproved.

Problem Statement

Determine, rigorously, the capacities of the even and charge(3) constraints on the square lattice Z2\mathbb{Z}^2. This comprises two linked targets with a single overarching objective. First, resolve Conjecture 1 of Chan and Rechnitzer (2014): prove that κcharge(3)=κeven\kappa_{\mathrm{charge}(3)}=\kappa_{\mathrm{even}} on Z2\mathbb{Z}^2 (the inequality κcharge(3)≥κeven\kappa_{\mathrm{charge}(3)}\ge\kappa_{\mathrm{even}} is already proved), or prove that the two growth rates differ. A finite construction cannot settle this claim in either direction, since it is a statement about exponential growth rates. Second, construct certified two-sided bounds for each of κeven\kappa_{\mathrm{even}} and κcharge(3)\kappa_{\mathrm{charge}(3)} of a quality comparable to what is now achieved for the hard-squares family — that is, for each constant a certified lower bound and a certified upper bound, each obtained directly from that constant's own model, whose rigorous gap is comparable in size to the hard-squares certified gap (about eighteen significant digits, i.e. of order 10−1810^{-18}): in particular a stable rigorous lower bound on κcharge(3)\kappa_{\mathrm{charge}(3)} obtained directly from the bond-state formulation (no such bound currently exists, owing to the instability of the bond-state power-method computation; the bound inherited via κcharge(3)≥κeven\kappa_{\mathrm{charge}(3)}\ge\kappa_{\mathrm{even}} does not count toward this target) and rigorous upper bounds on both constants (the Collatz-Wielandt/CTM upper-bound method of Chan and Rechnitzer requires irreducible transfer matrices, fails for the even model's bond-state formulation, and has not been extended to either of these non-cell-local models). Bounds or proofs restricted to strips, finite tori, or one-dimensional analogues do not answer the question, which concerns the full lattice Z2\mathbb{Z}^2.

References

  1. Yao-ban Chan and Andrew Rechnitzer, "Accurate Lower Bounds on 2-D Constraint Capacities From Corner Transfer Matrices", IEEE Transactions on Information Theory 60(7), 3845-3858 (2014). DOI: 10.1109/TIT.2014.2321554, https://doi.org/10.1109/TIT.2014.2321554. The preprint arXiv:1210.5189, https://arxiv.org/abs/1210.5189, carries the spelled-out title "Accurate lower bounds on two-dimensional constraint capacities from corner transfer matrices".
  2. Yao-ban Chan and Andrew Rechnitzer, "Upper bounds on the growth rates of hard squares and related models via corner transfer matrices", preprint (2014). arXiv:1411.7442, https://arxiv.org/abs/1411.7442.
  3. Yao-ban Chan and Andrew Rechnitzer, "Upper bounds on the growth rates of independent sets in two dimensions via corner transfer matrices", Linear Algebra and its Applications 555, 139-156 (2018). DOI: 10.1016/j.laa.2018.06.008, https://doi.org/10.1016/j.laa.2018.06.008.
  4. Yao-Ban Chan, "Upper bounds on the growth rates of hard squares and related models via corner transfer matrices", DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (2015). DOI: 10.46298/dmtcs.2486, https://doi.org/10.46298/dmtcs.2486.
  5. 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.
  6. Ronnie Pavlov, "Approximating the hard square entropy constant with probabilistic methods", The Annals of Probability 40(6) (2012). DOI: 10.1214/11-AOP681, https://doi.org/10.1214/11-AOP681.
  7. Kai Liang, "Independent Set Enumeration and Estimation of Related Constants of Grid Graphs and Their Variants" (2025). arXiv:2507.04007, https://arxiv.org/abs/2507.04007.
  8. Tomotoshi Nishino and Kouichi Okunishi, "Corner Transfer Matrix Algorithm for Classical Renormalization Group", Journal of the Physical Society of Japan 66(10), 3040-3047 (1997). DOI: 10.1143/jpsj.66.3040, https://doi.org/10.1143/jpsj.66.3040. (Origin of the corner transfer matrix renormalisation group method.)