Conjecture de Billaud

La conjecture de Billaud est la suivante :

La conjecture a été formulée en 1993^[1] par Michel Billaud (LaBRI, Université Bordeaux 1) et est encore ouverte en 2022.

Summarize Timeline Top Qs Fact Check

La conjecture est trivialement vérifiée pour un alphabet à 2 lettres, et a été démontrée par P. Zimmermann « A problem with words from Michel Billaud » pour un alphabet à 3 trois lettres^[2]. Françoise Levé et Gwénaël Richomme ont démontré^[2] la conjecture dans le cas où chaque morphisme ${\displaystyle f_{x}}$ de l'énoncé n'a qu'une seule lettre expansive (une lettre ${\displaystyle a}$ est dite expansive pour un morphisme ${\displaystyle h}$ si ${\displaystyle a}$ figure dans l'image ${\displaystyle h(a)}$ et si ${\displaystyle h(a)}$ est de longueur au moins 2). La conjecture a été prouvée pour un alphabet à 4 lettres^[3].

On considère^[2] le morphisme ${\displaystyle f}$ sur ${\displaystyle \{1,2,3,4,5,6,7,8,9\}}$ donné par

${\displaystyle f(1)=2}$, ${\displaystyle f(2)=1}$, ${\displaystyle f(3)=34}$, ${\displaystyle f(4)=435}$, ${\displaystyle f(5)=6}$, ${\displaystyle f(6)=7}$, ${\displaystyle f(7)=\varepsilon }$, ${\displaystyle f(8)=6787}$, ${\displaystyle f(9)=966}$.

Les lettres mortelles sont ${\displaystyle \{5,6,7\}}$, les lettres expansives sont ${\displaystyle \{8,9\}}$. Les points fixes de ${\displaystyle f}$ sont les mots de ${\displaystyle \{76787,96677\}^{*}}$ puisque en effet par exemple

${\displaystyle f(76787)=\varepsilon \cdot 7\cdot \varepsilon \cdot 6787\cdot \varepsilon }$.

On note FW l'ensemble des mots qui sont points fixes d'un morphisme non trivial

${\displaystyle \mathrm {FW} =\{w\mid \exists f\neq \mathrm {Id} :f(w)=w\}}$.

Un témoin pour un mot ${\displaystyle w}$ dans FW est un morphisme ${\displaystyle f}$ non trivial tel que ${\displaystyle f(w)=w}$. Enfin, on note ${\displaystyle \delta _{x}(w)}$ le mot obtenu en effaçant toutes les occurrences de la lettre ${\displaystyle x}$ dans ${\displaystyle w}$. Un tel mot est un héritier (heir en anglais) de ${\displaystyle w}$.

.

Un mot est morphiquement primitif^[4] s'il n'a pas d'autres points fixes que le morphisme identité. Par définition, un mot est morphiquement primitif si et seulement s'il n'appartient pas à l'ensemble FW. La conjecture de Billaud, par contraposition, s'énonce comme suit^[5] :