HOW MANY SQUARES CAN A STRING CONTAIN

All our words (strings) are over a fired alphabet. A square is a subwo rd 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 o ther. A word u is primitive if u cannot be written in the form u = v(j ) for some j greater than or equal to 2. A square u(2) with u primitiv e is primitive rooted Let M(n) denote the maximum number of distinct s quares, P(n) the maximum number of distinct primitive rooted squares i n a word of length,1. We prove: no position in any word can be the beg inning of the rightmost occurrence of more than two squares, from whic h we deduce M(n) < 2n for all n > 0, and P(n) = n - o(n) for infinitel y many n. (C) 1998 Academic Press.