Un collègue m'a poussé à réfléchir à des questions tournant autour du problème de Hadwiger-Nelson (ou problème du coloriage du plan, ou problème du nombre chromatique des unit distance graphs). Fatale erreur ! Ma maman m'avait pourtant toujours dit quand j'étais petit : Ne réfléchis jamais au problème de Hadwiger-Nelson. Ce problème est comme le Zahir de Borges : on commence à y penser, on se laisse tenter par son apparence si facile et si séduisante, sa faculté à relier des domaines mathématiques aussi divers que la théorie des graphes, la géométrie algébrique et la logique, et bientôt on ne peut plus songer qu'à lui, on le voit dans des rêves et on dessine partout des petits graphes avec des points à distance 1 les uns des autres.
Le problème de Hadwiger-Nelson (que j'avais d'ailleurs déjà évoqué, mais je n'en connaissais pas le nom à l'époque) est sans doute le problème mathématique ouvert le plus incroyablement simple à formuler (même si cette simplicité est peut-être un peu trompeuse). Et qui insulte l'honneur de l'esprit humain de ne pas être capable de répondre à une question aussi bête :
(On fixe une fois pour toutes une unité de distance.) Quel est le nombre minimal χ de couleurs qu'il faut pour colorier le plan de manière que deux points distants d'une unité ne soient jamais de la même couleur ?
Tout ce qu'on sait montrer est que 4≤χ≤7. Et c'est
d'autant plus frustrant que la démonstration de ces deux faits est à
la portée d'un collégien, et que toutes les maths sophistiquées qu'on
a pu essayer de balancer contre ce problème n'ont pas amélioré d'un
chouïa l'encadrement en question. La minoration par 4 est démontrée
par exemple par la figure suivante, appelée Moser's
spindle
(le fuseau de Moser
?) :
Chaque arête a distance 1 dans le plan, ce qui détermine rigidement la figure. Il est facile de se convaincre qu'il n'est pas possible de colorier les sommets de ce graphe avec seulement 3 couleurs de manière que deux sommets reliés par une arête ne soient pas de la même couleur (en effet, si on n'a que trois couleurs, quelle que soit la couleur c du sommet en bas à gauche, les deux autres sommets de chacun des triangles équilatéraux dont il est un sommet doivent avoir les deux autres couleurs, du coup le sommet tout en haut et celui tout à droite ont la même couleur c, or ils sont reliés par une arête, une contradiction). La majoration par 7 est démontrée par la figure suivante :
L'unité de longueur (figurée par le trait noir en haut à gauche, et qui est à la même échelle que sur la figure précédente) est juste un tout petit peu trop courte pour relier les sommets les plus proches de deux hexagones de la même couleur, mais juste un tout petit peu trop longue pour tenir à l'intérieur d'un même hexagone : donc quelle que soit la manière dont on place cette règle sur le plan, les deux extrémités auront une couleur différente.
On ne sait rien dire de mieux, donc. Oh, on sait dire des choses sur des problèmes adjacents : par exemple, sur le nombre chromatique fractionnaire du plan pour la relation être-distant-d'une-unité (on sait qu'il est compris entre 3.55 et 4.36), ou sur les coloriages dans lesquels on impose de plus aux parties coloriées d'être mesurables (on sait qu'il faut alors au moins 5 couleurs), ou sur le coloriage des points à coordonnées rationnelles (seulement 2 couleurs suffisent alors) ; en fait, on sait dire assez de choses pour qu'Alexandr Soifer écrive un livre de 600 pages consacré à peu près entièrement à ce problème. Mais l'inégalité 4≤χ≤7 continue de nous narguer et de rappeler les mathématiciens à l'humilité. Personnellement je trouve ça beaucoup plus rageant que le problème de Collatz/Syracuse/3n+1 ou que le théorème de Fermat n'a jamais pu l'être.
Et ce que ce problème a de rageant, aussi, c'est qu'on ne sait pas trop quoi conjecturer. Un théorème d'Erdős et de Bruijn (qui est une conséquence immédiate du théorème de compacité du calcul propositionnel, ou — un petit peu moins immédiate — de la compacité des produits de compacts) assure que pour minorer le nombre de couleurs χ nécessaire pour colorier le plan, il « suffit » [OK, en fait ça veut dire « il faut », comme on me le signale en commentaire] d'exhiber un graphe fini réalisable avec distance 1 et qui n'est coloriable qu'avec ce nombre de couleurs. On pourrait donc se dire que puisque ces « unit distance graphs » ont été tant étudiés, s'il y en avait un qui ait nombre chromatique 5 ou plus, ça aurait fini par se voir : mais il est aussi parfaitement plausible qu'il ait un nombre de sommets faramineux, alors que la borne supérieure de 7 par le pavage hexagonal, elle, a l'air tellement naturelle, tellement appropriée a la situation, qu'on a envie de croire qu'elle est optimale. De fait, jusqu'à récemment, j'étais convaincu en mon for intérieur que la bonne valeur de χ est 7. Mais il est parfaitement possible que ce ne soit la bonne valeur que pour des parties coloriées possédant des propriétés de régularité sympathique (ceci dit, même avec l'hypothèse de mesurabilité on ne sait pas fermer le gap), et qu'un coloriage avec 4 couleurs existe mais nécessite l'axiome du choix (qui est caché derrière le théorème d'Erdős-de-Bruijn). Croire que χ=4 se défend aussi : elle consiste à croire que les configurations de points à distance 1 dans le plan ne peuvent pas trop nous jouer de tour ou de coïncidences inattendues, qu'ils ne sont pas trop éloignés des graphes de Laman (lesquels sont toujours 4-coloriables pour des raisons idiotes de degré). Entre les deux, il est aussi permis de croire que la bonne valeur est 5 ou 6, même si ça semble moins plausible qu'aucun des deux arguments élégants pour 4 ou 7 ne donne la bonne valeur, mais bon, c'est comme en politique, il faut bien qu'il y ait aussi des centristes qui croient qu'in medio stat virtus.
Mise à jour : Quelques années plus tard, j'ai écrit un article sur le problème de Hadwiger-Nelson où on se concentre sur les points à valeurs dans certains corps de nombres comme ℚ(√2) ou ℚ(√3).
Nouvelles mises à jour : Voir aussi cette entrée pour mes mésaventures liées à l'article mentionné ci-dessus, et celle-ci pour un progrès démontrant χ≥5 (et mes méditations à ce sujet).
✶
Bon, à part ça, je continue à vouloir écrire un textes sur les octonions pour mettre dans ce blog, mais je retarde ça tant que je n'ai pas trouvé le temps de lire l'article attentivement fondamental Lie Groups in the Foundations of Geometry de Hans Freudenthal (qui expose généralement la raison pour laquelle les octonions sont naturels). Comme cet article est dense, ça risque de prendre du temps.
Et je maintiens aussi sur le feu mes éphérémides astronomiques (dans lesquels je mets des quaternions, comme beaucoup de gens l'ont deviné, mais pas d'octonions), mais comme dès que je m'y mets pour trop longtemps je m'énerve contre l'astronomie, il ne faut pas non plus y compter pour sitôt.