Avoidability of circular formulas (Q1743715)

A pattern \(p\) is a non-empty finite word over an alphabet \(\Delta\) of variables. The formula associated to \(p\) is obtained by replacing every variable that appears only once in \(p\) by a dot. The factors between the dots are called fragments. An occurrence of a formula \(f\) in a word \(w\) over an alphabet \(\Sigma\) is a non-erasing morphism \(h:\Delta^\ast\to\Sigma^\ast\) such that the \(h\)-image of every fragment of \(f\) is a factor of \(w\). The avoidability index \(\lambda(f)\) of a formula \(f\) is the smallest size of \(\Sigma\) such that an infinite word over \(\Sigma\) contains no occurrence of \(f\). The circular formula \(C_t\) is the formula over \(t\geq 1\) variables \(A_0,\dots, A_{t-1}\) consisting of the \(t\) fragments \(A_iA_{i+1}\dots A_{i+t}\) such that the indices are taken modulo \(t\). Thus, \(C_1 = A_0A_0\), \(C_2 = A_0A_1A_0.A_1A_0A_1\), \(C_3 = A_0A_1A_2A_0.A_1A_2A_0A_1.A_2A_0A_1A_2\), and so on. It is known that \(\lambda(A_0A_0)=3\) [\textit{A. Thue}, Christiania Vidensk.-Selsk. Skr. 1906, No. 7, 22 p. (1906; JFM 39.0283.01)] and \(\lambda(A_0A_1A_0.A_1A_0A_1)=3\) [\textit{J. Cassaigne}, Motifs évitables et régularité dans les mots. Paris: Université Paris VI (PhD Thesis) (1994)]. The authors prove that \(\lambda(C_3)=3\) and \(\lambda(C_t)=2\) for all \(t\geq4\) (Theorem 1). They also calculate that \(\lambda(ABCBA.CBABC)=2\) and \(\lambda(ABCA.CABC.BCB)=3\) (Theorem 4).