David Madore's WebLog: 2013-11

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.]

Je donne à Télécom ParisBientôtSaclayTech, dans le cadre d'un master de sécurité, un cours de remise à niveau en algèbre pour la cryptographie : il s'agit essentiellement de présenter les ℤ/mℤ (théorème chinois, fonction indicatrice d'Euler, éléments primitifs), la notion de groupe cyclique, et, à la fin, la notion de corps fini (et la manière de les voir comme des quotients des polynômes), voire la définition du symbole de Legendre (je fais ça en TD). Pour ceux que ça intéresse, les notes de mon cours ainsi que les feuilles d'exercices et les sujets de contrôle sont disponibles ici (je crois que c'est en accès public, en tout cas j'ai demandé que ce le soit ; sinon, il y a une copie de mes notes de cours ici).

Il s'agit de notions assez agréables à enseigner, et même si le niveau des étudiants est extrêmement hétérogène, c'est plutôt plaisant. Les objectifs sont modestes (d'ailleurs, si c'était moi qui faisais les programmes, quelques unes de ces choses seraient enseignées au lycée, au moins dans les terminales scientifiques) et l'ambiance est agréable.

Il y a pourtant une erreur récurrente que je vois chaque année dans une proportion alarmante des copies et que je m'arrache les cheveux à me demander comment l'éviter.

Je définis la notion d'ordre d'un élément a dans un groupe G comme le plus petit n tel que aⁿ=1 : j'insiste en disant ça sur le fait qu'avoir aⁿ=1 ne signifie pas que l'ordre de a soit n mais seulement qu'il divise n (ou que n est multiple de l'ordre de a). Quand j'énonce le « petit » théorème de Fermat, selon lequel si p est premier et a non multiple de p alors a^p−1≡1 (mod p) (ou bien le théorème d'Euler selon lequel si a est premier avec m alors a^φ(m)≡1 (mod m)), j'insiste sur le fait que cette borne n'est pas forcément optimale, il se peut très bien qu'il existe un exposant k plus petit que celui prédit par le théorème pour lequel on ait a^k≡1, autrement dit, que l'ordre multiplicatif de a modulo p n'est pas forcément p−1 (ou φ(m) modulo un m quelconque), et d'ailleurs qu'on va appeler primitifs les éléments pour lesquels il l'est (et que ces éléments existent pour p premier et pour certains m composés, et qu'ils sont un objet d'étude important). Dans les exercices je souligne de nombreuses fois que quand on cherche à calculer l'ordre multiplicatif d'un élément a (non nul) modulo p, le petit théorème de Fermat donne l'assurance qu'à la puissance p−1 on retombera sur 1 mais qu'il est possible qu'on retombe sur 1 plus tôt, exemples à l'appui ; je leur fais notamment calculer les ordres additifs et multiplicatifs de tous les éléments modulo m pour différentes valeurs de m. Je donne même des exemples de situations où tous les éléments sont d'ordre plus petit que ce que prédit le théorème d'Euler, c'est-à-dire qu'il n'existe pas d'éléments primitifs. Je souligne qu'il ne faut pas faire cette erreur que de penser qu'avoir un multiple de l'ordre signifie qu'on ait l'ordre exact (mais que comme l'ordre exact doit diviser p−1 ou φ(m), on peut souvent le trouver). Bref, je tourne ça de toutes les façons que je peux imaginer, dans l'espoir que ça finisse par rentrer.

Et ça ne rentre pas. La première question du contrôle que je leur ai donné avant-hier était : quel est l'ordre multiplicatif de 2 modulo 11, et il y a vraiment trop d'étudiants qui me répondent : on a 2¹⁰≡1 (mod 11) d'après le théorème de Lagrange / Euler / Fermat [ce qui est correct], donc 2 est d'ordre multiplicatif 10 [c'est le donc qui est faux[#] : on peut seulement en conclure qu'il divise 10] ; voire, qui enfoncent le clou en disant : on peut donc dire que 2 est primitif. (M'enfin ! Si tous les éléments étaient primitifs, on n'introduirait pas cette notion !)

[#] C'est uniquement le donc qui est faux : la conclusion est juste, 2 est bien d'ordre multiplicatif 10 modulo 11 (mais on ne peut pas le déduire du théorème de Lagrange / Euler / Fermat — il faut au minimum calculer 2² et 2⁵ modulo 11).

Je sais que les enseignants aiment se plaindre que leurs élèves sont nuls, mais là, je ne peux pas dire ça : si quelqu'un écrit des énormités dans une copie, on peut se dire qu'il est idiot et en rire, mais vu que cette erreur revient chaque année chez au moins un tiers de mes étudiants, la faute est forcément la mienne, pas la leur. (J'en ai déjà parlé, mais cette année je croyais avoir mis le paquet, avoir passé un temps démesuré à répétér, rabâcher, mettre en garde, avertir, sermonner : le fait d'avoir aⁿ=1 ne signifie pas que l'ordre de a soit n mais seulement qu'il divise n.)

Alors, comment est-ce que je dois faire ? Est-ce que quelqu'un a une idée ? Il paraît que la pédagogie est une science : qu'on m'explique, sur cet exemple extrêmement précis, ce que je dois faire (je ne dis pas que je suis satisfait à 100% de ce qu'ils retiennent du reste du cours, mais ce point précis est vraiment celui qui me pose le plus de problème, c'est l'erreur nº1 que je voudrais leur faire éviter).

(Si c'était un point anecdotique du cours, je pourrais l'ignorer ; mais c'est vraiment ce qui sous-tend la notion de logarithme discret que de bien comprendre le concept d'ordre d'un élément dans un groupe et d'élément primitif.)

Deux idées que m'ont données les deux dernières entrées, à retenir pour plus tard, peut-être, un jour, si jamais j'ai du temps :

• Combiner mon intérêt pour les labyrinthes avec celui des projections du plan hyperbolique, et faire un jeu de labyrinthe (en JavaScript) qui se joue dans le plan hyperbolique. Probablement sur ce pavage-ci (le pavage régulier du plan hyperbolique par des quadrangles — peut-on les appeler carrés ? — d'angle 72° à chaque sommet), qui a l'avantage qu'on pourrait jouer de façon évidente avec les flèches pour avancer ou reculer d'un quadrangle, ou tourner de 90° vers la droite ou la gauche. Il y a des chances que ce soit encore plus labyrinthique que mon labyrinthe 3D, et ça donnera peut-être une bonne intuition de la « vastesse » du plan hyperbolique. Si quelqu'un est motivé pour coder ça et a besoin que je lui explique comment on pourrait faire, qu'il me contacte !
• Calculer le rendu de ma projection élue de la Terre, qui sera définie de la façon suivante : c'est une projection sur un patron d'icosaèdre (comme la Dymaxion), sauf que, pour chaque face de l'icosaèdre, la projection du triangle sphérique vers le triangle euclidien, plutôt qu'être la projection gnomonique ou la projection de la Dymaxion, sera l'unique application conforme (comme je l'ai expliqué) qui respecte les symétries du triangle. (J'ai pensé à un moment que ce serait une projection stéréographique par bouts, mais c'est idiot, ça ne peut évidemment pas être ça.) Bref, un peu comme la projection quinconciale de Peirce, mais en icosaèdre. Pareil, si quelqu'un se sent motivé pour appliquer la formule de Schwarz-Christoffel, qu'il se dénonce.

Écrire l'entrée précédente m'a motivé pour faire quelque chose dont je traîne l'idée depuis longtemps : produire de jolies illustrations de quelques projections de la sphère et du plan hyperbolique, et des analogies entre elles.

On trouve beaucoup d'images et de vidéos des projections de la sphère, mais elles utilisent généralement l'image des continents de la Terre, parce qu'elles ciblent la cartographie, et pour cette raison aussi elles ont tendance à omettre la projection gnomonique, ce qui est dommage parce qu'elle est mathématiquement intéressante (elle met en lumière le fait que la sphère quotientée par l'antipodie donne un plan projectif réel tandis que la projection stéréographique illustre le fait que la sphère peut être vue comme une droite projective complexe).

Il y a aussi beaucoup d'images et de vidéos du plan hyperbolique, mais presque exclusivement en utilisant les modèles du disque et demi-plan de Poincaré (les projections conformes standards), beaucoup plus rarement le modèle de Beltrami-Klein, et je crois que je n'ai jamais vu une projection équivalente (=préservant les aires) du plan hyperbolique, alors qu'on en montre souvent pour la sphère.

Enfin, les analogies entre la sphère et le plan hyperbolique sont rarement mises en valeur. Bref, j'ai fait cette vidéo pour essayer de combler les trous (le commentaire est en anglais ; apparemment YouTube ne permet pas de faire des vidéos bilingues, ce qui est tout de même con) :

Comme souvent, ce n'est pas ce qu'on pense qui a pris du temps : le programme pour calculer les images (qu'on peut trouver ici) est extrêmement simple et m'a pris nettement moins d'une heure à écrire (environ 150 lignes de C ! on fait difficilement plus simple, même s'il est vrai que j'ai dû faire quelques petits calculs de trigonométrie sphérique et hyperbolique pour calculer les constantes au début du programme). Le calcul lui-même a été aussi assez indolore. La lecture du commentaire, en revanche, a été abominable, et j'ai fini par craquer et renoncer à produire quelque chose de pas trop mauvaise qualité où je ne bégaierais pas sur plein de mots, où on n'entendrais pas les voisins qui passent dans le couloir, où je ne parlerais pas avec une voix différente entre chaque paragraphe, etc. Je ne suis vraiment pas doué pour ça.

[Ajout : une série de trois entrées ultérieures sur la géométrie hyperbolique : 1, 2, 3 (plus ou moins indépendantes) ; voir aussi les jeux de labyrinthe hyperbolique que j'introduis ici, là et là, et dont j'explique le fonctionnement dans des transparents disponibles ici.]

Parmi les théorèmes mathématiques que je trouve les plus magiques, le théorème de l'application conforme de Riemann est assez haut dans la liste.

Pour expliquer un peu au niveau grand public ce que ce théorème signifie, il faut d'abord expliquer application conforme : une application conforme (ou holomorphe — au niveau où je me place ce n'est pas la peine de faire de distinction) est simplement une transformation du plan qui conserve les angles (orientés). De façon encore plus simple, disons qu'une application conforme est une application qui préserve localement les formes sans les aplatir : elle peut plus ou moins les agrandir ou les rétrécir d'un point à l'autre, mais un tout petit cercle se transforme en quelque chose qui ressemble à un cercle, pas à une ellipse (voir plus loin ce que je dis sur les cartes de la Terre).

Pour ceux qui comprennent un peu plus de maths, je peux dire ceci : une application affine (c'est-à-dire, préservant l'alignement) qui conserve les angles (orientés) est ce qu'on appelle une similitude (directe), c'est-à-dire la composition d'une homothétie et d'une rotation (et éventuellement d'une translation) ; si on voit le plan comme l'ensemble des nombres complexes, alors une similitude (directe) est précisément une application de la forme z↦a·z+b pour certains nombres complexes a et b (le module et l'argument de a déterminant le rapport de l'homothétie et l'angle de la rotation, tandis que b détermine la translation ou le « centre » de la transformation). Une application conforme est une transformation qui, au premier ordre, en tout point, est une similitude (directe), c'est-à-dire, une application (d'une région du plan vers le plan) qui est différentiable et dont la différentielle est partout une similitude (directe) : d'après ce que je viens de dire, cela revient à voir ça comme une application dérivable au sens complexe.

À titre d'exemple, l'application exponentielle complexe, c'est-à-dire l'application qui à un point (x,y) du plan (qu'on peut identifier au nombre complexe z = x+i·y) associe le point (exp(x)·cos(y), exp(x)·sin(y)) (qu'on peut identifier au nombre complexe exp(z)), où ici exp(•) désigne e^•, est une transformation conforme. J'ai tenté de la représenter sur la figure suivante :

→

[Lire la suite…]

Mon poussinet m'a offert pour mon anniversaire (oui, c'était il y a plus de trois mois, mais le temps qu'on se décide vraiment on en a laissé passer deux, et le temps que je ne sois pas trop débordé pour m'en servir ça a fait un de plus) une petite imprimante thermique à tickets, le genre qu'on voit dans tous les commerces pour sortir les reçus ou facturettes, une Epson TM-T20 pour être précis.

C'est surtout un joujou que je trouvais assez mignon. L'idée n'est pas de faire des fausses factures (encore que ?) mais plutôt d'imprimer des petites notes ou pense-bête en tout genre. Par exemple des listes de courses, je me suis fait un petit programme Perl pour ça :

(Excusez la photo pourrie, c'est tellement fastidieux de transférer une photo de mon téléphone vers mon ordinateur que je ne vais pas en reprendre une juste pour la surexposition. D'autre part, j'ai un vrai petit logo à mettre en tête de ticket, mais comme mon poussinet a honte de mes talents de dessinateur je ne veux pas qu'il soit contrefait je l'ai juste remplacé par une image qui dit <Logo> <ici>.)

C'est assez rigolo d'utiliser les commandes ESC/POS, je me crois revenu à l'époque où j'étais petit et où j'avais une imprimante Epson FX-80 (enfin, un clone quelconque) à laquelle j'envoyais des codes d'échappement pour tester le gras, l'italique, etc., avec des programmes en BASIC ou en Pascal. Bon, mon imprimante à ticket est un chouïa plus moderne : même si elle ne connaît pas Unicode, elle a au moins un jeu de caractères un petit peu mieux foutu, et des commandes graphiques moins pourries (et quelques goodies amusants comme le fait de pouvoir imprimer des codes-barres ou des QR-codes). Par ailleurs, elle imprime à une vitesse assez impressionnante.

🔧

Parlant d'imprimante, celle de mon travail a changé. Avant j'avais en face de bureau une HP LaserJet 9040dn (noir et blanc) affectueusement baptisée Margot. Elle a fait place à un très impressionnant appareil copieur-imprimante-scanner (couleur, bien sûr) de modèle Ricoh MP-C3003 qui a dû coûter une petite fortune. Globalement c'est un progrès, mais il me reste encore des choses à configurer, parce que si j'utilise le pilote (enfin, le fichier PPD) trouvé sur OpenPrinting, certes l'impression en un exemplaire marche parfaitement que ce soit en couleur ou en noir et blanc, mais dès que j'essaie d'imprimer en n exemplaires :

• si je ne choisis pas collate (comment dit-on ça en français, d'ailleurs ? regrouper ? rassembler ?), elle imprime n fois la page 1, puis n fois la page 2, puis n fois la page 3, etc., et j'ai bien dit page et pas feuille, or c'est rarement utile d'avoir une feuille avec une page 1 de chaque côté ;
• si je choisis collate, elle imprime n fois la première feuille (page 1 + page 2), puis n fois la deuxième, et ainsi de suite, et ensuite elle refait le tout n fois, ce qui fait que n'ai n² exemplaires de mon document au lieu de n (si bien que je peux donc obtenir n'importe quel nombre de copies en au plus quatre impressions, comme quoi ça sert d'avoir fait des études).

Je ne sais pas si la faute en est à l'interprétation du format PJL par l'imprimante ou par le pilote, mais en tout cas c'est franchement ridicule.