Exact values of the hard-square entropy constant and the bipartite hard-square constant for grid-graph independent-set enumeration

For the $m\times n$ grid graph, the number $\sigma(G_{m\times n})$ of independent vertex sets grows asymptotically as $\eta^{mn}$, where $\eta$ is the hard-square entropy constant of statistical mechanics, and the number $\beta(G_{m\times n})$ of bipartite independent vertex sets (each chosen vertex is colored white or black, with same-colored vertices pairwise non-adjacent) grows as $\kappa^{mn}$. Oh and Lee (2016) proved both limits exist and gave finite-grid sandwich bounds, obtaining $2.003942\le\kappa\le 2.181636$; for $\eta$ the best numerical estimate is $1.5030480824753322643220663294755536893857810$ with about 19 digits certified rigorously. The problem is to determine both constants: exact closed-form values or their arithmetic nature (algebraic versus transcendental), and, as the pressing quantitative gap, a rigorous certified enclosure for $\kappa$ at the target relative width fixed in the Problem Statement — a separately reportable partial result — its published interval still spanning roughly 9 percent in relative width.

Background

An independent set of a graph is a set of vertices no two of which are joined by an edge. For a finite graph $G$ the total number $\sigma(G)$ of independent vertex sets is called the Merrifield–Simmons index in chemical graph theory, and for the square-lattice grid graph $G_{m\times n}$ (vertices $\{1,\dots,m\}\times\{1,\dots,n\}$ with horizontal and vertical adjacencies) it counts exactly the configurations of the hard-square lattice gas of statistical mechanics — particles with nearest-neighbor exclusion placed in an $m\times n$ box. The diagonal values are $\sigma(G_{n\times n})=2,7,63,1234,\dots$ for $n=1,2,3,4,\dots$ (sequence A006506 in the On-Line Encyclopedia of Integer Sequences (OEIS), the community database of integer sequences).

Because $\sigma$ grows exponentially in the area, the fundamental quantity is the per-site growth constant $\eta=\lim_{m,n\to\infty}\sigma(G_{m\times n})^{1/(mn)},$ the hard-square entropy constant ($\log\eta$ is the entropy per site). Its existence was proved by Calkin and Wilf (1998), who bounded it between eigenvalue expressions of finite-width transfer matrices (the matrices that encode how a row of admissible particle placements propagates to the next row); Oh and Lee (2016) re-proved existence by a two-dimensional form of Fekete's lemma (a standard result asserting convergence of doubly sub/supermultiplicative sequences), obtaining the sandwich inequality $\sigma(G_{m\times n})^{1/((m+1)(n+1))}\le\eta\le\sigma(G_{m\times n})^{1/(mn)}$. Numerically, transfer-matrix and corner-transfer-matrix computations — Baxter's variational technique in which the partition function of a whole lattice quadrant is approximated by products of corner transfer matrices, which transfer a quarter-plane boundary instead of a single row — pin $\eta\approx 1.5030480824753322643220663294755536893857810$ (Baxter 1999; 44 digits listed in OEIS A085850), and rigorous arguments — Rayleigh-quotient lower bounds and Collatz–Wielandt upper bounds (the classical characterization of the largest eigenvalue of a nonnegative matrix through one-sided matrix–vector product estimates) applied to finite-width transfer matrices — certify about 19 digits: $1.503048082475332264322066329475553689385781\ldots<\eta<1.503048082475332264519$ (Chan and Rechnitzer 2014, 2018). By contrast, for the hard-hexagon model — particles with nearest-neighbor exclusion on the triangular lattice, solved exactly by Baxter — the corresponding entropy constant is an algebraic number given as a root of an explicit degree-24 integer polynomial (OEIS A085851); the square-lattice hard-square model has resisted every exact-solution attempt. It is not known whether $\eta$ admits any exact representation, nor whether it is algebraic or transcendental, and Pavlov (2012) showed the entropy is nonetheless computable to any prescribed tolerance in polynomial time.

Oh and Lee (2016) enumerated independent vertex sets in grid graphs by the state matrix recursion algorithm — a transfer-matrix-style framework that converts lattice enumeration problems into recursively defined block matrices, here a $2^m\times 2^m$ matrix whose powers give the generating function $\sum_d k(d)z^d$ of independent sets by size — and extended it to bipartite independent vertex sets. A bipartite independent vertex set (BIVS) is a vertex subset whose members are each colored white or black such that same-colored vertices are pairwise non-adjacent (vertices of different colors may be adjacent); $\beta(G)$, the bipartite Merrifield–Simmons index, counts them. Equivalently, BIVSs are the configurations of a two-species lattice gas with same-species nearest-neighbor exclusion — the lattice Widom–Rowlinson model at unit activity (equal weight one for placing a particle of either species) — and also pairs consisting of a vertex subset that induces a bipartite graph together with a proper 2-coloring of it. Every independent set is a BIVS of a single color, so $\kappa\ge\eta$. Oh and Lee proved that the limit $\kappa=\lim_{m,n\to\infty}\beta(G_{m\times n})^{1/(mn)}$ exists by the same Fekete argument, and computed, from grids with $m=9$, $n=100$ using their $3^m$-dimensional recursion, the enclosure $2.003942\le\kappa\le 2.181636$ — a relative gap of roughly 9 percent, far cruder than what is known for $\eta$. No exact value, tighter enclosure, or further computation of $\kappa$ has appeared since.

Problem Statement

Determine the two growth constants of independent-set enumeration on the square grid. Write $\sigma(G_{m\times n})$ for the number of independent vertex sets (vertex subsets containing no two adjacent vertices) of the $m\times n$ grid graph, and $\beta(G_{m\times n})$ for the number of bipartite independent vertex sets — vertex subsets whose members each carry one of two colors, with same-colored vertices pairwise non-adjacent (vertices of different colors may be adjacent). The two constants are:

1. the hard-square entropy constant $\eta=\lim_{m,n\to\infty}\sigma(G_{m\times n})^{1/(mn)}$, whose numerical value is pinned to $1.5030480824753322643220663294755536893857810\ldots$ with about 19 digits certified rigorously, but for which no exact representation is known and whose algebraic or transcendental nature is open;

2. the bipartite hard-square constant $\kappa=\lim_{m,n\to\infty}\beta(G_{m\times n})^{1/(mn)}$, for which the best published enclosure remains $2.003942\le\kappa\le 2.181636$ (Oh and Lee 2016).

A complete solution of the task requires an exact determination of both constants of the same enumeration framework on the same lattice — for each of $\eta$ and $\kappa$ separately, a closed-form expression, an identification as an algebraic number together with its minimal polynomial and an isolating interval, or a proof of irrationality or transcendence. An exact determination of one of the two constants may be reported on its own for partial credit, but it does not discharge the requirement for the other constant, and no bounded-enclosure result can discharge either requirement. The two limits are the one-species and two-species versions of nearest-neighbor exclusion on $\mathbb{Z}^2$, and they may be approached by different means. A rigorous certified enclosure of $\kappa$ — a proven interval $\kappa_-\le\kappa\le\kappa_+$ containing $\kappa$, of relative width $(\kappa_+-\kappa_-)/\kappa_-$ below 5 percent, where the published interval $2.003942\le\kappa\le2.181636$ spans about 8.9 percent in this same measure, together with a correctness proof that the finite computation genuinely bounds the infinite-lattice limit — is a separately reportable partial-credit result, subsumed by an exact determination of $\kappa$ but not a substitute for it.

References

1. Seungsang Oh and Sangyop Lee, "Enumerating independent vertex sets in grid graphs", Linear Algebra and its Applications 510 (2016) 192–204. DOI: 10.1016/j.laa.2016.08.025; arXiv:1609.00515, https://arxiv.org/abs/1609.00515 (source paper)
2. R. J. Baxter, "Planar lattice gases with nearest-neighbor exclusion", Annals of Combinatorics 3 (1999) 191–203. DOI: 10.1007/BF01608783, https://doi.org/10.1007/BF01608783
3. Neil J. Calkin and Herbert S. Wilf, "The number of independent sets in a grid graph", SIAM Journal on Discrete Mathematics 11 (1998) 54–60. DOI: 10.1137/S089548019528993X, https://doi.org/10.1137/S089548019528993X
4. Yao-Ban Chan and Andrew Rechnitzer, "Accurate lower bounds on 2-D constraint capacities from corner transfer matrices", IEEE Transactions on Information Theory 60 (2014) 3845–3858. DOI: 10.1109/TIT.2014.2321554, https://doi.org/10.1109/TIT.2014.2321554
5. 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 (2018) 139–156. DOI: 10.1016/j.laa.2018.06.008; arXiv:1411.7442, https://arxiv.org/abs/1411.7442
6. Ronnie Pavlov, "Approximating the hard square entropy constant with probabilistic methods", Annals of Probability 40(6) (2012) 2362–2399. DOI: 10.1214/11-AOP681, https://doi.org/10.1214/11-AOP681; preprint arXiv:1011.1983, https://arxiv.org/abs/1011.1983
7. 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
8. Yotam Svoray, "The Algebraicity Problem for Hard-Core Entropy Constants on the Discrete Hypertori", arXiv:2608.28332 (2026), https://arxiv.org/abs/2608.28332
9. Eric W. Weisstein, "Hard Square Entropy Constant", MathWorld — A Wolfram Resource, https://mathworld.wolfram.com/HardSquareEntropyConstant.html (accessed 2026-08-31; states that no exact representation of the constant is known)
10. OEIS Foundation Inc., "A085850: Decimal expansion of hard square entropy constant", The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A085850 (accessed 2026-08-31; 44 digits from Baxter's computation)
11. OEIS Foundation Inc., "A085851: Decimal expansion of hard hexagon entropy constant", The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A085851 (accessed 2026-08-31; the exactly-solved hard-hexagon analogue, an algebraic number given as a root of an explicit integer polynomial)