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 une 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 [5]
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

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

12 janvier 2014

[#] Ordre et désordre

Un dernier verre, peut-être ? Venez, ma mie, je vous invite pour un dernier chocolat chaud. Installez-vous sur le canapé, je reviens dans un instant. Ne faites pas attention à cette pile de papiers sur la table et faites comme si les affaires qui traînent par terre, c'est normal. Ignorez également la vaisselle entassée dans l'évier, toute comme cette casserole dans lequel il reste un fond de... euh... ce que j'ai mangé la semaine dernière. Comment ça, cet appartement est mal rangé ? Absolument pas ! D'ailleurs, le désordre total ne peut pas exister ! Ce n'est pas moi qui dit ça, c'est la théorie de Ramsey... Et n'allez pas croire que je me cache derrière les maths... Eh, revenez, je n'ai pas terminé le chocolat chaud !...

La théorie de Ramsey est la suivante : dans une structure contenant beaucoup d'éléments, on finit toujours par retrouver une propriété donnée. La question qui se pose alors, c'est la valeur numérique de ce "beaucoup", qui, pour certain exemple, peut être démesurément grand. On résume plus souvent la théorie de Ramsey par "le désordre total n'existe pas".

Le principe de base de la théorie de Ramsey est le principe des pigeons (alias principe des tiroirs de Dirichlet). Par exemple, à partir de combien de personnes peut-on être sûr d'en trouver deux possédant le même signe du zodiaque ? Puisqu'avec 12 personnes, on peut avoir le zodiaque au complet, la propriété "au moins deux personnes possèdent le même signe astrologique" devient vraie à partir de 13.

Théorème de Ramsey
Le problème central en théorie de Ramsey (et, de façon plus générale, en combinatoire) est celui du théorème de Ramsey. On présente souvent ce théorème par le célèbre problème des six amis.

Vous invitez un groupe d'amis pour une occasion quelconque (soirée foot à la télé, soirée puzzle ...). Parmi ces invités, certains se sont déjà rencontrés auparavent, d'autres se rencontrent pour la première fois. Mais à partir de combien d'invités peut-on être sûr qu'il y ait
- soit trois invités qui se connaissent deux à deux
- soit trois invités qui ne se connaissent pas deux à deux.
Ce nombre, on le notera R(3).

K5

Graphe de la situation.
Deux invités sont reliés par une arête bleue si ils se connaissent, en rouge sinon.
Pour 5 invités, il n'existe pas forcément de trio qui se connaissent ou qui ne se connaissent pas
Ce contre-exemple prouve R(3) ≥ 6.

La réponse est 6, et je peux le prouver ! On suppose que 6 invités sont là, et que David en fait partie (il y a toujours un David dans les invités). Parmi les 5 autres invités, soit il y en a 3 qui le connaissent, soit 3 ne le connaissent pas (par le principe des tiroirs). Sans pertes de généralité, on peut supposer que ces trois invités connaissent David, et qu'ils s'appellent respectivement Karen, Natalie et Billy. Deux possibilités alors : soit ces trois invités ne se connaissent pas (et on a notre trio gagnant), soit il y en a au moins deux qui se connaissent, et ils forment avec David le trio gagnant. CQFD.

Ce problème se reformule dans la théorie des graphes : si les arêtes d'un graphe complet d'ordre 6 sont colorés à l'aide deux couleurs, alors il existe un triangle unicolore.

Friends_strangers_graph

On peut lister l'ensemble des graphes bicolores complets à 6 noeuds.
Ils admettent tous un sous-graphe complet unicolore.

Mais le problème se généralise : combien faut-il réunir d'invités pour être sûr que, parmi eux, il existe un groupe de k invités se connaissant mutuellement, ou ne se connaissant pas du tout ? Ce que nous dit le théorème de Ramsey, c'est que ce nombre existe toujours. Ce que ne nous dit pas le théorème, c'est sa valeur exacte.

Pour k = 4, on peut montrer R(4) = 18, en raisonnant de façon similaire (en trouvant un graphe contre-exemple à 17 sommets, puis en montrant que cela marche bien dès que n=18).
Pour k = 5, les choses se compliquent. Tout ce que l'on sait dire aujourd'hui, c'est que R(5) est strictement compris entre 42 et 50.
Pour k = 6, cela empire : on ne sait pour l'instant dire qu'une seule chose, c'est que le nombre R(6) est quelque part entre 102 et 165...

A ce sujet, Erdõs a imaginé ce qu'il se passerait si une armée d'aliens belliqueux nous déclarait la guerre, à moins qu'on leur fournisse la valeur de R(5). Dans un tel cas, on pourrait mettre à profit l'ensemble des ordinateurs et des mathématiciens de la planète pour calculer ce nombre. Cependant, si ils nous réclamaient R(6), les ordinateurs et mathématiciens disponibles seraient plutôt réquisitionnés pour mettre au point une stratégie permettant de mettre hors d'état de nuire ces extraterrestres...

Le problème de la fin heureuse
Dès qu'un problème cherche le nombre minimal d'objets à réunir pour qu'une propriété soit vérifiée, on peut l'inclure dans la théorie de Ramsey. Un autre problème représentatif est le problème du Happy ending (parce que, à la fin, ils se marièrent et eurent beaucoup1 d'enfants). Ce théorème nous annonce que :

Etant donné (au moins) 5 points du plan (jamais alignés ni confondus),
il y existe toujours quatre points formant les sommets d'un quadrilatère convexe.

Un quadrilatère (ou n'importe quelle figure géométrique) est convexe quand il ne possède aucun creux. Par exemple, le quadrilatère rouge en dessous n'est pas convexe.

HappyEnding

A gauche : un exemple où 4 points ne forment pas un quadrilatère convexe.
A droite, plusieurs dispositions de 5 points. Dans tous les cas, il existe toujours (au moins) un quadrilatère convexe. L'enveloppe convexe des groupes de 5 points est représentée en jaune.

Pour démontrer ce fait, il suffit d'envisager tous les cas possibles, selon l'enveloppe convexe des 5 points (l'enveloppe convexe, c'est le polygone que l'on obtient quand on place un élastique autour de l'ensemble de ses points. Par essence, une enveloppe convexe est convexe).
- si l'enveloppe convexe est un pentagone, il suffit d'en retirer un point pour retrouver le quadrilatère tant cherché.
- si l'enveloppe convexe est un quadrilatère, inutile d'aller chercher plus loin
- si c'est un triangle, alors les deux points à l'intérieur forment un quadrilatère convexe avec au moins l'un des côté (avec le côté qui ne coupe pas la droite formée par les points intérieurs). CQFD.

Cette histoire de quadrilatère convexe est le problème original du happy ending, découvert et démontré en 1933 par Esther Klein. Elle demande alors a ses collègues si l'un d'eux a une idée pour généraliser la question : étant donné un grand nombre de points, y existe-t-il toujours un pentagone/hexagone/n-gone convexe. George Szekeres revient une semaine plus tard avec sa réponse : oui !

Théorème de Erdös-Szekeres : Étant donné un ensemble suffisamment grand de points du plan (jamais alignés ni confondus), il y existe toujours N points formant les sommets d'un polygone convexe.

HappyEnding5
9 points suffisent pour y trouver un pentagone convexe

Si Erdös a accolé son nom a celui de Szekeres, c'est qu'il a pas mal étudié la question lui aussi. C'est d'ailleurs Erdos qui a surnommé ce théorème "happy ending" en 1937, puisque c'est celui-ci qui a mené Esther Klein et George Szekeres à se marier en 1937 !

On peut être un peu plus précis sur la valeur de "suffisamment grand" :
- si on cherche les triangles convexes, 3 points suffisent (puisqu'on les suppose ni alignés, ni confondus)
- si on cherche les quadrilatères convexes, 5 points suffisent.
- si on cherche les pentagones convexes, il faut au moins 9 points.
- si on cherche des hexagones convexes, c'est 17 points qu'il est suffisant d'avoir. Ceci n'a été démontré qu'en 2006 (Szekeres, Peters)
- pour les polygones plus grand, rien n'est encore sûr. On sait qu'il faut au moins 1+2N-2 points pour y trouver à coup sûr un N-gone convexe, on conjecture que cette borne est optimale.

Le problème du polygone vide
Le théorème de Erdös-Szekeres serait encore plus élégant si, en plus d'être convexe, le polygone pouvait être vide (aucun point à l'intérieur). Pour 5 points, pour peu que l'on modifie légèrement la démonstration, on peut montrer qu'il existe toujours un quadrilatère convexe vide. Pour 9 points, il n'existe pas forcément de pentagone convexe vide, mais il suffit de 10 points pour rendre cette assertion vraie. Mais existe-t-il toujours un hexagone convexe vide dans un ensemble assez grand de points ?

La réponse est oui, mais il a fallu attendre 2007 pour en être sûr. Le nombre exact de points suffisant n'est pas connu exactement, mais on sait quand même qu'avec 463 points, on est sûr d'avoir un hexagone convexe vide.

HexagoneCache

463 points au hasard. Il y existe forcément (au moins) un hexagone convexe vide
Avec moins de 463 points, rien n'est sûr...

Je prèfère ne pas trop évoquer le cas de l'heptagone convexe vide, puisqu'il contredit la théorie de Ramsey : même avec un nombre arbitrairement grand de points, on ne peut pas être sûr d'y trouver d'heptagone convexe vide...

Le nombre de Graham
Un dernière exemple de problème de la théorie de Ramsey, le problème de Graham :

Considérons un hypercube de dimension n où chaque arête et diagonale est coloré en rouge ou en bleu.
Y existe-t-il toujours un plan unicolore défini par 4 sommets coplanaires ?
Si non, à partir de quelle dimension n est-ce toujours vraie ?

Exemple, avec n = 3. On a donc un cube (on ne peut plus classique, en 3D), on colore en rouge/bleu ses 28 arêtes et diagonales. Parfois, on peut y trouver un plan unicolore :

GrahamCube

Et parfois, non :

GrahamCube2
Impossible de trouver un plan unicolore passant par 4 points dans ce cube

A partir de quelle dimension peut-on être sûr d'en trouver ? Les spécialistes conjecturent qu'il suffit de chercher dans un hypercube de dimension 13. Mais entre ce que l'on conjecture et ce qu'on l'on arrive à démontrer il y a un gouffre, ce problème en est le plus gros exemple. Ce que Graham est parvenu à démontrer, c'est que la dimension recherchée est un nombre grand. Très grand. Ce nombre est tellement grand que je ne peux l'écrire sur ce blog. Je ne peux même pas écrire le nombre de chiffres qui le compose, pas plus que le nombre de chiffres qui compose son nombre de chiffresCe nombre est tellement grand que si je l'utilise dans une blague de "ta mère", on pourrait penser que j'exagère un peu. A l'heure d'aujourd'hui, cette borne supérieure reste la pire qui existe de toute l'histoire des démonstrations mathématiques. Et pourtant, grâce à cette démonstration, on peut quand même dire qu'il est vrai que la propriété de Graham est vraie en grandes dimensions...

Ce nombre N*, c'est le 64e terme de la suite
u1 = 4
u2 = 3 ↑ 3
u3 = 3  3 3
... où n désigne la flèche (itérée n fois) de Knuth (voir ce vieil article)

Certaines personnes ont du mal à penser en dimension 3, la plupart des gens sont incapable de penser en dimension 4. Il ne me semble pas que quiconque sur Terre soit capable de réfléchir en dimension N*. 


Sources :
Une démonstration du calcul de R(4)
, et plein d'autres articles intéressants sur cut-the-knot
Colorie-moi le ciel, qui parle aussi du théorème de Ramsey infini
Le désordre total n'existe pas..., Pour la Science N°376 - fevrier 2009

Images :
Friends strangers graph


1 : Encore une fois, la théorie de Ramsey ne nous donne pas la valeur exacte de ce "beaucoup".

05 janvier 2014

[#] 2013+1 (Cette nouvelle année est-elle intéressante ? Episode 05)

Nous venons de changer d'année, et, comme en chaque nouvelle année, je ne peux pas résister à l'envie de passer en revue les différentes propriétés (in)intéressantes du nombre de l'année.

Pour savoir si un nombre est intéressant, l'instrument de mesure officiel est l'OEIS, l'encyclopédie en ligne des suites entières. Plus un nombre apparaît sur l'OEIS, plus il est intéressant. A titre d'exemple, 2011 possédait 378 propriétés et était, ce ce fait, un nombre particulièrement intéressant (il faut dire que c'était un nombre premier, une vertu qui se fait de plus en plus rare chez les nombres). Les années 2012 et 2013 possèdent respectivement 121 propriétés et 96 propriétés, ce qui font d'elles des années bien moins intéressantes.

Et 2014, dans tout ça ? Eh bien... Comment dire ?... Il va falloir faire avec... C'est la crise pour tout le monde, hein ?...

2014 possède seulement 76 propriétés !

Ce n'est pas encore cette année que la courbe des propriétés va s'inverser. Mais j'ai cru comprendre que le changement, c'est l'année prochaine. Voyons tout de même ce que le nombre 2014 a à nous offrir.

Excursions de Motzkin [A057585]
Le n-ième nombre de Motzkin (noté Mn), c'est le nombre de façons de placer des cordes non concourantes sur un cercle, entre n points [A001006].

Par exemple, M4 = 9 : il y a 9 façons de dessiner des cordes qui ne se croisent pas entre 4 points d'un cercle :

Motzkin

En cherchant à la main, on peut voir que M1 = 1, M2 = 2, M3 = 4 et que M4 = 9.

Pour calculer les nombre suivants, il faut réfléchir de manière un peu plus récursive. Supposons que l'on vient de calculer Mn, et cherchons Mn+1. Combien y a-t-il de façons de placer des cordes entre ces n+1 points ?
Déjà, il y en a au moins Mn (il suffit d'ignorer ce n+1-ième point que l'on vient d'ajouter.
Maintenant, prenons en compte ce nouveau point, et reliant-le à l'un des autres points, disons qu'il s'agit du k-ième (n choix possibles). Cette corde sépare le cercle en deux morceaux, l'un comptant k-1 points (donc Mk-1 façons d'y placer des cordes), l'autre en comptant en comptant n-k (et donc, Mn-k placements de cordes possibles). Cette séparation offre donc Mk-1×Mn-k façons de placer les cordes.

Schema_Motzkin
La corde [n+1;k] sépare le cercle en deux zones, l'une comptant k-1 points, l'autre n-k.
Il y a donc Mk-1×Mn-k placements comptant cette corde.

Si on fait le compte, il y a Mn placements qui ne prennent pas en compte le n+1 points, et, pour chaque point k entre le 1er et le n-ième, il y a  Mk-1×Mn-k placements comprenant la corde [n+1 ; k]. Donc :

FormuleMotzkin

A l'aide de cette formule, on peut calculer que M5 = 21, M6 = 51, M7 = 127, M8 = 323, M9 = 835 et que M10 = 2188. Non, 2014 n'est pas un nombre de Motzkin (mais on y arrive...)

Mais il existe d'autres façons d'intérpréter les nombres de Motzkin, en particulier, celle des chemins de Motzkin : un chemin qui peut monter, descendre ou aller tout droit, et qui revient à sa hauteur de départ. Le nombre de chemins de Motzkin de longueur n est donné par Mn. Ainsi, il existe 9 chemins de Motzkin de longueur 4 :

CheminMotzkin
9 chemins de Motzkin de longueur 4, autant que de cercles de Motzkin.

On peut obtenir un chemin de Motzkin à partir d'un cercle cordé en le parcourant dans l'ordre de ses points. Un début de corde se traduira par un chemin montant, une fin de corde se traduit par un chemin descendant.

Chemin_8
Exemple de placements de corde sur un cercle à 8 points, et son chemin de Motzkin de longueur 8 correspondant.

La question primordiale qui se pose alors : quid de l'aire sous les chemins de Motzkin ? Pour n=4, on peut compter que A4 = 16. Mais pour n plus grand ? On peut montrer (la démonstration en question a été coupée au montage de cet article) que l'aire totale An sous les chemins de longueur n est donnée par la formule :

FormuleMotzkin2

On peut calculer que A5 = 56, A6 = 190, A7 = 624 et A8 = 2014.

Bref : l'aire totale sous les 323 chemins de Motkin est 2014 ! (Tout ça pour ça...) Et c'est a peu près la seule propriété qui vaut la peine d'être développée parmi tout ce que l'OEIS a à nous proposer.

Mais 2014 a de nombreuses autres propriétés intéressantes :

  • 2014 correspond à la somme de 12 nombres triangulaires (nombres de la forme T(N)=1+2+3+...+N), en commençant par le 12e : 2014 = T(12) + T(13) + ... + T(23). [A119034
  • 2014 est de la forme n(n+15) : 2014 = 38×(38+15). [A132760]
  • Ma préférée : 2014 = 133 - 132 - 131 - 130.[A083074]
  • 5 × 22014-1 est un nombre premier. [A001770]
  • 2014 peut-être écrit comme la somme de plusieurs carrés impairs distincts de 89 façons différentes, c'est plus que pour n'importe quel nombre plus petit. [A167702]
  • Il y a 2014 4-uplets (a,b,c,d), où 1 ≤ a,b,c,d ≤ 7, tels que ab+cd ≤ 49. [A212150]
  • Les 2014e nombre dodécahédral peut s'écrire comme la somme de deux nombres dodécahédraux. C'est plutôt rare ! [A053017]
  • Le numérateur du 4028e (=2*2014) nombre de Bernoulli est divisible par 233. J'ai du mal à comprendre pourquoi cette liste existe... [A092228]
  • Et c'est à peu près tout...

Du côté des propriétés qui trainent sur Twitter aux alentours du premier janvier, on a :

  • 1024 + 512 + 256 + 128 + 64 + 16 + 8 + 4 + 2 = 2014 (@mikko)
  • (10 + 9 ) × ((8×7) + 6 - 5 - 4) × (3 - 2 + 1 + 0) = 2014 (@alexbello)

Bref : bonne année 2014 !

Et la santé !

01 décembre 2013

[#] Calendrier de l'avent

Et pourquoi pas un calendrier de l'avent, en attendant petit papa Noël ? A la manière des Shots of science, un nouvel instantané mathématique sera ajouté tous les jours dans cet article, histoire de frimer à la machine à café  (pour peu que vous ayez des collègues compréhensifs...)

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

24 novembre 2013

[#] Bézout futé

Le théorème de Bézout n'est pas qu'un théorème d'arithmétique vu en Terminale, c'est aussi un des principaux résultats de la géométrie algébrique. Ce qui est chouette avec ce résultat, c'est qu'il est manifestement faux au premier abord, mais qu'il devient particulièrement satisfaisant quand on s'y penche un peu. Je ne vais pas le creuser dans cet article, simplement déblayer le terrain. En quelques mots, il dit que :

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection.

Une courbe algébrique, c'est une courbe dont l'équation est un polynôme (que l'on peut écrire sous la forme P(x,y)=0, comme par exemple 3x36y6+4x²y-1=0). Le degré de la courbe, c'est le degré du polynôme. Globalement, les courbes algébriques, c'est ce qui se fait de plus joli en matière de courbes.

A titre d'exemple, les courbes algébriques de degré 1 sont les droites (ax + by + c = 0), celles de degré 2 sont les coniques (paraboles, hyperboles, ellipses...). Plus on grimpe en dégré, plus les courbes sont compliquées à appréhender.

Vous avez échappé à des cubiques de tous horizons, faute de place.

Quelques exemples de courbes algébriques de degré 1 et 2.

Ainsi, d'après le théorème de Bézout, deux droites (degré 1) se coupent toujours en un (=1×1) seul point, deux coniques (degré 2) se coupent toujours en 4 (=2×2) points, une droite (degré 1) coupe toujours une cubique (degré 3) en exactement 3 (=1×3) points...

Jusqu ici, tout va bien (Sophia Aram)

A gauche, l'intersection d'un cercle (degré 2) et d'une cubique de Humbert (degré 3) donne 6 points d'intersection
A droite, l'intersection de deux cubiques (de degré 3) donne 9 points d'intersection

Mais ça, c'est ce qu'il se passe dans un monde parfait. Les contre-exemples sont malheureusement légion :

En général, on se contente d un seul contre-exemple. Quand on en a besoin de quatre, c est que l on cherche à compenser quelque chose.

Quatre contre-exemples au théorème de Bézout.

Et pourtant, dans chaque cas, le nombre de points annoncé est bien le bon. Il y a cependant de nombreuses subtilités...

Sauf que... la multiplicité
Dans certains cas, un même point d'intersection comptera plusieurs fois (on parle de la multiplicité de ce point d'intersection). C'est injuste, mais il faut faire avec. Cette situation peut arriver sous plusieurs formes différentes.

Déjà, il y a les courbes qui s'auto-intersectent. C'est par exemple le cas de la cubique x3 - 3x² + y² = 0 (représentée dans le premier contre-exemple), dont la courbe forme une boucle. Au point (0,0), la courbe s'auto-coupe, ce point là sera donc compté deux fois s'il intervient dans une intersection.

On pourrait surement faire une version algébrique du Scrabble, dans lequel les points compteraient double...

Le point (0,0) appartient à la fois à l'arc vert et à l'arc jaune, il sera donc compté deux fois, ce qui donne bien trois points d'intersection.
Remarquons que si on déplace un peu la droite bleue, on retrouve trois vrais points d'intersection.

Lorsque les courbes se touchent sans se croiser, on tombe aussi sur des points comptés double (voire pire). En particulier, c'est ce qui se passe lorsque l'on compte le nombre de point d'intersection entre une courbe et l'une de ses tangentes. 

Ca serait un scrabble où, au lieu de jouer des lettres, on jourait des polynômes !... Non, ça semble définitivement être une mauvaise idée.

La droite bleue est tangente à la courbe rouge au point (2,2), ce point d'intersection comptera double.
En déplaçant un peu la droite, on peut faire apparaître ces deux points.

Le théorème de Bézout est en fait:

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection, comptés avec leur multiplicité.

Sauf que... les nombres complexes
Le problème de la représentation graphique des courbes algébriques, c'est qu'elles ne sont que la partie émergée de l'iceberg. Rien n'oblige les courbes à se croiser dans le plan réel, les points d'intersection peuvent parfaitement être complexes. Et cette situation arrive bien trop souvent pour être négligée.

On peut reprendre l'exemple des points d'intersection de la parabole d'équation y-x²=0 et de l'ellipse d'équation x²+2y²-y-2=0. Les points (-1;1) et (1;1) sont solutions, mais les points (i;-1) et (-i;-1) aussi (vérifiez par le calcul si vous ne me croyez pas !). On a bien les quatre points attendus.

DesCourbesComplexes

En comptant les points à coordonnées complexes, on a bien 4 points d'intersection.

Le théorème de Bézout est en fait :

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection dans le plan complexe ℂ² , comptés avec leur multiplicité.

Sauf que... les points à l'infini
Où se coupent deux droites parallèles ? Eh bien, elles se croisent... à l'infini ! Pour le voir, il suffit de pencher un peu la caméra pour regarder ce qu'il se passe au loin. En faisant cela, on fait apparaître la ligne d'horizon, où se rencontrent toutes les droites parallèles.

Là où toutes les droites se croisent...

A gauche : deux droites parallèles, vu de dessus
A droite : deux droites parallèles, vu de biais

Ces deux droites, courbes algébriques de degré 1, possèdent donc bien un unique point d'intersection, mais il est "à l'infini". Ce point d'intersection n'est pas dans le plan, mais dans le plan projectif, où l'on a ajouté tous les points à l'infini (chaque point à l'infini correspond à une direction de droite).

De la même façon, on peut voir que la droite et la parabole du premier exemple possèdent bien deux points d'intersection, dont un à l'infini :

Après 3 heures de réflexion, j ai enfin réussi à dessiner ce f$#$* plan projectif !

En penchant la caméra, la parabole devient une ellipse, faisant apparaître un deuxième point d'intersection à l'infini. On peut en fait démontrer que n'importe quelle conique est une ellipse, pourvu qu'on la regarde sous le bon angle.

C'est aussi ce qui arrive lorsque deux courbes sont asymptotes l'une à l'autre : elle se croisent sur la ligne de l'infini (et en plus, le point d'intersection sera de multiplicité 2 ou plus).

Le théorème de Bézout est en fait :

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection dans le plan projectif complexe P2(ℂ) , comptés avec leur multiplicité.

Sauf que... des composantes communes
Un dernier point à vérifier pour que le théorème fonctionne parfaitement : il ne faut pas que les courbes aient des composantes communes.

Par exemple, prenons les courbes (de degré 2) d'équation x² - 1 = 0 et xy-x-y+1=0. Selon Bézout, ces courbes devraient avoir 4 points en commun. En réalité, ces courbes ont une infinité de points d'intersection :

Non, ces courbes ne sont pas vraiment intéressantes.
Les deux courbes ont une composante commune, la droite verticale d'équation x=1, qui correspond donc à une infinité de points en commun.

Le problème, c'est que les courbes en question peuvent être écrites comme la réunion de courbes de degré plus petit (des composantes irréductibles). La première est la réunion des droites d'équation x-1=0 et x+1=0, la deuxième est la réunion des droites d'équation x-1=0 et y-1=0. Les deux courbes ont une même composante commune (x-1=0), et le théorème de Bézout n'est pas prévu pour ça.

Le théorème de Bézout est en fait :

Deux courbes algébriques sans composantes communes de degré n et p ont exactement n×p points d'intersection dans le plan projectif complexe P2(ℂ) , comptés avec leur multiplicité.

Maintenant, on peut appliquer le théorème, et jouer au jeu pratiqué dans le cercle très fermé des géomètres algébristes : "où sont passés les points d'intersection manquant ?!".

Par exemple, combien de points d'intersection possèdent ce quadrifolim (en bleu), de degré 6, et ce trifolium (en rouge), de degré 4 ?

Oui, j ai piqué cette image sur wikipédia. Mais on a rarement de si joli points de multiplicité 14.

A première vue, on compte 5 points d'intersection, mais il y en a en fait 24 :
4 points réels, de multiplicité 1
1 point réel, de multiplicité 14
2 points complexes à l'infini (les deux à la fois !), de multiplicité 3

(Et joyeux anniversaire à ce blog, qui vient de fêter ses 7 ans !)


A lire également :
Bézout et les intersections de courbes algébriques, sur BibNum, analyse de Liliane Alfonsi du texte original de Bézout.



  1  2  3  4  5    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.