Complexité abélienne d'un mot

Deux mots sont commutativement équivalents ou équivalents au sens abélien s'ils ont même image commutative, autrement dit s'ils sont les mêmes à une permutation de lettres près, ou encore s'ils sont des anagrammes l'un de l'autre.

La complexité abélienne d'un mot fini ou infini ${\displaystyle x}$ est la fonction ${\displaystyle p_{x}}$ qui compte le nombre de facteurs de longueur donnée dans ce mot, à permutation de lettres près. C'est une autre mesure de la complexité combinatoire d'une suite.

Exemple. Les 6 facteurs de longueur 6 du mot de Fibonacci ${\displaystyle 010010100100101001010\cdots }$ sont ${\displaystyle 001010,010010,010100,100100,100101,101001}$. Ces facteurs se regroupent, par une permutation des lettres, en deux classes : les quatre mots contenant deux occurrences de ${\displaystyle 1}$, et les deux qui en contiennent trois. La complexité abélienne prend donc la valeur 2.

Soit ${\displaystyle A}$ un alphabet. L'image commutative d'un mot ${\displaystyle w}$ sur ${\displaystyle A}$ est l'image, dans le monoïde commutatif libre, de ce mot. On appelle souvent cette image le vecteur de Parikh du mot, d'après le mathématicien Rohit Parikh qui l'a considéré le premier dans le cadre d'un travail sur l'image commutative de langages algébriques. Si ${\displaystyle A=\{a_{1},a_{2},\ldots ,a_{n}\}}$, le vecteur de Parikh d'un mot ${\displaystyle w}$ sur ${\displaystyle A}$ est le vecteur ${\displaystyle \Psi (w)}$ de ${\displaystyle \mathbb {N} ^{n}}$ défini par

${\displaystyle \Psi (w)=(|w]_{a_{1}},|w]_{a_{2}},\ldots ,|w]_{a_{n}})}$.

Ici, ${\displaystyle |w]_{a}}$ est le nombre de lettres ${\displaystyle a}$ qui apparaissent dans le mot ${\displaystyle w}$.

Exemple

Soit ${\displaystyle A=\{0,1,2\}}$ un alphabet à trois lettres, et soit ${\displaystyle w=0120200}$. Le vecteur de Parikh de ${\displaystyle w}$ est ${\displaystyle \Psi (w)=(4,1,2)}$, parce qu'il y a quatre lettres ${\displaystyle 0}$, une lettre ${\displaystyle 1}$ et deux lettres ${\displaystyle 2}$ dans le mot ${\displaystyle w}$.

La complexité abélienne d'un mot fini ou infini ${\displaystyle x}$ est la fonction notée ${\displaystyle p_{x}}$ qui, pour tout entier naturel ${\displaystyle n}$, donne le nombre notée ${\displaystyle p_{x}(n)}$d e vecteurs de Parikh distincts de facteurs de longueur ${\displaystyle n}$ de ${\displaystyle x}$. De manière pratique on regarde, pour chaque entier ${\displaystyle n}$, les facteurs de longueur ${\displaystyle n}$ de ${\displaystyle x}$, et on les groupe en paquets contenant les facteurs de même image commutative. Le nombre de paquets est le nombre cherché.

Deux mots sont commutativement équivalents à l'ordre ${\displaystyle k}$, ou ${\displaystyle k}$-commutativement équivalents s'il chaque facteur de longueur au plus ${\displaystyle k}$ apparaît le même nombre de fois dans chacun des deux mots[4]. Pour ${\displaystyle k=1}$, on retrouve l'équivalence commutative, et pour ${\displaystyle k=\infty }$, on obtient l'égalité.

Formellement, deux mots ${\displaystyle x}$ et ${\displaystyle y}$ sont ${\displaystyle k}$-commutativement équivalents, et on écrit ${\displaystyle x\sim _{k}y}$ si ${\displaystyle |x|_{u}=|y|_{u}}$ pour tout mot ${\displaystyle u}$ de longueur ${\displaystyle |u|\leq k}$. Ici on note ${\displaystyle |w|_{u}}$ le nombre d’occurrences du mot ${\displaystyle u}$ comme facteur dans ${\displaystyle w}$.

Si ${\displaystyle k=1}$, on retrouve la notion d’équivalence commutative ; si ${\displaystyle |x|=|y|\leq k}$, alors ${\displaystyle x\sim _{k}y}$ si et seulement si${\displaystyle x=y}$.

Exemple. Les mots ${\displaystyle x=010110}$ et ${\displaystyle y=011010}$ sont 3-commutativement équivalents (0 et 1 apparaissant chacun 3 fois; 01 et 10 chacun 2 fois etc), mais ils ne sont pas 4-commutativement équivalents puisque 0101 apparaît dans ${\displaystyle u}$ et pas dans ${\displaystyle v}$.

Exemple. Les mots ${\displaystyle x=0110}$ et ${\displaystyle y=1101}$ ne sont pas 2-commutativement équivalents : ils ont les mêmes facteurs de longueur 2, mais ils ne sont pas commutativement équivalents.

Pour un entier ${\displaystyle k}$, on note ${\displaystyle p_{x}^{(k)}}$ la fonction de complexité ${\displaystyle k}$-abélienne d'un mot ${\displaystyle x}$ qui donne, pour chaque entier ${\displaystyle n}$, le nombre de classes de la relation \sim_k, donc le nombre de facteurs de ${\displaystyle x}$ de longueur ${\displaystyle n}$ distincts à ${\displaystyle k}$-commutativité près. ${\displaystyle p_{x}^{(1)}}$ dénote la complexité commutative, et ${\displaystyle p_{x}^{(\infty )}}$ est la fonction de complexité usuelle qui compte le nombre de facteurs distincts.

Il est commode d'introduire une fonction auxiliaire ${\displaystyle q^{(k)}}$ définie par

${\displaystyle q^{(k)}(n)={\begin{cases}n+1&n<2k\\2k&n\geq 2k\end{cases}}}$.

La suite des valeurs prises par cette fonction est ${\displaystyle (1,2,3,\ldots ,2k-1,2k,2k,\ldots )}$.

Propriété.- Si la complexité ${\displaystyle k}$-abélienne d'un mot infini ${\displaystyle x}$ vérifie ${\displaystyle p_{x}^{(k)}(n)<q^{(k)}(n)}$ pour tout ${\displaystyle n}$, alors ${\displaystyle x}$ est ultimement périodique.

La caractérisation des mots sturmiens par leur fonction e complexité abélienne se généralise comme suit :

Propriété.- Un mot apériodique dont la complexité k-abélienne ${\displaystyle p_{x}^{(k)}=}$ est égale à ${\displaystyle q^{(k)}}$ est sturmien.