suite de Prouhet-Thue-Morse

Écrivez 0. Remplacez-le par 01, puis remplacez simultanément chaque 0 par 01 et chaque 1 par 10. Les débuts successifs sont 0, 01, 0110, puis 01101001. À chaque étape, le mot précédent revient en premier, suivi de son complément où 0 et 1 sont échangés.

En répétant indéfiniment ce geste, on obtient la suite de Prouhet-Thue-Morse. Sa régularité vient d'une règle très courte, mais elle ne se réduit pas à la répétition périodique d'un bloc.

La suite de Prouhet-Thue-Morse est une suite infinie de termes égaux à 0 ou à 1. Dans la convention qui commence à l'indice 0, on part du mot 0 et l'on applique simultanément la substitution 0 → 01 et 1 → 10. La limite des mots 0, 01, 0110, 01101001, … commence donc par 0110100110010110.

Pour calculer directement un terme, on note t_n le terme d'indice n, avec n entier positif ou nul. On écrit n en base 2, puis on compte ses chiffres 1 : t_n vaut 0 si ce nombre est pair et 1 s'il est impair. Cette règle donne notamment t₀ = 0.

Une seconde convention échange partout 0 et 1 ; elle commence par 1001011001101001. C'est le complément terme à terme de la première suite. Les deux conventions portent couramment le même nom, à condition d'annoncer le symbole initial ou la règle de parité retenue.

La construction réunit quatre éléments. L'alphabet {0, 1} fournit les deux symboles. Le mot initial, ici 0, fixe la convention. La substitution associe 01 à 0 et 10 à 1. Enfin, l'indice n repère chaque terme à partir de 0.

Le mot initial et la substitution déterminent ensemble tous les préfixes : chaque passage double leur longueur. La règle sur l'écriture binaire relie ensuite l'indice au symbole sans reconstruire les étapes précédentes. Échanger le mot initial 0 contre 1 échange tous les termes, mais conserve le même mécanisme d'auto-similarité. Ces données suffisent à produire n'importe quel préfixe ou à calculer un terme isolé.

Construisons le préfixe de longueur 16 et contrôlons son terme d'indice 13. Les données sont le mot initial 0, les substitutions 0 → 01 et 1 → 10, ainsi que la numérotation à partir de l'indice 0. La figure rend visibles les quatre premiers doublements.

1. À partir de 0, une substitution donne 01.
2. En substituant simultanément les deux symboles, on obtient 0110.
3. Le passage suivant donne 01101001.
4. Un dernier passage donne 0110100110010110.

Pour le contrôle, l'entier 13 s'écrit 1101 en base 2. Cette écriture contient trois chiffres 1, nombre impair : le terme t₁₃ vaut donc 1. Le symbole d'indice 13, quatorzième symbole du préfixe obtenu, est bien 1.

Pour produire un long préfixe, la substitution est le geste naturel : chaque tour double d'un coup le nombre de symboles. Pour obtenir seulement t_n, compter les 1 de l'écriture binaire de n évite de construire tous les termes précédents.

Dans l'étude des mots, on inspecte les blocs qui réapparaissent et la façon dont un préfixe engendre son complément. Une suite périodique convient si l'on veut répéter un motif fixe ; Prouhet-Thue-Morse convient lorsque l'on veut une règle déterministe sans période globale.

La source retrace aussi plusieurs emplois historiques : Prouhet en 1851 pour une répartition d'entiers, Thue en 1906 en combinatoire des mots, Morse en 1921 pour des géodésiques récurrentes et Euwe en 1929 à propos de parties d'échecs sans répétition de position.

Une suite binaire périodique répète indéfiniment un même bloc dès son premier terme ; si la répétition ne commence qu'à partir d'un certain rang, elle est seulement ultimement périodique. Prouhet-Thue-Morse n'est pas périodique : chacun des mots successifs construits par substitution est prolongé par son complément, et non par une copie identique. Par exemple, 0110 est suivi de 1001, pas de 0110.

Il ne faut pas non plus confondre la suite avec l'écriture binaire des entiers successifs. L'écriture binaire de n est la donnée examinée ; le terme t_n n'en retient qu'une information, la parité du nombre de chiffres 1. Pour n = 13, 1101 devient ainsi le seul symbole 1.

Le premier symbole doit être vérifié avant tout calcul. La substitution partant de 0 et la règle « nombre de 1 pair → 0 » produisent 0110100110010110. Le préfixe 1001011001101001 correspond à la convention complémentaire ; mélanger ces conventions remplace chaque réponse par son complément, sans décaler les indices.

L'expression « sans carré » ne convient pas à la suite binaire elle-même. Un carré est la répétition immédiate d'un bloc non vide ; or le préfixe 01101001 contient 1010, soit deux occurrences consécutives du bloc 10. Il faut donc tester le motif précis revendiqué plutôt que conclure à l'absence de toute répétition.

L'indice commence ici à 0. Si une source numérote les termes à partir de 1, le quatorzième symbole porte l'indice 14 au lieu de 13 dans son système ; avant d'appliquer le critère binaire, il faut convertir l'indice selon la convention annoncée.

L'article Combinatoire des mots et musiques traditionnelles prolonge l'étude des motifs, répétitions et structures portés par des suites de symboles.

Le glossaire écriture binaire éclaire le codage des indices dont dépend le calcul direct de t_n.