Combinatorial Theory

Let $u$ be a nonempty finite word, a square is a word of the form $uu$. In this paper, we prove that for a given finite word $w$, the number of distinct square factors of $w$ is bounded by $|w|-|\mathrm{Alph}(w)|$, where $|w|$ denotes the length of $w$ and $|\mathrm{Alph}(w)|$ denotes the number of distinct letters in $w$. This result answers positively a conjecture stated by Fraenkel and Simpson in 1998 and the $d$-step conjecture stated by Deza, Franek and Jiang in 2011.

Mathematics Subject Classifications: 68R15, 68R10, 68R05

Keywords: Combinatorics on words, squares, repetition