Sesquipuissance

En mathématiques, en informatique théorique, et notamment en combinatoire des mots, une sesquipuissance ou mot de Zimin[1] 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$ [2]. Le degré d'un mot non vide est le plus grand entier $d$ tel que $w$ est une sesquipuissance d'ordre $d$ [3].

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$ [3].

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[4] - [5].

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[6]. Un mot infini est une suite bi-idéale si et seulement s'il est un mot récurrent[6] - [7], c'est-à-dire si tous ses facteurs apparaissent infiniment souvent[8].

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[7].

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

Dénommé ainsi d'après son inventeur, le mathématicien russe A. Zimin.
de Luca et Varricchio 2011, p. 135
de Luca et Varricchio 2011, p. 136
de Luca et Varricchio 2011, p. 137
Berstel et al. 2008, p. 132
de Luca et Varricchio 2011, p. 141
Berstel et al. 2008, p. 133
Berstel et Perrin 2011, p. 30

(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