Les mots sturmiens

Introduction

On étudie ici des mots infinis constitués de a et de b, et qui possèdent la propriété d'être de complexité minimale parmi les mots non périodiques : les mots sturmiens.

On étudiera certaines de leurs propriétés combinatoires, puis on recherchera un procédé itératif systématique pour les engendrer. Ce faisant, outre la définition de départ, on aura trouvé deux autres définitions équivalentes de ces mots.

On s'intéressera aussi à des ensembles de mots sturmiens appelés systèmes dynamiques sturmiens, définis à partir de l'itération d'un opérateur, et qui lient des mots sturmiens partageant certaines propriétés.

Définitions d'ordre général sur les mots

Un mot infini est une application de $\N$ dans un ensemble A appelé alphabet. On prendra ici $A=\{a,b\}$ . Un mot fini de longueur n est une application de $\{1,\ldots,n\}$ dans A (ou le mot vide si $n=0$ ).

Un facteur d'un mot u est un mot fini constitué de lettres consécutives de u.

Le langage d'un mot u est l'ensemble de ses facteurs.

La complexité d'un mot u est l'application qui à chaque $n\in \N$ associe le nombre de facteurs de u de longueur n différents. On notera $P_n(u)$ ce nombre.

Propriétés combinatoires des mots sturmiens

Définition des mots sturmiens

Un mot infini u est dit sturmien si , ou encore s'il contient exactement facteurs différents de longueur n.

Le choix de la valeur $n+1$ peut sembler arbitraire. En fait, comme annoncé en introduction, les mots sturmiens sont les mots de complexité minimum (l'ensemble des complexités étant ordonné par l'ordre lexicographique) parmi les mots non périodiques. On peut en effet montrer que s'il existe $n\in \N$ tel que $P_n(u)\leq n$ , alors u est périodique (à partir d'un certain rang), et réciproquement. La complexité $n+1$ est donc un minimum pour les mots non périodiques :

La complexité $n+1$ signifie aussi que lorsqu'on considère les facteurs d'un mot de longueur n, il existe exactement un facteur U tel que Ua et Ub soient facteurs de ce mot, tous les autres facteurs de longueur n étant prolongeables à droite d'une unique manière.

Mots équilibrés

Un mot infini u est dit équilibré si le nombre de a dans deux de ses facteurs de même longueur diffère de 0 ou 1.

On obtient une définition équivalente en remplaçant a par b.

Il se trouve qu'on a quasi-identité entre les mots sturmiens et les mots équilibrés.

Un mot non périodique est sturmien si et seulement s'il est équilibré.

Un mot équilibré est donc soit périodique (à partir d'un certain rang), soit sturmien, et, comme un mot sturmien n'est jamais périodique, tout mot sturmien est équilibré.

Propriétés géométriques des mots sturmiens

On a donc obtenu jusqu'ici une double définition des mots sturmiens. On va maintenant définir trois processus dynamiques de génération de mots, qui fourniront une troisième caractérisation des mots sturmiens.

Mots de billard

Un premier exemple est constitué des mots de billard. On considère la trajectoire d'une boule ponctuelle soumise aux lois de réflexion de Descartes dans un billard :

En l'absence de pertes d'énergie, la boule rencontre les parois un nombre infini de fois. On repère par un a un choc avec une paroi verticale, et par un b un choc avec une paroi horizontale. On obtient ainsi un mot infini. Ce mot est noté $B(\beta,x)$ où $\beta$ et x sont la pente et l'ordonnée à l'origine de la droite que constitue la trajectoire de la boule avant le premier choc. On prendra $\beta\geq 0$ . La pente est calculée relativement aux longueurs des côtés du billard (la diagonale du billard ayant une pente 1).

Les mots de billard vérifient la propriété suivante :

$B(\beta,x)$ est équilibré.

Il est périodique si et seulement si $\beta$ est rationnel.

$B(\beta,x)$ est donc sturmien si et seulement si $\beta$ est irrationnel.

Mots de Christoffel

Les mots de billard sont liés à un autre ensemble de mots dont l'interprétation est de nature géométrique, les mots de Christoffel. Ils répondent au problème de l'approximation d'une droite par des points à coordonnées entières (qui se pose par exemple lors du tracé de droites sur un écran d'ordinateur). On considère une droite passant par l'origine, de pente comprise entre 0 et 1, et on l'approche par une suite de points dont les abscisses sont les entiers successifs, et les ordonnées, les plus grands entiers tels que le point reste sous la droite :

On construit ensuite un mot infini : lorsque deux points successifs ont même ordonnée, on écrit un a, et un b lorsque l'ordonnée varie. On obtient ainsi le mot de Christoffel associé à une droite de pente $\alpha$ . On peut généraliser la construction au cas où la droite a une ordonnée à l'origine x non nulle (qu'on prendra entre 0 et 1, par invariance du mot associé par addition d'un entier). Le mot correspondant sera noté $C(\alpha,x)$ .

Il existe une bijection entre mots de billard et mots de Christoffel :

$B(\beta,x)=C\left(\frac{\beta}{\beta+1},\frac{\beta+x}{\beta+1}\right)$

On vérifie que les intervalles de pente et d'ordonnée à l'origine pour lesquels ces mots sont définis entraînent bien le caractère bijectif.

Conséquence immédiate :

$C(\alpha,x)$ est équilibré. Il est sturmien si et seulement si $\alpha$ est irrationnel, périodique sinon.

Rotations irrationnelles

On peut donner une construction alternative des mots de Christoffel :

On se donne un nombre $\alpha\in[0;1[$ et on considère l'opération qui consiste à ajouter $\alpha$ modulo 1. On construit ainsi, à partir d'un nombre $x_0$ , une suite $x_0,x_1,\ldots,x_n\ldots$ de nombres de $[0;1[$ . Cette suite est interprétée comme un mot en écrivant un a si $x_n$ est inférieur à $\alpha$ , et un b sinon. Cette construction redonne $C(\alpha,x)$ . On dira que ce mot est engendré par la rotation d'angle $\alpha$ .

Un point reste flou dans les trois constructions ci-dessus : le comportement à adopter lorsque la boule du billard heurte un coin, lorsque la droite de Christoffel passe par un point à coordonnées entières, et lorsque l'un des $x_n$ vaut 0 ou $\alpha$ . Deux conventions cohérentes sont possibles. Elles ne donnent des résultats différents que dans un nombre dénombrable de cas. Par la suite, on dira qu'un mot est engendré par une rotation s'il l'est avec l'une ou l'autre des conventions.

On savait déjà que les mots engendrés par des rotations d'angle irrationnel étaient sturmiens. La réciproque est vraie :

Un mot est sturmien si et seulement s'il est engendré par une rotation irrationnelle.

On peut remarquer que l'existence des deux conventions ci-dessus n'est pas fortuite : la définition combinatoire des mots sturmiens s'interprète en remarquant que parmi tous les facteurs d'un mot sturmien, un exactement est prolongeable à gauche par a et par b (une propriété du même type sera vraie pour les systèmes sturmiens, cf. ci-dessous) : ce cas correspond précisément au cas où la droite de Christoffel passe par un point à coordonnées entières (ou encore au cas où la boule arrive dans un coin du billard).

Systèmes dynamiques sturmiens

On s'intéresse dorénavant à des ensembles de mots définis par l'itération d'un opérateur (d'où le qualificatif " dynamique "), en liaison avec des propriétés topologiques. On verra que ces systèmes sont en rapport avec la construction des mots sturmiens par les rotations irrationnelles.

Topologie sur les mots

On définit une topologie sur l'ensemble des mots infinis, induite par la distance ultramétrique

$d(u,v)=2^{-\inf \{n\in \N,u_n\neq v_n\}}$

L'ensemble des mots infinis est compact pour cette topologie.

L'ensemble des mots sturmiens est d'intérieur vide, de mesure nulle. Son adhérence est l'ensemble des mots équilibrés.

L'application qui à chaque mot sturmien associe l'angle de la rotation qui l'engendre est continue.

On définit sur l'ensemble des mots l'opérateur " décalage " (pour Shift) qui consiste à retirer la première lettre :

$S(u_0u_1u_2\ldots u_n\ldots)=u_1u_2\ldots u_n\ldots$

C'est un opérateur lipschitzien d'ordre 2.

Il possède les trois propriétés des opérateurs usuellement appelés chaotiques : la densité des points périodiques, la propriété de brassage et la dépendance sensitive aux conditions initiales.

Système associé à un mot sturmien

Le système dynamique associé au mot sturmien u est l'adhérence de son orbite sous l'opérateur S.

C'est un fermé d'intérieur vide, stable par S.

Tous les mots d'un système sturmien jouent des rôles équivalents :

Le système associé à un mot sturmien est l'ensemble des mots ayant le même langage.

Tout mot d'un système sturmien est sturmien et engendre le système.

Il existe une autre caractérisation des systèmes sturmiens, qui fournit une bijection (même un homéomorphisme avec une bonne topologie) entre les systèmes sturmiens et les irrationnels de :

Deux mots sturmiens appartiennent au même système si et seulement s'ils sont engendrés par des rotations de même angle.

Dans chaque système sturmien, il existe un unique mot biprolongeable à gauche (i.e. au et bu appartiennent au système). Ce mot est $C(\alpha,\alpha)$ où $\alpha$ est l'angle de la rotation associée.

On retrouve ici la propriété typique des facteurs d'un mot sturmien, à l'échelle d'un système.

Systèmes sturmiens et fractions continues

Soit $\sigma_a$ (resp. $\sigma_b$ ) le morphisme de monoïde (pour la concaténation) qui à a associe a (resp. ab) et à b, ba (resp. b).

Soit un système sturmien associé à l'irrationnel $\alpha$ et dont le mot biprolongeable est v.

On écrit la décomposition de $\alpha$ en fraction continue : $\alpha=\cfrac{1}{a_1+\cfrac{1}{a_2+\ddots}}$

Alors $\sigma_a^{a_1-1}\sigma_b^{a_2}\sigma_a^{a_3}\ldots\sigma_b^{a_{2k}}(a)$ et $\sigma_a^{a_1-1}\sigma_b^{a_2}\sigma_a^{a_3}\ldots\sigma_b^{a_{2k}}(b)$ sont des préfixes de abv et bav respectivement.

Ce résultat qui peut sembler abscons donne en fait des informations précises sur la structure du mot. Par exemple, le mot correspondant sera composé de $a_2$ ou $a_2-1$ séquences successives $b(a^{a_1-1})$ entrecoupées de séquences $b(a^{a_1})$ , etc.

Cette relation fournit de plus un algorithme rapide (en $O(\log n)$ ) pour calculer des approximations d'un mot sturmien ainsi que pour retrouver l'angle à partir du mot.

Illustration avec le mot de Fibonacci

On construit par récurrence une suite de mots en partant des deux mots a et ab et en concaténant à chaque étape les deux mots précédents, de manière analogue à la construction de la suite de Fibonacci ( $w_{n+2}=w_{n+1}w_n$ ). La suite ainsi définie converge vers le mot de Fibonacci.

C'est aussi le point fixe de l'application contractante sur l'ensemble des mots (finis et infinis) qui consiste à remplacer les a par des ab et les b par des a.

C'est, enfin, et de manière surprenante, le mot biprolongeable du système sturmien associé à $1/\phi^2$ où $\phi$ est le nombre d'or.

Conclusion

On a obtenu une triple caractérisation des mots sturmiens (complexité, équilibre, rotations)

On a aussi une triple caractérisation des systèmes sturmiens (opérateur S, langage, angle de la rotation).

Petite bibliographie

Sujet de l'agrégation de mathématiques 1994, option Mathématiques de l'informatique.

C. Bourguignat, T. Fajour et R. Zara, Complexité de suites. Suites sturmiennes, in Quadrature 26 (1996).

Back to: Main Page > Mathématiques

To leave a comment: contact (domain) yann-ollivier.org