28 décembre 2014

Deux minutes pour le duc de Densmore

Cette vidéo ne contient aucun 42 et c'est une honte !

Ce sont les fêtes de Noël ! Quoi de mieux qu'une enquête policière sur fond de théorie des graphes ? !


Sources :
Qui a tué le duc de Densmore, Claude Berge, à lire à partir de la page 77

Posté par El Jj à 11:09 - Commentaires [0] - Permalien [#]
Tags : , ,


30 novembre 2014

Deux minutes pour les maisons de Dudeney

Water_gaz_electricity_Dudeney

Nouvel épisode de "deux minutes pour", où il est cette fois-ci question de problèmes de voisinages à SimCity...

 Et bon anniversaire à ce blog qui vient de souffler sa huitième bougie !

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

09 novembre 2014

NP Entertainment System

Super Mario Bros : The Lost Levels est un jeu très difficile, tous les joueurs qui l'ont testé le savent. Mais ce qu'une bande de mathématiciens / informaticiens (G. Aloupis, E. D. Demaine, A. Guo et G. Viglietta) ont démontré en février 2014 dans un article d'une trentaine de pages, c'est que c'est plus qu'un jeu difficile : c'est un jeu... NP-difficile ! Et ce n'est pas le seul : la plupart des jeux de la série des Mario, Zelda, Donkey Kong, Metroid et Pokémon sont eux aussi NP-difficile. Candy Crush aussi, d'ailleurs, mais cela n'a aucun rapport.
Il n'est pas vraiment ici question de la difficulté de ces jeux en elle-même, mais plutôt de la complexité des puzzles qu'il est possible de générer avec le moteur de ces jeux.

En informatique, une question de type Oui/Non peut être plus ou moins complexe : plus un problème est complexe, plus les algorithmes permettant de les résoudre seront long à être exécutés. Il existe tout un bestiaire de classes de complexités, les principales étant les classes P et NP (bien que l'on ne sache pas réellement si ces deux classes sont distinctes ou non, mais c'est un autre problème). 
D'un côté, donc, il y a les problèmes P (polynomiaux), ceux qui sont faciles et rapides à résoudre. Par exemple, savoir si une liste est triée est un problème facile : si il me faut 21 secondes pour vérifier qu'une liste donnée de mots est rangée par ordre alphabétique, il m'en faudra 42 pour vérifier qu'une liste 2 fois plus grande l'est. Le temps de cette vérification est ici proportionnel à la taille des données qui rentrent en jeu, et c'est en cela que l'on peut dire que ce problème est facile. De manière plus globale, un problème est "facile" si le temps nécessaire pour y répondre est une fonction polynomiale de la taille des données.
De l'autre côté, il y a les problèmes NP qui ne sont pas P (Non déterministe en temps polynomial), ceux qui sont dans les grandes lignes difficiles et longs à résoudre. Par exemple, savoir s'il est possible de relier les 6 plus grandes villes de France en moins de 30 heures demandera 20 secondes de calculs, tandis que savoir si on peut relier les 12 plus grandes villes en moins de 60h prendra 5 jours de calculs, et c'est encore pire si le nombre de villes augmente. Le temps n'est pas du tout proportionnel à la taille des données impliquées ! Un problème est donc "difficile" si le temps nécessaire pour répondre "non" n'est pas une fonction polynomiale de la taille des données (mais qu'il peut quand même être résolu de manière polynomiale si l'algorithme utilise un générateur de hasard).

Ce qui est NP-difficile chez les jeux classiques de Nintendo, c'est de savoir si, dans une carte d'un Mario ou d'un Pokémon généralisé, il est toujours possible d'aller d'un point A à un point B en respectant les règles de ce jeu. Et on va le prouver, en montrant que dans tous les jeux Nintendo se cache en fait un problème 3-SAT !

Le problème 3-SAT
Le problème SAT est un problème de classe NP. S'il ne devait en rester qu'un, ça serait celui-là. Pour montrer qu'un problème est NP-difficile, le meilleur moins de procéder est bien souvent de montrer qu'il peut être ramené à ce problème. Le problème SAT est le suivant :

Étant donné une forme normale conjonctive, est-il possible d'assigner des valeurs booléennes à ses variables qui la rende logiquement vraie ?

Détaillons un peu. Si on dispose de plusieurs variables booléennes ("Vrai" ou "Faux") A, B, C et D, une forme normale conjonctive est une expression construite avec ces variables (ou leur négation) composée de parenthèses de "ou" entrecoupées de "et". L'expression suivante

(A ou B ou ¬D) et (¬A ou ¬C ou ¬D) et (A ou C ou D) et (¬A ou B ou ¬C) et (B ou ¬C ou ¬D)

est un exemple de forme normale conjonctive. Celle-ci est constituée 4 variables, de 5 clauses et de 3 variables par clauses. La question qui se pose alors est de savoir si il est possible de déterminer des valeurs logiques pour chacune des 4 variables qui rendent l'expression vraie.
Dans ce cas, c'est effectivement possible, en prenant par exemple les variables A=Vrai, B=Vrai et C=Faux et D=Faux, car chacune des 5 clauses de la FNC sont vérifiées. Mais pour aboutir à cette solution, la façon la plus simple de procéder reste encore d'essayer les 16 combinaisons possibles jusqu'à tomber sur une solution qui fonctionne. Mais lorsque le nombre de variables augmente, le nombre de combinaisons explose, et c'est pour cela que le problème SAT est (NP-)difficile !
Puisqu'il a été démontré que le problème SAT est équivalent au problème 3-SAT (cas où chaque clause ne contient que 3 variables), c'est ce problème particulier qui va nous intéresser.

Pour démontrer que les jeux Nintendo sont NP-difficiles, il faut donc montrer que certains niveaux de Metroid ou de Zelda peut être ramenés à l'assignation de variables d'une forme normale conjonctive. Prenons l'exemple de la forme normale conjonctive suivante

FNC = (A ou ¬B ou C) et (¬A ou B ou C) et (A ou ¬B ou ¬C)

Pour transformer ce problème 3-SAT en niveau de Zelda, il faut que le level design oblige Link à résoudre ce problème de logique. Pour cela, on va simuler au sein du jeu l'assignation des variables, ainsi que la vérification des clauses en fonction des variables rentrées.
Dans un premier temps, notre avatar passera successivement, et sans possibilité de retour en arrière, par trois modules d'assignation de variables (autant que de variables). Chacun de ces modules consiste à choisir un chemin, celui-ci correspond à donner une valeur logique (Vrai/Faux) à chacune des variables A, B et C. Lorsqu'une valeur "Vrai" ou "Faux" est choisie pour une variable, elle donne accès aux modules de clauses correspondant (par exemple, choisir "Vrai" pour la variable A donne un accès aux clauses (A ou ¬B ou C) et (A ou ¬B ou ¬C), car c'est une valeur qui valide ces clauses). Ces modules de clauses, si ils sont tous visités au moins une fois, ouvrent l'accès final à l'arrivée. Résoudre le problème 3-SAT consiste donc à trouver le chemin qui permet d'ouvrir ce chemin final.

Schéma modules

Schéma de la carte qui permettra de résoudre le problème 3-SAT ci-dessus.
En vert les modules de départ/arrivée, en bleu les modules d'assignation des variables et en rouge les modules de vérification des clauses.
Les chemins noirs correspondent à des chemins que l'on peut passer que dans un seul sens, les chemins rouges peuvent être traversés dans les deux sens. Il ne doit être à aucun moment possible de sortir de ces chemins.
La sortie V du module variable A donne seulement accès aux entrées A, lorsqu'elles existent, des modules de clauses, ainsi qu'à une entrée sans retour possible dans le module variable B.

Ainsi, il faudra construire pour chacun des jeux les modules correspondant aux différentes étapes logiques:

  • Module d'assignation des variable
  • Module de clause

Ainsi que des modules qui permettent de mettre en place le schéma au sein du jeu :

  • Module de départ / d'arrivée
  • Module de carrefour, qui empêche de passer d'un chemin à un autre lorsque deux chemins différents se croisent
  • Module de chemin à sens unique

La saga The Legend of Zelda est NP-difficile !
Commençons par la saga The Legend of Zelda ! Dans cette série, on incarne Link, héros vêtu du vert, qui s'attelle épisode après épisode à sauver la princesse Zelda des griffes de génies démoniaques. Pour l'aider dans sa quête, il dispose d'un arsenal d'objets variant en fonction des jeux, comme des bombes, un boomerang, un marteau ou un masque permettant de danser comme Kamaro. L'un des objets emblématique de la série est le grappin qui permet à Link d'atteindre des zones inatteignables, et c'est cet objet qui nous permettra de montrer que le jeu est NP-difficile !

Ce n'est pas vraiment du jeu The Legend of Zelda que parle le théorème de Aloupis, mais de sa version généralisée. Dans cette version, les cartes peuvent être arbitrairement grande, tout comme la mémoire de la SNES qui la ferait tourner. Elle garde cependant les caractéristiques du jeu original : même comportement des ennemis, des décors et des objets, même gameplay, etc. Le théorème de Aloupis énonce donc :

Dans le jeu The Legend of Zelda : A Link to the past généralisé, déterminer si il est possible d'atteindre un point donné depuis un autre point donné est un problème NP-difficile.

On va commencer par le démontrer dans la version généralisé de The Legend of Zelda: A Link to the Past pour une raison assez simple : c'est le meilleur épisode de la série. Seuls deux éléments du gameplay nous seront utile dans la démonstration :

  • Link est capable de pousser certaines pierres (mais ne peut pas les tirer)
  • A l'aide du grappin, Link peut rejoindre une plate-forme contenant un coffre, dans le cas où aucun obstacle se trouve dans sa trajectoire. Il peut aussi s'agriper aux pierres.

On supposera alors que Link ne dispose d'aucun autre objet que le grappin (en particulier, qu'il ne possède aucun objet lui permettant de sauter).

Module de départ / d'arrivée :
Pas de problème pour cela : on supposera que Link entre dans la salle depuis une porte, et cherche à atteindre l'autre porte. On veillera cependant à placer un sol destructible au début de la pièce, puisque si Link tombe dans un précipice, il serait téléporté en début de salle.

Module d'assignation des variables :
Pour chacune des variables du problème SAT correspondant, Link doit choisir une valeur logique Vrai ou Faux. Pour modéliser cela, on oblige Link a devoir choisir entre deux chemins qui s'offre à lui, sans possibilité de retour en arrière, et c'est le grappin qui permet cela :

Zelda_assignation_variable
Module d'assignation de variable :
Link arrive en haut, et doit choisir, grâce au grappin, l'un des deux chemins proposés
Le chemin de gauche correspondra à l'assignation Vrai, le chemin de droite à l'assignation Faux.

Ce module donne également une façon de construire le module de passage à sens unique, en plaçant un coffre de l'autre côté d'un précipice.

Module de clauses :
Avant de pouvoir accéder à la porte finale, Link doit avoir ouvert le passage pour chacun des modules de clauses. Chacun de ces modules doit avoir été visité au moins une fois par Link pendant la phase d'assignation des variables, avant de procéder à la vérification finale.

Zelda_clause
Module de clause :
Link entre dans ce module par la droite, et doit atteindre la sortie à gauche.
Pour passer, il faut que (au moins) l'une des pierres ait été poussée, afin qu'elle puisse être atteinte à l'aide du grappin.
Chaque pierre correspond à l'une des trois variables de la clause concernée, les chemins y menant étant reliés à leur variable correspondante.

Module de carrefour :
Les chemins se croisent souvent, et il ne faut pas que Link puisse passer d'un chemin à un autre. Encore une fois, le grappin permet de construire de tels croisements :

Zelda_carrefour
Module de carrefour :
Si Link entre à l'ouest, il ne peut que ressortir à l'est, grâce au grappin. Et inversement.

Maintenant que l'on dispose de tous ces modules, on peut fabriquer un donjon pour The Legend of Zelda: A Link to the Past arbitrairement difficile, au sens de la complexité. CQFD !

Un petit exemple pour montrer à quel point cette construction est horrible, avec la FNC donnée plus haut en exemple :  (A ou ¬B ou C) et (¬A ou B ou C) et (A ou ¬B ou ¬C) :

Zeldaaaaaaah
Le plan du donjon correspondant à la FNC : (A ou ¬B ou C) et (¬A ou B ou C) et (A ou ¬B ou ¬C)
Terminer cette salle est équivalent à résoudre le problème NP-difficile 3-SAT correspondant !
Ce qui prend en fait le plus de place dans est le nombre énorme de modules de carrefour...

Les épisodes RPG de la série qui suivent A Link to the Past gardent les mêmes mécaniques de jeu, en particulier le grappin et la possibilité de pousser des pierres. La démonstration est donc exactement la même, et on peut conclure que tous les épisodes de la série, dans leur version généralisée, sont NP-difficile.
Cependant, le grappin ne peut pas être trouvé dans le premier épisode de la série, The Legend of Zelda. Des mécanismes de poussage de blocs sont cependant présent, ce qui permet tout de même de prouver que lui aussi est NP-difficile, puisqu'il est équivalent au jeu Sokoban (un jeu où l'on incarne un garde d'entrepot chargé de ranger des caisses, démontré comme étant NP-difficile).
Seul The Adventure of Link ne peut pas être prouvé de cette façon comme NP-difficile, son gameplay étant radicalement différent des autres épisodes de la série. La complexité de ce jeu est donc toujours ouverte !

La saga Super Mario Bros. est NP-difficile !
Autre saga phare de Nintendo : les jeux de plate-forme de la série des Super Mario Bros., qui contient quand même une vingtaine d'épisodes. On y incarne Mario, un plombier moustachu vouant sa vie à arpenter le monde pour venir en aide à divers avatars féminins. Et sa tâche n'est pas aisée : pour ce qui est des épisodes 2D de la série, on peut montrer qu'ils sont tous NP-difficiles. Le schéma de la preuve est le même : il faut construire les modules de variables, de clause et de croisement !

Chaque épisode de la série présente ses spécificités, mais on peut commencer par les deux premiers épisodes : Super Mario Bros. et Super Mario Bros. : The Lost Levels. Ces deux épisodes sont techniquement similaires, puisqu'ils sont basés sur le même moteur de jeu. En particulier, tous les éléments du premier épisode de retrouvent à l'identique dans le suivant.

Encore une fois, on parlera de maps généralisées pour Super Mario Bros. On supposera que la carte peut être arbitrairement grande, et qu'elle n'est soumise à aucune contrainte technique. En particulier, on va admettre que l'écran du jeu peut être arbitrairement grand, puisque, dans le jeu original, le scrolling empêche Mario de sortir de l'écran par la gauche. On supprimera aussi la contrainte du temps. Le théorème de Aloupis énonce donc :

Dans le jeu Super Mario Bros. généralisé, déterminer si il est possible d'atteindre le drapeau de fin d'un niveau depuis son départ est un problème NP-difficile.

Pour démontrer cela, on s'appuiera sur les propriétés suivantes :

  • Mario est capable de marcher, courir et sauter (jusqu'à une hauteur fixée). Il peut mourir instantanément si il tombe dans un trou sans fond, mais ne subit aucun dommage lors de chutes.
  • Initialement, Mario est petit. Lorsqu'il ramasse un champignon, il devient super Mario, plus grand, et acquière le pouvoir de casser certaines briques en sautant par en-dessous. Lorsqu'il est touché par un ennemi, il redevient Mario, petit.
  • Mario peut également ramasser des étoiles dans des blocs "?", qui le rendent temporairement invulnérable.

Ces quelques éléments du gameplay vont nous permettre de construire les modules nécessaires à la preuve

Module de départ / d'arrivée :
On supposera que Mario doit ramasser en début de niveau un super champignon, et qu'il doit rester Super Mario jusqu'à la fin du niveau. Pour obliger cela, on utilisera les modules de départ et d'arrivée suivants :

Mario_debut
Module de départ :
Le bloc contient un super champignon

Mario_fin
Module d'arrivée :
Pour atteindre le drapeau d'arrivée, il est nécessaire d'avoir pris le champignon du départ

Module d'assignation de variable :
Pour affecter une valeur booléenne à une variable, on utilisera le fait que lorsque Mario tombe, il ne pourra plus remonter :

Mario_variables
Module d'assignation de variable :
Mario doit faire un choix entre le chemin de gauche et de droite. Une fois le choix fait, on ne pourra plus revenir en arrière.

Module de clause :
Pour pouvoir passer ce module de clause, Mario doit faire apparaître une étoile d'invincibilité contenue dans les blocs "?", seule celle-ci permettra de passer les tourniquets enflammés sans être blessé. Ce sont ces blocs "?" qui sont accessibles depuis les chemins d'assignation de variables.

Mario_clause
Module de clause :
Pour franchir ce module, il est nécessaire d'avoir activé l'un des blocs "?"

Module de carrefour :
Le plus difficile à construire, c'est en fait ce module de carrefour :

Mario_carrefour
Module de carrefour :
Si Mario arrive du côté gauche, il ne pourra que sortir du côté droit. Pour cela, il devra retrouver sa taille initiale grâce au Goomba, ce qui lui donne accès au petit passage. Sa petite taille l'empêche de casser les briques, et l'oblige à ressortir du côté droit, après avoir repris un champignon dans le bloc "?".
Si Mario arrive en bas, sa grande taille lui permettra de prendre le chemin du haut en cassant les briques, mais lui interdit le passage réservé au petit Mario.
Ce carrefour ne peut cependant être traversé que dans le sens gauche-droite ou bas-haut.

Puisque ces modules peuvent être réalisés, Super Mario Bros. et Super Mario Bros. : The Lost Levels sont NP-difficile ! CQFD.

Je ne me vais pas me risquer à construire un exemple de monde simulant un problème SAT, la taille du module de carrefour rendront la carte démesurée...
Et les autres jeux de la saga dans tout ça ? Eh bien, il va falloir regarder au cas par cas...

Super Mario Bros 3
Dans ce jeu, les flammes n'existent pas ! Il va falloir du coup modifier le module de clause.

SMB3_clause
Module de clause de SMB3 :
Pour franchir le mur de brique du chemin du bas, il est nécessaire d'avoir éliminé l'un des trois Koopa du dessus (chaque tortue correspond à une variable de la clause). 

Super Mario World
Les flammes n'existent pas non plus dans cette opus de la série. Mais les grands absents de cet épisode, ce sont les briques, qui sont remplacées par des blocs jaunes. Ces blocs ne peuvent pas être détruit, mais il est possible de les franchir par en-dessous quel que soit la taille de Mario, et par au-dessus lorsque Mario est grand. Il faut donc modifier les modules d'arrivée, de clause et de carrefour:

SMW_Arrivee
Module d'arrivée :
Un champignon est nécessaire pour franchir le bloc jaune.

SMW_Clause
Module de clause :
Mario doit franchir ce module depuis le côté droit jusqu'au côté gauche. Pour ce faire, il doit appuyer sur le bouton P contenu dans le bloc "?", celui-ci transformant les pièces en blocs franchissables. Pour que ce bouton apparaisse, il faut que l'une des carapaces de Koopas atteigne le bloc "?", les chemins amenant à ces Koopas n'étant accessibles que lors de la phase d'assignation des variables.
A noter tout de même qu'il faut placer un dispositif (des vignes servant d'échelle, par exemple) empêchant Mario d'emporter l'une des carapaces.

SMW_Carrefour
Module de carrefour :
Le principe reste le même. Ce carrefour est traversable de gauche à droite et de haut en bas.

Les autres épisodes
Pour les épisodes suivants, le principe reste le même. Il faut simplement se méfier des wall jump qui apparaissent à partir de Super Mario 64, qui obligent à repenser les modules d'assignation de variable...

La saga Pokémon est NP-difficile !
Une fois n'est pas coutume, je vais devoir à nouveau parler de Pokémon sur ce blog ! Ce n'est quand même pas ma faute si on peut y trouver autant de problématiques mathématiques... Les jeux de cette saga mettent en scène un jeune à casquette qui cherche à réaliser son rêve : capturer un maximum de Pokémon et les entraîner à combattre afin de devenir maître Pokémon ! Une vingtaine d'épisodes sont sortis, et le constat est sans appel : ils sont tous NP-difficiles !

Tous les jeux de la série mettent en scène des problèmes de type Sokoban, et la simple existence de ce mécanisme entraîne sa NP-complexité. Mais on va plutôt le démontrer en s'appuyant sur le cœur des jeux Pokémon : les combats contre les dresseurs !

Encore une fois, il nous faut une version idéalisée du jeu (carte et mémoire en machine arbitrairement grande), et le théorème de Aloupis devient :

Dans la série RPG des jeux Pokémon (généralisés), déterminer si il est possible d'atteindre un point donné depuis un autre point donné est un problème NP-difficile.

Pour construire des cartes construisant des problèmes SAT, on va s'appuyer sur un principe de base des jeux : quand on passe dans le champs visuel d'un dresseur Pokémon adverse, il s'avance vers nous pour nous combattre. Si le dresseur est battu, il restera à sa place, ne pourra plus bouger et ne cherchera plus à combattre. Si un autre dresseur est dans le champ de vision de premier dresseur, celui-ci ne nous verra pas. On se servira de ces mécanismes pour bloquer certains passages

Pour les besoins de la démonstration, on ne considérera que deux types de dresseurs ennemis : les dresseurs faibles et les dresseurs forts.

  • On supposera que notre avatar ne possède aucun objet utilisable et une équipe composée de un seul Pokémon avec une seule attaque : Fantominus (avec l'attaque Destruction, qu'il apprend dans la génération I ou II), ou Skelénox (avec l'attaque Souvenir, à partir de la génération III). Les attaques Destruction et Souvenir ont la particularité de mettre K.O. le Pokémon qui le lance. Ainsi, notre seule action possible lors d'un combat est de lancer l'autodestruction, et de perdre le combat si l'on attaque en premier.
  • Les dresseurs faibles seront forcément battu. Pour implémenter un tel dresseur, on pourra par exemple supposer qu'ils ne possèdent que un Pokémon, un Électrode de niveau 100 et de vitesse maximale possédant la seule attaque Destruction. Dans un combat, ce dresseur faible attaquera en premier, et la destruction lui fera perdre le match. Puisque notre Pokémon est de type spectre, il sera insensible à cette attaque de type Normal.
  • Les dresseurs forts sont imbattables. Ils possèdent deux Pokémon quelconques. Lorsque l'on combat un de ces dresseurs, on sera obligé d'utiliser l'attaque Destruction ou Souvenir, amenant nécessairement à la défaite.

Dans les modules suivants, le champs de vision des dresseurs sera représenté en rouge pour les dresseurs invulnérable, et en bleu pour les dresseurs faibles.

Module de départ / d'arrivée :
Rien de particulier pour ce module, on a juste à se fixer un point de départ et d'arrivée.

Module de chemin à sens unique :
Les routes à sens unique existent déjà dans tous les jeux de la série, grâce à l'existence des corniches. Il est tout de même possible de construire ces chemins uniquement grâce à des dresseurs :

Pokemon_sens_unique
Module de chemin à sens unique :
Quand on passe ce chemin dans un sens, le dresseur bleu s'avancera pour combattre (et perdre), ce qui laissera la voie libre au dresseur rouge du bas. Le chemin de retour implique donc de combattre ce dresseur invulnérable : le retour est impossible. 
L'autre dresseur rouge est présent pour nous empêcher d'aller parler au dresseur bleu.

Module d'assignation de variable :
Dans les jeux Pokémon, les combats contre les dresseurs peuvent être déclenchés de deux façons différentes : soit lorsque l'on rentre dans leur champ de vision (et le dresseur s'avance pour nous combattre), soit lorsqu'on leur parle. Ce sont ces mécaniques que l'on utilisera pour assigner les variables.

Pokemon_Variables (2)
Module d'assignation de variable :
On arrive par la gauche. Pour prendre la sortie de droite, il faut commencer par aller parler au dresseur sans être vu. Une fois immobilisé, la sortie de droite est disponible, et la sortie haute condamnée. Inversement, pour prendre la sortie haute, on commencera par faire avancer le dresseur en rentrant dans son champ visuel. Il laisse alors un accès au chemin du haut.

Module de clause :

Pokemon_Clause
Module de clause :
Il doit être traversé de droite à gauche. 
Si le module n'a pas été visité depuis les entrées A, B ou C, tous les dresseurs bleus s'avanceront pour combattre, laissant le champ libre au dresseur rouge qui regarde vers la gauche. Il bloquera alors le chemin. Il faut donc préalablement neutraliser ces dresseurs bleus, en allant parler à au moins l'un d'entre eux.

Module de carrefour :
Encore une fois, le module de carrefour est le plus compliqué. Celui-ci peut être traversé une fois de gauche à droite, ou une fois de haut en bas.
Ce module comprend 4 modules de chemin à sens unique.

Pokemon_carrefour
Module de carrefour :
Pour franchir ce carrefour de gauche à droite, on commencera par venir parler au dresseur bleu qui regarde loin vers la droite. Après avoir franchit deux des quatre modules de sens unique, la voie sera libre pour la sortie de droite. 

Puisque ces modules peuvent être réalisés, les 25 RPG Pokémon sont NP-difficiles ! CQFD.

Les sagas Metroid et Donkey Kong sont NP-difficiles !
D'un côté, il y a Metroid, où l'on incarne Samus, une chasseuse de primes en quête de retrouver les métroïdes volées par les pirates de l'espace. De l'autre, il y a Donkey Kong Country, où l'on incarne Donkey Kong, un gorille en quête de retrouver son stock de bananes volé par le roi K. Roll, un crocodile obèse. Les scénarios sont plutôt différents, mais la conclusion de Aloupis est la même : ce sont des jeux NP-difficile !
Encore une fois, les démonstrations s'appuient sur la construction des différents modules, mais je ne vais pas les détailler (allez consulter l'article de Aloupis !).

Pour le cas de Donkey Kong Country, les modules de carrefour et de sens unique sont présent directement dans le jeu, grâce aux tonneaux. Le module de variable est similaire à celui de Mario, tandis que le module de clause s'appuie sur l'existence des Zingers, monstres abeilloïdes. Ces éléments se retrouvent dans tous les autres opus 2D de la série, qui sont donc eux aussi NP-difficiles.

Pour Metroid, les modules de carrefour utilisent la capacité de Samus à se transformer en morphball, tandis que le module de clause s'appuie sur l'existence des Hépixors (Zoomers, en VO), monstres mollusquoïdes. Ces éléments sont également présents dans l'ensemble des autres épisodes de la série, les rendant eux aussi NP-difficiles.

Dans leur papier, Aloupis, Demaine, Guo et Viglietta ne s'arrêtent pas à la démonstration de la NP-difficulté de toutes ces licences Nintendo, mais ils démontrent également, pour Zelda et Donkey-Kong Country, leur PSPACE-difficulté. Ces deux jeux sont donc encore plus complexes que complexes !
Si un algorithme cherche à résoudre un problème de déplacement dans une carte de l'un de ces jeux, non seulement le temps de calcul demandé sera énorme (=non proportionnel à la taille de la carte), mais la mémoire demandée par l'algorithme sera elle aussi énorme. La méthodologie de la démonstration est similaire, mais ils montrent que ces jeux sont équivalent à un autre problème de logique (le problème TQBF), et construisent d'autres types de modules.

Bref, vous avez tout ce qu'il faut pour maintenant démontrer vous même que Sonic, Alex Kidd, Tomb RaiderMinecraft ou Mr Carré sont (ou non) NP-difficiles !


Sources
Classic Nintendo Games are (Computationally) Hard --  G. Aloupis, E. D. Demaine, A. Guo et G. Viglietta 

Posté par El Jj à 10:10 - Commentaires [10] - Permalien [#]
Tags : , , , , ,

31 octobre 2014

Don't dead open inside

Le zombie est une créature à capacités cognitives limitées à la fois morte et vivante, se nourrissant essentiellement de cerveaux humains. Ils peuvent se nourrir avec d'autres types de viandes, mais la viande humaine reste quand même leur principale source de protéines. Le mathématicien, quant à lui, est une créature bien vivante dont les capacités cognitives sont potentiellement infinies et qui, sauf rares exceptions, ne se nourrit pas de cerveaux humains, mais plutôt de café. 

Will_you_be_ready

Pourtant, les mathématiciens entretiennent des rapports très proches avec les zombies dès qu'il s'agit de modélisation. Et la question qui se pose vraiment, c'est de savoir comment réagirait la population mondiale face à une épidémie de type zombie...

Le modèle SIR
Pour modéliser une apocalypse zombie, on peut piocher parmi les modèles classiques d'évolution des population. On penser au modèle proie-prédateur de Lotka et Volterra, mais puisque les zombies sont considérés comme des malades dans la plupart des histoires de zombies modernes, c'est plutôt du côté des modèles épidémiologiques que l'on va se tourner.

Le modèle de base en épidémiologie (qui date tout de même de 1927) duquel dérive la majorité des autres modèles est le modèle SIR. Il part de l'hypothèse que, face à une maladie donnée, le monde se divise en trois catégories : les individus sains et susceptibles de tomber malade (S), les individus infectés (I) et les individus remis de leur maladie (c'est à dire, soit immunisés, soit morts) (R). Evidemment, c'est un modèle, et de très nombreuses variantes ont été proposées et étudiées.

Pour mathématiser le modèle, on va devoir faire appel aux équations différentielles. Pour cela, on va considérer les fonctions suivantes :

  • S(t) : le nombre (ou la concentration / proportion) d'individus sains, en fonction du temps
  • I(t) : le nombre d'individus infectés, en fonction du temps
  • R(t) : le nombre d'individus remis, en fonction du temps

Pour modéliser le problème, on a également besoin de connaître plusieurs coefficients, propres à chaque maladie :

  • β, le taux de propagation du virus (plus β est grand, plus la maladie est infectieuse)
  • ζ, le taux de rémission ou de décès du virus (1/ζ correspond alors au temps moyen de rémission/décès) (plus ζ est petit, plus le temps durant lequel le malade est contagieux est long)

Ainsi, le nombre d'individus sains diminuera au cours du temps. Cette diminution sera proportionnelle selon le coefficient de propagation β du virus, et dépendra donc du nombre d'invidivus infectés présents (plus le nombre d'infecté est grand, plus la propagation sera rapide). Mathématiquement, cela s'écrit S'(t) = – β.I(t).S(t), où S'(t) désigne la dérivée de la fonction S en fonction de t, qui correspond à la vitesse de diminution du nombre d'individus sains.
Inversement, le nombre d'individus infectés augmente proportionnellement au taux β et au nombre d'individus encore sains, mais diminue selon le taux de rémission ζ. L'équation est alors I'(t) = β.S(t).I(t) – ζ I(t)
Enfin, l'augmentation du nombre d'individus remis/morts est proportionnelle au nombre d'individus infectés, d'un facteur ζ. On a alors l'équation R'(t) = ζ I(t).

Finalement, on obtient un système de trois équations différentielles :

Modele_SIR

Qu'on se le dise tout de suite, il est hors de question de chercher une formule explicite pour la solution de ce système. Déjà parce que la connaître ne nous apportera pas grand chose, mais surtout, parce qu'une telle formule n'existe généralement pas. On peut quand même étudier le comportement des solutions !
On peut le faire mathématiquement, en étudiant par exemple les points d'équilibre du système. Mais on peut aussi, et c'est quand même plus amusant, choisir des valeurs pour les coefficients β et ζ, ainsi que des conditions initiales, et laisser l'ordinateur faire les calculs pour compter le nombre de morts causés par notre virus fictif (bien sûr, cela implique également de s'y connaître en mathématique de modélisation pour vérifier que les courbes que l'on obtient sont les bonnes, mais on va fermer les yeux là-dessus et faire comme si c'était quelque chose de facile). 

ModèleSIR

Scénario catastrophe : comment réagirait la population en présence d'un virus mortel et incurable ? Simulons !
A : maladie très infectieuse (β=4) mais rapidement mortelle (ζ=4). 60% de la population survit, c'est pas mal.
B : maladie très infectieuse (β=4) et longtemps contagieuse (ζ=1) : extinction de l'humanité.
C : maladie peu infectieuse (β=0.5) et mais très longtemps contagieuse (ζ=0.25). 20% de survivant !
Dans chaque cas, on part de 90% d'individus sains et de 10% de malades.

Apocalypse zombie, modèle de Munz
Seulement, être un zombie n'est pas une maladie comme les autres puisque, la rémission est rarement possible, et que la mort n'y est que temporaire. Dans un article en 2009, quatre mathématiciens canadiens (P.Munz, I. Hudea, J. Imad et R.J. Smith) proposent une modélisation dérivée du modèle SIR, dans lequel :

  • la population I des infectés est remplacée par la population Z des zombifiés.
  • on ajoute à l'équation de l'évolution de S un taux de naissance naturel (π) ainsi qu'un taux de décès naturel et/ou de suicide δ (ce qui ajoutera le terme +δ.S à R(t))
  • on ajoute à l'équation de l'évolution de Z le terme – α.S(t).Z(t) indiquant la tendance naturelle qu'on les individus sains à attaquer à la hache les individus infectés (ce qui est rarement le cas dans les infections plus classiques), ainsi que le terme + ζ.R(t), indiquant la tendance qu'on les zombies et individus morts à revenir à la vie sous forme de zombie.
  • on ajoute à l'équation de l'évolution de R le terme – ζ.R(t), correspondant à la faculté qu'on les morts à revenir à la vie, ainsi que le terme + α.S(t).Z(t) correspondant aux individus débarrasses de leur infection suite à un coup de hache bien placé.

On obtient alors le système d'équation suivant (les "(t)" sont sous-entendus) :

Modele_Munz

Testons ce modèle avec les coefficients π=0.001, δ = 0.001 (naissances et suicides négligeables), α=1 (humains sains moyennement violents), β=0.5 (zombies peu agressifs) et ζ=0.25 (résurrection des zombies non négligeable), et avec initialement seulement 5% d'humains. On obtient les courbes suivantes :

ModeleMunz
28 jours plus tard, l'humanité a quasiment disparu...

En fait, on peut démontrer que, quelles que soient les conditions initiales, le nombre de zombies tendra vers l'infini. Selon ce modèle, l'apocalypse zombie est inévitable...

Munz et son équipe proposent d'autres modèles dérivés de celui-ci, en envisageant un temps de latence entre la morsure et la transformation en zombie, ou en proposant la possibilité de placer les infectés en quarantaine. Ce modèle possède cependant une énorme faille : les zombies y sont immortels !

Pourtant, il est parfaitement connu qu'un coup de masse, d'arbalette, de fusil, de batte de base-ball ou de n'importe quel objet de tir ou de frappe dans le cortex préfrontal d'un zombie entraîne sa mort définitive. Il faut ajouter une classe au modèle, celui des zombies définitivement morts !

Apocalypse zombie, modèle de Witkowski 
En 2013, deux biologistes C. Witkowski et B. Blais proposent une alternative au modèle de Munz comprenant 4 classes :

  • S : individus sains
  • E : individus en passe de devenir zombie. Ces classes permet d'unifier les différentes formes de zombies selon les oeuvres : chez Romero, la classe E correspond aux morts ; chez Marc Forster, ce sont les 12 secondes d'incubation du virus, etc.
  • Z : zombies
  • R : zombie définitivement mort

Les interactions entre les différents groupes sont les suivantes :

  • Au contact de zombies, les individus sains passent temporairement dans le groupe E, au taux β.
  • Les individus du groupe E deviennent inexorablement des zombies, à un taux  ζ.
  • Les individus sains peuvent, en se suicidant, intégrer directement la classe R, au taux δ.
  • En visant la tête, les individus sains peuvent se débarasser définitivement des zombies, au taux α.

Le système d'équation est alors :

Modele_Witkowski

On peut alors démontrer que le scénario catastrophe du modèle précédent n'aura pas forcément lieu, dans le cas où α est supérieur à β (autrement dit, si les humains sont plus agressifs que les zombies)

Il ne reste plus qu'à déterminer les coefficients α, β, δ et ζ pour tenter quelques modélisations. Et pour cela, Witkowski et Blais ont fait une petite étude de cas, et ont visionné attentivement La Nuit des morts-vivants (1968, George A. Romero), film qui a donné la définition des morts-vivants, et Shaun of the Dead (2004, Edgar Wright), film où les morts-vivants correspondent parfaitement au stéréotype du zombie moderne.

Pour La Nuit des Morts-vivants, ils ont déterminé α=0.9, β=1.1, ζ=3.6 et δ négligeable. Pour Shaun of the dead,  α=0.49, β=0.59 ζ=2 et δ=0. Dans les deux cas, l'humanité finit par périr, contrairement à ce que la conclusion des films laisse à penser...

Modele_Witkowski
Nombre de vivants et de morts-vivants en fonction du temps dans les deux films, en suivant le modèle de Witkowski

Finalement, face à une épidémie de zombies, toutes les études aboutissent aux mêmes conclusions :
- l'humanité périra,
- quelques humains mieux entraînés que les autres ou en quarantaine survivront peut-être,
- les mathématiciens mourront très vite, trop occupés à déterminer les coefficients de leurs équations différentielles.


Sources :
Bayesian Analysis of Epidemics - Zombies, Influenza, and other Diseases, C. Witkowski et B. Blais
When zombies attack ! : mathématical modelling of an outbreak of zombie infection, P.Munz, I. Hudea, J. Imad et R.J. Smith
Modélisation mathématique, calcul scientifique et zombies, conférence à des lycéens de R. Turpault (il ne se base pas sur le modèle SIR, mais sur l'équation de Lokta-Volterra, puis sur l'équation de Boltzmann)

Image : Will you be ready

Posté par El Jj à 10:00 - Commentaires [2] - Permalien [#]
Tags : ,

26 octobre 2014

Deux minutes pour l'heptagone régulier

Nouvel épisode de "deux minutes pour" (qui, étonnamment, dure plus de 4 minutes...), où il est cette fois-ci question de découper des tartes aux litchis pour l'anniversaire de mathématiciens grecs avec un tétracontakaidigone régulier.

Et on peut retourner lire ce vieil article pour lire la construction de l'heptadécagone régulier.

[Edit] Et je rajoute la construction du 257-gone (dihectapentacontakaiheptagone (?) ) à la règle et au compas, signalé en commentaire par Plopilop.

Posté par El Jj à 10:00 - Commentaires [4] - Permalien [#]
Tags : , , , ,



19 octobre 2014

En soulevant le couvercle

D8, fossoyeur assumé de jeux télévisé, vient de déterrer "à prendre ou à laisser", plutôt connu entre 2004 et 2010 sous le nom de "jeu des boîtes d'Arthur". Le jeu est aujourd'hui présenté par Julien Courbet, mais il garde ses principes de base : ouvertures de boîtes, musiques de suspens, téléphone à cadran et candidats recalés de télé réalité.

Le principe du jeu est plutôt simple mais diablement efficace. 24 boîtes, contenant des sommes connues de 0.01 € à 100 000 € (jusqu'à 1 000 000 € dans les précédentes éditions de l'émission), sont confiées à des candidats qui ne connaissent par leur contenu. L'un des candidat est tiré au sort et aura le privilège d'ouvrir une par une les 23 autres boîtes, jusqu'à ce qu'il ne reste plus que la sienne. Le candidat gagne alors le contenu de sa boîte.
Là où le jeu passe du bingo traditionnel à une application de théorie des jeux, c'est que de nombreuses fois durant l'émission, le "banquier" appelle et propose un choix : échanger sa boîte avec un autre candidat, ou bien, accepter de vendre sa boîte au banquier.

La question que se pose n'importe quel candidat est alors la suivante : à quel moment faut-il échanger sa boîte ? à quel moment est-il préférable d'accepter la proposition pécuniaire du banquier ?

Paradoxe de Monty Hall

monty_hall
Le paradoxe de Monty Hall, par xkcd

Le problème de à prendre ou à laisser, à cause de cette possibilité d'échanger sa boîte, fait terriblement penser au paradoxe de Monty Hall (ou, dans son nom plus franchouillard, paradoxe du Bigdil). Pourtant, cela n'a rien à voir !

L'énoncé du problème de Monty Hall est le suivant :
Vous participez à un jeu télé, et vous êtes enfin arrivé en finale. Devant vous, trois portes A, B et C. Deux d'entre elles cachent une chèvre, la troisième cache une voiture. Bien sûr, vous jouez pour remporter la voiture et non la chèvre. Vous devez choisir une porte, et vous gagnerez ce que cache cette porte. Le choix de la porte se fera selon la procédure suivante :
- vous choisissez la porte de votre choix ;
- le présentateur ouvrira une porte que vous n'avez pas choisi et qui cache une chèvre (il connaît le lot attribué à chaque porte);
- vous avez la possibilité de changer de porte, et vous gagnez le contenu de la porte finalement retenue.

La question est la suivante : est-il préférable de changer de porte, ou bien, est-ce que cela ne change en rien les probabilités ?

Un raisonnement erroné consiste à dire que, au stade où il ne reste que deux portes, il y a une chance sur deux d'avoir la bonne porte, et que changer de choix ne change rien. Ce raisonnement est pourtant faux : en changeant de porte, on fait passer la probabilité de gagner la voiture de 33% à 67% !

Pour comprendre pourquoi les probabilités changent, il faut comprendre ce qu'il se passe quand l'animateur retire une chèvre : dans le cas où l'on se trompe dans le choix initial, l'animateur n'a pas le choix dans la chèvre qu'il devra retirer, et laissera nécessairement la voiture. Changer de choix assure alors de remporter la voiture. Cette situation arrive donc dans deux tiers des cas.
Si on choisit la voiture lors de son choix initial, l'animateur pourra retirer n'importe quelle autre porte, qui cachera forcément une chèvre. En changeant de choix, on tombera donc sur l'autre chèvre. Mais cette situation n'arrive que dans un tiers des cas (si la voiture a été choisie dès le début).
Finalement, en changeant de choix après la révélation de la chèvre par l'animateur, on est assuré de gagner la voiture avec une probabilité de 2/3. En fait, le choix de l'animateur apporte une information nouvelle que l'on peut utiliser pour renverser les probabilités de gagner.

Screen Shot 11-01-14 at 11

On peut se convaincre du bienfondé du raisonnement en plaçant dans une situation où 100 portes sont présentes (99 chèvres, une voiture), et où l'animateur retire 98 chèvres lors de l'étape 2. La probabilité de tomber sur la voiture lors du choix initial est particulièrement faible (1/100), le changement de porte sera donc plus que conseillé.

Changer de boîte chez Courbet
Mais dans à prendre ou à laisser, la situation est complètement différente. Contrairement au paradoxe de Monty Hall, la phase d'élimination des boîtes est faite au hasard, et non par un animateur qui connaît le contenu des boîtes et cherche à ménager le suspens. L'ouverture des boîtes n'apporte donc aucune nouvelle information, et il est impossible de l'utiliser pour modifier les probabilités.

La probabilité de détenir la boîte à 100 000 € est donc de 1 / 24, et aucun changement de boîte ne peut modifier cette probabilité !

« Oui, mais pour le candidat d'hier, il ne lui restait au final que deux boîtes possibles, un contenant 100 000 € et une autre contenant une ventouse. Dans ce cas, il a bien une chance sur 2 de gagner le gros lot ! »
Effectivement ! Dans ce cas (que l'on échange ou non sa boîte), la probabilité de gagner les 100 000 € est bien de 1/2 (et donc, échanger sa boîte n'apporte pas un supplément de probabilité)
Mais "ce cas" (où la boîte à 100 000 € n'est pas éliminé pendant les 22 premiers tours) ne se présentera qu'avec une probabilité de une chance sur 12*, ce qui, puisque (1/2) x (1/12) = (1/24), nous ramène bien au fait que l'on a toujours que une chance sur 24 de remporter les 100 000 €.

Bref : la possibilité d'échanger sa boîte dans à prendre ou à laisser est un non-choix total !  Il est presque aussi pertinent que le choix des numéros que l'on coche dans une grille de loto (bien que, pour le loto, le partage des gains au rang 1 implique que certains numéros peuvent rapporter plus que d'autre).

Bon, pour être un peu honnête, la possibilité d'échanger sa boîte est là pour garantir l'équité du jeu. Étant donné que le banquier connaît la répartition des différentes somme entre les boîtes, il pourra systématiquement proposer des sommes inférieures au contenu de la boîte, rendant le jeu injuste. Une meilleure solution serait que le banquier ne connaisse pas le contenu des boîtes, comme dans les versions étrangères du jeu.

Une proposition que l'on ne peut pas refuser
Mais il reste un choix qui garde un sens : les propositions du banquier !

Après que l'on a éliminé six premières boîtes, le banquier appelle et offre la possibilité de racheter la boîte. D'autres propositions seront faite après 11 boîtes, 15, 18, 20, 21 et 22 boîtes éliminées.

La somme qu'il propose est systématiquement inférieure à la moyenne des sommes restantes en jeu (sauf lorsque ces montants sont dérisoires, le banquier a tendance à proposer un geste commercial), et plus le nombre de boîtes diminue, plus la somme proposée par le banquier se rapproche de la moyenne des boîtes restantes en jeu.

Une stratégie optimale consiste à jouer tant que le banquier ne propose pas de somme supérieure à 10 000 (ce qui correspond au gain moyen des 24 boîtes). Mais comme le banquier ne propose jamais des sommes supérieure au gain moyen, appliquer cette stratégie revient à refuser systématiquement les propositions, rendant forcément le jeu moins intéressant.
Pour être un peu précis, l'élimination initiale de 6 boîtes fait varier le gain moyen de 1250 € à 13500 €, mais la stratégie optimale n'a pas plus de chance de porter ses fruits.

La question est donc de savoir à quel moment il faut savoir vendre sa boîte, et c'est à ce moment que la théorie des probabilité laisse sa place aux théories économiques.
Grossièrement, les dilemmes de à prendre ou à laisser peuvent être résumées par « préférez vous gagner 40 000 € ou avoir une chance sur 2 de gagner 100 000 € ?». Dans le deuxième cas, l'espérance de gain est de 50 000 €, et c'est donc ce choix qu'il serait logique de prendre. Mais dans la pratique, une personne sensée choisira les 40 000 € garantis, puisque 60 000 € supplémentaires ne nous rendront pas plus heureux, il n'est pas raisonnable de risquer de les perdre. C'est donc cette notion de satisfaction qu'il faut prendre en compte ("l'utilité"), et non les valeurs absolues des sommes engagées. C'est finalement cette utilité que l'on cherche à maximiser quand on joue à un tel jeu. 
Évidemment, la risquophilie est bénéfique pour le suspens de l'émission, et est donc encouragée ! Il a d'ailleurs été montré que les mécaniques mises en oeuvre par l'émission diminuent l'aversion au risque des candidats. C'est d'ailleurs pour cette raison que l'émission s'est pour la première fois arrêtée en 2010 : avec la crise, les candidats étaient devenus moins tolérant au risque...

Finalement, la meilleure stratégie consiste à se fixer une somme idéale satisfaisante, et à ne rien risquer pour la dépasser. D8, si vous me lisez, sachez que je suis prêt à venir dans l'émission pour y appliquer cette stratégie désespérément pragmatique !

Il existe cependant une véritable stratégie permettant à tous les candidats de gagner avec une bonne probabilité une somme autour de 10 000 € : il suffit que chaque jour, le candidat désigné n'accepte à aucun moment les offres du banquier, et garde sa boîte jusqu'au bout. En suivant cette stratégie, chaque candidat gagnera donc en moyenne 10 000 €,  mais c'est après plusieurs semaines de jeu que la stratégie se met en place : il suffit que l'ensemble des candidats se partagent leur gains. Le risque associé à cette stratégie est bien plus faible, puisqu'il invoque la loi des grands nombres ! Le seul hic, c'est qu'il peut être compliqué de convaincre Crystal, la gogo-danseuse recalée des Ch'tis à Mykonos qui vient de gagner 50 000 € de partager ses gains avec Marie-Joe, prof de lettres à la retraite, qui a seulement gagné 0.42 €.

Bon, de toutes façons, il y Question pour un champion à la même heure sur France 3. A choisir, je préfère regarder ma maman qui y participe bientôt répondre à des questions sur le cyclisme, plutôt qu'un pourfendeur d'huissier s'accoquiner avec une candidate qui n'en a que faire des théories économiques de la gestion du risque. C'est finalement dommage qu'un laboratoire de théorie des jeux appliqués se soit transformé en réunion tupperware de toutes les superstitions les plus délirantes...


 * D'un côté, on  1 chance sur 24 d'avoir la boîte à 100 000 €. On a donc une proba de 23/24 de ne pas l'avoir. Dans ce second cas, la probabilité de ne pas révéler la boîte à 100 000 € lors de la première ouverture est de 22/23. Si elle n'a pas été ouverte lors de la première révélation, la probabilité qu'elle ne le soit pas lors de la deuxième est de 21/22. etc. Au final, dans le cas où l'on ne possède pas soi-même la boîte à 100 000 €, la probabilité ne pas pas l'ouvrir avant qu'il n'en reste plus que deux est 23/24 × 22/23 × 21/22 × ... × 2/3 × 1/2 = 1/24. En ajoutant la probabilité de soi même détenir cette boîte, on retrouve bien cette probabilité de 1/12.


Sources :
Deal or No Deal? Decision Making under Risk in a Large-Payoff Game Show
T. Post, M. Van den Assem , G. Baltussen, R. Thaler

Images : une chèvre, une autre chèvre, une voiture 

Posté par El Jj à 10:00 - Commentaires [1] - Permalien [#]
Tags : , , ,

12 octobre 2014

Deux minutes pour les boeufs d'Hélios

Nouvel épisode de "deux minutes pour", avec cette fois-ci l'étonnant problème des boeufs d'Hélios. 

Sources :
Problème des bœufs d'Hélios - Gérard Villemin - pour le détail de la résolution par le calcul du système
Archimedes' cattle problem - Ilan Vardi - pour le détail de la résolution de l'équation de Pell-Fermat
The cattle problem - pour les précisions historiques et pour les 206 545 chiffres de la solution

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

28 septembre 2014

Deux minutes pour le théorème de Pythagore

Peut-on démontrer le théorème de Pythagore en moins de deux minutes ? Bien sûr, ce n'est pas difficile.

Mais peut-on le faire de 8 façons différentes ? C'est justement le sujet de la première vidéo de ma nouvelle chaîne Youtube !

Bonus
Il y a une autre démonstration du théorème de Pythagore que j'aurais voulu placer dans la vidéo, mais elle aurait gravement dépassé les 2 minutes... La démonstration de Arioni, basée sur la convergence de la série géométrique.

Pour cela, la première chose à remarquer, c'est que, dans un triangle rectangle, la hauteur issue de l'angle droit donne deux triangles semblables au premier (car ils ont forcément un angle en commun en plus de l'angle droit).

Du coup, sur la figure suivante, tous les triangles représentés sont semblables :

Arioni
ABC est un triangle rectangle en A, de côtés a, b et c.
Pour tout k, Ck+1 est le pied de la hauteur issue de Adu triangle CkAkB, 
et Ak+1 est le pied de la hauteur issue de Ck+1 du triangle Ck+1AkB

Tous les triangles bleus sont similaires, si bien que

Arioni_1

On a alors, pour tout k, 

Arioni_2

On regarde ensuite les triangles de part et d'autres des segments hk :

Arioni_3

On a alors, pour tout k,

Arioni_4

En remplaçant dans l'égalité des triangles bleus, on a :

Arioni_5

De plus, tous les triangles rouges sont similaires à ABC, donc

Arioni_6

Donc 

Arioni_7

Autrement dit, la suite c est géométrique, de raison c²/a²

La longueur c est égale à la série géométrique c0+c1+c2+...
Donc

Arioni_8

De plus, la similarité de ABC avec ABH0 implique que h0 = cb/a
La similarité de A1H0A avec ABC implique que c0 = h0.b/a
Donc c0 = c b²/a².

On remplace dans la série géométrique :

Arioni_9

Ce qui se simplifie en :

Arioni_10

Autrement dit :

a² = b² + c²

CQFD !


Sources :
Vous pouvez retrouver 103 (103 !) démonstrations du théorème de Pythagore sur cut the knot

Posté par El Jj à 10:00 - Commentaires [2] - Permalien [#]
Tags : , , ,

14 septembre 2014

Artur Avila, celui qui mélange

Dans le dernier épisode, j'avais entrepris d'écrire de petits articles pour décrire les travaux de la dernière fournée des médaillés Fields. Dès le premier article sur Manjul Bhargava, j'ai échoué, puisque l'article était trop long. Je vais tenter de me rattraper, en parlant aujourd'hui du plus brésilien de tous les médaillés Fields français (puisque c'est le seul qui soit franco-brésilien) : Artur Avila !

RTEmagicC_Artur_Avila
Artur Ávila Cordeiro de Melo

Artur Ávila est né le 29 juin 1979 à Rio de Janeiro, si bien qu'il a été médaillé Fields à moins de 36 ans (ce qui est plutôt rare). En même temps, vu qu'il a démarré sa thèse à 19 ans, il est normal qu'il obtienne la médaille Fields plus tôt que les autres. Cette médaille, il l'a remporté grâce à 

"ses profondes contributions à la théorie des systèmes dynamiques qui ont bouleversé le domaine, en utilisant la puissante idée de renormalisation comme principe unificateur"

Suite logistique
Ce qui intéresse Artur Avila, c'est de comprendre le comportement des systèmes dynamiques : le mouvement des planètes, la dynamique des populations, le mouvement des électrons... Ce qui caractérise un système dynamique, c'est que leur évolution est parfaitement déterministe : la connaissance exacte des conditions initiales permet toujours de savoir leur avenir. Mais si on ne connaît que vaguement les conditions initiales, la prédiction du futur du système est souvent compromise. Mais ce n'est pas une fatalité ! Commençons déjà par étudier le plus célèbre des systèmes dynamiques, issu d'une modélisation de la croissance de populations : la suite logistique.

Pour un nombre réel r∈ ]0,4], on définit la fonction logistique f:x ↦ r.x.(1-x). 
Puis, étant donné un nombre u0  ]0,1[, on va observer le comportement de la suite (un) définie par un+1 = f(un).

Malgré son apparence très simple, cette suite peut avoir des comportements très bizarres pour certaines valeurs de r et de u0.

Prenons un premier exemple, avec r = 2.8 et u0 = 0.2. Dans ce cas, la suite logistique est la suivante :
u0 = 0.2, u1 = f(u0) = 0.448, u2 = f(u1) = 0.692..., u3 = 0.596..., u4 = 0.674..., u5 = 0.615..., u6 = 0.662...
En itérant davantage, on constate que la suite finit par se stabiliser autour de 0.6428 (9/14). La suite converge !

On peut observer le comportement de ces suites à l'aide de ce que l'on appelle les diagrammes en "toile d'araignée" (ou diagrammes de Vershult). Pour cela, on dessine la fonction que l'on va itérer (ici, f), ainsi que la droite d'équation y=x, et on place le terme initial u0 sur l'axe horizontal. On va ensuite placer le point u1 en reliant verticalement u0 à la courbe de f, puis horizontalement la courbe f à la droite y=x. En répétant l'opération, on fabriquera la "toile d'araignée" qui représentera les différents termes de la suite.
La convergence d'une suite se traduit sur ce diagramme par la convergence des zig-zag.

Logistic_28 (2)
Diagramme en toile d'araignée de la suite logistique, pour r = 2.8 et u0 = 0.2
Les 500 premiers termes de (un) sont représentés (même si 99% d'entre eux sont concentrés autour de 9/14)

En fait, le choix du terme initial u0 n'a aucune incidence sur le devenir de cette suite de paramètre r=2.8 : elle finira toujours par converger vers 9/14.

Mais pour les autres valeurs de r ? Eh bien, ça dépend...

Déjà, il y a les valeurs r comprises entre 0 et 3 : c'est toujours la même chose qui se passe, la suite converge :

logistique_13logistique_2logistique_23
logistique_26logistique_295logistique_3
Pour r ∈ ]0,3], la suite converge, quelle que soit la valeur initiale u0.
Pour r=3, la convergence vers 2/3 est cependant particulièrement lente.

Mais pour les valeurs plus grandes que r=3, les choses se corsent. D'abord, gentiment, lorsque r est compris entre 3 et 3.449 : la suite ne se stabilise pas autour de une seule valeur, mais autour de 2 :

logistique_310logistique_320logistique_330logistique_342
Diagramme pour r=3.1, r=3.2, r=3.3 et r=3.42
Pour r ∈ ]3,1+√6], la suite se stabilise autour de 2 valeurs, quelle que soit (sauf exception) la valeur initiale u0.

Pour des valeurs encore plus grande de r, ça se complique davantage : la suite se stabilisera autour de 4 valeurs (r ∈]3.449, 3.544]), puis autour de 8 valeurs (r∈]3.544;3.564]), puis autour de 16 valeurs, etc., et ce, tant que r ≤ 3.57.

logistique_350logistique_356logistique_3565
Diagramme pour r=3.5, r=3.56, r=3.565
Pour ces valeurs r ≤ 3.57, la suite finira par se stabiliser autour de 2n valeurs

Mais pour les valeurs plus grandes que 3.57, le chaos arrive ! Il n'y a plus aucune valeur autour desquelles la suite va se stabiliser. De plus, si on change même très légèrement la valeur initiale u0, la trajectoire sera complètement différente. On peut alors dire que la suite a un comportement chaotique. Encore une fois, ce chaos est indépendant de la valeur initiale (sauf exceptions)

logistique_370logistique_380logistique_390logistique_400
Diagramme pour r=3.7, r=3.8, r=3.9 et r=4
Pour ces valeurs r ∈ [3.57;4], la suite est chaotique : elle ne se stabilisera autour d'aucune valeur

En fait, ceci n'est pas totalement vrai. A partir de r=3.57, on peut trouver parfois des valeurs r pour lesquelles la suite se stabilisera autour de 3 valeurs, autour de 6 valeurs, ou autour de n'importe quel nombre de valeurs choisies à l'avance. Par exemple, pour r=3.83, la suite se stabilise autour de 3 valeurs :

logistique_383
Diagramme pour r=3.83 : la suite se stabilise autour de 3 valeurs.

On peut résumer le comportement de la suite logistique par son diagramme de bifurcation : en abscisse, le paramètre r, et en ordonnée, ses valeurs d'adhérence :

800px-LogisticMap_BifurcationDiagram

Finalement, la suite peut présenter deux comportements, suivant la valeur r :
- ou bien elle est régulière : elle finit par se stabiliser autour d'une ou de plusieurs valeurs
- ou bien elle est chaotique

Dans le cas où la suite est chaotique, elle n'est cependant pas si imprévisible qu'on voudrait bien le croire. Même si on ne peut pas connaître la valeur de la suite après un grand nombre de valeurs, on peut tout de même prédire avec une certaine probabilité dans quel intervalle elle se trouvera. Par exemple, on peut vérifier que dans le cas r = 0.9, la suite passera plus de 20% de son temps dans l'intervalle [0.9;1], ou qu'elle sera deux fois plus souvent autour de 0.35 qu'autour de 0.7. Et ça, indépendemment du choix de u0 (sauf, comme toujours, cas particuliers). 
Autrement dit, quand on connaît la valeur r, on peut connaître la répartition des valeurs prises par la suite. Le système dynamique se comporte alors comme un objet aléatoire : on dit alors que la suite stochastiquement stable.

Existe-t-il des valeurs r pour laquelle la suite serait ni régulière, ni stochastiquement stable ? ... Eh bien, oui, mais ces exemples sont négligeables (les cycles attracteurs peuvent par exemple être des ensembles de Cantor...). C'est l'objet du théorème de Lyubich (2002), qui indique que presque toutes les suites logistiques sont régulières ou stochastiquement stable.

Mais ça, c'était juste pour le cas très particulier des suites logistiques. Qu'en est-il de tous les autres systèmes dynamiques ? Eh bien, c'est ça l'objet du travail de Artur Avila : il a démontré, avec Lyubich et Melo, que la plupart des systèmes dynamiques observent cette dualité régulier/stochastiquement stable !

Les échanges d'intervalles
Un autre problème qui a longtemps empêché Avila de dormir est celui du mélange des jeux de cartes (bon, avec un nombre infini et continu de cartes, mais l'idée est là).

Par exemple, pour mélanger un jeu de 32 cartes, on peut répéter plusieurs fois l'opération suivante : faire 4 tas de cartes A, B, C, D, puis les réassembler en mélangeant l'ordre des tas (par exemple, D, A, C, B). Quand on parle de système dynamique, il est nécessaire que l'opération soit toujours identique.

Disons que les tas A, B, C et D contiennent respectivement 7, 7, 7, et 11 cartes. En numérotant les cartes de 1 à 32, on a le découpage suivant :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

En permutant ces 4 tas selon le motif DACB, on obtient :

22 23 24 25 26 27 28 29 30 31 32 1 2 3 4 5 6 7 15 16 17 18 19 20 21 8 9 10 11 12 13 14

Et si on répète encore la même opération :

18 19 20 21 8 9 10 11 12 13 14 22 23 24 25 26 27 28 4 5 6 7 15 16 17 29 30 31 32 1 2 3
7 15 16 17 29 30 31 32 1 2 3 18 19 20 21 8 9 10 25 26 27 28 4 5 6 11 12 13 14 22 23 24
28 4 5 6 11 12 13 14 22 23 24 7 15 16 17 29 30 31 21 8 9 10 25 26 27 32 1 2 3 18 19 20
10 25 26 27 32 1 2 3 18 19 20 28 4 5 6 11 12 13 17 29 30 31 21 8 9 14 22 23 24 7 15 16
31 21 8 9 14 22 23 24 7 15 16 10 25 26 27 32 1 2 6 11 12 13 17 29 30 3 18 19 20 28 4 5
13 17 29 30 3 18 19 20 28 4 5 31 21 8 9 14 22 23 27 32 1 2 6 11 12 24 7 15 16 10 25 26
2 6 11 12 24 7 15 16 10 25 26 13 17 29 30 3 18 19 9 14 22 23 27 32 1 20 28 4 5 31 21 8
23 27 32 1 20 28 4 5 31 21 8 2 6 11 12 24 7 15 30 3 18 19 9 14 22 16 10 25 26 13 17 29

Après 10 répétitions, le jeu est plutôt mélangé, et c'est parfait pour une bataille ! 
Après un grand nombre n d'opérations, on dira que le jeu est mélangé si, dans n'importe quel petit groupe de carte, la proportion de carte d'un groupe donné est la même que dans le jeu complet.
Autrement dit, un jeu de carte est bien mélangé si, dans une main, on a toujours environ 50% de cartes rouges, 25 % de piques, 12.5% de carte as ou roi...

Il y a quand même un problème avec le mélange d'un jeu de 32 cartes, c'est qu'après un certain nombre de répétitions, on reviendra forcément à un jeu parfaitement trié. En effet, puisque chaque répétition donne une nouvelle permutation des 32 cartes, et qu'il n'existe *que* 32! (=32×31×30×...×1 = 3.2×1035) permutations différentes, on retombera tôt ou tard sur le jeu trié.
Cela signifie qu'il existe des grands nombres d'itérations n pour lesquelles le jeu n'est pas mélangé...

Cependant, un tel mélange par permutation peut facilement se généraliser à des intervalles :

MelangeIntervalles
Permutation DACB, itérée deux fois

On peut se poser la même question : est-ce que cette permutation est mélangeante ?
Si oui, cela signifierait que, après plusieurs itérations, la première moitié (ou n'importe quel sous-ensemble) de l'intervalle contiendrait exactement la même proportion de rouge (et des autres couleurs) que dans l'intervalle initial. Une telle perfection de mélange est impossible à obtenir, mais on peut l'exprimer en terme de limite : la limite de la proportion de rouge dans la première moitié de l'intervalle doit tendre vers la proportion initiale de rouge.
Malheureusement, une permutation mélangeante, ça n'existe pas, et c'est à Anatole Katok que l'on doit se résultat. Mais ce que Avila a montré, avec Giovanni Forni, c'est que la plupart des permutations d'intervalles sont faiblement mélangeantes : elles sont mélangentes à condition d'exclure un "petit" nombre de valeurs de n.

Ce résultat sur les intervalles peut s'appliquer sur les billards de forme quelconque, ce qui fournit de précieux résultats dans l'étude des mouvements des particules en physique statistique.

Le problème des 10 Martinis
Il existe des problèmes mathématiques côtés à un million de dollars (les fameux problèmes du prix du millénaire, comme l'hypothèse de Riemann ou le problème P=NP). Et il y en existe pour qui la récompense est à première vue moindre, comme le problème des dix martinis. Comme son nom l'indique, dix martinis seraient offerts en échange de la résolution du problème ; une proposition du mathématicien Mark Kac (proposer une ou plusieurs boissons alcoolisées en échange de la résolution d'un problème étant l'une des coutumes des mathématiciens de l'école de Lwów, en Pologne). A noter qu'il existe une variante plus "sèche" de ce problème, appelé problème des dix dry martini... Le problème des 10 martinis est donc le suivant :

Montrer que, pour tout λ ≠ 0, et pour tout α irrationnel, le spectre de l'opérateur presque-Mathieu OperateurMathieu
est un ensemble de Cantor

J'ai retranscrit l'énoncé pour la forme, je ne vais pas le détailler davantage. La seule chose qu'il faut dire, c'est que l'opérateur presque-Mathieu décrit l'évolution d'un électron dans un champ magnétique particulier. Il ne fait nul doute que les physiciens apprécient de connaître le spectre d'un tel opérateur. 

Artur Avila, ainsi que Raphaël Krikorian, Svetlana Jitomirskaya et David Damanik ont résolu ce problème des 10 martinis, ainsi que d'autres problèmes issus de la liste des problèmes de Simon, 15 problèmes issus de la théorie des opérateurs de Schrödinger à destination des mathématiciens du XXIe sicèle. L'histoire ne dit pas si ils ont gagné leur dix verres de vermouth.

L'opérateur presque-Mathieu est lié au papillon de Hofstadter, qui, avant d'écrire des livres (Godel, Escher, Bach), s'intéressait à la physique. Cette fractale issue de la physique représente la conductance de Hall (?) en fonction de l'énergie (??) et du flux magnétique (???). Autant dire que je n'ai pas compris exactement ce qu'est le papillon de Hofstadter, mais comme c'est joli, je ne vais pas me priver de le mettre ici pour conclure cet article...

Hofstadter's_butterfly
Le papillon de Hofstadter
Je devrais un jour faire un top 10 des utilisations du papillon en mathématiques...


Sources
The work of Artur Avila
La suite logistique et le chaos, Daniel Perrin
Weak mixing for interval exchange transformations and translation flows, Artur Avila et Giovanni Forni

 

Posté par El Jj à 10:00 - Commentaires [1] - Permalien [#]
Tags : , , , ,

31 août 2014

Manjul Bhargava, celui qui compte

Quand on part en vacances, on se coupe des informations. Parfois par choix, parfois simplement parce que le wifi du camping n'est pas tout à fait fonctionnel. Et quand on rentre de vacances, on découvre que l'on est passé à côté du décès de Robin Williams et de la révélation des nouveaux médaillés Fields. Du coup, je ne sais pas comment les médias ont traité l'hommage au professeur John Keating, à Sean Maguire ou à Alan Parish, ni comment ils sont parvenus à saboter l'événement de l'année de la communauté mathématique.

Rappellons-le : la médaille Fields, c'est comme le prix Nobel, mais pour les mathématiques. Mais elles ne sont remies que tous les quatre ans, contrairement au prix Nobel. C'est donc plutôt les JO des mathématiques. Mais ça n'a rien à voir, d'autant que les Olympiades de mathématiques existentt, et qu'elles ont lieu tous les ans. Mais chaque année, 4 mathématiciens sont récompensés par la médaille Fields, ce qui fait une moyenne de une médaille Fields par an, ce qui est équivalent au prix Nobel. Mais la médaille Fields limite ses récipiendaires à 40 ans, ce qui n'a rien à voir avec le Nobel. Du coup, on n'a qu'à dire que le Nobel des mathématiques est le prix Abel, et que la médaille Fields est la médailles Fields des mathématiques, puisqu'ils ne font jamais rien comme tout le monde.

En cette année 2014, les quatre mathématiciens qui ont reçu la fameuse médaille sont :
- Artur Ávila, franco-brésilien
- Manjul Bhargava, américano-canadien, d'origine indienne
- Maryam Mirzakhani, iranienne, professeur aux USA
- Martin Hairer, autrichien, professeur au Royaume-Uni

Trois choses sont alors à remarquer :
- il faut arrêter de donner la nationalité des mathématiciens, puisqu'ils font vraiment tout pour compliquer les choses
- je n'ai pas encore parlé des lauréats du prix Nevanlinna, du prix Gauss, du prix Leelavati ni de la médaille Chern, remis en même temps que les médailles Fields, mais j'en parlerai (peut-être) dans un futur article
- heureusement qu'une femme et qu'un français ont été médaillés, sinon, on aurait vraiment rien eu à dire

Mais qu'on fait ces 4 mathématiciens pour mériter une médaille ? Commençons aujourd'hui en nous penchant sur les travaux de Manjul Bhargava.

RTEmagicC_ManjulBhargava_FieldsMedal
मंजुल भार्गव

Pour situer, Manjul Bhargava est né le 8 août 1974 à Hamilton, au Canada, si bien qu'il avait plus de 40 ans lorsqu'il a reçu la médaille Fields (mais le règlement stipule(rait) qu'il faut être âgé de moins de 40 ans au 1er janvier de l'année du congrès). Il obtient son doctorat en 2001 à Princeton (USA), sous la direction de Andrew Wiles, célèbre pour avoir démontré le grand théorème de Fermat (mais comme il a finalisé sa démonstration à 41 ans, il est passé à côté de la médailles Fields...). Il a donc été récompensé :

"pour avoir développé des nouvelles méthodes en géométrie des nombres, lesquelles ont été utilisées pour compter les anneaux de petits rangs, ainsi que pour avoir borné le rang moyen des courbes elliptiques"

... en géométrie des nombres...
La géométrie des nombres consiste à résoudre de façon géométrique des problèmes issus de théorie des nombres (la théorie des nombres est le domaine où l'on cherche les solutions entières ou rationnelles (les fractions) d'équations).
Par exemple, on peut chercher quels sont les entiers x et y qui vérifient x² + y² = 13. La façon la plus simple de le faire est de dessiner dans un repère le cercle de centre (0,0) et de rayon √13 (autrement dit, le cercle d'équation x²+y²=13), et de regarder où il coupe le quadrillage. Un coup d'oeil rapide permet de vérifier que l'équation possède 8 solutions entières.

EquationCercle
Géométriquement, on voit que l'équation x²+y² = 13 possède 8 solutions entières.

On peut également poser la question du nombre de solutions (entières) de l'inéquation x² + y² ≤ 13. Cette fois-ci, il faut compter le nombre de points à l'intérieur du disque de centre (0,0) et de rayon √13.

InequationCercle
Géométriquement, on voit que l'équation x²+y² ≤ 13 possède 45 solutions.

En généralisant la construction, on peut voir que si le nombre C est assez grand, l'équation x² + y² ≤ C aura environ π.C solutions entières. En effet, l'équation x² + y² ≤ C correspond à un disque de rayon √C, donc d'aire π.C. Chaque noeud du quadrillage correspond à un carré d'aire 1, qui recouvre à peu près le disque, ce qui nous donne une approximation pas trop mauvaise.

InequationCercleGeneralise
Le cercle d'équation x² + y² ≤ C est d'aire π.C, il contient donc environ π.C noeuds du quadrillages

Autrement dit, une considération géométrique sur l'aire d'un disque nous apporte une réponse à une question de thoérie des nombres. C'est ça, la géométrie des nombres, et c'est pour ça que c'est cool.

... de nouvelles méthodes...
Le principal fait d'arme de Bhargava, c'est d'avoir découvert de nouvelles lois de compositions pour des polynômes. Cette découverte s'est faite en trois étapes :
- il a lu attentivement Disquisitiones arithmeticae, de Carl Friedrich Gauss, où il est entre autre question de composition de formes quadratiques
- il a joué avec un Rubik's Cube 2x2x2, ce qui lui a fait penser que le cube serait parfait pour illustrer le problème de la composition de formes quadratiques (sérendipité !)
- il a réfléchi longuement, et a abouti à la découverte de 13 nouvelles lois de compositions (là où Gauss en a péniblement décrit une).

Gauss s'est donc intéressé aux formes quadratiques binaires, autrement dit, aux polynômes à deux variables où tous les monômes sont de degré total 2. Bref, aux polynômes de la forme :

Q(x,y) = a x² + b xy + c y²
avec a, b, c entiers

On apprend au lycée qu'il existe trois types de trinômes du second degré : ceux qui possèdent deux racines, ceux qui n'en possèdent qu'une seule, et ceux qui n'en ont aucune. Pour savoir à quel type de trinôme on a affaire, on calcule son discriminant :

Δ = b² − 4ac

Lorsque Δ est négatif, le trinôme n'a pas de racine, et c'est là que c'est intéressant. Pour les formes quadratiques binaires, c'est pareil, elles ne sont intéressantes que lorsque Δ est négatif. Et si, en plus, les coefficients a et c sont positifs, on leur donne un nom : les formes quadratiques définies positives.

Une question qui taraude Gauss est de savoir combien il existe de formes quadratiques binaires définies positives (que je vais abrégéer en écrivant simplement "forme", parce que c'est pénible à écrire) différentes ayant un discriminant -Δ donné. Par exemple, quels sont les formes de discriminant -4 ?
Déjà, il y a Q(x,y) = x² + y².
Mais il y a aussi Q'(x,y) = x² + 2xy + 2y²
Ou alors il y a Q''(x,y) = 65 x² + 94 xy + 34 y²
En fait, n'importe quelle forme Q(rx+sy,tx+uy) (avec r,s,t,u entiers tel que ru-st=1) a le même discriminant que Q, ce qui donne une infinité d'exemples possibles 
Du coup, tous ces exemples de formes ne sont pas réellement différents. Ils constituent alors une même classe d'équivalence, à un changement de variable près. Mais y en a-t-il d'autres ? Pour Δ=-4, non, mais ce n'est pas le cas pour d'autres valeurs de Δ.

La question qu'il faut donc se poser est donc plutôt : combien existe-t-il de classes différentes de formes quadratiques, pour un discriminant -Δ donné ? C'est avec des outils de la géométrie des nombres que l'on peut répondre, au moins de manière approximative, à cette question.

Une autre question qui taraudait Gauss était celle de la structure de ces formes quadratiques : y a t-il un opération (une composition) que l'on peut faire entre deux formes qui donnerait une autre forme ? Il y a des façons naïves de le faire (en additionnant deux formes, on trouve une autre forme), mais celles-ci ne préservent pas le coeur de la forme quadratique : son déterminant. Et c'est là que le génie de Gauss, et plus tard, celui de Bhargava, opèrent !

Pour cela, Gauss s'appuie sur un fait bien connu : quand on multiplie deux sommes de deux carrés (x²+y²), on obtient une somme de deux carrés. Par exemple, le produit de 13 (=2²+3²) et de 25 (=3²+4²) est 325 (=6²+17²), tous trois sommes de deux carrés.
Ceci vient du fait que, pour tout nombres x, y, x', y', on a l'identité (x²+y²)(x'²+y'²) = (xx'-yy')² + (xy'+yx')² (on peut l'illustrer en remarquant que le module d'un produit de deux nombres complexes est égal au produit des modules).
Ainsi, en combinant la forme Q(x,y)=x²+y² avec elle-même, on trouve à nouveau cette forme : d'une certaine façon, on peut dire que Q×Q=Q.

On peut voir sur un autre exemple. Il existe seulement deux formes (à équivalence près) de déterminant -12 :
Q1 = x² + 3y² et Q2 = 2x² + 2xy + 2y²

On peut alors vérifier que l'on a les identités suivantes :
Q1(x,y)×Q1(x',y') = Q1(xx'-3yy',xy'+x'y) 
Q1(x,y)×Q2(x',y') = Q2(xx'-x'y-2yy',xy'+2x'y+yy') 
Q2(x,y)×Q2(x',y') = Q2(xx'-xy'+2yx'+yy',xx'+xy'+yy') 

Autrement dit : Q1×Q1 = Q1, Q1×Q2 = Q2 et Q2×Q2 = Q1 ! C'est ce que l'on appelle la composition des formes quadratiques, et on peut trouver des formules similaires liant entre eux toutes les différentes forme d'un même déterminant donné. Ces identités sont plutôt obscures, et il fallait au moins le génie de Gauss pour découvrir leur existence. 

Mais là où Bhargava intervient, c'est qu'en reprenant et en améliorant les méthodes de Gauss, il est parvenu à généraliser la composition des formes quadratiques à des polynômes de degré supérieur. Du coup, il a fait passer de 1 à 14 le nombre de lois de compositions connues pour les polynômes, cassant au passage l'idée que de telles identités ne pouvait exister que dans le cas des formes quadratiques.

Outre la satisfaction d'avoir plein de nouvelles identités pour les polynômes de degré 2 ou plus, toutes ces constructions sont utiles pour étudier les corps de nombres, objet central en algèbre.
Un corps, c'est un ensemble dans lequel on peut faire sans problèmes les quatre opérations de base : addition, soustraction, multiplication et division. On peut citer, par exemple, le corps des nombres rationnels ℚ, ou celui des nombres réels ℝ.

Ce que l'on aime bien faire avec les corps, c'est y ajouter des nombres pour voir ce que cela donne (on parle d'extensions de corps). Par exemple, on peut prendre le corps des nombres réels ℝ, et y ajouter un nombre qui serait la racine du polynôme X²+1. Si on appelle cette racine i, on obtient des nombres de la forme a+ib, où i²=-1, autrement dit, le corps des nombres complexes. C'est un corps quadratique de discriminant -4, puisqu'il a été construit à partir du polynôme X²+1.
Ce qui serait génial de savoir, c'est le nombre d'extensions de corps qui existent pour un déterminant donné (plus le déterminant est grand, plus le corps sera complexe). Grâce à Bhargava et à ses lois de compositions des polynômes, c'est chose faite !

(Mine de rien, la théorie des corps est centrale en algèbre, et c'est quand elle a été mise au point que l'on a pu résoudre sans difficulté les 3 grands problèmes de l'antiquité)

...avoir borné le rang moyen des courbes elliptiques...
Deuxième prouesse de Manjul Bhargava (avec Arul Shankar) : avoir borné le rang moyen des courbes elliptiques. Evidemment, rien n'aurait été possible sans tous les outils qu'il venait de mettre au point. Par ce théorème qui a fait sa renommé, Bhargava et Shankar ont fait un pas de plus vers la résolution de la conjecture de Birch et Swinnerton-Dyer, l'un des 7 problèmes du millénaire.

Une équation elliptique, c'est une équation de la forme :

y² + a1 xy + a2y = x3 +a3 x² +a4 x + a5
où a1a2a3a4a5 sont des nombres rationnels

Par exemple, les deux equations suivantes sont elliptiques :

y² = x3 +1

y² + y = x3 - x

Encore une fois, le but est de trouver des solutions rationnelles pour ces équations, et surtout, dire combien il y en a : un nombre infini ou pas ?
Dans le cas de l'équation y² = x3 +1, il n'y a que 5 solutions : (-1,0), (0,1), (0,-1), (2,3) et (-2,3)
Dans le cas de l'équation y² + y = x3 - x, il y a une infinité de solutions : (0,0), (1,-1), (1,0), (-1,0), (-1,-1), (2,2), (2,-3), (6,-15), (0.25, -0.375), ...

Mais pourquoi certaines équations elliptiques ont un nombre fini de solutions, et d'autres un nombre infini ? C'est injuste ! Pour cela, on va voir comment déterminer ces solutions, et on va le faire de façon graphique, puisque à chaque équation elliptique correspond sa courbe elliptique :

EquationCourbesElliptiques
Deux courbes elliptiques

Sur ces courbes, on va définir deux opérations : étant donné deux point P et Q de la courbe, on note :

  • P*Q : le troisième point d'intersection entre la courbe et la droite (PQ). Si P=Q, la droite (PQ) est la tangente à la courbe au point P.
  • P+Q : le symétrique de P*Q par rapport à l'axe de symétrie de la courbe.
    On peut démontrer que le point P+Q existe toujours, sans aucune ambiguité (le point P+Q peut éventuellement être un point à l'infini)

CompositionCourbesElliptiques4

Pour deux points P et Q de la courbe (distincts ou non), on fait correspondre un point P*Q et un point P+Q.

Ce qui est intéressant avec cette opération, c'est que si P et Q sont des points à coordonnées rationnelles (des solutions de l'équation de départ), alors P*Q et P+Q aussi. On peut donc, si l'on connaît une solution de l'équation, en déterminer d'autres.

Reprenons la première équation : y² = x3 +1. Une solution particulière de cette équation est le point A (2,3).
Pour déterminer le point A+A, on trace la tangente à la courbe au point A. Cette tangente coupe la courbe en A*A = D(0,-1), donc A+A est le symétrique de D par rapport à l'axe Ox, c'est B (0,1).

SolutionsEquationsElliptiques
Les 5 solutions rationnelles de l'équation y² = x3 +1

On a donc A*A = D, donc 2A = A+A = B
De même :
A*B = C, donc 3A = A + 2A = A+B = C
A*C = B, donc 4A = A + 3A = A+C = D
A*D = A, donc 5A = A + 4A = A + D = E
Et enfin, A*E = O (le point à l'infini), donc 6A = A + E = O
O est élément neutre, puisque A+O = A.
Les 5 solutions de l'équation y² = x3 +1 sont donc tous les multiples du point A !

Si on part sur la deuxième équation y² + y = x3 - x, les choses se passent légèrement différement. Une solution évidente est la solution A(0,0).
En suivant la même méthode, on trace la tangente à la courbe au point A, ce qui nous donne le point A*A = B'(1,-1), et donc, 2A = B(1,0).

SolutionsEquationsElliptiques2

On peut poursuivre : 3A = C (-1,1)
4A = D (2,-3)
5A = E (-0.25, -0.625)
6A = (6,14)
7A = (-5/9 , 8/27)
etc.
En continuant ainsi, on passera par tous les points à coordonnées rationnelles de la courbe, qui sont en nombre infini. Puisque le point A(0,0) permet de trouver l'ensemble infini des solutions de l'équation, on dira que A est un point générateur.

Mais parfois, il arrive qu'un point générateur ne suffise pas pour obtenir l'ensemble des points rationnels de la courbe. C'est par exemple ce qui arrive avec la courbe d'équation y² + y = x3 + x² - 2x, où il est nécéssaire d'avoir deux points générateurs.
Le nombre minimum de points générateurs nécéssaires pour engendrer l'ensemble des points rationnels de la courbe est appellé son rang, et c'est ce nombre qui mesure la complexité de la courbe elliptique que l'on étudie.
Ainsi, la courbe y² + y = x3 - x est de rang 1, la courbe y² + y = x3 + x² - 2x est de rang 2 et la courbe y² = x3 +1 est de rang 0 (puisqu'elle n'a qu'un nombre fini de solution).
Le rang d'une courbe elliptique est toujours un nombre fini, mais n'est a priori pas borné. On ne connaît cependant que très peu de courbes elliptique de très haut rang, le record étant une courbe de rang (au moins) 28, et date de 2006 :

y² + xy + y = x3 - x² - 20067762415575526585033208209338542750930230312178956502x + 34481611795030556467032985690390720374855944359319180361266008296291939448732243429

Les courbes de haut rang sont en fait particulièrement rares, tandis que les courbes de rang 0 ou 1 semblent légions. Mais est-ce toujours le cas ? Si je prend au hasard une courbe elliptique, quelle est la probabilité de tomber sur une courbe de rang 0 ou 1 ? L'expérience montre que environ la moitié sont de rang 0, l'autre moitié de rang 1, et que les rang supérieurs sont négligeables. 
En moyenne (dans un sens que je n'expliquerai pas), on doit donc s'attendre à ce que le rang d'une courbe elliptique soit autour de 0.5. 

Mais la démonstration que le rang moyen est bien 0.5 n'est pas aisée... Ce n'est d'ailleurs aujourd'hui toujours pas démontré, mais on s'approche doucement de cette valeur.
Avant que Bhargava et Shankar ne s'intéressent au sujet en 2010, on s'était arrêté à un rang moyen inférieur à 1.79. Mais la démonstration de cette valeur sous-optimale utilise comme acquis la démonstration de l'hypothèse de Riemann et de la conjecture de Birch et Swinnerton-Dyer (deux conjectures à un millions de dollars que l'on est très loin d'avoir percé).
Aujourd'hui, on sait que le rang moyen des courbes elliptique est inférieur à 1.17, et pas besoin de théorèmes non démontrés pour le prouver. C'est en particulier ce théorème qui a permis à Bhargava d'obtenir la médaille Fields.

Le théorème 290.
Un dernier théorème de Bhargava que j'apprécie tout particulièrement : le théorème 290 ! Il dit la chose suivante :

On considère une forme quadratique définie positive à coefficients entiers.
Si elle peut représenter les 29 nombres suivants :
1, 2, 3, 5, 6, 7, 10, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 34, 35, 37, 42, 58, 93, 110, 145, 203, and 290
alors, elle peut représenter n'importe quel nombre entier (on dit qu'elle est universelle).

Par exemple, le polynôme Q(x,y,z,t) = x²+y²+z²+t² est une forme quadratique définie positive à coefficients entiers.
On peut vérifier qu'il existe un moyen d'écrire 
tous les nombres de la liste avec ce polynôme : 1 = Q(1,0,0,0), 2 = Q(1,1,0,0), 31 = Q(5,2,1,1), etc. D'après le théorème 290, tous les nombres entiers 
Autrement dit, n'importe quel nombre peut être écrit comme somme de (au plus) 4 carrés. Cette propriété porte un nom, c'est le théorème des quatre carrés de Lagrange. Le théorème 290, lui, permet de généraliser le théorème de Lagrange en fournissant un critère d'universalité des formes quadratiques. (à noter tout de même que le théorème de Lagrange intervient dans la démo du théorème 290)
Par contre, le polynôme Q(x,y,z) = x² + y² + z² échoue au test, puisqu'il est impossible d'écrire 7 comme somme de trois carrés : ce polynôme n'est pas universel.

Les 29 nombres de l'énoncé sont optimaux : pour chacun de ces entiers, il existe une forme quadratique représentant l'ensemble des entiers sauf lui. Par exemple, la forme quadratique x² + 2y² + 2z² + 5t² représente tous les nombres, sauf 15 !

Ce critère a permis à Bhargava de compléter la liste des forme quadratiques quaternaires (à 4 inconnues) universelles. Alors que Ramanujan pensait qu'il n'y en avait que 54, Bhargava a montré qu'il y en avait en fait 6436 !


Sources
The Work of Manjul Bhargava

Composition and Bhargava's cube, Florian Bouyer

Answers on a donut – the Fields medal lecture of Manjul Bhargava, Rachel Thomas

Universal quadratic forms and the 290-Theorem, Manjul Bhargava and Jonathan Hanke

Manjul Bhargava, médaille Fields 2014, Étienne Ghys
Le rang des courbes elliptiques, François Brunault

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



  1  2  3  4  5    Fin »