Le problème de la conjecture de Syracuse, également connue sous les noms de problème de Collatz, Kakutani, ou Ulam, se présente de manière très simple. On se donne une entier naturel n plus grand que 1. S'il est pair, on le divise par deux, s'il est impair, on le multiplie par 3 et on lui ajoute 1 (ce qui revient à lui appliquer la fonction x |-> 3x+1). On >conjecture< que l'on finit toujours par trouver la valeur 1 au fil des calculs, valeur à partir de laquelle on restera bloqué dans le cycle 1-4-2-1-... Cependant, le fait que l'on retrouve toujours 1 n'a pas été démontré et même si on est presque sûr que cela est vrai, quel que soit l'entier n choisi au départ, il n'est pas exclu qu'il existe un entier n ne vérifiant pas cette propriété, d'où le nom de : >conjecture< de Syracuse. Depuis plusieurs dizaines d'années, ce problème est activement étudié par les mathématiciens, mais n'a pas encore été résolu. Les recherches ont cependant bien avancé, comme nous allons le voir plus loin.
Comme souvent, les mathématiciens, en travaillant sur ce problème, ont senti que certaines idées étaient récurrentes et ont introduit un vocabulaire adapté pour décrire les phénomènes étudiées. Imaginons que l'on vérifie la propriété pour n=15. On obtient : 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1. On appelle cette suite finie d'entiers le VOL, ou la TRAJECTOIRE de 15. Il faut imaginer une représentation de cette suite sur un graphique, l'axe des abscisses figurant l'indice de chaque entier dans la suite, l'axe des ordonnées indiquant l'entier correspondant. On appelle ETAPE, un nombre de cette suite finie. Ici, par exemple, 80 est une étape du vol de 15. Si la conjecture est vraie, on remarque que la suite atteint une étape maximale, appelé ALTITUDE MAXIMALE du vol. Ici, l'altitude maximale était 160. On définit également la DUREE de chaque vol comme le nombre d'étapes à franchir avant d'arriver pour la première fois au chiffre 1, et la durée de VOL EN ALTITUDE comme la durée entre le moment où le vol commence, et celui où il repasse sous sa valeur initiale.
A partir de là, il est plus facile de comprendre les dernières avancées dans la résolution du problème. Il a été ainsi démontré que chacune des propositions suivantes était équivalente à l'énoncé de la conjecture de Syracuse elle-même : (1) Tout vol a une durée finie C'est en gros l'énoncé de la conjecture en elle-même. (2) Tout vol est de durée en altitude finie En effet, si ceci est vrai, alors on conclut sur notre problème par récurrence. Pour n=2 on finit par retomber sous 2, c'est à dire à 1. Supposons que n et tous les entiers plus petits quelui vérifient la conjecture. Démontrons que c'est alors le cas de n+1 : Le vol n+1 a une durée en altitude finie, donc, au cours des calculs, on arrive à n, ou à un entier inférieur, que l'on note i. Mais i vérifie la conjecture, donc il aboutit au cycle 4-2-1. Ainsi n+1 aboutit-il aussi à ce cycle. Réciproquement, si la conjecture est vraie, la propriété (2) est bien entendue vraie. (3) Tout vol a un nombre fini d'étapes paires (resp. impaires) On considère le vol n. Après un certain nombre d'étapes, on atteint un dernier nombre pair. On le divise par deux, et on obtient un impair. Mais, si on applique x -> 3x+1 à cet impair, on obtiendra un pair, ce qui contredit le fait qu'on ait dépassé les dernier pair, sauf si le nombre impair que l'on vient de trouver est 1. Alors on s'arrête dans les calculs, et n vérifie la conjecture, qui de ce fait est vraie. (4) Tout vol a un nombre fini d'étapes paires (resp. impaires) en altitude Démonstration analogue. Les mathématiciens désespèrent quant au fait de démontrer directement la conjecture elle-même, et pensent qu'il est moins difficile de montrer que l'une de ces propriétés, équivalentes au problème, est vraie. On sait par ailleurs montrer que la propriété est vraie pour un très grand nombre d'entiers. On considère par exemple n = 4*k + 1. En effectuant les calculs, on trouve qu'il devient 12*k+4, 6*k+2, 3*k+1, ce dernier entier étant plus petit que n. Pour n = 4*k, on descend sous n dès la première étape du calcul. De même que pour 4k + 2. Il suffirait donc de pouvoir montrer que 4k+3 a lui aussi une durée de vol en altitude finie pour conclure que la conjecture est vraie ! On peut affiner ce type de démonstration. En travaillant avec les entiers du type 65536*k + i (avec i compris entre 0 et 65535), tous les cas aboutissent sauf 1729 cas, donc il ne reste que 2,6% des nombres à étudier. Des développements plus récents ont montré que pour n assez grand, il existait une constante alpha telle que au moins n^alpha des entiers inférieurs à n possèdent la propriété de Syracuse. En 1995, J. Lagarias et D. Applegate démontrèrent ce résultat pour la constante alpha=0,81. Mais leurs calculs furent menés avec des ordinateurs et sont invérifiables à la main.
Les records enregistrés au fur et à mesure des recherches ont été soigneusement consignés. C'est à T. Oliveira e Silva que l'on doit les records les plus récents et les plus significatifs. Les records suivants proviennent de sa page web : Le plus grand nombre testé est : 77 * 2^50 = 86694292826882048. La conjecture a été vérifiée par deux fois avec des ordinateurs jusqu'à n = 2^51 = 2251799813685248. Le record de l'altitude maximale est tenu par le vol 82450591202377887, qui atteint l'entier : 875612750096198197075499421245450. D'autres records, datant de 1998 et sans doute améliorés depuis : Celui de vol de durée record en vol est celui du vol 100759293214567, de durée 1820 (c'est assez faible, on aurait pu croire que des entiers résisteraient plus). Enfin celui de durée en altitude record est le vol 70665924117439, dont la durée en altitude est de 1177 étapes.
Si l'on étudie la façon dont les entiers évoluent en terme de parité au cours d'un calcul de Syracuse, on peut avoir une idée de son temps de vol.. Ainsi, si l'on obtient souvent des nombres pairs, ils vont être divisés par deux, et on arrivera plus rapidement à 1 (en admettant qu'on arrive toujours à 1). En tenant compte du fait qu'un nombre impair donne un nombre pair et que ce dernier va être divisé par deux ensuite, et qu'il y a dans l'ensemble des entiers naturels autant de pairs que d'impairs, on estime, au moyen d'un calcul probabiliste, qu'un entier donné est en moyenne multiplié par 3/4 lorsqu'on effectue une étape du calcul. Ceci tend à confirmer la conjecture. Expérimentalement, ce résultat de 3/4 est très bien confirmé, et le modèle statistique semble performant. Cependant, certains mathématiciens sont arrivés à se poser la question de l'indécidabilité du problème. Ils ont proposé quelques extensions du problème : autoriser les entiers négatifs, ou remplacer 3x+1 quand x est impair par qx+1 avec q un entier impair donné. Pour certaines valeurs de q>3, la conjecture n'est pas vraie. Mais c'est J. Conway qui a semé le doute. Plutôt que de ce demander si un entier donné, au cours du calcul, était pair ou impair, c'est à dire avait 0 ou 1 pour reste par la division euclidienne par 2, il s'intéresse au reste par la division euclidienne par un entier p et propose alors p formules à employer pour effectuer les calculs selon ce que ce reste soit 0, 1, 2, .., ou p-1. Il a montré que si alors on étendait la conjecture de Syracuse, on arrivait à un problème indécidable. Finalement, on a vu que beaucoup de résultats tendent à nous faire penser qu'il est >presque< impossible que la conjecture soit fausse. Cependant, il est arrivé dans l'histoire que les mathématiciens aient une telle intuition très forte en faveur d'une conjecture et qu'elle soit en fait fausse. Les résultats de J. Conway montrant que des problèmes très similaires sont indécidables incitent donc à la prudence !
Et sur le web : http://www.ieeta.pt/~tos/3x+1.html