Sesquipuissance

En mathématiques, en informatique théorique, et notamment en combinatoire des mots, une sesquipuissance ou mot de Zimin est un mot sur un alphabet qui possède un préfixe propre qui est aussi un suffixe propre. En d'autre termes, une sesquipuissance est un mot avec bord. Une sesquipuissance est un motif inévitable, en ce sens que tout mot assez long en contient une en facteur. On définit par récurrence des sesquipuissances d'ordre n>1 : ce sont des mots qui ont un bord qui lui-même est une sesquipuissances d'ordre n-1.

Suite bi-idéale

Soit $A$ un alphabet. On définit sur $A$ les sesquipuissances d'ordre $n$, par récurrences sur $n$ comme suit. Tout mot non vide sur $A$ est une sesquipuissance d'ordre $1$; si $u$ est une sesquipuissance d'ordre $n$ et $v$ est un mot non vide, alors $uvu$ est une sesquipuissance d'ordre $n+1$. Le degré d'un mot non vide est le plus grand entier $d$ tel que $w$ est une sesquipuissance d'ordre $d$.

Une suite bi-idéale est une suite de mots $(f_{i})_{i\geq 1}$, avec $f_{1}$ un mot non vide, et tel que, pour $i\geq 1$, il existe un mot non vide $g_{i}$ avec

$f_{i+1}=f_{i}g_{i}f_{i}$.

Avec cette définition, le degré d'un mot $w$ est la longueur de la plus longue suite bi-idéale se terminant par $w$.

Pour un alphabet fini $A$ à $k$ lettres, il existe un entier $M$ dépendant de $k$ et de $n$ tel que tout mot de longueur $M$ possède un facteur qui est une sesquipuissance d'ordre au moins $n$. Ceci signifie que les sesquipuissances sont des motifs inévitables.

Dans toute suite bi-idéale $(f_{i})_{i\geq 1}$, le mot $f_{i}$ est un préfixe propre de $f_{i+1}$, et la suite $(f_{i})_{i\geq 1}$ converge vers le mot infini

$f=f_{1}g_{1}f_{2}g_{2}\cdots \$

Un mot infini est une sesquipuissance s'il est la limite d'une suite bi-idéale infinie. Un mot infini est une suite bi-idéale si et seulement s'il est un mot récurrent, c'est-à-dire si tous ses facteurs apparaissent infiniment souvent.

Supposons fixé un ordre total sur les lettres de l’alphabet $A$. Pour des entiers positifs quelconques $p$ et $n$, tout mot assez long ou bien possède un facteur qui est une puissance d'ordre $p$, ou un facteur qui est une sesquipuissance d'ordre au moins $n$; dans le deuxième cas, ce facteur a une factorisation en $n$ mots de Lyndon.

Mot de Zimin

Les mots de Zimin sont les éléments d'une suite bi-idéale particulière, où le facteur central de chaque terme est une nouvelle lettre : ils sont définis par récurrence par :

$Z_{0}=\varepsilon ;Z_{n}=Z_{n-1}a_{n}Z_{n-1}$,

où $a_{1},\dots ,a_{n},\dots$ sont des letres.

• Les mots de Zimin d'ordre 1,2,... les plus courts sont :

a, aba, abacaba, abacabadabacaba

Ici, a, b, c, d sont des lettres. Leurs longueurs forment la suite A123121 de l'OEIS. Ces mots interviennent dans la description des mouvements du jeux des tours de Hanoï.

• Les exposants des plus hautes puissances de 2 qui divisent les entiers naturels positifs sont :

0102010301020104010201030102010...

Les préfixes de longueur $2^{n}-1$ sont des mots de Zimin.

• Les mots de Zimin forment des motifs inévitables, en ce sens que tout mot assez long en contient une en facteur.

Bornes sur les mots de Zimin

Les bornes sur la longueur des mots de Zimin continuent à être un sujet d'étude actif.

Notes et références

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

Bibliographie

• Jean Berstel, Aaron Lauve, Christophe Reutenauer et Franco V. Saliola, Combinatorics on words : Christoffel words and repetitions in words, American Mathematical Society et Centre de recherches mathématiques, coll. « CRM Monograph Series » (n^o 27), 2008, 504 p. (ISBN 978-1-4200-7267-9, zbMATH 1161.68043) (lien Zentralblatt MATH)
• Aldo de Luca et Stefano Varricchio, « Sesquipowers », dans M. Lothaire, Algebraic combinatorics on words, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 90), 2011 (réimpr. 2011) (1^re éd. 2002) (ISBN 978-0-521-18071-9, zbMATH 1221.68183), p. 135-163 (lien Math Reviews, lien Zentralblatt MATH)
• Jean Berstel et Dominique Perrin, « Finite and infinite words », dans M. Lothaire, Algebraic combinatorics on words, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 90), 2011 (réimpr. 2011) (1^re éd. 2002) (ISBN 978-0-521-18071-9, zbMATH 1221.68183), p. 1-44 (lien Math Reviews, lien Zentralblatt MATH)
• [2019] David Conlon, Jacob Fox et Benny Sudakov, « Tower-type bounds for unavoidable patterns in words », Transactions of the American Mathematical Society, vol. 372, n^o 9,‎ 2019, p. 6213-6229 (DOI 10.1090/tran/7751, arXiv 1704.03479).

Articles liés

• Motif inévitable