Répétition inévitable

En combinatoire des mots, une répétition est une suite de symboles qui se répète plusieurs fois consécutivement. Par exemple, le mot répétition lui-même contient la répétition titi, formé de deux occurrences consécutives du mot ti. L'étude des répétitions a des applications importantes en biologie, où on les retrouve sous le terme général de répétition en tandem, en compression des données à l’aide de dictionnaires, comme dans l'algorithme de Lempel-Ziv-Welch. Une répétition évitable est une répétition que l’on peut éviter dans certains cas, une répétition inévitable est une répétition qui apparaîtra nécessairement à un moment donné. Une généralisation de cette notion est celle de motif inévitable.

Par exemple, un cube xxx est évitable sur 2 lettres, un carré xx est inévitable sur 2 lettres, mais est évitable sur 3 lettres : ce sont les mots sans carré. Le motif xyx est inévitable, même sur 2 lettres.

Période, exposant, répétition et sesquipuissance

Un entier $p$ est une période du mot $w=a_{1}\cdots a_{n}$ si $a_{i}=a_{i+p}$ pour $i=1,\ldots n-p$. Dans ce cas, $w$ est une puissance (rationnelle) de $x=a_{1}\cdots a_{p}$. L'exposant de cette puissance est le nombre $n/p$. Ainsi, l'entier 5 est la période minimale de $abaababa$, et $abaababa=(abaab)^{8/5}$. Une sesquipuissance est un mot dont l'exposant est strictement supérieur à 1. Le mot $abaababa$ est aussi une puissance fractionnaire de $abaabab$, puisque $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 $x=a_{1}\cdots a_{p}$, on a $w=x^{e}y$, où $e=n/p$^{[Information douteuse]} est l'exposant et $y$ est le préfixe de $w$ de longueur $n-pe$. On peut aussi définir la période (minimale) d'un mot $w$ comme la longueur du plus court préfixe $x$ de $w$ telle que $w$ est préfixe du mot infini $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.

Répétition inévitable

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

Répétition abélienne

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. Une réponse positive a été apportée successivement pour des alphabets à 25 symboles, puis à 5 lettres et enfin à 4 lettres par Veikko Keränen en 1992 . 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 $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.

Un problème voisin est celui des puissances $k$-abéliennes. Deux mots $u$ et $v$ sont dits $k$-abéliennement équivalents s'ils possèdent les mêmes facteurs de longueur au plus $k$. Il est commode de noter cette propriété par $u\sim v$. Pour $k=1$, on retrouve l'équivalence commutative usuelle. Une puissance $k$-abélienne d'ordre $n$ est un mot $u_{1}u_{2}\cdots u_{n}$ composé de mots $k$-abéliennement équivalents, donc avec $u_{1}\sim _{k}u_{2}\sim _{k}\cdots \sim _{k}u_{n}$. On peut démontrer 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 $k$-abélienne d'ordre $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 $3^{1/19}=1,059526\dots$

Répétition additive

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 $w_{1}w_{2}\cdots w_{k}$ est une puissance additive d'ordre k, ou une k-puissance additive, si les $w_{i}$ ont même longueur $|w_{1}|=|w_{2}|=\cdots =|w_{k}|$ et si $\sum w_{1}=\sum w_{2}=\cdots =\sum w_{k}\,$, où $\sum w$ est la somme des symboles de $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.

Les cubes additifs sont évitables

Un important résultat sur les cubes additifs est que les cubes additifs sont évitables sur l'alphabet A={0,1,3,4}. Pour établir ce résultat, il faut exhiber un mot infini sur cet alphabet et montrer qu'il est sans cube additif. Le mot construit par les auteurs de l’article est obtenu en itérant à partir de 0 le morphisme uniforme donné par : $0\mapsto 03\ ,\quad 1\mapsto 43\ ,\quad 3\mapsto 1\ ,\quad 4\mapsto 01\,$. Le mot obtenu est purement morphique, il commence par $03143011034343031\dots$

Articles liés

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