A Polynomial related to Colourings of Triangulation of Sphere

by Yuri Matiyasevich

With every triangulation T of a sphere we associate a polynomial M_T in many variables, coefficients of which are related in several unexpected ways to the number c_T of 3-colourings of the edges of the triangulation. Respectively, this allows us to state a number of equivalent reformulations of the famous Four Colour Conjecture (4CC for short).

Let T be a triangulation of a sphere with 2n triangles. Such a triangulation has 3n edges which will be denoted e₀,...,e_3n-1. Let us enumerate the triangles in some way, and let e_pk, e_qk, e_rk be the edges of the kth triangle listed in clock-wise order.

Let us associate with each edge e_i of the triangulation a formal variable x_i, and let us associate with the kth triangle the polynomial S_k equal to

Let N_T denote the (auxiliary) polynomial equal to the product of all 2n polynomials S_k. The polynomial N_T has degree 4 in each of its variables. Let us reduce it to a polynomial M_T of degree 2 in each variable according to the scheme x³-->1, i.e. in each monomial comprising the polynomial N_T we delete variables coming in degree 3, and replace the exponent 4 by exponent 1 for variables coming in degree 4 (such a transformation is justified if the values of the variables are assumed to be cubic roots of 1).

The polynomial M_T is the sum of 3³ⁿ monomials of the form

To simplify notation, we will view the multiindex i₀...i_3n-1 as base-3 notation of the number i=i₀+3i₁+3²i₂+... +3^3n-1i_3n-1, and respectively denote the coefficients of M_T by c₀,...,c_3³ⁿ-1.

Let c_T denote the number of proper colorings of the edges of the triangulation T; we consider colourings as mappings from edges into a 3-element set, so our counting for the triangulation T₂ consisting of just 2 triangles gives c_T2=6 rather that c_T2=1.

It turned out that there are several surprising relations between c_T and c₀,...,c_3³ⁿ-1.

It is easy to see from the definition of c_k that the sum of all of them is equal to 0 and hence they cannot be all of the same sign. Thus we have

COROLLARY 3b. The 4CC is equivalent to the statement that for every triangulation

In fact, the maximum and minimum in the above two corollaries have direct relations with c_T:

THEOREM 4b. c_T = -2min{c₀,...,c_3³ⁿ-1}.

We can also pinpoint a coefficient on which the max in Theorem 4a is reached:

According to Corollary 2, in order to prove the 4CC is sufficient to prove the existence of a coefficient which is non-zero modulo some prime number p. What primes can be used?

Theorem 6 says that p=3 cannot be used for finding a non-zero coefficient.
Theorem 7 says that any other module can be used:

More theorems can be proved about coefficients a_k and b_k introduced in the following way. Let us expand the polynomial S_k as

Then the polynomial N_T, and hence the polynomial M_T as well, can be formally expanded as the sums of 6²ⁿ monomials with coefficients equal to either +1 or -1. Let us collect together those monomials of M_T which are equal completely, i.e. including the signs too. The resulting coefficients will be denoted a_k and b_k. For the sake of simplicity of the statements of theorems, we will use different notation depending on the parity of n. Namely, a_k (respectively, b_k) denotes the number of monomials with coefficient (-1)ⁿ (respectively, -(-1)ⁿ). In other words,

In the new notation Corollary 2 says that the 4CC is equivalent to the statement that the coefficients a_k and b_k are not identical. Moreover, it turned out that their square means should be different too, and again we have a precise expression for c_T:

According to Corollary 2, in order to prove the 4CC it is sufficient to find an index m such that a_m and b_m are different modulo some prime p, and according to Theorem 5 any prime but 3 can be used. More detailed information is known for p=2.

Each of the 6³ⁿ monomials with coefficients +1 or -1 in the above described expansion of the polynomial M_T has its own history consisting in particular choice of one of the 6 terms in each polynomial S_k. Theorem 9 implies that on the histories one can define a symmetric relation of duality in such a way that:

• terms with dual histories are equal;
• for each history there is exactly one dual history;
• histories corresponding to monomials with coefficients -(-1)ⁿ are not self-dual;
• different self-dual histories correspond to different monomials.

In terms of such a relation of duality the 4CC conjecture is equivalent to the existence of self-dual histories. Unfortunately, my proof of Theorem 9 is a computational one and does not produce a combinatorial definition of such duality. Nevertheless, I believe that there exist a natural combinatorial definition of duality of histories which has the above listed properties and for which it will be possible to give a direct proof of the existence of self-dual histories, thus giving a new proof of the Four Colour Theorem.

Other relations between a_k, b_k, c_k and c_T were found later and were stated as Problem 21 in "Combinatorial and Asymptotical Analisys", issue 2, G.P.Egorychev (editor), Krasnoyarskii State University, Krasnoyarsk, 1977, pp. 178-179.

More results of this type were proved later by Dmitrii Karpov.