2026-09-05T06:57:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25932 2026-06-23T13:12:23Z ddc:004 open_access

Improved Bounds on the Maximum Number of Distinct Squares in Circular Words Charalampopoulos, Panagiotis Mohamed, Manal Radoszewski, Jakub Rytter, Wojciech Waleń, Tomasz Zuba, Wiktor circular words squares repetitions We investigate the asymptotic growth of function CS(n), which maps n to the maximum number of distinct squares in a circular word of length n (that is, the maximum number of distinct squares of length at most n in a word ww of length 2n). We improve upon the lower bound of 1.25n established by Amit and Gawrychowski [SPIRE 2017] and the straightforward upper bound of 2n, which follows from the recent result of Brlek and Li [Comb. Theory, 2025] stating that there are fewer than n squares in standard (i.e., non-circular) words of length n. (Previously, Amit and Gawrychowski gave an upper bound of 32/15n using a weaker upper bound on squares in standard words.) Specifically, we show that CS(n) ≤ ⌈1.8 n⌉ and that, for infinitely many n, CS(n) ≥ 1.5n-𝒪(√n). For the lower bound, we exploit the combinatorial structure of Fibonacci words to construct a family of square-rich circular words. For the upper bound, we exploit density properties of the starting positions of long squares, adapting an approach of Amit and Gawrychowski. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Panagiotis Charalampopoulos and Manal Mohamed and Jakub Radoszewski and Wojciech Rytter and Tomasz Waleń and Wiktor Zuba 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.6 urn:nbn:de:0030-drops-259325 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.6 eng https://creativecommons.org/licenses/by/4.0/legalcode