FR – Approche par racine minimal

Retours −1/4, squelette MCC et « distance » : pourquoi c’est utile (et comment s’en servir)

Idée générale. Les retours (y−1)/4 ne sont pas la règle Collatz compressée, mais l’inverse du pas fratrie NE : x↦4x+1. Ils permettent de remonter le squelette MCC jusqu’à la racine minimale et fournissent des congruences fortes modulo \(4^{j}\) qui forcent des poids 2-adiques élevés pour \(3y+1\). Cela mène à des barrières utiles pour l’analytique et pour les certificats min–mean (Karp/Howard).

1) Rappels MCC : fratries, squelette et « distance »

Sur les impairs, chaque case du tableau (repère MCC) s’écrit \[ L_{r,n}=\frac{(3r+1)4^{\,n}-1}{3}=r\,4^{\,n}+\frac{4^{\,n}-1}{3}. \] Le pas fratrie (diagonale NE) est \(L_{r,n+1}=4L_{r,n}+1\). Son inverse est le retour \(L_{r,n-1}=(L_{r,n}-1)/4\). Répéter \(-1/4\) jusqu’au non-entier ramène à la racine \(r\).

Vocabulaire. Pour rester alignés avec l’export, on appelle ici « distance linéaire » \(D\) (entier pair dans les tableaux), à ne pas confondre avec la profondeur de colonne \(4^d\).

2) Distance \(D\) : deux racines minimales et deux liens

Pour une distance paire \(D\), il y a exactement deux racines minimales compatibles, donnant deux « branches » :

• Branche − (inverse via \(F(y)=(y+1)/2\)) : \(r_-=2D-1\) (toujours \(≡3,7\pmod 8\)) et son lien \(Y_-=\mathrm{oddize}(3r_-+1)=3D-1\).
• Branche + (parenté « fratrie ») : \(r_+=4D+1\) (toujours \(≡1\pmod 8\)) et son lien \(Y_+=\mathrm{oddize}(3r_+ +1)=3D+1\).

Exemples. \(D=10\Rightarrow (r_-,Y_-)=(19,29),\ (r_+,Y_+)=(41,31)\). \(D=14\Rightarrow (27,41)\) et \((57,43)\). \(D=16\Rightarrow (31,47)\) et \((65,49)\).

D (pair)	r−=2D−1	Y−=3D−1	r+=4D+1	Y+=3D+1
10	19	29	41	31
14	27	41	57	43
16	31	47	65	49

3) Lemme « j-retours » : congruence et poids 2-adique

Lemme. On peut appliquer \(-1/4\) exactement \(j\) fois à un impair \(y\) ssi \[ y \equiv \frac{4^{j}-1}{3} \pmod{4^{j}}. \] Dans ce cas, \(3y+1=4^{j}(1+3t)\) et donc \(\nu_2(3y+1)\ge 2j\).

Conséquence. Les classes \(j\) (ex. 1, 5, 21, 85 mod \(4^j\)) sont des barrières hiérarchiques : les traverser force des poids 2-adiques élevés. C’est la congruence « plus forte » qui manque si l’on reste au seul modulo 8.

4) Lien direct « squelette → poids »

Pour tout \(L_{r,n}\), \[ 3L_{r,n}+1=(3r+1)\,4^{n}\quad\Rightarrow\quad k=\nu_2(3L_{r,n}+1)=2n+\nu_2(3r+1). \] Ainsi, sur le squelette, le poids du pas compressé est déterministe à partir de \((r,n)\) : le rang \(n\) compte pour \(2n\) et la racine ajoute l’offset \(\nu_2(3r+1)\).

5) Pas compressé (rappel mod 8)

• \(y\equiv 3,7\ (\mathrm{mod}\ 8)\) : \(F(y)=\frac{3y+1}{2}=y+\frac{y+1}{2}\).
• \(y\equiv 1\ (\mathrm{mod}\ 8)\) : \(F(y)=\frac{3y+1}{4}=y-\frac{y-1}{4}\).
• \(y\equiv 5\ (\mathrm{mod}\ 8)\) : \(3y+1\) divisible par \(8\) (souvent plus) : faire \(z\leftarrow y-\frac{y-1}{4}\) puis diviser \(z\) par \(2\) jusqu’à l’impair.

Note. Les retours \(-1/4\) servent à naviguer dans la fratrie (géométrie MCC), pas à itérer Collatz directement ; projetée sur le squelette, l’arête est la même (NE) après l’effondrement vertical (divisions par 2).

6) Pourquoi c’est utile pour la preuve

• Barrières empilées. Si une trajectoire visite la couche \(j\ge J\) avec fréquence \(p\), alors \(\overline{k}\ge 2J\,p\). Dès que \(2J\,p>\log_2 3\approx 1.58496\), tout cycle est impossible.
• Automate plus tranchant. Dans un NFA « cohérent », taguer/forcer les classes \(j\) fait monter la moyenne min \(\mu_{\min}\) au-dessus de \(\log_2 3\) plus vite qu’avec une seule barrière (ex. \(21\ \mathrm{mod}\ 64\)).
• Squelette déterministe. Sur \((r,n)\), les poids sont connus a priori : pruning des états trop faibles et bornes inférieures analytiques de \(\mu_{\min}\) avant l’exploration complète.

7) Encadré « implémentation »

Détection du niveau \(j\) (nombre de retours \(-1/4\) possibles) :

// j = max { t ≥ 0 : y ≡ (4^t − 1)/3 (mod 4^t) }
// équivalent : while ((y − 1) % 4 == 0) { y = (y − 1)/4; j++; }

Pas compressé (impairs uniquement) :

z = 3*y + 1;
// diviser z par 2 jusqu'à l'impair
while ((z & 1) == 0) z >>= 1;
return z;  // = oddize(3y+1)

Pont squelette → poids. Si l’état est \((r,n)\), alors k = 2n + v2(3r+1) sans calculer 3y+1 au vol.

8) FAQ rapide

« Les −1/4 reproduisent-ils Collatz ? » Non. Ce sont des retours de fratrie (géométrie), pas la dynamique compressée. Projeté sur le squelette, l’arc est la même NE après divisions par 2.

« En quoi est-ce nouveau vs \(21\ \mathrm{mod}\ 64\) ? » On peut empiler les classes \(j\) (mod \(4^{j}\)) et obtenir des poids garantis \(\ge 2j\), ce qui fait grimper les moyennes plus vite et simplifie pruning/certificats.

« Où intervient la distance \(D\) ? » Elle indexe un doublet canonique de racines minimales : \(r_-=2D-1\) et \(r_+=4D+1\), avec liens \(Y_-=3D-1\) et \(Y_+=3D+1\). C’est le point de jonction entre ta métrique pratique et la géométrie MCC.

Conditions nécessaires d’un cycle non trivial (compressé impair)

Cadre. On travaille en compressé impair, avec pas $latex \ (3y+1)/2^{k_i}$ et la géométrie MCC (distances paires $latex D$ et branches $\pm$). Les conditions ci-dessous sont nécessaires à l’existence d’un cycle non trivial.

1) Budget 2-adique exact

$latex \displaystyle \prod_{i=1}^{E}\frac{3}{2^{k_i}}=1 \iff \sum_{i=1}^{E}k_i \;=\;E\,\log_2 3 \;=:\; E\,\theta,\quad \theta\approx 1.5849625.$
Autrement dit, la moyenne doit être $latex \bar k=\theta$ exactement.

2) Fermeture géométrique (distances $latex D$)

Pour une distance paire $latex D$, il y a deux racines minimales compatibles (donc deux branches) :

• Branche $latex (-)$ (retour inverse via $latex F(y)=(y+1)/2$) : $latex \ r_-=2D-1\ (\equiv 3,7\ \mathrm{mod}\ 8)$, et son lien $latex \ Y_-=\mathrm{oddize}(3r_-+1)=3D-1$.
• Branche $latex (+)$ (parenté fratrie) : $latex \ r_+=4D+1\ (\equiv 1\ \mathrm{mod}\ 8)$, et son lien $latex \ Y_+=\mathrm{oddize}(3r_++1)=3D+1$.

Sur un tour complet de longueur $latex E$, la somme signée des déplacements doit s’annuler : $latex \ \sum_{i=1}^{E}\varepsilon_i D_i=0$, avec $latex \ \varepsilon_i\in\{+1,-1\}$ selon la branche $latex (+)$ ou $latex (-)$.

D (pair)	$latex r_-=2D-1$	$latex Y_-=3D-1$	$latex r_+=4D+1$	$latex Y_+=3D+1$
10	19	29	41	31
14	27	41	57	43
16	31	47	65	49

3) Lemme « j-retours » (barrières hiérarchiques)

On peut appliquer $latex -\frac14$ exactement $latex j$ fois à un impair $latex y$ ssi $latex \ y\equiv \frac{4^j-1}{3}\pmod{4^j}$. Alors $latex \ 3y+1=4^j(1+3t)$ donc $latex \ \nu_2(3y+1)\ge 2j$.
Conséquence. Les classes $latex \ D_j=\bigl\{\frac{4^j-1}{3}\ (\mathrm{mod}\ 4^j)\bigr\}$ sont des barrières : les franchir impose $latex \ k\ge 2j$.

4) Lien direct « squelette → poids »

Pour $latex \ L_{r,n}=\frac{(3r+1)4^{\,n}-1}{3}$ (colonne MCC $latex 2+n$) : $latex \ 3L_{r,n}+1=(3r+1)4^n$ donc $latex \ k=\nu_2(3L_{r,n}+1)=2n+\nu_2(3r+1)$.
À colonne fixée, la valuation est déterministe (le rang donne $latex 2n$, la racine donne l’offset).

5) Rappels $latex \bmod 8$ (sélection des pas)

• $latex y\equiv 3,7\pmod 8$ : $latex \ F(y)=3y+1$ (pas compressé « direct »).
• $latex y\equiv 1\pmod 8$ : $latex \ k\ge 2$ (au moins une division supplémentaire).
• $latex y\equiv 5\pmod 8$ : $latex \ k\ge 3$ (souvent plus).

Corollaires utiles

• Confinement : un cycle hypothétique doit rester dans de petites colonnes (typiquement $latex j\le 2$). Toucher régulièrement $latex D_3$ (ex. $latex 21\ (\mathrm{mod}\ 64)$) force $latex \bar k$ au-dessus de $latex \theta$.
• Version machine : c’est exactement ce que certifie le min–moyenne (Karp/Howard) sur ton automate : si toute CFC vérifie $latex \mu_{\min}>\theta$, aucun cycle non trivial.

Exemples (distances)

Pour $latex D=10$ : $latex (r_-,Y_-)=(19,29)$ et $latex (r_+,Y_+)=(41,31)$. Pour $latex D=14$ : $latex (27,41)$ et $latex (57,43)$. Pour $latex D=16$ : $latex (31,47)$ et $latex (65,49)$.

Distances racine↔lien, fratries, et famille universelle F_m

Cadre. On travaille sur les impairs et l’on recentre toute visite d’un membre de fratrie par l’opération (x-1)/4 autant que possible pour revenir à la racine minimale r (i.e. $latex r\equiv 1,3,7\ (\bmod\ 8)$) avant de passer au lien Y. On appelle distance le saut structurel entre racine et lien :

$latex d = \lvert Y-r\rvert$   (toujours pair). On note $latex d^{+}$ quand $latex r<Y$ et $latex d^{-}$ quand $latex r>Y$.

Fratrie issue d’une racine minimale $latex r$ (ligne du tableau, opérateur de colonne x ↦ 4x+1) :

$latex L_{r,n}=r\,4^{n}+\frac{4^{n}-1}{3}=\frac{(3r+1)\,4^{n}-1}{3}\quad(n\ge 0).$

1) Cas classique 3x+1 (m=1, C=1)

Catalogue par distance. Pour chaque $latex d\in\{2,4,6,\dots\}$, il y a exactement deux liens possibles, qui couvrent tous les impairs non multiples de 3 (structurellement 50/50) :

• $latex d^{+}$ (saut vers le haut, $latex v_2(3r+1)=1$) : $latex r=2d-1,\quad Y=3d-1$  ($latex Y\equiv 5\ (\bmod\ 6)$).
• $latex d^{-}$ (saut vers le bas, $latex v_2(3r+1)=2$) : $latex r=4d+1,\quad Y=3d+1$  ($latex Y\equiv 1\ (\bmod\ 6)$).

Inversion depuis un lien. Chaque lien impair $latex Y\not\equiv 0\ (\bmod\ 3)$ provient d’un unique couple $latex (d,\pm)$ :

• Si $latex Y\equiv 5\ (\bmod\ 6)$ : $latex d=\frac{Y+1}{3}$ (pair), $latex r=\frac{2Y-1}{3}$ → branche $latex d^{+}$.
• Si $latex Y\equiv 1\ (\bmod\ 6)$ : $latex d=\frac{Y-1}{3}$ (pair), $latex r=\frac{4Y-1}{3}$ → branche $latex d^{-}$.

Fratries paramétrées par d.

• Depuis $latex d^{+}$ ($latex r=2d-1,\ Y=3d-1$) : $latex L_{+,d}(n)=\frac{2(3d-1)\,4^{n}-1}{3}$.
• Depuis $latex d^{-}$ ($latex r=4d+1,\ Y=3d+1$) : $latex L_{-,d}(n)=\frac{(3d+1)\,4^{n+1}-1}{3}$.

d	d+ : r → Y	d− : r → Y
2	3 → 5	9 → 7
4	7 → 11	17 → 13
6	11 → 17	25 → 19
8	15 → 23	33 → 25

2) Famille universelle F_m (constante $latex C=2^{m}-1$)

On généralise via $latex T_m(x)=\frac{3x+C}{2^{\,v_2(3x+C)}}$ avec $latex C=2^{m}-1$ (impair). Le catalogue par distance $latex d$ (toujours paire) devient :

• $latex d^{+}$ ($latex v_2(3r+C)=1$) : $latex r=2d-C,\quad Y=3d-C$.
• $latex d^{-}$ ($latex v_2(3r+C)=2$) : $latex r=4d+C,\quad Y=3d+C$.

Inversion depuis un lien. Tout lien impair se met de façon unique sous l’une des deux formes $latex Y=3d-C$ ou $latex Y=3d+C$ avec $latex d$ pair. Poser $latex d_{+}=\frac{Y+C}{3}$ et $latex d_{-}=\frac{Y-C}{3}$ :

• Si $latex d_{+}$ est pair → $latex Y=3d_{+}-C$ et $latex (r,Y)=(2d_{+}-C,\ 3d_{+}-C)$ (branche $latex d^{+}$).
• SINON $latex d_{-}$ est pair → $latex (r,Y)=(4d_{-}+C,\ 3d_{-}+C)$ (branche $latex d^{-}$).

Fratrie pour F_m. L’opérateur de colonne reste affine (car $latex 3(4x+C)+C=4(3x+C)$) et l’on a :

$latex L^{(m)}_{r,n}=r\,4^{n}+\frac{C\,(4^{n}-1)}{3}=\frac{(3r+C)\,4^{n}-C}{3}\quad(n\ge 0).$

Remarque mod 3. Si $latex m$ est impair ($latex C\equiv 1\ (\bmod\ 3)$), alors $latex Y\equiv -1\ (\bmod\ 3)$ caractérise la branche $latex d^{+}$ et $latex Y\equiv +1\ (\bmod\ 3)$ la branche $latex d^{-}$. Si $latex m$ est pair ($latex C\equiv 0\ (\bmod\ 3)$), on a $latex Y\equiv 0\ (\bmod\ 3)$ dans les deux cas : on utilise alors directement l’algorithme $latex d_{\pm}=\frac{Y\pm C}{3}$ et (dans tes posts) le périmètre S adapté.

3) Structure 50/50 vs fréquences dynamiques

Structurellement (catalogue par $latex d$) : exactement moitié des liens sont de la forme $latex 3d-C$ (branche $latex d^{+}$) et moitié de la forme $latex 3d+C$ (branche $latex d^{-}$).

Dynamiquement (le long d’une trajectoire), pour le cas classique, les racines minimales $latex r\equiv 3,7\ (\bmod\ 8)$ (branche $latex +$) se présentent typiquement environ deux fois plus que $latex r\equiv 1\ (\bmod\ 8)$ (branche $latex -$) : on observe souvent ~2/3 de pas “+” pour ~1/3 de pas “−”. Cela n’affecte pas le 50/50 structurel.

4) Translation inter-fratries $latex \Delta=r’-r$

Après le saut $latex r\to Y$, on recentre $latex Y$ par (x-1)/4 autant que possible jusqu’à la racine minimale $latex r’$. Posons $latex q=\left\lfloor \frac{v_2(3Y+C)}{2}\right\rfloor$, alors

$latex r’=\frac{\,3Y+C\,-\,C\,4^{q}\,}{\,3\cdot 4^{q}\,}$,   d’où $latex \Delta=r’-r$.

• Branche $latex d^{+}$ ($latex r=2d-C,\ Y=3d-C$) : $latex \ \Delta=\frac{\,9d-2C\,-\,C\,4^{q}\,}{\,3\cdot 4^{q}\,}-(2d-C)$, avec $latex q=\left\lfloor \frac{v_2(9d-2C)}{2}\right\rfloor$.
• Branche $latex d^{-}$ ($latex r=4d+C,\ Y=3d+C$) : $latex \ \Delta=\frac{\,9d+4C\,-\,C\,4^{q}\,}{\,3\cdot 4^{q}\,}-(4d+C)$, avec $latex q=\left\lfloor \frac{v_2(9d+4C)}{2}\right\rfloor$.

Cas générique $latex q=0$ (pas de recentrage supplémentaire après le saut) : $latex \Delta=+d$ pour la branche $latex d^{+}$, et $latex \Delta=-d$ pour la branche $latex d^{-}$. Si $latex q\ge 1$, les recentrages (x-1)/4 rabaisseront $latex r’$ et feront dévier $latex \Delta$ de $latex \pm d$.

5) Unité universelle B | u (rappel concis, m=1)

Tout impair $latex x$ s’écrit $latex x=8B+u$ avec $latex u\in\{1,3,5,7\}$. Pour $latex d=2k$ :

• Branche $latex d^{+}$ ($latex r=4k-1,\ Y=6k-1$) : $latex u_r=3$ si $latex k$ impair, $latex u_r=7$ si $latex k$ pair; et $latex u_Y=7,5,3,1$ pour $latex d\equiv 0,2,4,6\ (\bmod\ 8)$.
• Branche $latex d^{-}$ ($latex r=8k+1,\ Y=6k+1$) : $latex u_r=1$; et $latex u_Y=1,7,5,3$ pour $latex d\equiv 0,2,4,6\ (\bmod\ 8)$.

Dans une fratrie $latex L_{r,n}$ : l’unité vaut $latex u_r$ en $latex n=0$, puis 1 en $latex n=1$, puis 5 pour tout $latex n\ge 2$.

6) Résumé express

• Distance paire $latex d$ → deux liens et seulement deux : $latex d^{+}:(r,Y)=(2d-C,\ 3d-C)$, $latex d^{-}:(r,Y)=(4d+C,\ 3d+C)$.
• Inversion unique depuis $latex Y$ par $latex d_{\pm}=\frac{Y\pm C}{3}$ (exactement l’un est pair).
• Fratrie : $latex L^{(m)}_{r,n}=r\,4^{n}+\frac{C(4^{n}-1)}{3}=\frac{(3r+C)\,4^{n}-C}{3}$.
• Structure vs dynamique : 50/50 entre $latex 3d\pm C$ au niveau catalogue; ≈2/3 “+” et ≈1/3 “−” le long d’une trajectoire classique.
• Translation inter-fratries : génériquement $latex \Delta=\pm d$ (si $latex v_2(3Y+C)=1$), sinon déviation gouvernée par $latex q=\left\lfloor \frac{v_2(3Y+C)}{2}\right\rfloor$.