Are there uncountably many cube-free infinite binary words? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T11:09:18Z http://mathoverflow.net/feeds/question/61615 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61615/are-there-uncountably-many-cube-free-infinite-binary-words Are there uncountably many cube-free infinite binary words? Gerry Myerson 2011-04-14T01:05:16Z 2011-08-19T05:51:58Z <p>In <a href="http://mathoverflow.net/questions/61373" rel="nofollow">http://mathoverflow.net/questions/61373</a> 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. </p> <p>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. </p> http://mathoverflow.net/questions/61615/are-there-uncountably-many-cube-free-infinite-binary-words/61622#61622 Answer by Gjergji Zaimi for Are there uncountably many cube-free infinite binary words? Gjergji Zaimi 2011-04-14T01:54:39Z 2011-04-14T12:55:17Z <p>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.</p> <p>This stronger result is proved <a href="http://arxiv.org/abs/math/0511425" rel="nofollow">here</a>. I believe all known constructions of large families of such sequences are defined by iterative mappings.</p> http://mathoverflow.net/questions/61615/are-there-uncountably-many-cube-free-infinite-binary-words/61624#61624 Answer by Mark Sapir for Are there uncountably many cube-free infinite binary words? Mark Sapir 2011-04-14T01:56:40Z 2011-04-14T01:56:40Z <p>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. </p> http://mathoverflow.net/questions/61615/are-there-uncountably-many-cube-free-infinite-binary-words/61628#61628 Answer by Steve Kass for Are there uncountably many cube-free infinite binary words? Steve Kass 2011-04-14T02:12:35Z 2011-04-14T02:12:35Z <p>In “Open Problems in Pattern Avoidance” (<a href="http://www.jstor.org/stable/2324790" rel="nofollow">here</a>), 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 <a href="http://www.jstor.org/stable/1998321" rel="nofollow">here</a>; 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.</p> http://mathoverflow.net/questions/61615/are-there-uncountably-many-cube-free-infinite-binary-words/61631#61631 Answer by Nishant Chandgotia for Are there uncountably many cube-free infinite binary words? Nishant Chandgotia 2011-04-14T02:28:12Z 2011-04-14T02:28:12Z <p>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.<br> 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}$ .</p> http://mathoverflow.net/questions/61615/are-there-uncountably-many-cube-free-infinite-binary-words/73203#73203 Answer by James Currie for Are there uncountably many cube-free infinite binary words? James Currie 2011-08-19T05:51:58Z 2011-08-19T05:51:58Z <p>I just saw and answered the earlier question, but perhaps I should repeat my post:</p> <p>Here are some deep facts relating to binary cfw's:</p> <p>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.</p> <p>2) Given any finite binary sequence, it is decidable whether it extends to an infinite binary cube-free word.</p> <p>3) The number of (finite) binary cfw's of length n grows exponentially with n.</p> <p>These results (and analogous ones for k-power free words over various alphabets) are proved in</p> <p><a href="http://dl.acm.org/citation.cfm?id=873885" rel="nofollow">http://dl.acm.org/citation.cfm?id=873885</a> and <a href="http://www.sciencedirect.com/science/article/pii/0195669895900519" rel="nofollow">http://www.sciencedirect.com/science/article/pii/0195669895900519</a></p>