Exposant critique d'un mot

En mathématiques et en informatique théorique, et notamment en combinatoire des mots, l'exposant critique d'un mot (en anglais critical exponent) est une propriété d'un mot infini. C'est l'exposant de la plus grande puissance fractionnaire d'un mot qui peut apparaître dans ce mot infini. C'est une mesure de régularité des suites infinies de symboles.

Définition modifier

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

Voici quelques exemples.

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

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

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

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

Exemples modifier

L'exposant critique de la suite de Prouhet-Thue-Morse est 2. Ceci provient de ce que ce mot contient des carrés, mais aucun facteur d'exposant strictement plus grand que 2 puisqu'il ne contient pas de facteur chevauchant, c'est-à-dire de la forme $xxb$ où $b$ est la première lettre de $x$ .
L'exposant critique du mot infini de Fibonacci est $(5+{\sqrt {5}})/2$ ^[2]^,^[3].
Le mot infini de Fibonacci contient des cubes, et est sans puissance 4^e. Il contient, pour $n\geq 4$ , en facteur les mots de la forme $f_{n}f_{n}f_{n}g_{n-1}$ , où $f_{n}$ est un mot de Fibonacci fini, et où $g_{n-1}$ est le mot $f_{n-1}$ privé de ses deux dernières lettres. Le plus simple de ces mots est (01001)(01001)(01001)0. La longueur de ces mots est $3F_{n}+(F_{n-1}-2)$ , où $F_{n}$ est le $n$ ^e nombre de Fibonacci, et l'exposant de ces mots est $3+(F_{n-1}-2)/F_{n}$ .
Les mots sturmiens ont tous des exposants critiques supérieurs à celui du mot de Fibonacci^[4].
Le mot de Champernowne contient tous les facteurs, donc toutes les puissances. Son exposant critique est infini.

Commentaire modifier

Les deux premiers exemples montrent les deux cas qui peuvent se produire pour l'exposant critique : dans le mot de Thue-Morse, l'exposant critique est l'exposant d'une puissance réalisée, et donc l'intervalle des exposants des facteurs qui ne sont pas puissance est ouvert. C'est pourquoi on dit aussi que le mot de Thue-Morse est sans puissance $2^{+}$ , le symbole additif voulant signifier qu'il est sans puissance strictement plus grande que 2.

Pour le mot de Fibonacci en revanche, c'est l'intervalle des exposants des puissances réalisées qui est ouvert. Il est sans puissance $(5+{\sqrt {5}})/2$ , et cet exposant étant irrationnel, il ne peut bien sûr pas être réalisé.

Propriétés modifier

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

L'exposant critique peut prendre toute valeur réelle plus grande que $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].

Exposant critique minimal modifier

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 :

RT(d)=\inf\{E(w)\mid u

est un mot infini sur

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 $u$ et $v$ de même longueur, le nombre d'occurrences de chaque lettre dans $u$ et $v$ diffère d'au plus 1. Sur un alphabet binaire, les mots équilibrés apériodiques coïncident avec les mots de Sturm.

Seuil de répétition équilibré modifier

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

RTB(d)=\inf\{E(w)\mid u

est un mot infini équilibré sur

d

symboles.

Les seuils connus sont :

$RTB(2)=2+(1+{\sqrt {5}})/{2}$
$RTB(3)=2+1/{\sqrt {2}}$
$RTB(4)=1+(1+{\sqrt {5}})/4$
$RTB(d)=d-2/d-3$ pour $5\leq d\leq 10$ .
$RTB(d)\geq d-2/d-3$ pour $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 à $d\geq 5$ symboles est égal à $d-2/d-3$ . Pour $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 $x_{0}$ ; les occurrences des 1 sont, de même, remplacées par les symboles successifs d'un mot infini $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 $(ab)^{\omega }$ et les 1 par les symboles de $(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 $d=9$ et $d=10$ ^[10]. Dvořáková, Opočenská, Pelantová et Shur donnent^[11], pour tout $d\geq 12$ , un mot équilibré d'exposant critique $d-1/d-2$ . Comme $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 $d-2/d-3$ par la nouvelle conjecture $d-1/d-2$ .

Articles connexes modifier

Notes et références modifier

Notes modifier

↑ L'usage du terme exposant critique a été systématisé dans (Krieger 2006). Il apparaît avant dans (Vandeth 2000). On a également utilisé le mot index, par exemple dans (Allouche et Shallit 2003) ou (Damanik et Lenz 2003).
↑ Allouche et Shallit 2003.
↑ Mignosi et Pirillo 1992.
↑ Damanik et Lenz 2003.
↑ Krieger et Shallit 2007.
↑ Krieger 2006.
↑ Ce résultat, de (Mignosi 1991), a été précisé ensuite. On connaît exactement les exposants critiques des mots sturmiens depuis (Carpi et De Luca 2000) et (Vandeth 2000).
↑ Narad Rampersad, Jeffrey Shallit et Élise Vandomme, « Critical exponents of infinite balanced words », Theor. Comput. Sci., vol. 777,‎ 2019, p. 454-463 (zbMATH 1446.68132)
↑ Pascal Hubert, « Suites équilibrées », Theor. Comput. Sci., vol. 242, n^os 1-2,‎ 2000, p. 91-108 (zbMATH 0944.68149).
↑ Francesco Dolce, Lubomíra Dvořáková et Edita Pelantová, « Computation of critical exponent in balanced sequences », Lect. Notes Comput. Sci., vol. 12847 « Combinatorics on words. 13th international conference, WORDS 2021 »,‎ 2021, p. 78-90 (zbMATH 07530210).
↑ Lubomíra Dvořáková, Daniela Opočenská, Edita Pelantová et Arseny M. Shur, « On minimal critical exponent of balanced sequences », Theoretical Computer Science, vol. 922,‎ juin 2022, p. 158-169 (arXiv 2112.02854).

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Critical exponent of a word » (voir la liste des auteurs).

Références modifier

(en) Jean-Paul Allouche et Jeffrey O. Shallit, Automatic sequences : Theory, applications, generalizations, Cambridge, Cambridge University Press, 2003, 571 p. (ISBN 0-521-82332-3, MR 1997038, zbMATH 1086.11015)
Dalia Krieger, « On critical exponents in fixed points of non-erasing morphisms », dans Oscar H. Ibarra et Zhe Dang, Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 4036), 2006, p. 280–291
Dalia Krieger et J. Shallit, « Every real number greater than one is a critical exponent », Theor. Comput. Sci., vol. 381,‎ 2007, p. 177–182 (DOI 10.1016/j.tcs.2007.04.037)
M. Lothaire, Algebraic combinatorics on words, Réimpression de l'édition de 2002 Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 90), 2011, 520 p. (ISBN 978-0-521-18071-9, MR 1905123, zbMATH 1221.68183, présentation en ligne)
Filippo Mignosi et Guiseppe Pirillo, « Repetitions in the Fibonacci infinite word », Theoret. Inform. Appl., vol. 26, n^o 3,‎ 1992, p. 199–204
D. Damanik et D. Lenz, « Powers in Sturmian sequences », European Journal of Combinatorics, vol. 24, n^o 4,‎ 2003, p. 377–390
Filippo Mignosi, « On the number of factors of Sturmian words », Theoret. Comput. Sci, vol. 82,‎ 1991, p. 71-84
Arturo Carpi et Aldo de Luca, « Special factors, periodicity, and an application to Sturmian words », Acta Informatica, vol. 36,‎ 2000, p. 983-1006
D. Vandeth, « Sturmian words and words with a critical exponent », Theoret. Comput. Sci., vol. 242,‎ 2000, p. 283-300

[1] L'usage du terme exposant critique a été systématisé dans (Krieger 2006). Il apparaît avant dans (Vandeth 2000). On a également utilisé le mot index, par exemple dans (Allouche et Shallit 2003) ou (Damanik et Lenz 2003).

[AS-2] Allouche et Shallit 2003.

[MP-3] Mignosi et Pirillo 1992.

[D-4] Damanik et Lenz 2003.

[KS-5] Krieger et Shallit 2007.

[K-6] Krieger 2006.

[Mi-7] Ce résultat, de (Mignosi 1991), a été précisé ensuite. On connaît exactement les exposants critiques des mots sturmiens depuis (Carpi et De Luca 2000) et (Vandeth 2000).

[8] Narad Rampersad, Jeffrey Shallit et Élise Vandomme, « Critical exponents of infinite balanced words », Theor. Comput. Sci., vol. 777,‎ 2019, p. 454-463 (zbMATH 1446.68132)

[9] Pascal Hubert, « Suites équilibrées », Theor. Comput. Sci., vol. 242, n^os 1-2,‎ 2000, p. 91-108 (zbMATH 0944.68149).

[10] Francesco Dolce, Lubomíra Dvořáková et Edita Pelantová, « Computation of critical exponent in balanced sequences », Lect. Notes Comput. Sci., vol. 12847 « Combinatorics on words. 13th international conference, WORDS 2021 »,‎ 2021, p. 78-90 (zbMATH 07530210).

[11] Lubomíra Dvořáková, Daniela Opočenská, Edita Pelantová et Arseny M. Shur, « On minimal critical exponent of balanced sequences », Theoretical Computer Science, vol. 922,‎ juin 2022, p. 158-169 (arXiv 2112.02854).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]