2020-10-16 MATH 3600 Thue Morse Kolakoski

581 days ago by calkin

We will consider some binary and related sequences.

1. The Thue-Morse sequence.

2. The Kolakoski sequence.

The Thue-Morse sequence can be defined in several different ways. 

(i) Start with 0. 

Find the current sequence's binary complement and append it to the current sequence.

0 -> 01 -> 0110 -> 01101001 -> 0110100110010110

(ii) second construction:  Start with 0

replace every occurence of 0 with 01, every occurence of 1 with 10.

We end up with the same sequence!

(iii) Third construction.  List the non-negative integers in binary, and count the number of 1's (mod 2).

0  ->  0

1  ->  1

10 -> 1

11 -> 0

100-> 1

101 -> 0

110 -> 0

111 -> 1

What is special about the Thue-Morse sequence?  Do we ever see three consecutive 0's? Or 1's?

Suppose we did: ask the question: where does the first string of three consecutive 0's or 1's occur?

The three consecutive bits would have to cross a $2^n$ boundary, but since we always have two different consecutive bits at the boundary, this can't happen!  So, we never see three consecutive 0's or three consecutive 1's.

Similarly for each of the "words" w of length 2, we can never see three repeated w's.  Clearly can't see (00)(00)(00) or (11)(11)(11) or (01)(01)(01) or (10)(10)(10).  In fact, it is a theorem that for any word w of length k, we never see three consecutive copies of w. We call the sequence "cube-free".

Can we check this computationally? 


(i) Compute the first $2^k$ terms of the Thue-Morse sequence

(ii) Write code to check if a sequence has cubes.   Read a substring of a sequence and check whether that substring is a cube.

Separate question: given a binary sequence $\Sigma$, which words appear as a consecutive string in the sequence?  In the Thue-Morse sequence, of the 16 possible binary words of length 4, only 0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100, 1101, for a total of 10 words that appear.

Task: how many cube-free words of length $j$ are there?

Can you compute them?

What proportion of cube-free words appear as substrings of the Thue-Morse sequence? Do they all appear or are there some that are missing? 


A puzzle:  what is going on with the following sequence?











Testing whether a string is cube-free. 

Need a function is_a_cube(L), which takes a list L as input, checks that its length is a multiple of 3, and checks whether L is a cube.

Need a function is_cube_free(S), which takes a list, and checks for every j, l with j+3l $\leq$ n if the string 

S[j: j+3*l] is a cube.  If it ever is, is_cube_free(S) returns False, otherwise it returns True.

You should run your function on the Thue Morse sequence and the Kolakoski sequence to check that they are both cube-free. Also create some non-cube-free sequences and check that it tells you they are not cube-free.

It might be helpful as well to have the function print out or return the position and length of a cube found, and perhaps to print out the string which is cubed.