arXiv:1410.7051v6 [] 21 Jul 2017

TWISTED CONJUGACY IN HOUGHTON’S GROUPS
CHARLES GARNET COX
Abstract. For a fixed n ∈ {2, 3, . . .}, the Houghton group Hn consists of
bijections of Xn = {1, . . . , n} × N that are ‘eventually translations’ of each
copy of N. The Houghton groups have been shown to have solvable conjugacy
problem. In general, solvable conjugacy problem does not imply that all finite
extensions and finite index subgroups have solvable conjugacy problem. Our
main theorem is that a stronger result holds: for any n ∈ {2, 3, . . .} and any
group G commensurable to Hn , G has solvable conjugacy problem.

1. Introduction
Given a presentation hS | Ri = G, a ‘word’ in G is an ordered f -tuple a1 . . . af
with f ∈ N and each ai ∈ S ∪ S −1 . Dehn’s problems and their generalisations
(known as decision problems) ask seemingly straightforward questions about finite
presentations. The problems that we shall consider include:
• WP(G), the word problem for G: show there exists an algorithm which given
any two words a, b ∈ G, decides whether a =G b or a 6=G b i.e. whether
these words represent the same element of the group. This is equivalent
to asking whether or not ab−1 =G 1. There exist finitely presented groups
where this problem is undecidable (see [Nov58] or [Boo59]).
• CP(G), the conjugacy problem for G: show there exists an algorithm which
given any two words a, b ∈ G, decides whether or not there exists an x ∈ G
such that x−1 ax = b. Since {1G } is always a conjugacy class of G, if CP(G)
is solvable then so is WP(G). There exist groups where WP(G) is solvable
but CP(G) is not (e.g. see [Mil71]) and so CP(G) is strictly weaker than
WP(G).
• TCPφ (G), the φ-twisted conjugacy problem for G: for a fixed φ ∈ Aut(G),
show there exists an algorithm which given any two words a, b ∈ G, decides
whether or not there exists an x ∈ G such that (x−1 )φax = b (meaning
that a is φ-twisted conjugate to b). Note that TCPId (G) is CP(G).
• TCP(G), the (uniform) twisted conjugacy problem for G: show there exists
an algorithm which given any φ ∈ Aut(G) and any two words a, b ∈ G,
decides whether or not they are φ-twisted conjugate. There exist groups G
such that CP(G) is solvable but TCP(G) is not (e.g. see [BMV10]).
Should any of these problems be solved for one finite presentation, then they
may be solved for any other finite presentation of that group. We therefore say
that such problems are solvable if an algorithm exists for one such presentation.
Date: July 4, 2017.
2010 Mathematics Subject Classification. Primary: 20F10, 20B99.
Key words and phrases. uniform twisted conjugacy problem, Houghton group, permutation
group, orbit decidability, conjugacy problem for commensurable groups, computable centralisers.
1

2

CHARLES GARNET COX

Many decision problems may also be considered for any group that is recursively
presented.
We say that G is a finite extension of H if H E G and H is finite index in G. If
CP(G) is solvable, then we do not have that finite index subgroups of G or finite
extensions of G have solvable conjugacy problem, even if these are of degree 2.
Explicit examples can be found for both cases (see [CM77] or [GK75]). Thus it is
natural to ask, if CP(G) is solvable, whether the conjugacy problem holds for finite
extensions and finite index subgroups of G. The groups we investigate in this paper
are Houghton groups (denoted Hn with n ∈ N).
Theorem 1. Let n ∈ {2, 3, . . .}. Then TCP(Hn ) is solvable.
We say that two groups A and B are commensurable if there exists NA ∼
= NB
where NA is normal and finite index in A and NB is normal and finite index in B.
Theorem 2. Let n ∈ {2, 3, . . .}. Then, for any group G commensurable to Hn ,
CP(G) is solvable.
As a consequence of this work we also obtain.
Theorem 3. There exists an algorithm which takes as input any n ∈ {2, 3, . . .} and
any a ∈ Hn ⋊ Sn , and which decides whether or not CHn (a) is finitely generated.
If CHn (a) is finitely generated, then the algorithm also outputs a finite generating
set for CHn (a).
We structure the paper as follows. In Section 2 we introduce the Houghton
groups, make some simple observations for them, and reduce TCP(Hn ) to a problem similar to CP(Hn ⋊ Sn ), the difference being that, given a, b ∈ Hn ⋊ Sn , we
are searching for a conjugator x ∈ Hn . This occurs since, for all n ∈ {2, 3, . . .},
Aut(Hn ) ∼
= Hn ⋊ Sn . In Section 3 we describe the orbits of elements of Hn ⋊ Sn and
produce identities that a conjugator of elements in Hn ⋊ Sn must satisfy. These are
then used in Section 4 to reduce our problem of finding a conjugator in Hn to finding
a conjugator in the subgroup of Hn consisting of all finite permutations (which we
denote by FSym, see Notation 2.1 below). Constructing such an algorithm provides
us with Theorem 1. In Section 5 we use Theorem 1 and [BMV10, Thm. 3.1] to
prove our main result, Theorem 2. In Section 6 we discuss the structure of CHn (a)
where a ∈ Hn ⋊ Sn and prove Theorem 3.
Acknowledgements. I thank the authors of [ABM15] whose work is drawn upon
extensively. I especially thank the author Armando Martino, my supervisor, for
his encouragement and the many helpful discussions which have made this work
possible. I thank Peter Kropholler for his suggested extension which developed into
Theorem 2. Finally, I thank the referee for their time and many helpful comments.
2. Background
As with the authors of [ABM15], the author does not know of a class that contains
the Houghton groups and for which the conjugacy problem has been solved.
2.1. Houghton’s groups. Throughout we shall consider N := {1, 2, 3, . . .}. For
convenience, let Zn := {1, . . . , n}. For a fixed n ∈ N, let Xn := Zn × N. Arrange
these n copies of N as in Figure 1 below (so that the k th point from each copy of N
form the vertices of a regular n-gon). For any i ∈ Zn , we will refer to the set i × N
as a branch or ray and will let (i, m) denote the mth point on the ith branch.

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

3

Notation 2.1. For a non-empty set X, the set of all permutations of X form a
group which we denote Sym(X). Those permutations which have finite support (i.e.
move finitely many points) form a normal subgroup which we will denote FSym(X).
If there is no ambiguity for X, then we will write just Sym or FSym respectively.
Note that, if X is countably infinite, then FSym(X) is countably infinite but is
not finitely generated, and Sym(X) is uncountable and so uncountably generated.
Definition 2.2. Let n ∈ N. The nth Houghton group, denoted Hn , is a subgroup
of Sym(Xn ). An element g ∈ Sym(Xn ) is in Hn if and only if there exist constants
z1 (g), . . . , zn (g) ∈ N and (t1 (g), . . . , tn (g)) ∈ Zn such that, for all i ∈ Zn ,
(1)

(i, m)g = (i, m + ti (g)) for all m > zi (g).

For simplicity, the numbers z1 (g), . . . , zn (g) are assumed to be minimal i.e. for
any m′ < zi (g), (i, m′ )g 6= (i, m′ + ti (g)). The vector t(g) := (t1 (g), . . . , tn (g))
represents the ‘eventual translation length’ for each g in Hn since ti (g) specifies
how far g moves the points {(i, m) | m > zi (g)}. We shall say that these points are
those which are ‘far out’, since they are the points where g acts in the regular way
described in (1). As g induces a bijection from Xn to Xn , we have that
n
X
(2)
ti (g) = 0.
i=1

Given g ∈ Hn , the numbers zi (g) may be arbitrarily large. Thus FSym(Xn ) 6 Hn .
Also, for any n ∈ {2, 3, . . .}, we have (as proved in [Wie77]) the short exact sequence
1 −→ FSym(Xn ) −→ Hn −→ Zn−1 −→ 1

where the homomorphism Hn → Zn−1 is given by g 7→ (t1 (g), . . . , tn−1 (g)).
These groups were introduced in [Hou78] for n ∈ {3, 4, . . .}. The generating
set that we will use when n ∈ {3, 4, . . .} is {gi | i = 2, . . . , n} where, for each
i ∈ {2, . . . , n} and (j, m) ∈ Xn ,

(1, m + 1) if j = 1



(1, 1)
if j = i, m = 1
(j, m)gi =
(i,
m
−
1)
if
j = i, m > 1



(j, m)
otherwise.

Note, for each i, t1 (gi ) = 1 and tj (gi ) = −δi,j for j ∈ {2, . . . , n}. Figure 1 shows
a geometric visualisation of g2 , g4 ∈ H5 . Throughout we shall take the vertical
ray as the ‘first ray’ (the set of points {(1, m) | m ∈ N}) and order the other rays
clockwise.
We shall now see that, for any n ∈ {3, 4, . . .}, the set {gi | i = 2, . . . , n} generates Hn . First, any valid eventual translation lengths (those satisfying (2)) can
be obtained by these generators. Secondly, the commutator (which we define as
[g, h] := g −1 h−1 gh for every g, h in G) of any two distinct elements gi , gj ∈ Hn is a
2-cycle, and so conjugation of this 2-cycle by some combination of gk ’s will produce
a 2-cycle with support equal to any two points of Xn . This is enough to produce any
element that is ‘eventually a translation’ i.e. one that satisfies condition (1), and so
is enough to generate all of Hn . An explicit finite presentation for H3 can be found
in [Joh99], and this was generalised in [Lee12] by providing finite presentations for
Hn for all n > 3.

4

CHARLES GARNET COX

g4

g2

Figure 1. Part of the set X5 and a geometrical representation of
the action of the standard generators g2 , g4 ∈ H5 .
We now describe H1 and H2 . If g ∈ H1 , then t1 (g) = 0 (since the eventual
translation lengths of g must sum to 0 by condition (2)) and so H1 = FSym(N). For
H2 we have hg2 i ∼
= Z. Using a conjugation argument similar to the one above, it can
be seen that a suitable generating set for H2 is {g2 , ((1, 1) (2, 1))}. These definitions
of H1 and H2 agree with the result for Hn in [Bro87], that (for n > 3) each Hn is
FPn−1 but not FPn i.e. H1 is not finitely generated and H2 is finitely generated
but not finitely presented. Since H1 = FSym(N) and Aut(FSym(N)) ∼
= Sym(N)
(see, for example, [DM96] or [Sco87]) we will work with Hn where n ∈ {2, 3, . . .}.
2.2. A reformulation of TCP(Hn ). We require knowledge of Aut(Hn ). We
noted above that Aut(H1 ) ∼
= Sym(N), and so will work with n ∈ {2, 3, . . .}.
Notation. Let g ∈ Sym(X). Then (h)φg := g −1 hg for all h ∈ G.
From [BCMR14], we have for all n ∈ {2, 3, . . .} that NSym(Xn ) (Hn ) ∼
= Aut(Hn )
via the map ρ 7→ φρ and that NSym(Xn ) (Hn ) ∼
= Hn ⋊ Sn . We will make an abuse
of notation and consider Hn ⋊ Sn as acting on Xn via the natural isomorphism
NSym(Xn ) (Hn ) 6 Sym(Xn ). Here Inn(Hn ) ∼
= Hn because Hn is centreless, and
Sn acts on Xn by isometrically permuting the rays, where g ∈ Hn ⋊ Sn is an
isometric permutation of the rays if and only if there exists a σ ∈ Sn such that
(i, m)g = (iσ, m) for all m ∈ N and all i ∈ Zn .
Notation. For any given g ∈ Hn ⋊ Sn , let Ψ : Hn ⋊ Sn → Sn , g 7→ σg where
σg denotes the isometric permutation of the rays induced by g. Furthermore, let
ωg := gσg−1 . Thus, for any g ∈ Hn ⋊ Sn , we have g = ωg σg and will consider
ωg ∈ Hn and σg ∈ Sn . We shall therefore consider any element g of Hn ⋊ Sn as
a permutation of Xn which is eventually a translation (denoted ωg ) followed by an
isometric permutation of the rays σg .
Definition 2.3. Let G 6 Hn ⋊ Sn and g, h ∈ Hn ⋊ Sn . Then we shall say g and h
are G-conjugated if there is an x ∈ G such that x−1 gx = h.

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

5

We now relate twisted conjugacy in Hn to conjugacy in Hn ⋊Sn . Let c ∈ Hn ⋊Sn .
Then the equation for φc -twisted conjugacy becomes:
(x−1 )φc gx = h ⇔ c−1 x−1 cgx = h ⇔ x−1 (ωc σc g)x = ωc σc h.
Thus, for any n ∈ {2, 3, . . .}, two elements g, h ∈ Hn are φc -twisted conjugate if and
only if ωc σc g and ωc σc h ∈ Hn ⋊ Sn are Hn -conjugated. Note that, if g, h ∈ Hn ⋊ Sn
are Hn -conjugated, then σg = σh . Thus for the remainder of this note a and b will
refer to the elements in Hn ⋊ Sn that we wish to decide are Hn -conjugated, where
σa = σb . In order to solve TCP(Hn ), we will therefore produce an algorithm to
search for an x ∈ Hn which conjugates a to b.
3. Computations in Hn ⋊ Sn
Our first lemma provides the generating set that we will use for Hn ⋊ Sn .
Lemma 3.1. Let n ∈ {2, 3, . . .}. Then Hn ⋊ Sn can be generated by 3 elements.
Proof. If n > 3, two elements can be used to generate all of the isometric permutations of the rays. Our third generator will be g2 , the standard generator for Hn .
Conjugating g2 by the appropriate isometric permutations of the rays produces the
set {gi | i = 2, . . . , n}, which can then be used to generate all permutations in Hn .
For H2 ⋊ S2 we note that H2 is 2-generated and that S2 is cyclic.

3.1. The orbits of elements in Hn ⋊ Sn . Our main aim for this section is to
describe the orbits of any element g ∈ Hn ⋊ Sn ‘far out’. For elements of Hn , any
element eventually acted like a translation. In a similar way, any element of Hn ⋊Sn
eventually moves points in a uniform manner. More specifically, g ∈ Sym(Xn ) is in
Hn ⋊Sn if and only if there exist constants z1 (g), . . . , zn (g) ∈ N, (t1 (g), . . . , tn (g)) ∈
Zn , and a permutation σ ∈ Sn such that for all i ∈ Zn
(3)

(i, m)g = (iσ, m + ti (g)) for all m > zi (g).

If g ∈ Hn ⋊ Sn , then g = ωg σg . Therefore for any g ∈ Hn ⋊ Sn , σg (the isometric
permutation of the rays induced by g) will induce the permutation denoted σ in
(3), we have that ti (ωg ) = ti (g) for all i ∈ Zn , and z1 (ωg ), . . . , zn (ωg ) are suitable
values for the constants z1 (g), . . . , zn (g).
Definition 3.2. Let g ∈ Hn ⋊ Sn and i ∈ Zn . Then a class of σg , denoted [i]g ,
is the support of the disjoint cycle of σg which contains i i.e. [i]g = {iσgd | d ∈ Z}.
Additionally, we define the size of a class [i]g to be the length of the cycle of σg
containing i, i.e. the cardinality of the set [i]g , and denote this by |[i]g |.
We shall choose z1 (g), . . . , zn (g) ∈ N to be the smallest numbers such that
(4)

(i, m)g d = (iσgd , m +

d−1
X

tiσgs (g)) for all m > zi (g) and all 1 6 d 6 |[i]g |.

s=0

Note that, for any g ∈ Hn ⋊ Sn and all i ∈ Zn , we have zi (g) > zi (ωg ). We now
justify the introduction of condition (4). Consider a g ∈ Hn ⋊ Sn , i ∈ Zn , and
m ∈ N such that
zi (ωg ) 6 m < zi (g) and m + ti (ωg ) < ziσg (ωg ).
This would mean that (i, m)g = (iσg , m + ti (ωg )), but it may also be that
(i, m)g 2 = (iσg , m + ti (g))g 6= (iσg2 , m + ti (g) + tiσg (g)).

6

CHARLES GARNET COX

Thus the condition (4) above means that, for any g ∈ Hn ⋊ Sn , the numbers
z1 (g), . . . , zn (g) capture the ‘eventual’ way that g permutes the points of a ray.
Let us fix some g ∈ Hn ⋊ Sn . Consider if σg acts trivially on a particular branch
i′ . This will mean that this branch has orbits like those occurring for elements of
Hn . If ti′ (g) = 0, then g leaves all but a finite number of points on this branch
fixed. If ti′ (g) 6= 0, then for any given m′ > zi′ (g),
{(i′ , m′ )g d | d ∈ Z} ⊃ {(i′ , m) | m > m′ and m ≡ m′ mod |ti′ (g)|}.
Notice that, for any g ∈ Hn ⋊ Sn , the σg -classes form a partition of Zn , relating
to the branches of Xn . We now consider the case |[k]g | > 1. We first note, for any
i ∈ [k]g and m1 > zi (g), that
(5)

(i, m1 )g |[k]g | ∈ {(i, m) | m ∈ N}

and that for any 1 6 p < |[k]g |, i ∈ [k]g , and m1 > zi (g),
(i, m1 )g p 6∈ {(i, m) | m ∈ N}.
In fact we may compute (i, m)g |[k]g | for any i ∈ [k]g and m > zi (g),
|[k]g |−1

(6)

(i, m)g

|[k]g |

= (i, m +

X

tiσgs (g)).

s=0

In light of this, we introduce the following.

Definition 3.3. For any g ∈ Hn ⋊ Sn , class [i]g , and k ∈ [i]g = {i1 , i2 , . . . , iq }, let
t[k] (g) :=

q
X

tis (g).

s=1

Hence, if t[k] (g) = 0, then for all i′ ∈ [k]g and m′ > zi′ (g), the point (i′ , m′ ) will
lie on an orbit of length |[k]g |. If t[k] (g) 6= 0, then (6) states that for all i′ ∈ [k]g
and all m′ > zi′ (g), that (i′ , m′ )g |[k]g | 6= (i′ , m′ ). Hence when t[k] (g) = 0, almost all
points of the k th ray will lie on an orbit of g of length |[k]g |, and when t[k] (g) 6= 0
almost all points of the k th ray will lie in an infinite orbit of g. Since different
arguments will be required for finite orbits and infinite orbits, we introduce the
following notation.
Notation. Let g ∈ Hn ⋊ Sn . Then I(g) := {i ∈ Zn | t[i] (g) 6= 0} consists of
all i ∈ Zn corresponding to rays of Xn which have infinite intersection with some
infinite orbit of g. Let I c (g) := Zn \ I(g), the complement of I(g).
Definition 3.4. Two sets are almost equal if their symmetric difference is finite.
For any g ∈ Hn ⋊ Sn and any infinite orbit Ω of g, our aim is now to describe
a set almost equal to Ω, so to have a suitable description of the infinite orbits of
elements of Hn ⋊ Sn . We work with t[k] (g) > 0, since if t[k] (g) is negative, we will
be able to apply our arguments to g −1 . For any i1 ∈ [k]g and m1 > zi1 (g), we shall
compute the orbit of (i1 , m1 ) under g. First,
{(i1 , m1 )g d|[k]g | | d ∈ N} = {(i1 , m) | m > m1 , m ≡ m1 mod |t[k] (g)|}.
Similarly, {(i1 , m1 )g d|[k]g |+1 | d ∈ N} is equal to
(7)

{(i1 σg , m) | m > m1 + ti1 (g), m ≡ m1 + ti1 (g) mod |t[k] (g)|}.

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

For every 2 6 s 6 |[k]g |, setting is := i1 σgs−1 and ms := m1 +

7

s−1
P

tid (g) we have,

d=1

for any 0 6 r < |[k]g |, that

{(i1 , m1 )g d|[k]|g +r | d ∈ N} = {(ir+1 , m) | m > mr+1 , m ≡ mr+1 mod |t[k] (g)|}
and hence {(i1 , m1 )g d | d ∈ N} is equal to
|[k]g |

(8)

G

{(iq , m) | m > mq , m ≡ mq mod |t[k] (g)|}.

q=1

It is therefore natural to introduce the following.
Definition 3.5. Let g ∈ Hn ⋊ Sn , i1 ∈ I(g), and m1 ∈ N. Then
Xi1 ,m1 (g) := {(i1 , m) ∈ Xn | m ≡ m1 mod |t[i1 ] (g)|}.
Furthermore, for every 2 6 s < |[k]g | let is := i1 σgs−1 , ms := m1 +

s−1
P

tid (g), and

d=1
|[i1 ]g |

X[i1 ],m1 (g) :=

G

Xiq ,mq (g).

q=1

Note that suppressing m2 , . . . , m|[k]g | from the notation is not ambiguous since these
are uniquely determined from i1 , m1 , and g.
Let us summarise what we have shown.
Lemma 3.6. Let g ∈ Hn ⋊ Sn and i ∈ I(g). Then, for any infinite orbit Ω of
g intersecting {(i, m) ∈ Xn | m > zi (g)}, there exists i′ ∈ I(g) and constants
d1 , e1 ∈ N such that the set
X[i],d1 (g) ⊔ X[i′ ],e1 (g)
is almost equal to Ω.
3.2. Identities arising from the equation for conjugacy. In Section 2.2 we
showed that TCP(Hn ) was equivalent to producing an algorithm which, given any
a, b ∈ Hn ⋊ Sn , decides whether or not a and b are Hn -conjugated. In this section
we shall show some necessary conditions which any x ∈ Hn must satisfy in order to
conjugate a to b. First, some simple computations to rewrite ti (σa xσa−1 ) are needed.
Note that, since σa = σb is a necessary condition for a and b to be Hn -conjugated
(and σa , σb are computable), the following will not be ambiguous.
Notation. We will write [i] to denote [i]a (which is also a class of b).
Lemma 3.7. For any isometric permutation of the rays σ and any y ∈ Hn ,
ti (σ −1 yσ) = tiσ−1 (y) for all i ∈ Zn .
Proof. Let σ = σ1 σ2 . . . σs be written in disjoint cycle notation, and let σ1 =
(i1 i2 . . . iq ). Since σ ∈ NSym(Xn ) (Hn ), we have that σ −1 yσ ∈ Hn . We compute
ti1 (σ −1 yσ) by considering the image of (i1 , m) where m > max{zi (y) | i ∈ Zn }:
(i1 , m)σ −1 yσ = (iq , m)yσ = (iq , m + tiq (y))σ = (i1 , m + tiq (y)).
Similarly, for 1 < s 6 q,
(is , m)σ −1 yσ = (is−1 , m)yσ = (is−1 , m + tis−1 (y))σ = (is , m + tis−1 (y)).
Thus ti (σ −1 yσ) = tiσ−1 (y) for any i ∈ Zn .



8

CHARLES GARNET COX

Lemma 3.8. Let a, b ∈ Hn ⋊ Sn . Then a necessary condition for a and b to be
Hn -conjugated is that, for all [i] classes, t[i] (a) = t[i] (b). Also if x ∈ Hn conjugates
a to b, then ti (ωb ) = −ti (x) + ti (ωa ) + tiσa (x) for all i ∈ Zn .
Proof. From our hypotheses, we have that
ωb σa = x−1 ωa σa x
⇒ ωb = x−1 ωa (σa xσa−1 )
and so, since ωa , ωb , x, and σa xσa−1 can all be considered as elements of Hn , we
have for all i ∈ Zn that
ti (ωb ) = ti (x−1 ) + ti (ωa ) + ti (σa xσa−1 )
which from the previous lemma can be rewritten as
ti (ωb ) = −ti (x) + ti (ωa ) + tiσa (x).
′

Now, for any branch i , we sum over all k in [i′ ]
X
X
X
X
tk (x)
tk (ωa ) +
tk (x) +
tk (ωb ) = −
⇒

X

k∈[i′ ]

k∈[i′ ]

k∈[i′ ]

k∈[i′ ]

tk (ωb ) =

X

k∈[i′ ]

tk (ωa )

k∈[i′ ]

⇒ t[i′ ] (b) = t[i′ ] (a)

as required.



Thus, if a, b ∈ Hn ⋊Sn are Hn -conjugated, then I(a) = I(b). For any g ∈ Hn ⋊Sn
the set I(g) is computable, and so the first step of our algorithm can be to check
that I(a) = I(b). Hence the following is not ambiguous.
Notation. We shall use I to denote I(a) and I(b).
Lemma 3.9. Let a, b ∈ Hn ⋊ Sn be conjugate by x ∈ Hn . Then, for each class [k],
choosing a value for ti′ (x) for some i′ ∈ [k] determines values for {ti (x) | i ∈ [k]}.
Moreover, let i1 ∈ [k] and, for 2 6 s 6 |[k]|, let is := i1 σas−1 . Then the following
formula determines tis (x) for all s ∈ Z|[k]|
tis (x) = ti1 (x) +

s−1
X

(tid (ωb ) − tid (ωa )).

d=1

Proof. If |[k]| = 1, then there is nothing to prove. Lemma 3.8 states that
ti (ωb ) = −ti (x) + ti (ωa ) + tiσa (x)
for all i ∈ Zn , and so we are free to let i := is ∈ [k], where s ∈ Z|[k]| , to obtain
tis (ωb ) = −tis (x) + tis (ωa ) + tis σa (x)
⇒ tis σa (x) = tis (x) + tis (ωb ) − tis (ωa ).

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

9

Setting s = 1 provides a formula for ti2 (x). If 2 6 s < |[k]|, then
tis σa (x) = tis (x) + tis (ωb ) − tis (ωa )
= tis−1 (x) + tis−1 (ωb ) − tis−1 (ωa ) + tis (ωb ) − tis (ωa )
= ...
= ti1 (x) +

s
X

(tid (ωb ) − tid (ωa )).

d=1

Thus, for all s ∈ Z|[k]| , we have a formula for tis (x) which depends on the com
putable values {ti (a), ti (b) | i ∈ [k]} and the value of ti1 (x).
4. An algorithm for finding a conjugator in Hn
In this section we construct an algorithm which, given a, b ∈ Hn ⋊ Sn with
σa = σb , either outputs an x ∈ Hn such that x−1 ax = b, or halts without outputting
such an x if one does not exist.
We will often need to make a choice of some i ∈ [k]g . For each class [k]g we shall
do this by introducing an ordering on [k]g . We shall choose this ordering to be the
one defined by i1 := inf[k]g (under the usual ordering of N) and is := i1 σgs−1 for all
2 6 s 6 |[k]g |. Hence [k]g = {i1 , . . . , i|[k]g | }.
4.1. An algorithm for finding a conjugator in FSym. Many of the arguments
of this section draw their ideas from [ABM15, Section 3]. By definition, any element
which conjugates a to b will send the support of a to the support of b. If we wish to
find a conjugator in FSym, this means that the symmetric difference of these sets
must be finite, whilst supp(a) ∩ supp(b) can be infinite.
Notation. For any g, h ∈ Sym, let N (g, h) := supp(g) ∩ supp(h), the intersection
of the supports of g and h.
Notation. Let g ∈ Hn ⋊ Sn . Then Z(g) := {(i, m) ∈ Xn | i ∈ Zn and m < zi (g)}
which is analogous to the Z region used by some authors when dealing with the
Houghton groups.
This yields a quadratic solution to WP(Hn ⋊Sn ). First note that, for any i ∈ Zn ,
(i, zi (g))g = (iσg , zi (g) + ti (g)). Thus if g acts trivially on {(i, zi (g)) | i ∈ Zn }, then
supp(g) ⊆ Z(g). Secondly, by using [ABM15, Lem 2.1], the size of Z(g) is bounded
by a linear function in terms of |g|S (the word length of g with respect to S). Finally,
for each point in Z(g)∪{(i, zi (g)) | i ∈ Zn }, compute the action of g (which requires
|g|S computations). This is sufficient to determine if g is the identity, since we have
that g is the identity if and only if g acts trivially on Z(g) ∪ {(i, zi (g)) | i ∈ Zn }.
Definition 4.1. Let g ∈ Hn ⋊Sn . Then, for a fixed r ∈ N, let gr denote the element
of Sym(Xn ) which consists of the product of all of the r-cycles of g. Furthermore,
let g∞ denote the element of Sym(Xn ) which consists of the product of all of the
infinite cycles of g.
Our strategy for deciding whether a, b ∈ Hn ⋊ Sn are FSym-conjugated is as
follows. We show, for any r ∈ N, that if ar and br are FSym-conjugated, then ar
and br are conjugate by an x ∈ FSym where supp(x) is computable. Similarly we
show that if a∞ and b∞ are FSym-conjugated, then there is a computable finite
set such that there is a conjugator of a∞ and b∞ with support contained within

10

CHARLES GARNET COX

this set. In order to decide if a, b ∈ Hn ⋊ Sn are FSym-conjugated we may then
decide if a∞ and b∞ are FSym-conjugated, produce such a conjugator y1 if one
exists, and then decide if y1−1 ay1 and b are FSym-conjugated by deciding whether
(y1−1 ay1 )r and br are FSym-conjugated for every r ∈ N (which is possible since br
is non-trivial for only finitely many r ∈ N, see Lemma 4.4).
Lemma 4.2. If g, h ∈ Sym are FSym-conjugated, then
| supp (g) \ N (g, h)| = | supp (h) \ N (g, h)| < ∞.
Proof. The proof [ABM15, Lem 3.2] applies to our more general hypotheses.



Lemma 4.3. Let g ∈ Hn ⋊ Sn and r ∈ N. Then gr ∈ Hn ⋊ Sn . Note this means
that gr restricts to a bijection on Z(gr ) and Xn \ Z(gr ).
Proof. It is clear that gr ∈ Sym(Xn ). From our description of orbits in Section 3.1,
for all (i, m) ∈ Xn \ Z(g) we have that (i, m) lies either on: an infinite orbit of g;
an orbit of g of length s 6= r; or on an orbit of g of length r. In the first two cases,
we have that (i, m)gr = (i, m) for all (i, m) ∈ Xn \ Z(g). In the final case, we have
that (i, m)gr = (i, m)g for all Xn \ Z(g). Hence gr is an element for which there
exists an isometric permutation of the rays σ, and constants t1 (gr ), . . . , tn (gr ) ∈ Z
and z1 (gr ), . . . , zn (gr ) ∈ N such that for all i ∈ Zn
(i, m)gr = (iσ, m + ti (gr )) for all m > zi (gr )
which was labelled (3) in Section 3.1. Thus, gr ∈ Hn ⋊ Sn .



Lemma 4.4. Let S be the generating set of Hn ⋊ Sn described in Lemma 3.1.
Then there is an algorithm which, given any (i, m) ∈ Xn and any word w over
S ±1 representing g ∈ Hn ⋊ Sn , computes the set Og (i, m) := {(i, m)g d | d ∈ Z}.
Moreover the set {gr 6= id | r ∈ N ∪ {∞}} is finite and computable.
Proof. From [ABM15, Lem 2.1], the numbers t1 (ωg ), . . . , tn (ωg ), z1 (ωg ), . . . , zn (ωg )
are computable. Hence the action of σg is computable, as are the classes [i]g and
the numbers zi (g) and t[i] (g).
We note that for all (i′ , m′ ) ∈ Xn , the number |Og (i′ , m′ )| is computable. First,
let (i′ , m′ ) ∈ Xn \ Z(g). Then |Og (i′ , m′ )| is infinite if t[i′ ] (g) 6= 0 and is equal to
|[i′ ]g | otherwise. If (i′ , m′ ) ∈ Z(g), either |Og (i′ , m′ )| is finite and so (i′ , m′ )g d =
(i′ , m′ ) for some 0 6 d 6 |Z(g)|, or (i′ , m′ )g d ∈ Xn \ Z(g) for some d ∈ N and
so (i′ , m′ ) lies in an infinite orbit of g. When Og (i′ , m′ ) is finite, it is clearly
computable.
Now we deal with the infinite orbits of g. For every i ∈ I(g) and d1 ∈ N,
the set X[i],d1 (g) - introduced in Definition 3.5 - is computable from the numbers
t1 (g), . . . , tn (g) and classes {[k]g | k ∈ Zn }. Given (j, m) ∈ X[i],d1 (g), the set
Fg (j, m) := {(j, m)g d | d ∈ Z} ∩ Z(g) is finite and computable. Hence we may
compute the i′ ∈ I(g) and e1 ∈ N such that Og (j, m) is almost equal to X[i],d1 (g) ⊔
X[i′ ],e1 (g). Thus
Og (j, m) = Fg (j, m) ⊔ (X[i],d1 (g) \ Z(g)) ⊔ (X[i′ ],e1 (g) \ Z(g))
and is therefore computable.
Since we can compute the size of orbits and the set Z(g), we may determine
those r ∈ N for which gr is non-trivial. First, record those r for which there is an
orbit of length r within Z(g). Secondly, for each k ∈ I c (g), compute |[k]| (since

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

11

then g will have infinitely many orbits of length |[k]|). Finally compute |I(g)| to
determine whether or not g∞ is trivial. Hence the set {gr 6= id | r ∈ N ∪ {∞}} is
finite and computable.

This lemma means that, given a word w in S ±1 representing g ∈ Hn ⋊Sn , we may
compute the equations (4) - which appeared after Definition 3.2 - that capture the
‘eventual’ way that g acts. Since Z(g) is finite, only finitely many more equations
are required to completely describe the action of g on Xn .
This lemma also means that, given a word w over S ±1 representing g ∈ Hn ⋊ Sn
and any r ∈ N ∪ {∞}, the action of the element gr can be determined.
Notation. Let g ∈ Sym(Xn ). Given any set Y ⊆ Xn for which Y g = Y (so that g
restricts to a bijection on Y ), let g Y denote the element of Sym(Xn ) which acts as
g on the set Y and leaves all points in Xn \ Y invariant i.e. for every (i, m) ∈ Xn

(i, m)g if (i, m) ∈ Y
(i, m)(g Y ) :=
(i, m)
otherwise.
Notation. Given g ∈ Hn ⋊ Sn , let Z ∗ (g) := Z(g) ∩ supp(g).

Lemma 4.5. Fix an r ∈ {2, 3, . . . } and let g, h ∈ Hn ⋊ Sn . If gr and hr are
FSym-conjugated, then there exists an x ∈ FSym which conjugates gr to hr such
that supp(x) ⊆ Z ∗ (gr ) ∪ Z ∗ (hr ).
Proof. Let Z := Z(gr )∪Z(hr ) and Z c := Xn \Z. If gr and hr are FSym-conjugated,
then
(i, m)gr = (i, m)hr for all (i, m) ∈ Z c .

(9)

By Lemma 4.3 and (9), gr and hr restrict to a bijection of Z c . Thus, gr and hr
must also restrict to a bijection of Z. We may therefore apply Lemma 4.2 to gr
and hr to obtain
| supp (gr ) \ N (gr , hr )| = | supp (hr ) \ N (gr , hr )|
c

which, since Z ⊆ N (gr , hr ), implies that
| supp (gr Z) \ N (gr Z, hr Z)| = | supp (hr Z) \ N (gr Z, hr Z)|
and since Z is finite,
| supp(gr Z)| = | supp(hr Z)| < ∞.
Since gr and hr consist of only r-cycles, gr Z and hr Z are elements of FSym with
the same cycle type, and so are FSym-conjugated. Thus there is a conjugator
x ∈ FSym with supp(x) ⊆ supp(gr Z) ∪ supp(hr Z) = Z ∗ (gr ) ∪ Z ∗ (hr ).

Lemma 4.6. If g∞ = h∞ and g, h ∈ Hn ⋊ Sn are FSym-conjugated, then there is
an x ∈ FSym which conjugates g to h with supp(x) ⊆ Y , a computable finite set
disjoint from supp(g∞ ).
Proof. By Lemma 4.4, {gr 6= id | r ∈ N} is finite and computable implying that
there is a computable k ∈ N such that gr = id for all r > k. Using Lemma 4.5,
compute x2 ∈ FSym that conjugates g2 to h2 with supp(x2 ) ⊆ Z ∗ (g2 ). Therefore
−1
(2)
:= x−1
(x−1
2 gx2 . Now, for each i =
2 gx2 )∞ = h∞ and (x2 gx2 )2 = h2 . Let g
3, 4, . . . , k, use Lemma 4.5 to define xi to conjugate (g (i−1) )i to hi with supp(xi ) ⊆
Q
(i−1)
Z ∗ ((g (i−1) )i ) ∪ Z ∗ (hi ) and g (i) := x−1
xi . Then kr=2 xr conjugates g to h
i g
−1 −1
since (x2 x3 . . . xk )−1 g(x2 x3 . . . xk ) = x−1

k (. . . (x3 (x2 gx2 )x3 ) . . .)xk .

12

CHARLES GARNET COX

We now reduce finding an FSym-conjugator of a and b to the case of Lemma
4.6. In order to do this we require a well known lemma.
Lemma 4.7. Let x ∈ G conjugate a, b ∈ G. Then, x′ ∈ G also conjugates a to b
if, and only if, x′ = cx for some c ∈ CG (a).
Lemma 4.8. Let g, h ∈ Hn ⋊ Sn . If g∞ and h∞ are FSym-conjugated, then there
exists an x ∈ FSym which conjugates g∞ to h∞ with supp(x) ⊆ Z(g∞ ) ∪ Z(h∞ ).
Proof. We show that a bound for zi (x) is computable for each i ∈ Zn , inspired in
part by the proof of [ABM15, Prop 3.1]. Note that I(g∞ ) = I(g) = I(h) = I(h∞ ).
For all i ∈ I(g∞ ) and all m > zi (g∞ ), we have that (i, m)(g∞ )|[i]g | = (i, m + t[i] (g)).
Our claim is that there is an x ∈ FSym which conjugates g∞ to h∞ with
(i, m)x = (i, m) for all i ∈ Zn and for all m > max(zi (g∞ ), zi (h∞ )).
Let Z := Z(g∞ )∪Z(h∞ ). We first work with I c (g∞ ). Let j ∈ I c (g), (j, m) ∈ Xn \Z,
and assume that (j, m) ∈ supp(x). Then (j, m)h∞ = (j, m) and so (j, m)x−1 g∞ x =
(j, m). If (j, m)x−1 6∈ supp(g∞ ), then the 2-cycle γ := ((j, m) (j, m)x−1 ) is
in CFSym (g∞ ) and so x′ := γx also conjugates g∞ to h∞ by Lemma 4.7. Now
(j, m)γx = (j, m) and so (j, m) 6∈ supp(x′ ). If (j, m)x−1 = (j ′ , m′ ) ∈ supp(g∞ ),
then x sends (j ′ , m′ ) to (j, m). But, from the fact that (j, m)x−1 g∞ x = (j, m),
x must send (j ′ , m′ )g∞ to (j, m), and so x sends both (j ′ , m′ ) and (j ′ , m′ )g∞ to
(j, m), a contradiction. Hence {(j, m) | j ∈ I c (g)} ∩ supp(x) ⊆ Z(g∞ ) ∪ Z(h∞ ).
We now work with i ∈ I(g∞ ). Let t[i] (g) > 0, since replacing g and h with
−1
g and h−1 respectively will provide an argument for t[i] (g) < 0. Assume, for a
contradiction, that for some i ∈ I(g∞ ) we have that
zi (x) > max(zi (g∞ ), zi (h∞ )).
For all m ∈ {0, 1, . . .}, we have that zi (x) + m > zi (x) > max(zi (g∞ ), zi (h∞ )).
Therefore
(i, zi (x) + m)(x−1 g∞ x)−|[i]g | = (i, zi (x) + m)(h∞ )−|[i]g |
=(i, zi (x) + m − t[i] (h∞ )) = (i, zi (x) + m − t[i] (g∞ ))
and similarly
(i, zi (x) + m)(x−1 g∞ x)−|[i]g | = (i, zi (x) + m)x−1 (g∞ )−|[i]g | x
=(i, zi (x) + m)(g∞ )−|[i]g | x = (i, zi (x) + m − t[i] (g∞ ))x
implying that (i, zi (x) + m − t[i](g∞ ))x = (i, zi (x) + m − t[i] (g∞ )), which contradicts
the minimality of zi (x).

Proposition 4.9. Given g, h ∈ Hn ⋊ Sn , there is an algorithm which decides
whether or not g and h are FSym-conjugated, and produces a conjugator in FSym
if one exists.
Proof. By Lemma 4.8, enumerating all possible bijections of the set Z(g∞ )∪Z(h∞ )
is sufficient to decide whether or not g∞ and h∞ are FSym-conjugated. If g∞ and
h∞ are not FSym-conjugated, then g and h are not FSym-conjugated since such a
conjugator would also conjugate g∞ to h∞ . Let y1 ∈ FSym conjugate g∞ to h∞
′
and let g ′ := y1−1 gy1 . By construction, g∞
= h∞ .
Lemma 4.6 states that there is a finite computable set Y such that if g ′ and h
are FSym-conjugated, then there is a conjugator y2 with supp(y2 ) ⊆ Y . Therefore

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

13

enumerating all possible bijections of Y is sufficient to decide whether g ′ and h are
FSym-conjugated. A suitable conjugator of g and h is then y1 y2 . Note that g and
h are FSym-conjugated if and only if g ′ and h are FSym-conjugated.

4.2. Reducing the problem to finding a conjugator in FSym. The previous
section provided us with an algorithm for deciding whether a, b ∈ Hn ⋊ Sn are
FSym-conjugated. Our problem is to decide if a and b are Hn -conjugated. We
start with Lemma 4.11, a simple observation that allows further application of our
algorithm determining conjugacy in FSym.
Definition 4.10. Given g, h ∈ Hn ⋊ Sn and a group G such that FSym(Xn ) 6
G 6 Hn , a witness set of G-conjugation is a finite subset V (g, h, G) of Zn satisfying
that if g, h are G-conjugated, then there is an x ∈ G such that g = x−1 hx and
t(x) ∈ V (g, h, G).
Note that if FSym(Xn ) 6 U, V 6 Hn and {t(u) | u ∈ U } = {t(v) | v ∈ V }, then
U = V . For assume that u ∈ U , v ∈ Hn , and t(u) = t(v). Then t(u−1 v) = 0 which
implies that u−1 v = σ ∈ FSym(Xn ). Thus v = uσ ∈ U , and deciding whether or
not a given h ∈ Hn lies in such a U becomes membership of t(h) in {t(u) | u ∈ U }.
Lemma 4.11. Let FSym(Xn ) 6 G 6 Hn . If, for any g, h ∈ Hn ⋊ Sn it is possible
to compute a witness set of G-conjugation V (g, h, G), then there is an algorithm
which, given any a, b ∈ Hn ⋊ Sn , decides whether they are G-conjugated.
Proof. We use, from the previous section, that there exists an algorithm
for deciding
Pn
if g, h ∈ Hn ⋊ Sn are FSym-conjugated. For any v ∈ Zn with i=1 vi = 0 let
(10)

xv :=

n
Y

−vi

gi

i=2

where the elements {gi | i = 2, . . . , n} are our generators of Hn so that t(xv ) = v.
Thus, if g and h are G-conjugated, then there exists v ∈ V (g, h, G) and x ∈ FSym
such that xv x conjugates g to h. Now, to decide if g and h are G-conjugated, it
is sufficient to check whether any of the pairs {(x−1
v gxv , h) | v ∈ V (g, h, G)} are
FSym-conjugated. This is because
−1
x−1 (x−1
g(xv x) = h
v gxv )x = h ⇔ (xv x)

and so a pair is FSym-conjugated if and only if g and h are G-conjugated.



From this lemma, if, for any g, h ∈ Hn ⋊ Sn , the set V (g, h, Hn ) was computable
(from only g and h), then TCP(Hn ) would be solvable. We shall show that solving
our problem can be achieved by producing an algorithm to decide if elements are
G-conjugated where G is a particular subgroup of Hn .
Definition 4.12. Let g ∈ Hn ⋊ Sn , |σg | denote the order of σg ∈ Sn , and
Hn∗ (g) := {x ∈ Hn | ti (x) ≡ 0 mod ti (g |σg | ) for all i ∈ I(g)},
Hn (g) := {x ∈ Hn | ti (x) ≡ 0 mod |t[i] (g)| for all i ∈ I(g)}.
Recall that if a, b ∈ Hn ⋊ Sn are Hn -conjugated, then σa = σb . Also, from
Lemma 3.8, t[i] (a) = t[i] (b) for all i ∈ Zn . Hence, if a and b are Hn -conjugated,
then Hn∗ (a) = Hn∗ (b) and Hn (a) = Hn (b). Note that Hn∗ (g) 6 Hn (g) since, for any
i ∈ I(g), |t[i] (g)| = |ti (g |[i]g | )| and |ti (g |[i]g | )| divides |ti (g |σg | )|. Given x ∈ Hn (g)
and any infinite orbit Og of g, we have that (Og )x and Og are almost equal, and
hence elements of Hn∗ (g) also have this property.

14

CHARLES GARNET COX

Lemma 4.13. Assume there exists an algorithm which, given any g, h ∈ Hn ⋊ Sn ,
decides whether g and h are Hn∗ (g)-conjugated. Then there exists an algorithm
which, given any g, h ∈ Hn ⋊ Sn , decides whether g and h are Hn -conjugated.
Proof. Given g ∈ Hn ⋊ Sn , construct the set
Pg := {(v1 , . . . , vn ) ∈ Zn : 0 6 vi < ti (g |σg | ) for all i ∈ I(g) and vk = 0 otherwise}.
Note that, for
F any y ∈ Hn ⋊ Sn , Py will be finite. Define xv as in (10) above. Note
that Hn = v∈Pg xv Hn∗ (g) and so any element of Hn is expressible as a product of
xv for some v ∈ Pg and an element in Hn∗ (g). Thus, deciding whether any of the
∗
finite number of pairs {(x−1
v gxv , h) | v ∈ Pg } are Hn (g)-conjugated is sufficient to
decide whether g and h are Hn -conjugated.

Remark 4.14. From Lemma 4.11, if for any g, h ∈ Hn ⋊ Sn a set V (g, h, Hn∗ (g))
is computable, then it is possible to decide whether any g, h ∈ Hn ⋊ Sn are Hn∗ (g)conjugated. By Lemma 4.13, it will then be possible to decide whether any g, h ∈
Hn ⋊ Sn are Hn -conjugated. From Section 2.2, this will mean that TCP(Hn ) is
solvable.
In the following two sections we will show that for any g, h ∈ Hn ⋊ Sn a witness
set of Hn∗ (g)-conjugation is computable from only g and h. In Section 4.3 we show
that the following is computable.
Notation. Let n ∈ {2, 3, . . .} and g, h ∈ Hn ⋊ Sn . Let MI (g, h) denote a number
such that, if g and h are Hn∗ (g)-conjugated, then there is a conjugator x ∈ Hn∗ (g)
with
X
|ti (x)| < MI (g, h).
i∈I(g)

In Section 4.4 we show that for any g, h ∈ Hn ⋊Sn , numbers {yj (g, h) | j ∈ I c (g)}
are computable (using only g and h) such that if there exists an x ∈ Hn∗ (g) which
conjugates g to h, then there is an x′ ∈ Hn∗ (g) which conjugates g to h such that
ti (x′ ) = ti (x) for all i ∈ I(g) and tj (x′ ) = yj (g, h) for all j ∈ I c (g).
Remark 4.15. Note that if the numbers MI (g, h) and {yj (g, h) | j ∈ I c (g)} are
computable using only g and h then the set V (g, h, Hn∗ (g)) is computable from only g
and h. This is because defining V (g, h, Hn∗ (g)) to consist of all vectors v satisfying:
P
i)
i∈I |vi | < MI (g, h);
ii) P
vi = yi for all i ∈ I c (g);
n
iii)
i=1 vi = 0.
provides us with a finite set such that if g and h are Hn∗ (g)-conjugated, then they
are conjugate by an x ∈ Hn∗ (g) with t(x) ∈ V (g, h, Hn∗ (g)).
4.3. Showing that MI (g, h) is computable. Let g, h ∈ Hn ⋊ Sn and x ∈ Hn∗ (g)
conjugate g to h. In this section we will show that a number MI (g, h) is computable
from only the elements g and h.
Notation. Let x ∈ Hn∗ (a) conjugate a, b ∈ Hn ⋊ Sn . Then, for each i ∈ I, let li (x)
be chosen so that ti (x) = li (x)|t[i] (a)|. Note, since ti (x) ≡ 0 mod t[i] (a) for all
i ∈ I, that li (x) ∈ Z for each i ∈ I.

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

15

Recall that σa = σb and that Lemma 3.8 tells us that, if a and b are Hn conjugated, then t[i] (a) = t[i] (b) for every [i] class of σa . Thus, for every i ∈ I and
d1 ∈ N, we have that Xi1 ,d1 (a) = Xi1 ,d1 (b) (the sets from Definition 3.5). Also,
(Xi1 ,d1 (a))x is almost equal to Xi1 ,d1 (a) since the set Xi1 ,d1 (a) consists of all points
(i1 , m) ∈ Xn where m ≡ d1 mod |t[i1 ] (a)|. Moreover (X[i1 ],d1 (a))x is almost equal
to X[i1 ],d1 (a) since X[i1 ],d1 (a) is the union of sets Xis ,ds (a) where for each is ∈ [i1 ]
we have that (Xis ,ds (a))x is almost equal to Xis ,ds (a).
Remark 4.16. From Lemma 3.8, we have for any Hn -conjugated g, h ∈ Hn ⋊ Sn
and any i ∈ I(g) that tiσg (x) − ti (x) = ti (ωh ) − ti (ωg ). If we assume that x ∈
Hn∗ (g), we then have that ti (ωg ) ≡ ti (ωh ) mod |t[i] (g)|. Hence if g and h are Hn∗ (g)
conjugate, then for any infinite orbit Og of g, there must be an infinite orbit of h
which is almost equal to Og . It will therefore not be ambiguous to omit a and b and
simply write Xi1 ,d1 and X[i],d1 .
Definition 4.17. Given g ∈ Hn ⋊ Sn , we define an equivalence relation ∼g on
{[k]g | k ∈ I(g)} as the one generated by setting [i]g ∼g [j]g if and only if there
is an orbit of g almost equal to X[i],d1 (g) ⊔ X[j],e1 (g) for some d1 , e1 ∈ N. Writing
[i] ∼g [j] will not be ambiguous since the relation ∼g will always be used with
respect to the σg -classes of g. Note that if a, b ∈ Hn ⋊ Sn are Hn -conjugated, then
σa = σb and a and b produce the same equivalence relation.
Proposition 4.18. Let a, b ∈ Hn ⋊ Sn be Hn∗ (a)-conjugated. Then there exists
a computable constant K(a, b) (computable from only a and b) such that for any
x ∈ Hn∗ (a) which conjugates a to b and any given i, j where [i] ∼a [j], we have that
|[i]||li (x)| − |[j]||lj (x)| < K(a, b).
Proof. We follow in spirit the proof of [ABM15, Prop 4.3]. For convenience, we
introduce notation to describe a set almost equal to X[i],d1 .
Notation. For any set Y ⊆ Xn , and any q := (q(1), q(2), . . . , q(n)) ∈ Nn , let
Y q := Y \ {(i, m) | i ∈ Zn and m < q(i)}.
We will assume that a, b ∈ Hn ⋊ Sn and x ∈ Hn∗ (a) are known. Let i, j ∈ I
satisfy [i] ∼a [j]. Then there exist d1 , e1 ∈ N such that X[i],d1 ⊔ X[j],e1 is almost
equal to an infinite orbit of a and hence, by Remark 4.16, is almost equal to an
infinite orbit of b. Denote these infinite orbits by Oa and Ob respectively. Note
that Oa x = Ob .
Let ǫk be the smallest integers such that
i) for all k ∈ [i] ∪ [j], ǫk > max(zk (a), zk (b));
ii) for all k ∈ [i], ǫk ≡ dk mod |t[i] (a)|;
iii) for all k ∈ [j], ǫk ≡ ek mod |t[j] (a)|

ǫk if k ∈ [i] ∪ [j]
and define v ∈ Zn by vk =
1 otherwise.
We now have that
⊆ X[i],d1 ∩ Ob ;

X[i],d1

v

⊆ X[i],d1 ∩ Oa ; X[i],d1

X[j],e1

v

⊆ X[j],e1 ∩ Oa ; and X[j],e1

v

v

⊆ X[j],e1 ∩ Ob .

This allows us to decompose Oa and Ob :
Oa = X[i],d1

v

⊔ X[j],e1

v

⊔ Si,j

Ob = X[i],d1

v

⊔ X[j],e1

v

⊔ Ti,j

16

CHARLES GARNET COX

where Si,j and Ti,j are finite sets. Define ǫ′k to be the smallest integers such that
for all k ∈ [i] ∪ [j]
i) ǫ′k > zk (x);
ii) ǫ′k > ǫk + |tk (x)|;
iii) ǫ′k ≡ ǫk mod |t[k] (a)|
 ′
ǫk if k ∈ [i] ∪ [j]
′
n
′
and define v ∈ Z by vk =
1 otherwise.
These conditions for ǫ′k imply that x restricts to a bijection from
X[i],d1

v′

to X[i],d1

v ′ +t(x)

and X[j],e1

v′

to X[j],e1

v ′ +t(x)

.

Hence x restricts to a bijection between the following finite sets


(11)
X[i],d1 v \ X[i],d1 v′ ⊔ X[j],e1 v \ X[j],e1 v′ ⊔ Si,j


(12)
and X[i],d1 v \ X[i],d1 v′ +t(x) ⊔ X[j],e1 v \ X[j],e1 v′ +t(x) ⊔ Ti,j .

By definition, x eventually translates with amplitude tk (x) = lk (x)·|t[k] (a)| for each
k ∈ [i] ⊔ [j]. Thus


X

lk (x)
X[i],d1 |v \ X[i],d1 |v′ +t(x) = X[i],d1 |v \ X[i],d1 |v′ +
k∈[i]



and X[j],e1 |v \ X[j],e1 |v′ +t(x) =

X[j],e1 |v \ X[j],e1 |v′

Now, since (11) and (12) have the same cardinality, we have
X
X
(13)
lk′ (x) + |Ti,j | = |Si,j |
lk (x) +
k∈[i]



+

X

lk′ (x).

k′ ∈[j]

k′ ∈[j]

where |Si,j | and |Ti,j | are constants computable from only a and b. Using Lemma
3.9 we may rewrite each element of {lk (x) | k ∈ [i]} as a computable constant plus
li (x) and each element of {lk′ (x) | k ∈ [j]} as a computable constant plus lj (x).
Let Ai,j denote the sum of all of these constants (which ‘adjust’ the values of the
translation lengths of x amongst each σa class). Now (13) becomes
|[i]|li (x) + |[j]|lj (x) + Ai,j + |Ti,j | = |Si,j |.
By the generalised triangle inequality we have
|[i]||li (x)| 6 |[j]||lj (x)| + |Ai,j | + |Si,j | + |Ti,j |
and |[j]||lj (x)| 6 |[i]||li (x)| + |Ai,j | + |Si,j | + |Ti,j |.
Thus
|[i]||li (x)| − |[j]||lj (x)| 6 |Ai,j | + |Si,j | + |Ti,j | =: C(i, j)
|[j]||lj (x)| − |[i]||li (x)| 6 |Ai,j | + |Si,j | + |Ti,j | = C(j, i)
⇒ |[i]||li (x)| − |[j]||lj (x)| 6 C(i, j).
We may then complete this process for all pairs of rays i′ , j ′ ∈ I such that there
exist d′1 , e′1 ∈ N such that X[i′ ],d′1 ⊔ X[j ′ ],e′1 is almost equal to an infinite orbit of a.
Let Ĉ(a, b) denote the maximum of all of the C(i′ , j ′ ).

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

17

Now, consider if k, k ′ ∈ I satisfy [k] ∼a [k ′ ]. This means that there exist
(0) (1)
(f ) (1)
(f ) (f +1)
k (1) , k (2) , . . . , k (f ) ∈ I and d1 , d1 , . . . , d1 , e1 , . . . , e1 , e1
∈ N such that
for all p ∈ Zf −1
X[k],d(0) ⊔ X[k(1) ],e(1) , X[k(p) ],d(p) ⊔ X[k(p+1) ],e(p+1) , and X[k(f ) ],d(f ) ⊔ X[k′ ],e(f +1)
1

1

1

1

1

1

are almost equal to orbits of a. We wish to bound |[k]||lk (x)| − |[k ′ ]||lk′ (x)| , and
will do this by producing bounds for
|[k]||lk (x)| − |[k ′ ]||lk′ (x)| and |[k ′ ]||lk′ (x)| − |[k]||lk (x)|.
We start by rewriting |[k]||lk (x)| − |[k ′ ]||lk′ (x)| as


|[k]||lk (x)| − |[k (1) ]||lk(1) (x)| + |[k (1) ]||lk(1) (x)| − |[k (2) ]||lk(2) (x)| + . . .


. . . + |[k (f −1) ]||lk(f −1) (x)| − |[k (f ) ]||lk(f ) (x)| + |[k (f ) ]||lk(f ) (x)| − |[k ′ ]||lk′ (x)|
which by definition is bounded by
C(k, k (1) ) +

f
−1
X

C(k (q) , k (q+1) ) + C(k (f ) , k ′ )

q=1

and so

|[k]||lk (x)| − |[k ′ ]||lk′ (x)| 6 C(k, k (1) ) +

f
−1
X

C(k (q) , k (q+1) ) + C(k (f ) , k ′ )

q=1

6 (f + 1)Ĉ(a, b)
6 n · Ĉ(a, b)
′

Similarly, |[k ]||lk′ (x)| − |[k]||lk (x)| 6 (f + 1)Ĉ(a, b) 6 n · Ĉ(a, b). Thus n · Ĉ(a, b) + 1
is a suitable value for K(a, b).
Now we note that, without knowledge of the conjugator x, for all k, k ′ such that
X[k],d1 ⊔ X[k′ ],e1 is almost equal to an infinite orbit of a, the sets Sk,k′ and Tk,k′ are
computable, and so the constants C(k, k ′ ) are also computable. Hence Ĉ(a, b) and
so K(a, b) are computable using only the elements a and b.

We shall now show that, if a is conjugate to b in Hn∗ (a), then there is a conjugator
x ∈ Hn∗ (a) such that for all i ∈ I there exists a j ∈ I such that [j] ∼a [i] and
tj (x) = 0. This will allow us to use the previous proposition to bound |tk (x)| for all
[k] ∼a [j]. We will produce such a conjugator using an adaptation of the element
defined in [ABM15, Lem 4.6]. As with their argument, we again use Lemma 4.7,
which stated that if x ∈ G conjugates a to b then y ∈ G also conjugates a to b if
and only if there exists a c ∈ CG (a) such that cx = y.
Notation. Let g ∈ Hn ⋊ Sn and i ∈ I(g). Then Cg ([i]) := {k | [k] ∼g [i]} ⊆ I(g).
This is the set of all k ∈ Zn corresponding to rays of Xn whose σg -class is related
to [i]g .
This following definition is inspired by [ABM15, Lem 4.6].
Definition 4.19. Let h ∈ Hn ⋊Sn , i ∈ I(h), and g ∈ CHn (h). Then g[i] ∈ Sym(Xn )
is defined to be equal to the product of all cycles of g∞ whose support have infinite
intersection with a set Xj,d (g) where j ∈ Ch ([i]) and d ∈ N.

18

CHARLES GARNET COX

Lemma 4.20. Let n ∈ {2, 3, . . .}, h ∈ Hn ⋊ Sn , g ∈ CHn (h) and i ∈ I. If ti (g) 6= 0,
then tj (g) 6= 0 for all j ∈ Ch ([i]).
Proof. If j ∈ [i], then by Lemma 3.9, tj (g) = ti (g) 6= 0.
Since the equivalence relation ∼h is generated by pairs of classes [i] 6= [j] with
X[i],d (h) ⊔ X[j],e (h) for some d, e ∈ N almost equal to some infinite orbit of h, it is
enough to prove the lemma in that case. Let (i, m) ∈ X[i],d with m > zi (g) and let
|s| >> 0 so that (i, m)hs = (j ′ , m′ ) ∈ X[j],e where m′ > zj ′ (g). If tj ′ (g) = 0, then
(i, m)hs gh−s = (i, m) 6= (i, m + ti (g)) = (i, m)g. Hence tj ′ (g) 6= 0 and, therefore,
tk (g) 6= 0 for all k ∈ [j ′ ] = [j].

Lemma 4.21. Let h ∈ Hn ⋊ Sn , i ∈ I(h), and g ∈ CHn (h). Then g has no
finite orbits within supp((h|σh | )[i] ). Also, if tj (g) 6= 0 for some j ∈ Ch ([i]), then
supp(g[i] ) = supp((h|σh | )[i] ).
Proof. Consider if {(k, m)g d | d ∈ Z} is finite for some (k, m) ∈ supp((h|σh | )[i] ).
Then, for all e ∈ Z, {(k, m)h−e g d he | d ∈ Z} is finite since h−e g d he = g d . But this
implies that g has infinitely many finite orbits, contradicting that g ∈ Hn .
From now on fix a j ∈ Ch ([i]) and m > max{zj (g), zj (h)}. By Lemma 4.20
if tj (g) 6= 0 for some j ∈ Ch ([i]), then tk (g) 6= 0 for all k ∈ Ch ([i]). Consider if (j, m)g d 6∈ supp(h∞ ) for some d ∈ Z. Then there exists e ∈ N such
that (j, m)g d he g −d = (j, m) and because g ∈ CHn (g) this is a contradiction:
(j, m)g d he g −d = (j, m)he 6= (j, m).
Now consider if (j, m)g d 6∈ supp((h|σh | )[i] ). From the previous two paragraphs,
we may assume that (j, m)g d lies in an infinite orbit of h and an infinite orbit of g.
Hence we may choose |d| >> 0 so that (j, m)g d = (j ′ , m′ ) where j ′ 6∈ Ch ([i]) and
m′ > max{zj ′ (g), zj ′ (h)}. If f t[j ′ ] (h) > 0 and f t[j ′ ] (h) − dtj ′ (g) > 0, then
′

(j, m)g d hf |[j ]| g −d = (j ′ , m′ + f t[j ′ ] (h) − dtj ′ (g))
′

and so {(j, m)g d hf |[j ]| g −d | f ∈ Z} has infinite intersection with Rj ′ . But this
′
contradicts that j ′ 6∈ Ch ([i]) i.e. that {(j, m)h|[j ]|f | f ∈ Z} ∩ Rj ′ is finite. Hence
supp(g[i] ) ⊆ supp((h|σh | )[i] ). Assume that supp((h|σh | )[i] ) 6⊆ supp(g[i] ). Then there
exists e ∈ Z such that (j, m)he 6∈ supp(g). But then (j, m)he gh−e = (j, m) implies
that (j, m)g = (j, m), contradicting that (j, m) ∈ supp(g).

Lemma 4.22. Let h ∈ Hn ⋊ Sn and g ∈ CHn (h). Then, for every i ∈ I(h),
g[i] ∈ CHn (h). Moreover, tj (g[i] ) = tj (g) if j ∈ Ch ([i]) and tj (g[i] ) = 0 otherwise.
Proof. If tj (g) = 0 for some j ∈ Ch ([i]), Lemma 4.20 states that tk (g) = 0 for all
k ∈ Ch ([i]), and hence g[i] = idSym(Xn ) and the statement trivially holds. We are
therefore free to apply Lemma 4.21 so that supp(g[i] ) = supp((h|σh | )[i] ). Thus for
each k 6∈ Ch ([i]), supp(g[i] ) ∩ Rk is finite and for each k ∈ Ch ([i]) the action of
g[i] can only differ from the action of g on a finite subset of Rk . It follows that
g[i] ∈ Hn and that tj (g[i] ) = tj (g) if j ∈ Ch ([i]) and tj (g[i] ) = 0 otherwise. Finally
we show h and g[i] commute. If (k, m) ∈ supp((h|σh | )[i] ), then (k, m) ∈ supp(g)
and (k, m) ∈ supp(g[i] ). Hence (k, m)gh = (k, m)hg ⇒ (k, m)g[i] h = (k, m)hg[i] . If
(k, m) 6∈ supp((h|σh | )[i] ), then (k, m), (k, m)h 6∈ supp(g[i] ).

From this lemma, if h ∈ Hn ⋊ Sn and i ∈ I(h), then (h|σh | )[i] ∈ CHn (h).

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

19

Lemma 4.23. Let a, b ∈ Hn ⋊ Sn be conjugate by some x ∈ Hn∗ (a). Then there
exists a conjugator x′ ∈ Hn∗ (a) which, for each i ∈ I, there is a j such that [j] ∼a [i]
and tj (x′ ) = 0.
Proof. Let x ∈ Hn∗ (a) conjugate a to b. From the definition of Hn∗ (a), we have for
all i ∈ I that ti (x) ≡ 0 mod |ti (a|σa | )|. Thus there exist constants m1 , . . . , mn ∈ Z
such that, for all i ∈ I,
ti (x) = mi |ti (a|σa | )|.
1
u
Let R(a)
Qu:= {j , . . . j } ⊆ I be a set of representatives for the ∼a -classes (so that
a∞ = s=1 a[j s ] ). Thus, given i ∈ I, there is a unique d ∈ {1, . . . , u} such that
[j d ] ∼a [i]. Choose some j ∈ R(a) and consider
(a−|σa |mj )[j] x.

By Lemma 4.22 (ad|σa | )[j] ∈ CHn (a) and (ad|σa | )[j] ∈ Hn∗ (a) for every d ∈ Z. Now
tj ((a−|σa |mj )[j] x) = 0
and (a−|σa |mj )[j] x conjugates a to b by Lemma 4.7. Thus a suitable candidate for
x′ is


Y

(a−|σa |mj )[j]  x.

j∈R(a)

Recall, given a, b ∈ Hn ⋊ Sn , that MI (a, b) was a number such that if a and b
∗
∗
are
P Hn (a)-conjugated, then there exists x ∈ Hn (a) which conjugates a to b with
i∈I |ti (x)| < MI (a, b).

Proposition 4.24. Let a, b ∈ Hn ⋊ Sn be Hn∗ (a)-conjugated. Then a number
MI (a, b) is computable.
F
Proof. Let S(a) := {i1 , . . . , iv } ⊆ I be representatives of I, so that i∈S(a) [i] = I
and, for any distinct d, e ∈ Zv , we have [id ] 6= [ie ] . We work for a computable
bound for {|li (x)| | i ∈ S(a)} since ti (x) = li (x)|t[i] (a)| and the numbers |t[i] (a)| are
computable. Lemma 3.9 from Section 3.2 will then provide a bound for |li (x)| for
all i ∈ I. Proposition 4.18 says that there is a computable number K(a, b) =: K
such that for every i, j ∈ I where [i] ∼a [j], we have
|[i]||li (x)| − |[j]||lj (x)| < K.
By Lemma 4.23, we can assume that for any given i ∈ S(a), either ti (x) = 0 or
there exists a j ∈ I such that [j] ∼a [i] and tj (x) = 0. If ti (x) = 0, then we are
done. Otherwise,
K
< K.
|[i]||li (x)| − |[j]||lj (x)| < K ⇒ |[i]||li (x)| < K ⇒ |li (x)| <
|[i]|
Continuing this process for each i ∈ S(a) (of which there are at most n) implies
that
X
|li (x)| < nK.
i∈S(a)

We may then compute, using Lemma 3.9 from Section 3.2, a number K ′ such that
X
|li (x)| < K ′ .
i∈I

20

CHARLES GARNET COX

A suitable value for MI (a, b) is therefore K ′ · max {|t[i] (a)| : i ∈ I}.



4.4. Showing that the numbers {yj (g, h) | j ∈ I c } are computable. In this
section we will show, given any g, h ∈ Hn ⋊ Sn , numbers {yj (g, h) | j ∈ I c (g)}
are computable such that if there exists an x ∈ Hn∗ (g) which conjugates g to h,
then there is an x′ ∈ Hn∗ (g) which conjugates g to h such that ti (x′ ) = ti (x) for all
i ∈ I(g) and tj (x′ ) = yj (g, h) for all j ∈ I c (g).
Note that the condition on elements to be in Hn∗ (g) provides no restriction on
the translation lengths for the rays in I c (g). This means that the arguments in this
section work as though our conjugator is in Hn .
From Section 3.1 we have that for any g ∈ Hn ⋊ Sn , any point (j, m) such that
j ∈ I c (g) and m > zj (g) lies in an orbit of g of size |[j]|.
Notation. Let g ∈ Hn ⋊ Sn and r ∈ N. Then Irc (g) := {j ∈ I c (g) | |[j]| = r}. Also,
′
we may choose jr1 , . . . , jru such that [jr1 ] ∪ [jr2 ] ∪ . . . ∪ [jru ] = Irc (g) and [jrk ] 6= [jrk ] for
every distinct k, k ′ ∈ Zu . We shall say that jr1 , . . . , jru are representatives of Irc (g).
Lemma 4.25. Let a ∈ Hn ⋊ Sn . Fix an r ∈ N, let jr1 , . . . , jru be representatives of
Irc (a), and let d, d′ be distinct numbers in Zu . Fix an ordering on the r-cycles of a
within Z(a). Label these σ1 , . . . , σf and, for each e ∈ Zf , let (ie , me ) ∈ supp(σe ).
Now define cjrd ,jrd′ ∈ Sym(Xn ) by

(i, m + 1)
if i ∈ [jrd ] and m > zi (a)


′


if i ∈ [jrd ] and m > zi (a) + 1

 (i, m − 1)s−1
′

(i1 , m1 )a
if (i, m) = (jrd , zjrd′ (a))as−1 for some s ∈ Zr
(i, m)cjrd ,jrd′ :=

(ie+1 , me+1 )as−1 if (i, m) = (ie , me )as−1 for some e ∈ Zf −1 , s ∈ Zr




if (i, m) = (if , mf )as−1 for some s ∈ Zr
(j d , z d (a))as−1

 r jr
(i, m)
otherwise.
Then cjrd ,jrd′ ∈ CHn (g).

Proof. Note that cjrd ,jrd′ produces a bijection on the r-cycles of g, and so conjugates
g to g i.e. cjrd ,jrd′ ∈ CSym(Xn ) (g). By construction it satisfies the condition to be in
Hn .

Lemma 4.26. Let g, h ∈ Hn ⋊ Sn and r ∈ N. If x1 , x2 ∈ Hn both conjugate g to
h and jr1 , . . . , jru are representatives of Irc (g), then
u
u
X
X
tjrs (x1 ) =
tjrs (x2 ).
s=1

s=1

Proof. Given x1 , x2 ∈ Hn which both conjugate g to h, it is possible to produce,
by multiplying by an element of the centraliser which is a product of elements
cjr1 ,k (with k ∈ {jr2 , . . . , jru }), elements x′1 , x′2 ∈ Hn which both conjugate g to h
and for which tjrs (x′1 ) = 0 = tjrs (x′2 ) for all s ∈ {2, . . . , u} and so by Lemma 3.9,
tj (x′1 ) = tj (x′2 ) for all j ∈ Irc (g) \ [jr1 ]. By construction we then have that
tjr1 (x′1 ) =

u
X
s=1

tjrs (x1 ) and tjr1 (x′2 ) =

u
X

tjrs (x2 ).

s=1

Now consider y := x′1 (x′2 )−1 . By construction tj (y) = 0 for all j ∈ Irc (g) \ [jr1 ]
since tj (x′1 ) = tj (x′2 ) for all j ∈ Irc (g) \ [jr1 ]. Also tj (y) = tjr1 (y) for all j ∈ [jr1 ]
since y conjugates g to g (and so we also have that y ∈ CHn (g)). If tjr1 (y) 6= 0,

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

21

then y contains an infinite cycle with support intersecting the branch jr1 and a
branch jp ∈ I c (g) \ Irc (g) so that |[jp ]| = p 6= r i.e. the infinite cycle contains
(jr1 , m1 ), (jp , m2 ) ∈ Xn . This means there exists an e ∈ Z such that (jr1 , m1 )y e =
(jp , m2 ). But then y e ∈ CHn (g) and y e sends an r-cycle to an p-cycle where r 6= p,
a contradiction. Hence for any x, x′ ∈ Hn which both conjugate g to h,
u
u
X
X
tjrs (x) =
tjrs (x′ ).
s=1

s=1



From this proof, the following is well defined.
Notation. Let g, h ∈ Hn ⋊ Sn , r ∈ N and jr1 , . . . , jru be representatives of Irc (g).
Then M{jr1 ,...,jru } (g, h) denotes the number such that, for any x ∈ Hn∗ (g) which
Pu
conjugates g to h, d=1 tjrd (x) = M{jr1 ,...,jru } (g, h). Since we will fix a set of representatives, we will often denote M{jr1 ,...,jru } (g, h) by Mr (g, h).
We will show that one combination {yd ∈ Z | d ∈ Zu } is computable in order
to show, for any g, h ∈ Hn ⋊ Sn and any r ∈ N, that Mr (g, h) is computable. The
following will be useful for this. Recall that for any g ∈ Hn ⋊ Sn , Z(g) := {(i, m) ∈
Xn | i ∈ Zn and m < zi (g)}.
Notation. Let g ∈ Hn ⋊ Sn and r ∈ {2, 3, . . .}. Then ηr (g) := supp(gr Z(gr )) /r
denotes the number of orbits of gr Z(gr ) of size r. This is well defined since Lemma
4.3 states that gr restricts to a bijection on Z(gr ). Also, let η1 (g) := |Z(g) \
(supp(g Z(g))|. Since Z(gr ) is finite for all r ∈ N, we have that ηr (g) is finite for
all r ∈ N.
Lemma 4.27. Let g, h ∈ Hn ⋊ Sn , r ∈ N and jr1 , . . . , jru be representatives of Irc (g).
Then M{jr1 ,...,jru } (g, h) and the numbers {yj (g, h) | j ∈ I c (g)} are computable (using
only the elements g and h).
Proof. For each r ∈ N, any conjugator of g and h must send the r-cycles of g to
the r-cycles of h. Fix an r ∈ N and let jr1 , . . . , jru be representatives of Irc (g). Given
any g, h ∈ Hn ⋊ Sn which are Hn -conjugated, let
(14)

yk (g, h) := zk (h) − zk (g) for all k ∈ {jr2 , . . . , jru }.

(15)

yjr1 (g, h) := zjr1 (h) − zjr1 (g) + ηr (g) − ηr (h).

We work towards proving that the values for yk (g, h) defined in (14) and (15) are
suitable in 3 steps. First, consider if ηr (g) = ηr (h). This means that there is a
conjugator in FSym which conjugates gr Z(gr ) to hr Z(hr ) and hence the values
are sufficient. Secondly, consider if ηr (g) = ηr (h) + d for some d ∈ N. In this case,
first send ηr (h) r-cycles in Z(gr ) to those in Z(hr ). Then send the d remaining
cycles in Z(gr ) to the first d r-cycles on the branches [jr1 ] by increasing yjr1 (g, h)
by d. Finally, if ηr (g) = ηr (h) − e for some e ∈ N, then send the ηr (g) r-cycles in
Z(gr ) to r-cycles in Z(hr ) and then send the first e r-cycles of g on the branches
[jr1 ] to the remaining r-cycles in Z(hr ) by decreasing yjr1 (g, h) by e. With all of
these cases, the values defined in (14) and (15) are suitable.

Proof of Theorem 1. From Remark 4.14 and Remark 4.15 of Section 4.2, TCP(Hn )
is solvable if, given a, b ∈ Hn ⋊ Sn , the numbers MI (a, b) and {yj (a, b) | j ∈ I c } are

22

CHARLES GARNET COX

computable from only a and b. The computability of these numbers was shown,
respectively, in Proposition 4.24 and Lemma 4.27.

5. Applications of Theorem 1
Our strategy is to use [BMV10, Thm. 3.1]. We first set up the necessary notation.
Definition 5.1. Let H be a group and G E H. Then AGEH denotes the subgroup
of Aut(G) consisting of those automorphisms induced by conjugation by elements
of H i.e. AGEH := {φh | h ∈ H}.
Definition 5.2. Let G be a finitely presented group. Then A 6 Aut(G) is orbit
decidable if, given any a, b ∈ G, there is an algorithm which decides whether there
is a φ ∈ A such that aφ = b. If Inn(G) 6 A, then this is equivalent to finding a
φ ∈ A and x ∈ G such that x conjugates aφ to b.
The algorithmic condition in the following theorem means that certain computations for D, E, and F are possible. This is satisfied by our groups being given by
recursive presentations, and the maps between them being defined by the images
of the generators.
Theorem 5.3. (Bogopolski, Martino, Ventura [BMV10, Thm. 3.1]). Let
1 −→ D −→ E −→ F −→ 1
be an algorithmic short exact sequence of groups such that
(i) D has solvable twisted conjugacy problem,
(ii) F has solvable conjugacy problem, and
(iii) for every 1 6= f ∈ F , the subgroup hf i has finite index in its centralizer
CF (f ), and there is an algorithm which computes a finite set of coset representatives, zf,1 , . . . , zf,tf ∈ F ,
CF (f ) = hf izf,1 ⊔ · · · ⊔ hf izf,tf .
Then, the conjugacy problem for E is solvable if and only if the action subgroup
ADEE = {φg | g ∈ E} 6 Aut(D) is orbit decidable.
Remark. For all that follows, the action subgroup ADEE is provided as a recursive
presentation where the generators are words from Aut(D).
5.1. Conjugacy for finite extensions of Hn . We shall say that B is a finite
extension of A if A E B and A is finite index in B. The following is well known.
Lemma 5.4. If G is finitely generated and H is a finite extension of G, then H is
finitely generated.
Proposition 5.5. Let n ∈ {2, 3, . . .}. If E is a finite extension of Hn , then CP(E)
is solvable.
Proof. Within the notation of Theorem 5.3, set D := Hn and F to be a finite group
so to realise E as a finite extension of Hn . Conditions (ii) and (iii) of Theorem
5.3 are satisfied since F is finite. Theorem 1, the main theorem of the previous
section, states that condition (i) is satisfied. Thus CP(E) is solvable if and only if
AHn EE = {φe | e ∈ E} is orbit decidable. We note that AHn EE contains a copy
of Hn (since Hn is centreless). Moreover, it can be considered as a group lying
between Hn and Hn ⋊ Sn . Hence AHn EE is isomorphic to a finite extension of

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

23

Hn , and so by Lemma 5.4 is finitely generated. Thus AHn EE = hφe1 , φe2 , . . . , φek i
where {e1 , . . . , ek } is a finite generating set of E. From Lemma 4.4, given any
g ∈ NSym(Xn ) (Hn ) ∼
= Aut(Hn ), we may compute σg : the isometric permutation
of the rays induced by g. Thus we may compute hσei | i ∈ Zk i =: Eσ . Now,
given a, b ∈ Hn , our aim is to decide whether there exists φe ∈ AHn EE such that
(a)φe = b. Since Inn(Hn ) 6 AHn EE , this is equivalent to finding a τ ∈ Eσ and
x ∈ Hn such that (xτ )−1 a(xτ ) = b, which holds if and only if x−1 ax = τ bτ −1 .
Finally, since Eσ is finite (there are at most n! permutations of the rays), searching for an x ∈ Hn which conjugates a to σe bσe−1 for all σe ∈ Eσ provides us with a
suitable algorithm. Searching for such a conjugator can be achieved by Theorem 1
or [ABM15, Thm. 1.2].

5.2. Describing Aut(U ) for U finite index in Hn . Recall that g2 , . . . , gn were
elements of Hn such that gi : translates the first branch of Xn by 1; translates
the ith branch by -1; sends (i, 1) to (1, 1); and does not move any points of the
other branches (which meant that, if n ∈ {3, 4, . . .}, then Hn = hgi | i = 2, . . . , ni).
For any given n ∈ {2, 3, . . .}, the family of finite index subgroups Up 6 Hn were
defined (for p ∈ N) in [BCMR14] as follows. Note that FAlt(X) denotes the index
2 subgroup of FSym(X) consisting of all even permutations on X.
Up := h FAlt(Xn ), gip | i ∈ {2, ..., n} i
Notation. Let A 6f B denote that A has finite index in B.
Let n ∈ {3, 4, . . .}. If p is odd, then Up consists of all elements of Hn whose
eventual translation lengths are all multiples of p. If p is even, then Up consists of
all elements u of Hn whose eventual translations are all multiples of p and
n
Y
t (u)
(16)
gi i ∈ FAlt(Xn )
u
i=2

i.e. FSym(Xn ) 6 Up if and only if p is odd. This can be seen by considering, for
some i, j ∈ Zn , the commutator of gip and gjp . This will produce p 2-cycles which
will produce an odd permutation if and only if p is odd. If n = 2, then for all p ∈ N
all u ∈ Up 6 H2 will satisfy (16).
Lemma 5.6 (Burillo, Cleary, Martino, Röver [BCMR14]). Let n ∈ {2, 3, . . .}. For
every finite index subgroup U of Hn , there exists a p ∈ 2N with
FAlt(Xn ) = Up′ < Up 6f U 6f Hn
where Up′ denotes the commutator subgroup of Up .
Alternative proof. Let n ∈ {2, 3, . . .} and let U 6f Hn . Thus FAlt ∩U 6f FAlt.
Since FAlt is both infinite and simple, FAlt 6 U . Let πn : Hn → Zn−1 , g 7→
(t2 (g), . . . , tn (g)). Thus (U )πn 6f Zn−1 and so there is a number d ∈ N such that
(dZ)n−1 6 (U )πn ([(U )πn : Zn−1 ] is one such value for d). This means that for any
k ∈ Zn \ {1} there exists a u ∈ U such that tk (u) = −d, t1 (u) = d, and ti (u) = 0
otherwise. Moreover, for each k ∈ Zn \ {1} there is a σ ∈ FSym such that gkd σ ∈ U .
First, let n ∈ {3, 4, . . .}. Since FAlt 6 U , we may assume that either σ is trivial or
is a 2-cycle with disjoint support from supp(gk ). Thus (gkd σ)2 = gk2d ∈ U . If n = 2,
we may assume that σ is either trivial or equal to ((1, s) (1, s + 1)) for any s ∈ N.

24

CHARLES GARNET COX

Now, by direct computation, g2d ((1, 1) (1, 2))g2d ((1, d + 1) (1, d + 2)) = g22d . Thus,
for any n ∈ {2, 3, . . .},
hg22d , . . . , gn2d , FAlt(Xn )i 6 U.
Hence, if p := 2d, then Up 6 U .

Remark. {(Up )πn | p ∈ N} are the congruence subgroups of Zn−1 .
Now, given U 6f Hn , our strategy for showing that CP(U ) is solvable is as
follows. First, we show for all p ∈ N that TCP(Up ) is solvable. Using Theorem 5.3,
we then obtain that all finite extensions of Up have solvable conjugacy problem.
By the previous lemma, we have that any finite index subgroup U of Hn is a finite
extension of some Up (note that Up E U since Up E Hn ). This will show that CP(U )
is solvable.
TCP(Up ) requires knowledge of Aut(Up ). From [Cox16, Prop. 1], we have that
any group G for which there exists an infinite set X where FAlt(X) 6 G 6 Sym(X)
has NSym(X) (G) ∼
= Aut(G) by the map ρ 7→ φρ . By Lemma 5.6 any finite index
subgroup of Hn contains FAlt(Xn ). Thus, if U 6f Hn , then NSym(Xn ) (U ) ∼
=
Aut(U ) by the map ρ 7→ φρ . In fact we may show that a stronger condition holds.
Lemma 5.7. If 1 6= N E Hn , then FAlt(Xn ) 6 N .
Proof. We have that N ∩ FAlt(Xn ) E Hn . Since FAlt(Xn ) is simple, the only way
for our claim to be false is if N ∩ FAlt(Xn ) were trivial. Now, N 6 Hn , and so
[N, N ] 6 FSym(Xn ). Thus [N, N ] must be trivial, and so N must be abelian. But
the condition for elements α, β ∈ Sym(Xn ) to commute (that, when written in
disjoint cycle notation, either a power of a cycle in α is a power of a cycle in β or
the cycle in α has support outside of supp(β)) is not preserved under conjugation
by FAlt(Xn ), and so cannot be preserved under conjugation by Hn i.e. N is not
normal in Hn , a contradiction.

Remark. It follows that all Houghton groups are monolithic: each has a unique
minimal normal subgroup which is contained in every non-trivial normal subgroup.
The unique minimal normal subgroup in each case will be FAlt(Xn ).
We now introduce notation to help describe any finite index subgroup of Hn
(where n ∈ {2, 3, . . .}).
Notation. For each i ∈ Zn , let Ti (U ) := min{ti (u) | u ∈ U and ti (u) > 0}.
Pk
Furthermore for all k ∈ Zn , let T k (U ) := i=1 Ti (U ) and let T 0 (U ) := 0.

We will now introduce a bijection φU : Xn → XT n (U) . This bijection will induce
an isomorphism φ̂U : Sym(Xn ) → Sym(XT n (U) ) which restricts to an isomorphism
NSym(Xn ) (U ) → NSym(XT n (U ) ) ((U )φ̂U ).

Our bijection φU will send the ith branch of Xn to Ti (U ) branches in XT n (U) . For
simplicity let g1 := g2−1 . Now, for any i ∈ Zn and d ∈ N,
T (U)

Xi,d (gi i

T (U)

) = {(i, m) | m ≡ d mod |ti (gi i

)|}

T (U)
|ti (gi i )|
th

where
Thus the i

= Ti (U ) by the definition of gi .
branch of Xn may be partitioned into Ti (U ) parts:
T (U)

Xi,1 (gi i

T (U)

) ⊔ Xi,2 (gi i

T (U)

) ⊔ . . . ⊔ Xi,Ti (U) (gi i

).

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

25

We will now define the bijection φU by describing the image under φU of all points
T (U)
T (U)
in each set Xi,d (gi i ) where i ∈ Zn and d ∈ ZTi (U) . Let (i, m) ∈ Xi,d (gi i ).
Then


m−d
((i, m))φU := T i−1 (U ) + d,
+1
Ti (U )
T (U)

i.e. φU sends, for all i ∈ Zn and d ∈ ZTi (U) , the ordered points of Xi,d (gi i ) to
the ordered points of the (T i−1 (U ) + d)th branch of XT n (U) . An example of this
bijection with n = T1 (U ) = T2 (U ) = T3 (U ) = 3 is given below.

The set Xn

The set XT n (U )

Figure 2. Our bijection between Xn and XT n (U) , which can be
visualised by rotating the rectangles 90 degrees clockwise.
We now describe the image of U under φ̂U . First, φ̂U preserves cycle type.
Thus FAlt(XT n (U) ) 6 (U )φ̂U . Moreover FSym(XT n (U) ) 6 (U )φ̂U if and only if
FSym(Xn ) 6 U . The following will be useful to describe (U )φ̂U .
Notation. For any n ∈ N and any i ∈ Zn , let Ri := i × N, the ith branch of Xn
or XT n (U) , and Qi := (Ri )φU , so that Qi consists of Ti (U ) branches of XT n (U) .
Lemma 5.8. Let n ∈ {2, 3, . . .} and U 6f Hn . If u ∈ U , then (u)φ̂U ∈ HT n (U) .
Moreover, for each i ∈ ZT n (U) there exists a g ∈ (U )φ̂U such that ti (g) = 1.
Proof. Let n ∈ {2, 3, . . .} and U 6f Hn . Since φ̂U preserves cycle type, outside of a finite set, (u)φ̂U consists of fixed points and infinite cycles. If i ∈ Zn
and m > zi (u) + |ti (u)|, let (i′ , m′ ) = (i, m)φU and note, since Ti (U ) ti (u), that
(i′ , m′ )(u)φ̂U = (i′ , m′ + ti (u)/Ti (U )). Hence (u)φ̂U ∈ HT n (U) . Now, from the
definition of Ti (U ), there exists a g ∈ (U )φ̂U such that ti (g) = 1.

Using the above notation we have, for any g ∈ (U )φ̂U , that
(17)

if ti (g) = d, then tj (g) = d for all j such that Rj ⊆ Qi

i.e. for any u ∈ U and any i ∈ Zn , the eventual translation lengths of (u)φ̂ for the
branches in Qi must be the same.
Lemma 5.9. Let n ∈ {2, 3, . . .} and U 6f Hn . Then NSym(XT n (U ) ) ((U )φ̂U ) 6
HT n (U) ⋊ R where R 6 ST n (U) consists of isometric permutations of the rays of
XT n (U) . Thus if ρ ∈ NSym(Xn ) (U ), then (ρ)φ̂U ∈ HT n (U) ⋊ ST n (U) .
Proof. Let G := NSym(XT n (U ) ) ((U )φ̂U ). Describing G will be simpler than describing NSym(Xn ) (U ). We will do this in three stages: we first show, for any ρ ∈ G,
that the image under ρ of each ray of XT n (U) is almost equal to a ray of XT n (U) ;

26

CHARLES GARNET COX

secondly we show that ρσρ−1 ∈ HT n (U) , meaning that G 6 HT n (U) ⋊ ST n (U) ; and
finally we will describe a subgroup of R 6 ST n (U) such that {σρ | ρ ∈ G} 6 R.
Let i, j ∈ ZT n (U) and ρ ∈ G. Consider if (Ri )ρ and Rj have infinite intersection
but are not almost equal. Either (Ri )ρ has infinite intersection with Rj and Rj ′
where j ′ 6= j, or there is an i′ 6= i such that (Ri′ )ρ is almost equal to an infinite
subset of Rj . For the first case, let g ∈ (U )φ̂U be chosen so that ti (g) = 1. Thus
g has an infinite cycle containing {(i, m) | m > zi (g)}. Let (i′ , m′ ) = (i, zi (g))ρ.
Then {(i′ , m′ )(ρ−1 gρ)d | d ∈ N} = {(i′ , m′ )ρ−1 g d ρ | d ∈ N} = {(i, m)ρ | m > zi (g)}
which has infinite intersection with Rj and Rj ′ . But from the description of orbits
of Hn in [ABM15], ρ−1 gρ 6∈ HT n (U) and so (ρ−1 gρ)φ̂−1
U 6∈ U i.e. ρ 6∈ G. The second
case reduces to the first, since it implies that (Rj )ρ−1 has infinite intersection with
Ri and Ri′ . Hence if (Ri )ρ and Rj have infinite intersection (where i, j ∈ ZT n (U) ),
then (Ri )ρ and Rj are almost equal.
Let ρ ∈ G and let ω := ρσρ−1 ∈ Sym so that ω sends almost all of each branch of
XT n (U) to itself. Since, for each branch, ω preserves the number of infinite orbits
induced by g, we have for all k ∈ ZT n (U) and all g ∈ (U )φ̂U that tk (ω −1 gω) = tk (g).
Fix an i ∈ ZT n (U) and choose g ∈ HT n (U) so that ti (g) = 1. Note that g −1 ωgω −1 ∈
FSym. Thus there is a d ∈ N such that, for all m > d, (i, m)g −1 ωgω −1 = (i, m).
We may now assume for some m′ > d that (i, m′ )ω = (i, m′ + s), where s ∈ N. This
is because ω sends only finitely many points of Ri to another branch and to ensure
the positivity of s we may replace ω with ω −1 . Hence
(i, m′ + 1)g −1 ωgω −1 = (i, m′ )ωgω −1 = (i, m′ + s)gω −1 = (i, m′ + s + 1)ω −1 .
But, from our assumptions, (i, m′ + 1)g −1 ωgω −1 = (i, m′ + 1). Hence
ω : (i, m′ + 1) 7→ (i, m′ + s + 1)
i.e. ω : (i, m) 7→ (i, m + s) for all m > m′ . Running this argument for each
k ∈ ZT n (U) we have for any ρ ∈ G that ρσρ−1 ∈ HT n (U) .
We now describe necessary conditions on the branches of XT n (U) for there to
be a ρ ∈ G that permutes those branches. Let us assume that ρ ∈ G and that
(Rj )ρ is almost equal to Rj ′ , where Rj ⊆ Qk and Rj ′ ⊆ Qk′ . If k = k ′ then for
all g ∈ (U )φ̂U , tj (g) = tj ′ (g); hence all permutations of the branches in Qk may lie
in G. If k 6= k ′ then let g ∈ U be such that tk (g) > 0, tk′ (g) < 0, and ti (g) = 0
for all branches i in Xn \ (Rk ∪ Rk′ ). Such an element exists by Lemma 5.6: there
is a p ∈ N such that Up 6 U . Let h := (g)φ̂. For a ray j ′ in Qk′ ⊆ XT n (U) we
have that tj ′ (ρ−1 hρ) > 0 and so, by (17), if ρ−1 hρ ∈ (U )φ̂U then we must have for
all branches i′ in Qk′ that ti′ (ρ−1 hρ) > 0. From our choice of g, we may conclude
that Qk cannot contain fewer branches than Qk′ . Similarly tj (ρhρ−1 ) < 0 and so
for all rays i in Qk , ti (ρhρ−1 ) < 0 meaning that Qk′ cannot contain fewer branches
than Qk . Hence a necessary condition on j, j ′ ∈ ZT n (U) for there to be a ρ ∈ G
such that (Rj )ρ is almost equal to Rj ′ is that Qk ⊇ Rj and Qk′ ⊇ Rj ′ contain
the same number of branches. This condition is equivalent to the statement that

Tk (U ) = Tk′ (U ).
Remark 5.10. We can more precisely
describe the subgroup R from the previous
Ln
lemma. We have that R = ( i=1 STi (U) ) ⋊ A, where A 6 Sn corresponds to
permuting the factors of the summand that have the same size. More explicitly, if

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

27

σ ∈ Sn and σ = σ1 . . . σd in disjoint cycle notation, then σ ∈ A if and only if, for
every i ∈ Zd and k, k ′ ∈ supp(σi ), Tk (U ) = Tk′ (U ).
We now consider the particular case of Um := hFAlt(Xn ), gim | i ∈ Zn i 6f Hn
(where gi is our standard generator of Hn with t1 (g) = 1 and ti (g) = −1). In this
case the sets Qi , i ∈ Zn , all consist of m rays. Thus Lemma 5.9 states that
NSym(Xmn ) ((Um )φ̂Um ) 6 Hmn ⋊ (Sm ≀ Sn )
Ln
where Sm ≀Sn = ( i=1 Sm )⋊Sn . In fact (18) is an equality. Let ρ ∈ Hmn ⋊(Sm ≀Sn ).
Then conjugation by ρ preserves cycle type. Thus ρ−1 (FAlt(Xmn ))ρ = FAlt(Xmn ).
Given gim ∈ Um , we have that (gim )φ̂Um is a product of m infinite cycles, each
with support equal to two branches of Xmn . Since conjugation by any ω ∈ Hmn
preserves cycle type and sends almost all of each branch of Xmn to itself, we have
that ω −1 ((gim )φ̂Um )ω ∈ (Um )φ̂Um . Elements of the head of Sm ≀ Sn send (gim )φ̂Um
to (gjm gk−m )φ̂Um for some j, k ∈ Zn . We now consider the preimage, under φ̂Um , of
elements of the base of Sm ≀ Sn .
(18)

Notation. Let Yi,0 (U ) := {(i, m) | 1 6 m 6 Ti (U )} and, for any s ∈ N, let
−sT (U)
Yi,s (U ) := {(i, m) | sTi (U ) + 1 6 m 6 (s + 1)Ti (U )} = Yi,0 (U )gi i . Thus
∞
∞
F
F
−sT (U)
Ri =
Yi,s (U ) =
Yi,0 (U )gi i .
s=0

s=0

Definition 5.11. Given any i ∈ Zn and σ ∈ FSym(Xn ) with supp(σ) ⊆ Yi,0 (U )),
let uσ,i be the element of Sym(Xn ) such that supp(uσ,i ) ⊆ Ri and, for every s ∈
−sT (U)
sT (U)
i.e. let uσ,i induce the permutation σ on
N ∪ {0}, uσ,i Yi,s (U ) = gi i σgi i
every set Yi,s (U ).
The preimage of the base of Sm ≀Sn is therefore {uσ,i | i ∈ Zn , σ ∈ FSym(Yi,0 (Um ))}.
Let j ∈ Zn and σ ∈ FSym(Yj,0 (Um )). We have that conjugation by uσ,j sends gim
−1 m
m
to an element of Hn and, in particular, t1 (u−1
σ,j gi uσ,j ) = −ti (uσ,j gi uσ,j ) = m.
m
Now u−1
σ,j gi uσ,j ∈ Um since conjugation by elements of Sym preserves cycle type.
Hence all elements of Hmn ⋊ (Sm ≀ Sn ) normalise (Um )φ̂Um .
Proposition 5.12. Let n ∈ {2, 3, . . .} and U 6f Hn . Then there exists an m ∈ N
such that Um 6 U and NSym(Xn ) (U ) 6 NSym(Xn ) (Um ). Importantly this implies
that Um is characteristic in U .

Proof. Let n ∈ {2, 3, . . .} and U 6f Hn . Lemma 5.6 states that there exists an m ∈
2N such that Um 6f U . Let Gm := NSym(Xmn ) ((Um )φ̂Um ), which, from the above,
equals Hmn ⋊ (Sm ≀ Sn ). We wish to show that NSym(Xn ) (U ) 6 NSym(Xn ) (Um ).
From Lemma 5.9, NSym(XT n (U ) ) ((U )φ̂) 6 HT n (U) ⋊ R where R 6 ST n (U) . It is
−1
therefore sufficient to show that (HT n (U) ⋊ R)φ̂−1
U 6 (Gm )φ̂Um .
Ln
−1
First consider (R)φ̂U . By Remark 5.10, R = ( i=1 STi (U) ) ⋊ A. But (A)φ̂−1
U 6
Sn corresponds to the isometric permutations of the rays of Xn , all of which lie in
Ln
−1
(Gm )φ̂−1
i=1 STi (U) )φ̂U consists of {uσ,i | i ∈ Zn , σ ∈ FSym(Yi,0 (U ))}.
Um . Now (
But since Ti (U ) m for every i ∈ Zn , this is a subset of {uσ,i | i ∈ Zn , σ ∈
FSym(Yi,0 (Um ))} 6 (Gm )φ̂−1
Um .
Finally we consider (HT n (U) )φ̂−1
U . Let gj ∈ HT n (U) . Then t1 (gj ) = 1 and
−1
tj (gj ) = −1 where Rj ⊆ Qk . We first consider the image of gj under φ̂U
. Since

28

CHARLES GARNET COX

−1
(R)φ̂−1
U 6 (Gm )φ̂Um , we may assume that j is the lowest numbered branch in Qk ,
T (U)

T (U)

−1
1
) ⊔ Xk,1 (gj k ). We
meaning that supp((gj )φ̂−1
U ) = (supp(gj ))φU = X1,1 (gj
now consider the image of this element under φ̂Um . For every d ∈ N let id :=
(d − 1) · T1 (U ) + 1, let kd := (d − 1) · Tk (U ) + (k − 1)m + 1 and, for each i ∈ Zn ,
let ci denote the constant such that m = ci Ti (U ). Then
!
c1
c1
G
G
T1 (U)
c1 T1 (U)
(X1,1 (gk
))φUm =
X1,id (gk
) φUm =
Rid
d=1

d=1

and

T (U)
(Xk,1 (gk k ))φUm

=

ck
G

!

c T (U)
X1,kd (gkk k )

d=1

φUm =

ck
G

Rkd

d=1

Fc1
F ck
where c1 T1 (U ) = ck Tk (U ) = m. Thus supp((gj )φ̂−1
U φ̂Um ) = ( d=1 Rid )⊔( d=1 Rkd ).
Consider the element g ∈ Gm that: has one infinite orbit; preserves the colexicographic
Fc1 order (inherited
Fck from this ordering on Xmn = {(i, m) | i ∈ Zmn , m ∈ N})
on d=1
Rid and on d=1
Rkd ; sends (k1 , 1) to (1, 1); and fixes all other points of
Xmn . We note that g and (gj )φ̂−1
U φ̂Um have the same supports, and considering

their actions on Xmn we see that g = (gj )φ̂−1
U φ̂Um .
5.3. Conjugacy for groups commensurable to Hn . In Section 6.2 we show that
there exists an algorithm which, for any n ∈ {2, 3, . . .}, p ∈ N, and Hnp -conjugated
a, b ∈ Hnp ⋊ Snp , decides whether a and b are (Up )φ̂Up -conjugated.
Proposition 5.13. Let n ∈ {2, 3, . . .}, p ∈ 2N and Up 6 Hn . Then TCP(Up ) is
solvable.
Proof. Our aim is to produce an algorithm which, given a, b ∈ Up and φρ ∈ Aut(Up ),
decides whether there exists a u ∈ Up such that (u−1 )φρ au = b i.e. u−1 ρau = ρb.
Let φ̂ := φ̂Up and let us rephrase our question in (Up )φ̂:
u−1 ρau = ρb
⇔ (u−1 ρau)φ̂ = (ρb)φ̂
⇔ (u−1 )φ̂(ρa)φ̂(u)φ̂ = (ρb)φ̂
where (ρa)φ̂, (ρb)φ̂ ∈ Hnp ⋊ Snp and (u)φ̂ ∈ (Up )φ̂ 6 Hnp from Lemma 5.8 and
Lemma 5.9. The algorithm for TCP(Hnp ) in Section 4 may be used to produce a
conjugator x ∈ Hnp if one exists. Given such a x, Proposition 6.8 decides whether
there exists a y ∈ (Up )φ̂ which conjugates (ρa)φ̂ to (ρb)φ̂.

Proposition 5.14. Let n ∈ {2, 3, . . .}, p ∈ 2N, and Up 6 Hn . If E is a finite
extension of Up , then AUp EE is orbit decidable.
Proof. Recall that for AUp EE = {φe | e ∈ E} to be orbit decidable, there must exist
an algorithm which decides, given any a′ , b′ ∈ Up , whether there exists a ψ ∈ AUp EE
such that
(19)

(a′ )ψ = b′ .

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

29

Since Aut(Up ) ∼
= NSym(Xn ) (Up ), we may rewrite (19) as searching for an element
φρ ∈ Aut(Up ) such that
(a′ )φρ = b′ and φρ ∈ AUp EE
i.e. searching for a ρ ∈ Ē, the image of the natural epimorphism from AUp EE , such
that ρ−1 a′ ρ = b′ . Now we rephrase this question using the map φ̂ := φ̂Up :
(ρ−1 )φ̂(a′ )φ̂(ρ)φ̂ = (b′ )φ̂.
Let a := (a′ )φ̂, b := (b′ )φ̂, and y := (ρ)φ̂. Thus a, b ∈ (Up )φ̂ 6 Hnp are known, and y
must be chosen to be any element in (Ē)φ̂ so that y −1 ay = b. We have that (Up )φ̂ 6c
(Ē)φ̂ 6 Hnp ⋊ Snp for some c ∈ N. Thus there exist coset representatives e2 , . . . , ec
and (Ē)φ̂ = h(g2p )φ̂, . . . , (gnp )φ̂, FAlt(Xmn ), e2 , . . . , ec i. Now, deciding whether a, b
are (Ē)φ̂-conjugated is equivalent to deciding whether any pair in {(a, ei be−1
i )|2 6
i 6 c} is (Up )φ̂-conjugated, by noting that every element in (Ē)φ̂ decomposes as uei
for some u ∈ (Up )φ̂ and 2 6 i 6 c and that u−1 au = ei be−1
⇔ (uei )−1 a(uei ) = b.
i
Deciding if any pair is (Up )φ̂-conjugated is possible by first deciding whether any
pair is Hmn -conjugated and then, for each such pair, applying Proposition 6.8. 
Proposition 5.15. Let n ∈ {2, 3, . . .}, p ∈ 2N, and Up Ef G. Then CP(G) is
solvable.
Proof. We again use [BMV10, Thm. 3.1]. G is a finite extension of Up by F , some
finite group. TCP(Up ) is solvable by Proposition 5.13. AUp EG is orbit decidable by
Proposition 5.14. Hence CP(G) is solvable.

Recall that A and B are commensurable if and only if there exist NA ∼
= NB with
NA finite index and normal in A and NB finite index and normal in B. Our aim is
to prove Theorem 2, that, for any n ∈ {2, 3, . . .} and any group G commensurable
to Hn , CP(G) is solvable.
Proof of Theorem 2. Fix an n ∈ {2, 3, . . .} and let G and Hn be commensurable.
Then there is a U Ef G, Hn . By Proposition 5.12, there exists an m ∈ 2N such
that Um is finite index and characteristic in U . It is a well know result that if A is
characteristic in B and B is normal in C, then A is normal in C. Hence Um E G
and we may apply Proposition 5.15 to obtain that CP(G) is solvable.

6. Further computational results
6.1. Computational results regarding centralisers in Hn .
Proposition 6.1. There is an algorithm that, given any n ∈ {2, 3, . . .} and any
g ∈ Hn ⋊ Sn , outputs a finite generating set for t(CHn (g)) 6 Zn .
In order to prove Proposition 6.1 we need some notation.
Notation. Given a subset A ⊆ Zn and g ∈ Hn ⋊ Sn , let tA (g) = (x1 , . . . , xn ) ∈ Zn
be given by xi = ti (g) if i ∈ A and xi = 0 otherwise.
Note that tA is not a homomorphism: consider h, an isometric permutation
of the 1st and 2nd branches of Xn , and g2 , a standard generator of Hn . Then
t1 (h−1 g2 h) = t1 (g2−1 ) = −1 but t1 (h−1 ) + t1 (g2 ) + t1 (h) = 0 + 1 + 0. It is a
homomorphism from Hn however. Also, given any g ∈ Hn ⋊ Sn and A ⊆ Zn , the
vector tA (g) is computable by Lemma 4.4.

30

CHARLES GARNET COX

Lemma 6.2. Given n ∈ {2, 3, . . .} and g ∈ Hn ⋊ Sn ,
t(CHn (g)) = tI c (g) (CHn (g)) ⊕ tI(g) (CHn (g)).
Proof. Let h ∈ CHn (g) and i ∈ I(g). From Lemma 4.22, h[i] ∈ CHn (g) and
−1
tj (hh−1
[i] ) = 0 if j ∈ Cg ([i]) and tj (hh[i] ) = tj (h) otherwise. Thus, repeating the
argument for all classes of I(g), we construct h′ ∈ CHn (g) with t(h′ ) = tI c (g) (h), and
thus t(h(h′ )−1 ) = tI(g) (h). It follows that t(h) ∈ htI c (g) (CHn (g)), tI(g) (CHn (g))i.
Clearly tI c (g) (CHn (g)) ∩ tI(g) (CHn (g)) is the trivial element of Zn and hence they
generate a direct sum.

P
Lemma 6.3. Let n ∈ {2, 3, . . .}, g ∈ Hn ⋊ Sn , and r ∈ N. Then i∈I c (g) ti (h) = 0
r
for all h ∈ CHn (g).
1
u
Proof. By Lemma
all j ∈ [i]g . If
Pjur , . . . jr are representatives
P 3.9, tj (h) = ti (h)Pfor
u
c
of Ir (g), then
s=1 tjrs (id) = 0 by Lemma
i∈Irc (g) ti (h) = r
s=1 tjrs (h) = r
4.26.


Definition 6.4. Given g ∈ Hn ⋊Sn , let Θ(g) be the set of all cjrd ,jrd′ of the statement
of Lemma 4.25 where r ∈ N, jr1 , . . . , jru are distinct representatives of Irc (g), and
d, d′ ∈ Zu are distinct. Note that since I c (g) is finite, Θ(g) is finite.
Lemma 6.5. Given n ∈ {2, 3, . . .} and g ∈ Hn ⋊ Sn , tI c (g) (CHn (g)) is generated
by the image of Θ(g) under t.
Proof. By Lemma
P 3.9 and Lemma 6.3, for any h ∈ CHn (g) and for every r ∈ N
we have that i∈Irc (g) ti (h) = 0 and ti (h) = tk (h) if [k] = [i]. Thus tI c (g) (CHn (g))
must be contained in
X
xi = 0 for all r ∈ N, xj = xk if [j] = [k]}.
A := {(x1 , . . . , xn ) ∈ Zn | xi = 0 if i ∈ I(g),
i∈Irc (g)

Note that it follows from the definition of Θ(g) that t(c) ∈ tI c (g) (CHn (g)) for all
c ∈ Θ(g). Thus ht(Θ(g))i ⊆ tI c (g) (CHn (g)) ⊆ A. We claim that ht(Θ(g))i = A.
Clearly, the lemma follows now from the claim. To see that t(Θ(g)) generates
PA, we
argue by induction on the L1 -norm of (x1 , . . . , xn ) ∈ A (i.e. ||(x1 , ..., xn )|| = |xi |).
Let y ∈ A. If ||y|| = 0, then y ∈ ht(Θ(g))i. Suppose that y = (x1 , ..., xn ). If
||y|| > 0, since xi = 0 for all i ∈ I(g), there must be j ∈ I c with xj 6= 0. Assume
xj < 0. Let r ∈ N such that j ∈ Irc (g). Then, by Lemma 6.3, there must be
k ∈ Irc (g), [k] 6= [j] with xk > 0. Observe that tl (cj,k ) is equal to 1 for l ∈ [j], is
equal to −1 for l ∈ [k], and zero otherwise. Hence ||yt(ck,j )|| = ||y|| − 2r, and we
conclude by induction that yt(ck,j ) ∈ ht(Θ(g))i and hence y ∈ ht(Θ(g))i.

We now have to find a generating set for tI(g) (CHn (g)).
Lemma 6.6. Let n ∈ {2, 3, . . .} and g ∈ Hn ⋊ Sn . Then for each i ∈ I(g),
tCg ([i]) (CHn (g)) 6 Zn is infinite cyclic and
M
tI(g) (CHn (g)) =
tCg ([i]) (CHn (g)),
i∈R

where R is a set of different representatives of I(g)/ ∼g .

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

31

Proof. Let i ∈ I(g). Write g = ωg σg . Note that g |σg | ∈ CHn (g) and that t((g |σg | )[i] )
is non-zero and lies in tCg ([i]) (CHn (g)). Thus tCg ([i]) (CHn (g)) is non-trivial.
Let h ∈ CHn (g), such that ti (h) is positive and minimum. Take c ∈ CHn (g). We
will show that tCg ([i]) (c) ∈ htCg ([i]) (h)i.
If ti (c) = 0 then, by Lemma 4.20, tCg ([i]) (c) has all its coordinates equal to zero
and hence lies in htCg ([i]) (h)i.
Assume that ti (c) > 0, the other is analogous. By the Euclidean algorithm,
ti (c) = dti (h) + r with 0 6 r < ti (h). Note that r = ti (ch−d ) and ch−d ∈ CHn (g)
and thus r = 0 by the minimality of h. Therefore ti (ch−d ) = 0, and, by Lemma 4.20,
tCg ([i]) (ch−d ) has all its coordinates equal to zero, and hence tCg ([i]) (c) = tCg ([i]) (hd ).
By Lemma 4.21 and Lemma 4.22, if h ∈ CHn (g), then h[i] ∈ CHn (g) and
tCg ([i]) (h) =
P tCg ([i]) (h[i] ) = t(h[i] ). Thus tCg ([i]) (CHn (g)) 6 tI(g) (CHn (g)). Since
tI(g) (h) = j∈R t(h[j] ), we get that tI(g) (CHn (g)) is generated by {tCg ([j]) (CHn (g)) |
j ∈ R} and clearly if [j] 6∼g [k] the cyclic subgroups tCg ([j]) (CHn (g)) and tCg ([k]) (CHn (g))
intersect trivially. Now the direct sum follows.

Lemma 6.7. There is an algorithm that given any n ∈ {2, 3, . . .}, g ∈ Hn ⋊Sn , and
i ∈ Zn , decides if i ∈ I(g) and moreover, if i ∈ I(g), it outputs some h ∈ CHn (g)
such that t(h) generates tCg ([i]) (CHn (g))
Proof. Deciding if i ∈ I(g) follows from Lemma 4.4.
So suppose that i ∈ I(g). By Lemma 6.6, tCg ([i]) (CHn (g)) is infinite cyclic, so
there must be h ∈ CHn (g) such that tCg ([i]) (h) generates tCg ([i]) (CHn (g)).
From Lemma 4.22 if h ∈ CHn (g) then h[i] ∈ CHn (g) and tCg ([i]) (h) = t(h[i] ).
Thus we can assume that h ∈ CHn (g) has only infinite orbits, its support has finite
intersection with the rays Rj , j 6∈ Cg ([i]), and t(h) generates tCg ([i]) (CHn (g)).
Write g = ωg σg . Note that g |σg | ∈ CHn (g) and that t((g |σg | )[i] ) is non-zero
and lies in tCg ([i]) (CHn (g)) = ht(h)i. Let g ∗ denote (g |σg | )[i] and observe that
h ∈ CHn (g) ⇒ h ∈ CHn (g ∗ ). Thus |tj (h)| 6 |tj (g ∗ )| for j ∈ [i], and tj (g ∗ ) is
computable from g by Lemma 4.4.
We will find computable bounds for zk (h), k ∈ Zn . If k ∈ I c (g), then Lemma
4.21 states that supp(h) = supp(g ∗ ) and so zk (h) 6 zk (g ∗ ) for all k ∈ I c (g). Now
consider if k ∈ I(g). We will show that zk (h) 6 zk (g ∗ ) + |tk (g ∗ )|. Assume, for
a contradiction, that zk (h) is minimal and that zk (h) > zk (g ∗ ) + |tk (g ∗ )|. Since
h ∈ CHn (g ∗ ), we have
(i, m)g ∗ h = (i, m)hg ∗ for all (i, m) ∈ Xn .

(20)

We may assume that tk (g ∗ ) < 0, since replacing g ∗ with (g ∗ )−1 yields a proof for
when tk (g ∗ ) > 0. Let m > zk (g ∗ ) + |tk (h)|. Note that
(k, m)g ∗ h = (k, m + tk (g ∗ ))h
and also that
(k, m)g ∗ h = (k, m)hg ∗ = (k, m + tk (h))g ∗ = (k, m + tk (g ∗ ) + tk (h)).
Thus (k, m + tk (g ∗ ))h = (k, m + tk (g ∗ ) + tk (h)), which, since tk (g ∗ ) < 0, contradicts
the minimality of zk (h).
Let S = {s ∈ Hn : zk (s) 6 zk (g) + |tk (g ∗ )|, |tk (s)| 6 |tk (g ∗ )|, k ∈ Zn }. Note
that S must contain h ∈ CHn (g). Note also that S is finite, and with the given
restrictions, one can enumerate all elements of S. For each s ∈ S, using the word
problem for Hn ⋊ Sn we can decide if s ∈ CHn (g), and using that the functions tA

32

CHARLES GARNET COX

are computable, we can decide if t(s) is non-zero and equal to tCg ([i]) (s). Let S ′ be
the subset of S of the elements satisfying the two conditions above. Finally, since
S ′ is finite, we can find c ∈ S ′ such that tCg ([i]) (s) ∈ ht(c)i for all s ∈ S ′ . Note that
since h ∈ S ′ such an c must exist.

Proof of Proposition 6.1. From Lemma 4.4 there is an algorithm that computes
I(g), I c (g), and Cg ([i]) for each i ∈ I(g). From Lemma 6.2 t(CHn (g)) = tI c (g) (CHn (g))⊕
tI(g) (CHn (g)), and we only need algorithms that gives generating sets for each of
the direct summands. By Lemma 6.5, there is an algorithm that outputs a generating set for tI c (g) (CHn (g)). By Lemma 6.7, there is an algorithm that computes
a generator of tCg ([i]) (CHn (g)) for each i ∈ I(g) and by Lemma 6.6, those elements

generate tI(g) (CHn (g)).
6.2. Deciding conjugacy in (Up )φ̂Up . Recall Up := hg2p , . . . , gnp , FAlt(Xn )i 6 Hn .
From Section, 5.2 (Up )φ̂Up 6 Hnp and


n−1

X 
t((Up )φ̂Up ) = (a1 . . . a1 a2 . . . a2 . . . an . . . an )T a1 , . . . , an−1 ∈ Z, an = −
ai .
| {z }
 | {z } | {z }

p

p

p

i=1

When p is even, FSym(Xnp ) ∩ (Up )φ̂Up = FAlt(Xnp ). In this section we prove the
following (which has been used in Section 5.3 above).

Proposition 6.8. There is an algorithm which, given any n ∈ {2, 3, . . .}, p ∈ 2N,
a, b ∈ Hnp ⋊ Snp and an x ∈ Hnp which conjugates a to b, decides whether a and b
are (Up )φ̂Up -conjugated.
Lemma 4.7 stated that if x ∈ G conjugates a to b then y ∈ G also conjugates a
to b if and only if there exists a c ∈ CG (a) such that cx = y.
Lemma 6.9. Let a, b ∈ Hnp ⋊ Snp be conjugate by x ∈ Hnp . Then a and b are
(Up )φ̂Up -conjugated if and only if there is a c ∈ CHnp (a) such that cx ∈ (Up )φ̂Up .
Proof. We apply Lemma 4.7. If there is a c ∈ CHnp (a) such that cx ∈ (Up )φ̂Up
then a and b are conjugate by cx ∈ (Up )φ̂Up . If there exists y ∈ (Up )φ̂Up such that

y −1 ay = b, let c := yx−1 . Then c ∈ CHnp (a) and cx = y ∈ (Up )φ̂Up .
Lemma 6.10. Let a, b ∈ Hnp ⋊ Snp and let x ∈ Hnp conjugate a to b. Then there
is an algorithm that decides whether there exists c ∈ CHnp (a) such that t(cx) ∈
t((Up )φ̂Up ), and outputs such an element if one exists.
Proof. Let {δ1 , . . . , δ e } denote a finite generating set of t(CHnp (a)), which is computable by Proposition 6.1. Deciding whether there is a c ∈ CHnp (a) such that
t(cx) ∈ t((Up )φ̂Up ) is equivalent to finding powers αi of the generators δ i ∈ Zn such
that
e
X
αi δ i ∈ t((Up )φ̂Up ).
t(x) +
i=1

Hence we must decide whether there are constants {a1 , . . . , an−1 } and {α1 , . . . , αe }
such that
e
n−1
X
X
αi δ i = (a1 . . . a1 a2 . . . a2 . . . . . . an . . . an )T , where an := −
(21) t(x) +
ai .
i=1

i=1

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

33

Viewing this as np linear equations, this system of equations has a solution if and
only if there is an element c ∈ CHnp (a) such that t(cx) ∈ t((Up )φ̂Up ). By writing
these equations as a matrix equation we may compute the Smith normal form to
decide if the equations have an integer solution (see, for example, [Laz96]) and
compute one should one exist (either from the reference or by enumerating all
possible inputs). Definition 6.4 and Lemma 6.7 then provide suitable preimages for

the elements {δ 1 , . . . , δ e } in order to output a viable c.
Lemma 6.11. Let n ∈ {2, 3, . . .} and g ∈ Hn ⋊ Sn . Then it is algorithmically
decidable whether CHn (g)∩(FSym(Xn )\FAlt(Xn )) is empty. A necessary condition
for it to be empty is that I c (g) = ∅.
Proof. We use Lemma 4.4 to compute I c (g). If there exists j ∈ I c (g), either |[j]g | is
odd or even. If |[j]g | is even, then we have that the first |[j]g |-cycle on this branch
is a finite order element of the centraliser that lies in FSym(Xn ) \ FAlt(Xn ). If
|[j]g | is odd, then the element that permutes only the first two |[j]g |-cycles of the
branches [j]g provides an element of the centraliser in FSym(Xn )\FAlt(Xn ). Hence
CHn (g)∩ FSym(Xn )\FAlt(Xn ) is non-empty whenever g has an even length orbit
or g has two or more orbits of length m for some odd number m. Since one of these
is satisfied if I c (g) is non-empty, assume that I(g) = Zn . From Section 3.1, this
implies that all of the finite orbits of g lie inside a finite subset of Xn , which is
computable by Lemma 4.4. Searching for orbits of g of the appropriate length is
therefore also possible in this case.

Definition 6.12. Let sgnX : FSym(X) → {1, −1} be the sign function for FSym(X),
Q
t (g)
so that the preimage of 1 is FAlt(X). For any g ∈ Hn , let fg := g( ni=2 gi i ). Note
that t(fg ) = 0 and so fg ∈ FSym(Xn ). Thus let ξn : Hn → {1, −1}, h 7→ sgnXn (fh ).
Note that for any g ∈ Hn , ξn (g) = ξn (fg ).

Lemma 6.13. There exists an algorithm which, given g ∈ Hn , computes ξn (g).
Q
t (g)
Proof. Since g( ni=2 gi i ) lies in FSym(Xn ), we may apply Lemma 4.4 to determine its cycle type, which is sufficient to compute ξn (g).

The previous definition exactly captures the form of the elements in (Up )φ̂Up .
Lemma 6.14. Let n ∈ {2, 3, . . .}, p ∈ 2N, g ∈ Hnp , and t(g) ∈ t((Up )φ̂Up ). Then
g ∈ (Up )φ̂Up if and only if ξnp (g) = 1.
Proof. Let h := (g)φ̂−1
Up . Using that t(g) ∈ t((Up )φ̂Up ) and that p ti (h) for every
i ∈ Zn : h ∈ Up ⇔ fh ∈ Up ⇔ fh ∈ FAlt(Xn ) ⇔ fg ∈ FAlt(Xnp ) ⇔ ξnp (g) = 1.

Lemma 6.15. Let n ∈ {2, 3, . . .}. Then ξn is a homomorphism.
Proof. Clearly the function sgnX is a homomorphism. Let g, h ∈ Hn . Then
n
n
n
Y
Y
Y
−(t (g)+ti (h))
−t (h)
−t (g)
)
gh = fg ( gi i )fh ( gi i ) = fg fh′ ( gi i
i=2

i=2

i=2

Q
Q
t (g)
−t (g)
where
= ( ni=2 gi i )fh ( ni=2 gi i ) has the same cycle type as fh . Thus
′
fgh = fg fh and ξn (gh) = ξn (fgh ) = ξn (fg fh′ ) = ξn (fg )ξn (fh′ ) = ξn (fg )ξn (fh ) =
ξn (g)ξn (h).

fh′

34

CHARLES GARNET COX

Proof of Proposition 6.8. By Lemma 6.9, a and b are (Up )φ̂Up -conjugated if and
only if there exists a c ∈ CHnp (a) such that cx ∈ (Up )φ̂Up . A necessary condition for
cx ∈ (Up )φ̂Up is that t(cx) ∈ (Up )φ̂Up . Lemma 6.10 decides whether this condition
can be satisfied. If not, then CHnp (a)x ∩ (Up )φ̂Up is empty and a and b are not
(Up )φ̂Up -conjugated. We can therefore assume that this condition is satisfied.
Let c ∈ CHnp (a) be the element outputted by the algorithm of Lemma 6.10 so
that t(cx) ∈ (Up )φ̂Up . By Lemma 6.14, cx ∈ (Up )φ̂Up if and only if ξnp (cx) = 1.
By Lemma 6.13, ξnp (cx) is computable. If ξnp (cx) = 1 we are done and so let us
assume that ξnp (cx) = −1. If there exists c′ ∈ CHnp (a) ∩ (FSym(Xnp ) \ FAlt(Xnp ))
then c′ c ∈ CHnp (a), t(c′ cx) = t(c′ ) + t(cx) = t(cx) ∈ t((Up )φ̂Up ), and ξnp (c′ cx) =
ξnp (c′ )ξnp (cx) = 1 since ξnp is a homomorphism by Lemma 6.15. Hence c′ cx
conjugates a to b and c′ cx ∈ (Up )φ̂Up . Lemma 6.11 decides whether such a c′
exists. If no such c′ exists, Lemma 6.11 states that I c = ∅. Thus the generating
set {δ 1 , . . . , δ e } for t(CHnp (a)) from Proposition 6.1 consists only of those elements
from Lemma 6.7. Lemma 6.7 computes δ̂ 1 , . . . , δ̂e ∈ CHnp (a) such that t(δ̂ j ) = δ j
for each j ∈ Ze . We then take the equations
t(x) +

e
X

αi δ i = (a1 . . . a1 a2 . . . a2 . . . . . . an . . . an )T , where an := −

n−1
X

ai .

i=1

i=1

labelled (21) above (where a1 , . . . , an−1 and α1 , . . . , ae are to be found) and add
the equation


e
Y

ξ(δ̂ j )αj  ξ(x) = 1
j=1

which ensures that the chosen c ∈ CHnp (a) satisfies ξ(cx) = 1 (from Lemma 6.15).
From our assumptions, the choice of generating set and preimage are arbitrary: if
h, h′ ∈ CHnp (a) satisfy t(h) = t(h′ ), then we musthave that h−1 h′ ∈ FAlt(Xnp ),
since otherwise CHnp (a) ∩ FSym(Xnp ) \ FAlt(Xnp ) would be non-empty. We may
then write these equations as a matrix equation and compute the Smith normal
form to decide whether or not the equations have an integer solution.


6.3. Proving Theorem 3. The structure of centralisers for elements in Hn was
studied in [JG15]. In this section we show, for any g ∈ Hn ⋊ Sn , when CHn (g)
is finitely generated and when it is, that a finite generating set is algorithmically
computable. From Section 6.1, a finite set {δ 1 , . . . , δ e } is computable, from only
hδ 1 , . . . , δ e i. Hence, given
n ∈ {2, 3, . . .} and a ∈ Hn ⋊ Sn , such that t(CHn (a)) =P
e
c ∈ CHn (a), there exist α1 , . . . , αe ∈ Z such that t(c) = i=1 αi δ i .
Notation. Let {δ 1 , . . . , δ e′ } be the image of Θ(a) under t (where the set Θ(a) was
introduced in Definition 6.4) and let {δe′ +1 , . . . , δ e } be the image under t of the
elements outputted by the algorithm of Lemma 6.7.

We will begin to describe a finite generating set for CHn (a) (should one exist)
by choosing certain preimages (under t) of {δ1 , . . . , δ e }. Lemma 4.25 states that
Θ(a) ⊆ CHn (a), and so our preimages of {δ 1 , . . . , δ e′ } will be the elements of Θ(a).
The following lemma shows that, by imposing the condition that the preimage may
only have infinite orbits, there is a unique preimage for the elements {δe′ +1 , . . . , δ e }.

TWISTED CONJUGACY IN HOUGHTON’S GROUPS

35

Lemma 6.16. Let n ∈ {2, 3, . . .}, a ∈ Hn ⋊ Sn , i ∈ I, and g ∈ CHn (a) such
that ht(g)i = tCa ([i]) (CHn (a)). If h ∈ CHn (a) and t(h) = t(g), then g[i] = h[i] . In
addition, for each s ∈ {e′ + 1, . . . , e} there is a unique preimage δs of δ s having only
infinite orbits.
Proof. Lemma 4.21 states that supp(g[i] ) = supp((a|σa | )[i] ) = supp(h[i] ) and so
|σa |
supp(g[i] h−1
)[i] ). Now, g[i] h−1
[i] ) ⊆ supp((a
[i] ∈ FSym(Xn ) must be trivial by the
first part of the statement of Lemma 4.21: elements of CHn (a) cannot have finite
orbits intersecting supp((a|σa | )[i] ).

The previous lemma therefore provides a unique preimage for each of the elements {δ e′ +1 , . . . , δ e }. We now describe the structure of CFSym(Xn ) (a) in order to
determine when CHn (a) is not finitely generated, and to describe a finite generating
set when one exists.
(0)

Notation. Let g ∈ Sym(X) for some non-empty set X. Then Yg
(1)
Yg

:= X \ supp(g), and, for each r ∈ N,
(r)

(r)
Yg

:= supp(g

:= supp(g r ). Thus:

(1)
Yg

∞

),

denotes

the fixed points of g; Yg , where r ∈ {2, 3, . . .}, is the union of the orbits of g of
(0)
size r; and Yg is the union of the infinite orbits of g.
Lemma 6.17. Let g ∈ Sym(X) and G 6 Sym(X) for some non-empty set X. If
Q∞
(r)
c ∈ CG (g), then c = r=0 αr where, for every r ∈ {0, 1, 2, . . .}, supp(αr ) ⊆ Yg .

Proof. We show that c must restrict to a bijection, for each r ∈ {0, 1, 2, . . .}, on
(r)
the set Yg . Consider if c sent an r-cycle of g to an s-cycle of g where r 6= s. By
possibly replacing c with c−1 , we may assume that r < s (where s may be finite
or infinite). Let y be in this orbit of size r. Then (y)g r = y. Since c ∈ CG (g),
(y)c−1 g r c = y. But then c sends both (y)c−1 and (y)c−1 g r to y, a contradiction. 
Lemma 6.18. Let g ∈ Sym(X) for some non-empty set X. Then
∞
M
CFSym(Y (r) ) (g)
CFSym(X) (g) ∼
=
g

r=0

Q∞
Proof. Given c ∈ CFSym(X) (g), the previous lemma states that c = r=0 αr where,
(r)
for every r ∈ {0, 1, 2, . . .}, supp(αr ) ⊆ Yg . Now c ∈ FSym ⇒ | supp(c)| < ∞,
(r)
and so, for every r, | supp(αr )| < ∞ ⇒ αr ∈ FSym(Yg ). Clearly, if r 6= s, then
(r)
(s)
FSym(Yg ) ∩ FSym(Yg ) is trivial.

Lemma 6.19. Let g ∈ Sym(X), where X is a non-empty set, and let y, z ∈ X. If
c ∈ CSym(X) (g) and c : y 7→ z, then c : yg d 7→ zg d for all d ∈ Z.
Proof. For all d ∈ Z,
(z)c−1 g d c = yg d c and (z)c−1 g d c = (z)g d .
Thus c : yg d 7→ zg d for all d ∈ Z.



Lemma 6.20. Let r ∈ N and g ∈ Sym(X) where X is a non-empty set. Then
  (r) 
CFSym(Y (r) ) (g) ∼
Cr ≀ FSym g Yg
=
g
 (r)
(r)
where g Yg is the set obtained from Yg by the equivalence relation x ∼ y ⇔
(r)
xg d = y for some d ∈ Z. Moreover, as a subgroup of FSym(Yg ), the base of

36

CHARLES GARNET COX

this wreath product consists of all of the r-cycles of g, and the head consists of all
finitary permutations of the orbits of g of size r.
Proof. Let c ∈ CFSym(Y (r) ) (g). From Lemma 6.18 and Lemma 6.19, c restricts to a
g
bijection of the r-cycles of g. We will impose the following condition on c: whenever
c sends an r-cycle σ of g to an r-cycle ω of g, it sends the smallest point of supp(σ)
(under some total ordering on X) to the smallest point of supp(ω). We may do
this by replacing c with hc where h is a product of r-cycles of g, since each r-cycle
of g clearly lies in CFSym(Y (r) ) (g). Then c is determined by its action on the points
g
 (r)
Y
in g g , where the representatives can be chosen to be the smallest point in each
g-orbit of size r. Thus every element of CFSym(Y (r) ) (g) is a product of r-cycles of
g
g together with a permutation of the r-cycles of g i.e. CFSym(Y (r) ) (g) is the above
g
wreath product.

We now work through the cases |Irc (a)| = 0, |Irc (a)| = r, and |Irc (a)| > 2r.
(r)

Definition 6.21. Let n ∈ {2, 3, . . .} and g ∈ Hn ⋊ Sn . For each r ∈ N where Yg
is finite, let Ωr (g) consist of the elements of CFSym(Y (r) ) (g). This set is enumerable
g
since, from our description of orbits in Section 3.1, all such r-cycles of g lie in Z(g)
which is finite and computable from only the element g.
Notation. Given n ∈ N and Y ⊆ Xn , let Hn (Y ) := {h ∈ Hn | supp(h) ⊆ Y }.
Lemma 6.22. Let r ∈ N and |Irc (g)| = r. Then CHn (g) is not finitely generated.
Proof. By Lemma 6.5, if c ∈ CHn (g) then tj (c) = 0 for all j ∈ Irc (g). By Lemma
(r)
(r)
6.17, if c ∈ CHn (g) then c = f c′ where supp(f ) ⊆ Yg and supp(c′ ) ⊆ Xn \ Yg .
Thus
CHn (g) = CFSym(Y (r) ) (g) ⊕ CHn (Xn \Y (r) ) (g).
g

g

Lemma 6.20 states that

  (r) 
.
CFSym(Y (r) ) (g) ∼
Cr ≀ FSym g Yg
=
g

(22)

If (22) were finitely generated then FSym would also be finitely generated. Hence
CHn (g) is not finitely generated since it has a non-finitely generated quotient. 
Lemma 6.23. Fix an r ∈ N such that |Irc (g)| = 2r and fix a j ∈ Irc (g). Then
CFSym(Y (r) ) (g) is a subgroup of the group generated by:
g

i) an element h ∈ Θ(g) with tj (h) 6= 0;
ii) an r-cycle
(g)) (j, zj (g))g . . . (j, zj (g))g r−1 ); and
Qr λr := ((j, zjs−1
(j, zj (g))g s−1 ).
iii) µr := s=1 ((j, zj (g))g

  (r) 
lie in
Proof. We show that the elements of CFSym(Y (r) ) (g) ∼
Cr ≀ FSym g Yg
=
g
(r)

hh, λr , µr i. Note that, by construction, supp(h) = Yg . Thus, given any r-cycle
σ of g, there exists d ∈ Z such that h−d λr dd = σ and so the base of our wreath
 (r)
product lies in hh, λr , µr i. In the space g Yg , h consists of a single infinite orbit
 (r)
and µr a single
It follows that hh, µr i ∼
= H2 , and so, in g Yg , we have

  2-cycle.
(r)
6 hh, µr i. Thus all finitary permutations of the orbits of g of
that FSym g Yg

size r lie in hh, µr i, and so CFSym(Y (r) ) (g) 6 hh, λr , µr i.
g



TWISTED CONJUGACY IN HOUGHTON’S GROUPS

37

Lemma 6.24. Fix an r ∈ N such that |Irc (g)| = sr where s > 3. Fix representatives
jr1 , . . . , jrs of Irc (g). Then CFSym(Y (r) ) (g) is a subgroup of the group generated by:
g

i) elements h2 , . . . , hs ∈ Θ(g) with tjr1 (hi ) = 1 for all 2 6 i 6 s and tjrk (hk ) = −1
for each 2 6 k 6 s; and
ii) an r-cycle λr := ((jr1 , zjr1 (g)) (jr1 , zjr1 (g))g . . . (jr1 , zjr1 (g))g r−1 ).
  (r) 
Proof. We again show that the elements of CFSym(Y (r) ) (g) ∼
Cr ≀ FSym g Yg
=
g
lie in hh2 , . . . , hs , λr i. Note that
s
s
\
[
supp(hi ) ⊇ {(j, m) | j ∈ [jr1 ], m > zj (g)}.
supp(hi ) = Yg(r) and that
i=2

i=2

Thus, given any r-cycle σ of g, there is an i ∈ {2, . . . , s} and d ∈ Z such that
d
h−d
i λr hi = σ, and so the base of our wreath product lies in hh2 , . . . , hs , λr i. Now, in
 (r)
the space g Yg , each hi consists of a single infinite orbit and there is a natural map
hh2 , . . . hs i ։ Hs , hi 7→ gi where {gi | i = 2, . . . , s} denotes our standard generating
set of Hs . To be more specific, this epimorphism is induced by the surjection of sets
Xn → Xs , where: for each d ∈ {2, . . . , s} and each e ∈ N, {(k, zk (g) + e − 1) | k ∈
[jrd ]} 7→ (d, e); for each 1 6 l 6 f , supp(σl ) 7→ (1, l) where σ1 , . . . , σf are the ordered
r-cycles within Z(g); and, for each e ∈ N, {(k, zk
(g) + e − 1) | k ∈ [jr1 ]} 7→ (1, f + e).
 (r)
 (r)
6 hh2 , . . . , hs i and so all finitary
Thus, in g Yg , we have that FSym g Yg
permutations of the orbits of g of size r lie in hh2 , . . . , hs i.



Note that the elements appearing in Lemma 6.23 and Lemma 6.24 lie in CHn (g).
This is because the element λr , of type (ii), is an orbit of g of size r, and the
(r)
elements of type (i) and (iii) have support within Yg and induce a permutation
of the orbits of g of size r.
Definition 6.25. Let Fa consist of:
i) the preimages of the elements {δ 1 , . . . , δ e } defined above;
ii) the set Ωr (a) (of Definition 6.21) for those r ∈ N such that |Irc (a)| = 0;
iii) the elements λr and µr of Lemma 6.23 for those r ∈ N such that |Irc (a)| = 2r;
iv) the element λr of Lemma 6.24 for those r ∈ N such that |Irc (a)| > 3r.
Proof of Theorem 3. By Lemma 4.4 we may compute the set {gr 6= id | r ∈ N} and,
for each r ∈ N, the sets Irc (a). If |Irc (a)| = r for any r ∈ N, then our algorithm may
conclude, by Lemma 6.22, that CHn (a) is not finitely generated. We now show that
if this is not the case, then the set Fa defined above is sufficient to generate CHn (a).
Note that Fa is finite since {gr 6= id | r ∈ N} is finite. Also Fa is computable.
P
Let c ∈ CHn (a). There exist numbers α1 , . . . , αe ∈ Z such that t(c) = ei=1 αi δ i .
Thus, by using the preimages of the elements {δ1 , . . . , δ e } in Fa , we can reduce to
the case where c ∈ CFSym(Xn ) (a). By Lemma 6.18 it is sufficient to show, for each
r ∈ N, that CFSym(Y (r) ) (a) 6 hFa i. For each r ∈ N, one of the following three cases
a
occurs: |Irc (a)| = 0; |Irc (a)| = 2r; or |Irc (a)| > 3r. In the first case, the elements of
Ωr (a) are sufficient to generate CFSym(Y (r) ) (a). The second and third cases were
a
dealt with by Lemma 6.23 and Lemma 6.24 respectively, since Fa contains the finite
generating sets described in each.


38

CHARLES GARNET COX

References
[ABM15]

Y. Antolı́n, J. Burillo, and A. Martino, Conjugacy in Houghton’s groups, Publ. Mat.
59 (2015), no. 1, 3–16. MR 3302573
[BCMR14] J. Burillo, S. Cleary, A. Martino, and C. E. Röver, Commensurations and Metric
Properties of Houghton’s Groups, Pacific Journal of Mathematics, 285(2) (2016), 289–
301 (doi:10.2140/pjm.2016.285.289)
[BMV10] O. Bogopolski, A. Martino, and E. Ventura, Orbit decidability and the conjugacy
problem for some extensions of groups, Trans. Amer. Math. Soc. 362 (2010), no. 4,
2003–2036. MR 2574885 (2011e:20045)
[Boo59]
W.W. Boone, The word problem, Annals of mathematics 70(2) (1959), 207–265.
[Bro87]
K. S. Brown, Finiteness properties of groups, Proceedings of the Northwestern conference on cohomology of groups (Evanston, Ill., 1985), vol. 44, 1987, pp. 45–75.
MR 885095 (88m:20110)
[CM77]
D. J. Collins and C. F. Miller, III, The conjugacy problem and subgroups of finite
index, Proc. London Math. Soc. (3) 34 (1977), no. 3, 535–556. MR 0435227 (55
#8187)
[Cox16]
C. Cox, A note on the R∞ property for groups FAlt(X) 6 G 6 Sym(X),
arXiv:1602.02688 (2016)
[DM96]
J. D. Dixon and B. Mortimer, Permutation groups, Graduate Texts in Mathematics,
vol. 163, Springer-Verlag, New York, 1996. MR 1409812 (98m:20003)
[GS14]
D. Gonçalves and S. Parameswaran, Sigma theory and twisted conjugacy-II: Houghton
groups and pure symmetric automorphism groups, Pacific Journal of Mathematics,
280(2) (2016), 349–369 (doi: 10.2140/pjm.2016.280.349)
[GK75]
A. V. Gorjaga and A. S. Kirkinskiı̆, The decidability of the conjugacy problem cannot
be transferred to finite extensions of groups, Algebra i Logika 14 (1975), no. 4, 393–
406. MR 0414718 (54 #2813)
[Hou78]
C. H. Houghton, The first cohomology of a group with permutation module coefficients,
Archiv der Mathematik 31 (1978), 254–258.
[Joh99]
D. L. Johnson, Embedding some recursively presented groups, Groups St. Andrews
1997 in Bath, II, London Math. Soc. Lecture Note Ser., vol. 261, Cambridge Univ.
Press, Cambridge, 1999, pp. 410–416. MR 1676637 (2000h:20057)
[Laz96]
F. Lazebnik, On Systems of Linear Diophantine Equations, Math. Mag. Vol. 69, 1996,
pp. 261–266
[Lee12]
S. R. Lee, Geometry of Houghton’s Groups, arXiv:1212.0257v1 (2012).
[Mil71]
C.F. Miller III, On group-theoretic decision problems and their classification, Annals
of Math. Studies 68, (1971).
[Nov58]
P.S. Novikov On the algorithmic unsolvability of the word problem in group theory,
Trudy Mat. Inst. Steklov. 44 (1955), 143 pages. Translation in Amer. Math. Soc.
Transl. 9(2) (1958), 1–122.
[Sco87]
W. R. Scott, Group theory, second ed., Dover Publications, Inc., New York, 1987.
MR 896269 (88d:20001)
[JG15]
S. St. John-Green, Centralizers in Houghton’s groups, Proceedings of the Edinburgh
Mathematical Society (Series 2) 58 (2015), 769–785.
[Wie77]
J. Wiegold, Transitive groups with fixed-point-free permutations, II. Arch. Math.
(Basel) 29 (1977), no. 6, 571–573.
Mathematical Sciences, University of Southampton, SO17 1BJ, UK
E-mail address: cpgcox@gmail.com

