Noga Alon recently stopped by my department earlier this month to give two talks. During his visit, he pointed me to some interesting recent work he had done on coloring the plane, buried in the discussion at the end of his preprint “Unit and distinct distances in typical norms” (arXiv:2302.09058, with Matija Bucić and Lisa Sauermann). Recall that the still-unsolved Hadwiger–Nelson problem asks how many colors are needed to color the points of the plane so that no two points at distance one from each other have the same color. The figure below shows a 7-coloring in the pattern of a hexagonal tiling, with this property, so at most seven colors are needed. The black unit distance graph outlined in the same figure, the Moser spindle, requires four colors, but by now much larger and more complicated unit distance graphs are known that force the number of colors to be at least five.

Seven-coloring of the plane with superimposed Moser spindle

The preprint asks, what if we use a different distance function for the plane, defined by a non-Euclidean norm? The answer turns out to be very different: for most such distances, the optimal number of colors is four.

Any norm in the \(d\)-dimensional space \(\mathbb{R}^d\) can be described by its unit ball, a centrally symmetric convex body, and any centrally symmetric convex body defines a norm. The distance between two points is measured by the factor you would need to scale the body so that if you center it at one of the two points it touches the other one. A unit vector, for a distance defined in this way, is just a point on the boundary of the unit ball. For Euclidean distance in the plane the unit ball is a circular disk, and it is also common in computational geometry to consider norms whose unit ball is a regular polygon (with evenly many sides), such as a square or hexagon. But infinitely many other less-regular shapes are also possible, each defining its own distance. Because these distances are different from each other, the number of colors they need may also be different, and may be easier to compute. For instance, for a square unit ball, you can use a square tiling instead of the hexagonal one and color the tiling with only four colors (being careful of how to handle boundary points) so that no two points at unit distance have the same color:

Four-coloring of the plane for a square norm

Alon, Bucić, and Sauermann approach this problem by treating \(\mathbb{R}^d\) as an infinite-dimensional vector space over the rational numbers rather than a \(d\)-dimensional vector space over the real numbers, and asking questions about which subsets of the unit vectors are rationally independent (treating a unit vector and its negation as being the same for this purpose). That means that there is no way to produce one of the vectors as a weighted combination of other vectors in the same set, with rational numbers as the weights. This is much in the same spirit as using Dehn invariants to study polygonal dissections where again, it is rational dependence more than real dependence that is central.

For a polygonal distance, any two unit vectors on the same side of a polygon have infinitely many rational combinations that are also unit vectors. If \(u\) and \(v\) are unit vectors on one side of a convex polygon, and \(p\) is any rational number with \(0\lt p\lt 1\), then \(pu+(1-p)v\) is a rational combination that lies between \(u\) and \(v\) on the same side of the polygon. Because it is on the boundary of the polygon, it is a unit vector. For the Euclidean distance, we have to be more careful, but there still can be infinitely many rational combinations that are also unit vectors. For instance, if \(x=(1,0)\) and \(y=(0,1)\) are the axis-parallel unit vectors of a Cartesian coordinate system, their rational combination \(\tfrac12 x + \tfrac12 y = (\tfrac12,\tfrac12)\) is not a unit vector for Euclidean distance (its length is \(1/\sqrt2\)), and the unit vector in the same direction, \((1/\sqrt2,1/\sqrt2)\), is not a rational combination of \(x\) and \(y\). However, if \(a^2+b^2=c^2\) is any integer Pythagorean triple, the vector \(\tfrac{a}{c}x+\tfrac{b}{c}y=(\tfrac{a}{c},\tfrac{b}{c})\) is both a unit vector and a rational combination of \(x\) and \(y\). Because there are infinitely many Pythagorean triples, \(x\) and \(y\) have infinitely many unit-vector rational combinations.

What Alon, Bucić, and Sauermann show is that for “most” norms in a certain technical sense (a comeager set of norms in a certain topological space of norms), rational combinations are much less common. More precisely, they prove the following statements, which are equivalent to each other by standard results in the theory of matroid partitions:

  • Every finite set \(U\) of unit vectors, for a \(d\)-dimensional generic norm, has rational rank \(\ge \vert U\vert/d\)

  • If \(U\) is a finite set of unit vectors for a \(d\)-dimensional generic norm, then every subset of \(k\) vectors from \(U\) has at most \(kd\) rational combinations in \(U\) (including themselves, but not counting negations as different).

  • Every finite set of unit vectors for a \(d\)-dimensional generic norm can be partitioned into at most \(d\) subsets, so that the vectors within each subset are rationally independent.

If we give each of these \(d\) subsets a color, and use these colors for the edges of any finite unit distance graph, then every two parallel edges will have the same color, and every monochromatic cycle will have edges that can be paired into parallel edges in opposite directions from each other (like the edges of a square or regular hexagon). This means that the subgraph of edges of any single color will be bipartite. We can color each of these subgraphs with two colors, and combine the subgraphs to get \(2^d\) colors for the whole unit distance graph. Let’s see how such a coloring might look for the Moser spindle:

Four-coloring the Moser spindle by partitioning it into bipartite subgraphs

In this example, the blue-edge subgraph has two cycles, both rhombi. Each edge of a rhombus can be paired with another parallel edge; if you travel around the rhombus you will follow these two edges in opposite directions. The yellow-edge subgraph has no cycles at all. Combining the 2-colorings of the two subgraphs gives us a 4-coloring of the whole Moser spindle.

This method 4-colors every finite unit distance graph, for a generic norm, but not the whole plane at once. To color the whole plane, the De Bruijn–Erdős theorem can be used. This is a theorem that, whenever all finite subgraphs of an infinite graph can be colored with a certain finite number of colors, the whole graph can be colored with the same number of colors. It’s possible to construct a copy of the Moser spindle as a unit distance graph for any norm, by using the intermediate value theorem to find equilateral triangles supported by any edge and then rotating one pair of triangles with respect to another until getting another unit distance. Therefore, four colors is optimal. But the 4-coloring you get is a nasty set-theoretic thing, impossible to visualize, unlike the nice tiling-based 7-coloring of the Euclidean plane.

Noga left me with some related but unsolved questions: Can we find an explicit example of a norm with this few-rational-combinations property? It would need to be strictly convex (the boundaries of its balls could not include any line segments); can we find an explicit example of a strictly-convex norm requiring only four colors? Is it possible for such a norm to have a simple finite description? And what about smooth norms, or \(L^p\)-norms (possibly for non-integer \(p\))?

(Discuss on Mastodon)