How Many Squares Can a String Contain?

. All our words (strings) are over a fixed alphabet. A square is a subword of the form uu = u 2 , where u is a nonempty word. Two squares are distinct if they are of different shape, not just translates of each other. A word u is primitive if u cannot be written in the form u = v j for some j 2. A square u 2 with u primitive is primitive rooted. Let M (n) denote the maximum number of distinct squares, P (n) the number of distinct primitive rooted squares in a word of length n. We prove: no position in any word can be the beginning of the rightmost occurrence of more than two squares, from which we deduce M (n) ! 2n for all n ? 0, and P (n) = n \Gamma o(n) for infinitely many n. 1. Introduction We consider words (strings, sequences) over a fixed alphabet throughout. A square is a pair of identical adjacent subwords, such as 1011010110 = 10110 2 over the binary alphabet. Two squares are distinct if they are of different shape, not just translates of each other. Denote by M (n..