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).

Bibliographie

• Aviezri S. Fraenkel et Jamie Simpson, « How many squares can a string contain? », J. Comb. Theory, Sér. A, vol. 82, n^o 1,‎ 1998, p. 112-120 (zbMATH 0910.05001).
• Shuo Li, « On the number of k-powers in a finite word », Advances in Applied Mathematics, vol. 139,‎ août 2022, article n^o 102371 (DOI 10.1016/j.aam.2022.102371, arXiv 2203.16742).
• Shuo Li, Jakub Pachocki et Jakub Radoszewski, « A note on the maximum number of k-powers in a finite word », Arxiv,‎ mai 2022 (arXiv 2205.10156).
• Srecko Brlek et Shuo Li, « On the number of squares in a finite word », Arxiv,‎ avril 2022 (arXiv 2204.10204).
• Lucian Ilie, « A note on the number of distinct squares in a word », dans S. Brlet et Ch. Reutenauer, C. (éditeurs), Proc. Words 2005, 5-th International Conference on Words, Montréal, LaCIM, coll. « Publications du LaCIM » (n^o 36), 13–17 sept. 2005, p. 289–294
• Lucian Ilie, « A simple proof that a word of length n has at most 2n distinct squares », J. Comb. Theory, Ser. A, vol. 112, n^o 1,‎ 2005, p. 163-164 (zbMATH 1088.68146).
• Antoine Deza, Frantisek Franek et Adrien Thierry, « How many double squares can a string contain? », Discrete Appl. Math., vol. 180,‎ 2015, p. 52-69 (zbMATH 1303.05002).
• Adrien Thierry, « A proof that a word of length n has less than 1.5n distinct squares », Arxiv,‎ 2020 (arXiv 2001.02996).
• Maithilee Patawar et Kalpesh Kapoor, « Density of distinct squares in non-primitive words », Information Processing Letters, vol. 182,‎ août 2023, article n^o 106367 (DOI 10.1016/j.ipl.2023.106367)