Two-dimensional constraint capacities: the charge(3)-even equality conjecture and certified corner-transfer-matrix bounds

Baxter's corner transfer matrix (CTM) formalism, combined with the corner transfer matrix renormalization group (CTMRG) method, yields certified rigorous lower bounds and high-precision estimates for the growth rates (capacities) of two-dimensional constraints on the square lattice, such as hard squares, q-colouring, the even (parity) constraint, and the charge(3) constraint. Chan and Rechnitzer (IEEE Trans. Inform. Theory 60, 3845, 2014) proved only the one-sided inequality kappa_charge(3) >= kappa_even >= 1.357587502184123, while their estimates for the two constants agree to 8 significant digits, leading to Conjecture 1: the charge(3) and even constraints have equal growth rate on Z^2. The same paper left certified upper bounds of comparable precision open, noting that Wilkinson-type eigenvalue perturbation bounds cannot certify dominance. The authors' own Collatz-Wielandt/CTM upper-bound program resolved the upper-bound item only for the exclusion family (hard squares, non-attacking kings, read-write isolated memory); no proof or disproof of Conjecture 1, no certified upper bounds for the even, charge(3), or colouring models, and no convergence proof of CTMRG are known. The objective is to resolve Conjecture 1 and construct certified upper bounds of comparable precision for the remaining families, with stable certified computation for bond-state formulations as the supporting methodological strand.

Background

A two-dimensional constraint is a rule restricting the infinite arrays of symbols ('spins', typically two values, occupied or vacant) that may be written on the vertices of the square lattice $\mathbb{Z}^2$; in symbolic dynamics such a set of arrays is a two-dimensional shift of finite type or sofic system, meaning membership is decided by forbidden local patterns or by finite-state labellings. Such constraints arise in data storage, where the spins encode bits on a medium and physical limitations forbid certain local arrangements. If $Z_N$ is the number of admissible configurations on $N$ sites, then $Z_N$ grows like $\kappa^N$, where $\kappa=\lim_{N\to\infty}Z_N^{1/N}$ is the growth rate (the partition function per site; its logarithm is the topological entropy in the statistical-mechanics convention), and the storage capacity in bits per site is $\log_2\kappa$.

In one dimension $\kappa$ is computed exactly as the dominant eigenvalue (Perron root) of a finite transfer matrix. In two dimensions no such finite matrix exists, computing the capacity of a general two-dimensional finite-type system is algorithmically undecidable (a classical consequence of the domino problem, which asks whether a given finite set of square tiles with edge-matching colours can cover the plane), and even for the most studied natural models the exact values are unknown: for the hard squares model (independent sets of $\mathbb{Z}^2$, i.e. no two occupied sites adjacent) one knows only bounds and estimates, the best estimates giving $\kappa\approx 1.50304808247533226432\ldots$ The field therefore seeks rigorous two-sided bounds. Calkin and Wilf showed that finite-width transfer matrices yield computable lower and upper bounds converging to $\kappa$, at a cost exponential in the strip width; Louidor and Marcus improved lower bounds for several 'symmetric' two-dimensional constraints using Rayleigh quotients (variational eigenvalue bounds).

The source paper introduced CTM-based certified lower bounds. Baxter's corner transfer matrix (CTM) formalism rewrites the partition function of a lattice quadrant as the trace of a product of four 'corner' matrices, one per quadrant (the formalism underlies Baxter's exact solution of the hard hexagons model). Nishino and Okunishi's corner transfer matrix renormalization group (CTMRG) makes the CTM equations numerically tractable by an iterate-diagonalise-truncate loop that keeps the $n$ dominant eigenvectors. Chan and Rechnitzer observed that a variational (min-max) structure of the CTM equations converts any approximate solution into a certified rigorous lower bound on $\kappa$, while the converged CTMRG solution supplies a high-precision estimate. They applied this to the exclusion family (hard squares; read-write isolated memory, RWIM, a model of sequentially updated one-dimensional memories; non-attacking kings, NAK, at most one occupied site per lattice face), to $q$-colouring (proper vertex colourings of $\mathbb{Z}^2$ with $q$ colours, i.e. antiferromagnetic Potts configurations; $q=3$ is known exactly, $(4/3)^{3/2}$, while for $q\ge 4$ only bounds were available), to the parity family (the even constraint requires that along every row and column, any two consecutive occupied sites are separated by an even number of vacant sites; the odd constraint, requiring odd separations, has growth rate exactly $\sqrt{2}$), and to the charge family (charge($Q$) requires that the spin sum, occupied $=+1$ and vacant $=-1$ say, along any finite horizontal or vertical line segment lies between $-Q$ and $+Q$; charge(1) is trivial, the growth rate of charge(2) on $\mathbb{Z}^d$ is known to be $2^{2^{-d}}$, and charge(3) is the first case with unknown growth rate, for which earlier work could not even determine the first digit).

The even and charge constraints, though non-local on vertices, become local in reformulations with states on lattice bonds (edges): the even model maps to a 'p-i' bond model and charge(3) to a 'Q-charge' bond model. The numerical results include, for example, a 92-significant-digit hard-squares lower bound whose corresponding estimate agrees with all 43 digits of the series estimate in the literature, $\kappa_{\mathrm{even}}\ge 1.357587502184123$, a 4-colouring lower bound $2.33605664104113\ldots$, and a charge(3) estimate of only 8 significant digits ($1.35758750$, computed at smaller matrix size because the rigorous-bound power method was numerically unstable for the Q-charge bond formulation, for reasons the authors could not determine). The even and charge(3) estimates agree to all 8 computed digits, which led to Conjecture 1. In one dimension the equality is provable: both growth rates equal the golden ratio $(1+\sqrt{5})/2$, via a 2-to-1 graph homomorphism between the one-dimensional Q-charge and p-i finite-state graphs. The same construction restricted to configurations with fixed bond parities proves the one-sided inequality $\kappa_{\mathrm{charge}(3)}\ge\kappa_{\mathrm{even}}$ on $\mathbb{Z}^2$. For the reverse inequality only a heuristic 'tartan' argument exists: after fixing the parities of all rows and columns (a sub-exponential $2^{2\sqrt{N}}$ choices), a Q-charge configuration decomposes into 'good' faces (obeying a p-i/even-type constraint), 'bad' faces (fully-packed dimer configurations, i.e. perfect matchings, whose growth rate $e^{\mathrm{Catalan}/\pi}\approx 1.3385$ is proved, where $\mathrm{Catalan}$ denotes Catalan's constant $G\approx 0.9160$), and interfacial 'elbow' configurations (bounded above by $1.333521$ via Calkin-Wilf) - all below the proved lower bound for $\kappa_{\mathrm{even}}$ - but the step combining these contributions into an upper bound on the whole ensemble is not rigorous.

On the upper-bound side, the source notes that eigenvalue perturbation theory (Wilkinson's theorem) can bound the distance from a computed estimate to the nearest eigenvalue of the transfer object but cannot certify that this eigenvalue is dominant, so certified upper bounds of comparable precision were out of reach at the time. The authors' own follow-up closed this gap for the exclusion family: starting from the Calkin-Wilf bound and applying the Collatz-Wielandt characterization of the spectral radius (for a nonnegative matrix $M$ and any positive vector $v$, $\min_i (Mv)_i/v_i\le\rho(M)\le\max_i (Mv)_i/v_i$), with the required approximate eigenvector supplied by CTM/CTMRG, they proved certified upper bounds on the growth rates of hard squares, NAK and RWIM, reducing the upper-lower gaps by 4-6 orders of magnitude. The even and charge(3) models, whose amenable reformulations live on bond states rather than vertices, and the colouring models have not been given such bounds.

Problem Statement

The problem is to convert the certified lower bounds and high-precision estimates that corner-transfer-matrix computations provide for two-dimensional constraint capacities into a certified two-sided determination of these constants, and to settle the equality relation that this precision revealed. Its components jointly serve this single objective:

(1) Resolve Conjecture 1 of Chan and Rechnitzer: prove that the charge(3) and even constraints on $\mathbb{Z}^2$ have equal growth rate, $\kappa_{\mathrm{charge}(3)}=\kappa_{\mathrm{even}}$, or disprove it by a certified argument (a rigorous upper bound on $\kappa_{\mathrm{even}}$ strictly below a rigorous lower bound on $\kappa_{\mathrm{charge}(3)}$). Currently only $\kappa_{\mathrm{charge}(3)}\ge\kappa_{\mathrm{even}}\ge 1.357587502184123$ is proved, while the computed estimates agree to 8 significant digits ($\approx 1.35758750$).

(2) Construct certified rigorous upper bounds, of precision comparable to the existing CTM lower bounds for the same model (explicitly, certifying at least as many correct significant digits as that model's certified CTM lower bound), for the growth rates of the constraint families that the lower-bound program treated but that the 2018 Collatz-Wielandt follow-up did not cover: the even and charge(3) models and the $q$-colouring models with $q\ge 4$ treated by the lower-bound program (4- and 5-colouring). (The exclusion-family models - hard squares, non-attacking kings, read-write isolated memory - already have certified upper bounds.)

(3) Supply, as the methodological strand needed wherever (1)-(2) rely on it, a stable and provably correct procedure for computing rigorous bounds from bond-state (states-on-bonds) formulations such as the Q-charge model, whose power-method implementation in the source was numerically unstable for undetermined reasons.

A complete solution resolves the conjecture in either direction and delivers the certified upper bounds of (2). The systematic extension to further families (charge($Q$) for $Q>3$, larger $q$), which the source itself marks as future work, and a full convergence proof of the CTMRG iterate-diagonalise-truncate loop, whose convergence the source notes is not proved, are natural continuations; they support the objective but are not required for completion, since the source establishes that bound validity does not depend on CTMRG convergence.

References

1. Yao-ban Chan and Andrew Rechnitzer, 'Accurate lower bounds on two-dimensional constraint capacities from corner transfer matrices', IEEE Transactions on Information Theory 60(7), 3845-3858 (2014). DOI: 10.1109/TIT.2014.2321554; preprint arXiv:1210.5189, https://arxiv.org/abs/1210.5189
2. 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; preprint arXiv:1411.7442, https://arxiv.org/abs/1411.7442 (the preprint version is titled 'Upper bounds on the growth rates of hard squares and related models via corner transfer matrices')
3. Erez Louidor and Brian H. Marcus, 'Improved lower bounds on capacities of symmetric 2D constraints using Rayleigh quotients', IEEE Transactions on Information Theory 56(4), 1624-1639 (2010). DOI: 10.1109/TIT.2010.2040942, https://doi.org/10.1109/TIT.2010.2040942
4. Brian Marcus, 'Capacity of Higher-Dimensional Constrained Systems', in 'Coding Theory and Applications', CIM Series in Mathematical Sciences, Springer (2015). DOI: 10.1007/978-3-319-17296-5_1, https://doi.org/10.1007/978-3-319-17296-5_1
5. Douglas Lind and Brian Marcus, 'An Introduction to Symbolic Dynamics and Coding', 2nd edition, Cambridge University Press (2021). DOI: 10.1017/9781108899727, https://doi.org/10.1017/9781108899727
6. 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
7. R. J. Baxter, 'Dimers on a Rectangular Lattice', Journal of Mathematical Physics 9, 650-654 (1968). DOI: 10.1063/1.1664623, https://doi.org/10.1063/1.1664623
8. R. J. Baxter, 'Hard hexagons: exact solution', Journal of Physics A: Mathematical and General 13, L61-L70 (1980). DOI: 10.1088/0305-4470/13/3/007, https://doi.org/10.1088/0305-4470/13/3/007
9. R. J. Baxter, 'Planar lattice gases with nearest-neighbor exclusion', Annals of Combinatorics 3(2), 191-203 (1999). DOI: 10.1007/BF01608783, https://doi.org/10.1007/BF01608783
10. Tomotoshi Nishino and Kouichi Okunishi, 'Corner Transfer Matrix Renormalization Group Method', Journal of the Physical Society of Japan 65(4), 891-894 (1996). DOI: 10.1143/JPSJ.65.891, https://doi.org/10.1143/JPSJ.65.891
11. 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
12. J. H. Wilkinson, 'Rigorous Error Bounds for Computer Eigensystems', The Computer Journal 4(3), 230-241 (1961). DOI: 10.1093/comjnl/4.3.230, https://doi.org/10.1093/comjnl/4.3.230
13. 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
14. Matthew Theodore Fishman, 'Development of Tensor Network Algorithms for Studying Classical and Quantum Many-Body Systems', PhD thesis, California Institute of Technology (2018). DOI: 10.7907/44S6-0Q68, https://doi.org/10.7907/44S6-0Q68
15. Zhengyue Chen and Sheng Ran, 'Hexagonal Stacking Maximizes Proton Configurational Entropy among Ice-I Polytypes', arXiv:2608.07613 (2026), https://arxiv.org/abs/2608.07613
16. X. F. Liu, Y. F. Fu, W. Q. Yu, J. F. Yu and Z. Y. Xie, 'Variational corner transfer matrix renormalization group method for classical statistical models', arXiv:2203.17098 (2022), https://arxiv.org/abs/2203.17098