Conjecture de Restivo
# Conjecture de Restivo

La conjecture de Restivo est une assertion de la théorie des codes due à Antonio Restivo en 1981. Son énoncé original a été contredit en 2010, cependant des versions plus faibles demeurent aujourd'hui ouvertes.

## Énoncé

On se donne un alphabet fini Σ et un ensemble de mots sur cet alphabet $S\subseteq \Sigma ^{*}$. L'ensemble des facteurs de S, noté Fact(S), est l'ensemble suivant :

$Fact(S)=\{w\in \Sigma ^{*}|\exists u,v\in \Sigma ^{*},uwv\in S^{*}\}$

Un mot $m\in \Sigma ^{*}$ est dit incomplétable pour un ensemble $M\subseteq \Sigma ^{*}$si $m\in Fact(M^{*})\backslash \Sigma ^{*}$, autrement dit tel que si on prend une suite finie quelconque de mots de $M$, et qu'on concatène pour en former un nouveau $u=u_{1}u_{2}...u_{n}$, $m$ n’apparaîtra pas dans $u$.

On note $l(M)=\max _{w\in M}|w|$ la longueur maximale d'un mot de $M$et $sl(M)=\sum _{m\in M}|m|$la somme des longueurs des mots de $M$.

On peut remarquer que $M\subseteq \Sigma ^{\leq l(M)}$donc $|M|\leq |\Sigma ^{\leq l(m)}|={\frac {|\Sigma |^{l(M)+1}-1}{|\Sigma |-1}}=O(|\Sigma |^{l(M)})$ et $sl(M)\leq \sum _{m\in M}l(M)=|M|l(M)=O(l(M)|\Sigma |^{l(M)})$

En 1981 Restivo conjecture que tout ensemble $M$ayant un mot incomplétable en a, en particulier, un de longueur au plus $2l(M)^{2}$et que de plus ce mot est de la forme $m_{1}um_{2}u...m_{l(M)-1}u$où $u$est un mot de longueur $l(M)$ n'appartenant pas à $M$et les $m_{i}$sont des mots de longueur au plus $l(M)$. Ceci est vrai dans le cas où $M=\Sigma ^{k}\backslash \{w\}$avec $w$de longueur $k$, mais pas en général.

## Énoncés plus faibles

On ne sait pas si la longueur du plus petit mot incomplétable de $M$est polynomiale en $l(M)$, ni même si elle est polynomiale en $sl(M)$

On dit que $M$est un code si pour tous $u_{1},...,u_{n},v_{1},...,v_{m}\in M$, si $u_{1}...u_{n}=v_{1}...v_{m}$alors $n=m$et pour tout $0<i\leq n$, $u_{i}=v_{i}$.

Dans ce cas on ne sait pas si la longueur du plus petit mot incomplétable est polynomiale en $l(M)$.

