Cobham's theorem for the Gaussian integers

Résumé Technique : Le Théorème de Cobham pour les Entiers de Gauss

Énoncé du Problème
Le théorème de Cobham est un résultat fondamental dans la théorie des automates et la théorie des nombres, stipulant qu'une suite de nombres naturels est à la fois $k$-automatique et $\ell$-automatique (où $k$ et $\ell$ sont des entiers multiplicativement indépendants) si et seulement si la suite est éventuellement périodique. Bien que ce théorème ait été généralisé à divers contextes logiques et dynamiques, une lacune importante subsistait dans son extension des entiers $\mathbb{Z}$ aux domaines euclidiens, spécifiquement aux entiers de Gauss $\mathbb{Z}[i]$.

Des travaux antérieurs par Hansel et Safer ont abordé les systèmes de numération en base $\alpha = -m + i$ (où $m \ge 1$) avec des ensembles de chiffres d'entiers non négatifs. Ils ont démontré que si un sous-ensemble $S \subset \mathbb{Z}[i]$ est reconnaissable par deux bases de ce type, l'ensemble est syndétique. Ils ont conjecturé qu'un tel ensemble doit être éventuellement périodique (c'est-à-dire invariant par translation par deux vecteurs $\mathbb{Z}$-linéairement indépendants en dehors d'un ensemble fini). Cependant, leur preuve reposait sur la Conjecture des Quatre Exponentielles, une hypothèse profonde et non prouvée de la théorie analytique des nombres, laissant la conjecture non résolue.

Méthodologie
Les auteurs fournissent une preuve du théorème de Cobham pour les entiers de Gauss qui ne dépend pas de la Conjecture des Quatre Exponentielles. Leur approche généralise le théorème à la plus grande famille possible de numérations gaussiennes (tout ensemble de chiffres générateur fini) et supprime la dépendance à la théorie analytique profonde des nombres.

La méthodologie centrale implique :

1. Approximation de Dirichlet dans $\mathbb{Z}[i]$ : Au lieu de s'appuyer sur la densité du groupe multiplicatif $\langle \alpha, \beta \rangle$ dans $\mathbb{C}$ (ce qui nécessite la Conjecture des Quatre Exponentielles), les auteurs utilisent un résultat plus faible : $1$ n'est pas un point isolé dans le groupe multiplicatif généré par deux entiers de Gauss multiplicativement indépendants. Ceci est établi via le Lemme 3, qui prouve que si $1$ était isolé, le groupe serait discret, impliquant une dépendance multiplicative.
2. Lemme de pompage et nombres de retour : Les auteurs analysent la structure des automates à états finis (DFAO) agissant sur les expansions d'entiers gaussiens. Ils définissent des « nombres de retour » à des états spécifiques de l'automate. En appliquant le théorème de van der Waerden aux états des automates, ils identifient des progressions arithmétiques d'indices correspondant aux nombres de retour.
3. Analyse de colinéarité : Une étape critique implique le Lemme 14, qui démontre que si une séquence de nombres de retour est située sur une droite (est colinéaire), la base doit être une racine d'un entier. Par conséquent, si la base n'est pas une racine d'un entier, les nombres de retour doivent être non colinéaires. Cela permet la construction de deux périodes $\mathbb{Z}$-linéairement indépendantes.
4. Propagation de la périodicité : En utilisant une version du théorème de Fine et Wilf adaptée aux entiers de Gauss (Lemmes 18 et 19), les auteurs montrent que la périodicité locale (périodicité par étapes) sur des boules se chevauchantes peut être propagée à une périodicité globale. Ils construisent un recouvrement de $\mathbb{Z}[i]$ par des boules où la configuration présente des périodes spécifiques dérivées des nombres de retour non colinéaires.

Contributions Clés et Résultats
Le résultat principal est le Théorème 1, qui stipule :

Soient $\alpha$ et $\beta$ deux entiers de Gauss multiplicativement indépendants avec $|\alpha|, |\beta| > 1$. Si l'un de $\alpha$ ou $\beta$ n'est pas la racine d'un entier, alors une configuration $(a_z)_{z \in \mathbb{Z}[i]}$ est $\alpha$- et $\beta$-automatique si et seulement si elle est éventuellement périodique.

Principaux résultats techniques :

• Résolution de la Conjecture de Hansel et Safer : L'article prouve la conjecture selon laquelle les ensembles reconnaissables par des bases de la forme $-m+i$ sont éventuellement périodiques. Puisque $-m+i$ n'est jamais une racine d'un entier pour $m > 1$ (par le théorème de Niven), la condition du Théorème 1 est satisfaite.
• Nécessité de la Condition : Les auteurs montrent que la condition « une base n'est pas une racine d'un entier » est stricte. Si les deux bases sont des racines d'entiers, des configurations non éventuellement périodiques peuvent exister (par exemple, la fonction caractéristique de $\mathbb{N}$ est $\alpha$-automatique si $\alpha$ est une racine d'un entier).
• Généralisation des Systèmes de Numération : La preuve est valable pour tout ensemble de chiffres fini $D$ qui génère un système de numération, et non seulement pour les ensembles de chiffres « naturels » d'entiers non négatifs considérés par Hansel et Safer.
• Corollaire sur la Conjugaison : L'article établit que si un ensemble $U \subset \mathbb{Z}[i]$ est $\beta$-automatique et égal à son conjugué complexe ($U = \bar{U}$), et n'est pas éventuellement périodique, alors $\beta$ doit être une racine d'un entier.

Signification
L'article affirme régler l'extension du théorème de Cobham aux entiers de Gauss sans dépendre de conjectures analytiques non prouvées. En démontrant que le résultat tient sur la base de propriétés élémentaires des automates et de la géométrie des entiers de Gauss (spécifiquement la non-isolation de $1$ dans le groupe multiplicatif), les auteurs « ouvrent la voie à Cobham pour les anneaux de nombres généraux ».

Le travail généralise le théorème de Cobham-Semenov aux numérations gaussiennes. Il se connecte également aux travaux de Cabezas et Petite sur les substitutions à forme constante, impliquant que des configurations non triviales générées par des bases gaussiennes qui ne sont pas des racines d'entiers ne peuvent pas être reproduites par des configurations $(k, k)$-automatiques standards. Les auteurs notent que bien qu'il s'agisse d'une première étape, l'extension à d'autres anneaux d'entiers (tels que $\mathbb{Z}[\zeta]$ ou les anneaux d'entiers quadratiques) reste une direction naturelle pour des recherches futures.