Return to Question

Let $u(x_1,...,x_n)$ be a word, $k\in \mathbb{N}$. We say that $u$ is $k$-avoidable if there exists an infinite word in $k$ letters $\{a_1,...,a_k\}$ which does not contain values of $u$ (i.e. words of the form $u(v_1,...,v_n)$, $v_i\in \{a_1,...,a_k\}^+$ as a subword. For example $x^3$ is 2-avoidable and $x^2$ is 3-avoidable but not 2-avoidable because two infinite words constructed by Thue and Morse avoid $x^2$ and $x^3$. All avoidable words have been described by Bean-Ehrenfeucht-McNulty and Zimin (see these slides of George McNulty's talk, for example.

• Is there an example of a $6$-avoidable but not $5$-avoidable word?

The word $x^3$ is 2-avoidable but not 1-avoidable.

The word $x^2$ is $3$-avoidable (Thue) but not 2-avoidable (obvious).

Walter's word $$abwbcxcayba$$ is 4-avoidable but not $3$-avoidable.

Ronald Clark in his PhD thesis proved that $$abubawacxbcycdazdcd$$ is $5$-avoidable but not $4$-avoidable (see Clark, Ronald J. The existence of a pattern which is 5-avoidable but 4-unavoidable. Internat. J. Algebra Comput. 16 (2006), no. 2, 351–367.)

It is of course hard to believe that every avoidable word is $5$-avoidable (or $C$-avoidable for any constant $C$). There were rumors that an example of a $6$-avoidable word which is not $5$-avoidable has also been constructed.

What is the status of that question?

Update Since according to James Currie, the above is almost as much as we know, as far as the lower bound is concerned, here is the best upper bounds I know. Let $k$ ibe the number of letters in an avoidable word $u$, $n=n(k)$ is the minimal $n$ such that all such $u$ are $n$-avoidable. An exponential upper bound for $n(k)$ was found in the original papers by Bean-Ehrenfeucht-McNulty and Zimin, quadratic upper bound - in my paper, 1987 (I considered a more complicated problem of avoidability of identities) and a linear upper bound $9k+20$ in Baker, McNulty, Taylor, Growth problems for avoidable words. Theoret. Comput. Sci. 69 (1989), no. 3, 319–345. The best upper bound I know is $n(k)\le 3\lfloor k/2\rfloor+3$. It was proved by Irina Mel'nichuk in "On the existence of infinite finitely generated free semigroups in some varieties of semigroups", Leningrad Algebraic Systems with One Operation and Relations (1985), pp. 74–83. George McNulty claims in the talk I linked to above that Mel'nichuk proved the upper bound $k+6$ in 1988, but I could not find a reference. The question is whether $k(n)$ is bounded by a constant.

Let $u(x_1,...,x_n)$ be a word, $k\in \mathbb{N}$. We say that $u$ is $k$-avoidable if there exists an infinite word in $k$ letters $\{a_1,...,a_k\}$ which does not contain values of $u$ (i.e. words of the form $u(v_1,...,v_n)$, $v_i\in \{a_1,...,a_k\}^+$ as a subword. For example $x^3$ is 2-avoidable and $x^2$ is 3-avoidable but not 2-avoidable because two infinite words constructed by Thue and Morse avoid $x^2$ and $x^3$. All avoidable words have been described by Bean-Ehrenfeucht-McNulty and Zimin (see these slides of George McNulty's talk, for example.

• Is there an example of a $6$-avoidable but not $5$-avoidable word?

The word $x^3$ is 2-avoidable but not 1-avoidable.

The word $x^2$ is $3$-avoidable (Thue) but not 2-avoidable (obvious).

Walter's word $$abwbcxcayba$$ is 4-avoidable but not $3$-avoidable.

Ronald Clark in his PhD thesis proved that $$abubawacxbcycdazdcd$$ is $5$-avoidable but not $4$-avoidable (see Clark, Ronald J. The existence of a pattern which is 5-avoidable but 4-unavoidable. Internat. J. Algebra Comput. 16 (2006), no. 2, 351–367.)

It is of course hard to believe that every avoidable word is $5$-avoidable (or $C$-avoidable for any constant $C$). There were rumors that an example of a $6$-avoidable word which is not $5$-avoidable has also been constructed.

What is the status of that question?

Update Since according to James Currie, the above is almost as much as we know, as far as the lower bound is concerned, here is the best upper bounds I know. Let $k$ ibe the number of letters in an avoidable word $u$, $n=n(k)$ is the minimal $n$ such that all such $u$ are $n$-avoidable. An exponential upper bound for $n(k)$ was found in the original papers by Bean-Ehrenfeucht-McNulty and Zimin, quadratic upper bound - in my paper, "Problems of Burnside type and the finite basis property in varieties of semigroups". Math. USSR-Izv. 30 (1988), no. 2, 295–314 (I considered a more complicated problem of avoidability of identities) and a linear upper bound $9k+20$ in Baker, McNulty, Taylor, Growth problems for avoidable words. Theoret. Comput. Sci. 69 (1989), no. 3, 319–345. The best upper bound I know is $n(k)\le 3\lfloor k/2\rfloor+3$. It was proved by Irina Mel'nichuk in "On the existence of infinite finitely generated free semigroups in some varieties of semigroups", Leningrad Algebraic Systems with One Operation and Relations (1985), pp. 74–83. George McNulty claims in the talk I linked to above that Mel'nichuk proved the upper bound $k+6$ in 1988, but I could not find a reference. The question is whether $k(n)$ is bounded by a constant.

Let $u(x_1,...,x_n)$ be a word, $k\in \mathbb{N}$. We say that $u$ is $k$-avoidable if there exists an infinite word in $k$ letters $\{a_1,...,a_k\}$ which does not contain values of $u$ (i.e. words of the form $u(v_1,...,v_n)$, $v_i\in \{a_1,...,a_k\}^+$ as a subword. For example $x^3$ is 2-avoidable and $x^2$ is 3-avoidable but not 2-avoidable because two infinite words constructed by Thue and Morse avoid $x^2$ and $x^3$. All avoidable words have been described by Bean-Ehrenfeucht-McNulty and Zimin (see these slides, for example.

• Is there an example of a $6$-avoidable but not $5$-avoidable word?

The word $x^3$ is 2-avoidable but not 1-avoidable.

The word $x^2$ is $3$-avoidable (Thue) but not 2-avoidable (obvious).

Walter's word $$abwbcxcayba$$ is 4-avoidable but not $3$-avoidable.

Ronald Clark in his PhD thesis proved that $$abubawacxbcycdazdcd$$ is $5$-avoidable but not $4$-avoidable (see Clark, Ronald J. The existence of a pattern which is 5-avoidable but 4-unavoidable. Internat. J. Algebra Comput. 16 (2006), no. 2, 351–367.)

It is of course hard to believe that every avoidable word is $5$-avoidable (or $C$-avoidable for any constant $C$). There were rumors that an example of a $6$-avoidable word which is not $5$-avoidable has also been constructed.

What is the status of that question?

Let $u(x_1,...,x_n)$ be a word, $k\in \mathbb{N}$. We say that $u$ is $k$-avoidable if there exists an infinite word in $k$ letters $\{a_1,...,a_k\}$ which does not contain values of $u$ (i.e. words of the form $u(v_1,...,v_n)$, $v_i\in \{a_1,...,a_k\}^+$ as a subword. For example $x^3$ is 2-avoidable and $x^2$ is 3-avoidable but not 2-avoidable because two infinite words constructed by Thue and Morse avoid $x^2$ and $x^3$. All avoidable words have been described by Bean-Ehrenfeucht-McNulty and Zimin (see these slides of George McNulty's talk, for example.

• Is there an example of a $6$-avoidable but not $5$-avoidable word?

The word $x^3$ is 2-avoidable but not 1-avoidable.

The word $x^2$ is $3$-avoidable (Thue) but not 2-avoidable (obvious).

Walter's word $$abwbcxcayba$$ is 4-avoidable but not $3$-avoidable.

Ronald Clark in his PhD thesis proved that $$abubawacxbcycdazdcd$$ is $5$-avoidable but not $4$-avoidable (see Clark, Ronald J. The existence of a pattern which is 5-avoidable but 4-unavoidable. Internat. J. Algebra Comput. 16 (2006), no. 2, 351–367.)

It is of course hard to believe that every avoidable word is $5$-avoidable (or $C$-avoidable for any constant $C$). There were rumors that an example of a $6$-avoidable word which is not $5$-avoidable has also been constructed.

What is the status of that question?

Update Since according to James Currie, the above is almost as much as we know, as far as the lower bound is concerned, here is the best upper bounds I know. Let $k$ ibe the number of letters in an avoidable word $u$, $n=n(k)$ is the minimal $n$ such that all such $u$ are $n$-avoidable. An exponential upper bound for $n(k)$ was found in the original papers by Bean-Ehrenfeucht-McNulty and Zimin, quadratic upper bound - in my paper, 1987 (I considered a more complicated problem of avoidability of identities) and a linear upper bound $9k+20$ in Baker, McNulty, Taylor, Growth problems for avoidable words. Theoret. Comput. Sci. 69 (1989), no. 3, 319–345. The best upper bound I know is $n(k)\le 3\lfloor k/2\rfloor+3$. It was proved by Irina Mel'nichuk in "On the existence of infinite finitely generated free semigroups in some varieties of semigroups", Leningrad Algebraic Systems with One Operation and Relations (1985), pp. 74–83. George McNulty claims in the talk I linked to above that Mel'nichuk proved the upper bound $k+6$ in 1988, but I could not find a reference. The question is whether $k(n)$ is bounded by a constant.