Algebraic formulation of Hadwiger-Nelson problem

This is a part of Polymath16 - for the main page, see 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]

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{Z} }[/math] extended with some finite set of unit fractions [math]\displaystyle{ \mathcal{R} = \mathcal{Z}\left[\frac{1}{n_1},...,\frac{1}{n_m}\right] }[/math]. In the simplest cases [math]\displaystyle{ \mathcal{Z} }[/math] is a ring of quadratic integers making its elements easy to describe in terms of sums of square roots.

example: 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{ \mathcal{M} = \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{ \mathcal{M} = \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{ \mathcal{M} = \left\{\frac{a+ib\sqrt{3}+ic\sqrt{c}+d\sqrt{33}}{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]

Rings generated by quadratic irrationals

For [math]\displaystyle{ d\equiv 1\,(4) }[/math] write [math]\displaystyle{ \xi_d = \frac{1+\sqrt{d}}{2} }[/math] so that the ring of integers of [math]\displaystyle{ \mathbb{Q}(\sqrt{d}) }[/math] is [math]\displaystyle{ \mathbb{Z}[\xi_d] = \mathbb{Z}\oplus \mathbb{Z}\xi_d }[/math]. Writing [math]\displaystyle{ d = 1-4t }[/math] we have [math]\displaystyle{ \omega_t = \frac{2t+1+i\sqrt{1-4t}}{2t} }[/math].

We fix a set [math]\displaystyle{ D = \left\{ d_j\right\} }[/math] of relatively prime integers congruent to [math]\displaystyle{ 1 }[/math] mod [math]\displaystyle{ 4 }[/math]. Let [math]\displaystyle{ \Xi_D = \left{\xi_d\}_{d\in D} }[/math] be the associated algebraic integers and let [math]\displaystyle{ K = \mathbb{Q}(\Xi_D) = \mathbb{Q}\left(\{\sqrt{d}\}_{d\in D}\right) }[/math] be the field generated by the square roots of numbers in [math]\displaystyle{ D }[/math]. Write [math]\displaystyle{ \mathcal{O}_K }[/math] for the ring of integers of [math]\displaystyle{ K/math\gt . '''Lemma 1''' \lt math\gt \mathcal{O}_K }[/math] = \mathbb{Z}[\Xi_D]</math> with one integral basis being [math]\displaystyle{ \left\{ \prod_{d\in N}\xi_d \right\}_{N\subset D} }[/math].