MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Cube-free infinite binary words

A word $y$ is a subword of $w$ if there exist words $x$ and $z$ (possibly empty) such that $w=xyz$. Thus, $01$ is a subword of $0110$, but $00$ is not a subword of $0110$. I'm interested in right-infinite words over a two-letter alphabet that do not contain subwords of the form $xxx$, where $x$ is a word of one or more letters. (For example, the Thue-Morse word, the Kolakoski word, Stewart's choral sequence, and so on.) In particular, I would like to know if there are any general statements about all such words. For example, are there an infinite number of them? Is there any way to classify them?

It's possible that one way to classify cube-free infinite binary words is to group them according to their subwords. For example, the Kolakoski word has the subword $00100$ whereas the Thue-Morse word does not, so they belong in different classes. The words created in Tony's answer (see below) have the same subwords (the Thue-Morse word is recurrent), so they belong to one class. I suppose there an infinite number of these classes.

Another possible way to classify cfib words is to group them according to their subword complexity. For example, Stewart's choral sequence has a subword complexity of $2n$ (where $n$ is the length of the subword), so we can group it with other cfib words with subword complexity $2n$. Is the subword complexity of the Kolakoski word known?

-
 As I write this, there are only two answers (Tony's and Amy's). I wish I could select both of them. I'm selecting Tony's because he answered first. – Joel Reyes Noche Apr 16 2011 at 15:34 I changed my selected answer because I feel that James Currie's answer is what I originally had in mind when I asked the question. – Joel Reyes Noche May 27 2012 at 15:19

Here are some deep facts relating to binary cfw's:

1) The set of right infinite binary cube-free words is a perfect set in the topological sense: For any given such sequence, there is a distinct one which agrees with it to the nth letter. In particular, there are uncountably many binary cfw's.

2) Given any finite binary sequence, it is decidable whether it extends to an infinite binary cube-free word.

3) The number of (finite) binary cfw's of length n grows exponentially with n.

These results (and analogous ones for k-power free words over various alphabets) are proved in

-
 Thank you for the references. – Joel Reyes Noche Aug 19 2011 at 7:30

As far as I'm aware, there is no known characterisation of cube-free infinite binary words. However, one way to generate such words is by iteration of so-called cube-free binary morphisms, i.e., endomorphisms on a binary alphabet that preserve cube-free finite binary words. The family of all such morphisms has been characterised; see for instance the paper by Richomme & Wlazinski (2002) and references therein. Note that there exist binary morphisms that are not cube-free, but generate cube-free infinite binary words. Richomme & Wlazinski (2002) provided an example of such a morphism. They also proved a new characterisation of morphisms of a particular form that generate cube-free infinite binary words and showed that this characterisation provides a more effective method of deciding whether a given binary morphism generates a cube-free infinite word compared to the original characterisation of such morphisms obtained by KarhumÃ¤ki (1983). The references in Richomme & Wlazinski's paper should be helpful to you.

-
 Thank you for this! – Joel Reyes Noche Apr 12 2011 at 14:47

There are an infinite number of cube-free binary words. Let $w$ be one such word (such as the Thue-Morse word). Let $w-j$ denote the word obtained by deleting the first $j$ letters from $w$. Clearly, for all $j \in \mathbb{N}$, $w-j$ is also cube-free. Also, I claim that $w-j \neq w-k$ for any $j < k$, from which the result follows. Towards a contradiction, suppose that $w-j=w-k$ for some $j < k$. Let $w=abc$, where $a$ has length $j$ and $b$ has length $k-j$. Then $bc=c$ by hypothesis. Iterating, we see that $c$ starts with $bbb$, contradicting that $w$ is cube-free.

-
The word $w = 010101\ldots$ is cube-free, and $w - j = w - k$ if $j$ and $k$ are the same modulo $2$. – Tara Brough Apr 12 2011 at 10:23
Oh, sorry, I had misunderstood the definition of cube-free. I thought that $x$ was just a single symbol, not a word in $\{0,1\}^*$! – Tara Brough Apr 12 2011 at 10:31
This construction gives a countable infinity of cube-free words. I would imagine there would be an uncountable infinity. – Gerry Myerson Apr 12 2011 at 13:00
@Tony: Wow. I didn't think of that. Thanks! – Joel Reyes Noche Apr 12 2011 at 13:15
Gerry asks a question related to his comment above at mathoverflow.net/questions/61615 – Joel Reyes Noche Apr 14 2011 at 1:56