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.


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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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