1 files changed, 67 insertions, 0 deletions
diff --git a/posts/2015-05-30-infinite-binary-words-containing-repetitions-odd-periods.org b/posts/2015-05-30-infinite-binary-words-containing-repetitions-odd-periods.org
new file mode 100644
index 0000000..b632c03
--- /dev/null
+++ b/posts/2015-05-30-infinite-binary-words-containing-repetitions-odd-periods.org
@@ -0,0 +1,67 @@
+#+title: AMS review of 'Infinite binary words containing repetitions of
+#+title: odd period' by Badkobeh and Crochemore
+
+#+date: <2015-05-30>
+
+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;
+[[http://www.ams.org/mathscinet/search/publdoc.html?r=1&pg1=MR&s1=2142071&loc=fromrevtext][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.