Are there references for the properties of words formed in finite groups using L-systems? (In particular, the algae L-system.)

Question

Let $G$ be a (finite) group, and $a, b \in G$ be any two elements. Consider the sequence defined by \begin{eqnarray*} s_0 &=& a, \\ s_1 &=& b, \text{and} \\ s_{n+2} &=& s_{n+1} s_{n} \text{ for $n \geq 0$}. \end{eqnarray*} This sequence is what we get when replace the letters in the algae L-system (cf: https://en.wikipedia.org/wiki/L-system#Example_1:_Algae) with the two elements of our group. As $G$ is finite, there are finitely many pairs $(s_{n+1}, s_{n})$ and hence that the sequence will eventually start repeating. Do we know more about this sequence $(s_n)$? Like, when is it periodic?

Answer 1

Here are some observations about the sequence when $a$ and $b$ commute.

If $a=e$, then $s_n=b^{F_n}$, where $F_n$ is the $n$th Fibonacci number. Let $|b|$ denote the order of $b$; we are interested in Fibonacci numbers modulo $|b|$. The Fibonacci numbers are periodic modulo any finite number, so the sequence $s_n$ is periodic. The period is the Pisano period $\pi(|b|)$.

If $a$ commutes with $b$, then $s_n=b^{F_n}a^{F_{n-1}}$ (with the natural convention that $F_{-1}=1$). Therefore $s_n$ is a (commutative) product of two periodic sequences and therefore periodic.

If $a$ and $b$ are powers of the same element, we get again the Fibonacci numbers but with different initial conditions than $F_0=0$ and $F_1=1$. Again, we get periodicity.

Answer 2

For that system, it is always periodic, in other words it starts repeating right away. The function $(a,b) \mapsto (b, ba)$ is invertible: we have $(c^{-1} d,c) \mapsto (c,d)$. So if iterating this function starting from some point eventually starts repeating, it must have been repeating the whole time.

More generally, consider any word $w(x,y)$ in the free generators $x$ and $y$. By the same argument, if $\langle y, w(x,y) \rangle$ is the entire free group $F = \langle x,y \rangle$, then the corresponding sequence in a finite group will be always be periodic.

The other direction also holds. If a finite set $S$ generates a proper subgroup $K < F$, there is some finite quotient $\tilde F$ in which $\tilde S$ generates a proper subgroup of $\tilde F$. This can be seen by taking the Schreier graph of the action of $F$ on the cosets of $K$, cutting out a large ball, and linking up the cut edges to each other arbitrarily. If we apply this to $S = \{y, w(x,y)\}$, we get a sequence in $\tilde F$ which starts out $a, b, w(a,b)$. But $b$ and $w(a,b)$ generate a strictly smaller subgroup than $a$ and $b$, so $a$ will never again appear in the sequence.

Using Nielsen reduction, it's fairly easy to write down the condition for when $y$ and $w(x,y)$ actually generate all of $\langle x, y \rangle$.

Answer 3

You may start with the PhD thesis of P. P. Campbell

http://www-circa.mcs.st-and.ac.uk/Theses/ppcphd.pdf