CLR cover
Previous problem

Problem 79: Binary Words with Few Squares

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

The goal of the problem is to exhibit binary words containing the fewest number of (distinct) square factors.

A square is a word whose exponent is even, it is of the form $u^2=uu$ for a non-empty word $u$. The longest words on the binary alphabet $\{\sa{0},\sa{1}\}$ containing no square as factor are $\sa{010}$ and $\sa{101}$. But there are square-free infinite words on three-letter alphabets. One of them, on the alphabet $\{\sa{a}, \sa{b}, \sa{c}\}$, is obtained by iterating the morphism $f$ defined by $$\cases{ f(\sa{a}) = \sa{abc} &\cr f(\sa{b}) = \sa{ac} &\cr f(\sa{c}) = \sa{b}, }$$ which gives the infinite square-free word $$ \mathbf{f}=f^{\infty}(\sa{a})=\sa{abcacbabcbacabcacbacabcb}\cdots $$ despite the fact that $f$ does not preserve square-freeness of words, since $f(\sa{aba})=\sa{abcacabc}$ that contains the square $(\sa{ca})^2$.

A cube is a word whose exponent is a multiple of $3$.

Show that no infinite binary word contains less than 3 squares. Show that no infinite binary word that contains only 3 squares avoids cubes; i.e. is cube free.

Let $g$ be the morphism from $\{\sa{a}, \sa{b}, \sa{c}\}^*$ to $\{\sa{0},\sa{1}\}^*$ defined by $$\cases{ g(\sa{a}) = \sa{01001110001101} &\cr g(\sa{b}) = \sa{0011} &\cr g(\sa{c}) = \sa{000111}, }$$ Note that $g(\sa{ab})$ contains the three squares, $\sa{0}^2$, $\sa{1}^2$ and $\sa{10}^2$, as well as the two cubes $\sa{0}^3$ and $\sa{1}^3$.

Show there are only three squares and two cubes occurring in $\mathbf{g}=g(f^{\infty}(\sa{a}))$.
Consider distances between consecutive occurrences of $\sa{000}$.

References

  • G. Badkobeh. Infinite words containing the minimal number of repetitions. J. Discrete Algorithms, 20:38-42, 2013.
  • G. Badkobeh and M. Crochemore. Fewest repetitions in infinite binary words. RAIRO - Theor. Inf. and Applic., 46(1):17-31, 2012.
  • A. S. Fraenkel and J. Simpson. How many squares must a binary sequence contain? Electr. J. Comb., 2, 1995.
  • N. Rampersad, J. Shallit, and M. Wang. Avoiding large squares in infinite binary words. Theor. Comput. Sci., 339(1):19-34, 2005.