The Tight Upper Bound on the Number of Distinct Squares in Circular Words

Abstract

A square is a word $xx$, where $x$ is nonempty. We show that a circular word of length $n$ contains at most $\lfloor 3n/2\rfloor$ distinct squares of length at most $n$. The proof combines known results relating squares to circuits in Rauzy graphs. The coefficient $3/2$ agrees with the known lower bound.

arXiv commentv2: Corrected cross-references and typographical errors, standardized notation, and clarified definitions and exposition. Main results unchanged