Carrés distincts dans un mot

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

Le nombre ${\displaystyle M_{k}(n)}$ de puissances ${\displaystyle k}$^e contenues dans un mot a été encadré par Li (2022) qui donne la majoration ${\displaystyle M_{k}(n)\leq n-1/k-1}$ et la minoration ${\displaystyle 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 ${\displaystyle 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).

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

• Portail des mathématiques
• Portail de l'informatique théorique