Exact thermodynamic-limit value of proper $x$-colourings of the square lattice for $x>3$ (the square-lattice chromatic polynomial beyond $q=3$)

How many ways are there to colour the vertices of the infinite square lattice with $x$ colours so that adjacent vertices differ? The exponential growth rate of this count — the chromatic polynomial per site, $W(\mathrm{sq},x)$, equivalently the ground-state degeneracy per site of the $x$-state Potts antiferromagnet on the square lattice at zero temperature — is known exactly only for $x=2$ (trivially, $W=1$) and $x=3$, where the Lenard–Lieb equivalence with Pauling's square-ice (six-vertex) problem yields $W=(4/3)^{3/2}$. The source paper (da Silva, Nakao and Drugowich de Felício, 2021) notes that for more than three colours no exact thermodynamic-limit result exists, only the 1977 bounds of Biggs. No exact thermodynamic-limit value of $W(\mathrm{sq},x)$ is known for $x>3$: the available results are rigorous two-sided bounds (Biggs 1977; tightened by Shrock–Tsai 1997 and Chang–Shrock 2015), the Monte Carlo estimate $W(\mathrm{sq},4)=2.3370(7)$, and convergent large-$q$ series (Jacobsen 2010, to order $q^{-79}$) — every known exact-solution route (the Lenard–Lieb six-vertex mapping, Baxter's critical-line solution) terminates at $x=3$, in marked contrast to the triangular lattice, which Baxter solved exactly for $q\ge4$. The open core is the exact value of $W(\mathrm{sq},x)$ for $x>3$.

Background

Pauling's 1935 theory of ice assigns to each oxygen atom two 'near' hydrogens among its four bonds (the ice rule), giving a macroscopically degenerate proton arrangement whose residual entropy is a pure counting problem. On the two-dimensional square lattice this 'square ice' problem becomes the six-vertex model: an arrow on every lattice edge with exactly two arrows pointing into each vertex, giving six allowed vertex patterns. Lieb (1967) solved it exactly: the number of ice configurations per site tends, in the thermodynamic limit (infinitely many sites), to $W_{\rm ice}=(4/3)^{3/2}\approx1.5396$.

The same constant governs a purely combinatorial problem: proper vertex 3-colourings of the square lattice, i.e. assignments of three colours to vertices such that adjacent vertices differ. As observed by Lenard (reported in Lieb's 1967 paper), taking the difference of the two vertex colours modulo 3 on each edge — a value $\pm1$ — identifies each colouring with an ice-rule arrow configuration, so apart from a factor of three (the global colour permutation) the three-colouring problem is exactly the six-vertex ice problem; hence $W(\mathrm{sq},3)=(4/3)^{3/2}$. The source paper by da Silva, Nakao and Drugowich de Felício — a didactic study that re-derives this connection and estimates the limit with transfer matrices (the standard device that builds a lattice partition function row by row) on grids of up to $N=225$ sites — highlights the number-theoretic interest of this constant and then raises the natural generalization: what happens with more than three colours?

For a general number $x$ of colours the counting function is the chromatic polynomial $P(G,x)$ of the graph $G$ — the polynomial in $x$ that counts proper vertex colourings — and for an infinite lattice the object of interest is the per-site limit

$$W(\mathrm{sq},x)=\lim_{N\to\infty}P(G_N,x)^{1/N},$$

which is independent of boundary conditions in the thermodynamic limit. In statistical mechanics this is the ground-state degeneracy per site of the $x$-state Potts antiferromagnet (spins taking $x$ values, with an energy penalty for equal adjacent spins) at zero temperature: the partition function there equals the number of proper $x$-colourings, and the zero-temperature entropy per site is $k_B\ln W$. On the square lattice, exact values are known only at $x=2$ (the lattice is bipartite, $W=1$) and $x=3$ (Lenard–Lieb; equivalently Baxter's 1982 exact solution of the critical antiferromagnetic square-lattice Potts model, whose critical line $e^{J/k_BT}=-1+\sqrt{4-q}$ is real only for $q\le3$ and meets the zero-temperature point exactly at $q=3$). For every $x>3$ no exact evaluation is known. Biggs (1977) rigorously proved two-sided bounds using a coloring-compatibility-matrix method — bounding $W$ by maximal eigenvalues of matrices that count mutually compatible colourings of adjacent lattice rows: a lower bound $(x^2-3x+3)/(x-1)$ and an upper bound $\tfrac12(x-2+\sqrt{x^2-4x+8})$ — both formulas re-derived with explicit credit to Biggs in the modern bounds literature. At $x=4$ these give $7/3\le W\le1+\sqrt2$, i.e. $[2.3333,2.4142]$.

Later work tightened the bounds and supplied numbers without reaching exactness: Shrock and Tsai (1997) generalized the compatibility-matrix method to Archimedean lattices and their duals, derived two-sided bounds, and measured $W(\mathrm{sq},4)=2.3370(7)$ by Monte Carlo simulation (zero-temperature entropy $0.8489(3)\,k_B$ per site); Chang and Shrock (2015) proved strictly tighter lower bounds, although Biggs' lower bound is already within about 0.2% of the true value at $x=4$; Jacobsen (2010) computed the chromatic polynomials of square-lattice rectangles up to $20\times21$ exactly and extended the large-$q$ series of the bulk free energy to order $q^{-79}$ — a series whose radius of convergence corresponds to $q=3$, so it converges for every real $q>3$, making $W$ numerically accessible there, though in closed form it is not. The contrast with the triangular lattice is striking: Baxter (1987) found an integrable structure there — a hidden infinite-dimensional algebraic symmetry that makes exact solution possible — and an exact infinite-product free energy for $q\ge4$, while the square lattice — the most canonical lattice of all — has resisted every known technique: the mod-3 arrow construction (two edge states per edge) has no analogue for $x>3$, and for $x=4$ colours the analogous construction produces a 21-vertex model with no known solution.

Problem Statement

Let $\Omega_x(N)$ be the number of proper vertex $x$-colourings of an $N$-vertex region of the square lattice (equivalently, colourings of the cells of a square tiling such that cells sharing an edge receive different colours), and define the per-site growth constant

$$W(\mathrm{sq},x)=\lim_{N\to\infty}\Omega_x(N)^{1/N},$$

i.e. the limiting chromatic polynomial per site of the infinite square lattice, independent of boundary conditions. For $x=3$, $W(\mathrm{sq},3)=(4/3)^{3/2}$ exactly. The problem, raised by the source paper following Biggs (1977), is: determine the exact value of $W(\mathrm{sq},x)$ for integer $x>3$, in the first instance $x=4$ (where the classical Biggs bounds are $7/3\le W(\mathrm{sq},4)\le1+\sqrt2$); a complete solution determines the exact value of $W(\mathrm{sq},4)$ (an exact expression, not merely a numerical estimate), while the exact value for every integer $x>3$ — equivalently a closed form of the analytic function $W(\mathrm{sq},q)$ valid for all real $q>3$ — is a stronger result that also resolves the task. Equivalently: obtain the exact zero-temperature free energy (ground-state entropy) of the $x$-state Potts antiferromagnet on the square lattice for $x>3$.

References

1. R. da Silva, O. S. Nakao, and 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. https://doi.org/10.1088/1361-6404/abc89f
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. L. Pauling, 'The Structure and Entropy of Ice and of Other Crystals with Some Randomness of Atomic Arrangement', Journal of the American Chemical Society 57, 2680–2684 (1935). DOI: 10.1021/ja01315a102. https://doi.org/10.1021/ja01315a102
6. R. J. Baxter, 'Critical antiferromagnetic square-lattice Potts model', Proceedings of the Royal Society of London A 383, 43–54 (1982). DOI: 10.1098/rspa.1982.0119. https://doi.org/10.1098/rspa.1982.0119
7. R. J. Baxter, 'Chromatic polynomials of large triangular lattices', Journal of Physics A: Mathematical and General 20, 5241–5261 (1987). DOI: 10.1088/0305-4470/20/15/037. https://doi.org/10.1088/0305-4470/20/15/037
8. R. Shrock and S.-H. Tsai, 'Ground-state entropy of Potts antiferromagnets: Bounds, series, and Monte Carlo measurements', Physical Review E 56, 2733–2737 (1997). DOI: 10.1103/PhysRevE.56.2733; arXiv:cond-mat/9706162. https://arxiv.org/abs/cond-mat/9706162
9. R. Shrock and 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. https://doi.org/10.1103/PhysRevE.56.4111
10. R. Shrock and 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; arXiv:cond-mat/9612249. https://doi.org/10.1103/PhysRevE.55.5165
11. S.-C. Chang and R. Shrock, 'Improved lower bounds on the ground-state entropy of the antiferromagnetic Potts model', Physical Review E 91, 052142 (2015). DOI: 10.1103/PhysRevE.91.052142; arXiv:1502.07254. https://arxiv.org/abs/1502.07254
12. J. L. Jacobsen, 'Bulk, surface and corner free-energy series for the chromatic polynomial on the square and triangular lattices', Journal of Physics A: Mathematical and Theoretical 43, 315002 (2010). DOI: 10.1088/1751-8113-43-31/315002; arXiv:1005.3609. https://arxiv.org/abs/1005.3609
13. J. Salas and A. D. Sokal, 'Transfer matrices and partition-function zeros for antiferromagnetic Potts models VI. Square lattice with extra-vertex boundary conditions', Journal of Statistical Physics 144, 1028–1122 (2011). DOI: 10.1007/s10955-011-0292-x; arXiv:1002.3761 (preprint titled 'Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with special boundary conditions'). https://doi.org/10.1007/s10955-011-0292-x
14. S. K. Singh and S. R. Jain, 'Entropy of hard square lattice gas with $k$ distinct species of particles: coloring problems and vertex models', Journal of Statistical Mechanics: Theory and Experiment 2018, 123102 (2018). DOI: 10.1088/1742-5468/aaeb41; arXiv:1806.06751. https://arxiv.org/abs/1806.06751