Conjecture de Syracuse

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, on appelle suite de Syracuse une suite d'entiers naturels définie de la manière suivante :

On part d'un nombre entier plus grand que zéro ; s’il est pair, on le divise par 2 ; s’il est impair, on le multiplie par 3 et on ajoute 1. En répétant l’opération, on obtient une suite d'entiers positifs dont chacun ne dépend que de son prédécesseur.

Par exemple, à partir de 14, on construit la suite des nombres : 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2… C'est ce qu'on appelle la suite de Syracuse du nombre 14.

Après que le nombre 1 a été atteint, la suite des valeurs (1,4,2,1,4,2…) se répète indéfiniment en un cycle de longueur 3, appelé cycle trivial.

Si l'on était parti d'un autre entier, en lui appliquant les mêmes règles, on aurait obtenu une suite de nombres différente. A priori, il serait possible que la suite de Syracuse de certaines valeurs de départ n'atteigne jamais la valeur 1, soit qu'elle aboutisse à un cycle différent du cycle trivial, soit qu'elle diverge vers l'infini. Or, on n'a jamais trouvé d'exemple de suite obtenue suivant les règles données qui n'aboutisse pas à 1 et, par suite, au cycle trivial.

La conjecture de Syracuse, encore appelée conjecture de Collatz, conjecture d'Ulam, conjecture tchèque ou problème 3x+1 est l'hypothèse mathématique selon laquelle la suite de Syracuse de n'importe quel entier strictement positif atteint 1.

En dépit de la simplicité de son énoncé, cette conjecture défie depuis de nombreuses années les mathématiciens. Paul Erdős a dit à propos de la conjecture de Syracuse : « les mathématiques ne sont pas encore prêtes pour de tels problèmes »[1].

Origines[modifier | modifier le code]

Dès 1928, Lothar Collatz s'intéressait aux itérations dans les nombres entiers, qu'il représentait au moyen de graphes et d'hypergraphes. Il inventa alors le problème 3x+1, et le présentait souvent ensuite dans ses séminaires. En 1952, lors d'une visite à Hambourg, Collatz expliqua son problème à Helmut Hasse. Ce dernier le diffusa en Amérique à l'université de Syracuse : la suite de Collatz prit alors le nom de « suite de Syracuse ». Entre temps, le mathématicien polonais Stanislas Ulam le répand dans le Laboratoire national de Los Alamos. Dans les années 1960, le problème est repris par le mathématicien Shizuo Kakutani qui le diffuse dans les universités Yale et Chicago.

Cette conjecture mobilisa tant les mathématiciens durant les années 1960, en pleine guerre froide, qu'une plaisanterie courut selon laquelle ce problème faisait partie d'un complot soviétique visant à ralentir la recherche américaine.

Première approche et vocabulaire[modifier | modifier le code]

La suite de Syracuse d'un nombre entier N est définie par récurrence, de la manière suivante :

 u_0 = N
et pour tout entier  n \geq 0 : u_{n+1} =  \begin{cases}
  \dfrac{u_n}{2}& \mbox{si } u_n \mbox{ est pair}\\
   3u_n + 1 & \mbox{si } u_n \mbox{ est impair}
 \end{cases}

La conjecture affirme que, pour tout  N>0 , il existe un indice n tel que u_n = 1.

L'observation graphique de la suite pour N = 15 et pour N = 127 montre que la suite peut s'élever assez haut avant de retomber. Les graphiques font penser à la chute chaotique d'un grêlon ou bien à la trajectoire d'une feuille emportée par le vent. De cette observation est né tout un vocabulaire imagé : on parlera du vol de la suite.

On définit alors :

  • le temps de vol : c'est le plus petit indice n tel que un = 1.Il est de 17 pour la suite de Syracuse 15 et de 46 pour la suite de Syracuse 127.
  • le temps de vol en altitude : c'est le plus petit indice n tel que un+1u0.Il est de 10 pour la suite de Syracuse 15 et de 23 pour la suite de Syracuse 127.
  • l'altitude maximale : c'est la valeur maximale de la suite.Elle est de 160 pour la suite de Syracuse 15 et de 4372 pour la suite de Syracuse 127.
u_0 u_1 u_2 u_3 u_4 u_5 u_6 u_7 u_8 u_9 u_{10} u_{11} u_{12} u_{13} u_{14} u_{15} u_{16} u_{17} u_{18} u_{19} u_{20}
15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 4 2 1

Autres formulations[modifier | modifier le code]

On peut donner de nombreuses formulations équivalentes au problème de Syracuse. La conjecture de Syracuse est équivalente aux propositions suivantes :

  1. la durée de tout vol est finie ;
  2. la durée de tout vol en altitude est finie ;
  3. tout vol a un nombre fini d'étapes paires ;
  4. tout vol a un nombre fini d'étapes impaires ;
  5. tout vol a un nombre fini d'étapes paires en altitude ;
  6. tout vol a un nombre fini d'étapes impaires en altitude.

La suite compressée[modifier | modifier le code]

Suite de Syracuse compressée, pour N = 15.
Suite de Syracuse compressée, pour N = 127.

Par exemple, on remarque que si  u_n est impair dans la formule ci-dessus,  u_{n+1} est nécessairement pair et donc, le pas suivant de la suite doit être une division par deux ; on peut définir une nouvelle version compressée de la suite de Syracuse en combinant ces deux pas de la façon suivante  :

 v_{n+1} =  \begin{cases}
   \frac{v_n}{2}& \mbox{si } v_n \mbox{ est pair}\\
   \frac{3v_n\,+\,1}{2} & \mbox{si } v_n \mbox{ est impair.}
  \end{cases}

La nouvelle suite est une suite extraite de la version de base, et la conjecture dit que cette suite aboutit toujours au cycle (1,2,1…).

v_0 v_1 v_2 v_3 v_4 v_5 v_6 v_7 v_8 v_9 v_{10} v_{11} v_{12} v_{13} v_{14}
15 23 35 53 80 40 20 10 5 8 4 2 1 2 1

Énoncés concernant la durée de vol[modifier | modifier le code]

La conjecture admet des énoncés équivalents, par exemple :

  • pour tout N, la suite a une durée de vol finie ;
  • pour tout N, la suite a une durée de vol en altitude finie.

Approche inverse[modifier | modifier le code]

On peut aussi partir d'un algorithme inverse :

 R(n) = \begin{cases}\{2n\}& \mbox{si } n\equiv 0,1,2,3\mbox{ ou } 5 \\ \{2n,(n-1)/3\} & \mbox{si } n\equiv 4 \end{cases} \pmod{6}.

Au lieu de prouver que la suite directe, partant de n'importe quel entier naturel non nul, mène toujours à 1, on essaye de démontrer que l'algorithme inverse, partant de 1, est capable de générer tous les nombres entiers naturels non nuls.

Il existe aussi une version compressée de l'algorithme inverse :

 R(n) = \begin{cases}\{2n\}& \text{si } n\equiv 0 \mbox{ ou } 1 \\ \{2n,(2n-1)/3\}& \text{si } n\equiv 2 \end{cases} \pmod{3}.

Ces algorithmes inverses peuvent être représentés par des arbres, dont la racine est 1. Si la conjecture est vraie, ces arbres recouvrent tous les entiers naturels non nuls.

L'arbre reliant les nombres à durée de vol inférieure à 20 (cliquer pour agrandir).

Quelques résultats[modifier | modifier le code]

Approche probabiliste[modifier | modifier le code]

Il existe des arguments heuristiques et statistiques de nature à motiver la conjecture. Considérons par exemple une itération de la suite de Syracuse compressée sur un nombre v pris aléatoirement dans un intervalle assez grand. Si v est pair, il est multiplié par (1/2), tandis qu'un nombre impair se trouve multiplié par (3/2) environ. Dans les deux cas, on vérifie que la parité du résultat est indépendante de celle de v. Un raisonnement heuristique consiste à supposer que ce raisonnement probabiliste est valable pour n'importe quel terme de la suite compressée[2]. Bien que ce ne soit pas rigoureux (les termes de la suite ne sont pas aléatoires), certaines observations expérimentales tendent à le confirmer. Ainsi, le modèle obtenu en appliquant cette hypothèse prédit convenablement le temps de vol en altitude de la suite[3]. Avec cette heuristique, on peut dire que statistiquement, l'effet de deux opérations consécutives de la suite revient à multiplier le nombre de départ par (3/4), ou encore que l'opération de Syracuse est contractante, en moyenne, dans un rapport approximativement égal à la racine carrée de (3/4) = 0,866…

Ce rapport nettement inférieur à l'unité suggère fortement que les éléments successifs d'une suite de Syracuse ne peuvent croître indéfiniment. Il n'existe aucune preuve rigoureuse de cette affirmation (et même si l'on parvenait à rendre rigoureux cet argument probabiliste, cela ne permettrait pas encore de conclure, un événement de probabilité nulle n'étant pas pour autant impossible). Également, l'argument ici esquissé n'exclut nullement l'existence de cycles non triviaux.

Concernant la répartition des nombres qui satisfont à l'hypothèse de Syracuse, par des méthodes élaborées de programmation linéaire on arrive à montrer que, pour  x suffisamment grand, le nombre d'entiers inférieurs à  x qui satisfont l'hypothèse de Syracuse est au moins  x ^  a pour certaine constante  a < 1 . En 2002, I. Krasikov et J. Lagarias obtinrent  a=0,84 .

Approche calculatoire[modifier | modifier le code]

Une voie d'exploration intéressante consiste en l'étude systématique du comportement de la suite de Syracuse à l'aide d'ordinateurs, pour des nombres de départ de plus en plus grands. On[4],[5] a ainsi vérifié la conjecture pour tout N < 1,25×262. La grandeur de ce nombre, supérieur à cinq milliards de milliards, est de nature à renforcer notre croyance en la véracité de la conjecture de Syracuse. Il convient cependant de comprendre qu'aussi loin que l'on poursuive le calcul, il ne peut directement fournir une démonstration de cette conjecture ; le calcul pourrait éventuellement, au contraire, rencontrer un contre-exemple, qui démontrerait la fausseté de la conjecture. Cette approche présente aussi l'intérêt de fournir des résultats numériques utilisables par les théoriciens pour compléter leurs démonstrations. Par exemple, en utilisant la borne N ci-dessus avec un théorème[6]sur la longueur des cycles de la suite de Syracuse, on peut conclure qu'à part le cycle trivial (1,4,2,1…) il n'existe aucun cycle de longueur inférieure à 17 milliards[7].

Les résultats numériques permettent de chercher des corrélations entre le nombre de départ N et la durée de vol, ou le record d'altitude. On a ainsi observé que si les records d'altitude pouvaient être très élevés, la durée du vol était en comparaison plus modeste. Une observation sur les nombres déjà étudiés semble indiquer que l'altitude maximale est majorée par φ(N).N2, où φ(N) pourrait être soit une constante, soit une fonction lentement croissante. Le temps de vol est plus erratique mais semble majoré par un multiple du logarithme de N. Les expériences numériques suggèrent ainsi de nouvelles conjectures auxquelles les théoriciens peuvent s'attaquer.

En revanche, la recherche théorique est seule en mesure d'apporter des lumières concernant l'existence de trajectoires infinies : il a été démontré que l'ensemble des nombres appartenant à une telle trajectoire aurait une densité asymptotique nulle ; pour rester dans l'image du vol, on pourrait dire que le grêlon, pour ne pas retomber jusqu'au sol, doit acquérir et maintenir une haute « vitesse de libération ». Si la conjecture est vraie, alors un tel vol infini est impossible.

Un énoncé indécidable ?[modifier | modifier le code]

La relative faiblesse des résultats obtenus en dépit de l'application acharnée de méthodes mathématiques puissantes par des esprits brillants a conduit certains chercheurs à se demander si la conjecture de Syracuse est un problème indécidable. En 1972, John Conway a établi l'indécidabilité algorithmique pour une famille de problèmes qui généralise de manière naturelle le problème 3x+1 (voir l'article sur le langage de programmation exotique FRACTRAN). Ce résultat implique qu'il y a dans la famille considérée des problèmes individuels qui sont indécidables (il est en fait même possible, en théorie sinon en pratique, d'en expliciter un), mais ne résout pas la décidabilité du problème de Syracuse en particulier[8].

Notes et références[modifier | modifier le code]

  1. (en) Jeffrey C. Lagarias, « The 3x + 1 problem and its generalizations », Amer. Math. Month., vol. 92, no 1,‎ janvier 1985, p. 3-23 (JSTOR 10.2307/2322189, lire en ligne)
  2. Cette piste est explorée par Terras, Everett et Crandall (1978-1977), Lagarias (1985), et E. Barone (1999) [1]
  3. Jean-Paul Delahaye, Jeux mathématiques et mathématiques des jeux, Belin - Pour la Science,‎ décembre 1999 (ISBN 2-84245-010-8), chap. 18 (« La conjecture de Syracuse »), p. 124-125
  4. janvier 2009 - T. Oliveira e Silva.
  5. T.Oliveira e Silva, Empirical verification of the 3x+1 and related conjectures, The Ultimate Challenge : the 3x+1 problem, American Mathematical Society, Providence, (2010) p.189-207
  6. (en) Shalom Eliahou, The 3x+1 problem: new lower bounds on nontrivial cycle lengths, Discrete Mathematics 118 (1993) p. 45-56
  7. Shalom Eliahou, Le problème 3n+1 : y a-t-il des cycles non triviaux ?, Images des mathématiques (2011) [2]
  8. John H. Conway, On Unsettleable Arithmetical Problems, Amer. Math Monthly, 120, no 3 (mars 2013), 192-198.

Sources[modifier | modifier le code]

Liens externes[modifier | modifier le code]