Voir la source de Suite de Prouhet-Thue-Morse

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 (mathématiques)|suite]] [[système binaire|binaire]] {{incise|c'est-à-dire dont les termes valent 0 ou 1|point}}. Elle commence par :

:<math>t=0\; 1\; 10\; 1001\; 10010110\; 1001011001101001 \ldots</math>

C'est une [[suite automatique]] (elle est calculable par un [[automate fini]]), ''uniformément récurrente'' et [[mot sans facteur carré|sans cube]] (aucun mot n'y est répété trois fois consécutivement).

Elle est répertoriée comme la {{OEIS|id=A010060}}.

== Histoire ==
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]]<ref>M. E. Prouhet, [https://gallica.bnf.fr/ark:/12148/bpt6k29901/f227.image.langFR Mémoire sur quelques relations entre les puissances des nombres], C. R. Acad. Sci. Paris, série I, '''33''', (1851), 225</ref>.

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

=== Redécouverte dans le domaine des jeux ===
La suite a été redécouverte indépendamment plusieurs fois, pas toujours par des [[mathématicien]]s professionnels.

==== Au shogi ====
{{article détaillé|Sennichite}}
{{Diagramme de Shogi|right
| 金 <br/>
<small>△</small> Koji Tanigawa 
 | lg |    |    |    |    |    |    | ng | lg   
 |    |    |    |    |    |    | gg | kg |    
 |    | hs |    |    |    |    | gg | pg | pg  
 | pg |    |    | ns | pg | pg | pg |    |    
 | bg | ng |    | ps |    |    |    | ps | ps  
 |    | ps | ps | ss | ps |    | ps |    |  
 | ps |    |    |    |    |    |    |    |   
 | ks |    | sg |    |    |    |    |    | ls 
 | ls | ns |    |    |    |    |    | rs |    
|<small>▲</small> Kunio Yonenaga <br/> 飛 , 金 , 銀 , 歩 x 4 
}}
Le {{date-|8 mars 1983}}, une partie de [[shogi]] disputée entre [[Kunio Yonenaga]] et [[Koji Tanigawa|Kōji Tanigawa]] a fait apparaître une suite analogue à la suite de Prouhet-Thue-Morse<ref name="hidetchi">{{YouTube|7SZpI_a4aC0|How to play Shogi(将棋) -Lesson#15- Repetition("Sen-nichi-te")|en}}, à partir de 3 min 26s.</ref>. La position ci-contre apparaît au coup 118 ; Tanigawa est dans une position désavantageuse car il a moins de matériel en main que Yonenaga et tente alors d'obtenir une [[Sennichite|nulle par triple répétition d'une séquence de coup]]<ref name="hidetchi"/>. Cependant dans cette position Yonenaga a plusieurs manières équivalentes de commencer une séquence amenant à la reproduction du diagramme : deux qui commencent par le parachutage d'un général d'or en '''h8''' (par exemple *Gh8 Gg8 Gxg8 Sxg8 Rxg8 *Sh7 Kh9) et une commençant par un général d'argent en '''g8''' (*Sg8 Sxg8 Rxg8 *Sh7 Kh9)<ref name="hidetchi"/>. En alternant deux de ces séquences selon une suite de Prouhet-Thue-Morse il est alors possible de forcer une séquence de coups arbitrairement longue sans que la partie soit nulle puisque la suite de Prouhet-Thue-Morse est sans cube (Yonenaga a choisi une autre séquence de coups ayant la même propriété)<ref name="hidetchi"/>. Yonenaga a alors pu prendre le temps de réfléchir à une manière de rompre la répétition à son avantage pour remporter la partie<ref name="hidetchi"/>. Comprenant cela Tanigawa a rompu lui-même la séquence 60 coups plus tard pour tenter de prendre l'avantage avant que son adversaire n'arrive à trouver le moyen de forcer la victoire, mais il finit par perdre la partie<ref name="hidetchi"/>. La règle du [[sennichite]] a été modifiée deux mois plus tard à la suite de cette partie : une partie est déclarée nulle après quatre répétitions d'une même position et ce quelles que soient les séquences aboutissant à ces répétitions de position<ref name="hidetchi"/>.

==== Aux échecs ====
[[Max Euwe]], un champion d'[[jeu d'échecs|échecs]] et professeur de mathématiques, a découvert en 1929 une application analogue de cette suite aux échecs, prouvant, par ce biais, qu'il existe des parties infinies ne comportant pas de répétition immédiate d'une même séquence de coups par trois fois. En 1944, Marston Morse et [[Gustav Hedlund]] ont développé cet aspect.

=== Dans le sport ===
==== Tirs au but au football ====

Les études des séances de [[tirs au but]] au [[football]] ont démontré un avantage statistique pour l’équipe qui effectue le premier tir. Pour corriger ce déséquilibre dû selon les chercheurs à la pression plus forte sur les tireurs de la deuxième équipe, l’économiste espagnol Ignacio Palacios-Huerta a proposé d’alterner les tirs selon la suite de Prouhet-Thue-Morse. {{pas clair|C’est-à-dire, A et B les deux équipes et A étant celle qui tire la première}}, après le premier tir de l’équipe A, on effectuerait deux tirs de l’équipe B, puis un de A et un de B, puis deux de A, puis un de B, les huit premiers tirs faisant un cycle complet qui recommence de la même manière au neuvième tir. Selon Palacios-Huerta, cette méthode réduirait le déséquilibre statistique actuellement constaté de 60,6%-39,4 % à 51%-49 % en faveur de l’équipe A<ref>[http://www.swissinvestlab.com/lab-hebdo/021_rj6g4.html ''Faites votre choix : Goldman Sachs ou Franck Ribéry ?''], numéro 21 (9 juin 2016) de Lab Hebdo écrit par Sylvain Frochaux.</ref>.

La réalité statistique de cet avantage à tirer en premier est controversée. Voir les références données dans l'article sur les [[tirs au but]].

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

=== Définition par récurrence ===
La suite de Prouhet-Thue-Morse est la suite <math>t=(t_n)</math> qui satisfait <math>t_0 = 0</math> et

:<math>\begin{array}{lcl}t_{2n}&{\!\!\!=\!\!\!}&t_n\\t_{2n+1}&{\!\!\!=\!\!\!}&1-t_n\end{array}</math>

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

=== Autre récurrence ===
[[Image:Morse-Thue sequence.gif|vignette|droite|Construction de la suite de Prouhet-Thue-Morse : chaque bloc est obtenu par [[concaténation]] du bloc précédent avec son opposé.]]Soient <math>u_n</math> et <math>v_n</math> les suites de mots définis par :

:<math>\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}
</math>

Alors
:<math>t=\lim_{n\to\infty}u_n=0v_0v_1v_2\cdots v_n\cdots</math>

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

Cette construction provient de la relation <math>t_{2^n+k}=1-t_k</math> pour tous naturels {{Mvar|n}} et {{Mvar|k}}.

=== Définition directe ===
[[Fichier:Automate-Thue-Morse.png|vignette|Automate de Prouhet-Thue-Morse.]]
<math>t_n</math> est égal à la somme, modulo 2, des chiffres dans le développement binaire de <math>n</math>. Par exemple, <math>(18)_2=10010</math>, et donc <math>t_{18}=0</math>. Ce calcul est réalisé par l'[[automate fini|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ée, selon qu'il est jaune ou rose, indique que la valeur de la suite est 0 ou 1. Pour <math>(18)_2=10010</math>, on obtient :
:<math>a0\xrightarrow1b1\xrightarrow0b1\xrightarrow0b1\xrightarrow1a0\xrightarrow0a0</math>
et la valeur est donc 0.

=== Définition par morphisme ===
La suite <math>t</math> est obtenue aussi en itérant le morphisme <math>\mu</math> appelé parfois le ''morphisme de Thue-Morse'' suivant :
:<math>\begin{array}{lcl}0\mapsto01\\1\mapsto10\end{array}</math>
Les premières itérations à partir de <math>0</math> donnent :
:<math>\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}</math>
Si l'on itère à partir de 1, on obtient la suite opposée.

=== Définition par fonction génératrice ===
La [[fonction génératrice]] de la suite <math>((-1)^{t_n})=(1-2t_n)</math> est donnée par 
:<math> \sum_{n=0}^\infty(-1)^{t_n} X^n=\prod_{n=0}^\infty(1 - X^{2^n}) </math>
Donc pour <math>t</math> elle même :

<math> \sum_{n=0}^\infty t_nX^n={1\over2}\left(\frac1{1-X}-\prod_{n=0}^\infty(1 - X^{2^n})
\right) </math>

== Propriétés ==

* La suite de Prouhet-Thue-Morse est ''uniformément récurrente'' : pour tout entier <math>n</math>, il existe un entier <math>N</math> tel que tout facteur de <math>t</math> de longueur <math>N</math> contient tous les facteurs de <math>t</math> de longueur <math>n</math>.
* 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 <math>axaxa</math>, où <math>a</math> est un des symboles <math>0</math> ou <math>1</math> et <math>x</math> est un bloc<ref>{{Ouvrage|auteur1=Jean-Paul Delahaye|titre=Le désordre total existe-t-il ?|éditeur=Pour la Science|année=1993|passage=35|lire en ligne=https://www.cristal.univ-lille.fr/~jdelahay/pls/1993/016.pdf}}</ref>.
* La [[constante de Prouhet-Thue-Morse]] est le nombre <math>\tau\,</math> dont le développement binaire est la suite de Prouhet-Thue-Morse, c’est-à-dire le nombre<span style="display: block; padding: 0.3em;margin-left: 1.3em"><math>  \tau = \sum_{i=0}^{\infty} \frac{t_i}{2^{i+1}} = 0{,}412\,454\,033\,640 \ldots </math></span>C'est un [[nombre transcendant]].

== Produits infinis associés à la suite ==
J.P Allouche a démontré que le [[produit infini]] : <math>\prod_{n\geqslant0}\left (  \frac{2n+1}{2n+2}\right )^{(-1)^{t_n}}</math> est semi-convergent et a pour valeur <math>1/\sqrt2</math> <ref>{{Article|langue=en|auteur1=Jean-Paul Allouche|titre=Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence|périodique=Journal de théorie des nombres de Bordeaux, Tome 27, no 2|date=2015|pages=381}}</ref>{{,}}<ref>{{Article|auteur1=Jean Moussa|titre=Quelques propriétés associées à la suite de Prouhet-Thue-Morse|périodique=Bulletin de l'APMEP|date=mars-Avril 2016|lire en ligne=https://www.apmep.fr/IMG/pdf/AAA16022.pdf|pages=199-206}}</ref>.

Nota : Ce produit infini a une définition naturelle, car si l'on considère la suite de fractions <math>u_1=\frac{1}{2},u_2=\frac{\frac{1}{2}}{\frac{3}{4}},
u_3=\frac{\frac{1}{2}}{\frac{3}{4}}/\frac{\frac{5}{6}}{\frac{7}{8}}</math>, alors <math>u_n=</math><math>\prod_{k=0}^{2^{n-1}-1}\left (  \frac{2k+1}{2k+2}\right )^{(-1)^{t_k}}</math>, et par conséquent, <math>\lim u_n={1\over\sqrt2}</math>.

{{Démonstration/début}}

La fraction <math>u_n</math> s'obtient en multipliant la fraction précédente par l'image de cette fraction obtenue en échangeant numérateurs et dénominateurs, avec les mêmes entiers augmentés de <math>2^{n-1}</math>, règle reproduisant exactement la règle de construction de la suite de Prouhet-Thue-Morse.

Donc <math>u_n=\prod_{k=0}^{2^n-1}(k+1)^{(-1)^{t_k}}</math> ; en regroupant les termes deux à deux, on obtient <math>u_n=\prod_{k=0}^{2^{n-1}-1}(2k+1)^{(-1)^{t_{2k}}}(2k+2)^{(-1)^{t_{2k+1}}}
=\prod_{k=0}^{2^{n-1}-1}\left (  \frac{2k+1}{2k+2}\right )^{(-1)^{t_k}}</math>.

{{Démonstration/fin}}

En utilisant le [[Produit de Wallis|produit infini de Wallis]], on en déduit :

: <math>\prod_{n\geqslant0}
{\left( \frac{2n+1}{2n+2} \right)}^{2t_n}\left( \frac{2n+3}{2n+2}
\right)=\frac{2 \sqrt{2}}{\pi}</math> <ref name=":0">{{harvsp|Allouche|Shallit|2003|loc=page 204}}</ref>,

: <math>\prod_{n\geqslant0} 
{\left( \frac{2n+1}{2n+2} \right)}^{2(1-t_n)}\left( \frac{2n+3}{2n+2}
\right)=\frac{ \sqrt{2}}{\pi}</math> <ref name=":0" />.

Le produit infini <math>\prod_{n\geqslant1}\left (  \frac{2n}{2n+1}\right )^{(-1)^{t_n}}</math> est également convergent, mais on ne connait pas sa valeur, ni son statut algébrique ; voir la {{OEIS|A086744}}.

== Suite de Prouhet-Thue-Morse et nombres normaux ==
=== Complexité combinatoire ===
La [[complexité d'un mot|complexité combinatoire]] de la suite de Prouhet-Thue-Morse est par définition la fonction <math>c_t(n)</math> qui donne le nombre de facteurs (ou blocs) distincts de longueur ''n'' de la suite. Les premières valeurs de cette fonction sont
{| class="wikitable centre" width="50%" align="center"
|+ Fonction de complexité de la suite de Prouhet-Thue-Morse
! <math>n</math>
! 0 !! 1 !! 2!! 3!! 4!! 5!! 6!! 7!! 8!! 9!! 10
|----- 1 2 4 6 10 12 16 20 22 24 28 32 36 40 42 44 46 48 52 56
|align="center"| <math>c_t(n)</math>||align="center"| 1
|align="center"| 2||align="center"| 4
|align="center"| 6||align="center"| 10
|align="center"| 12||align="center"| 16
|align="center"| 20||align="center"| 22
|align="center"| 24||align="center"| 28
|}
C'est la {{OEIS|id=A005942}}. La formule qui donne les valeurs est la suivante : Pour <math>n\geqslant 1</math>, soit <math>k\geqslant0</math> l'entier tel que <math>2^k+1\leqslant n\leqslant 2^{k+1}</math>, et soit <math>r</math> tel que <math>n=2^k+r</math>, avec <math>1\leqslant r \leqslant 2^k</math>. Alors
:<math>c_t(n)=\begin{cases}
  3\cdot 2^k+4(r-1)&\text{si } 1\leqslant r\leqslant 2^{k-1},\\
  4\cdot 2^k+2(r-1)&\text{si } 2^{k-1}+1\leqslant r\leqslant 2^k.
\end{cases}</math>
Comme toutes les fonctions de complexités des [[suite automatique|suites automatiques]], cette fonction croît au plus linéairement. De fait, on peut prouver que <math>c_t(n)\leqslant \frac{10}3n</math>.

=== Suite aux positions carrées ===
La suite de Prouhet-Thue-Morse n'est pas une [[nombre normal|suite normale]], puisque dans une suite normale tous les facteurs apparaissent, et deux facteurs de même longueur apparaissent avec la même fréquence asymptotique. Mais il en va autrement d'une suite associée à la suite de Prouhet-Thue-Morse <math>t</math>, qui est la suite extraite aux positions qui sont des carrés. C'est la suite <math>u</math> donnée par :
: <math>u_n=t_{n^2}</math>
La suite commence par
:<math>0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1,</math>
C'est la {{OEIS|id=A010060}}. Cette suite a fait l'objet de plusieurs études : Allouche et Shallit <ref>{{harvsp|Allouche|Shallit|2003|loc=Problem 10.12.7}}.</ref> se demandent si la complexité de la suite <math>u</math> est maximale, c'est-à-dire si le nombre <math>c_u(n</math>) de facteurs de longueur <math>n</math> de la suite <math>u</math> vérifie <math>c_u(n)=2^n</math>. Une réponse positive à cette question est donnée par Moshe en 2007<ref>
{{article|auteur=Y. Moshe|titre=On the subword complexity of Thue-Morse polynomial extractions|journal=Theoret. Comput. Sci.|volume=38|année=2007|pages=318–329}}.</ref>. Mauduit et Rivat montrent<ref>
{{article|auteur1=C. Mauduit|auteur2=J. Rivat|titre=La somme des chiffres des carrés|journal=Acta Math. |volume=203|année=2009|pages=107-148}}.</ref> que les 0 et les 1 apparaissent dans <math>u</math> avec la même fréquence asymptotique <math>1/2</math>. Ceci à son tour résout une [[conjecture]] longtemps ouverte de Gelfond<ref>
{{article|auteur1=A. O. Gelfond|titre=Sur les nombres qui ont des propriétés additives et multiplicatives données |journal=Acta Arith. |volume=13|année=1967/1968|pages=259-265}}.</ref>. Un résultat, annoncé par [[Michael Drmota|Drmota]], [[Christian Mauduit (mathématicien)|Mauduit]], et Rivat en 2013 et publié en 2019, dit<ref name="DrmotaMauduit2018">{{article
 |nom1=Drmota|prénom1=Michael
 |nom2=Mauduit|prénom2=Christian
 |nom3=Rivat|prénom3=Joël
 |titre=Normality along squares
 |journal=[[Journal of the European Mathematical Society]]
 |volume=21|numéro=2|année=2019
 |pages=507–548|doi=10.4171/JEMS/843
 |url = http://dmg.tuwien.ac.at/drmota/alongsquares.pdf}}.</ref> que la suite <math>u</math> est normale. D'autres suites ont cette propriété, comme la [[suite de Rudin-Shapiro]]<ref name="Müllner2018">{{article
 |nom1=Müllner|prénom1=Clemens
 |titre=The Rudin–Shapiro Sequence and Similar Sequences Are Normal Along Squares
 |journal=Canadian Journal of Mathematics
 |volume=70|numéro=5|année=2018|pages=1096–1129
 |doi=10.4153/CJM-2017-053-1}}.</ref>.

== Suite bilatère ==
La suite de Prouhet-Thue-Morse peut être étendue en une suite indexée par <math>\Z</math> en posant
:<math>t_{-i}=t_{i-1} \quad (i \geqslant 1)</math>
On obtient donc (un point central est placé avant <math>t_0</math>) la suite :
:<math>\dotso 0110100110010110.01101001100101101001011001101001\dotso</math>
Cette suite est encore une suite sans chevauchement. De plus, le [[dynamique symbolique|système dynamique]] engendré par cette suite est exactement l'ensemble des suites bilatères sans chevauchement.

== Notes et références ==
=== Notes ===
{{Notes}}
=== Références ===
{{Références}}

== Bibliographie ==
* {{Article|auteur1=[[Jean-Paul Delahaye]]|titre=Des mots magiques infinis|périodique=[[Pour la Science]]|numéro=347|mois=septembre|année=2006|date=2006|lire en ligne=https://www.cristal.univ-lille.fr/~jdelahay/pls/2006/147.pdf|pages=90-95}}
*{{Ouvrage|auteur1=[[Jean-Paul Delahaye]]|titre=Mathématiques pour le plaisir|passage=160-167|éditeur=Belin - Pour La Science|date=janvier 2010|lire en ligne=https://books.google.fr/books?id=ejiWDgAAQBAJ&pg=PA160&lpg=PA160&dq=%22des+mots+magiques+infinis%22&source=bl&ots=cmNNB-qjiM&sig=ACfU3U04MALhTktRC-_yg3qeHZd13WWzRw&hl=fr&sa=X&ved=2ahUKEwiAmf7M-aT1AhUIKBoKHXUKAPUQ6AF6BAg8EAM#v=onepage&q=%22des%20mots%20magiques%20infinis%22&f=false|titre chapitre=Des mots magiques infinis (même article que le précédent)}}
*{{Article|auteur1=[[Jean-Paul Delahaye]]|titre=Des suites fractales d'entiers|périodique=[[Pour la Science]]|numéro=531|mois=|année=|pages=82-83|date=janvier 2022|lire en ligne=https://nextcloud.univ-lille.fr/index.php/s/wXZapZc4JY6ibsn}}
*{{Article|auteur1=Fabien Aoustin|titre=La très riche suite de Prouhet-Thue-Morse|périodique=Bibliothèque Tangente|date=décembre 2021|lire en ligne=https://tangente-mag.com/article.php?id=6015|accès url=payant|pages=90-94}}
* {{Ouvrage|langue=en|auteur1=[[Jean-Paul Allouche]]|auteur2=[[Jeffrey Shallit]]|titre=Automatic sequences|sous-titre=Theory, applications, generalizations|lieu=Cambridge|éditeur=[[Cambridge University Press]]|année=2003|pages totales=571|isbn=0-521-82332-3|math reviews=1997038}}
* {{article
 |nom1=Narayanan|prénom1=Shyam
 |titre=Functions on antipower prefix lengths of the Thue–Morse word
 |journal=[[Discrete Mathematics]]
 |volume=343|numéro=2|année=2020|numéro article = 111675
 |doi=10.1016/j.disc.2019.111675}}

== Articles connexes ==
* [[Complexité abélienne d'un mot]]
* [[Suite automatique]]
* [[Mot de faible complexité]]
* [[Combinatoire des mots]]
* [[Mot sans carré]]
* [[Théorème de Dejean]]

== Liens externes ==

* {{en}} Jean-Paul Allouche et Jeffrey O. Shallit, [http://www.cs.uwaterloo.ca/~shallit/Papers/ubiq.ps The Ubiquitous Prouhet-Thue-Morse Sequence.] Contient de nombreuses propriétés et références.
* {{MathWorld|nom_url=Thue-MorseSequence|titre=Thue-Morse Sequence}}. Des applications supplémentaires.

{{Portail|mathématiques|informatique théorique|jeux}}

[[Catégorie:Suite d'entiers|Prouhet-Thue-Morse]]
[[Catégorie:Combinatoire des mots|Prouhet-Thue-Morse]]