Being Cayley automatic is closed under taking
wreath product with virtually cyclic groups

Since $G$ is Cayley automatic, there exists a finite symmetric generating set $S_{0}$ for $G$, an alphabet $\Lambda_{0}$, a regular language $L_{0}\subseteq\Lambda_{0}^{*}$, a bijection $\psi_{0}\colon L_{0}\to G$, and a 2-tape automaton $\texttt{M}_{s}$ for each $s\in S_{0}$ with accepted language

Without loss of generality assume $\psi_{0}(\varepsilon)=1_{G}$.

Let $H$ be a finite extension of its cyclic subgroup $\mathbb{Z}=\langle t\rangle$ of index $m+1$, and denote by $\langle t\rangle x_{0},\langle t\rangle x_{1},\dots,\langle t\rangle x_{m}$ the distinct right cosets of $\mathbb{Z}$, where $x_{0}=1_{H}$. Let

then $S=S_{0}\cup T$ is a symmetric generating set for $G\wr H$. We identify a particular spanning tree $\mathcal{S}$ of the Cayley graph $\Gamma(H,T)$ which consists of a “spine” corresponding to $\langle t\rangle$, and at each vertex $t^{k}$ there are $m$ “spokes” terminating at the $m$ vertices $t^{k}x_{j}$ of $H$, for $k\in\mathbb{Z}$ and $1\leqslant j\leqslant m$, as in Figure 1.

As a concrete example, consider the infinite dihedral group

In this case we can take $t=ab,x_{1}=a$ and $\mathcal{S}=\Gamma(D_{\infty},T)$, as shown in Figure 2.

We borrow some terminology from the lamplighter groups $\mathbb{Z}_{n}\wr\mathbb{Z}$ to describe elements of $G\wr H$. An element $v\in G\wr H$ can be thought of in two equivalent ways:

1. (1)

   algebraically, as an element $(\gamma,h)$ where $\gamma\in\bigoplus_{k\in H}(G)_{k}$ has finitely many nontrivial entries and $h\in H$.

2. (2)

   geometrically, as a copy of $\mathcal{S}$ (or $\Gamma(H,T)$) where each vertex is marked by some element of $G$, with all but finitely many vertices marked by $1_{G}$, and the vertex $h$ of $\mathcal{S}$ is also marked with a pointer indicating the final position of the “lamplighter”. We refer to this marking as a configuration of ${\mathcal{S}}$.

Write $v=(\gamma,h)$ where $\gamma\in\bigoplus_{h_{i}\in H}(G)_{h_{i}}$ and $h\in H$. Since every element $h$ of $H$ can be written uniquely as $h=t^{k}x_{q}$ for some $k\in\mathbb{Z}$ and $0\leqslant q\leqslant m$, the map $\xi:H\rightarrow\mathbb{Z}$ defined by $\xi(t^{k}x_{q})=k$ is well defined. Then the vertex corresponding to $h\in H$ is an endpoint of a spoke attached to the vertex $t^{\xi(h)}$. For $v=(\gamma,h)$ with $\gamma$ as above, let

1. (1)

   $k_{*}=\xi(h)$,

2. (2)

   $k_{1}=\min\{0,\xi(h_{i})\mid(g)_{h_{i}}\in\gamma,(g)_{h_{i}}\neq 1_{G}\}$, and

3. (3)

   $k_{2}=\max\{0,\xi(h_{i})\mid(g)_{h_{i}}\in\gamma,(g)_{h_{i}}\neq 1_{G}\}$.

Additionally, let $m_{1}=\min(k_{*},k_{1})$ and $m_{2}=\max(k_{*},k_{2})$. Define the integer support of $v$, denoted $\mathrm{isupp}(v)$, to be the interval $[m_{1},m_{2}]$. The left endpoint of the integer support is the smallest $k$ so that either

1. (1)

   $v$ has a nontrivial entry among the copies of $\Gamma(G,S_{0})$ attached to the spine at the vertex $t^{k}x_{i}$ for some $0\leqslant i\leqslant m$,

2. (2)

   the final position of the lamplighter is $t^{k}x_{i}$ for some $0\leqslant i\leqslant m$, or

3. (3)

   all of $k_{*}$ and $\xi(h_{i})$ are positive, that is, the lamplighter is never in a position along the spine with negative index, so $m_{1}=0$ denotes the starting position of the lamplighter.

The right endpoint of the integer support is defined analogously, where the $0$ is included in the definition of $k_{2}$ to account for the possibility that $k_{*}$ and all the $\xi(h_{i})$ are negative.

To define our normal form, we mimic the standard “left-first” representation of elements of the lamplighter group $\mathbb{Z}_{n}\wr\mathbb{Z}$ (cf.  [4]). Given $v=(\gamma,h)\in G\wr H$, we describe a path traversed by the lamplighter from the vertex $1_{H}$ in ${\mathcal{S}}$ to its final vertex $h\in{\mathcal{S}}$. If $m_{1}<0$, the lamplighter first moves left along the spine of ${\mathcal{S}}$ to the vertex labeled $t^{m_{1}}$, and marks it with a possibly trivial element of $G$. The lamplighter then visits $t^{m_{1}}x_{1}$ and marks it with a possibly trivial element of $G$ and returns to $t^{m_{1}}$. This procedure is repeated for the vertices $t^{m_{1}}x_{2},\cdots,t^{m_{1}}x_{m}$. The lamplighter then proceeds to the vertex corresponding to $t^{m_{1}+1}$ and repeats the process of visiting the vertex at the end of each spoke in order and marking it with a possibly trivial element of $G$. This continues until the lamplighter reaches the vertex corresponding to $t^{m_{2}}$, where the process is repeated one last time. If $m_{1}=0$, the lamplighter begins the process of marking the vertices with possibly trivial elements of $G$ at $1_{H}\in{\mathcal{S}}$, and then visits the spokes as described above, until it reaches the vertex labeled $t^{m_{2}}$ and marks the vertices $t^{m_{2}}x_{j}$ for $0\leqslant j\leqslant m$ with possibly trivial elements of $G$.

We refer to the subpath which starts at the vertex $t^{m_{1}}$ and ends at the vertex $t^{m_{2}}$ after having marked the vertices $t^{i}x_{j}$ for $m_{1}\leqslant i\leqslant m_{2},0\leqslant j\leqslant m$ with possibly trivial elements of $G$ as the positive path, because when written as a word in the group generators, the exponents of $t$ are all positive. See Figure 3 for an example of a configuration with integer support $[-2,1]$ where the positive path is marked.

Upon completing the positive path, one of two things will occur. It may be that the lamplighter is in its final position, and the path simply ends. If not, the lamplighter moves to its final position via a subpath of the form $t^{k}$ or $t^{k}x_{q}$ where $k\in\mathbb{Z},k\leqslant 0$. Note that since $m_{2}$, the right endpoint of $\mathrm{isupp}(v)$, is the maximum of $k_{2}$ and $k_{*}$, the lamplighter will never be in a position along $\mathbb{Z}=\langle t\rangle$ to the right of $m_{2}$, so the exponent $k$ is non-positive.

As the lamplighter travels along its positive path, we will wish to indicate two special positions: the first time the lamplighter is at the vertex corresponding to $1_{H}=t^{0}$, and the first time the lamplighter is at the vertex which will be its final position. The integer support and the positive path are defined so that these are unique positions along the positive path.

The normal form for the Cayley automatic structure on $G\wr H$ will be constructed in stages. We first define a normal form $\mathcal{N}_{0}\subseteq(\Lambda_{0}\cup T)^{*}$ for elements of $G\wr H$ as follows. Given $v\in G\wr H$ with $\mathrm{isupp}(v)=[m_{1},m_{2}]$, the above description allows us to uniquely represent $v$ as a word either of the form

where $n,j,q,s\in\mathbb{Z},\ j\leqslant 0$, $s\geqslant 1,\ 0\leqslant q\leqslant m$, $m_{1}+(s-1)=m_{2}$ and

with $v_{\varsigma,t}\in L_{0}$. If $m_{1}=k_{*}$ then we allow $v_{1}$ to be trivial, otherwise $v_{1}$ must be nontrivial. If $m_{2}=k_{*}$ we allow $v_{\varsigma}$ to be trivial, otherwise $v_{\varsigma}$ must be nontrivial. Each word $v_{\varsigma}$ encodes a sequence of words $(v_{\varsigma,0},\dots,v_{\varsigma,m})\in L_{0}^{m+1}$ with $\psi_{0}(v_{\varsigma,0})$ labeling the vertex at position $t^{m_{1}+\varsigma-1}$ in $\mathcal{S}$ and $\psi_{0}(v_{\varsigma,i})$ labeling the end of the spoke at position $t^{m_{1}+\varsigma-1}x_{i}$ for $1\leqslant i\leqslant m$. Note that in Equation (1), the $v_{\varsigma}$ are separated by instances of $t$ as the lamplighter moves along the positive path. Let ${\mathcal{N}}_{0}\subseteq(\Lambda_{0}\cup T)^{*}$ denote the set of words of this form.

For example, the element in Figure 3 has $\mathcal{N}_{0}$ normal form

where $\psi_{0}(v_{1,2})=g_{1},\psi_{0}(v_{1,4})=g_{2}$, $\psi_{0}(v_{4,0})=g_{3}$, $\psi_{0}(v_{4,1})=g_{4}$, and in all other cases, $v_{i,j}=\varepsilon$ where $\psi_{0}(\varepsilon)=1_{G}$.

Next, we insert special symbols into the words in $\mathcal{N}_{0}$ to obtain the intermediate language $\mathcal{N}_{1}$.

Let $\Lambda_{1}=\Lambda_{0}\cup T\cup\{B,C,B_{0},C_{*}\}$ and $\Lambda=\Lambda_{0}\cup\{B,C,B_{0},C_{*}\}$. Let $v=(\gamma,h)\in G\wr H$ be written in the form of Equation (1). Notice that all terms of the form $v_{\varsigma}$ are part of the positive path. With $v_{\varsigma}$ as in Equation (2), before each $v_{\varsigma,j}$ we place the symbol $C$, with one exception. If $v_{\varsigma,j}$ is the label of the vertex $h$ of ${\mathcal{S}}$ which is the final position of the lamplighter, then precede $v_{\varsigma,j}$ by the symbol $C_{*}$. Before each term $v_{\varsigma}$ we place the symbol $B$, with one exception. If $m_{1}+\varsigma-1=0$ we place the symbol $B_{0}$ in front of $v_{\varsigma}$, indicating the unique position along the positive path where the lamplighter is at the vertex $1_{H}\in{\mathcal{S}}$.

Let ${\mathcal{N}}_{1}\subseteq\Lambda_{1}^{*}$ denote the set of all words in ${\mathcal{N}_{0}}$ where the symbols $\{B,C,B_{0},C_{*}\}$ have been inserted as described. The word in $\mathcal{N}_{1}$ for the element in Figure 3 is then

To obtain the final normal form which will be the basis of the Cayley automatic structure for $G\wr H$, let ${\mathcal{N}}\subseteq\Lambda^{*}$ denote the set of words in ${\mathcal{N}}_{1}$ where all instances of the letters $t,x_{1},\dots,x_{m},t^{-1},x_{1}^{-1},\dots,x_{m}^{-1}$ from the set $T$ are removed. The word in $\mathcal{N}$ for the element in Figure 3 is then

Define the language

As $L_{0}$ is a regular language, it follows that $L_{1}$ is a regular language.

Recall that when $v\neq t^{k}x_{q}$, if $m_{1}=k_{*}$ we allow $v_{1}$ to be trivial, otherwise $v_{1}$ must be nontrivial, and if $m_{2}=k_{*}$ we allow $v_{s}$ to be trivial, otherwise $v_{s}$ must be nontrivial. These conditions are easily verified by a finite state automaton inspecting, respectively, the first and last expressions in the product representing an element of $L_{1}$ according to the following rules:

1. (1)

   if $C_{*}$ occurs in the first factor in the product as expressed in Equation 3, then all $v_{i,j}$ may be $\varepsilon$ for $0\leqslant j\leqslant m$; if not, at least one $v_{i,j}$ must be nontrivial.

2. (2)

   if the $C_{*}$ occurs in the last factor in the product as expressed in Equation 3, then all $v_{i,j}$ may be $\varepsilon$ for $0\leqslant j\leqslant m$; if not, at least one $v_{i,j}$ must be nontrivial.

Note that a finite state automaton can also easily verify that when all $v_{\varsigma}$ are trivial, we have a normal form corresponding to $t^{k}x_{q}$. Let $L_{2}\subseteq L_{1}$ be the set of all strings in $L_{1}$ for which all three of these conditions are satsified. Since these conditions are easily checked by a finite state automaton, and $L_{1}$ is a regular language, it follows that $L_{2}$ is a regular language.

Finally, we verify that the string has only one occurrence each of $B_{*}$ and $C_{*}$. Let

It follows that $L$ is regular and that $L={\mathcal{N}}$.

As a further example, note that if $v=t^{n}x_{q}$, the corresponding word in $L$ is as follows:

1. (1)

   when $n>0$, we have $\mathrm{isupp}(t^{n}x_{q})=[0,n]$ and the corresponding word is

   $$B_{0}C^{m+1}(BC^{m+1})^{n-1}BC^{q}C_{*}C^{m-q};$$

2. (2)

   when $n=0$, we have $\mathrm{isupp}(x_{q})=[0,0]$ and the corresponding word is

   $$B_{0}C^{q}C_{*}C^{m-q};$$

3. (3)

   when $n<0$, we have $\mathrm{isupp}(t^{n}x_{q})=[n,0]$ and the corresponding word is

   $$BC^{q}C_{*}C^{m-q}(BC^{m+1})^{n-1}B_{0}C^{m+1}.$$

Given a word $\sigma\in L$, the symbols $B_{0}$ and $C_{*}$ allow us to reconstruct the integer support of the corresponding element, as well as the final position of the lamplighter, that is, the coordinate $h$. The words $v_{i,j}$ correspond (via $\psi_{0}$) to elements of $G$ listed in a specified order. That is, we can deterministically reconstruct $\gamma\in\bigoplus_{h\in H}(G)_{h}$ and $h\in H$ from $\sigma$. Formally, let $\psi\colon L\rightarrow G\wr H$ be the bijective map defined by

where

with $u_{i,j}=v_{i,j}$, $\beta_{k}\in\{B,B_{0}\}$, $\Gamma_{k,j}\in\{C,C_{*}\}$ and $m_{1}$ calculated from the positions of $B_{0}$ and $C_{*}$ as described above.

We claim that $(S,\Lambda,L,\psi)$ is a Cayley automatic structure for $G\wr H$. To prove this, we must show that for every generator $s\in S=S_{0}\cup T$ the set

is a regular language, that is, recognised by a 2-tape synchronous automaton. It suffices to do this for $s\in S_{0}\cup\{x_{1},\cdots,x_{m},t\}$; see, for example, [5, Lemma 9].

First let $s\in S_{0}$ and suppose $(u,v)\in R_{s}$. Viewing $\psi(u)$ as a configuration of ${\mathcal{S}}$ with finitely many vertices marked with elements of $G$ and a distinguished position for the lamplighter, we can easily see the effect of multiplication by $s$ on the normal form. Let $t^{k}x_{q}$ denote the vertex of ${\mathcal{S}}$ which is the final position of the lamplighter in $u$, marked by the element $g_{u}\in G$. Let $\rho_{u}\in L_{0}$ be such that $\psi_{0}(\rho_{u})=g_{u}$. To obtain the normal form word for $\psi(u)s$ we simply multiply $\rho_{u}$ by $s$ and verify that the multiplication is correct using the multiplier automaton $\texttt{M}_{s}$ given as part of the given Cayley automatic structure on $G$. Therefore we need to accept pairs of strings $(u,v)\in L\times L$ of the following form:

and

where $\beta_{i}\in\{B,B_{0}\}$, $\alpha_{i,j}\in L_{0}$,

and

where $(\alpha_{p+1,r},\alpha^{\prime}_{p+1,r})$ is accepted by the multiplier automaton $\texttt{M}_{s}$ given as part of the given Cayley automatic structure on $G$. The bold highlighted symbols represent the only difference between the two words.

By [7] (see also [5, Lemma 8]) the language $L_{0}$ is necessarily quasigeodesic. It follows that the difference between the lengths of $\alpha_{p+1,r}$ and $\alpha^{\prime}_{p+1,r}$ is uniformly bounded. As it is regular to check that two words are identical with a bounded shift, it follows that we can construct a 2-tape automaton which checks that the prefixes of $u$ and $v$ are identical, then calls $\texttt{M}_{s}$ to read $(\alpha_{p+1,r},\alpha^{\prime}_{p+1,r})$, and finally checks that the suffixes of $u$ and $v$ are identical (with a bounded shift). Thus $R_{s}$ is a regular language.

Next let $x_{i}\in\{x_{1},\cdots,x_{m}\}$, and suppose $(u,v)\in R_{x_{i}}$. Writing $\psi(u)$ as in Equation (1), we see that $\psi(u)x_{i}$ ends in the letters $x_{q}x_{i}$. The product $x_{q}x_{i}\in H$ is an element of some right coset $\langle t\rangle x_{r}$. That is, $x_{q}x_{i}=t^{k}x_{r}$ for some $k$ and $r$. Viewing $\psi(u)$ and $\psi(v)$ as configurations in ${\mathcal{S}}$, this means that the configurations are identical except for the final position of the lamplighter which is indicated by $C_{*}$ in the normal form. Note that as $x_{q}$ and $x_{i}$ vary among the finite set of coset representatives, there are only a finite number of possible values of $(k,r)$ which arise.

The elements $\psi(u)$ and $\psi(v)$ may or may not have identical integer support. For example if $\psi(u)=t^{-10}g_{1}t^{20}g_{2}t^{-5}x_{q}$ and $x_{q}x_{i}=t^{-7}x_{r}$ then $\mathrm{isupp}(\psi(u))=\mathrm{isupp}(\psi(v))$, whereas if $\psi(u)=t^{-10}g_{1}t^{20}g_{2}t^{-5}x_{q}$ and $x_{q}x_{i}=t^{-17}x_{r}$ then $\mathrm{isupp}(\psi(u))\neq\mathrm{isupp}(\psi(v))$.

If $\mathrm{isupp}(\psi(u))=\mathrm{isupp}(\psi(v))$, then we simply need to check the two strings are identical except for the location of $C_{*}$. If $\psi(u)$ ends in $x_{q}$ when written as in Equation (1), we have $x_{q}x_{i}=t^{k}x_{r}$. Let $\pi\colon\Lambda^{*}\to\{C,C_{*},B_{0}\}^{*}$ be a homomorphism which is the identity on $C,C_{*},B_{0}$ and sends all other letters to $\varepsilon$. Then $\pi(u)$ and $\pi(v)$ are identical strings except for the location of $C_{*}$ in each string. Observe the letter $B_{0}$ is in the same position in each string since the integer supports of $\psi(u)$ and $\psi(v)$ are the same. Further observe that there exists an integer $s_{q,i}$ such that for every pair $(u,v)\in R_{x_{i}}$ which have the same integer support, if $C_{*}$ is the $x$th letter of $\pi(u)$ and the $y$th letter of $\pi(v)$, then $x-y=s_{q,i}$.

Consider the language $X_{q,i}\subseteq\{C,C_{*},B_{0}\}^{*}\times\{C,C_{*},B_{0}\}^{*}$ consisting of all pairs of strings, each of which contains exactly one $C_{*}$ letter and one $B_{0}$ letter, where $C_{*}$ is the $x$th letter of the first string and the $y$th letter of the second string with $x-y=s_{q,i}$, and $B_{0}$ is in the same position in both strings. Since these conditions are regular to check, $X_{q,i}$ is a regular language.

Let

be the map which in each coordinate is the identity on $C,C_{*}$ and $B_{0}$ and sends all other letters to $\varepsilon$. Let $Y\subseteq\Lambda^{*}\times\Lambda^{*}$ be the language consisting of all pairs of strings such that for every positive integer $z$ the $z$th letter of the first string and the second string is the same unless one of these letters is $C_{*}$ and the other is $C$. The language $Y$ is regular. Then the language

is regular, and the union of these languages for $0\leqslant q\leqslant m+1$ is exactly the subset of $R_{x_{i}}$ for which multiplication by $x_{i}$ does not change the integer support for the first entry.

Now consider all the possible ways that the integer support of $\psi(u)$ can change upon multiplication by $x_{i}$. Again assume $\psi(u)$ ends in $x_{q}$ when written as in Equation (1), and $x_{q}x_{i}=t^{k}x_{r}$. We must consider the following cases.

1. (1)

   $\psi(u)=t^{n}x_{q}$ and $k\neq 0$,

2. (2)

   $\psi(u)=t^{m_{1}}v_{1}tv_{2}\dots tv_{s}t^{j}x_{q}$ with $\mathrm{isupp}(\psi(u))=[m_{1},m_{2}],j\leqslant 0$ and

   1. (a)

      $k>-j$; in this case the integer support of $v$ extends further to the right of $m_{2}$,

   2. (b)

      $k<m_{1}-m_{2}-j$; in this case the integer support of $v$ extends further to the left of $m_{1}$.

Each of these cases can be handled in a manner similar to the above case, by considering the relative positions of $C_{*}$ and $B_{0}$ in $\pi(u),\pi(v)$. For the first case, if $n>0,k>-n$ then