Carrés distincts dans un mot
# Carrés distincts dans un mot

En combinatoire, et notamment en combinatoire des mots, le calcul du nombre de carrés distincts que peut contenir un mot donné est un problème posé par Fraenkel et Simpson en 1998 et pas encore entièrement résolu.

## Définitions

Un carré est un mot de la forme $xx$, comme bonbon. Un mot $z$ est un facteur d'un mot $w$ s'il apparaît dans le mot comme une séquence consécutive de symboles ; ainsi kipé est un facteur de wikipédia.

## Nombre de facteurs carrés

Soit $M(n)$ le nombre maximum de carrés distincts qui sont facteurs d'un mot de longueur $n$. Fraenkel et Simpson (1998) ont montré que $M(n)\leq 2n$. Ils ont conjecturé que $M(n)\leq n$. Ilie (205) a donné la borne $M(n)\leq 2n-\Theta (\log(n))$; Nguyen Huong Lam a amélioré la borne à $M(n)\leq 95/48n$; et Deza, Franek et Thierry (2015) obtiennent la borne $11/6n$; Thierry (2020) enfin obtient $M(n)\leq 3/2n$. Dans Brlek et Li (2022), il est montré que, sur un alphabet à $h$ lettres, on a $M(n)\leq n+1-h$. Ceci démontre la conjecture de Fraenkel et Simpson et en fait une version plus forte.

Le nombre $M_{k}(n)$ de puissances $k$e contenues dans un mot a été encadré par Li (2022) qui donne la majoration $M_{k}(n)\leq n-1/k-1$ et la minoration $n/k-1-\theta ({\sqrt {n}})\leq M_{k}(n)$. Il montre aussi que le nombre de toutes les puissances distinctes d’exposant au moins 2 est au plus $n-1$. Une version plus récente est Li, Pachocki et Radoszewski (2022). Les deux textes font suite à l'article de Brlek et Li (2022).

