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

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

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
Équivalence entre mot de coupure (cutting sequence) et mot mécanique : l'opération est un cisaillement, c'est-à-dire la transformation . La pente de la droite dans la figure gauche et la pente de la droite dans la figure droite sont liées par .

La deuxième définition est plus proche de la géométrie ou de l'arithmétique. Une suite sur {0,1} est un mot mécanique si et seulement s'il existe deux nombres réels et , avec irrationnel, tels que, pour tout  :

ou

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

,

et deux intervalles semi-ouverts , . Pour la suite mécanique inférieure, on a alors si et si . La même chose vaut pour la suite supérieur, avec les intervalles , semi-ouverts de l'autre côté.

Mot équilibré

modifier

Un ensemble de mots est dit équilibré si, pour deux mots et de de même longueur, le nombre de symboles dans et dans diffèrent d'au plus 1. Par exemple, l'ensemble des facteurs de longueur 3 du mot de Fibonacci est équilibré, puisque le nombre de dans un mot de cet ensemble est soit 1, soit 2. En revanche, l'ensemble n'est pas équilibré, puisque le premier des mots a 2 lettres , et le dernier aucun. Un mot infini est dit équilibré si l'ensemble de ses facteurs est équilibré.

Équivalence des définitions

modifier

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

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

Mot standard ou mot caractéristique

modifier

Lorsque , 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 le restant du mot, donc et .

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

Ce mot caractéristique peut aussi être obtenu de la façon suivante: Soit le développement en fractions continues de , et définissons :

  •  ;
  •  ;
  • pour .

(Souvenons-nous que le produit de deux mots est leur concaténation). Chaque mot dans la suite est le préfixe des suivants, de telle sorte que la suite elle-même converge vers un mot infini qui est . Les mots 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/φ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

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

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 un mot infini uniformément récurrent, et soit un préfixe de . Comme l'ensemble des occurrences de dans est un ensemble syndétique, la suite des débuts d'occurrences de , classés en ordre croissant, est à différences consécutives bornées. Chaque facteur de débutant en une position d'indice , et terminant à la position , est un mot de retour. Il n'y a donc qu'un nombre fini de mots de retour pour dans . Pour le préfixe 0100 du mot de Fibonacci,

,

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

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

La fonction de récurrence d'une mot sturmien est la fonction définie par : est le plus petit entier tel que tout facteur de de cette longueur contient tous les facteurs de longueur . Cette fonction ne dépend que de la pente du mot sturmien. Soit donc 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
,
est tel que .

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, et on appelle index de , la borne supérieure des nombres rationnels tels que est un facteur de . Ici, est le mot de longueur | qui est de la forme , où est un préfixe de . Par exemple, . On a alors la caractérisation suivante :

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

Morphismes sturmiens

modifier

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 SSt est le monoïde généré par {φ, ψ, E} par composition.

Théorème (Mignosi et Séébold, 1993) —  Soit σ un morphisme sur un alphabet binaire. Les conditions suivantes sont équivalentes :

  1. σ est sturmien ;
  2. σ est localement sturmien ;
  3. σ ∈ SSt.

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

Histoire

modifier

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

modifier
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sturmian word » (voir la liste des auteurs).
  1. Morse et Hedlund 1940.
  2. M. Lothaire, Algebraic combinatorics on words, Cambridge University Press, coll. « Encyclopedia of mathematics and its applications », (ISBN 978-0-521-81220-7)

Voir aussi

modifier

Articles connexes

modifier

Bibliographie

modifier
Articles fondamentaux
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,‎ , article no 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 » (no 12847), (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,‎ .