David Madore's WebLog: Sections du diagramme de Voronoï du réseau E₈

Je ne savais pas bien à quoi m'attendre quand j'ai calculé cette image, mais probablement pas à ça :

(Cliquez pour une vue plus large.)

De quoi s'agit-il ? C'est une section plane aléatoire du diagramme de Voronoï du réseau E₈ : il faut que j'explique ces termes (mais is ça ne vous intéresse pas, il y a d'autres images, et des liens vers des vidéos, plus bas).

Le réseau E₈ est un arrangement régulier de points en dimension 8, qui a toutes sortes de propriétés remarquables. En fait, il n'est pas difficile de le définir concrètement : il s'agit des octuplets (x₀,x₁,…,x₇) de nombres réels tels que :

• les coordonnées x₀,x₁,…,x₇ sont soit toutes entières soit toutes entières-et-demi (par entier-et-demi je veux évidemment dire un nombre qui vaut un entier plus ½, par exemple 5/2),
• la somme x₀+x₁+⋯+x₇ de toutes les coordonnées (qui est forcément un entier d'après le point précédent) est paire.

À titre d'exemple, (0, 0, 0, −1, 2, −1, 1, −1) et (−1.5, 2.5, −0.5, 1.5, −1.5, −0.5, −2.5, 0.5) sont dans le réseau E₈ ; en revanche, (0, 0, 0, −1, 2, −1, 1.5, −1.5) n'y sont pas (les coordonnées ne sont ni toutes entières ni toutes entières-et-demi), et (−1.5, 2.5, −0.5, 1.5, −1.5, −0.5, −2.5, 0.5) non plus (la somme n'est pas paire).

La somme ou différence de deux points du réseau E₈ est encore dedans : c'est là la propriété essentielle d'être un réseau (et ce qu'un non-mathématicien qualifierait de points régulièrement espacés). Les points du réseau E₈ les plus proches de l'origine (0,0,0,0,0,0,0,0) sont d'une part ceux de la forme (±1,±1,0,0,0,0,0,0) (où exactement deux coordonnées, quelconques, valent soit 1 soit −1 : ceci fait 28×4=112 possibilités — 28 choix de deux coordonnées et 4 choix de leurs signes), et d'autre part ceux de la forme (±½,±½,±½,±½,±½,±½,±½,±½) (où chaque coordonnée vaut ½ ou −½, et où il y a un nombre pair de valeurs −½ : ceci fait 2⁸/2=128 possibilités) : au total, 112+128=240 points tous à distance √2 de l'origine ; ces 240 points sont ce qu'on appelle les racines du système E₈ et ils engendrent le réseau, mais ici c'est le réseau plus que ses racines qui m'intéresse. Entre autres propriétés remarquables, c'est le réseau E₈ qui réalise l'empilement optimal de boules identiques en dimension 8 (mettre une boule de rayon (√2)/2 autour de chaque point du réseau : elles se touchent sans se chevaucher et remplissent 25.367% de l'espace, ce qui ne paraît peut-être pas impressionnant, mais en dimension 8 on ne peut pas faire mieux).

Donné un ensemble (discret) de points dans l'espace euclidien, le diagramme de Voronoï associé est la division de l'espace en cellules de Voronoï, la cellule de Voronoï d'un point étant la région des points de l'espace qui sont plus proches de ce point-là que de tout autre point de l'ensemble. En général, un diagramme de Voronoï ressemble à ce que Google images vous montrera (il est formé de cellules qui sont des polytopes convexes dont les facettes sont hyperplans médiateurs entre le point définissant la cellule et un autre point). Lorsque l'ensemble des points est un réseau, toutes les cellules ont la même forme : la cellule de Voronoï de l'origine est l'ensemble des points plus proches de l'origine que de tout autre point du réseau, elle est d'ailleurs symétrique, et toutes les autres cellules sont identiques autour d'un autre point, elles sont translatées les unes des autres. S'agissant du réseau E₈ précisément, la cellule de Voronoï de l'origine est un polytope convexe ayant 240 facettes[#], une par racine du système de racines, chaque facette étant un morceau de l'hyperplan médiateur entre l'origine et la racine en question. (Il n'est pas vrai dans un réseau en général que les facettes de la cellule de Voronoï de l'origine soient ainsi définies uniquement par les points les plus proches de l'origine. Mais c'est vrai pour ce qu'on appelle un réseau de racines, et notamment E₈.)

[#] Il a aussi 19440 sommets : 2160 sont les points à distance 1 de l'origine ainsi que de quinze autres points du réseau, on les appelle les trous profonds du réseau E₈ (un exemple d'un tel point est (1,0,0,0,0,0,0,0)), et 17280 sont les points à distance (2√2)/3≈0.943 de l'origine ainsi que de sept autres et ce sont les trous superficiels (un exemple d'un tel point est (−5/6, 1/6, 1/6, 1/6, 1/6, 1/6, 1/6, 1/6)).

Bref, le diagramme de Voronoï du réseau E₈ est un pavage de l'espace de dimension 8 par des copies (translatées) de ce polytope à 240 facettes, chacune étant centrée sur un point du réseau. Il y a un algorithme assez simple[#2] pour décider, quand on se donne un point de l'espace, à quelle cellule de Voronoï il appartient, c'est-à-dire, trouver le point du réseau le plus proche (on parle aussi d'algorithme de décodage pour ce réseau).

[#2] En voici une description. Commençons par expliquer comment trouver le point du réseau D₈ le plus proche d'un point donné, où le réseau D₈ est le réseau formé des points de coordonnées toutes entières de somme paire (c'est-à-dire les points du réseau E₈ dont toutes les coordonnées sont entièrs). Donné (z₀,z₁,…,z₇) un point à approcher, on appelle x₀ l'entier le plus proche de z₀ et de même pour les autres : ceci fournit le point (x₀,x₁,…,x₇) à coordonnées entières le plus proche de (z₀,z₁,…,z₇). Si la somme x₀+x₁+⋯+x₇ des coordonnées est paire, c'est le point de D₈ recherché. Sinon, l'astuce suivante permet de le trouver : parmi les coordonnées x, prendre celle qui est le plus loin du z correspondant, et la remplacer par l'arrondi de ce z dans l'autre sens. À titre d'exemple, si on part du point (0.3, −0.1, 0.1, −1.0, 2.0, −0.4, 0.9, −0.7), l'arrondi des coordonnées à l'entier le plus proche donne (0, 0, 0, −1, 2, 0, 1, −1), la somme est impaire, donc on corrige le plus mauvais arrondi, à savoir −0.4 transformé en 0, en prenant l'entier de l'autre côté, donc −1, ce qui donne le point (0, 0, 0, −1, 2, −1, 1, −1) qui est le point du réseau D₈ le plus proche du point initial. S'agissant du réseau E₈, maintenant, on peut faire ce calcul une fois pour trouver le point de D₈ le plus proche, puis soustraire ½ toutes les coordonnées, refaire le calcul pour trouver le point de D₈ le plus proche du point ainsi modifié et rajouter ½ à toutes les coordonnées : on obtient ainsi deux points de E₈ (l'un dans D₈ et l'autre dans D₈+(½,½,½,½,½,½,½,½)) ; il n'y a plus qu'à comparer la distance de ces deux points au point d'origine et choisir le plus proche (soit en comparant les distances soit en calculant l'équation de l'hyperplan médiateur, ce qui revient essentiellement au même). Il existe des algorithmes légèrement plus efficaces que ce que je viens de décrire, mais en contrepartie ils sont plus fastidieux à implémenter et je pense que ça n'en vaut pas la peine.

Maintenant, ce que j'ai fait pour calculer l'image ci-dessus est de prendre un plan aléatoire dans l'espace euclidien de dimension 8 (plus exactement, la direction du plan est définie par deux vecteurs unitaires orthogonaux, tirés uniformément pour cette propriété, et l'origine est tirée uniformément modulo le réseau), et tracer l'intersection de ce plan avec les cellules de Voronoï du réseau E₈. Bien que le diagramme de Voronoï de E₈ soit complètement régulier, le fait de l'intersecter avec un plan aléatoire fournit quelque chose d'assez irrégulier comme on le voit, mais où on peut discerner, si on regarde bien (et surtout sur la vue plus complète), une forme de quasipériodicité. Je ne suis pas sûr d'avoir une description ni une explication complète de tout ce qu'il y a à remarquer sur l'image.

Pour information, l'échelle de l'image est de 10 pixels pour 1 unité (l'« unité » en question étant celle des coordonnées que j'ai exposées ci-dessus, c'est-à-dire que la distance entre deux points les plus proches du réseau vaut √2, ou encore que l'unité est le rayon de la sphère circonscrite à une cellule de Voronoï, ou encore que la cellule a un volume de 1 unité⁸), ce qui veut dire que l'image fait 136.6 unités en largeur et 76.8 en hauteur pour les images larges (la moitié pour les images plus étroites reproduites ci-dessus).

Pour ce qui est du coloriage des cellules de Voronoï, j'ai tiré aléatoirement trois directions orthogonales au plan et orthogonales entre elles, et les composantes rouge, verte et bleue donnent la distance au point du réseau (le centre de la cellule de Voronoï) selon ces trois directions, le gris étant le zéro.

J'ai aussi calculé des images selon des plans ayant des directions particulières : on appelle plan de Coxeter du réseau E₈ un plan tel que la projection (orthogonale) du système de racines sur ce plan présente une symétrie d'ordre maximal, en l'occurrence 30. (Le dessin le plus courant du système de racines de E₈ est généralement choisi projeté selon un tel plan : par exemple, cette image Wikimédia Commons est une projection sur un plan de Coxeter, aussi appelé dans ce contexte plan de Petrie.) Le résultat est le suivant :

(Cliquez pour une vue plus large.)

De nouveau, l'origine de projection est aléatoire modulo le réseau, et les directions choisies pour définir les couleurs des cellules sont aléatoires sujettes à la contrainte d'être perpendiculaires au plan de projection. Ce qui est intéressant est qu'on voit apparaître des symétries d'ordre 30 approximatives autour de différents points : ce sont ceux qui sont les plus proches d'un point du réseau. Si ça ne vous frappe pas, regardez attentivement la vue plus large, éventuellement depuis une certaine distance : on voit apparaître toutes sortes de figures en cercles concentriques, un peu comme des ondes de gravité circulaires à la surface de l'eau quand on y fait tomber quelque chose (des encyclies si on veut faire chic, des ronds dans l'eau si on veut faire moins chic) ; je suppose que le cortex visuel détecte quelque chose de cette symétrie localte approximative d'ordre 30, mais je ne sais pas exactement ce qu'il détecte.

J'ai aussi fait le calcul pour un plan la projection sur lequel présente une symétrie d'ordre 24 du système de racines :

L'effet est à peu près le même, peut-être encore plus fort.

J'ai aussi calculé et mis sur YouTube des vidéos de sections tridimensionnelles (ou (2+1)-dimensionnelles) du même diagramme de Voronoï : tridimensionnelles, c'est-à-dire que le temps est la troisième dimension, ou plus exactement, qu'il s'agit de sections planes se déplaçant dans une direction aléatoire orthogonale au plan (et orthogonale aux trois directions servant à définir les couleurs comme expliqué ci-dessus) : celle-ci montre une section aléatoire et celle-ci une section dont le plan 2D est un plan de Coxeter. Les deux sont assez envoutantes à regarder, mais la seconde l'est particulièrement à cause de la manière dont apparaissent puis disparaissent des symétries approximatives d'ordre 30. Les vidéos sont cadrées plus serré que les images fixes : l'image est large de 16 unités et haute de 9, et dans le temps le plan parcourt 40 unités en 48 secondes.

J'hésite à refaire des calculs analogues pour le réseau de Leech, qui est un réseau peut-être encore plus remarquable en dimension 24. Mais l'algorithme pour retrouver « décoder » le réseau de Leech (c'est-à-dire en trouver le point le plus proche d'un point donné, autrement dit, pour calculer les cellules de Voronoï) est un peu pénible à écrire, et j'ai peur que le résultat soit décevant parce que autant 2 dimensions (voire 2+3 en comptant les couleurs, voire 2+1+3 pour les vidéos) sur 8, ce n'est pas complètement négligeable, autant 2 dimensions, ou même 2+3 ou 2+1+3, sur 24, ça ne fait vraiment pas beaucoup, et j'ai peur qu'il ne subsiste absolument rien de la très extraordinaire symétrie du réseau de Leech.

A contrario, je pourrais peut-être baisser la dimension et regarder ce qui se passe dans des réseaux comme A₄ à A₆, D₄ à D₆ et E₆. S'agissant de A₄, par exemple, si on le regarde selon un plan de Coxeter, cela fera apparaître une symétrie d'ordre 5 qui ne manque sans doute pas d'intérêt (je crois qu'il y a des liens avec les quasi-cristaux et les pavages de Penrose à symétrie pentagonale, mais je ne connais pas les détails). D'un autre côté, j'ai une certaine flemme, parce que calculer les plans de Coxeter est assez fastidieux, et je ne sais plus bien comment il faut faire (dans le cas de E₈ j'avais les résultats sous la main, mais je me souviens m'être battu contre Sage et Gap pour les obtenir). Quant au réseau A_n, il est pénible parce que son système de coordonnées le plus naturel utilise n+1 coordonnées entières à somme nulle, certes il rend le plan de Coxeter évident, mais il est plus délicat à manier (sinon, pour A₄, exactement la même définition que j'ai donnée de E₈ doit marcher avec 4 coordonnées, mais alors de nouveau le plan de Coxeter n'est pas évident).

Ajout (2017-04-10T22:50+02:00) : Finalement, j'ai fait les calculs pour A₈ et D₈ (ainsi que ℤ⁸, qui n'est pas très intéressant). L'algorithme pour trouver le point de D₈ le plus proche d'un point de ℝ⁸ est expliqué au passage quand j'explique celui de E₈ ci-dessus ; s'agissant de A₈ (qui est l'ensemble des 9-uples d'entiers de somme nulle), l'algorithme pour décoder (z₀,z₁,…,z₈) consiste à considérer (x₀,x₁,…,x₈) les entiers les plus proches, puis, si la somme x₀+x₁+⋯+x₈ est strictement positive, soustraire 1 aux x qui tels que l'erreur x−z correspondante est la plus grande pour l'amener à 0, tandis que si elle est strictement négative, ajouter 1 aux x qui tels que l'erreur x−z correspondante est la plus négative. Le plan de Coxeter de D₈ présente une symétrie d'ordre 14 (correspondant à une rotation cyclique des 7 premières coordonnées en même temps qu'on change le signe des deux dernières), tandis que pour A₈ elle est d'ordre 9 (correspondant à une rotation cyclique des 9 coordonnées). Voici les images : section plane aléatoire de D₈, section plane de Coxeter de D₈, section plane aléatoire de A₈, section plane de Coxeter de A₈, section plane aléatoire de ℤ⁸. J'ai aussi calculé une section de E₈ selon le plan de Coxeter de D₈, pour mieux comparer les deux. (J'ai aussi rassemblé ces images ici sur imgur.) Je vais peut-être produire aussi quelques vidéos.

Ajout 2 (2017-04-14T23:23+02:00) : Comme on m'y a incité en commentaire, j'ai aussi calculé des images où ce qui est représenté est la distance (au carré) au point du réseau le plus proche (avec 0=noir et 1=blanc). C'est effectivement beaucoup plus joli à voir, et peut-être encore plus parlant visuellement (même s'il y a, techniquement, plutôt moins d'information) ; et je dois dire qu'artistiquement je trouve ça absolument époustouflant (quoique légèrement déconseillé aux trypophobes), ça fait penser à quelque chose en train de bouillonner ou aux cellules de convexion dans le soleil. Bref, merci à Fab pour la suggestion. Voici donc une vidéo noir et blanc selon un plan aléatoire et selon un plan de Coxeter, et en bonus selon un plan présentant une symétrie d'ordre 24.

Code source : Il est ici pour la version originale, et ici pour la version mentionnée dans le deuxième ajout ci-dessus. Quelques explications (et les instructions sur comment compiler) sont en commentaire au début du code lui-même.