Couture par distances et potentiel décroissant pour la dynamique Collatz (odd-only)
1) Paramétrisation par distances
On travaille dans la dynamique impaire compressée \( T(y)=\frac{3y+1}{2^{\nu_2(3y+1)}} \). Pour toute distance paire \( D=2d \), il y a exactement deux couples (racine minimale, lien) à cette distance :
- Branche \((\,-\,)\) : \( r_- = 2D-1 \equiv 3,7 \ (\bmod\ 8) \), \( Y_- = 3D-1 \).
- Branche \( (+) \) : \( r_+ = 4D+1 \equiv 1 \ (\bmod\ 8) \), \( Y_+ = 3D+1 \).
Par construction, \( |Y_\pm – r_\pm| = D \) et les \( D \) restent toujours pairs tout au long de la couture.
2) Couture d’un pas impair \( y\to T(y) \)
On part de \( D=2d \) et on applique \( T \) sur le lien \( Y_\pm \). On obtient des formules fermées :
| Départ | Quantité | Définition | Décision branche | Nouveau \(D’\) |
|---|---|---|---|---|
| \((\,-\,)\) | \( S_- \) | \( S_- = 9d-1 \) | \( s_-=\nu_2(S_-) \) pair \(\Rightarrow (\,-\,)\), impaire \(\Rightarrow (+)\) | \( y’=\frac{S_-}{2^{s_-}} \), puis \( D’=\frac{y’+1}{3} \) (si \((\,-\,)\)) ou \( D’=\frac{y’-1}{3} \) (si \(+\)) |
| \((+)\) | \( S_+ \) | \( S_+ = 9d+2 \) | \( s_+=\nu_2(S_+) \) pair \(\Rightarrow (\,-\,)\), impaire \(\Rightarrow (+)\) | même règle que ci-dessus |
Heuristique utile : \( D’ \approx \frac{3}{2^{k}}\,D \) avec \( k=\nu_2(3y+1)=s_\pm+1 \). En particulier, \(k=1\) « gonfle » \(D\) (≈ ×1.5), tandis que \(k\ge 2\) le contracte.
3) Un potentiel strictement décroissant (sans probas)
On utilise l’inégalité sûre \[ D’ \;\le\; \frac{3}{2^{k}}\,D \;+\; 1, \] qui vient directement de la couture ci-dessus. Par concavité du log, \[ \log_2(D’+\kappa)-\log_2(D+\kappa) \;\le\; \log_2\!\Big(\frac{3}{2^{k}}+\frac{1}{\kappa}\Big). \] On définit alors le potentiel \[ \quad \Phi \;=\; \log_2(D+\kappa)\;-\;\gamma\cdot \mathrm{clip}(k-2,\,\le 2)\quad \] où \(\mathrm{clip}(x,\le 2)=\min(x,2)\) (pas de “bonus” supérieur à 2 par pas), avec le choix numérique : \[ \kappa=32,\qquad \gamma=0.8. \]
Baisse uniforme. Pour tout pas impair et tout \(k\ge 1\), \[ \Delta\Phi \;\le\; \log_2\!\Big(\frac{3}{2^{k}}+\frac{1}{32}\Big)\;-\;0.8\cdot \bigl(2-\min(k-2,2)\bigr) \;\le\; -0.18, \] le pire cas étant \(k=1\). Tous les autres cas donnent une baisse plus forte.
4) Exemples de couture \( D \mapsto D’ \) (un pas)
Ci-dessous : pour \( D=2,4,\dots,20 \), on affiche pour un départ en branche \((\,-\,)\) et un départ en \( (+) \) : la valuation \( s=\nu_2(9d\pm\cdot) \), la prochaine branche, et le nouveau \( D’ \) (ainsi que \( \Delta D = D’-D \)).
| D | Départ \((\,-\,)\) | Départ \( (+) \) | ||||||
|---|---|---|---|---|---|---|---|---|
| \(s\) | br. | \(D’\) | \(\Delta D\) | \(s\) | br. | \(D’\) | \(\Delta D\) | |
| 2 | 3 | + | 0 | -2 | 0 | – | 4 | +2 |
| 4 | 0 | – | 6 | +2 | 2 | – | 2 | -2 |
| 6 | 1 | + | 4 | -2 | 0 | – | 10 | +4 |
| 8 | 0 | – | 12 | +4 | 1 | + | 6 | -2 |
| 10 | 2 | – | 4 | -6 | 0 | – | 16 | +6 |
| 12 | 0 | – | 18 | +6 | 3 | + | 2 | -10 |
| 14 | 1 | + | 10 | -4 | 0 | – | 22 | +8 |
| 16 | 0 | – | 24 | +8 | 1 | + | 12 | -4 |
| 18 | 4 | – | 2 | -16 | 0 | – | 28 | +10 |
| 20 | 0 | – | 30 | +10 | 2 | – | 8 | -12 |
Vérifs rapides : \(D=2\) : \((\,-\,)\Rightarrow Y_-=5\Rightarrow T(5)=1\Rightarrow D’=0\). \(D=2\) : \( (+)\Rightarrow Y_+=7\Rightarrow T(7)=11\Rightarrow D’=\frac{11+1}{3}=4\). \(D=10\) : \( (+)\Rightarrow D’=16\) (gonflement), \((\,-\,)\Rightarrow D’=4\) (contraction), etc.
5) Pseudocode (une couture)
# Entrée: D pair ≥ 0, branch in {'-','+'}
# Sortie: (branch_next, D_next, k)
d = D//2
S = (9*d - 1) if branch=='-' else (9*d + 2)
s = v2(S) # valuation 2-adique
y = S >> s # impair
branch_next = '-' if (s % 2 == 0) else '+'
D_next = ( (y+1)//3 ) if branch_next=='-' else ( (y-1)//3 )
k = s + 1 # ν₂(3y+1)
6) Figure (à remplacer par ton SVG)
Fichier source : importe le SVG dans la médiathèque puis remplace l’attribut
src.Remarque. Le choix « clip à 2 » dans \( \mathrm{clip}(k-2,\le 2) \) évite qu’un très grand \(k\) fasse artificiellement remonter le potentiel via le terme “crédits”. Avec \(\kappa=32,\ \gamma=0.8\), on obtient une baisse uniforme \( \Delta\Phi \le -0.18 \) au pire (\(k=1\)), et de plus en plus négative ensuite.
Modèle unifié : odd-only ↔ distance-only ↔ tape (suivi 2-adique relatif aux impairs)
0) Variables, notations, états
- Odd-only. État impair
y, pasT(y) = (3y+1)/2^{k^+}aveck^+ = ν_2(3y+1) ≥ 1. - Distance-only. Décomposition d’un impair en familles \(Y_-(D)=3D-1\), \(Y_+(D)=3D+1\), \(Y_0(D)=3D\) (ancre \(0\bmod 3\)), avec \(D \in 2\mathbb N\) pour \(Y_\pm\).
- Tape (ruban) : valeurs \( …, -3, 3, -2, 2, -1, 1 …\); transition “aller à l’index décalé de la valeur”. Fonction sur valeurs :
- \(v>0\) pair : \(F(v)=\frac{3v}{2}\).
- \(v>0\) impair : \(F(v)=-\frac{3v-1}{2}\) (une fois \(×\frac{3}{2}\) puis \(−1\), changement de signe).
- \(v<0\) pair : \(F(v)=\frac{v}{2}\) (halving en négatif).
- \(v<0\) impair : si \(v=-m\) (impair) alors \(F(v)=\frac{m+1}{2}>0\).
- Budgets 2-adiques relatifs (au même impair \(y\)) : \(k^+=ν_2(3y+1)\), \(k^-=ν_2(3y-1)\). Exactement l’un vaut 1, l’autre ≥2.
1) Pont exact odd-only ↔ distance-only bisimulation locale
Formules fermées (cas \(D=2d\))
- Si \(y=Y_-(D)=3D-1\) : \(3y+1 = 9D-2 = 2(9d-1)\). Poser \(s_-:=ν_2(9d-1)\), alors \(k^+=s_-+1\) et \(T(y)=Y_{\star}(D’)\) avec
- \(s_-\) pair ⇒ \(\star=-\), \(D’=(\frac{9d-1}{2^{s_-}}+1)/3\).
- \(s_-\) impair ⇒ \(\star=+\), \(D’=(\frac{9d-1}{2^{s_-}}-1)/3\).
- Si \(y=Y_+(D)=3D+1\) : \(3y+1 = 9D+4 = 2(9d+2)\). Poser \(s_+:=ν_2(9d+2)\), alors \(k^+=s_++1\) et \(T(y)=Y_{\star}(D’)\) avec
- \(s_+\) pair ⇒ \(\star=-\), \(D’=(\frac{9d+2}{2^{s_+}}+1)/3\).
- \(s_+\) impair ⇒ \(\star=+\), \(D’=(\frac{9d+2}{2^{s_+}}-1)/3\).
✓ Conclusion. Un pas odd-only est exactement un pas en distance-only sur \((\star,D)\). C’est une bisimulation locale (un-pour-un) hors ancre \(Y_0\).
2) Pont compressé odd-only ↔ tape K-simulation (K=2)
Compression “demi-pas négatif”
- De \(y>0\) impair (donc \(y\in Y_\pm\)) : un pas tape donne \(-m_0\) avec \(m_0=\frac{3y-1}{2}\).
- On compresse la chaîne de divisions par 2 négatives : poser \(s^-:=ν_2(m_0)\) et \(m^\star:=m_0/2^{s^-}\) (impair).
- Rebond positif unique : \(y_{\text{tape}}=\frac{m^\star+1}{2}\), qui tombe soit dans \(Y_+\), soit dans l’ancre \(Y_0\) selon la parité de \(s^-\).
En deux arêtes (“aller au négatif”, puis “bloc de halvings compressé & rebond”), on simule le pas impair de odd-only. La longueur du bloc de halvings \(s^-\) n’est pas bornée, mais il est comprimé en une seule arête. D’où une K-simulation avec K=2 (indépendant de \(y\)).
✓ Conclusion. Chaque pas odd-only se simule par ≤2 pas dans le graphe tape-compressé; réciproquement, tout 2-pas tape-compressé correspond à un pas odd-only (relation de simulation réciproque “à stuttering” sur \(Y_\pm\)).
3) Inégalité commune de contraction sur \(D\)
Pour les deux ponts précédents (odd-only et tape-compressé), on a la même forme d’encadrement :
\( D_{\text{next}} \le \frac{3}{2^{\kappa}}\,D + 1 \), avec \(\kappa = k^+\) (odd-only) ou \(\kappa = s^-+2\) (tape-compressé).
Elle alimente un potentiel unifié \(\displaystyle \Phi=\log_2(D+\kappa_0)+\gamma(\kappa-2)\) (par ex. \(\kappa_0=32\), \(\gamma=0.8\)), qui décroit strictement pas-à-pas sur \(Y_\pm\), et ne monte pas lors du “demi-pas” ancre \(Y_0\) si \(\kappa_0\) est assez grand.
4) Sur-approx odd-only → NFA cohérent B monotonicité de \(\mu_{\min}\)
- Injection de comportements. La projection \(\psi: y \mapsto (\alpha\bmod 64,\ \beta\bmod 3^b,\ C)\) envoie chaque pas minimal réel \(y\to T(y)\) (étiqueté \(k^+\)) sur une arête \(\psi(y)\to\psi(T(y))\) de \(B\). B peut contenir des arêtes en plus (sur-approx).
- Monotone. Si \(B\) vérifie \(\mu_{\min}(B)>\log_2 3\) (poids = \(k^+\)), alors \(\mu_{\min}(\text{odd-only})\ge \mu_{\min}(B)>\log_2 3\). Donc pas de cycle non trivial réel.
✓ Conclusion. Une borne stricte sur \(\mu_{\min}\) prouvée dans B vaut a fortiori pour la dynamique réelle.
5) Checklist de validation (à cocher)
- [ ] Égalité odd-only ↔ distance. Vérifier sur un échantillon dense que \(k^+=1+ν_2(9d\pm \text{const})\) et les formules \(D’\) ci-dessus coïncident avec \(T(y)\) pour \(Y_\pm\).
- [ ] Compression tape. Implémenter la “demi-arête négative compressée” : \(m_0=(3y-1)/2\), \(s^-=ν_2(m_0)\), \(m^\star=m_0/2^{s^-}\), \(y_{\rm tape}=(m^\star+1)/2\). Montrer : 2 pas tape-compressés = 1 pas odd-only.
- [ ] Contraction sur \(D\). Tester \(\;D_{\text{next}}\le \frac{3}{2^{\kappa}}D+1\;\) pour \(\kappa=k^+\) et \(\kappa=s^-+2\) jusqu’à une coupe haute \(D\le D_{\max}\), puis raisonner par structure sur \(d\mapsto 9d\pm c\).
- [ ] Potentiel \(\Phi\). Fixer \(\kappa_0=32,\ \gamma=0.8\); tracer \(\Delta\Phi\) vs \(k\) et \(s^-\); vérifier \(\Delta\Phi\le -\varepsilon\) (\(\varepsilon\approx 0.13\) à \(0.18\)) sur \(Y_\pm\); traiter \(Y_0\) comme étape neutre (non-croissante).
- [ ] Sur-approx B. Générer \(B\) (fenêtre \(b\)), vérifier l’inclusion des arêtes réelles, puis certifier \(\mu_{\min}(B)>\log_2 3\) (Howard/Karp). En conclure l’absence de cycle réel.
6) Figure
7) À retenir
- Bisimulation locale (odd-only ↔ distance) : pas-à-pas, même \(k^+\), mêmes \(D\to D’\).
- K-simulation compressée (odd-only ↔ tape) : un pas impair = 2 pas tape-compressés (indép. de \(y\)).
- Sur-approx NFA cohérent : prouver \(\mu_{\min}(B)>\log_2 3\) suffit pour la dynamique réelle.
- Potentiel unifié sur \(D\) et budgets 2-adiques : décroissance stricte hors ancre, neutre sur ancre.
No responses yet