Analytic evaluation of the square-lattice k-coloring entropy W(k) beyond the exactly solved k=3 ice point: higher-cycle algebra, non-Eulerian subgraphs for k>3, and finite-width Toeplitz transfer-matrix recursions

The number of proper k-colorings of the square lattice — equivalently, the close-packing entropy of a lattice gas of k hard-square particle species with infinite repulsion between same-species nearest neighbors, or of a generalized vertex model with $M_k=(k-1)^3-(k-1)^2+(k-1)$ allowed vertex configurations — grows as $[W(k)]^N$ on $N$ sites. $W(3)=(4/3)^{3/2}$ is exact (Lieb's square-ice constant), and for $k\geq 4$ the values are already pinned numerically by convergent large-q series ($W(4)\approx 2.33606$), but no closed-form analytic evaluation exists for any $k\geq 4$. Singh and Jain (2018) recast $W(k)$ as a vertex-model transfer-matrix problem and initiated a Nagle-type subgraph expansion in which elementary Eulerian cycles contribute $(k-2)(k-1)^n/M_k^n$ in closed form, while non-Eulerian subgraphs, whose contributions cancel identically at $k=3$ by Nagle's theorem, contribute nonzero terms $(k-2)-2(k-2)^2-(k-2)^3+2$ for $k>3$. The open problem is the analytic (closed-form) evaluation of $W(k)$ for general $k$: closed-form contributions of complicated cycles and their lattice multiplicities; systematic incorporation or resummation of the non-Eulerian contributions for $k>3$; closed-form finite-width Toeplitz-block trace recursions beyond $m=4$ rows; and analytic extrapolation of transfer-matrix eigenvalue estimates to $W(k)$.

Background

The residual entropy of ice (the entropy that remains at zero temperature because many atomic arrangements are compatible with the same ground state) was estimated by Pauling (1935) by treating local bond arrangements as independent, giving $W\approx 3/2$ per molecule; Lieb (1967) computed the exact value $W(3)=(4/3)^{3/2}\approx 1.5396$ for the two-dimensional analogue, square ice, by solving the six-vertex model — the vertex model on the square lattice in which each of the four edges at a vertex carries an arrow and only the six 'ice-rule' configurations with two arrows in and two out are allowed, each with unit weight. Lenard (as recounted in Lieb's paper) observed that, up to a factor of three, counting proper 3-colorings of the square lattice (coloring the faces with colors $1,2,3$ so that adjacent faces differ) is the same problem: orienting every edge from color $i$ to color $i+1$ (mod 3) turns a proper 3-coloring into an ice-rule configuration. Baxter (1970) solved the three-coloring model with arbitrary color activities exactly, formulating it as a hard-squares model (a lattice gas whose particles each forbid occupation of the adjacent sites).

For general $k$, the number $C_N(k)$ of proper k-colorings of an $N$-site square lattice — the chromatic polynomial $P(G,k)$ of the lattice graph, i.e. the zero-temperature partition function of the k-state Potts antiferromagnet (the spin model whose interaction energy penalizes equal colors on adjacent sites) — grows as $[W(k)]^N$. Physically, $W(k)$ is the close-packing entropy of a lattice gas of $k$ particle species with infinite repulsion between same-species nearest neighbors: each species occupies an independent set (a set of sites no two of which are nearest neighbors), and close packing forces a proper coloring of every site. Singh and Jain (2018) map the k-coloring problem to a generalized vertex model: put a state $e\in\mathbb{Z}_k\setminus\{0\}$ on each edge, defined as the difference of the two adjacent face colors modulo $k$, so that (i) the two states of any edge, read from its two ends, sum to $0$ mod $k$, and (ii) the four edge states around any vertex sum to $0$ mod $k$. Exactly $M_k=(k-1)^3-(k-1)^2+(k-1)$ vertex configurations satisfy these rules ($k=3$: the six-vertex model; $k=4$: a 21-vertex model), and each admissible edge-state configuration corresponds to exactly $k$ colorings, a factor irrelevant per site in the thermodynamic limit.

Nagle (1966, 1971) developed a subgraph expansion for such entropy constants: writing each vertex weight relative to its mean-field value, the correction terms to the Pauling estimate are indexed by subgraphs of the lattice, and at $k=3$ all 'non-Eulerian' subgraphs — those containing a vertex of odd degree 1 or 3 in the subgraph — cancel identically, leaving only even-degree ('Eulerian') subgraphs whose lowest members are elementary cycles. The generalized Pauling estimate reads $W(k)\approx M_k/(k-1)^2=k-2+1/(k-1)$, with $W(k)\sim k$ at large $k$. Singh and Jain generalized the expansion to arbitrary $k$: an elementary Eulerian cycle with $n$ vertices contributes $(k-2)(k-1)^n/M_k^n$ in closed form (at $k=3$, $n=4$ this reproduces Nagle's series term $1/3^4$), so the corrected estimate $W(k)\approx(M_k/(k-1)^2)(1+(k-2)(k-1)^4/M_k^4)$ already tracks the known values for $k=4,\dots,7$ well. However, the three-edge non-Eulerian vertex contribution sums to $(k-2)-2(k-2)^2-(k-2)^3+2$, which vanishes at $k=3$ (Nagle's result) and is nonzero for every $k>3$: the cancellation mechanism that makes the ice expansion tractable fails, and no systematic treatment of these terms exists.

On the numerical side, $W(k)$ for $k\geq 4$ has long been pinned: Bakaev and Kabanovich (1994) and subsequently Jacobsen (2010) — building on the transfer-matrix and chromatic-zero (zeros of the chromatic polynomial in the complex plane) studies of Salas and Sokal (2001) — computed the large-q series of the bulk free energy of the square-lattice chromatic polynomial to order $z^{79}$ in $z=1/(k-1)$, with radius of convergence $|z|=1/2$ (the boundary $k=3$ is the edge of the square-lattice chromatic critical region $0\leq q\leq 3$). The series therefore converges for all real $k\geq 4$ and gives, e.g., $W(4)\approx 2.33606$, $W(5)\approx 3.25040$. These coefficients are exact integers obtained by the finite-lattice method (exact partition functions of finite rectangles combined with fixed weights); they are not closed-form algebraic expressions organized per subgraph class, and they yield no exact value of $W(k)$ for any $k\geq 4$. On the triangular lattice, by contrast, Baxter obtained analytical expressions for the bulk chromatic free energy (verified term by term against the series by Jacobsen 2010); the square lattice beyond the ice point remains analytically unsolved, and the $k\geq 4$ vertex models (such as the 21-vertex model at $k=4$) are not known to be integrable (exactly solvable by analytic means, as the six-vertex model is).

For the transfer-matrix program of the source paper: with open (non-periodic) boundary conditions along the rows, the transfer matrices possess a block Toeplitz structure (block matrices constant along diagonals, with blocks $A_{n,p}$ indexed modulo $k$, of dimension $(k-1)^p$ for general $k$). For rows of $p$ sites, the row-to-row transfer matrix is the sum of these blocks, $B_p=\sum_{n=1}^{k-1}A_{n,p}$ (paper Eq. (21)); at $k=3$, where each edge carries one of two states, this reduces to $B_p=A_p+A_p^{T}$ (paper Eq. (5)). A cylindrical lattice (periodic boundary conditions in the transfer direction) with $m$ rows of $p$ sites, the last row connected to the first, has partition function $Z_{m\times p}=\mathrm{Tr}[B_p^m]$. At $k=3$ the closed-form trace identities $\mathrm{Tr}[A_p^n]=2^p$ and $\mathrm{Tr}[A_p^nA_p^{T}]=(n+2)^p$ yield closed-form partition functions for $m\leq 4$: $Z_{2\times p}=2(2^p+3^p)$, $Z_{3\times p}=2^{p+1}+6\cdot 4^p$, and $Z_{4\times p}$ governed by the eigenvalues $(7\pm\sqrt{33})/2$. Numerically, $[\lambda_{\max}(B_p)]^{1/p}$ — the per-site partition function of a cylinder with rows of $p$ sites in the limit of infinitely many rows — at $k=3$ for $p\leq 10$ extrapolates to $1.53967$, versus Lieb's exact $1.5396007$.

Problem Statement

Let $W(k)=\lim_{N\to\infty}C_N(k)^{1/N}$, where $C_N(k)$ is the number of proper k-colorings of the faces of an $N$-site square lattice, i.e. assignments of the $k$ colors to the faces so that adjacent faces differ (coloring the sites instead of the faces gives the same $W(k)$, since the square lattice is self-dual). Equivalently, $W(k)$ is the exponential growth constant of the chromatic polynomial of the square lattice, or the close-packing entropy of the k-species hard-square lattice gas / generalized vertex model with $M_k=(k-1)^3-(k-1)^2+(k-1)$ vertex configurations. $W(3)=(4/3)^{3/2}$ is exact and the numerical values of $W(k)$ for $k\geq 4$ are pinned by convergent large-q series. The problem is the analytic evaluation of $W(k)$ for general $k$ beyond the exactly solved $k=3$ case — a closed-form result (an exact expression for $W(k)$, or an expansion or finite-width recursion with closed-form coefficients and proved convergence to $W(k)$), not a restatement of the numerically pinned values. The four directions below are the current lines of attack on this objective:

(1) Cycle algebra. In the subgraph expansion of $W(k)$, in which the generalized Pauling estimate $M_k/(k-1)^2$ is corrected by subgraph terms and elementary Eulerian cycles of $n$ vertices contribute the closed form $(k-2)(k-1)^n/M_k^n$, derive the general algebraic expressions for the contributions of the Eulerian cycles and subgraphs beyond the elementary four-edge plaquette order — the non-elementary closed cycles and the composite Eulerian subgraphs, enumerated by vertex count $n$ — each with its lattice combinatorial multiplicity, for arbitrary $k$.

(2) Non-Eulerian sector. The three-edge vertex contribution sums to $(k-2)-2(k-2)^2-(k-2)^3+2$, which vanishes at $k=3$ (Nagle's theorem) but is nonzero for every $k>3$, so the cancellation that organizes the ice expansion is lost. Determine how the non-Eulerian subgraphs are to be systematically incorporated — or resummed — into an analytic evaluation of $W(k)$ for $k>3$.

(3) Finite-width transfer matrices. The Toeplitz-block transfer matrices yield closed-form trace recursions and partition functions $Z_{m\times p}=\mathrm{Tr}[B_p^m]$ only for $m\leq 4$ periodic rows (at $k=3$); for larger $m$ the coupled recursions for traces of the strip transfer matrix $A_p$ and its transpose, such as $\mathrm{Tr}[A_p^{m_1}(A_p^{T})^{m_2}\cdots]$, resist closed-form prediction. Extend the closed-form finite-width trace recursions and dominant-eigenvalue extraction beyond $m=4$, and to general $k$.

(4) Infinite-width extrapolation. Establish that $[\lambda_{\max}(B_p)]^{1/p}\to W(k)$ as $p\to\infty$ for general $k$ (here $B_p=\sum_{n=1}^{k-1}A_{n,p}$ is the row transfer matrix of a cylinder with rows of $p$ sites; at $k=3$, $B_p=A_p+A_p^{T}$), going beyond the existing $k=3$ numerical fits ($p\leq 10$, fitted limit 1.53967 vs the exact 1.5396007).

These four directions are complementary approaches to the single objective stated here, not four independent subgoals: progress along one of them is a partial result unless it yields an analytic evaluation of $W(k)$ for general $k$.

References

1. Sahil K. 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-172 (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-3124 (1970). DOI: 10.1063/1.1665102. https://doi.org/10.1063/1.1665102
4. L. Pauling, 'The Structure and Entropy of Ice and of Other Crystals with Some Randomness of Atomic Arrangement', J. Am. Chem. Soc. 57, 2680-2684 (1935). DOI: 10.1021/ja01315a102. https://doi.org/10.1021/ja01315a102
5. J. F. Nagle, 'Lattice Statistics of Hydrogen Bonded Crystals. I. The Residual Entropy of Ice', J. Math. Phys. 7, 1484-1491 (1966). DOI: 10.1063/1.1705058. https://doi.org/10.1063/1.1705058
6. J. F. Nagle, 'A new subgraph expansion for obtaining coloring polynomials for graphs', J. Comb. Theory B 10, 42-59 (1971). DOI: 10.1016/0095-8956(71)90066-9. https://doi.org/10.1016/0095-8956(71)90066-9
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-6739 (1994). DOI: 10.1088/0305-4470/27/20/013. https://doi.org/10.1088/0305-4470/27/20/013
8. J. Salas and A. 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-699 (2001). DOI: 10.1023/A:1010376605067; arXiv:cond-mat/0004330. https://arxiv.org/abs/cond-mat/0004330
9. 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
10. R. J. Baxter, 'Chromatic polynomials of large triangular lattices', J. Phys. A: Math. Gen. 20, 5241-5261 (1987). DOI: 10.1088/0305-4470/20/15/037. https://doi.org/10.1088/0305-4470/20/15/037
11. Yuri Martínez-Ratón and Enrique 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