AMS review of 'Infinite binary words containing repetitions of odd period' by Badkobeh and Crochemore
.

This paper is about the existence of pattern-avoiding infinite binary words, where the patterns are squares, cubes and $$3^+$$-powers.    There are mainly two kinds of results, positive (existence of an infinite binary word avoiding a certain pattern) and negative (non-existence of such a word). Each positive result is proved by the construction of a word with finitely many squares and cubes which are listed explicitly. First a synchronising (also known as comma-free) uniform morphism $$g\: \Sigma_3^* \to \Sigma_2^*$$

is constructed. Then an argument is given to show that the length of squares in the code $$g(w)$$ for a squarefree $$w$$ is bounded, hence all the squares can be obtained by examining all $$g(s)$$ for $$s$$ of bounded lengths. The argument resembles that of the proof of, e.g., Theorem 1, Lemma 2, Theorem 3 and Lemma 4 in [N. Rampersad, J. O. Shallit and M. Wang, Theoret. Comput. Sci. 339 (2005), no. 1, 19–34; MR2142071]. The negative results are proved by traversing all possible finite words satisfying the conditions.

Let $$L(n_2, n_3, S)$$ be the maximum length of a word with $$n_2$$ distinct squares, $$n_3$$ distinct cubes and that the periods of the squares can take values only in $$S$$ , where $$n_2, n_3 \in \Bbb N \cup \{\infty, \omega\}$$ and $$S \subset \Bbb N_+$$ .    $$n_k = 0$$ corresponds to $$k$$-free, $$n_k = \infty$$ means no restriction on the number of distinct $$k$$-powers, and $$n_k = \omega$$ means $$k^+$$-free.

Below is the summary of the positive and negative results:

(1) (Negative) $$L(\infty, \omega, 2 \Bbb N) < \infty$$ : $$\nexists$$ an infinite $$3^+$$ -free binary word avoiding all squares of odd periods. (Proposition 1)

(2) (Negative) $$L(\infty, 0, 2 \Bbb N + 1) \le 23$$ : $$\nexists$$ an infinite 3-free binary word, avoiding squares of even periods. The longest one has length $$\le 23$$ (Proposition 2).

(3) (Positive) $$L(\infty, \omega, 2 \Bbb N + 1) = \infty$$ : $$\exists$$ an infinite $$3^+$$ -free binary word avoiding squares of even periods (Theorem 1).

(4) (Positive) $$L(\infty, \omega, \{1, 3\}) = \infty$$ : $$\exists$$ an infinite $$3^+$$ -free binary word containing only squares of period 1 or 3 (Theorem 2).

(5) (Negative) $$L(6, 1, 2 \Bbb N + 1) = 57$$ : $$\nexists$$ an infinite binary word avoiding squares of even period containing $$< 7$$ squares and $$< 2$$ cubes. The longest one containing 6 squares and 1 cube has length 57 (Proposition 6).

(6) (Positive) $$L(7, 1, 2 \Bbb N + 1) = \infty$$ : $$\exists$$ an infinite $$3^+$$ -free binary word avoiding squares of even period with 1 cube and 7 squares (Theorem 3).

(7) (Positive) $$L(4, 2, 2 \Bbb N + 1) = \infty$$ : $$\exists$$ an infinite $$3^+$$ -free binary words avoiding squares of even period and containing 2 cubes and 4 squares (Theorem 4).

Copyright notice: This review is published at http://www.ams.org/mathscinet-getitem?mr=3313467, its copyright owned by the AMS.