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.
