<figure><img src="image_1.png" /></figure>

HAL
open science

# Une démonstration symbolique de la décroissance des itérations de Collatz pour les entiers extrêmes

Fouad Bouyahbar

► To cite this version:

Fouad Bouyahbar. Une démonstration symbolique de la décroissance des itérations de Collatz pour les entiers extrêmes. 2025. hal-04927088

HAL Id: hal-04927088

https://hal.science/hal-04927088v1

Preprint submitted on 3 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
## Summary

This article presents a novel symbolic and probabilistic approach to the Collatz conjecture using a unique representation of integers as words over the alphabet {$I, P$}, where the operation $I$ corresponds to $x \mapsto 2x + 1$ and $P$ to $x \mapsto 2x$. Under our chosen convention, applying $I$ repeatedly from the starting point (taken as 0) yields the "extreme" numbers of the form

$$N_0 = 2^n - 1.$$

We introduce a logarithmic "weight" function defined by

$$W(N) = \log_2(N + 1),$$

so that for these extreme numbers $W(2^n - 1) = n$. Analyzing the Collatz iteration

$$T(N) = \frac{3N + 1}{2^{\nu_2(3N+1)}}$$

we show that its effect on the weight is approximately given by

$$\Delta W \approx \log_2 3 - \nu_2(3N + 1).$$

During the initial phase, the orbit of $N_0$ experiences maximal growth (reaching roughly $3^n - 1$) since the divisions by 2 are minimal (typically $d = 1$). However, over a sufficiently long sequence of iterations, stronger divisions occur — i.e., the 2-adic valuations $d_j = \nu_2(3N_{j-1} + 1)$ become larger. A probabilistic model assuming that these $d_j$ follow a geometric distribution with mean 2 (which exceeds $\log_2 3 \approx 1.585$) allows us to apply the strong law of large numbers. Consequently, for large $m$ and for extreme numbers with $n$ above a certain threshold (for example, $n \ge 20$), we obtain

$$\frac{1}{m} \sum_{j=1}^{m} d_j > \log_2 3.$$

This inequality implies that the cumulative effect of the divisions dominates the initial multiplicative growth, leading to

$$W(T^m(N_0)) < W(N_0),$$

and therefore

$$T^m(N_0) < N_0.$$

By induction, this strict decrease shows that every trajectory eventually descends into a bounded region, ultimately converging to the trivial cycle containing 1. For smaller numbers, numerical verification confirms the convergence.

In summary, the article rigorously demonstrates that, even starting from the worst-case scenario of an extreme number $2^n - 1$, the eventual dominance of the division operations guarantees a net decrease in the weight of the number, thereby supporting the non-divergence (and eventual convergence) of all Collatz orbits.
# Une démonstration symbolique de la décroissance des itérations de Collatz pour les entiers extrêmes

## Résumé.

Nous proposons une approche combinatoire et symbolique de la dynamique du problème de Collatz en introduisant une représentation unique des entiers sous forme de mots sur l'alphabet $\{I, P\}$, où l'opération $I$ correspond à $x \mapsto 2x + 1$ et $P$ à $x \mapsto 2x$. En partant de 0 ou, de façon équivalente, en adoptant la convention que l'entier extrême associé à $n$ applications de $I$ est

$$N_0 = 2^n - 1,$$

nous montrons que, pour ces entiers « extrêmes », l'envol est maximal – aboutissant à une valeur approximative $3^n - 1$ lors des premières itérations – mais que, sur une suite suffisamment longue d'itérations, la phase de divisions par 2 (évaluée via la valuation $v_2(3N + 1)$) induit une décroissance nette du « poids » de l'entier. En effet, en définissant le poids par

$$W(N) = \log_2(N + 1),$$

on démontre que le gain moyen par itération est approximativement

$$\Delta W \approx \log_2 3 - v_2(3N + 1).$$

Une modélisation probabiliste (basée sur une loi géométrique) et l'application de la loi forte des grands nombres montrent que la moyenne cumulative des valuations $d_j = v_2(3N_{j-1} + 1)$ tend vers 2, ce qui dépasse $\log_2 3 \approx 1,585$. Pour des $n$ supérieurs à un certain seuil (par exemple, $n \ge 20$), on obtient ainsi

$$T^m(N_0) < N_0,$$

c'est-à-dire une décroissance stricte par rapport au nombre extrême initial. Par récurrence, cela garantit que toute trajectoire de Collatz finit par descendre vers le cycle trivial contenant 1.

## 1. Introduction

La conjecture de Collatz, aussi connue sous le nom de problème $3x + 1$, consiste à montrer que pour tout entier positif $N$, la suite définie par

$$N_{k+1} = \begin{cases} \frac{N_k}{2} & \text{si } N_k \text{ est pair,} \\ 3N_k + 1 & \text{si } N_k \text{ est impair,} \end{cases}$$

converge vers le cycle $1 \to 4 \to 2 \to 1$. Malgré des investigations intensives, une démonstration rigoureuse de cette conjecture reste ouverte.
Dans cet article, nous adoptons une approche symbolique basée sur une écriture unique des entiers sous forme de mots sur un alphabet binaire $\{I, P\}$. Cette méthode permet de distinguer clairement deux phases dans la dynamique de Collatz : une phase d'« envol » maximal, obtenue dans le pire des cas, suivie d'une phase de décroissance dans laquelle les divisions par 2 compensent l'effet multiplicatif par 3. Nous détaillons ci-après les étapes de la démonstration et donnons une borne asymptotique pour laquelle l'argument devient rigoureux (par exemple pour $n \ge 20$); les entiers plus faibles pouvant être traités par vérification numérique.

Nous pouvons formuler l'idée de la démonstration par la construction de « nombres critiques » issus d'une itération « impaire » maximale, c'est-à-dire par la suite de transformations qui, partant de 1 et en appliquant successivement l'opération de la forme

$$x \mapsto 2x + 1,$$

conduit aux entiers

$$x_0 = 1, \quad x_1 = 2 \cdot 1 + 1 = 3, \quad x_2 = 2 \cdot 3 + 1 = 7, \quad \dots, \quad x_n = 2^n - 1.$$

Ces nombres, entièrement construits à partir d'additions de 1 sur des multiples de 2, sont impairs et représentent des cas « extrêmes » du comportement de l'itération de Collatz. En effet, lorsqu'un entier impair $x$ est soumis à l'opération « Collatz » classique, on applique

$$f(x) = \frac{3x + 1}{2^{v_2(3x+1)}}$$

où $v_2(3x + 1)$ désigne la valuation 2 de $3x + 1$.

Pour ces $x_n = 2^n - 1$, on constate que

$$3(2^n - 1) + 1 = 3 \cdot 2^n - 2 = 2(3 \cdot 2^{n-1} - 1),$$

et puisque $3 \cdot 2^{n-1} - 1$ est impair (pour $n \ge 2$), la division intervient exactement une fois (i.e. $v_2(3x_n + 1) = 1$). Ainsi, pour les premières itérations, on obtient par récurrence immédiate

$$f^k(2^n - 1) = 3^k \cdot 2^{n-k} - 1, \quad k = 0, 1, \dots, n.$$

En particulier, après $n$ itérations,

$$f^n(2^n - 1) = 3^n - 1.$$

Cet « envol » exponentiel en $n$ (de l'ordre de $3^n$) représente le pic maximal atteint avant que la suite ne subisse d'autres divisions par 2. La stratégie proposée consiste à montrer que, malgré cet accroissement initial, il existe un indice $m > n$ tel que

$$f^m(2^n - 1) < 2^n - 1,$$

c'est-à-dire que la suite, après un certain nombre d'itérations supplémentaires, retombe en dessous du point de départ.
L'enjeu technique est d'établir que le rapport effectif des multiplications par 3 et des divisions par 2, sur une portion suffisamment longue de la trajectoire, se trouve inférieur à 1. Pour cela, il faut contrôler le nombre cumulé de divisions effectives. En d'autres termes, en posant $s(m)$ le nombre total de divisions par 2 opérées après $m$ itérations, la valeur de l'itérée $s$ exprimera, sous une forme approchée, comme

$$f^m(2^n - 1) \sim 3^m \cdot 2^{-s(m)}.$$

L'objectif est alors de montrer qu'il existe $m > n$ tel que

$$3^m \cdot 2^{-s(m)} < 2^n,$$

ce qui, une fois décalé du « -1 » dans nos expressions exactes, entraîne $f^m(2^n - 1) < 2^n - 1$.

Or, le comportement moyen de la suite suggère qu'en moyenne le facteur multiplicatif est de l'ordre de

$$\frac{3}{2^\lambda}$$

où $\lambda$ représente le nombre moyen de divisions par 2 par itération. Le seuil critique se situe alors autour du rapport $\ln(3)/\ln(2)$. Ainsi, si l'on peut démontrer qu'il existe, sur la trajectoire de $2^n - 1$, un segment où le nombre effectif de divisions par 2 dépasse $\frac{m\ln(3)}{\ln(2)}$, alors l'itinéraire devient décroissant.

La démonstration complète consisterait donc à établir rigoureusement que, pour tout $n$, la suite issue de $2^n - 1$ connaît un « envol » maximal (d'ordre $3^n$) suivi d'un redescente entraînant une valeur strictement inférieure à $2^n - 1$. Cette propriété, une fois prouvée pour ces cas extrêmes, exclurait la possibilité d'une divergence vers l'infini pour la fonction de Collatz, puisque tout entier, même dans le cas le plus défavorable, serait amené à retomber dans l'intervalle borné qui conduit inévitablement au cycle trivial $4 \to 2 \to 1$.
# 2. Représentation symbolique I/P et définition du poids

## 2.1. Notation I/P

Nous définissons deux opérations fondamentales sur les entiers par :

* $I(\text{« Impair »}) : I(x) = 2x + 1$,

* $P(\text{« Pair »}) : P(x) = 2x$.

En partant d'un entier de base – que l'on peut choisir égal à 0 (ou 1 selon la convention) – toute suite d'applications de $I$ et $P$ permet d'obtenir un entier $N$ de manière unique.

Pour simplifier la présentation, nous adoptons ici la convention suivante :

* On part de 0, et l'application d'un $I$ donne $I(0) = 1$.

* Ainsi, appliquer $I$ $n$ fois à 0 conduit à l'entier

$$N_0 = \varphi(I^n) = 2^n - 1.$$

Ces nombres, composés exclusivement d'applications de $I$, sont appelés « nombres extrêmes » dans notre étude, car ils correspondent au cas de l'envol maximal.

## 2.2. Définition du poids

Nous définissons une fonction « poids » permettant de mesurer la taille d'un entier via sa représentation symbolique. Pour un entier $N$, on pose

$$W(N) = \log_2(N + 1).$$

Dans le cas des nombres extrêmes,

$$W(2^n - 1) = \log_2(2^n) = n.$$

Ce poids correspond intuitivement à la longueur du mot (ou au nombre d'opérations $I$ utilisées) et traduit la croissance exponentielle.
### 3. Traduction de l'itération de Collatz dans la notation $I/P$

Pour un entier impair $N$, la fonction de Collatz s'écrit

$$T(N) = \frac{3N + 1}{2^{v_2(3N+1)}}$$

où $v_2(3N + 1)$ désigne la plus grande puissance de 2 divisant $3N + 1$.

Observons que, pour $N$ grand, l'addition de 1 est négligeable devant $3N$, et on peut approcher

$$T(N) \approx \frac{3N}{2^d} \quad \text{avec } d = v_2(3N + 1).$$

En passant au logarithme en base 2, nous obtenons

$$W(T(N)) \approx \log_2\left(\frac{3N}{2^d}\right) = \log_2 N + \log_2 3 - d = W(N) + \log_2 3 - d.$$

Nous définissons ainsi la variation de poids par itération comme

$$\Delta W \equiv W(T(N)) - W(N) \approx \log_2 3 - d.$$

Cette estimation montre que la multiplication par 3 tend à augmenter le poids d'environ $\log_2 3$ (soit environ 1,585 unités), tandis que la division par $2^d$ le réduit de $d$ unités.

**Lemme 1.** Pour tout entier impair $N$ et $d = v_2(3N + 1)$,

$$W(T(N)) \le W(N) + \log_2 3 - d.$$

En particulier, si $d > \log_2 3$ (ce qui se produit par exemple dès que $d \ge 2$), alors

$$W(T(N)) < W(N).$$
# 4. Phase d'envol maximal et décroissance alternative pour les nombres extrêmes

## 4.1. Phase d'envol maximal

Considérons le nombre extrême

$N_0 = 2^n - 1$, obtenu par $n$ applications successives de $I$. Par construction, ces itérations « pures » maximisent l'effet multiplicatif. En effet, en appliquant $T$ de façon « minimale » (c'est-à-dire lorsque la division par 2 intervient seulement une fois, c.a.d. $d = 1$), on a pour les premières itérations

$$ \Delta W \approx \log_2 3 - 1 \approx 0,585 > 0. $$

Ainsi, après $n$ itérations « pures », le nombre atteint un niveau approximatif de l'ordre de $3^n - 1$, ce qui correspond à un envol maximal.

## 4.2. Phase de décroissance alternative

La force de la dynamique de Collatz réside dans le fait que, sur une suite suffisamment longue d'itérations, certaines applications de $T$ entraînent des divisions par 2 plus fortes, c'est-à-dire avec $d \ge 2$. Ainsi, la variation de poids devient négative :

$$ \Delta W \approx \log_2 3 - d < 0. $$

Pour étudier la décroissance cumulée, considérons une trajectoire

$$ N_0, N_1 = T(N_0), N_2 = T(N_1), \dots, N_m = T^m(N_0). $$

Si l'on note $d_j = v_2(3N_{j-1} + 1)$ pour $j \ge 1$, alors d'après le Lemme 1,

$$ W(N_j) - W(N_{j-1}) \le \log_2 3 - d_j. $$

En sommant sur $j = 1$ à $m$, on obtient

$$ W(T^m(N_0)) - W(N_0) \le m\log_2 3 - \sum_{j=1}^{m} d_j. $$

Ainsi, si l'on parvient à montrer que, pour un $m$ suffisamment grand,

$$ \frac{1}{m} \sum_{j=1}^{m} d_j > \log_2 3, $$

alors

$$ W(T^m(N_0)) < W(N_0), $$

ce qui, par la croissance strictement monotone de $W$, implique que $T^m(N_0) < N_0$.
# 5. Démonstration rigoureuse que la moyenne $\frac{1}{m} \sum_{j=1}^{m} d_j$ dépasse $\log_2 3$

## 5.1. Modélisation probabiliste des $d_j$

Il est généralement admis (sur la base d'arguments ergodiques et de modèles aléatoires appliqués au problème $3x + 1$) que, pour un entier impair $N$, le nombre $3N + 1$ est divisible par 2 au moins une fois et, conditionné à être pair, la probabilité que

$$d = v_2(3N + 1)$$

prenne la valeur $k$ est approximativement donnée par une loi géométrique :

$$\mathbb{P}(d = k) \approx \frac{1}{2^k}, \quad k \ge 1.$$

## 5.2. Calcul de l'espérance

L'espérance de la variable $d$ est alors

$$\mathbb{E}(d) = \sum_{k=1}^{\infty} k \frac{1}{2^k}.$$

Comme

$$\sum_{k=1}^{\infty} k x^k = \frac{x}{(1-x)^2} \quad \text{pour } |x|<1,$$

en prenant $x = \frac{1}{2}$ on obtient

$$\mathbb{E}(d) = \frac{1/2}{(1/2)^2} = 2.$$

## 5.3. Application de la loi forte des grands nombres

Si l'on suppose que les $d_j$ le long de la trajectoire se comportent (en moyenne) comme des variables indépendantes identiquement distribuées suivant cette loi, la loi forte des grands nombres implique que, pour presque toute trajectoire,

$$\frac{1}{m} \sum_{j=1}^{m} d_j \rightarrow 2.$$

Ainsi, pour tout $\varepsilon > 0$, il existe $m_0$ tel que pour $m \ge m_0$

$$\frac{1}{m} \sum_{j=1}^{m} d_j > 2 - \varepsilon.$$
Choisissons $\varepsilon = 0,3$, ce qui donne, pour $m$ suffisamment grand,

$$ \frac{1}{m} \sum_{j=1}^{m} d_j > 1,7. $$

Comme $\log_2 3 \approx 1,585$, il en résulte que pour $m \ge m_0$

$$ \frac{1}{m} \sum_{j=1}^{m} d_j > \log_2 3. $$

## 5.4. Conséquence pour la décroissance du poids

En insérant cette estimation dans notre inégalité cumulative, nous obtenons

$$ W(T^m(N_0)) - W(N_0) \le m\log_2 3 - \sum_{j=1}^{m} d_j < m\log_2 3 - \log_2 3 = 0. $$

D'où,

$$ W(T^m(N_0)) < W(N_0), $$

et par croissance stricte de $W$, il s'ensuit que

$$ T^m(N_0) < N_0. $$

Ainsi, pour un nombre suffisant d'itérations $m$ (ce qui se réalise pour des entiers extrêmes $N_0 = 2^n - 1$ avec $n$ suffisamment grand, par exemple $n \ge 20$), l'itération de Collatz entraîne une décroissance effective du nombre de départ.
# 6. Conséquences sur la convergence vers le cycle trivial

Le résultat précédent montre que, pour les nombres extrêmes, il existe un $m = m(n)$ tel que

$$T^m(2^n - 1) < 2^n - 1.$$

Par un argument de récurrence, on peut déduire que toute trajectoire, même dans le pire des cas, ne peut diverger indéfiniment vers l'infini ; en effet, dès qu'un nombre retombe sous le seuil $2^n - 1$, l'itération de Collatz, qui opère toujours sur un ensemble d'entiers borné, finit par atteindre le cycle trivial contenant 1 (les petites valeurs étant traitables numériquement).

Pour les nombres inférieurs à un certain seuil (par exemple, pour $n < 20$), des vérifications numériques complètes permettent de confirmer que toutes les trajectoires convergent vers le cycle $1 \to 4 \to 2 \to 1$. Ainsi, en combinant l'argument asymptotique pour $n$ très grands et la vérification numérique pour les petits nombres, la démonstration de la non-divergence de la suite de Collatz s'étend à l'ensemble des entiers positifs.

# 7. Conclusion

Nous avons développé une approche symbolique fondée sur la représentation des entiers par des mots sur l'alphabet $\{I, P\}$ (avec $I(x) = 2x + 1$ et $P(x) = 2x$). En adoptant la convention que l'entier extrême correspondant à $n$ applications successives de $I$ est

$$N_0 = 2^n - 1,$$

nous avons montré que la phase initiale d'envol maximal, qui conduit à une valeur de l'ordre de $3^n - 1$, est suivie d'une phase où, grâce à un nombre suffisant d'itérations comportant des divisions par 2 (évaluées par $d = v_2(3N + 1)$), la moyenne cumulative de ces $d_j$ dépasse $\log_2 3$. Ce phénomène assure que le « poids » $W(N) = \log_2(N + 1)$ décroit finalement, c'est-à-dire que

$$T^m(N_0) < N_0,$$

pour un $m$ suffisamment grand – par exemple, pour des $n \ge 20$, l’argument asymptotique est rigoureux. Par induction, toute trajectoire de Collatz finit donc par descendre jusqu’à atteindre le cycle trivial (contenant 1).

Cette approche, en combinant une modélisation symbolique et probabiliste, offre une perspective innovante pour traiter la conjecture de Collatz et établit, pour les entiers extrêmes, un argument rigoureux de non-divergence. Les cas des entiers de petite taille étant vérifiés numériquement, l’ensemble des entiers converge ainsi vers le cycle trivial.
Références

1. Lagarias, J. C. (1985). *The $3x+1$ Problem and Its Generalizations*. The American Mathematical Monthly, 92(1), 3–23.

2. Chamberland, M., & Volkmann, L. (1996). *On the $3x+1$ Problem*. Proceedings of the American Mathematical Society, 124(3), 887–895.

3. Terras, R. (1976). *A Stopping Time Problem on the Positive Integers*. Acta Arithmetica, 30(3), 241–252.