Suite de Syracuse

Suite de Syracuse

Conjecture de Syracuse

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 quatorze.

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 à 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 les suites de Syracuse de tous les nombres strictement positifs atteignent 1.

En dépit de la simplicité de son énoncé, cette conjecture continue de défier 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 ».

Sommaire

Origines

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 : le succès fut immédiat et 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 de Yale et Chicago.

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

Première approche et vocabulaire

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

u0 = N
et pour tout entier  n \geq 0 : u_{n+1} =  \begin{cases}
  \frac{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 un = 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+1 < u0
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
u0 u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 u11 u12 u13 u14 u15 u16 u17 u18 u19 u20
15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 4 2 1

Autres formulations

On peut donner de nombreuses formulations équivalentes au problème de Syracuse.

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

Par exemple, on remarque que si un est impair dans la formule ci-dessus, un + 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…).

v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14
15 23 35 53 80 40 20 10 5 8 4 2 1 2 1


La conjecture elle-même 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

Quelques résultats

Il existe des arguments heuristiques et statistiques de nature à motiver la conjecture : par exemple, considérons l'effet de l'opération de la suite de Syracuse compressée sur un nombre v 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, de sorte que statistiquement l'on peut dire que 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. Étonnamment, on ne connaît aucune preuve rigoureuse de cette affirmation. Il convient également de noter que 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 xa pour certaine constante a < 1. En 2002, I. Krasikov et J. Lagarias obtinrent a = 0,84 .

L'étude systématique du comportement de la suite de Syracuse, rendue possible par les ordinateurs pour des nombres de départ de plus en plus grands, offre une voie d'exploration intéressante. On a ainsi vérifié la conjecture pour tout N < 262 (janvier 2008 - T. Oliveira e Silva.) La grandeur de ce nombre, supérieur à quatre milliards de milliards, est de nature à renforcer notre croyance en la vérité 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. Ces calculs ont 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 sur la longueur des cycles de la suite de Syracuse, démontré par Matti K. Sinisalo (http://www.geocities.com/mattiksinisalo/collatz.doc), on peut conclure qu'à part le cycle trivial (1,4,2,1…) il n'existe aucun cycle de longueur inférieure à 17 milliards !

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. Ces observations suggèrent ainsi de nouvelles conjectures auxquelles les théoriciens peuvent s'attaquer.

Sur un plan théorique, certains chercheurs se sont demandé si la conjecture de Syracuse pourrait être un problème indécidable. En 1972, John Conway établit l'indécidabilité algorithmique pour une famille de problèmes qui généralise de manière naturelle le problème 3x+1. Ce résultat implique qu'il y a dans la famille considérée des problèmes individuels qui sont indécidables, mais ne dit rien du problème de Syracuse en particulier.

Références

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Conjecture de Syracuse ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Suite de Syracuse de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Suite (mathématiques) — Pour les articles homonymes, voir Suite. En mathématiques, une suite[1] est une famille d éléments indexée par les entiers naturels. Une suite finie est une famille indexée par les entiers strictement positifs inférieurs ou égaux à un certain… …   Wikipédia en Français

  • Syracuse (New-York) —  Cet article concerne la ville de l État de New York nommé Syracuse. Pour les autres significations du nom Syracuse, voir Syracuse (homonymie). Syracuse …   Wikipédia en Français

  • Syracuse Nationals — 76ers de Philadelphie 76ers de Philadelphie …   Wikipédia en Français

  • Syracuse (New York) — Cet article concerne la ville de l État de New York nommé Syracuse. Pour les autres significations du nom Syracuse, voir Syracuse (homonymie). 43° 02′ 49″ N …   Wikipédia en Français

  • Syracuse (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sommaire 1 Toponymie 2 Mathématiques 3 …   Wikipédia en Français

  • Syracuse Crunch — Crunch de Syracuse Crunch de Syracuse …   Wikipédia en Français

  • Conjecture De Syracuse — 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… …   Wikipédia en Français

  • Conjecture de Syracuse — 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… …   Wikipédia en Français

  • Conjecture de syracuse — 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… …   Wikipédia en Français

  • Le problème de Syracuse — Conjecture de Syracuse 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… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”