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
\(\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 \(s\) (i.e. \(n_s=n_0\)) et en multipliant, on obtient l’équation de cycle
\(\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 \(2^{\,s}>3^{\,K}\) et, en divisant par \(s\) :
\(\displaystyle \frac{K}{s}\;<\;\log_3 2\;\approx\;0{,}63093.[/latex]
Mais comme chaque [latex]\kappa_i\ge 1\), on a \(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
\(\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 \(s\) (i.e. \(x_s=x_0\)), l’équation de cycle analogue donne
\(\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 \(2^{\,K}>3^{\,s}\) et
\(\displaystyle \frac{K}{s}\;>\;\log_2 3\;\approx\;1{,}5849625.\)
Or on ne sait a priori que \(k_i\ge 1\) (donc \(K/s\ge 1\)), ce qui est insuffisant. Toute preuve d’absence de cycles doit garantir partout une marge \(\underline{k}>\log_2 3\) sur la moyenne des \(k_i\) au sein de toute composante candidate.
| Problème | Bloc compressé | Valuation par pas | Seuil critique | Conclusion |
|---|---|---|---|---|
Variante /3 ou *2−1 | \(n\mapsto\dfrac{2n-1}{3^{\kappa}}\) | \(\kappa=\nu_3(2n-1)\ge 1\) | \(\log_3 2\approx 0{,}6309\) | Impossible d’avoir \(K/s<\log_3 2[/latex] alors que [latex]K/s\ge 1[/latex] ⇒ pas de cycles |
| Collatz classique (impairs) | [latex]x\mapsto\dfrac{3x+1}{2^{k}}\) | \(k=\nu_2(3x+1)\ge 1\) | \(\log_2 3\approx 1{,}585\) | Il faut prouver \(\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 \((\alpha\bmod 2^m)\) impairs, \((\beta\bmod 3^b)\), phases MCC0/1/2), chaque arête porte le poids \(k=\nu_2(3y+1)\). Pour une composante fortement connexe (CFC), on calcule la moyenne minimale \(\mu_{\min}\) des poids des cycles (Karp/Howard). Si dans chaque CFC on a \(\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, \(\log_3 2<1[/latex] rend la contradiction immédiate. Dans la classique, [latex]\log_2 3>1\) impose d’obtenir une marge stricte \(\underline{k}>\log_2 3\).
- Opérationnellement : certifier \(\mu_{\min}>\log_2 3\) dans toutes les CFC de la fenêtre \((2^m,3^b)\) + garantir par BFS inverse et barrières (ex. \(\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 \(\nu_2(3x+1)\). C’est exactement ce que mesurent tes rapports min-mean sur Ufin.
No responses yet