Cube-free infinite binary words

Question

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?

Answer 1

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

http://dl.acm.org/citation.cfm?id=873885 and http://www.sciencedirect.com/science/article/pii/0195669895900519

Answer 2

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.

Answer 3

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.

Answer 4

Lemma: Someone only able to speak an infinite cubefree word can convey information at least $1/24$ of the speed of an ordinary person able to speak an arbitrary binary sequence.

Proof: Consider the following period-$12$ sequence over the alphabet $\{ 0, 1, ?\}$:

$S = (001?010?1011)^{\infty}$

Now suppose $T$ is a sequence derived from $S$ by replacing each $?$ with a $0$ or $1$.

• $T$ clearly has no words of the form $xxx$ for a single digit $x$.

If we take alternate digits in $T$, we obtain $(010011)^{\infty}$. The only cubes in this sequence have length a multiple of $6$, hence:

• If $T$ contains a word of the form $WWW$, where $W$ has even length, then $W$ has length divisible by 12.

• Also, $T$ contains a word of the form $WWW$ where $W$ has length $3$ if and only if two question marks in the same dodecad $(001?010?1011)$ are both zero. Assert that this will not happen.

• If $T$ contains a word of the form $WWW$, where $W$ has length divisible by $3$, then $W$ has length divisible by $12$.

Hence we are only worried about words of length coprime to or divisible by $12$.

• If the length of $W$ is $\pm 1 \mod 12$, then the existence of $WWW$ is ruled out by the proof of the non-existence of $xxx$.

• Similarly, it is easy to observe that there are none of length $\pm 5 \mod 12$.

So any word of the form $WWW$ in $T$ requires $W$ to have length divisible by $12$.

---

Now begin with any tripleless sequence over $\{A, B\}$ (such as the Thue-Morse sequence) and apply the substitution rules:

$A \mapsto (001001011011)$

$B \mapsto (0011010?1011)$

Then we obtain an infinite word over $\{0, 1, ?\}$ such that:

• Every replacement of the question marks with digits yields an infinite cubefree word.
• Every icositetrad contains one question mark.

The result follows.