Suite de Prouhet-Thue-Morse

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

En mathématiques, en informatique théorique, en combinatoire des mots et ses applications, la suite de Prouhet-Thue-Morse, également appelée suite de Thue-Morse, est une suite binaire. Elle commence par :

t=0 1 10 1001 10010110 1001011001101001...

Cette suite infinie est la suite A010060 de l'OEIS. C'est une suite automatique.

Histoire[modifier | modifier le code]

La suite de Prouhet-Thue-Morse a été utilisée pour la première fois de façon implicite par le mathématicien français Eugène Prouhet en 1851, pour donner une solution à un problème de théorie des nombres appelé depuis le problème de Prouhet-Tarry-Escott[1].

Le mathématicien norvégien Axel Thue l'a découverte et utilisée dans un article publié en 1912 qui, avec un autre article datant de 1906, est l'article fondateur de la combinatoire des mots. Cet article a été longtemps méconnu. La suite a été redécouverte par Marston Morse en 1921. Morse l'a utilisée pour donner un exemple d'une suite uniformément récurrente (la définition est donnée plus loin) non périodique, résolvant ainsi un problème de géométrie différentielle.

La suite a été redécouverte indépendamment plusieurs fois, pas toujours par des mathématiciens professionnels. Par exemple, Max Euwe, un champion d'échecs et professeur de mathématiques, l'a découverte en 1929 pour une application aux échecs, prouvant, par ce biais, qu'il existe des parties infinies ne comportant pas de répétition des trois mêmes coups. En 1944, Marston Morse et Gustav Hedlund ont développé cet aspect.

Définition[modifier | modifier le code]

Il y a plusieurs manières équivalentes de définir cette suite.

Relation de récurrence[modifier | modifier le code]

Construction de la suite de Prouhet-Thue-Morse : chaque bloc est obtenu par concaténation du bloc précédent avec son opposé.

La suite de Prouhet-Thue-Morse est la suite t=(t_n) qui satisfait t_0 = 0 et

\begin{array}{lcl}t_{2n}&{\!\!\!=\!\!\!}&t_n\\t_{2n+1}&{\!\!\!=\!\!\!}&1-t_n\end{array}

pour tous les entiers naturels n. Cette définition peut s'interpréter comme suit : si l'on ne conserve, dans la suite t, que les termes d'indices pairs, on retrouve la suite t ; si en revanche on ne garde que les termes d'indices impairs, on obtient la suite opposée, où les 0 et 1 ont été échangés.

Une autre relation de récurrence[modifier | modifier le code]

Soient u_n et v_n les suites de mots définis par :

\begin{array}{lcl}u_{0}&{\!\!\!=\!\!\!}&0\\u_{n+1}&{\!\!\!=\!\!\!}&u_nv_n\end{array}
\quad\begin{array}{lcl}v_{0}&{\!\!\!=\!\!\!}&1\\v_{n+1}&{\!\!\!=\!\!\!}&v_nu_n.\end{array}

Alors

t=\lim_{n\to\infty}u_n=0v_1v_2\cdots v_n\cdots

On a en fait v_n=\overline{u_n}, où le mot surligné est l'opposé (obtenu en échangeant les 0 et 1). C'est cette méthode qui est illustrée dans la figure.

Une définition directe[modifier | modifier le code]

Automate de Prouhet-Thue-Morse.

t_n est égal à la somme, modulo 2, des chiffres dans le développement binaire de n. Par exemple, (18)_2=10010, et donc t_{18}=0. Ce calcul est réalisé par l'automate de Prouhet-Thue-Morse : partant de l'état initial, on suit les transitions indiquées par les bits du développement binaire. L'état d'arrivé, selon qu'il est jaune ou rose, indique que la valeur de la suite est 0 ou 1. Pour (18)_2=10010, on obtient :

a0\xrightarrow1b1\xrightarrow0b1\xrightarrow0b1\xrightarrow1a0\xrightarrow0a0

et la valeur est donc 0.

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

La suite t est obtenue aussi en itérant le morphisme \mu appelé parfois le morphisme de Thue-Morse suivant :

\begin{array}{lcl}0\mapsto01\\1\mapsto10\end{array}

Les premières itérations à partir de 0 donnent :

\begin{array}{lcl}\mu^0(0)=0\\\mu^1(0)=01\\
\mu^2(0)=0110\\\mu^3(0)=01101001\\\mu^4(0)=0110100110010110\end{array}

Si l'on itère à partir de 1, on obtient la suite opposée.

Un produit infini[modifier | modifier le code]

La suite est aussi définie par :

 \prod_{i=0}^\infty(1 - x^{2^i}) = \sum_{j=0}^\infty(-1)^{t_j} x^j.

Propriétés[modifier | modifier le code]

  • La suite de Prouhet-Thue-Morse est uniformément récurrente : pour tout entier n, il existe un entier N tel que tout facteur de longueur N contient tous les facteurs de longueur n.
  • La suite de Prouhet-Thue-Morse est sans cube : aucun bloc n'est répété trois fois consécutivement. En revanche, elle contient des carrés arbitrairement longs. Axel Thue a prouvé que la suite est sans chevauchement : aucun bloc n'est de la forme axaxa, où a est un des symboles 0 ou 1 et x est un bloc.
  • La constante de Prouhet-Thue-Morse est le nombre \tau\, dont le développement binaire est la suite de Prouhet-Thue-Morse, c’est-à-dire le nombre  \tau = \sum_{i=0}^{\infty} \frac{t_i}{2^{i+1}} = 0,412454033640 \ldots C'est un nombre transcendant.

Suite de Prouhet-Thue-Morse et nombres normaux[modifier | modifier le code]

Complexité combinatoire[modifier | modifier le code]

La complexité combinatoire de la suite de Prouhet-Thue-Morse est par définition la fonction c_t(n) qui donne le nombre de blocs distincts de longueur n de la suite. Les premières valeurs de cette fonction sont

Fonction de complexité de la suite de Prouhet-Thue-Morse
n 0 1 2 3 4 5 6 7 8 9 10
c_t(n) 1 2 4 6 10 12 16 20 22 24 28

C'est la suite A005942 de l'OEIS. La formule qui donne les valeurs est la suivante : Pour n\ge 1, soit k\ge0 l'entier tel que 2^k+1\le n\le 2^{k+1}, et soit r tel que n=2^k+r, avec 1\le r \le 2^k. Alors

c_t(n)=\begin{cases}
  3\cdot 2^k+4(r-1)&\text{si } 1\le r\le 2^{k-1},\\
  4\cdot 2^k+2(r-1)&\text{si } 2^{k-1}+1\le r\le 2^k.
\end{cases}

Comme toutes les fonctions de complexités des suites automatiques, cette fonction croît au plus linéairement. De fait, on peut prouver que c_t(n)\le \frac{10}3n.

Suite aux positions carrées[modifier | modifier le code]

La suite de Prouhet-Thue-Morse est certainement pas une suite normale, puisque dans une suite normale tous les facteurs apparaissent, et deux facteurs de même longueur apparaissent avec la même frquence asymptotique. Mais il est va autrement d'une suite associée à la suite de Prouhet-Thue-Morse t, qui est la suite extraite aux positions qui sont des carrés. C'est la suite u donnée par :

u_n=t_{n^2}

La suite commence par

0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1,

C'est la suite A010060 de l'OEIS. Cette suite a fait l'objet de plusieurs études : Allouche et Shallit [2] se demandent si la complexité de la suite u est maximale, c'est-à-dire si le nombre c_u(n) de facteurs de longueur n de la suite u vérifie c_u(n)=2^n. Une réponse positive à cette question est donnée par Moshe en 2007[3]. Mauduit et Rivat montrent[4] que les 0 et les 1 apparaissent dans u avec la même fréquence asymptotique 1/2. Ceci à son tour résout une conjecture longtemps ouverte de Gelfond[5]. La grande nouveauté est un résultat annoncé par Drmota, Mauduit, et Rivat en 2013. Ils prouvent[6] que la suite u est normale.

Suite bilatère[modifier | modifier le code]

La suite de Prouhet-Thue-Morse peut être étendue en une suite indicée par \Z en posant

t_{-i}=t_{i-1}\quad(i\ge1)

On obtient donc (un point central est placé avant t_0) la suite :

. . .0110 1001 1001 0110.0 1 10 1001 10010110 1001011001101001...

Cette suite est encore une suite sans chevauchement. De plus, le système dynamique engendré par cette suite est exactement l'ensemble des suite bilatères sans chevauchement.

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

  1. M. E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres, C. R. Acad. Sci. Paris, série I, 33, (1851), 225
  2. Allouche et Shallit 2003, Problem 10.12.7.
  3. Y. Moshe, « On the subword complexity of Thue-Morse polynomial extractions », Theoret. Comput. Sci., vol. 38,‎ 2007, p. 318–329.
  4. C. Mauduit et J. Rivat, « La somme des chiffres des carrés », Acta Math., vol. 203,‎ 2009, p. 107-148.
  5. A. O. Gelfond, « Sur les nombres qui ont des propriétés additives et multiplicatives données », Acta Arith., vol. 13,‎ 1967/1968, p. 259-265.
  6. M. Drmota, C. Mauduit et J. Rivat, « The Thue-Morse Sequence Along The Squares is Normal, Abstract », Congrès du ÖMG-DMV,‎ 2013, p. 80 (lire en ligne). (Préprint ici).

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]