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?



Subwords of cube-free binary words
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$.


