A Note on Squares in Binary Words

Abstract

We consider words over a binary alphabet. A word $w$ is overlap-free if it does not have factors (blocks of consecutive letters) of the form $uvuvu$ for nonempty $u$. Let $M(w)$ denote the number of positions that are middle positions of squares in $w$. We show that for overlap-free binary words, $2M(w)\le |w|+3$, and that there are infinitely many overlap-free binary words for which $2M(w)=|w|+3$.

6 pages