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

Piste bleue 16 novembre 2011  - Ecrit par  Shalom Eliahou Voir les commentaires (9)

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 ko

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

Notes

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

Partager cet article

Pour citer cet article :

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

Crédits image :

Image à la une - L’auteur remercie Jason Davies, créateur du logo.

Commentaire sur l'article

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

    le 16 novembre 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 novembre 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 novembre 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 novembre 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 novembre 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 novembre 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 décembre 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 16 novembre 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 novembre 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

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM