Mahler equations for Zeckendorf numeration

1. Problématique et Contexte

Ce travail s'inscrit dans le domaine de la théorie des nombres, de la combinatoire des mots et de la théorie des automates. Il vise à établir un lien fondamental entre deux concepts :

1. La régularité des suites (Regular Sequences) : Généralisation des suites automatiques introduite par Allouche et Shallit. Une suite est dite $U$-régulière si elle peut être générée par un automate pondéré (weighted automaton) lisant la représentation des entiers dans un système de numération $U$.
2. Les équations de Mahler : Équations fonctionnelles de la forme $P(x, y) = \sum A_i(x) \Phi^i(y) = 0$, où $\Phi$ est un opérateur linéaire agissant sur les séries formelles.

Le problème central :
Le théorème de Christol caractérise les suites automatiques (sur un corps fini) comme les coefficients de séries algébriques. Becker et Dumas ont généralisé ce résultat aux suites $k$-régulières (pour la base $k$) en montrant qu'elles sont solutions d'équations $k$-Mahler isolantes (où le coefficient de $y$ est 1).
Cependant, ces résultats reposent sur la propriété clé de la base $k$ : l'ajout d'un zéro à la fin de la représentation d'un entier $n$ correspond à la multiplication par $k$ ($n \mapsto kn$). Cette propriété de linéarité permet d'utiliser les opérateurs de Cartier.

Les auteurs s'intéressent au système de numération de Zeckendorf ($Z$), basé sur les nombres de Fibonacci ($F_n$), où chaque entier est représenté de manière unique comme somme de nombres de Fibonacci non consécutifs. Dans ce système, l'opération analogue à « ajouter un zéro » (décalage) n'est pas une multiplication par une constante, mais une application non linéaire $\phi$. La question est de savoir si l'équivalence entre suites $Z$-régulières et solutions d'équations de Mahler adaptées (Z-Mahler) persiste malgré cette non-linéarité.

2. Méthodologie

Les auteurs développent une approche constructive combinant la théorie des automates pondérés et l'analyse de la structure arithmétique du système de Zeckendorf.

A. Définition de l'opérateur $\Phi$ et des équations Z-Mahler

Ils définissent un opérateur linéaire $\Phi : R[[x]] \to R[[x]]$ adapté à la numération de Zeckendorf :
$$\Phi\left(\sum_{n \ge 0} f_n x^n\right) = \sum_{n \ge 0} f_n x^{\phi(n)}$$
où $\phi(n)$ est l'entier obtenu en décalant la représentation de Zeckendorf de $n$ d'un cran vers la gauche (équivalent à $n \mapsto \lfloor n\varphi \rfloor$ ou similaire, lié à la relation $F_{k+1}$).
Une équation Z-Mahler est une équation de la forme :
$$P(x, y) = \sum_{i=0}^d A_i(x) \Phi^i(y) = 0$$
Elle est dite isolante si $A_0(x) = 1$.

B. Gestion de la non-linéarité de $\phi$

Le principal obstacle est que $\phi$ n'est pas linéaire : $\phi(m+n) \neq \phi(m) + \phi(n)$ en général. Cependant, les auteurs montrent que le défaut de linéarité $\delta(m, n) = \phi(m+n) - \phi(m) - \phi(n)$ est borné (il appartient à $\{-1, 0, 1\}$).
Ils démontrent que ce défaut de linéarité est calculable par un automate déterministe. Plus précisément, ils construisent un automate qui, étant donné les représentations de $m$ et $n$, calcule $\delta(m-n, n)$.

C. Construction d'automates universels

Pour prouver que les solutions d'équations Z-Mahler isolantes sont $Z$-régulières, ils construisent explicitement un automate pondéré universel.

• Contrairement au cas $k$-adique où l'automate est simple, ici l'état de l'automate doit mémoriser non seulement l'indice de récurrence et le degré du polynôme, mais aussi une information sur le défaut de linéarité accumulé.
• L'état est de la forme $(i, j, q, u)$, où $q$ est un état de l'automate calculant le défaut de linéarité et $u$ est un mot de longueur fixe servant de tampon pour le calcul.

3. Contributions Clés et Résultats Principaux

Résultat Principal (Théorème 1)

Soit $R$ un anneau commutatif et $P(x, y) = 0$ une équation Z-Mahler isolante. Si $f(x) = \sum f_n x^n$ est une solution de cette équation, alors la suite $(f_n)_{n \ge 0}$ est $Z$-régulière.
Cela signifie qu'il existe un automate pondéré qui, en lisant la représentation de Zeckendorf de $n$, produit le coefficient $f_n$.

Construction d'Automates Universels (Théorème 2 et 14)

Les auteurs proposent une construction directe d'automates pondérés pour les équations $k$-Mahler (cas classique) et Z-Mahler (cas généralisé).

• Ils introduisent un automate pondéré universel dont les poids sont déterminés par les coefficients de l'équation de Mahler.
• Cette construction évite l'utilisation des opérateurs de Cartier (qui échouent dans le cas de Zeckendorf) et fournit une preuve constructive de la régularité.
• Ils bornent le nombre d'états de l'automate en fonction de l'exposant $d$ et de la hauteur $h$ de l'équation, ainsi que du nombre d'or $\varphi$.

Converse (Corollaire 34)

Toute suite $Z$-régulière est solution d'une équation Z-Mahler (potentiellement non isolante). Cela établit une correspondance complète entre les deux notions, sous réserve de la condition d'isolation pour la direction inverse.

Contre-exemple et Nécessité de l'Isolation (Proposition 38)

Les auteurs montrent que la condition d'équation isolante est cruciale. Ils présentent un exemple d'équation Z-Mahler non isolante :
$$(1-x)f(x) = \Phi(f(x))$$
La solution de cette équation a des coefficients qui croissent trop vite (super-polynomialement) pour être générés par un automate pondéré fini (selon le lemme de croissance des suites régulières). Ainsi, sans l'hypothèse d'isolation, la régularité n'est pas garantie.

4. Signification et Implications

• Généralisation du théorème de Christol : Ce papier étend le pont entre l'algèbre (séries solutions d'équations fonctionnelles) et l'informatique théorique (automates pondérés) au-delà des bases entières classiques, vers les systèmes de numération de Pisot, en particulier Zeckendorf.
• Nouvelle méthode de preuve : En remplaçant les opérateurs de Cartier par la construction d'automates calculant le défaut de linéarité, les auteurs ouvrent la voie à l'analyse d'autres systèmes de numération où la multiplication par la base n'est pas triviale.
• Structure des automates : La découverte que les automates générant des suites régulières peuvent être vus comme des instanciations d'un automate universel offre une perspective structurelle unifiée.
• Limites et Ouvertures : Le papier soulève des questions sur la caractérisation complète des suites $Z$-régulières (sans hypothèse d'isolation) et sur l'extension de ces résultats à d'autres systèmes de Pisot. Il mentionne également l'absence actuelle d'exemple de suite $Z$-régulière qui ne serait pas solution d'une équation Z-Mahler isolante (contrairement au cas $k$-adique où de tels exemples existent).

En résumé, ce travail réussit à surmonter la non-linéarité intrinsèque de la numération de Zeckendorf pour établir une théorie cohérente des équations de Mahler et de la régularité, enrichissant ainsi la compréhension des liens entre arithmétique, automates et équations fonctionnelles.