# TWISTED CONJUGACY IN DIHEDRAL ARTIN GROUPS I: TORUS KNOT GROUPS

Gemma Crowe

###### Abstract

In this paper we provide an alternative solution to a result by Juhász [11],
that the twisted conjugacy problem for odd dihedral Artin groups is solvable,
that is, groups with presentation $G(m)=\langle
a,b\;|\;_{m}(a,b)={}_{m}(b,a)\rangle$, where $m\geq 3$ is odd, and
${}_{m}(a,b)$ is the word $abab\dots$ of length $m$, is solvable. Our solution
provides an implementable linear time algorithm, by considering an alternative
group presentation to that of a torus knot group, and working with geodesic
normal forms. An application of this result is that the conjugacy problem is
solvable in extensions of odd dihedral Artin groups.

2020 Mathematics Subject Classification: 20F10, 20F36.

_Keywords_ : Twisted conjugacy problem, dihedral Artin groups, orbit
decidability, torus knot groups.

## INTRODUCTION

Over a century ago, Dehn defined his famous decision problems, which have been
studied across a wide range of groups. One of these is the _conjugacy problem_
, which asks if there exists an algorithm to determine if two elements in a
group, given by words on the generators, are conjugate. This decision problem
has been generalised to include an algebraic property known as _twisted
conjugacy_.

For a finitely generated group $G$ with generating set $X$, we say two
elements $u,v\in G$ are _twisted conjugate_ , by some automorphism
$\phi\in\mathrm{Aut}(G)$, if there exists an element $w\in G$ such that
$v=\phi^{-1}(w)uw$. The _twisted conjugacy problem_ (TCP) asks whether there
exists an algorithm to determine if two elements, given as words over $X$, are
twisted conjugate by some automorphism $\phi\in\mathrm{Aut}(G)$. Whilst the
TCP is a relatively new decision problem, in comparison to the conjugacy
problem, several important results have been established (see [1, 3, 6, 9]).
Note that a positive solution to the TCP implies a positive solution to the
conjugacy problem, however the converse is not necessarily true [2, Corollary
4.9].

In a series of two papers, we solve the TCP for dihedral Artin groups. Artin
groups are defined by a simple graph with edge labelling from
$\mathbb{Z}_{\geq 2}$. Despite their long history of study, there are still
open questions, such as the decidability of the word problem, which are not
known for all Artin groups. A typical approach to understand these open
problems is to consider subclasses of Artin groups, which are often defined
using conditions on the defining graph. Dihedral Artin groups are one such
class, and are defined by a simple graph with precisely two vertices and one
edge, that is, they have a group presentation $G(m)=\langle
a,b\;|\;_{m}(a,b)={}_{m}(b,a)\rangle$, where $m\geq 3$ and ${}_{m}(a,b)$ is
the word $abab\dots$ of length $m$.

These one-relator, torsion free groups are appealing to study from a
computational perspective, and recent studies have found interesting results
such as decidability of equations [5], and solvable conjugacy problem in
linear time [10]. We note here that the TCP for dihedral Artin groups was
already known to be solvable by Juhász [11], with respect to length preserving
automorphisms. To solve the TCP for dihedral Artin groups with respect to all
automorphisms, we consider when the edge labelling of our defining graph is
either odd or even. In this first paper, we focus on odd dihedral Artin groups
and further improve on Juhász’s result, by constructing an algorithm to check
if two words, representing group elements, are twisted conjugate. Moreover,
this algorithm has linear time complexity, based on the length of the input
words.

thmTCP The $\mathrm{TCP}(G(m))$, where $m$ is odd, $m\geq 3$, is solvable in
linear time. The key step is to utilise the fact that any odd dihedral Artin
group $G(m)$ is isomorphic to a _torus knot group_. In particular, $G(m)$ is
isomorphic to the group with presentation $\langle
x,y\;|\;x^{2}=y^{m}\rangle$, where $m$ is odd. With this presentation, we find
that the automorphism group of $G(m)$ is finite of order two. Moreover, we can
use a geodesic normal form derived by Fujii [7], to construct a linear time
algorithm to solve the $\mathrm{TCP}(G(m))$.

As an application of Section 1, we consider the conjugacy problem in
extensions of odd dihedral Artin groups, using a criteria from [2] (see 4.1).
This criteria requires understanding _orbit decidability_ for subgroups
$A\leq\mathrm{Aut}(G)$, for some group $G$. The _orbit decidability problem_
asks whether we can determine if for two elements $u,v\in G$, there exists an
automorphism $\phi\in A$ such that $v$ is conjugate to $\phi(u)$. To apply the
criteria from [2], we require what is known as the ‘action subgroup’ of odd
dihedral Artin groups to be orbit decidable. For odd dihedral Artin groups, we
prove a stronger statement, by showing that all subgroups of the automorphism
group of odd dihedral Artin groups are orbit decidable.

thmorbit Every finitely generated subgroup
$A\leq\mathrm{Aut}(\mathrm{DA}_{m})$, when $m$ is odd, is orbit decidable.
Combined with Section 1, we can find new examples of groups with solvable
conjugacy problem.

thmextension Let $G=\mathrm{DA}_{m}\rtimes H$ be an extension of an odd
dihedral Artin group by a finitely generated group $H$ which satisfies
conditions $(ii)$ and $(iii)$ from 4.1 (e.g. let $H$ be torsion-free
hyperbolic). Then $G$ has decidable conjugacy problem. We note that the
conjugacy problem is solvable for virtual dihedral Artin groups [5, Corollary
3.2], which proves Section 1 in the case where $H$ is finite.

The structure of this paper is as follows. After providing necessary details
on decision problems, twisted conjugacy and odd dihedral Artin groups in
Section 2, we construct a linear time solution to the TCP for odd dihedral
Artin groups in Section 3. Finally in Section 4, we study orbit decidability
in odd dihedral Artin groups, which allows us to use the criteria from [2] to
find new examples of group extensions of odd dihedral Artin groups with
solvable conjugacy problem.

## PRELIMINARIES

All groups in this paper are finitely generated, and all finite generating
sets are inverse-closed.

###  Decision problems and twisted conjugacy

Let $X$ be a finite set, and let $X^{\ast}$ be the set of all finite words
over $X$. For a group $G$ generated by $X$, we use $u=v$ to denote equality of
words in $X^{\ast}$, and $u=_{G}v$ to denote equality of the group elements
represented by $u$ and $v$. We let $l(w)$ denote the word length of $w$ over
$X$. For a group element $g\in G$, we define the _length_ of $g$, denoted
$|g|_{X}$, to be the length of a shortest representative word for the element
$g$ over $X$. A word $w\in X^{\ast}$ is _geodesic_ if $l(w)=|\pi(w)|_{X}$,
where $\pi\colon X^{\ast}\rightarrow G$ is the natural projection. If there
exists a unique word $w$ of minimal length representing $g$, then we say $w$
is a _unique geodesic_. Otherwise, $w$ is a non-unique geodesic.

######  Definition 2.1.

Let $G=\langle X\rangle$. The _word problem_ for $G$, denoted
$\mathrm{WP}(G)$, takes as input a word $w\in X^{\ast}$, and decides whether
it represents the trivial element of $G$. The _conjugacy problem_ for $G$,
denotes $\mathrm{CP}(G)$, takes as input two words $u,v\in X^{\ast}$, and
decides whether they represent conjugate elements in $G$. We write $u\sim v$
when $u$ and $v$ represent conjugate elements in $G$.

######  Definition 2.2.

Let $G=\langle X\rangle$, let $u,v\in X^{\ast}$, and let
$\phi\in\mathrm{Aut}(G)$ be an automorphism of $G$.

  1. 1.

We say $u$ and $v$ are _$\phi$ -twisted conjugate_, denoted $u\sim_{\phi}v$,
if there exists an element $w\in G$ such that $v=_{G}\phi(w)^{-1}uw$.

  2. 2.

The _$\phi$ -twisted conjugacy problem_ for $G$, denoted
$\mathrm{TCP}_{\phi}(G)$, takes as input two words $u,v\in X^{\ast}$, and
decides whether they represent groups elements which are $\phi$-twisted
conjugate to each other in $G$.

  3. 3.

The (uniform) _twisted conjugacy problem_ for $G$, denoted $\mathrm{TCP}(G)$,
takes as input two words $u,v\in X^{\ast}$, and decides whether $u$ and $v$
represent groups elements which are $\phi$-twisted conjugate in $G$, for some
$\phi\in\mathrm{Aut}(G)$.

Clearly a solution to the $\mathrm{TCP}(G)$ implies a solution to
$\mathrm{TCP}_{\phi}(G)$ for all $\phi\in\mathrm{Aut}(G)$, and therefore a
solution to the $\mathrm{CP}(G)$ and the $\mathrm{WP}(G)$. We first observe
that to solve the $\mathrm{TCP}(G)$, we can study the outer automorphism
group, rather than the automorphism group as a whole. This was originally
noted in [9].

######  Remark 2.3.

Let $\psi\circ\phi\in\mathrm{Aut}(G)$, where $\psi\in\mathrm{Inn}(G)$,
$\phi\in\mathrm{Out}(G)$. If $\phi$ is trivial, then the
$\mathrm{TCP}_{\psi}(G)$ is equivalent to solving the $\mathrm{CP}(G)$ by the
following relations:

$v=_{G}\psi(w)^{-1}uw\Leftrightarrow v=_{G}g^{-1}w^{-1}guw\Leftrightarrow
gv=_{G}w^{-1}(gu)w,$

for some $g\in G$. Otherwise, we have

$v=_{G}(\psi\circ\phi)(w)^{-1}uw\Leftrightarrow
v=_{G}g^{-1}\phi(w)^{-1}guw\Leftrightarrow gv=_{G}\phi(w)^{-1}(gu)w,$

for some $g\in G$. Therefore if $\phi\in\mathrm{Out}(G)$ is non-trivial, then
the $\mathrm{TCP}_{\psi\circ\phi}(G)$ is equivalent to solving the
$\mathrm{TCP}_{\phi}(G)$, for $\phi\in\mathrm{Out}(G)$.

######  Definition 2.4.

For any $\phi\in\mathrm{Aut}(G)$ of $G$, we say $\phi$ is:

  1. (i)

_length preserving_ if $l(w)=l(\phi(w))$ for any word $w\in X^{\ast}$, and

  2. (ii)

_non-length preserving_ otherwise.

For length preserving cases, $l(\phi(x))=1$ if and only if $x\in X$.

###  Odd dihedral Artin groups

######  Definition 2.5.

Let $m\in\mathbb{Z}_{>1}$. The dihedral Artin group is the group defined by
the following presentation:

$G(m)=\langle a,b\;|\;_{m}(a,b)={}_{m}(b,a)\rangle,$ (1)

where ${}_{m}(a,b)$ is the word $abab\dots$ of length $m$.

We first note the following result, which solves the
$\mathrm{TCP}_{\phi}(G(m))$ in the case where the automorphism
$\phi\in\mathrm{Aut}(G(m))$ is trivial.

######  Theorem 2.6.

[10, Proposition 3.1] The conjugacy problem is solvable in dihedral Artin
groups in linear time.

If $m=2$, then $G(m)$ is the free abelian group, and if $m=3$, then $G(m)$ is
the braid group $B_{3}$. We note that the twisted conjugacy problem has been
solved in both of these cases [2, 9]. For the remainder of this paper, we will
assume $m\geq 3$ is odd. To solve the TCP for $G(m)$, we will work with a
different generating set, which we now define.

######  Definition 2.7.

Let $G(m)$ denote the dihedral Artin group, with presentation given in Eq. 1.
For $m$ odd,

$G(m)\cong\langle x,y\;|\;x^{2}=y^{m}\rangle,$ (2)

by setting $x={}_{m}(a,b),y=ab$. Here $G(m)$ is isomorphic to a _torus knot
group_.

For notation we let $X=\\{x,y\\}$, and $m=2k+1$ for some $k\in\mathbb{Z}_{\geq
1}$. Before considering twisted conjugacy, we first need to understand the
outer automorphisms of this group.

######  Theorem 2.8.

[8, Theorem C] Let $G(m)$ be defined as Eq. 2. Then $\mathrm{Out}(G(m))\cong
C_{2}$.

In particular,
$\mathrm{Aut}(G(m))=\mathrm{Inn}(G(m))\sqcup\mathrm{Inn}(G(m))\cdot\phi$ where
$\phi\in\mathrm{Out}(G(m))$ inverts all generators, i.e.

$\phi\colon x\mapsto x^{-1},\;y\mapsto y^{-1}.$ (3)

For the remainder of this section, we assume $\phi\in\mathrm{Out}(G(m))$ is as
in Eq. 3. We let $\mathsf{rev}(w)$ denote the word $w\in X^{\ast}$ written in
reverse, and note that for any word $w\in X^{\ast}$,
$\phi(w)^{-1}=\mathsf{rev}(w)$. Indeed if $w=w^{a_{1}}_{i_{1}}\dots
w^{a_{n}}_{i_{n}}\in X^{\ast}$, where each $w_{i_{j}}\in X$ and
$a_{j}\in\mathbb{Z}_{\neq 0}$ $(1\leq j\leq n)$, then
$\phi(w)=w^{-a_{1}}_{i_{1}}\dots w^{-a_{n}}_{i_{n}}$, and so
$\phi(w)^{-1}=w^{a_{n}}_{i_{n}}\dots w^{a_{1}}_{i_{1}}=\mathsf{rev}(w)$.
Therefore checking if two elements are twisted conjugate reduces to checking
if $v=_{G}\mathsf{rev}(w)uw$.

We now provide a set of geodesic normal forms for $G(m)$. These were
originally derived from [7], and further details can be found in [4] and
Appendix A.

######  Proposition 2.9.

Any element can be represented by a geodesic word $u=x^{a_{1}}y^{b_{1}}\dots
y^{b_{\tau}}\Delta^{c}$, where $\Delta=_{G}x^{2}=_{G}y^{2k+1}$, with
conditions given in Table 1.

We refer to $\Delta$ as the _Garside element_ , and note that any power of
$\Delta$ is central.

######  Definition 2.10.

Let $u=x^{a_{1}}y^{b_{1}}\dots y^{b_{\tau}}\Delta^{c}\in X^{\ast}$ be
geodesic. We say $u$ is _Garside-free_ if $c=0$.

Let $u\in X^{\ast}$ be a geodesic, where $l(u)>1$. We can write $u$ in the
form $u=u_{1}u_{2}$ for some non-empty geodesic words $u_{1},u_{2}\in
X^{\ast}$. We say $u_{1}$ is a _proper prefix_ of $u$, and $u_{2}$ is a
_proper suffix_ of $u$. We let $\mathcal{P}(u)$ and $\mathcal{S}(u)$ be the
set of all possible proper prefixes and suffixes of $u$ respectively. With
these definitions, we can define an equivalent notion of cyclic permutations,
with respect to twisted conjugacy.

######  Definition 2.11.

Let $u\in X^{\ast}$ be a geodesic, where $l(u)>1$. Let $u=u_{1}u_{2}$ for some
$u_{1}\in\mathcal{P}(u),\;u_{2}\in\mathcal{S}(u)$. Let
$\phi\in\mathrm{Out}(G(m))$ as defined in Eq. 3. We define a _$\phi$ -cyclic
permutation of a prefix_ of $u$ to be the following operation on $u$:

$u=u_{1}u_{2}\mapsto u_{2}\phi(u_{1}).$

Similarly we define a _$\phi$ -cyclic permutation of a suffix_ of $u$ as

$u=u_{1}u_{2}\mapsto\phi(u_{2})u_{1}.$

For brevity, we will use $\xleftrightarrow{\phi}$ to denote a $\phi$-cyclic
permutation of either a prefix or suffix. We note that any $\phi$-cyclic
permutation can be reversed as follows:

$u_{1}u_{2}\mapsto u_{2}\phi(u_{1})\mapsto\phi(\phi(u_{1}))u_{2}=u_{1}u_{2}.$

If two geodesics $u,v\in X^{\ast}$ are related by a $\phi$-cyclic permutation,
then $u\sim_{\phi}v$.

## ALGORITHM FOR THE TWISTED CONJUGACY PROBLEM

To solve the $\mathrm{TCP}_{\phi}(G(m))$, where $\phi\in\mathrm{Out}(G(m))$ is
as in Eq. 3, we will show that every geodesic is twisted conjugate to a
minimal length twisted conjugacy representative which is Garside free.
Moreover, for two minimal representatives which are twisted conjugate, we will
show that they are related by a finite sequence of $\phi$-cyclic permutations
and equivalent geodesics. Since $\phi$ is length-preserving, this will lead to
our basic algorithm, which we later improve to give a linear time algorithm.

###  Garside free representatives

######  Definition 3.1.

Let $u\in X^{\ast}$ be geodesic. We say $u$ is of Type (3) if $u$ is not of
Type (1) or (2) (see Table 1). In particular, Type (3) geodesics are Garside
free (recall 2.10). We let $\overline{(3)}\subset(3)$ denote the set of all
words $u\in(3)$, such that $u$ starts and ends with opposite letters.

Our first step is to prove the following result, which shows that any geodesic
$u\in X^{\ast}$ can be transformed to a geodesic $u^{\prime}\in X^{\ast}$,
which is Garside free, such that $u\sim_{\phi}u^{\prime}$.

######  Proposition 3.2.

Let $u\in X^{\ast}$ be a geodesic. Then there exists a geodesic
$u^{\prime}\in\overline{(3)}$, such that $u\sim_{\phi}u^{\prime}$ and
$l(u^{\prime})\leq l(u)$.

We first consider some simple cases.

######  Lemma 3.3.

Let $u=x^{t}$ and $v=y^{t+mc}$, for some $t\in\mathbb{Z}_{\geq
0},c\in\mathbb{Z}$. Then

$\begin{split}u=x^{t}\sim_{\phi}\begin{cases}\varepsilon,&t\quad\text{is
even},\\\ x^{\pm 1},&t\quad\text{is
odd},\end{cases}\end{split}\quad\text{and}\quad\begin{split}v=y^{t+mc}\sim_{\phi}\begin{cases}\varepsilon,&c,t\quad\text{have
same parity},\\\ y^{\pm 1},&c,t\quad\text{have opposite
parity}.\end{cases}\end{split}$

###### Proof.

First consider $u=x^{t}$. If $t=2d$, for some $d\in\mathbb{Z}$, we can apply
the following $\phi$-cyclic permutation to $u$:

$u=_{G}x^{d}x^{d}\xleftrightarrow{\phi}x^{-d}x^{d}=_{G}\varepsilon.$

Similarly if $t=2d+1$, we have

$u=_{G}x^{d}x^{d+1}\xleftrightarrow{\phi}x^{-d}x^{d+1}=_{G}x\xleftrightarrow{\phi}x^{-1}.$

Now suppose $v=y^{t+mc}=_{G.}y^{t}\Delta^{c}$. If $c=2d$, for some
$d\in\mathbb{Z}$, then
$v=_{G}y^{t}\Delta^{2d}\xleftrightarrow{\phi}\Delta^{-d}y^{t}\Delta^{d}=_{G}y^{t}.$
If $t$ is even, then
$y^{t}\xleftrightarrow{\phi}y^{-t/2}y^{t/2}=_{G}\varepsilon$. Similarly if $t$
is odd, then $y^{t}\xleftrightarrow{\phi}y^{\pm 1}$. Otherwise, if $c=2d+1$,
then
$v=y^{t}\Delta^{2d+1}\xleftrightarrow{\phi}\Delta^{-d}y^{t}\Delta\Delta^{d}=_{G}y^{t}\Delta=y^{t+m}.$
If $t$ is odd, then $t+m$ is even, and so
$y^{t+m}\xleftrightarrow{\phi}\varepsilon$. Similarly if $t$ is even, then
$t+m$ is odd and so $y^{t+m}\xleftrightarrow{\phi}y^{\pm 1}$. ∎

To prove 3.2, we will construct a set of rewriting rules which can be
repeatedly applied to a geodesic $u\in X^{\ast}$ to obtain an element
$u^{\prime}\in\overline{(3)}$. These rules are invariant under $\sim_{\phi}$,
that is, after applying a sequence of these rules to $u$, we obtain a word
$u^{\prime}\in\overline{(3)}$ such that $u\sim_{\phi}u^{\prime}$. Let $v\in
X^{\ast}$ such that $v$ is Garside free, let $x,y\in X$ and
$\epsilon,\epsilon_{1},\epsilon_{2}\in\\{\pm 1\\}$. We define our set of
rewrite rules as follows.

  * (R1):

$v\Delta^{c}\rightarrow\begin{cases}v,&c=2d,\;d\in\mathbb{Z}_{\neq 0},\\\
v\Delta,&c=2d+1,\;d\in\mathbb{Z}_{\neq 0}.\end{cases}$

  * (R2):

For $c\in\\{-1,0,1\\}$,
$x^{\epsilon_{1}}vx^{\epsilon_{2}}\Delta^{c}\rightarrow\begin{cases}v\Delta^{c},&\epsilon_{1}=\epsilon_{2},\\\
v\Delta^{c+\epsilon},&\epsilon_{1}\neq\epsilon_{2}.\end{cases}$

  * (R3):

For $c\in\\{-1,0,1\\}$,
$y^{b_{1}}vy^{b_{n}}\Delta^{c}\rightarrow\begin{cases}y^{b_{1}-b_{n}}v\Delta^{c}&b_{1}-b_{n}\in[-(m-1),m-1]\cap\mathbb{Z}_{\neq
0},\\\ v\Delta^{c},&b_{1}=b_{n},\\\
v\Delta^{c+\epsilon},&|b_{1}-b_{n}|=m.\end{cases}$

  * (R4):

$x^{\epsilon_{1}}vy^{b}\Delta^{\epsilon_{2}}\rightarrow
x^{-\epsilon_{1}}vy^{b}$.

  * (R5):

$y^{b}vx^{\epsilon_{1}}\Delta^{\epsilon_{2}}\rightarrow
y^{b}vx^{-\epsilon_{1}}$.

All rules either preserve or decrease word length.

######  Proposition 3.4.

The rules (R1)-(R5) are invariant under $\sim_{\phi}$.

###### Proof.

Each rule can be obtained by applying $\phi$-cyclic permutations and relations
from $G(m)$ as follows.

  1. (R1):

If $c=2d$, then
$v\Delta^{2d}\xleftrightarrow{\phi}\Delta^{-d}v\Delta^{d}=_{G}v$. If $c=2d+1$,
then
$v\Delta^{2d+1}\xleftrightarrow{\phi}\Delta^{-d}v\Delta^{d}\Delta=_{G}v\Delta$.

  2. (R2):

$x^{\epsilon_{1}}vx^{\epsilon_{2}}\Delta^{c}=_{G}x^{\epsilon_{1}}v\Delta^{c}x^{\epsilon_{2}}\xleftrightarrow{\phi}x^{\epsilon_{1}-\epsilon_{2}}v\Delta^{c}$.
This is equivalent to $v\Delta^{c}$ when $\epsilon_{1}=\epsilon_{2}$, and
$x^{\pm 2}v\Delta^{c}=_{G}v\Delta^{c\pm 1}$ when
$\epsilon_{1}\neq\epsilon_{2}$.

  3. (R3):

$y^{b_{1}}vy^{b_{n}}\Delta^{c}=_{G}y^{b_{1}}v\Delta^{c}y^{b_{n}}\xleftrightarrow{\phi}y^{b_{1}-b_{n}}v\Delta^{c}$.
The result then follows since $y^{m}=\Delta$.

  4. (R4):

If $\epsilon_{1}=\epsilon_{2}$, then
$x^{\epsilon_{1}}vy^{b}\Delta^{\epsilon_{2}}=x^{\epsilon_{1}}vy^{b}x^{2\epsilon_{1}}\xleftrightarrow{\phi}x^{\epsilon_{1}-2\epsilon_{1}}vy^{b}=_{G}x^{-\epsilon_{1}}vy^{b}$.
Otherwise, if $\epsilon_{1}=-\epsilon_{2}$, then
$x^{\epsilon_{1}}vy^{b}\Delta^{\epsilon_{2}}=x^{\epsilon_{1}}vy^{b}x^{-2\epsilon_{1}}=_{G}x^{-\epsilon_{1}}vy^{b}$.
(R5) follows a similar proof.

∎

###### Proof of 3.2.

Assume $u\not\in\overline{(3)}$. If $u$ contains only $x$ or $y$ factors, then
we obtain $u^{\prime}\in\\{\varepsilon,x^{\pm 1},y^{\pm 1}\\}$, such that
$u\sim_{\phi}u^{\prime}$, based on the conditions given in Lemma 3.3.

We can therefore assume $u$ contains both $x$ and $y$ factors, and so
$u=u_{1}\Delta^{c}$, where $u_{1}\in(3)$ is Garside free, and
$c\in\mathbb{Z}$. We apply the following sequence of rewrite rules, to obtain
an element $u^{\prime}\in\overline{(3)}$:

  1. 1.

If $c\neq 0$, apply (R1) to obtain an element of the form $v$ or $v\Delta$.

  2. 2.

If $v$ starts and ends with the same letter, then repeatedly apply (R2)-(R3),
to obtain an element of the form $v$ or $v\Delta^{\pm 1}$, where
$v\in\overline{(3)}$. If, after any application of (R2)-(R3), we obtain an
element of the form $v\Delta^{\pm 2}$, then return to Step 1 and apply (R1).

  3. 3.

If, after Step 2, we obtain $v\Delta^{\pm 1}$ where $v\in\overline{(3)}$, then
apply (R4) or (R5) to obtain an element $v\in\overline{(3)}$.

By 3.4, $u$ is twisted conjugate to the output of this sequence of rewrite
rules. Since (R1)-(R5) either preserves or decreases word length, then
$l(u^{\prime})\leq l(u)$. ∎

###  Twisted cyclic geodesics

We now consider which elements of Type $\overline{(3)}$, as defined in 3.1,
are minimal length up to twisted cyclic permutations.

######  Definition 3.5.

Let $G=G(m)$ be a group with presentation as in Eq. 2. We define the set of
_twisted cyclic geodesics_ , denoted $\mathsf{CycGeo}_{\phi}(G,X)$, to be the
set of all geodesics $u\in X^{\ast}$, such that every $\phi$-cyclic
permutation of $u$ is also geodesic.

Let
$\mathsf{CycGeo}_{\phi,\overline{(3)}}(G,X)=\mathsf{CycGeo}_{\phi}(G,X)\cap\;\text{Type}\;\overline{(3)}$
be the set of all twisted cyclic geodesics of Type $\overline{(3)}$. The
following example highlights that when we apply a $\phi$-cyclic permutation to
$u\in\overline{(3)}$, we can obtain a word which is no longer geodesic.

######  Example 3.6.

Suppose $m=5$, and consider $u=y^{-3}x^{-1}\in X^{\ast}$, which is geodesic of
length 4. We can take a twisted cyclic permutation of $u$ by applying the
$\phi$-cyclic permutation
$u=y^{-3}x^{-1}\xleftrightarrow{\phi}\phi\left(x^{-1}\right)y^{-3}=xy^{-3}=u^{\prime}.$
Here $u^{\prime}$ is not geodesic, since $u^{\prime}=_{G}x^{-1}y^{2}$, which
is of length 3.

To consider when words of Type $\overline{(3)}$ lie in
$\mathsf{CycGeo}_{\phi,\overline{(3)}}(G,X)$, we first consider when geodesics
of Type (3) are geodesic.

######  Definition 3.7.

For $u=x^{a_{1}}y^{b_{1}}\dots x^{a_{\tau}}y^{b_{\tau}}\in(3)$, define

$\displaystyle\mathrm{Pos}_{x}(u)$
$\displaystyle:=\mathrm{max}\\{a_{i}\;:\;a_{i}\geq 0,1\leq
i\leq\tau\\},\quad\mathrm{Neg}_{x}(u)$
$\displaystyle:=\mathrm{max}\\{-a_{i}\;:\;a_{i}\leq 0,1\leq i\leq\tau\\},$
$\displaystyle\mathrm{Pos}_{y}(u)$
$\displaystyle:=\mathrm{max}\\{b_{i}\;:\;b_{i}\geq 0,1\leq
i\leq\tau\\},\quad\mathrm{Neg}_{y}(u)$
$\displaystyle:=\mathrm{max}\\{-b_{i}\;:\;b_{i}\leq 0,1\leq i\leq\tau\\}.$

######  Proposition 3.8.

[7, Proposition 3.5] Let $u\in(3)$ be geodesic. Then the following conditions
must all be satisfied:

  1. 1.

$\mathrm{Pos}_{x}(u)+\mathrm{Neg}_{x}(u)\leq 2$.

  2. 2.

$\mathrm{Pos}_{y}(u)+\mathrm{Neg}_{y}(u)\leq 2k+1$.

  3. 3.

$\mathrm{Pos}_{x}(u)+\mathrm{Neg}_{y}(u)\leq k+1$.

  4. 4.

$\mathrm{Pos}_{y}(u)+\mathrm{Neg}_{x}(u)\leq k+1$.

Suppose $u\in\overline{(3)}$ is geodesic and
$u\xleftrightarrow{\phi}u^{\prime}$ for some $u^{\prime}\in X^{\ast}$. We want
to establish when $u^{\prime}$ is geodesic, and hence
$u\in\mathsf{CycGeo}_{\phi,\overline{(3)}}(G,X)$. Let
$u=x^{a_{1}}y^{b_{1}}\dots x^{a_{\tau}}y^{b_{\tau}}\in\overline{(3)}$ and
consider a $\phi$-cyclic permutation of the form

$u^{\prime}=x^{-a_{i}}y^{-b_{i}}\dots
x^{-a_{\tau}}y^{-b_{\tau}}x^{a_{1}}y^{b_{1}}\dots x^{a_{i-1}}y^{b_{i-1}},$

for some $1\leq i\leq\tau$. We consider each of the 4 conditions from 3.8,
when applied to $u^{\prime}$.

The first condition is immediate, since $\mathrm{Pos}_{x}(w)\leq 1$ and
$\mathrm{Neg}_{x}(w)\leq 1$ for all words $w\in X^{\ast}$. Since $u^{\prime}$
contains at least one $x^{\pm 1}$ term, then by Conditions 3 and 4, there
cannot be any $y^{\pm(k+1)}$ terms in $u^{\prime}$. Condition 2 always holds
with this restriction. This immediately implies that for $u^{\prime}$ to be
geodesic, then $u$ cannot be of Type $(3^{0+}N)$ or $(3^{0-}N)$ (recall Table
1), since both of these require the existence of $y^{\pm(k+1)}$ terms. This
allows us to fully classify twisted cyclic geodesics of Type $\overline{(3)}$.

######  Corollary 3.9.

Let $\left(3^{++}\right)=\left(3^{+}\right)\cup\left(3^{0+}U\right)$, and let
$\left(3^{--}\right)=\left(3^{-}\right)\cup\left(3^{0-}U\right)$. Then

$\mathsf{CycGeo}_{\phi,\overline{(3)}}(G,X)=\\{u\in\left(3^{++}\right)\cup\left(3^{--}\right)\cup\left(3^{0*}\right)\;|\;u\;\text{starts
and ends with opposite factors}\\}.$

In particular, if $u=x^{a_{1}}y^{b_{1}}\dots
x^{a_{\tau}}y^{b_{\tau}}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}(G,X)$, then
$u$ satisfies the following conditions:

  1. (i)

$a_{1}=0$ if and only if $b_{\tau}=0$,

  2. (ii)

$-k\leq b_{i}\leq k\;(1\leq i\leq\tau),\;b_{i}\neq 0\;(1\leq i\leq\tau-1)$,
and

  3. (iii)

$\begin{cases}0\leq a_{i}\leq 1\;(1\leq i\leq\tau),&a_{i}\neq 0\;(2\leq
i\leq\tau),\;u\in(3^{++}),\\\ -1\leq a_{i}\leq 0\;(1\leq i\leq\tau),&a_{i}\neq
0\;(2\leq i\leq\tau),\;u\in(3^{--}),\\\ -1\leq a_{i}\leq 1\;(1\leq
i\leq\tau),&a_{i}\neq 0\;(2\leq i\leq\tau),\;\text{there exist
both}\;x,x^{-1}\;\text{terms},\;u\in(3^{0*}).\end{cases}$

For notation, we let
$\mathsf{CycGeo}_{\phi,\overline{(3)}}=\mathsf{CycGeo}_{\phi,\overline{(3)}}(G,X)$.

######  Lemma 3.10.

Let $u\in\overline{(3)}$. Then there exists
$u^{\prime}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$ such that
$u\sim_{\phi}u^{\prime}$ and $l(u)\geq l(u^{\prime})$.

###### Proof.

By the previous discussion, we only need to consider words
$u\in\overline{(3)}$ which contain any $y^{\pm(k+1)}$ terms. For $\epsilon=\pm
1$, we can first rewrite all pairs
$\left(y^{\varepsilon(k+1)},y^{-\epsilon(k+1)}\right)$ as $\left(y^{-\epsilon
k},y^{\epsilon k}\right)$, until we are left only with $y^{k+1}$ terms or
$y^{-(k+1)}$ terms (see A.1). Then, we can take a $\phi$-cyclic permutation,
which switches all $y^{\epsilon(k+1)}$ terms to $y^{-\epsilon(k+1)}$, and then
apply the following rewrite rule to obtain a word
$u^{\prime}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$:

$sx^{\epsilon}ty^{-\epsilon(k+1)}z=_{G}sx^{2\epsilon}x^{-\epsilon}ty^{-\epsilon(2k+1)}y^{\epsilon
k}z=_{G}sx^{-\epsilon}ty^{\epsilon k}z,$ (4)

where $s,t,z\in X^{\ast}$. ∎

We also have to consider when non-unique geodesics can occur in
$\mathsf{CycGeo}_{\phi,\overline{(3)}}$.

######  Proposition 3.11.

[7, Proposition 3.8]
Let $u\in(3)$ be geodesic. Then $u$ is a non-unique geodesic representative if
at least one of the following conditions is satisfied:

  1. 1.

There exists both $x$ and $x^{-1}$ terms in $u$, or

  2. 2.

$\mathrm{Pos}_{y}(u)+\mathrm{Neg}_{y}(u)=m$.

######  Corollary 3.12.

Let $u\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$ be a non-unique geodesic. Then
the only rewrite rule we can apply to $u$ is that of the form

$sx^{\epsilon}tx^{-\epsilon}z=_{G}sx^{2\epsilon}x^{-\epsilon}tx^{-2\epsilon}x^{\epsilon}z=_{G}sx^{-\epsilon}tx^{\epsilon}z,$
(5)

where $\epsilon=\pm 1,s,t,z\in X^{\ast}$.

###### Proof.

For any $y^{b}$ factor in $u$, we have that $|b|\leq k$ by 3.9, and so
Condition 2 of 3.11 is never satisfied. For the first condition, the only
rewrite rule we can apply is Eq. 5, for all pairs of $\left(x,x^{-1}\right)$
terms. ∎

######  Remark 3.13.

We note that if $u\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$, then $u$ is a
non-unique geodesic precisely when $u\in\left(3^{0*}\right)$. Eq. 5 allows us
to check quickly if two geodesics
$u,v\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$ represent the same element. In
particular, if $u=x^{a_{1}}y^{b_{1}}\dots
x^{a_{\tau_{u}}}y^{b_{\tau_{u}}},\;v=x^{\alpha_{1}}y^{\beta_{1}}\dots
x^{\alpha_{\tau_{v}}}y^{\beta_{\tau_{v}}}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$,
then $u=_{G}v$ if and only if $\tau_{u}=\tau_{v}$, $b_{i}=\beta_{i}$ for all
$1\leq i\leq\tau_{u}$, and the sets $X_{u}=\\{a_{1},\dots,a_{\tau_{u}}\\}$ and
$X_{v}=\\{\alpha_{1},\dots,\alpha_{\tau_{u}}\\}$ are equal.

The following result highlights that if
$u\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$ is a non-unique geodesic, then any
equivalent word $u^{\prime}=_{G}u$ is also of minimal length up to twisted
cyclic permutations.

######  Lemma 3.14.

Let $u\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$, and suppose
$u=_{G}u^{\prime}$ for some geodesic $u^{\prime}\in X^{\ast}$. Then
$u^{\prime}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$.

###### Proof.

If $u$ is uniquely geodesic we are done, so suppose $u$ is a non-unique
geodesic. From 3.12, we only need to consider rewriting of the form in Eq. 5.
Assume $u$ is of the form $u=sxtx^{-1}z$, for some $s,t,z\in X^{\ast}$, and
$u^{\prime}=sx^{-1}txz=_{G}u$. We now check if all $\phi$-cyclic permutations
of $u^{\prime}$ are geodesic. All $\phi$-cyclic permutations of $u^{\prime}$
are equivalent to a $\phi$-cyclic permutation of $u$, which are geodesic by
assumption, except for the following cases.

  1. (i)

$u^{\prime}=sx^{-1}txz\xleftrightarrow{\phi}x^{-1}\phi(z)sx^{-1}t=v_{1}$. The
only possibility for $v_{1}$ to not be geodesic is if there exists a
$y^{\beta}$ factor in either $\phi(z),s$ or $t$, where $\beta=\pm(k+1)$. This
however is impossible since $u\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$, so no
$y^{\beta}$ terms in $s,t$, and $z$ can equal $y^{\pm(k+1)}$.

  2. (ii)

$u^{\prime}=sx^{-1}txz\xleftrightarrow{\phi}txz\phi(s)x=v_{2}$. A similar
argument to (i) shows $v_{2}$ must also be geodesic.

A symmetric argument holds in the case where $u=sx^{-1}txz$. ∎

With this set $\mathsf{CycGeo}_{\phi,\overline{(3)}}$ of minimal length
twisted conjugacy representatives, we can show that a finite sequence of
$\phi$-cyclic permutations and equivalent geodesics exists between any two
twisted conjugate elements which lie in
$\mathsf{CycGeo}_{\phi,\overline{(3)}}$.

######  Theorem 3.15.

Let $u,v\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$. Then $u\sim_{\phi}v$ if and
only if $l(u)=l(v)$ and there exists a finite sequence
$u=u_{0},u_{1},\dots,u_{s}=v$, such that $u_{i}\leftrightarrow u_{i+1}$ via a
$\phi$-cyclic permutation or an equivalent geodesic, for all $0\leq i\leq
s-1$.

###### Proof.

The reverse implication is clear by 2.11 and Lemma 3.14. For the forward
direction, assume $v=_{G}\phi(w)^{-1}uw=\mathsf{rev}(w)uw$ for some $w\in
X^{\ast}$. We assume $w$ is written in geodesic form, as defined in Table 1.
We consider different cases for $w\in X^{\ast}$.

Case 1: $w=\Delta^{c}$.
Suppose $v=_{G}\mathsf{rev}(\Delta^{c})u\Delta^{c}=_{G}u\Delta^{2c}$. Without
loss of generality, assume $c>0$. Since
$v\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$, $v$ is Garside free, so there
exists free cancellation between $u$ and $\Delta^{2c}$. First, note that no
cancellation of $\Delta^{2c}$ can occur with any $y$ factors in $u$. If this
were the case, we’d have

$v=_{G}u\Delta^{2c}=sy^{b_{i}}t\Delta^{2c}=_{G}sy^{b_{i}+m}y^{-m}t\Delta^{2c}=_{G}sy^{b_{i}+m}t\Delta^{2c-1},$

for some $b_{i}$ where $-k\leq b_{i}<0$, and some $s,t\in X^{\ast}$. Since
$b_{i}+m\geq k+1$, and no $y^{\beta}$ term, where $|\beta|>k$, can occur in
$v$ by 3.9, then either this type of cancellation cannot occur, or we need to
reverse this rewrite. Since $c>0$, the only way we can do this is through the
existence of an $x^{-1}$ term in $u$. If this is the case, we can apply the
following rewrite:

$v=_{G}u\Delta^{2c}=sx^{-1}ty^{b_{i}}z\Delta^{2c}=_{G}sx^{-1}ty^{b_{i}+m}z\Delta^{2c-1}=_{G}sx^{-2}xty^{b_{i}}y^{m}z\Delta^{2c-1}=_{G}sxty^{b_{i}}z\Delta^{2c-1},$
(6)

where $s,t,z\in X^{\ast}$. From Eq. 6, we note that we can skip the middle
step, and lower the power of the Garside element using the $x^{-1}$ term
directly, whilst leaving all $y$ terms unchanged. Therefore, we can assume
that no $y$ factors cancel with $\Delta^{2c}$, and that there exists $2c$
$x^{-1}$ terms in $u$, which cancel with $\Delta^{2c}$, to give a Garside free
element as required.

Let $u_{x}=\\{a_{1},\dots,a_{\tau}\\}$ denote the multiset of exponents of $x$
factors in $u$. Similarly let $v_{x}$ be the multiset of exponents of $x$
factors in $v$. By the previous observation, there exists a (possibly non-
unique) set $I=\\{a_{i_{1}},\dots,a_{i_{2c}}\\}\subseteq u_{x}$, such that
$v_{x}=\phi(I)\sqcup u_{x}\setminus I$, where
$\phi(I)=\\{-a_{i_{1}},\dots,-a_{i_{2c}}\\}$. In other words, we take a subset
$I\subseteq u_{x}$, such that all exponents $a_{i}\in I$ correspond to
$x^{-1}$ terms which cancel with $\Delta^{2c}$, by repeatedly applying
$x^{-1}\Delta=x$. In particular, all values $a_{p}\in I$ equal -1, and all
values $a_{q}\in\phi(I)$ equal 1 (for $i_{1}\leq p,q\leq i_{2c})$. We can
write $I=I_{1}\sqcup I_{2}$ as two disjoint sets of equal size:

$I_{1}=\\{a_{i_{1}},\dots,a_{i_{c}}\\},\quad
I_{2}=\\{a_{i_{c+1}},\dots,a_{i_{2c}}\\}.$

Let $u=_{G}u_{1}u_{2}$ such that $u_{1},u_{2}\in X^{\ast}$ are geodesics, such
that all $x$ factors with exponents in $I_{1}$ lie in $u_{1}$, and similarly
$x$ factors with exponents in $I_{2}$ lie in $u_{2}$. By applying
$x^{-1}\Delta=x$ to all $x$ factors in $u$ with exponents in $I$, we can write
$v$ in the form $v=_{G}u_{1}u_{2}\Delta^{2c}=_{G}v_{1}v_{2}$, for some
geodesic words $v_{1},v_{2}\in X^{\ast}$ such that $v_{1}v_{2}\in X^{\ast}$ is
also geodesic. Note
$u_{1}u_{2},v_{1}v_{2}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$ by Lemma 3.14.
We now have

$u=_{G}\underbrace{u_{1}}_{I_{1}}\underbrace{u_{2}}_{I_{2}},\quad
v=_{G}\underbrace{v_{1}}_{\phi(I_{1})}\underbrace{v_{2}}_{\phi(I_{2})}.$

Here $v_{1}$ contains all $x$ factors with exponents from $\phi(I_{1})$, that
is all $x$ factors in $u_{1}$ with exponents in $I_{1}$, which have now been
rewritten. Similarly $v_{2}$ contains all $x$ factors with exponents from
$\phi(I_{2})$, that is all $x$ factors in $u_{2}$ with exponents in $I_{2}$,
which have now been rewritten. In other words, $u_{1}$ is equal to $v_{1}$ as
a word, up to applying $\phi$ to all $x$ factors with exponents in $I_{1}$,
and similarly $u_{2}$ is equal to $v_{2}$ as a word, up to applying $\phi$ to
all $x$ factors with exponents in $I_{2}$. We will denote this property by
$u_{1}\cong_{1}v_{1}$ and $u_{2}\cong_{2}v_{2}$.

We want to show that there exists a sequence from $v$ to $u$ of $\phi$-cyclic
permutations and equivalent geodesics. First, we can apply the following
$\phi$-cyclic permutation to $v_{1}v_{2}$:

$v=_{G}\underbrace{v_{1}}_{\phi(I_{1})}\underbrace{v_{2}}_{\phi(I_{2})}\xleftrightarrow{\phi}\underbrace{\phi(v_{2})}_{I_{2}}\underbrace{v_{1}}_{\phi(I_{1})}=v^{\prime}.$

Here $v^{\prime}$ has $c$ $x^{-1}$ terms in $\phi(v_{2})$ corresponding to
$I_{2}$, and $c$ $x$ terms in $v_{1}$ corresponding to $\phi(I_{1})$. These
powers can be switched with each other, by repeatedly applying Eq. 5.
Equivalently, we can apply $\phi$ to all $x$ factors with exponents
corresponding to $I_{2}$ and $\phi(I_{1})$. This gives us a word of the form
$\overline{\phi(v_{2})}\overline{v_{1}}$, where
$\phi(v_{2})\cong_{2}\overline{\phi(v_{2})}$ and
$v_{1}\cong_{1}\overline{v_{1}}$. This leaves us with

$v=_{G}\underbrace{v_{1}}_{\phi(I_{1})}\underbrace{v_{2}}_{\phi(I_{2})}\xleftrightarrow{\phi}\underbrace{\phi(v_{2})}_{I_{2}}\underbrace{v_{1}}_{\phi(I_{1})}=_{G}\underbrace{\overline{\phi(v_{2})}}_{\phi(I_{2})}\underbrace{\overline{v_{1}}}_{I_{1}}.$

Again note
$\overline{\phi(v_{2})}\overline{v_{1}}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$
by Lemma 3.14. Finally, we can apply another $\phi$-cyclic permutation to
obtain a word equivalent to $u$:

$v=_{G}\underbrace{v_{1}}_{\phi(I_{1})}\underbrace{v_{2}}_{\phi(I_{2})}\xleftrightarrow{\phi}\underbrace{\phi(v_{2})}_{I_{2}}\underbrace{v_{1}}_{\phi(I_{1})}=_{G}\underbrace{\overline{\phi(v_{2})}}_{\phi(I_{2})}\underbrace{\overline{v_{1}}}_{I_{1}}\xleftrightarrow{\phi}\underbrace{\overline{v_{1}}}_{I_{1}}\underbrace{\overline{v_{2}}}_{I_{2}}=u_{1}u_{2}=_{G}u$

The last equality holds by the following observation. Since
$u_{1}\cong_{1}v_{1}\cong_{1}\overline{v_{1}}$, then $u_{1}=\overline{v_{1}}$,
since $\phi$ is of order 2. Similarly since
$\phi(v_{2})\cong_{2}\overline{\phi(v_{2})}$, then
$v_{2}\cong_{2}\overline{v_{2}}$. Hence
$u_{2}\cong_{2}v_{2}\cong_{2}\overline{v_{2}}$, and so
$u_{2}=\overline{v_{2}}$, which completes this case.

Case 2: $w$ is Garside free.
Suppose $v=_{G}\mathsf{rev}(w)uw$, where $w$ is Garside free. Since $v$ starts
and ends with opposite factors, there exists free cancellation in
$\mathsf{rev}(w)uw$. Moreover, this cancellation occurs either in
$\mathsf{rev}(w)u$ or $uw$, but not both, since $u$ starts and ends with
opposite factors. Assume free cancellation occurs in $uw$. We let
$u=_{G}u_{1}u_{2},\;w=_{G}u^{-1}_{2}z.$ Then we can write
$v=_{G}\mathsf{rev}(z)\mathsf{rev}\left(u^{-1}_{2}\right)u_{1}z$. Since
$u_{1}u_{2}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$ by Lemma 3.14, the
subword $\mathsf{rev}\left(u^{-1}_{2}\right)u_{1}=\phi(u_{2})u_{1}$ must be
geodesic. Assuming $u_{2}$ is maximal, we can assume $z$ is empty, since $v$
starts and ends with opposite factors. Therefore
$v=_{G}\mathsf{rev}\left(u^{-1}_{2}\right)u_{1}$ and we obtain our required
sequence of $\phi$-cyclic permutations and equivalent geodesics as follows:

$v=_{G}\mathsf{rev}\left(u^{-1}_{2}\right)u_{1}\xleftrightarrow{\phi}u_{1}\phi\left(\mathsf{rev}\left(u^{-1}_{2}\right)\right)=u_{1}u_{2}=_{G}u.$

A similar proof holds when cancellation occurs in $\mathsf{rev}(w)u$.

Case 3: All remaining cases.
Assume $w=w_{1}\Delta^{c}$ is a geodesic of Type 1 or 2, and so
$v=_{G}\mathsf{rev}(w_{1})uw_{1}\Delta^{2c}$. Without loss of generality,
assume $w$ is of Type 1, that is $c>0$ and all $x$ factors in $w_{1}$ have
positive powers. In this situation, there can exist either free cancellation
within $\mathsf{rev}(w_{1})uw_{1}$, or we can rewrite factors of
$\mathsf{rev}(w_{1})uw_{1}$ with the Garside element. We first consider free
cancellation in $\mathsf{rev}(w_{1})uw_{1}$. Similar to Case 2, we assume
$u=_{G}u_{1}u_{2},\;w_{1}=_{G}u^{-1}_{2}z,$ and hence

$v=_{G}\mathsf{rev}(z)\mathsf{rev}\left(u^{-1}_{2}\right)u_{1}z\Delta^{2c}.$

If $z$ is the empty word, then
$v=_{G}\mathsf{rev}\left(u^{-1}_{2}\right)u_{1}\Delta^{2c}$. Here we can apply
Case 1 to obtain a sequence of $\phi$-cyclic permutations and equivalent
geodesics between $v$ and $\mathsf{rev}(u^{-1}_{2})u_{1}$. Then since
$\mathsf{rev}(u^{-1}_{2})u_{1}\xleftrightarrow{\phi}u_{1}u_{2}=_{G}u$, we have
that $u$ and $v$ are related by a sequence of $\phi$-cyclic permutations and
equivalent geodesics.

Otherwise, suppose $z$ is not empty. We use similar techniques to Case 1, by
considering rewriting $x$-factors from
$\mathsf{rev}(z)\mathsf{rev}\left(u^{-1}_{2}\right)u_{1}z$ with the Garside
element, as follows. The only rewrite rule we can apply is Eq. 5, however we
note that all $x^{-1}$ terms which cancel with $\Delta^{2c}$ must come from
the subword $\mathsf{rev}\left(u^{-1}_{2}\right)u_{1}$. This is because $w$ is
of Type 1, and so all $x$ factors in $z$ have a positive exponent. After
cancellation with the Garside element, we can rewrite $v$ as

$v=_{G}\mathsf{rev}(z)\overline{\mathsf{rev}\left(u^{-1}_{2}\right)u_{1}}z,$

after $2c$ $x^{-1}$ terms from $\mathsf{rev}\left(u^{-1}_{2}\right)u_{1}$ have
cancelled with the Garside element. Since $v$ starts and ends with opposite
letters, we can assume
$v=_{G}\overline{\mathsf{rev}\left(u^{-1}_{2}\right)u_{1}}$, and from here we
can apply the same proof as Case 1. A similar proof holds when free
cancellation occurs in $\mathsf{rev}(w_{1})u$, or when we rewrite factors of
$\mathsf{rev}(w_{1})uw_{1}$. ∎

######  Proposition 3.16.

The $\mathrm{TCP}_{\phi}(G(m))$, where $m$ is odd, $m\geq 3$, with respect to
$\phi\colon x\mapsto x^{-1},y\mapsto y^{-1}$, is solvable.

###### Proof.

A summary of our algorithm is as follows.

Input:

  1. (i)

$m\in\mathbb{Z}_{\geq 3}$ which is odd.

  2. (ii)

Words $u,v\in X^{\ast}$ representing group elements.

  3. (iii)

$\phi\colon x\mapsto x^{-1},y\mapsto y^{-1}\in\mathrm{Out}(G(m))$.

Step 1: Geodesic form Write $u,v$ in geodesic forms
$\overline{u},\overline{v}$ respectively, given by Table 1. Step 2: Simple
cases If $\overline{u}$ or $\overline{v}$ is of the form $x^{a}$ or $y^{b}$,
then apply Lemma 3.3 to determine if $\overline{u}$ and $\overline{v}$ are
twisted conjugate. Otherwise, we can assume $\overline{u},\overline{v}$
contain at least one $x$ and $y$ factor. Step 3: Twisted cyclic geodesics
Apply $\phi$-cyclic permutations and geodesic reductions to obtain
$\overline{u}_{\min},\overline{v}_{\min}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$,
such that $\overline{u}\sim_{\phi}\overline{u}_{\min}$ and
$\overline{v}\sim_{\phi}\overline{v}_{\min}$ (existence follows from 3.2 and
Lemma 3.10). If $l(\overline{u}_{\min})\neq l(\overline{v}_{\min})$, then
Output = False (by 3.15). Step 4: Set of representatives Compute all possible
sequences of $\phi$-cyclic permutations and equivalent words from
$\overline{u}_{\min}$, to get a finite set $\mathcal{D}$ of minimal length
twisted conjugacy representatives. If $\overline{v}_{\min}\in\mathcal{D}$,
then Output = True. Otherwise, Output = False (by 3.15). ∎

######  Example 3.17.

We illustrate Step 4 of our algorithm, by considering the group
$G(3)=\langle x,y\>|\;x^{2}=y^{3}\rangle$, and the word $u=x^{-1}yx^{-1}y\in
X^{\ast}$. Here $u\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$ by 3.9, and Fig. 1
gives the finite set $\mathcal{D}$ of words obtained by computing all possible
$\phi$-cyclic permutations and equivalent words. Here the arrowed lines
indicate $\phi$-cyclic permutations.

$xy^{-1}x^{-1}y$$y^{-1}xy^{-1}x^{-1}$$xy^{-1}xy^{-1}$$yxy^{-1}x$$x^{-1}yxy^{-1}$$yx^{-1}yx$$x^{-1}yx^{-1}y$$y^{-1}x^{-1}yx^{-1}$$x^{-1}y^{-1}xy$$y^{-1}x^{-1}y^{-1}x$$x^{-1}y^{-1}x^{-1}y^{-1}$$yx^{-1}y^{-1}x^{-1}$$xyx^{-1}y^{-1}$$yxyx^{-1}$$xyxy$$y^{-1}xyx$$=_{G}$$=_{G}$$=_{G}$$=_{G}$
Figure 1: Set $\mathcal{D}$ obtained in 3.17.

###  Complexity of algorithm

We make some observations to improve our algorithm, which will lead to linear
time complexity. We recall 3.17 as a motivating example. Rather than computing
all words of minimal length in $\mathcal{D}$, we could have instead computed
all $\phi$-cyclic permutations from
$u\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$ only. Then, if we want to check if
$v\in\mathcal{D}$, we simply check if $v$ is equal, as group elements, to a
word $u^{\prime}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$ obtained from $u$
via $\phi$-cyclic permutations. This step runs in linear time, based on the
length of $u$, and we will go on to show that this idea can be applied in all
cases.

First, recall that for non-unique geodesics in
$\mathsf{CycGeo}_{\phi,\overline{(3)}}$, the only rewrite which can occur is
that of the form in Eq. 5. This allows us to make the following observation.

######  Proposition 3.18.

Let $u=x^{a_{1}}y^{b_{1}}\dots x^{a_{\tau}}y^{b_{\tau}}$,
$v=x^{\alpha_{1}}y^{\beta_{1}}\dots
x^{\alpha_{\tau}}y^{\beta_{\tau}}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$. If
$u\sim_{\phi}v$, then
$\left(\beta_{1},\dots,\beta_{\tau}\right)=\left(-b_{i},\dots,-b_{n},b_{1},\dots,b_{i-1}\right)$,
for some $1\leq i\leq\tau$.

###### Proof.

By 3.15, $u\sim_{\phi}v$ if and only if $u$ and $v$ are related by a sequence
of $\phi$-cyclic permutations and equivalent geodesics. Since Eq. 5 does not
affect any $y$ factors, we can assume $y$ factors are changed only by
$\phi$-cyclic permutations. ∎

3.18 allows us to add the following information to Step 3 of our algorithm.

Step 3: Twisted cyclic geodesics Let
$\overline{u}_{\min}=x^{a_{1}}y^{b_{1}}\dots x^{a_{\tau}}y^{b_{\tau}}$ and
$\overline{v}_{\min}=x^{\alpha_{1}}y^{\beta_{1}}\dots
x^{\alpha_{\tau}}y^{\beta_{\tau}}$. If
$(\beta_{1},\dots,\beta_{\tau})\neq(-b_{i},\dots,-b_{\tau},b_{1},\dots,b_{i-1})$
for all $2\leq i\leq\tau$, then Output = False. We can also adapt Step 4 of
our algorithm, to find group elements of minimal length for each twisted
conjugacy class, rather than words of minimal length. We find that the number
of group elements of minimal length for each twisted conjugacy class is
quadratic, with respect to word length.

######  Proposition 3.19.

Let $\overline{u}_{\min}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$, where
$l(\overline{u}_{\min})=n$. Then the number of minimal length group elements
$v\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$, such that $u\sim_{\phi}v$, is
bounded above by $2n(n+1)$.

###### Proof.

First recall from 3.13 that to check if two words
$u,v\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$ represent the same group
element, then we only need to check that the exponents of $y$ factors of $u$
and $v$ match exactly, and that the number of $x$ terms in $u$ equals the
number of $x$ terms in $v$ (or analogously, the number of $x^{-1}$ terms in
$u$ equals the number of $x^{-1}$ terms in $v$). Combined with 3.15, we can
find unique representatives for each group element in a twisted conjugacy
class as follows.

Let $\overline{u}_{\min}=x^{a_{1}}y^{b_{1}}\dots x^{a_{m}}y^{b_{m}}$, i.e.
$l(\overline{u}_{\min})=n=m+\sum^{m}_{i}|b_{i}|$. We can write
$\overline{u}_{\min}$ in a block decomposition of the form

$u=\left(\\#y^{b_{1}}\right)\left(\\#y^{b_{2}}\right)\dots\left(\\#y^{b_{m}}\right),$

where each $\\#$ represents an $x^{\pm 1}$ term. Note if $u$ starts with a $y$
factor, then we can apply a $\phi$-cyclic permutation to obtain the correct
form. Suppose the number of $x$ terms in $u$ equals $q\leq m$. Consider the
following $\phi$-cyclic permutation:

$u^{\prime}=\left(\\#y^{-b_{m}}\right)\left(\\#y^{b_{1}}\right)\dots\left(\\#y^{b_{m-1}}\right).$

Here the number of $x$ terms in $u^{\prime}$ must be equal to either $q-1$ or
$q+1$, depending on whether we move an $x$ or $x^{-1}$ from the last block in
$u$. In particular, each time we apply a $\phi$-cyclic permutation of a block,
we either increase or decrease the number of $x$ terms by 1. Moreover, the
number of $x$ terms in any element is bounded below by 0 and above by $m$. By
repeated application of $\phi$-cyclic permutations of blocks, we see that for
any $v$ obtained from $\overline{u}_{\min}$ via $\phi$-cyclic permutations
must have either an even or odd number of $x$ terms.

In total, we obtain $2(m+1)\sum^{m}_{i}|b_{i}|$ group elements, by computing
all $\phi$-cyclic permutations of $\overline{u}_{\min}$ using this block
decomposition. To see this, we group together block decomposition’s which only
differ by one $\phi$-cyclic permutation of a block. These pairs have either
odd or even number of $x$ terms, which gives us $m+1$ group elements. Summing
across all $y$ powers, to include all possible $\phi$-cyclic permutations, we
get $(m+1)\sum^{m}_{i}|b_{i}|$ group elements. This is then doubled when we
repeat this procedure for $\overline{u}_{\min}$, with respect to a block
decomposition of the form
$u=\left(y^{b_{1}}\\#\right)\dots\left(y^{b_{m}}\\#\right)$, which gives us a
total of $2(m+1)\sum^{m}_{i}|b_{i}|$ group elements. Since $m<n$, this value
has an upper bound of $2n(n+1)$. ∎

This already improves our algorithm to quadratic time, in that at Step 4, we
can compute all minimal length group elements which are twisted conjugate to
$\overline{u}_{\min}$, and then check if $\overline{v}_{\min}$ represents one
of these group elements or not. This can be improved further to obtain a
linear time Step 4 of our algorithm as follows.

Step 4: Checking group elements For $u=x^{a_{1}}y^{b_{1}}\dots
x^{a_{\tau}}y^{b_{\tau}}\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$, define

$X(u):=\begin{cases}(0,2,4,\dots,\tau)&\\#x\text{-terms in}\;u\;\text{is
even},\\\ (1,3,5,\dots,\tau-1)&\\#x\text{-terms in}\;u\;\text{is
odd},\end{cases}$

if $\tau$ is even, and define analogously for $m$ odd. We compute all
$\phi$-cyclic permutations of
$\overline{u}_{\min}\mathsf{CycGeo}_{\phi,\overline{(3)}}$ using the block
decomposition, whilst keeping track of how many $x$ terms can exist for each
element we obtain (for each $\phi$-cyclic permutation, we switch between odd
and even). For each group element $w\in\mathsf{CycGeo}_{\phi,\overline{(3)}}$
obtained via $\phi$-cyclic permutations, we check whether the exponents of $y$
factors of $w$ and $\overline{v}_{\min}$ match exactly, and that
$X(w)=X(\overline{v}_{\min})$. If this holds for some $w$, then Output = True.
Otherwise, if no such $w$ exists, then Output = False . We are now able to
determine linear complexity for our adapted algorithm.

######  Proposition 3.20.

The $\mathrm{TCP}_{\phi}(G(m))$, where $m$ is odd, $m\geq 3$, with respect to
$\phi\colon x\mapsto x^{-1},y\mapsto y^{-1}$, is solvable in linear time.

###### Proof.

Let $u,v\in X^{\ast}$ be our input words, where $|u|+|v|=n$. Step 1 of our
algorithm runs in linear time, by checking the conditions from Table 1, and
applying the relations from $G(m)$ (see A.1). Linearity is also clear in Step
2.

For Step 3, we need to analyse the complexity of applying the rewrite rules
(R1)-(R5). (R1) takes at most $n-1$ time, by reading off the Garside element.
To apply (R2) or (R3), we are checking the first and last terms from the free
product and reducing by two each time. After all possible reductions, we have
taken at most $n$ steps to do so. At this stage we may have to reapply (R1),
but we only have to do this once. Finally for (R4) and (R5), we only read the
first and last letters of the free product, and the Garside element of length
one, so we are only reading three letters at this stage here. Overall this
gives a complexity of $3n+1$.

Next we need to understand the complexity of finding a minimal length element
in $\mathsf{CycGeo}_{\phi,\overline{(3)}}$, using Lemma 3.10. This only
requires us to check for any $y^{\pm(k+1)}$ terms, and apply $\phi$-cyclic
permutations and rewriting rules. The complexity of this step is bounded above
by $2n$. Finally Step 4 runs in linear time from the discussion above, and so
our adapted algorithm has complexity of $\mathcal{O}(n)$. ∎

###### Proof.

Let $u,v\in X^{\ast}$. Let $\psi\in\mathrm{Inn}(G(m))$, i.e.
$\psi(w)=g^{-1}wg$ for some $g\in X^{\ast}$. By 2.8, we need to check two
cases.

  1. 1.

$u\sim_{\psi}v$. This case reduces to solving the conjugacy problem for
$(gu,gv)$ (see 2.3). The conjugacy problem in dihedral Artin groups is
solvable in linear time by 2.6.

  2. 2.

$u\sim_{\psi\circ\phi}v$, where $\phi\in\mathrm{Out}(G(m))$ is of the form in
Eq. 3. This case reduces to solving the $\mathrm{TCP}_{\phi}(G(m))$ with
respect to $\phi$ (see 2.3). This is solvable in linear time by 3.20.

∎

## CONJUGACY PROBLEM IN EXTENSIONS OF $\mathrm{DA}_{M}$

The aim of this section is to prove the following. This will allow us to apply
a criteria from [2] to find new examples of group extensions of odd dihedral
Artin groups with solvable conjugacy problem. We recall this criteria here.

######  Theorem 4.1.

[2, Theorem 3.1] Let

$1\rightarrow F\xrightarrow{\alpha}G\xrightarrow{\beta}H\rightarrow 1$

be an algorithmic short exact sequence of groups such that

  1. (i)

$F$ has solvable twisted conjugacy problem,

  2. (ii)

$H$ has solvable conjugacy problem, and

  3. (iii)

for every $1\neq h\in H$, the subgroup $\langle h\rangle$ has finite index in
its centralizer $C_{H}(h)$, and there is an algorithm which computes a finite
set of coset representatives $z_{h,1},\dots z_{h,t_{h}}\in H$, i.e.

$C_{H}(h)=\langle h\rangle z_{h,1}\sqcup\dots\sqcup\langle h\rangle
z_{h,t_{h}}.$

Then the conjugacy problem for $G$ is decidable if and only if the action
subgroup
$A_{G}=\\{\varphi_{g}\;|\;g\in G\\}\leq\mathrm{Aut}(F)$ is orbit decidable.

######  Definition 4.2.

Let $A\leq\mathrm{Aut}(G)$ for a group $G=\langle X\rangle$. The _orbit
decidability problem_ for $A$, denoted OD(A), takes as input two words $u,v\in
X^{\ast}$, and decides whether there exists $\phi\in A$ such that
$v\sim\phi(u)$.

When $m$ is odd, we recall that $|\mathrm{Out}(\mathrm{DA}_{m})|=2$ by 2.8, so
we can apply a similar technique as [9, Theorem 5.1] to prove Section 1.

###### Proof of Section 1.

Let $\varphi_{1},\dots\varphi_{s}\in\mathrm{Aut}(\mathrm{DA}_{m})$ be given,
and consider
$A=\langle\varphi_{1},\dots\varphi_{s}\rangle\leq\mathrm{Aut}(\mathrm{DA}_{m})$.
For each $i=1,\dots,s$, compute $w_{i}\in\mathrm{DA}_{m}$ such that
$\varphi_{i}=\gamma_{w_{i}}\phi_{i}$, where
$\gamma_{w_{i}}\in\mathrm{Inn}(\mathrm{DA}_{m})$ and
$\phi_{i}\in\mathrm{Out}(\mathrm{DA}_{m})$. Given two words $u,v\in X^{\ast}$,
we want to decide whether $v\sim\varphi_{i}(u)$ for some $\varphi_{i}\in A$.

If $\phi_{i}$ is trivial for every $i$, then
$A\leq\mathrm{Inn}(\mathrm{DA}_{m})$, and so the set
$\\{\varphi_{i}(u)\;|\;\varphi_{i}\in A\\}$ is a collection of conjugates of
$u$. Here our problem reduces to deciding if $v$ is conjugate to $u$, which is
decidable by 2.6. Otherwise, the set $\\{\varphi_{i}(u)\;|\;\varphi_{i}\in
A\\}$ is a collection of conjugates of $u$ and $\phi(u)$, where $\phi(u)$ is
defined in Eq. 3. Here, we need to decide whether $v$ is conjugate to either
$u$ or $\phi(u)$, which is decidable by two applications of 2.6. ∎

Our final result is then immediate from Section 1, Section 1 and 4.1.

## Acknowledgements

The author would like to thank Laura Ciobanu and Fujii Michihiko for helpful
discussions.

##  Appendix A Geodesic normal forms

Table 1 gives a summary of geodesic normal forms for $G(m)$, originally
derived from [7]. We provide details on how to find geodesic representatives
in $G(m)$ in linear time.

######  Proposition A.1.

Let $w\in X^{\ast}$ represent an element of $G(m)$. Then we can determine, in
linear time, a geodesic representative $u=x^{a_{1}}y^{b_{1}}\dots
y^{b_{\tau}}\Delta^{c}$, where $\Delta=_{G}x^{2}=_{G}y^{2k+1}$, with
conditions given in Table 1, such that $w=_{G}u$.

###### Proof.

Our first step is to rewrite $w\in X^{\ast}$ into a Garside normal form. This
gives us a representative $w_{1}=_{G}w$, where

$w_{1}=x^{a_{1}}y^{b_{1}}\dots y^{b_{\tau}}\Delta^{c},$

such that $\tau\in\mathbb{Z}_{>0}$, $c\in\mathbb{Z}$, and

$\begin{cases}0\leq a_{i}\leq 1\;(1\leq i\leq\tau),&a_{i}\neq 0\;(2\leq
i\leq\tau),\\\ 0\leq b_{i}\leq 2k\;(1\leq i\leq\tau),&b_{i}\neq 0\;(1\leq
i\leq\tau-1).\end{cases}$

This is achieved by reading $w$ once, and either applying free cancellation to
each factor, or moving any $x^{\pm 2}$ or $y^{\pm(2k+1)}$ terms to the Garside
element. Then, we read the word again, and for every $x^{a_{i}}$ and
$y^{b_{i}}$ term, such that $a_{i},b_{i}<0$, we replace these terms by
$x^{a_{i}+2}\Delta^{-1}$ and $y^{b_{i}+2k+1}\Delta^{-1}$ respectively, and
move all $\Delta^{-1}$ terms to the Garside element.

Next, we rewrite $w_{1}$ into a modified Garside normal form. This gives us a
representative $w_{2}=_{G}w$, where

$w_{2}=x^{a_{1}}y^{b_{1}}\dots y^{b_{\tau}}\Delta^{c},$

such that $\tau\in\mathbb{Z}_{>0}$, $c\in\mathbb{Z}$, and

$\begin{cases}0\leq a_{i}\leq 1\;(1\leq i\leq\tau),&a_{i}\neq 0\;(2\leq
i\leq\tau),\\\ -(k-1)\leq b_{i}\leq k+1\;(1\leq i\leq\tau),&b_{i}\neq
0\;(1\leq i\leq\tau-1).\end{cases}$

This is achieved by reading $w_{1}$, and for every $y^{b_{i}}$ term such that
$b_{i}\geq k+2$, we replace each $y^{b_{i}}$ term with
$y^{b_{i}-(2k+1)}\Delta$, and move all $\Delta$ terms to the Garside element.
If $c\geq 0$, then $w_{2}$ is a geodesic of Type $(1)$, $(3^{+})$ or
$(3^{+}\cap 3^{-})$. For the remaining cases, we define the following
quantities based on our modified normal form $w_{2}$. Let

$\begin{cases}R_{a}:=\\{i\;|\;a_{i}>0\\},&r_{a}:=|R_{a}|,\\\
R_{b}:=\\{j\;|\;k\leq b_{j}\leq k+1\\},&r_{b}:=|R_{b}|,\\\
r_{w_{2}}:=r_{a}+r_{b}.&\end{cases}$

If $c<0$ and $r_{w_{2}}\leq-c$, then replace all $x^{a_{i}}$, such that $i\in
R_{a}$, by $x^{a_{i}-2}\Delta$, and similarly replace all $y^{b_{j}}$, such
that $j\in R_{b}$, by $y^{b_{j}-(2k+1)}\Delta$, and move all $\Delta$ terms to
the Garside. This gives us a geodesic of Type (2) or $(3^{-})$. If $c\leq 0$
and $r_{w_{2}}>-c$, then first rewrite all terms as before from $R_{a}$ and
$R_{b}$, until the Garside element is empty. This leaves us with a word
$w_{3}=_{G}w$, where

$w_{3}=x^{a_{1}}y^{b_{1}}\dots y^{b_{\tau}},$

such that

$\begin{cases}-1\leq a_{i}\leq 1\;(1\leq i\leq\tau),&a_{i}\neq 0\;(2\leq
i\leq\tau),\\\ -(k+1)\leq b_{i}\leq k+1\;(1\leq i\leq\tau),&b_{i}\neq
0\;(1\leq i\leq\tau-1).\end{cases}$

If $w_{3}\in(3^{0+}U)\cup(3^{0-}U)\cup(3^{0+}N)\cup(3^{0-}N)\cup(3^{0*})$ then
we are done. Otherwise, we read $w_{3}$ and determine the following values:

$\displaystyle\alpha^{+}$ $\displaystyle:=\\#x\;\text{terms in}\;w_{3},\quad$
$\displaystyle\alpha^{-}:=\\#x^{-1}\;\text{terms in}\;w_{3},$
$\displaystyle\beta^{+}$ $\displaystyle:=\\#y^{k+1}\;\text{terms
in}\;w_{3},\quad$ $\displaystyle\beta^{-}:=\\#y^{-(k+1)}\;\text{terms
in}\;w_{3}.$

We note that for $\epsilon=\pm 1$, then any pairs
$\left(y^{\epsilon(k+1)},y^{-\epsilon(k+1)}\right)$ can be rewritten as
$\left(y^{-\epsilon k},y^{\epsilon k}\right)$, using the rewrite rule

$sy^{\epsilon(k+1)}ty^{-\epsilon(k+1)}z=_{G}sy^{\epsilon(2k+1)}y^{-\epsilon
k}ty^{-\epsilon(2k+1)}y^{\epsilon k}z=_{G}sy^{-\epsilon k}ty^{\epsilon k}z,$

where $s,t,z\in X^{\ast}$. After rewriting all possible pairs of this form in
$w_{3}$, we have a word where either $\beta^{+}=0$ or $\beta^{-}=0$. If
$\beta^{+}=\beta^{-}=0$, then our word is of Type $(3^{0+}U)$, $(3^{0-}U)$ or
$(3^{0*})$.

Suppose $\beta^{+}=0$ and $\beta^{-}>0$. If $\alpha^{+}=0$, then $w_{3}$ is of
Type $(3^{0-}N)$. Otherwise, if $\alpha^{+}>0$, then rewrite all pairs
$\left(x,y^{-(k+1)}\right)$ to $(x^{-1},y^{k})$ as far as possible, using the
rewrite rule defined in Eq. 4. This leaves us with a word of Type $(3^{0-}N)$
or $(3^{0*})$. Now suppose $\beta^{+}>0$ and $\beta^{-}=0$. If $\alpha^{-}=0$,
then $w_{3}$ is of Type $(3^{0+}N)$. Otherwise, if $\alpha^{-}>0$, then
rewrite all pairs $(x^{-1},y^{k+1})$ to $(x,y^{-k})$ as far as possible, again
using Eq. 4, which leaves us with a word of Type $(3^{0+}N)$ or $(3^{0*})$.

This covers all cases, and we obtain a geodesic representative in linear time.
∎

Type Conditions on $w=x^{a_{1}}y^{b_{1}}\dots
x^{a_{\tau}}y^{b_{\tau}}\Delta^{c}$, where $\tau\in\mathbb{Z}_{>0}$
Unique/Non-unique $(1)$ $\begin{array}[]{cc}c>0,&\\\ 0\leq a_{i}\leq 1\;(1\leq
i\leq\tau),&a_{i}\neq 0\;(2\leq i\leq\tau),\\\ -(k-1)\leq b_{i}\leq
k+1\;(1\leq i\leq\tau),&b_{i}\neq 0\;(1\leq i\leq\tau-1).\end{array}$ Unique
$(2)$ $\begin{array}[]{cc}c<0,&\\\ -1\leq a_{i}\leq 0\;(1\leq
i\leq\tau),&a_{i}\neq 0\;(2\leq i\leq\tau),\\\ -(k+1)\leq b_{i}\leq
k-1\;(1\leq i\leq\tau),&b_{i}\neq 0\;(1\leq i\leq\tau-1).\end{array}$
$(3^{+})$ $\begin{array}[]{cc}c=0,&\\\ 0\leq a_{i}\leq 1\;(1\leq
i\leq\tau),&a_{i}\neq 0\;(2\leq i\leq\tau),\\\ -(k-1)\leq b_{i}\leq
k+1\;(1\leq i\leq\tau),&b_{i}\neq 0\;(1\leq i\leq\tau-1).\end{array}$
$(3^{-})$ $\begin{array}[]{cc}c=0,&\\\ -1\leq a_{i}\leq 0\;(1\leq
i\leq\tau),&a_{i}\neq 0\;(2\leq i\leq\tau),\\\ -(k+1)\leq b_{i}\leq
k-1\;(1\leq i\leq\tau),&b_{i}\neq 0\;(1\leq i\leq\tau-1).\end{array}$
$(3^{+}\cap 3^{-})$ $w=y^{b}$ where $-(k-1)\leq b\leq k-1$. $(3^{0+}U)$
$\begin{array}[]{cc}c=0&\\\ 0\leq a_{i}\leq 1\;(1\leq i\leq\tau),&a_{i}\neq
0\;(2\leq i\leq\tau),\\\ -k\leq b_{i}\leq k\;(1\leq i\leq\tau),&b_{i}\neq
0\;(1\leq i\leq\tau-1),\\\ \text{There exist at least
one}\;y^{-k}\;\text{term}.&\\\ \end{array}$ $(3^{0-}U)$
$\begin{array}[]{cc}c=0&\\\ -1\leq a_{i}\leq 0\;(1\leq i\leq\tau),&a_{i}\neq
0\;(2\leq i\leq\tau),\\\ -k\leq b_{i}\leq k\;(1\leq i\leq\tau),&b_{i}\neq
0\;(1\leq i\leq\tau-1),\\\ \text{There exist at least
one}\;y^{k}\;\text{term}.&\\\ \end{array}$ $(3^{0+}N)$
$\begin{array}[]{cc}c=0&\\\ 0\leq a_{i}\leq 1\;(1\leq i\leq\tau),&a_{i}\neq
0\;(2\leq i\leq\tau),\\\ -k\leq b_{i}\leq k+1\;(1\leq i\leq\tau),&b_{i}\neq
0\;(1\leq i\leq\tau-1),\\\ \text{There exist
both}\;y^{-k}\;\text{and}\;y^{k+1}\;\text{terms}.&\\\ \end{array}$ Non-unique
$(3^{0-}N)$ $\begin{array}[]{cc}c=0&\\\ -1\leq a_{i}\leq 0\;(1\leq
i\leq\tau),&a_{i}\neq 0\;(2\leq i\leq\tau),\\\ -(k+1)\leq b_{i}\leq k\;(1\leq
i\leq\tau),&b_{i}\neq 0\;(1\leq i\leq\tau-1),\\\ \text{There exist
both}\;y^{k}\;\text{and}\;y^{-(k+1)}\;\text{terms}.&\end{array}$ $(3^{0*})$
$\begin{array}[]{cc}c=0&\\\ -1\leq a_{i}\leq 1\;(1\leq i\leq\tau),&a_{i}\neq
0\;(2\leq i\leq\tau),\\\ -k\leq b_{i}\leq k\;(1\leq i\leq\tau),&b_{i}\neq
0\;(1\leq i\leq\tau-1),\\\ \text{There exist
both}\;x,x^{-1}\;\text{terms.}&\end{array}$

Table 1: Geodesic normal forms

## References

  * [1] O. Bogopolski, A. Martino, O. Maslakova, and E. Ventura.  The Conjugacy Problem is Solvable in Free-By-Cyclic Groups.  Bulletin of the London Mathematical Society, 38(5):787–794, 2006\.
  * [2] O. Bogopolski, A. Martino, and E. Ventura.  Orbit decidability and the conjugacy problem for some extensions of groups.  Transactions of the American Mathematical Society, 362(4):2003–2036, 2009.
  * [3] José Burillo, Francesco Matucci, and Enric Ventura.  The conjugacy problem in extensions of Thompson’s group F.  Israel Journal of Mathematics, 216(1):15–59, 2016.
  * [4] Laura Ciobanu and Gemma Crowe.  Conjugacy geodesics and growth in dihedral Artin groups.  Preprint 2024.
  * [5] Laura Ciobanu, Derek Holt, and Sarah Rees.  Equations in groups that are virtually direct products.  Journal of Algebra, 545:88–99, 2020.
  * [6] Charles Garnet Cox.  Twisted conjugacy in Houghton’s groups.  Journal of Algebra, 490:390–436, 2017.
  * [7] Michihiko Fujii.  A new formula for the spherical growth series of an amalgamated free product of two infinite cyclic groups.  Kodai Mathematical Journal, 41(3):475–511, 2018.
  * [8] N. D. Gilbert, J. Howie, V. Metaftsis, and E. Raptis.  Tree actions of automorphism groups.  Journal of Group Theory, 3(2), 2000.
  * [9] Juan González-Meneses and Enric Ventura.  Twisted conjugacy in braid groups.  Israel Journal of Mathematics, 201(1):455–476, 2014.
  * [10] Derek F. Holt and Sarah Rees.  Conjugacy in Artin groups of extra-large type.  Journal of Algebra, 434:12–26, 2015.
  * [11] A. Juhász.  Twisted conjugacy in certain Artin groups.  In Ischia Group Theory 2010, pages 175–195. World Scientific, September 2011.

DEPARTMENT OF MATHEMATICS, HERIOT-WATT UNIVERSITY, AND THE MAXWELL INSTITUTE
FOR MATHEMATICAL SCIENCES, EDINBURGH, EH14 4AS.

Email address<EMAIL_ADDRESS>