Cet article est le dernier volet d’une série consacrée au problème $3n+1$. Les deux premiers volets sont [1] sur piste verte et [2] sur piste bleue.

Rappelons la définition de la transformation de Collatz : 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$ 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, \ldots$, qui est donc un cycle de longueur 3, appelé le cycle trivial.

Le problème de Collatz consiste à déterminer s’il est vrai que la trajectoire de tout entier strictement positif $n$ de départ atteint $1$. Cette prédiction a été vérifiée sur ordinateur jusqu’à $5 \times 10^{18}$ par Tomás Oliveira e Silva en 2009 [3].

Le logo [4] représente toutes les trajectoires atteignant $1$ en au plus 18 étapes. Une image de celui-ci, qu’on peut agrandir un peu, se trouve dans le volet vert.

Rappelons enfin qu’une liste commentée de tous les articles publiés sur ce problème est maintenue par Jeff Lagarias [5], qui vient aussi de publier un livre très complet sur le sujet : The Ultimate Challenge : The $3x+1$ Problem [6].

Cycles de Collatz

Par commodité, appelons cycle de Collatz toute trajectoire cyclique de la transformation de Collatz sur les nombres entiers relatifs. On en connaît cinq à ce jour :

• la trajectoire de $1$, cycle trivial de longueur 3 ;

• celle de $0$, de longueur 1 ;

• celle de $-1$, de longueur 2 ;

• celle de $-5$, de longueur 5 ;

• celle de $-17$ enfin, de longueur 18.

On conjecture qu’il n’y en a pas d’autres. Un sous-problème du problème de Collatz consiste à déterminer s’il est vrai que le seul cycle de Collatz dans les entiers strictement positifs est le cycle trivial.

Dans le volet bleu de cette série, on a prouvé l’inexistence de cycles de Collatz de longueur 5 dans les entiers positifs. Dans une première partie du présent article, sur piste bleue aussi, on va exclure l’existence de tels cycles en longueur 18. Puis, en s’aventurant sur piste rouge avec des logarithmes, le langage commode des intervalles, et quelques concepts d’approximation rationnelle, on exclura bien d’autres longueurs : toutes celles comprises entre 4 et 17.026.679.260, très précisément.

Deux ingrédients de preuve

Notre preuve d’exclusion de la longueur 5 pour les cycles de Collatz dans les entiers positifs, donnée dans le volet bleu, est constituée de deux ingrédients principaux :

• d’une part, la stabilité du cycle présumé sous l’action de la transformation de Collatz ;

• d’autre part, une équation très contraignante associée à ce cycle.

Pour exclure de plus grandes longueurs de cycles, le premier ingrédient se généralise facilement, comme on le verra.

Par contre, le second avait découlé d’une description précise de la répartition des pairs et des impairs dans le cycle. Or il est illusoire d’espérer obtenir une telle description en longueur supérieure, pour des raisons d’explosion combinatoire. Comment surmonter cet obstacle, alors ? Grâce à un petit saut dans l’abstraction, en acceptant d’introduire une notation spécifique distinguant les pairs des impairs dans le cycle présumé.

Notations pour un cycle

Voici ces notations, qu’on utilisera dans toute la suite de l’article. On considère un hypothétique cycle de Collatz $C$ dans les entiers positifs. On notera $N$ sa longueur et $a_1, a_2, \ldots,a_N$ la liste de ses éléments distincts deux à deux, dans leur ordre d’apparition sur la trajectoire de $a_1$ :
\[ a_1 \rightarrow a_2 \rightarrow \ldots \rightarrow a_N \rightarrow a_1. \]
On notera aussi :

• $p$ le nombre d’éléments pairs de $C$ ;

• $q$ le nombre de ses éléments impairs.

On ignore tout a priori de $p$ et $q$, si ce n’est qu’ils satisfont l’égalité
\[ p + q \, = \, N. \]
Poursuivant sur notre lancée, on notera
\[ b_1,\ldots,b_p \]
la liste des éléments pairs de $C$, et
\[ c_1,\ldots,c_q \]
celle de ses éléments impairs.

Enfin, le plus petit élément de $C$ jouera un rôle particulier. On le notera $m$. Ce nombre est forcément impair [7].

Nous allons maintenant, dans ce cadre plus général, revisiter nos deux ingrédients de preuve.

Stabilité par transformation de Collatz

Premier ingrédient : si l’on applique la transformation de Collatz à la liste des éléments du cycle $C$, on retombe sur cette même liste, à l’ordre près.

En effet, en appliquant la transformation de Collatz aux éléments
\[ a_1, a_2, \ldots, a_{N-1},a_N \]
de $C$, dans leur ordre d’apparition sur la trajectoire de $a_1$, on obtient la liste
\[ a_2,a_3, \ldots, a_N, a_1. \]
C’est toujours la liste d’origine, juste décalée cycliquement d’un cran. Le cycle $C$ est donc bien stable par transformation de Collatz [8].

Pairs et impairs

Passons maintenant au second ingrédient de preuve, à savoir l’équation associée au cycle $C$. On ignore comment se répartissent les pairs $b_1,\ldots,b_p$ et les impairs $c_1,\ldots,c_q$ dans $C$. Mais évidemment, en les agrégeant, la liste
\[b_1, \ldots, b_p, c_1, \ldots, c_q\]
obtenue n’est rien d’autre qu’un réarrangement de la liste des éléments de $C$. Or, comme on l’a vu, celle-ci est globalement stable par transformation de Collatz. De plus, on sait exactement ce que donne cette transformation sur les $b_i$ et les $c_j$, puisqu’on connaît leur parité ! Faisons-le donc. En appliquant la transformation de Collatz à la liste
\[b_1, \ldots, b_p, c_1, \ldots, c_q,\]
on obtient la liste
\[\frac{b_1}2, \ldots, \frac{b_p}2, 3c_1+1, \ldots, 3c_q+1,\]
et ces deux listes contiennent exactement les mêmes éléments à l’ordre près, à savoir ceux de $C$.

L’équation associée au cycle $C$

En particulier, comme dans le volet bleu, prenons le produit $P$ des termes de $C$. En utilisant chacune des deux listes ci-dessus représentant $C$, on obtient à nouveau deux expressions différentes de $P$ :
\[ P \, = \, b_1 \cdots b_p c_1 \cdots c_q \]
d’une part, et
\[ P \, = \, \frac{b_1}2 \cdots \frac{b_p}2 (3c_1+1) \cdots (3c_q+1) \]
d’autre part. De cette double expression de $P$, on déduit aussitôt l’équation suivante associée à $C$, dans sa version brute :
\[ b_1 \cdots b_p c_1 \cdots c_q \, = \, \frac{b_1}2 \cdots \frac{b_p}2 (3c_1+1) \cdots (3c_q+1). \]
Quelques manipulations algébriques, exactement comme celles faites dans le volet bleu en longueur $N=5$, permettent de réécrire cette équation sous sa forme épurée [9].

Cas particuliers

Pour $N=3$, on a le cycle trivial $1 \rightarrow 4 \rightarrow 2 \rightarrow 1$. On voit que $p=2$ et $q=1$, la liste des impairs $c_1,\ldots,c_q$ se réduisant à $c_1=1$. Il est alors bien vrai que
\[ 2^2 \, =\, \left(3+\frac{1}{1}\right). \]

Pour $N=5$, en supposant que le minimum du cycle est $a_1$, on avait trouvé trois pairs ($a_2$, $a_4$ et $a_5$) et deux impairs ($a_1$ et $a_3$), donnant donc $p=3$ et $q=2$. On retrouve bien l’équation
\[ 8 \, = \, \left(3+\frac1{a_1}\right) \left(3+\frac1{a_3}\right) \]
avec laquelle on avait exclu les cycles de Collatz de longueur 5 dans les entiers positifs.

Une comparaison

On a établi deux fois l’équation associée à un cycle. Une première fois dans le volet bleu pour la longueur 5, puis ici en général. Que le lecteur s’amuse à comparer les deux preuves, tant cela peut servir de paradigme illustrant pourquoi les mathématiques raffolent d’abstraction !

Pour la longueur 5, la seule notation $a_1,\ldots,a_5$ des éléments du cycle présumé avait bien permis, mais au prix de quelque effort, d’analyser la situation et d’établir l’équation.

Par contre ici, on a accepté de considérer un cycle $a_1, \ldots, a_N$ de longueur $N$ non spécifiée, avec des nombres inconnus $p$ de pairs et $q$ d’impairs, et d’introduire une notation en $b_i$ et $c_j$ pour les distinguer dans le cycle. C’est assurément plus abstrait qu’en longueur 5. Mais cela a permis, finalement, d’obtenir l’équation annoncée de façon à la fois plus simple et plus générale.

Tels sont souvent, en quelque sorte, les termes du marché en mathématiques : au prix d’un peu d’abstraction supplémentaire, on gagne en puissance et on acquiert les moyens de pousser l’analyse plus loin.

Un encadrement de $2^p$

Montrons maintenant que l’équation en question fournit un encadrement de $2^p$ très contraignant. Rappelons qu’on note $c_1,\ldots,c_q$ les éléments impairs de $C$ et $m$ son minimum. On a donc
\[ c_i \, \ge \, m \]
pour tout indice $i$ entre $1$ et $q$. En inversant, puis en ajoutant $3$, on obtient
\[ 3 \, < \, 3 + \frac{1}{c_i} \, \leq\, 3 + \frac{1}{m} \]
pour tout $i$, sachant que les $c_i$ sont strictement positifs. En prenant le produit de ces $q$ termes, on obtient les inégalités suivantes :
\[ 3^q \, <\, \left(3+\frac{1}{c_1}\right) \cdots \left(3+\frac{1}{c_q}\right) \, \leq \, \left(3+\frac{1}{m}\right)^q. \]
Maintenant, par l’équation associée au cycle, le terme du milieu est égal à $2^p$. On obtient donc l’encadrement suivant :
\[ 3^q \, < 2^p \, \leq \, \left(3+\frac{1}{m}\right)^q. \]
Résumons formellement ce que l’on vient d’obtenir.

Voici pourquoi on pourra tirer des informations de cet encadrement : plus le minimum $m$ de $C$ est grand, plus son inverse $1/m$ est petit, et plus il sera difficile de trouver une puissance de $2$ coincée entre des puissances de $3$ et de $3+1/m$ avec un exposant commun $q$. On va voir que cela suffit déjà pour exclure la longueur 18.

En longueur 18

On sait que la trajectoire de $-17$ est un cycle de Collatz de longueur 18 dans les entiers négatifs. Montrons qu’au contraire, il n’existe pas de cycle de Collatz $C$ de cette longueur dans les entiers positifs. Les symboles $p$, $q$ et $m$ ci-dessus sont compris relativement à cet hypothétique cycle $C$. En particulier, le minimum $m$ de $C$ est strictement plus grand que 1, puisque la trajectoire de $1$ est un cycle de longueur 3 et non pas 18.

Comme $p+q=18$, on a $p=18-q$, et l’encadrement de $2^p$ ci-dessus devient :
\[ 3^q \, < \, 2^{18-q} \, \leq \, \left(3+\frac{1}{m}\right)^q. \]
Puisque $m > 1$, il suit que $\left(3+\frac{1}{m}\right) < 4$. Le terme de droite ci-dessus est donc dominé par $4^q$. On obtient ainsi les inégalités strictes
\[ 3^q \, < \, 2^{18-q} \, < \, 4^q. \]
Quelles sont les valeurs de $q$ satisfaisant ces deux inégalités ?

• Si $q$ est trop grand, alors $3^q$ dépassera $2^{18-q}$ et $q$ ne conviendra pas.

• De même, si $q$ est trop petit, alors $18-q$ sera trop grand et $2^{18-q}$ dépassera $4^q$ ; donc $q$ ne conviendra pas non plus.

Concrétisons ces observations avec une calculette. On trouve
$3^7=2187$ et $2^{11}=2048$, donnant l’inégalité
\[ 3^7 \, >\, 2^{11}. \]
Donc les valeurs de $q$ supérieures ou égales à 7 sont interdites. Dans l’autre sens, on a
\[ 2^{13} \, >\, 4^5, \]
puisque $4^5\,=\, 2^{10}$. Les valeurs de $q$ inférieures ou égales à 5 sont donc interdites également.

Reste une unique valeur permise, à savoir $q\,=\,6$, ce qui donne $18-q\,=\,12$. Or on a
\[ 2^{12} \, = \, 4^{6}, \]
en contradiction avec l’inégalité stricte $2^{18-q}\, <\, 4^q$ requise plus haut.

Conclusion : il n’existe aucun cycle de Collatz de longueur 18 dans les entiers positifs.

Entrée douce sur piste rouge

On peut — et on va — aller au delà de l’exclusion de la longueur 18. Mais pour y arriver, on a besoin d’outils nous permettant de mieux exploiter la force de l’encadrement de $2^p$ obtenu plus haut. L’idée est de faire « descendre » $p$ et $q$ qui s’y trouvent en exposants, afin de les manipuler plus aisément. Or les mathématiques ont un outil tout indiqué pour cela : les logarithmes.

Logarithmes

Notons simplement $\log$ la fonction logarithme en base 10 [10]. Que le lecteur peu à l’aise avec elle ne lâche pas prise à cet endroit ! Car, au début tout au moins, on utilisera cette fonction surtout comme une boîte noire, dotée des propriétés suivantes :

• $\log$ respecte l’ordre : si $x\, <\, y$, alors $\log(x)\, <\, \log(y)$ ;

• $\log$ permet de « descendre » les exposants : $\log(x^r)\, =\, r \log(x)$.

Cette seconde propriété se voit très bien sur ces valeurs de base : $\log(10) = 1$, $\log(100) = 2$, $\log(1000) = 3$, et plus généralement,
\[ \log(10^r) \, = \, r \log(10) \, = \, r. \]
Cela découle du fait que $\log$, à l’inverse de l’exponentielle, transforme produits en sommes [11] :
\[ \log(xy) \, = \, \log(x)+\log(y). \]

Enfin, une troisième propriété du logarithme intervenant ici est sa continuité : si $x$ et $y$ sont très proches, alors $\log(x)$ et $\log(y)$ le sont aussi, dans un sens pouvant être quantifié de façon précise. On indiquera à quel endroit cette propriété se manifeste.

Un encadrement de $p/q$

On va pouvoir déduire, grâce aux logarithmes, un encadrement de $p/q$ à partir de celui de $2^p$ obtenu auparavant. Rappelons que pour un cycle de longueur $N=p+q$, avec $p$ pairs, $q$ impairs et de minimum $m$, on a forcément :
\[ 3^q \, < 2^p \, \leq \, \left(3+\frac{1}{m}\right)^q. \]
Appliquons le logarithme à ces termes. Comme $\log$ respecte l’ordre, on obtient
\[ \log\left(3^q\right) \, <\, \log\left(2^p\right) \, \leq \, \log\left(\left(3+\frac{1}{m}\right)^q\right). \]
Descendons les exposants, puisque $\log$ permet de le faire :
\[ q \log\left(3\right) \, <\, p\log\left(2\right) \, \leq \, q\log\left(3+\frac{1}{m}\right). \]
Divisons ces termes par $q$. Cela donne
\[ \log\left(3\right) \, <\, \frac pq \log\left(2\right) \, \leq \, \log\left(3+\frac{1}{m}\right). \]
Enfin, divisant le tout par $\log(2)$, on obtient le résultat suivant.

Encore une fois, plus $m$ est grand, plus $1/m$ est petit et, par continuité, plus $\log(3+1/m)$ est proche de $\log(3)$. Autrement dit, le rapport $p/q$ se retrouve coincé entre deux nombres d’autant plus proches que $m$ est grand. Ces contraintes vont se révéler très fortes.

Où la borne $5\times 10^{18}$ intervient

Pour un hypothétique cycle de Collatz non trivial $C$ dans les entiers positifs, de minimum $m$, on a forcément
\[ m \, > \, 5\times 10^{18}.\]

Cela découle de la vérification du problème $3n+1$ sur ordinateur par Tomás Oliveira e Silva jusqu’à cette borne : pour tout entier $n$ inférieur à $5\times 10^{18}$, sa trajectoire finit par atteindre 1. Celle-ci ne peut donc constituer un cycle autre que le cycle trivial de longueur 3. On en déduit ce qui suit.

En effet, notant toujours $m$ le minimum de $C$, on a $m > 5\times 10^{18}$. En prenant les inverses, l’ordre s’inverse, ce qui donne
\[ \frac1m \, <\, \frac{1}{5\times 10^{18}}, \]
ou encore, comme $1/5 \,=\,0,2\,=\,2 \times 10^{-1}$,
\[ \frac1m \, < 2 \, \times 10^{-19}. \]
Reste enfin, de chaque côté, à ajouter $3$ ; à prendre le logarithme, ce qui conserve l’ordre ; et à diviser par $\log(2)$. Cela donne l’inégalité :
\[ \frac{\log\left(3+\frac{1}{m}\right)}{\log(2)} \, < \, \frac{\log\left(3+2\times10^{-19}\right)}{\log(2)}. \]
Combinée à l’encadrement de $p/q$ obtenu plus haut, on obtient celui annoncé.

Intervalles

Cet encadrement de $p/q$ s’exprime très bien dans le langage des intervalles : il dit que $p/q$ appartient à l’intervalle ouvert suivant [12] :
\[ \frac pq \, \in \, \left]\frac{\log(3)}{\log(2)} \, , \, \frac{\log\left(3+2\times10^{-19}\right)}{\log(2)}\right[. \]
Concrètement, voici les 25 premières décimales de ces extrémités :
\[ \begin{array}{rcl} \log(3)/\log(2) & = & 1,584962500721156181\mathbf{4}537389, \\ \log(3+2\times 10^{-19})/\log(2) & = & 1,584962500721156181\mathbf{5}499186. \end{array} \]
Leur différence est minuscule [13] : elle ne se manifeste qu’à partir de la 19ème décimale, montrée en gras. En gommant les dernières décimales, on déduit ce qui suit.

Une conséquence drastique

Reprenons l’intervalle minuscule ci-dessus et désignons-le par $I$ :
\[ I \, = \, \left]1,584962500721156181\mathbf{4}5, \,\,1,584962500721156181\mathbf{5}5 \right[. \]
En quoi le fait de savoir que $p/q$ est contraint d’y habiter pourrait-il nous être utile ? Assez curieusement parce que, comme on le verra, toute fraction appartenant à $I$ est tenue d’avoir ses numérateur et dénominateur très grands, dans un sens tout à fait explicite. Concrètement, on verra que pour tout habitant rationnel $s/t$ de $I$, avec $s$ et $t$ entiers positifs, on a forcément
\[ \begin{array}{rcr} s & \ge & 10.439.860.591,\\ t & \ge & 6.586.818.670. \end{array} \]
En particulier, ces seuils s’appliqueront à $p$ et $q$ respectivement, puisque $p/q$ appartient à $I$. Il en découlera aussitôt que la longueur de notre présumé cycle $C$ doit dépasser la somme de ces seuils, à savoir $17.026.679.261$.

Entamons maintenant quelques préliminaires qui finiront par nous conduire à une preuve de ces affirmations.

Convention

A partir d’ici, on dira simplement « rationnel » pour « nombre rationnel » ou « fraction d’entiers ». Et en écrivant un rationnel sous forme de fraction $s/t$, on supposera implicitement que $s$ et $t$ sont entiers, avec $t\ge 1$ [14].

Rationnels économiques dans un intervalle

On est donc confrontés à la question suivante. Considérons un intervalle ouvert $J$ dans la droite des nombres réels, disons $J\, =\, ]x,y[$. Parmi tous les habitants rationnels $s/t$ de cet intervalle, autrement dit ceux satisfaisant
\[ x \, < \, s/t \, < \, y, \]
quel est le plus économique, c’est-à-dire celui avec numérateur et dénominateur minimaux ? Plus précisément, quel est le rationnel $a/b$ dans $J$ avec dénominateur $b \ge 1$ minimal et, ce $b$ étant fixé, avec numérateur $a$ minimal en valeur absolue ?

Par exemple, dans l’intervalle ouvert $]0,1[$, l’habitant rationnel le plus économique est $1/2$, bien sûr.

Comme second exemple, considérons l’intervalle ouvert $J=]2,3[$. Alors son habitant rationnel le plus économique est $5/2$. En effet, d’une part $5/2$ appartient à $J$, puisque
\[ 2 \, < \, \frac52 \, < \, 3. \]
D’autre part, montrons que pour tout rationnel $s/t$ dans $]2,3[$, on a $s\, \ge\, 5$ et $t\, \ge\, 2$. La borne $t\, \ge\, 2$ est évidente, puisque les rationnels avec dénominateur $1$ sont des nombres entiers, donc exclus de $J$ ! Pour établir $s\, \ge\, 5$, considérons au contraire un rationnel $r/t$ avec $t \ge 2$ mais $r \le 4$. Alors
\[ \frac rt \, \le \, 2, \]
et donc $r/t$ est exclu de $J$. Il suit bien que pour tout rationnel $s/t$ dans $J$, on a forcément $s \ge 5$ .

Heureusement, on dispose d’outils pour aborder ce problème de façon plus efficace et dans des intervalles bien plus corsés.

Un cas apparemment particulier

Ce problème du rationnel le plus économique est très ancien et appartient à la théorie des approximations rationnelles. Des solutions en ont été données au 17ème siècle par John Wallis (1616-1703) et par Christiaan Huygens (1629-1695), avec le concept de fractions continues [15]. La motivation de Huygens était très concrète : il lui fallait déterminer les bons nombres de dents pour chaque paire de roues dentées contiguës de son célèbre planétarium !

Notre approche ici repose sur la solution du problème dans un cas apparemment particulier, celui des intervalles de Farey. En fait on pourra tout faire avec.

Par exemple, l’intervalle $\left]\frac{7}{9},\frac{4}{5}\right[$ est de Farey, puisque
\[ 4 \times 9 - 7 \times 5 \,=\, 36-35 \,=\, 1. \]
De façon remarquable, pour ces intervalles, décrire l’habitant rationnel le plus économique est très facile. Voici comment, en mots d’abord.

Le rationnel le plus économique dans un intervalle de Farey est la somme des numérateurs de ses extrémités, divisée par la somme de leurs dénominateurs.

Puis traduit en formules.

Voici quelques exemples.

• L’intervalle $]0,1[\, =\, \left]\frac{0}{1},\frac{1}{1}\right[$ est de Farey, et son habitant rationnel le plus économique est effectivement $(0+1)/(1+1)$, c’est-à-dire $1/2$.

• Pour l’intervalle $]2,3[\,=\,\left]\frac{2}{1},\frac{3}{1}\right[$, qui est aussi de Farey, on retrouve bien notre observation précédente : son rationnel le plus économique est $5/2\, =\, (2+3)/(1+1)$.

• Enfin, pour l’intervalle de Farey $\left]\frac{7}{9},\frac{4}{5}\right[$ ci-dessus, la proposition affirme que son rationnel le plus économique est $11/14$.

Ce résultat, qui nous sera fort utile plus loin, découle d’un énoncé bien plus général décrivant carrément tous les habitants rationnels d’un intervalle de Farey.

Rationnels dans un intervalle de Farey

Commençons par un peu de terminologie maison. On dira d’un entier $s$ qu’il est un panachage de la paire d’entiers $(s_1,s_2)$ s’il est de la forme
\[s \, = \, a s_1 + b s_2,\]
où $a$ et $b$ sont deux nombres entiers strictement positifs. On appellera alors $a$ et $b$ les coefficients ou les doses du panachage.

Par exemple, 19 est un panachage de la paire (5,7), de coefficients 1 et 2, puisque une dose de 5 plus deux doses de 7 font bien 19.

Le résultat général dont nous aurons besoin, et qu’on appellera le théorème du panachage, dit ceci.

Pour un intervalle de Farey $J\, =\, \left]\frac{s_1}{t_1}, \; \frac{s_2}{t_2}\right[$, tout habitant rationnel $s/t$ de $J$ est de la forme suivante : son numérateur $s$ est un panachage de $(s_1,s_2)$, son dénominateur $t$ est un panachage de $(t_1,t_2)$, et les coefficients de ces deux panachages sont les mêmes. Et réciproquement, tout rationnel de cette forme habite dans $J$.

Voici le même énoncé, en formules.

Notons que ce résultat entraîne instantanément le précédent, selon lequel le rationnel le plus économique dans $J$ est $(s_1+s_2)/(t_1+t_2)$. En effet, le plus petit panachage possible de $(s_1,s_2)$ est l’entier $s_1+s_2$, c’est-à-dire avec doses égales à 1, et celui de $(t_1,t_2)$ avec ces mêmes doses est l’entier $t_1+t_2$.

Notons aussi que ce théorème se vérifie aisément pour l’intervalle de Farey particulier
\[ J_0 \, =\, ]0,1[ \, =\, \left]\frac{0}{1},\frac{1}{1}\right[. \]
En effet, les rationnels $s/t$ dans $]0,1[$ sont exactement ceux pour lesquels
\[ 1 \, \le \, s \, \le \, t-1. \]
Or tout entier $s\, \ge\, 1$ est un panachage de la paire $(0,1)$ avec coefficients $t-s$ et $s$, qui sont bien strictement positifs comme requis ; et tout entier $t\, \ge\, s+1$ est un panachage de $(1,1)$ avec ces mêmes coefficients, puisque
\[ \begin{array}{lcl} s & = & (t-s)\times 0 \, +\, s \times 1, \\ t & = & (t-s)\times 1 \, +\, s \times 1. \end{array} \]
Le théorème est donc bien vrai pour l’intervalle $]0,1[$. La preuve dans le cas général, donnée ci-dessous, consiste à se ramener à ce cas particulier, grâce à un dictionnaire parfait entre les rationnels de $]0,1[$ et ceux de $]s_1/t_1, s_2/t_2[$.

Preuve du théorème du panachage

Nous allons décrire ce dictionnaire parfait [16] par formules explicites. En fait, on va le faire au niveau des intervalles fermés :

• à tout rationnel $z$ dans $[0,1]$, on associera un rationnel dénoté $f(z)$ et appartenant à $\left[\frac{s_1}{t_1}, \; \frac{s_2}{t_2}\right]$ ;

• à tout rationnel $z'$ dans $\left[\frac{s_1}{t_1}, \; \frac{s_2}{t_2}\right]$, on associera un rationnel dénoté $g(z')$ et appartenant à $[0,1]$.

Voici les formules, un peu compliquées de prime abord, décrivant $f$ et $g$. Pour tout rationnel $c/d$ dans $[0,1]$, on définit
\[ f\left(\frac{c}{d}\right) \, = \, \frac{(s_2-s_1)\times c \,+\, s_1 \times d}{(t_2-t_1)\times c \,+\, t_1 \times d} ; \]
et pour tout rationnel $c'/d'$ dans $\left[\frac{s_1}{t_1}, \; \frac{s_2}{t_2}\right]$, on définit
\[ g\left(\frac{c'}{d'}\right) \, = \, \frac{t_1\times c' \,-\, s_1 \times d'}{(t_1-t_2)\times c' \,+\, (s_2-s_1) \times d'}. \]

Pour montrer que ces deux associations constituent un dictionnaire parfait entre les rationnels de l’intervalle ouvert $]0,1[$ et ceux de $J$, il suffit de vérifier les huit propriétés suivantes ; les quatre ci-dessous, plus les quatre autres obtenues en interchangeant partout $f$ avec $g$ et $[0,1]$ avec $\left[\frac{s_1}{t_1}, \; \frac{s_2}{t_2}\right]$ :

• $f$ envoie les extrémités de $[0,1]$ sur celles de $\left[\frac{s_1}{t_1}, \; \frac{s_2}{t_2}\right]$.

• $f$ respecte l’ordre : si $z_1$, $z_2$ sont rationnels et $z_1\, <\, z_2$, alors $f(z_1)\, <\, f(z_2)$.

• $f$ préserve les panachages, dans le sens que si l’on part d’un rationnel $z$ dans $[0,1]$ dont les numérateur et dénominateur
  sont des panachages d’une même paire avec mêmes doses, alors il en est de même pour $f(z)$.

• $f$ et $g$ sont inverses l’une de l’autre : si l’on part d’un rationnel $z$ dans $[0,1]$, qu’on lui applique $f$, puis qu’on applique $g$ au résultat, alors on retombe sur $z$. Autrement dit, $g(f(z)) = z$.

Comment vérifier ces propriétés ? On l’indique brièvement ci-dessous. Mais on peut déjà conclure que ce dictionnaire parfait prouve le théorème du panachage en toute généralité.

Vérification directe ... ou conceptuelle

Le lecteur patient saura prouver les propriétés ci-dessus par calcul direct. Mais celui connaissant un peu les matrices et les homographies pourra aussi le faire de façon plus conceptuelle. En effet, $f$ et $g$ sont essentiellement des homographies relativement aux matrices
\[ A = \left( \begin{array}{cc} s_2-s_1 & s_1 \\ t_2-t_1 & t_1 \end{array} \right) \quad \textrm{ et } \quad B = \left( \begin{array}{cc} t_1 & -s_1 \\ t_1-t_2 & s_2-s_1 \end{array} \right). \]
Ces matrices sont de déterminant 1 : cela découle directement de l’hypothèse que $J$ est un intervalle de Farey. De plus, elles sont inverses l’une de l’autre ; c’est grâce à cela que $f$ et $g$ sont des fonctions inverses l’une de l’autre [17].

Application au problème $3n+1$

Considérons un hypothétique cycle de Collatz non trivial $C$ dans les entiers positifs, avec $p$ pairs et $q$ impairs. On a vu plus haut qu’alors, ${p}/{q}$ appartient à l’intervalle ouvert

\[ I \, = \, \left]1,584962500721156181\mathbf{4}5, \,\,1,584962500721156181\mathbf{5}5 \right[. \]

Cet intervalle n’est sûrement pas de Farey. Quel est donc son habitant rationnel le plus économique ? Voici tout de suite la réponse :

Le rationnel le plus économique dans $I$ est
\[\frac{10.439.860.591}{6.586.818.670}.\]

Comment peut-on l’affirmer, puisque la théorie présentée plus haut ne décrit les rationnels économiques que dans les intervalles de Farey ?

Eh bien, l’astuce consiste à construire deux intervalles de Farey contigus englobant $I$, c’est-à-dire contenant chacun une extrémité de $I$.

Voici ces deux intervalles contigus, avec l’extrémité respective de $I$ qui s’y trouve :

\[ \begin{array}{ccc} 1,584962500721156181\mathbf{4}5 & \in & \left]\frac{9.809.721.694}{6.189.245.291}, \, \frac{10.439.860.591}{6.586.818.670} \right[, \\ \\ 1,584962500721156181\mathbf{5}5 & \in & \left]\frac{10.439.860.591}{6.586.818.670}, \, \frac{630.138.897}{397.573.379} \right[. \end{array} \]

Un bon logiciel de calcul suffit pour constater que ces deux intervalles sont bien de Farey, et qu’ils contiennent les extrémités indiquées [18].

Or, on connaît le rationnel le plus économique dans chacun de ces deux intervalles de Farey : c’est la somme des numérateurs des extrémités, divisée par la somme de leurs dénominateurs [19]. Mais visiblement, ces deux rationnels-là sont bien moins économiques que l’extrémité commune des deux intervalles, à savoir
\[\frac{10.439.860.591}{6.586.818.670}.\]
C’est donc lui, le rationnel le plus économique strictement compris entre l’extrémité gauche du premier intervalle et l’extrémité droite du second. Et par conséquent, le plus économique dans $I$.

En particulier, tout habitant rationnel $s/t$ de $I$ satisfait
\[ \begin{array}{rcr} s & \ge & 10.439.860.591,\\ t & \ge & 6.586.818.670. \end{array} \]
Ces bornes respectives valent donc pour $p$ et $q$, puisque $p/q$ habite dans $I$. On vient de démontrer le résultat suivant.

S’il existe un cycle de Collatz non trivial dans les entiers positifs, de longueur $N$, avec $p$ pairs et $q$ impairs, alors $p\, \ge\, 10.439.860.591$, $q\, \ge\, 6.586.818.670$, et donc $N \, \ge\, 17.026.679.261.$

En particulier, s’il y avait un cycle de longueur exactement 17.026.679.261, ce que personne ne sait encore exclure, alors il contiendrait exactement 10.439.860.591 pairs et 6.586.818.670 impairs. C’est rigide ! Et ça rappelle le cas de longueur 18, où la seule répartition possible était 12 pairs et 6 impairs.

En longueur 18 milliards

Personne, disions-nous, ne sait encore exclure la longueur 17.026.679.261. Par contre, on en sait assez pour exclure la longueur 18 milliards pile. En effet, supposons qu’il existe un cycle de Collatz dans les entiers positifs de longueur $N=p+q$ strictement supérieure à 17.026.679.261.

Alors $p/q$ devrait habiter dans l’un des deux intervalles de Farey contigus ci-dessus, puisqu’ici il doit différer de leur extrémité commune $\frac{10.439.860.591}{6.586.818.670}$. Or, pour le rationnel $s/t$ le plus économique du deuxième intervalle, on voit que
\[ \begin{array}{lcl} s + t & = & (10.439.860.591+630.138.897)\,+\, (6.586.818.670+397.573.379) \\ & = & 18.054.391.537, \end{array} \]
ce qui dépasse légèrement 18 milliards. Quant à la valeur de $s+t$ correspondante pour le premier intervalle de Farey, elle est de l’ordre de 33 milliards.

On a donc obtenu l’inégalité suivante :
\[ p+q \, \ge \, 18.054.391.537. \]
Ce qui exclut, parmi bien d’autres, la longueur 18.000.000.000.

Intervalles de Farey contigus

« Très bien », dira peut-être le lecteur pas encore épuisé. « Mais comment construire de tels intervalles de Farey contigus ? »

On peut lui donner deux réponses, l’une assez opaque et l’autre totalement transparente.

La première dirait : en prenant des convergentes secondaires successives d’une fraction continue. Bon.

Mais voici plutôt la seconde.

En coupant n’importe quel intervalle de Farey là où se situe son rationnel le plus économique, les deux morceaux contigus résultants forment chacun un intervalle de Farey !

Pour le redire en formules, partons d’un intervalle de Farey
\[ J\, =\, \left]\frac{s_1}{t_1}, \; \frac{s_2}{t_2}\right[. \]
Appelons médian son rationnel le plus économique, à savoir la fraction $(s_1+s_2)/(t_1+t_2)$. Alors les intervalles obtenus en coupant $J$ en son médian, c’est-à-dire
\[ J_1\, =\, \left]\frac{s_1}{t_1}, \; \frac{s_1+s_2}{t_1 + t_2}\right[ \quad \textrm{ et } \quad J_2\, =\, \left]\frac{s_1+s_2}{t_1 + t_2}, \; \frac{s_2}{t_2}\right[, \]
sont évidemment contigus et ils sont tous deux de Farey. La vérification se fait par un calcul direct instantané.

Reprenons maintenant notre minuscule intervalle $I$ défini plus haut [20]. Partons d’un intervalle de Farey $J$ contenant $I$, par exemple $J=]1,2[$. Coupons $J$ en son médian. Si ce médian tombe en dehors de $I$, alors l’un des deux intervalles de Farey résultant contient encore $I$. Dans ce cas, on remplace $J$ par ce sous-intervalle et on recommence. Au bout d’un nombre fini de telles étapes, il arrivera au contraire que le médian de $J$ tombe dans $I$. Il en résulte deux intervalles de Farey contigus englobant $I$, et on a fini.

C’est précisément en suivant cette procédure que l’on a construit la jolie paire d’intervalles de Farey contigus, englobant $I$, de laquelle on a déduit plus haut nos bornes inférieures pour $p$, $q$ et $N$.

Conclusion

On a montré que tout hypothétique cycle de Collatz non trivial $C$ dans les entiers positifs doit contenir au moins 17 milliards d’éléments, s’il existe. Cela ne répond pas, hélas, à la question du titre de cet article. Mais c’est déjà ça, en attendant mieux.

Et un léger mieux viendra peut-être bientôt. En effet, cette borne de 17 milliards repose sur la vérification actuelle du problème $3n+1$ jusqu’à $5 \times 10^{18}$. Lorsque la vérification future du problème atteindra $2,17 \times 10^{20}$, dans quelques années sans doute, alors notre borne inférieure sur les longueurs de cycles sautera de 17 milliards à ... 186 milliards, d’un seul coup [21] ! À part une bonne calculette, tous les ingrédients théoriques et numériques nécessaires pour s’en convaincre se trouvent dans cet article. Qui est partant pour le vérifier ?