David Madore's WebLog: 2013-11

This WebLog is bilingual, some entries are in English and others are in French. A few of them have a version in either language. Other than that, the French entries are not translations of the English ones or vice versa. Of course, if you understand only English, the English entries ought to be quite understandable without reading the French ones.

Ce WebLog est bilingue, certaines entrées sont en anglais et d'autres sont en français. Quelques-unes ont une version dans chaque langue. À part ça, les entrées en français ne sont pas des traductions de celles en anglais ou vice versa. Bien sûr, si vous ne comprenez que le français, les entrées en français devraient être assez compréhensibles sans lire celles en anglais.

Note that the first entry comes last! / Notez que la première entrée vient en dernier !

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entries published in November 2013 / Entrées publiées en novembre 2013:

(jeudi)

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) :

[La Terre vue en projection stéreographique depuis le pôle sud]

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

(jeudi)

Une erreur que je voudrais ne plus voir

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 an=1 : j'insiste en disant ça sur le fait qu'avoir an=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 ap−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 ak≡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 210≡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 22 et 25 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 an=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.)

(mercredi)

Petit TODO pour plus tard

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 :

(mardi)

Visualisation de la sphère et du plan hyperbolique

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

[Pavage heptagonal du plan hyperbolique] [Pavage pentagonal de la sphère (dodécaèdre)]

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.

(lundi)

La magie du théorème de l'application conforme de Riemann

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 za·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 :

[Grille cartésienne + polaire] [Image de la grille par l'exponentielle]

(samedi)

Imprimante à tickets

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 :

[Photo de liste de courses]

(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 :

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.

Continue to older entries. / Continuer à lire les entrées plus anciennes.


Entries by month / Entrées par mois:

2017 Jan 2017 Feb 2017
2016 Jan 2016 Feb 2016 Mar 2016 Apr 2016 May 2016 Jun 2016 Jul 2016 Aug 2016 Sep 2016 Oct 2016 Nov 2016 Dec 2016
2015 Jan 2015 Feb 2015 Mar 2015 Apr 2015 May 2015 Jun 2015 Jul 2015 Aug 2015 Sep 2015 Oct 2015 Nov 2015 Dec 2015
2014 Jan 2014 Feb 2014 Mar 2014 Apr 2014 May 2014 Jun 2014 Jul 2014 Aug 2014 Sep 2014 Oct 2014 Nov 2014 Dec 2014
2013 Jan 2013 Feb 2013 Mar 2013 Apr 2013 May 2013 Jun 2013 Jul 2013 Aug 2013 Sep 2013 Oct 2013 Nov 2013 Dec 2013
2012 Jan 2012 Feb 2012 Mar 2012 Apr 2012 May 2012 Jun 2012 Jul 2012 Aug 2012 Sep 2012 Oct 2012 Nov 2012 Dec 2012
2011 Jan 2011 Feb 2011 Mar 2011 Apr 2011 May 2011 Jun 2011 Jul 2011 Aug 2011 Sep 2011 Oct 2011 Nov 2011 Dec 2011
2010 Jan 2010 Feb 2010 Mar 2010 Apr 2010 May 2010 Jun 2010 Jul 2010 Aug 2010 Sep 2010 Oct 2010 Nov 2010 Dec 2010
2009 Jan 2009 Feb 2009 Mar 2009 Apr 2009 May 2009 Jun 2009 Jul 2009 Aug 2009 Sep 2009 Oct 2009 Nov 2009 Dec 2009
2008 Jan 2008 Feb 2008 Mar 2008 Apr 2008 May 2008 Jun 2008 Jul 2008 Aug 2008 Sep 2008 Oct 2008 Nov 2008 Dec 2008
2007 Jan 2007 Feb 2007 Mar 2007 Apr 2007 May 2007 Jun 2007 Jul 2007 Aug 2007 Sep 2007 Oct 2007 Nov 2007 Dec 2007
2006 Jan 2006 Feb 2006 Mar 2006 Apr 2006 May 2006 Jun 2006 Jul 2006 Aug 2006 Sep 2006 Oct 2006 Nov 2006 Dec 2006
2005 Jan 2005 Feb 2005 Mar 2005 Apr 2005 May 2005 Jun 2005 Jul 2005 Aug 2005 Sep 2005 Oct 2005 Nov 2005 Dec 2005
2004 Jan 2004 Feb 2004 Mar 2004 Apr 2004 May 2004 Jun 2004 Jul 2004 Aug 2004 Sep 2004 Oct 2004 Nov 2004 Dec 2004
2003 May 2003 Jun 2003 Jul 2003 Aug 2003 Sep 2003 Oct 2003 Nov 2003 Dec 2003