Conjecture de Syracuse - Définition

Introduction

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 à 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 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 ».

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

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 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 :

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…).

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.