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