Le problème 3n+1 : cycles de longueur 5 (II)

Pista azul El 16 noviembre 2011  - Escrito por  Shalom Eliahou Ver los comentarios (12)
Leer el artículo en  

La transformation $3n+1$ de Collatz admet-elle des trajectoires cycliques de longueur 5 ? Oui, celle de $-5$. Mais la réponse est non sur les entiers positifs. D’où vient cette différence ?

Dans ce volet bleu sur le problème $3n+1$, nous montrons qu’il n’existe aucun cycle de longueur 5 pour la transformation de Collatz sur les entiers positifs.

En fait on peut montrer plus : il n’existe aucun tel cycle de longueur comprise entre 4 et environ 17.000.000.000 (17 milliards), comme on le verra dans un article ultérieur.

L’intérêt de cette preuve séparée pour la longueur 5 est d’être assez élémentaire, tout en contenant déjà l’idée essentielle pour la suite : la mise en évidence d’une équation très contraignante associée à un cycle. Pour aller plus loin, c’est sur piste rouge qu’il faudra s’aventurer, en s’équipant de logarithmes et d’approximations rationnelles ; il n’en sera nul besoin ici.

Quelques rappels

Rappelons la définition de la transformation de Collatz, présentée dans le volet vert de cette série [1]: si $n$ est un entier pair, on le transforme en $n/2$; s’il est impair, on le transforme en $3n+1$.

On symbolise cette transformation par une petite flèche. Par exemple, $10 \rightarrow 5$ (qu’on peut lire «10 va sur 5») et $5 \rightarrow 16$. La règle générale s’écrit donc $n \rightarrow n/2$ ou $n \rightarrow 3n+1$, suivant que $n$ est pair ou impair.

La trajectoire de $n$ est la suite obtenue en partant de $n$ et en lui appliquant la transformation de Collatz de façon répétée. Par exemple, la trajectoire de 1 est la suite 1,4,2,1, ..., qui est donc un cycle de longueur 3.

Le problème de Collatz consiste à déterminer s’il est vrai que la trajectoire de n’importe quel nombre entier positif $n$ de départ tombe forcément sur 1.

Cycles dans les entiers négatifs

La transformation de Collatz peut très bien s’étendre aux entiers négatifs, avec exactement les mêmes formules :

  • si $n$ est pair, on l’envoie sur $n/2$ ;
  • si $n$ est impair, on l’envoie sur $3n+1$.

Par exemple, la trajectoire de $-1$ est un cycle de longueur 2 :
\[-1 \rightarrow -2 \rightarrow -1.\]
La trajectoire de $-5$ donne un autre cycle, cette fois-ci de longueur 5 :

PNG

Retour aux entiers positifs

Pourrait-il aussi exister un cycle de longueur 5 dans les entiers positifs ? La réponse est non. Pour le prouver, nous procéderons par l’absurde : on suppose au contraire qu’il en existe un ; puis on le manipule comme on peut, révélant ainsi une équation qui lui est associée ; et on conclut en constatant que cette équation est insoluble.

Le plus petit élément d’un cycle

Commençons par une remarque à la fois simple et utile : pour un hypothétique cycle de la transformation de Collatz sur les entiers positifs, son plus petit élément est forcément impair.

En effet, notons $C$ ce cycle et $m$ son plus petit élément. Alors bien sûr, $C$ est la trajectoire de $m$. Notons maintenant $m'$ le nombre obtenu à partir de $m$ par transformation de Collatz. Alors $m'$ est

  • lui aussi dans $C$, puisque $C$ est la trajectoire de $m$ ;
  • plus grand que $m$, puisque $m$ est minimal dans $C$.

Or si par l’absurde $m$ était pair, on aurait $m'=m/2$ qui est plus petit que $m$ : contradiction. Donc $m$ est bien impair.

Le cas de longueur 5

Considérons maintenant un hypothétique cycle de longueur 5 dans les entiers positifs. On notera ses cinq éléments distincts deux à deux $a_1,a_2,a_3,a_4,a_5$, donnant

PNG - 11.4 KB

par transformation de Collatz.

Quitte à renommer les indices, on peut supposer que le plus petit des cinq est $a_1$. Alors $a_1$ est forcément impair par la remarque ci-dessus, et en particulier $a_2=3a_1+1$. Notons encore que $a_1$ est différent de 1, puisque la trajectoire de 1 donne un cycle de longueur 3 et non 5. Donc $a_1$ est supérieur ou égal à 3.

Stabilité par transformation de Collatz

Si on applique la transformation de Collatz à la liste \[a_1,a_2,a_3,a_4,a_5\] des éléments du cycle, on obtient la même liste décalée d’un cran, puisque c’est un cycle justement : \[a_2,a_3,a_4,a_5,a_1.\]
On exprime cela en disant que ce cycle est stable par transformation de Collatz. C’est évident, mais ce sera crucial pour la suite.

Répartition des pairs et des impairs

Pour savoir concrètement comment la transformation de Collatz agit sur $a_1,\ldots,a_5$, on doit savoir lesquels parmi eux sont pairs et lesquels sont impairs. On sait déjà, par minimalité de $a_1$ dans ce cycle, que $a_1$ est impair. Quant aux quatre autres termes, on va montrer par étapes successives que

  • $a_2$, $a_4$ et $a_5$ sont pairs ;
  • $a_3$ est impair.

En voici la preuve.

(1) Puisque $a_1$ est impair, il suit que $a_2=3a_1+1$. Donc $a_2$ est pair.

(2) Il suit que $a_3=a_2/2 = (3a_1+1)/{2}$. Se pourrait-il que $a_3$ soit pair ? Si c’était le cas, on aurait alors $a_4=a_3/2$ et, si on enchaîne avec ce que l’on sait déjà sur $a_2$ et $a_1$, cela donnerait
\[ \begin{array}{rcl} a_4 & = & \frac{a_3}2\\ & = & \frac{a_2}4\\ & = & \frac{3a_1+1}{4}. \end{array} \]
Mais cette relation dirait que $a_4$ vaut environ les trois quarts de $a_1$ ; il serait donc plus petit que $a_1$ (puisque celui-ci est supérieur ou égal à 3), en contradiction avec la minimalité de $a_1$. L’hypothèse que $a_3$ est pair conduisant à une contradiction, on conclut que $a_3$ est forcément impair.

(3) Puisque $a_3 \rightarrow a_4$, il suit que $a_4=3a_3+1$, et donc que $a_4$ est pair. De plus, comme $a_4 \rightarrow a_5$, il suit que $a_5=a_4/2$.

(4) Pour finir, $a_5$ est pair. En effet, d’une part on a $a_5 \rightarrow a_1$, et de l’autre $a_5$ est plus grand que $a_1$ (toujours par minimalité de $a_1$). La seule possibilité est que $a_5$ soit pair et donc que $a_1=a_5/2$. Car dans le cas contraire, $a_1$ serait plus grand que $a_5$, ce qui est exclu.

Nous connaissons maintenant l’exacte répartition des pairs et des impairs dans notre cycle. Résumons les formules obtenues en chemin, exprimant chaque terme du cycle en fonction du précédent :
\[ \begin{array}{rcl} a_1 & = & \frac{a_5}{2}\\ a_2 & = & 3a_1+1\\ a_3 & = & \frac{a_2}{2}\\ a_4 & = & 3a_3+1\\ a_5 & = & \frac{a_4}{2}. \end{array} \]

Le produit des termes du cycle

L’étape suivante consiste à prendre le produit de ces 5 termes, qu’on appellera $P$. En les lisant du côté gauche de la colonne d’égalités ci-dessus, on obtient
\[P\, = \, a_1 a_2 a_3 a_4 a_5.\]
En les lisant maintenant du côté droit — et avec la première ligne lue en dernier —, on obtient toujours $P$ bien sûr, mais exprimé différemment :
\[P\, = \, (3a_1+1) \frac{a_2}{2} (3a_3+1) \frac{a_4}{2} \frac{a_5}{2} .\]
C’est l’existence même de ces deux expressions différentes de $P$ qui donne lieu à l’équation annoncée. La voici donc, dans une première version brute :
\[ a_1 a_2 a_3 a_4 a_5 \, = \, (3a_1+1) \frac{a_2}{2} (3a_3+1) \frac{a_4}{2} \frac{a_5}{2}. \]

Quelques manipulations

Cette équation contient des informations intéressantes. Mais pour les révéler, il faut s’autoriser quelques manipulations algébriques. Rassemblons d’abord les trois dénominateurs $2$, ce qui donne $2 \times 2 \times 2 = 8$ :
\[ a_1 a_2 a_3 a_4 a_5 \, = \, \frac{(3a_1+1) a_2 (3a_3+1) a_4 a_5}{8}. \]
Puis chassons le dénominateur $8$ du côté droit, en multipliant simplement les deux côtés de l’égalité par $8$ :
\[ 8 a_1 a_2 a_3 a_4 a_5 \, = \, (3a_1+1) a_2 (3a_3+1) a_4 a_5. \]
Dans le terme de droite, intervertissons $a_2$ et son voisin de droite :
\[ 8 a_1 a_2 a_3 a_4 a_5 \, = \, (3a_1+1) (3a_3+1) a_2 a_4 a_5. \]
On voit que $a_2a_4a_5$, qui est non-nul, est un facteur commun aux deux côtés de l’égalité. On peut donc s’en débarrasser en divisant le tout par ce facteur, ce qui donne :
\[ 8 a_1 a_3 \, = \, (3a_1+1) (3a_3+1). \]
Divisons maintenant les deux côtés par $a_1a_3$, qui est lui aussi non-nul :
\[ 8 \, = \, \frac{(3a_1+1)}{a_1} \frac{(3a_3+1)}{a_3}. \]
En appliquant l’identité générale \[\frac{a+b}c = \frac ac + \frac bc\] aux deux facteurs du terme de droite, on obtient finalement :

\[ 8 \, = \, (3+\frac1{a_1}) (3+\frac1{a_3}). \]

C’est l’équation annoncée, sous sa forme épurée, associée à n’importe quel hypothétique cycle de longueur 5.

Fin de la preuve

Nous pouvons maintenant conclure : comme $a_1$ et $a_3$ sont supposés positifs, l’équation ci-dessus est impossible à satisfaire, puisqu’à droite on obtient un nombre supérieur à 9, alors qu’à gauche on n’a que 8.

On vient de prouver que la transformation de Collatz n’admet aucun cycle de longueur 5 sur les entiers positifs.

Une apparente contradiction

Il y a une bizarrerie à comprendre : le développement ci-dessus reste valable sur les entiers négatifs, quitte à remplacer les comparaisons de grandeur par des comparaisons de grandeur en valeur absolue [2]. Comment se fait-il que, malgré cela, il existe bel et bien un cycle de longueur 5 dans les entiers négatifs?

La solution de cette apparente contradiction tient à l’ultime argument de la preuve : bien qu’insoluble dans les entiers positifs, l’équation associée admet quand même des solutions dans les entiers négatifs ! En effet, posons $a_1=-5$ et $a_3=-7$. Un petit calcul montre qu’on a bien égalité,
\[ 8 \, = \, (3+\frac1{-5}) (3+\frac1{-7}). \]
Cette solution vient d’ailleurs, comme on pouvait s’y attendre, des deux termes impairs du cycle $-5,-14,-7,-20,-10,-5$.

Épilogue

À part les trajectoires de $-1$ et de $-5$, on connaît encore un autre cycle pour la transformation de Collatz sur les entiers négatifs. C’est la trajectoire de $-17$, qui est de longueur 18 :
\[ \begin{array}{l} & -17 \rightarrow -50 \rightarrow-25 \rightarrow-74 \rightarrow-37 \rightarrow-110 \rightarrow -55 \rightarrow-164\\ & \rightarrow-82 \rightarrow-41 \rightarrow-122 \rightarrow-61 \rightarrow -182 \rightarrow-91 \rightarrow-272 \\ & \rightarrow-136 \rightarrow-68 \rightarrow-34 \rightarrow-17 \rightarrow \ldots \end{array} \]

Dans le volet rouge de cette série, on exclura d’abord les cycles de longueur 18 sur les entiers positifs, avec des arguments analogues à ceux présentés ici pour la longueur 5. Mais à une différence importante près : en longueur 18, il devient presque impossible de connaître la répartition des pairs et des impairs, sa combinatoire devenant ingérable.

Pour surmonter cette difficulté, il faudra faire un petit saut dans l’abstraction, en introduisant une notation spécifique pour distinguer les pairs des impairs dans un cycle hypothétique.

Ce n’est que dans une seconde partie du volet rouge qu’on invoquera les logarithmes et l’approximation rationnelle pour pouvoir exclure, sur les entiers positifs, toutes les longueurs de cycles comprises entre 4 et 17.000.000.000.

Post-scriptum :

L’auteur remercie Etienne Ghys et Bruno Martin pour leurs commentaires, et Carole Gaboriau pour son aide technique. La rédaction d’Images des maths, ainsi que l’auteur, remercient pour leur relecture attentive,
les relecteurs dont le pseudonyme est le suivant : Struffi, P.Levallois, GANDONOU Akoudo David, Joël Merker et Gilles Damamme.

Article édité par Étienne Ghys

Notas

[2Par exemple, $-1$ est plus grand que $-2$, mais en valeur absolue il est plus petit.

Comparte este artículo

Para citar este artículo:

Shalom Eliahou — «Le problème 3n+1 : cycles de longueur 5 (II)» — Images des Mathématiques, CNRS, 2011

Créditos de las imágenes:

Imagen de portada - L’auteur remercie Jason Davies, créateur du logo.

Comentario sobre el artículo

  • Le problème 3n+1 : cycles de longueur 5 (II)

    le 16 de noviembre de 2011 à 11:17, par Bruno Duchesne

    Bonjour,

    Tout d’abord, merci pour cette série d’articles sur le problème $3n+1$.

    J’ai juste une remarque sur la contradiction amenant l’impossibilité d’un cycle de longeur 5 parmi les entiers positifs. Une fois que l’on connaît la répartition des parités, on peut facilement exprimer $a_5$ en fonction de $a_1$ et l’équation $a_1=a_5/2$ donne une équation linéaire n’ayant que $-5$ comme solution. Ce qui me paraît plus simple mais ce n’est sûrement la méthode qui se généralise aux cycles de longueur plus grande.

    Vivement la suite.

    Bruno.

    Répondre à ce message
  • Le problème 3n+1 : cycles de longueur 5 (II)

    le 16 de noviembre de 2011 à 14:20, par Gilles Bonnet

    J’ai eu le même réflexe que Bruno pour trouver un cycle de longueur 5.
    Je suis maintenant impatient de lire les prochains articles.

    Répondre à ce message
    • Le problème 3n+1 : cycles de longueur 5 (II)

      le 17 de noviembre de 2011 à 09:49, par Shalom Eliahou

      Oui Bruno et Gilles, vous avez raison : en résolvant le système linéaire on tombe sur l’équation $a_1 = (9a_1+5)/8$, ce qui donne $-5$ pour seule solution. Mais en effet, le développement présenté ici fonctionne mieux en longueur supérieure.

      Bien cordialement,

      Shalom

      Répondre à ce message
  • Le problème 3n+1 : cycles de longueur 5 (II)

    le 16 de noviembre de 2011 à 18:15, par Pierre de la Harpe

    Joli !

    Ma seule petite déception vient des lecteurs et non de l’auteur : aucune réaction jusqu’ici à l’assertion du chapeau du premier tiers-temps, selon laquelle le problème 3n+1 est «accessible à tout écolier de 8 ans».

    Dans quelques courriels hors Images des Maths, Shalom et moi avons débattu de la question suivante : y a-t-il un «problème ouvert» mathématique qui soit plus élémentaire que tous les autres et si oui quel est-il ? On aura compris que nos convictions étaient inégales ...

    J’espère que, d’une façon ou d’une autre, un débat de ce genre va trouver sa place dans les commentaires, et j’espère même y lire l’opinion de lecteurs qui ne sont pas mathématiciens professionnels.

    Répondre à ce message
    • Le problème 3n+1 : cycles de longueur 5 (II)

      le 17 de noviembre de 2011 à 18:18, par Thomas Boulier

      Pour répondre quant aux problèmes ouverts élémentaires, il me semble que celui des nombres premiers jumeaux me semble être un bon candidat, non ?

      Répondre à ce message
      • Le problème 3n+1 : cycles de longueur 5 (II)

        le 18 de noviembre de 2011 à 09:22, par Shalom Eliahou

        Le bagage mathématique requis pour comprendre le problème 3n+1 est extrêmement maigre. C’est un sous-ensemble strict, me semble-t-il, de celui requis pour comprendre n’importe quel problème sur les nombres premiers.

        Shalom

        Répondre à ce message
    • Le problème 3n+1 : cycles de longueur 5 (II)

      le 8 de diciembre de 2011 à 18:35, par Hervé

      Je devais avoir effectivement environ 8 ans quand j’ai découvert ce problème (dans la revue Virgule).

      Répondre à ce message
    • Le problème 3n+1 : cycles de longueur 5 (II)

      le 25 de mayo à 15:40, par pierre simonnet

      C’est vrai que c’est joli.
      l’enoncé est il accessible aux enfants de 8 ans? Je pense que oui.
      ce que je trouve amusant c’est que grâce à la théorie des automates finis, on peut montrer que pour un k fixé, on peut prouver que l’existence d’un cycle de longueur inférieur ou égal à k, autre que le cycle trivial de longueur 3, est un problème décidable. Malheureusement comme il s’agit de composer un petit transducteur en base 2, de 7 états ( k-1) fois avec lui même, on se retrouve à tester
      le vide sur un automate à 7^k états. Shalom à de l’avance sur un programme éventuel.

      Répondre à ce message
  • Le problème 3n+1 : cycles de longueur 5 (II)

    le 16 de noviembre de 2011 à 20:55, par Dimitri Karpov

    Cette série d’articles est très prometteuse, et c’est vrai qu’en dehors de la réputation de ce problème, on n’en sait pas toujours grand chose. Je suis donc content de voir quelques résultats ou ébauches de résultats prouvés, vivement la suite et bravo à l’auteur du billet!

    Répondre à ce message
  • Le problème 3n+1 : cycles de longueur 5 (II)

    le 22 de noviembre de 2011 à 22:46, par Nils Berglund

    J’ai souvenir d’un exposé de Yakov Sinai, il y a une dizaine d’années, sur une version stochastique du problème. Il y suggérait qu’une version aléatoire de la conjecture pourrait être vraie (pour presque toute valeur initiale). Quelqu’un est-il au courant de développements dans cette direction?

    Répondre à ce message
  • Le problème 3n+1 : cycles de longueur 5 (II)

    le 29 de marzo de 2018 à 14:50, par ROUAK

    Je ne comprend pas le lien entre cette affirmation tirée de l’article:

    «En fait on peut montrer plus : il n’existe aucun tel cycle de longueur comprise entre 4 et environ 17.000.000.000 (17 milliards), comme on le verra dans un article ultérieur» ,

    et le fait que ce cycle 3->10->5->16->8->4->2->1 contient 7 cycle.

    qu’est-ce que je n’ai pas bien compris?

    Merci d’avance pour votre réponse

    Répondre à ce message
  • Le problème 3n+1 : cycles de longueur 5 (II)

    le 18 de julio à 15:30, par CAMI

    Tout nombre impair x entier strictement positif peut être représenté par l’une des deux formules suivantes utilisant deux variables entières a et b :

    - ((3*a-2)*2^(2*b)-1)/3 avec a entier impair > 0 et b entier > 0.

    - ((3*a-1)*2^(2*b-1)-1)/3 avec a entier pair > 0 et b entier > 0.

    Démonstration :

    Soit x impair > 0 on a x = 3*x/3 = ((3*x+1)-1)/3 et 3*x+1 est pair puisque x est impair.
    3*x+1 pair est donc le produit d’un nombre impair y par une puissance de 2.
    3*x+1 est 1 modulo 3.
    Les puissances de 2 paires 2^(2*b) sont 1 modulo 3.
    Les puissances de 2 impaires 2^(2*b-1) sont -1 modulo 3.
    Si la puissance de 2 est paire y doit être 1 modulo 3 soit y impair = 3*a-2 et a impair > 0.
    Si la puissance de 2 est impaire y doit être -1 modulo 3 soit y impair = 3*a-1 et a pair > 0.
    Donc x est bien égal à ((3*a-2)*2^(2*b)-1)/3 avec a impair > 0 et b >0
    ou égal à ((3*a-1)*2^(2*b-1)-1)/3 avec a pair > 0 et b >0.

    Définition de le table de Syracuse :

    La première colonne d’indice zéro contient les nombres impairs y plus grand que zéro non multiple de 3 dans l’ordre naturel d’occurrence : 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, ...
    Les colonnes d’indice i > 0 contiennent (y*2^(2*i)-1)/3 si y est 1 modulo 3 ou (y*2^(2*i-1)-1)/3 si y est -1 modulo 3.
    Le tableau commence par :

    1, 1, 5, 21, 85, 341, 1365, ....
    5, 3, 13, 53, 213, 853, 3413, ....
    7, 9, 37, 149, 597, 2389, 9557, ....
    11, 29, 117, 469, 1877, 7509, 30037, ....
    13, 17, 69, 277, 1109, 4437, 17749, ....
    17, 11, 45, 181, 725, 2901, 11605, ....
    Les propriétés remarquables de la table de Syracuse :

    Tout nombre impair strictement positif non multiple de 3 est présent une seule fois colonne 0.
    Tout nombre impair strictement positif non multiple de 3 est présent une seule fois dans les colonnes d’indice > 0.
    Tout nombre impair strictement positif est présent une seule fois dans les colonnes d’indice > 0.
    Tous les nombres d’une même ligne d’indice de colonne > 0 ont tous le même successeur direct dans une suite de Syracuse et ce nombre est celui colonne 0 dans la ligne.
    Seul le nombre impair 1 est présent deux fois dans la première ligne colonne 0 et colonne 1 cycle trivial oblige puisque 1 doit être son propre successeur impair.
    Comme tous les nombres impairs d’une même ligne avec indice de colonne > 0 ont tous le même successeur (en colonne zéro de la ligne) et que ce successeur est unique il est impossible de revenir à la même ligne après l’avoir quittée sauf si d’une ligne d’indice > 1 on arrive à la première ligne pour atteindre le cycle trivial.
    Donc une suite de Syracuse ne peut que se terminer par 1 ou diverger.
    La suite ne peut diverger car il est évident que en partant de 1 on peut construire toute suite de Syracuse inverse et que chacune de ces suites vont diverger.
    D’où la preuve de la validité de la conjecture.
    Mais si on choisi un très grand nombre impair proche de l’infini pour commencer une suite de Syracuse on peut ne jamais avoir le temps de calcul nécessaire pour faire la preuve que la suite se termine bien par 1 !!!
    En partant d’un nombre impair x > 0 on va obtenir y nombres impairs successeurs de x avant d’atteindre 1, quelque soit y aussi grand qu’il soit il existe toujours une infinité de nombres x tels qu’ils ont tous y nombres impairs successeurs de x avant d’atteindre 1.
    Donc il existe une infinité de nombres impairs x qui ont une infinité de successeurs impairs avant d’atteindre 1, ces nombres x sont bien sur proches de l’infini.

    Répondre à ce message

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexióninscribirse¿contraseña olvidada?

La traducción del sitio del francés al castellano se realiza gracias al apoyo de diversas instituciones de matemáticas de América Latina.