How many squares can a string contain? (Q1268630): Difference between revisions

Given a word over a fixed alphabet, a square is a subword of the form \(uu= u^2\) where \(u\) is a nonempty word. Denote by \(M(n)\) the maximum number of distinct squares (not translates of each other) possible in a word of length \(n\). Given the word \(a_1a_2\cdots a_n\) let \(s_i\) be the number of squares beginning with \(a_i\) that do not appear later. The authors show \(s_i\leq 2\), \(1\leq i\leq n\), and deduce that \(M(n)< 2n\) for all \(n\). Additionally, for infinitely many \(n\) it is shown that \(M(n)= n- o(n)\). Similar results are obtained for \(P(n)\), the maximum number of distinct primitive squares (\(u\) is not of the form \(v^j\), \(j\geq 2\)) possible in a word of length \(n\).