Algebraic formulation of Hadwiger-Nelson problem

Given a unit distance graph [math]\displaystyle{ G }[/math], the edges of the graph are formed by a set of vectors [math]\displaystyle{ V }[/math] of unit length. Often a single vector is used many times in the same graph for different edges. The vectors generate an infinite abelian group [math]\displaystyle{ \mathcal{G} }[/math] under addition. The Cayley graph [math]\displaystyle{ \Gamma(\mathcal{G},S) }[/math] is a unit distance graph that will contain [math]\displaystyle{ G }[/math] as a subgraph. A coloring of the Cayley graph reduces to a coloring of [math]\displaystyle{ G }[/math], and is an efficient way to set an upper bound on its chromatic number.

In two dimensions it is useful to identify the vectors with complex numbers. For example the Eisenstein integers [math]\displaystyle{ \mathbb{Z}[\omega] }[/math] are generated by an equilateral triangle or hexagon with unit length sides. These are complex numbers of the form [math]\displaystyle{ z = a + b\omega, a,b \in \mathbb{Z} }[/math] where [math]\displaystyle{ \omega = \frac{1 + i\sqrt{3}}{2} }[/math] is a cube root of [math]\displaystyle{ -1 }[/math]. A 3-colouring is given by a mapping to the group [math]\displaystyle{ \mathbb{Z}_3 }[/math] defined by [math]\displaystyle{ c(z) = x \in \mathbb{Z}, x \equiv a - b \bmod{3} }[/math]. To verify that this is valid it is sufficient to check that no element of [math]\displaystyle{ \mathbb{Z}[\omega] }[/math] which is of unit modulus is sent to the identity (zero) in [math]\displaystyle{ \mathbb{Z}_3 }[/math].

Note that in general a group generated in this way will not be a simple lattice and in most cases it will be formed from vertices that are dense in the plane.

A [math]\displaystyle{ k }[/math]-coloring is linear if it is given by a group homomorphism onto a finite group of order [math]\displaystyle{ k }[/math]. I.e. [math]\displaystyle{ c(x+y) = c(x)+c(y) }[/math] for all [math]\displaystyle{ x,y }[/math] in the ring.

A [math]\displaystyle{ k }[/math]-coloring is periodic with period [math]\displaystyle{ p \in \mathbb{Z} }[/math] if [math]\displaystyle{ c(x+py) = c(x) }[/math] for all [math]\displaystyle{ x,y }[/math] in the ring.

A linear [math]\displaystyle{ k }[/math]-coloring is always periodic with period [math]\displaystyle{ k }[/math].

Rings

The Cayley graph of a group enables us to consider the colorability of graphs formed from all possible repeated Minkowski sums of a graph with itself. Another operation used to create graphs is spindling where a graph [math]\displaystyle{ G }[/math] is combined with a copy of itself rotated about one of its vertices through an angle [math]\displaystyle{ \theta }[/math]. In the complex plane the center of rotation [math]\displaystyle{ O }[/math] can be placed at zero and another point [math]\displaystyle{ A }[/math] connected by an edge [math]\displaystyle{ OA }[/math] can be placed at one in the complex plane. The rotation takes [math]\displaystyle{ A }[/math] to the point [math]\displaystyle{ B }[/math] at [math]\displaystyle{ \tau = e^{i\theta} }[/math]. All other points given by complex numbers [math]\displaystyle{ z \in G }[/math] are rotated to [math]\displaystyle{ \tau z }[/math]. The combination of all possible spindlings and Minkowski sums is therefore contained in the Cayley graph of a ring [math]\displaystyle{ \mathcal{R} = \mathbb{Z}[\tau_1,...,\tau_n] \subset \mathbb{C} }[/math] generated from a set of complex numbers of unit modulus. More specifically [math]\displaystyle{ \mathcal{R} }[/math] ia an integral domain

The generators [math]\displaystyle{ \tau_i }[/math] are chosen so as to add new edges in the graph in addition to themselves. This will makes them algebraic numbers. If they are Algebraic integers then the additive group [math]\displaystyle{ (\mathcal{R}, +) }[/math] will be finitely generated. In most cases they are not algebraic integers, but any algebraic number is equal to an algebraic integer divided by a (rational) integer. The ring [math]\displaystyle{ \mathcal{R} }[/math] is therefore a ring of algebraic integers [math]\displaystyle{ \mathcal{O}_{\mathcal{R}} }[/math] extended with some finite set of unit fractions [math]\displaystyle{ \mathcal{R} = \mathcal{O}_{\mathcal{R}}\left[\frac{1}{n_1},...,\frac{1}{n_m}\right] }[/math]. In the simplest cases [math]\displaystyle{ \mathcal{O}_{\mathcal{R}} }[/math] is a ring of quadratic integers making its elements easy to describe in terms of sums of square roots.

example [math]\displaystyle{ \overline{R}_2 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}] }[/math]

The squared distances between points on the triangular lattice given by the Eisenstein integers in the complex plane are integers from the sequence of Loeschian numbers. Spindling this lattice through angles [math]\displaystyle{ \omega_t = \exp(i\arccos(1 - \tfrac{1}{2t})) }[/math] will form new edges of unit length at the base of isosceles triangles with two sides equal to these distances. In particular [math]\displaystyle{ \omega_3 }[/math] is used to generate a ring [math]\displaystyle{ \overline{R}_2 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}] }[/math] which contains Moser spindles. [math]\displaystyle{ \omega_1 = \omega = \frac{1+i\sqrt{3}}{2} }[/math] and [math]\displaystyle{ \omega_3 = \frac{5 + i\sqrt{11}}{6} }[/math]

This ring can also be given as [math]\displaystyle{ \overline{R}_2 = \mathbb{Z}\left[{\frac{1+i\sqrt{3}}{2}, \frac{1+i\sqrt{11}}{2}, \frac{1}{3}}\right] }[/math] where the first two generators are algebraic integers.

In explicit form it is [math]\displaystyle{ \overline{R}_2 = \left\{\frac{a+ib\sqrt{3}+ic\sqrt{11}+d\sqrt{33}}{4 \cdot 3^k} : a,b,c,d,k \in \mathbb{Z}, a \equiv b \equiv c \equiv d \bmod 2, a+b+c-d \equiv 0 \bmod 4, k \ge 0\right\} }[/math]

example [math]\displaystyle{ \overline{R}_3 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}, \omega_4, \overline{\omega_4}] }[/math]

This ring includes the Moser spindle and an additional rotation to form a 2,2,1 isosceles triangle.

[math]\displaystyle{ \omega_4 = \frac{7+i\sqrt{15}}{8} }[/math]

[math]\displaystyle{ \overline{R}_3 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}, \omega_4, \overline{\omega_4}] = \mathbb{Z}\left[\frac{1+i\sqrt{3}}{2}, \frac{1+i\sqrt{11}}{2}, \frac{1+i\sqrt{15}}{2}, \frac{1}{2}, \frac{1}{3}\right] }[/math]

In explicit form it is [math]\displaystyle{ \overline{R}_3 = \left\{\frac{a+ib\sqrt{3}+ic\sqrt{11}+d\sqrt{33}+e\sqrt{5}+if\sqrt{15}+ig\sqrt{55}+h\sqrt{165}}{2^l \cdot 3^k}, a,b,c,d,e,f,g,h,k,l \in \mathbb{Z}, k,l \ge 0\right\} }[/math]

Coloring Rings

The main goal is to establish the chromatic number of rings that contain graphs known to be of interest to the Hadwiger-Nelson problem. For each ring and each number of colors [math]\displaystyle{ k }[/math] there are four main possibilities:

The ring cannot be [math]\displaystyle{ k }[/math]-colored (X),

the ring can be coloured but only with linear colourings (L),

the ring can be [math]\displaystyle{ k }[/math]-colored with a periodic colouring of periodicity [math]\displaystyle{ p }[/math] (P_{[math]\displaystyle{ p }[/math]})

the ring can be [math]\displaystyle{ k }[/math]-colored with non-linear colorings (periodic or non-periodic) only (N), or

the ring can be [math]\displaystyle{ k }[/math]-colored with in more than one of the above ways (e.g. L+N).

This table summarises what is known. Where there is more than one option shown the correct answer is unknown.

Ring	2-color	3-color	4-color	5-color	6-color	7-color
[math]\displaystyle{ \mathbb{Z} }[/math]	L	L+N	L+N	L+N	L+N	L+N
[math]\displaystyle{ R_1 = \mathbb{Z}[\omega] }[/math]	X	L	L+N	L+N	L+N	L+N
[math]\displaystyle{ R_2 = \mathbb{Z}[\omega, \omega_3] }[/math]	X	X	L+P8	L+N	N	L+N
[math]\displaystyle{ R_3 = \mathbb{Z}[\omega, \omega_3, \omega_4] }[/math]	X	X	X	L or L+N	N	L+N
[math]\displaystyle{ R_H = \mathbb{Z}[\omega, \omega_3, \omega_{64/9}] }[/math]	X	X	X	L or L+N	N	L+N
[math]\displaystyle{ R_4 = \mathbb{Z}[\omega, \omega_3, \omega_4, \omega_7] }[/math]	X	X	X	L or L+N	N	N
[math]\displaystyle{ \mathbb{Z}[\omega, \omega_3, \omega_4, \omega_{25/9}] }[/math]	X	X	X	X or N	X or N	L+N
[math]\displaystyle{ \mathbb{C} }[/math]	X	X	X	X or N	X or N	N

If a ring has a linear [math]\displaystyle{ k }[/math]-coloring then it has a non-linear [math]\displaystyle{ (k+1) }[/math]-coloring

Every ring [math]\displaystyle{ \mathcal{R} \subset \mathbb{C} }[/math] has a non-linear 7-coloring. This follows from the Isbell 7-colouring of the plane.

If a ring [math]\displaystyle{ \mathcal{R} }[/math] contains a unit fraction [math]\displaystyle{ \frac{1}{n} }[/math] and [math]\displaystyle{ k \mid n }[/math] then [math]\displaystyle{ \mathcal{R} }[/math] does not have a linear [math]\displaystyle{ k }[/math]-colouring. This is because for any [math]\displaystyle{ z \in \mathcal{R} }[/math] it follows from linearity that [math]\displaystyle{ z = k\left(\frac{z}{k}\right) }[/math] must be colored with zero.

Therefore [math]\displaystyle{ \mathbb{C} }[/math] has no linear colorings for any finite number of colors.

If a ring has only linear [math]\displaystyle{ k }[/math]-colorings then every element that is [math]\displaystyle{ k }[/math] times another element in the ring will be colored the same as the origin. In This case a new ring can be constructed by spindling that has no [math]\displaystyle{ k }[/math]-coloring.

A coloring for a ring [math]\displaystyle{ \mathcal{R} \subset \mathbb{C} }[/math] can sometimes be constructed as follows

Step 1: find a ring-homomorphism from [math]\displaystyle{ \mathcal{R} }[/math] to a finite ring [math]\displaystyle{ \mathcal{F} }[/math]

Step 2: find the image [math]\displaystyle{ \mathcal{T} }[/math] in [math]\displaystyle{ \mathcal{F} }[/math] of the set of all elements of unit modulus in [math]\displaystyle{ \mathcal{R} }[/math]

Step 3: look for a [math]\displaystyle{ k }[/math]-coloring of [math]\displaystyle{ \mathcal{F} }[/math] such that no two elements that differ by an element in [math]\displaystyle{ \mathcal{T} }[/math] have the same color.

The composition of the ring homomorphism and the coloring of the finite ring [math]\displaystyle{ \mathcal{F} }[/math] will then be a [math]\displaystyle{ k }[/math]-coloring of [math]\displaystyle{ \mathcal{R} }[/math]

An ring of algebraic numbers [math]\displaystyle{ \mathcal{R} }[/math] has a ring homomorphism onto a finite ring [math]\displaystyle{ \mathcal{R}/p\mathcal{R}, p \in \mathbb{Z} }[/math] with the additive structure [math]\displaystyle{ {\mathbb{Z}_p}^d }[/math] where [math]\displaystyle{ d }[/math] is the algebraic degree of [math]\displaystyle{ \mathcal{R} }[/math]. All periodic colorings with period [math]\displaystyle{ p }[/math] can be constructed from a coloring of [math]\displaystyle{ \mathcal{R}/p\mathcal{R} }[/math].

example [math]\displaystyle{ \overline{R}_1 = \mathbb{Z}[\omega] }[/math]

[math]\displaystyle{ \mathbb{Z}[\omega] }[/math] consists of elements of the form [math]\displaystyle{ a + b\omega }[/math] where [math]\displaystyle{ \omega }[/math] is the first cube root of -1. There is a ring homomorphism onto [math]\displaystyle{ \mathcal{F} = \mathbb{Z}[\omega]/3\mathbb{Z}[\omega] = \mathbb{Z}_3[\omega] }[/math] by taking [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] modulo 3. The additive structure of [math]\displaystyle{ \mathcal{F} }[/math] is [math]\displaystyle{ \mathbb{Z}_3 \times \mathbb{Z}_3 }[/math].

The elements of [math]\displaystyle{ \mathbb{Z}[\omega] }[/math] which have unit modulus will map onto elements of [math]\displaystyle{ \mathcal{F} }[/math] for which [math]\displaystyle{ (a - b\omega)(a + b\overline{\omega}) = a^2 + ab + b^2 \equiv 1 \bmod 3 }[/math]. A check of all 9 elements of the group confirms that the only solutions are [math]\displaystyle{ \{\pm 1, \pm \omega, \pm(\omega - 1)\} }[/math].

Coloring the ring [math]\displaystyle{ \mathcal{F} }[/math] is equivalent to filling out a three by three grid with three numbers such that no row or column or cyclic diagonals in one direction has the same number twice. The solution is a latin square unique up to permutations of colours. This can also be specified by the linear colouring [math]\displaystyle{ c(a + b\omega) = a - b }[/math].

example [math]\displaystyle{ \overline{R}_2 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}] }[/math]

The Moser spindle ring is [math]\displaystyle{ \overline{R}_2 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}] = \mathbb{Z}\left[\frac{1+i\sqrt{3}}{2}, \frac{1+i\sqrt{11}}{2}, \frac{1}{3}\right] = \mathbb{Z}\left[\frac{1+i\sqrt{3}}{2}, \frac{1+\sqrt{33}}{2}, \frac{1}{3}\right] }[/math]

[math]\displaystyle{ \overline{R}_2 }[/math] does not have a 3-coloring because it contains the Moser spindle.

To look for a 4-coloring reduce modulo 4, use [math]\displaystyle{ \frac{1}{3} \equiv 3 \bmod 4 }[/math] to get a ring homomorphism from [math]\displaystyle{ \overline{R}_2 }[/math] to the 64 element finite ring [math]\displaystyle{ \mathbb{Z}_4\left[\frac{1+i\sqrt{3}}{2}, \frac{1+\sqrt{33}}{2}\right] }[/math].

[math]\displaystyle{ \alpha = \frac{1+\sqrt{33}}{2} }[/math] is a solution of [math]\displaystyle{ \alpha^2 - \alpha - 8 = 0 }[/math]. This has two solutions modulo 4, [math]\displaystyle{ \alpha \equiv 0,1 \bmod 4 }[/math] either of which can be used to provide a further homomorphism onto the 16 element finite ring [math]\displaystyle{ \mathbb{Z}_4\left[\frac{1+i\sqrt{3}}{2}\right] = \mathbb{Z}_4\left[\omega\right] }[/math]. The elements of unit modulus in this ring are again [math]\displaystyle{ \{\pm 1, \pm \omega, \pm(\omega - 1)\} }[/math] and the linear coloring [math]\displaystyle{ c(a + b\omega) = a - b }[/math].

A computer assisted analysis has confirmed that [math]\displaystyle{ \overline{R}_2 }[/math] has non-linear 4-colorings and that all 4-colorings are periodic with period 8. See also this

example [math]\displaystyle{ \overline{R}_4 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}, \omega_4, \overline{\omega_4}, \omega_7, \overline{\omega_7}] }[/math]

[math]\displaystyle{ \omega_4 = \frac{7+i\sqrt{15}}{8} }[/math] [math]\displaystyle{ \omega_7 = \frac{13+i3\sqrt{3}}{14} }[/math]

[math]\displaystyle{ \overline{R}_3 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}, \omega_4, \overline{\omega_4}] = \overline{R}_2\left[\phi, \frac{1}{2}\right] = \mathbb{Z}\left[i\sqrt{3}, i\sqrt{11}, \sqrt{5}, \frac{1}{2}, \frac{1}{3}\right], \phi = \frac{1+\sqrt{5}}{2} }[/math]

[math]\displaystyle{ \overline{R}_4 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}, \omega_4, \overline{\omega_4}, \omega_7, \overline{\omega_7}] = \overline{R}_3\left[\frac{1}{7}\right] = \mathbb{Z}\left[i\sqrt{3}, i\sqrt{11}, \sqrt{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{7}\right] }[/math]

These rings do not have linear 4-colorings because they contain [math]\displaystyle{ \frac{1}{4} }[/math]. Furthermore they are known not to be 4-colorable by any means because they contain graphs that are not 4-colorable such as [math]\displaystyle{ G_2 }[/math] and [math]\displaystyle{ V_A \oplus V_A \oplus V_A }[/math]

To seek a 5-coloring the rings are first reduced modulo 5 using real equivalences [math]\displaystyle{ \sqrt{5} \equiv 0, \frac{1}{2} \equiv 3, \frac{1}{3} \equiv 2, \frac{1}{7} \equiv 3 \bmod 5 }[/math]

This defines a ring homomorphism from [math]\displaystyle{ \overline{R}_4 }[/math] to [math]\displaystyle{ \mathbb{Z}_5[i\sqrt{3}, i\sqrt{11}] }[/math] whose elements are of the form [math]\displaystyle{ x = a + bi\sqrt{3} + ci\sqrt{11} + d\sqrt{33}, a,b,c,d \in \mathbb{Z}_5 }[/math]

To find the image of the elements of unit modulus in [math]\displaystyle{ \mathbb{Z}_5[i\sqrt{3}, i\sqrt{11}] }[/math] find [math]\displaystyle{ |x|^2 \equiv a^2 + 3b^2 + c^2 + 3d^2 + (ad + bc)\sqrt{33} \equiv 1 \bmod 5 }[/math] which separates into [math]\displaystyle{ a^2 + 3b^2 + c^2 + 3d^2 \equiv 1, ad + bc \equiv 0 \bmod 5 }[/math]. Applying this to the 625 elements of [math]\displaystyle{ \mathbb{Z}_5[i\sqrt{3}, i\sqrt{11}] }[/math] finds 24 elements of unit modulus. It can then be verified that the colouring [math]\displaystyle{ c(x) = a + b + c +d }[/math] does not give zero for any of these elements and is therefore a linear 5-colouring for [math]\displaystyle{ \overline{R}_3 }[/math] and [math]\displaystyle{ \overline{R}_4 }[/math]

example [math]\displaystyle{ \overline{R}_H = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}, \omega_{64/9}, \overline{\omega_{64/9}}] }[/math]

In the ring [math]\displaystyle{ \overline{R}_2 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}] }[/math] it is known that the element [math]\displaystyle{ \frac{8}{3} }[/math] has the same color as zero. Therefore the ring [math]\displaystyle{ \overline{R}_H = \overline{R}_2[\omega_{64/9}, \overline{\omega_{64/9}}] }[/math] formed by spindling this element has no 4-colorings.

[math]\displaystyle{ \omega_{64/9} = \frac{119+3i\sqrt{247}}{128} }[/math] so [math]\displaystyle{ \overline{R}_2[\omega_{64/9}, \overline{\omega_{64/9}}] = \overline{R}_2\left[\sqrt{741}, \frac{1}{2}\right] }[/math]

741 is a square modulo 5 so this can again by mapped by a ring homomorphism to [math]\displaystyle{ \mathbb{Z}_5[i\sqrt{3}, i\sqrt{11}] }[/math] which has a linear 5-coloring. Therefore [math]\displaystyle{ \overline{R}_H }[/math] has a linear 5-coloring.

Unit vectors

A useful application of the algebraic method is to find all edges in a unit distance graph. These are provided by the unit vectors in the additive group of the graph. When the plane is treated as the the Argand diagram these unit vectors are given by complex numbers of unit modulus [math]\displaystyle{ |z|^2 = 1 }[/math]. When the graph is derived from a subring of the complex numbers, the elements of unit modulus form a multiplicative group which is finitely generated if it is derived from a finite graph. The generators of this group can sometimes be determined by factoring [math]\displaystyle{ |z|^2 = 1 }[/math] for a given linear presentation of the ring.

example [math]\displaystyle{ \overline{R}_2 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}] }[/math]

Elements of [math]\displaystyle{ \overline{R}_2 }[/math] take the form [math]\displaystyle{ z = \frac{a+ib\sqrt{3}+ic\sqrt{11}+d\sqrt{33}}{4 \cdot 3^k} }[/math] where [math]\displaystyle{ a,b,c,d }[/math] are integers subject to some congruence relations (see above). The elements of unit modulus are determined by [math]\displaystyle{ |z|^2 = 1 }[/math] which is equivalent to

[math]\displaystyle{ a^2 + 3b^2 + 11c^2 + 33d^2 + (ad + bc)\sqrt{33} = 16 \cdot 3^{2k} }[/math]

Since [math]\displaystyle{ \sqrt{33} }[/math] is irrational this splits into two integer equations. The solutions of [math]\displaystyle{ ad + bc = 0 }[/math] can be parametrised over integers by [math]\displaystyle{ a = wx, b = wy, c = zx, d = -zy }[/math]. Substituting into the rest of the equation gives

[math]\displaystyle{ (wx)^2 + 3(wy)^2 + 11(zx)^2 + 33(-zy)^2 = 16 \cdot 3^{2k} }[/math]

which factorizes to [math]\displaystyle{ (w^2 + 11z^2)(x^2 + 3y^2) = 16 \cdot 3^{2k} }[/math]

Also, [math]\displaystyle{ 4 \cdot 3^k z = wx + wy\sqrt{3} + zx\sqrt{11} - zy\sqrt{33} = (w+z\sqrt{11})(x + y\sqrt{3}) }[/math]

Therefore [math]\displaystyle{ 3^k z = u v }[/math] where [math]\displaystyle{ u \in \mathbb{Z}\left[\frac{1+i\sqrt{3}}{2}\right], |u|^2 = 3^l }[/math] and [math]\displaystyle{ v \in \mathbb{Z}\left[\frac{1+i\sqrt{11}}{2}\right], |v|^2 = 3^{k-l} }[/math]

Both [math]\displaystyle{ \mathbb{Z}\left[\frac{1+i\sqrt{3}}{2}\right] }[/math] and [math]\displaystyle{ \mathbb{Z}\left[\frac{1+i\sqrt{11}}{2}\right] }[/math] are unique factorization domains. Prime factorizations of 3 are given by [math]\displaystyle{ 3 = (-i\sqrt{3}) \times i\sqrt{3} }[/math] in [math]\displaystyle{ \mathbb{Z}\left[\frac{1+i\sqrt{3}}{2}\right] }[/math] and [math]\displaystyle{ 3 = \frac{1+i\sqrt{11}}{2} \times \frac{1-i\sqrt{11}}{2} }[/math] in [math]\displaystyle{ \mathbb{Z}\left[\frac{1+i\sqrt{11}}{2}\right] }[/math]. Units in [math]\displaystyle{ \mathbb{Z}\left[\frac{1+i\sqrt{3}}{2}\right] }[/math] are [math]\displaystyle{ \omega^i }[/math] and [math]\displaystyle{ \pm 1 }[/math] in [math]\displaystyle{ \mathbb{Z}\left[\frac{1+i\sqrt{11}}{2}\right] }[/math]

By prime factorization this gives all solutions for elements of unit modulus in [math]\displaystyle{ \overline{R}_2 }[/math] in the form [math]\displaystyle{ z = \omega^i \eta^j, i,j \in \mathbb{Z} }[/math] where [math]\displaystyle{ \eta = \frac{\sqrt{33}+i\sqrt{3}}{6} = \sqrt{\omega_3} }[/math]

Applications

[math]\displaystyle{ \overline{R}_2 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}] }[/math]

It is known that for 4-colourings in the ring [math]\displaystyle{ \overline{R}_2 }[/math] there can be no monochromtaic equilateral triangles with sides of length [math]\displaystyle{ \sqrt{3} }[/math] This has not yet been demonstrated by means of a human verifiable proof, but once established computationally it can be shown that the ring [math]\displaystyle{ \overline{R}_3 }[/math] is not 4-colorable by hand-checking the ways of colouring graph [math]\displaystyle{ K }[/math]. Another route to the conclusion that the CNP is at least 5 is to show that for 4-colorings in the ring [math]\displaystyle{ \overline{R}_2 }[/math] two vertices at a separation of 8/3 are monochromatic (This is equivalent to a periodicity of 8.) It then follows from an immediate spindling argument that [math]\displaystyle{ \overline{R}_H }[/math] cannot be 4-colored. This method requires further computational steps.

The goal here is to apply algebraic methods to show that 4-colorings of [math]\displaystyle{ \overline{R}_2 }[/math] have a periodicity of 8 given only two assumptions:

• That there are no monochromatic [math]\displaystyle{ \sqrt{3} }[/math]-triangles.
• That any rhombus of unit sides that is not in a single [math]\displaystyle{ \overline{R}_1 }[/math] sub-ring is always coloured with either two or four colours (never three)

The first step is to use the assumption that there are such no monochromatic triangles to demonstrate two features of any 4-coloring [math]\displaystyle{ c_4(z), z \in \overline{R}_2 }[/math] when restricted to a subring [math]\displaystyle{ \overline{R}_1 \subset \overline{R}_2 }[/math]

• That in at least one of the three direction along edges of the [math]\displaystyle{ \overline{R}_1 }[/math] sub-ring, the colouring has peridicity 2, i.e. [math]\displaystyle{ c_4(z+2\omega^a) = c_4(z), z \in \overline{R}_1 }[/math] for [math]\displaystyle{ a = 0,1 }[/math] or [math]\displaystyle{ 2 }[/math].
• That no two points of the same color are separated by an odd integer distance in a direction along edges of the graph

This was shown in the sixth thread

The assumption that a rhombus in any other plane is either 2-coloured or 4-coloured means that given the colour of three of its vertices, the fourth can be determined by an exclusive-or operation. This in turn means that for any parallelogram made from edges of the graph but with sides of any (integer) length, the same rule applies to the colors at its four corner vertices.

Consider now single vertex corresponding to an element of the ring which by translation symmetry we can assume to be the origin without loss of generality. This vertex is also the origin of lattices [math]\displaystyle{ L(\eta^a) }[/math] generated additively by [math]\displaystyle{ \eta^a }[/math] and [math]\displaystyle{ \omega \eta^a }[/math] for all [math]\displaystyle{ a \in \mathbb{Z} }[/math]. As a lattice, group or graph, each [math]\displaystyle{ L(\eta^a) }[/math] is isomorphic to [math]\displaystyle{ \overline{R}_1 }[/math] Therefore by assumption it has a periodicity of two in one of its three directions [math]\displaystyle{ u(a) = \omega^{b(a)} \eta^a, b(a) \in \{0,1,2\} }[/math] for any four coloring [math]\displaystyle{ c_4 }[/math], i.e. [math]\displaystyle{ c_4(x+2u(a)) = c_4(x) }[/math], for all [math]\displaystyle{ x \in L(\eta^a) }[/math].

Consider in particular the four lattices [math]\displaystyle{ L(1), L(\eta^2), L(\eta^4), L(\eta^6) }[/math]. [math]\displaystyle{ b(a) }[/math] takes one of three values so by the pigeon-hole principle it must take the same value for at least one pair out of these four lattices. By rotational symmetry of the ring it can be assumed without loss of generality that the two lattices with periodicity two in the same direction are [math]\displaystyle{ L(\eta^6) }[/math] and [math]\displaystyle{ L(\eta^a) }[/math] for one of [math]\displaystyle{ a = 0,2,4 }[/math], and furthermore that the direction with the perioicity two for these two lattices is [math]\displaystyle{ b(a) = b(6) = 0 }[/math]. Therefore [math]\displaystyle{ c_4(x) = c_4(x+2\eta^a), x \in L(\eta^a) }[/math] and [math]\displaystyle{ c_4(x) = c_4(x+2\eta^6), x \in L(\eta^6) }[/math].

example [math]\displaystyle{ \overline{R}_4 = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}, \omega_4, \overline{\omega_4}, \omega_7, \overline{\omega_7}] }[/math]

[math]\displaystyle{ \overline{R}_4 = \overline{R}_2\left[\frac{1}{2},\frac{1}{7}, \phi \right] }[/math]. Since [math]\displaystyle{ \mathbb{Z}[\phi] }[/math] is another unique factorization domain the same method used to find the elements of unit modulus in [math]\displaystyle{ \overline{R}_2 }[/math] can be used here multiple times to solve this case too. the details are omitted. The result is that elements [math]\displaystyle{ z }[/math] of unit modulus in [math]\displaystyle{ \overline{R}_4 }[/math] must be of the form

[math]\displaystyle{ z = \omega^p \eta^q \zeta^r \alpha^s \beta^t \gamma^u, p,q,r,s,t,u \in \mathbb{Z} }[/math]

where [math]\displaystyle{ \omega = \frac{1 + i\sqrt{3}}{2}, \eta = \frac{\sqrt{33}+i\sqrt{3}}{6}, \zeta = \frac{1 + i\sqrt{15}}{4}, \alpha = \frac{\sqrt{5}+i\sqrt{11}}{4}, \beta = \frac{1+4i\sqrt{3}}{7}, \gamma = \frac{17+3i\sqrt{55}}{28} }[/math]

For the elements of unit modulus in [math]\displaystyle{ \overline{R}_4 }[/math] use just [math]\displaystyle{ \omega^p \eta^q \zeta^r \alpha^s }[/math]