Noch nicht übersetzt: englische Originalfassung.
HOW MANY COLOURS TO PAINT SPACE? FOR A TYPICAL RULER, NO MORE THAN 2d
Take every point of a flat plane and give each one a colour. One rule: two points exactly one unit apart must never have the same colour. What is the smallest number of colours that works?
This is the Hadwiger–Nelson problem, dating back to 1950 and, in the words of the authors, one of the most famous open problems in discrete geometry. For a long time the answer was known to lie between 4 and 7. A recent breakthrough raised the lower bound to 5. The exact answer is still unknown.
Changing the ruler
Distance does not have to be measured with an ordinary ruler. Mathematicians define many other norms — ways of measuring length — each described by its “unit ball”, the set of points at distance at most 1 from the centre. For the usual distance it is a round ball; for other norms it can be any convex shape symmetric about its centre.
For every norm on the plane, the answer to the colouring puzzle is between 4 and 7. In d dimensions, it is at most exponential in d for any norm, and for many natural norms — the usual Euclidean one included — it is also at least exponential: the number of colours explodes as the dimension grows.
Is that explosion the rule? Noga Alon (Princeton University and Tel Aviv University), Matija Bucić (University of Vienna) and James Davies (Leipzig University) looked at a typical norm. There is no natural way to pick a norm “at random”, so they use a topological notion: a property holds for a typical norm if the exceptions form a negligible (“meagre”) set. Earlier work by Alon, Bucić and Lisa Sauermann had shown that a typical norm needs at most 2ᵈ colours, and asked how close that was to the truth.
Linear, not exponential
The answer: far from it. The new paper proves that
- for a typical norm on d-dimensional space, 2d colours always suffice;
- this is best possible: an open set of norms requires at least 2d colours. So some norms need exactly 2d.
In ten dimensions, a typical norm needs at most twenty colours, while the usual distance needs a number that grows exponentially. According to the authors, it is also the first time the colouring number has been pinned down exactly for a “strictly convex” norm in any dimension d.
The lower bound uses a neat trap. Find 2d points that are all exactly one unit apart from each other, except two, a and b, which are half a unit apart. Add the mirror image of the whole configuration through a. With fewer than 2d colours, both b and its mirror image would be forced to take the colour of a — but they are exactly one unit apart. Contradiction. A stability lemma shows that this configuration survives any small change of the norm.
A lonely runner in high dimensions
The upper bound colours each point according to where a well-chosen projection of it falls, in slices of width 1/(2d). Making it work requires a key ingredient that the authors describe as a high-dimensional, matrix version of the famous lonely runner conjecture:
sup over x of minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)
where ‖t‖ is the distance from t to the nearest integer, for any n vectors aᵢ in k dimensions of which any k are independent. This statement also settles a 1978 conjecture of I. J. Schoenberg on “view obstruction” — a question about how thick periodic slabs must be to block every view to infinity — which the authors call one of the most classical open problems in the area, as well as a related conjecture by Henze and Malikiosis.
The machine in the acknowledgements
The authors are explicit: “ChatGPT 6 Pro has provided us with the proof of the final ingredient we needed in the proof of Theorem 1, namely that of Lemma 7, following a prolonged discussion”, in which they had shared their own observations — including the induction idea and the general strategy. “The lower-bound argument was also found with the assistance of ChatGPT 6 Pro.”
Questions remain. The exact value 2d is proved on an open set of norms, not for all typical ones. And for the ordinary Euclidean distance, the authors expect strictly more than 2d colours in every dimension — something already known in dimensions 2, 4, 7, 8 and 9 and up, but still open in dimensions 3, 5 and 6.