Mot de Lyndon

En mathématiques, dans les domaines de la combinatoire et de l'informatique, un mot de Lyndon est un mot qui est strictement plus petit, dans l'ordre lexicographique, que tous ses permutés circulaires. Les mots de Lyndon doivent leur nom au mathématicien Roger Lyndon qui les a introduits en 1954 sous le nom standard lexicographic sequences. Il existe plusieurs définitions équivalentes. Un mot de Lyndon k-aire de longueur n est un mot à n lettres sur un alphabet totalement ordonné de taille k, et qui est strictement minimal (au sens de l'ordre lexicographique) parmi tous ses conjugués (ou permutés circulaires). Strictement minimal signifie ici qu'il n'apparaît qu'une seule fois dans la liste de ses permutés ; il est donc forcément primitif, c'est-à-dire n'est pas puissance entière d'un autre mot. De manière équivalente, un mot de Lyndon est caractérisé par la propriété suivante : est toujours lexicographiquement plus petit que tous ses suffixes non triviaux. En d'autres termes, est un mot de Lyndon si et seulement si, pour toute factorisation en deux mots, avec et non vides, on a . Une variante de cette caractérisation est la suivante: un mot de longueur est un mot de Lyndon si et seulement si, pour tout avec , le préfixe de longueur de est strictement inférieur au suffixe de longueur de . Une autre définition : est un mot de Lyndon si et seulement si, pour toute factorisation en deux mots, avec et non vides, on a . Ces définitions impliquent que si n'est pas une lettre, alors est un mot de Lyndon si et seulement s'il existe deux mots de Lyndon et tels que et . Les mots de Lyndon sont des représentants des classes de conjugués de mots primitifs, et sont donc en bijection avec les mots circulaires ou colliers primitifs. Soit le nombre de mots de Lyndon de longueur sur un alphabet à lettres. Alors on a la formule suivante, aussi appelée formule de Witt dans le contexte des algèbres de Lie : où est la fonction de Möbius classique. La fonction a plusieurs interprétations, voir . Ainsi, est le nombre de polynômes irréductibles de degré sur le corps fini .