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|-|\operatorname{Alph}(w)|\), where \(|w|\) denotes the length of \(w\) and \(|\operatorname{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