Exact evaluation of the entropy $W(k)$ of $k$-colorings of the square lattice ($k$-species close-packed hard-square lattice gas)

The number of proper $k$-colorings of the faces of the infinite square lattice grows exponentially, as $[W(k)]^N$ for $N$ lattice sites. Equivalently, $W(k)$ is the residual entropy per site of a hard-square lattice gas of $k$ distinct particle species with infinite nearest-neighbor repulsion between equal species at zero chemical potential, and the exponential growth rate of the chromatic polynomial of the square lattice, i.e. the ground-state entropy of the zero-temperature $k$-state Potts antiferromagnet. For $k=3$ the problem is the classic square-ice problem solved exactly by Lieb, and Baxter solved the general-activity three-coloring; for every $k \ge 4$ no exact value is known — the $k=4$ case is a 21-vertex model — and only numerical estimates exist for the first open case: $W(4) = 2.3370(7)$ from Monte Carlo (Shrock and Tsai 1997). The problem, distilled from Singh and Jain (2018), is to determine $W(k)$ for general $k$ exactly or with certified error bounds.

Background

A proper $k$-coloring of the square lattice assigns one of $k$ colors to each face so that faces sharing an edge have different colors; by planar duality this is equivalent to coloring the vertices of the dual square lattice, so $W(k) = \lim_{N\to\infty} P(\text{sq}, k)^{1/N}$ where $P(G, q)$ is the chromatic polynomial, the polynomial counting proper vertex $q$-colorings of a graph $G$. The same quantity is the ground-state entropy per site of the $k$-state Potts antiferromagnet (spins with $k$ states and nearest-neighbor repulsion) at zero temperature, and of a lattice gas of $k$ distinct species of 'hard squares' — particles with infinite repulsion between nearest neighbors of the same species — at close packing (every site of the dual lattice occupied by exactly one particle) with zero chemical potential for each species; since the number of admissible configurations grows as $[W(k)]^N$, the thermodynamic entropy per site is $\ln W(k)$ in units of $k_B$, and $W(k)$ itself is what the residual-entropy literature quotes as the entropy per site. Two special facts anchor the subject. First, the $k=2$ case is trivial: only the two checkerboard colorings exist, so $W(2)=1$ and there is no entropy. Second, $k=3$ is exactly solved: Lenard observed that three-coloring the square lattice is equivalent (up to a factor) to Pauling's ice problem of counting arrow configurations on the lattice edges obeying the ice rule — two arrows in, two arrows out at every vertex — which is the six-vertex model; Lieb computed the exact residual entropy $W(3) = (4/3)^{3/2} \approx 1.5396$, and Baxter went on to solve the three-coloring with general activities $z_1, z_2, z_3$ per color, the fully general close-packed hard-square gas with three species. For $k \ge 4$ no exact result exists; for the first open case the standard numerical estimates are $W(4) = 2.3370(7)$ from Monte Carlo and 2.3361 from the large-$q$ series, both due to Shrock and Tsai (1997).

Singh and Jain (2018) recast the problem for general $k$. Each edge is assigned a state from the nonzero residues modulo $k$, i.e. from $\{1, \dots, k-1\}$, by taking the difference of the two adjacent face colors in a fixed orientation; the rules are that the two states an edge carries at its two endpoints are negatives of each other mod $k$, and the four edge states around a vertex sum to $0$ mod $k$. The number of allowed vertex configurations is $M_k = (k-1)^3 - (k-1)^2 + (k-1)$; for $k=3$ this gives the 6 configurations of the six-vertex model, and for $k=4$ a 21-vertex model. They construct transfer matrices — matrices acting on the space of allowed configurations of one lattice column, whose dominant eigenvalue controls the exponential growth of the finite-lattice partition function — for lattices with non-periodic boundary conditions imposed in at least one direction and prove a Toeplitz block structure (blocks constant along block diagonals) with a recursion relating the width-$(p+1)$ transfer matrices to the width-$p$ ones, denoted $B_p$ (a matrix of dimension $(k-1)^p$ acting on the allowed edge-state configurations of a lattice row of length $p$), and they evaluate finite-width partition functions in closed form for transverse widths $m = 2, 3, 4$ at $k=3$ (e.g. a $2\times p$ cylinder has $Z = 2(2^p + 3^p)$, entropy rate $\sqrt{3}$), observing numerically that $[\lambda_{max}(B_p)]^{1/p}$ approaches Lieb's constant.

They also develop the graph-theoretic expansion of $W(k)$ in the tradition of DiMarzio–Stillinger and Nagle: writing each nearest-neighbor pair's compatibility as a fluctuation around its mean, the partition function becomes a sum over subgraphs of the lattice, open-ended graphs cancel exactly by construction, and the corrections to the leading term are the closed even-degree (Eulerian) subgraphs — cycles. The leading term is the generalized Pauling (mean-field) estimate $M_k/(k-1)^2 = k - 2 + 1/(k-1)$; an elementary Eulerian cycle with $n$ vertices contributes $(k-2)(k-1)^n / M_k^n = O(1/k^{2n-1})$, so the mean-field term dominates at large $k$. Crucially, they prove that Nagle's $k=3$ cancellation of non-Eulerian subgraphs — those having vertices of degree 1 or 3 — fails for $k>3$: the local three-edge sum equals $(k-2) - 2(k-2)^2 - (k-2)^3 + 2$, which is zero only at $k=3$.

Independent of this program, the neighboring literature has pushed series and numerics far: Bakaev and Kabanovich (1994) derived large-$q$ series for the $q$-color problem on the square lattice; Shrock and Tsai (1997) gave rigorous lower bounds, Monte Carlo values, and series evaluations for $3 \le q \le 10$; Salas and Sokal (2000–2011) and Jacobsen and co-workers developed sparse transfer matrices for the square-lattice chromatic polynomial on strips, extending the large-$q$ expansion of the bulk free energy to order $q^{-47}$ and then $q^{-79}$ with exact rational coefficients. On the triangular lattice this machinery verified Baxter's exact bulk free energy and led to conjectural product formulae for surface and corner free energies; for the square lattice at $q \ge 4$ no closed form is known or conjectured, and the convergence of the $1/k$ expansion is unproven. The source paper itself notes that computing general algebraic expressions for the contributions of complicated cycles 'is tricky and can be another avenue of investigation'.

The source work develops three methodological strands towards this objective — the graph-theoretic subgraph (cycle) expansion of $W(k)$ in powers of $1/k$, the closed-form trace recursions of the Toeplitz-block transfer matrices $B_p$, and the extrapolation of $[\lambda_{max}(B_p)]^{1/p}$ to the infinite-lattice entropy — and these are facets of the single objective of evaluating $W(k)$ exactly or with provable error control. Each strand stops short of general $k$ in that work: the closed-form trace recursions are established only for transverse widths $m \le 4$ at $k=3$; the subgraph expansion is carried out only for the elementary Eulerian cycles at general $k$, the non-Eulerian subgraphs contributing identically zero at $k=3$ but provably nonzero for every $k>3$; and the convergence of $[\lambda_{max}(B_p)]^{1/p}$, observed numerically at $k=3$ towards Lieb's constant, is not controlled.

Problem Statement

Determine $W(k) = \lim_{N\to\infty} P(\text{sq}, k)^{1/N}$, the entropy per site of the $k$-coloring of the square lattice — equivalently the residual entropy per site of the $k$-species close-packed hard-square lattice gas at zero chemical potential, or the ground-state entropy of the zero-temperature $k$-state Potts antiferromagnet on the square lattice — for general $k$. The first open case is $k=4$ (the 21-vertex model); $k=3$ is Lieb's exactly solved case and $k=2$ is trivial. The requested result is an exact closed-form evaluation with proof, or an evaluation with certified, provable error bounds; numerical estimates without proven error control do not suffice.

References

1. Sahil Kumar Singh and Sudhir R. Jain, 'Entropy of hard square lattice gas with k distinct species of particles: coloring problems and vertex models', J. Stat. Mech. (2018) 123102. DOI: 10.1088/1742-5468/aaeb41, arXiv:1806.06751, https://arxiv.org/abs/1806.06751
2. E. H. Lieb, 'Residual Entropy of Square Ice', Phys. Rev. 162, 162 (1967). DOI: 10.1103/PhysRev.162.162, https://doi.org/10.1103/PhysRev.162.162
3. R. J. Baxter, 'Three-Colorings of the Square Lattice: A Hard Squares Model', J. Math. Phys. 11, 3116 (1970). DOI: 10.1063/1.1665102, https://doi.org/10.1063/1.1665102
4. J. F. Nagle, 'Lattice Statistics of Hydrogen Bonded Crystals. I. The Residual Entropy of Ice', J. Math. Phys. 7, 1484 (1966). DOI: 10.1063/1.1705058, https://doi.org/10.1063/1.1705058
5. J. F. Nagle, 'A new subgraph expansion for obtaining coloring polynomials for graphs', J. Combin. Theory B 10, 42 (1971). DOI: 10.1016/0095-8956(71)90066-9, https://doi.org/10.1016/0095-8956(71)90066-9
6. E. A. DiMarzio and F. H. Stillinger, 'Residual Entropy of Ice', J. Chem. Phys. 40, 1577 (1964). DOI: 10.1063/1.1725363, https://doi.org/10.1063/1.1725363
7. A. V. Bakaev and V. I. Kabanovich, 'Series expansions for the q-colour problem on the square and cubic lattices', J. Phys. A: Math. Gen. 27, 6731 (1994). DOI: 10.1088/0305-4470/27/20/013, https://doi.org/10.1088/0305-4470/27/20/013
8. Robert Shrock and Shan-Ho Tsai, 'Asymptotic limits and zeros of chromatic polynomials and ground-state entropy of Potts antiferromagnets', Phys. Rev. E 55, 5165 (1997). DOI: 10.1103/PhysRevE.55.5165, arXiv:cond-mat/9612249, https://arxiv.org/abs/cond-mat/9612249
9. Jesús Salas and Alan D. Sokal, 'Transfer matrices and partition-function zeros for antiferromagnetic Potts models. I. General theory and square lattice chromatic polynomial', J. Stat. Phys. 104, 609 (2001). DOI: 10.1023/A:1010376605067, arXiv:cond-mat/0004330, https://arxiv.org/abs/cond-mat/0004330
10. Jesper Lykke Jacobsen and Jesús Salas, 'Transfer matrices and partition-function zeros for antiferromagnetic Potts models. II. Extended results for square lattice chromatic polynomial', J. Stat. Phys. 104, 701 (2001). DOI: 10.1023/A:1010328721905, arXiv:cond-mat/0011456, https://arxiv.org/abs/cond-mat/0011456
11. Jesús Salas and Alan D. Sokal, 'Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial', J. Stat. Phys. 135, 279 (2009). DOI: 10.1007/s10955-009-9725-1, arXiv:0711.1738, https://arxiv.org/abs/0711.1738
12. Jesper Lykke Jacobsen, 'Bulk, surface and corner free energy series for the chromatic polynomial on the square and triangular lattices', J. Phys. A: Math. Theor. 43, 315002 (2010). DOI: 10.1088/1751-8113/43/31/315002, arXiv:1005.3609, https://arxiv.org/abs/1005.3609
13. Jesús Salas and Alan D. Sokal, 'Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with extra-vertex boundary conditions', J. Stat. Phys. 144, 1028 (2011). DOI: 10.1007/s10955-011-0292-x, arXiv:1002.3761, https://arxiv.org/abs/1002.3761
14. Shu-Chiuan Chang and Robert Shrock, 'Ground state entropy of the Potts antiferromagnet on strips of the square lattice', Physica A 290, 402 (2001). DOI: 10.1016/S0378-4371(00)00457-X, arXiv:cond-mat/0004161, https://arxiv.org/abs/cond-mat/0004161
15. R. J. Baxter, 'Chromatic polynomials of large triangular lattices', J. Phys. A: Math. Gen. 20, 5241 (1987). DOI: 10.1088/0305-4470/20/15/037, https://doi.org/10.1088/0305-4470/20/15/037
16. Y. Martínez-Ratón and E. Velasco, 'Highly confined mixtures of parallel hard squares: A density-functional-theory study', Phys. Rev. E 100, 062604 (2019). DOI: 10.1103/PhysRevE.100.062604, arXiv:1910.09506, https://arxiv.org/abs/1910.09506