David Madore's WebLog

2009-05-30 (samedi)

Fragment littéraire gratuit #119 (le songe de Labrunie)

La nuit est avancée : l'Auteur est las. La voilà qui approche, cette heure où l'inspiration va frapper, impitoyable ; où les mots s'arracheront de sa plume en lui volant son âme. Les livres attendent leur tour : le moment où la synesthésie passagère de l'écrivain leur prêtera une voix, une odeur de sang et de sueur, et la faculté d'invoquer les spectres. Sur une feuille accrochée au mur, un sceau de Salomon, au centre duquel figure le mot liminaire du dernier évangile selon Jean : λόγος. Que signifie ce mot ? L'esprit ? La force ? Non, il est écrit : au commencement était l'action. Au moment où l'Auteur murmure cela, le premier fantôme paraît — c'est le caliphe Hakem, qui emprunte les traits de de Quincey et le costume des Turcs ; il fume un houka d'où se dégage une fumée verte, rouge, jaune, bleue et blanche. Les volutes perdent leur couleur et se transforment en une mer de nuages, noyant le fumeur. Sur une montagne dominant ce brouillard, l'Auteur voit soudain la figure de Lord Byron, tenant ouvert le Paradis perdu de Milton ; apercevant l'Auteur, il lit à haute voix : Il vaut mieux régner en Enfer que servir au Paradis. Ici, au moins, nous serons libres ! Lorsqu'il prononce ces mots en disparaissant, les pages du livre s'envolent, et sept d'entre elles prennent des formes d'hommes : l'Auteur sait aussitôt qu'ils sont Homère, Virgile, Ossian, Wolfram von Eschenbach, Dante, le Tasse et Edmund Spenser. Un chariot et des chevaux de feu apparaissent et les emportent dans une tempête. Le visage d'Albrecht Dürer, riant, gigantesque, se matérialise un instant. Puis une femme à l'apparence maladive : il s'agit de Mignon, qui chante doucement le pays où les citronniers fleurissent. Enfin, l'Auteur voit son propre reflet devant lui, mais il sait qu'il s'agit là de Prospero, qu'il entend faire ses adieux à la magie et implorer l'indulgence du spectateur.

Les visions se dissipent. L'Auteur peut enfin lire les vers que sa main a tracés ; il a écrit :

Je suis le ténébreux, — le veuf, — l'inconsolé…

Je dois présenter mes excuses à ceux qui trouveront que c'est inutilement savant ; mais comme il s'agit d'une sorte de glose sur un poème (et un de mes poèmes préférés, d'ailleurs) qui est lui-même passablement hermétique et dont l'auteur n'avait plus toute sa lucidité, il n'est pas surprenant que quand j'essaie d'imaginer quelles visions ont pu en créer l'inspiration, ce soit un peu tortueux. (Je dis bien imaginer car je ne prétends même pas être vraisemblable : j'ai très bien pu commettre des anachronismes[#] ridicules.) Même si c'est parfaitement déplacé de commenter ses propres textes, j'essaierai peut-être d'expliquer plus tard quelques uns des choix que j'ai faits. En tout cas, il m'arrive de ressentir l'inspiration un peu comme ce que je viens de décrire (mais de façon moins graphique, évidemment : je ne prends pas de drogues), c'est-à-dire comme une cohorte d'auteurs, de personnages ou d'idées qui se pressent dans mon esprit pour me persuader d'écrire ceci ou cela.

Mise à jour : une tentative d'explication est ici.

[#] J'ai hésité — mais finalement renoncé — à en commettre un exprès : car je regrette profondément que Nerval soit mort juste un chouïa trop tôt pour avoir pu connaître les Rubáiyát d'Omar Khayyám telles que traduits — ou faudrait-il plutôt dire, composés — par Edward FitzGerald. Je suis sûr qu'il les aurait immensément aimés.

Commentaires

2009-05-22 (vendredi)

Comment un mathématicien ouvre une infinité de boîtes

Les remarques faites en commentaire sur mon entrée récente me semblent mériter quelques précisions d'ordre mathématique, auxquelles je vais consacrer cette entrée. Les deux parties suivantes, et même leurs différentes sous-parties, sont indépendantes (et au moins formellement indépendantes de l'entrée précédente). Vue la longueur de ce post, ce n'est pas une mauvaise chose, d'ailleurs.

Sur la calculabilité, et l'utilisation de l'axiome du choix

Plutôt que discuter sur le problème d'origine, je vais utiliser celui-ci, qui est légèrement plus simple :

Le cruel Docteur No a capturé une infinité dénombrable de mathématiciens pour les soumettre à une épreuve pernicieuse. Il a créé des chapeaux de plusieurs couleurs différentes. Après avoir permis aux mathématiciens de se concerter, il va les soumettre à son épreuve dont il leur communique les termes : il empêchera toute communication entre eux, puis rangera les mathématiciens en file indienne dans un certain ordre (indexé par les entiers naturels), et mettra sur la tête de chacun un chapeau d'une certaine couleur (les couleurs possibles sont connues à l'avance), de sorte que chaque mathématicien puisse voir les couleurs des chapeaux de tous ceux situés devant lui (une infinité), mais pas de ceux (en nombre fini) situés derrière lui ni du sien propre. Chaque mathématicien devra noter sur un papier (et toujours sans aucune communication avec les autres) ce qu'il croit être la couleur de son chapeau. Le Docteur No tolérera un nombre fini d'erreurs, mais pas plus : si une infinité de mathématiciens s'est trompée en annonçant la couleur de leur chapeau, tous seront tués avec des tortures particulièrement raffinées — à l'inverse, si tous sauf un nombre fini avaient raison, ils seront tous libérés. Comment les mathématiciens se tirent-ils de ce mauvais pas (de façon certaine) ?

De façon mathématique, on demande de construire une fonction φ:X^ℕ→X^ℕ (où X est l'ensemble des couleurs et ℕ l'ensemble des naturels) qui à une suite de couleurs de chapeau associe la suite des réponses des mathématiciens, telle que si u et v ne diffèrent que sur les n premiers termes alors φ(u) et φ(v) ne diffèrent que sur les n−1 premiers termes (car, pour tout n, seuls les n−1 premiers mathématiciens peuvent pas voir certains des n premiers chapeaux), et telle que pour tout u les suites u et φ(u) coïncident sauf en un nombre fini de termes (seuls un nombre fini des mathématiciens a le droit d'avoir tort). Dispensons-nous des généralités vaseuses et mettons que X={0,1} (il n'y a que deux couleurs de chapeau : noir et blanc).

Peut-on avoir une stratégie calculable ?

Supposons un instant que nos mathématiciens soient, en fait, des informaticiens : ils ne peuvent calculer que les fonctions calculables effectivement par une machine de Turing ; plus exactement, il doit exister une machine de Turing T qui, quand on l'exécute en lui fournissant un entier naturel n et un oracle u (dont elle peut interroger librement les valeurs mais seulement celles qui sont au moins égales à n+1) doit terminer et renvoyer φ(u)(n). (On souligne qu'une machine de Turing ne peut évidemment, au cours de son exécution, interroger qu'un nombre fini de valeurs de l'oracle.) Or, dans ces conditions, les informaticiens ne peuvent pas être certains d'être libérés : en effet, si le Docteur No a connaissance[#] de la machine de Turing T qui sera utilisée par les informaticiens, il peut lancer l'exécution de T sur le nombre n₀=0 en fixant arbitrairement la valeur de u(k) lorsque la machine T interroge l'oracle en k (forcément différent de 0 par hypothèse), puis choisir une couleur de chapeau u(0) pour l'informaticien 0 qui soit différente de la valeur retournée par T pour ce calcul (qui se fait en temps fini puisque T est censée toujours terminer) ; puis il lance l'exécution de T sur le premier nombre n₁ pour lequel la valeur de u n'a pas encore été fixée, et de nouveau, à chaque fois que la machine T interroge l'oracle sur une valeur non encore déterminée de u, elle est fixée arbitrairement, et à la fin u(n₁) est choisi différent du nombre renvoyé par T. Et ainsi de suite : alors les informaticiens n₀, n₁, n₂, etc., se tromperont tous, donc le Docteur No aura réussi son plan diabolique.

On voit même, d'ailleurs, que dans l'opération, le Docteur No peut lui-même être un informaticien, car j'ai présenté un programme effectif qui calcule la fonction u de couleur à donner aux chapeaux (pour mettre en défaut des informaticiens qui utiliseraient une machine de Turing T connue). Par ailleurs, je n'ai essentiellement rien utilisé sur les machines de Turing, donc ceci vaut encore si on les remplace par des machines plus puissantes, par exemple si les informaticiens et le Docteur No disposent d'un oracle de l'arrêt des machines de Turing (elles-mêmes sans oracle), ou de même pour tout degré de Turing : si on demande aux fonctions φ et u d'être arithmétiques (= définissables dans l'arithmétique de Peano, c'est-à-dire exactement appartenant au degré de Turing 0^(ω)), on a donc la même conclusion (à ce stade-là, ce ne sont plus vraiment des informaticiens, ce sont plutôt des mathématiciens finitistes).

[#] Là, normalement, quelqu'un va protester que je n'ai pas mis dans mes hypothèses que le Docteur No connaît la stratégie des informaticiens ! Mais je cherche à prouver que les informaticiens n'ont pas de stratégie leur permettant d'être libérés à coup sûr : or s'ils en avaient une, utilisant la machine de Turing T, elle devrait fonctionner même si le Docteur No connaissait cette machine T — il peut, après tout, très bien avoir vu juste par hasard.

En revanche, si les informaticiens disposent d'un oracle de l'arrêt des machines de Turing et que le Docteur No n'en dispose pas (ou plus généralement si les mathématiciens ont un saut de Turing d'avance sur le Docteur No), alors les informaticiens ont de nouveau l'avantage. En effet, l'informaticien numéro i va considérer les i premières machines de Turing et, pour chaque couple de deux (T,T′) parmi elles, en utilisant l'oracle dont il dispose, déterminer s'il existe un j>i telles qu'elles calculent une valeur différente en j (ou au contraire si elles calculent systématiquement la même valeur en tout j>i) ; il fixe alors N>i suffisant pour garantir que si deux machines (T,T′) parmi les i premières calculent toujours les mêmes valeurs pour les j entre i+1 et N, alors elles calculent les mêmes valeurs pour tout j>i. En observant la couleur des chapeaux numérotés par j entre i+1 et N, il élimine les machines de Turing qui ne calculent pas des valeurs conformes à ces observations : si T est la première qui s'y conforme, alors il prédit pour son propre chapeau la couleur renvoyée par T (appliquée au nombre i). Dans ces conditions, si le Docteur No calcule les couleurs des chapeaux en utilisant une machine de Turing, et si T_k (la machine de Turing numérotée k) est la première qui calcule les couleurs des chapeaux ainsi choisis à partir d'un certain rang fini (disons n₀), alors les informaticiens portant un numéro supérieur au max de k et de n₀ vont tous répondre juste puisqu'ils utiliseront justement cette machine T_k pour déterminer la couleur de leur chapeau.

Doit-on utiliser l'axiome du choix ?

Maintenant que les informaticiens qui n'ont pas d'oracle dans leur poche se sont fait impitoyablement trucider par le Docteur No, reprenons des mathématiciens.

Une stratégie φ:{0,1}^ℕ→{0,1}^ℕ des mathématiciens leur permettant de passer l'épreuve du cruel Docteur No est, on l'a dit, une fonction φ telle que pour u une suite quelconque φ(u) et u coïncident à partir d'un certain rang, et que si u et v coïncident à partir d'un rang n alors φ(u) et φ(v) coïncident à partir du rang n−1. Maintenant, imaginons qu'on à partir d'une suite u on itère la fonction φ (ou, si on veut, chaque mathématicien remplace son chapeau par celui qu'il croit avoir en fonction des mathématiciens devant lui — mais seul un nombre fini d'entre eux change de chapeau en ce faisant puisque la stratégie était bonne — et on itère le processus) : on voit facilement qu'on tombe ainsi en un nombre fini d'étapes sur un point fixe, que je vais appeler φ_∞(u), lequel coïncide toujours avec u à partir d'un certain rang, et que si u et v coïncident à partir d'un certain rang, alors φ_∞(u) et φ_∞(v) sont exactement égales. Or en fait, la fonction φ_∞ convient tout aussi bien que la fonction φ (elle vérifie les propriétés supposées de cette dernière), donc rechercher une stratégie pour les mathématiciens revient exactement à chercher une telle fonction φ_∞ : il s'agit d'une section (un choix de représentants) pour la relation d'équivalence « coïncider à partir d'un certain rang », appelons-la ∼, sur les suites.

Visiblement le choix d'un élément dans chaque classe d'équivalence pour ∼ fait appel à l'axiome du choix. Évidemment, ça ne prouve pas qu'on ne puisse pas faire autrement : je vais donc esquisser une démonstration du fait qu'on ne peut pas démontrer l'existence de cette section dans ZF (s'il est consistant…) en l'absence de l'axiome du choix. Autrement dit, je veux montrer qu'il existe un modèle N de ZF dans lequel la surjection canonique 2^ω↠2^ω/∼ n'admet pas de section. Comme c'est un peu fastidieux (et plus fastidieux encore vu qu'il s'agit d'écrire ça en HTML, qui sera sans doute illisible pour tout le monde faute de polices Unicode assez complètes), et vu qu'environ 0.42 lecteurs vont lire le zblurgh qui suit (ceux qui peuvent le comprendre peuvent probablement l'inventer eux-mêmes), je vais être un peu elliptique. Mais il y a à la fin des choses que je ne sais pas démontrer concernant l'axiome du choix dépendant : voir plus bas.

On appelle (dans un modèle M de ZFC) P l'ensemble partiellement ordonné formé des fonctions définies sur un sous-ensemble fini de ω₁×ω et à valeurs dans 2={0,1}, partiellement ordonné par l'inclusion réciproque (q≤p, i.e., q est plus fort que p, lorsque q prolonge p), et on appelle B l'algèbre de Boole complété de P, c'est-à-dire l'algèbre de Boole (complète) des ouverts réguliers sur l'espace topologique 2^ω₁×ω (muni de la topologie produit). Soit D un ultrafiltre B-générique (ou son nom canonique dans le modèle M^B à valeurs dans B) : autrement dit, M[D] est le modèle qui ajoute ℵ₁ réels génériques que je vais appeler x_α (je vais expliquer plus loin pourquoi j'en utilise ℵ₁ et pas simplement ℵ₀). Pour chaque α∈ω₁, soit x_α:ω→{0,1} la réunion des p(α,·) pour p dans D ; soit c_α la classe de x_α modulo ∼.

Soit G ≅ ∏_α∈ω1 ⨁_i∈ω (ℤ/2ℤ) le groupe (commutatif) des automorphismes σ_X de P (ou de B) où X⊆ω₁×ω parcourt les ensembles tels que chaque X∩({α}×ω) (pour α∈ω₁) soit fini, où σ_X agit sur p∈P en échangeant (entre 0 et 1) la valeur de p sur les couples (α,i) appartenant à X (et sur lesquels p est défini) : concrètement, G est donc constitué des automorphismes de P qui changent la valeur des p∈P(α,i) en un nombre fini de i pour chaque α. Soit F le filtre (normal) de sous-groupes de G engendré par les Fix(E) avec E⊆ω₁ dénombrable, où par Fix(E) on désigne l'ensemble des σ_X pour lesquels X⊆E×ω. Soit N le modèle symétrique associé à la situation, c'est-à-dire le modèle formé des éléments de M[D] qui ont un nom hériditairement symétrique (i.e., fixé par un Fix(E)). Manifestement, chaque x_α est dans N, ainsi que chaque c_α : mais même la fonction α↦c_α elle-même est dans N (puisqu'elle — ou plutôt son nom évident — est fixée par tout σ_X). En revanche, il est assez clair, et on va le justifier dans un instant, que la fonction α↦x_α, elle, n'est pas dans N (c'est une fonction de choix pour α↦c_α). Ce N est un modèle de ZF ; on veut prouver que la fonction α↦c_α n'a pas de fonction de choix (et en particulier 2^ω↠2^ω/∼ n'a pas de section).

Supposons donc pour cela que h:ω₁→2^ω soit une fonction de choix pour α↦c_α (ici comme ailleurs, par ω₁ on entend ω₁^M, i.e., le ω₁ du modèle initial — il se trouve qu'il est égal à ω₁^M[D], et donc ω₁^N, parce que P vérifie la condition de chaîne dénombrable, mais il me semble qu'on n'en aura pas besoin). On appelle aussi abusivement h un nom symétrique pour cette fonction ; mettons qu'il soit fixé par Fix(E) avec E dénombrable. Soit p dans D qui force (⊩) h à être une fonction ω₁→2^ω telle que h(α)∈c_α pour tout α∈ω₁. Soit γ supérieur à chaque élément de E. Soit q≤p et n₀∈ω tel que q ⊩ si i≥n alors h(γ,i)=x_γ(i). Soit k≥n et tel que k soit supérieur à i pour tout (γ,i) dans le domaine de q. Soit π=σ_{(γ,k)}. Alors π(q) et q sont égaux : alors (comme π(h)=h tandis que q ⊩ π(x_γ)(k)=1−x_γ(k)), on a q ⊩ h(γ,k)=1−h(γ,k), une contradiction.

Ce qui précède montre qu'en l'absence de l'axiome du choix, on ne peut pas prouver que 2^ℕ↠2^ℕ/∼ a une section. Mais ce qui me chagrine fort, c'est que je n'arrive pas à tordre le cou à l'axiome du choix dépendant (abrégé en DC ci-après) : j'étais parti pour construire un modèle qui vérifie l'axiome du choix dépendant (c'est pour cette raison que j'ai rédigé avec ω₁ et pas ω : comme l'axiome du choix dépendant implique l'axiome du choix dénombrable, on ne va pas arriver à avoir DC et à éviter d'avoir une fonction de choix pour les classes d'un nombre dénombrable de suites génériques), et j'ai lamentablement échoué. Dans le modèle que je viens de décrire, je ne sais pas si DC est vérifié, car bien que le filtre F permette de fixer un ensemble E dénombrable de α∈ω₁, pour construire une suite de choix dépendants à partir d'une relation, j'aurais besoin de borner inférieurement une suite de conditions de forcing, et ce n'est visiblement pas possible ; ou alors je remplace P par l'ensemble, plus fin, des fonctions partielles à domaine au plus dénombrable dans ω₁×ω (toujours à valeurs dans 2, évidemment), le reste étant inchangé : dans ce cas il est facile de voir que DC est vérifié dans le modèle symétrique, mais je ne sais plus montrer que α↦c_α n'a pas de fonction de choix, car la phrase tel que k soit supérieur à i pour tout (γ,i) dans le domaine de q dans la démonstration ci-dessus n'est plus juste (en gros, le problème est que les réels x_α sont beaucoup moins génériques avec cette condition de forcing plus fine — d'ailleurs, un nombre dénombrable d'entre eux peut très bien être dans M — du coup, on ne peut rien conclure avec un seul x_α, et je n'arrive pas à en exploiter une infinité non dénombrable à la fois). Pourtant, je reste complètement persuadé que DC ne suffit pas à démontrer l'existence d'une section ; mais j'ai passé deux jours à m'y arracher les cheveux et à essayer toutes sortes de variantes sur mes conditions de forcing, en vain, alors je dois être vraiment mauvais sur ce coup, et je vais demander de l'aide à des gens plus savants que moi. Si par hasard un lecteur sait comment faire, qu'il m'explique.

Sur la façon d'ouvrir des boîtes

Un commentateur m'a fait remarquer, à juste titre, que si on a une infinité de boîtes à ouvrir pour en observer le contenu, une phrase comme [le mathématicien] pourra ouvrir les boîtes qu'il souhaite pour en examiner le contenu, y compris une infinité d'entre elles (en fonction éventuellement des nombres lus dans les boîtes déjà ouvertes) n'est pas terriblement claire. Comment formaliser, au juste, ce qui est autorisé ?

Par exemple, si j'ai une infinité dénombrable de boîtes indicées par les entiers naturels, ai-je le droit de les ouvrir « en commençant par la fin » ? C'est-à-dire, par exemple, de décréter qu'au temps t (un nombre réel) j'ai ouvert les boîtes numérotées par tous les naturels i tels que t≥1/i (donc j'ouvre la boîte 1 au bout de 1 seconde, la boîte 2 au bout de 1/2 seconde, la boîte 3 au bout de 1/3 de seconde, etc.) ? Après tout, on admet qu'il faut bien pouvoir ouvrir une infinité de boîtes en un temps fini, donc pourquoi pas de façon non bien ordonnée ? Pire encore : peut-on faire des choix, dans ce cas, en fonction des boîtes précédemment ouvertes ?

Posons le problème de façon encore plus vicieuse : imaginons que mon défi soit le suivant : j'ai une infinité dénombrable de boîtes (indicées par les entiers naturels), contenant chacune un nombre réel, on m'assure que la suite ainsi formée tend vers zéro, et mon but est d'ouvrir une infinité de boîtes ne contenant que des réels entre −1 et 1 (une telle infinité de boîtes existe forcément puisque la suite tend vers 0). Ai-je le droit de dire : j'ouvre les boîtes en partant de la fin (comme je viens de le dire : la boîte i serait ouverte après un temps 1/i), et à un moment où je constate avoir ouvert une infinité de boîtes contenant chacune des nombres entre −1 et 1, je m'arrête ? En apparence, j'ai respecté ma règle de ne tenir compte que des boîtes déjà ouvertes. Pourtant, on a fermement l'impression que c'est de la triche : une façon de s'en convaincre est que si je change la suite en modifiant le contenu de la dernière boîte que j'aie ouverte (celle numérotée par le plus petit indice) pour y mettre le nombre 42, ma règle ferait que magiquement je ne l'ouvrirais pas, mais si les deux suites ne diffèrent que par ce nombre, on voit mal comment je peux savoir que je ne dois pas l'ouvrir vu que, justement, je ne l'ouvre pas… Avec de tels super-pouvoirs, les mathématiciens de l'énigme de mon entrée précédente arrivent à avoir tous raison, pas seulement 99 sur 100.

La moindre des choses qu'on veut demander, donc, c'est que si on change le contenu d'une boîte que le mathématicien n'a pas ouverte, alors cela ne change rien aux opérations qu'il fait. Formellement, je définirai un schéma global d'ouverture comme une fonction h définie sur X^ℕ (où X est l'ensemble des contenus possibles d'une boîte, peu importe ce que c'est) et qui à toute suite u dans cet ensemble associe un ensemble h_O(u) de boîtes ouvertes ainsi que d'autres choses (par exemple une prédiction qui serait faite par le mathématicien sur une boîte non ouverte) et qui vérifie la propriété que si deux suites u et v coïncident sur l'ensemble h_O(u), alors h(u)=h(v) (c'est-à-dire au moins que h_O(u)=h_O(v), et aussi que les autres choses associées à h coïncident).

On peut être sceptique quant au fait que la seule donnée de l'ensemble des boîtes finalement ouvertes suffise à certifier qu'il n'y ait pas de la poussière sous le tapis. Une définition a priori plus stricte serait la suivante, qui introduit l'ordre dans lequel on ouvre les boîtes : un schéma de déroulement d'ouvertures est une fonction S:X^ℕ→H×(…), où les points de suspension désignent d'autres données comme avant, et H est l'ensemble des parties de 𝒫(ℕ) (ensemble des parties de ℕ) totalement ordonnées par l'inclusion (moralement, S définit non seulement quelles boîtes on ouvre, mais aussi l'ordre dans lequel on les ouvre) et complètes (c'est-à-dire ayant un plus petit élément, un plus grand élément, et possédant des bornes inf et sup pour toutes ses parties ; en gros, on peut toujours s'y ramener en ajoutant les intersections et unions idoines), où on demande que S vérifie la condition suivante (si je note S_H la composante de S sur H) : pour tous u et v dans X^ℕ, si I est le plus petit élément de S_H(u) tel que u et v ne coïncident pas identiquement sur I, alors S_H(v) contient également I ainsi que tous les J plus petits (dans S_H(u)), et si un tel élément n'existe pas (c'est-à-dire si u et v coïncident identiquement sur tout élément de S_H(u)), alors S(u)=S(v). En clair : on doit ouvrir les boîtes dans un certain ordre, et le contenu d'une boîte ne peut affecter que les boîtes ouvertes ultérieurement. Visiblement, un schéma de déroulement d'ouvertures S, tel que je viens de le définir, détermine un schéma global d'ouvertures h comme défini précédemment (il suffit de prendre pour h_O(u) le plus grand élément de S_H(u), les autres données coïncidant). Je pense qu'il n'est pas vrai qu'un schéma global d'ouverture puisse toujours être défini par un schéma de déroulement d'ouvertures, mais je n'arrive pas non plus à trouver de contre-exemple (là aussi, je me trouve assez mauvais de ne pas arriver à trancher cette question !).

Est-ce encore suffisant ? Avec ces définition, un schéma d'ouverture légitime pour une suite de boîtes contenant des naturels serait : si toutes à partir d'un certain rang contiennent la même valeur i, alors j'ouvre toutes les boîtes à partir du rang i lui-même (en partant de la fin), sinon je les ouvre toutes à partir du rang 42 (visiblement, ceci vérifie bien la propriété demandée pour un schéma global d'ouverture : si je modifie le contenu d'une boîte non ouverte, alors effectivement j'ouvre encore exactement les mêmes boîtes ; et si on prend l'ensemble des intervalles de boîtes de k à l'infini, on voit facilement qu'on peu fabriquer un schéma de déroulement d'ouvertures comme défini ci-dessus). Pourtant, on a toujours l'impression que c'est de la triche : pour savoir si toutes les boîtes à partir d'un certain rang contenaient la valeur i, il a bien fallu que j'ouvrisse une boîte, mais je ne peux jamais prendre le risque d'ouvrir une boîte quelconque puisque si je le fais je risque d'avoir violé la contrainte. Bref, on voudrait pouvoir parler de la première boîte ouverte (ou en tout cas, des premières boîtes ouvertes), qui ne pourraient évidemment dépendre de rien du tout, puis des suivantes, etc.

Là, la définition qui s'impose, c'est celle d'un schéma bien-déroulé d'ouvertures : la définition serait la même que celle que j'ai donnée pour un schéma de déroulement d'ouvertures, mais en imposant que l'ensemble S_H(u), pour chaque suite u, soit bien ordonné (en particulier, il doit avoir un plus petit élément I, et la propriété qu'on a imposée sur S fait que I doit être indépendant de u). En outre, l'intérêt d'un schéma bien-déroulé d'ouvertures est qu'on doit pouvoir le définir par induction (transfinie), l'ouverture de chaque lot de boîtes étant fait en fonction des contenus des lots précédemment ouverts. D'une certaine manière, ça montre comment le concept d'ensemble bien ordonné peut apparaître de façon assez naturelle en essayant de formaliser l'intuition qu'on peut avoir du déroulement d'un processus transfini automatique.

Je vais m'en tenir là, parce que mon poussinet en a assez de me voir réfléchir sur ces problèmes, mais si quelqu'un a des lumières sur une des questions que j'ai laissées en suspens, ces lumières seront les bienvenues.

Commentaires

2009-05-19 (mardi)

Enfin un vrai site de prévisions pour les élections européennes

Essayez de trouver un journal français qui parle des élections du parlement européen pour donner des pronostics ou des sondages qui dépassent un peu le cadre de la France : ce n'est pas facile (← ceci est une litote). Et ça m'agace énormément : les députés européens ne représentent pas leur pays (il y a le Conseil pour ça), et les études (comme l'excellent livre de Hix, Noury & Roland à ce sujet) montrent qu'ils votent réellement selon les lignes des partis, ou au moins des groupes parlementaires, au niveau européen, et non selon leur pays d'origine — et accessoirement (parce que certains semblent parfois en douter dans le cadre de l'espèce de coalition perpétuelle entre PSE et PPE-DE) qu'il y a une vraie différence entre la gauche et la droite au niveau des votes. Donc savoir combien le parti socialiste et l'UMP auront en France m'importe très peu. Savoir comment l'équilibre des partis va changer au niveau européen, et notamment si Rasmussen[#] a la moindre chance de remplacer à Barroso, ça, en revanche, ça me semble important[#2].

Je veux bien croire que ce soit difficile pour les journalistes d'obtenir des chiffres et de faire des prévisions pour 27 pays, dont 26 qu'ils connaissent mal : mais, d'un autre côté, rien ne leur interdit d'aller trouver des collègues à eux dans ces 26 autres pays et de se partager le boulot de pronostic !

Enfin, toujours est-il que quelqu'un a enfin (le mois dernier — je suis toujours le dernier informé de tout) eu la bonne idée de lancer un vrai site web rassemblant des prévisions au niveau européen, www.predict09.eu, enfin quelque chose d'un peu comparable avec ce qu'on pouvait trouver aux États-Unis, avec des analyses état par état et une synthèse globale faite intelligemment et de façon lisible.

Maintenant, ce serait bien s'il y avait un peu plus que un site de ce genre.

[#] Je veux évidemment parler de Poul Nyrup Rasmussen, président du PSE, à ne pas confondre avec Anders Fogh Rasmussen, bientôt secrétaire-général de l'OTAN, ni avec Lars Løkke Rasmussen, l'actuel premier ministre danois et successeurs des deux précédents à ce poste (oui, le Club Contexte est très fier de son coup : les trois derniers chefs de gouvernement danois s'appellent tous Rasmussen !).

[#2] Sans compter la question éminemment importante de savoir si le Piratpartiet aura un, voire deux, parlementaires.

Commentaires

2009-05-16 (samedi)

Le Docteur No continue ses méfaits

Dans l'esprit des énigmes de combinatoire cybernétique que j'avais déjà posées, celle-ci est particulièrement étrange et étonnante (je la décris donc de façon très détaillée et verbeuse, pour qu'il n'y ait aucun doute sur les termes de l'épreuve) :

Le cruel Docteur No a capturé 100 mathématiciens pour les soumettre à une épreuve démoniaque. Il dispose dans une pièce de son bateau d'une infinité (dénombrable) de boîtes, étiquetées par les entiers naturels (0,1,2,3,…), contenant chacune un nombre (disons un nombre réel pour fixer les idées, même si des naturels marcheraient tout aussi bien : en tout cas, il n'y a aucune contrainte sur la suite de nombres ainsi formée) ; il est évidemment impossible de connaître le contenu d'une boîte sans l'ouvrir. Après avoir permis aux mathématiciens de se concerter, il va les soumettre à son épreuve dont il leur communique les termes : il empêchera toute communication entre eux et les emmènera chacun, dans un certain ordre, dans la pièce où se trouvent les boîtes.

Lorsqu'un mathématicien est dans la pièce, il pourra ouvrir les boîtes qu'il souhaite pour en examiner le contenu, y compris une infinité d'entre elles (en fonction éventuellement des nombres lus dans les boîtes déjà ouvertes) ; il devra cependant laisser au moins une boîte sans l'ouvrir, et faire une prédiction sur le contenu exact d'une boîte qu'il n'aura pas ouverte. (Entre les passages de deux mathématiciens, les boîtes sont bien sûr refermées, puisque les mathématiciens ne doivent disposer d'aucun moyen de communication ; ou, si on préfère, on peut imaginer qu'il y a 100 pièces différentes contenant chacune une copie identique de la même suite de nombres, et que tous les passages ont lieu simultanément : c'est équivalent.)

Au final, les 100 mathématiciens auront chacun fait une prédiction sur le contenu d'une boîte sans en avoir regardé le contenu. (Les mathématiciens ont le droit de faire des prédictions sur des boîtes différentes les uns des autres, ou sur la même.) Le Docteur No tolérera une seule erreur parmi ces prédictions : si au moins 99 des 100 mathématiciens ont donné exactement le bon nombre pour la boîte qu'ils ont désignée, alors le Docteur No les libérera tous. Si deux mathématiciens ou plus se sont trompés, alors le Docteur No tuera tous les mathématiciens avec ses tortures particulièrement raffinées.

Comment les mathématiciens font-ils pour être certains d'être tous libérés ?

La raison pour laquelle l'énigme semble (si on essaie d'y réfléchir) impossible à résoudre, c'est bien sûr qu'ouvrir des boîtes autres que celle sur laquelle on va faire la prédiction n'apporte aucune information sur cette dernière (puisque le Docteur No a le droit d'avoir rempli les boîtes absolumnet comme il le veut !), et on ne voit pas ce que peut apporter le fait qu'il y ait 100 mathématiciens, puisqu'ils ne communiquent pas du tout entre eux ; certes, on a droit à une erreur, mais on voit mal comment exploiter ce droit.

Je vais donc donner trois indications (cachées ci-dessous : cliquez sur les liens qui suivent pour les dévoiler) : la première est mathématique et devrait clarifier ce qu'on s'autorise à faire d'une infinité de nombres. La seconde indication est une nouvelle énigme, beaucoup plus simple (mais qui peut éventuellement être intéressante en elle-même, notamment pour les gens qui n'aiment pas les infinis), censée démystifier comment utiliser le droit à faire une erreur. Les deux ensemble devraient rendre claire la façon dont on peut prédire quelque chose sur une boîte sans l'avoir ouverte. (Attention cependant, il est possible que ma seconde indication, prise seule, mette sur une fausse piste.) Enfin, la troisième indication propose le mode opératoire. Les trois indications mises ensemble devraient rendre la solution assez évidente. Au lecteur de choisir quelle(s) indication(s) il souhaite ouvrir pour en lire le contenu !

Première indication : On peut considérer la relation d'équivalence ∼ sur les suites de nombres qui est définie en convenant que u∼v lorsque les suites u et v coïncident après un nombre fini de termes : si on appelle C un ensemble qui contient un représentant et un seul de chaque classe d'équivalence (un tel ensemble existe grâce à l'axiome du choix, auquel nos mathématiciens n'hésitent pas à avoir recours !), alors par définition toute suite de nombres u coïncide, à partir d'un certain rang n, avec un unique élément v de C — donc si on connaît les éléments de u à partir de N≥n, on peut se servir de C pour « prédire » les éléments entre n et N.

Deuxième indication : Dans une variante plus facile de l'énigme, le Docteur No a non plus une infinité de boîtes, mais seulement 100 (autant que de mathématiciens), chaque mathématicien pourra toujours en ouvrir autant qu'il le souhaite mais devra en laisser (au moins) une fermée, et on demande non plus aux mathématiciens de prédire le contenu exact d'une boîte non ouverte mais seulement de le majorer, c'est-à-dire, de dire qu'il sera inférieur à tant (et, de nouveau, les mathématiciens ont collectivement droit à une unique erreur). Comment les mathématiciens font-ils pour faire des majorations toutes correctes sauf au plus une ?

Troisième indication : On peut diviser la suite infinie de boîtes en 100 suites infinies de boîtes, chaque mathématicien peut ouvrir la totalité des boîtes de 99 de ces 100 suites pour les examiner, puis enfin toutes les boîtes de la dernière suite sauf un nombre fini judicieusement choisi d'après l'observation des autres suites.

Commentaires

2009-05-14 (jeudi)

Fragment littéraire gratuit #118 (grammaire)

Je crois que vous ne voulez vraiment pas rencontrer cette langue en vrai :

§339. La forme d'un verbe est déterminée par son mode, son temps, son aspect et sa voix.

Les modes verbaux à flexion interne (ou finitifs) sont : l'indicatif, le subjonctif, le métajonctif, l'orthojonctif, l'optatif et l'impératif (sur leur emploi, cf. §828–852). Les modes verbaux à flexion quasi-nominale sont : l'indéfinitif, le définitif et le participe (sur leur emploi, cf. §853–867) : les deux premiers sont souvent, et parfois aussi par abus de langage le troisième, regroupés sous le nom de modes infinitifs. Les temps simples sont (à l'indicatif) : l'éternel, le présent, le prétérit et le futur. Les aspects verbaux sont (à l'indicatif prétérit) : l'aoriste, l'inchoactif, l'imparfait et le parfait. (Sur l'emploi des temps et aspects, cf. §898–914.) Les voix verbales sont : l'actif, l'objectif et le subjectif (sur le sens des voies verbales, cf. §784–789).

Toutes les combinaisons ne sont cependant pas possibles : le mode optatif n'a pas de prétérit, et le mode impératif n'a pas de futur ; le mode indéfinitif entraîne nécessairement l'aspect aoriste ; l'aspect inchoactif n'existe qu'aux temps présent et prétérit, et le temps éternel qu'aux aspects aoriste et imparfait.

§340. Chacun des mode, temps et aspect du verbe est marqué par un flexème particulier, qui sont normalement adjoints dans cet ordre sauf pour le flexème *u₀[3] du métajonctif qui est adjoint en dernier (cf. §347–351). Les voix verbales sont ensuite marquées dans les modes finitifs par un jeu de flexèmes (§390–398) dépendant du sujet principal aux voix active et subjective, et de l'objet principal à la voix objective.

Il existe en outre, à l'indicatif, des temps dits composés (cf. §378–382), qui sont le plus-que-prétérit (aux aspects imparfait et parfait), le futur antérieur, et le conditionnel (ou futur postérieur), formés respectivement par l'adjonction de deux flexèmes *ne[2] du prétérit, d'un flexème du prétérit puis d'un flexème *s[3] du futur, ou inversement d'un flexème du futur puis d'un flexème du prétérit.

§341. Les paradigmes grammaticaux sont généralement donnés sur le verbe *tis[2]gar[3] (faire, accomplir).

Ainsi on a à l'indicatif : éternel aoriste tiset gar (il fait), présent aoriste tisgar i (il fait), prétérit aoriste tisne gar (il fit), futur aoriste tisgars (il fera), présent inchoactif tisgarəŋ (il commence à faire), prétérit inchoactif tisneŋ gar (il commençait à faire), éternel imparfait tisja gar (il fait pour toujours), présent imparfait tisjasu gar (il est en train de faire), prétérit imparfait tisneja gar (il faisait), futur imparfait tisjas gar (il sera en train de faire), présent parfait ekkar tis (il a fait), prétérit parfait ekne tis-gar (il avait fait), futur parfait ekkars tis (il fera).

Au subjonctif (flexème *j/*jə[4], cf. §342–344) : éternel aoriste tiseč gar, présent aoriste tisgarji, prétérit aoriste tisnej gar, futur aoriste tisgars jə, présent inchoactif tisgarəŋ jə, prétérit inchoactif tisneŋ garjə, éternel imparfait tisjaj gar, présent imparfait tisjasu gar-jə, prétérit imparfait tisneja garjə, futur imparfait tisjas gar-jə, présent parfait ekkarjə tis, prétérit parfait eknej tis-gar, futur parfait ekkars tis-jə.

Au métajonctif (flexème *t/*ti[3], cf. §345–346) : éternel aoriste tisetti gar, présent aoriste tisgart i, prétérit aoriste tisnet gar, futur aoriste tisgarts, présent inchoactif tisgartəŋ, prétérit inchoactif tisnetəŋ gar, éternel imparfait tisjat gar, présent imparfait tisjatsu gar, prétérit imparfait tisneja gart, futur imparfait tisjats gar, présent parfait ekkart tis, prétérit parfait eknet tis-gar, futur parfait ekkarts tis.

À l'orthojonctif (flexème *u₀[3] post-adjoint, cf. §347–351) : éternel aoriste tisetu gar, présent aoriste tisgaru i, prétérit aoriste tisneu gar, futur aoriste tisgarsu, présent inchoactif tisgarəŋu, prétérit inchoactif tisneŋu gar, éternel imparfait tisjau gar, présent imparfait tisjasuu gar, prétérit imparfait tisnejau gar, futur imparfait tisjasu gar, présent parfait ekkaru tis, prétérit parfait ekneu tis-gar, futur parfait ekkarsu tis.

À l'optatif (flexème *e[3], cf. §352–354) : éternel aoriste tisete gar, présent aoriste tisgare i, futur aoriste tisgares, présent inchoactif tisgareŋ, éternel imparfait tisjaa gar, présent imparfait tisjaasu gar, futur imparfait tisjaas gar, présent parfait ekkare tis, futur parfait ekkares tis.

À l'impératif (flexème *an[1], cf. §355–359) : éternel aoriste anet tisgar, présent aoriste aŋgar tis, prétérit aoriste anne tisgar, présent inchoactif aŋgarəŋ tis, prétérit inchoactif anneŋ tisgar, éternel imparfait añja tisgar, présent imparfait añjasu tisgar, prétérit imparfait anneja tisgar, présent parfait anek tisgar, prétérit parfait anek tisne-gar.

(Pour les modes infinitifs et participe, cf. §403–410.

§342. L'indicatif n'est pas marqué par un flexème particulier : *tis[2]gar[3] (faire, accomplir) → tisgar i (il fait, présent aoriste). Les verbes dits éthiques (dont le mode naturel est l'optatif) et prennent cependant flexème *pa₂[4] : ainsi, *deʒ[3] (avoir pour but) → deʒpa i (il a pour but, présent aoriste), nepa deʒ (il eut pour but, prétérit aoriste).

Le défi, ensuite, ce serait de reconstituer, à partir de ça, les règles d'ordonnement des flexèmes (celles qui constituent les §35ss).

Commentaires

2009-05-08 (vendredi)

Fragment littéraire gratuit #117 (persuasion)

— Vous avez insisté pour me voir, aussi vous ai-je reçu : mais vous connaissez déjà quelle sera ma réponse. Le personnage que vous me demandez d'être n'existe plus ; et cela, vous le savez.

Ce furent les premières paroles qu'il m'adressa après le long silence qui suivit un échange de politesses et de formalités. Il ajouta encore :

— Celui que j'ai été, je ne le suis plus. J'ai beau savoir que c'est bien moi qui ai fait les choses qu'on met sur mon compte, je ne reconnais pas comme miennes les actions de ce héros. Car ce n'est pas tant moi qui ai été lui que lui qui a été moi : moi qui ne suis que cette carcasse qu'ont animée un instant les dieux de l'Histoire pour faire avancer leurs desseins, vous me demandez plus que je n'ai à vous offrir. Ce n'est pas ce corps que vous cherchez, c'est l'âme qui l'habitait : or cette âme, elle pourrait aussi bien être en vous car elle m'a été reprise.

L'idée que la postérité a choisi de retenir de cette conversation provient des mémoires de mon interlocuteur et, plus que de ces mémoires eux-mêmes, de l'adaptation cinématographique qui en a été tirée et dont chacun connaît le succès. Elle me montre sous les traits d'un prêcheur déterminé à persuader et sûr de la réponse qu'il obtiendra finalement : peut-être même est-ce le souvenir que l'autre en a sincèrement gardé. Mais je dois à regret m'élever contre cette gloire que je ne mérite pas : le jeune homme que j'étais alors, tout intimidé qui était assis en face de lui, n'avait pas plus la fougue de l'acteur qui joue mon rôle que je n'avais sa beauté ravageuse. Si j'ai convaincu, c'est presque par hasard, c'est presque malgré moi. Non, je dois respectueusement contredire le récit que fait notre héros de ma première rencontre avec lui : jamais je ne lui ai dit — jamais je n'aurais pu lui dire — jamais je n'aurais eu l'audace de lui faire cette réponse : Et cette âme, Monsieur, je suis venu pour tâcher de vous la retrouver.

Au lieu de ça, j'ai baissé la tête vers la tasse de thé qu'il m'avait servie, et je crois que j'ai dit : J'ai peur. Je ne veux pas mourir.

Commentaires

2009-05-01 (vendredi)

Encore un taquin de Mathieu

J'avais déjà proposé (deux fois) des petits jeux comme ça : celui qui se trouve en bas de cette entrée (cliquez ici s'il n'apparaît pas bien ci-dessous, et maudissez avec moi la norme HTML qui ne permet pas d'inclure un document dans un autre en l'insérant à sa taille naturelle) est donc ma troisième tentative, et j'en suis un peu plus content parce que, contrairement aux deux précédents qui étaient sérieusement trop durs, je crois qu'il est vraiment jouable (et construit de façon un peu moins ad hoc). Par contre, je ne suis pas du tout content de l'interface, comme je vais l'expliquer.

Le but du jeu, donc, est de mélanger les nombres de 1 à 24 puis d'arriver à les remettre dans l'ordre évident dans lequel ils sont présentés initialement. La commande ¿ (un point d'interrogation à l'envers, ne me demandez pas pourquoi) mélange complètement le taquin, et la commande † (une croix) le réinitialise à sa position de départ ; quant à ¡ (un point d'exclamation à l'envers), elle effectue un mélange partiel, que j'appelle un m12lange pour une raison que je vais expliquer, qui n'échange pas de nombres entre les deux moitiés (dodécades), et qui peut donc servir de puzzle plus simple pour s'entraîner avant de passer au problème complet. Bref, votre mission est de mélanger — ou au moins de m12langer — le puzzle, puis d'arriver à le remettre dans son état initial en n'utilisant que les commandes de mouvement que je vais expliquer (mais peut-être que le mieux est d'expérimenter avec plutôt que de lire les instructions). Avant que quelqu'un n'exprime sa déception à ce sujet : non, il n'y a pas de message de félicitation quand on arrive à remettre le puzzle en ordre.

Expliquons donc quels sont les mouvements autorisés. Tout d'abord, les nombres sont placés en deux tableaux de 3 lignes × 4 colonnes (qu'on pourrait appeler dodécades), le tableau d'en haut contenant initialement les nombres de 1 à 12 et celui d'en bas de 13 à 24. Parmi les mouvements possibles, on peut faire n'importe quelle permutation des trois lignes d'un tableau, à condition de faire la même sur l'autre tableau : pour concrétiser ça, j'ai mis des commandes ↓ et ↑, qui permutent cycliquement les trois lignes de chaque tableau, et ↕ qui échange les deux lignes d'en bas de chaque tableau : avec ça, on arrive assez facilement à faire n'importe quelle permutation des lignes (la même sur les deux tableaux). Pour ce qui est des colonnes, on à le droit à ce qu'on appelle une permutation paire (toujours la même sur les deux tableaux) : concrètement, j'autorise à faire une permutation cyclique des trois colonnes de gauche, ou des trois colonnes de droite, avec les commandes ← et → situées de part et d'autre du losange central — celles à gauche permutent cycliquement les trois colonnes de gauche et celles à droite les trois colonnes de droite. Ensuite, on a l'opération la plus importante, le flip de Mathieu, commandée par le losange ◊ : elle échange huit paires de nombres (quatre en haut et quatre en bas, mais pas organisées de la même façon), rappelées par des couleurs sur les cases en question — le contenu de chaque case coloriée est échangé avec celui de la case de même couleur. (Chaque paire est composée de deux cases adjacentes en diagonale — du moins, pour le tableau du bas, si on regarde les colonnes cycliquement.)

Aucune des opérations qu'on vient de décrire n'échange des nombres entre les deux tableaux : les nombres qui étaient en haut restent en haut et ceux d'en bas restent en bas ; je dirai que tout mélange effectué avec les différentes opérations que je viens de décrire est un m12lange du tableau : mais pour avoir un mélange complet, il me faut une dernière opération. Celle-ci est représentée par ↨ (flèche haut-bas avec une base horizontale), et elle échange deux des trois lignes du tableau supérieur (les deux lignes d'en bas, en l'occurrence) avec les deux mêmes lignes du tableau inférieur (en combinant avec des permutations cycliques, on voit bien sûr qu'on peut facilement faire échanger n'importe quel nombre pair de lignes entre les deux tableaux).

Ces règles étant décrites, que peut-on en dire mathématiquement ? Il y a 244823040 façons de mélanger le puzzle, c'est-à-dire seulement la fraction 1/2534272925184000 des 620448401733239439360000 manières en tout dont on peut permuter 24 objets. Néanmoins, ces 244823040 permutations, qui forment le groupe M₂₄ de Mathieu, suffisent à permettre de placer cinq nombres quelconques (parmi les 24) à cinq emplacements quelconques : on dit qu'il est cinq fois transitif — et c'est assez remarquable, parce que tout puzzle consistant en des permutations, arbitrairement composables, sur n objets et qui permettrait d'en placer six quelconques à six emplacement quelconques (i.e., qui serait six fois transitif), ou a fortiori plus que six, réaliserait obligatoirement[#] toutes les permutations de ces n objets, sauf peut-être à un échange près (autrement dit, les permutations paires : tout le monde sait sans doute que le taquin habituel ne permet de réaliser que la moitié des permutations imaginables). En particulier, si on ajoutait n'importe quelle nouvelle opération (qui ne soit pas déjà réalisable avec celles proposées), on pourrait obtenir n'importe quel arrangement des 24 nombres ou au moins tous les arrangements pairs.

Quant aux façons de m12langer le puzzle, il en existe 95040 (là, ce n'est vraiment pas énorme !), c'est-à-dire 1/5040 des 479001600 manières de permuter 12 objets, et, de nouveau, le groupe des permutations ainsi formées, qui est le groupe M₁₂ de Mathieu, opère cinq fois transitivement, c'est-à-dire que sans échanger de nombres entre les deux tableaux on peut arriver à placer cinq quelconques d'un tableau donné à un emplacement quelconque dans ce tableau. Donc ce puzzle, contrairement aux précédentes tentatives que j'avais faites pour présenter le groupe M₂₄ sous forme de jeu de taquin, montre clairement comment le sous-groupe M₁₂ apparaît, et permet de s'en servir comme d'un mini-puzzle à l'intérieur du puzzle complet, si on s'interdit simplement d'utiliser l'opération ↨ qui échange des lignes entre les deux tableaux (et si on m12lange avec ¡). Ce mini-puzzle, d'ailleurs, est tout à fait jouable tout en étant loin d'être évident ! Et puis, il y a quelque chose d'un peu magique, quand on arrive à remettre en ordre le tableau du haut après l'avoir m12langé, à constater que celui du bas se remet aussi magiquement[#2] dans l'ordre.

Mes opérations ne sont pas tout à fait irredondantes : par exemple, il n'est pas nécessaire de disposer d'une opération ↕ échangeant les deux lignes inférieures (de chaque tableau), et il n'est pas non plus nécessaire de pouvoir faire une rotation cyclique des trois colonnes de droite — on peut engendrer tout M₁₂ avec juste une rotation cyclique des lignes, une rotation cyclique des trois colonnes de gauche, et le flip, et M₂₄ avec l'opération ↨ en plus. (Mais ça me semblait tout de même pertinent de tout autoriser, pour que le puzzle ne soit pas injouable, et aussi parce que ça me semble plus logique avec toutes les opérations. Si on est téméraire, on peut cependant essayer de jouer avec seulement les opération que je viens de dire.) En revanche, le flip est évidemment indispensable : sans lui, deux nombres situés sur la même ligne ou colonne resteront toujours sur la même ligne ou colonne, et on n'obtient que 288 permutations en tout.

J'ai expliqué que M₂₄ ne contient qu'une toute petite fraction des 24!≈6×10²³ permutations possibles de 24 objets : les joueurs de Rubik's cube auront peut-être tendance à rigoler de la taille de ce groupe, qu'est-ce que 245 millions d'éléments par rapport aux 4×10¹⁹ configurations du cube 3×3×3 ? Pourtant, je pense que c'est justement le fait que le groupe de Mathieu soit petit (donc très contraint) dans le groupe symétrique qui fait que le puzzle n'est pas très facile : on ne peut pas espérer trouver de façon d'échanger juste deux nombres, ou juste deux paires, ou quelque chose comme ça — le plus grand nombre d'éléments qu'on peut simultanément laisser fixe par une opération quelconque est huit (ou, si vous préférez, si neuf nombres quelconques sont à leur bonne place, le puzzle est forcément résolu ; et dans M₁₂ c'est même cinq). En même temps, le fait que M₂₄ soit quand même cinq fois transitifs signifie que le problème a énormément de symétries, on ne peut pas toutes les « voir » à la fois. Par rapport à mes présentations précédentes de M₂₄ comme puzzle (ici et là), on a peine à croire que c'est le même groupe (à conjugaison près dans 𝔖₂₄, c'est-à-dire à réétiquetage près), mais avec des générateurs différents : je pense que ce nouveau puzzle est à la fois plus simple à résoudre (je n'y arrive pas non plus sans aide de l'ordinateur, mais je n'y ai pas passé un temps fou, et j'arrive au moins à faire le mini-puzzle de M₁₂) et moins artificiel (les mouvements proposés ne sont pas atrocement compliqués, et notamment j'arriverais à retenir toutes les règle, notamment les cases échangées par le flip de Mathieu, alors que dans mes précédentes descriptions c'était vraiment sorti d'un chapeau. Là, je crois que je vais retenir cette description des groupes de Mathieu.

Par contre, je ne suis vraiment pas content de mon interface en HTML+JavaScript : c'est atrocement peu maniable, et fort peu intuitif. Donc si quelqu'un trouve une autre façon de faire ça, une interface montrant facilement qu'on peut faire une permutation quelconque des lignes, une permutation paire des colonnes, l'échange d'un nombre pair de lignes entre les deux tableaux, plus le flip magique, ça m'intéresse. (Enfin, ça m'intéresse surtout si quelqu'un réalise cette interface, parce que donner des conseils c'est toujours facile…)

Trêve de blabla, voici le puzzle : jouez-y, c'est addictif !

[#] Techniquement : tout groupe de permutations sur n objets qui est six fois transitif est égal au groupe symétrique 𝔖_n ou au groupe alterné 𝔄_n ; et à part eux, les seuls qui soient cinq fois transitifs sont les groupes M₁₂ et M₂₄ de Mathieu, opérant naturellement sur 12 ou 24 objets. (J'en avais déjà parlé.) On peut aussi donner des listes de groupes opérant fidèlement de façon deux à quatre fois transitive, mais il y en a plus que ça.

[#2] En fait, si on fait correspondre le tableau du haut avec le tableau du bas dans lequel on a permuté cycliquement les colonnes d'un cran (dans un sens quelconque), on obtient une application qui associe à chaque élément de M₁₂ un autre élément de ce même groupe, et qui préserve la composition : il se trouve que cette correspondance constitue l'unique (à conjugaison près) automorphisme extérieur de M₁₂. Quant à M₂₄, lui, il ne possède pas d'automorphisme extérieur : c'est un groupe complet.

Commentaires