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 Modèle:Nobr, un carré xx est inévitable sur Modèle:Nobr, mais est évitable sur Modèle:Nobr : ce sont les mots sans carré. Le motif xyx est inévitable, même sur Modèle:Nobr.

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,\dots n-p$. Dans ce cas, $w$ est une puissance (rationnelle) de $x=a_1\cdots a_p$. LModèle:'exposant de cette puissance est le nombre $n/p$. Ainsi, l'Modèle:Nobr est la période minimale de $abaababa$, et $abaababa=(abaab{)}^{8/5}$. Une sesquipuissance est un mot dont l'exposant est strictement supérieur Modèle:Nobr. 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ù Modèle:Douteux 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

Modèle:Article connexe Un carré xx est inévitable sur Modèle:Nobr : tout mot de Modèle:Nobr 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 Modèle:Nobr : 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 Modèle:Nobr ne contenant pas de carré.

Répétition abélienne

Modèle:Article connexe 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 à Modèle:Nobr, puis à Modèle:Nobr et enfin à Modèle:Nobr par Veikko Keränen en 1992Modèle:, . Dekking a montré que les cubes abéliens sont évitables sur Modèle:Nobr au moyen du mot infini engendré par itération à partir de 0 par le morphisme Modèle:Retrait Il a aussi montré que les cubes abéliens sont inévitables sur Modèle:Nobr et que les puissances abéliennes d'Modèle:Nobr sont évitables sur Modèle:Nobr.

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'Modèle:Nobr 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'Modèle:Nobr 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'Modèle:Nobr, ou une k-puissance additive, si les $w_i$ ont même longueur Modèle:Retrait 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 à 1994Modèle:,.

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 : Modèle:Retrait 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