Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words

Ces notes de cours introduisent la combinatoire des mots et ses interactions avec la dynamique, l'algèbre et l'arithmétique en explorant la complexité factorielle minimale des mots infinis non triviaux, notamment à travers l'étude des mots de Sturmian, des graphes de Rauzy et d'une nouvelle preuve algébrique d'un théorème de R. Tijdeman.

L'essentiel

🌟 Le Secret des Mots Infinis : Une Chasse au Trésor Mathématique

Imaginez que vous avez un ruban de papier infini sur lequel sont écrits des mots. Ce ruban est composé de lettres (comme A, B, C...). En mathématiques, on appelle cela un mot infini.

Le but de ce cours, donné par Mélodie Andrieu, est de répondre à une question simple mais profonde : Comment mesurer la "complexité" de ce ruban ?

1. Le Compteur de Mots (La Complexité)

Pour savoir si un ruban est simple ou compliqué, on utilise un petit compteur magique appelé la complexité.

• Prenez une longueur, disons 3 lettres.
• Comptez combien de combinaisons différentes de 3 lettres apparaissent sur votre ruban infini.
• Si vous avez "AAA", "AAB", "ABA", "ABB", etc., le compteur augmente.

L'analogie du jardin :
Imaginez un jardin infini.

• Si le jardin est un désordre total (chaque fleur est différente), il y a des milliards de combinaisons. C'est très complexe.
• Si le jardin est un tapis vert parfait (toujours la même fleur), il n'y a qu'une seule combinaison. C'est très simple.
• La question est : Quel est le niveau de complexité le plus bas possible pour un jardin qui n'est pas juste un tapis vert ennuyeux ?

2. La Règle d'Or (Le Théorème de Morse et Hedlund)

Dans les années 1930, deux mathématiciens (Morse et Hedlund) ont découvert une loi fondamentale pour les jardins à deux couleurs (un alphabet binaire, comme 0 et 1).

Ils ont dit :

"Si votre compteur de mots s'arrête de grandir ou reste trop petit (moins que la longueur du mot), alors votre jardin est périodique. C'est-à-dire qu'il répète toujours la même séquence : 01010101...."

C'est comme si vous marchiez sur un tapis roulant : vous ne voyez jamais rien de nouveau. Pour avoir un jardin intéressant (qui ne répète pas bêtement), il faut que le compteur augmente au moins d'une unité à chaque fois.

Les mots qui atteignent ce minimum absolu (le compteur augmente juste de 1 à chaque fois) s'appellent les mots de Sturmian.

• L'analogie : Ce sont les mots les plus "économes" en information tout en restant intéressants. C'est comme un poème qui utilise le minimum de mots possibles pour raconter une histoire infinie sans jamais se répéter.

3. Le Lien Magique avec les Nombres (Les Fractions Continues)

Le cours explique que ces mots de Sturmian ne sont pas de simples suites de lettres. Ils sont liés à des nombres spéciaux : les nombres irrationnels (comme le nombre d'or $\phi$).

• L'analogie du miroir : Imaginez que vous écrivez un mot de Sturmian. Si vous regardez dans le miroir de la "fraction continue" (une façon étrange d'écrire les nombres), vous verrez le reflet exact de ce mot.
• Chaque nombre irrationnel unique génère un mot de Sturmian unique. C'est comme si chaque nombre irrationnel avait son propre "code secret" écrit en lettres.

4. Le Problème des Jardins à Plusieurs Couleurs (Alphabets à $d$ lettres)

Jusqu'ici, on parlait de jardins à 2 couleurs (0 et 1). Mais que se passe-t-il si on a 3, 4, ou 10 couleurs ? (Un alphabet à $d$ lettres).

C'est là que le cours devient passionnant.

• Le piège : Si on essaie simplement d'ajouter plus de couleurs, on trouve des mots qui semblent simples mais qui sont en fait des "tricheries" (des mots qui répètent des motifs artificiels).
• La nouvelle règle : Pour qu'un mot soit vraiment "intéressant" avec beaucoup de couleurs, il ne suffit pas qu'il ne soit pas périodique. Il faut que les couleurs apparaissent avec des fréquences "irrationnelles".
  • Explication simple : Si vous avez 3 couleurs, et que la première apparaît 1/3 du temps, la deuxième 1/3, et la troisième 1/3, c'est trop "régulier" (trop périodique). Il faut que les proportions soient des nombres bizarres et irrationnels pour que le motif soit vraiment unique et non répétitif.

5. La Grande Découverte de Tijdeman (et la preuve nouvelle)

En 1999, un mathématicien nommé Tijdeman a trouvé la réponse pour les jardins à $d$ couleurs. Il a calculé le minimum de complexité possible pour ces mots "intéressants".

• La formule magique : Si vous avez $d$ couleurs, le compteur de complexité doit être au moins égal à $(d-1) \times n + 1$.
  • Pour 2 couleurs : $1 \times n + 1$ (C'est le cas des mots de Sturmian).
  • Pour 3 couleurs : $2 \times n + 1$.
  • Pour 10 couleurs : $9 \times n + 1$.

Le coup de génie de ce cours (2022) :
L'auteure et son collègue Cassaigne ont redécouvert ce résultat et ont trouvé une nouvelle façon de le prouver.

• L'ancienne méthode (Tijdeman) : C'était comme résoudre un puzzle en essayant des pièces au hasard (méthode combinatoire).
• La nouvelle méthode (Andrieu & Cassaigne) : Ils ont utilisé l'algèbre linéaire (des matrices et des vecteurs).
  • L'analogie : Imaginez que le mot infini est un réseau de canalisations d'eau. Chaque lettre est un tuyau. Ils ont créé une "matrice de flux" (un tableau de chiffres) qui représente comment l'eau circule. En utilisant les règles de l'électricité (les lois de Kirchhoff), ils ont prouvé mathématiquement qu'il est impossible d'avoir un flux plus simple que celui prédit par la formule de Tijdeman.

6. La Conclusion : Les Mots "Arborescents"

Le cours se termine par une découverte surprenante : tous ces mots qui atteignent ce niveau de complexité minimale ont une structure très particulière. Ils sont "dendriques".

• L'analogie de l'arbre : Imaginez que vous prenez un mot au milieu du ruban. Si vous regardez toutes les façons de le faire grandir (en ajoutant une lettre devant ou derrière), les possibilités forment un arbre (pas de boucles, pas de cycles). C'est une structure très propre et organisée, comme les branches d'un arbre, contrairement à un labyrinthe emmêlé.

En Résumé

Ce cours nous dit que :

1. Il existe des mots infinis aussi simples que possible sans être ennuyeux.
2. Pour 2 lettres, ce sont les mots de Sturmian (liés aux nombres irrationnels).
3. Pour plus de lettres, la règle change légèrement : il faut des fréquences irrationnelles.
4. La complexité minimale suit une formule précise découverte par Tijdeman.
5. Une nouvelle preuve algébrique (comme un circuit électrique) confirme que ces mots ont une structure en forme d'arbre, ce qui les rend fascinants pour les mathématiciens, les physiciens et les informaticiens.

C'est une belle démonstration de comment des concepts abstraits (nombres, mots, graphes) s'entremêlent pour révéler l'ordre caché dans le chaos apparent.

Résumé technique

Résumé Technique : Mots infinis à très faible complexité de facteurs

Auteur : Mélodie Andrieu (avec des résultats collaboratifs avec J. Cassaigne)
Contexte : Introduction à la combinatoire des mots, interactions avec la dynamique, l'algèbre et l'arithmétique.
Sujet central : La complexité de facteurs des mots infinis et la généralisation du théorème de Morse-Hedlund aux alphabets de taille $d \ge 3$.

1. Problématique et Contexte

La complexité de facteurs $p_w(n)$ d'un mot infini $w$ sur un alphabet fini de taille $d$ compte le nombre de sous-mots (facteurs) distincts de longueur $n$.

• Le cas binaire ($d=2$) : Le théorème fondamental de Morse et Hedlund (1938) établit qu'un mot est ultimement périodique si et seulement si sa complexité est bornée. Les mots non périodiques ont donc $p_w(n) \ge n+1$. Ceux qui atteignent ce minimum ($p_w(n) = n+1$) sont les mots de Sturmian. Ils sont intimement liés aux fractions continues, aux rotations irrationnelles et aux billards carrés.
• Le problème pour $d \ge 3$ : Comment généraliser ces résultats ?
  • La condition "non ultimement périodique" est insuffisante pour exclure les mots triviaux sur des alphabets plus grands (ex: mots quasi-Sturmian construits artificiellement).
  • Quelle est la complexité minimale pour un mot "intéressant" (non trivial) sur un alphabet de taille $d$ ?
  • Quels sont les mots qui atteignent cette complexité ?

2. Méthodologie et Outils

L'article utilise une approche hybride combinant la combinatoire des mots, la théorie ergodique et l'algèbre linéaire.

• Renormalisation et Fractions Continues (Chapitre 1) : Pour le cas binaire, l'auteur introduit un processus de renormalisation basé sur l'effacement de lettres spécifiques, reliant la structure des mots de Sturmian aux fractions continues et démontrant que leurs fréquences de lettres sont irrationnellement indépendantes.
• Graphes de Rauzy et Matrices de Flux (Chapitre 3) : C'est l'apport méthodologique majeur. L'auteur définit la matrice de flux (flow matrix) $M$, une matrice rectangulaire indexée par les facteurs de longueur $n$ (lignes) et $n+1$ (colonnes). Les entrées sont $1, -1$ou$0$selon que le facteur de longueur$n+1$commence ou finit par le facteur de longueur$n$.
  • Cette matrice est liée à la loi de Kirchhoff (conservation du flux) appliquée aux graphes de Rauzy.
  • La preuve repose sur l'analyse de l'algèbre linéaire de cette matrice (théorème du rang, noyaux sur $\mathbb{Q}$ et $\mathbb{R}$).

3. Résultats Clés

A. Généralisation du théorème de Morse-Hedlund (Théorème de Tijdeman)
L'article redécouvre et renforce un théorème de R. Tijdeman (1999).

• Condition de non-trivialité : Au lieu de la non-périodicité, la condition appropriée pour $d \ge 3$ est l'indépendance rationnelle des fréquences de lettres.
• Théorème 2.12 (Tijdeman) : Pour un mot infini $d$-aire avec des fréquences de lettres rationnellement indépendantes, la complexité satisfait :
  $$p_w(n) \ge (d-1)n + 1$$
  Il existe des mots atteignant cette borne (ex: mots d'Arnoux-Rauzy, codages d'échanges d'intervalles).

B. Preuve Algébrique Alternative (Théorème 3.1)
Andrieu et Cassaigne (2022) fournissent une preuve conceptuellement nouvelle et plus forte du théorème de Tijdeman.

• Résultat renforcé : La borne inférieure dépend du degré maximal d'irrationalité $\Delta_w$ des fréquences (dimension de l'espace vectoriel engendré sur $\mathbb{Q}$ par les fréquences, même si elles n'existent pas strictement, mais via des limites de sous-suites).
  $$p_w(n) \ge (\Delta_w - 1)(n - 1) + d$$
• Preuve : L'argument utilise le fait que le vecteur des fréquences pseudo-asymptotiques des facteurs appartient au noyau de la matrice de flux $M$. En étudiant la dimension de ce noyau via le théorème du rang, on montre que si la complexité est trop faible, la dimension de l'espace engendré par les fréquences des lettres doit être strictement inférieure à $\Delta_w$, ce qui est une contradiction.

C. Caractérisation Combinatoire : Les Mots Dendriques
Un résultat majeur découle de cette preuve algébrique.

• Théorème 3.2 : Tout mot infini $d$-aire ayant des fréquences de lettres rationnellement indépendantes et une complexité minimale $p_w(n) = (d-1)n + 1$ est un mot dendrique.
• Définition : Un mot est dendrique si le graphe d'extension de chaque facteur est un arbre (connexe et sans cycle).
• Signification : Cela établit un lien structurel profond : la minimalité de la complexité (dans le sens de Tijdeman) impose une structure arborescente stricte aux extensions des facteurs. Cela généralise la propriété des mots de Sturmian (qui sont dendriques) au cas $d$-aire.

4. Signification et Implications

1. Unification Théorique : L'article unifie la compréhension des mots de faible complexité. Il montre que la notion de "minimalité" change avec la taille de l'alphabet : pour $d=2$, c'est $n+1$ (Sturmian) ; pour $d \ge 3$, c'est $(d-1)n+1$, et la condition de non-trivialité passe de la périodicité à l'indépendance rationnelle des fréquences.
2. Nouvelle Preuve et Outils : La preuve par matrices de flux offre un outil puissant et purement algébrique, évitant les arguments combinatoires complexes de la preuve originale de Tijdeman. Elle permet d'obtenir des résultats plus fins (degré maximal d'irrationalité).
3. Structure des Mots Optimaux : La démonstration que les mots de complexité minimale sont dendriques est une avancée majeure pour la classification de ces mots. Bien que la caractérisation complète (géométrique/dynamique) pour $d \ge 3$ reste un problème ouvert, cette propriété structurelle (dendricité) fournit un cadre solide pour les étudier.
4. Lien avec la Dynamique : Le texte réaffirme le lien entre la complexité combinatoire et les systèmes dynamiques (rotations, billards, échanges d'intervalles), montrant que les mots de complexité minimale correspondent aux codages de systèmes minimaux avec des fréquences irrationnellement indépendantes.

En résumé, ce travail fournit une introduction rigoureuse aux mots de Sturmian, généralise les bornes de complexité aux alphabets de taille arbitraire via le théorème de Tijdeman, et propose une preuve algébrique innovante qui révèle que les mots atteignant ces bornes minimales possèdent une structure dendrique fondamentale.