La conjecture de Syracuse (Probleme de Collatz)


Présentation de la conjecture

   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.

Une métaphore éclairante

   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.

Des avancées intéressantes

   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 établis

   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.

Données heuristiques et indécidabilité du problème

   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 !

Bibliographie

"La conjecture de Syracuse", par Jean-Paul Delahaye in: _Pour La Science_ N°247 de mai 1998.

Et sur le web : http://www.ieeta.pt/~tos/3x+1.html


Cette page est extraite de la FAQ fr.sci.maths