Subwords of cube-free binary words

Question

I'm currently working on subwords of cube-free binary words.

A binary word is one composed of letters from a two-letter alphabet such as $\{0,1\}$. 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$. A word is cube-free if it does not contain subwords of the form $xxx$, where $x$ is a word of one or more letters.

I suspect that all sufficiently long cube-free binary words (those whose length is greater than a certain $n$) contain all the subwords $001$, $010$, $011$, $100$, $101$, and $110$. I know that $n\ge 21$ because the cube-free binary word $110011001101100110011$ has a length of 21 and does not contain the subword $010$.

Does anyone know the length of the longest cube-free binary word that does not contain all the three-letter subwords I mentioned above?

Answer 1

I wrote a recursive program to find the words of each length with no cube, avoiding a given string. If I programmed correctly, there are only $230800$ cube-free binary words of length $30$.

$001$: The longest string is of length $17$:

11010110101101100

$010$: The longest $2$ are of length $23$, the one found by Zack Wolske and it's reversal:

10011011001101100110011
11001100110110011011001

The others are equivalent to $000$ (no extra restriction), $001$, or $010$. So, any cube-free binary word of length $24$ or longer has all possible subwords of length $3$.

---

That was easy, so I'll do the same for words of length $4$, too:

$0010$: There are $76604$ cube-free binary words of length $40$ avoiding $0010$, and I would guess that the entropy per digit is positive, that there is some $a \gt 0, c\gt 1$ so that there are about $a c^n$ cube-free binary strings of length $n$ which avoid $0010$.

$0011$: There are $94238$ cube-free binary words of length $40$ avoiding $0011$.

$0101$: There are $110378$ cube-free binary words of length $40$ avoiding $0101$.

$0110$: The longest $3$ are length $17$. Avoiding $0110$ is not much different from avoiding $011$.

00101001010010011
11001001010010011
11001001010010100

---

What about pairs of words to avoid? Although there are long cube-free binary words avoiding either $0011$ or $0101$, the longest words which avoid both have length $14$:

01101101001001
10110110010010

The number of pairs to consider is larger than the number of pairs from $\lbrace 0010, 0011, 0101 \rbrace$. Avoiding both $0011$ and $0101$ is different from avoiding $0011$ and $1010$. The latter pair is avoided by $1310$ binary cube-free words of length $40$.

Here are some counts of cube-free binary words of length $40$ which avoid pairs of words:

        0010    0011    0101
----------------------------  
0010   76604       0    4376
0011       0   94238       0
0100    3721     994       0
0101    4376       0  110378 
1010       0    1310    2600
1011       0       0    4376
1100     994     730    1310
1101       0     994       0

It might be interesting if some of these turn out to have polynomial growth instead of exponential. However, my guess is that they still have exponential growth, with a base about $\sqrt[10]{2}$ for the pair $0011$ and $1100$.

Answer 2

The word $1001$-$1001$-$101$-$1001$-$101$-$1001$-$1$ (separated to show how it was constructed and to ease reading) is cube-free and does not contain the subword $010$.

Perhaps you can prove that no 24 letter word begins with a $1$ and avoids $010$ by arguing about possible arrangements of the words $1001$ and $101$.

Answer 3

Try this: start with the infinite Thue-Morse word $TM = 0110100110010110...$ which is known to be cubefree and make the following transformations:

$0 \Rightarrow x0$

$1 \Rightarrow x1$

This gives the the infinite word:

$TM^\prime = x0x1x1x0x1x0x0x1x1x0x0x1x0x1x1x0x...$

Next make the following transformation on $TM^\prime$:

$x\Rightarrow 11$

$0\Rightarrow 0$

$1\Rightarrow 00$

This gives the following infinite word:

$C = 110110011001101100110110110011...$

Clearly $C$ does not contain the subword $010$, and unless I overlooked something in my analysis, the cube-freeness of $TM$ implies $C$ is also cube-free, which would mean there is no upper bound to the size of cube-free binary strings not containing all six of the given strings.

(Incidentally, the composition of these two transformations is equivalent to performing the transformation $0\Rightarrow 110$, $1\Rightarrow 1100$ on $TM$ to get $C$, but I figured the intermediate step makes it a bit clearer, to me at least, why $C$ should be cube-free).

If anyone sees any flaw in the reasoning that $C$ is cube-free, please do point it out.

Answer 4

I may lose my own bet. By hand I computed less than 50 binary words of length 10 that start with 0. A little less than 40 of them have 4 or 5 of the subwords. This should be easily handled by computer, and with some patience can be completed by hand. My guess is that 21 is close to the maximum, and that there will be less than 10 words of maximal length.

EDIT 2012.09.20: Here is more detail on my pseudo elegant idea mentioned in comments to the question.

Assume we are trying to make a cubefree word which avoids 011. Then after an initial block of at most two ones, our word has a subword matching the regexp ((0|00)1)*, where the subpattern repeats more than 3 times if we are getting a long such word.

Then 001001001 and 010010010 and 010101 and 101010 are other words to be avoided, so the pattern has to alternate between 00101 and 01001, but also cannot contain that pattern three times in a row. So it can have at most 5 occurrences of 00 , one of which appears in 10100101, and two occurrences of 101, otherwise a cube will appear. So the regexp repetition will happen at most 7 times, by my mental (mis?)calculation.

A similar argument appears for avoiding 011, and also avoiding 010, in which case 11 is the subpattern replacing 1 in the regexp above. A similar case for 0 occurs in the 0-1 reversal of letters for the remaining words.

By this analysis, I get 28 as an upper bound, with candidate word 1100110011011001101100110011. Unfortunately that has a cube in it, so the real bound is likely to be lower.

Again, this should be doable by hand, but Joel should verify it by computer, or deflate the above argument. END EDIT 2012.09.20

Gerhard "Just Keep Adding Another Digit" Paseman, 2012.09.19