Mot primitif

Les propriétés suivantes se trouvent dans les manuels, comme ceux de Lothaire[1] ou de Shallit[2]

On trouve parfois le nom « racine » de ${\displaystyle x}$ pour désigner l'unique mot primitif dont ${\displaystyle x}$ est une puissance ; il est aussi noté ${\displaystyle {\sqrt {x}}}$. L'entier ${\displaystyle n}$ tel que ${\displaystyle x={\sqrt {x}}^{n}}$ est l'« exposant » de ${\displaystyle x}$. Par exemple, pour ${\displaystyle x=ababab}$, ${\displaystyle {\sqrt {x}}=ab}$ et ${\displaystyle x=(ab)^{3}}$, d'exposant 3. La propriété se démontre à l'aide du lemme ci-dessous.

Prenons par exemple ${\displaystyle x=abaab}$. Ses conjugués sont

${\displaystyle abaab,baaba,aabab,ababa,babaa}$.

Ils sont tous primitifs.

Comme les conjugués d'un mot primitif sont tous distincts, car s'il y en avait deux égaux, ils vérifieraient une équation décrite dans le lemme ci-dessous, et seraient puissances d'un troisième mot, donc imprimitifs. La classe de conjugaison d'un mot primitif, ou de manière équivalent le mot circulaire associé à ce mot, est appelé un collier apérodique. Le nombre de colliers apériodiques de longueur ${\displaystyle n}$, donc le nombre de classes de conjugaison de mots primitifs de longueur longueur n sur un alphabet à k lettres est

${\displaystyle M_{k}(n)={1 \over n}\sum _{d\mid n}\mu (d)k^{n/d}}$.

Ici, ${\displaystyle \mu }$ est la fonction de Möbius. Comme les conjugués d'un mot primitif sont tous primitifs et distincts, le nombre de mots primitifs de longueur longueur n sur un alphabet à k lettres est

${\displaystyle nM_{k}(n)=\sum _{d\mid n}\mu (d)k^{n/d}}$.

Les fonctions ${\displaystyle M_{k}(n)}$ sont aussi appelés les polynômes de colliers (en la variable ${\displaystyle k}$), et la formule est attribuée au colonel Moreau. Pour ${\displaystyle k=2}$, la suite des ${\displaystyle M_{k}(n)}$ est la suite A001037 de l'OEIS. Pour ${\displaystyle n=3}$ et ${\displaystyle n=4}$, les colliers apériodiques binaires sont respectivement 001,011 et 0001,0011,0111.

Le nombre ${\displaystyle M_{k}(n)}$ est le nombre de mots de Lyndon de longueur ${\displaystyle n}$ sur ${\displaystyle k}$ lettres : Toute classe de conjugaison d'un mot primitif contient un seul élément qui est plus petit que les autres dans un ordre lexicographique fixé, et c'est l'unique mot de Lyndon de la classe, de sorte que les mots de Lyndon forment un système de représentants des classes de mots primitifs ou de colliers apériodiques.

La première partie de cette propriété est en fait une paraphrase du théorème de Lyndon et Schützenberger qui dit que si ${\displaystyle x^{n}y^{m}=z^{p}}$ pour ${\displaystyle n,m,p\geq 2}$, alors ${\displaystyle x,y}$ et ${\displaystyle z}$ ont même racine. Ceci n'est plus vrai si ${\displaystyle n=1}$ ou ${\displaystyle m=1}$. Ainsi, pour ${\displaystyle x=aba}$ et ${\displaystyle y=baab}$, le mot ${\displaystyle x^{2}y=abaababaab}$ est un carré. La deuxième partie de l'énoncé[3] dit qu'au plus l'un des mots ${\displaystyle x^{n}y}$ ou ${\displaystyle xy^{m}}$ n'est pas primitif. Si ${\displaystyle x}$ et ${\displaystyle y}$ sont de même longueur, alors le seul mot éventuellement imprimitif  est ${\displaystyle xy}$. Par exemple, si ${\displaystyle x=aba}$ et ${\displaystyle y=bab}$, alors ${\displaystyle xy=(ab)^{3}}$. On peut montrer[4] que dans le cas général, si ${\displaystyle xy^{m}}$ est imprimitif, alors ${\displaystyle m\leq M}$, avec ${\displaystyle M=2+(|x|-2)/|y|}$. Ainsi, pour ${\displaystyle x=aababa}$ et ${\displaystyle y=ab}$, on a ${\displaystyle M=2+(|x|-2)/|y|=2+(6-2)/2=4}$, et pour ${\displaystyle m=2}$, on a ${\displaystyle xy^{2}=(aabab)^{2}}$.

Un bord d'un mot ${\displaystyle w}$ est un mot qui est à la fois un préfixe propre et un suffixe propre de ${\displaystyle w}$. Un mot sans bord est un mot qui ne possède pas de bord non vide.

Le résultat suivant est utile dans les démonstrations des propriétés des mots primitifs :

Ainsi, pour démontrer que tout mot a une racine unique, on peut supposer qu'un mot ${\displaystyle w}$ s'écrit de deux façons comme puissance d'un mot primitif, soit ${\displaystyle w=x^{n}=y^{m}}$ avec ${\displaystyle x}$ et ${\displaystyle y}$ des mots primitifs. Par la condition (3), il en résulte que ${\displaystyle x=z^{p}}$ et ${\displaystyle y=z^{q}}$, et comme ${\displaystyle x}$ et ${\displaystyle y}$ sont primitifs, on a ${\displaystyle p=q=1}$ et ${\displaystyle x=y}$.