David Madore's WebLog: Un labyrinthe hyperbolique, et une nouvelle vidéo

J'écrivais récemment un petit TODO pour plus tard. Il faut que je dise un peu ce que j'en ai fait.

Je me suis rendu compte que faire un labyrinthe hyperbolique était à la fois mathématiquement plus intéressant, et aussi plus facile, que ce que j'imaginais. En fait, j'ai eu une sorte d'épiphanie mathématique en réfléchissant à la question de savoir à la fois comment mettre des coordonnées sur un pavage comme ça (je veux dire quelque chose qui soit informatiquement manipulable et numériquement robuste, pour étiqueter les cases) et comment limiter la taille du labyrinthe. Comme Knuth l'a dit, on ne comprend vraiment bien un objet mathématique que quand on l'a enseigné, et on comprend encore mieux quand on l'a enseigné à un ordinateur.

(Ceux qui ne sont pas intéressés par les maths peuvent sauter les quelques paragraphes suivants.)

Quand on fait un jeu informatique sur le bête plan euclidien, pour ne pas aller à l'infini, parfois on met des bords, mais parfois aussi on préfère cycler dans les deux directions (i.e., quand on va trop loin, on retourne à son point de départ), ce qui revient en fait, mathématiquement, à quotienter le plan, et le réseau du pavage Λ (presque toujours un réseau carré en informatique, pour des raisons de simplicité du tracé) par un sous-réseau Γ des périodes (presque toujours aussi un réseau carré, même si pour le coup il n'y a guère de raison à ça), de sorte que Λ/Γ soit un groupe fini (un (ℤ/mℤ)⊕(ℤ/nℤ)), qui est celui où les coordonnées du jeu prennent leurs valeurs : du coup, les coordonnées sont des entiers modulo m et n (généralement deux puissances de 2, souvent égales, ce qui simplifie encore les choses), donc faciles à manipuler en informatique, et le monde est un quotient du plan par Γ, ce qu'on appelle un tore plat (ou, si on veut être sophistiqué, une surface de Riemann compacte de genre 1, c'est-à-dire une courbe elliptique, dont Γ est le groupe fondamental et dont Λ/Γ est un sous-groupe de points de torsion).

Bon, mais voilà, que faire pour le plan hyperbolique ? Contrairement au plan euclidien, ses translations ne commutent pas (c'est très clair quand on joue au jeu vers lequel je fais un lien ci-dessous) : on peut certes le paramétrer par deux coordonnées (par exemple les coordonnées polaires : la distance à une origine arbitrairement choisie et le cap/azimuth), mais ce sera des coordonnées réelles, peu pratiques à manipuler, et dès qu'on s'éloigne un peu de l'origine, elles deviennent numériquement délicates à gérer. Notamment, pour étiqueter les cases d'un pavage, ce n'est pas commode. Ce qui joue le rôle dans le cas hyperbolique du réseau du pavage dans le cas euclidien, c'est le groupe Δ des isométries du pavage (ou éventuellement le sous-groupe Δ⁰ des isométries directes) : c'est un groupe de Coxeter (en l'occurrence un groupe de triangle, qui, pour le pavage que j'ai choisi, est Δ(2,4,5), engendré par la réflexion par rapport à un mur du pavage, la rotation d'angle π/2 autour du centre d'un « carré » et la rotation d'angle 2π/5 autour d'un sommet). Ce qui permet déjà de le manipuler un peu informatiquement (il y a toutes sortes d'algorithmes pour calculer dans les groupes de Coxeter).

Mais surtout, ce qu'il y a, c'est qu'on peut aussi trouver, et de façon très agréable, des sous-groupes distingués Γ de Δ⁰ qui agissent sans point fixe, et de sorte que le quotient du plan hyperbolique par Γ soit compact (c'est une surface de Riemann compacte de genre ≥2) et notamment que Δ⁰/Γ soit fini (c'est le groupe des isométries de cette surface de Riemann). J'avoue n'avoir pas une idée aussi claire que je voudrais de comment décrire « tous » ces Γ, mais ce n'est pas difficile d'en trouver (en l'occurrence, j'ai écrit les matrices des isométries hyperboliques de mon pavage dans les nombres algébriques, j'ai trouvé un nombre premier p, en l'occurrence 89, qui scindait toutes ces matrices, et j'ai réduit modulo p). Du coup, ce qui joue le rôle analogue aux coordonnées cycliques (ℤ/mℤ)⊕(ℤ/nℤ) dans le cas d'un jeu euclidien, sur mon jeu hyperbolique, c'est le groupe Δ⁰/Γ, qui dans mon cas est PSL(2,89) (le groupe projectif spécial linéaire des matrices 2×2 sur le corps des entiers modulo 89 ; il a 352440 éléments), et le labyrinthe est en fait un sous-graphe du graphe de Cayley de ce groupe.

Voilà donc que j'ai figuré informatiquement, sans trop m'y attendre, trois objets mathématiques dignes d'intérêt : le plan hyperbolique, le graph de Cayley d'un groupe simple fini, et une surface de Riemann compacte de genre 8812 ayant ce groupe de symétries (et le plan hyperbolique comme revêtement universel, Γ étant le groupe fondamental).

(Il faudra que j'essaie voir avec un groupe Δ⁰/Γ plus petit — à commencer par trouver le plus petit possible, d'ailleurs — ce qui rendra le jeu moins intéressant mais peut-être la géométrie plus facile à visualiser. Une autre question sur laquelle je n'ai pas les idées parfaitement claires, c'est de savoir, si je voulais calculer les périodes de ma surface de Riemann, quelle serait la difficulté de l'opération.)

Bref, voici mon petit jeu de labyrinthe hyperbolique en JavaScript (qui devrait marcher sur les navigateurs vaguement récents ; mais n'essayez pas depuis un téléphone, d'une part parce qu'on joue avec les touches et d'autre part parce que les calculs sont un peu lents au démarrage et que ça consomme pas mal de mémoire).

Je l'ai présenté sous forme d'un jeu (il faut d'abord chercher à atteindre le cercle vert, puis revenir à son point de départ en ayant fait une « boucle » : c'est très facile si on se fie aux indications de distance données à droite, un peu plus difficile si on n'utilise que la couleur des cercles comme indication, et ce serait quasiment impossible s'il n'y avait rien du genre). Mais en fait l'intérêt est surtout d'explorer le plan hyperbolique et de se rendre compte comment il fonctionne. Par exemple, on peut chercher à se déplacer avec uniquement des « translations », sans jamais faire de rotation, et s'apercevoir qu'on peut revenir à son point de départ avec une différence d'orientation. On peut aussi s'amuser à essayer d'appliquer l'algorithme de la main droite (garder toujours un mur à droite et le suivre) et ceci donnera une idée de la vastesse du plan hyperbolique. Je trouve ça très instructif, et ce fut tout à fait agréable à programmer (une heureuse surprise).

🌍

Pour ce qui est des projections cartographiques, je n'ai pas calculé celle dont je parlais dans mon TODO, parce qu'elle ferait intervenir les fonctions hypergéométriques de façon pas du tout évidente, et je n'ai pas vraiment envie de me farcir le Abramowitz & Stegun pour un résultat incertain. En revanche, j'ai calculé les mêmes projections que dans ma vidéo précédente mais pour la Terre, c'est amusant à voir (et comme cette fois-ci je n'ai pas fait de commentaire audio, ça a été beaucoup plus rapide à faire) :

Allez, je termine par une vue de la Terre en projection stéréographique depuis le pôle sud sur une grande distance, parce qu'on n'a pas l'habitude de la voir comme ça, je trouve ça vraiment rigolo (et on comprend ce que ça veut dire qu'une projection conforme préserve les formes mais pas les tailles ; clickez pour zoomer) :

À ce propos, mon poussinet et moi avons cherché à trouver s'il y avait des vols aériens qui passent au-dessus de l'Antarctique : Wikipédia prétend que non, mais c'est au moins amusant, et étonnamment difficile, de chercher quelles lignes droites entre deux grandes villes sur Terre, passent au-dessus de l'Antarctique (nous avons trouvé, si je me rappelle bien : Sydney–Rio, Auckland–Le Cap, ou encore Buenos Aires–Shanghaï, mais aucune de ces liaisons n'existe en vol direct). Encore une illustration du fait qu'il est difficile de visualiser la géographie sphérique.

[Ajout : pour en savoir plus sur la géométrie hyperbolique, voir les entrées ultérieures suivantes : 1, 2, 3 (plus ou moins indépendantes), et celle-ci pour des illustrations de différentes projections ; voir aussi un autre jeu de labyrinthe hyperbolique que j'introduis là et là, et dont j'explique le fonctionnement dans des transparents disponibles ici.]