Sturmian substitutions, cutting paths and their projections

Sierk Rosema

Universiteit Leiden, Netherlands

We start with some notation and definitions. A word is a function $u$ from a finite or infinite block of integers $B$ to $\{0,1\}$. We call a word $u$ finite when $B$ is finite and infinite otherwise. If $k\in B$ and $u(k)=a$ we say $u$ has the letter $a$ at position $k$. If a word $u$ is finite, we denote by $\vert u\vert _a$ the number of occurrences of the letter $a$ in $u$.

A word $u$ is called balanced if $\vert\vert v\vert _0-\vert w\vert _0\vert<2$ for all subwords $v,w$ of equal length of $u$. A finite word $u$ is called strongly balanced if $u^2$ is balanced. Here $u^2$ is the concatenation of $u$ with $u$. An example of a strongly balanced word is $u=01001$. An infinite word is Sturmian if it is balanced and not ultimately periodic.

A substitution $\sigma$ is an application from $\{0,1\}$ to the set of finite words. It extends to a morphism by concatenation, that is, $\sigma(uv)=\sigma(u)\sigma(v)$. It also extends in a natural way to a map from infinite words to infinite words. We call $M_\sigma:=\left(\begin{array}{cc}\vert\sigma(0)\vert _0&\vert\sigma(0)\vert _1 Vert\sigma(1)\vert _0&\vert\sigma(1)\vert _1\end{array}\right)$ the incidence matrix corresponding to the substitution $\sigma$. A fixed point of a substitution $\sigma$ is an infinite word $u$ with $\sigma(u)=u$.

We call a substitution $\sigma$ Sturmian if $\sigma$ maps every Sturmian word to a Sturmian word. An example of a Sturmian substitution is

$$\sigma:\left\{\begin{array}{ccl}0&\rightarrow&01001\\ 1&\rightarrow&010010101001.\end{array}\right.$$

Now we will explain how to form a new word $v$ from a strongly balanced word $u$. If $u=u(0)u(1)\ldots u(n)$ is a strongly balanced word with $\gcd(\vert u_n\vert _0,\vert u_n\vert 1)=1$, we define the cutting points corresponding to $u$ by $p_i=(\vert u(0)\ldots u(i-1)\vert _0,\vert u(0)\ldots u(i-1)\vert _1)$. These cutting points approximate a line piece between the origin and $p_{n+1}$ quite well. We can project the cutting points parallel to this line piece, onto the $y$-axis. We call $g$ the value such that the projection of the $g$th cutting point has the smallest positive $y$-coordinate. Next we replace the projection of each cutting point $p_i$ with 0 or 1, depending on whether $i$ is smaller than $g$ or not, and form a word $v$ by writing down the zeros and ones in the order that they appear on the $y$-axis, from the top down.

Our main result is the following. Let $\sigma$ be a Sturmian substitution that has incidence matrix with determinant 1 and a fixpoint starting with 0. Let $u_n=\sigma^n(0)$, and $v_n$ the word constructed from $u_n$ in the way described above. Then there exists a Sturmian substitution $\tau$ such that $v_n=\tau(v_{n-1})$ for every $n>1$.