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$. Modèle:Harvsp ont montré que $M(n)\le 2n$. Ils ont conjecturé que $M(n)\le n$. Modèle:Harvsp a donné la borne $M(n)\le 2n-\mathrm{\Theta }(\log (n))$; Nguyen Huong Lam a amélioré la borne à $M(n)\le 95/48n$; et Modèle:Harvsp obtiennent la borne $11/6n$; Modèle:Harvsp enfin obtient $M(n)\le 3/2n$. Dans Modèle:Harvsp, il est montré que, sur un alphabet à $h$ lettres, on a $M(n)\le 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$Modèle:E contenues dans un mot a été encadré par Modèle:Harvsp qui donne la majoration $M_k(n)\le n-1/k-1$ et la minoration $n/k-1-\theta (\sqrt{n})\le 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 Modèle:Harvsp. Les deux textes font suite à l'article de Modèle:Harvsp.

Bibliographie

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article