How many double squares can a string contain?

Counting the types of squares rather than their occurrences, we consider the problem of bounding the number of distinct squares in a string. Fraenkel and Simpson showed in 1998 that a string of length nn contains at most 2n2n distinct squares. Ilie presented in 2007 an asymptotic upper bound of 2n−Θ(logn). We show that a string of length nn contains at most ⌊11n/6⌋⌊11n/6⌋ distinct squares. This new upper bound is obtained by investigating the combinatorial structure of double squares and showing that a string of length nn contains at most ⌊5n/6⌋⌊5n/6⌋ particular double squares. In addition, the established structural properties provide a novel proof of Fraenkel and Simpson’s result.