Mot sturmien

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 mécanique

Équivalence entre mot de coupure (cutting sequence) et mot mécanique : l'opération est un cisaillement, c'est-à-dire la transformation ${\displaystyle (x,y)\mapsto (x+y,y)}$. La pente ${\displaystyle \beta }$ de la droite dans la figure gauche et la pente ${\displaystyle \alpha }$ de la droite dans la figure droite sont liées par ${\displaystyle \alpha =\beta /(1+\beta )}$.

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.

Équivalence entre le mot de coupure, les carrés traversés, et les mots mécaniques supérieurs et inférieurs.

À 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é.

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.

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 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}$.

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.