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)$?

  • $\begingroup$ It appears you posted on Math.SE and got feedback about how to improve your question. You also got an answer there. I'm not sure why it has been deleted on Math.SE. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Commented Oct 3, 2020 at 6:09

1 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$).

  • $\begingroup$ It is the modulo operation. I don't that you need me to try out an example. $\endgroup$ Commented Oct 3, 2020 at 12:12
  • $\begingroup$ It extracts the third letter (indices start at $0$). $\endgroup$ Commented Oct 3, 2020 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.