Choux romanesco, Vache qui rit et intégrales curvilignes

13 avril 2014

[#] La dualité. Mesdames et messieurs.

Il n'y a pas que les physiciens quantiques et les philosophes qui ont le monopole de la dualité. Les mathématiciens ont aussi leur mot à dire, et ils ne se sont pas privés : dual d'un polyèdre, dual d'un graphe, dual d'un espace vectoriel, dualité de Poincaré...

Ma dualité préférée est celle de la géométrie projective, le domaine de la géométrie qui étudie les notions de perspectives. Cette dualité permet sans effort de fabriquer plein de nouveaux théorèmes de géométrie. Mais pour cela, il faut comprendre dans ses très grandes lignes la géométrie projective, en admettant ses deux axiomes suivants :

  1. Par deux points distincts passe toujours un droite (et une seule).
  2. Deux droites distinctes se coupent toujours en un point (et un seul).

Le premier axiome, on le retrouve dans notre bonne vieille géométrie euclidienne, il ne va pas nous étonner. Par contre, le deuxième axiome a l'air manifestement faux, puisque deux droites parallèles ne se coupent a priori en aucun point. Mais ça, c'était avant : en géométrie projective, des droites parallèles se coupent quand même, mais en un point "à l'infini", sur la ligne d'horizon.

En fait, ces deux axiomes peuvent tout les deux se résumer sous la forme :

  • Deux machins distincts se schtroumpfent toujours en un truc

Ces machins-trucs que sont les droites et les points sont en quelque sorte en dualité : en les inversant dans un axiome, on obtient l'autre.

Mais on peut faire encore plus fort. Partons de l'idée qu'un plan, c'est juste un ensemble de droites et des points. Alors on peut imaginer un nouvel espace où l'on appellerait "points" les droites du premier espace, et inversement (on se moque de savoir à quoi ressemble ce plan, ce n'est pas la question qui nous intéresse). Ce nouveau plan, on peut l'appeller "dual" du premier.
Mais ce plan dual vérifie toujours les deux axiomes de départ : il y a de bonnes raisons à le considérer comme un plan projectif comme les autres...

En fait, on peut mathématiser proprement la construction de ce plan projectif dual ; en le faisant, on s'aperçoit qu'il ressemble étrangement au plan de départ. Du coup, puisque ces objets passent au dual, on peut démontrer que les propriétés qui les définissent aussi.

Par exemple :

  • Un point P du plan devient une droite (p) du dual ; une droite (d) du plan devient un point D du dual
  • Dans le plan, deux droites (d) et (e) se coupent en un point P
    => dans le dual, deux points D et E forment une droite (p)
  • Dans le plan, trois points alignés P, Q et R forment une droite (d)
    => dans le dual, trois droites concourantes (p), (q) et (r) forment un point D

Plan_et_son_dual
Une configuration du plan : trois droites (d), (e) et (f) concourantes en P, et trois points P, Q et R alignés sur (d).
La même configuration dans le dual : trois points D, E et F alignés sur (p), et trois droites (p), (q) et (r) concourantes en D.

Du coup, si un théorème de géométrie ne fait appel qu'à des notions d'alignements de points ou de concourances de droites, on peut les dualiser afin d'obtenir un nouveau théorème. C'est l'outil parfait pour doubler le nombre de théorèmes existants ! Place aux exemples !

Le théorème de Pappus
Parmi les théorèmes de géométrie injustement méconnus, il y a le théorème de Pappus (que l'on doit à Pappus d'Alexandrie) :

Théorème de Pappus :
Soit A, B et C trois points distincts alignés sur une droite (d),
soit A', B' et C' trois points distincts alignés sur une droite (d'), 
Notons (p)=(AB'), (p')=(A'B), (q)=(AC'), (q')=(A'C), (r)=(BC') et (r')=(B'C)
Alors, les points E = (p')∩(p'), F = (q)∩(q') et G = (r)∩(r') sont alignés

Pappus

Ce théorème peut se dualiser, en inversant "droite" et "point", et en inversant "concourant" et "alignés". On obtient alors un tout nouveau théorème :

Théorème dual de Pappus : 
Soit (a), (b) et (c) trois droites distinctes concourantes en un point D, 
Soit (a'), (b') et (c') trois droites distinctes concourantes en un point D', 
Notons P=(a)∩(b'), P'=(a')∩(b), Q=(a)∩(c'), Q'=(a')∩(c)R=(b)∩(c'), R'=(b')∩(c)

Alors, les droites (E) = (PP'), F=(QQ') et G=(RR') sont concourantes

 Pappus_dual

Ce théorème est loin d'être aussi élégant que son dual, mais il a le mérite d'exister. (Bon, en réalité, il décrit exactement la même configuration que dans le théorème de Pappus !...)

Le théorème de Desargues
Le théorème phare de la géométrie projective, c'est le théorème de Desargues, conséquence de celui de Pappus. On le doit au français Girard Desargues, que l'on peut considérer comme le père de la géométrie projective. Il indique :

Théorème de Desargues (*)
Soit deux triangles (non aplatis) ABC et A'B'C'
Si les droites (AA'), (BB') et (CC') sont concourantes
alors les points P = (AB)∩(A'B'), Q = (AC)∩(A'C') et R = (BC)∩(B'C') sont alignés

Desargues

Encore une fois, le passage au dual permet de fabriquer un nouveau théorème. Enfin, presque nouveau, puisque ce n'est autre que la réciproque du théorème précédent. La seule différence est la surcomplexification inutile de son énoncé...

Réciproque du théorème de Desargues
Soit deux triangles (non aplatis) de côtés (a), (b) et (c), et de côtés (a'), (b') et (c') 

Si les points (a)∩(a'), (b)∩(b') et (c)∩(c') sont alignés
alors les droites (p) = (ab;a'b'), (q) = (ac;a'c') et (r) = (bc;b'c') sont concourantes
(en notant (ab;a'b') la droite passant par ab=(a)∩(b) et a'b'=(a')∩(b'))
Desargues_dual

 

Le théorème de Pascal
Un autre théorème qui passe parfaitement au dual est celui de l'hexagramme mystique de Pascal, qui parle de coniques (ellipses, hyperboles, paraboles, ...) :

Théorème de Pascal
Soit A, B, C, A', B' et C' six points distincts sur une conique
Notons (p)=(AB'), (p')=(A'B), (q)=(AC'), (q')=(A'C), (r)=(BC') et (r')=(B'C)
Alors, les points E = (p)∩(p'), F = (q)∩(q') et G = (r)∩(r') sont alignés

Pascal

On peut voir que ce théorème est une généralisation de celui du théorème de Pappus, puisqu'un couple de droites n'est qu'un cas particulier de conique dégénéré.

L'hexagramme de Pascal peut également être dualisé, en ajoutant deux nouvelles correspondances entre le plan et son dual :

  • Une conique dans le plan reste une conique dans le dual
  • Un point sur une conique dans le plan devient une droite tangente à une conique dans le dual

Théorème de Brianchon
Soit (a), (b), (c), (a'), (b') et (c') six droites distinctes tangente à une conique
Notons P=(a)∩(b'), P'=(a')∩(b), Q=(a)∩(c'), Q'=(a')∩(c), R=(b)∩(c'), R'=(b')∩(c)

Alors, les droites (E) = (PP'), F=(QQ') et G=(RR') sont concourantes


Pascal_dual

Le théorème de Pascal est vrai quel que soit l'ordre des points A, B, C, A', B', C' que l'on considère. La droite orange obtenue dépend donc de l'ordre des points. Puisqu'il y a 60 façons de dessiner un hexagone à partir de 6 points, on peut obtenir une famille de 60 droites, les droites de Pascal. Cet énoncé passe au dual, ce qui entraîne l'existence de 60 points particuliers, les points de Kirkman (points de concourance des droites de Pascal).

Droites_de_Pascal
(Une partie de) Les 60 droites de Pascal et les 60 points de Kirman
Oui, c'est n'importe quoi.


(*) Note de bas de page : à première vue, le théorème de Desargues n'est qu'un amas sans fond ni forme de points et de cercles. Pour le visualiser (et le mémoriser), on peut penser à cette figure : il faut imaginer que ABC et A'B'C' sont des coupes transversales parallèles d'une même pyramide. Ces coupes étant parallèles, les côtés se prolongent et se coupent deux à deux sur la même ligne d'horizon : ces points de concours sont donc alignés.


Sources :
Wikipedia, essentiellement
Pascal Lines, sur MathWorld


06 avril 2014

[#] Mokshû Patamû

Après une partie contre des banquiers véreux qui n'ont jamais voulu échanger votre Faubourg Saint-Honoré contre leur Boulevard Malesherbes, vous avez choisi de renoncer définitivement à ouvrir cette boîte de ce jeu de l'enfer qu'est le Monopoly. Mais à quoi jouer avec beau-papa en ce dimanche après-midi ? Une partie de Scrabble ? des colons de Catanes ? des Aventuriers du Rail ? Non ! Revenons aux bases, et ouvrons la boîte pleine de poussière qui renferme un vénérable plateau de Serpents et échelles !

Bon, finalement, vous avez débuté le jeu, et vous n'avez maintenant plus qu'une seule envie : que cela se termine ! Mais au fait, combien de temps dure en moyenne une partie de Serpents et échelles ?!

320px-Snakes_and_ladders2

Pour les quelques-uns qui n'ont jamais perdu des heures à tomber en boucle sur la même gueule de serpent, voici ce qu'il faut savoir sur ce jeu :

  • Le plateau de jeu est composé de 100 cases, numérotées de 1 à 100.
  • Les joueurs, chacun leur tour, lancent le dé, puis déplacent leur pion du nombre de cases indiqué.
  • Des serpents et des échelles sont disséminés sur le plateau de jeu. Lorsqu'on arrive au pied d'une échelle, on la monte ; inversement, lorsque l'on tombe sur une tête de serpent, on descend jusqu'à sa queue.
  • Le premier joueur à atteindre (ou dépasser) la 100e case est déclaré vainqueur, et félicité pour sa chance au jeu.
  • A l'origine, ce jeu est une métaphore indoue du chemin spirituel pour atteindre le Nirvana.

De nombreuses variantes de plateaux de jeu existent, je vais me baser sur la version Hasbro, dont le plateau comporte 9 échelles et 7 serpents, et qui ressemble à ceci :

Plateau

Au nom de la loi de X
En détaillant un peu le plateau, on peut voir que la centième case peut être atteinte en seulement 7 lancés de dés, en empruntant 3 échelles (l'échelle 1 -> 38, la 51-> 67 et la 71 -> 91). Cependant, il n'y a pas de nombre maximum de coups permettant d'atteindre la dernière case. Heureusement, ce cas est presque impossible.

Finalement, quel est le temps moyen permettant d'atteindre cette centième case ? Les chaînes de Markov sont là pour nous aider à appréhender la situation. Pour comprendre, observons ce qu'il se passe lancé par lancé.

Au début du jeu, les pions sont en dehors du plateau. Au premier lancé de dé, 6 cases sont atteignables (38 (si on obtient 1 au dé, grâce à l'échelle), 2, 3, 14 (4 au dé), 5 ou 6). La probabilité d'atteindre chacune de ces cases après le premier lancé de dé est donc de 1/6 (≈0.17).

proba_ees_lance_1

Pour ce qui est du deuxième lancé de dé, il faut envisager les 6 cas précédents :

  • depuis la case 38, on peut atteindre 39, 40, 41, 42, 43, 44
  • depuis la case 2, on peut atteindre 3, 14, 5, 6, 7, 8
  • depuis la case 3, on peut atteindre 14, 5, 6, 7, 8, 31
  • depuis la case 14, on peut atteindre 15, 6, 17, 18, 19, 20
  • depuis la case 5, on peut atteindre 6, 7, 8, 31, 10, 11
  • depuis la case 6, on peut atteindre 7, 8, 31, 10, 11, 12

Puisqu'il y a 36 façons de lancer deux fois le dé, chacune de ces cases a pour probabilité 1/36 d'être atteinte par le chemin indiqué. On peut alors remarquer, par exemple, que :

  • il n'y a qu'une seule façon d'atteindre la case 42 en deux lancés de dé : sa probabilité est de 1/36 (≈0.03).
  • il y a 4 façons d'atteindre la case 6 en deux lancés de dé : la probabilité de cette case est donc de 4/36 (≈0.11).

proba_ees_lance_2

On pourrait suivre le même raisonnement pour le troisième lancé de dé, mais le décrire entièrement serait trop long. Heureusement, les matrices vont venir prendre le relai. Pour cela, on a besoin de la matrice de transition M du plateau, qui donne la probabilité d'atteindre une case sachant que l'on est sur une autre case.

Pour être plus précis, le coefficient de la ligne I et de la colonne J correspond à la probabilité d'atteindre la J-ième case sachant que l'on se trouve sur la I-ème. A titre d'exemple, le coefficient ligne 2 colonne 3 est 1/6 car il y a une chance sur 6 d'atteindre la case 3 en partant de la case 2.

matrice_ligne23_echelles_et_serpents

La matrice finale M contient donc une très grand nombre de 0, beaucoup de 1/6 et quelques valeurs un peu plus grandes (le coefficient ligne 52 colonne 53 vaut 2/6, car il y a deux façons d'atteindre la case 53 depuis la 52). Graphiquement, la matrice ressemble à ceci.

matrice_echelles_et_serpents

Cette matrice nous permet de calculer la probabilité de chacune des cases pour un nombre de lancé choisi, en utilisant le fait que

U(n+1) = U(n) × M
où U(n) la matrice-ligne qui donne la probabilité de chacune des 100 cases lors du n-ième lancé de dé.

On peut notemment calculer la distribution des probabilités pour 6 ou 7 lancés, ce qui confirme la remarque initiale : il est théoriquement possible de gagner en 7 lancés de dés, mais la probabilité est excessivement faible (0.2 %). Après 7 lancés, on se retrouve plus facilement en case 26...

proba_ees_lance_6_7

Le temps d'en finir
Tout ceci ne nous dit pas encore combien de temps on doit se farcir les serpents et les échelles pour en finir avec le jeu. Il ne reste en fait plus qu'à chercher la probabilités d'atteindre la 100e en exactement n lancés de dés, pour toutes les valeurs de n. Aussitôt dit, aussitôt fait :

proba_case100

Ce graphique (et quelques calculs autour des données) nous apprend des choses essentielles :

  • Le plus probable est d'atteindre la centième case en 20 lancés de dés
  • En moyenne, il faut 36 lancés de dés pour gagner
  • Il y a 50% de chances de finir en moins de 29 mouvements
  • Il y a 98% de chances d'en finir en moins de 100 mouvements

Oui, mais...
D'aucun me diront que, dans les règles officielles du jeu, il faut atteindre exactement la case 100, sinon la règle "tu dépasses, tu recules" s'applique. Ca change tout !

Qu'il en soit ainsi, je modifie la matrice tout de suite :

matrice_echelles_et_serpents_2

Ce qui nous donne ce chouette graphique :

proba_case1002

En détaillant en peu les chiffres, on découvre que...

  • Le plus probable est d'atteindre la centième case en 22 lancés de dés (et la probabilité est bien plus faible que dans le cas précédent)
  • En moyenne, il faut 43 lancés de dés pour gagner
  • Il y a 50% de chances de finir en moins de 34 mouvements
  • Il y a 94% de chances d'en finir en moins de 100 mouvements

Mouais... Finalement, cette règle supplémentaire a surtout pour effet de rallonger la traîne de la courbe : le cas le plus probable ne change pas, mais les événements très rares le deviennent un petit peu moins.


 

Sources :
Analysis of Chutes and Ladders, sur DataGenetics

Images :
Snakes_and_ladders
 

Posté par El Jj à 10:00 - Commentaires [3]
Tags : , , ,

30 mars 2014

[#] Made in Sinaï

Le prix Abel 2014 a été annoncé le 26 mars dernier, et l'heureux lauréat est russe ! C'est donc le mathématicien (et un peu physicien) Iakov Sinaï qui décroche cette année le prix Nobel des maths (parce que, non, la médaille Fields n'est pas l'équivalent d'un Nobel, c'est encore plus prestigieux). Il est récompensé pour l'ensemble de son œuvre : des travaux sur les systèmes dynamiques, sur la théorie ergodique et en physique mathématique. Son nom restera surtout associé aux systèmes dynamiques, grâce au billard de Sinaï et à l'entropie de Sinaï-Kolmogorov. A quoi ressemblent ces bêtes là ? Quelques éléments de réponse.

174px-Yakov_G_Sinai_photo
Iakov (Yakov ?!) Sinaï

Le billard de Sinaï
On appelle système dynamique un processus évoluant au cours du temps qui ne fait absolument pas intervenir le hasard (autrement dit, déterministe). L'objet préféré des gens qui étudient les systèmes dynamiques, c'est le billard. Enfin, pas n'importe quel billard : un billard sans trou et qui se joue avec une seule boule (infiniment fine). Une fois lancée, la boule ne s'arrête plus, et suit les loi de la physique lorsqu'elle rebondit sur les parois. En fait, le billard des mathématicien est surtout une façon simple de modéliser le comportement d'un particule d'un gaz.

Dans un tel billard, une fois que l'on connaît la position précise de la balle et sa direction initiale, les lois de la physique nous permettent de prédire avec exactitude la trajectoire qu'elle suivra. Cette trajectoire est donc parfaitement déterministe.

Billard_1
Je lance ma boule selon la direction bleue : elle rebondit, tout est normal.

Si je modifie un peu la position ou la direction initiale de la balle, la trajectoire change. Mais pas tant que ça. En déplaçant la balle et en conservant la même direction, la balle aura une trajectoire parallèle à sa trajectoire initiale ; si c'est la direction que l'on change, la balle déviera de plus en plus de sa trajectoire initiale avec le temps, mais rien de très inquiétant.

Billard_non_chaotique
à gauche, un changement de position initiale
à droite, un changement de direction initiale
De petits changements entraînent de petites déviations

Par contre, quand Sinaï joue au billard, il n'hésite pas à rajouter un gros cylindre en plein milieu de sa table. La physique permet toujours de prédire la trajectoire de la balle, ce système dynamique est toujours parfaitement déterministe.

Billard_Sinaipng
Le véritable "billard de Sinaï" est carré, mais l'idée est la même

La grosse différence d'avec le premier billard, c'est que la trajectoire devient difficile à prévoir lorsque l'on modifie un peu les conditions initiales. En déplaçant, même légèrement, la position de départ de la balle, la trajectoire devient très rapidement complètement différente. Même remarque si l'on modifie un peu sa direction.

Billard_Sinai_chaotique
Avec un petit changement des conditions initiales, la trajectoire change du tout au tout.

Bien que les trajectoires soient complètement prévisible, puisque déterministe, il est en fait impossible de les prévoir sans passer par l'essai. On peut alors qualifier ces trajectoires comme "chaotique" : une petite modification des conditions initiales change très rapidement l'aspect global de la trajectoire. Il existe de très nombreux exemple de systèmes chaotiques, je vous invite plutôt à écouter le dernier épisode de Podcast Science sur le sujet.

Assez paradoxalement, bien qu'il soit impossible de prévoir le comportement d'une trajectoire sans connaître précisément ses conditions initiales, il est quand même possible d'y prévoir des choses. Par exemple, (sauf cas particuliers), les trajectoires seront ergodiques : si on choisit un point sur le bord du billard, la balle finira forcément par passer à un moment ou à un autre près de ce point (et même, aussi près de ce point que l'on veut, si l'on accepte d'attendre longtemps).

Sinaï a en fait produit cet exemple de billard pour montrer qu'il existe un système qui soit à la fois chaotique ("d'exposant de Lyapounov positif") et ergodique, dans le cadre d'un problème sur le comportement physique du mouvement de gaz.

L'entropie de Sinaï-Kolmogorov
Finalement, certains systèmes dynamiques sont faciles à prévoir à court comme à long terme, d'autres le sont à court terme mais pas à long terme, d'autres encore ne le sont plus à moyen terme... Il faut trouver quelque chose pour mesurer tout ça ; ce quelque chose, c'est l'entropie.

Cette entropie n'a pas de rapport direct avec l'entropie des physiciens, mais plutôt avec celle des théoriciens de l'information, à travers l'entropie de Shannon. La définition de l'entropie de Shannon permet de dire qu'une suite de caractère possédant une forte entropie est riche en informations.

Par exemple, les deux phrases "six fois sept égale quarante-deux" et "6×7=42" apportent exactement la même information, mais la deuxième compte sensiblement moins de caractère que la première. La quantité d'information par caractère contenu dans la première phrase est donc très faible, par rapport à l'autre ; son entropie est donc plus petite.
Du coup, quand on commence à écrire "six fois se...", on peut sans trop se tromper penser que les caractères suivants seront "p" et "t" : il est facile de prédire le futur d'une phrase de faible entropie. C'est en s'appuyant sur cette idée que Sinaï produit une notion d'entropie pour certains systèmes dynamiques, en s'appuyant sur les travaux de Kolmogorov (son directeur de recherche).

L'entropie de Sinaï-Kolmogorov permet donc de quantifier la complexité d'un système dynamique, et offre un moyen parfait pour mesurer le chaos. Un système à forte entropie est difficile à prévoir, tout comme il est difficile de prévoir quel sera le mot suivant d'une phrase très riche en information (forte entropie, au sens de Shannon). Si l'on s'accorde à dire que le désordre est riche en information, on peut aussi la relier à l'entropie des physiciens.

Finalement, le mathématicien Iakov Sinaï s'est inspiré de la théorie de l'information pour décrire mathématiquement des systèmes dynamiques issus de la physique. Celui qui a écrit un article intitulé "Mathematicians and Physicists = Cats and Dogs ?" a en fait passé son temps a relier les deux milieux.


Sources :
Site officiel du prix Abel

Images :
Yakov G Sinai photo

Posté par El Jj à 10:00 - Commentaires [0]
Tags : , ,

23 février 2014

[#] Cravate club

L'info a largement été relayée dans les médias, il existerait 177 147 façons de nouer une cravate, et c'est une équipe de mathématiciens et d'informaticiens suédoise qui vient de le publier. Cette étude fait suite à une autre étude qui n'avait compté *que* 85 nouages de cravates différents. 

Mais concrètement, comment ont-ils compté tout ces nœuds de cravate ? Et quel est le rapport entre le film Matrix et cette histoire de cravates ? Détaillons un peu leur méthode.

Les 85 nœuds de Fink et Mao
Thomas Fink et Young Mao, deux physiciens anglais, sont les premiers à s'être formellement penché sur l'épineux problème du nœud de cravate en 1999. 

Pour aborder le problème, pensons cravate. Pour avoir une belle cravate, selon Fink et Mao :
- c'est la partie large de la cravate que l'on manipule
- on commence en plaçant cette partie large du côté gauche du corps (au-dessus ou en dessous de la partie fine, selon le nœud)
- on la passe alternativement au dessus et au-dessous du nœud.
- on termine en passant ce bout à l'intérieur du nœud, pour le "fermer".

La plus simple des variantes est le nœud "quatre en main", qui s'élabore en 4(+1) étapes, de la façon suivante :

Quatre mouvements pour un quatre en main

- on commence en plaçant la partie large de la cravate au-dessus et à gauche de l'autre partie (Li)
- on passe la partie large en-dessous et à droite de l'autre partie (Ro)
- on passe la partie large au-dessus et à gauche de l'autre partie (Li)
- on passe la partie large en-dessous du nœud et on la fait sortir par le col (Co)
- on passe la partie large dans le nœud de la cravate (U)

Les opérations que l'on peut finalement faire, c'est passer la partie large en-dessous (noté o) et au-dessus (noté i) de l'autre partie ; on peut, selon les situations, faire ressortir ce bout du côté droit de la cravate (R), gauche (L) ou au niveau du col (C). La dernière opération faisable, c'est celle qui consiste à passer la partie large dans le nœud de la cravate (et qui n'interviendra qu'une seule fois, à la fin) : la fermeture, notée U.

Bref, il y a 7 opérations possibles : Ro Ri Lo Li Co Ci et U. Un nœud de cravate sera alors complètement défini par une suite de ces opérations, en respectant tout de même certaines règles :

  • Règle 1 : on commence par Lo ou Li (commencer par Ro ou Ri entrainerait des nœuds miroirs, oublions-les).
  • Règle 2 : on ne peut pas faire successivement deux opérations R, L ou C identiques
  • Règle 3 : les opérations o et i doivent être alternées.
  • Règle 4 : la fermeture U n'intervient qu'à la fin, et seulement après les opérations Ro Li Co ou Lo Ri Co (car la cravate doit venir par le dessous du nœud, en passant par le côté col)

Ainsi, la succession de mouvements Lo Ri Lo Ri Co Li Ro Li Co U est tout à fait convenable (et il s'agit du nœud Grandchester, le #44 de la liste de Fink, qui requiert 9 mouvements). 

En traduisant les conditions par un graphe, on peut voir qu'une succession de mouvements qui donne un beau nœud de cravate correspond à un chemin sur le graphe ci-dessous, qui commence à D et se termine en U.

Cravate_simple

On peut alors voir qu'il y a un seul nœud faisable en 3 mouvements (Lo Ri Co U, le nœud oriental), un nœud en 4 mouvements (Li Ro Li Co U, le nœud quatre en main présenté plus haut) et 3 nœuds en 5 mouvements (les nœuds Kelvin, Nicky et Pratt). 
En notant an le nombre de nœuds faisables en n mouvements, on peut remarquer que l'on a an+2 = an+1 + 2 an. En se limitant à 8 mouvements au maximum, on dénombre alors 85 nœuds de cravate différents (le mouvement U final n'intervient pas dans le décompte).

85_noeuds

La notation WTU de Vejdemo-Johansson
Sauf qu'en 2003, toute la théorie a sauté, puisque le film Matrix Reloaded est sorti au cinéma. On ne retiendra qu'une seule chose du film : la cravate porté par Lambert Wilson, qui interprète Le Mérovingien, est nouée de façon à ce que la partie large de la cravate termine en-dessous de la partie fine ! Incroyable ! Luke Housego se dépêche de créer un tutoriel sur Internet, et baptise ce nœud le nœud Edeity.

Noeud_Merovingien
Le nœud Mérovingien, ou nœud Edeity, porté avec classe par Lambert Wilson
Séquence : Lo Ci Lo Ri Co Ri Lo Ci U

En 2008, c'est un nouveau nœud qui apparaît sur Youtube, le nœud Eldredge. Tous les tabous de la cravate sautent : ce n'est pas la partie large de la cravate qui est manipulée mais sa partie fine, celle-ci passe plusieurs fois dans le nœud et, ultime affront, elle termine sa course dans le col de son porteur !

Noeud_eldredge
Le nœud Eldredge
Séquence : Li Ro Ci Lo Ri Co Li Ro U Ci Lo Ci Ro U

Les règles imposées par Fink et Mao sont clairement trop restrictives, en particulier la règle n°4. Pour englober davantage de nœuds (dont le nœud Eldredge), disons plutôt que :

  • Règle 4' : le mouvement U peut intervenir n'importe quand, même après un mouvement L ou R, à condition qu'au moins deux mouvements au moins le précède. De plus, sous certaines conditions d'existence, on autorisera le mouvement UU (ou U²) consistant à rentrer la cravate dans deuxième couche du nœud, et, de manière générale, Uk qui consiste à rentrer la cravate dans la k-ième couche du nœud. Un tel mouvement est possible qu'après au moins 2k autres mouvements.

Il faut alors adapter les règles 2 et 3, en précisant qu'un mouvement U n'influence pas le fait que deux mouvements R, L ou C ne peuvent se succéder à l'identique, même chose pour o et i.

D'ailleurs, la notation o et i est complètement superflue. En effet, une fermeture U ne peut exister qu'après un mouvement o, où la cravate passe sous le nœud. Du coup, l'alternance o/i permet de retrouver les directions d'une séquence RLC de mouvements donnée.

Par exemple, la suite de mouvements du nœud Trinity est LCLRCRLCURLU. Le L qui précède le dernier U ne peut être qu'un mouvement de type Lo, et donc, en remontant, on peut retrouver que le mouvement initial est Li :

Noeud_Trinity
Le nœud Trinity (aucun rapport avec Matrix)
Li Co Li Ro Ci Ro Li Co U Ri Lo U

On peut donc se restreindre à seulement 4 symboles pour décrire le nouage de la cravate : L, R, C et U.
Enfin... Pas tout à fait, puisque l'on a pris pour hypothèse que l'on commence toujours à gauche (mouvement L). Il est donc inutile de le noter dans la liste. Comme deux mouvements L, R et C ne peuvent se succéder à l'identique, on peut se contenter de dire si le prochain mouvement est un mouvement dans le sens des aiguilles d'une montre (noté T - comme Turnwise) ou dans le sens inverse (noté W - comme widdershin).

  • T : tourner dans le sens des aiguilles d'une montre (sens indirect) : R -> L, L -> C ou C -> R.
  • W : tourner dans le sens inverse des aiguilles d'une montre (sens direct) : L -> R, R -> C ou C -> L.

Par exemple, la suite de mouvement WTWTWUTTU du nœud Floating Spiral débute, comme tous les nœuds, par L. Puisque le premier mouvement est de type W, la région suivante est R. On peut ainsi en déduire la séquence complète :

Noeud_Floating_Spiral
Nœud Floating Spiral
Li Ro Li Ro Li Ro U Li Co U

Les 177 147 nœuds de Vejdemo-Johansson
Il est temps de dénombrer les différents nœuds de cravate. Pour cela, l'équipe de Vejdemo-Johansson a remarqué que les nœuds de cravate de 1ere espèce (où la cravate ne peut passer que sous la couche la plus récente crée au dessus du nœud) obéissent toujours au schéma ⟨préfixe⟩ ⟨développement⟩ ⟨fermeture⟩, sachant que

  • le préfixe peut être T ou W (ou rien).
  • le développement est constitué d'une suite (pouvant être vide) de paires (TT, TW, WW ou WT) et de fermetures (TTU ou WWU)
  • la fermeture finale est obligatoire (TTU ou WWU).

Ainsi, WWU et TTU sont des nœuds possibles (correspondant respectivement à un nœud de cravate oriental, et à un nœud où la cravate est mise comme une écharpe autour du cou...). Le nœud T.WW.WW.WWU (Windsor) correspond lui aussi parfaitement à cette description.

Ce schéma peut alors se traduire par un graphe, où les nœuds de cravates valides correspondent à un chemin débutant et terminant sur la case centrale :

Graphe_cravates

Avec un peu de théorie des graphes, on peut remarquer que le nombre de nœuds de 1ere espèce de longueur n et ne comportant qu'une seule fois l'opération U est de 2n-1. En se limitant à au plus 11 mouvements (nécéssaires pour Eldredge), on compte un total de 2048 nœuds de référence fondamentalement différents, auquels s'ajoutent les variantes comptant plusieurs fois l'opération U.

On peut alors les répartir en trois classes, selon la position finale de la cravate (CU, LU ou RU), les nœuds classiques recensés par Fink et Mao sont alors ceux de la première classe, (où la différence entre le nombre de W et de T est de 2 modulo 3).

2046_noeuds
Répartition des 2046 nœuds de référence (Le U final ne rentre pas de le décompte des mouvements)

Mais ces 2046 nœuds et leurs variantes ne représentent qu'une petite portion des 177 147 différents nœuds de cravate recensés. Il faut en effet ajouter toutes leurs variantes de fermetures pour obtenir les nœuds de seconde espèce. Les conditions d'existence de ces variantes s'appuient sur des considérations sur le nombre de W et T précédant les différentes fermetures U. A titre d'exemple, TTWTUU est une séquence valide de 2nde espèce, même si elle n'obéit pas au schéma présenté plus haut.

Au final, les 2046 nœuds engendrent 177 147 nœuds de cravate, ce qui est prodigieusement... beaucoup. Ce que la théorie ne dit cependant pas, c'est le caractère esthétique de chacun de ces nœuds, point qui avait été abordé par Fink et Mao. Du coup, il est aujourd'hui impossible de savoir si nous sommes passé à côté d'un nouage de cravate inédit mêlant élégance et originalité. En attendant, vous pouvez toujours tenter de reproduire l'un des nœuds obtenu à partir du générateur !


Sources :
D. Hirsch, M. L. Patterson, A. Sandberg, M.Vejdemo-Johansson, More tie than we though (d'où provient le dernier graphe)
M.Vejdemo-Johansson, Random tie knots
T. Fink, Encyclopedia of tie knot - donne la liste des 85 nœuds de Fink et Mao
T. Fink, Y. Mao, Designing tie knots by random walks (d'où provient la première illustration)

08 février 2014

[#] Just another Huffman tree

La nétiquette, c'est un ensemble de règles à suivre pour être un gentleman des internets, une charte implicite que tout le monde se devrait de suivre. Par exemple, dans son point 2.1.1 relatif aux bonnes règles d'usage du courrier électronique, la nétiquette requiert :

« Soyez conscient de la longueur des messages que vous envoyez. Annexer de grands fichiers, tels que des documents en Postscript ou des programmes, peut rendre vos messages si grands qu'ils peuvent ne pas être transmis ou au moins consommer une part exagérée de ressources. Une bonne règle sera de ne pas envoyer de fichier dépassant les 50 Ko. Comme alternative, réfléchissez au transfert de fichier, ou à découper le fichier en morceaux plus petits et à les envoyer séparément. » netiquette.fr

Il faut d'autant plus faire attention que 50 ko, c'est très vite atteint !... Bon, la nétiquette date de 1995, un temps où les modems 56k chantaient de la dubstep.
Mais il faut se souvenir qu'un gentleman n'envoie pas de fichier trop lourd à ses amis. Non, il commencera par le compresser à l'aide d'un logiciel adéquat, en s'assurant que son ami sache comment décompresser ce fichier.

Mais d'ailleurs, comment ça marche, la compression de fichiers ? De nombreuses méthodes existent aujourd'hui, mais la première d'entre toutes, c'est quand même la méthode de Huffman, qui n'a aujourd'hui rien perdu de sa superbe. En ce dimanche, parlons de Huffman et de ses arbres.

Saut ASCII
Je souhaite stocker, dans la mémoire de mon ordinateur, la phrase suivante « je ne suis qu'une phrase d'exemple mais j'ai quand même un cœur ». Et comme je suis exigent, je veux le faire de la façon la plus économique possible. Le gros problème, c'est que la seule chose qu'il est réellement possible de stocker dans la mémoire d'un ordinateur, ce sont des petits bouts d'information, des 0 et des 1 (les bits). Ma phrase d'exemple, elle, contient quand même 21 caractères différents, ce qui est sensiblement plus grand que 2.

Du coup, la première idée géniale est de regrouper les bits par groupe de 8 (les octets). Avec 8 bits, on peut fabriquer tout de même 256 nombres. Il suffit d'associer à chaque caractère un des 256 octets possibles, et le tour est joué.

On va dire que le « j » est codé par 01101010, que le « e » est codé par 01100101 ou que l'astérique est codé par 00101010 !

C'est ce que se sont dit dans les années 60 les créateurs de la convention de codage ASCII, histoire d'uniformiser tout ce qui prééxistait. Au final, le codage ASCII permet de coder 127 caractères, dont 95 caractères effectivement affichables, chacun codable sur 7 bits seulement, ce qui est bien suffisant pour les américains de l'époque. On se garde de côté le huitième bit de l'octet, il pourra nous servir à l'occasion.

La phrase « je ne suis qu'une phrase d'exemple mais j'ai quand même un cœur » se codera en ASCII (presque) par 

01101010 01100101 00100000 01101110 01100101 00100000 01110011 01110101 01101001 01110011 00100000 01110001 01110101 00100111 01110101 01101110 01100101 00100000 01110000 01101000 01110010 01100001 01110011 01100101 00100000 01100100 00100111 01100101 01111000 01100101 01101101 01110000 01101100 01100101 00100000 01101101 01100001 01101001 01110011 00100000 01101010 00100111 01100001 01101001 00100000 01110001 01110101 01100001 01101110 01100100 00100000 01101101 00111111 01101101 01100101 00100000 01110101 01101110 00100000 01100011 00111111 01110101 01110010

L'ASCII est cependant incapable de coder des caractères farfelus comme « ê » ou « œ ». Tant pis, ils auront été codé par 00111111 (« ? »).

Au final, avec ce codage, on s'en sort avec un texte codé sur 63 octets, soit 504 bits (ou 441 bits si on enlève tous les '0' inutiles au début de chaque octet). C'est quand même beaucoup. En plus, on s'est fait flouer, puisqu'on a perdu deux caractères essentiels à l'intégrité de la phrase.

Ce qui serait parfait, c'est de compresser cette série de bits, mais sans perdre aucune information sur la phrase.

De l'inégalité patente entre les caractères
La norme ASCII est profondément égalitariste : que l'on soit un caractère cool comme le « », une caractère fréquent comme le « e » et l'espace, ou un caractère inutile comme le «|», on est logé à la même enseigne, sur 8 bits. Une idée géniale, ça serait de coder sur peu de bits les caractères très utilisés, et sur plus de bits les caractères superflus.

C'est en fait le principe du code Morse : une lettre fréquente est codée par un signal rapide (le « e » est codé par « · »), alors qu'une lettre rare est codée par un signal plus long (« y » est codé par « — · — —») .

Faisons ça, toujours sur la même phrase d'exemple. L'espace et le « e » sont fréquent, on les code sur un seul bit ; le « x »  et le « c » sont rares, on les code sur 4 bits :

Code_pas_pratique

Ainsi codée, la phrase sera :

01110011 01000001 10010000 01000011 01010000 11011101 01110101 00011000 10101011 00001100 11000110 10110010 10000110 11110000 00100001 00001000 11010000 110

On s'en sort maintenant avec seulement 139 bits ! Le progrès est énorme ! Oui, mais... Comment on va décoder ça ? Les 4 premiers bits sont 0111, qui peuvent se traduire par « je », mais aussi par « na » ou par « _eee ». Impossible de trancher, on a fait tout ça pour rien.
Pour ne pas avoir ce soucis d'ambiguïté, il nous faut un "code préfixe" ; autrement dit, un système de codage binaire où le code d'un caractère ne doit pas pouvoir être prolongé de façon à former le code d'un autre caractère. Ainsi, si l'on décide que l'espace est codé par 0, le codage d'aucun autre caractère ne doit pouvoir commencer par zéro.

C'est sur ce principe que se base la norme UTF-8 (la norme de codage de caractère la plus utilisée) : un caractère sera codé sur un ou plusieurs octets. Si le premier octet commence par 0, c'est qu'il est codé sur un seul octet selon la norme ASCII, dans le cas contraire, le caractère est codé sur plusieurs octets, et il faut se référer à la base de donnée idoine.

Compression de Huffman
Il me faut donc un code préfixe pour coder « je ne suis qu'une phrase d'exemple mais j'ai quand même un cœur » en utilisant le minimum de bits. La construction d'un tel codage, on la doit à David Albert Huffman, qui a mis au point l'algorithme qui suit lors de sa thèse de doctorat en 1952.

Pour cela, on commence par trier par ordre croissant de présence les caractères qui nous intéressent :

etape0étape 0

Puis, on prend les deux arbres de plus petit poids (ici, « l » et « œ », chacun de poids 1), puis on les réunis de façon à former un arbre binaire, qui sera alors de poids 1+1 = 2. L'arbre ainsi formé est alors remis à sa place, selon l'ordre croissant des poids.

etape1étape 1

On poursuit le processus, en réunissant à chaque étape les deux caractères (ou arbres précédemment formés) de plus petit poids sous une même bannière, dont le poids est la somme des deux poids :

etape2
étape 2

etape3
étape 3

(...)

etape15
étape 12

Finalement, après 19 étapes, on obtient un arbre complet, où les feuilles sont les caractères que l'on cherchait à coder. Le code, il est tout trouvé : en partant du haut de l'arbre, on codera '0' si l'on descend à gauche, et '1' sinon.

♫ And all that I can see is just a yellow Huffman tree ♫

L'arbre codant / décodant

Ainsi, 001 codera « u » ou 01101 codera « j ». Par construction de l'arbre, les caractères les plus fréquents seront au plus prêt de la racine et demanderont une chaîne courte de bits, tandis que les caractères les plus rares seront codés par une chaîne plus longue.

Finalement, ma phrase initiale peut être codée sans aucune ambiguité (grâce à l'arbre) sur 249 bits (32 octets) par 

01101110 11110111 10111101 00010001 10101110 11000010 00000110 11110111 01111010 10101110 10011010 11011101 00100001 10010100 11010000 11110100 00110111 10001001 00011010 11101101 00001001 00011110 11000011 00110110 10011111 00001011 11000110 11100110 11111010 11001000 10010111 0

Cela représente tout de même un gain de 50% par rapport au codage ASCII. Il est d'ailleurs impossible de le coder sur moins de bit avec un code préfixe. merci Huffman !

Si je dois déchiffrer cette séquence de bits, il suffit de la lire en suivant l'arbre. Les premiers caractères étant 01101, ils ne peuvent que coder le « j ».

Bon, il a quand même un hic : si je compresse ma phrase et que je la garde telle quelle, j'aurai du mal à retrouver la phrase initiale si je ne garde pas l'arbre de décodage quelque part. L'arbre doit être rattaché au fichier pour qu'il puisse être décompressé, et cet arbre a un poids : au moins 40 octets !
Finalement, mon message compressé pèsera environ 52 octets, ce qui ne représente plus vraiment un énorme gain par rapport au poids du message initial (63 octets). On peut éviter ce problème en utilisant un arbre générique, spécifique à la langue du texte que l'on code (voir commentaires de l'aticle). Il n'y a alors plus besoin de transmettre l'arbre, mais la compression sera forcément moins importante.
Cependant, le surplus représenté par le codage de l'arbre devient négligeable dès que les fichiers deviennent imposant (à partir de quelques ko).

L'algorithme de Huffman est utilisé par la plupart des logiciel de compression (WinZip, 7-Zip, WinRar...), mais il est le plus souvent couplé à un algorithme de compression de type LZ, qui commence par chercher et éliminer les redondances dans le fichier que l'on cherche à compresser.

Je terminerai par un fait tout à fait intéressant qui n'a rien à voir avec le sujet de l'article. David Albert Huffman ne s'est pas intéressé qu'à la compression de données, il a aussi découvert des méthodes d'origami tout à fait inédites en marge de ses travaux de topologie. Le résultat est particulièrement élégant :

Un bel origami
Pavage origami, mis au point par Huffman.
Il est cependant déconseillé de le compresser.


Sources :
D.A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, l'article original de Huffman
E. Davis & friends, Reconstructing David Huffman's Origami Tessellations, d'où provient l'illustration de l'origami

Posté par El Jj à 10:00 - Commentaires [7]
Tags : , ,

19 janvier 2014

[#] 24 jours après le Big Bang

Devinette ! Complétez la suite logique suivante :

3
13
1113
3113
132113
...

Ok, tout le monde la connaît, celle-là. Le terme qui suit, c'est 1113122113, car il s'agit de la suite "look and say" (abrégée LS) inventée en 1987 par Conway : chaque terme de la suite s'obtient en lisant les chiffres du terme précédent. Ainsi, la ligne 3113 peut se lire "un '3' puis deux '1' puis un '3'", ce qui donne 132113.

On pourrait s'arrêter au simple constat "ok, elle est marrante ta suite logique, mais t'es gentil, je regarde le match, là". Mais je me dois d'en dire plus, puisque cette suite possède de nombreuses propriétés. La plus merveilleuse d'entre elle a été intitulée "théorème cosmologique" et, résumé par son auteur, nous apprend que "24 jours après le Big Bang, l'ensemble des éléments exotiques ont disparu" ! Il faut dire que derrière cette suite se cache John Conway, qui baptise toujours ses découvertes par des noms improbables, comme le jeu de la vie, les nombres surréels ou le jeu "Sprouts"...
J'avais déjà écrit un article sur ce sujet en 2007, il est temps de le réactualiser.

Évidemment, on peut changer de terme initial pour former d'autres suites LS, comme

3333
43
1413
11141113
...

Il y a également le cas particulier de la suite 22, qui donne :

22
22
22
22
...

Théorème du jour 1 & théorème du jour 2
Avant que vous me trouviez des contre-exemples, mettons nous d'accord sur une chose : le chiffre 0 n'existe pas, tout comme les nombres supérieurs à 9. Si jamais ils venaient à exister, on les écrira quand même avec un seul chiffre. Par exemple, la chaîne qui suivra 1111111111 n'est pas 101 mais ⁂1 (où ⁂ est le chiffre que je viens d'inventer pour désigner le nombre 10) :

1111111111
⁂1
1⁂11
111⁂21
311⁂1211
...

Quelques définitions : on appellera "graine" la chaîne initiale d'une suite LS. Tous les termes qui suivent sont ses descendants : on dira que le premier est âgé de 1 jour, le suivant de 2 jours, etc.
La graine d'une suite LS peut être aussi compliquée que l'on veut, le terme suivant répondra quand même à quelques propriétés.

Du coup, on peut énoncer le théorème du jour 1 : une chaîne âgée de 1 jour...

  • ne peut pas débuter par yxzx (où x, y et z désignent trois chiffres différents - ou pas), ni contenir une telle chaîne dans une position paire.
  • ne peut pas contenir le même chiffre répété 4 fois ou plus (conséquence de la propriété précédente)
  • ne peut pas contenir la chaîne xxxyyy

En conséquence du théorème du jour 1, on a le théorème du jour 2 : une chaîne âgée de 2 jours...

  • ne peut pas faire naître un nouveau 4 (ou tout autre chiffre supérieur)
  • ne peut pas contenir la chaîne 3x3

Il n'est fait aucune mention d'un théorème du jour 3, mais je reviendrai plus tard sur celui du jour 24.

Théorème de séparation
Le point central de la théorie des suites LS est l'idée qu'elles puissent se scinder, dans le sens où il arrive qu'à partir d'une certain étape, la partie gauche de la chaîne n'interfère plus avec la partie droite. Prenons par exemple la suite débutant par 42 :

4·2
14·12
1114·1112
3114·3112
...

D'après le théorème du jour 2, aucun nouveau '4' ne peut apparaître, en particulier à droite du chiffre '4' déjà présent. De ce fait, il ne peut y avoir que un seul '4' à une étape donnée, ce qui le transformera inexorablement en '14' à l'étape suivante, n'interférant pas sur les chiffres qui suivent. On notera par "·" cette scission. 

Il existe dix cas (et pas plus) dans lesquels une chaîne se scinde (c'est le théorème de séparation). Par exemple, une chaîne contenant ...XY... (avec X≥4 et Y≤3) se scindera sous la forme ...X·Y..., ce qui est le cas dans l'exemple précédent . De la même façon, une chaîne contenant ...2111... se scindera en ...2·111... (voir [1] si vous voulez la liste en détail).

Évidemment, les sous-chaînes obtenues peuvent elles aussi se scinder, donnant au fil des étapes de nombreuses sous-chaînes indépendantes.

Il existe alors des sous-chaînes qui ne peuvent pas se scinder : on les appelle les "éléments" (ou "atomes"). Parmi ces éléments, certains finissent inexorablement par apparaître, quelle que soit la graine de la suite (sauf si c'est 22). Ces éléments particuliers (les "éléments communs") sont au nombre de 92, si bien que Conway les a nommé à partir des 92 éléments chimiques existant naturellement, allant de l'hydrogène H1 = 22 jusqu'à l'uranium U92 = 3, en passant par exemple par le carbone C6 = 3113112211322112211213322112 (tous les éléments communs ne sont pas aussi simples que H1 ou U92). Puisque ces éléments ont la fâcheuse tendance à se désintégrer les uns en les autres, Conway les a baptisé "éléments audioactifs".

On ajoute à cette liste les deux éléments transuraniens Np93 et Nu94, les deux seuls éléments comprenant un chiffre supérieur à 3. De ce fait, ces deux éléments existent sous une infinité de versions (leurs "isotopes"), autant que de chiffre supérieur à 4 possibles.

Enfin, il existe une infinité d'éléments 'exotiques', comme 1, 2 ou 4443333444, qui ne peuvent pas apparaître en tant qu'atome après plusieurs étapes.

Du coup, on peut ranger ces 94 éléments communs et transuraniens dans leur tableau périodique :

Tableau périodique des éléments audioactifs

Le tableau périodique des 94 éléments audioactifs de Conway (click doit / ouvrir dans un nouvel onglet, pour voir en encore plus grand !)

A titre d'exemple, l'élément Sm62 = 311332 devient après un jour 13212312, qui se scinde sous la forme 132·12·312 = Pm61·Ca20.Zn30. : Du coup, on peut réécrire la suite de graine 311332 sous la forme suivante :

Sm62
Pm61·Ca20.Zn30
Nd60·K19·Cu29
Pr59·Ar18·Ni28
Ce58·Cl17·Zn30·Co27
...

Ainsi, si la graine de la suite est un élément commun ou transuranien, tous ses descendants seront uniquement composés d'éléments communs et transuraniens. D'ailleurs, si la graine est composée d'éléments communs et/ou transuraniens (et n'est pas H1 = 22), il arrivera tôt ou tard un descendant composé d'au moins une fois les 92 éléments (plus éventuellement des éléments transuraniens) !

L'ordre des éléments a été choisi de façon à ce qu'un élément n soit le descendant direct de l'élément n+1 . Ainsi, en partant d'une graine U92, on aura après 91 génération l'élément H1, au milieu de beaucoup d'autres. Il en fait 6 autres façons de ranger les 92 éléments en suivant cette règle, le tableau ci-dessus correspond à la liste originale dressée par Conway (voir [2] pour les détails).

Le théorème cosmologique
On arrive au théorème le plus important de la théorie des suites LS, le théorème cosmologique :

Quelle que soit la graine choisie, il arrivera une étape où les descendants seront composés uniquement d'éléments communs et transuraniques. Ceci arrivera en au plus 24 étapes !

Ce théorème prouve en particulier qu'un élément exotique ne pourra pas le rester éternellement. Par exemple, si on choisit la graine 1 (élément exotique), on fini par tomber (après 7 étapes) sur le composé Hf72·Sn50 :

1
11
21
1211
111221
312211
13112221
11132·13211 = Hf72·Sn50
311312·11131221 = Lu71·In49
...

La borne des 24 étapes est optimale, puisqu'il existe un élément exotique demandant les 24 jours pour se scinder en élément commun. Cet élément est 22333222114, découvert et baptisé Mathusalum par Mike Guy, collègue de Conway.

La démonstration de ce théorème est particulièrement difficile, si bien que Conway nous a fait le coup de la démonstration perdue. Du coup, la preuve complète la plus récente du théorème cosmologique date seulement de 2003, et, à l'image du théorème des quatre couleurs, comporte une grande partie de calcul informatique.

La constante de Conway
Entre deux termes consécutifs d'une suite LS (quelle que soit sa graine), le nombre de chiffres est en moyenne multiplié par λ = 1.303678... Autrement dit, en notant un le nombre de termes d'une suite LS, on a :

limite_suite_LS

Ce nombre n'est autre que l'unique solution réelle de l'équation

x71 - x69 - 2x68 - x67 + 2x66 + 2x65 + x64 - x63 - x62 - x61 - x60 - x59 +
2x58 + 5x57 + 3x56 - 2x55 - 10x54 - 3x53 - 2x52 + 6x51 + 6x50 + x49 + 9x48 - 3x47 +
- 7x46 - 8x45 - 8x44 + 10x43 + 6x42 + 8x41 - 5x40 - 12x39 + 7x38 - 7x37 + 7x36 + x35 +
- 3x34 + 10x33 + x32 - 6x31 - 2x30 - 10x29 - 3x28 + 2x27 + 9x26 - 3x25 + 14x24 - 8x23 +
- 7x21 + 9x20 + 3x19 - 4x18 - 10x17 - 7x16 + 12x15 + 7x14 + 2x13 - 12x12 - 4x11 +  
- 2x10 + 5x9 + x7 - 7x6 + 7x5 - 4x4 + 12x3 - 6x2 + 3x - 6 = 0

Il s'agit donc de la racine d'un polynôme de degré 71 ! (D'autant que le polynôme est irréductible, ce qui fait de λ l'un des nombres algébriques ayant le plus haut degré de toute la littérature mathématique)

Pour comprendre d'où sort ce polynôme, regardons plutôt la suite suivante, où chaque terme est obtenu à partir du précédent en transformant a en ab, et en transformant b en a :

b
a
ab
aba
abaab
abaababa
...

On peut remarquer que le nombre de caractères des termes de cette suite correspondent à (Fn), la suite de Fibonacci (1, 1, 2, 3, 5, 8, ...), où le rapport des termes consécutifs converge vers le nombre d'or φ :

limite_suite_Fibo

Une façon de démontrer ceci est de remarquer que le nombre an et bn de a et de b à la n-ième ligne de la suite vérifie :

matrice_Fibo

Dans une telle situation, on peut montrer (avec ce qu'il faut d'algèbre linéaire) que les rapports Fn+1/Fn convergent vers la plus grande valeur propre (en module) de la matrice (et indépendamment du terme initial), qui n'est autre φ. Autrement dit, ce rapport converge vers la plus grande racine du polynôme caractéristique de la matrice, qui est X² - X - 1.

Pour les suites LS, l'idée est la même, sauf que la matrice est un tantinet plus compliquée, puisqu'elle est de taille 92×92 ; mais sa plus grande valeur propre est effectivement λ. Voir [3] pour davantage de détails sur le calcul de la matrice et de son polynôme caractéristique.

 

Bref, la prochaine fois qu'un petit malin vous met au défi de compléter la suite de Conway, n'hésitez pas à lui dire que derrière cette bête devinette se cache un bestiaire chimico-mathématique étonnant et une complexité hallucinante !


Sources 
[1] Oscar Martin, Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA, dont l'introduction est très complète
[2] Henry Bottomley, Seven complete sequences for the Conway Look and Say elements
[3] Nathaniel Johnston, A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial
[4] John Conway, Weird and wonderful chemistry of audioactive decay



Fin »
Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 France.
ISSN 2270-129X