🔢 mathematics

State Complexity of Shifts of the Fibonacci Word

Cet article démontre que la complexité en états de l'automate générant le mot de Fibonacci décalé d'une constante $c$ est de l'ordre de $O(\log c)$ , tant pour les représentations en base de Zeckendorf de poids faible que de poids fort, en utilisant une combinaison de techniques de complexité d'états et d'approximation diophantienne.

Auteurs originaux : Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic

Publié 2026-03-20

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.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

🧵 Le Fil d'Or et le Décalage Temporel : Une histoire de complexité

Imaginez que vous avez un fil infini (une séquence de chiffres 0 et 1) qui suit un motif très spécial, appelé le mot de Fibonacci. Ce motif est célèbre en mathématiques, un peu comme une mélodie parfaite qui ne se répète jamais exactement de la même manière, mais qui garde une structure très cohérente.

Les auteurs de ce papier se posent une question simple mais profonde :

« Si je prends ce fil infini et que je le décale de quelques centimètres (je commence à le lire un peu plus tard), est-ce que le "moteur" nécessaire pour générer ce nouveau fil devient beaucoup plus gros et compliqué ? »

En termes techniques, ils étudient la complexité en états (la taille du "moteur" ou automate) nécessaire pour produire ce fil décalé.

1. Le Problème : La machine à lire les nombres

Pour générer ce fil, on utilise une petite machine (un automate) qui lit un nombre (par exemple, la position 100 ou 1000) et sort le chiffre correspondant (0 ou 1).

Il existe deux façons de lire un nombre, comme deux manières différentes de lire un livre :

LSB-first (De la fin vers le début) : On lit les chiffres des unités, puis des dizaines, etc. (comme on écrit souvent les nombres en binaire).
MSB-first (Du début vers la fin) : On lit le chiffre le plus important en premier (comme on lit un livre de gauche à droite).

Dans la plupart des cas, si vous décalez votre séquence de $c$ positions, la machine devient énormément plus grosse. C'est comme si pour lire un livre décalé de 10 pages, vous deviez emporter un camion entier de livres de rechange.

2. La Surprise : La magie du nombre d'or

Les auteurs ont découvert quelque chose de miraculeux pour le mot de Fibonacci. Peu importe la taille du décalage $c$ (que ce soit 10, 1000 ou 1 milliard), la machine nécessaire pour lire le fil décalé reste très petite.

En fait, la taille de la machine ne grandit que très lentement, proportionnellement au logarithme de $c$ .

L'analogie : Imaginez que vous voulez déplacer une montagne. Pour la plupart des séquences, déplacer la montagne de 1 km nécessite un camion de 1 km de long. Pour le mot de Fibonacci, déplacer la montagne de 1 km ne nécessite qu'un petit chariot de 10 mètres, et même pour 1000 km, le chariot ne fait que 20 mètres !

C'est presque la taille minimale théoriquement possible pour une séquence qui ne se répète pas. C'est une économie d'énergie incroyable.

3. Comment ont-ils fait ? (Les outils de l'architecte)

Pour prouver cela, les chercheurs ont utilisé trois outils principaux, qu'on peut imaginer ainsi :

Le système de Zeckendorf (La règle spéciale) : Au lieu d'utiliser les chiffres classiques (0, 1, 2...), ils utilisent une règle spéciale basée sur les nombres de Fibonacci (1, 2, 3, 5, 8, 13...) pour écrire les nombres. C'est comme si on écrivait les nombres en utilisant uniquement des pièces de monnaie de valeurs spécifiques, sans jamais utiliser deux pièces de même valeur consécutivement.
L'approximation Diophantienne (La boussole géométrique) : Ils ont transformé le problème de lecture de chiffres en un problème de géométrie circulaire. Imaginez un cercle (comme une horloge). Chaque nombre correspond à un point sur ce cercle. Le mot de Fibonacci est généré en regardant si ce point tombe dans une zone "bleue" (sortie 1) ou "orange" (sortie 0).
- Quand on décale le fil, on déplace simplement la zone bleue/orange sur le cercle.
- La magie est que, grâce aux propriétés du nombre d'or ( $\phi$ ), ces zones restent très bien structurées, même après un grand décalage.
L'ordinateur comme juge (Walnut) : Une partie de la preuve a été faite par un logiciel appelé "Walnut". C'est comme un juge robot très strict qui vérifie des milliers de cas logiques pour s'assurer qu'aucune erreur ne s'est glissée dans le raisonnement.

4. Le Résultat Final

Que vous lisiez le fil de la fin vers le début (LSB) ou du début vers la fin (MSB), la conclusion est la même : le décalage ne rend pas la machine compliquée.

Pourquoi c'est important ? Cela montre que le mot de Fibonacci possède une structure mathématique d'une élégance et d'une stabilité rares. Même si on le perturbe (en le décalant), il reste "simple" à décrire.
L'analogie finale : C'est comme si le mot de Fibonacci était un cristal parfait. Si vous le déplacez légèrement, il ne se brise pas et ne devient pas désordonné ; il conserve sa forme cristalline, quelle que soit la distance du déplacement.

En résumé

Ce papier nous dit que le mot de Fibonacci est un "super-héros" de la complexité. Même quand on le décale de manière arbitraire, il ne nécessite pas de "super-ordinateur" pour être généré, mais seulement une petite machine intelligente, dont la taille croît très doucement. C'est une victoire de la structure mathématique sur la complexité apparente.

Titre : Complexité d'état des décalages du mot de Fibonacci

Auteurs : Delaram Moradi, Pierre Popoli, Jeffrey Shallit et Ingrid Vukusic.

1. Problématique

Le papier s'intéresse à la complexité d'état (le nombre d'états minimal requis) des automates finis déterministes avec sortie (DFAO) qui génèrent des séquences automatiques décalées. Plus précisément, les auteurs étudient le mot infini de Fibonacci $f = (f_i)_{i \ge 0}$ , une séquence célèbre en combinatoire sur les mots.

Le problème central est le suivant : si l'on connaît un automate à $m$ états générant la séquence de Fibonacci $f(i)$ , quelle est la complexité d'état de l'automate générant la séquence décalée $(f(i+c))_{i \ge 0}$ pour un entier $c$ donné ?

L'étude est menée sous deux formats d'entrée distincts :

LSD-first (Least Significant Digit first) : Lecture des chiffres de la représentation de l'entier $i$ du moins significatif au plus significatif.
MSD-first (Most Significant Digit first) : Lecture des chiffres du plus significatif au moins significatif.

Le défi spécifique réside dans le fait que le mot de Fibonacci est naturellement associé au système de numération de Zeckendorf (somme de nombres de Fibonacci non consécutifs), et non à une base entière classique. Contrairement aux bases entières, l'addition dans le système de Zeckendorf ne peut pas être effectuée par un transducteur déterministe en un seul passage, ce qui rend les techniques standards de décalage inapplicables.

2. Méthodologie

Les auteurs combinent plusieurs domaines mathématiques pour résoudre ce problème :

Théorie des automates et complexité d'état : Construction explicite d'automates et analyse de leur minimisation.
Approximation diophantienne : Utilisation des propriétés des nombres irrationnels, en particulier du nombre d'or $\phi = \frac{1+\sqrt{5}}{2}$ , et des parties fractionnaires $\{x\} = x \mod 1$ .
Logique et preuve automatique : Utilisation de l'outil de preuve automatique Walnut pour vérifier rigoureusement des propriétés de séquences automatiques via la logique du premier ordre.

Points clés de la méthode :

Caractérisation géométrique : Le papier repose sur un lemme fondamental (Lemme 1) établissant que $f(i) = 1$ si et seulement si $\{i\phi\} \in (-\phi, -2\phi) \mod 1$ . Pour le décalage $c$ , la condition devient $\{i\phi\} \in (-(c+1)\phi, -(c+2)\phi) \mod 1$ .
Partitions de l'intervalle $[0, 1)$ :
- Pour le cas LSD-first, les auteurs définissent une partition de $[0, 1)$ basée sur les chiffres de rang faible de la représentation de Zeckendorf. Ils montrent que les bits de poids faible de $i$ déterminent dans quel intervalle de la partition se trouve $\{i\phi\}$ .
- Pour le cas MSD-first, ils introduisent une partition cohérente avec la représentation de Zeckendorf, construite à partir des points $\{r_k\phi\}$ où $r_k$ sont des entiers négatifs dérivés de la représentation de $-(c+1)$ et $-(c+2)$ .
Construction d'automates :
- Les états de l'automate correspondent aux intervalles de ces partitions.
- La transition d'état correspond au passage d'un intervalle à un sous-intervalle lorsque l'on lit un nouveau chiffre (ajout d'un bit à droite pour MSD, ou lecture de bits de poids faible pour LSD).
- La fonction de sortie est déterminée par la position de l'intervalle par rapport à l'intervalle cible défini par le décalage $c$ .

3. Contributions Clés et Résultats

Résultat Principal :
Les auteurs prouvent que pour le mot de Fibonacci, la complexité d'état d'un automate générant la séquence décalée $(f(i+c))$ est $O(\log c)$ pour les deux formats d'entrée (LSD-first et MSD-first).

Théorème 1 (LSD-first) : Il existe un automate à $O(\log c)$ états. La preuve montre que l'automate n'a besoin de lire qu'un nombre logarithmique de bits (liés à la taille de $c$ dans la base de Fibonacci) pour déterminer si $\{i\phi\}$ tombe dans l'intervalle cible, après quoi il atteint un état puits (sink state).
Théorème 2 (Optimalité LSD) : Ils fournissent une formule exacte pour le nombre minimal d'états : $2(|(c)_F| + 1) + 1 - g(c)$ , où $|(c)_F|$ est la longueur de la représentation de Zeckendorf de $c$ . Cela confirme que la borne $O(\log c)$ est optimale.
Théorème 3 (MSD-first) : Contrairement à d'autres séquences (comme la séquence de Thue-Morse où la complexité peut être linéaire en $c$ ), le mot de Fibonacci permet une complexité logarithmique même en lecture MSD-first. La construction repose sur la cohérence de la partition $P(r)$ avec la représentation MSD.

Signification des résultats :

Efficacité exceptionnelle : Une croissance logarithmique $O(\log c)$ est proche du minimum théorique informationnel pour une séquence apériodique. Cela contraste fortement avec le cas général où le décalage peut entraîner une explosion exponentielle ou linéaire du nombre d'états.
Spécificité du mot de Fibonacci : Ce résultat met en lumière la structure mathématique profonde du mot de Fibonacci, liée à la propriété de Sturmian et à l'approximation diophantienne de $\phi$ , qui permet de "compresser" l'information nécessaire pour gérer le décalage.
Technique hybride : L'utilisation conjointe de l'approximation diophantienne et de la théorie des automates ouvre une nouvelle voie pour l'analyse de la complexité des opérations sur les séquences automatiques.

4. Conclusion et Perspectives

Le papier démontre que le mot de Fibonacci possède une robustesse remarquable face aux opérations de décalage, maintenant une complexité d'état très faible ( $O(\log c)$ ) indépendamment du sens de lecture des chiffres.

Les auteurs suggèrent que ces résultats pourraient être généralisés à d'autres nombres irrationnels quadratiques ou à d'autres mots infinis comme le mot de Tribonacci, bien que l'analyse soit plus complexe dans ces cas. Ils prévoient d'explorer ces généralisations dans des travaux futurs.

En résumé, ce travail établit une borne supérieure optimale pour la complexité des décalages du mot de Fibonacci, reliant élégamment la théorie des nombres, la combinatoire sur les mots et la théorie des automates.