Exact growth constant for colourings of the square lattice with more than three colours

The number of proper q-colourings of N-site regions of the square lattice grows exponentially like $W(q)^{N}$, where $W(q)$ is the exponential growth constant of the square-lattice chromatic polynomial, equivalently the per-site ground-state degeneracy of the zero-temperature q-state Potts antiferromagnet. For q=3 the problem is equivalent (up to a factor) to square ice and was solved exactly by Lieb, giving $W(3)=(4/3)^{3/2}$; for q=2 the answer is trivial. For every integer q>3, however, no exact value of $W(q)$ is known: since Biggs (1977) only rigorous two-sided bounds and increasingly precise numerical series and transfer-matrix estimates exist (for q=4 the value lies near 2.34, strictly inside Biggs' bounds $[7/3,\,1+\sqrt2]$). The source paper (da Silva, Nakao and Drugowich de Felício, arXiv:2006.08330) states explicitly that colouring the square lattice with more colours "does not have an exact solution, only an upper and a lower bound are known in the thermodynamic limit". The problem posed here is the exact determination of $W(q)$ for integers $q\ge 4$, the central case being q=4.

Background

A proper q-colouring of a graph assigns one of q colours to each vertex so that adjacent vertices receive different colours; the number of such colourings is the chromatic polynomial $P(G,q)$. For an infinite square lattice one defines the exponential growth constant $W(\mathrm{sq},q)=\lim_{n\to\infty}P(G_{n},q)^{1/n}$, where $G_{n}$ exhausts the lattice; $k_{B}\ln W$ is the ground-state (residual) entropy per site of the q-state Potts antiferromagnet on the square lattice, since the zero-temperature partition function of that model equals the chromatic polynomial.

The prototype is square ice. Pauling's model places a hydrogen atom near one of the two oxygens on each bond with the Bernal–Fowler ice rule (two hydrogens near each oxygen); counting the allowed arrow configurations gives the six-vertex model, in which each lattice vertex must have exactly two arrows pointing in and two out, allowing six local vertex types. As noted by A. Lenard in Lieb's paper, this problem is equivalent, up to a factor of 3, to counting proper 3-colourings of the square lattice, and Lieb (1967) solved it exactly by the Bethe ansatz — an exact technique for diagonalizing the transfer matrix of a two-dimensional vertex model by parameterizing its eigenvectors — obtaining $W(3)=(4/3)^{3/2}\approx 1.5396$ (compared with Pauling's mean-field estimate 3/2). Baxter (1970) re-derived and generalized the 3-colouring partition function with unequal colour activities through a mapping to a hard-squares model, a lattice gas whose particles each occupy a $2\times2$ block of sites with mutual exclusion. Six-vertex models whose vertex types are energetically distinct (unequal weights) are the classical ferroelectric KDP and antiferroelectric F models, also solved exactly by Lieb in 1967; the equal-weight case relevant to ice is the one tied to 3-colourings.

For two colours the lattice is bipartite: every connected bipartite region admits exactly two proper 2-colourings, so $P(G_{n},2)=2$ and the per-site growth constant is $W(2)=1$ exactly. For x>3 colours the exact thermodynamic-limit constant is unknown. Biggs (1977), by a colouring-matrix method, proved the rigorous bounds

$\frac{x^{2}-3x+3}{x-1}\ \le\ \phi(x)\ \le\ \frac{1}{2}\Big(x-2+\sqrt{x^{2}-4x+8}\Big)$

for the growth constant $\phi(x)$ of x-colourings, which at x=3 gives $3/2\le\phi(3)\le(1+\sqrt5)/2$ bracketing Lieb's value, and at x=4 gives $7/3\le\phi(4)\le 1+\sqrt2$. Extensive later work has refined the numerics but not produced an exact value: series expansions (Nagle 1971; Bakaev–Kabanovich 1994), Monte Carlo and rigorous colouring-matrix bounds (Shrock–Tsai 1997 and related work), transfer-matrix studies on strips of width up to 13 and large-q free-energy series to order $q^{-79}$ (Salas–Sokal and Jacobsen–Salas 2000–2010), and a reformulation of the q-colouring problem as a generalized vertex model — for q=4 a 21-vertex model — with Toeplitz-block transfer matrices (equivalently, a close-packed lattice gas of q hard-square species) and a large-q series dominated by the generalized Pauling estimate (Singh–Jain 2018). Numerically $W(4)$ is pinned near 2.34, only slightly above the lower Biggs bound, with no closed form identified.

Structurally, the square-lattice chromatic polynomial is critical on the real interval $q\in[0,3]$ and disordered for q>3. Baxter's exactly solved square-lattice Potts curves in the $(q,v)$ plane ($v=\pm\sqrt q$ and $v=-2\pm\sqrt{4-q}$, where $v=e^{K}-1$ is the Potts bond variable for coupling $K$, so that the zero-temperature antiferromagnetic point $v=-1$ is precisely the chromatic point) meet the zero-temperature line $v=-1$ only at q=3, so the known integrable machinery does not reach the chromatic point for any $q\ge 4$; this is why the case x>3 has remained open since the 1970s.

Problem Statement

Determine the exact thermodynamic-limit growth constant of the chromatic polynomial of the square lattice for more than three colours: for integers $q\ge 4$, compute in closed form

$W(\mathrm{sq},q)=\lim_{n\to\infty}P(G_{n},q)^{1/n},$

where $G_{n}$ is a sequence of finite square-lattice regions exhausting $\mathbb{Z}^{2}$ in the standard way (for instance $L\times L$ regions with free or periodic boundary conditions, for which the limit exists and is boundary-condition independent) — equivalently, the per-site ground-state degeneracy (exponential entropy) of the zero-temperature q-state Potts antiferromagnet on the square lattice, or the entropy of the close-packed q-species hard-square lattice gas. The central case is $q=4$, but the full target — the standard a complete answer must meet — is a general exact expression in q (or at least exact values for each fixed integer $q\ge 4$), so an exact value for $q=4$ alone is not sufficient. A complete answer must come with a proof — an integrable-model solution, an exact evaluation of the relevant generalized vertex model (the 21-vertex model for q=4), or another rigorous derivation — not merely a numerical estimate.

References

1. R. da Silva, O. S. Nakao, J. R. Drugowich de Felício, A connection between the Ice-type model of Linus Pauling and the three-color problem, European Journal of Physics 42, 025101 (2021), DOI 10.1088/1361-6404/abc89f, arXiv:2006.08330 (preprint 2020), https://arxiv.org/abs/2006.08330
2. N. Biggs, Colouring Square Lattice Graphs, Bulletin of the London Mathematical Society 9, 54–56 (1977), DOI 10.1112/blms/9.1.54, https://doi.org/10.1112/blms/9.1.54
3. E. H. Lieb, Residual Entropy of Square Ice, Physical Review 162, 162–172 (1967), DOI 10.1103/PhysRev.162.162, https://doi.org/10.1103/PhysRev.162.162
4. E. H. Lieb, Exact Solution of the Problem of the Entropy of Two-Dimensional Ice, Physical Review Letters 18, 692–694 (1967), DOI 10.1103/PhysRevLett.18.692, https://doi.org/10.1103/PhysRevLett.18.692
5. E. H. Lieb, Exact Solution of the Two-Dimensional Slater KDP Model of a Ferroelectric, Physical Review Letters 19, 108–110 (1967), DOI 10.1103/PhysRevLett.19.108, https://doi.org/10.1103/PhysRevLett.19.108
6. E. H. Lieb, Exact Solution of the F Model of An Antiferroelectric, Physical Review Letters 18, 1046–1048 (1967), DOI 10.1103/PhysRevLett.18.1046, https://doi.org/10.1103/PhysRevLett.18.1046
7. R. J. Baxter, Three-Colorings of the Square Lattice: A Hard Squares Model, Journal of Mathematical Physics 11, 3116–3124 (1970), DOI 10.1063/1.1665102, https://doi.org/10.1063/1.1665102
8. J. F. Nagle, A new subgraph expansion for obtaining coloring polynomials for graphs, Journal of Combinatorial Theory B 10, 42–59 (1971), DOI 10.1016/0095-8956(71)90066-9, https://doi.org/10.1016/0095-8956(71)90066-9
9. A. V. Bakaev, V. I. Kabanovich, Series expansions for the q-colour problem on the square and cubic lattices, Journal of Physics A 27, 6731–6739 (1994), DOI 10.1088/0305-4470/27/20/013, https://doi.org/10.1088/0305-4470/27/20/013
10. R. Shrock, S.-H. Tsai, Asymptotic limits and zeros of chromatic polynomials and ground-state entropy of Potts antiferromagnets, Physical Review E 55, 5165–5178 (1997), DOI 10.1103/PhysRevE.55.5165, https://doi.org/10.1103/PhysRevE.55.5165
11. R. Shrock, S.-H. Tsai, Lower bounds and series for the ground state entropy of the Potts antiferromagnet on Archimedean lattices and their duals, Physical Review E 56, 4111–4124 (1997), DOI 10.1103/PhysRevE.56.4111, arXiv:cond-mat/9707306, https://arxiv.org/abs/cond-mat/9707306
12. R. Shrock, S.-H. Tsai, Ground State Entropy in Potts Antiferromagnets and Chromatic Polynomials, Nuclear Physics B Proceedings Supplement 73, 751–753 (1999), DOI 10.1016/S0920-5632(99)85193-7, arXiv:hep-lat/9809061 (preprint 1998), https://arxiv.org/abs/hep-lat/9809061
13. J. Salas, A. D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models I. General Theory and Square-Lattice Chromatic Polynomial, Journal of Statistical Physics 104, 609–699 (2001), DOI 10.1023/A:1010376605067, arXiv:cond-mat/0004330 (preprint 2000), https://arxiv.org/abs/cond-mat/0004330
14. J. L. Jacobsen, J. Salas, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models II. Extended Results for Square-Lattice Chromatic Polynomial, Journal of Statistical Physics 104, 701–723 (2001), DOI 10.1023/A:1010328721905, arXiv:cond-mat/0011456 (preprint 2000), https://arxiv.org/abs/cond-mat/0011456
15. J. Salas, A. D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models V. Further Results for the Square-Lattice Chromatic Polynomial, Journal of Statistical Physics 135, 279–373 (2009), DOI 10.1007/s10955-009-9725-1, arXiv:0711.1738 (preprint 2007), https://arxiv.org/abs/0711.1738
16. J. L. Jacobsen, Bulk, surface and corner free energy series for the chromatic polynomial on the square and triangular lattices, Journal of Physics A 43, 315002 (2010), DOI 10.1088/1751-8113/43/31/315002, arXiv:1005.3609, https://arxiv.org/abs/1005.3609
17. S. K. Singh, S. R. Jain, Entropy of hard square lattice gas with k distinct species of particles: coloring problems and vertex models, Journal of Statistical Mechanics (2018) 123102, DOI 10.1088/1742-5468/aaeb41, arXiv:1806.06751, https://arxiv.org/abs/1806.06751