Dynamique symbolique

En mathématiques, la dynamique symbolique est une branche de l'étude des systèmes dynamiques. Cela consiste à étudier un système en partitionnant l'espace en un nombre fini de régions et en s'intéressant aux suites possibles de régions traversées lors de l'évolution du système. Si l'on associe à chaque région un symbole, on peut associer à chaque trajectoire une suite (infinie) de symboles, d'où le nom de « dynamique symbolique ».

Les trajectoires symboliques ne sont bien sûr qu'une approximation des trajectoires réelles, mais elles peuvent refléter certaines propriétés du système réel comme la transitivité, la récurrence ou l'entropie.

Une introduction générale au domaine est donné dans le manuel de Lind et Marcus (1995). Parmi les articles précurseurs, on peut citer Morse et Hedlund (1938) et Hedlund (1969). Ethan M. Coven et Zbigniew H. Nitecki (2008) considèrent que la dynamique symbolique, en tant que discipline autonome, débute véritablement avec l'article de Hedlund (1944).

Exemple

Un exemple simple illustrant cette approche est la transformation du boulanger. Il s'agit d'un système unidimensionnel modélisant le pétrissage d'une pâte par un boulanger : le boulanger étire la pâte jusqu'à doubler sa longueur, puis la replie sur elle-même pour retrouver la longueur initiale et itère le processus. Cette transformation est souvent évoquée comme exemple de système chaotique car la trajectoire d'une fève placée dans la pâte durant ce processus de pétrissage est sensible aux conditions initiales.

Si l'on identifie la pâte à l'intervalle $[0;1]$ , on peut voir cette transformation comme une fonction $T:[0;1]\rightarrow [0;1]$ qui associe à toute position initiale $x$ une position $T(x)$ après une étape de pétrissage.

Si l'on partitionne l'espace du système en deux intervalles $I_{0}=[0;1/2[$ et $I_{1}=[1/2;1]$ , on peut associer à toute orbite $(T^{n}(x))_{n\in \mathbb {N} }$ une suite $X$ d'entiers $0$ et $1$ indiquant à chaque étape dans quel intervalle se trouve la fève si on la placée initialement en position $x$ .

Il n'est pas difficile de voir que dans ce cas, la suite $X$ est en bijection avec le développement binaire du réel $x$ (en inversant le $n$ -ième chiffre si le nombre de 1 obtenus jusque-là est impair). En particulier, la sensibilité aux conditions initiales du système apparaît clairement puisque pour savoir dans quelle moitié de pâte se trouve la fève après $n$ étapes, il faut connaître le $n$ -ième chiffre du développement binaire de sa position initiale.

La dynamique symbolique ne s'applique pas uniquement à des systèmes aussi élémentaires : Hadamard (1898) utilise cette approche pour étudier des flots géodésiques sur des surfaces à courbure négative.

Définitions

L'opérateur de décalage $\sigma$ (shift en anglais) est défini, pour tout mot infini

x=a_{0}a_{1}\cdots a_{n}\cdots

par

\sigma (x)=a_{1}\cdots a_{n}\cdots

.

La même définition vaut pour les mots infinis bilatères. Dans ce cas, $\sigma$ est une bijection. L'opérateur de décalage est une fonction continue pour la topologie de Cantor.

Un système dynamique symbolique (en anglais subshift ou shift space) sur l'alphabet $A$ est un ensemble $S$ non vide de mots infinis sur $A$ qui est

fermé pour l’opérateur de décalage $\sigma$ ,
fermé pour la topologie.

La même définition vaut pour les mots infinis bilatères.

Caractérisation

Un ensemble $S$ de mots infinis sur $A$ est un système dynamique symbolique si et seulement s'il existe un ensemble $X$ de mots finis sur $A$ tel que $S$ est l'ensemble des mots infinis sur $A$ dont aucun facteur n'est dans $X$ . L'ensemble $X$ est parfois appelé ensemble de facteurs interdits. Noter que l'ensemble $X$ n'est pas unique.

Cette caractérisation permet de traduire des propriétés de systèmes dynamiques symboliques en propriétés combinatoires.

Lorsque l'ensemble $X$ est fini, le système dynamique $S$ est appelé système de type fini, et lorsque l'ensemble $X$ est un langage rationnel, le système $S$ est un système sofique.

Exemples

L'ensemble $A^{\mathbb {N} }$ de tous les mots infinis sur $A$ est appelé le full shift en anglais. C'est un système de type fini (l'ensemble $X$ des facteurs interdits est vide).
Soit $A=\{a,b\}$ . L'ensemble des mots infinis ne contenant pas le facteur $bb$ est un système de type fini.
Toujours sur $A=\{a,b\}$ , l'ensemble des mots contenant au plus un $b$ est un système sofique qui n'est pas de type fini. L'ensemble $X$ des facteurs interdits est le langage rationnel $ba^{*}b$ .

Propriétés

Un système dynamique est minimal s'il ne contient strictement aucun autre système dynamique.

Morse a prouvé que tout système dynamique contient un système dynamique minimal.
Le système dynamique $X=Cl(O(x))$ engendré par le mot infini $x$ est la clôture topologique de l'ensemble des décalés de $x$ .
Un mot $y$ appartient à $X=Cl(O(x))$ si et seulement si tout facteur de $y$ est facteur de $x$ . Ainsi, un système dynamique $S$ est minimal si et seulement si $Cl(O(x))=S$ pour tout $x$ de $S$ .
Un système dynamique minimal est soit apériodique, soit périodique (et dans ce cas il est composé d'une orbite périodique). Il est apériodique si et seulement si l'ensemble des mots spéciaux à droite (resp. gauches) est infini.
On a la propriété suivante^[1] : Un système dynamique est minimal si et seulement s'il est uniformément récurrent.

Exemples

Le système engendré par le mot de Prouhet-Thue-Morse est minimal. Le mot opposé au mot de Prouhet-Thue-Morse (obtenu en échangeant les lettres) a les mêmes facteurs que le mot de Prouhet-Thue-Morse lui-même. Ils engendrent le même système
Tout mot sturmien engendre un système minimal. Ce système est composé des mots sturmiens de même pente.

Bibliographie

Jacques Hadamard, « Les surfaces à courbures opposées et leurs lignes géodésiques », Journal de Mathématiques Pures et Appliquées, vol. 4,‎ 1898, p. 27
Douglas Lind et Brian Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge, Cambridge University Press, 1995, 495 p. (ISBN 0-521-55900-6, présentation en ligne)
M. Lothaire, Algebraic Combinatorics on Words, Cambridge, Cambridge University Press, 2002, 504 p. (ISBN 0-521-81220-8, lire en ligne), « Finite and Infinite Words »
Marston Morse et Gustav A. Hedlund, « Symbolic Dynamics », American Journal of Mathematics, vol. 60, n^o 4,‎ 1938, p. 815–866 (DOI 10.2307/2371264, JSTOR 2371264)
Gustav A. Hedlund, « Endomorphisms and automorphisms of the shift dynamical system », Math. Systems Theory, vol. 3, n^o 4,‎ 1969, p. 30-375 (lire en ligne)
Gustav A. Hedlund, « Sturmian minimal sets », Amer. J. Math., vol. 66,‎ 1944, p. 605-620 (MR 0010792)

Ethan M. Coven et Zbigniew H. Nitecki, « On the genesis of symbolic dynamics as we know it », Colloq. Math., vol. 110, n^o 2,‎ 2008, p. 227-242

Fabien Durand et Dominique Perrin, Dimension groups and dynamical systems: substitutions, Bratteli diagrams and Cantor systems, Cambridge University Press, coll. « Cambridge studies in advanced mathematics », 2022, viii + 584 (ISBN 978-1-108-83868-9)

Marie-Pierre Béal, Dominique Perrin et Antonio Restivo, « Decidable problems in substitution shifts », Journal of Computer and System Sciences, vol. 143,‎ 1^er août 2024, article n^o 103529 (DOI 10.1016/j.jcss.2024.103529, arXiv 2112.14499)

Notes et références

↑ Martine Queffélec, Substitution dynamical systems, spectral analysis, Springer-Verlag, coll. « Lecture notes in mathematics » (n^o 1294), 2010, 2^e éd., xv+351p. (ISBN 978-3-642-11211-9) : Proposition 2.3

Voir aussi

Portail des mathématiques

[1] Martine Queffélec, Substitution dynamical systems, spectral analysis, Springer-Verlag, coll. « Lecture notes in mathematics » (n^o 1294), 2010, 2^e éd., xv+351p. (ISBN 978-3-642-11211-9) : Proposition 2.3

[1]