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

In Cube-free infinite binary words it was established that there are infinitely many cube-free infinite binary words (see the earlier question for definitions of terms). The construction given in answer to that question yields a countable infinity of such words. In a comment on that answer, I raised the question of whether there is an uncountable infinity of such words. My comment has not generated any response; perhaps it will attract more interest as a question.

I should admit that I ask out of idle curiosity, and have no research interest in the answer; it just seems like the logical question to ask once you know some set is infinite.

share|improve this question
1  
Thanks for asking this as a separate question, as I'd also like to know the answer (out of idle curiosity). –  Tony Huynh Apr 14 '11 at 1:24
    
Thank you also for posting this. I admit that it is only now I realize the implications of your earlier comment. –  Joel Reyes Noche Apr 14 '11 at 1:54
add comment

5 Answers

up vote 11 down vote accepted

Denote by $\mu$ the mapping from the Thue-Morse sequence, $\mu(0)=01$ and $\mu(1)=10$. Now define a sequence of maps from binary words to binary words, $g$, so that $g_{\emptyset}(w)=w$, $g_{0b}(w)=\mu^2(g_{b}(w))$ and $g_{1b}(w)=0\mu^2(g_{b}(w))$. Now given an infinite binary sequence $B=b_1b_2\dots$ define $w_{B}$ to be the limit of $$g_{b_1}(w),g_{b_1b_2}(w),g_{b_1b_2b_3}(w),\dots$$ The $w_B$ give you uncountably many $7/3$-power free words (so in particular, cube free) which moreover have infinitely many overlaps.

This stronger result is proved here. I believe all known constructions of large families of such sequences are defined by iterative mappings.

share|improve this answer
1  
I'm also going to take a guess that $7/3$ is the critical exponent. I.e. there are only countably many $\alpha$-power free infinite binary words when $\alpha<7/3$. But I don't know how to prove this. –  Gjergji Zaimi Apr 14 '11 at 2:03
    
It is not true that all of the cube-free (or 7/3-free) words are defined by iterating substitutions. See my answer, for example. –  Mark Sapir Apr 14 '11 at 2:06
    
I believe our answers are quite similar. Even in your answer you start with a Thue-Morse sequence, I guess I should have phrased it as "all constructions have similar flavour"... :P But then again, I'm not sure of that either. –  Gjergji Zaimi Apr 14 '11 at 2:12
1  
The most general proof is probably topological. Take the set of all bi-infinite cube-free words $A$. It is a closed subset of the (compact) metric space of all bi-infinite words in 2 letters closed under the shift. Then argue that such an $A$ is either finite of uncountable. I think a similar argument can be found in one of the papers by Furstenberg on symbolic dynamics and uniform recurrence. –  Mark Sapir Apr 14 '11 at 2:25
2  
The critical exponent question was solved by Karhumaki and Shallit: J. Karhum¨aki and J. Shallit. Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory. Ser. A 105 (2004), 335–347. –  James Currie Oct 28 '11 at 23:05
show 5 more comments

There are uncountably many cube-free infinite words. Indeed, consider any cube-free word in 2 letters $a$ and $b$ (say, the Thue-Morse word). Then replace some occurrences of $a$ by $a'$ and some occurrences of $a$ by $a''$. You get a new infinite word in $a',a'',b$ which is also cube-free (but in 3 letters), a continuum of them. One can then use a substitution from a 3-letter alphabet to a 2-letter alphabet that preserves cube-freeness (see Bean, Dwight R.; Ehrenfeucht, Andrzej; McNulty, George F.Avoidable patterns in strings of symbols. Pacific J. Math. 85 (1979), no. 2, 261–294) to obtain a continuum of cube-free words in 2 letters.

share|improve this answer
add comment

One can also consider the following. Let x be the Thue Morse sequence. Let X be the closure of the set of shifts of sequences i.e. sequences obtained by deleting the first few letters. This set is perfect. Hence X is uncountable. Also every element of X is cube free.
The only thing to check here is that X is perfect. For this it is sufficient to check that x is a limit point. One can do this by using the fact that x is generated by the sequence $0 \rightarrow 01$ and $1 \rightarrow 10$. The topology on $\{0,1\}^{\mathbb N}$ is the product of the discrete topology on $\{0,1\}$ .

share|improve this answer
    
Right: see my comment above. –  Mark Sapir Apr 14 '11 at 2:32
1  
Isn't the Symbolic Dynamics tag apt for this question? –  Nishant Chandgotia Apr 14 '11 at 4:20
add comment

I just saw and answered the earlier question, but perhaps I should repeat my post:

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
add comment

In “Open Problems in Pattern Avoidance” (here), James Currie wrote, “It is known [15] that the set of cubefree $\omega$-words over a 2-letter alphabet is uncountable.” Reference [15] of Currie’s paper is here; it claims to establish a method for generating the set of all strongly cube-free infinite words (no subword of the form $BBb$ where $b$ is the first symbol of $B$, called in this paper “irreducible”), and it shows that a particular subset is uncountable.

share|improve this answer
add comment

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.