Are there uncountably many cube-free infinite binary words? - MathOverflow

Are there uncountably many cube-free infinite binary words?

2011-04-14T01:05:16Z

In http://mathoverflow.net/questions/61373 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.

Answer by Gjergji Zaimi for Are there uncountably many cube-free infinite binary words?

2011-04-14T01:54:39Z

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.

Answer by Mark Sapir for Are there uncountably many cube-free infinite binary words?

2011-04-14T01:56:40Z

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.

Answer by Steve Kass for Are there uncountably many cube-free infinite binary words?

2011-04-14T02:12:35Z

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.

Answer by Nishant Chandgotia for Are there uncountably many cube-free infinite binary words?

2011-04-14T02:28:12Z

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}$ .

Answer by James Currie for Are there uncountably many cube-free infinite binary words?

2011-08-19T05:51:58Z

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