Conjecture de Syracuse
Sous son apparente simplicité, cette suite défie encore les mathématiciens actuels. Il semble que, quel que soit le terme initial N de la suite, celle-ci finisse inexorablement par boucler sur 1 , 4 , 2 , 1 ... Cette observation non démontrée s'appelle la conjecture de Syracuse ou conjecture de Collatz, aussi connue sous le nom de conjecture du 3n+1, de conjecture d'Ulam ou de suite de Hailstone.
Par exemple, en commençant avec n = 6, nous obtenons la suite (6, 3, 10, 5, 16, 8, 4, 2, 1). La conjecture de Collatz dit que ce processus s'arrête toujours, indépendamment de la valeur de départ, ce qui revient à dire que le chiffre 1 est toujours atteint.
| Sommaire |
Origines
Les noms multiples de cette suite prouvent la difficulté d'en retrouver la paternité exacte. La naissance de ce problème semble se situer autour des années 1950. Helmut Hasse, un ami de Lothar Collatz, de visite à l'université américaine de Syracuse propose le problème aux universitaires. Celui-ci remporte un vif succès et la suite de Collatz, appelée aussi algorithme de Hasse prend alors le nom de suite de Syracuse. Entretemps, le mathématicien polonais Stanislas Ulam le répand dans l'université de Los Alamos et la suite devient la suite d'Ulam. Dans les années 1960, le problème est repris par le mathématicien S. Kakutani qui le diffuse dans les universités de Yale et Chicago. Le problème prend alors le nom de problème de Kakutani.
L'étude de cette suite a donné lieu à la création d'un vocabulaire très imagé comme le temps de vol, le temps de vol en altitude, l'altitude maximale, le facteur d'expansion...
Cette conjecture mobilisa tant les mathématiciens durant les années 60, en pleine guerre froide, qu'une blague courut selon laquelle ce problème serait l'œuvre d'un complot soviétique pour ralentir la recherche américaine. Plus sérieusement, Paul Erdős dit à propos de la conjecture de Collatz : « les mathématiques ne sont pas encore prêtes pour de tels problèmes ». Il proposa une offre de 500 $ à quiconque lui donnerait une solution.
Première approche et vocabulaire
Syracuse15.png
Syracuse127.png
Le calcul de la suite pour N = 7 : (7 , 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, ...) laisse déjà entr'apercevoir que la suite peut prendre des valeurs assez grandes avant de retomber à 1. L'observation graphique de la suite pour N = 15 et N = 127 montre que la suite peut monter assez haut avant de redescendre. C'est de cette observation qu'est né le vocabulaire sur l'étude de cette suite. En observant ces graphiques, on a l'impression d'y voir la trajectoire d'une feuille emportée par le vent.
On parle donc 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 12 pour la suite de syracuse15 et de 31 pour la suite de syracuse127
- le temps de vol en altitude : c'est le plus petit indice n tel que un< N
- Il est de 17 pour la suite de syracuse15 et de 15 pour la suite de syracuse127
- l'altitude maximale : c'est la valeur maximale de la suite
- Elle est de 80 pour la suite de syracuse15 et de 2186 pour la suite de syracuse127
- Le facteur d'expansion: c'est le rapport entre le nombre de départ et l'altitude maximale
Enoncés équivalents
On rencontre parfois une relation de récurrence de la forme
Qui ne change pas fondamentalement le problème mais qui réduit le temps de vol.
Des énoncé équivalents de la conjecture existent
- si on arrête la suite dès qu'elle atteint 1, la conjecture peut s'exprimer par pour tout N, la suite possède un nombre fini de termes impairs (resp pairs)
- Pour tout N, la suite possède une durée de vol finie
- Pour tout N, la suite possède une durée de vol en altitude finie
Quelques résultats
Il est facile de démontrer que si la suite commençant par k2p - 1 a une durée de vol finie, il en est de même de la suite commençant par k3p - 1 .
On est capable de démontrer que si N = 4k+1 ou 4k ou 4k+2, sa durée de vol en altitude est finie, ce qui fait que l'on peut diviser par 4 le nombre de cas à étudier. Une tentative est donc faite de travailler sur la forme de N pour diminuer le nombre de cas à étudier.
Une autre voie d'exploration est une étude systématique par ordinateur de tous les cas. Jusqu'à présent, les ordinateurs ont prouvé la conjecture pour tout N < 262 (juin 2004- Eric Roosendaal ou T. Oliveira e Silva)
Des corrélations ont été cherchées entre le nombre N de départ 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 voisine de φ(N).N2 où φ(N) serait une fonction quasi-constante. Le temps de vol est plus erratique mais semble en général ne pas dépasser une fonction proportionnelle à ln(N)
Il existe des arguments heuristiques et statistiques qui renforcent la conjecture : si nous considérons uniquement les nombres impairs de la suite générée par le processus de Collatz, alors nous pouvons arguer qu'en moyenne le prochain nombre impair vaudra environ 3/4 du précédent, ce qui suggère qu'ils diminueront pour atteindre 1.
D'autres chercheurs comme J. Conway penchent pour l'indécidabilité de la conjecture. Ils tentent de travailler en élargissant le champ d'étude à d'autres suites du même type (problème 5n +1 etc).
Références
- Jeff Lagarias : The 3x+1 problem and its generalizations, American Mathematical Monthly Volume 92, 1985, pp. 3 - 23. À l'adresse électronique: http://www.cecm.sfu.ca/organics/papers/lagarias/
- Pour un historique
- Une page de la FAQ fr.sci.maths
- La conjecture de SyracuseJean-Paul Delahaye (Pour La Science: N°247 de mai 1998)