Accueil
Dernières images
Rechercher
S'enregistrer
ConnexionLa conjecture de Syracuse
Page 1 sur 1
La conjecture de Syracuse
gérard menvussa Mar 28 Juin - 15:48
sur un blog passsionnant : "science étonnante".... Gros poutou a son auteur (hé hé !)
La conjecture de Syracuse est un merveilleux problème d’arithmétique : un enfant de 8 ans peut le comprendre, les ordinateurs l’ont vérifiée jusqu’à des nombres astronomiques, et pourtant les mathématiciens n’ont toujours pas réussi à la démontrer ou à l’infirmer.
Il y a quelques jours, une prépublication a annoncé sa démonstration…avant de se rétracter après la découverte d’une faille dans un point du raisonnement.
Syracuse, un bastion proche de tomber ? Voyons cela de plus près !
L’énoncé de la conjecture
Prenez un nombre entier positif, et appliquez lui le traitement suivant :
s’il est pair, vous le divisez par 2;
s’il est impair, vous le multipliez par 3 et vous ajoutez 1.
Vous obtenez alors un nouveau nombre, sur lequel vous répétez la procédure. Et ainsi de suite, pour fabriquer une séquence de nombres.
Mettons que je parte du nombre 7, voici la séquence que j’obtiens :
7,22,11,34,17,52,26,13,40,20,10,5,15,16,8,4,2,1,4,2,1,4,2,1,…
Vous remarquez qu’à la fin, une fois qu’on est tombé sur 1, la suite finit par répéter indéfiniment le cycle 4,2,1. Si vous essayez vous-même avec d’autres nombres, vous allez voir que l’on finit toujours à 1. Vous voulez faire le test ? Si vous partez de nombres pas trop élevés, ça se fait presque de tête. Si vous êtes fainéant, vous pouvez aller sur ce site.
La conjecture de Syracuse s’énonce ainsi : quel que soit le nombre que l’on choisisse au départ, on finira par tomber sur 1.
Contrairement à ce que peut laisser supposer le parfum archimédien de son nom, cette conjecture est relativement récente puisqu’elle a été popularisée par le mathématicien allemand Lothar Collatz (ci-dessous) aux environ de 1937. C’est à la suite d’un exposé à l’Université de Syracuse à New York qu’elle a acquis son surnom le plus connu.
Peut-on finir ailleurs qu’à 1 ?
Si la conjecture de Syracuse est vraie, quel que soit le nombre initial on doit tomber sur le cycle 4,2,1, appelé cycle trivial. Pour qu’elle soit fausse, il suffit de trouver un contre-exemple. On peut facilement se convaincre que s’il existe un contre-exemple, il correspond nécessairement à l’une de ces deux situations :
une séquence qui diverge à l’infini;
une séquence se termine sur un cycle autre que le cycle trivial.
Si vous êtes courageux, vous pouvez essayer de prendre des nombres au hasard, et construire la suite de Syracuse pour voir si vous tombez sur une de ces deux situations. Petit indice : la conjecture a déjà été vérifiée numériquement jusqu’à 10^20 (par Tomas Oliveira e Silva), alors essayez de choisir un nombre de départ plus grand que ça !
Si l’idée de chercher un contre-exemple vous fatigue, vous pouvez chercher une démonstration. Il suffit de prouver 1) qu’on ne diverge jamais à l’infini, et 2)qu’il n’existe aucun autre cycle que le cycle trivial. Voyons ces éventualités.
Un argument probabiliste
Pour se convaincre qu’une divergence à l’infini est peu probable, on peut avoir recours à un argument probabiliste. Pour cela, il suffit d’observer que quand on a un nombre impair, et qu’on le multiplie par 3 en ajoutant 1, on tombe nécessairement sur un nombre pair. On peut donc directement le diviser par 2. Ceci donne naissance à la forme comprimée de la procédure :
si N pair ==> N/2
si N impair ==> (3*N+1)/2
Quel est l’intérêt de cette forme comprimée ? Que le nombre N soit pair ou impair, le nombre sur lequel on tombe sera à 50% de probabilité pair, et à 50% de probabilité impair. Après K opérations, le nombre initial a en moyenne été multiplié K/2 fois par (1/2) et K/2 fois par en gros (3/2). Donc après K opérations, le nombre initial a en moyenne été multiplié par
\left(\frac{3}{4}\right)^{K/2}
Puisque 3/4<1, on voit quand itérant les opérations à l’infini, on doit en moyenne toujours décroitre. Bien sûr cet argument probabiliste n’est pas une démonstration, puisqu’il suppose qu’on tombe bien à chaque fois à 50% de chance sur un nombre pair ou sur un nombre impair. C’est vrai en moyenne, mais pas pour chaque suite prise individuellement. Donc ce raisonnement montre qu’un contre-exemple allant à l’infini est assez improbable, mais il peut très bien exister !
A la recherche du cycle non-trivial ?
Autre étape nécessaire pour démontrer la conjecture de Syracuse : prouver qu’il n’existe pas d’autre cycle que le cycle trivial 4,2,1. Là aussi vous pouvez vous amuser à en chercher un à la main, mais soyez ambitieux. En effet puisque la conjecture est vérifiée numériquement jusqu’à 10^20, un tel cycle ne peut contenir que des nombres supérieurs à cette valeur. Cette limite implique même que s’il existe un tel cycle, il est constitué de plus de 17 milliards d’éléments. Bon courage !
Bien sûr il y a aussi le cycle qui ne contient que 0. Mais comme les matheux sont curieux, ils sont allés faire un tour du côté des nombres négatifs. Si vous vous autorisez les nombres négatifs comme point de départ, il existe en effet quelques cycles. En fait il y en a 3, qui partent respectivement de -2, -5 et -17. On suppose qu’il n’en existe pas d’autres, mais on ne sait pas non plus le démontrer !
Alors va-t-on y arriver un jour ?
Comme je vous le disais au début de ce billet, un mathématicien de l’Université de Hambourg, Gerhard Opfer, a récemment posté une prépublication(*) annonçant la démonstration de la conjecture de Syracuse. Le gars a l’air sérieux, il est d’ailleurs un ancien étudiant de L. Collatz lui-même (cf le Math Genealogy Project).
En survolant le papier, on remarque deux choses surprenantes. D’une part la démonstration est assez courte, quelques pages, c’est plutôt inattendu. D’autre part elle semble ne faire appel qu’à des notions de mathématiques plutôt simples (algèbre linéaire, fonctions complexes), sans avoir besoin d’invoquer la tour de Teichmüller ou les formes modulaires semi-stables sur le groupe de Galois absolu d’une clôture séparable. On a presque envie de penser que si on lisait le papier, on pourrait comprendre.
Malheureusement, Mesdames et Messieurs, comme souvent dans ce genre d’annonces, il y semble qu’il y ait une faille dans sa démonstration. Opfer vient d’ajouter la page suivante à son papier :
Les curieux peuvent aller lire le papier, puis aller là pour une discussion de la faille. On peut tout de même rêver que la faille soit curable, ou tout au moins que la tentative de G. Opfer soit à l’origine de nouveaux essais, dont un finira bien par fonctionner ! Sauf si, comme le pense le célèbre mathématicien Paul Erdös à propos de la conjecture de Syracuse
« Les mathématiques ne sont pas encore prêtes pour de tels problèmes ».
(*) G. Opfer, An analytic approach to the Collatz 3n + 1 Problem Merci à Hervé qui m’a mis au courant de cette annonce !
La conjecture de Syracuse est un merveilleux problème d’arithmétique : un enfant de 8 ans peut le comprendre, les ordinateurs l’ont vérifiée jusqu’à des nombres astronomiques, et pourtant les mathématiciens n’ont toujours pas réussi à la démontrer ou à l’infirmer.
Il y a quelques jours, une prépublication a annoncé sa démonstration…avant de se rétracter après la découverte d’une faille dans un point du raisonnement.
Syracuse, un bastion proche de tomber ? Voyons cela de plus près !
L’énoncé de la conjecture
Prenez un nombre entier positif, et appliquez lui le traitement suivant :
s’il est pair, vous le divisez par 2;
s’il est impair, vous le multipliez par 3 et vous ajoutez 1.
Vous obtenez alors un nouveau nombre, sur lequel vous répétez la procédure. Et ainsi de suite, pour fabriquer une séquence de nombres.
Mettons que je parte du nombre 7, voici la séquence que j’obtiens :
7,22,11,34,17,52,26,13,40,20,10,5,15,16,8,4,2,1,4,2,1,4,2,1,…
Vous remarquez qu’à la fin, une fois qu’on est tombé sur 1, la suite finit par répéter indéfiniment le cycle 4,2,1. Si vous essayez vous-même avec d’autres nombres, vous allez voir que l’on finit toujours à 1. Vous voulez faire le test ? Si vous partez de nombres pas trop élevés, ça se fait presque de tête. Si vous êtes fainéant, vous pouvez aller sur ce site.
La conjecture de Syracuse s’énonce ainsi : quel que soit le nombre que l’on choisisse au départ, on finira par tomber sur 1.
Contrairement à ce que peut laisser supposer le parfum archimédien de son nom, cette conjecture est relativement récente puisqu’elle a été popularisée par le mathématicien allemand Lothar Collatz (ci-dessous) aux environ de 1937. C’est à la suite d’un exposé à l’Université de Syracuse à New York qu’elle a acquis son surnom le plus connu.
Peut-on finir ailleurs qu’à 1 ?
Si la conjecture de Syracuse est vraie, quel que soit le nombre initial on doit tomber sur le cycle 4,2,1, appelé cycle trivial. Pour qu’elle soit fausse, il suffit de trouver un contre-exemple. On peut facilement se convaincre que s’il existe un contre-exemple, il correspond nécessairement à l’une de ces deux situations :
une séquence qui diverge à l’infini;
une séquence se termine sur un cycle autre que le cycle trivial.
Si vous êtes courageux, vous pouvez essayer de prendre des nombres au hasard, et construire la suite de Syracuse pour voir si vous tombez sur une de ces deux situations. Petit indice : la conjecture a déjà été vérifiée numériquement jusqu’à 10^20 (par Tomas Oliveira e Silva), alors essayez de choisir un nombre de départ plus grand que ça !
Si l’idée de chercher un contre-exemple vous fatigue, vous pouvez chercher une démonstration. Il suffit de prouver 1) qu’on ne diverge jamais à l’infini, et 2)qu’il n’existe aucun autre cycle que le cycle trivial. Voyons ces éventualités.
Un argument probabiliste
Pour se convaincre qu’une divergence à l’infini est peu probable, on peut avoir recours à un argument probabiliste. Pour cela, il suffit d’observer que quand on a un nombre impair, et qu’on le multiplie par 3 en ajoutant 1, on tombe nécessairement sur un nombre pair. On peut donc directement le diviser par 2. Ceci donne naissance à la forme comprimée de la procédure :
si N pair ==> N/2
si N impair ==> (3*N+1)/2
Quel est l’intérêt de cette forme comprimée ? Que le nombre N soit pair ou impair, le nombre sur lequel on tombe sera à 50% de probabilité pair, et à 50% de probabilité impair. Après K opérations, le nombre initial a en moyenne été multiplié K/2 fois par (1/2) et K/2 fois par en gros (3/2). Donc après K opérations, le nombre initial a en moyenne été multiplié par
\left(\frac{3}{4}\right)^{K/2}
Puisque 3/4<1, on voit quand itérant les opérations à l’infini, on doit en moyenne toujours décroitre. Bien sûr cet argument probabiliste n’est pas une démonstration, puisqu’il suppose qu’on tombe bien à chaque fois à 50% de chance sur un nombre pair ou sur un nombre impair. C’est vrai en moyenne, mais pas pour chaque suite prise individuellement. Donc ce raisonnement montre qu’un contre-exemple allant à l’infini est assez improbable, mais il peut très bien exister !
A la recherche du cycle non-trivial ?
Autre étape nécessaire pour démontrer la conjecture de Syracuse : prouver qu’il n’existe pas d’autre cycle que le cycle trivial 4,2,1. Là aussi vous pouvez vous amuser à en chercher un à la main, mais soyez ambitieux. En effet puisque la conjecture est vérifiée numériquement jusqu’à 10^20, un tel cycle ne peut contenir que des nombres supérieurs à cette valeur. Cette limite implique même que s’il existe un tel cycle, il est constitué de plus de 17 milliards d’éléments. Bon courage !
Bien sûr il y a aussi le cycle qui ne contient que 0. Mais comme les matheux sont curieux, ils sont allés faire un tour du côté des nombres négatifs. Si vous vous autorisez les nombres négatifs comme point de départ, il existe en effet quelques cycles. En fait il y en a 3, qui partent respectivement de -2, -5 et -17. On suppose qu’il n’en existe pas d’autres, mais on ne sait pas non plus le démontrer !
Alors va-t-on y arriver un jour ?
Comme je vous le disais au début de ce billet, un mathématicien de l’Université de Hambourg, Gerhard Opfer, a récemment posté une prépublication(*) annonçant la démonstration de la conjecture de Syracuse. Le gars a l’air sérieux, il est d’ailleurs un ancien étudiant de L. Collatz lui-même (cf le Math Genealogy Project).
En survolant le papier, on remarque deux choses surprenantes. D’une part la démonstration est assez courte, quelques pages, c’est plutôt inattendu. D’autre part elle semble ne faire appel qu’à des notions de mathématiques plutôt simples (algèbre linéaire, fonctions complexes), sans avoir besoin d’invoquer la tour de Teichmüller ou les formes modulaires semi-stables sur le groupe de Galois absolu d’une clôture séparable. On a presque envie de penser que si on lisait le papier, on pourrait comprendre.
Malheureusement, Mesdames et Messieurs, comme souvent dans ce genre d’annonces, il y semble qu’il y ait une faille dans sa démonstration. Opfer vient d’ajouter la page suivante à son papier :
Les curieux peuvent aller lire le papier, puis aller là pour une discussion de la faille. On peut tout de même rêver que la faille soit curable, ou tout au moins que la tentative de G. Opfer soit à l’origine de nouveaux essais, dont un finira bien par fonctionner ! Sauf si, comme le pense le célèbre mathématicien Paul Erdös à propos de la conjecture de Syracuse
« Les mathématiques ne sont pas encore prêtes pour de tels problèmes ».
(*) G. Opfer, An analytic approach to the Collatz 3n + 1 Problem Merci à Hervé qui m’a mis au courant de cette annonce !
gérard menvussa- Messages : 6658
Date d'inscription : 06/09/2010
Age : 67
Localisation : La terre
Re: La conjecture de Syracuse
Invité Mar 28 Juin - 18:52
Si tu as envie de te faire du pognon, il existe 7 problèmes insolubles à 1 million de dollar l'unité. On s'y colle ?
Problèmes du prix du millénaire
Problèmes du prix du millénaire
Les problèmes du prix du millénaire sont sept problèmes mathématiques réputés insoluble. Un million de dollars US est à la clé de la résolution de chacun de ces problèmes.
C'est en démontrant une hypothèse ou une conjecture ou en donnant l'ensemble des solutions d'équations bien précises qu'on se voit attribué ce prix.
Le ou les auteurs proposeront leur solution à la communauté des mathématiciens et si, au bout de deux ans, elle reste valable et acceptée, alors le Clay Mathematical Institute remettra un million de dollars US à la ou les personnes qui l'auront proposée.
Les solutions auront des applications tout d'abord en mathématiques fondamentales, puis, pourront s'étendre dans d'autres domaines tels que, par exemple, l'informatique.
Media
Ces problèmes sont maintenant très connus du grand public, surtout grâce à la rémunération qu'apporte la résolution d'un de ces problèmes. Des références sont faites dans des séries télévisées ou sur internet. Mais pour certains mathématiciens enseignant dans les grandes universités cette prime n'apporte pas grand-chose au vu de leur salaire mensuel. D'ailleurs, Giorgi Perelman, qui a démontré la conjecture de Poincaré, a refusé cet argent.
Les problèmes
* Hypothèse de Riemann
* Conjecture de Poincaré
* Problème ouvert P=NP
* Conjecture de Hodge
* Conjecture de Birch et Swinnerton-Dyer
* Équations de Navier-Stokes
* Équations de Yang-Mills
Invité- Invité
Re: La conjecture de Syracuse
gérard menvussa Mar 28 Juin - 21:38
Moi qui croyait que tu avais résolu le problème de la complexité des algorithmes (polynomial, or not polynomial) je suis cruellement déçu !
gérard menvussa- Messages : 6658
Date d'inscription : 06/09/2010
Age : 67
Localisation : La terre
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum