{'fraction_non_alphanumeric': 0.046896251564115116, 'fraction_numerical': 0.020945541591861162, 'mean_word_length': 3.981571815718157, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Iterative Solution of the Three-colour Problem on a Random Lattice

We study the generalisation of Baxter's three-colour problem to a random lattice. Rephrasing the problem as a matrix model problem we discuss the analyticity structure and the critical behaviour of the resulting matrix model. Based on a set of loop equations we develop an algorithm which enables us to solve the three-colour problem recursively


Introduction
Consider a hexagonal lattice with N vertices. In how many ways is it possible to colour the links of the lattice with three colours, A, B and C so that no two links which meet at the same vertex carry the same colour. This is the classical three-colour problem solved by Baxter in 1969 [1]. The problem is equivalent to a loop gas problem, namely the problem of enumerating the number of ways one can cover the lattice with closed, self-avoiding and non-intersecting loops which come in two different flavours, demanding that each vertex of the lattice belongs to a loop. This follows by noting that sequences of, say, B-and C-coloured links form loops which exactly have the properties described above [1]. The loop gas model, on the other hand, is a special version of the O(2) model [2]. Using the equivalence with the loop gas model Baxter furthermore proved that his problem was equivalent to the problem of colouring the faces of the hexagonal lattice with four different colours so that adjacent faces have different colours [1]. The dual lattice of a hexagonal lattice is a triangular lattice. Baxter's three-colour problem can hence also be formulated as the problem of counting the number of ways of colouring the links of the triangular lattice so that the three sides of any triangle have three different colours. In addition, it has recently been shown that Baxter's three-colour problem is equivalent to the problem of counting the different foldings of the regular triangular lattice [3].
In this letter we study the generalisation of Baxter's three-colour problem to a random triangular lattice. This can be viewed as coupling a hitherto unexplored type of matter to two-dimensional quantum gravity. Whereas the regular triangular lattice has six triangles meeting at each vertex, on a random triangular lattice any number of triangles can meet at a given vertex. However, the random lattice three-colour problem shares many features with its regular lattice version. For instance,the random lattice three-colour problem is equivalent to a loop gas model, namely a version of the O(2) model on a random lattice [4] where only loops of even length are allowed. Furthermore, as in the regular lattice case, the random lattice three-colour problem is equivalent to the problem of counting the possible four-colourings of the faces of the dual lattice. However, the random lattice three-colour problem can not be given an interpretation as a folding problem. This requires that only configurations where an even number of triangles meet at a given vertex are allowed. Finally, let us mention that the three-colour problem on a random lattice has recently attracted attention as a means of describing vertex models on random graphs [5].

The Model
The possible three-colourings of the random triangular lattice are generated by the following matrix model where A, B and C are hermitian N × N matrices. More precisely we have the following expansion of the free energy, F (g) = 1 N 2 log Z(g) where N h (2v) is the number of closed, connected, three-coloured random triangulations of genus h consisting of 2v triangles. (Here it is understood that a given triangulation, T , is counted with the weight 1/|Aut(T )| where |Aut(T )| is the order of its automorphism group.) It is important to note that it is necessary to take into account both of the terms Tr (ABC) and Tr (ACB) in (2.1) if one wishes to allow for any cyclic order of the colours around a given triangle. If one considers only triangulations where the colours occur in the same cyclic order for all triangles only one term is needed and the model simplifies drastically. The model with only one term, Tr (ABC), was studied by Cicuta et. al. who extracted numerically the value of the critical coupling constant and the critical index, γ str [6]. Later, it was shown that the model could be mapped onto an O(1) model on a random lattice with a non-polynomial potential and this led to an exact solution of the model [7] showing that the critical indices of the model coincide with those of the Ising model on a random lattice.
In stead of the model (2.1) we shall consider the more general model This model is not more difficult to treat than the model (2.1) and reduces to the latter for n = 1, and (2.4) 3 We note that in analogy with the n = 1 case discussed above, for general n the model (2.3) with only one term n i=1 Tr (AB i C i ) term can be mapped onto an O(n) model with a non-polynomial potential and solved exactly. In particular, the critical indices of the model can be shown to coincide with those of the O(n) model [7].
Integrating over the C-matrices in (2.3) we get (2.5) In this letter we shall concentrate on solving the counting problem for triangulations of spherical topology. We will derive an equation which allows us to calculate, in an efficient way, the genus zero contribution to all correlators of the type 1 N Tr A n iteratively in g. It will be clear, however, how to extend the idea to obtain the higher genera contributions. We note that just knowing 1 N Tr A 2 is enough to solve the three-colour problem, since we have for n = 1, and in particular for genus zero (cf. equation (2.2)) Baxter solved the regular lattice three-colour problem by a transfer matrix method. Recently a transfer matrix formalism for random triangulations has been invented [8] and it is natural to ask whether this formalism can be applied to the present model. It indeed can. A version of the transfer matrix formalism on random lattices, applicable to loop gas models, was presented in [9] and can be applied to the three-colour problem exploiting its equivalence with a variant of the O(2) model on a random lattice. In this approach no reference to any matrix model description is needed. However, we shall stay within the matrix model approach because this gives a faster way of deriving the equations we need.
In the subsequent section we shall write down the saddle point equation corresponding to the matrix integral (2.5). This exposes the analyticity structure of the model and shows why the full three-colour problem is so much more complicated than the restricted one. Actually one can derive the equation we are ultimately after entirely by analyticity arguments, based on the saddle point equation but we shall evoke another line of action, namely the loop equation method. This method has the advantage that it is immediate to see how to proceed to higher genera.

The saddle point equation
Integrating over the B-matrices in (2.5) we get Furthermore, integrating over the angular degrees of freedom leaves us with the following integral over the eigenvalues of the matrix A In the limit N → ∞ the eigenvalue configuration is determined by the saddle point of the integral above. The corresponding saddle point equation reads Following reference [10] we can introduce an eigenvalue density ρ(z) = 1 N i δ(z − λ i ) which in the limit N → ∞ becomes a continuous function, and a resolvant W (z) = This equation describes how W (z) transforms when z crosses the cut and enters into another sheet. In the second sheet, W (z) is a combination of W (z), W (1 − z) and W (−1 − z). Thus in the second sheet there are three cuts: Crossing again these cuts, we generate an increasing number of cuts in the next sheets, which means that W (z) is defined on a Riemann surface of infinite genus and with an infinite number of cuts in each sheet. As opposed to this, for the 1-matrix model (n = 0) W (z) has only one cut and two sheets and for the O(n) model on a random lattice W (z) has only two cuts in each sheet [4]. Here we need to consider and infinite series of cuts {I k } given by and we note that the critical situation referred to above, where one of the eigenvalues approaches − 1 2 or 1 2 , corresponds to the situation where all the cuts merge. One might expect, in analogy with what was the case for the O(n) model on a random lattice, that this type of critical behaviour can only be realized for a certain range of n-values [4]. We note that when this type of critical behaviour is realized the scaling behaviour of the eigenvalue distribution in the vicinity of the endpoints of its support will be as for the O(n) model. For instance, if we consider ρ(z) or equivalently W (z) in the vicinity of z = 1 2 we can view the term W (−1 − z) as being regular and the saddle point equation reduces to that of the O(n) model on a random lattice.
Let us now show how it is possible, using the saddle point equation, to build from W (z) a function which has no cut at all. First we define Then we can write the saddle point equation as Multiplying this equation by W (z k + i0) − W (z k − i0) we find that the function has no cut along I k (while it of course has cuts along I k−1 and I k+1 ). Now it is easy to see that the following function, S(z),has no cut at all Here R(z) is the polynomial part of W (z)V ′ (z) which we have subtracted in order to ensure that the sum converges. Since S(z) can have no singularities apart from the above mentioned cuts it must be analytic in the whole complex plane. Furthermore, it is easy to see that S(z) fulfils the following relations S(1 − z) = S(z), S(z + 2) = S(z). (3.10) From the periodicity relation it follows that S(z) can be written as a Fourier series Now it is actually possible by pure analyticity arguments to show that S p = 0 ∀p, i.e. that S(z) is identically equal to zero. However, we shall derive this result by another method, namely by means of the loop equations of the model. These equation have the advantage that they contain also information about higher genera contributions.

The loop equations
The loop equations simply express the invariance of the matrix integral (2.5) under analytic redefinitions of the integration variables. Let us introduce the notation B = (B 1 , . . . , B n ) and let us define where the subscript conn refers to the connected part. We note that the leading contribution to all of the above listed correlators is of the order N 0 . Now, let us perform the following redefinition of the field A This gives rise to the identity Furthermore, considering the following redefinition of the field B we find We see that as announced the loop equations (as usual) permit a study of higher genera contributions. However, in the following discussion we shall restrict ourselves to genus zero. First, we note that equation (4.7) simplifies considerably when z + x = ±1 ≡ δ. Then, setting x = δ − z and combining (4.5) and (4.7) we find Replacing z by z k , and δ by (−1) k we have δ − z k = z k+1 and summing over k (from k 1 to k 2 − 1) we get The right hand side vanishes when k 1 → −∞ and k 2 → +∞, while the left hand side is precisely the function S(z) of equation (3.9). Therefore we have S(z) = 0. (4.10) We thus have a closed (non-local) equation for W , which could in principle allow us to retrieve W (z).

An equation for the moments
We shall now write equation (4.10) in a more manageable form, namely as an equation for the moments t m = 1 N T rA m , related to W (z) by We shall use the normalisation condition t 0 = 1 which corresponds to requiring that the eigenvalue distribution is normalised to one.
First, we note that we can write Next, we introduce the following functions The functions ζ m (z) can be determined explicitly (by Fourier transform). One has In other words ζ m (z) = π sin πz m P m (sin πz) where P m is a polynomial of degree less than or equal to m − 1. Actually, we can give an explicit expression for this polynomial, namely P m (s) consists of the first m − 1 powers of s in the power series expansion of s arcsin s m for s in the vicinity of zero. The functions ζ m,p (z) and ζ m,p (z) can be expressed in terms of the ζ k (z) as follows Now, starting from the expression (5.1) and choosing the potential of our model as we can write Using relations (5.8) and (5.9), and identifying the coefficients of each ζ m we get for m ≥ 1 This equation is equivalent to equation (4.10) and contains all information about the full non-perturbative solution of the model. Lacking a means of solving this equation exactly we shall in the next section describe how a perturbative solution can be found.

Perturbative solution
Let us specialise to the case of a Gaussian potential, i.e. V ′ (z) = z, but keep n arbitrary. Setting n = 1 at any stage of the calculation then brings us to the three-colour problem. For a quadratic potential, obviously t 2m+1 = 0, ∀m, and the function W (z) is an odd function of z which is analytic in the complex plane except for a cut of the type [−a, a] ⊂ [− 1 2 , 1 2 ]. The relation (5.11) in this case reduces to 2k + 2l + 1 2k + 1 t 2(m+k) t 2l , m ≥ 1. (6.1) This equation can be solved perturbatively in g: First we note that for g = 0, the model under consideration is nothing but the Gaussian one-matrix model for which the function W (z) is known to be To the zeroth order in g we hence have Using as initial condition (6.4) and the normalisation condition T 0 = 1, it is obvious that equation (6.2) allows one to calculate the individual moments order by order in g. We remind the reader that just knowing the moment T 1 (for n = 1) one has the solution of the three-colour problem on a random lattice (cf. equation (2.7)). Writing g i it appears that to determine T = 5544n + 9520n 2 + 4840n 3 + 800n 4 + 32n 5 , T (6) 1 = 56628n + 119704n 2 + 84216n 3 + 23440n 4 + 2400n 5 + 64n 6 .
Unfortunately, we have not been able to express T 1 (g) in a closed form, neither for n general, nor for n = 1. However, we can do better than determining the moments individually. As we shall see, by an appropriate ansatz we can replace the quadratic recursion relation (6.2) by a linear one and solve simultaneously for all T i . In stead of solving the model iteratively in g we shall solve it iteratively in a 2 where a is the endpoint of the cut of W (z). It is obvious from the eigenvalue integral This relation expresses the fact that W (z) has a square root branch point at z = a. Equation (6.5) can be solved iteratively in d. To leading order in d the solution is again given by (6.3), i.e. we have Based on an analysis of the structure of the solution found after the first steps of the iteration process we introduce the following ansatz This ansatz fulfills the boundary condition (6.7) to any finite order in d and the requirement that equation (6.5) should be satisfied and that T 0 = 1 will give us a linear recursion relation for the v j 's. We note that the function X = X(d) encodes the information about the critical behaviour of the model. Critical behaviour occurs when the radius of convergence of the power series X = X(d) is reached. We know that we will encounter one type of singularity when d approaches 1 16 but there might be others. Inserting the ansatz (6.9) in (6.5) we get Since this equation must be fulfilled for any value of m and to any order in d the quantity in the curly bracket must vanish. This implies that for all s we have Since v 0 = 0 this equation can only be satisfied for all s if the term in the curly bracket vanishes for all q, i.e.
v b τ l+b d l+b 2q + 2l + 1 2q + 1 = 0. (6.14) Now we have succeeded in replacing the quadratic recursion relation (5.11) by a linear one! The relation (6.14) must be supplemented by the normalisation condition From (6.14) and (6.15) we can determine X, {v i } ∞ i=1 and hence W (z) to (in principle) any order in d. Inserting the expansion (6.10) in (6.14) and (6.15) we get v (i) where on our way we have made use of the initial condition v (0) i = 0 for i = 0. To solve recursively these equations we determine in each step first v (i) 0 , next X (i) and then v (i) j , for j > 0. We note that in order to determine X(d) and W (z) to order s in d we need only to know {v (j) i } i=0,...s;j=0,...,s−i . Since by our iteration process we find indeed a perturbative solution of equation (6.5) and since this equation is known to have a unique perturbative solution our ansatz is justified. Below we give the function X(d) to the first seven orders in d X (1) = 2n, X (2) = 12n, X (3) = 100n, X (4) = 980n − 12n 2 , X (5) = 10584n − 360n 2 , X (6) = 121968n − 7424n 2 , X (7) = 1472328n − 132160n 2 + 240n 3 .
We remind the reader that the function X = X(d) is related to the endpoint of the cut of W (z) by the relation (6.6) and that the three-colour problem corresponds to the case n = 1. Unfortunately, we have not been able to express X(d) in a closed form, neither for n general, nor for n = 1. However, we recognise the coefficient of the term linear in n as the integral of an elliptic function [11] 2 d+12 d 2 +100 d 3 +980 d 4 +. . . = ∞ k=1 [(2k)!] 2 (k!) 3 (k + 1)! d k = 1 8πd 16d 0 K(t 1/2 ) dt − 1 (6.18) We here explicitly see that the model becomes singular when d approaches 1 16 as argued earlier. By means of our results for X(d) we can determine the corresponding value of the coupling constant, namely In particular, using (6.18), we find to the first order in n 1 g c = 16 1 + n 4 π − 1 + O(n 2 ) . (6.20)

Conclusion
Exploiting the matrix model formulation of the three-colour problem on a random lattice we have developed an algorithm which allows us to solve the problem recursively. In addition we have exposed the analyticity structure of the problem and argued why the full three-colour problem is so much more difficult to solve than its restricted counterpart. Let us finish by mentioning an interesting observation. By arguments analogous to those given in the introduction for the three-colour model it can be seen that the model given by (2.3) is equivalent to an O(2n) model on a random lattice where the loops are restricted to having even length. We have seen that the critical behaviour of the model (2.3) is the same as that of the O(n) model on a random lattice. Hence, restricting the loops to be of even length takes the O(n) model to the universality class of the O( n 2 ) model.