Does the Thue-Morse sequence form a Sturmian Word?

487 Views Asked by At

Does the Thue-Morse sequence form a Sturmian Word?

The Thue-Morse sequence 011010011001001..., formed by appending the negation of the existing string, yields the Prouhet-Thue-Morse constant when expressed as a decimal. Said constant has been proven to yield a transcendental number.

Sturmian words / sequences are cutting sequences with irrational slopes; the slope of the Thue-Morse sequence would seem to be irrational (being precisely the Prouhet-Thue-Morse constant), but I'm not sufficiently confident of my understanding of cutting sequences to know if it satisfies that condition.

1

There are 1 best solutions below

0
On BEST ANSWER

The answer is no and there are several ways to show this. Probably the easiest way is to look at the complexity of the sequences. The complexity $p_w$ of a sequence $w$ is given by $$p_w(n)=\#\mathcal{L}_n(w)$$ where $\mathcal{L}_n(w)$ is the set of all length-$n$ subwords appearing in $w$, and $\#$ is the cardinality of the set.

It can be shown that Sturmian words are precisely those words $w$ on two letters which satisfy $$p_w(n)=n+1$$ for all $n\geq 1$. In fact, this is sometimes taken to be the definition of Sturmian words.

A quick check of a small part of the Thue-Morse sequence $w_{TM}$ shows us that $p_{w_{TM}}(2)=\#\{00,01,10,11\}=4$ which contradicts the possibility of $w_{TM}$ being Sturmian.

Another easy way to check this would be to note that in a Sturmian sequence, one of the symbols is always isolated (corresponding to the smaller of the components of the vector which defines our cutting sequence), and it is clear that $w_{TM}$ has neither $0$ nor $1$ isolated.

It's also easy to show that Sturmian sequences are balanced (in fact this is a characterisation of Sturmian sequences). A balanced sequence is one for which the abelianised difference of any two length-$n$ subwords of the sequence has entries at most of absolute value $1$. For instance the abelianised difference of the word $aababab$ and $aabaaba$ is $(-1,1)$ because the first word has one more $a$, and the second word has one more $b$. Whereas Thue-Morse is not balanced, as we have the two-letter words $00$ and $11$ whose abelianised difference is $(-2,2)$ with absolute value of entries both being $2$.

Another very simple way would be to note that the normalised right Perron-Frobenius eigenvector of the Thue-Morse substitution matrix is $(1/2,1/2)^T$ and so the frequency of $0$s and $1$s are both $1/2$. Any aperiodic Sturmian sequence has irrational letter frequencies and so, as the Thue-Morse sequence is aperiodic, it cannot be Sturmian.


Sledgehammers

Here are a couple of ways using techniques that are far more powerful than required:

  • Another way would be to calculate the cohomologies of the suspension-spaces $\Omega$ of the corresponding subshifts which would be isomorphic if $w_{TM}$ was Sturmian - Sturmian subshifts always have $\check{H}^1(\Omega_{sturm})\cong\mathbb{Z}^2$, whereas the Thue-Morse subshift has $\check{H}^1(\Omega_{TM})\cong\mathbb{Z}\oplus \mathbb{Z}[\frac{1}{2}]$.

  • Yet another way would be to consider the dynamical or diffraction spectrum of the Thue-Morse word, which is not pure point. As Sturmian words come from cutting sequences, like you say, they do have pure point spectrum.