Balanced Fibonacci word rectangles, and beyond

1. Problématique

L'article s'intéresse à la propriété d'équilibre (balance) des rectangles de mots infinis. Plus précisément, étant donné une suite infinie $(a_i)_{i \ge 0}$ sur un alphabet (généralement $\{0, 1\}$), on définit une matrice infinie $A$ où l'entrée $a_{k,\ell} = a_{k+\ell}$. Les sous-matrices $m \times n$ de cette matrice, notées $A(i, m, n)$, sont considérées comme des « rectangles de mots » décalés.

Le problème central est de déterminer pour quelles paires d'entiers naturels $(m, n)$ ces rectangles sont équilibrés. Un rectangle est dit équilibré si, pour toutes les positions de départ $i$, le nombre d'occurrences d'un symbole donné (la somme des entrées pour les mots binaires) dans le rectangle $A(i, m, n)$ ne prend qu'un nombre restreint de valeurs distinctes (généralement au plus deux valeurs distinctes pour les mots binaires).

L'article se concentre initialement sur le mot de Fibonacci infini, mais généralise ensuite la question aux mots de Sturmian, au mot de Tribonacci et au mot de Thue-Morse.

2. Méthodologie

Les auteurs utilisent une approche combinant la théorie des automates finis, la logique du premier ordre et l'arithmétique des systèmes de numération non standards.

• Critère de l'équilibre : Pour les mots de Sturmian (associés à un nombre irrationnel $\alpha$), les auteurs démontrent que l'équilibre des rectangles $m \times n$ dépend de la séquence des différences $\Delta(i, m, n) = T(i+1, m, n) - T(i, m, n)$. Le couple $(m, n)$ est équilibré si et seulement si la séquence $\Delta$ ne contient pas de blocs de la forme $1, 0, \dots, 0, 1$ ou $-1, 0, \dots, 0, -1$.
• Systèmes de numération : Pour traiter les nombres entiers en entrée des automates, les auteurs utilisent le système de numération d'Ostrowski (basé sur la représentation de $\alpha$). Pour le mot de Fibonacci, c'est le système de Zeckendorf (somme de nombres de Fibonacci non consécutifs). Pour le mot de Tribonacci, c'est le système de numération de Tribonacci. Pour le mot de Thue-Morse, ils utilisent une astuce impliquant la base $(-2)$ pour gérer les nombres négatifs dans les calculs de somme.
• Outil logiciel (Walnut) : L'implémentation pratique repose sur le logiciel libre Walnut, capable de traduire des formules de logique du premier ordre (impliquant l'addition, la comparaison et des prédicats définis par des automates) en automates finis. Ces automates acceptent les paires $(m, n)$ si et seulement si elles satisfont la propriété d'équilibre.
• Représentations linéaires : Pour prouver des résultats sur la diversité des valeurs (Section 5), les auteurs utilisent des représentations linéaires de fonctions génératrices, calculées via des matrices et vérifiées algorithmiquement.

3. Contributions et Résultats Clés

A. Mot de Fibonacci et Mots de Sturmian

• Caractérisation par automate : Les auteurs prouvent qu'il existe un algorithme pour construire un automate fini qui accepte exactement les paires $(m, n)$ équilibrées pour tout mot de Sturmian associé à un irrationnel quadratique $\alpha$.
• Cas du mot de Fibonacci : Ils construisent un automate de 15 états (Figure 1) qui résout le problème d'équilibre pour le mot de Fibonacci.
• Généralisation d'un théorème précédent : Ils démontrent que si $\max(m, n)$ est un nombre de Fibonacci, alors le rectangle $m \times n$ est équilibré (confirmant un résultat récent d'Anselmo et al.), mais montrent que ce n'est pas la seule condition (ex: $(4,3)$ est équilibré).
• Propriétés structurelles : Ils établissent des propriétés de densité et de périodicité des paires équilibrées en fonction des nombres de Fibonacci (Propositions 5 et 6).
• Diversité des sommes : Ils montrent que pour $m=n=F_{3k/2}$, le nombre de valeurs distinctes prises par la somme $T(i, m, n)$ est de l'ordre de $\Theta(k)$, prouvant que le nombre de valeurs distinctes peut croître linéairement avec la taille du rectangle, ce qui empêche une caractérisation simple par un automate calculant directement le nombre de valeurs.

B. Mot de Tribonacci

• Équilibre 2-balancé : Le mot de Tribonacci est connu pour être 2-balancé (la différence de comptage de lettres entre deux mots de même longueur est $\le 2$).
• Résultat principal : Les auteurs caractérisent les rectangles $m \times n$ qui sont 2-balancés entre eux :
  • Si $m=1$, tous les rectangles sont 2-balancés.
  • Si $m=2$, il existe un automate de 77 états acceptant les $n$ correspondants. La liste des $n$ valides semble complexe et ne possède pas de description simple.
  • Si $m \ge 3$, aucun $n$ ne rend les rectangles 2-balancés. Ils prouvent cela en exhibant deux rectangles $m \times n$ dont la différence de comptage d'un symbole spécifique est de 3.

C. Mot de Thue-Morse

• Analyse fine : Pour le mot de Thue-Morse, les auteurs obtiennent une description complète de l'équilibre.
• Bornes : Ils montrent que pour tout rectangle $m \times n$, la valeur $|2 \cdot |A(i, m, n)|_1 - mn|$ est bornée par 4.
• Automate de balance : Ils construisent un automate de 92 états (nécessitant un calcul intensif avec des représentations en base $-2$) qui détermine la balance exacte (1, 2, 3 ou 4) pour toute paire $(m, n)$.
• Condition d'équilibre 3 : Ils prouvent que pour $m, n \ge 3$, la balance est exactement 3 si et seulement si $m$ et $n$ sont tous deux impairs.

4. Signification et Impact

• Méthodologique : Ce travail démontre la puissance de l'approche « automates + logique » pour résoudre des problèmes de combinatoire des mots qui semblent analytiquement complexes. La capacité à transformer des propriétés globales de suites infinies en automates finis permet une vérification algorithmique rigoureuse de conjectures.
• Théorique : Il fournit une caractérisation complète et décidable de l'équilibre des rectangles pour plusieurs classes de mots célèbres (Sturmian, Tribonacci, Thue-Morse), comblant des lacunes dans la compréhension de la structure bidimensionnelle de ces suites.
• Pratique : Tous les codes (Walnut et Maple) sont rendus publics, permettant à la communauté de reproduire les résultats et d'explorer d'autres suites ou paramètres. L'article ouvre la voie à l'étude de l'équilibre pour d'autres morphismes et structures de mots.

En résumé, l'article établit que la propriété d'équilibre des rectangles de mots, bien que dépendante de la structure fine de la suite sous-jacente, est décidable et caractérisable par des automates finis pour une large classe de suites, offrant ainsi une nouvelle perspective sur la combinatoire des mots et la théorie des nombres.