## Example

\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\)

For example, when $u=\sa{abaab}$, $v=\sa{abaababa}$, $w=\sa{abaababaabaabab}$,
the prefix condition is met:

$\sa{abaababaab}$

$\sa{abaababaabaababa}$

$\sa{abaababaabaabababaababaabaabab}$

but $u^2$ is not a prefix of $v$ nor $v^2$ a prefix of $w$, which otherwise
would provide a trivial example.

#
Problem 72: Three Square Prefixes

The combinatorial analysis of square prefixes of a
word leads to several consequences useful to design algorithms related to
periodicities.

Three non-empty words $u$, $v$ and $w$ satisfy the square-prefix condition if
$u^2$ is a proper prefix of $v^2$ and $v^2$ a proper prefix of $w^2$.

Show that if $u^2$, $v^2$ and $w^2$ satisfy the square-prefix condition and
$|w| \leq 2|u|$ then $u,v,w \in z^2z^*$ for some word $z$.

The conclusion implies in particular that $u$ is not primitive.
In fact, this implication holds true if both the square-prefix condition
and the inequality $|w|\lt |u|+|v|$ are met (Three-Square-Prefix lemma).
But the statement in the above question has a stronger conclusion that says
we are essentially in the trivial situation where $w^2=\sa{a}^k$ or the like.

Give infinitely many examples of word triples that satisfy the square-prefix
condition and for which both $|u|+|v|=|w|$ and $u$ is primitive.

The next question provides a consequence of the *Three-Square-Prefix lemma*
or of the first statement.
The exact upper bound or even a tight bound
on the concerned quantity is still unknown.

Show that less than $2|x|$ (distinct) primitively rooted squares can be
factors of a word $x$.

Another direct consequence of the Three-Square-Prefix lemma is that a word of
length $n$ has no more than $\log_\Phi n$ prefixes that are primitively
rooted squares.
The golden mean $\Phi$ comes from the recurrence relation for
Fibonacci numbers in the second question.

## References

H. Bai, A. Deza, and F. Franek. On a lemma of Crochemore and Rytter.
*J. Discrete Algorithms*, **34**:18-22, 2015.
M. Crochemore, C. Hancart, and T. Lecroq. *Algorithms on Strings*.
Cambridge University Press, 2007. 392 pages.
M. Crochemore and W. Rytter. Squares, cubes, and time-space efficient
string searching. *Algorithmica*, **13**(5):405-425, 1995.
A. Deza, F. Franek, and A. Thierry. How many double squares can a
string contain? *Discrete Applied Mathematics*, **180**:52-69, 2015.
A. S. Fraenkel and J. Simpson. How many squares can a string contain?
*J. Comb. Theory, Ser. A*, **82**(1):112-120, 1998.
D. Hickerson. There are at most 2n distinct twins in any finite string of
length n. Personal communication by D. Gusfield, 2003.
L. Ilie. A simple proof that a word of length $n$ has at most $2n$ distinct
squares. *J. Comb. Theory, Ser. A*, **112**(1):163-164, 2005.
[147] L. Ilie. A note on the number of squares in a word. *Theor. Comput.
Sci.*, **380**(3):373-376, 2007.
M. Lothaire. Algebraic *Combinatorics on Words*. Encyclopedia of Mathematics
and its Applications. Cambridge University Press, 2002.