Improved Bounds on the Maximum Number of Distinct Squares in Circular Words

We investigate the asymptotic growth of function CS(n), which maps n to the maximum number of<br/>distinct squares in a circular word of length n (that is, the maximum number of distinct squares of<br/>length at most n in a word ww of length 2n). We improve upon the lower bound of 1.25n established<br/>by Amit and Gawrychowski [SPIRE 2017] and the straightforward upper bound of 2n, which follows<br/>from the recent result of Brlek and Li [Comb. Theory, 2025] stating that there are fewer than n<br/>squares in standard (i.e., non-circular) words of length n. (Previously, Amit and Gawrychowski gave<br/>an upper bound of 3 2 15 n using a weaker upper bound on squares in standard words.) Specifically,<br/>we show that CS(n) ≤ ⌈1.8n⌉ and that, for infinitely many n, CS(n) ≥ 1.5n−O(√n).<br/>For the lower bound, we exploit the combinatorial structure of Fibonacci words to construct<br/>a family of square-rich circular words. For the upper bound, we exploit density properties of the<br/>starting positions of long squares, adapting an approach of Amit and Gawrychowski.