Suite automatique

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

En mathématique, en combinatoire des mots et en théorie des automates, une suite automatique (ou suite -automatique est un entier) est une suite infinie de symboles qui peut être caractérisée de plusieurs manières: par Automate fini déterministe, par morphisme uniforme, par noyau ou par Série formelle. Par exemple, pour un automate fini, on définit une suite automatique de la façon suivante : le n-ième terme est fonction de l'état atteint par lecture de la représentation de l'entier en base [1]. L'exemple par excellence d'une suite 2-automatique est la suite de Prouhet-Thue-Morse.

Un nombre réel automatique (plus précisément un nombre réel -automatique) est un nombre réel dont le développement en base est une suite automatique, pour un entier [2]. Tout nombre réel automatique est soit rationnel, soit transcendant[3]. Ceci fournit une large classe de nombres transcendants. Par exemple, la constante de Prouhet-Thue-Morse 0,412 454 033 640..., dont le développement binaire est donné par la suite 0,0110100110010110..., est un nombre transcendant.

Suite automatique[modifier | modifier le code]

Il existe quatre méthodes équivalentes pour définir les suites automatiques.

Définitions[modifier | modifier le code]

Définition par automate[modifier | modifier le code]

Préliminaires sur les automates:

Soit un entier. Soit un automate fini déterministe complet où :

  • est un alphabet égal à
  • est l'ensemble des états
  • est l'état initial
  • est une application de dans appelée fonction de transition
  • est une application qui étiquette les états de l'automate par des symboles de .

NB: L'état final n'intervient pas pour une suite -automatique

On généralise à l'ensemble des mots de en posant:

est le mot vide

et

Définition d'une suite -automatique par automate:

Soit un ensemble fini, et soit une application qui étiquette les états de l'automate par des symboles de .

Soit , on note l'écriture en base de l'entier .

On définit une suite de la manière suivante: . Concrètement est le symbole de l'alphabet associé à l'état atteint par lecture du mot .

La suite -automatique définie par est la suite (concaténation de tous les termes de la suite )

L'automate est appelé automate déterministe avec sortie (en anglais DFAO)[4]. Ne pas confondre avec l'automate de Mealy, ou l'automate de Moore.

Exemple:

La suite de Prouhet-Thue-Morse peut être définie par l'automate et l'application suivante:

Automate de Prouhet-Thue-Morse. Notation: est l'état avec C'est un exemple de DFAO.

On prend un automate fini déterministe complet et où :

  • est l'état initial

En utilisant l'écriture binaire des entiers naturels (cf Système binaire), on peut voir qu'après lecture du mot on est sur si il y avait un nombre pair de 1 dans l'écriture de et inversement pour être en .

Ce qui donne :

qui est le début de la suite de Prouhet-Thue-Morse.

Définition par morphisme uniforme[modifier | modifier le code]

Préliminaire sur les morphismes:

Soit , un alphabet et .

  • Un morphisme est -uniforme si (c'est à dire que l'image de tout élément de est un mot de longueur )
  • Un morphisme -uniforme est -prolongeable si commence par [5]
  • Si est une application, on peut la prolonger en qui étiquette les mots de longueurs infini.

Avec

avec et

Définition d'un suite -automatique par morphisme uniforme:

Soit , un alphabet et .

Soit un morphisme -uniforme et -prolongeable.

La suite des itérés a la propriété suivante: est un préfixe de .

On peut alors parler de convergence de la suite vers un mot de taille infini noté . Ce mot est purement morphique.

Soit un alphabet et soit une application. Elle est étendue en un morphisme lettre à lettre sur les mots infinis noté .

La suite est une suite morphique. C'est la deuxième définition des suites -automatiques[6].

Exemples:

qui engendre le mot infini qui, suivi du morphisme qui envoie sur et laisse et inchangés donne

Construction de la suite de Prouhet-Thue-Morse par morphisme 2-uniforme

qui engendre le mot infini qui, suivi du morphisme qui envoie sur et laisse et inchangés donne la constante de Prouhet-Thue-Morse en écriture binaire.

Remarque:

Lorsque , l'écriture en base d'une entier est composée de symboles identiques. Dans ce cas, l'automate considéré opère sur un alphabet à une seule lettre. La définition par morphisme ne s'étend en revanche pas. On peut vérifier qu'un ensemble 1-automatique est exactement l'union d'un ensemble fini, et d'une union finie de progressions arithmétiques infinies.

Définition par noyau[modifier | modifier le code]

Soit une suite infinie. Le -noyau de est l'ensemble des sous-suites

.
Construction du -noyau de la suite de Prouhet-Thue-Morse avec le triplet En rouge et vert, les deux suites du -noyau.

Cette définition un peu compliquée s'explique bien pour  : le -noyau est formé de la suite , puis des 2 suites obtenues en prenant un terme sur deux dans , puis des 4 suites obtenues en prenant un terme sur 4, etc.

La caractérisation, ou la troisième définition, est la suivante : une suite est -automatique si et seulement si son -noyau est fini.

Exemple:

En s’intéressant au -noyau de la suite de Prouhet-Thue-Morse, on remarque que celui-ci ne contient que deux suites: la suite elle même et son contraire.

Ce qui montre que la suite de Prouhet-Thue-Morse est une suite -automatique pour la définition par noyau.

Définition par série formelle algébrique[modifier | modifier le code]

Les suites -automatiques, lorsque est un nombre premier, ont une caractérisation par séries formelles. On note le corps de fractions rationnelles, et l'anneau des séries formelles en une variable et à coefficients dans . Une série est algébrique sur s'il existe des polynômes tels que

.

Nous prenons pour corps le corps à éléments.

Théorème (Christol (de))[7] —  Soit une suite à éléments dans un alphabet . On suppose que est un sous-ensemble de pour un entier positif . Alors est -automatique si et seulement si la série

est algébrique sur .

Exemples:

.

On a

.

Sur , on a , ce qui donne l'équation : . Ceci montre que est algébrique sur . Donc la suite des puissances de 2 est -automatique.

avec [8]

On a : sur . Ce qui montre que la suite de Prouhet-Thue-Morse est une suite -automatique [8]

Exemples de suites automatiques[modifier | modifier le code]

Les suites suivantes sont automatiques :

  • La suite de Prouhet-Thue-Morse
  • Le mot infini ternaire de Thue-Morse, qui est un mot sans carré
  • Le mot infini d'Arshon, qui est un autre mot sans carré
  • La suite de Rudin-Shapiro
  • La suite de Baum et Sweet
  • Les suites de pliage de papier sont automatiques si elles sont régulières.
  • Un autre exemple est le mot infini, appelé mot de Sierpiński par Anna Frid[9], et qui est lié à l'ensemble triadique de Cantor. C'est le mot purement morphique qui est le point fixe du morphisme 3-uniforme On obtient successivement Les dans ce mot infini sont aux positions des entiers naturels dont l'écriture en base 3 ne comporte pas le chiffre 1.

La suite de Fibonacci, et les suites sturmiennes ne sont pas automatiques.

Propriétés sur les suites automatiques[modifier | modifier le code]

Influence de la base[modifier | modifier le code]

La propriété principale est le théorème de Cobham qui énonce que le fait d'être -automatique dépend fortement de l'entier . Deux entiers et sont dits multiplicativement dépendants s'il existe des entiers et tels que . Par exemple et sont multiplicativement dépendants parce que .

Théorème (Cobham) — Soient et deux entiers multiplicativement indépendants. Une suite est à la fois -automatique et -automatique seulement si elle est -automatique[10].

En complément de ce théorème, il y a la proposition suivante :

Proposition — Si et sont deux entiers multiplicativement dépendants, alors les suites -automatique sont les mêmes que les suites -automatiques.

Robustesse[modifier | modifier le code]

Les suites automatiques sont stables pour un certain nombre de transformations.

  • Si deux suites ne diffèrent que par un nombre fini de termes, et l'une est -automatique, alors l'autre est également -automatique.
  • Si est une suite -automatique sur un alphabet , et si est un morphisme uniforme, alors la suite obtenue par concaténations des mots est -automatique.
  • Si est une suite -automatique, alors la sous-suite est -automatique pour tous entiers .

Complexité en facteurs[modifier | modifier le code]

Le nombre de facteurs de longueur d'une suite automatique croît au plus linéairement.

Nombres réels automatiques[modifier | modifier le code]

Un nombre réel automatique est un nombre réel dont le développement en base est une suite -automatique[2]. Un nombre réel automatique est soit rationnel, soit transcendant[3]. Ainsi, le nombre (binaire) de Thue-Morse, appelé la constante de Prouhet-Thue-Morse :

est un nombre transcendant.

Notes et références[modifier | modifier le code]

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

  1. Allouche et Shallit 2003, p. 152.
  2. a et b Hejhal 1999, p. 556.
  3. a et b (en) Boris Adamczewski et Yann Bugeaud, « On the complexity of algebraic numbers. I. Expansions in integer bases », Ann. of Math, vol. 165, no 2,‎ , p. 547-565.
  4. Allouche et Shallit 2003.
  5. (en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, (ISBN 9780521823326, lire en ligne), p. 175
  6. Allouche et Shallit 2003, p. 175.
  7. Allouche et Shallit 2003, p. 356.
  8. a et b (en) « What is an automatic sequence? »
  9. (en) Anna E. Frid, « Arithmetical complexity of the symmetric D0L words », Theoretical Computer Science, vol. 306,‎ , p. 535-542 (DOI 10.1016/S0304-3975(03)00345-1).
  10. Allouche et Shallit 2003, p. 345-350.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « automatic sequence » (voir la liste des auteurs).

Bibliographie[modifier | modifier le code]

  • (en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences, Cambridge University Press, (ISBN 0-521-82332-3) Document utilisé pour la rédaction de l’article
  • (en) Dennis A. Hejhal (en), Emerging applications of number theory, Springer, coll. « The IMA volumes in mathematics and its applications » (no 109), (ISBN 0387988246)
  • (en) Alan Cobham, « Uniform tag sequences », Math. Systems Theory, vol. 6,‎ , p. 164-192
  • (en) Boris Adamczewski et Yann Bugeaud, « Transcendence and Diophantine approximation », dans Valérie Berthé et Michel Rigo (éditeurs), Combinatorics, automata and number theory, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (no 135), (ISBN 978-0-521-51597-9, lire en ligne), p. 410- 451

Article connexe[modifier | modifier le code]

Théorème d'Eisenstein