502 – Thue sequences

This is a “hint” for exercise 3.4. An infinite 2-free 3-sequence is sometimes called a Thue sequence, since the number theorist Axel Thue was the first to study them. There are several ways of generating Thue sequences. I mention three:

  1.  One could define a map \sigma as in the case of 3-free 2-sequences. Now set \sigma(0)=012, \sigma(1)=02, and \sigma(2)=1, and once again consider the iterates \sigma^n(0).
  2. Thue’s original example was \sigma(0)=01201, \sigma(1)=020121, and \sigma(2)=0212021.
  3. Another approach consists on taking the transformation \sigma giving the 3-free 2-sequence, so \sigma(0)=01 and \sigma(1)=10. Now define q_n for n\ge1 to be the string obtained from \sigma^{2n}(0) by counting ones between consecutive zeros. For example, \sigma^2(0)=0110 so q_1=2, while \sigma^4(0)=0110100110010110, so q_2=2102012. Check that each q_n is a 3-sequence. Now check that the \sigma^{2n}(0) contain no string of the form ixixi where i\in 2 and x\in 2^{<{\mathbb N}}, and conclude from this that the strings q_n are 2-free. 

If you need extra time, you have until Friday, September 11, to work on this question.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: