2. Preliminaries

We will now present the basic definitions and results on rational, algebraic and context-free subsets of groups. For more detail, the reader is referred to [Reference Bartholdi, Silva and Pin1, Reference Berstel3].

Let $G=\langle A\rangle $ be a finitely generated group, A a finite generating set, $\tilde A=A\cup A^{-1}$ and $\pi :\tilde A^*\to G$ be the canonical (surjective) homomorphism.

A subset $K\subseteq G$ is said to be rational if there is some rational language $L\subseteq \tilde A^*$ such that $L\pi =K$ and recognisable if $K\pi ^{-1}$ is rational. We will denote by $\mathrm {Rat}(G)$ and $\mathrm {Rec}(G)$ the class of rational and recognisable subsets of G, respectively. Rational subsets generalise the notion of finitely generated subgroups.

We remark that, as long as we can test membership in the subset H, the above theorem is constructive, in the sense that if we have an automaton recognising a language L such that $L\pi $ is a subgroup, we can compute a set of generators for the subgroup H. That can be seen by following the proof of [Reference Bartholdi, Silva and Pin1, Theorem 3.1]. We will prove the main result by proving that centralisers of elements in [f.g. free]-by-cyclic groups are rational subsets and an automaton generating them can be computed.

A natural generalisation of these concepts relates to the class of context-free languages. A subset $K\subseteq G$ is said to be algebraic if there is some context-free language $L\subseteq \tilde A^*$ such that $L\pi =K$ and context-free if $K\pi ^{-1}$ is context-free. We will denote by $\text {Alg}(G)$ and $\text {CF}(G)$ the class of algebraic and context-free subsets of G, respectively. It follows from [Reference Herbst13, Lemma 2.1] that $\text {CF}(G)$ and $\text {Alg}(G)$ do not depend on the alphabet A or the surjective homomorphism $\pi $ . We follow the terminology in [Reference Carvalho8, Reference Herbst13, Reference Herbst14]. However, for example, in [Reference Ciobanu, Evetts and Levine9], algebraic subsets are called context-free subsets and context-free subsets are called recognisably context-free.

It is obvious from the definitions that $\mathrm {Rec}(G)$ , $\mathrm {Rat}(G)$ , $\text {CF}(G)$ and $\text {Alg}(G)$ are closed under union, since both rational and context-free languages are closed under union. Intersections behave differently: from the fact that rational languages are closed under intersection, it follows that $\mathrm {Rec}(G)$ must be closed under intersection. However, $\mathrm {Rat}(G)$ , $\text {Alg}(G)$ and $\text {CF}(G)$ might not be. We will also use the fact that the class of rational subsets is closed under inversion.

For a finitely generated group G, it is immediate from the definitions that

$$ \begin{align*} \mathrm{Rec}(G)\subseteq \text{CF}(G) \subseteq \text{Alg}(G) \quad\mbox{and}\quad \mathrm{Rec}(G)\subseteq \mathrm{Rat}(G) \subseteq \text{Alg}(G). \end{align*} $$

However, there is no general inclusion between $\mathrm {Rat}(G)$ and $\text {CF}(G)$ . For example, if G is virtually abelian, then $\text {CF}(G)\subseteq \text {Alg}(G)= \mathrm {Rat}(G)$ (and the inclusion is strict if the group is not virtually cyclic) and if the group is virtually free, then $\mathrm {Rat}(G)\subseteq \text {CF}(G)$ (see [Reference Herbst13, Lemma 4.2]). In the case of the free group $F_n$ of rank $n\geq 1$ , Herbst proves in [Reference Herbst13, Lemma 4.6] an analogue of Benois’ theorem for context-free subsets, showing that for a subset $K\subseteq F_n$ , we have $K\in \text {CF}(F_n)$ if and only if the set of reduced words representing elements of K is context-free.

The fact that context-free languages are closed under intersection with rational languages and that the emptiness of a context-free language can be decided implies that we can decide whether a context-free subset intersects a rational subset or not. This, together with the main result, yields a proof of Corollary 3.6.

3. The main result

Let G be a group, $\phi \in \mathrm {Aut}(G)$ , $x\in G$ and $a\in \mathbb {Z}$ . We define the set $\mathcal E_{a,x,\phi }$ by ${\mathcal E_{a,x,\phi }=\{k\in \mathbb {Z}\mid x\phi ^k\sim _{\phi ^a} x\}}$ . Usually, we omit the subscripts $\phi $ and x as these will be clear from the context.

Proof. We have $0\in \mathcal E_{a}$ , because $x\phi ^0=x=(1^{-1}\phi ^a)x1$ . Since $x\phi ^a=(x\phi ^a)xx^{-1}$ , we have $x\sim _{\phi ^a}x\phi ^a$ , and so $a\in \mathcal E_{a}$ . It follows that $\mathcal E_a=\{0\}$ if and only if $a=0$ . Suppose that $\mathcal E_{a}\neq \{0\}$ and let $b=\min \{|k|\mid k\in \mathcal E_{a}\setminus \{0\}\}$ . We will prove that $\mathcal E_{a}=b\mathbb {Z}$ , which in particular implies that $b\mid a$ , as $a\in \mathcal E_{a}$ . We start by showing that $k\in \mathcal E_{a}$ if and only if $-k\in \mathcal E_{a}$ . This follows from the fact that

$$ \begin{align*} x\phi^b=(y^{-1}\phi^a)xy\iff x=(y^{-1}\phi^{a-b})(x\phi^{-b})(y\phi^{-b})\iff x\phi^{-b}=(y\phi^{-b})\phi^ax(y^{-1}\phi^{-b}). \end{align*} $$

Now we show that $\mathcal E_{a}$ is closed under addition, from which it follows that $\mathcal E_{a}$ is a subgroup of $\mathbb {Z}$ , and so cyclic. Let $k_1,k_2\in \mathcal E_{a}$ . Then, there are $y,z\in G$ such that $x\phi ^{k_1}=(y^{-1}\phi ^a)xy$ and $x\phi ^{k_2}=(z^{-1}\phi ^a)xz$ . Hence,

$$ \begin{align*} x\phi^{k_1+k_2} &=x\phi^{k_1}\phi^{k_2}\\ & =((y^{-1}\phi^a)xy)\phi^{k_2}\\ & =(y^{-1}\phi^{k_2})\phi^a(x\phi^{k_2})(y\phi^{k_2})\\ & =(y^{-1}\phi^{k_2})\phi^a \cdot (z^{-1}\phi^a)xz \cdot(y\phi^{k_2})\\ & =((y^{-1}\phi^{k_2})z^{-1})\phi^a\cdot x \cdot z(y\phi^{k_2}).\\[-34pt] \end{align*} $$

We will denote the minimal element b from the above lemma by $e_a$ .

Proof. For $t^b y\in G\rtimes _\phi \mathbb {Z}$ ,

(3.1) $$ \begin{align} x (t^b y)=(t^b y)x\iff(y^{-1}t^{-b})x (t^b y)= x \iff y^{-1}(x\phi^b)y=x. \end{align} $$

If there is no $k\neq 0$ such that $x\phi ^k \sim x$ , then, by (3.1), $t^by\in C_{G\rtimes _\phi \mathbb {Z}}$ implies that $b=0$ and $y\in C_G(x)$ . So, in this case, $C_{G\rtimes _\phi \mathbb {Z}}(x)=C_{G}(x)$ .

Assume now that there is such a k. Clearly, $C_G(x)\trianglelefteq C_{G\rtimes _\phi \mathbb {Z}}(x)$ and $t^{e_0}z\in C_{G\rtimes _\phi \mathbb {Z}}(x)$ by (3.1). If $t^ay\in C_{G\rtimes _\phi \mathbb {Z}}(x)$ , then $a\in e_0\mathbb {Z}$ , by Lemma 3.1, so $a=\lambda e_0$ for some $\lambda \in \mathbb {Z}$ . This means that $(t^{e_0}z)^{-\lambda }(t^ay)\in G\cap C_{G\rtimes _\phi \mathbb {Z}}(x)= C_{G}(x)$ , and so $(t^ay)\in (t^{e_0}z)^{\lambda }C_G(x)= ((t^{e_0}z)C_G(x))^{\lambda }$ .

Now, we define

$$ \begin{align*}\mathcal C_{k,a,x,\phi}:=\{y\in G\mid x=(y^{-1}\phi^a)(x\phi^k)y\}.\end{align*} $$

Notice that $\mathcal C_{k,a,x,\phi }\neq \emptyset $ if and only if $k\in \mathcal E_{a,x,\phi }$ . Again, we will typically write $\mathcal C_{k}$ , since a, x and $\phi $ will be clear from context.

Proposition 3.3. Let G be a group, $\phi \in \mathrm {Aut}(G)$ , $a\in \mathbb {Z}$ , $x\in G$ and $k\in \mathbb {Z}$ . If ${\mathcal E_{a,x,\phi }\neq \{0\}}$ , then

$$ \begin{align*}\mathcal C_{(k+1)e_a,a,x,\phi}= (\mathcal C_{ke_a,a,x,\phi})\phi^{e_a}\mathcal C_{e_a,a,x,\phi}= (\mathcal C_{ke_a,a,x,\phi})\phi^{e_a}z\end{align*} $$

for all $z\in \mathcal C_{e_a,a,x,\phi }$ .

Proof. Let $y\in \mathcal C_{(k+1)e_a}$ . Then

(3.2) $$ \begin{align} x=(y^{-1}\phi^a)(x\phi^{(k+1)e_a})y. \end{align} $$

Let $z\in \mathcal C_{e_a}$ , that is, take $z\in G$ such that

$$ \begin{align*} x=(z^{-1}\phi^a)(x\phi^{e_a})z, \end{align*} $$

so that

(3.3) $$ \begin{align} x\phi^{-e_a}=(z^{-1}\phi^{a-e_a})x(z\phi^{-e_a}). \end{align} $$

From (3.2), we deduce that $x\phi ^{-e_a}=(y^{-1}\phi ^{a-e_a})(x\phi ^{ke_a})(y\phi ^{-e_a})$ , which, combined with (3.3), yields

$$ \begin{align*}(z^{-1}\phi^{a-e_a})x(z\phi^{-e_a})=(y^{-1}\phi^{a-e_a})(x\phi^{ke_a})(y\phi^{-e_a})\end{align*} $$

or, equivalently,

$$ \begin{align*}x=((zy^{-1})\phi^{-e_a})\phi^a(x\phi^{ke_a})(yz^{-1})\phi^{-e_a},\end{align*} $$

that is, $(yz^{-1})\phi ^{-e_a}\in \mathcal C_{ke_a}$ . Hence, $y\in (\mathcal C_{ke_a})\phi ^{e_a}z$ and it follows that

$$ \begin{align*}\mathcal C_{(k+1)e_a}\subseteq (\mathcal C_{ke_a})\phi^{e_a}z\subseteq (\mathcal C_{ke_a})\phi^{e_a}\mathcal C_{e_a}.\end{align*} $$

Now, let $y\in \mathcal C_{ke_a}$ and $z\in \mathcal C_{e_a}$ . Then $x=(y^{-1}\phi ^a)(x\phi ^{ke_a})y$ and $x=(z^{-1}\phi ^a)(x\phi ^{e_a})z$ . From the first condition, $x\phi ^{e_a}=(y^{-1}\phi ^{a+e_a})(x\phi ^{(k+1)e_a})(y\phi ^{e_a})$ which, from the second condition, yields

$$ \begin{align*}(z\phi^a)xz^{-1}=(y^{-1}\phi^{a+e_a})(x\phi^{(k+1)e_a})(y\phi^{e_a})\end{align*} $$

or, equivalently,

$$ \begin{align*}x=(z^{-1}(y^{-1}\phi^{e_a}))\phi^a(x\phi^{(k+1)e_a})((y\phi^{e_a})z),\end{align*} $$

that is, $(y\phi ^{e_a})z\in \mathcal C_{(k+1)e_a}$ . Hence, $ (\mathcal C_{ke_a})\phi ^{e_a}\mathcal C_{e_a}\subseteq \mathcal C_{(k+1)e_a}$ . Therefore,

$$ \begin{align*}\mathcal C_{(k+1)e_a,a,x,\phi}= (\mathcal C_{ke_a,a,x,\phi})\phi^{e_a}\mathcal C_{e_a,a,x,\phi}= (\mathcal C_{ke_a,a,x,\phi})\phi^{e_a}z\end{align*} $$

for all $z\in \mathcal C_{e_a,a,x,\phi }$ .

Proof. We start with the case $a=0$ . We start by computing $u\in F_n$ such that ${C_{F_n}(x)=\langle u\rangle }$ . Then we decide if there is some $k\neq 0$ such that $x\phi ^k \sim x$ , using [Reference Logan16, Lemma 4.1] with input $(\phi ,x\phi ,x)$ . If there is, we compute the minimal $k>0$ such that $x\phi ^k\sim x$ by solving the conjugacy problem until we find a positive answer and compute a conjugator z in $F_n$ . Lemma 3.2 yields $C_{F_n\rtimes _\phi \mathbb {Z}}(x)=\langle t^kz, u\rangle $ . If there is no such k, then Lemma 3.2 yields $C_{F_n\rtimes _\phi \mathbb {Z}}(x)=\langle u\rangle $ .

Next, for the case $a\neq 0$ ,

$$ \begin{align*}(y^{-1}t^{-b})(t^ax) (t^b y)=t^a x \iff t^a (y^{-1}\phi^a)(x\phi^b)y=t^ax\iff (y^{-1}\phi^a)(x\phi^b)y=x.\end{align*} $$

So

$$ \begin{align*}t^by\in C_{F_n\rtimes_\phi \mathbb{Z}}(t^ax)\iff y\in \mathcal C_{b,a,x,\phi}\end{align*} $$

and, in particular, $b\in \mathcal E_{a,x,\phi }$ . From Lemma 3.1, it follows that $\mathcal E_{a,x,\phi }=e_a\mathbb {Z}$ (notice that $a\in \mathcal E_{a,x,\phi }$ and $a\neq 0$ ). Also, since the twisted conjugacy problem is decidable for automorphisms of free groups by [Reference Bogopolski, Martino, Maslakova and Ventura4, Theorem 1.5], then $e_a$ is computable. Hence,

$$ \begin{align*}C_{F_n\rtimes_\phi \mathbb{Z}}(t^ax)=\bigcup_{k\in \mathbb{Z}} t^{ke_a}\mathcal C_{ke_a,a,x,\phi}.\end{align*} $$

By Proposition 3.3, for all $k\in \mathbb {Z}$ ,

$$ \begin{align*}\mathcal C_{(k+1)e_a,a,x,\phi}= \mathcal C_{ke_a,a,x,\phi}\phi^{e_a}\mathcal C_{e_a,a,x,\phi}.\end{align*} $$

It follows by induction that, for $k\geq 0$ ,

(3.4) $$ \begin{align} \mathcal C_{ke_a,a,x,\phi}= (\mathcal C_{e_a,a,x,\phi}\phi^{ke_a})(\mathcal C_{e_a,a,x,\phi}\phi^{(k-1)e_a})\cdots (\mathcal C_{e_a,a,x,\phi}\phi^{e_a})\mathcal C_{e_a,a,x,\phi}. \end{align} $$

Also, using the fact that $C_{e_a,a,x,\phi }t^{e_a}=t^{e_a}C_{e_a,a,x,\phi }\phi ^{e_a}$ , we can see by induction that for all $k>0$ ,

(3.5) $$ \begin{align} (\mathcal C_{e_a,a,x,\phi}t^{e_a})^k=t^{ke_a}\mathcal C_{e_a,a,x,\phi}\phi^{ke_a}\mathcal C_{e_a,a,x,\phi}\phi^{(k-1)e_a}\cdots \mathcal C_{e_a,a,x,\phi}\phi. \end{align} $$

Indeed, if $k=1$ , we have $\mathcal C_{e_a,a,x,\phi }t^{e_a}=t^{e_a}\mathcal C_{e_a,a,x,\phi }\phi ^{e_a}$ and assuming that the claim holds for all integers up to some k, we have

$$ \begin{align*} (\mathcal C_{e_a,a,x,\phi}t^{e_a})^{k+1}&=(\mathcal C_{e_a,a,x,\phi}t^{e_a})^{k}(\mathcal C_{e_a,a,x,\phi}t^{e_a})\\ &=(t^{ke_a}\mathcal C_{e_a,a,x,\phi}\phi^{ke_a}\mathcal C_{e_a,a,x,\phi}\phi^{(k-1)e_a}\cdots \mathcal C_{e_a,a,x,\phi}\phi)\cdot (\mathcal C_{e_a,a,x,\phi}t^{e_a})\\ &=t^{(k+1)e_a}\mathcal C_{e_a,a,x,\phi}\phi^{(k+1)e_a}\mathcal C_{e_a,a,x,\phi}\phi^{ke_a}\cdots \mathcal C_{e_a,a,x,\phi}\phi. \end{align*} $$

By [Reference Ladra and Silva15, Proposition 5.7], $\mathcal C_{e_a,a,x,\phi }$ is rational and effectively constructible. It follows from (3.4) and (3.5) that

$$ \begin{align*} \bigcup_{k>0} t^{ke_a}\mathcal C_{ke_a,a,x,\phi}=\, & \bigcup_{k>0} t^{ke_a} \mathcal C_{e_a,a,x,\phi}\phi^{ke_a}\mathcal C_{e_a,a,x,\phi}\phi^{(k-1)e_a}\cdots \mathcal C_{e_a,a,x,\phi}\\ =\,& \bigcup_{k>0}(\mathcal C_{e_a,a,x,\phi}t^{e_a})^k\mathcal C_{e_a,a,x,\phi}\\ =\,& (\mathcal C_{e_a,a,x,\phi}t^{e_a})^+\mathcal C_{e_a,a,x,\phi} \end{align*} $$

and so $\mathcal S=\bigcup _{k>0} t^{ke_a}\mathcal C_{ke_a,a,x,\phi }$ is also rational and effectively constructible. Again, the set of elements with negative integral part is the set of inverses of elements in $\mathcal S$ . Since rational subsets are effectively closed under taking inverses and, again by [Reference Ladra and Silva15, Proposition 5.7], $\mathcal C_{0,a,x,\phi }=\{y\in G\mid (y^{-1}\phi ^a) x y=x\}$ is rational and computable,

$$ \begin{align*}C_{F_n\rtimes_\phi \mathbb{Z}}(t^ax)=\mathcal S^{-1}\cup \mathcal C_{0,a,x,\phi} \cup \mathcal S\end{align*} $$

is rational and computable. Since we can test if an element $t^by\in F_n\rtimes _\phi \mathbb {Z}$ belongs to $C_{F_n\rtimes _\phi \mathbb {Z}}(t^ax)$ by checking if $t^byt^ax=t^axt^by$ , we can effectively compute a finite set of generators for $C_{F_n\rtimes _\phi \mathbb {Z}}(t^ax)$ .

Since the union of two rational subsets is again rational and effectively constructible, it follows from the previous corollary that the set of solutions of ${x^{-1}(t^au)x\in K}$ is rational and computable for a finite subset K. By [Reference Ladra and Silva15, Example 5.3], the finite subset K cannot be replaced by arbitrary rational subsets in this statement, as the example presents an [f.g. free]-by-cyclic group G, an element $g\in G$ and a rational subset $K\subseteq G$ such that the solution set of $x^{-1}gx\in K$ is not rational.

In a group $G=\langle A\rangle $ , we denote by $\pi $ the canonical surjective homomorphism $\pi : (A\cup A^{-1})^*\to G$ . Since context-free languages are closed under intersection with rational languages and it is decidable whether a context-free grammar generates the empty language, the following corollary is immediate.

Naturally, the same result holds for subsets K for which we can decide if ${K\pi ^{-1} \cap L =\emptyset} $ for rational languages L.

4. Further work

We now present the main questions arising from this work.

First, we would also like to understand what $CF(F_n\rtimes \mathbb {Z})$ consists of. As remarked in Section 2, for free groups, $\mathrm {Rat}(F_n)\subseteq \text {CF}(F_n)$ and for virtually abelian groups, $\text {CF}(F_n)\subseteq \mathrm {Rat}(F_n)$ . Also for free groups, context-free subsets are well described. Understanding context-free subsets of [f.g. free]-by-cyclic groups would allow us to fully understand the strength of Corollary 3.6.

We also remark that Theorem 3.4 holds for any G-by- $\mathbb {Z}$ group as long as G has finitely generated and computable centralisers, decidable Brinkmann’s conjugacy problem, and decidable twisted conjugacy problem with rational and computable twisted conjugacy classes. Notice that decidability of Brinkmann’s conjugacy problem and of the twisted conjugacy problem in G implies decidability of the conjugacy problem in G-by- $\mathbb {Z}$ groups, and so the corollaries of the theorem also follow.

If G is a braid group, then the centralisers of its elements are computable [Reference Franco and González-Meneses10], and both Brinkmann’s conjugacy problem and the twisted conjugacy problem are decidable [Reference González-Meneses and Ventura11]. So, a natural problem is the following one.

We remark that it follows from the proof of [Reference González-Meneses and Ventura11, Theorem 4.9] that it is enough to solve this problem for $\varepsilon $ -twisted conjugacy classes.

If G is a finitely generated virtually free group, then its centralisers are computable (see for example [Reference Ladra and Silva15]) and the twisted conjugacy problem is proved to be decidable in [Reference Carvalho7, Theorem 5.4]. In the proof, it is shown that, given a virtually free group G, an endomorphism $\phi $ , elements $u,v\in G$ and constructing $G_1=G*\langle x,y|\rangle $ , the free product of G with a free group of rank 2, it is possible to define an endomorphism $\psi $ of $G_1$ such that the set of $\phi $ -twisted conjugators of u and v is precisely $x^{-1}\text {Fix}(\psi )y^{-1}\cap G$ . The latter is the intersection of two rational and computable (see [Reference Carvalho6] for the computability of Fix( $\psi $ )) subsets of the virtually free group $G_1$ , and thus computable [Reference Silva19, Lemma 4.4]. The obstruction to a generalisation of our theorem to [f.g. virtually free]-by- $\mathbb {Z}$ groups is the solution of Brinkmann’s conjugacy problem for virtually free groups. We remark that Brinkmann’s equality problem was solved in [Reference Carvalho7, Theorem 5.3].

An easier, but still interesting, decision problem is satisfiability of the condition in Lemma 3.2, which can be seen as periodicity modulo conjugation, for some natural classes of groups.