COMBIEN DE COULEURS POUR PEINDRE L'ESPACE ? AVEC UNE RÈGLE TYPIQUE, PAS PLUS DE 2d
Prenez tous les points d’un plan et donnez une couleur à chacun. Une seule règle : deux points situés exactement à une unité l’un de l’autre ne doivent jamais avoir la même couleur. Quel est le plus petit nombre de couleurs qui marche ?
C’est le problème de Hadwiger-Nelson, qui remonte à 1950 et, selon les auteurs, l’un des plus célèbres problèmes ouverts de géométrie discrète. Pendant longtemps, on savait seulement que la réponse est comprise entre 4 et 7. Une percée récente a relevé la borne inférieure à 5. La réponse exacte reste inconnue.
Changer de règle
On n’est pas obligé de mesurer les distances avec une règle ordinaire. Les mathématiciens définissent bien d’autres normes — des façons de mesurer les longueurs —, chacune décrite par sa « boule unité », l’ensemble des points à distance au plus 1 du centre. Pour la distance habituelle, c’est une boule ronde ; pour d’autres normes, ce peut être n’importe quelle forme convexe symétrique par rapport à son centre.
Pour toute norme du plan, la réponse à l’énigme est entre 4 et 7. En dimension d, elle est au plus exponentielle en d pour toute norme, et pour beaucoup de normes naturelles — dont la norme euclidienne habituelle — elle est aussi au moins exponentielle : le nombre de couleurs explose quand la dimension augmente.
Cette explosion est-elle la règle ? Noga Alon (université de Princeton et université de Tel-Aviv), Matija Bucić (université de Vienne) et James Davies (université de Leipzig) se sont intéressés à une norme typique. Il n’existe pas de façon naturelle de tirer une norme « au hasard » ; ils utilisent donc une notion topologique : une propriété est vraie pour une norme typique si les exceptions forment un ensemble négligeable (« maigre »). Des travaux antérieurs d’Alon, Bucić et Lisa Sauermann avaient montré qu’une norme typique demande au plus 2ᵈ couleurs, et demandaient à quel point c’était proche de la vérité.
Linéaire, pas exponentiel
La réponse : très loin. Le nouvel article démontre que
- pour une norme typique en dimension d, 2d couleurs suffisent toujours ;
- c’est optimal : un ensemble ouvert de normes exige au moins 2d couleurs. Certaines normes en demandent donc exactement 2d.
En dimension dix, une norme typique demande au plus vingt couleurs, quand la distance habituelle en demande un nombre qui croît exponentiellement. Selon les auteurs, c’est aussi la première fois que le nombre de couleurs est déterminé exactement pour une norme « strictement convexe » en dimension d quelconque.
La borne inférieure repose sur un piège astucieux. Trouver 2d points tous situés exactement à une unité les uns des autres, sauf deux, a et b, distants d’une demi-unité. Ajouter l’image miroir de toute la configuration par rapport à a. Avec moins de 2d couleurs, b et son image seraient tous deux forcés de prendre la couleur de a — or ils sont exactement à une unité l’un de l’autre. Contradiction. Un lemme de stabilité montre que cette configuration résiste à toute petite modification de la norme.
Un coureur solitaire en grande dimension
La borne supérieure colorie chaque point selon l’endroit où tombe une projection bien choisie de ce point, par tranches de largeur 1/(2d). Pour que cela marche, il faut un ingrédient clé que les auteurs décrivent comme une version matricielle, en grande dimension, de la célèbre conjecture du coureur solitaire :
sup sur x de minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)
où ‖t‖ est la distance de t à l’entier le plus proche, pour n vecteurs aᵢ en dimension k dont k quelconques sont indépendants. Cet énoncé résout aussi une conjecture de 1978 d’I. J. Schoenberg sur l’« obstruction de la vue » — quelle épaisseur doivent avoir des tranches périodiques pour bloquer toute vue vers l’infini —, que les auteurs comptent parmi les problèmes ouverts les plus classiques du domaine, ainsi qu’une conjecture voisine de Henze et Malikiosis.
La machine dans les remerciements
Les auteurs sont explicites : « ChatGPT 6 Pro nous a fourni la preuve du dernier ingrédient dont nous avions besoin pour démontrer le Théorème 1, à savoir celle du Lemme 7, après une longue discussion », au cours de laquelle ils lui avaient soumis leurs propres observations — dont l’idée de récurrence et la stratégie générale. « L’argument de la borne inférieure a aussi été trouvé avec l’aide de ChatGPT 6 Pro. »
Des questions restent ouvertes. La valeur exacte 2d est prouvée sur un ensemble ouvert de normes, pas pour toutes les normes typiques. Et pour la distance euclidienne ordinaire, les auteurs s’attendent à strictement plus de 2d couleurs en toute dimension — c’est déjà établi en dimensions 2, 4, 7, 8 et à partir de 9, mais toujours ouvert en dimensions 3, 5 et 6.