Répétition inévitable

Un entier ${\displaystyle p}$ est une période du mot ${\displaystyle w=a_{1}\cdots a_{n}}$ si ${\displaystyle a_{i}=a_{i+p}}$ pour ${\displaystyle i=1,\ldots n-p}$. Dans ce cas, ${\displaystyle w}$ est une puissance (rationnelle) de ${\displaystyle x=a_{1}\cdots a_{p}}$. L'exposant de cette puissance est le nombre ${\displaystyle n/p}$. Ainsi, l'entier 5 est la période minimale de ${\displaystyle abaababa}$, et ${\displaystyle abaababa=(abaab)^{8/5}}$. Une sesquipuissance est un mot dont l'exposant est strictement supérieur à 1. Le mot ${\displaystyle abaababa}$ est aussi une puissance fractionnaire de ${\displaystyle abaabab}$, puisque ${\displaystyle abaababa=(abaabab)^{8/7}}$. Quand on cherche des puissances (fractionnaires) dans un mot, on considère souvent la plus petite période, et donc l'exposant le plus élevé. En posant ${\displaystyle x=a_{1}\cdots a_{p}}$, on a ${\displaystyle w=x^{e}y}$, où ${\displaystyle e=n/p}$ est l'exposant et ${\displaystyle y}$ est le préfixe de ${\displaystyle w}$ de longueur ${\displaystyle n-pe}$. On peut aussi définir la période (minimale) d'un mot ${\displaystyle w}$ comme la longueur du plus court préfixe ${\displaystyle x}$ de ${\displaystyle w}$ telle que ${\displaystyle w}$ est préfixe du mot infini ${\displaystyle x^{\omega }}$.

Le terme de répétition est quelquefois réservé aux mots d'exposant valant au moins deux. L'existence d'un seuil pour les répétitions fractionnaires a été conjecturé par Françoise Dejean en 1972 ; la démonstration de ce fait est le théorème de Dejean.

Un carré xx est inévitable sur 2 lettres : tout mot de longueur 4 sur deux lettres, disons a et b, contient un carré. Ceci est clair si le mot contient deux occurrences consécutives de la même lettres. Les autres mots sont abab et baba, qui sont des carrés.

Un carré xx est inévitable sur 3 lettres : c'est une construction du mathématicien norvégien Axel Thue qui a, en premier, donné un exemple d'un mot sans carré, mot infini sur 3 lettres ne contenant pas de carré.

Une répétition abélienne ou puissance abélienne est une suite de mots consécutifs de même longueur qui sont égaux entre eux à une permutation près. En d'autres termes, les blocs consécutifs composant une puissance abélienne sont des anagrammes les uns des autres. Un carré abélien est une répétition abélienne composée de deux blocs, donc un mot xy, où y est une permutation de x.

Paul Erdős a posé la question de l'existence d'un mot infini sans carré abélien en 1961[1]. Une réponse positive a été apportée successivement pour des alphabets à 25 symboles[2], puis à 5 lettres[3] et enfin à 4 lettres par Veikko Keränen en 1992[4] - [5]. Dekking a montré que les cubes abéliens sont évitables sur 3 lettres au moyen du mot infini engendré par itération à partir de 0 par le morphisme ${\displaystyle 0\mapsto 0012\ ,\quad 1\mapsto 112\ ,\quad 2\mapsto 022\;}$. Il a aussi montré que les cubes abéliens sont inévitables sur 2 lettres et que les puissances abéliennes d'ordre 4 sont évitables sur 2 lettres[6].

Un problème voisin est celui des puissances ${\displaystyle k}$-abéliennes. Deux mots ${\displaystyle u}$ et ${\displaystyle v}$ sont dits ${\displaystyle k}$-abéliennement équivalents s'ils possèdent les mêmes facteurs de longueur au plus ${\displaystyle k}$. Il est commode de noter cette propriété par ${\displaystyle u\sim v}$. Pour ${\displaystyle k=1}$, on retrouve l'équivalence commutative usuelle. Une puissance ${\displaystyle k}$-abélienne d'ordre ${\displaystyle n}$ est un mot ${\displaystyle u_{1}u_{2}\cdots u_{n}}$ composé de mots ${\displaystyle k}$-abéliennement équivalents, donc avec ${\displaystyle u_{1}\sim _{k}u_{2}\sim _{k}\cdots \sim _{k}u_{n}}$. On peut démontrer[7] l'existence d'un mot binaire infini sans cubes 2-abéliens et d'un mot ternaire infini sans carrés 3-abéliens. Pour ce faire, Michaël Rao donne des conditions suffisantes pour qu'un morphisme préserve les mots sans puissance ${\displaystyle k}$-abélienne d'ordre ${\displaystyle n}$ et il construit des morphismes qui satisfont ces conditions. De plus, ces constructions montrent que le nombre de tels mots croît exponentiellement. En particulier, le nombre de mots sans cube abélien croît au moins comme ${\displaystyle 3^{1/19}=1,059526\dots }$

Lorsque l'alphabet est composé lui-même de nombres, on peut replacer la condition sur les symboles par une condition sur la somme des symboles constituant les facteurs. Ainsi, un carré additif est un mot xy, où x et y ont même longueur et où la somme des symboles de x est égale à la somme des symboles de y. Par exemple, sur l’alphabet {1,2,3,4}, le mot 1423 est un carré additif parce que 1+4=2+3.

Plus généralement, un mot est une puissance additive s'il est composé de blocs consécutifs de même longueur et de même somme. Ainsi, un mot ${\displaystyle w_{1}w_{2}\cdots w_{k}}$ est une puissance additive d'ordre k, ou une k-puissance additive, si les ${\displaystyle w_{i}}$ ont même longueur ${\displaystyle |w_{1}|=|w_{2}|=\cdots =|w_{k}|}$ et si ${\displaystyle \sum w_{1}=\sum w_{2}=\cdots =\sum w_{k}\,}$, où ${\displaystyle \sum w}$ est la somme des symboles de ${\displaystyle w}$.

Une k-puissance additive est évitable sur un alphabet donné s'il existe un mot infini sur cet alphabet qui ne contient pas de k-puissance additive. La première mention du problème d'existence de mots sans k-puissance additive remonte à 1994[8] - [9].

• Mot sans carré
• Motif inévitable
• Théorème de Dejean
• Sesquipuissance