COMPUTING CENTRALISERS IN [FINITELY GENERATED FREE]-BY-CYCLIC GROUPS

Abstract

We prove that centralisers of elements in [finitely generated free]-by-cyclic groups are computable. As a corollary, given two conjugate elements in a [finitely generated free]-by-cyclic group, the set of conjugators can be computed and the conjugacy problem with context-free constraints is decidable. We pose several problems arising naturally from this work.

1. Introduction

Two elements $x,y\in G$ are said to be conjugate if there is some $z\in G$ such that ${x=z^{-1}yz}$ . Conjugacy is an equivalence relation and we write $x\sim y$ if x and y are conjugate. The conjugacy problem which consists in deciding whether two elements in a group G are conjugate or not is an important problem in combinatorial group theory. It is undecidable in general [17] and has been studied in many different classes of groups (see, for example, [4, 12, 15, 16, 18]).

Some variations and questions related to the conjugacy problem have also been studied. In [15], Ladra and Silva study the generalised conjugacy problem, which is the problem of deciding, given an element $g \in G$ and a subset $K\subseteq G$ , whether g has a conjugate in K, and they prove that this is decidable in virtually free groups when the subset K is rational. More than that, they prove that the set of solutions of the equation $x^{-1}gx\in K$ is rational and effectively constructible in a virtually free group. This allows the solution of the constrained generalised conjugacy problem when the constraints have good intersection properties with rational subsets. This problem consists in deciding whether g has a conjugate in K with the conjugator belonging to some constraint subset. Since it is decidable whether a context-free and a rational subset intersect, it follows that the generalised conjugacy problem for rational subsets of virtually free groups with context-free subsets as constraints is decidable. We remark that the class of context-free subsets of virtually free groups contains the class of rational subsets (see [13]) and so, in particular, we can decide this problem when the constraint is a finitely generated subgroup. Even though this is not relevant in the virtually free group case since finitely generated subgroups of virtually free groups are again virtually free, we remark that solving the conjugacy problem with finitely generated subgroups as constraints in a given group G yields a solution of the conjugacy problem in any finitely generated subgroup H of G, since two elements $h_1,h_2\in H$ are conjugate in H if and only if they are conjugate in G with a conjugator belonging to H.

Given an endomorphism $\phi \in \text {End}(G)$ , two elements $x,y\in G$ are $\phi $ -twisted conjugate if there is some $z\in G$ such that $x=(z^{-1}\phi ) y z$ , in which case we write $x\sim _{\phi }y$ . This is again an equivalence relation. Brinkmann’s conjugacy problem was introduced in [5], where it was solved in the affirmative for automorphisms of the free group; this problem consists in deciding, given an automorphism $\phi $ and elements $x,y\in G$ , whether there is some integer k such that $x\phi ^k\sim y$ .

In [4], Bogopolski et al. proved that the conjugacy problem is decidable in [f.g. free]-by-cyclic groups by proving that it can be reduced to the twisted conjugacy problem and Brinkmann’s conjugacy problem for automorphisms of the free group (f.g. will be used from now on as an abbreviation for finitely generated). They solve the twisted conjugacy problem and use Brinkmann’s result from [5] to finish the proof. This approach was followed in [7] for the generalised versions of these problems. In [16], Logan generalised the ideas in [4] and proved that the conjugacy problem is decidable in ascending HNN-extensions of the free group by reducing it to nonbijective versions of Brinkmann’s conjugacy problem and the twisted conjugacy problem, and proving decidability of these algorithmic questions. In [16], Logan highlights the fact that many (in a precise sense) one-relator groups appear as subgroups of ascending HNN-extensions of a free group, so solving the conjugacy problem for ascending HNN-extensions with finitely generated subgroups as constraints would yield a solution to the conjugacy problem in many one-relator groups, which is an important open problem.

The set of conjugators between two conjugate elements $x,y$ of a group G is a coset of the centraliser of x in G. For this reason, if in a group the conjugacy problem is decidable and centralisers of elements are computable, then given two elements x and y, the set of conjugators between x and y (which might be empty) is also computable. This can be done, for example, in virtually free groups [15], polycyclic-by-finite groups [2] and braid groups [10].

The main goal of this paper is to prove that centralisers of elements of [f.g. free]-by-cyclic groups are computable. If the cyclic group is finite, then the group is virtually free, so this case is already known. For this reason, we will focus on the [f.g. free]-by- $\mathbb {Z}$ case.

Theorem 3.4. There is an algorithm taking as input an automorphism $\phi \in \mathrm {Aut}(F_n)$ and an element $t^ax\in F_n\rtimes _\phi \mathbb {Z}$ that outputs a finite set of generators for $C_{F_n\rtimes _\phi \mathbb {Z}}(t^ax)$ .

Naturally, if two elements $x,y\in G$ are conjugate, the set of conjugators is a coset of $C_G(x)$ and, since the conjugacy problem is decidable in [f.g. free]-by- $\mathbb {Z}$ groups, then we have the following corollary, in the same spirit as the result in [15].

Corollary 3.5. Let $\phi \in \mathrm {Aut}(F_n)$ and $t^au, \, t^bv\in F_n\rtimes _\phi \mathbb {Z}$ . The set of solutions to the equation $x^{-1}(t^au)x=t^bv$ is rational and effectively constructible.

This corollary clearly implies that the solution set of the equation $x^{-1}(t^au)x\in K$ for a finite K is rational and computable since it is a finite union of rational and computable subsets. By [15, Example 5.3], we cannot replace finite by rational as, in this case, the solution set is not rational.

Since context-free languages are closed under the intersection with rational languages and we can decide their emptiness, we also have the following corollary.

Corollary 3.6. The conjugacy problem with context-free constraints is decidable for [f.g. free]-by-cyclic groups, that is, there is an algorithm taking as input any two elements $t^ax,\, t^by \in F_n\rtimes _{\phi }\mathbb {Z}$ and a context-free grammar generating a language L such that $L=K\pi ^{-1}$ for some $K\subseteq F_n\rtimes _\phi \mathbb {Z}$ , which decides whether there is an element $t^cz\in K$ such that $t^ax=(t^cz)^{-1}(t^by) t^c z$ .

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 [1, 3].

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.

Theorem 2.1 [3, Theorem III.2.7].

Let H be a subgroup of a group G. Then ${H\in \mathrm {Rat}(G)}$ if and only if H is finitely generated.

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 [1, 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 [13, 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 [8, 13, 14]. However, for example, in [9], 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 [13, Lemma 4.2]). In the case of the free group $F_n$ of rank $n\geq 1$ , Herbst proves in [13, 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.

Lemma 3.1. Let G be a group, $\phi \in \mathrm {Aut}(G)$ , $x\in G$ and $a\in \mathbb {Z}$ . Then, either $\mathcal E_{a,x,\phi }=\{0\}$ or there is some b dividing a such that $\mathcal E_{a,x,\phi }=b\mathbb {Z}$ .

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

Lemma 3.2. Let G be a group, $\phi \in \mathrm {Aut}(G)$ and $x\in G$ .

1. (i) If there is $k\neq 0$ such that $x\phi ^k\sim x$ , then

   
   where $z\in G$ is such that $x=z^{-1}(x\phi ^{e_0})z$ . In particular,
   $$ \begin{align*}C_{G\rtimes_\phi \mathbb{Z}}(x)=\langle t^{e_0}z, C_{G}(x)\rangle.\end{align*} $$

2. (ii) If there is no $k\neq 0$ such that $x\phi ^k \sim x$ , then

   $$ \begin{align*}C_{G\rtimes_\phi \mathbb{Z}}(x)= C_{G}(x).\end{align*} $$

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 }$ .

Theorem 3.4. There is an algorithm taking as input an automorphism $\phi \in \mathrm {Aut}(F_n)$ and an element $t^ax\in F_n\rtimes _\phi \mathbb {Z}$ that outputs a finite set of generators for $C_{F_n\rtimes _\phi \mathbb {Z}}(t^ax)$ .

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 [16, 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 [4, 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 [15, 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 [15, 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)$ .

Corollary 3.5. Let $\phi \in \mathrm {Aut}(F_n)$ and $t^au, \, t^bv\in F_n\rtimes _\phi \mathbb {Z}$ . The set of solutions to the equation $x^{-1}(t^au)x=t^bv$ is rational and effectively constructible.

Proof. Solving the conjugacy problem in $ F_n\rtimes _\phi \mathbb {Z}$ using [4, Theorem 1.1], we check if $t^au$ and $t^bv$ are conjugate. If not, there are no solutions; if they are conjugate, we compute a conjugator $t^cz$ and the set of solutions is $C_{F_n\rtimes _\phi \mathbb {Z}}(t^au)t^cz$ , which, by Theorem 3.4, is computable.

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 [15, 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.

Corollary 3.6. The conjugacy problem with context-free constraints is decidable for [f.g. free]-by-cyclic groups, that is, there is an algorithm taking as input any two elements $t^ax,\, t^by \in F_n\rtimes _{\phi }\mathbb {Z}$ and a context-free grammar generating a language L such that $L=K\pi ^{-1}$ for some $K\subseteq F_n\rtimes _\phi \mathbb {Z}$ , which decides whether there is an element ${t^cz\in K}$ such that $t^ax=(t^cz)^{-1}(t^by) t^c z$ .

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.

Problem 4.1. Can we understand what the class of context-free subsets of [f.g. free]-by-cyclic groups consists of? Is there any relation with the class of rational subsets?

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 [10], and both Brinkmann’s conjugacy problem and the twisted conjugacy problem are decidable [11]. So, a natural problem is the following one.

Problem 4.2. Are twisted conjugacy classes in Braid groups rational and computable?

We remark that it follows from the proof of [11, 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 [15]) and the twisted conjugacy problem is proved to be decidable in [7, 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 [6] for the computability of Fix( $\psi $ )) subsets of the virtually free group $G_1$ , and thus computable [19, 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 [7, Theorem 5.3].

Problem 4.3. Is Brinkmann’s conjugacy problem decidable for automorphisms of virtually free groups?

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.

Problem 4.4. Given an f.g. virtually free (or hyperbolic) group G, an automorphism $\phi \in \mathrm {Aut}(G)$ and an element $x\in G$ , can we decide whether there is some $k\neq 0$ such that $x\phi ^k\sim x$ ?