#
Problem 79: Binary Words with Few Squares

\(
\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.