Dynamique symbolique

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

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.

On trouvera une introduction générale au domaine dans 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 | modifier le code]

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 \scriptstyle 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 \scriptstyle\bigl(T^n(x)\bigr)_{n\in\N} une suite X de 0 et de 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, le système symbolique nous renseigne parfaitement sur le système réel : 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 niè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 | modifier le code]

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

x=a_0a_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

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

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

Caractérisation[modifier | modifier le code]

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 le système S est un système sofique.

Exemples[modifier | modifier le code]

  1. L'ensemble A^\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).
  2. Soit A=\{a,b\}. L'ensemble des mots infinis ne contenant pas le facteur bb est une système de type fini.
  3. 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é[modifier | modifier le code]

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 Cl(O(x)) engendré par le mot infini x est la clôture topologique de l'ensemble des décalés de x. Un système dynamique est minimal si et seulement s'il est le système dynmique engendré par un mot uniformément récurrent.
  • Un mot y appartient à 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.

Exemples[modifier | modifier le code]

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

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

  • 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 University Press,‎ 1995 (ISBN 0521559006, présentation en ligne)
  • M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press,‎ 2002 (ISBN 0521812208, lire en ligne), « Finite and Infinite Words »
  • Marston Morse et Gustav A. Hedlund, « Symbolic Dynamics », American Journal of Mathematics, vol. 60, no 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, no 4,‎ 1969, p. 30-375 (lire en ligne)
  • Gustav A. Hedlund, « Sturmian minimal sets », Amer. J. Math., vol. 66,‎ 1944, p. 605-620
  • Ethan M. Coven et Zbigniew H. Nitecki, « On the genesis of symbolic dynamics as we know it », Colloq. Math., vol. 110, no 2,‎ 2008, p. 227-242

Voir aussi[modifier | modifier le code]