Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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 '11 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 '12 at 15:19
add comment

3 Answers

up vote 7 down vote accepted

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

share|improve this answer
    
Thank you for the references. –  Joel Reyes Noche Aug 19 '11 at 7:30
add comment

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.

share|improve this answer
    
Thank you for this! –  Joel Reyes Noche Apr 12 '11 at 14:47
add comment

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.

share|improve this answer
    
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 '11 at 10:23
1  
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 '11 at 10:31
1  
This construction gives a countable infinity of cube-free words. I would imagine there would be an uncountable infinity. –  Gerry Myerson Apr 12 '11 at 13:00
1  
@Tony: Wow. I didn't think of that. Thanks! –  Joel Reyes Noche Apr 12 '11 at 13:15
1  
Gerry asks a question related to his comment above at mathoverflow.net/questions/61615 –  Joel Reyes Noche Apr 14 '11 at 1:56
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.