Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
It should be resolvable through brute force. Have you done a computer enumeration? Gerhard "Ask Me About System Design" Paseman, 2012.09.18 –  Gerhard Paseman Sep 19 '12 at 14:16
    
In fact, the number of cube free binary words of lrngth n is O(F_n), or about twice or four times the nth Fibonacci number. With judicious pruning, you can compute the words not containing the set by hand. Gerhard "I Might Try It Myself" Paseman, 2012.09.19 –  Gerhard Paseman Sep 19 '12 at 14:37
    
Just computing by hand, I get less than 30 words of length 8 which begin with 0. All of these have at least 3 of the subwords of length 3, and most have 4,5, or all 6 of them. I bet by the time you get to length 12, there will be very few prefixes to check. Gerhard "I Almost Did It Myself" Paseman, 2012.09.19 –  Gerhard Paseman Sep 19 '12 at 17:04
    
Here is a pseudo-elegant suggestion. Suppose you look at cube free words that avoid 010. Then all blocks after the initial block will be 0, 00, or 11. Cube-free words will then have a suffix having mostly 11's. But there are only finitely many ways to avoid cubes with this restriction. Argue similarly for the other five subwords. Gerhard "I'll Take Working Over Elegant" Paseman, 2012.09.19 –  Gerhard Paseman Sep 19 '12 at 23:01
    
Note that cube-free binary words do not necessarily have equal letter frequencies (although some, like the (infinite) Thue-Morse word, do). See, for example, section 6.1 of a paper by Grimm and Heuer (mdpi.com/1099-4300/10/4/590), where they empirically found that the frequency of a letter in a binary cube-free word (of up to length 80) is between 0.4 and 0.6. –  Joel Reyes Noche Sep 20 '12 at 0:07
show 2 more comments

4 Answers 4

up vote 4 down vote accepted

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

share|improve this answer
    
My counts of cube-free words agree with oeis.org/A028445 which oddly only has the counts up to length $28$. –  Douglas Zare Sep 20 '12 at 15:26
    
The number of cubefree words of length 30 is less than twice the 29th Fibonacci number, which is less than 10*7^6, so it is believable. Gerhard "Ask Me About Crude Estimates" Paseman, 2012.09.20 –  Gerhard Paseman Sep 20 '12 at 15:45
    
The number of cube-free binary words of length $n$, for $1\le n\le 80$ can be found in table 1 (page 600) of mdpi.com/1099-4300/10/4/590. Your figure of 230800 words of length 30 agrees with theirs. –  Joel Reyes Noche Sep 21 '12 at 0:02
    
Thanks! This answers my question. –  Joel Reyes Noche Sep 21 '12 at 0:19
    
I observed that by the time I got to 12 characters, most words had 5 of the 6 allowable triplets. It might be interesting to see the stats on length vs number of k-length subwords covered. Gerhard "Ask Me About System Design" Paseman, 2012.09.21 –  Gerhard Paseman Sep 21 '12 at 22:01
add comment

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

share|improve this answer
    
Thanks! So now we know that $n\ge 23$. –  Joel Reyes Noche Sep 20 '12 at 12:27
add comment

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.

share|improve this answer
    
Also, although I don't have access to it, looking at the abstract of the paper by Richomme & Wlazinski cited in Amy Glen's answer to your other question (mathoverflow.net/questions/61373/), it seems that paper might provide examples of transforms to $TM$ which avoid one or more of your words (maybe even the transform I described above) –  ARupinski Sep 20 '12 at 3:29
5  
Your word contains (0110)^3 starting at the third letter. –  Evan Jenkins Sep 20 '12 at 3:30
    
Ahh, so it does; thanks for noticing that oversight. So much for trying to do math at late-night. –  ARupinski Sep 20 '12 at 22:21
    
Thanks for the effort, anyway. (+1 for effort!) –  Joel Reyes Noche Sep 21 '12 at 0:06
add comment

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

share|improve this answer
    
Thanks. I'll try a brute-force method. I'm just curious if someone has done a more elegant solution. –  Joel Reyes Noche Sep 19 '12 at 22:19
    
(After the edit) Thank you for the non-brute-force (i.e., more elegant) insight. –  Joel Reyes Noche Sep 21 '12 at 0:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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