# Avoidable words

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.

-
Oddly enough, Guy has a problem much like this in his Unsolved problems in Number Theory text. If there was a resolution, the first place I would look is in the latest edition of his book, with MathOverflow a close second. Gerhard "Ask Me About System Design" Paseman, 2012.04.13 –  Gerhard Paseman Apr 14 '12 at 0:30
@Gerhard: I hope that MO is a better source for this kind of information. I knew the status of the problem till approximately 2006. After that I stopped paying attention. –  Mark Sapir Apr 14 '12 at 0:33
@Mark, Google and Mathscinet turned nothing up. Maybe ask James Currie. He seems on top of these things. –  Benjamin Steinberg Apr 14 '12 at 2:13
@Ben: There was a conference on avoidability in BIRS (this February) co-organized by James Currie. It does not look like they discussed the problem. –  Mark Sapir Apr 14 '12 at 10:38
@Ben: I asked James Currie. He said that the information in the question is up to date, nothing new has been proved lately. –  Mark Sapir Apr 14 '12 at 15:24
show 2 more comments