Forum de mathématiques - Bibm@th.net

Eureka ! J'ai trouvé au moins une erreur :

Une de mes inégalités suppose qu'un pas réel correspond à une arête de l'automate. Cette correspondance est fausse.
* Le Pas Réel (Exemple : y=21)
   $y=21 \implies 3y+1 = 64$.
   La valuation est $u = \nu_2(64) = \mathbf{6}$.
   Le pas réel est $T(21) = 1$.
* Automate
   L' automate ne possède que des arêtes $\kappa=\mathbf{1}$ ou $\kappa=\mathbf{2}$.

L'automate ne peut pas représenter le pas réel u=6 avec une seule arête. La correspondance 1-pour-1 est rompue. L'inégalité de pont (Étape 1) et la sommation (Étape 4) qui en découlent sont donc invalides.

Étape 1 : [tex]r \to r'[/tex] (avec label [tex]\kappa[/tex]).
[tex]\Delta\log_2 y \le w_{\mathrm{aug}}(r \to r')[/tex]

Étape 4 :
[tex]
\sum_{i=0}^{m-1} \Delta\log_2 y_i \le \sum_{i=0}^{m-1} w_{\mathrm{aug}}(e_i)
[/tex]
[tex]
\sum_{i=0}^{m-1} w_{\mathrm{aug}}(e_i) \le \sum_{i=0}^{m-1} (\mu + \Delta h_i)
= \mu \cdot m + (h_{\text{fin}} - h_{\text{début}})
[/tex]

Non, pas une attaque sur ma personne, mais sur le fait qu'on puisse discuter, tout simplement. Je regardais justement pour les termes, pour moi aussi être constructif quant à ta réponse précédente. Comme j'ai "modélisé" (pour moi c'est un modèle, mais bon, j'entends ;)) en dehors de standard mathématique, les termes ne sont sans doute pas bons.

J'ai donc demandé à l'IA de faire un dictionnaire entre mon vocabulaire non standardisé, et celui plus mathématique. J'espère que ça t'aidera à mieux comprendre.

Dictionnaire des termes (définitions formelles + équivalents standards)

Cadre de base.

[tex]
T(y)=\frac{3y+1}{2^{\nu_2(3y+1)}},\qquad
\psi(y)=\frac{y+1}{2}=D,\qquad
y=2D-1.
[/tex]

Identités élémentaires :

[tex]
3y+1=2(3D-1),\qquad
T(y)=\mathrm{oddize}(3D-1),\qquad
\Sigma(D):=\frac{T(y)+1}{2}.
[/tex]

1) « Grille collée » = petit graphe à 2 nœuds par D (objet standard : graphe orienté)

Définition. On considère les nœuds

[tex]
\mathcal{V}:=\{\,L(D),\,M(D)\ :\ D\in\mathbb N\,\}.
[/tex]

et les arêtes

[tex]
L(D)\xrightarrow{\mathrm{LH}} M(D),
\qquad
M(D)\xrightarrow{\mathrm{SEAM}} L(\Sigma(D)).
[/tex]

Fait (simulation exacte en 2 pas).
Pour tout impair \(y=2D-1\),

[tex]
L(D)\ \xrightarrow{\mathrm{LH}}\ M(D)\ \xrightarrow{\mathrm{SEAM}}\ L(\Sigma(D))
[/tex]

réalise exactement le pas impair \(y\mapsto T(y)\) (aucune approximation).

Équivalent « vocabulaire standard » :
c’est un graphe orienté avec 2 états par \(D\) et 2 transitions étiquetées ;
“LH/SEAM” sont juste des noms d’arêtes.

2) « Mouvements atomiques » = arêtes élémentaires du graphe

Ce sont les deux transitions précédentes. Rien d’exotique : ce sont des arêtes.

3) « Automate fini de coutures » = automate déterministe sur[tex]
\mathbb{Z}/(3^b\mathbb{Z})
[/tex](DFA).
Pour \(b\ge 1\), on définit l’automate \(\Sigma_b=(Q,E)\) avec

[tex]
Q=\mathbb{Z}/(3^b\mathbb{Z}),\qquad
E=\Bigl\{\, r\ \xrightarrow{\ \kappa\ }\ r' \ :\ r'\equiv (3r-1)\,(2^\kappa)^{-1}\!\!\!\pmod{3^b},\ \ \kappa\in\{1,2\}\,\Bigr\}.
[/tex]

(Ici \(2^\kappa\) est inversible modulo \(3^b\), donc la transition est toujours bien définie.)

Interprétation :
on projette \(\psi(y_i)=D_i\) en résidus \(r_i\equiv D_i\pmod{3^b}\) ;
la couture \(\kappa\) encode la division par \(2^\kappa\) apparaissant dans \(T(y)\).

4) « Min–moyenne strictement négative » = min mean cycle (Karp)

On pondère chaque arête \(r\xrightarrow{\kappa} r'\) par

[tex]
w(r\!\to\!r')=\log_2 3 - \kappa
\quad\text{ou}\quad
w_{\mathrm{aug}}(r\!\to\!r')=\log_2 3 - \kappa + \delta(r),
[/tex]

avec

[tex]
\begin{aligned}
\delta(r)&:=\log_2\!\left(1+\frac{1}{3\,y_{\min}(r)}\right),\\
y_{\min}(r)&:=2D_{\min}(r)-1,\\
D_{\min}(r)&:=\min\{\,D\ge 1:\ D\equiv r\pmod{3^b}\,\}.
\end{aligned}
[/tex]

La min–moyenne (classique) est

[tex]
\mu^\star(b):=\min_{\text{cycles }C}\ \frac{1}{|C|}\sum_{e\in C} w(e).
[/tex]

Fait simple et algébrique :
il existe un cycle 1-nœud en \(r\equiv -1\ (\bmod 3^b)\) avec \(\kappa=2\), donc

[tex]
\mu^\star(b)\le \log_2 3 - 2<0,\qquad
\mu^\star_{\mathrm{aug}}(b)\le \log_2\!\left(\frac{5}{6}\right)<0
\quad(\text{tous }b\ge1).
[/tex]

5) « Inégalité de bloc » = inégalité de chemin issue de la dualité min–moyenne

Forme duale classique : pour tout \(\mu\ge \mu^\star(b)\), il existe un potentiel \(h:Q\to\mathbb{R}\) tel que

[tex]
h(r')-h(r)\ \le\ w_{\mathrm{aug}}(r\!\to\!r') - \mu
\qquad(\forall\ \text{arête }r\!\to\!r').
[/tex]

En sommant le long d’un bloc de \(m\) pas impairs \(y_0\to\cdots\to y_m\) (résidus \(r_i\)),
et en utilisant la simulation en 2 mouvements + \(S\) “coutures” (au moins une par pas), on obtient

[tex]
\sum_{i=0}^{m-1}\bigl(\log_2 y_{i+1}-\log_2 y_i\bigr)
\ \le\ \mu\,S\ -\ \bigl(h(r_m)-h(r_0)\bigr),
\qquad
S\ge m.
[/tex]

C’est précisément ce que nous appelons “inégalité de bloc”.

6) « Approche structurelle »

Cela signifie simplement que l’on **structure** l’itération en :

(i) un graphe explicite (la “grille à 2 nœuds par \(D\)”) ;

(ii) une projection sur un automate fini \(\Sigma_b\) où l’on sait certifier une dérive moyenne négative ;

(iii) un poussage de l’inégalité duale le long des blocs simulés.

Rien de “magique” : graphes finis, DFA, min–moyenne.

7) Version minimaliste (sans aucun surnom)

– Lemme (identité).
Pour tout \(y\) impair, en posant \(D=(y+1)/2\),
on a \(T(y)=\mathrm{oddize}(3D-1)\) et
\(\psi(T(y))=(\mathrm{oddize}(3D-1)+1)/2\).

– Graphe auxiliaire.
États \(\{L(D),M(D)\}\) et arêtes
\(L(D)\to M(D)\), \(M(D)\to L(\Sigma(D))\).

– Automate fini \(\Sigma_b\) sur \(\mathbb{Z}/(3^b\mathbb{Z})\).
Transitions \(r\to (3r-1)(2^\kappa)^{-1}\) pour \(\kappa\in\{1,2\}\).

– Poids.
\(w_{\mathrm{aug}}=\log_2 3-\kappa+\delta(r)\).
Min–moyenne \(\mu^\star\le \log_2(5/6)<0\) (cycle \(r\equiv-1\)).

– Inégalité duale.
\(\sum \Delta\log_2 y_i \le \mu\,S-\Delta h\) avec \(S\ge m\).

Edit : je galère quand même avec la mise en forme, malgré l'aide de l'IA ;) Tu me dis si je dois améliorer quelque chose, ce sera avec plaisir.

Oui ! Merci pour ton implication!

Fait exact
Pour tout impair y, pose D=(y+1)/2 (donc y=2D−1) et u:=ν_2(3y+1).
Alors
[tex]
3y+1=3(2D-1)+1=2(3D-1)
\quad\Rightarrow\quad
\nu_2(3y+1)=1+\nu_2(3D-1).
[/tex]
En particulier,
[tex]
T(y)=\frac{3y+1}{2^{\nu_2(3y+1)}}
=\frac{2(3D-1)}{2^{1+\nu_2(3D-1)}}
=\frac{3D-1}{2^{\nu_2(3D-1)}}
=\mathrm{oddize}(3D-1).
[/tex]

Lecture pratique.
Ton (2) s’écrit
[tex]
T(y)=(3D-1)\,2^{\,1-u}.
[/tex]
Comme T(y) est impair, l’unicité impose
[tex]
u-1=\nu_2(3D-1)\qquad(\text{donc }u=1+\nu_2(3D-1)).
[/tex]
Il n’y a donc pas “à compter” a posteriori les divisions par 2 : il suffit de
lire le nombre de zéros de fin dans l’écriture binaire de \(3D-1\).

Exemples (vérif).
y=13, D=7 : 3D−1=20=4·5 ⇒ u=1+2=3, T(y)=5. 
y=53, D=27 : 3D−1=80=16·5 ⇒ u=1+4=5, T(y)=5. 
y=149, D=75 : 3D−1=224=32·7 ⇒ u=1+5=6, T(y)=7.

Conclusion.
C’est une identité exacte valable pour tout y impair.
C’est précisément ce qui motive le ré-étiquetage \(y\leftrightarrow D\) et la
simulation en deux mouvements \(L(D)\to M(D)\to L(\Sigma(D))\).

Si ça peut être utile, quelques questions réponses qui aideront peut-être à mieux comprendre le propos, et peut-être aussi à mieux comprendre où il y a une erreur de raisonnement.

FAQ — Questions / Réponses

Q1. “Pourquoi une seule boucle négative suffit-elle pour conclure \(\mu^\star(b)<0\) ?”

R. Par définition,
[tex]
\mu^\star(b):=\min_{\text{cycles }C}\ \frac{1}{|C|}\sum_{e\in C}w(e).
[/tex]
Si l’on exhibe un cycle de moyenne \(m_C<0\), alors
[tex]
\mu^\star(b)\le m_C<0.
[/tex]
Ici, la boucle 1-nœud en \(r\equiv -1\pmod{3^b}\) (couture \(\kappa=2\)) donne
[tex]
\mu^\star(b)\le \log_2 3-2<0,\qquad
\mu^\star_{\mathrm{aug}}(b)\le \log_2\!\left(\frac{5}{6}\right)<0.
[/tex]
Analogie : pour prouver qu’une vallée descend sous 0 m, il suffit d’un point à -3 m ; pas besoin que toute la vallée soit sous le niveau de la mer.

Q2. “Alors, pourquoi des vérifications numériques en \(b\) ?”

R. On n’en a pas besoin pour la négativité : l’argument est algébrique et vaut pour tout \(b\ge 1\).
Les tests numériques ( \(b=1\)→\(14\) ) sont là pour :
• illustrer concrètement les valeurs ;
• extraire un potentiel dual \(h\) “réaliste” (utile pour estimer \(\operatorname{osc}(h)\)) ;
• montrer la stabilité empirique au-delà du minimum théorique.

Q3. “Comment passes-tu de \(\mu^\star<0\) à des propriétés globales sur les orbites ?”

R. Chaîne standard min–moyenne → inégalités duales → télescopage sur blocs simulés.
• Simulation : chaque pas impair \(y\mapsto T(y)\) se simule par \(L(D)\to M(D)\to L(\Sigma(D))\), avec \(D=(y+1)/2\).
• Comptage : si \(m\) est le nombre de pas impairs et \(S\) le nombre total de coutures,
[tex]
S\ge m
[/tex]
(détails en Q4).
• Terme “petit” :
[tex]
\delta(y_i)=\log_2\!\Bigl(1+\frac{1}{3y_i}\Bigr)
\le
\delta(r_i)=\log_2\!\Bigl(1+\frac{1}{3\,y_{\min}(r_i)}\Bigr),
[/tex]
car \(y_i\ge y_{\min}(r_i)\) par définition, et \(t\mapsto \log_2(1+1/t)\) est décroissante.
• Inégalité de bloc (dualité) : il existe \(h\) tel que, pour un bloc de \(m\) pas,
[tex]
\sum_{i=0}^{m-1}\bigl(\log_2 y_{i+1}-\log_2 y_i\bigr)
\ \le\ \mu^\star(b)\,S-\bigl(h(r_m)-h(r_0)\bigr).
[/tex]
Avec \(S\ge m\),
[tex]
\sum_{i=0}^{m-1}\Delta\log_2 y_i\ \le\ \mu^\star(b)\,m+\operatorname{osc}(h).
[/tex]
Conséquences : pas de cycle impair non trivial (somme et \(\Delta h\) nulles sur un cycle), et borne \(O(\log y_0)\) (voir Q6).

Q4. “Es-tu sûr que \(S\ge m\) pour tous les blocs (y compris les petits cas) ?”

R. Oui. Pour tout impair \(y\),
[tex]
3y+1=2(3D-1)\quad\Rightarrow\quad \nu_2(3y+1)\ge 1.
[/tex]
Deux implantations :
1) une SEAM par pas impair \(\Rightarrow S=m\) ;
2) décomposition en \(\kappa\in\{1,2\}\) \(\Rightarrow S=\sum \lceil \nu_i/2\rceil\ge m\).
Cas limites \(y=1\) (\(\nu=2\)) ou \(3D-1\) impair (\(\nu=1\)) respectent aussi \(S\ge m\).

Q5. “D’où vient la borne uniforme \(\log_2(5/6)\) ?”

R. Sur \(r\equiv -1\), on a une boucle \(\kappa=2\) et
[tex]
y_{\min}(-1)=2(3^b-1)-1=2\cdot 3^b-3\ge 3,
\quad
\delta(-1)\le \log_2\!\left(1+\frac{1}{9}\right)=\log_2\!\left(\frac{10}{9}\right).
[/tex]
Donc
[tex]
w_{\mathrm{aug}}\le \bigl(\log_2 3-2\bigr)+\log_2\!\left(\frac{10}{9}\right)
= \log_2\!\left(\frac{5}{6}\right)<0.
[/tex]
Ainsi \(\mu^\star_{\mathrm{aug}}(b)\le \log_2(5/6)<0\) pour tout \(b\).

Q6. “Comment obtiens-tu la borne \(O(\log y_0)\) sur le temps de vol impairs ?”

R. À partir de
[tex]
\sum_{i=0}^{m-1}\Delta\log_2 y_i\ \le\ \mu^\star(b)\,m+\operatorname{osc}(h),
[/tex]
en posant \(\varepsilon:=-\mu^\star(b)>0\),
[tex]
m(y_0;Y^\star)\ \le\ \left\lceil
\frac{\log_2(y_0/Y^\star)+\operatorname{osc}(h)}{\varepsilon}
\right\rceil.
[/tex]
En particulier, si \(h\equiv 0\) et en utilisant la borne uniforme,
[tex]
\varepsilon\ \ge\ -\log_2\!\left(\frac{5}{6}\right)
=\log_2\!\left(\frac{6}{5}\right)\approx 0.263.
[/tex]
Remarque : numériquement, on observe souvent \(\mu^\star\approx -0.415\) sur nos graphes (\(b=1\to 9\) puis \(9\to 14\)), ce qui donne une marge effective \(\varepsilon\approx 0.415\), plus forte que la garantie uniforme \(0.263\).

Q7. “Pourquoi travailler modulo \(3^b\) (et pas \(2^b\) ou autre) ?”

R.
• La dynamique est \(3D-1\) : mod \(3^b\) on a l’inversibilité de \(2\) (donc les divisions par \(2^\kappa\) sont bien définies) et la boucle cruciale \(r\equiv -1\) avec \((3r-1)/4\equiv r\). 
• Les valuations \(\nu_2(3D-1)\) sont naturellement “stratifiées” par les résidus mod \(3^b\). 
• Mod \(2^b\), \(3\) n’est pas inversible, ce qui casse la couture \((3r-1)\,(2^\kappa)^{-1}\). 
D’autres modules peuvent être étudiés, mais \(3^b\) capture exactement la structure arithmétique utilisée par la couture et la boucle négative.

Q8. “Les trajectoires peuvent monter avant de descendre. Est-ce un problème ?”

R. Non : l’inégalité de bloc contrôle la somme
[tex]
\sum_{i=0}^{m-1}\bigl(\log_2 y_{i+1}-\log_2 y_i\bigr),
[/tex]
donc la tendance nette sur \(m\) pas. Des hausses locales sont permises, mais sur des blocs suffisamment longs la dérive moyenne négative l’emporte (tant que \(\mu^\star<0\)).

Résumé.
— La boucle \(r\equiv -1\) force \(\mu^\star(b)<0\) pour tout \(b\) (fait algébrique, indépendant des tests). 
— Le pont “grille collée” \(\Rightarrow\) \(\Sigma_b\), le comptage \(S\ge m\) et \(\delta(y)\le\delta(r)\) permettent d’appliquer la dualité min–moyenne et d’en déduire : pas de cycle impair non trivial et borne \(O(\log y_0)\). 
— Les vérifications numériques ( \(b=1\to 14\)) illustrent et affinent la marge effective, sans être nécessaires à la preuve de la négativité uniforme.

Merci pour cette illustration, très clair !

Il trouve 0 avec un n négatif qui dépasse la borne. J'ai clairement expliqué qu'avec n négatif, pour trouver un impair plus petit ayant le même lien, il ne fallait pas dépasser la borne.
0 n'est pas un impair positif.

Bref, de toute façon cette formule n'est pas révolutionnaire, elle est juste plus "sophistiqué" que X4+1, ou -1 puis divisé par 4. L'intérêt étant peut-être par contre qu'on peut trouver un frère lointain sans iterrer (de préférence plus grand, car on ne connait pas la borne négative). A priori sans aucune utilité pour ton automate.

Merci pour ta réponse.  Il me semble qu'elle dépasse la cadre de la fonction dont je parlais, et de son utilisation. Je m'étais sans aucun doute mal exprimé quand je l'ai introduite la première fois, mea culpa. Je t'invite à prendre en considération le message en haut de cette page qui est certainement mieux cadré.

Sinon, intéressant ce que tu dis. Je vais voir comment ça s'intègre avec ma "preuve" (qui n'en est sans doute pas une, pour le moment je n'aurais que no-cycle, non divergente/borné, et donc par déduction de ces deux là, tend vers 1).

C'est un mariage arrangé ;)

Par ailleurs, 0 n'est pas impair.

Je te donne un court extrait de mon doc, ça explique peut-être mieux le contexte.

Exposant 2-adique.
Pour un entier $m\neq0$, $v_2(m)$ est le plus grand entier $e\ge0$ tel que $2^e\mid m$ (et $2^{e+1}\nmid m$).

Exemples : $v_2(12)=2$, $v_2(40)=3$, $v_2(1)=0$.

Itération de Collatz accélérée (sur impairs)
Pour les impairs $y\ge1$,
\[
f(y):=\frac{3y+1}{2^{v_2(3y+1)}}\in\mathbb N.
\]
On calcule $3y+1$, puis on divise par $2$ autant que possible pour revenir à un impair.

La famille $L_{x,n}$ : descendants et ancêtres.
Pour un impair $x$ et tout $n\in\mathbb Z$,
\[
L_{x,n}:=\frac{(3x+1)\,4^{\,n}-1}{3}.
\]

Descendants ($n\ge0$).
      $L_{x,0}=x$ et $L_{x,n+1}=4L_{x,n}+1$.
      Ainsi $x\to4x+1\to16x+5\to\cdots$.
      Pour $n\ge0$, $L_{x,n}$ est toujours impair.

Ancêtres ($n<0$).} Poser $p:=-n\ge1$. Alors
      \[
      L_{x,-p}=\frac{(3x+1)/4^{\,p}-1}{3}
      \]
      est un entier si et seulement si $4^{\,p}\mid(3x+1)$ (i.e. $v_2(3x+1)\ge 2p$). Dans ce cas,
      $L_{x,-p}$ s’obtient par $p$ fois l’inverse $y\mapsto(y-1)/4$ (pas forcément impair).

Exemples
Pour $x=5$ : $3x+1=16$,
\[
L_{5,0}=5,\quad L_{5,1}=21,\quad L_{5,2}=85,\qquad
L_{5,-1}=\frac{16/4-1}{3}=1,\quad L_{5,-2}=\frac{16/16-1}{3}=0.
\]

Formules fermées utiles : $L_{x,1}=4x+1$, $L_{x,2}=16x+5$.

Fratrie (au sens large)
La fratrie de $x$ est $\{\,L_{x,n}\in\mathbb Z:\ n\in\mathbb Z\,\}$ :
$n\ge0$ donne les descendants ($y\mapsto4y+1$), $n\le0$ (quand défini) les ancêtres ($y\mapsto(y-1)/4$).

Racines minimales
Un impair $r$ est minimal s’il n’existe pas d’impair $s<r$ et $n\ge1$ tels que $r=L_{s,n}$.
Intuition : $r$ n’est pas un descendant (via $y\mapsto4y+1$) d’un plus petit impair.

Deux tests rapides (nécessaires) pour repérer des non-minimales.

Si $r\equiv1\pmod 4$, alors $r=4s+1=L_{s,1}$ avec $s=(r-1)/4<r$ : $r$ n’est pas minimale.
Si $v_2(3r+1)\ge3$, alors $r$ est non minimale.

Être $\equiv3\pmod4$ est donc nécessaire (mais pas suffisant) pour être minimal.