Le problème 3n+1 : cycles de longueur 5 (II)
Piste bleue Le 16 novembre 2011 Voir les commentaires (12)Lire l'article 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 :
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
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.
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.
Notes
[2] Par 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
Laisser un commentaire
Articles suggérés
Si vous avez aimé cet article, voici quelques suggestions automatiques qui pourraient vous intéresser :
-
le 13 novembre 2011Parmi tous les problèmes mathématiques actuellement non résolus, quel est celui dont l’énoncé est le plus élémentaire ? C’est peut-être bien le problème présenté...lire l'article -
-
le 23 avril 2020La conjecture de Hadamard postule l’existence de matrices de Hadamard de tout ordre n multiple de 4. Ouverte depuis 1893, elle est étroitement liée au problème fondamental de la maximisation...lire l'article
Actualités des maths
-
5 mars 2023Maths en scène : Printemps des mathématiques (3-31 mars)
-
6 février 2023Journées nationales de l’APMEP, appel à ateliers (9/4)
-
20 janvier 2023Le vote électronique - les défis du secret et de la transparence (Nancy, 26/1)
-
17 novembre 2022Du café aux mathématiques : conférence de Hugo Duminil-Copin (Nancy et streaming, 24/11)
-
16 septembre 2022Modélisation et simulation numérique d’instruments de musique (Nancy & streaming, 22/9)
-
11 mai 2022Printemps des cimetières
Commentaire sur l'article
Le problème 3n+1 : cycles de longueur 5 (II)
le 16 novembre 2011 à 11:17, par Bruno Duchesne
Le problème 3n+1 : cycles de longueur 5 (II)
le 16 novembre 2011 à 14:20, par Gilles Bonnet
Le problème 3n+1 : cycles de longueur 5 (II)
le 17 novembre 2011 à 09:49, par Shalom Eliahou
Le problème 3n+1 : cycles de longueur 5 (II)
le 16 novembre 2011 à 18:15, par Pierre de la Harpe
Le problème 3n+1 : cycles de longueur 5 (II)
le 17 novembre 2011 à 18:18, par Thomas Boulier
Le problème 3n+1 : cycles de longueur 5 (II)
le 18 novembre 2011 à 09:22, par Shalom Eliahou
Le problème 3n+1 : cycles de longueur 5 (II)
le 8 décembre 2011 à 18:35, par Hervé
Le problème 3n+1 : cycles de longueur 5 (II)
le 25 mai 2020 à 15:40, par pierre simonnet
Le problème 3n+1 : cycles de longueur 5 (II)
le 16 novembre 2011 à 20:55, par Dimitri Karpov
Le problème 3n+1 : cycles de longueur 5 (II)
le 22 novembre 2011 à 22:46, par Nils Berglund
Le problème 3n+1 : cycles de longueur 5 (II)
le 29 mars 2018 à 14:50, par ROUAK
Le problème 3n+1 : cycles de longueur 5 (II)
le 18 juillet 2020 à 15:30, par CAMI