Substitutions and Sturmian sequences

Question

We know that any substitution can generate sequence, for example the Fibonacci substitution:

$\sigma(0)=01, \sigma(1)=0$, then we can define a Sturmian sequence $\omega$, i.e., the fixed point of $\sigma$. ($\sigma(\omega)=\omega$). We can define an orbit space which is based on the fixed point of the substitution, for example, the Fibonacci substitution, we can define $\Omega=\overline{\{T^{n}(\omega):n\in \mathbb{N}\}}$, here $T$ is the left shift. This system is very good as it has a uniquely ergodic measure, say $\mu$. By ergodic theorem we have that $\mu([0])=\mbox{frequency of }0 $, $\mu([1])=\mbox{frequency of }1 $, where $[0],[1]$ are cylinders in $\Omega$. Also we can calculate the measure of other cylinders, such as $\mu([01]),\mu([100])$ and so on. We can use the irrational rotation to find the formula of the measure of each block.

My question is that if given other substitution, for example, $\sigma(1)=110, \sigma(0)=11$, we can also define the orbit space according to the fixed point of this substitution. Let the orbit space be $X=\overline{\{T^{n}(\tau):n\in \mathbb{N}\}}$, where $\tau$ is the fixed point of the substitution mentioned above. We can always define an invariant measure, say $\nu$, on $X$. In fact it is the limit of $\nu_n=\dfrac{1}{n}\sum_{i=1}^{n-1}\delta_{T^{i}(\tau)}$ in the weak sense. Here $\delta_{x}$ is the Dirac measure. How can we calculate the measure of cylinders, for instance, $\nu([1])=?$ $\nu([11])=?$ Can we give a formula to find the measure of all the cylinders?

Answer 1

My understanding is that there are no general techniques for answering your question, even for some specific examples. Certainly this was the case a few years ago.

A relatively well known example is the Kolakoski sequence, see http://mathworld.wolfram.com/KolakoskiSequence.html . This can be generated by a length two substitution on two symbols but the values of $\nu[1]$ and $\nu[0]$ are not known (they are conjectured to be 1/2).

I don't know much about the example, but I imagine that if you have access to the article 'What is the long range order in the Kolakoski sequence?' by Michel Dekking it would probably explain the problem quite neatly.

Answer 2

As Dan alluded to, there's in fact a quite easy way to find measures of cylinder sets for letters, which can extend to larger words with a bit of effort; I'm quite surprised it wasn't mentioned yet.

To any substitution $\tau: A \rightarrow A^*$, you can associate an $|A| \times |A|$ matrix whose $ij$ entry is the number of times that letter $j$ occurs in $\tau(i)$. For example, if $\tau$ sends $0 \mapsto 001$, $1 \mapsto 12$, $2 \mapsto 202$, then $A = \left( \begin{smallmatrix} 2 & 1 & 0\\ 0 & 1 & 1\\ 1 & 0 & 2 \end{smallmatrix} \right)$.

As long as $A$ is primitive (some power positive), then the substitution is uniquely ergodic, and the normalized left Perron eigenvector measures the frequencies of letter cylinder sets. For instance, in the previous example, the eigenvector is $(.43, .24, .33)$, so the frequency of $1$ is $.24$.

If you want longer words, it's tougher, and I don't want to write all details here (and perhaps don't know all details). But you can use a similar idea to get frequencies of cylinder sets $[\tau^i(a)]$ for letters $a$. (Briefly, I think you can consider the substitution $\tau^i$, then define a substitution $\rho$ by adding a new symbol $*$ to the alphabet, defining $\rho(c) = \tau^i(c)$ for $c \neq a$, define $\rho(a)$ to be $\tau^i(a)$ with its first letter $b$ replaced by $*$, and define $\rho(*) = \rho(b)$; then $*$ appears in sequences for the substitution subshift generated by $\rho$ only where $\tau^i(a)$ would have in the original substitution subshift. So the left eigenvector for the matrix of $\rho$ should give the frequency of $\tau^i(a)$ in the original.)

In theory, there's an issue since the linear algebra approach will only give the frequency of $\tau^i(a)$ appearing "expectedly." In other words, any sequence in the substitution subshift can be written as a concatenation of words $\tau^i(a)$, and the linear algebra will only give the frequency of these words appearing explicitly in the concatenation, and not those that "unexpectedly" occur on overlaps between two such words. For instance, above, if you wanted to find the measure of $[12]$, linear algebra would not catch occurrences of $12$ occuring within $\tau(0) \tau(2) = 001202$.

However, Mosse proved that all primitive aperiodic substitutions are uniquely decomposable, i.e. for every $i$, every sequence in the substitution subshift can be uniquely written as a concatenation of words $\tau^i(a)$. So, for large $i$, I think this problem either goes away completely or can be controlled. (Sorry for lack of details, this is just supposed to be an outline).

Then, once you have measures of all $[\tau^i(a)]$, since primitive substitutions are minimal, every word $w$ occurs within some $\tau^i(a)$, and you should be able to deduce the measure of $[w]$ accordingly.