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

Posted on 2015-05-30

Untitled

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.