Conjecture de Collatz

Écrite sous forme d’application, la règle de la conjecture de Collatz est

Un vol part de $n$, passe par $f(n)$, $f(f(n))$ et ainsi de suite, et s’arrête quand il atteint 1 : ensuite, il ne ferait que tourner dans la boucle 1 → 4 → 2 → 1. La conjecture affirme que tout entier strictement positif y arrive. Ici, tu peux faire voler des entiers, même de plusieurs centaines de chiffres, seuls ou en groupe. Tu peux les confronter au raisonnement approximatif qui rend la conjecture si plausible, et voir pourquoi ce raisonnement n’est pas une preuve.

L’axe horizontal donne le nombre d’étapes, l’axe vertical la valeur, sur une échelle logarithmique sauf si tu choisis Linéaire, qui donne le dessin classique en grêlons. Chaque nombre du groupe est une ligne colorée. Un tronçon emprunté par beaucoup de nombres est donc plus marqué : plus clair sur fond sombre, plus foncé sur fond clair. Le nombre observé est mis en évidence, avec un point rouge à sa position actuelle. Les vols sont difficiles à prévoir : 27 monte jusqu’à 9 232 et met 111 étapes à atteindre 1, alors que 28 n’en met que 18.

Pourquoi y croit-on ? Une étape impaire donne toujours un nombre pair : regroupons-la donc avec la division par deux qui suit en une seule étape raccourcie. Supposons maintenant que les parités de ces étapes soient des lancers indépendants d’une pièce équilibrée. La moitié du temps, $n$ est multiplié par environ 3/2, et l’autre moitié par 1/2. En moyenne, une étape raccourcie fait donc varier $\ln n$ de

Les nombres devraient alors diminuer, typiquement d’un facteur 3/4 toutes les deux étapes raccourcies. Sur l’axe logarithmique, cette dérive est la ligne en pointillé, tracée pour un groupe Même ordre de grandeur d’au moins 100 nombres. Elle ignore l’atterrissage : les nombres qui atteignent 1 restent au sol. Vers la fin, la hauteur moyenne du groupe sur cet axe descend donc plus lentement que la ligne.

Les lancers de pièce ne sont qu’un modèle du comportement moyen des nombres. La conjecture porte sur chaque entier strictement positif : un seul vol qui n’atteindrait jamais 1 suffirait à la réfuter.

Les nombres négatifs révèlent ce que le raisonnement manque. La même règle y produit des boucles ; on en connaît trois, par exemple −5 → −14 → −7 → −20 → −10 → −5. Le modèle des lancers prédit une diminution là aussi, alors qu’un tour complet de n’importe quelle boucle fait varier $\log|n|$ d’exactement 0. Une dérive moyenne vers le bas ne peut pas exclure une boucle, même parmi les nombres positifs.

Corail inverse les vols : en remontant depuis 1, les chemins d’un groupe forment un arbre. Chaque arête tourne par rapport à la précédente de $+\alpha$ si le nouveau nombre est pair, et de $-\alpha \log_2 3$ s’il est impair ; α se règle avec Courbure. En remontant depuis 1, une étape paire double le nombre et augmente son $\log_2$ de 1, tandis qu’une étape impaire le diminue d’un peu plus que $\log_2 3$. L’arête qui atteint n a donc tourné au total de $\alpha \log_2 n$ depuis la verticale vers le haut, plus un petit supplément à chaque étape impaire : sa rotation garde la trace de la grandeur de n. Le long d’une branche, la direction monte et descend avec les nombres d’un vol : chaque branche est donc un vol enroulé. Les branches se rejoignent là où les vols se rencontrent. Dans cette représentation, la conjecture dit que l’arbre issu de 1 contient tous les entiers strictement positifs.

Le problème est généralement attribué à Lothar Collatz, qui posait ce genre de questions dans les années 1930. Le corail reprend la « Collatz seaweed » d’Edmund Harriss (2016).