Suite de Prouhet-Thue-Morse

La suite a été redécouverte indépendamment plusieurs fois, pas toujours par des mathématiciens professionnels.

金 △ Koji Tanigawa

9 8 7 6 5 4 3 2 1 a b c d e f g h i

▲ Kunio Yonenaga 飛 , 金 , 銀 , 歩 x 4

Le 8 mars 1983, une partie de shogi disputée entre Kunio Yonenaga et Kōji Tanigawa a fait apparaître une suite analogue à la suite de Prouhet-Thue-Morse[2]. 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 nulle par triple répétition d'une séquence de coup[2]. 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 et une commençant par un général d'argent en g8[2]. 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é)[2]. 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[2]. 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[2]. 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[2].

Max Euwe, un champion d'é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.

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

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.

La suite de Prouhet-Thue-Morse est la suite ${\displaystyle t=(t_{n})}$ qui satisfait ${\displaystyle t_{0}=0}$ et

${\displaystyle {\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 ${\displaystyle t}$, que les termes d'indices pairs, on retrouve la suite ${\displaystyle t}$ ; si en revanche on ne garde que les termes d'indices impairs, on obtient la suite opposée, où les ${\displaystyle 0}$ et ${\displaystyle 1}$ ont été échangés.

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

Soient ${\displaystyle u_{n}}$ et ${\displaystyle v_{n}}$ les suites de mots définis par :

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

Alors

${\displaystyle t=\lim _{n\to \infty }u_{n}=0v_{0}v_{1}v_{2}\cdots v_{n}\cdots }$

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

Cette construction provient de la relation ${\displaystyle t_{2^{n}+k}=1-t_{k}}$ pour tous naturels n et k.

Automate de Prouhet-Thue-Morse.

${\displaystyle t_{n}}$ est égal à la somme, modulo 2, des chiffres dans le développement binaire de ${\displaystyle n}$. Par exemple, ${\displaystyle (18)_{2}=10010}$, et donc ${\displaystyle 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 ${\displaystyle (18)_{2}=10010}$, on obtient :

${\displaystyle a0{\xrightarrow {1}}b1{\xrightarrow {0}}b1{\xrightarrow {0}}b1{\xrightarrow {1}}a0{\xrightarrow {0}}a0}$

et la valeur est donc 0.

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

${\displaystyle {\begin{array}{lcl}0\mapsto 01\\1\mapsto 10\end{array}}}$

Les premières itérations à partir de ${\displaystyle 0}$ donnent :

${\displaystyle {\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.

La fonction génératrice de la suite ${\displaystyle ((-1)^{t_{n}})=(1-2t_{n})}$ est donnée par

${\displaystyle \sum _{n=0}^{\infty }(-1)^{t_{n}}X^{n}=\prod _{n=0}^{\infty }(1-X^{2^{n}})}$

Donc pour ${\displaystyle t}$ elle même :

${\displaystyle \sum _{n=0}^{\infty }t_{n}X^{n}={1 \over 2}\left({\frac {1}{1-X}}-\prod _{n=0}^{\infty }(1-X^{2^{n}})\right)}$

La complexité combinatoire de la suite de Prouhet-Thue-Morse est par définition la fonction ${\displaystyle c_{t}(n)}$ qui donne le nombre de facteurs (ou 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

${\displaystyle n}$	0	1	2	3	4	5	6	7	8	9	10
${\displaystyle 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 ${\displaystyle n\geq 1}$, soit ${\displaystyle k\geq 0}$ l'entier tel que ${\displaystyle 2^{k}+1\leq n\leq 2^{k+1}}$, et soit ${\displaystyle r}$ tel que ${\displaystyle n=2^{k}+r}$, avec ${\displaystyle 1\leq r\leq 2^{k}}$. Alors

${\displaystyle c_{t}(n)={\begin{cases}3\cdot 2^{k}+4(r-1)&{\text{si }}1\leq r\leq 2^{k-1},\\4\cdot 2^{k}+2(r-1)&{\text{si }}2^{k-1}+1\leq r\leq 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 ${\displaystyle c_{t}(n)\leq {\frac {10}{3}}n}$.

La suite de Prouhet-Thue-Morse n'est 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 fréquence asymptotique. Mais il en va autrement d'une suite associée à la suite de Prouhet-Thue-Morse ${\displaystyle t}$, qui est la suite extraite aux positions qui sont des carrés. C'est la suite ${\displaystyle u}$ donnée par :

${\displaystyle u_{n}=t_{n^{2}}}$

La suite commence par

${\displaystyle 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 [7] se demandent si la complexité de la suite ${\displaystyle u}$ est maximale, c'est-à-dire si le nombre ${\displaystyle c_{u}(n}$) de facteurs de longueur ${\displaystyle n}$ de la suite ${\displaystyle u}$ vérifie ${\displaystyle c_{u}(n)=2^{n}}$. Une réponse positive à cette question est donnée par Moshe en 2007[8]. Mauduit et Rivat montrent[9] que les 0 et les 1 apparaissent dans ${\displaystyle u}$ avec la même fréquence asymptotique ${\displaystyle 1/2}$. Ceci à son tour résout une conjecture longtemps ouverte de Gelfond[10]. Un résultat, annoncé par Drmota, Mauduit, et Rivat en 2013 et publié en 2019, dit[11] que la suite ${\displaystyle u}$ est normale. D'autres suites ont cette propriété, comme la suite de Rudin-Shapiro[12].