Choux romanesco, Vache qui rit et intégrales curvilignes

05 juillet 2016

Deux (deux ?) minutes pour le théorème de Bézout

C'est un théorème auquel javais déjà consacré un article il y a quelques temps, mais je l'aime beaucoup, et je n'ai pas résisté à l'envie de l'animer : le théorème de Bézout.

Vignette

Transcription augmentée

En 1764, le mathématicien français Étienne Bézout publie “Recherches sur le degré des équations résultantes de l'évanouissement des inconnues et sur les moyens qu'il convient d'employer pour trouver ces équations (je n'ai pas eu le courage de donner le nom en entier, ma vidéo ne dure que "2" minutes)”, un mémoire dans lequel il détaille sur une cinquantaine de pages des méthodes pour résoudre des équations polynomiales. Il en résultera alors le théorème de Bézout, un théorème fondamental de la géométrie algébrique. Ça tombe bien, j’ai deux minutes pour en parler…

A noter que je prononce le nom de ce mathématitien "bÉzout" ou non "bEzout". Les deux prononciation ont l'air de coexister, tout comme les deux orthographes "Bézout" ou "Bezout" (voir l'article d'investigation de Olivier Leguay)

Attention. Cette vidéo parle de géométrie algébrique. Il y sera donc question de géométrie, mais aussi d’algèbre. Vous voilà prévenus.

Si jamais on me demande quel est mon théorème préféré, je répondrai, probablement après un trop long temps d’hésitation, le théorème de Bézout. Il présente en effet tout ce qui fait le sel de la recherche en mathématiques, le passage d’un énoncé simple, intuitif mais faux à quelque chose de plus rigoureux, forcément plus complexe, mais plus profond. Bon, jusqu’à présent, personne ne m’a encore posé cette question, mais je garde cette réponse dans un coin au cas où.

Le théorème de Bézout énonce ceci. Si deux entiers relatifs a et b sont premiers entre eux, alors il existe deux autres entiers relatifs x et y tels que ax + by = 1, et réciproquement. En fait, ce théorème porte plutôt le nom d’identité de Bézout, ou de théorème de Bachet-Bézout, et ce n’est pas du tout de celui-ci que je veux parler aujourd’hui.

Je vais en fait parler du théorème de Bézout en géométrie algébrique, qui énonce ceci.Deux courbes algébriques planes respectivement de degré n et de degré p possèdent exactement n × p points d’intersection.

Le théorème de Bachet-Bézout est un théorème que l'on voit dans le programe de spécialité mathémathématiques en terminale S. Le théorème de Bézout en géométrie algébrique est plutôt rencontré au niveau master.

    Pour comprendre l’énoncé, il faut bien sûr comprendre ce qu’est une courbe algébrique planes, et ce que représente leur degré. Les plus simples sont les courbes de degré 1, puisqu’il s’agit des droites du plan. On dit que ces courbes sont algébriques dans le sens où elles possèdent une équation polynomiale. Celle-ci a par exemple pour équation x + 2y – 8 = 0, celle-là a pour équation x – 4 = 0, et ainsi de suite. De manière plus générale, on peut trouver pour n’importe quelle droite une équation de la forme P(x,y) = 0, où P est un polynôme d’inconnues x et y et de degré 1.

Un peu plus compliqué, on a les courbe algébriques de degré 2, c’est à dire, les courbes définies par une équation de la forme P(x,y) = 0, où P est un polynôme de degré 2. Ces courbes portent le nom de coniques. On y retrouve, entre autres, les cercles, les ellipses, les paraboles, les hyperboles, mais aussi les couples de droites. Toutes ces courbes peuvent être décrites par une équation polynomiale à 2 inconnues et de degré 2, c’est à dire une équation où les inconnues x et y apparaissent au moins une fois sous la forme d’un produit xy ou d’un carré x² ou y². Je n'ai finalement pas donné la définition rigoureuse d'une équation polynomiale. J'espère que vous me le pardonnerez.  Ce cercle centré en (1,1) et de rayon 2 est bien une courbe algébrique de degré 2, puisque les coordonnées (x,y) de ses points vérifient tous l’équation x² + y² – 2x – 2y – 2 = 0 (c'est à dire (x-1)²+(y-1)²=2²).

Les courbes de degré 3 portent le nom de courbes cubiques, et il en existe une belle ribambelle de différentes formes.

De façon plus générale, une équation polynomiale de n’importe quel degré permet de définir une courbe algébrique. Cette équation là, qui est de degré 6, décrit cette courbe appellée quadrifolium. Autre exemple avec celle-ci, de degré 5, qui décrit une courbe appellée quintique de l’Hopital.

Bref, les courbes algébriques sont les courbes définies par une équation polynomiale, et c’est ce qui se fait de plus joli en terme de courbes mathématiques.

 Revenons donc au théorème de Bézout, qui dit que deux courbes algébriques planes  respectivement de degré n et de degré p possèdent exactement n × p points d’intersections.

En prenant deux courbes de degré 1, c’est à dire des droites, on a bien 1 × 1 = 1 point d’intersection.

En prenant une droite, de degré 1, et une conique, de degré 2, on retrouve bien 1 × 2 = 2 points d’intersection.

Avec deux coniques, les courbes de degré 2, on retrouve bien 2 × 2 = 4 points d’intersection.

Avec une courbe de degré 4 et une courbe de degré 2, on retrouve bien 2 × 4 = 8 points d’intersection.
On pourrait multiplier les exemples.

Le théorème de Bézout fonctionne donc comme il faut, tout le monde est content… Enfin, presque. Je vous entends déjà derrière votre écran, en train de préparer plein de contre-exemples pour me prouver que j’ai tort. C’est vrai, l’énoncé que je vous ai donné est trop simple pour être honnête, mais on va tenter de le parfaire !

 Premier contre-exemple. Voici deux courbes algébriques, chacune de degré 1. Des droites, en fait. Où se trouve leur point d’intersection ?

Pour le trouver, est nécéssaire de se tourner vers une branche de la géométrie appellée la géométrie projective. Les deux droites se coupent bien, mais sur une ligne imaginaire, appelée l’horizon. En effet, si je penche ma caméra pour regarder ce qu’il se passe au loin, je ne peux que constater que les deux droites ont bien un point d’intersection, mais sur cette droite d’horizon. En géométrie projective, il est donc tout à fait justifié de dire que deux droites parallèles ont un point d’intersection, car c’est la branche des mathématiques qui s’occupe de modéliser les notions de perspective et d’horizon.

 Un point important que j'aurais du préciser dans la vidéo, c'est que l'analogie de la rotation de caméra pour observer ces fameux points à l'infini se justifie mathématiquement, mais n'est pas complètement rigoureuse. On peut donc penser que deux droites parallèles admettent deux points d'intersection à l'infini, un ans un sens, et l'autre dans l'autre. Ces deux points ne sont en fait qu'un seul et unique "point à l'infini".
En fait, ce que l'on appelle un "point à l'infini" n'est pas à proprement parler un "point" au sens où on l'entend, mais plutôt une famille de droites. On peut définir plus rigouresement un "point à l'infini" comme étant une direction (horizontal, vertical, etc) des droites. Le "point à l'infini" évoqué dans la vidéo est la famille des droites parallèle à la droite d'équation y = 4x, que l'on peut interpréter comme le point de fuite de ces droites sur l'horizon de votre choix (vous pouvez penchez la caméra comme vous le voulez, ce cera toujours le même point que l'on observera). 

 Deuxième exemple. On prend cette parabole, courbe de degré 2, et cette droite de degré 1. On constate un seul point d’intersection, mais le théorème de Bézout en implique deux. Le deuxième est en fait situé lui aussi sur la ligne d’horizon.

Cette opération de rotation de caméra se traduit parfaitement en équation mathématiquement, mais je ne détaillerai pas l’aspect technique ici. Même si ce point d’intersection peut sembler un peu artificiel, il doit être pris en compte.

 Bref, il faut corriger l’énoncé du théorème de Bézout :

Deux courbes algébriques projectives planes respectivement de degré n et de degré p possèdent exactement n × p points d’intersection.

Deuxième contre-exemple. Voici deux courbes algébriques, chacune de degré 2, qui ont donc 4 points d’intersection. On voit bien deux points d’intersection, mais où se trouvent les deux autres ?

Pour le découvrir, on va mettre le problème en équation. On cherche les points de coordonnés (x,y) qui vérifient à la fois x² + y² = 2 et y² = x. En substituant y² à x dans la première équation, on doit donc résoudre x² + x = 2, qui a pour solutions x = 1 et x = – 2.

En remplaçant x par 1 dans la deuxième équation, on obtient y² = 1, soit y = 1 ou y = –1. On retrouve donc les coordonnées (1 ; 1) et (1; – 1), c’est à dire celles des deux premiers points visibles.
Au contraire, si on remplace x par – 2 dans la deuxième équation, on obtient y² = –2. Cette dernière équation n’a pas de solutions réelles. Cependant, les nombres complexes sauvent la mise, puisque l’équation admet tout de même deux solutions complexes, qui sont i√2 et –i√2. On obtient alors les deux autres points d’intersection, de coordonnées (–2, i √2) et (–2;–i√2). Ils ne sont pas visibles directement puisqu’ils se trouvent dans le plan complexe, mais on a bien nos quatre points d’intersection promis.

 On peut se poser la question : existe-t-il un moyen simple de visualiser ces points complexes d'intersection ? Ces moyens existent, mais ils ne sont pas simples. Le plan réel possèdent deux dimensions : x et y. Le plan complexe, lui, compte 4 dimensions réelles : Re(x), Im(x), Re(y) et Im(y). Dans ce plan complexe, une courbe algébrique est donc une surface bidimentionnel (car un nombre complexe possède 2 dimensions réelles) dans un espace de dimension 4. La dimension 4 restera toujours difficile à appréhender à nous, pauvres habitants d'un monde tridimentionnel. On peut cependant interpréter une courbe algébrique complexe comme étant une courbe qui évolue en fonction du temps dans un espace 3D.

Il peut d’ailleurs aussi arriver que l’ensemble des points d’intersection soit dans le plan complexe, comme c’est le cas quand on cherche l’intersection entre ce cercle et cette parabole. Les quatre points d’intersection existent bel et bien, mais ont tous des coordonnées complexes.

 Bref, il faut corriger l’énoncé du théorème de Bézout :

Deux courbes algébriques projectives complexes planes respectivement de degré n et de degré p possèdent exactement n × p points d’intersection.

 Troisième contre-exemple. Voici deux courbes algébriques, l’une de degré 1 et l’autre de degré 2, qui ont donc 2 points d’intersection. On voit bien un point d’intersection, mais où se trouve l’autre ?

 Eh bien, dans ce cas, les points d’intersection sont en réalité tous les deux exactement au même endroit. On dit en fait que ce point est de multiplicité 2. C’est ce qui arrive lorsque les deux courbes sont tangentes l’une à l’autre.

 En fait, on peut faire correspondre la multiplicité d’un point aux nombres de points d’intersections qui apparaissent lorsque l’une des courbes est légèrement transformée. Cette définition n’est pas rigoureuse, mais elle permet de comprendre ce qui se passe. Dans le cas de la droite tangente au cercle, un léger déplacement de cette droite peut faire apparaitre deux vrais points d’intersection.

 Autre exemple. Où se trouvent les trois points d’intersection entre cette courbe cubique, de degré 3, et cette droite, de degré 1 ? Eh bien, ils sont tous les trois au même endroit. Pour le voir, il suffit de perturber un peu la cubique, ce sont bien trois points d’intersection qui apparaissent.

 Un dernier exemple, avec cette droite, de degré 1, et cette cubique, de degré 3. Où se trouvent les trois points d’intersection ? Dans ce cas, la cubique s’auto-intersecte, si bien qu’il semble légitime de compter double ce point d’intersection. C’est bien le cas, puisqu’en déplaçant légèrement la droite, ce sont deux points d’intersection qui apparaissent.

 Bref, il faut corriger l’énoncé du théorème de Bézout :

Deux courbes algébriques projectives complexes planes respectivement de degré n et de degré p possèdent exactement n × p points d’intersection, comptés avec leur multiplicité.

Bien sûr, on peut mélanger tout ces concepts. Par exemple, où se trouvent les deux points d’intersection entre cette hyperbole, courbe de degré 2, et de cette droite, de degré 1 ?

Il y a bien un point d’intersection à l’infini, mais celui-ci compte en fait double. En effet, quand on déplace légèrement la droite, on voit bien apparaitre deux points d’intersection, dont un se trouve toujours sur la ligne d’horizon. C’est en fait ce qui arrive lorsque deux courbes sont asymptotes l’une à l’autre.

Je termine par un dernier exemple un peu mindfuck. Où se trouvent les quatre points d’intersection de ces deux cercles concentriques ? Eh bien là, il est nécéssaire de passer par les calculs pour voir que les quatre point d’intersection sont en réalité deux points de multiplicité 2, mais que ceux-ci se trouvent sur une ligne à l’infini, mais une ligne à l’infini complexe. Oui, cela semble n’importe quoi, mais ce ne sont pas trois barrières d’abstraction qui vont suffir à rendre faux ce bon théorème de Bézout.

Il reste un dernier contre-exemple à prendre en compte. Où se trouvent les 4 points d’intersection entre ce couple de droites (qui est une courbe algébrique de degré 2) et ce couple-ci, lui aussi de degré 2.

Ici, ce ne sont pas quatre points d’intersection que l’on peut voir, mais bien une infinité. En fait, les deux courbes ont ce que l’on appelle une composante commune, c’est à dire un morceau que l’on retrouve à l’identique sur les deux courbes. C’est ce qui arrive lorsque les polynômes ont un facteur en commun. On préfère ne pas prendre en compte ces cas dégénérés, puisque c’est finalement le seul contre-exemple qui limite vraiment la validité du théorème.

Bref, il faut corriger l’énoncé du théorème de Bézout :

Deux courbes algébriques projectives complexes planes sans composantes communes respectivement de degré n et de degré p possèdent exactement n × p points d’intersections, comptés avec leur multiplicité.

On a donc enfin un énoncé qui a l’air correct. Il ne reste plus qu’à le démontrer, et le tour est joué. La preuve est technique, donc je préfère ne pas en parler. En fait, cet énoncé illustre assez bien une part de la recherche en mathématiques. On part d’un énoncé intuitif, et on essaye de le pousser dans ses retranchements pour déterminer quelles sont les meilleures hypothèses. Les mathématiciens sont des gens têtus, et quand il tiennent un énoncé pratique même un peu bancal, ils font tout pour le rendre juste. Cela implique parfois de changer de point de vue, comme lorsque l’on a été amené à considérer les courbes comme projectives puis complexes, ou bien de construire de nouveau concept, comme celui de la multiplicité. Le mathématicien cherchera ensuite à le généraliser à des espaces de dimensions supérieures, ou à d’autres structures que celui des nombres complexes. En l'occurence, si vous vous renseignez sur ce théorème dans des livres de géométrie algébrique, il sera présenté non pas sur l'ensemble des nombres complexes, mais sur des corps quelconques (des structures algébriques qui partagent les propriétés calculatoires intéressantes des nombres réels usuels). Ce sont en fait ces généralisations qui ont des applications concrètes en cryptographie.

Il existe d’ailleurs une formulation alternative du théorème de Bézout qui n’a pas besoin de prendre en compte toutes ces considérations projective ou complexe, et qui énonce ceci :

Deux courbes algébriques planes sans composantes communes respectivement de degré n et de degré p possèdent au plus n × p points d’intersection.

C'est en fait ce théorème qui a été démontré par Etienne Bézout en 1764. Sa démonstration utilise la théorie des résultants, un concept bien connu de ceux qui préparent l'agréagation (et que l'on ne retrouve que très peu en dehors de ce concours).

Seulement voilà, les mathématiciens n’aiment pas les solutions de facilité. Quand on tient un bel énoncé, pourquoi chercher à le minimiser quand on peut faire le contraire ?

Bref, le théorème de Bézout est l’un des premiers théorèmes que l’on croise en géométrie algébrique, l’un des principaux domaine étudié aujourd’hui dans les labos de mathématiques.

Un haut-fait de la discipline est la résolution de la conjecture de Fermat, qui énonce que l’équation xⁿ + yⁿ = zⁿ n’a pas de solution entière dès que n est strictement supérieur à 2. Le mathématicien anglais Andrew Wiles est parvenu en 1995, grâce à son indubitable génie et aux courbes elliptiques, une classe particulière de courbes algébriques, à démontrer ce théorème de Fermat qui résistait depuis presque 360 ans. Début 2016, on a d’ailleurs remis à Wiles le prix Abel, l’une des plus prestigieuses récompenses en mathématique.

On trouve aussi de nombreuses applications de ces courbes elliptiques  en cryptographie. Elles permettent de mettre au point des méthode de chiffrement particulièrement puissantes, et qui c’est sûr marqueront le futur. Mais ça, c’est une autre histoire.

 


Sources :
Bézout et les intersections de courbes algébriques, sur Bibnum.
Un « savant » du siècle des Lumières : Étienne Bézout (1730-1783),mathématicien, académicien et enseignant, Liliane Alfonsi
Introduction à la géométrie algébrique et courbes elliptiques
Bézout’s Theorem: A taste of algebraic geometry, Stephanie Fichett

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

08 avril 2016

Deux (deux ?) minutes pour l'hypothèse de Riemann

Elle m'a pris du temps, mais voici enfin une nouvelle petite vidéo où il est question du "problème mathématique le plus difficile du monde".

Deux (deux ?) minutes pour... l'hypothèse de Riemann

Transcription + commentaires

En 1859, Bernhard Riemann publie “Sur le nombre de nombres premiers inférieurs à une quantité donnée”, un article de théorie des nombres où il évoque pour la première fois la question des points d’annulation d’une certaine fonction. Cette question lui semble sur le moment intéressante, mais pas au point de creuser davantage le sujet. Ce qu’il ne sait pas encore, c’est qu’il vient de poser la première pierre à la question encore ouverte la plus importante de toutes les mathématiques, mise à prix aujourd’hui à un million de dollars et sur laquelle plusieurs générations de mathématiciens se sont cassés les dents : l’hypothèse de Riemann. Si vous vous êtes toujours demandé quel est le plus difficile des problèmes auxquels les mathématiciens ont affaire, ça tombe bien, j’ai deux minutes pour en parler.

 

Quand on veut résumer la question, tout bon mathématicien vous dira sans sourciller que l’hypothèse de Riemann conjecture que les zéros non triviaux de la fonction ζ ont une partie réelle égale à ½. L’information est exacte, mais on est pas plus avancé. Qu’est ce qu’un zéro non trivial ? C’est quoi cette histoire de partie réelle ? Et surtout, c’est quoi cette fonction ζ ?

L’hypothèse de Riemann est considérée comme l’un des problèmes les plus difficiles des mathématiques, et présente aussi le défaut d’être plutôt ardu à expliciter. Je présente donc d’avance mes excuses aux néophites : je vais parler de fonctions complexes, de sommes infinies et probablement de nombres premiers, il est donc possible que certains détails vous passent complètement au-dessus de la tête. Mes excuses également aux experts : je ne vais aborder que les grandes lignes, juste pour donner l’idée de la question posée par l’hypothèse, rien de plus.

 

L’histoire débute en 1734, lorsque Leonhard Euler, encore lui, s’intéresse à un problème connu aujourd’hui sous le nom de “problème de Bâle”. Bâle, comme la ville, pas comme celle du tennis. La question est de savoir à combien est égale la somme infinie des inverses des carrés, c’est à dire, combien vaut la somme 1 + ¼ + 1/9 + 1/16 + 1/25 + …. Quand on calcule cette somme avec seulement quelques termes, on trouve successivement 1 puis 1.25, puis 1.36, puis 1.42, et ainsi de suite. Ce que l’on est capable de dire à l’époque, c’est que cette somme infinie a un résultat qui n’est pas infini, mais impossible de dire à combien cela peut bien être égal. Heureusement, Leonhard Euler a une intuition assez dingue, et détermine le résultat de cette somme, avec un tour de passe-passe assez audacieux : il applique à la fonction sinus une propriété qui n’est normalement vraie que pour les polynômes. Enfin bref. Sa conclusion : cette somme est complètement égale à π²/6, soit un peu plus de 1.64. Avant lui, personne n’aurait pu imaginer l’intrusion du nombre π dans ce calcul n’ayant semble-t-il aucun rapport avec les cercles. Sa démonstration n’est sur le moment pas très rigoureuse, mais c’est tout de même une véritable prouesse d’en avoir déterminé la valeur exacte.

 

Euler ne s’arrête pas en si bon chemin et poursuit ses investigations sur les sommes d’inverses de puissances, et trouve, par exemple, que la somme infinie 1 + 1/16 + 1/81 + 1/256 + ..., c’est à dire, la somme des inverses des puissances 4, est égale à π⁴/90. Il trouve aussi que la somme des inverses des puissances 6 est π⁶/945. En fait, il trouve une formule pour toutes les puissances qui sont paires.

 

Par contre, pour les puissances impaires, il bloque complètement, mis a part pour la puissance 1. Dans ce cas de figure, la somme des inverses des nombres à la puissance 1 n’est autre que la somme infinie 1 + ½ + ⅓ + ¼ + ⅕ + …, autrement dit, la série harmonique que j’avais évoqué dans ma vidéo sur l’escargot de Gardner. Cette somme là ne peut pas valoir autre chose que l’infini.

Pour la somme 1 + 1/8 + 1/27 + 1/64 + …, c’est à dire, la somme des inverses des cubes, Euler ne trouve aucune formule pratique. Il faut dire que, aujourd’hui, presque 300 ans plus tard, on n’en sait pas tellement plus que lui. On peut seulement dire que cette somme vaut environ 1.202, et on sait depuis 1977 que ce nombre n’est pas rationnel, c’est à dire qu’il n’est pas égal à une fraction de deux entiers. Ce nombre semble avoir bien d’autres propriétés interessantes, mais elles restent aujourd’hui inatteignables.

 

Pour évoquer toutes ces découvertes sous une même bannière, Bernhard Riemann invente la fonction ζ. La fonction ζ est la fonction qui associe à un nombre s la somme infinie des inverses des puissances de s. Ainsi, on peut dire que  ζ(2) = π²/6, que ζ(3) vaut environ 1.202, que ζ(4) = π⁴/90. On peut même  dire que ζ(1) = ∞.

On peut faire le lien entre ce résultat ζ(2) = π²/6 et le fait que la probabilité que deux nombres entiers choisis au hasard soient premiers entre eux soit 6/π² (théorème de Cesàro). Ce n'est pas du tout un hasard, puisque, moyennant la formule d'Euler explicité dans la suite de la vidéo, la démonstration du théorème de Cesàro fait intervenir la fonction ζ.

 

Rien n’empêche non plus de calculer ζ pour des valeurs non entières. Par exemple, ζ(1.5), qui vaut 1 + 1/(2^1.5) + 1/(3^1.5) + …, vaut dans les 2.61.

En fait, cette formule de ζ permet de donner une image à n’importe quel nombre plus grand que 1.

Pour les nombres plus petits que 1, c’est autre chose. Par exemple, si on cherche à calculer ζ(0), on se retrouve à devoir calculer la somme infinie 1+1+1+1+1…, qui est naturellement égale à l’infini. Si on cherche à calculer ζ(-1), c’est la somme infinie 1+2+3+4+5+... que l’on se retrouve à devoir calculer, qui est bien entendue elle aussi égale à l’infini. Comment pourrait-elle l’être autrement, de toutes façons ?...  En fait, pour n’importe quelle valeur inférieure à 1, l’expression de ζ aboutira à un résultat infini. Cette fonction ζ ne semble donc intéressante que lorsqu'elle est calculée pour les nombres réels strictement plus grands que 1.

 

Mais il y a quand même quelque chose à creuser là-dessous. Que se passe-t-il si l’on cherche à évaluer cette fonction ζ sur les nombres complexes ? En schématisant grossièrement, les nombres complexes sont une sorte de nombres qui se situeraient non plus sur l’axe des nombres réels, mais sur un plan à 2 dimensions. Un nombre complexe peut donc être identifié à un point de ce plan complexe, mais il s’agit bien de nombres sur lesquels on peut faire les opérations habituelles : additions, soustractions, multiplications, divisions, etc. On appelle partie réelle d’un nombre complexe l’abscisse du point qui lui correspond dans le plan complexe, et partie imaginaire son ordonnée. Je vous renvoie à ma vidéo sur l’ensemble de Mandelbrot où je détaille davantage le sujet.

Bref. Revenons à ζ. Si je prend le nombre complexe 2+i et que je lui applique la fonction ζ, que se passera-t-il ? D’après la définition, il faut calculer 1 + 1/2²⁺ⁱ + ⅓²⁺ⁱ et ainsi de suite. Ça oblige à définir des puissances et des sommes infinies sur les nombres complexes, mais pour un mathématicien chevronné, cela ne pose en fait aucun problème. Les calculs feront intervenir les fonctions trigonométriques et logarithmiques, mais c’est moins méchant que ça n’en a l’air au premier coup d’oeil. Ce qui ne pose aucun problème, c'est d'élever un nombre positif (comme c'est le cas ici) à une puissance complexe. Dès qu'il s'agit d'élever un nombre négatif ou complexe à une puissance complexe, il faut prolonger la fonction ln, et les choses se compliquent atrocement.

 

On peut alors sans problèmes calculer chacun des termes de la somme infinie 1 + ½²⁺ⁱ + ⅓²⁺ⁱ + .... Plus on calcule de termes de la somme, plus on se rapprocher du nombre complexe 1.15 - 0.44i. On peut donc dire que c’est la valeur de ζ(2+i).

Mais si on essaie de faire la même chose sur le nombre complexe 1+i, cela ne fonctionne pas tout à fait comme prévu. La somme infinie n’est pas égale à l’infini, mais elle ne converge pas non plus. En fait, quand on calcule les termes de la somme, on ne se rapprochera jamais d’une valeur complexe en particulier. On ne peut donc pas définir ζ(1+i) de cette façon là.

Et ce problème là touche tous les nombres complexes ayant une partie réelle inférieure ou égale à 1, ce qui prive notre belle fonction ζ de toute une région du plan complexe. Ce qui est dommage, c’est dans cette région que la fonction ζ est la plus intéressante. Il nous faut donc la prolonger !

 

Et prolonger des fonctions, les mathématiciens savent faire. Mais il y a les bons prolongements, et les mauvais prolongements. Les bons prolongements étendent des fonction sur des domaines plus grands. Les mauvais aussi, sauf que ce ne sont pas des bons prolongements.

Bon. Prenons par exemple ce morceau de courbe. Je peux le prolonger de différentes façons : comme ça, comme ça ou même comme ça. Vous en conviendrez, ces trois façons de faire prolongent ma courbe, mais la première est sans doute la meilleure. Il n’y a pas de façon absolues de bien faire, mais en prolongeant ma courbe de façon rectiligne, je conserve une propriété importante : c’est une droite ! Un bon prolongement se doit donc de conserver les propriétés de ce qu’il prolonge.

Pour la fonction ζ, le principe est la même. Cette fonction a la bonne idée d’être ce que l’on appelle une fonction holomorphe. Je ne vais bien sûr pas rentrer dans la technique, mais c’est en gros l’équivalent pour les fonctions complexes d’être dérivable. Et être holomorphe, c’est cool, puisqu’il n’existe jamais plusieurs façons différentes de prolonger les fonctions holomorphes.

Il s'agit du théorème de prolongement analytique. Si une expression holomorphe f(s) est égal à celle de ζ(s) au moins sur un petit domaine où les deux expressions sont définies, alors f est non seulement un bon prolongement de ζ, mais surtout, n'importe quel autre prolongement de ζ sera égal à f. Dès qu'il s'agit de fonction holomorphes, il n'y a toujours qu'une seule façon de prolonger (les formules sont éventuellement différentes, mais seront toutes égales là où elles sont définies).

 

Du coup, n’importe quelle formule vérifiant cette condition d’être holomorphe est un bon candidat. Et des formules qui prolongent ζ, il n’y a qu’à se baisser pour en trouver.

Je donne dans la vidéo deux formules prolongeant ζ. La première est le prolongement via la fonction êta de Dirichlet η(s) = Σ (-1)ᵏ⁺¹/kˢ, où ζ(s) = η(s)/(1-2⁻ˢ). Etant donné que cette expression est définie pour tout nombre complexe s vérifiant Re(s)>0 (et 1-2⁻ˢ ≠0), on obtient un premier prolongement sur le demi-plan x>0. Le second prolongement est la relation fonctionelle ζ(s) = 2<sup>s</sup> π s-1 sin(πs/2) Γ(1-s) ζ(1-s). Cette formule est valide partout (sauf en s=0 et en s=1), à condition que ζ ait préalablement été prolongée pour Re(s)>0 à cause du ζ(1-s). C'est bien le cas, grâce au prolongement via la fonction êta de Dirichlet.

 

Grâce à ces prolongement, on peut affirmer que la fonction ζ, que l’on avait définit au départ comme somme infini des inverses des puissances des nombres entiers, est maintenant défini sur l’ensemble de presque tous les nombres complexes.

Par exemple, ζ est maintenant définie en 0. Il suffit de prendre l’une des nombreuses formules définissant ζ, et de la calculer en 0, ce qui donnera - ½. Mais la formule originale calculée en 0 correspond à la somme infinie 1+1+1+1+1+1+1… Il n’est donc pas complètement faux de dire que, moyennant cette histoire de prolongement, que 1+1+1+1… = - ½. Oui, c’est bizarre.

Et ça l’est aussi pour la somme infinie 1+2+3+4+5+6+..., qui correspond à l’image de -1 par la fonction ζ. Définie comme somme infinie, on ne peut pas lui attribuer de valeurs, mais en calculant à l’aide d’une autre formule de ζ, on trouvera -1/12. Voilà pourquoi on dit parfois que 1+2+3+4+5+6… est égal à -1/12. Je conçois parfaitement que l’on puisse ne pas être d’accord avec ça. En tant que telle, cette somme infinie devrait valoir l’infini, mais si on se force à lui attribuer une valeur, la façon la plus naturelle de faire, c’est de prolonger la fonction ζ, ce qui ne peut pas donner autre chose que... - 1/12.

Et pour la série harmonique 1+½+⅓+¼+..., c’est à dire, pour l’image de 1, peut-on aussi lui attribuer une valeur ? Eh bien, les choses sont encore différentes. Selon la formule initiale, il faudrait calculer une somme infinie, ce qui vaut l’infini. En prenant les autres formules définissant ζ, et bien, c’est toujours le cas. Il n’y a en fait aucun moyen de prolonger la fonction ζ en 1, on dit que ce nombre est un pôle de la fonction. Quelle que soit la façon dont on s’y prend, la somme 1 +½+⅓+¼+..., vaudra toujours l’infini.

 

Bref, la fonction ζ, c’est une fonction définie sur presque tout le plan complexe. Elle pourrait n’être qu’une fonction vaguement intéressante si Leonhard Euler n’avait pas eu la mauvaise idée de lui trouver un lien avec les nombres premiers, c’est à dire les nombres comme 2, 3, 5, 7, 11 ou 45319. Les nombres premiers, ce sont les briques élémentaires de tous nombres entiers, puisque tout entier peut s’écrire de façon unique comme produit de nombres premiers. Au début, les nombres premiers n’étaient considérés que comme des amusettes pour les matheux, mais maintenant qu’ils ont une place de choix en cryptographie, on les prend davantage au sérieux. La question qui empêche de dormir de nombreux mathématiciens est de savoir comment ces nombres premiers se répartissent parmi les nombres entiers. On sait depuis très longtemps qu’il en existe une infinité, on sait a peu près estimer le nombre de nombres premiers inférieurs à un seuil donné, on sait dire si un nombre est premier ou non sans avoir à trop attendre et avec de relativement bonnes probabilités de ne pas se planter. Mais beaucoup, beaucoup, beaucoup de questions sur les nombres premiers attendent toujours une réponse.

 

Il se trouve que ζ(s), et c’est ce que Euler a découvert,  est égal au produit infini des nombres 1/(1-p⁻ˢ), où p désigne successivement tous les nombres premiers. Cela peut sembler anecdotique au premier abord, mais cette formule donne un lien réellement inattendu entre, à droite, la théorie des nombres premiers, c’est à dire, l’arithmétique, et à gauche, celle des fonctions complexes, c’est à dire l’analyse. Jusqu’alors, aucun lien entre ces domaines n’avait été observé. Et ça, ça change tout, puisque tous les problèmes posés en arithmétique peuvent grâce à cette relation être attaqués en passant par l’analyse.

Prouvons que ζ(s) = 1/(1-2-s1/(1-3-s)×1/(1-5-s)×1/(1-7-s)×.... On part de ζ(s) = 1 + 1/2ˢ + 1/3ˢ + 1/4ˢ + ... (*) , et on multiplie le tout par 1/2ˢ, ce qui donne 1/2ˢ ζ(s)1/2ˢ + 1/4ˢ + 1/6ˢ + 1/8ˢ + .... (**). En soustrayant (**) à (*), on se retrouve avec (1-1/2ˢ)ζ(s) = 1 + 1/3ˢ1/5ˢ + 1/7ˢ + 1/9ˢ + .... On a ainsi éliminé tous les dénominateurs divisibles par2. En procédant de la même façon après avoir multiplié par 1/3ˢ, on éliminera tous les dénominateurs divisbles par 3, c'est à dire, (1-1/2ˢ)(1-1/3ˢ)ζ(s) = 1 1/5ˢ + 1/7ˢ + ..... En répétant ces opérations, on finit par obtenir  (1-2-s(1-3-s)×(1-5-s)×(1-7-s)×(...)ζ(s) = 1, c'est à dire l'expression de Euler. Bien sûr, il s'agit ici d'une démonstration informelle qui peut être rendue rigoureuse par d'autres moyens.ζ(s)ζ(s)

 

Depuis, d’autres liens ont été découverts entre arithmétique et analyse, et la plupart passent par des fonctions du même acabi que ζ. Il n’y a donc plus d’autres choix, il faut comprendre cette fonction ζ. Mais pour obtenir des réponses intéressantes, il faut impérativement savoir où cette fonction est égale à zéro. En fait, pour bien comprendre comment se comporte une fonction, la recherche de ses points d’annulation est toujours un passage incontournable.  Et c’est là que ça coince. Mais où s’annule la fonction ζ ?

On peut rapprocher cette histoire de recherche des zéros de ζ à celle des zéros d'un polynôme : quand on connaît l'ensemble des points d'annulation d'un polynôme, on peut en donner son expression (à une constante multiplicative près).

 

On sait par exemple dire que les nombres -2, -4, -6 et tous les nombres pairs négatifs ont une image par la fonction ζ égale à 0. Puisqu’il n’a pas fallu attendre bien longtemps avant de montrer que ζ s’annule sur les entiers négatifs pairs, on dit donc qu’il s’agit des zéros triviaux de la fonction. Mais cette fonction ζ s’annule ailleurs. Elle s’annule par exemple au point 0.5+14.135 i, mais aussi en 0.5+21.022 i, ou au point 0.5+25.011i. Ce sont eux, les zéros non triviaux de la fonction ζ. Quand on dit que 0.5+14.135 i est un zéro non trivial, le nombre 14.135... est une valeur approchée (on ne connaît pas d'expression simples pour ce nombre). Cependant, la partie réelle 0.5 est une valeur démontrée exacte. 

Quand on mène les calculs plus loin, on s’aperçoit que tous ces zéros ont un point commun : ils ont tous la même partie réelle, qui vaut ½. Les investigations ont été poussées particulièrement loin, puisque 10 000 milliards de zéros non triviaux ont été calculés. Ils ont tous leur partie réelle égale à ½. Mais ça, ce ne sont que des observations. Beaucoup d’observations, mais seulement des observations. Et ça ne vaut pas grand chose pour un mathématicien. Ce que l’on veut, c’est une démonstration du fait que tous les zéros non triviaux possèdent cette même partie réelle égale à ½. Et c’est ça, l’hypothèse de Riemann. Les zéros non triviaux de la fonction ζ ont-ils tous une partie réelle égale à ½ ?

On sait tout de même pas mal de choses sur ces zéros non triviaux. On sait par exemple dire qu'ils sont tous situés dans la bande 0<Re(s)<1, et qu'il en existe une infinité. 

 

Quand Hilbert a donné en 1900 sa conférence dans lequel il a proposé une liste de 23 défis mathématiques à résoudre au plus vite, il a fait figurer en 8eme position l’hypothèse de Riemann. A propos de ce problème, il aurait même d’ailleurs déclaré : “si je devais me reveiller après avoir dormi 1000 ans, ma première question serait “l’hypothèse de Riemann a-t-elle été résolue ?”.”

Cent ans plus tard, le problème n’est toujours pas été résolu. L’institut de mathématiques Clay décide d’augmenter les enjeux, en proposant aussi une liste de questions à résoudre, les 7 problèmes du millénaire. Pour chacun des 7 problèmes, un million de dollars est réservé au mathématicien qui en viendra à bout. 16 ans plus tard, un seul des sept a été résolu, par un mathématicien qui a d’ailleurs refusé la récompense. Mais l’hypothèse de Riemann reste aujourd’hui debout.

 

Résumons un peu les choses. L’hypothèse de Riemann est l’un des problèmes mathématiques les plus difficiles du monde. Il y est question de la fonction ζ, qui porte en elle tout ce qu’il faut savoir sur les nombres premiers. Mais pour accéder à ces précieuses informations, il faut trouver où la fonction s’annule.

 

Le mathématicien ou la mathématicienne qui parviendra à identifier l’ensemble des zéros gagnera alors tous les attributs qui le transformera instantanément en le dieu unique des mathématiques : la richesse absolue, la célébrité internationale et la connaissance parfaite de la répartition des nombres premiers.

Si seuls les deux premiers points vous intéressent, l’hypothèse de Riemann n’est pas faite pour vous. Les mathématiciens confrontés au problème ne sont en fait intéressés que par une seule chose. Le troisième point...

Le dessin final dans la vidéo est la représentation graphique de l'argument de ζ(s) en fonction du nombre complexe s. Cette représentation est certe très jolie, mais n'est pas du tout pratique pour visualiser ses zéros. Voilà pourquoi j'ai préféré dans le reste de la vidéo la représentation du module de ζ(s) en fonction du nombre complexe s.
 

12 février 2016

Deux (deux ?) minutes pour l'hydre de Kirby & Paris

Hey ! Et pourquoi pas une nouvelle vidéo ? On y parlerai des nombres ordinaux et du jeu de l'hydre. Ca serait une bonne occasion de parler d'énoncés indécidables !

Vignette

 

Transcriptions + commentaires

En 1982, Laurie Kirby et Jeff Paris réinventent dans leur article “Résultats d’indépendances accessibles pour l’arithmétique de Peano” le mythe de Hercule contre l’hydre de Lerne. Un problème qui fournit pour la première fois un exemple plutôt concret de ce que peut être un problème indécidable. Ça tombe bien, j’ai deux minutes pour en parler...

Voici l’hydre de Lerne : un monstre fabuleux qui possède de nombreuses têtes et de nombreux cous. Dans le cadre du deuxième de ses douze travaux, Hercule doit l’affronter et le vaincre, et doit pour cela couper chacune de ses têtes. Le hic, c’est que lorsque l’hydre se fait décapiter, des têtes repoussent, et contrairement à la légende, il ne pourra pas appeler son neveu à la rescousse. Existe-t-il pour notre héros une stratégie qui permettrait d’empêcher à tout jamais cet horrible monstre de nuire ? Eh bien, oui, et les nombres transfinis sont là pour nous aider !
Vous pouvez tenter de jouer au jeu de l'hydre en suivant ce lien.

Détaillons un peu le mécanisme de régénération des têtes. Mathématiquement, l’hydre peut être représentée comme un graphe, et plus précisément, comme un arbre enraciné. Un arbre est une structure mathématique composée de différents nœuds reliés par des arêtes, mais qui ne présente aucun cycle. Sur un arbre, les nœuds situés aux extrémités sont appelés les feuilles. On dit que l’arbre est enraciné lorsque l’un des nœuds a été choisi pour en être la racine.
On peut assimiler l’hydre à un arbre, où son corps est la racine de l’arbre, ses têtes sont ses feuilles, ses cous sont ses arêtes, et les jonctions entre les cous sont les autres nœuds du graphe.
La régénération céphalique de l’hydre fonctionne de la façon suivante. Lorsqu’une tête est découpée, la feuille et l’arête correspondante sont retirées du graphe. L’hydre se renouvellera à partir du nœud situé en dessous de l’arête retirée, en générant plusieurs copies de la partie de l’arbre située au-dessus de ce nœud. Le nombre de copies créées par l’hydre sera à chaque étape le nombre de coups donnés par Hercule.
Ainsi, l’hydre fabriquera une seule copie lors de sa première régénération, puis deux à la deuxième, et ainsi de suite. A noter tout de même que lorsque Hercule découpe une tête directement reliée  au corps de la bête, celle-ci ne pourra pas se régénérer.
   La question que Hercule se pose est évidente : quelle stratégie doit-il accomplir pour réduire à néant le mastodonte ?

   Assez étonnamment, il existe des stratégies, et ça quelle que soit la taille initiale de l’hydre. Encore plus étonnant, une stratégie qui fonctionne toujours est de couper les têtes complètement au hasard jusqu’à extinction complète du monstre. Mais ce qui est encore plus étonnant, c’est que ce résultat est vrai, mais qu’il est impossible de le démontrer avec les outils de l’arithmétique comme la démonstration par récurrence, ce qui fait que ce résultat est un indécidable de l’arithmétique. Heureusement, on peut le prouver dans la théorie des ensembles, et on va même le faire tout de suite !

Pour vaincre l’hydre, nous avons besoin des nombres transfinis, qui font partie de la classe des nombres ordinaux. Si vous pensez que les raisonnements sur les cardinaux infinis auquel on a eu recours lors de cette histoire d’hôtel de Hilbert qui possédait une infinité de chambres était tordue, accrochez-vous… Les nombres transfinis, c’est encore pire.
    Comptons les nombres le plus loin possible. 0, 1, 2, 3, 4, et ainsi de suite, on peut aller aussi loin que l’on veut. Mais qu’est ce qui arrive juste après ? Eh bien, c’est à ce moment que les nombres transfinis rentrent en jeu. Après tous les nombres entiers vient naturellement l’infini, que l’on appellera ici ω. ω, c’est donc l’ordinal qui vient juste après l’ensemble de tous les nombres entiers.
Et après ? Eh bien, il n’y a pas de raison qui pourrait nous empêcher de compter plus loin. Il vient donc ensuite ω+1, ω+2, ω+3 etc… Tous ces nombres là sont appelés les ordinaux, parmi lesquels ont distingue d’un côté les nombres entiers, et de l’autre côté les nombres transfinis et, comme souvent dès qu’il s’agit d’infinis, ces nombres ont été créés par le génial Georg Cantor.

    Cette construction peut sembler complètement absurde au premier abord, mais elle a du sens dès que l’on cherche à décrire des ensembles infinis bien ordonnés, c’est à dire, des ensembles où l’on peut toujours dire entre plusieurs éléments lequel est le plus petit.
Reprenons l’hôtel de Hilbert, qui possède un nombre infini dénombrable de chambres. Les affaires étant florissante, un deuxième étage a été créé dans cet hôtel, deuxième étage qui lui aussi possède une infinité dénombrable de chambres. Tous les matins, le service d’étage passe dans chacune des chambres pour refaire le lit, arroser les plantes, remplir le minibar et changer les échantillons de shampooing. Ils visiteront donc chacune des chambres, en commençant par le rez-de-chaussée, puis en visitant ensuite le second étage. De cette façon, les chambres sont bien ordonnées, et on peut du coup les numéroter à l’aide des ordinaux : il y a d’abord les chambres du rez-de-chaussée, numérotées par 0, 1, 2, 3, 4, et ainsi de suite, puis, une fois que l’intégralité du rez-de-chaussée aura été visité, on pourra passer aux chambres du premier étage que l’on numérotera par des ordinaux transfinis : ω, ω +1, ω +2, ω +3 et ainsi de suite.

    Bref : les ordinaux permettent de numéroter, même au-delà de l’infini. Mais ils ne s’arrêtent pas là. Après ω, ω +1, ω +2, ω +3, et ainsi de suite, il y a un ordinal encore plus grand : ω + ω, que l’on nommera plutôt ω×2. Vient ensuite ω×2+1, ω×2+2, ω×2+3, et ainsi de suite. Tous ces nombres permettraient de numéroter des chambres d’un hôtel de Hilbert à deux étages.
On peut continuer encore, et ainsi de parler de ω×3, de ω×4, et ainsi de suite, pour numéroter les chambres d’un hôtel de Hilbert avec davantage d’étages. Mais rien ne nous empêche de continuer, et on peut donc parler de l’ordinal ω × ω, que l’on note plus commodément ω². Les ordinaux inférieurs à ω² permettent de numéroter les chambres d’un hôtel de Hilbert possédant une infinité d’étages.
Vient ensuite ω²+1, puis ω²+2, et, si on va toujours plus loin, on pourra parler de ω² × 2, qui correspondrait à un deuxième hôtel de Hilbert possédant une infinité d’étages avec une infinité de chambres par étages construit juste en face du premier hôtel.
Mais après ω² viennent des ordinaux comme ω²×2, ω²×3, et on peut poursuivre jusqu’à ω² × ω, c’est à dire, de ω³. Un tel ordinal permet par exemple de numéroter les chambres d’un complexe hôtelier possédant une infinité d’hôtels de Hilbert.
    Gardons tout de même en tête une chose : les ordinaux ne servent pas à dénombrer, mais bien à numéroter. Pour dénombrer un ensemble, c’est à dire, compter le nombre d’objets que contient cet ensemble infini ou non, on utilisera les nombre cardinaux. Par exemple, le cardinal 5 correspond au nombre de doigts d’une main, le cardinal ℵ₀ correspond au nombre de nombres entiers ou au nombre de chambres dans l’hôtel de Hilbert tandis que le cardinal ℵ₁ correspond au nombre de nombres réels.
L'affirmation de cette dernière phrase n'est vraie que si l'on admet l'hypothèse du continu (qui est un indécidable de la théorie des ensembles). Il aurait été plus juste d'écrire que c'est le cardinal 2^ℵ₀ qui compte le nombre de nombres réels.

Les ordinaux, eux, permettent de préciser la position d’un objet au sein d’un ensemble bien ordonné. L’ordinal 4 correspond à la position de l’auriculaire sur une main, l’ordinal ω précise la position de la première chambre de l’étage de l’hôtel de Hilbert, tandis que ω+1 est la position de chambre juste à côté.
On peut s'étonner qu'il existe des façons de parler des ensembles infinis : ordinaux et cardinaux. En fait, ce sont deux points de vue différents sur des mêmes objets mathématiques. Tous les ordinaux présentés dans la vidéo (qui s'écrivent avec le symbole ω et les opérations usuelles +, × et ^) permettront de numéroter les éléments d'ensembles dénombrables (possédant ℵ₀ éléments). On peut aussi numéroter les éléments d'ensembles comptant 2^ℵ₀ comme l'intervalle [0,1] avec des ordinaux, mais il faudra utiliser des ordinaux encore plus grand (les ordinaux indénombrables).

    Évidemment, on peut continuer toujours plus loin, et parler de ω⁴, de ω ⁵, de ω⁶, et ainsi de suite jusqu’à ωᵚ. La métaphore de l’hôtel de Hilbert commence à devenir difficile à tenir à présent, surtout que l’on peut toujours trouver des ordinaux plus grand, comme ωᵚ+1, voire ω^(ω²), voir même ω^(ω^ω), ou encore ω^(ω^(ω^ω)). Je m’arrête ici dans la construction des ordinaux, mais il faut retenir qu’elle peut toujours être poursuivie une infinité de fois. D’ailleurs, si vous poursuivez la construction une infinité de fois, elle pourra toujours être poursuivie. Mais je m’égare. Retenons simplement que l’on peut additionner et multiplier des ordinaux, et même former des puissances.
Si vous regardez en détail les tables d'additions, de multiplications et de puissances présents dans la vidéo, vous pourrez voir que les opérations sur les ordinaux sont loin d'être triviales. Par exemple, 1+ω = ω. Cela vient du fait que les nombres ordinaux, même si ils sont présentés sous forme de nombres, sont davantages des ensembles. La définition formelle de l'addition des ordinaux, tout comme celle de la multiplication, passe par la théorie des ensembles, un point que je ne voulais pas aborder pour ne pas rendre l'exposé trop technique. En fait, additionner des ordinaux revient à placer l'un à la suite de l'autre des ensembles ordonnés correspondant à cet ordinal. La somme 1+ω correspond à l'ordinal associé à la suite "un élément puis 0, 1, 2, 3, 4, 5, ...". Renumérotée, c'est l'ensemble des entiers naturels (correspondant donc à l'ordinal, ω). A l'inverse, la somme ω+1 est l'ordinal associé à la suite "0, 1, 2, 3, 4, ... puis un élément" ; on ne peut pas le renuméroter autrement qu'en parlant de "l'ensemble des entiers naturels puis un autre élément", ce qui correspond bien à l'ordinal ω+1 . En fait, on appelle ça une addition puisqu'elle correspond à l'addition sur les entiers naturels, mais c'est sans doute un mauvais terme pour appréhender la somme des ordinaux transfinis. Cela dit, cette non commutativité ne pose pas de problème dans le cas de l'hydre, il suffira juste d'additionner les termes du plus grand au plus petit (je ne l'ai pas précisé dans la vidéo dans un soucis de vulgarisation).

    Les ordinaux partagent avec les entiers une propriété réellement remarquable : toute suite strictement décroissante d’ordinaux atteint 0 en un nombre fini d’étapes. Cela signifie que si on prend une séquence de nombres ordinaux où chaque ordinal est strictement plus petit que le précédent, on finira toujours par tomber sur 0.
    Prenons l’exemple du room service dans un hôtel de Hilbert ayant un étage. Chaque chambre est donc numérotée par un ordinal : soit un nombre entier pour le rez-de-chaussée, soit un nombre de la forme ω+k, avec k entier, pour le premier étage. Notre agent est situé quelque part dans une chambre de l’étage, et s’aperçoit qu’il a oublié ses lunettes dans l’une des chambres précédentes. Il doit donc faire marche arrière, et retourner voir certaines chambres, en suivant un ordre strictement décroissant. Dans un premier temps, ce sont des chambres de l’étage qu’il revisitera, jusqu’à ce qu’il atteigne la chambre ω. Dans un second temps, ce sont les chambres du rez-de-chaussée qu’il faut retourner voir. Seulement, il y a une infinité de chambres, il est donc impossible de recommencer par la dernière, mais seulement par une chambre avec un très grand numéro. Si il visite les chambres en suivant un ordre décroissant, c’est donc un nombre fini de chambres qu’il visitera finalement au rez-de-chaussée, avant de s’arrêter à zéro.
L'important à comprendre ici, c'est qu'il n'existe pas d'ordinal qui viendrait juste avant ω. Il n'y a rien, chez les ordinaux, que l'on pourrait appeller "ω-1". Si l'employé suit les chambres en sivant un ordre décroissant, il visitera après ω une chambre du rez-de-chaussée. Cela peut être la chambre 1000 (dans ce cas, il visitera ensuitre au plus 1000 chambres), cela peut être la chambre 100000 (dans ce cas, il visitera ensuitre au plus 1000000 chambres), peu importe. Ce que l'on est sûr, c'est que cela sera une chambre portant un numéro fini, et dans ce cas, il visitera ensuitre au plus un nombre fini de chambres.

    Bref : si on décompte des ordinaux, on retombe toujours sur zéro. Et ça, ça permettra à Hercule de vaincre cette affreuse hydre.

    Revenons justement à notre hydre, et mesurons sa force. Cette mesure ne se fera pas avec des nombres entiers ou réels, mais avec des nombres ordinaux. On va définir la mesure de la force d’une hydre en associant à chaque tête, à chaque cou et à chaque nœud une certaine force. Pour cela, on commence par affecter à chaque tête le nombre 0, et à chacun des cous menant à une tête le nombre 1. Ensuite, pour chaque nœud où sont basés un ou plusieurs de ces cous, on y associe le nombre de cous.
    Pour les autres cous et nœuds, on procède de façon similaire. On associe à chacun des cous l’ordinal ωˣ, où X est la force du nœud juste au-dessus. Ceci est cohérent avec la règle 0 : si une tête a pour force 0, un cou menant à une tête a pour force ω⁰=1. On associe enfin à chaque nœud la somme des forces des cous qui y repose. Si on veut être tout à fait précis, et pour éviter les soucis de non comutativité de la somme d'ordinaux, il faut tout de même préciser que ces ordinaux doivent être sommés en suivant un ordre décroissant. Par exemple, ce morceau de cou mène à un nœud de force 2, il aura donc pour force ω puissance 2, c’est à dire ω². Sur le nœud juste en dessous repose un cou de force 1 et un cou de force ω². Il aura donc pour force ω² +1. Le cou inférieur a donc pour force l’ordinal ω puissance ω² + 1. On calcule la force des autres éléments du corps de l’hydre de la même façon, ce qui permet finalement de dire que cette hydre a pour force ω^(ω ² +1) + ω³ + 2.

    Cette définition de la force permet d’associer un ordinal à chaque hydre imaginable. Celle-ci a par exemple pour force ω^(ω^ω) + 1, tandis que celle-ci a pour force ω^(ω³+ω²). Puisque l’on peut toujours comparer deux ordinaux, on peut par exemple affirmer ici que l’hydre de gauche est plus puissante que l’hydre de droite.

    Hercule entre en scène, et coupe l’une des têtes. Quelle que soit la tête qu’il attaquera, il en résultera que la force globale de l’hydre diminuera. Par exemple, si la première tête qu’il attaque est celle-ci, la force de l’hydre deviendra ω^(ω ² +1) + ω² × 2+ 2, qui est une force strictement plus petite, puisque ω²×2 est un ordinal strictement inférieur à ω³. S’il attaque ensuite à cette tête là, la force de l’hydre devient ω^(ω×3+1) + ω²×2+ 2, qui est à nouveau strictement inférieur à la force précédente. En fait, quand une tête est coupée, bien que la largeur de l’arbre augmente, sa hauteur diminue. Ce que l’on mesure avec les ordinaux, c’est justement cette hauteur, qui diminue donc à chaque étape.
    En poursuivant sans relâche ces attaques, la force de l’hydre ne cessera de décroître. Puisqu’il s’agit d’une suite strictement décroissante d’ordinaux,elle finira forcément par tomber à zéro après un nombre non infini de décapitations.
On m'a plusieurs fois posé la question "pourquoi définit-on la force des hydres de cette façon et pas d'une autre ?". La raison est assez terre à terre : parce que si on la définit autrement, il y a des chances que l'on ne puisse pas conclure quand à la finitude du combat de Hercule. Plus précisément, en définissant la force de l'hydre ainsi, on s'assure que l'opération "couper une tête" entraînebien l'existence d'une suite strictement décroissante d'ordinaux, auquel on pourra appliquer le théorème "toute suite strictement décroissante d'ordinaux est finie". Si on décide, par exemple, de définir le poids comme "le nombre de têtes", on obtiendra une suite qui sera parfois croissante, parfois décroissante, et pour laquelle on ne pourra finalement pas dire grand chose d'intéressant.

Hydre_grahamBien sûr, le combat sera très certainement très long, mais on ne peut pas abattre un monstre mythologique sans un minimum de patience.
Je n'ai pas caculé le nombre minimal de coups nécéssaires pour anéantir l'hydre de la vidéo. On peut tout de même dire que ce nombre va être immensément grand. A titre d'exemple, l'hydre ci-contre demande pour être détruit un nombre de coups supérieur au nombre de Graham, qui est un nombre inimaginablement et démesurément immense (évoqué là-bas).

    Finalement, on vient de démontrer que, quelle que soit la forme de l’hydre et quelle que soit la stratégie de Hercule, celui-ci parviendra toujours à occire son opposant. Pour démontrer ce théorème de l’hydre, il nous a fallu passer par les ordinaux.

    Mais ce que Kirby et Paris ont prouvé dans leur article est en réalité bien plus génial : pour prouver que Hercule est toujours plus fort que l’hydre, on ne peut pas faire autrement que d’utiliser les ordinaux. La démonstration du théorème de l’hydre est en fait absolument impossible à réaliser avec les outils de l’arithmétique que l’on connaît, comme les opérations sur les nombres entiers ou la démonstration par récurrence.

    Le théorème de l’hydre est en fait ce que l’on appelle en logique un théorème indécidable pour l’arithmétique : un théorème qui est vrai mais qui ne peut pas être démontré au sein de cette théorie.
La notion d'énoncé "vrai" est un peu plus précise que cela en mathématiques. Pour dire qu'un énoncé est vrai dans une théorie donné des mathématiques (comme celle de l'arithmétique de Peano), il faut qu'elle soit vraie dans tous les modèles de cette théorie (le modèle le plus simple de l'arithmétique de peano est celui de la séquence de nombres 0-1-2-3-... que l'on trouve dans la théorie des ensembles ZF). En fait, le théorème de Kirby & Paris montre que l'énoncé est vrai dans la théorie des ensembles (et donc, dans le modèle classique de l'arithmétique), mais ne dit rien de sa véracité de façon générale. Il a donc été un peu précipité pour moi d'affirmer que l'énoncé est vrai sans plus de précisions.

C’est d’ailleurs ce qu’énonce le théorème de Gödel : la plupart des théories mathématiques contiennent des énoncés qui sont vrais mais qui ne peuvent pas y être démontrés. Mais ça, c’est une autre histoire...
Le théorème de Gödel fera peut être un jour l'objet d'un article ou d'une vidéo. Cela dit, le sujet est vaste et particulièrement pointu. Je ne veux donc pas m'y précipiter pour ne pas y dire trop de choses approximatives.


Quelques liens :
L'article de Kirby et Peano
Une excellente approche un peu vulgarisée des ordinaux, par David Madore
Tester le jeu de l'hydre : Hercule vs l'hydre

Posté par El Jj à 16:45 - Commentaires [13] - Permalien [#]
Tags : , , , ,
03 janvier 2016

2015+1 (Cette nouvelle année est-elle intéressante ? Episode 07)

Une nouvelle année débute ! Je n'ai pas réellement abandonné ce blog, je suis simplement sur un projet plutôt chronophage... Mais je ne vais pas abandonner ma tradition annuelle : zieuter l'OEIS à la recherche des propriétés du nombre correspondant à l'année commençante.

Chaque année, je revêts donc mes plus beaux habits d'arithmomancien, afin de donner mes prédictions sur l'année qui arrive. Au contraire d'une Elisabeth Tessier affirmant que "la Vénus de la France, à 3° Balance [...] est en dissonance avec le thème de Daech, créé le 28 juin 2014, dans le premier décan du Cancer" pour expliquer les attentats de novembre, l'arithmomancie est une pratique divinatoire sans risque, puisqu'elle ne se risque à aucune prédiction concrète. En janvier dernier, j'affirmais sur ce blog que l'année 2015 allait être intéressante, et elle l'a été [référence nécessaire] . Qu'en est-il de 2016 ? Ouvrons pour cela l'encyclopédie en ligne des suites entières (OEIS).
Rappelons tout de même que si une suite de nombres (entiers) est intéressante, elle sera présente dans cette encyclopédie. Ainsi, plus un nombre possède des propriétés intéressantes, plus il apparaît dans l'OEIS.

Les nombres 2013, 2014 et 2015 possèdent donc (au moment où j'écris cet article) respectivement 111, 106 et 179 propriétés intéressantes. Et 2016, dans tout ça ?... Eh bien...

2016 OEIS
2016 possède 783 propriétés intéressantes !

C'est absolument indubitable : l'année 2016 sera intéressante ! C'est même l'année la plus intéressante depuis (au moins) 100 ans, et pour les 100 ans à venir (à l'exception de 2048, mais j'en reparlerai dans 32 ans) ! Voyons un peu quelques raisons.

2016 est un nombre triangulaire [A000217]
Premier point important, 2016 est un nombre triangulaire, ce qui signifie que 2016 points peuvent être représentés comme ça :

2016 Triangle2016 fera mal aux yeux.

Plus précisément, on dit qu'un nombre est triangulaire si on peut l'écrire sous la forme 1+2+3+4+...+N (la forme triangulaire vient du fait que la 1ere ligne compte 1 point, la seconde 2 points, etc.). Les premiers nombres triangulaires sont donc 1, 3, 6, 10, 15, ....
Avec N=63, cela correspond à l'égalité 1+2+3+...+63 = 2016.

Puisqu'il est question de nombre triangulaire, il convient de rappeller la légende autour de l'enfance du mathématicien Carl Friedrich Gauss. Alors qu'il était âgé de 9 ans, son professeur lui aurait demandé de calculer de tête la somme 1+2+3+...+100, pensant avoir la paix durant de nombreuses minutes. Ce n'est qu'après quelques secondes que le jeune Gauss aurait répondu 5050. En fait, avec un petit raisonnement, on peut retrouver très facilement ce résultat, en formant des paires de nombres. En effet, on peut voir que 1+100=101, 2+99=101, 3+98=101, et ainsi de suite, si bien que avec les nombres de 1 à 100, on peut former 50 paires de cette forme. Cela donne finalement 50×101=5050.
Il est assez amusant de découvrir que cette histoire a progressivement évolué de biographies en biographies de Gauss, l'histoire originale ne mentionnant jamais ces nombres de 1 à 100. Dans son article Gauss's Day of Reckoning, Brian Hayes recence plus d'une centaine de versions différentes de cette même histoire !

On peut tout de même appliquer cette méthode de Gauss pour prouver que 1+2+3+...+63 = 2016. En effet, on a 1+63=64, 2+62=64, et ainsi de suite. Dans la somme 1+2+3+...+63, on peut retrouver 31 paires dont la somme vaut 64, ce qui donne 31×64=1984. Il reste à ajouter 32, le terme central de la somme (qui n'a pas été pris en compte lors des paires), ce qui donne finalement 1984+32=2016.

En généralisant le raisonnement, on peut prouver que 1+2+3+4+...+N = N/2×(1+N). Une démonstration assez classique "sans mot" de cette formule repose sur la figure suivante :

Preuve sans mots

Une autre façon de retrouver les nombres triangulaires est de passer par le triangle de Pascal, un triangle formé de nombres contruit de façon à ce que chaque terme soit la somme des deux au-dessus. Par construction, on retrouve sur la troisième diagonale la suite des nombres triangulaires.

Triangle de pascal
Le triangle de Pascal, construit de façon à ce que chaque nombre soit la somme des deux juste au-dessus (à titre d'exemple, 15+6=21, en rose)
La troisième diagonale, en bleue, correspond donc à des nombres de la forme 1+2+3+4+...+N : les nombres triangulaires.
On retrouvera donc 2016 dans la 64e ligne du triangle de Pascal.

Les nombres que l'on retrouve dans le triangle de Pascal peuvent être interpréteés d'une façon combinatoire : le nombre que l'on retrouve sur la n-ème ligne et k-ième colonne est le nombre de façons de choisir k objets parmi n possibles. Ainsi, 2016 est le nombre de façons de choisir 2 objets parmi 64.

On peut alors interpréter ce résultat en disant que 2016 est :

  • Le nombre de façons de placer deux cavaliers sur un échiquier (cela correspond à choisir 2 cases parmi les 64)

Echiquier

  • Le nombre d'arêtes d'un graphe complet à 64 sommets (chaque arête correspond au choix de 2 sommets parmi les 64), ce qui donne visuellement ceci :

G64

 

2016 est un nombre hexagonal [A000384]
Mais 2016, c'est aussi un nombre hexagonal, ce qui visuellement donne ceci :

Hexagone 2016
2016 fera vraiment mal aux yeux.

Chose intéressante : les nombres hexagonaux sont toujours des nombres triangulaires. On peut bien sûr le prouver algébriquement, mais j'espère que cette petite animation saura être plus parlante :

triangle

A noter que tous les nombres triangulaires ne sont pas pour autant hexagonaux.

On peut aussi dire que 2016 est un nombre icosikaitetragonal, puisqu'il peut être représenté sous la forme de polygone à 24 côtés [A051876] ...

2016 est un nombre presque parfait [A006516]
2016 peut s'écrire sous la forme 2016 = 25(26-1). Grâce à cette propriété, cela fait de 2016 le nombre de diagonales d'un hypercube de dimension 6. Mais ce qui est encore beaucoup plus intéressant avec cette écriture, c'est que cela correspond parfois à des nombres parfaits.

Un nombre parfait, c'est un nombre égal à la somme de ses diviseurs propres. Le nombre 28 en est un bon exemple : ses diviseurs (propres) sont 1, 2, 4, 7 et 14, et on a l'égalité 1+2+4+7+14=28.
On sait facilement construire des nombres parfaits (relaté par Euclide dès le IIIe siècle avant JC) : si le nombre 2p-1 est un nombre premier, alors le nombre 2p-1(2p-1) sera un nombre parfait. Pour obtenir 28, il suffit de voir que 23-1=7 est premier, et donc que 22 (23-1) = 28 est parfait. Réciproquement, on peut prouver que dès qu'un nombre pair est parfait, alors on pourra l'écrire sous la forme 2p-1(2p-1) avec 2p-1 premier.

Des nombres premiers de la forme 2p-1, on en connaît pas mal : 3, 7, 31, 127... Depuis 2013, on connaît 48 nombres premiers de cette forme, si bien que l'on connaît aujourd'hui 48 nombres parfaits. Ces nombres premiers de la forme 2p-1 sont ce que l'on appelle les nombres premiers de Mersenne : ils ont un intérêt tout particulier en maths, puisqu'ils fournissent les plus grands exemples de nombres dont on peut être sûr et certain qu'ils sont bien des nombres premiers. Le plus grand d'entre eux est 257 885 161-1, et compte tout de même 17 425 170 chiffres (voir là). [Mise à jour du 07/01 : on compte en fait 49 nombres parfaits, puisqu'un nouveau nombre de Mersenne premier vient d'être découvert, il s'agit de 274,207,281-1, qui compte 22 338 618 chiffres]

Les nombres parfaits gardent encore pas mal de mystères. A l'heure actuelle, on ne peut aucunement connaître le nombre de nombres parfaits qui existent.
D'un côté, il y a les nombres parfaits pairs, liés aux nombres premiers de Mersenne. Puisqu'on ne sait pas s'il existe ou non un nombre infini de nombres premiers de Mersenne, on ne peut rien dire non plus pour les nombres parfaits pairs.
De l'autre côté, il y a les nombres parfaits impairs. Là, c'est encore pire : on peut dire de nombreuses choses à leur sujet (un nombre parfait impair doit avoir plus de 1500 chiffres ou ne pas être divisible par 105, par exemple), mais le principal reste à démontrer, puisqu'on ne sait pas si des nombres parfaits impairs existent bel et bien.

Bon, par contre, 2016 peut s'écrire sous la forme 2016=25(26-1). Or, 26-1=63, ce qui n'est pas un nombre premier, donc 2016 n'est pas un nombre parfait...

2016 appartient à la "suite des cabines téléphoniques" [A192008]
En cherchant un peu, on trouve aussi des propriétés beaucoup moins utiles. Cette situation, par exemple : 

Imaginons la salle d'attente d'une administration quelconque où sont disponibles seulement 8 chaises, toutes les unes à côté des autres. Successivement, 8 personnes vont arriver dans cette pièce (et aucune ne partira avant que la pièce ne soit remplie). Lorsqu'une personne entre dans la pièce pour venir s'asseoir, elle veillera toujours à maximiser son confort personnel. Pour cela, elle ne s'installera jamais à côté d'une place déjà occupée, sauf si ces places sont les seules disponibles (dans ce cas, une place ne possédant qu'un seul voisin sera toujours préféré à une place à 2 voisins).

Salle d attente 0

Ainsi, le premier arrivant aura le choix entre 8 chaises. Imaginons qu'il prenne la troisième.

Salle d attente 1

Les chaises 2 et 4 sont maintenant indisponibles (trop proche d'une place occupée), la deuxième personne à entrer pourra choisir entre la chaise 1, 5, 6, 7 et 8. Disons qu'elle prend la 7eme.

Salle d attente 2

A présent, seules deux chaises sont encore disponibles (la 1 et la 5). Les deux prochains qui entreront choisiront donc ces deux chaises.

Salle d attente 3-4

Une cinquième personne arrive. Parmi les 4 chaises restantes, toutes ont deux voisins, sauf la dernière. C'est donc vers cette dernière que le nouvel arrivant se dirigera.

Salle d attente 5

Les trois derniers qui arriveront n'auront plus la possibilité d'obtenir des places tranquilles. Ils se partageront donc les trois dernières places restantes.

Salle d attente 6-7-8

Les chaises ont donc été choisies selon l'ordre 3, 7, 1, 5, 8, 2, 4, 6, ce qui ne représente en fait que l'une des 2016 façons de remplir toutes ces places !

 

Mais aussi...

  • Un carré magique de taille 8×8 composé uniquement de nombres premiers a au minimum 2016 comme constante magique. [A073520]

Carré magique

  • Il existe 2016 matrices 2×2 inversibles dans ℤ/7ℤ. [A000252]
  • On peut compter 2016 cellules 5D dans un hypercube de dimension 9. [A054849]
  • Le déterminant de la matrice suivante est -2016. [A092415]

matrice_det_2016

En fait, la principale raison pour laquelle 2016 possède autant de propriétés, c'est que 2016 possède énormément de diviseurs (il en possède 36 : 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 18, 21, 24, 28, 32, 36, 42, 48, 56, 63, 72, 84, 96, 112, 126, 144, 168, 224, 252, 288, 336, 504, 672, 1008, 2016). Des nombres avec autant de diviseurs, c'est plutôt rare, et cela explique sa surreprésentation dans l'OEIS. Puisque, en plus, c'est un nombre triangulaire, cela lui rajoute de nombreuses propriétés dérivées.

Bref : que cette année 2016 soit la plus intéressante pour vous.
Et surtout, la santé !

Posté par El Jj à 10:06 - Commentaires [7] - Permalien [#]
Tags : , , ,
25 octobre 2015

Pierre, feuille, ciseaux... Et après ?

Il y a de cela 8 ans, j'avais codé une version un peu trop modernisée du chifoumi, et ça ressemblait à ceci.

Ce chifoumi à 10 symboles présente un désavantage majeur : il n'est pas équitable, puisque certains symboles sont en moyenne plus forts que les autres. C'est le cas par exemple de la feuille qui gagne contre 5 des 9 autres symboles, alors que la pierre ne gagne que contre 4 des 9 autres symboles.

On peut le voir sur la matrice des gains du jeu : certaines lignes ont davantage de "1" que les autres.

Matrice gains
Matrice des gains : les "1" correspondent à la victoire du joueur, les "-1" à la victoire de l'adversaire et les "0" à une égalité.

Il n'y a qu'une seule façon de régler le problème, c'est d'ajouter un nouveau symbole qui égalise chacune des lignes et colonnes. On peut, par exemple, ajouter le lapin, qui gagnera contre la feuille, les ciseaux, le puits, le pistolet et le sataniste (les justifications sont laissées en exercice au lecteur).

Matrice gains 2
Nouvelle matrice de gain : le jeu est équilibré, puisque chaque ligne contient à présent autant de "1" que de "-1".

Mais au fait, peut-on fabriquer un jeu de Pierre-Feuille-Ciseaux avec autant de symboles que l'on veut ?

Pierre - Feuille - Ciseaux - (...) - (...)
La plus connue des variantes à 4 symboles du chifoumi est celle du "Pierre-Feuille-Ciseaux-Puits". L'ajout du symbole supplémentaire donne cependant un jeu bancal, puisque la pierre devient un symbole stratégiquement inutile (On peut même démontrer que la stratégie optimale au "Pierre-Feuille-Ciseaux-Puits" est de joueur au hasard les symboles, excepté la pierre. Un jour, promis, je ferai un article sur la théorie des jeux...).
Plutôt que de représenter les chifoumis par leur matrice de gains, utilisons plutôt la représentation sous forme de graphe. Dans un graphe de chifoumi ("graphe de tournoi équilibré"), le nombre de flèches pointant sur un sommet doit être égal au nombre de flèches qui en partent. Le graphe du "Pierre-Feuille-Ciseaux-Puits" n'est donc pas un graphe de chifoumi :

PFCP

La pierre casse les ciseaux ;
La feuille recouvre la pierre et le puits ;
Les ciseaux coupent la feuille ;
Dans le puits tombent la pierre et les ciseaux.

En fait, on peut voir facilement qu'un chifoumi ayant un nombre pair de symboles ne pourra jamais être équitable. En effet, si un nombre pair de symboles est en présence, chaque symbole pourra se battre contre un nombre impair de symboles ; impossible dans ce cas d'avoir autant de victoires que de défaites.

L'autre variante classique du chifoumi, popularisée par la série "The Big Bang Theory" est celle où l'on ajoute les deux symboles "Lézard" et "Spock". Cela produit une version à 5 symboles, qui cette fois-ci est équilibrée.

PFCLS
La pierre casse les ciseaux et écrase le lézard ;
Les ciseaux décapitent le lézard et coupent la feuille ;
Le lézard mange la feuille et empoisonne Spock ;
La feuille désapprouve Spock et recouvre la pierre ;
Spock vaporise la pierre et écrabouille les ciseaux.

Existe-t-il d'autres variantes de chifoumi à 5 symboles qui seraient radicalement différentes du Pierre-Feuille-Ciseaux-Lézard-Spock ? Eh bien... non ! On peut prendre par exemple la variante Singe-Pirate-Robot-Ninja-Zombie.

mprnz-game

Le robot écrase le zombie et électrocute le ninja ;
Le zombie attaque le singe et mange le pirate ;
Le singe trompe le ninja et débranche le robot ;
Le ninja attaque le pirate et décapite le zombie ;
Le pirate coule le robot et embroche le singe.

En procédant à un simple changement de nom, on peut voir que ces deux variantes sont en fait exactement les mêmes. On dit alors que les graphes sont isomorphes.

Isomorphisme

Isomorphisme entre les deux graphes : on commence par renommer les sommets, puis on les déplace en préservant le sens des flèches.

On peut même prouver que si on a un chifoumi équilibré à 5 symboles, il sera forcément isomorphe au pierre-feuille-ciseaux-lézard-Spock. Pour cela, prenons un chifoumi ayant 5 symboles A, B, C, D et E.
La première chose à voir, c'est que le graphe possèdera forcément un 5-cycle, de type A → B → C → D → E → A.
Dans le cas contraire, c'est que l'on a seulement  un 4-cycle A→B→C→D→A. Dans ce cas, on aura (A→C ou C→A) et (B→D ou D→B). Sans perte de généralité, supposons que l'on a A→C et B→D. Pour que le chifoumi soit équitable, il faut nécéssairement E→B et C→E, ce qui fait apparaître le 5-cycle A→C→E→B→D→A.
Bref, il y a un 5-cycle. On peut supposer sans perte de généralité que ce 5-cycle est A→B→C→D→E→A. On a alors deux possibilités : soit A→C, soit A→D. On peut alors compléter les graphes en veillant à le construire équilibré, ce qui donne les deux graphes suivants :

ABCDE

Ces deux éventualités donnent deux graphes qui semblent au premier abord différents, mais qui sont bien isomorphes, puisque le premier est isomorphe au Pierre-Feuille-Ciseaux-Lézard-Spock, et que le second l'est au Singe-Pirate-Robot-Ninja-Zombie.

Pierre - Feuille - Ciseaux - (...) - (...) - (...) - (...)
La construction précédente a le mérite de fournir une première méthode générale pour fabriquer un graphe de chifoumi avec n-symboles : il suffit de partir de n symboles disposés en cercle, et de compléter ensuite le graphe. La façon la plus simple de le compléter, c'est de relier chaque symbole aux (n-1)/2 suivants.

C'est ce qu'a fait David C. Lovelace en 2005, en fabriquant un Pierre-Feuille-Ciseaux à 7 symboles (un "7-chifoumi") ;

hands

La pierre éteint le feu, écrase les ciseaux et l'éponge ;
Le feu fait fondre les ciseaux, brûle l'éponge et le papier ;
Les ciseaux coupent l'éponge, le papier et son claquement résonne dans l'air ;
L'éponge mouille le papier, contient des trous d'air et absorbe l'eau ;
Le papier évente l'air, flotte sur l'eau et recouvre la pierre ;
L'air évapore l'eau, érode la pierre et éteint le feu ;
L'eau érode la pierre, éteint le feu et rouille les ciseaux.
Sur le cercle, chaque symbole est relié aux (7-1)/2 = 3 symboles suivants.

... puis à 9 symboles, puis à 11 symboles, puis à 15 symboles, puis à 25 symboles, et même jusqu'à... 101 symboles ! Toutes ces variantes sont créées de la même façon : les n symboles sont disposés en un cercle, ce qui forme un n-cycle, et chaque symbole bat les (n-1)/2 suivants sur ce cercle.

Autre méthode de construction. On peut fabriquer son chifoumi au fur et à mesure, en ajoutant de nouveaux symboles 2 par 2, de façon à ce que le premier symbole ajouté batte la moitié (arrondi à l'entier supérieur) des symboles préexistants, et que l'autre symbole batte la seconde moitié des symboles préexistants, ainsi que le premier symbole ajouté.

Par exemple, partons du classique Pierre, Feuille, Ciseaux. On commence par ajouter deux symboles, l'arbre et le sac plastique.

L'arbre
+ ne craint rien des ciseaux ;
+ domine la pierre ;
- n'est rien sans feuilles ;
(- est pollué par le sac plastique).
Le sac plastique
+ ramasse la feuille ;
- se fait découper par les ciseaux ;
- cède sous le poids de la pierre ;
+ pollue l'arbre.

On peut continuer, en ajoutant deux autres symboles. Disons, la hache et l'homme.

La hache :
+ déchire le sac plastique ;
+ casse les ciseaux ;
+ abat l'arbre ;
- se fait emballer par la feuille ;
- se brise sur la pierre ;
(- est manipulé par l'homme).
L'homme :
+ écrit sur la feuille ;
+ marche sur la pierre ;
- se fait étouffer par le sac plastique ;
-  se fait cisailler par les ciseaux ;
- tombe de l'arbre ;
+ manipule la hache.

PFC_7
Le graphe de mon 7-chifoumi.

Et ainsi de suite, pour fabriquer des chifoumis avec toujours plus de symboles !

On peut alors se poser la même question que précédemment. Le 7-chifoumi de Lovelace "Pierre-Feuille-Ciseaux-Air-Eau-Feu-Éponge" est-il équivalent à mon 7-chifoumi "Pierre-Feuille-Ciseaux-Homme-Hache-Arbre-Sac" ?
Cette fois-ci, non ! Et on peut même le prouver, mais il va falloir pour cela compter consciencieusement les différents 5-cycles qui apparaissent dans la structure.

Dans la première, on ne peut compter que 28 5-cycles :

PFG_2
4 des 28 5-cycles du graphe du 7-Chifoumi de Lovelace.
Les 24 autres 5-cycles se retrouvent par rotation (d'angle 360°/7).

Tandis que la deuxième, on peut en compter jusqu'à 36 :

 

PFG_1

12 des 36 5-cycles du graphe du 7-Chifoumi personnalisé.
Les 24 autres 5-cycles se retrouvent par rotation (d'angle 360°/3)

Les deux graphes n'ont pas le même nombre de 5-cycles, ils sont donc fondamentalement différents, ce qui montre qu'il existe donc au moins deux façons distinctes de construire un 7-chifoumi. Et il en existe même une troisième, celle ayant la structure du plan de Fano (évoquée déjà ici). Cette structure-ci ne peut cependant pas être obtenue par la méthode de construction itérative décrite précédemment.

Plan de Fano
Le plan de chifoumi-Fano (qui contient 42 5-cycles)

En existe-t-il davantage ? Cette fois-ci, non. Pour le prouver, il faudrait cependant montrer que chacun des 2640 graphes de 7-chifoumi est isomorphe à l'un des trois graphes précédents...

Pierre - Feuille - Ciseaux - (...) - (...) - (...) - (...) - (...) - (...) - ...
À mesure que n augmente, le nombre de graphes de chifoumi à n symboles augmente de façon drastique :

n = 1 → 1 configuration
n = 3 → 1 configuration
n = 5 → 1 configuration
n = 7 → 3 configurations
n = 9 → 15 configurations
n = 11 → 1223 configurations
n = 13 → 1495297 configurations

Pour déterminer ces valeurs, Marc Chamberland et Eugene Herman n'ont pas cherché à calculer l'ensemble des graphes de chifoumi, le temps de calcul aurait été suicidaire (à titre indicatif, il y a 9 307 700 611 292 160 graphes de chifoumi à 13 symboles, analyser chacun d'entre eux aurait demandé des temps de calculs monstrueux). Pour le prouver, ils ont plutôt tenté de déterminer les différents "profils" possibles existants pour les graphes (la façon dont les 3-cycles sont disposés les uns par rapport aux autres), ce qui leur a permis de dénombrer efficacement toutes ces configurations. On ne connaît pas aujourd'hui le nombre de chifoumi distincts à 15 symboles, mais ce qui est sûr, c'est qu'ils sont particulièrement nombreux.

Bref : si vous voulez fabriquer un chifoumi complètement inédit, il vous faudra au minimum 7 symboles !

alex_the_kidd_hamburger


Sources :
Rock-Paper-Scissors meets Borromean Rings, Marc Chamberland, Eugene A. Herman

Posté par El Jj à 10:00 - Commentaires [7] - Permalien [#]
Tags : ,
18 octobre 2015

Deux (deux ?) minutes pour Newroz

Une nouvelle fois, j'ai adapté en vidéo un ancien article. Il est aujourd'hui question de diagramme de Venn :

Vignette

 

Transcription :

En juillet 2012, Mamakani et Ruskey, deux mathématiciens canadiens, ont représenté Newroz, le premier diagramme de Venn symétrique simple à 11 pétales. Cette découverte vient poursuivre un idéal initié par John Venn en 1880 : comment représenter élégamment les situations de la théorie des ensembles à l’aide de patates. Ça tombe bien, j’ai deux minutes pour en parler !


L’histoire débute dans la deuxième moitié du 18e siècle, lorsque le génial Leonard Euler a tenté d’étudier systématiquement les syllogismes. Un syllogisme, c’est un raisonnement logique en trois temps, du style :
- Tous les Pokémon électrique peuvent apprendre l’attaque Tonnerre
- Or, certains Pokémon électriques sont aussi de type vol
- Donc, certains Pokémon de type vol peuvent apprendre l’attaque Tonnerre

Pour étudier ces syllogismes, Euler a eu l’idée brillante d’utiliser des cercles. Et quand bien même l’idée ne serait pas réellement de Euler, elle n’en reste pas moins brillante. Chaque cercle correspond à l’un des ensembles de l’énoncé. Dans l’exemple précédent, on a le cercle des Pokémon électriques, le cercle des Pokémon apprenant l’attaque Tonnerre, et le cercle des Pokémon de type vol. Si un élément est à l’intérieur d’un cercle, c’est qu’il appartient à l’ensemble, et réciproquement. La première hypothèse, qui énonce que tout Pokémon électrique apprend l’attaque Tonnerre, se traduit par deux cercles imbriqués. La deuxième hypothèse, qui nous dit qu’il existe des Pokémon à la fois de type électrique et vol, se traduit par deux cercles qui se coupent. On constate alors que le cercle des Pokémon de type vol et celui des Pokémon qui apprenant Tonnerre se coupent, ce qui explique la conclusion : certains Pokémon de type vol apprennent l’attaque Tonnerre.

Bref : les diagrammes d’Euler permettent de représenter des syllogismes avec trois cercles qui se coupent, ou pas.

Cent ans plus tard, le logicien John Venn met un coup de pied dans la fourmilière, et réinvente complètement l’idée d’Euler :
- la première révolution, c’est que les ensembles ne seront plus forcément représentés par des cercles, mais pourront prendre n’importe quelle forme patatoïde ;
- la deuxième révolution, c’est qu’on pourra se permettre d’utiliser plus que 3 ensembles ;
- mais surtout, la dernière révolution, c’est que tous les cas imaginables doivent être envisagés.

Avec les diagrammes de Venn, l’exemple précédent se traduira donc par trois ensembles qui s’entrecroisent en formant 8 zones distinctes, correspondant à l’intersection de 0, 1, 2 et 3 ensembles.

Pour illustrer le syllogisme par un diagramme de Venn, on va devoir griser les zones impossibles. Ainsi, puisque tout les Pokémon électriques peuvent apprendre l'attaque Tonnerre, on peut griser les deux zones correspondant aux ensembles uniquement électriques. La deuxième hypothèse nous donne l’existence d’un élément appartenant à la fois à l’ensemble vol et à l’ensemble électrique. La conclusion, c’est bien que cet élément appartient à l’ensemble Tonnerre.

Bref : les diagrammes de Venn permettent de représenter les syllogismes avec trois patates ou plus, mais qui se coupent tous les uns les autres en formant toutes les intersections possibles.
Soyons honnêtes, les diagrammes de Venn c’est sympa pour illustrer les syllogismes, mais c’est surtout très pratique pour illustrer des histoires d’intersections d’ensembles. Et du coup, il faut aller plus loin que 3 ensembles. On en veut 4, 5, 6 et plus ! Mais déjà, à partir de 4 ensembles, les problèmes commencent à arriver.

La première idée, c’est de placer ses 4 patates de façon symétrique, ce qui ressemble à ça.

Venn 4

Le soucis, c’est que si on compte les zones délimitées, on ne pourra en dénombrer que 14, alors que 4 ensembles donnent au maximum 16 regroupements possibles. Pour qu’un diagramme de Venn puisse être qualifié comme tel, il faut que toutes les combinaisons d’ensembles soient représentées, et il manque ici les zones correspondant à l’intersection de seulement A et B, et celle à l’intersection de seulement C et D…
Bon, en déplaçant un peu les ellipses, John Venn est parvenu à obtenir un diagramme parfait, ou chacune des 16 zones est représentée.
Pour ce qui est d’un diagramme à 5 ensembles et donc, 32 zones, Venn a proposé l’ajout d’un anneau central. Il l’a lui même reconnu, le résultat est loin d’être satisfaisant…

Venn 4 +Venn 5
Solutions de diagrammes à 4 et 5 ensembles proposés par Venn

Notons tout de même une chose : un diagramme de Venn à n ensembles présente toujours 2ⁿ zones. On peut voir ça sur l’exemple du diagramme de Venn à 5 ensembles, qui contient 1 zone extérieure, 5 zones n’appartenant qu’à 1 ensemble, 10 zones appartenant à 2 ensembles, 10 appartenant à 3 ensembles, 5 appartenant à 4 et une dernière appartenant à tous les ensembles. On a bien 2⁵, c’est à dire, 32 zones.

Il existe pourtant des méthodes pour construire des diagrammes de Venn avec autant d’ensembles que l’on veut.
La première méthode est un peu braque : on part d’un diagramme à 3 ensembles, et on y trace un chemin qui entre et sort une fois de chacune des zones alors délimitée. En procédant ainsi, on délimite un nouvel ensemble, ce qui donne bien un diagramme de Venn à 4 ensemble.
On peut alors tracer un chemin qui passe par chacune des 16 zones, et on obtient un diagramme de Venn à 5 ensembles. Ce n’est d’ailleurs que depuis avril 2015 que l’on a démontré que la méthode fonctionne toujours, mais elle fournit vraiment ce qu’il y a de pire en terme de diagramme de Venn.

On doit sinon à Anthony Edward une autre méthode particulièrement esthétique pour construire des diagrammes de Venn, en partant de deux droites perpendiculaires et d’un cercle, ce qui forme alors un diagramme de Venn à trois ensembles. Ensuite, on fabrique chaque nouvel ensemble en faisant serpenter une courbe de part et d’autre du cercle central. Cette méthode fabriquera des diagrammes de Venn avec autant d’ensembles que l’on veut.

Venn_Edward

Solution de diagramme de Venn à n ensembles proposé par Edward

Il manque un petit quelque chose à toutes ces constructions, et ce petit quelque chose, c’est que tous les ensembles ne sont pas équivalents. Ce qu’il faudrait, c’est qu’ils soient tous identiques, mais surtout, qu’ils présentent davantage de symétrie, en se regroupant en formant une fleur. On peut fabriquer des fleurs de Venn avec 2 pétales, avec 3 ou même avec 5 : pourquoi ça ne marcherait pas avec davantage ?
On dit alors que ces diagrammes sont symétriques : chaque pétale se déduit des autres à partir d’une même rotation.
Il existe d’ailleurs des diagrammes symétriques à 7 pétales, comme par exemple celui obtenu à partir de cet ensemble là, répété 7 fois par rotation.
Ce sont ces diagrammes-là, les symétriques, qui sont à mon humble avis les plus beaux !

Et des diagrammes de Venn symétriques à 4 ou 6 pétales, alors ? On en a trouvé ? Eh bien… non ! Mais pour une raison assez simple : les diagrammes de Venn symétriques ne peuvent exister que lorsque leur nombre de pétales est un nombre premier.
Pour comprendre ça, essayons de construire un diagramme de Venn symétrique avec 4 ensembles. Un tel diagramme de Venn présente forcément 2⁴ zones. On peut même détailler : il possède 1 zone n’appartenant à aucun ensemble, 4 zones correspondant à un ensemble seul, 6 zones correspondant à l’intersection de deux ensembles, 4 zones correspondant à l'intersection de trois , et enfin, une dernière zone correspondant à l’intersection des 4 ensembles.
Le problème, c’est que dès que l’on fait un diagramme symétrique avec 4 ensembles, chaque zone apparaît soit une fois, soit 4 fois. Les zones qui apparaissent une seule fois sont la zone extérieure et la zone intérieure, tandis que toutes les autres zones apparaîtront, à cause de la symétrie, toujours par paquet de 4.
Pour les zones correspondant à l’intersection de 1 ou 3 ensembles, il n’y a pas de problème, puisqu’elles sont chacune au nombre de 4. Le soucis viendra forcément des 6 zones correspondant à l’intersection de 2 ensembles : soit il manquera deux zones, soit il y en aura 2 de trop. Le problème vient donc du fait que 6 n’est pas divisible par 4.

Ces nombres 1, 4, 6, 4 et 1 sont ce qu’on appelle des coefficients binomiaux, c’est à dire, les nombres qui apparaissent dans le triangle de Pascal, un triangle composé de nombres où chacun est égal à la somme des deux nombres juste au-dessus. En l’occurrence, 1, 4, 6, 4 et 1 apparaissent sur la 4e ligne du triangle, ce qui donne la décomposition en zones du diagramme de Venn correspondant.
Une des propriétés du triangle de Pascal, c’est que sa n-ième ligne ne contient que des multiples de n dans le seul cas où n est un nombre premier. Ainsi, puisque 5 est un nombre premier, la 5eme ligne ne contient que des multiples de 5, de même que la 7e ligne ne contient que des multiples de 7. Cette condition est nécessaire à l’existence de diagramme de Venn symétrique, ce qui explique l’existence de ces diagrammes avec 5 ou 7 ensembles.
Par contre, la 4e, la 6e ou la 8e ligne contient des nombres non multiples de 4, 6 ou 8 : il est donc parfaitement inutile d’espérer pouvoir construire de beaux diagrammes de Venn avec 4, 6 ou 8 ensembles.

Bref : si un diagramme de Venn est symétrique, il contiendra forcément un nombre premier de pétales.
Rien ne dit cependant comment on peut les construire. Ce n’est d’ailleurs qu’en 1992 que le premier diagramme symétrique à 7 pétales a été découvert, par Branko Grünbaum, qui a d’ailleurs longtemps pensé qu’ils n’existaient pas. Aujourd’hui, cependant, on en connaît beaucoup plus.

Pour 11 ensembles, ça se complique encore. Le premier exemple de diagramme de Venn symétrique à 11 pétales a été découvert en 2002 par Peter Hamburger, et il ressemble à ça !

GKSentire
Diagramme de Venn symétrique à 11 ensembles

Ce diagramme a un soucis majeur : il n’est pas simple. On dit qu’un diagramme est simple quand il n’existe aucun point où plus de deux courbes se croisent en même temps. Dans le diagramme de Hamburger, on trouve des points où les 11 courbes se croisent en même temps !

Existe-t-il un diagramme symétrique simple à 11 ensembles ? Eh bien, oui, mais il a fallu attendre juillet 2012 pour le voir arriver, grâce à Kaleygh Mamakani et Frank Ruskey.

VD_11_Filled
Diagramme de Venn symétrique simple à 11 ensembles

Le résultat est superbe, mais il ouvre évidemment une nouvelle question : existe-t-il un diagramme de Venn symétrique et simple avec 13 ensembles ? Plusieurs mathématiciens sont à sa recherche, mais la question demeure aujourd’hui toujours ouverte !...


Sources :
A note on the historical development of logic diagrams : Leibniz, Euler and Venn, Margaret E. Baron
Les diagrammes de Venn, Ernest Coumet
A New Rose : The First Simple Symmetric 11-Venn Diagram, Khalegh Mamakani, Frank Ruskey,
A Survey of Venn Diagrams, Frank Ruskey, Mark Weston