Exposant critique d'un mot

Soit ${\displaystyle x}$ un mot fini sur ${\displaystyle A}$ et soit ${\displaystyle \alpha \geq 1}$ un nombre réel. On dit qu'un mot ${\displaystyle z}$ est une puissance d'ordre ${\displaystyle \alpha }$ de ${\displaystyle x}$ si ${\displaystyle z=x^{n}y}$, où ${\displaystyle n}$ est la partie entière de ${\displaystyle \alpha }$, ${\displaystyle y}$ est un préfixe de ${\displaystyle x}$, et ${\displaystyle |z|\geq \alpha |x|}$.

Voici quelques exemples.

• Le mot ${\displaystyle aabbaa}$ est une puissance d'ordre 3/2 de ${\displaystyle aabb}$.
• Le mot ${\displaystyle abaababa}$ est une puissance d'ordre 8/5 de ${\displaystyle abaab}$.
• Un carré est une puissance d'ordre 2.
• La définition implique que si une mot est une puissance d'ordre ${\displaystyle \alpha }$, c'est aussi une puissance d'ordre ${\displaystyle \beta }$ pour tout réel ${\displaystyle \beta <\alpha }$ pourvu qu'ils aient même partie entière.

Soit maintenant ${\displaystyle w}$ un mot infini sur l'alphabet ${\displaystyle A}$. On dit que ce mot possède une puissance d'ordre ${\displaystyle \alpha }$ s'il contient un facteur qui est une puissance d'ordre ${\displaystyle \alpha }$. Il est dit sans puissance d'ordre ${\displaystyle \alpha }$ si, au contraire, il ne contient pas de facteur qui est une puissance d'ordre ${\displaystyle \alpha }$. Par exemple, un mot sans carré est un mot qui ne contient aucun facteur carré.

L'exposant critique ${\displaystyle E(w)}$ de ${\displaystyle w}$ est la borne supérieure des ${\displaystyle \alpha }$ pour lesquelles ${\displaystyle w}$ possède des puissances d'ordre ${\displaystyle \alpha }$ ou, de manière équivalente, la borne inférieure des ${\displaystyle \alpha }$ pour lesquelles ${\displaystyle w}$ est sans puissance d'ordre ${\displaystyle \alpha }$[1]. Formellement :

${\displaystyle E(w)=\sup\{\alpha \in \mathbb {Q} \mid x^{\alpha }{\text{ est un facteur non vide de }}w\}.}$

Propriétés remarquables de l'exposant critique :

• L'exposant critique peut prendre toute valeur réelle plus grande que ${\displaystyle 1}$[5].
• L'exposant critique d'un mot morphique sur un alphabet fini est un nombre algébrique dont le degré est au plus égal à la taille de l'alphabet[6].
• L'exposant critique d'un mot sturmien est fini si et seulement si les coefficients du développement en fraction continue de sa pente sont bornés[7].

Le plus petit exposant critique d'une famille de mots est appelé exposant critique minimal. Quand on considère tous les mots sur un alphabet d'une certaine taille, on parle aussi de seuil de répétition, formellemment :

${\displaystyle RT(d)=\inf\{E(w)\mid u}$ est un mot infini sur ${\displaystyle d}$ symboles.

Pour certaines familles de mots, on connaît des résultats assez précis. Un mot infini est dit équilibré si pour deux facteurs ${\displaystyle u}$ et ${\displaystyle v}$ de même longueur, le nombre d'occurrences de chaque lettre dans ${\displaystyle u}$ et ${\displaystyle v}$ diffère d'au plus 1. Sur un alphabet binaire, les mots équilibrés apériodiques coïncident avec les mots de Sturm.

Le seuil de répétition équilibré est le seuil de répétition pour les mots équilibrés, formellement :

${\displaystyle RTB(d)=\inf\{E(w)\mid u}$ est un mot infini équilibré sur ${\displaystyle d}$ symboles.

Les seuils connus sont :

• ${\displaystyle RTB(2)=2+(1+{\sqrt {5}})/{2}}$
• ${\displaystyle RTB(3)=2+1/{\sqrt {2}}}$
• ${\displaystyle RTB(4)=1+(1+{\sqrt {5}})/4}$
• ${\displaystyle RTB(d)=d-2/d-3}$ pour ${\displaystyle 5\leq d\leq 10}$.
• ${\displaystyle RTB(d)\geq d-2/d-3}$ pour ${\displaystyle d\geq 11}$.

De façon plus détaillé, Rampersad, Shallit et Vandomme[8] ont décrit des mots équilibrés avec exposant critique minimal sur des alphabets de taille 3, et ils ont conjecturé que l'exposant critique minimal des mots équilibrés sur un alphabet à ${\displaystyle d\geq 5}$ symboles est égal à ${\displaystyle d-2/d-3}$. Pour ${\displaystyle d\leq 10}$, ils ont donné des mots obtenus à partir de mots sturmiens à pente quadratique, qui atteignent ce minimum.

La construction repose sur une opération d'entrelacement de suites équilibrées que les autres attribuent à Pascal Hubert[9]. La construction part d'une suite binaire, par exemple sur les symboles 0 et 1. Les occurrences des 0 sont remplacées, les unes après les autres, par les symboles d'un mot infini ${\displaystyle x_{0}}$; les occurrences des 1 sont, de même, remplacées par les symboles successifs d'un mot infini ${\displaystyle x_{1}}$. Cette opération est appelée « à la Hubert ».

Par exemple, si l'on part du mot de Fibonacci 0100101001001..., et on remplace les 0 consécutifs par les symboles de ${\displaystyle (ab)^{\omega }}$ et les 1 par les symboles de ${\displaystyle (xxy)^{\omega }}$, on obtient :

010010100100101001010
a.ba.b.ab.ab.a.ba.b.a
.x..x.y..x..x.y..x.x.

soit :

axbaxbyabxabxaybaxbxa

Le résultat de Hubert utilisé est que la composition de mots équilibrés est encore équilibrée. La conjecture de Rampersad, Shallit et Vandomme a été confirmée pour ${\displaystyle d=9}$ et ${\displaystyle d=10}$[10]. Dvořáková, Opočenská, Pelantová et Shur donnent[11], pour tout ${\displaystyle d\geq 12}$, un mot équilibré d'exposant critique ${\displaystyle d-1/d-2}$. Comme ${\displaystyle d-1/d-2<d-2/d-3}$, ce résultat réfute la conjecture de Rampersad, Shallit et Vandomme. Les auteurs remplacent la valeur ${\displaystyle d-2/d-3}$ par la nouvelle conjecture ${\displaystyle d-1/d-2}$.

• Exposant critique d'un système physique
• Mot sturmien
• Mot automatique
• Mot morphique
• Mot quasi-périodique
• Théorème de Dejean