Variante « /3 sinon *2−1 » vs Collatz classique : équations de cycle et seuils critiques
But. Mettre en parallèle la variante T(n)=n/3 si 3|n, sinon T(n)=2n−1 (où l’on prouve qu’il n’y a aucun cycle non trivial), et la Collatz classique compressée (où il faut certifier une marge sur la moyenne des valuations). Les deux se lisent à travers la même « équation de cycle », mais avec des seuils inversés.
1) Variante « /3 ou *2−1 » : pas de cycles (preuve courte)
Étape compressée (émonder les 3) : on écrit
$latex \displaystyle n_{i+1}=\frac{2n_i-1}{3^{\kappa_i}},\qquad \kappa_i:=\nu_3(2n_i-1)\ge 1.$
En supposant un cycle de longueur $latex s$ (i.e. $latex n_s=n_0$) et en multipliant, on obtient l’équation de cycle
$latex \displaystyle (2^{\,s}-3^{\,K})\,n_0\;=\;\sum_{j=0}^{s-1} 2^{\,s-1-j}\,3^{\,\kappa_0+\cdots+\kappa_{j-1}}\;>\;0,\qquad K:=\sum_{i=0}^{s-1}\kappa_i.$
Donc $latex 2^{\,s}>3^{\,K}$ et, en divisant par $latex s$ :
$latex \displaystyle \frac{K}{s}\;<\;\log_3 2\;\approx\;0{,}63093.$
Mais comme chaque $latex \kappa_i\ge 1$, on a $latex K/s\ge 1$ : contradiction. Aucun cycle non trivial n’existe (seul 1 est fixe).
2) Collatz classique (impairs compressés) : ce qu’il faut prouver
Sur les impairs, la version compressée est
$latex \displaystyle x_{i+1}=\frac{3x_i+1}{2^{k_i}},\qquad k_i:=\nu_2(3x_i+1)\ge 1.$
En supposant un cycle de longueur $latex s$ (i.e. $latex x_s=x_0$), l’équation de cycle analogue donne
$latex \displaystyle (2^{\,K}-3^{\,s})\,x_0\;=\;\sum_{j=0}^{s-1} 3^{\,j}\,2^{\,K-(k_0+\cdots+k_j)}\;>\;0,\qquad K:=\sum_{i=0}^{s-1}k_i.$
Donc $latex 2^{\,K}>3^{\,s}$ et
$latex \displaystyle \frac{K}{s}\;>\;\log_2 3\;\approx\;1{,}5849625.$
Or on ne sait a priori que $latex k_i\ge 1$ (donc $latex K/s\ge 1$), ce qui est insuffisant. Toute preuve d’absence de cycles doit garantir partout une marge $latex \underline{k}>\log_2 3$ sur la moyenne des $latex k_i$ au sein de toute composante candidate.
| Problème | Bloc compressé | Valuation par pas | Seuil critique | Conclusion |
|---|---|---|---|---|
Variante /3 ou *2−1 | $latex n\mapsto\dfrac{2n-1}{3^{\kappa}}$ | $latex \kappa=\nu_3(2n-1)\ge 1$ | $latex \log_3 2\approx 0{,}6309$ | Impossible d’avoir $latex K/s<\log_3 2$ alors que $latex K/s\ge 1$ ⇒ pas de cycles |
| Collatz classique (impairs) | $latex x\mapsto\dfrac{3x+1}{2^{k}}$ | $latex k=\nu_2(3x+1)\ge 1$ | $latex \log_2 3\approx 1{,}585$ | Il faut prouver $latex \underline{k}>\log_2 3$ dans toute CFC ⇒ pas de cycles |
Encadré — Lecture via l’automate Ufin et le min-mean.
Dans l’automate (états $latex (\alpha\bmod 2^m)$ impairs, $latex (\beta\bmod 3^b)$, phases MCC0/1/2), chaque arête porte le poids $latex k=\nu_2(3y+1)$. Pour une composante fortement connexe (CFC), on calcule la moyenne minimale $latex \mu_{\min}$ des poids des cycles (Karp/Howard). Si dans chaque CFC on a $latex \mu_{\min}>\log_2 3$, alors aucun cycle Collatz non trivial ne peut exister dans le graphe (et, via la couverture inverse/BFS + barrières, nulle part ailleurs).
3) Ce que la variante nous “enseigne” pour la classique
- La structure d’équation de cycle est la même ; seul change le seuil. Dans la variante, $latex \log_3 2<1$ rend la contradiction immédiate. Dans la classique, $latex \log_2 3>1$ impose d’obtenir une marge stricte $latex \underline{k}>\log_2 3$.
- Opérationnellement : certifier $latex \mu_{\min}>\log_2 3$ dans toutes les CFC de la fenêtre $latex (2^m,3^b)$ + garantir par BFS inverse et barrières (ex. $latex \alpha\equiv 21\bmod 64$) que toute orbite finit par s’y loger.
- Le “tableau compressé” de la variante (limité à ce qui descend) est l’analogue conceptuel de nos ossatures MCC/MRC : il isole les classes qui tirent vers le bas vs celles qui forment une barrière.
Résumé. La variante donne une preuve-école (seuil <1) et la feuille de route pour la classique : tout revient à une contrainte de moyenne sur $latex \nu_2(3x+1)$. C’est exactement ce que mesurent tes rapports min-mean sur Ufin.
Aucune réponse