22
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Thanks for asking this as a separate question, as I'd also like to know the answer (out of idle curiosity). $\endgroup$
    – Tony Huynh
    Apr 14, 2011 at 1:24
  • $\begingroup$ Thank you also for posting this. I admit that it is only now I realize the implications of your earlier comment. $\endgroup$
    – JRN
    Apr 14, 2011 at 1:54

6 Answers 6

12
$\begingroup$

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.

$\endgroup$
11
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 14, 2011 at 2:03
  • $\begingroup$ 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. $\endgroup$
    – user6976
    Apr 14, 2011 at 2:06
  • $\begingroup$ 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. $\endgroup$ Apr 14, 2011 at 2:12
  • 2
    $\begingroup$ 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. $\endgroup$
    – user6976
    Apr 14, 2011 at 2:25
  • 3
    $\begingroup$ 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. $\endgroup$ Oct 28, 2011 at 23:05
14
$\begingroup$

There are uncountably many cube-free infinite words. Indeed, consider any cube-free infinite word in 2 letters $a$ and $b$ (say, the Thue-Morse word). This word contains infinitely many occurrences of $a $. 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.

$\endgroup$
11
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Some more details would be welcome... $\endgroup$
    – YCor
    Jun 19, 2019 at 21:03
7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

I'll give the details of the abstract proof, just to emphasize that proving uncountability is much easier than proving perfectness. This is not the same as Nishant's answer, but is more or less the same as user6976's comment.


The set of cube-free words is a subshift, i.e. shift-invariant and closed in the Cantor space $\{0,1\}^{\mathbb{N}}$. Clearly it has no periodic points, since an infinite word like $uuu...$ contains in particular the word $u^3$.

Now a basic fact:

Theorem. A nonempty subshift that has no periodic points is uncountable.

Proof. Take a minimal subsystem $Y$ (a nonempty subsystem that has no proper nonempty closed subsystems), it's a classical theorem that one exists. It is easy to show that minimality is equivalent to "every forward orbit enters every open set". From this characterization it is easy to see that a minimal system is either a single periodic orbit or is perfect, namely if $\{y\} \subset Y$ is open, then $\sigma(y)$ eventually enters it, and $y$ is periodic. Now, a perfect subset of Cantor space is uncountable, so $Y$ is uncountable, and it is contained in our original subshift so that one is also uncountable. Square.

In particular the argument is not specific to cube-free words.

Corollary. Let $\alpha > 1$ and $A$ a finite alphabet. If there exists an $\alpha$-power free infinite word $x$ over alphabet $A$, then there exist uncountably many such words.

Note that this does not tell you that the set of such words is perfect. The cube-free words do form a perfect set as explained by Currie, but the proof is much more intricate.

$\endgroup$
1
  • $\begingroup$ Nice proof. It immediately generalizes to the fact that for every $k\ge 1$ and $d$, the set of $k$-power-free $d$-letter words is either empty or has continuum cardinal, and so is every shift-invariant subset thereof. $\endgroup$
    – YCor
    Sep 20, 2022 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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