David Madore's WebLog: 2014-11

Vous êtes sur le blog de David Madore, qui, comme le reste de ce site web, parle de tout et de n'importe quoi (surtout de n'importe quoi, en fait), des maths à la moto et ma vie quotidienne, en passant par les langues, la politique, la philo de comptoir, la géographie, et beaucoup de râleries sur le fait que les ordinateurs ne marchent pas, ainsi que d'occasionnels rappels du fait que je préfère les garçons, et des petites fictions volontairement fragmentaires que je publie sous le nom collectif de fragments littéraires gratuits. • Ce blog eut été bilingue à ses débuts (certaines entrées étaient en anglais, d'autres en français, et quelques unes traduites dans les deux langues) ; il est maintenant presque exclusivement en français, mais je ne m'interdis pas d'écrire en anglais à l'occasion. • Pour naviguer, sachez que les entrées sont listées par ordre chronologique inverse (i.e., la plus récente est en haut). Cette page-ci rassemble les entrées publiées en novembre 2014 : il y a aussi un tableau par mois à la fin de cette page, et un index de toutes les entrées. Certaines de mes entrées sont rangées dans une ou plusieurs « catégories » (indiqués à la fin de l'entrée elle-même), mais ce système de rangement n'est pas très cohérent. Le permalien de chaque entrée est dans la date, et il est aussi rappelé avant et après le texte de l'entrée elle-même.

You are on David Madore's blog which, like the rest of this web site, is about everything and anything (mostly anything, really), from math to motorcycling and my daily life, but also languages, politics, amateur(ish) philosophy, geography, lots of ranting about the fact that computers don't work, occasional reminders of the fact that I prefer men, and some voluntarily fragmentary fictions that I publish under the collective name of gratuitous literary fragments. • This blog used to be bilingual at its beginning (some entries were in English, others in French, and a few translated in both languages); it is now almost exclusively in French, but I'm not ruling out writing English blog entries in the future. • To navigate, note that the entries are listed in reverse chronological order (i.e., the most recent is on top). This page lists the entries published in November 2014: there is also a table of months at the end of this page, and an index of all entries. Some entries are classified into one or more “categories” (indicated at the end of the entry itself), but this organization isn't very coherent. The permalink of each entry is in its date, and it is also reproduced before and after the text of the entry itself.

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]

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

↓Entry #2252 [older| permalink|newer] / ↓Entrée #2252 [précédente| permalien|suivante] ↓

(samedi)

Les ancêtres de Cléopâtre

On insiste souvent sur le fait que la consanguinité et l'inceste provoquent toutes sortes de malformations et de difformités physiques, comme le dernier Habsbourg d'Espagne au profil si princier. D'un autre côté, considérons la reine Cléopâtre — je parle bien de la reine lagide Cléopâtre VII Philopatôr, celle qui a été la maîtresse de Jules César puis de Marc-Antoine — renommée pour son nez si exquis : son père était fils d'un frère (Ptolémée IX) et d'une sœur, eux-mêmes enfants d'un oncle et de sa nièce (d'ailleurs doublement sa nièce !) ; tandis que la mère de Cléopâtre était fille d'un autre frère du même Ptolémée IX et d'une fille de ce dernier avec encore une autre de ses sœurs. Ptolémée IX (un de ceux qui est fils d'un oncle et de sa doublement nièce) est donc simultanément le grand-père paternel, le grand-oncle paternel, le grand-oncle maternel, l'arrière-grand-père maternel maternel, et l'arrière-grand-oncle idem, de Cléopâtre. Si vous arrivez à suivre sans tracer l'arbre généalogique, bravo. En tout cas, en matière de consanguinité, je crois que les Habsbourgs d'Espagne sont très largement battus (comme Cléopâtre, il est fils d'un oncle et de sa nièce, mais ça ne va pas beaucoup plus loin). (À part ça, le fait que tous les rois s'appellent Ptolémée et la moitié des reines Cléopâtre n'aide pas vraiment à s'y retrouver dans cet arbre de fous.)

↑Entry #2252 [older| permalink|newer] / ↑Entrée #2252 [précédente| permalien|suivante] ↑

↓Entry #2251 [older| permalink|newer] / ↓Entrée #2251 [précédente| permalien|suivante] ↓

(samedi)

Où je résous une équation

L'équation[#] a₁·b₁·a−1·b−1 · a₂·b₂·a−1·b−1 · a₃·b₃·a−1·b−1 · a₄·b₄·a−1·b−1 conjugué à u₁·v₂·u−1·v−1 · u₂·v₃·u−1·v−1 · u₃·v₄·u−1·v−1 · u₄·v₁·u−1·v−1 dans le groupe libre a (entre autres) comme solution :

  • a₁ = v₁·u₄·v−1
  • b₁ = v₂·u
  • a₂ = v₂·u₁·v−1
  • b₂ = v₃·u
  • a₃ = v₃·u₂·v−1
  • b₃ = v₄·u
  • a₄ = v₄·u₃·v−1
  • b₄ = v₁·u

ou réciproquement

  • u₁ = b−1·a₁·b
  • v₁ = a−1·b
  • u₂ = b−1·a₂·b
  • v₂ = a−1·b
  • u₃ = b−1·a₃·b
  • v₃ = a−1·b
  • u₄ = b−1·a₄·b
  • v₄ = a−1·b

(Et la conjugaison se fait par v₁·u₄.)

[#] Les inconnues sont a₁,b₂,a₃,b₄,a₁,b₂,a₃,b₄ tandis que u₁,u₂,u₃,u₄,v₁,v₂,v₃,v₄ sont les générateurs du groupe libre — mais ça ne change rien si on fait le contraire : c'est pour ça que je donne à la fois une solution et une réciproque.

Cela pouvait effectivement peut-être se trouver de tête en regardant assez longuement les équations et en ayant foi dans le fait (douteux) qu'une équation aussi symétrique devait pouvoir admettre une solution symétrique. En l'occurrence, j'ai trouvé ces valeurs en appliquant l'algorithme de Whitehead déguisé sous forme d'un problème combinatoire, et finalement en appliquant un Dijkstra sur le graphe des 127072 façons de tracer 8 cordes disjointes entre 16 points cycliquement ordonnées. Je n'ai pas du tout d'idée claire sur la question de savoir si cette solution est vaguement unique[#2] (et si oui, en quel sens).

[#2] Enfin, je sais qu'elle n'est pas unique, puisque la première version que j'ai trouvée (en minimisant le nombre de chiasmes plutôt qu'une certaine forme de longueur) était beaucoup plus désagréable : a₁=v−1·u−1·v₁·u₄·u₁·u₃·v₄, b₁=v−1·u−1·v₂·u−1·v−1·u₃·v₄, a₂=v−1·u−1·v₂·u₁·u₂, b₂=v₃·u−1·v−1·u₃·v₄, a₃=v−1·u−1·u−1·v−1·u₃·v₄, b₃=v−1·u−1·v₁·u₄·u₃·v₄·v−1·u₃·v₄, a₄=v−1·u−1·v₁·u₄·u₃·v₄·u−1·v−1·u−1·u−1·v−1·u₃·v₄, b₄=v−1·u−1·v₁·u₄·u₃·v−1·u−1·u−1·v−1·u₃·v₄, dont la réciproque est donnée par u₁=a₃·a−1·b−1·a₁·a₃·b₄·a₄·a−1, v₁=a₃·a−1·b−1·a−1·b−1·a−1, u₂=a₃·a−1·b−1·a−1·a−1·b−1·a₂, v₂=a₃·a−1·b−1·a−1·b₁·b₄·a₄·a−1, u₃=a₃·a−1·a−1, v₃=b₂·b₁·a₁·a₃·b₄·a₄·a−1, u₄=a₃·b₃·b₄·a₄·a−1, v₄=a₃·b−1·a−1 (et la conjugaison se fait par v−1·u−1·v₁·u₄). Est-ce pourtant, en un certain sens, « la même » solution ?

L'ennui, c'est qu'arrivé à ce stade-là, je ne sais plus très bien ce que je dois faire de cette solution, parce que je ne me rappelle plus vraiment ce que je voulais faire au début : je suis parti de questions sur le revêtement hyperbolique d'une surface de Riemann pour arriver, de fil en aiguille, à quelque chose de sérieusement différent, et maintenant que j'ai la réponse, j'ai oublié quelle était la question. Ça fait penser à une vieille blague avec un père jésuite, ça (quand on a la réponse, on ne comprend plus la question).

Suite : voir ici.

↑Entry #2251 [older| permalink|newer] / ↑Entrée #2251 [précédente| permalien|suivante] ↑

↓Entry #2250 [older| permalink|newer] / ↓Entrée #2250 [précédente| permalien|suivante] ↓

(jeudi)

Où je pose un problème combinatoire

Le problème qui suit vient d'une suite de réflexions sur le thème des deux dernières entrées, mais peu importe : la question est compréhensible et intéressante en elle-même, elle me semble même très jolie, et elle ne dépend pas de la lecture des entrées en question — je ne vais d'ailleurs quasiment pas expliquer comment je suis arrivé à ce problème (seulement en note en bas).

Je suppose que j'ai 2m symboles, pour un certain entier m≥1, que je noterai X1,X2,X3,…,Xm et X1′,X2′,X3′,…,Xm′ ; la correspondance entre Xi et Xi′ est essentielle, et je dirai que Xi′ est le symbole complémentaire de Xi et réciproquement. Je m'intéresse à des cycles de longueur 2m sur ces symboles faisant intervenir chaque symbole une et une seule fois (le terme cycle signifie qu'on identifie deux suites qui s'obtiennent l'un à partir de l'autre par une permutation cyclique, par exemple X1,X2,X1′,X2′ s'identifie à X2,X1′,X2′,X1). Il existe bien sûr (2m)!/(2m) = (2m−1)! tels cycles.

On va définir sur les cycles des opérations qui porteront le nom de chiasme de Whitehead (le terme est de moi). Pour définir un chiasme de Whitehead, on commence par choisir un des symboles Z (qui peut être un Xi ou un Xi′) qu'on appellera la base du chiasme ; puis on considère la suite des symboles strictement comprise entre Z et le symbole complémentaire Z′ (c'est-à-dire Xi′ ou Xi si Z vaut Xi ou Xi′ respectivement) qui le suit dans le cycle ; on découpe ce segment de façon quelconque en deux segments consécutifs (non vides si on veut que le chiasme soit non-trivial) et on échange ceux-ci. Voici un exemple : X1,X2,X3,X4,X1,X2,X3′,X4′ peut devenir X1,X2,X4,X1,X3,X2,X3′,X4′ par un chiasme de Whitehead si on choisit pour base Z=X2 et qu'on découpe le segment X3,X4,X1′ en X3 et X4,X1 ; en prenant pour base Z=X4 (et en se souvenant que tout est cylique !), le même cycle X1,X2,X3,X4,X1′,X2′,X3′,X4 peut devenir X3,X1,X2,X4,X1′,X2′,X3′,X4.

Remarquons que tout symbole Z peut servir à définir un chiasme de Whitehead (fût-il trivial), puisqu'on peut toujours lire cycliquement jusqu'à tomber jusqu'au symbole complémentaire Z′ qui suit ; si ce dernier survient k symboles plus loin, on pourra faire k−2 chiasmes de Whitehead non triviaux ; et comme le Z′ est lui-même suivi d'un Z (le même qu'au départ) 2mk symboles plus loin, on peut faire finalement 2m−4 chiasmes de Whitehead non triviaux partant de Z ou Z′ (du moins si ceux-ci ne sont pas immédiatement adjacents, i.e., k≠1,2m−1). Au final, on peut donc faire exactement m(2m−4) chiasmes de Whitehead non-triviaux sur n'importe quel cycle (n'ayant nulle part deux symboles complémentaire adjacents).

Ma question est la suivante : comment peut-on détecter si deux cycles peuvent se déduire l'un de l'autre par une suite de chiasmes de Whitehead, et le cas échéant, comment les produire ? (Il est évident que le problème est décidable puisqu'il est, après tout, fini, mais je demande quelque chose de plus utilisable que l'énumération exhaustive.) Une variante de cette question autorise aussi d'effectuer une permutation des symboles préservant la complémentarité (cf. ci-dessous).

Un point de vue possible, qui simplifie peut-être le problème, ou au contraire le complique, je ne sais pas, consiste à se limiter aux cycles ayant la propriété suivante. Donné un cycle, je peux considérer la fonction qui à un symbole U associe le complémentaire V′ du symbole V qui suit immédiatement U dans le cycle (autrement dit, la fonction composée du cycle considérée interprétée comme une permutation cyclique, et de la fonction « symbole complémentaire ») ; si cette fonction est elle-même un 2m-cycle (c'est-à-dire, si, en partant d'un symbole quelconque et en appliquant successivement cette fonction, on retombe sur le symbole en 2m étapes et pas avant), je dirai que le cycle de départ est parfait, et que l'autre cycle obtenu par cette construction est son dual de Whitehead. Il est clair que le dual de Whitehead est alors lui-même parfait et que son dual est le cycle de départ. Par exemple, le cycle X1,X2,X1′,X2′ est parfait et son dual est X1,X2′,X1′,X2 (i.e., dans ce cas particulier, le cycle inversé), tandis que X1,X2,X3,X1′,X2′,X3′ n'est pas pas parfaite (on tombe sur deux 3-cycle X1,X2′,X3 et X2,X3′,X1′). En fait, si m est impair, aucun cycle (de longueur 2m) n'est jamais parfait (en effet, un 2m-cycle est une permutation impaire, et la fonction « symbole complémentaire » l'est aussi si m est impair, donc la composée ne peut pas être un 2m-cycle). Notons d'ailleurs qu'un cycle parfait ne peut jamais avoir deux symboles complémentaires adjacents.

Il est facile de se convaincre que l'effet d'un chiasme de Whitehead sur le dual d'un cycle parfait est de déplacer le symbole de base d'un endroit à un autre sans changer aucun autre symbole — et notamment, un cycle parfait demeure parfait après application d'un chiasme de Whitehead (ou de façon plus générale, le nombre de cycles du dual ne changerait pas sous l'effet d'un chiasme de Whitehead si on prenait la peine de définir de façon évidente le dual d'un cycle imparfait). On peut se limiter à regarder l'effet des chiasmes de Whitehead sur les cycles parfaits. Ou, si on préfère, sur leur dual (l'effet du chiasme est alors très simple puisqu'on ne déplace qu'un symbole, mais la difficulté est qu'on ne peut pas le déplacer n'importe où).

Si j'ai bien réussi à dérouler[#] et à reformuler une série de résultats autour de la théorie des surfaces qui débutent par un théorème de Whitehead de 1936 (le neveu, pas l'oncle), on peut toujours passer d'un cycle parfait à un autre par une suite de chiasmes de Whitehead, quitte à effectuer, de plus, une permutation des variables préservant la complémentarité (c'est-à-dire qu'on peut renommer Xi en Xj ou Xj′, mais on doit alors renommer Xi′ en Xj′ ou Xj respectivement). Ce que je ne sais pas, c'est par exemple comment produire concrètement une telle suite d'opérations, ou quelle liberté on a dans le processus, ou comment détecter si on a vraiment besoin d'une permutation des variables. Ou si on a vraiment besoin de ces résultats assez compliqués (dont il s'agit d'un cas extrêmement spécial et particulier). En fait, à peu près tout est obscur pour moi dans cette histoire, à commencer par le meilleur point de vue à adopter (entre un cycle et son cycle dual, savoir s'il faut les voir comme des mots du groupe libre ou des permutations, etc.). Il faut peut-être que je me plonge dans les détails de la démonstration de la classification des surfaces topologiques pour y voir plus clair.

En attendant, ceci ferait peut-être un casse-tête amusant, que je pourrais essayer de programmer en JavaScript : quitte à tracer le cycle comme autant de points sur un cercle, entre lesquels on relierait les symboles complémentaires (c'est la seule donnée qui survit si on s'autorise, comme je le suggère ci-dessus, une permutation des variables préservant la complémentarité), essayer de transformer une configuration donnée en une autre par des chiasmes de Whitehead. Ceux-ci se voient assez bien graphiquement (comme illustré par les figures en SVG ci-contre à gauche : en rouge, la base d'un chiasme, qui échange les segments vert et bleu ; à droite, une cible possible à atteindre).

Bref, si quelqu'un a quelque chose à dire sur le sujet, ça m'intéresse. (Ou même sur les données d'un appariement sur 2m points cycliquement ordonnés, c'est-à-dire d'un 2m-cycle et d'une involution sans point fixe.)

[#] Plutôt pour m'en souvenir moi-même qu'à l'intention de mes lecteurs, je note ici rapidement le raisonnement. Si on note la suite cyclique des symboles donnée par le dual d'un cycle parfait comme je l'ai défini, on obtient un mot cyclique dans le groupe libre sur autant de générateurs ; l'algorithme de Whitehead (voir notamment Lyndon & Schupp, Combinatorial Group Theory (1977), proposition 4.19 et la discussion précédente) assure que deux mots cycliques sont transformables l'un en l'autre par un automorphisme du groupe libre exactement quand ils le sont par des transformations de Whitehead (n'allongeant pas le mot) qui, sur le cycle dual, se voient comme les chiasmes de Whitehead que j'ai définis. Mais d'autre part les cycles parfaits définissent des surfaces orientables (à un trou) de genre m/2, cf. l'article de Marc Culler auquel je faisais référence dans la dernière entrée.

↑Entry #2250 [older| permalink|newer] / ↑Entrée #2250 [précédente| permalien|suivante] ↑

↓Entry #2249 [older| permalink|newer] / ↓Entrée #2249 [précédente| permalien|suivante] ↓

(vendredi)

Où je comprends un peu mieux comment recoller les surfaces

Cette entrée fait logiquement suite à la précédente, même si je vais essayer de redire en partie (pour, j'espère, éclaircir) ce que j'y disais. Sinon, ce n'est pas grave, c'est au moins un nouveau prétexte pour faire des zoulis dessins.

[Un domaine fondamental dans le plan hyperbolique]Je me posais (dans l'entrée précédente) la question de comprendre la forme — et mathématiquement, la réalisation du groupe fondamental — d'une surface obtenue en recollant un polygone par identification de certaines arêtes du bord. (En l'occurrence, un polygone hyperbolique, mais peu importe si on veut juste se poser des questions de topologie.)

J'ai tracé ci-contre à gauche (cliquez pour agrandir) une version beaucoup plus symétrique, quitte à découper à l'intérieur des carrés du pavage, du « domaine fondamental » de mon labyrinthe hyperbolique jouet, ce sera beaucoup plus satisfaisant d'expliquer sur cet exemple-là, même si les explications que je vais donner sont tout à fait générales. J'ai aussi choisi un code de couleurs plus logique (et, j'espère, un peu moins difficile à repérer visuellement), et surtout, j'ai choisi de marquer les identifications par des pastilles au niveau des sommets plutôt que par des languettes au niveau des arêtes. Il faut donc comprendre qu'on a identifié les deux arêtes portant chaque paire de couleurs consécutives possible (par exemple les deux arêtes vert-clair–bleu-foncé sont identifiées, en identifiant bien sûr les extrémités de la même couleur ; ainsi, dans mon jeu de labyrinthe, si on sort du domaine fondamental par une arête vert-clair–bleu-foncé, on y rentre par l'autre arête ayant le même code de couleurs). Le but est de comprendre, de façon aussi explicite que possible, ce qu'on obtient en faisant ces identifications (et pourquoi, sur mon exemple, on obtient un tore à 4 poignées, et comment voir ces poignées).

Pour ceux qui auraient du mal à voir la figure ou qui voudraient plus de détails, la description complète du polygone hyperbolique ci-contre est la suivante : gris [X] bleu-clair [Y] vert-foncé* [X] rouge-clair [Y] jaune-foncé [Y] vert-clair [X] rouge-foncé* [Y] bleu-clair [X] gris [X] rouge-clair [Y] bleu-foncé* [X] jaune-clair [Y] vert-foncé [Y] bleu-clair [X] jaune-foncé* [Y] rouge-clair [X] gris [X] jaune-clair [Y] rouge-foncé* [X] vert-clair [Y] bleu-foncé [Y] rouge-clair [X] vert-foncé* [Y] jaune-clair [X] gris [X] vert-clair [Y] jaune-foncé* [X] bleu-clair [Y] rouge-foncé [Y] jaune-clair [X] bleu-foncé* [Y] vert-clair [X] : ici, les couleurs étiquettent les sommets (c'est la seule chose qui importe topologiquement), les astérisques qui suivent certains d'entre eux signifient qu'à cet endroit le polygone a un angle de 3π/4 (i.e., en suivant le périmètre, on fait un tournant de π/4 vers la gauche) alors que partout ailleurs c'est un angle droit (i.e., on fait un tournant de π/2 vers la gauche), et les lettres X et Y font référence aux longueurs des cotés, à savoir X≈1.4693517444 et Y≈1.5919125929 unités naturelles de longueur du plan hyperbolique. (Mon polygone hyperbolique a donc seulement deux angles différents et deux longueurs différentes de côtés ; par ailleurs, il est symétrique par rapport à quatre axes. Mais je répète que, pour ce qui est de la topologie, les longueurs des côtés et angles aux sommets n'ont pas d'importance.)

Le fait de colorier les sommets et pas les arêtes, pour l'identification, aide à y voir plus clair : on est naturellement amené à tracer le graphe des sommets du polygone en reliant deux sommets lorsqu'il y a une arête qui les joint sur le polygone. Sur mon exemple, bien que le polygone ait prima facie 32 sommets (et donc 32 arêtes), il n'a en fait, compte tenu des identifications, que 9 sommets distincts (i.e., 9 couleurs), et 32/2 = 16 arêtes. Le graphe d'adjacence des sommets est tracé ci-contre pour ceux dont le navigateur supporte le SVG.

↑Entry #2249 [older| permalink|newer] / ↑Entrée #2249 [précédente| permalien|suivante] ↑

↓Entry #2248 [older| permalink|newer] / ↓Entrée #2248 [précédente| permalien|suivante] ↓

(lundi)

J'essaie de recoller une surface de Riemann

[Un domaine fondamental dans le plan hyperbolique]Le hasard a fait que j'ai repensé à mon petit jeu HTML de labyrinthe hyperbolique, mais en fait surtout à sa version jouet (voir ici et pour les de mon blog où j'en discute), en même temps que je me posais des questions sur les surfaces de Riemann. En fait, je ne suis pas terriblement content de mon jeu : l'espace hyperbolique étant en lui-même labyrinthique, il est dommage de plaquer dessus un dédale avec des murs infranchissables — je voudrais refaire un jeu où les mouvements ne sont jamais bloqués, pour montrer qu'il est quand même difficile de trouver son chemin dedans. Mais pour cela, il faut que je comprenne un peu mieux des choses sur lesquelles j'ai encore des idées vagues, même sur la version jouet de mon labyrinthe.

☞ J'invite mon lecteur à essayer d'y jouer, ou plus exactement, à s'y déplacer en essayant de se faire une idée de la géographie du labyrinthe — je ne parle pas de la forme des murs eux-mêmes, mais de la périodicité de l'espace. On peut par exemple jouer à se rendre de la case de départ à la case d'arrivée en utilisant le nombre exact de déplacements optimal (indiqué à droite), et à prévoir le chemin avant de faire le moindre déplacement. On devrait au moins réussir à se convaincre qu'il n'y a en fait, dans ce labyrinthe-jouet, que 30 cellules différentes (les cellules étant des « carrés » de murs possibles, au centre desquels se trouve un cercle de référence). Les carrés blancs dans l'image ci-contre à gauche représentent un choix possible des 30 cellules du labyrinthe (c'est-à-dire que tout carré en-dehors de ceux-ci est, en fait, identique à l'un de ceux-ci) : on dit qu'il s'agit d'un domaine fondamental (pour le groupe fondamental de mon labyrinthe).

Il faut souligner qu'il y a beaucoup d'arbitraire dans le choix d'un tel domaine fondamental : j'aurais très bien pu faire passer tel ou tel carré d'un côté à l'autre en le remplaçant par un autre qui lui est équivalent. Mais bon, cela n'a pas beaucoup d'importance, et on n'aurait pas pu obtenir une figure symétrique — malgré le fait que la surface recollée que je décris ci-dessous soit réellement très symétrique.

La figure ci-contre à gauche peut être considérée comme une sorte de patron géométrique : les arêtes du bord ont été décorées par des petites languettes figurées en couleur ; si on recolle chaque languette sortante sur le bord des cases blanches avec la languette entrante qui lui correspond (par exemple, les deux languettes rouges qui forment une sorte d'entaille un tout petit peu à gauche du bas de la figure sont à recoller avec les deux languettes rouges qui forment une saillie en haut à gauche), on obtient la forme de l'espace de mon labyrinthe-jouet — ou pour dire les choses autrement, dans ce labyrinthe, si on sort du « domaine fondamental » par une des languettes colorées, on y rentre par la languette qui correspond.

↑Entry #2248 [older| permalink|newer] / ↑Entrée #2248 [précédente| permalien|suivante] ↑

↓Entry #2247 [older| permalink|newer] / ↓Entrée #2247 [précédente| permalien|suivante] ↓

(vendredi)

Grothendieck, la propriété intellectuelle, et le testament de Virgile

Bon alors il faut vraiment que je publie quelque chose sur la mort d'Alexander Grothendieck, ne serait-ce que pour faire cesser le flux de gens qui m'envoient un mail — ou postent un commentaire sur une entrée qui n'a rien à voir — pour me demander si j'en avais connaissance (oui, la preuve) ou s'étonner que je n'aie rien à dire à ce sujet (eh, calmez-vous un peu !, il est mort depuis même pas 48h, la presse people n'a pas encore sorti un numéro spécial à son sujet — permettez que je n'écrive pas instantanément des textes au kilomètre).

Je n'essaierai pas, en tout cas pas aujourd'hui, de parler du contenu de ses travaux mathématiques, parce que rien que pour vulgariser — et pas au niveau le plus élémentaire qui soit — le concept très basique de schéma j'avais écrit une des entrées les plus longues de ce blog, alors je ne sais pas ce que ça donnerait si je me lançais dans une explication de ce que sont les champs, les topos (topoï ?) ou les motifs (sur ce dernier concept au moins, ce serait en outre présumer de mes connaissances mathématiques que de tenter d'en parler).

Je n'essaierai certainement pas non plus de parler de la polémique autour de la paternité de telle ou telle idée mathématique, qui l'a conduit à se fâcher avec une partie de la communauté mathématique, notamment nombre de ses anciens élèves, et à publier sa version des faits dans un très long texte, Récoltes et Semailles, où il règle ses comptes avec beaucoup de gens. Je sais que je suis un peu extrémiste quand je pense que les articles scientifiques devraient être anonymes (pas forcément au sens où le nom des auteurs serait tenu secret mais au sens où il ne devrait pas être une donnée importante), et que les objets et théorèmes mathématiques ne devraient pas être nommés d'après des personnes vivantes ou mortes mais d'après des idées (i.e., pas comme la conjecture de Poincaré, le théorème des zéros de Hilbert ou les conjectures de Weil, mais comme l'hypothèse du continu, le théorème de la boule chevelue ou la conjecture de pureté cohomologique absolue) : toujours est-il que les questions de paternité m'intéressent très peu — le monde des idées, et en tout cas des idées mathématiques, n'est la propriété de personne. (Et de toute façon, quand les élèves de Grothendieck étaient mes enseignants ou les enseignants de mes enseignants, je me vois mal me prononcer sur qui à fait quoi.)

Je n'essaierai enfin pas de parler de la vie de Grothendieck ou de ses idées politiques (et plus généralement non-mathématiques), parce que je ne prétends pas en savoir assez, ou comprendre ce personnage complexe et énigmatique, et d'autres s'en chargeront certainement mieux que moi.

Mais il y a un point sur lequel je voudrais dire un mot, c'est sur la question des écrits de Grothendieck et de leur propriété intellectuelle (au sens juridique du droit d'auteur). Parce que la communauté mathématique, du moins, ceux qui s'intéressent à la géométrie algébrique, a un problème pratique : la référence incontournable qui fonde la lecture moderne de cette discipline est une série de textes (écrits en français), les Éléments de Géométrie algébrique (ÉGA), soit environ 1800 pages, plus les Séminaires de Géométrie algébrique [du Bois Marie] (SGA), numérotés de SGA1 à SGA7, soit environ 5700 pages au total (sans compter SGA4½), dont Grothendieck est soit l'auteur soit un coauteur (comme je l'explique ci-dessus, la question de la paternité intellectuelle m'intéresse peu — même si ici il n'y a aucune contestation — mais je parle au sens juridique). Malgré des efforts de divers auteurs pour écrire des introductions plus ou moins complètes à la géométrie algébrique (et dont le plus sérieux est sans doute le monumental Stacks Project que je salue très bas au passage ainsi que son grand coordinateur, A. Johan de Jong), aucun n'a réussi à couvrir tout ce que couvrent les ÉGA et encore moins les SGA (et quand bien même on y arriverait, il resterait encore que toutes les références numériques à ces textes n'ont de sens que si on y a accès).

Or voici le problème pratique : Alexander Grothendieck s'est toujours opposé à ce qu'on réédite ces textes. (Je ne prétends pas comprendre, encore moins expliquer, quelles étaient ses motivations pour le refuser.)

↑Entry #2247 [older| permalink|newer] / ↑Entrée #2247 [précédente| permalien|suivante] ↑

↓Entry #2246 [older| permalink|newer] / ↓Entrée #2246 [précédente| permalien|suivante] ↓

(lundi)

Comment travailler sur du XML en conservant le formatage ?

Je ne suis certainement pas le premier à me poser cette question, et ça m'étonnerait un peu qu'il n'y ait pas déjà une solution, mais je ne trouve pas — il faut dire que je ne sais pas bien quoi chercher comme mots-clés.

Voici mon problème :

J'ai des fichiers XML que je voudrais traiter avec des outils XML, par exemple appliquer une feuille de style XSLT (qui laissera la grande majorité du document inchangé, se contentant d'ajouter des attributs ici ou là, ou peut-être quelques balises). Néanmoins, je voudrais préserver, dans la mesure du raisonnable, le formatage du document d'origine : par formatage dans cette phrase, je veux dire la manière dont les balises et les attributs sont écrits/sérialisés (par exemple, <foo color="blueish" price="expensive" /> et <foo price='expensive' color='blueish'/> sont deux formatages différents de la même balise, de même que des changements possibles du whitespace, et plus généralement tout ce qui conduit au même XML canonique — on peut d'ailleurs considérer ça comme la définition du formatage : deux documents XML diffèrent uniquement par le formatage lorsqu'ils ont le même XML canonique). Concrètement, je veux que le diff de mon document après traitement (par une feuille de style XSLT qui ne change que quelques attributs ou balises) soit en gros aussi faible que possible avec celui avant traitement (parmi tous les formatages possibles de la sortie XML du traitement).

Éclaircissement/redite : Comme je semble avoir été mal compris, je vais essayer de redire différemment ce que je cherche à faire. Je ne cherche pas à reformater du XML, au contraire, je cherche à le modifier sans le reformater : je cherche à traiter du XML par des outils XML en changeant le moins possible le XML en sortie (et notamment, sans changer le formatage des balises qui n'auront pas du tout été modifiées). Concrètement, j'ai du XML écrit à la main, je veux faire des changements automatisés dessus tout en préservant les idiosyncrasies du formatage à la main (notamment : l'ordre des attributs, le whitespace dans les balises ouvrantes et fermantes, les sections CDATA, les entités, ou le fait d'écrire parfois certains caractères Unicode sous forme de références de caractères).

Y a-t-il des outils pour réaliser ça ?

Je pensais à l'idée suivante : inventer un namespace ad hoc qui sert à refléter le formatage XML. Autrement dit, partant d'un document XML sous un certain format texte, on aurait des outils qui ajoutent des attributs et balises de ce namespace servant à stocker tous les détails du formatage (l'ordre des attributs, le type de guillemets les représentant, le whitespace partout où il n'est pas significatif, etc.), et capables, inversement, d'interpréter (et retirer) ces attributs et balises pour recréer le document exactement tel qu'il était, même s'il a été reformaté entre temps (par exemple remplacé par son XML canonique). On pourrait alors travailler en trois étapes : ajouter les attributs et balises représentant le formatage, travailler avec XSLT sur le document ainsi enrichi (la feuille de style XSLT ignorerait typiquement les éléments de formatage), puis réappliquer le formatage sauvegardé dans les attributs et balises spécifiques (dans certains cas l'information de formatage serait incomplète ou non directement applicable, bien sûr, vu que des attributs ou balises ont pu être ajoutés, supprimés ou changés par le XSLT, mais le reformateur ferait « au mieux » dans un sens pas très important).

Ça ne doit pas être horriblement compliqué d'écrire des outils comme ça de sauvegarde/sérialisation et restauration/désérialisation du formatage, mais ça m'arrangerait de ne pas être celui qui invente la roue surtout si quelqu'un l'a fait avant moi. Quelqu'un connaît-il des choses dans ce sens ?

Ajout () : J'envisage essentiellement trois pistes pour résoudre mon problème :

  • La méthode générale exposée ci-dessus pourrait ressember à ceci : un premier outil transformerait le XML fourni en entrée en ajoutant des entités et éléments représentant sa syntaxe concrète. Par exemple <foo color='blueish' price='expensive'/> serait transformé en lui ajoutant un attribut ws:emptytag="&lt;foo color='blueish' price='expensive'/&gt;" servant à représenter la syntaxe concrète de la totalité de la balise sur une balise vide. Puis ce XML enrichi serait transformé par le XSLT. Enfin, un autre outil tenterait de réappliquer la syntaxe concrète, en vérifiant qu'elle correspond toujours à l'arbre XML (et en la supprimant dans le cas contraire) : du coup, par exemple, le XML canonique <foo color="blueish" price="expensive" ws:emptytag="&lt;foo color='blueish' price='expensive'/>"></foo> serait retransformé en <foo color='blueish' price='expensive'/> (grâce à la valeur de l'attribut ws:emptytag) tandis que s'il a été transformé, disons, en <foo color="blueish" price="inexpensive" ws:emptytag="&lt;foo color='blueish' price='expensive'/>"></foo> (par changement d'un attribut) alors il deviendrait simplement <foo color="blueish" price="expensive"></foo> (en supprimant purement et simplement l'attribut ws:emptytag qui n'a plus la bonne valeur).
  • Une deuxième approche consisterait à essayer simplement de faire des modifications avec perl, mais en ayant marqué les emplacements à modifier avec des outils XML. Voici donc une question plus simple que ma question générale ci-dessus : y a-t-il des outils qui permettent, donné un fichier XML et une expression XPath, de retourner le numéro de ligne (et éventuellement le numéro de colonne dans la ligne) où commence (la syntaxe concrète de) l'élément désigné par le XPath ? (Il y a une question apparentée par exemple ici. Je suppose que je dois pouvoir m'en sortir en construisant l'arbre DOM avec un parseur SAX et en annotant chaque élément par son numéro de ligne.)
  • Une troisième approche, qui est certainement la plus simple, mais évidemment aussi la moins générale : canoniser mon document XML, appliquer la transformation XSLT sur le document canonisé (et canoniser la sortie), faire le diff entre les deux, et essayer d'appliquer ce patch au fichier XML de départ, en priant pour qu'il s'applique sans mal (ce qui, pour ce que je veux faire, est tout de même hautement probable).

J'avais réfléchi à plusieurs occasions à ce problème et à des questions adjacentes, et je m'étais dit qu'il faudrait développer une petite théorie formelle des encodages, réencodages et transcodages de l'information : notamment, je pense que le théorème de Cantor-Schröder-Bernstein a son mot à dire dans l'histoire du round-trip encoding (je rappelle qu'il s'agit du théorème qui affirme que si on a une injection f:AB et une injection g:BA dans des sens opposés entre deux ensembles, alors on a une bijection entre A et B), et que sa démonstration (constructive !) pourrait fournir des conventions en la matière. (Je ne prétends pas qu'il s'agisse du même problème que celui évoqué ci-dessus, mais qu'il s'agit de problématiques du même genre ; on pourra par exemple réfléchir à la question suivante : si j'appelle f la fonction qui envoie tout arbre (DOM) XML abstrait sur son XML canonique, et g la fonction qui envoie un document texte sur l'arbre DOM XML qui a une unique balise text contenant tout le texte, alors à quoi ressemble la bijection entre fichiers texte et arbres XML que produit une démonstration constructive standard du théorème de Cantor-Schröder-Bernstein à partir de ces deux injections ? Même question si on remplace g par une injection des documents XML bien-formés dans les arbres DOM XML obtenue en ajoutant des balises de formatage comme je le suggère ci-dessus.)

↑Entry #2246 [older| permalink|newer] / ↑Entrée #2246 [précédente| permalien|suivante] ↑

↓Entry #2245 [older| permalink|newer] / ↓Entrée #2245 [précédente| permalien|suivante] ↓

(dimanche)

Fragment littéraire gratuit #148 (le souvenir du passé)

C'était le 9 novembre 2014. L'Europe fatiguée essayait de se souvenir des événements survenus vingt-cinq ans plus tôt, en même temps que les autres 9 novembre d'un siècle sanglant se bousculaient dans sa mémoire comme la chronologie dérangée d'une histoire qui bégaye. L'Europe avait la gueule de bois d'avoir trop fait la fête à la porte de Brandebourg sur l'air de Wind of Change des Scorpions, et cherchait maintenant à se rappeler ce qu'elle célébrait au juste.

Мир стоит на грани новой холодной войныLe monde est au bord d'une nouvelle guerre froide — avait averti le vieil ours Gorbatchev, l'air de dire : c'est moi qui ai fait tomber les dominos une première fois, ne comptez pas sur moi pour recommencer si vous les remettez en place.

Hegel a remarqué quelque part que tous les grands faits et personnages de l'Histoire du monde apparaissent pour ainsi dire deux fois. Il a oublié d'ajouter, nous prévient Marx : la première fois comme une tragédie, la seconde comme une farce.

Tout le monde se demande donc qui sera le dindon de la farce, — qui sera condamné à répéter le passé.

J'aurais voulu écrire ce fragment en allemand, mais je me suis rendu compte que ça me prendrait décidément trop de temps. Si quelqu'un veut faire l'effort de le traduire, qu'il ne se prive pas. Je vous donne au moins le troisième paragraphe, puisque c'est tiré du pamphlet de Marx de 1852 consacré au XVIII brumaire de Louis Napoléon Bonaparte : Hegel bemerkte irgendwo, dass alle großen weltgeschichtlichen Tatsachen und Personen sich sozusagen zweimal ereignen. Er hat vergessen, {warnt uns Marx vor,} hinzuzufügen: das eine Mal als Tragödie, das andere Mal als Farce.

↑Entry #2245 [older| permalink|newer] / ↑Entrée #2245 [précédente| permalien|suivante] ↑

↓Entry #2244 [older| permalink|newer] / ↓Entrée #2244 [précédente| permalien|suivante] ↓

(samedi)

Interstellar

(Je vais essayer de ne pas spoiler, ou en tout cas pas sur quoi que ce soit d'important.)

Je crois que j'ai toujours aimé les intrigues à rebondissements (je ne sais pas quel mot convient le mieux en français, rebondissements, révélations… l'anglais plot twist est sans doute le plus proche de ce que je veux dire) : les histoires où on découvre que le grand méchant est en fait le père du héros, que celui qu'on croyait gentil est en fait un méchant traître, que (et ce sens-là est à mon avis beaucoup plus intéressant et plus difficile à mener correctement) celui qu'on prenait pour un méchant est en fait un gentil, qu'on s'est totalement trompé sur la nature de X ou Y, que les intentions d'Untel n'étaient pas du tout ce qu'on pensait, que tel personnage est en fait tel autre déguisé, que tel personnage est en fait deux personnes différentes, que quelqu'un apparaît à un moment inattendu ou bien réapparaît, que tel personnage, tel lieu ou tel objet n'a jamais existé, ou bien le contraire, que le général que la princesse doit épouser est une femme ou au contraire que la princesse avec laquelle le héros a couché est un général, que celui qu'on croyait fou ne l'est pas, ou le contraire, que le meurtrier qu'on recherchait est en fait le détective / le narrateur / la victime elle-même, que la femme que le héros a épousé est sa mère tandis que l'homme qu'il a tué est son père, bref, ce genre de choses. Quand on aime ce genre de choses, il est difficile de ne pas apprécier les films de Christopher Nolan, et je pense que c'est beaucoup pour ça qu'il plaît — pas seulement à moi. Je l'ai découvert, je crois, quand je suis allé voir Le Prestige ; j'ai aussi beaucoup aimé Shutter Island [correction : on me fait remarquer que celui-ci n'est pas de Nolan, comme dans l'univers parallèle dont je viens, mais de Scorcese — il faut croire que c'est le plus nolanien des films de Scorcese], et un peu moins (et pour des raisons un peu différentes), Inception. Je ne prétends pas que tous ses films soient forcément bourrés de rebondissements, mais on peut révéler sans trop spoiler qu'au moins un ou deux des éléments de rebondissement que je viens de citer ont servi quelque part dans un film de Nolan.

Interstellar en a aussi sa part, même si ce n'est sans doute pas le plus important dans un film plutôt riche et qui semble hésiter entre plusieurs genres (dont l'un à part entière est sans doute le genre « hommage à 2001 »). Cela ne m'a pas empêché de l'apprécier. Je précise aussi, car c'est très important pour moi dans un film qui doit peut-être recevoir une suite, qu'il y a une véritable fin, on ne nous laisse pas en plan avec une intrigue à moitié achevée (chose que je déteste) : on voit que le film fait potentiellement partie d'un ensemble plus grand, mais il peut très bien se suffire à lui-même. (Et je reciterai cet exemple à ceux qui me prétendent parfois que c'est impossible de concilier les deux.)

Je ne révélerai pas quel est le point de vue du réalisateur sur la conquête spatiale (on sait quel est le mien), d'autant moins que je ne sais pas ce qu'il est : le film reste sans doute volontairement ambigu, et les personnages n'ont pas tous la même idée à ce sujet. Il pose néanmoins, d'ailleurs peut-être malgré lui, et en ayant l'intelligence de ne pas vraiment chercher à y répondre, une ou deux questions éthiques intéressantes, notamment sur ce que cela signifie de nous perpétuer en tant qu'espèce, ou quel but cela doit avoir (cf. l'entrée liée ci-dessus). Tout ça pour dire que la tagline mankind was born on Earth: it was never meant to die here est un peu simpliste.

Ce qui est sûr, en revanche, c'est qu'il faut bien accrocher sa suspension of disbelief, notamment en ce qui concerne la physique (ou d'autres lois de la nature, d'ailleurs). Pas que le film soit plus plein d'invraisemblances que d'autres films de SF, mais il donne l'impression de prétendre à plus de vraisemblance. J'ai eu quelque espoir en la matière en voyant que l'extérieur du trou de ver n'était pas ridicule, que certaines images de trou noir étaient inspirées d'images sérieuses (apparemment fournies avec la collaboration de Kip Thorne ; dommage qu'il ne soit pas tombé sur mes vidéos à ce sujet, j'aurais peut-être pu rencontrer M. Nolan). Mais au final, on a droit à la ration standard de bêtises, que ce soit le blabla sur la 5e dimension qui semble inévitable dès que quelqu'un évoque la courbure de l'espace-temps (mais noooooon ! pitié !) ou encore d'une planète près d'un trou noir sur laquelle il suffit de se poser pour que le temps subisse un ralentissement d'un facteur 60000 par rapport aux observateurs juste à côté (allô la Terre ?), et je ne parle même pas de planétologie, d'intelligence artificielle (soupir !), ou de simples ordres de grandeurs sur la taille des choses dans l'univers ou même de vraisemblance interne vis-à-vis de cette physique farfelue (par exemple, si le temps s'écoule 60000 plus lentement sur une planète, une sonde arrivée dessus va sembler envoyer ses bips 60000 fois plus lentement, je crois que tout le monde peut deviner ça). En revanche, j'ai bien envie de voir des images fixes des tableaux noirs remplis d'équations qu'on aperçoit dans quelques scènes du film, parce qu'il y a l'air d'avoir des choses rigolotes dessus (j'ai repéré quelques équations standard de la relativité générale transformée avec des lettres cyrilliques comme indices, je me demande s'il faut y voir une private joke).

↑Entry #2244 [older| permalink|newer] / ↑Entrée #2244 [précédente| permalien|suivante] ↑

↓Entry #2243 [older| permalink|newer] / ↓Entrée #2243 [précédente| permalien|suivante] ↓

(vendredi)

La sécurité de l'ambassade du Canada

Je suis allé hier déposer une demande de renouvellement de mon passeport canadien et, sans doute pour une raison qui n'est pas sans rapport avec un événement récent, le niveau de sécurité était vraiment impressionnant :

  • j'ai dû montrer une pièce d'identité avant même d'avoir le droit de me présenter à la sécurité ;
  • là, on m'a fait éteindre mon téléphone mobile et on a passé aux rayons X tout ce que je portais, puis je suis passé sous un portique détecteur de métaux ;
  • le réglage de celui-ci était si sensible que, forcément, ça a bippé, et on a donc passé chaque centimètre carré de mes vêtements à un détecteur à main, qui était réglé aussi sensible, si bien que même les rivets en métal de mon jean le faisaient bipper (et ils ont été vérifiés un par un), sans parler évidemment de ma montre et de ma boucle de ceinture ;
  • mon téléphone et mes clés, qui avaient été passés au rayons X, ont quand même été gardés en consigne (j'ai quand même eu le droit de reprendre mon porte-monnaie à la sortie des rayons X) ;
  • j'ai dû présenter mon (ancien) passeport canadien pour avoir le droit d'accéder aux services consulaires, histoire de vérifier que je n'étais pas un intrus,
  • ce qui m'a permis de voir une dame derrière une vitre apparemment blindée, à qui j'ai communiqué mes documents à travers un tiroir coulissant.

Bon, je ne me plains pas, il n'y avait en gros personne d'autre que moi donc je n'ai pas spécialement attendu, et tout le monde était très poli. Mais j'avais un peu l'impression de rentrer dans Fort Knox.

Le passeport que j'aurai est bien sûr aussi (comme mon passeport français, en fait) plein de chouettes mesures de sécurité qui garantiront mon impossibilité absolue d'avoir une vie privée.

↑Entry #2243 [older| permalink|newer] / ↑Entrée #2243 [précédente| permalien|suivante] ↑

↓Entry #2242 [older| permalink|newer] / ↓Entrée #2242 [précédente| permalien|suivante] ↓

(lundi)

Comment faire de la géographie algorithmique ?

Régulièrement[#], je me pose des questions du style :

  1. Quel est le plus long arc de grand cercle à la surface de la Terre qui soit entièrement dans les terres émergées (resp., qui soit entièrement dans la mer) ? Autrement dit, quelle est la plus longue distance qu'on puisse parcourir sur la terre ferme (resp. dans la mer) en allant tout droit ?
  2. Quel est le grand cercle à la surface de la Terre dont la proportion de terre émergée soit la plus grande possible (resp. la plus faible possible) ? Autrement dit, par où doit-on faire le tour de la Terre si on veut rencontrer le plus possible de terre (resp. le plus possible de mer) ?
  3. Quel est l'hémisphère (découpé par un grand cercle quelconque) de la surface de la Terre qui contienne la plus grande proportion de terre émergée (resp. la plus faible possible — ce sera bien sûr simplement l'autre côté du même grand cercle) ? Autrement dit, si on veut faire le tour de la Terre de façon à mettre le plus de terre d'un côté et le plus de mer de l'autre, comment doit-on s'y prendre ?

(Toutes ces questions assimilent implicitement la Terre à une sphère, qu'on aurait divisée, selon un contour bien défini, en une partie « terres émergées » et une partie « mers ». On pourrait bien sûr raffiner, soit en considérant la terre comme un ellipsoïde oblate[#2].)

On n'aura pas de mal à trouver d'autres questions dans le même genre (et on fera bien attention à distinguer des questions qui peuvent se ressembler subtilement : par exemple j'ai parfois eu du mal à expliquer à des non-mathématiciens la différence entre les deux premières questions que je pose ci-dessus, qui sont pourtant bien distinctes). J'ai envie d'appeler ça collectivement la géographie algorithmique, au croisement de la géométrie algorithmique et de la géographie physique (quoique ça pourrait être de la géographie humaine, aussi : je m'étais demandé ce que vaudrait l'entropie de distribution de la densité de population humaine à la surface de la Terre, ça pourrait aussi s'appeler une question de géographie algorithmique).

Certaines de ces questions trouvent une réponse en ligne. Par exemple la question 3 ci-dessus a sa réponse dans cet article Wikipédia, qui prétend que l'hémisphère de la Terre ayant le plus de terres émergées est celui centré sur Nantes (qui pourrait donc, en un certain sens[#3], se targuer d'être le centre des terres émergées), en faisant lui-même référence à un vieil article du Journal of Geography (auquel je n'ai pas accès, ce qui est d'ailleurs franchement honteux de la part de l'éditeur pour un texte aussi vieux [ajout : on m'a communiqué une copie de l'article, mais en fait il ne dit rien sur la manière dont le calcul a été mené : Geographers have made careful determinations to ascertain which hemisphere contains a larger percentage of land area than any other. It has been found to have its center in western France, near Nantes.]). Et la réponse à la question 1 pour ce qui est de la plus longue distance dans la mer prétend être apportée par cette vidéo YouTube, qui trace une ligne droite entre un point de la côte du Pakistan (du côté de Karachi) et un point de la péninsule du Kamčatka en Russie, en passant par le canal du Mozambique et le passage de Drake, ce qui fait plus de 30000km de mer en ligne droite, c'est indiscutablement impressionnant (et un petit peu difficile à visualiser). On trouve aussi des gens qui prétendent que la plus longue distance sur la Terre ferme relie le Libéria (vers Greenville) à la Chine (du coté de Taizhou), encore que ça a l'air de traverser la mer Morte, donc il reste à décider si celle-ci est un lac ou une vraie mer.

Mais la méta-question que je me pose, c'est : comment les gens qui prétendent avoir la réponse à ce genre de questions ont-ils obtenu la réponse en question ? Et comme je suis mathématicien, forcément, je me demande : ont-ils une preuve d'optimalité (au moins pour une certaine approximation bien définie de la forme de la Terre et de la limite des continents) ?, ou ont-ils simplement essayé de placer plein de grands cercles jusqu'à se dire oh, c'est sûrement ça le mieux qu'on puisse faire ? À vrai dire, je soupçonne fortement le second.

Et j'avoue que si je devais essayer de répondre exactement — et en tout cas plus scientifiquement qu'en essayant plein de possibilités à la main — à une de ces questions, je serais bien embarrassé, même si je sais vaguement, ou du moins j'ai su, me servir de PostGIS (et l'ai utilisé pour des problèmes de ce genre). Par exemple, s'agissant de la question 2, même en admettant que j'arrive, pour un grand cercle donné à calculer la proportion de terres émergées rencontrée sur sa circonférence (ce qui, en principe, si on se donne le contour des continents sous forme d'un énorme polygone, consiste simplement à calculer tous les points d'intersection et à sommer les longueurs qui vont bien), encore faut-il arriver à faire la maximisation correctement : peut-être commencer par placer un million de grands cercles à peu près bien répartis sur la Terre, calculer la proportion de terres émergées de chacun d'eux, puis faire un recuit simulé ou (si on arrive à calculer le gradient) une descente de gradient, en espérant que le million de grands cercles de départ était suffisant pour éviter un faux extremum. Au moins l'espace de recherche n'est que de dimension 2 (pour ce qui est des questions 2 et 3 que je pose ci-dessus, il y a « autant » de grands cercles sur une sphère que de paires de points antipodaux sur la sphère, grâce à la polarité, et de même autant d'hémisphères que de points sur lesquels ils peuvent être centrés ; et pour la question 1, on cherche un couple de points évidemment situés sur les côtes).

Mais si je devais programmer la recherche d'un extremum garanti et démontrablement exact une fois fixé un polygone sur la sphère dont on décrète arbitrairement que c'est ça la forme des continents (par exemple VMAP0), je serais encore plus embarrassé. Je suppose que je ferais quelque chose comme ceci, s'agissant par exemple de la question 2 : prendre un point de départ arbitraire (disons le pôle nord) et son grand cercle polaire (qui serait donc l'équateur), regarder l'intersection de ce dernier avec le polygone des côtes, en déduire à la fois la proportion de terres pour ce grand cercle, mais aussi la plus petite cellule polygonale autour de mon point de départ sur laquelle le grand cercle polaire coupe précisément les mêmes segments du polygone des côtes, cellule sur laquelle j'ai donc une forme simple de la fonction de proportion de terre, puis calculer les cellules adjacentes de la même façon, jusqu'à avoir recouvert la terre par des cellules sur chacune desquelles le grand cercle polaire coupe un certain ensemble de segments du polygone des côtes. Puis, dans chaque cellule, faire l'optimisation exacte, ce qui doit être facile vu que la cellule est polygonale et la fonction à optimiser a une forme simple, et enfin, rassembler l'optimum global, qui sera alors démontrablement le bon (pour peu qu'on a mené les calculs en précision garantie, en encadrant systématiquement les bornes d'erreur, etc.). Ça semble un projet assez monstrueux, et je doute sérieusement que quelqu'un ait fait ça.

À encore plus haut niveau, je peux dire que le problème est décidable en raison du théorème de Tarski sur la décidabilité de la géométrie algébrique réelle (plus un petit argument facile pour expliquer que maximiser une somme de sinus, bien que ce ne soient pas des fonctions algébriques, peut néanmoins se traduire comme une maximisation de fonctions algébriques). Et là ce sera vraiment une réponse de matheux, parce qu'essayer d'appliquer ça pour résoudre une des questions ci-dessus est beaucoup plus désespéré qu'essayer de vider les océans à la petite cuiller.

Je suis donc assez insatisfait par les réponses qu'on peut trouver en ligne à ces problèmes de géographie algorithmique, et je suis sûr qu'il faudrait monter une équipe de recherche à gros budget pour travailler là-dessus (et produire plein de thèses, et d'articles à la con, et de congrès internationaux, etc.).

Mise à jour () : Longest Straight Line Paths on Water or Land on the Earth de Rohan Chabukswar et Kushal Mukherjee est apparu récemment sur l'arXiv.

[#] Bon, en vérité, j'écris cette entrée pour me changer les idées, parce qu'il m'est encore arrivée la même chose dont je me plaignais récemment : comme mon entrée sur les espaces homogènes et isotropes partait dans tous les sens (alors qu'elle-même était destinée à être une entrée courte puisque je n'arrivais pas à en écrire une sur le carré magique de Freudenthal-Tits, elle-même commencée parce que celle sur les octonions devenait interminable), j'ai commencé à en écrire une sur le cas particulier du plan projectif complexe, en me disant que ça au moins c'était un sujet trop étroit pour que ça devienne si long que je n'arrive pas à finir l'entrée, et c'est pourtant de nouveau ce qui s'est produit. (Eh oui, je ne m'étais pas rendu compte de ça, mais comprendre comment sont foutus les plans projectifs réels dans le plan projectif complexe, ce n'est pas si trivial.) [Mise à jour : elle a été publiée ici.]

[#2] La terminologie pour désigner les ellipsoïdes de révolution (ceux dont deux axes ont la même longueur) est un peu confuse : il y a deux cas, selon que les deux axes égaux sont plus longs que le troisième (i.e., qu'on a fait tourner une ellipse autour de son axe mineur, ce qui donne une forme aplatie comme la Terre) ou plus courts (i.e., qu'on a fait tourner une ellipse autour de son axe majeur, ce qui donne une forme allongée comme un ballon de rugby). On trouve différentes paires de termes pour distinguer ces deux cas : oblate/prolate (c'est le plus fréquent en anglais, et un peu rare en français), oblate/oblong (où on fait varier le suffixe plutôt que le préfixe), ou encore aplati/allongé (peut-être plus clair, mais ça ne fait pas très scientifique) ou son équivalent anglais flattened/elongated. Je trouve toujours pénible quand des langues ont des terminologies gratuitement différentes : donc je décrète autoritairement que ces différentes paires de termes pourront être utilisées indifféremment (et on fera bien attention à distinguer prolate et oblong, qui sont synonymes, de oblate, qui est leur antonyme ; on évitera en revanche le mot prolong, dont on ne sait pas bien lequel des deux cas il devrait désigner).

[#3] Mais bon, le barycentre des terres émergées, c'est encore un autre problème dans le même genre : là, une des difficultés consiste à définir ce qu'est un barycentre en géométrie sphérique/elliptique (ou dualement, hyperbolique), et il y a plusieurs concepts concurrents, plus ou moins naturels, dans ce sens : à ce sujet, voir la section 7.4 (the Center of Mass Problem on Two-Point Homogeneous Spaces) du livre d'Alexey Shchepetilov, Calculus and Mechanics on Two-Point Homogeneous Spaces, (Springer / ISBN 978-3-540-35384-3), et, pour un concept parmi d'autres (mais peut-être le plus naturel), le joli article de Galperin, A concept of the mass center of a system of material points in the constant curvature spaces, Comm. Math. Phys. 154 (1993) 63–84, en Open Access ici (spoiler : le concept en question consiste, en pratique, pour la sphère, à faire le barycentre euclidien en trois dimensions et à reprojeter vers la sphère depuis son centre).

↑Entry #2242 [older| permalink|newer] / ↑Entrée #2242 [précédente| permalien|suivante] ↑

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


Entries by month / Entrées par mois:

2024 Jan 2024 Feb 2024 Mar 2024 Apr 2024
2023 Jan 2023 Feb 2023 Mar 2023 Apr 2023 May 2023 Jun 2023 Jul 2023 Aug 2023 Sep 2023 Oct 2023 Nov 2023 Dec 2023
2022 Jan 2022 Feb 2022 Mar 2022 Apr 2022 May 2022 Jun 2022 Jul 2022 Aug 2022 Sep 2022 Oct 2022 Nov 2022 Dec 2022
2021 Jan 2021 Feb 2021 Mar 2021 Apr 2021 May 2021 Jun 2021 Jul 2021 Aug 2021 Sep 2021 Oct 2021 Nov 2021 Dec 2021
2020 Jan 2020 Feb 2020 Mar 2020 Apr 2020 May 2020 Jun 2020 Jul 2020 Aug 2020 Sep 2020 Oct 2020 Nov 2020 Dec 2020
2019 Jan 2019 Feb 2019 Mar 2019 Apr 2019 May 2019 Jun 2019 Jul 2019 Aug 2019 Sep 2019 Oct 2019 Nov 2019 Dec 2019
2018 Jan 2018 Feb 2018 Mar 2018 Apr 2018 May 2018 Jun 2018 Jul 2018 Aug 2018 Sep 2018 Oct 2018 Nov 2018 Dec 2018
2017 Jan 2017 Feb 2017 Mar 2017 Apr 2017 May 2017 Jun 2017 Jul 2017 Aug 2017 Sep 2017 Oct 2017 Nov 2017 Dec 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

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]