Polymath Wiki - User contributions [en]

Algebraic formulation of Hadwiger-Nelson problem

2018-05-08T04:23:46Z

Lior: Reverting premature edits

''This is a part of Polymath16 - for the main page, see [[Hadwiger-Nelson problem]].''

Given a [https://en.wikipedia.org/wiki/Unit_distance_graph unit distance graph] <math>G</math>, the edges of the graph are formed by a set of vectors <math>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>\mathcal{G}</math> under addition. The [https://en.wikipedia.org/wiki/Cayley_graph Cayley graph] <math>\Gamma(\mathcal{G},S)</math> is a unit distance graph that will contain <math>G</math> as a subgraph. A coloring of the Cayley graph reduces to a coloring of <math>G</math>, and is an efficient way to set an upper bound on its [https://en.wikipedia.org/wiki/Graph_coloring chromatic number].

In two dimensions it is useful to identify the vectors with complex numbers. For example the [https://en.wikipedia.org/wiki/Eisenstein_integer Eisenstein integers] <math>\mathbb{Z}[\omega]</math> are generated by an equilateral triangle or hexagon with unit length sides. These are complex numbers of the form <math>z = a + b\omega, a,b \in \mathbb{Z}</math> where <math>\omega = \frac{1 + i\sqrt{3}}{2}</math> is a cube root of <math>-1</math>. A 3-colouring is given by a mapping to the group <math>\mathbb{Z}_3</math> defined by <math>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>\mathbb{Z}[\omega]</math> which is of unit modulus is sent to the identity (zero) in <math>\mathbb{Z}_3</math>.

Note that in general a group generated in this way will not be a simple [https://en.wikipedia.org/wiki/Lattice_Group lattice] and in most cases it will be formed from vertices that are dense in the plane.

A <math>k</math>-coloring is '''linear''' if it is given by a group homomorphism onto a finite group of order <math>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>G</math> is combined with a copy of itself rotated about one of its vertices through an angle <math>\theta</math>. In the complex plane the center of rotation <math>O</math> can be placed at zero and another point <math>A</math> connected by an edge <math>OA</math> can be placed at one in the complex plane. The rotation takes <math>A</math> to the point <math>B</math> at <math>\tau = e^{i\theta}</math>. All other points given by complex numbers <math>z \in G</math> are rotated to <math>\tau z</math>. The combination of all possible spindlings and Minkowski sums is therefore contained in the Cayley graph of a ring <math>\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>\mathcal{R}</math> ia an [https://en.wikipedia.org/wiki/Integral_domain integral domain]

The generators <math>\tau_i</math> are chosen so as to add new edges in the graph in addition to themselves. This will makes them [https://en.wikipedia.org/wiki/Algebraic_number algebraic numbers]. If they are [https://en.wikipedia.org/wiki/Algebraic_integer Algebraic integers] then the additive group <math>(\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>\mathcal{R}</math> is therefore a [https://en.wikipedia.org/wiki/Ring_of_integers ring of algebraic integers] <math>\mathcal{Z}</math> extended with some finite set of [https://en.wikipedia.org/wiki/Unit_fraction unit fractions] <math>\mathcal{R} = \mathcal{Z}\left[\frac{1}{n_1},...,\frac{1}{n_m}\right]</math>. In the simplest cases <math>\mathcal{Z}</math> is a ring of [https://en.wikipedia.org/wiki/Quadratic_integer 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 [https://oeis.org/A003136 Loeschian numbers]. Spindling this lattice through angles <math>\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>\omega_3</math> is used to generate a ring <math>\mathcal{M} = \mathbb{Z}[\omega_1, \omega_3, \overline{\omega_3}]</math> which contains [https://en.wikipedia.org/wiki/Moser_spindle Moser spindles]. <math>\omega_1 = \omega = \frac{1+i\sqrt{3}}{2}</math> and <math>\omega_3 = \frac{5 + i\sqrt{11}}{6}</math>

This ring can also be given as <math>\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>\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>

Algebraic formulation of Hadwiger-Nelson problem

2018-05-08T03:22:56Z