20
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – JRN
    Apr 16, 2011 at 15:34
  • $\begingroup$ 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. $\endgroup$
    – JRN
    May 27, 2012 at 15:19

4 Answers 4

16
$\begingroup$

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$ @JoelReyesNoche and OP: w.r.t. (3) - Isn't the number of finite binary cfw of length $n$ just twice the $(n+1)$st Fibonacci number? $\endgroup$ Jan 9, 2015 at 8:40
  • $\begingroup$ @BenjaminDickman, the last time I looked, no exact formula for the number of finite binary cfw has been found, only bounds. The number of cubefree words of length n on two letters: oeis.org/A028445 $\endgroup$
    – JRN
    Jan 9, 2015 at 12:45
  • $\begingroup$ @JoelReyesNoche Ah, I see now that $x$ can be one or more letters; my erroneous count is for the restriction $|x| = 1$. Thanks for the clarification. $\endgroup$ Jan 9, 2015 at 14:41
20
$\begingroup$

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.

$\endgroup$
0
14
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ Doesn't your $\omega$ contain the cube of $x=01$? $\endgroup$
    – Tony Huynh
    Apr 12, 2011 at 10:27
  • 1
    $\begingroup$ 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\}^*$! $\endgroup$ Apr 12, 2011 at 10:31
  • 1
    $\begingroup$ This construction gives a countable infinity of cube-free words. I would imagine there would be an uncountable infinity. $\endgroup$ Apr 12, 2011 at 13:00
  • 2
    $\begingroup$ @Tony: Wow. I didn't think of that. Thanks! $\endgroup$
    – JRN
    Apr 12, 2011 at 13:15
  • 2
    $\begingroup$ Gerry asks a question related to his comment above at mathoverflow.net/questions/61615 $\endgroup$
    – JRN
    Apr 14, 2011 at 1:56
6
$\begingroup$

Lemma: Someone only able to speak an infinite cubefree word can convey information at least $1/24$ of the speed of an ordinary person able to speak an arbitrary binary sequence.

Proof: Consider the following period-$12$ sequence over the alphabet $\{ 0, 1, ?\}$:

$S = (001?010?1011)^{\infty}$

Now suppose $T$ is a sequence derived from $S$ by replacing each $?$ with a $0$ or $1$.

  • $T$ clearly has no words of the form $xxx$ for a single digit $x$.

If we take alternate digits in $T$, we obtain $(010011)^{\infty}$. The only cubes in this sequence have length a multiple of $6$, hence:

  • If $T$ contains a word of the form $WWW$, where $W$ has even length, then $W$ has length divisible by 12.

  • Also, $T$ contains a word of the form $WWW$ where $W$ has length $3$ if and only if two question marks in the same dodecad $(001?010?1011)$ are both zero. Assert that this will not happen.

  • If $T$ contains a word of the form $WWW$, where $W$ has length divisible by $3$, then $W$ has length divisible by $12$.

Hence we are only worried about words of length coprime to or divisible by $12$.

  • If the length of $W$ is $\pm 1 \mod 12$, then the existence of $WWW$ is ruled out by the proof of the non-existence of $xxx$.

  • Similarly, it is easy to observe that there are none of length $\pm 5 \mod 12$.

So any word of the form $WWW$ in $T$ requires $W$ to have length divisible by $12$.


Now begin with any tripleless sequence over $\{A, B\}$ (such as the Thue-Morse sequence) and apply the substitution rules:

$A \mapsto (001001011011)$

$B \mapsto (0011010?1011)$

Then we obtain an infinite word over $\{0, 1, ?\}$ such that:

  • Every replacement of the question marks with digits yields an infinite cubefree word.
  • Every icositetrad contains one question mark.

The result follows.

$\endgroup$
2
  • $\begingroup$ Oops, $w$ should be $x$ (a single digit). $\endgroup$ Jan 9, 2015 at 22:15
  • $\begingroup$ This is a very nice result. Are there analogous results for other power-free words? $\endgroup$
    – JRN
    Jan 12, 2015 at 0:40

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.