Chromatic number of the plane

The unit distance graph on $\mathbb R^2$ has edges between those pairs of points at Euclidean distance $1$ . The chromatic number of this graph lies between $4$ (by exhibiting a small subgraph on $7$ vertices with chromatic number $4$ ) and $7$ (by an explicit colouring based on a hexagonal tiling of the plane). Aubrey de Grey has just posted a construction of a unit distance graph with chromatic number $5$ , raising the lower bound on $\chi(\mathbb R^2)$ by $1$ . This MathOverflow post is a good jumping off point into the discussion online.

I was explaining this problem to a colleague and they asked whether this graph was connected (it is) and whether that was still true if we restricted to rational coordinates. It turns out this was addressed by Kiran B.Chilakamarri in 1988, and the answer is the rational unit distance graph is connected from dimension $5$ onwards.

To see that $\mathbb Q^4$ is not connected, consider a general unit vector $x = (a_1/b, a_2/b, a_3/b, a_4/b)$ where $b$ is coprime to $\gcd(a_1, a_2, a_3, a_4)$ . Then $a_1^2 + a_2^2 + a_3^2 + a_4^2 = b^2$ .

Claim. $b$ is divisible by $2$ at most once.

Proof. Squares mod $8$ are either $0$ , $1$ or $4$ . If $b$ is divisible by $4$ then one of the $a_i$ is odd, hence squares to $1$ mod $8$ . But then $a_1^2 + a_2^2 + a_3^2 + a_4^2$ cannot be divisible by $8$ , which is a contradiction.

So the entries of $x$ in their reduced form do not contain any $4$ ‘s in their denominator, and so the same must hold for all sums of unit vectors. Hence we can’t express, say, $(1/4, 0, 0, 0)$ as a sum of unit vectors, and $(1/4, 0, 0, 0)$ is not connected to $0$ .

Connectedness in dimension $5$ (hence also later) uses Lagrange’s theorem on the sums of four squares. We’ll show that $(1/N, 0, 0, 0, 0)$ can be expressed as a sum of $2$ unit vectors. By Lagrange’s theorem, write $4N^2-1 = a_1^2 + a_2^2 + a_3^2 + a_4^2$ . Then

$1 = \left(\frac 1 {2N}\right)^2 + \left(\frac {a_1} {2N}\right)^2+ \left(\frac {a_2} {2N}\right)^2+ \left(\frac {a_3} {2N}\right)^2+ \left(\frac {a_4} {2N}\right)^2$

hence

$\left(\frac 1 {N},0,0,0,0\right) = \left(\frac 1 {2N},\frac {a_1} {2N},\frac {a_2} {2N},\frac {a_3} {2N},\frac {a_4} {2N}\right)+ \left(\frac 1 {2N}, -\frac {a_1} {2N}, -\frac {a_2} {2N}, -\frac {a_3} {2N}, -\frac {a_4} {2N}\right)$

is a sum of $2$ unit vectors.

Leave a Reply Cancel reply