Collatz « en distances » : définition, itération, exemples et pistes anti-cycle
Idée. On remplace l’impair visité x par une distance entière D et un signe de branche \( \sigma\in\{-,+\} \) tels que \(\;x=Y_\sigma(D)=\begin{cases} 3D-1 &(\sigma=-),\\ 3D+1 &(\sigma=+). \end{cases}\)
C’est une formulation strictement équivalente à la Collatz compressée classique (impair \(\mapsto\) diviser par \(2^k\) jusqu’à l’impair suivant), mais écrite uniquement en distances.
1) Encodage « distance » d’un impair
Pour tout impair \(x\), on peut choisir l’un des deux encodages (au besoin on choisit celui qui donne \(D\in\mathbb Z\)) : \(\qquad(\sigma,D)=\begin{cases} (-,\ \frac{x+1}{3}) &\text{si } x\equiv 2\pmod 3,\\[2pt] (+,\ \frac{x-1}{3}) &\text{si } x\equiv 1\pmod 3. \end{cases}\).
Parité structurelle (important). Dans le tableau compressé classique, on ne manipule que des impairs; par conséquent, toutes les distances que l’on considère sont paires : (i) la différence de deux impairs est paire ; (ii) pour la distance « racine ↔ lien » écrite via \(Y=3D\pm1\) (avec \(Y\) impair), on a \(3D\equiv0\pmod2\) donc \(D\) est pair ; (iii) au sein d’une fratrie, \(L_{r,n+1}-L_{r,n}=\frac{(3r+1)4^{\,n+1}-1}{3}-\frac{(3r+1)4^{\,n}-1}{3}=(3r+1)4^{\,n}\), multiple de \(4\) pour \(n\ge1\).
2) Une itération 100 % distances
Étape 1 — profondeur de division 2-adique. À partir de l’état \((\sigma,D)\), on calcule \(\qquad k=\nu_2\!\bigl(3\,Y_\sigma(D)+1\bigr)= \begin{cases} \nu_2(9D-2) &(\sigma=-),\\ \nu_2(9D+4) &(\sigma=+). \end{cases}\)
C’est exactement le nombre de divisions par 2 que l’on ferait après \(3x+1\) dans la version classique.
Étape 2 — saut de colonnes dans la ligne de \(D\). Dans une même ligne (fixer \(D\) de la 1re colonne), la navigation « colonne \(\to\) colonne » suit la récurrence affine \(\qquad F_{t+1}=4F_t+\beta_\sigma(D),\qquad \beta_\sigma(D)=\begin{cases} 2-9D &(\sigma=-),\\ 9D-4 &(\sigma=+). \end{cases}\)
En enchaînant \(k\) colonnes à droite d’un coup, on obtient la forme fermée \(\qquad D’ \;=\; 4^{\,k}D \;+\; \frac{4^{\,k}-1}{3}\,\beta_\sigma(D).\)
Étape 3 — signe suivant. Le nouvel impair \(x’=(3x+1)/2^k\) vérifie \(x’\equiv (-1)^k\pmod 3\). Donc \(\qquad \sigma’=\begin{cases} + &\text{si } k \text{ est pair},\\ – &\text{si } k \text{ est impair}. \end{cases}\)
On recode alors \(x’\) sous la forme \(x’=3D’\pm1\) avec ce \(\sigma’\). Résumé de l’itération : \(\qquad (\sigma,D)\ \longmapsto\ (\sigma’,D’).\)
3) Conjecture de Collatz — version « distances »
Énoncé. Pour tout état initial \((\sigma_0,D_0)\) issu d’un impair \(x_0\), l’itération en distances atteint en un nombre fini d’étapes l’état terminal \( (+,0) \) (i.e. \(x=1\)). Le seul cycle est le cycle trivial autour de \( (+,0) \).
4) Lois résiduelles utiles (lecture rapide)
Mod 8 pour le lien \(Y=3D\pm1\) :
| \(D\bmod 8\) | branche “−” \(3D-1\) | branche “+” \(3D+1\) |
|---|---|---|
| 0 | 7 | 1 |
| 2 | 5 | 7 |
| 4 | 3 | 5 |
| 6 | 1 | 3 |
Parité de \(k\) (donc signe suivant) : \(k\) pair \(\Rightarrow \sigma’=+\), \(k\) impair \(\Rightarrow \sigma’=-\).
Seuils « jump profonds » pour \(k\ge t\). Ce sont des classes très fines sur \(D \bmod 2^t\) :
Branche “−” : \(k\ge t\iff 9D\equiv 2\pmod{2^t}\iff D\equiv a_t\pmod{2^t}\) avec \(a_t\equiv 2\cdot 9^{-1}\ (\bmod 2^t)\).
Valeurs initiales : \(a_3\equiv 2,\ a_4\equiv 2,\ a_5\equiv 18,\ a_6\equiv 50\) (donc \(D\equiv 50\pmod{64}\Rightarrow k\ge 6\)).
Branche “+” : \(k\ge t\iff 9D\equiv -4\pmod{2^t}\iff D\equiv b_t\pmod{2^t}\) avec \(b_t\equiv (-4)\cdot 9^{-1}\ (\bmod 2^t)\).
Valeurs initiales : \(b_3\equiv 4,\ b_4\equiv 12,\ b_5\equiv 28,\ b_6\equiv 60\).
On voit apparaître des « lignes verticales » ultra-rares de \(D\) qui provoquent de gros \(k\) : très utile pour des barrières 2-adiques.
5) Navigation dans une ligne et changement de ligne
Dans la ligne (1re colonne \(F_1=D\)) : \(F_{t+1}=4F_t+\beta_\sigma(D)\). Forme fermée (aller directement à la colonne \(t\ge1\)) :
- si \(D\equiv 2\ (\bmod 8)\) (branche “−”) : \(F_t(d)=\bigl(3-2\cdot 4^{\,t-1}\bigr)d+\frac{2}{3}\bigl(4^{\,t-1}-1\bigr)\) ;
- si \(D\equiv -4\ (\bmod 8)\) (branche “+”) : \(F_t(d)=\bigl(4^{\,t}-3\bigr)d-\frac{4}{3}\bigl(4^{\,t-1}-1\bigr)\).
Ligne voisine (ta table alterne \(d\mapsto d+8\) pour “−” ; \(d\mapsto d-8\) pour “+”) : le paramètre de ligne varie simplement de \( \beta\mapsto \beta-72 \). En colonne \(t\), l’écart entre deux lignes adjacentes vaut :
- branche “−” : \(F_t(d+8)-F_t(d)=8\bigl(3-2\cdot 4^{\,t-1}\bigr)\) ;
- branche “+” : \(F_t(d-8)-F_t(d)=-8\bigl(4^{\,t}-3\bigr)\).
6) Exemple complet : résolution de 11
On part de \(x=11\equiv 2\pmod 3\Rightarrow (\sigma,D)=(-,4)\).
| étape | \((\sigma,D)\) | \(k\) | impair suivant \(x’=(3x+1)/2^k\) | \(\sigma’\) | \(D’\) |
|---|---|---|---|---|---|
| 0 | \((-,4)\) | \(\nu_2(34)=1\) | 17 | − (impair) | \((17+1)/3=6\) |
| 1 | \((-,6)\) | \(\nu_2(52)=2\) | 13 | + (pair) | \((13-1)/3=4\) |
| 2 | \((+,4)\) | \(\nu_2(40)=3\) | 5 | − (impair) | \((5+1)/3=2\) |
| 3 | \((-,2)\) | \(\nu_2(16)=4\) | 1 | + (pair) | \((1-1)/3=\mathbf{0}\) |
Lecture « distances » : \((-,4)\to(-,6)\to(+,4)\to(-,2)\to\mathbf{(+,0)}\). Lecture classique (impairs) : \(11\to17\to13\to5\to1\).
7) Est-ce que cette variante ouvre de nouvelles portes anti-cycle ?
Équivalence stricte : du point de vue logique, on n’a pas d’information « en plus » — prouver l’absence de cycle en distances est équivalent à la Collatz classique.
Mais la formulation « distance » rend très explicites deux leviers techniques utiles pour des certificats de type min-moyenne (à la Karp/Howard) et des barrières 2-adiques :
- Calcul local de \(k=\nu_2(9D\pm c)\) par congruences. Les « gros sauts » \(k\ge t\) ne surviennent que sur une seule classe \(D\bmod 2^t\). Cela crée des colonnes verticales rares (ex. \(D\equiv 50\bmod 64\Rightarrow k\ge 6\)) qui jouent le rôle de barrières fines, à combiner avec tes barrières \( \alpha\bmod 64 \).
- Affinité dans la colonne. La loi \(F\mapsto 4F+\beta\) permet de linéariser les transitions « à droite », ce qui simplifie le design d’automates résiduels et l’agrégation des poids \(k\) (test \(\mu_{\min}> \log_2 3\)).
En pratique : on peut bâtir un NFA/Graphe sur les états \((\sigma,\ D\bmod 2^b)\), arêtes étiquetées par \(k=\nu_2(9D\pm c)\), et vérifier par Karp/Howard que la moyenne minimale de \(k\) sur toute CFC non triviale reste \(>\log_2 3\) (exactement comme dans tes certificats Ufin, mais avec un squelette potentiellement plus économe grâce aux classes uniques \(D\bmod 2^t\) pour grands \(k\)).
Conclusion : théoriquement ça n’« avance » pas la conjecture au sens strict (formulation équivalente), mais méthodologiquement c’est très payant : on clarifie le squelette 2-adique, on comprend où naissent les grands \(k\), et on obtient un cadre linéaire pour tes certificats \(\mu_{\min}>\log_2 3\). En ce sens, oui, cela ouvre des pistes plus nettes pour renforcer les barrières et resserrer les CFC.
8) Annexe — Algorithme « distance only »
Entrée : impair x Si x ≡ 2 (mod 3) : σ ← − ; D ← (x+1)/3 Sinon (x ≡ 1 (mod 3)) : σ ← + ; D ← (x−1)/3 Répéter : k ← ν₂(9D − 2) si σ=−, autrement k ← ν₂(9D + 4) β ← (2 − 9D) si σ=−, autrement β ← (9D − 4) D ← 4^k · D + ((4^k − 1)/3) · β σ ← + si k pair, sinon σ ← − Jusqu’à atteindre (σ, D) = (+, 0)
No responses yet