Conjecture de Billaud

La conjecture de Billaud est une conjecture en combinatoire des mots, formulée par Michel Billaud, qui concerne une propriété qu'un mot vérifie s'il en est ainsi pour ses sous-mots obtenus en effaçant toutes les occurrences d'une lettre.

Énoncé

La conjecture de Billaud est la suivante :

Conjecture de Billaud — Si, pour chaque lettre $x$ apparaissant dans un mot $w$, le mot obtenu en effaçant toutes les occurrences de $x$ dans $w$ est point fixe d'un morphisme $f_{x}$ non trivial, alors le mot $w$ lui-même est aussi un point fixe d'un morphisme non trivial.

La conjecture a été formulée en 1993 et est encore ouverte en 2022.

Résultats partiels

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. Françoise Levé et Gwénaël Richomme ont démontré la conjecture dans le cas où chaque morphisme $f_{x}$ de l'énoncé n'a qu'une seule lettre expansive (une lettre $a$ est dite expansive pour un morphisme $h$ si $a$ figure dans l'image $h(a)$ et si $h(a)$ est de longueur au moins 2). La conjecture a été prouvée pour un alphabet à 4 lettres.

Exemple

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

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

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

$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

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

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

Énoncé

Théorème (Levé-Richomme) — Soit $w$ un mot avec sur un alphabet $A$ à au moins 3 lettres. Supposons que, pour tout $x$ dans $A$, l'héritier $\delta _{x}(w)$ appartient à FW et a un témoin $f_{x}$ avec une lettre expansive. Alors $w$ appartient à FW et a un témoin $f$ avec une lettre expansive

.

Une autre formulation

Un mot est morphiquement primitif 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 :

Contraposée de la conjecture de Billaud — Si un mot est morphiquement primitif, alors au moins un de ses héritiers est morphiquement primitif.

Discussion

Tester si un mot est morphiquement primitif peut se faire en temps linéaire. La conjecture de Billaud est une implication et non une caractérisation. Ainsi, alors qu'il existe des mots morphiquement non primitifs, tels que le mot $ababcdcd$ (point fixe du morphisme $a\mapsto ab$,$b,d\mapsto \varepsilon$, $c\mapsto cd$), dont aucun des héritiers $ababcc$, $ababdd$, $aacdcd$ et $bbcdcd$ n'est morphiquement primitif, il existe également des mots tels que $abccbcca$, qui sont morphiquement imprimitifs, mais dont certains héritiers sont morphiquement primitifs (ici $abba$ et $acccca$).

Michel Billaud est, de 1984 à 2021, Maître de Conférences au Département Informatique de l'Institut Universitaire de Technologie de l'Université Bordeaux ; il est membre du Laboratoire Bordelais d'Informatique (LaBRI)

Bibliographie

• M. Billaud, « A problem with words », Letter in Newsgroup Comp. theory,‎ 1993 (lire en ligne)
• Françoise Levé et Gwénaël Richomme, « On a conjecture about finite fixed points of morphisms », Theoretical Computer Science, vol. 339, n^o 1,‎ juin 2005, p. 103–128 (DOI 10.1016/j.tcs.2005.01.011 , lire en ligne)
• Daniel Reidenbach et Johannes C. Schneider, « Morphically primitive words », Theoretical Computer Science, vol. 410, n^o 21,‎ 17 mai 2009, p. 2148–2161 (DOI 10.1016/j.tcs.2009.01.020 , lire en ligne)
• Szymon Łopaciuk et Daniel Reidenbach, « On Billaud words and their companions », Theoretical Computer Science, vol. 940,‎ 9 janvier 2023, p. 231–253 (DOI 10.1016/j.tcs.2022.11.004 , lire en ligne)

• Szymon Łopaciuk et Daniel Reidenbach, « The Billaud Conjecture for $\Sigma =4$, and Beyond », Lecture Notes in Computer Science, Springer International Publishing, vol. 13257 « Developments in Language Theory »,‎ 2022, p. 213–225 (ISBN 978-3-031-05578-2, DOI 10.1007/978-3-031-05578-2_17, lire en ligne)