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.

L'adjectif Modèle:Citation a été attribué à ces suites en l'honneur du mathématicien Charles Sturm par Gustav Hedlund et Marston Morse, dans leur article de 1940, en référence aux suites de Sturm.

Caractérisation d'un mot sturmien par une droite. Ici, le mot de Fibonacci : pente φ-1 et passant par l'origine, où φ est le nombre d'or.

Définitions équivalentes

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

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

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

$a_n=\lfloor \alpha (n+1)+\rho \rfloor -\lfloor \alpha n+\rho \rfloor$

De même, la suite $(a_n{)}_{n\in \mathbb{N}}$ est un mot mécanique supérieur si et seulement si pour tout $n$ :

$a_n=\lceil \alpha (n+1)+\rho \rceil -\lceil \alpha n+\rho \rceil$

Pour $\alpha$ et $\rho$ fixés, le mot mécanique inférieur associé est noté $s_{\alpha ,\rho }$ et le mot mécanique supérieur associé est noté $s{\text{'}}_{\alpha ,\rho }$. Le nombre $\alpha$ est la pente, et le nombre $\rho$ est lModèle:'intercept du mot mécanique.

Deux mots mécaniques de même pente, qu'ils soient supérieurs ou inférieurs, 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 (Modèle:Citation étrangère 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 $R_{\alpha }$, d'angle $\alpha$, sur le cercle unité par

$R_{\alpha }(x)=x+\alpha mod1$,

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

Mot équilibré

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

Mot standard ou mot caractéristique

Lorsque $\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. En notant $c_{\alpha }$ le restant du mot, on obtient alors $s_{\alpha ,\rho }=0c_{\alpha }$ et $s{\text{'}}_{\alpha ,\rho }=1c_{\alpha }$.

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

Ce mot caractéristique peut aussi être obtenu de la façon suivante: Soit $[0;d_1+1,d_2,\dots ,d_n,\dots ]$ le développement en fractions continues de $\alpha$, et définissons :

• $s_0=1$ ;
• $s_1=0$ ;
• $s_{n+1}=s_n^{d_n}{s}_{n-1}$ pour $n>0$, où le produit de mots désigne la concaténation.

Chaque mot dans la suite $(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 $c_{\alpha }$. Les mots $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/φModèle:2 = 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 dModèle:Ind = 1 pour tout n et les sModèle:Ind 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 $x$ un mot infini uniformément récurrent, et soit $u$ un préfixe de $x$. Comme l'ensemble des occurrences de $u$ dans $x$ est un ensemble syndétique, la suite $(k_1=0,k_2,\dots ,k_n,\dots )$ des débuts d'occurrences de $u$, classés en ordre croissant, est à différences consécutives bornées. Chaque facteur de $x$ débutant en une position d'indice $k_n$, et terminant à la position $k_{n+1}-1$, est un mot de retour. Il n'y a donc qu'un nombre fini de mots de retour pour $u$ dans $x$. Pour le préfixe 0100 du mot de Fibonacci,

$\underset{\_}{0}1001\underset{\_}{0}10\underset{\_}{0}1001\underset{\_}{0}1001\underset{\_}{0}100\dots$,

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

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

La fonction de récurrence d'une mot sturmien $x$ est la fonction $R_x$ définie par : $R_x(n)$ est le plus petit entier tel que tout facteur de $x$ de cette longueur contient tous les facteurs de longueur $n$. Cette fonction ne dépend que de la pente du mot sturmien. Soit donc $[0,1+d_1,d_2,\dots ,d_n,\dots ]$ le développement en fraction continue de la pente, et soient qModèle:Ind les dénominateurs de ses réduites. Alors on a :

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

$R_x(n)=q_{N+1}+q_N+n-1$,

où $N$ est tel que $q_N\le 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$(w)$, et on appelle index de $w$, la borne supérieure des nombres rationnels $r$ tels que $w^r$ est un facteur de $x$. Ici, $w^r$ est le mot de longueur $r|w$| qui est de la forme $ww\cdots w{w}^{\prime }$, où $w^{\prime }$ est un préfixe de $w$. Par exemple, $(010{)}^{7/3}=0100100$. On a alors la caractérisation suivante :

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

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

Voir aussi

Articles connexes

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

Bibliographie

Articles fondamentaux

• Modèle:Article.
• Modèle:Ouvrage, Modèle:Google Livres.
• Modèle:Article.
• Modèle:Article.

Articles spécifiques

• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Article