Mot sturmien

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

É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\N} sur {0,1} est un mot mécanique 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

ou

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

Dans le premier cas, le mot obtenu est noté s_{\alpha,\rho} et est dit mécanique inférieur, dans le mot obtenu est noté s'_{\alpha,\rho} et est le deuxième cas mécanique supérieur. Le nombre \alpha est la pente, et le nombre \rho est 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 R_\alpha, d'angle \alpha, sur le cercle unité par

R_\alpha(x)=x+\alpha \bmod 1 ,

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^n_\alpha(\rho)\in I_0 et a_n=1 si R^n_\alpha(\rho)\in I_1. La même chose vaut pour la suite supérieur, avec les intervalles I'_0=]0,1-\alpha], I'_1=]1-\alpha,1] semi-ouverts de l'autre côté.

Mot équilibré[modifier | modifier le code]

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

Équivalence des définitions[modifier | modifier le code]

Théorème (Morse et Hedlund, 1940) —  Soit x un mot infini sur un alphabet binaire. Les conditions suivantes sont équivalentes :

  1. x est sturmien;
  2. x est mécanique de pente irrationnelle;
  3. x est équilibré et non ultimement périodique.

Mot standard ou mot caractéristique[modifier | modifier le code]

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. On note c_\alpha le restant du mot, donc s_{\alpha,\rho}=0c_\alpha et s'_{\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, \ldots, d_n, \ldots] 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

(Souvenons-nous que le produit de deux mots est leur 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.

Un exemple célèbre de mot sturmien est le mot de Fibonacci ; sa pente vaut 1/φ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 dn = 1 pour tout n et les sn sont bien les mots de Fibonacci finis.

Propriétés et caractérisations[modifier | modifier le code]

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

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 impair, 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,\ldots,k_n,\ldots) des début 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,

\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 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,\ldots,d_n,\ldots] le développement en fraction continue de la pente, et soient qn 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,
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 ww', où w' 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.

Histoire[modifier | modifier le code]

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.

Articles connexes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

Références[modifier | modifier le code]

Littérature[modifier | modifier le code]