Suite de Prouhet-Thue-Morse

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

t = 01101001100101101001011001101001...

Cette suite infinie est la suite A010060 de l’OEIS.

Définition

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

Relation de récurrence

Construction de la suite de Prouhet-Thue-Morse.

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

t_2n = t_n

t_{2n + 1} = 1 − t_n

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

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

$\begin{array}{ll}u_{0}&=0\\u_{n+1}&=u_nv_n\end{array} \quad\begin{array}{ll}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$

Un produit infini

La suite peut être aussi définie par:

$\prod_{i=0}^{\infty} (1 - x^{2^{i}}) = \sum_{j=0}^{\infty} (-1)^{t_j} x^{j} \mbox{,} \!$

Histoire

La suite de Prouhet-Thue-Morse a été décrite pour la première fois par le mathématicien français Eugène Prouhet en 1851. Il l'a utilisé pour donner une solution à un problème de théorie des nombres qui s'appelle le problème de Prouhet-Tarry-Escott (en).

Le mathématicien norvégien Axel Thue l'a découverte et utilisée dans un article publié en 1906 qui 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 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 (de) ont développé cet aspect.

Propriétés

• La suite de Prouhet-Thue-Morse est sans cube: aucun bloc n'est répété trois fois consécutivement. Axel Thue a prouvé que la suite est même 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.

Références

• Jean-Paul Delahaye, « Des mots magiques infinis » , Pour la Science n°347, sept 2006, p. 90-95

• Allouche, J.-P.; Shallit, J. O., Automatic sequences, Cambridge University Press, 2003.

Liens externes

• Allouche, J.-P., Shallit, J. O., The Ubiquitous Prouhet-Thue-Morse Sequence. Contient de nombreuses propriétés et références.

• (en) Eric W. Weisstein, « Thue-Morse Sequence », MathWorld Quelques autres applications