CLR cover
Previous problem

Problem 72: Three Square Prefixes

Next problem

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$.

Three square prefixes

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.