🔢 mathematics

Superlinear complexity of the $(3/2)^n$ steering word

Cet article prouve que la complexité des sous-mots du mot de pilotage généré par l'application $(3/2)^n$ est superlinéaire, un résultat établi à l'aide du théorème de l'espace vectoriel (Subspace Theorem) et entièrement formalisé dans Lean-4.

Auteurs originaux : Ralf Stephan

Publié 2026-07-14

📖 5 min de lecture🧠 Analyse approfondie

CC0 1.0

Auteurs originaux : Ralf Stephan

Article original placé dans le domaine public sous CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez une machine magique qui prend un nombre, le multiplie par 1,5, puis l'arrondit à l'entier le plus proche. Imaginez maintenant que vous fassiez passer cette machine de nombreuses fois, en partant du nombre 1.

1 devient 1,5, ce qui s'arrondit à 2.
2 devient 3, ce qui reste 3.
3 devient 4,5, ce qui s'arrondit à 5.
5 devient 7,5, ce qui s'arrondit à 8.

Cela crée une séquence de nombres entiers : 1, 2, 2, 3, 5, 8, et ainsi de suite. Mais le papier ne s'intéresse pas seulement aux nombres eux-mêmes ; il s'intéresse au « volant de direction » qui indique à la machine comment elle y est parvenue. À chaque étape, la machine a dû choisir d'arrondir à l'entier supérieur ou inférieur pour atteindre l'entier le plus proche. En assemblant toutes ces petites décisions, on obtient un long « mot de direction » infini.

La grande question posée par le papier est la suivante : Quelle est la complexité de ce code ?

Dans le monde des motifs, certains codes sont d'une simplicité ennuyeuse. Pensez à une chanson qui répète simplement « la-la-la » éternellement. C'est un motif simple. D'autres codes sont chaotiques et désordonnés, comme les parasites sur une radio. Les mathématiciens mesurent cette « désordonnance » en comptant combien de morceaux uniques (ou « sous-mots ») d'une certaine longueur existent dans le code. Si un code est simple, le nombre de morceaux uniques croît lentement (comme une ligne droite). S'il est complexe, le nombre de morceaux uniques explose.

La découverte principale
Le papier prouve que ce mot de direction est extrêmement complexe. Il ne se contente pas de croître selon une ligne droite ; il croît de manière « superlinéaire ». Cela signifie qu'à mesure que l'on observe des morceaux de plus en plus longs du code, le nombre de motifs uniques que l'on trouve augmente de plus en plus vite, s'envolant vers l'infini.

Pour le dire de façon ludique : si vous essayiez de prédire le prochain mouvement de cette séquence en regardant le passé, vous finiriez par heurter un mur. Peu importe la longueur du motif que vous trouvez, la séquence finira par faire quelque chose de complètement nouveau que vous n'avez jamais vu auparavant. Elle refuse de se stabiliser dans une boucle.

Ce que le papier exclut
Le papier exclut explicitement l'idée que cette séquence soit « périodique à terme ». En langage courant, cela signifie que la séquence ne sera jamais prise dans un cycle répétitif comme un disque rayé. Elle ne commencera jamais à dire « 1, 2, 3, 1, 2, 3 » pour toujours. Les auteurs prouvent que peu importe jusqu'où vous allez dans la séquence, vous ne trouverez jamais de point où elle répète simplement le même motif encore et encore.

À quel point en sont-ils sûrs ?
Les auteurs ne font pas que deviner ou simuler cela sur un ordinateur. Ils l'ont prouvé.

Ils ont construit une forteresse de logique en utilisant deux outils mathématiques puissants (les théorèmes de Corvaja–Zannier et de Nair–Kumar–Rout) qui agissent comme des verrous incassables. Ils ont également fait quelque chose de très spécial : ils ont traduit l'intégralité de leur preuve dans un langage informatique appelé Lean-4. Cet ordinateur a vérifié chaque étape de leur logique pour s'assurer qu'il n'y avait pas d'erreurs humaines. L'ordinateur a dit : « Oui, cette preuve est valide. »

Le parcours de la preuve
La preuve se déroule en trois étapes, comme l'ascension d'une montagne :

Étape 0 (La fondation) : Ils ont d'abord montré que si la séquence répétait un long motif, elle briserait les lois des mathématiques (plus précisément, elle créerait une impossibilité mathématique impliquant la division des nombres). Cela a prouvé que la séquence n'est pas une boucle simple et a déjà montré qu'elle était plus complexe que le motif non-bouclant le plus simple possible.
Étape 1 (La réduction) : Ils ont réalisé que pour prouver que la séquence est très complexe, ils n'avaient qu'à prouver une chose spécifique : que les nombres de la séquence ne sont pas « trop proches » les uns des autres trop souvent. S'ils restaient éloignés, le code serait forcé d'être désordonné et complexe.
Étape 2 (Le sommet) : Ils ont utilisé ces outils mathématiques puissants pour prouver que les nombres restent effectivement éloignés les uns des autres. Ils ont divisé le problème en trois zones :
- La zone des petits écarts : Quand les nombres sont proches les uns des autres dans la séquence.
- La zone des grands écarts : Quand les nombres sont très éloignés les uns des autres dans la séquence.
- La zone intermédiaire : La zone délicate entre les deux.

Pour les deux premières zones, ils ont utilisé un théorème puissant. Pour la zone intermédiaire, ils ont utilisé une astuce ingénieuse (une « dichotomie ») qui montrait que si le motif tentait d'être simple, cela mènerait à une contradiction (comme prouver qu'une fraction est en réalité un nombre entier, ce qui est impossible).

L'essentiel
Le mot de direction pour la séquence (3/2) est un chef-d'œuvre chaotique et non répétitif. Il est si complexe que le nombre de motifs uniques qu'il contient croît plus vite que n'importe quelle ligne droite. Ce n'est pas une suggestion ou une simulation, c'est un fait mathématiquement prouvé, vérifié par un ordinateur, montrant que cette règle apparemment simple génère une danse de nombres infiniment complexe.

Résumé Technique : Complexité Superlinéaire du Mot de Pilotage $(3/2)^n$

Énoncé du Problème
L'article étudie la dynamique symbolique générée par l'orbite du nombre 1 sous l'application $x \mapsto \frac{3}{2}x$ , en se concentrant spécifiquement sur la séquence des erreurs d'arrondi à l'entier le plus proche. Bien que la distribution de la séquence $\|(\frac{3}{2})^n\|$ (distance à l'entier le plus proche) soit un problème ouvert de longue date en théorie des nombres, ce travail déplace l'attention vers le « mot de pilotage » (steering word) $T = (t_n)_{n \geq 0}$ . Ce mot enregistre les translatés entiers sélectionnés à chaque étape de la dynamique autonome, définie par $t_n = 2m_{n+1} - 3m_n$ , où $m_n = \text{round}((\frac{3}{2})^n)$ . La question centrale abordée est la complexité de sous-mots $p_T(k)$ , qui compte le nombre de facteurs distincts de longueur $k$ dans $T$ . L'objectif de l'article est de prouver que cette complexité est superlinéaire, c'est-à-dire $\lim_{k \to \infty} p_T(k)/k = \infty$ .

Méthodologie
La stratégie de preuve est structurée en trois étapes distinctes, transférant les méthodes de l'étude de la complexité des nombres algébriques (spécifiquement la méthode d'Adamczewski–Bugeaud) à ce cadre dynamique. L'argument repose fortement sur le Théorème des Sous-Espaces et est noté comme étant entièrement formalisé en Lean-4.

Étape 0 : Identités Exactes et Bornes Inconditionnelles (Sections 2)
L'auteur dérive une « identité de répétition » exacte. Si un facteur de longueur $k$ se répète aux positions $a$ et $c$ ( $a < c$ ), cela impose la relation $3^k(\varepsilon_c - \varepsilon_a) = 2^k(\varepsilon_{c+k} - \varepsilon_{a+k})$ , où $\varepsilon_n$ est l'erreur d'arrondi.
- Cette identité produit une condition de divisibilité : $2^k \mid (m_c - m_a)$ .
- Combinée aux propriétés de croissance de l'orbite, cela établit que de longues répétitions ne peuvent pas se produire arbitrairement tardivement dans le mot.
- Résultat Inconditionnel : L'article prouve que $T$ n'est pas périodique à partir d'un certain rang et établit une borne inférieure linéaire $p_T(k) \geq \frac{41}{24}k - 3$ , ce qui est strictement supérieur au plancher de Morse–Hedlund ( $k+1$ ) pour les mots apériodiques.
Étape 1 : Réduction à un Noyau Diophantien (Section 3)
Le problème de la preuve de la complexité superlinéaire est réduit à une unique proposition diophantienne, appelée le Noyau (K).
- Énoncé (K) : Pour tout rationnel $\theta \in (0, 1)$ , l'ensemble des paires $(a, c)$ avec $2 \leq a < c$ satisfaisant $\|(\frac{3}{2})^c - (\frac{3}{2})^a\| \leq \theta^c$ est fini.
- Cela représente une propriété de « répulsion exponentielle des paires », améliorant la borne inférieure triviale de la distance entre les points de l'orbite de base $2^{-1}$ à une base arbitraire $\theta < 1$ .
- La réduction montre que si (K) est vérifié, alors $p_T(k)/k \to \infty$ .
Étape 2 : Établissement du Noyau (Sections 4 & 5)
La preuve de (K) est réalisée en partitionnant l'ensemble des solutions potentielles en trois « tranches » et en appliquant des résultats profonds de l'approximation diophantienne :
- Tranche à Écart Borné : Pour des écarts $c-a$ fixés, la finitude est prouvée en utilisant le Théorème Principal de Corvaja–Zannier (une conséquence du Théorème des Sous-Espaces de Schmidt).
- Tranche à Écart Immense : Pour la région où $a \leq \epsilon' c$ , la finitude est également établie via le théorème de Corvaja–Zannier en traitant le problème comme un cas spécifique d'exclusion de pseudo-Pisot.
- Bande Intermédiaire : Pour la région restante où les écarts croissent mais où $a$ n'est pas négligeable par rapport à $c$ , l'auteur emploie une dichotomie d'écart. Si l'ensemble des solutions était infini, on pourrait extraire une sous-famille avec des écarts distincts. Cela conduit à une contradiction via le théorème des $S$ -unit tuples de Nair–Kumar–Rout, ce qui impliquerait que $(\frac{3}{2})^c$ est un entier pour un certain $c$ , ce qui est impossible.

Contributions Principales et Résultats

Théorème Principal (Théorème 1.1) : La complexité de sous-mots du mot de pilotage $T$ est superlinéaire ( $p_T(k)/k \to \infty$ ).
Borne Inférieure Inconditionnelle : L'article fournit une borne inférieure linéaire explicite et inconditionnelle $p_T(k) \geq \frac{41}{24}k - 3$ , dérivée sans dépendre de conjectures non prouvées.
Formalisation : L'argument entier est formalisé en Lean-4. La formalisation dépend uniquement du Théorème des Sous-Espaces d'Evertse–Schlickewei en 3 variables, confirmant ainsi la validité des dépendances vis-à-vis des résultats de Corvaja–Zannier et de Nair–Kumar–Rout.
Apériodicité : Une preuve rigoureuse que le mot de pilotage n'est pas périodique à partir d'un certain rang.

Signification et Revendications
L'article prétend résoudre la question de la complexité pour ce système dynamique autonome spécifique en jetant un pont entre la dynamique symbolique et l'approximation diophantienne.

Transfert Méthodologique : Il adapte avec succès la méthode d'Adamczewski–Bugeaud, typiquement utilisée pour les nombres algébriques, à un mot dynamique. L'auteur note que la nature autonome de la dynamique $(3/2)$ simplifie la gestion comptable, permettant aux facteurs répétés de se compresser en inégalités diophantiennes nettes sans ancrage de préfixe.
Dépendance à des Théorèmes Profonds : La preuve de la superlinéarité est conditionnelle au théorème de Corvaja–Zannier (revu par les pairs) et au théorème de Nair–Kumar–Rout (un preprint au moment de la rédaction). Cependant, la formalisation en Lean-4 sert de vérification que ces dépendances sont des conséquences logiques saines du Théorème des Sous-Espaces.
Limites : Les résultats concernant la croissance superlinéaire sont ineffectifs ; le Théorème des Sous-Espaces ne fournit pas de bornes explicites sur la taille des ensembles exceptionnels (le nombre de solutions aux inégalités diophantiennes). L'article ne prétend pas résoudre le problème ouvert plus large concernant la densité de $\|(\frac{3}{2})^n\| \to 0$ , mais caractérise plutôt la complexité combinatoire de la séquence d'arrondi.

Articles similaires