Mot sturmien

En mathématiques, en combinatoire et particulièrement en combinatoire des mots, un mot sturmien (ou une suite sturmienne) est un mot infini d'un type particulier qui possède plusieurs définitions équivalentes, de nature arithmétique ou combinatoire. La définition la plus directe est la suivante : un mot infini est sturmien s'il possède exactement n + 1 facteurs (au sens de blocs de symboles consécutifs) de longueur n, pour tout entier naturel n. L'exemple le plus connu des mots sturmiens est le mot de Fibonacci infini. En revanche, le mot de Prouhet-Thue-Morse n'est pas sturmien.

L'adjectif « sturmien » a été attribué à ces suites en l'honneur du mathématicien Charles Sturm par Gustav Hedlund et Marston Morse, dans leur article de 1940^[1], en référence aux suites de Sturm.

Définitions équivalentes

En combinatoire des mots, un mot infini est une suite infinie de symboles construite à partir d'un alphabet fini. Toute sous-suite contiguë et finie d'un tel mot est un facteur de ce mot.

Mot sturmien

Un mot infini x est dit sturmien si, pour tout entier naturel n, le mot x a exactement n + 1 facteurs différents de longueur n.

La définition implique qu'il doit avoir 2 facteurs distincts de longueur 1 ; ceci entraîne que l'alphabet utilisé est nécessairement un alphabet de 2 lettres. Sans perte de généralité, on peut supposer que ces lettres sont 0 et 1.

Mot mécanique

La deuxième définition est plus proche de la géométrie ou de l'arithmétique. Une suite ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ sur {0,1} est un mot mécanique si et seulement s'il existe deux nombres réels ${\displaystyle \alpha }$ et ${\displaystyle \rho }$, avec ${\displaystyle 0<\alpha <1}$ irrationnel, tels que, pour tout ${\displaystyle n}$ :

${\displaystyle a_{n}=\lfloor \alpha (n+1)+\rho \rfloor -\lfloor \alpha n+\rho \rfloor }$

ou

${\displaystyle a_{n}=\lceil \alpha (n+1)+\rho \rceil -\lceil \alpha n+\rho \rceil }$

Dans le premier cas, le mot obtenu est noté ${\displaystyle s_{\alpha ,\rho }}$ et est dit mécanique inférieur, dans le deuxième cas, le mot obtenu est noté ${\displaystyle s'_{\alpha ,\rho }}$ et est dit mécanique supérieur. Le nombre ${\displaystyle \alpha }$ est la pente, et le nombre ${\displaystyle \rho }$ est l'intercept.

Deux mots mécaniques de même pente ont exactement le même ensemble de facteurs.

Un mot sturmien peut être représenté par une discrétisation d'une droite. Dans ce cas, on s'intéresse aux points d'intersection de la droite avec la grille entière. On obtient une suite de coupures (« cutting sequence » en anglais) qui code les intersections verticales et horizontales. La relation avec les mots mécaniques est un cisaillement. On peut aussi considérer les carrés traversés par la droite. Les contours supérieurs et inférieurs de ces carrés forment les mots mécaniques supérieurs et inférieurs respectivement.

À la place de mot mécanique, on trouve aussi le terme mot de rotation, pour la raison suivante. On définit la rotation ${\displaystyle R_{\alpha }}$, d'angle ${\displaystyle \alpha }$, sur le cercle unité par

${\displaystyle R_{\alpha }(x)=x+\alpha {\bmod {1}}}$,

et deux intervalles semi-ouverts ${\displaystyle I_{0}=[0,1-\alpha [}$, ${\displaystyle I_{1}=[1-\alpha ,1[}$. Pour la suite mécanique inférieure, on a alors ${\displaystyle a_{n}=0}$ si ${\displaystyle R_{\alpha }^{n}(\rho )\in I_{0}}$ et ${\displaystyle a_{n}=1}$ si ${\displaystyle R_{\alpha }^{n}(\rho )\in I_{1}}$. La même chose vaut pour la suite supérieur, avec les intervalles ${\displaystyle I'_{0}=]0,1-\alpha ]}$, ${\displaystyle I'_{1}=]1-\alpha ,1]}$ semi-ouverts de l'autre côté.

Mot équilibré

Un ensemble ${\displaystyle X}$ de mots est dit équilibré si, pour deux mots ${\displaystyle x}$ et ${\displaystyle y}$ de ${\displaystyle X}$ de même longueur, le nombre de symboles ${\displaystyle 0}$ dans ${\displaystyle x}$ et dans ${\displaystyle y}$ diffèrent d'au plus 1. Par exemple, l'ensemble ${\displaystyle \{001,010,100,101\}}$ des facteurs de longueur 3 du mot de Fibonacci est équilibré, puisque le nombre de ${\displaystyle 0}$ dans un mot de cet ensemble est soit 1, soit 2. En revanche, l'ensemble ${\displaystyle \{00,11\}}$ n'est pas équilibré, puisque le premier des mots a 2 lettres ${\displaystyle 0}$, et le dernier aucun. Un mot infini est dit équilibré si l'ensemble de ses facteurs est équilibré.

Équivalence des définitions

Mot standard ou mot caractéristique

Lorsque ${\displaystyle \rho =0}$, la droite passe par l'origine. Les mots mécaniques inférieurs et supérieurs ne diffèrent que par le premier symbole qui est 0 pour le premier et 1 pour le deuxième. On note ${\displaystyle c_{\alpha }}$ le restant du mot, donc ${\displaystyle s_{\alpha ,\rho }=0c_{\alpha }}$ et ${\displaystyle s'_{\alpha ,\rho }=1c_{\alpha }}$.

Le mot ${\displaystyle c_{\alpha }}$ est dit mot standard ou caractéristique de pente ${\displaystyle \alpha }$. Le mot caractéristique ${\displaystyle c_{\alpha }}$ est donc aussi constitué des écarts entre les termes de la suite de Beatty correspondant au nombre ${\displaystyle \alpha }$.

Ce mot caractéristique peut aussi être obtenu de la façon suivante: Soit ${\displaystyle [0;d_{1}+1,d_{2},\ldots ,d_{n},\ldots ]}$ le développement en fractions continues de ${\displaystyle \alpha }$, et définissons :

• ${\displaystyle s_{0}=1}$ ;
• ${\displaystyle s_{1}=0}$ ;
• ${\displaystyle s_{n+1}=s_{n}^{d_{n}}s_{n-1}}$ pour ${\displaystyle n>0}$.

(Souvenons-nous que le produit de deux mots est leur concaténation). Chaque mot dans la suite ${\displaystyle (s_{n})_{n>0}}$ est le préfixe des suivants, de telle sorte que la suite elle-même converge vers un mot infini qui est ${\displaystyle c_{\alpha }}$. Les mots ${\displaystyle s_{n}}$ eux-mêmes sont également appelés mots standard. Les mots standard de longueur au moins 2 se terminent par 01 ou 10. On appelle mot central un mot standard privé de ses deux dernières lettres.

Un exemple célèbre de mot sturmien est le mot de Fibonacci ; sa pente vaut 1/φ² = 1/(1 + φ), où φ est le nombre d'or. Le développement en fraction continue de la pente est 1/(1 + φ) = [0; 2, 1, 1, 1, …], donc d_n = 1 pour tout n et les s_n sont bien les mots de Fibonacci finis.

Propriétés et caractérisations

De nombreuses propriétés du mot de Fibonacci infini s'étendent aux mots sturmiens :

• L'ensemble des facteurs d'un mot sturmien est fermé par image miroir.
• Un mot sturmien est uniformément récurrent.

Certaines propriétés du mot de Fibonacci ne sont pas vérifiées par tous les mots sturmiens : tous les mots sturmiens ne sont pas substitutifs, par exemple.

Certaines propriétés sont même caractéristiques de mots sturmiens :

• Un mot infini est sturmien si et seulement s'il possède exactement deux facteurs palindromes de longueur impaire, et un facteur palindrome de longueur paire, pour toute longueur.

Une autre propriété concerne les facteurs :

• Deux mots sturmiens ont même ensemble de facteurs si et seulement ils ont même pente.

Pour énoncer la caractérisation suivante, on introduit la notion de mot de retour. Soit ${\displaystyle x}$ un mot infini uniformément récurrent, et soit ${\displaystyle u}$ un préfixe de ${\displaystyle x}$. Comme l'ensemble des occurrences de ${\displaystyle u}$ dans ${\displaystyle x}$ est un ensemble syndétique, la suite ${\displaystyle (k_{1}=0,k_{2},\ldots ,k_{n},\ldots )}$ des débuts d'occurrences de ${\displaystyle u}$, classés en ordre croissant, est à différences consécutives bornées. Chaque facteur de ${\displaystyle x}$ débutant en une position d'indice ${\displaystyle k_{n}}$, et terminant à la position ${\displaystyle k_{n+1}-1}$, est un mot de retour. Il n'y a donc qu'un nombre fini de mots de retour pour ${\displaystyle u}$ dans ${\displaystyle x}$. Pour le préfixe 0100 du mot de Fibonacci,

${\displaystyle {\underline {0}}1001{\underline {0}}10{\underline {0}}1001{\underline {0}}1001{\underline {0}}100\ldots }$,

on voit que le préfixe 0100 apparaît aux positions 0,5,8, 13, 18, ...; les mots de retour sont les deux mots ${\displaystyle 01001}$ et ${\displaystyle 010}$. La propriété d'avoir deux mots de retour est caractéristique :

• Un mot infini ${\displaystyle x}$ est sturmien si et seulement, pour tout préfixe ${\displaystyle u}$ de ${\displaystyle x}$, il existe exactement deux mots de retour à ${\displaystyle u}$ dans ${\displaystyle x}$.

La fonction de récurrence d'une mot sturmien ${\displaystyle x}$ est la fonction ${\displaystyle R_{x}}$ définie par : ${\displaystyle R_{x}(n)}$ est le plus petit entier tel que tout facteur de ${\displaystyle x}$ de cette longueur contient tous les facteurs de longueur ${\displaystyle n}$. Cette fonction ne dépend que de la pente du mot sturmien. Soit donc ${\displaystyle [0,1+d_{1},d_{2},\ldots ,d_{n},\ldots ]}$ le développement en fraction continue de la pente, et soient q_n les dénominateurs de ses réduites. Alors on a :

• La fonction de récurrence d'un mot sturmien x vérifie

${\displaystyle R_{x}(n)=q_{N+1}+q_{N}+n-1}$,

où ${\displaystyle N}$ est tel que ${\displaystyle q_{N}\leq n<q_{N+1}}$.

Cette formule a été déjà trouvée par Morse et Hedlund en 1940.

L'exposant critique ou index d'un mot sturmien est la plus haute puissance d'un mot qui peut apparaître comme facteur dans ce mot sturmien. Plus précisément, fixons un mot infini x. On note ind${\displaystyle (w)}$, et on appelle index de ${\displaystyle w}$, la borne supérieure des nombres rationnels ${\displaystyle r}$ tels que ${\displaystyle w^{r}}$ est un facteur de ${\displaystyle x}$. Ici, ${\displaystyle w^{r}}$ est le mot de longueur ${\displaystyle r|w}$| qui est de la forme ${\displaystyle ww\cdots ww'}$, où ${\displaystyle w'}$ est un préfixe de ${\displaystyle w}$. Par exemple, ${\displaystyle (010)^{7/3}=0100100}$. On a alors la caractérisation suivante :

• Un mot infini uniformément récurrent ${\displaystyle x}$ est un mot sturmien si et seulement s'il existe une infinité de facteurs ${\displaystyle w}$ de ${\displaystyle x}$ tels que

${\displaystyle R_{x}(|w|)=|w|{\text{ind}}(w)+1}$.

Morphismes sturmiens

Un morphisme σ est dit sturmien si, pour tout mot sturmien x, le mot σ(x) est aussi sturmien. Un morphisme σ est dit localement sturmien s'il existe un mot sturmien x tel que σ(x) est aussi sturmien. Berstel, Mignosi et Séébold^[2] ont établi une caractérisation complète de ces morphismes à l'aide des substitutions suivantes : φ : 0 → 01, 1 → 0 ; ψ : 0 → 10, 1 → 0, E : 0 → 1, 1 → 0. Le monoïde S_St est le monoïde généré par {φ, ψ, E} par composition.

Il existe d'autres ensembles générateurs du monoïde S_St , comme les cinq substitutions suivantes : L₀ : 0 → 0, 1 → 01 ; L₁ : 0 → 10, 1 → 1, R₀ : 0 → 0, 1 → 10, R₁ : 0 → 01, 1 → 1 et E : 0 → 1, 1 → 0. L'ensemble de substitutions {L₀, L₁, R₀, R₁} sert également à donner une caractérisation S-adique de l'ensemble des mots sturmiens.

Histoire

Bien que l'étude des mots sturmiens remonte à Jean Bernoulli (en 1772), la première grande étude a été réalisée par Gustav Hedlund et Marston Morse en 1940.

Notes et références

Voir aussi

Articles connexes

• Mot de faible complexité
• Complexité abélienne d'un mot
• Mot quasi-périodique

Bibliographie

Articles fondamentaux

• (en) Marston Morse et Gustav A. Hedlund, « Symbolic dynamics II. Sturmian trajectories », Amer. J. Math., vol. 62,‎ 1940, p. 1-42 (MR 0000745).
• (en) M. Lothaire, Algebraic Combinatorics on Words, Cambridge UK, Cambridge University Press, 2002, 504 p. (ISBN 978-0-521-81220-7, lire en ligne), chap. 2 (« Sturmian Words »), aperçu sur Google Livres.
• Valérie Berthé, Aldo de Luca et Christophe Reutenauer, « On an involution of Christoffel words and Sturmian morphisms », European Journal of Combinatorics, vol. 29, n^o 2,‎ 2008, p. 535–553 (DOI 10.1016/j.ejc.2007.03.001, lire en ligne).
• Aldo de Luca, « Sturmian words: structure, combinatorics, and their arithmetics », Theoretical Computer Science, vol. 183, n^o 1,‎ 1997, p. 45–82 (DOI 10.1016/S0304-3975(96)00310-6, lire en ligne).

Articles spécifiques

• Sebastián Barbieri, Sébastien Labbé et Štěpán Starosta, « A characterization of Sturmian sequences by indistinguishable asymptotic pairs », European Journal of Combinatorics, vol. 95,‎ 2021, article n^o 103318 (DOI 10.1016/j.ejc.2021.103318, arXiv 2011.08112).
• Sébastien Labbé et Jana Lepšová, « A Numeration System for Fibonacci-Like Wang Shifts », dans Thierry Lecroq et Svetlana Puzynina (éditeurs), Combinatorics on Words. WORDS 2021, Springer, Cham, coll. « Lecture Notes in Computer Science » (n^o 12847), 2021 (arXiv 2105.11898), p. 104-116.
• Filippo Mignosi et Patrice Séébold, « Morphismes sturmiens et règles de Rauzy », Journal de théorie des nombres de Bordeaux, vol. 5,‎ 1993.

• Portail des mathématiques
• Portail de l'informatique théorique