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

modifier

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  , on peut voir cette transformation comme une fonction   qui associe à toute position initiale   une position   après une étape de pétrissage.

Si l'on partitionne l'espace du système en deux intervalles   et  , on peut associer à toute orbite   une suite   d'entiers   et   indiquant à chaque étape dans quel intervalle se trouve la fève si on la placée initialement en position  .

Il n'est pas difficile de voir que dans ce cas, la suite   est en bijection avec le développement binaire du réel   (en inversant le  -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   étapes, il faut connaître le  -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

modifier

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

 

par

 .

La même définition vaut pour les mots infinis bilatères. Dans ce cas,   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   est un ensemble   non vide de mots infinis sur   qui est

  1. fermé pour l’opérateur de décalage  ,
  2. fermé pour la topologie.

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

Caractérisation

modifier

Un ensemble   de mots infinis sur   est un système dynamique symbolique si et seulement s'il existe un ensemble   de mots finis sur   tel que   est l'ensemble des mots infinis sur   dont aucun facteur n'est dans  . L'ensemble   est parfois appelé ensemble de facteurs interdits. Noter que l'ensemble   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   est fini, le système dynamique   est appelé système de type fini, et lorsque l'ensemble   est un langage rationnel, le système   est un système sofique.

Exemples

modifier
  1. L'ensemble   de tous les mots infinis sur   est appelé le full shift en anglais. C'est un système de type fini (l'ensemble   des facteurs interdits est vide).
  2. Soit  . L'ensemble des mots infinis ne contenant pas le facteur   est un système de type fini.
  3. Toujours sur  , l'ensemble des mots contenant au plus un   est un système sofique qui n'est pas de type fini. L'ensemble   des facteurs interdits est le langage rationnel  .

Propriétés

modifier

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   engendré par le mot infini   est la clôture topologique de l'ensemble des décalés de  .
  • Un mot   appartient à   si et seulement si tout facteur de   est facteur de  . Ainsi, un système dynamique   est minimal si et seulement si   pour tout   de  .
  • 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

modifier
  • 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

modifier
  • Jacques Hadamard, « Les surfaces à courbures opposées et leurs lignes géodésiques », Journal de Mathématiques Pures et Appliquées, vol. 4,‎ , p. 27
  • Douglas Lind et Brian Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge, Cambridge University Press, , 495 p. (ISBN 0-521-55900-6, présentation en ligne)
  • M. Lothaire, Algebraic Combinatorics on Words, Cambridge, Cambridge University Press, , 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, no 4,‎ , 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, no 4,‎ , p. 30-375 (lire en ligne)
  • Gustav A. Hedlund, « Sturmian minimal sets », Amer. J. Math., vol. 66,‎ , 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, no 2,‎ , 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 », , 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,‎ , article no 103529 (DOI 10.1016/j.jcss.2024.103529, arXiv 2112.14499)

Notes et références

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

Voir aussi

modifier