Computing morphic word produced by uniform morphism

Question

Let $\Sigma = \{a,b,c\}$, and consider the function $f\colon \Sigma \to \Sigma^*$ given by $f(a) = abc$, $f(b) = bac$, and $f(c) = cba$. We can extend $f$ to $\Sigma^*$ in the obvious way. Since $f(a)$ starts with $a$, it can be shown inductively that $f^{(n-1)}(a)$ is a prefix of $f^{(n)}(a)$ for every $n$, where $f^{(n)}(a)$ is the result of applying $f$ on $a$ for $n$ times: \begin{align} &f^{(0)}(a) = a \\ &f^{(1)}(a) = abc \\ &f^{(2)}(a) = abcbaccba \end{align} and so on. Hence the sequence $f^{(n)}(a)$ converges to an infinite limit word $f^{(\infty)}(a)$.

How do I compute the $i$'th symbol of $f^{(\infty)}(a)$?

Answer 1

Denote $f^{(\infty)}(a)$ by $w$. Thus $f(w) = w$. Let $w_0,w_1,w_2,\ldots \in \{a,b,c\}$ be the individual symbols of $w$. The crucial observation is that if $n = 3m + r$ for $r \in \{0,1,2\}$ then $$ w_n = f(w_m)_r. $$ Indeed, since $w = f(w)$, we have $$ w_0 w_1 w_2 w_3 w_4 w_5 w_6 w_7 w_8 \ldots = f(w_0 w_1 w_2 \ldots) = f(w_0) f(w_1) f(w_2) \ldots, $$ from which this formula can be recovered.

This gives a very simple recursive formula for computing $w_n$: $$ w_n = f(w_{\lfloor n/3 \rfloor})_{n \bmod 3}, $$ with base case $w_0 = a$.

A similar approach works for every morphic word produced by a uniform morphism (one in which $|f(\sigma)|$ is the same for all $\sigma \in \Sigma$).