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

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