Une Conjecture sur les Mots

Michel Billaud (michel.billaud@laposte.net)

12 janvier 2022

Ce texte fait partie d’une petite collection de notes mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 2.0 France.

Il y a très longtemps (vers 1988), je m’étais posé un petit problème, que je n’ai pas réussi à résoudre. Rien d’étonnant, c’était pas dans mon domaine, et je n’y ai travaillé que mollement. Donc j’ai laissé tomber rapidement, mais après avoir appelé à l’aide sur Usenet, qui ne manque pas de gens plus compétents (on en retrouve des traces dans le newsgroup comp.theory, en 1993, mais j’avais dû déjà poser la question en 1988).

Given a word w, if for each letter x occurring in w, there exists non-trivial morphism fx such that the word obtained by erasing all the occurrences of x in x is a fixed point of fx, then there exists a non-trivial morphism f such that w is a fixed point of f.

Et bon, surprise, on est en 2022, mais apparemment c’est toujours pas résolu.

Bon, peut-être que c’est pas très clair, alors j’explique :

1 Quelques définitions

Je suppose que vous avez quand même entendu parler de mots construits sur un alphabet. Sinon, c’est pas compliqué

1.1 Mots

1.2 Morphisme

En général, un morphisme est une application d’un ensemble vers un autre qui préserve une opération.

Ici on considére les morphismes entre deux ensembles de mots (construits sur des alphabets différents ou pas) qui préservent la concaténation.

C’est-à-dire que si f est un morphisme, pour tous mots u, v on a f(u.v) = f(u).f(v).

Une conséquence est qu’un morphisme est déterminé par la connaissance des images des lettres de l’alphabet. C’est évident : si on connait f(a), f(b) etc. alors on peut calculer l’image des mots formés à partir des lettres a, b, ... etc.

La notion s’étend à des langages (ensembles de mots) : l’image d’un ensemble de mots par un morphisme, c’est l’ensemble des images par le morphisme.

1.3 Points-fixes d’un morphisme

On regarde maintenant les morphismes dans le cas où les ensembles de départ et d’arrivée sont les mêmes. Automorphismes ?

Un point fixe du morphisme f, c’est un mot w qui est sa propre image par f (c-a-d f(w) = w).

Exemple ab est un point fixe pour f(a) = ab et f(b) = ϵ.

Un morphisme n’admet pas forcément de point fixe, exemple évident : le morphisme qui double chaque lettre : f(a) = aa, f(b) = bb,;....

Mais quand il en admet un, il en admet une infinité : si f(w) = w, alors f(wn) = wn.

2 Morphismes qui ont un mot comme point-fixe

On aurait pu s’amuser avec les propriétés de l’ensemble des points fixes d’un morphisme, mais on part dans la direction inverse :

Ce qui amène quelques observations :

Exemple : si on part du mot w = aa, on a f(w) = w si et seulement si f(a) = a. Les valeurs de f(b), f(c) etc. sont indifférentes.

On va donc se concentrer sur les morphismes restreints aux lettres qui apparaissent dans le mot.

2.1 Mots primitifs : qui ne sont points fixes que par l’identité

Ce qui nous intéresse, c’est les mots qui ne sont leur propre image que d’une seule et unique façon : par l’identité.

Exemples : a, aa, an, abba, ababa, (ab)na, etc.

Contre-exemple : abab, en prenant f(a) = ab et f(b) = ϵ.

Il est bien évident qu’il y en a une infinité (cf. les exemple ab).

On va les appeler “mots primitifs”.

2.2 La conjecture

Informellement, la question c’est

tout mot primitif sur un alphabet à n lettres peut-il être obtenu à partir d’un mot primitif sur un alphabet à n − 1 lettres, en y insérant judicieusement des occurrences de la lettre supplémentaire ?

Exemple

Bref, posé dans l’autre sens :

pour tout mot primitif w, existe-t-il au moins une lettre x dans w qu’on pourrait effacer pour retomber sur un mot primitif ?

Les enumérations par programme n’ont jusqu’ici pas trouvé de contre-exemple, et on conjecture que oui.

Mais la preuve reste à faire.

3 Bibliographie

(TODO)