THE SUBGROUP IDENTIFICATION PROBLEM FOR
FINITELY PRESENTED GROUPS

arXiv:1109.1792v4 [] 19 Oct 2016

MAURICE CHIODO
Abstract. We introduce the subgroup identification problem, and show
that there is a finitely presented group G for which it is unsolvable, and
that it is uniformly solvable in the class of finitely presented locally Hopfian
groups. This is done as an investigation into the difference between strong
and weak effective coherence for finitely presented groups.

1. Introduction
Decision problems for finitely presented groups are well-studied, going back
to the work of Dehn [8] in 1911. The word problem, of deciding when a word
represents the trivial element in a group, was the first of these to be well understood, with the independent work of Boone, Britton and Novikov [3, 5, 17]. A
clever adaption of this problem by the independent work of Adian and Rabin
[1, 18] gives rise to the impossibility of the isomorphism problem, of deciding
if two finite presentations describe isomorphic groups. To list all major results
in group-theoretic decision problems would be a substantial undertaking, and
we defer to [16] for an excellent introduction and survey of the discipline up to
1992.
For the remainder of this section we write X ∗ to denote all finite words on
a set X, P to denote the group given by a presentation P , and ⟨w1 , . . . , wn ⟩P
to denote the subgroup in P generated by words w1 , . . . , wn (see section 2.1 for
a clarification of this notation if required).
We introduce the following problem, and give the main result of this work.
Definition 1.1. We say that the subgroup identification problem for a finite
presentation P = ⟨X∣R⟩ is solvable if there is a partial algorithm that, on input
of any finite set of words w1 , . . . , wn ∈ X ∗ , and any finite presentation Q = ⟨Y ∣S⟩,
outputs (if the subgroup ⟨w1 , . . . , wn ⟩P ≅ Q) an explicit set map φ from Y to
{w1 , . . . , wn }∗ which extends to an isomorphism φ ∶ Q → ⟨w1 , . . . , wn ⟩P . That is,
the induced homomorphism φ ∶ Q → P is injective, and Im(φ) = ⟨w1 , . . . , wn ⟩P .
Otherwise, we place no conditions on the output, or even whether it halts.
Theorem 4.6. There is a finitely presented group with unsolvable subgroup
identification problem.
2010 AMS Classification: 20F10, 03D40, 03D80.
Keywords: Effectively coherent groups, subgroup identification problem, decidability.
The author was supported by:
An Australian Postgraduate Award, and a David Hay Postgraduate Writing-Up Award.
Date: October 20, 2016.
1

2

MAURICE CHIODO

As a consequence of lemma 2.6, having solvable subgroup identification problem depends only on the isomorphism class of a finite presentation.
In [9, Definition 1.1] a finitely generated group G is said to be effectively
coherent if it is coherent (all of its finitely generated subgroups are finitely
presentable) and there is an algorithm for G that, on input of a finite collection
of words S, outputs a finite presentation for the subgroup generated by S. This
motivates us to make the following two definitions:
Definition 1.2. We say a coherent group G = ⟨X∣R⟩ is weakly effectively coherent if there is an algorithm for G that, on input of a finite collection of words
S ⊂ X ∗ , outputs a finite presentation for the subgroup ⟨S⟩G generated by S.
Definition 1.3. We say a coherent group G = ⟨X∣R⟩ is strongly effectively
coherent if there is an algorithm for G that, on input of a finite collection of
words S ⊂ X ∗ , outputs a finite presentation P = ⟨Y ∣V ⟩ for the subgroup ⟨S⟩G
generated by S, along with a map φ ∶ Y → X ∗ which extends to an injection
φ ∶ P → G whose image is ⟨S⟩G .
By definition, strongly effectively coherent groups are weakly effectively coherent. Conversely, it is imediate that the notions of strong and weak effective
coherence are equivalent in groups with solvable subgroup identification problem. A motivating (unresolved) question for this work is whether strong and
weak effective coherence are equivalent notions for all finitely presented groups.
The subgroup identification problem was formulated after the author read
the proof of [9, Lemma 1.2] and [9, Remark 1.3] where, were it not for a later
typographical correction provided in [10, Definition 1.2], it would suggest that
the subgroup identification problem is (uniformly) solvable over all finitely presented groups. This would, in turn, imply that weak and strong effective coherence are equivalent notions. The groups encountered in [9] all have solvable
subgroup identification problem, as they are all locally Hopfian (see theorem 3.8
below). In addition, for all results shown in [9] all weakly effectively coherent
groups are actually proven to be strongly effectively coherent, so combined with
the typographical correction from [10, Definition 1.2] this then becomes a moot
point. We do not suggest that there are any errors with the main conclusions of
[9]. However, [9, Lemma 1.2 and Remark 1.3] do raise an interesting question
regarding the connection between strong and weak effective coherence.
An application of standard techniques gives the following result, which should
be read very carefully as one could misinterpret it as showing that the subgroup
identification problem is uniformly solvable for all finitely presented groups.
Proposition 3.5. There is a uniform partial algorithm that, on input of: A finite presentation P = ⟨X∣R⟩ of a group, and a finite set of words w1 , . . . , wn ∈ X ∗
such that ⟨w1 , . . . , wn ⟩P is finitely presentable, and Q = ⟨Y ∣S⟩ a finite presentation such that Q ≅ ⟨w1 , . . . , wn ⟩P ;
Outputs: A finite set of words c1 , . . . , ck ∈ {w1 , . . . , wn }∗ such that each ci is
trivial in P (when viewed as a word in X ∗ ) and ⟨w1 , . . . , wn ∣c1 , . . . , ck ⟩ is isomorphic to Q and hence also to ⟨w1 , . . . , wn ⟩P .

THE SUBGROUP IDENTIFICATION PROBLEM FOR FINITELY PRESENTED GROUPS 3

A group G is Hopfian if every surjective endomorphism of G is an isomorphism, and locally Hopfian if every finitely generated subgroup is Hopfian.
Theorem 3.8. The subgroup identification problem is uniformly solvable in the
class of finitely presented locally Hopfian groups. Hence, in this class of groups,
weak effective coherence is equivalent to strong effective coherence.
Thus the notions of weak and strong effective coherence are equivalent in
the class of locally Hopfian groups, and are so because in this class the subgroup identification problem is uniformly solvable. However, as soon as we start
dealing with non-Hopfian groups, the situation is a lot different.
The following theorem, and subsequent lemma, are vital to our main result.
They show that a solution to the word problem for a finite presentation cannot
be uniformly lifted to a solution to the word problem for a recursive presentation isomorphic to that same group (so an isomosphism between the two cannot
be constructed). This contrasts the case of having a pair of isomorphic finite
presentations, where an isomorphism can be uniformly constructed (lemma 2.6).
Theorem 4.1. There is a finite presentation P of a group with solvable word
problem (namely, the Baumslag-Solitar group BS(2, 3)) for which there is no
partial algorithm that, on input of a recursive presentation Q such that P ≅ Q,
outputs a solution to the word problem for Q.
Lemma 4.2. There is a finite presentation P = ⟨X∣R⟩ of a group with solvable
word problem (namely, BS(2, 3)) for which there is no partial algorithm that,
on input of a recursive presentation Q = ⟨Y ∣S⟩ such that P ≅ Q, outputs a set
map φ ∶ X → Y ∗ which extends to an isomorphism φ ∶ P → Q.
By viewing isomorphisms between groups as Tietze transformations rather
than set maps (see [13, §1.5] for a full exposition of this concept), we can reinterpret lemma 4.2 in the following way.
Lemma 4.4. There is a finite presentation P of a group with solvable word
problem (namely, BS(2, 3)) for which there is no algorithm that, on input of
a recursive presentation Q such that P ≅ Q, outputs a recursive enumeration
of Tietze transformations of type (T 1) and (T 2) (manipulation of relators),
and a finite set of Tietze transformations of type (T 3) and (T 4) (addition and
removal of generators), with notation as per [13, §1.5], transforming P to Q.
A direct consequence of the Higman embedding theorem [11, Theorem 1] is
that any recursively presented group can be uniformly embedded into a finitely
presented group. By a careful application of this result, paying special attention to the uniformity in which such a finite presentation is constructed as
given in the proof of [20, Theorem 12.18], our main result (theorem 4.6) follows.

4

MAURICE CHIODO

Acknowledgements: The author would like to thank Jack Button and Andrew Glass for their general advice, and Chuck Miller for giving general comments and corrections as well as pointing out a more elegant proof of lemma
3.6 and a much more direct proof of theorem 4.6. Thanks also go to Nicholas
Touikan for his helpful suggestions for a revised version of this work, and to
Daniel Groves and Henry Wilton for explaining their work in [9].
2. Preliminaries
2.1. Standard notation. With the convention that N contains 0, we take
ϕm to be the mth partial recursive function ϕm ∶ N → N, and the mth partial
recursive set (r.e. set) Wm as the domain of ϕm . If P = ⟨X∣R⟩ is a group
presentation with generating set X and relators R, then we denote by P the
group presented by P . A presentation P = ⟨X∣R⟩ is said to be a recursive
presentation if X is a finite set and R is a recursive enumeration of relators;
P is said to be an infinite recursive presentation if instead X is a recursive
enumeration of generators. A group G is said to be finitely presentable if G ≅ P
for some finite presentation P . If P, Q are group presentations then we denote
their free product presentation by P ∗ Q, given by taking the disjoint union
of their generators and relators; this extends to the free product of arbitrary
collections of presentations. If X is a set, then we denote by X −1 a set of
the same cardinality as X along with a fixed bijection φ ∶ X → X −1 , where
we denote x−1 ∶= φ(x). We write X ∗ for the set of finite words on X ∪ X −1 ,
including the empty word ∅. If g1 , . . . , gn are a collection of elements of a
group G, then we write ⟨g1 , . . . , gn ⟩G for the subgroup in G generated by these
elements, and ⟪g1 , . . . , gn ⟫G for the normal closure of these elements in G. A
group G is Hopfian if every surjective endomorphism of G is an isomorphism,
and locally Hopfian if every finitely generated subgroup is Hopfian. Finally, the
commutator [x, y] is taken to be xyx−1 y −1 .
2.2. Groups. It is a result by Mihailova [14] that there exists a finitely presented group with solvable word problem for which the subgroup membership
problem, of deciding when a word on the generators lies in a given finitely generated subgroup, is unsolvable. We mention this in the context of the following
known result about the word problem for HNN extensions of groups.
Lemma 2.1. Let H, K ⩽ G be isomorphic finitely generated subgroups of G,
each having solvable subgroup membership problem in G. Let ϕ ∶ H → K be an
isomorphism. Then the HNN extension G∗ϕ has solvable word problem.
Proof. This is immediate from the normal form theorem for HNN extensions
(see [12, §IV Theorem 2.1]).

The following group construction from [2] plays an important part in our
arguments, as it is an explicit example of a finitely presented non-Hopfian group
with solvable word problem.
Definition 2.2. The Baumslag-Solitar groups BS(m, n) are defined via the
following finite presentations, each an HNN extension of Z:
BS(m, n) ∶= ⟨s, t∣s−1 tm s = tn ⟩

THE SUBGROUP IDENTIFICATION PROBLEM FOR FINITELY PRESENTED GROUPS 5

Theorem 2.3 (Baumslag-Solitar [2, Theorem 1]). The group BS(2, 3) is nonHopfian and has solvable word problem. The map f ∶ BS(2, 3) → BS(2, 3) given
by extending the map f ∶ {s, t} → {s, t}∗ , f (s) = s, f (t) = t2 , is a non-injective
epimorphism. The word [s−1 ts, t] is non-trivial in BS(2, 3) and lies in ker(f ).
Proof. That BS(2, 3) has solvable word problem comes from the fact that it is
an HNN extension of Z (see lemma 2.1, or alternatively a result by Magnus in
[12, § IV Theorem 5.3] that all 1-relator groups have solvable word problem).
The remainder of the theorem is proved in [2, Theorem 1].

2.3. Enumerable processes in groups. We note some partial algorithms
and recursively enumerable sets, in the context of group presentations. These
are standard results, which we state (without proof) for the convenience of any
reader not familiar with the area.
Lemma 2.4. Let P = ⟨X∣R⟩ be a recursive presentation. Then the words in
X ∗ which represent the identity in P are recursively enumerable. Moreover,
this algorithm is uniform over all recursive presentations.
Lemma 2.5. There is a partial algorithm that, on input of two finite presentations P = ⟨X∣R⟩ and Q = ⟨Y ∣S⟩, and a set map φ ∶ X → Y ∗ , halts if and only
if φ extends to a homomorphism φ ∶ P → Q.
Lemma 2.6. There is a partial algorithm that, on input of two finite presentations P = ⟨X∣R⟩ and Q = ⟨Y ∣S⟩, halts if and only if P ≅ Q, and outputs an
isomorphism between them.
It is important to note that lemma 2.6 does not hold if we instead consider
recursive presentations. In fact, even if we start with one recursive presentation,
and one finite presentation, the lemma does not hold; we show this later as
lemma 4.2.
Lemma 2.7. Let P = ⟨X∣R⟩ be a finite presentation. Then the set of finite presentations defining groups isomorphic to P is recursively enumerable. Moreover,
this enumeration algorithm is uniform over all finite presentations.
3. Initial questions and observations
3.1. The finite presentation problem. Following [4, Definition 1.1], we say
that the finite presentation problem for a finitely presented group ⟨X∣R⟩ is
solvable if there is a partial algorithm that, on input of a finite set of words
w1 , . . . , wn ∈ X ∗ such that ⟨w1 , . . . , wn ⟩P is finitely presentable, outputs a finite
presentation Q for ⟨w1 , . . . , wn ⟩P . By definition, a finitely presented weakly effectively coherent group has solvable finite presentation problem. The existence
of a finitely presented group with unsolvable word problem immediately gives
rise to the following obsevation:
Lemma 3.1. There is a finite presentation P = ⟨X∣R⟩ of a group for which the
finite presentation problem is unsolvable.

6

MAURICE CHIODO

Proof. Take P = ⟨X∣R⟩ to be a finite presentation of a group with unsolvable
word problem (see [20, Lemma 12.7]), and suppose this has an algorithm to
solve the finite presentation problem. Note that for any word w ∈ X ∗ , we have
that ⟨w⟩P is cyclic, and hence finitely presentable. So, on input of a single word
w, the algorithm will output a finite presentation Q of the cyclic group ⟨w⟩P .
But the isomorphism problem for finitely presented abelian groups is solvable
(see [16] p. 31), so we can decide if Q is trivial, and hence if w is trivial in P ,
which is impossible since P has unsolvable word problem.

Remark. As pointed out to the author by Chuck Miller, the work of Collins in [7]
shows that the group in lemma 3.1 can be taken to have solvable word problem.
This is because such an algorithm for the finite presentation problem would
explicitly solve the order problem, of deciding what the order of an element of
the group is, and a direct consequence of [7, Theorem A] is that there is a finitely
presented group with solvable word problem and unsolvable order problem.
Bridson and Wilton [4] give an in-depth analysis of the finite presentation
problem, showing that it is not uniformly solvable in several classes of finitely
presented groups [4, Corollary C]. Moreover, they construct a finite presentation
of a group with polynomial Dehn function (and hence solvable word problem)
which has unsolvable finite presentation problem [4, Theorem E].
Having seen that the finite presentation problem is unsolvable in general, we
shift our attention to similar questions. By considering the trivial group, and
the fact that the triviality problem is undecidable, one can show that there is
no algorithm that, given two finite presentations P, Q, determines if P embeds
in Q or not. The following two stronger results were obtained in [6], and are
closely related to the subgroup identification problem.
Theorem 3.2 (Chiodo [6, Theorem 6.8]). There is a finitely presented group
G such that the set of finite presentations of groups which embed into G is not
recursively enumerable.
Theorem 3.3 (Chiodo [6, Theorem 6.6]). There is no algorithm that, on input
of two finite presentations P = ⟨X∣R⟩, Q = ⟨Y ∣S⟩ such that P embeds in Q,
outputs an explicit map φ ∶ X → Y ∗ which extends to an embedding φ ∶ P ↪ Q.
In the proof of theorem 3.3, as found in [6], we see that the algorithmic
problem arises from not definitely knowing a set of target words for an injection
from P into Q. Knowing which elements P maps to in Q brings us precisely to
the subgroup identification problem.
3.2. The subgroup identification problem for Hopfian groups. The following is a standard result about finitely presentable groups.
Lemma 3.4. Let ⟨X∣R⟩ be a recursive presentation of a finitely presentable
group. Then there is a finite subset R′ ⊆ R such that ⟨X∣R⟩ ≅ ⟨X∣R′ ⟩ via
extention of the identity map on X. That is, there is a finite truncation R′ of
R such that all other relations are a consequence of the first R′ .

THE SUBGROUP IDENTIFICATION PROBLEM FOR FINITELY PRESENTED GROUPS 7

The following result could lead us to think that all finitely presented groups
have solvable subgroup identification problem, and we urge the reader to study
this carefully to become convinced that it is not what is proved.
Proposition 3.5. There is a uniform partial algorithm that, on input of: A finite presentation P = ⟨X∣R⟩ of a group, and a finite set of words w1 , . . . , wn ∈ X ∗
such that ⟨w1 , . . . , wn ⟩P is finitely presentable, and Q = ⟨Y ∣S⟩ a finite presentation such that Q ≅ ⟨w1 , . . . , wn ⟩P ;
Outputs: A finite set of words c1 , . . . , ck ∈ {w1 , . . . , wn }∗ such that each ci is
trivial in P (when viewed as a word in X ∗ ) and ⟨w1 , . . . , wn ∣c1 , . . . , ck ⟩ is isomorphic to Q and hence also to ⟨w1 , . . . , wn ⟩P .
Proof. Begin an enumeration c1 , c2 , . . . of all words in the {w1 , . . . , wn }∗ which
are trivial in P (when viewed as words in X ∗ ); this can be done by repeated application of lemma 2.4. Define the presentation Pl ∶= ⟨w1 , . . . , wn ∣c1 , . . . , cl ⟩. By
lemma 3.4, as ⟨w1 , . . . , wn ⟩P is finitely presentable, and T ∶= ⟨w1 , . . . , wn ∣c1 , c2 , . . .⟩
is a recursive presentation of a group isomorphic to ⟨w1 , . . . , wn ⟩P via extension
of the map wi ↦ wi , there exists some finite m such that P m ≅ T (again via
extension of the map wi ↦ wi ). That is, using lemma 3.4 we can truncate the
relations of T at position m (forming Pm ) such that all successive relations are
consequences of the first m (note that selecting m is not an algorithmic process;
for the moment we merely appeal to the fact that such an m exists). So we have
Q ≅ ⟨w1 , . . . , wn ⟩P ≅ T ≅ P m , where Q is our given explicit finite presentation.
Now we use lemma 2.6 to begin checking for an isomorphism between Q and
P 1 , P 2 , . . . as a parallel process. Eventually this process will stop at some k

(perhaps different from m) such that P k ≅ T ≅ Q.
Note that we were very careful to mention that the selection of m in the above
proof was existential, but not necessarily recursive. This is very important, as
later in corollary 4.3 we construct a class of recursive presentations for which
the selection of such an m is provably non-recursive.
Remark. With the above proof in mind, one would naively hope that the map
from Pk = ⟨w1 , . . . , wn ∣c1 , . . . , ck ⟩ to P = ⟨X∣R⟩ given by extending wi ↦ wi ∈ X ∗
would be an injection onto its image ⟨w1 , . . . , wn ⟩P ; in the case that P k is
Hopfian this would indeed be true, as shown later in in lemma 3.7. But theorem
4.6 shows that this is not true in general.
The existence of a finitely presented non-Hopfian group, combined with
lemma 3.4, immediately gives rise to the following:
Lemma 3.6. There exist finite presentations P = ⟨x1 , . . . , xn ∣r1 , . . . , rm ⟩ and
Q = ⟨x1 , . . . , xn ∣r1 , . . . , rm , s1 , . . . , sk ⟩, along with a recursive presentation T =
⟨x1 , . . . , xn ∣r1 , r2 , . . .⟩ (where ri are the same in P, Q, T for all i ≤ m) such that:
1. P ≅ Q ≅ T (and hence T is finitely presentable).
2. The quotient maps φ ∶ P → Q and ψ ∶ P → T , each an extension of the map
xi ↦ xi , are not isomorphisms.

8

MAURICE CHIODO

Observe that the above quotient maps are always isomorphisms in the case of
Hopfian groups, by very definition. The point of making the above observation
is to stress the following:
1. There may be many ways to truncate the relators of T to get a presentation
of a group isomorphic to P .
2. Truncating T to get a finite presentation T ′ with T ′ ≅ T may not give
a presentation which is isomorphic to P via the quotient map we have been
discussing.
Lemma 3.7. Let P , Pk and {w1 , . . . , wn } be as in the proof of proposition 3.5.
If ⟨w1 , . . . , wn ⟩P is Hopfian, then the map φ ∶ {w1 , . . . , wn } → X ∗ sending wi
(as a generator of Pk ) to wi (as a word in X ∗ ) extends to a monomorphism
φ ∶ P k ↪ P , and thus to an isomorphism to its image ⟨w1 , . . . , wn ⟩P .
Proof. By the proof of proposition 3.5, we know that φ extends to a surjection
φ ∶ P k ↠ ⟨w1 , . . . , wn ⟩P . But P k ≅ ⟨w1 , . . . , wn ⟩P , which is Hopfian. Hence φ
must be injective, and thus an isomorphism.

Theorem 3.8. The subgroup identification problem is uniformly solvable in the
class of finitely presented locally Hopfian groups. Hence, in this class of groups,
weak effective coherence is equivalent to strong effective coherence.
Proof. The first part follows from lemma 3.7; the second is then immediate.



4. Main results
We begin by making the important observation that a solution to the word
problem can’t be algorithmically lifted from a finite presentation of BS(2, 3) to
a recursive presentation of BS(2, 3).
Theorem 4.1. There is a finite presentation P of a group with solvable word
problem (namely, BS(2, 3)) for which there is no partial algorithm that, on input
of a recursive presentation Q such that P ≅ Q, outputs a solution to the word
problem for Q.
Proof. Assume we have such an algorithm. Take P = ⟨X∣R⟩ to be a finite
presentation for BS(2, 3). Fix Q = ⟨X∣R∪S⟩ to be a finite presentation of a nontrivial quotient which is isomorphic to P , but not by the extension IdX of the
map IdX ∶ X → X (say, instead, by the extension φ of the map φ ∶ X → X ∗ ). Fix
a word w ∈ X ∗ such that w lies in the kernel of φ, but is not trivial in BS(2, 3).
Given any r.e. set Wi , we form the recursive presentation Pi,j ∶= ⟨X∣R (∪S if j ∈
Wi ) ⟩. That is, Pi,j ∶= ⟨X∣R⟩ if j ∉ Wi , and Pi,j ∶= ⟨X∣R ∪ S⟩ if j ∈ Wi . So Pi,j
is a recursive presentation (we add all the relators S to Q if we see j ∈ Wi ).
Now use our assumed algorithm that solves the word problem in Pi,j to test
if φ(w) = e in P i,j ; this will occur if and only if j ∈ Wi . By taking Wi to be
non-recursive, we derive a contradiction.

Note. The above proof is not the original proof as developed by the author, but
a simplified version due to Chuck Miller which follows from lemma 3.6 of this
work. The author is grateful to Chuck for this simplification.

THE SUBGROUP IDENTIFICATION PROBLEM FOR FINITELY PRESENTED GROUPS 9

Lemma 4.2. There is a finite presentation P = ⟨X∣R⟩ of a group with solvable
word problem (namely, BS(2, 3)) for which there is no partial algorithm that,
on input of a recursive presentation Q = ⟨Y ∣S⟩ such that P ≅ Q, outputs a set
map φ ∶ X → Y ∗ which extends to an isomorphism φ ∶ P → Q.
Proof. Suppose such an algorithm exists. Given a recursive presentation Q =
⟨Y ∣S⟩ such that P ≅ Q, use our supposed algorithm to output a set map φ ∶
X → Y ∗ which extends to an isomorphism φ ∶ P → Q. But since we have a
solution to the word problem for P , we can combine this with the map φ to get
a solution to the word problem for Q, thus contradicting theorem 4.1.

Note that, by lemma 3.4, in the above proof there will always be a finite
subset S ′ of S such that all other relators are consequences of S ′ , and hence
⟨Y ∣S⟩ ≅ ⟨Y ∣S ′ ⟩. So we have the following immediate corollary:
Corollary 4.3. There is a finite presentation P = ⟨X∣R⟩ of a group with solvable word problem (namely, BS(2, 3)) for which there is no partial algorithm
that, on input of a recursive presentation Q = ⟨Y ∣S⟩ such that P ≅ Q, outputs
a finite subset S ′ ⊆ S such that all other relators S ∖ S ′ are consequences of S ′ .
Equivalently, construction of a finite truncation point m of S (with m as in the
proof of proposition 3.5) is not algorithmically possible in general.
As an aside, if we were instead to view isomorphisms between groups as
Tietze transformations rather than set maps (see [13, §1.5] for a full exposition
of this concept) then we can interpret lemma 4.2 in the following way.
Lemma 4.4. There is a finite presentation P of a group with solvable word
problem (namely, BS(2, 3)) for which there is no algorithm that, on input of
a recursive presentation Q such that P ≅ Q, outputs a recursive enumeration
of Tietze transformations of type (T 1) and (T 2) (manipulation of relators),
and a finite set of Tietze transformations of type (T 3) and (T 4) (addition and
removal of generators), with notation as per [13, §1.5], transforming P to Q.
Remark. It should be pointed out that such a sequence of Tietze transformations
as described above will always exist, which follows directly from lemma 3.4; we
merely truncate the relators of Q to get a finite presentation Q′ , perform a
finite sequence of Tietze transformations which takes P to Q′ (possible by [13,
Corollary 1.5]), and then add the rest of the enumeration of relators of Q to Q′ .
The point here is that we cannot compute an enumeration of such a sequence
in general.
Before proceeding to our main result, we note the following lemma which
shows that the direction in which we define our isomorphism in lemma 4.2 is
inconsequential.
Lemma 4.5. Using the notation of lemma 4.2, having an explicit set map
φ ∶ X → Y ∗ which extends to an isomorphism φ allows us to construct a set map
ψ ∶ Y → X ∗ which extends to the inverse of φ (and hence is an isomorphism).
The reverse also holds.

10

MAURICE CHIODO

Proof. This follows from the fact that we only deal with recursive presentations, and we can uniformly enumerate all trivial words of such presentations
by lemma 2.4.

We now have all the technical machinery required to prove our main result:
Theorem 4.6. There is a finitely presented group with unsolvable subgroup
identification problem.
Note that, by theorem 3.8, such a group cannot be locally Hopfian.
Proof. Take a recursive enumeration Pi ∶= ⟨Xi ∣Ri ⟩ of all recursive presentations
of groups (fix some countably infinite alphabet A; each Xi is a finite subset of
A, and each Ri is a recursive enumeration of words in Xi∗ ). By the Higman
embedding theorem (see [20, Theorem 12.18]) we can embed their free product
(with presentation P1 ∗P2 ∗. . .) into a finitely presented group with presentation
P = ⟨X∣R⟩. Then the group P does not have solvable subgroup identification
problem, for if it did then we could use this to contradict lemma 4.2 as follows:
By the uniformity of Higman’s result, as described in the proof of [20, Theorem
12.18], there is a uniform procedure that, for any i, outputs a finite set of
words Si ⊂ X ∗ in 1-1 correspondence with Xi such that the subgroup ⟨Si ⟩P
is isomorphic to P i , and an explicit bijection φi ∶ Xi → Si which extends to
an isomorphism φi ∶ Pi → ⟨Si ⟩P . That is, we can keep track of where each
P i is sent in this embedding. So, given a recursive presentation Q = ⟨Y ∣S⟩
and a finite presentation H = ⟨Z∣V ⟩ such that H ≅ Q, compute j such that
Pj = Q as recursive presentations (that is, number all Turing machines which
read alphabet Y , and look for one identical to the description S). We know that
H ≅ ⟨Sj ⟩P . So use our algorithm to output a set map ψ ∶ Z → Sj∗ which extends
to an isomorphism ψ ∶ H → ⟨Sj ⟩P . But we can compose ψ with φ−1
j to get the
∗
−1
set map φ−1
j ○ ψ ∶ Z → Y which extends to an isomorphism φj ○ ψ ∶ H → Q.
But this is impossible by lemma 4.2, so our assumed algorithm can’t exist. 

5. Further work
The group G constructed in theorem 4.6 contains an embedded copy of every
recursively presented group, and so is not coherent, let alone weakly effectively
coherent. We ask the question of whether theorem 4.6 can be modified so that
G is weakly effectively coherent, or even merely coherent. Either of these would
help make the result even more relevant, as we conjecture that strong and weak
effective coherence are not equivalent properties for finitely presented groups.
References
[1] S. I. Adian, Finitely presented groups and algorithms, Dokl. Akad. Nauk SSSR 117, 9–12
(1957).
[2] G. Baumslag, D. Solitar, Some two generator one-relator non-Hopfian groups, Bull. Amer.
Math. Soc. 68, 199–201 (1962).
[3] W. W. Boone, The word problem, Ann. of Math., 70, 207–265 (1959).
[4] M. Bridson, H. Wilton, On the difficulty of presenting finitely presentable groups, Groups
Geom. Dyn. 5, 301–325 (2011).

THE SUBGROUP IDENTIFICATION PROBLEM FOR FINITELY PRESENTED GROUPS11

[5] J. L. Britton, The word problem for groups, Proc. London Math. Soc. (3) 8, 493–506
(1958).
[6] M. Chiodo, Finding non-trivial elements and splittings in groups, J. Algebra. 331, 271–
284 (2011).
[7] D. J. Collins, The word, power and order problems in finitely presented groups, in Word
Problems, eds. Boone, Cannonito, and Lyndon, Amsterdam, North-Holland, 401–420
(1973).
[8] M. Dehn, Über unendliche diskontinuerliche Gruppen (German), Math. Ann. 69, 116–144
(1911).
[9] D. Groves, H. Wilton, Enumerating limit groups, Groups Geom. Dyn. 3, 389–399 (2009).
[10] D. Groves, H. Wilton, Enumerating limit groups: A Corrigendum, arXiv:1112.1223v1
(2011).
[11] G. Higman, Subgroups of finitely presented groups, Proc. Royal Soc. London Ser. A 262,
455–475 (1961).
[12] R. Lyndon, P. Schupp, Combinatorial Group Theory, Springer (2001).
[13] W. Magnus, A. Karrass, D. Solitar, Combinatorial group theory, Dover (2004).
[14] K. A. Mihailova, The occurrence problem for direct products of groups, Dokl. Akad. Nauk
SSSR 119, 1103–1105 (1958).
[15] C. F. Miller III, On group theoretic decision problems and their classification, Annals of
Math. Study 68, Princeton University Press, Princeton, NJ (1971).
[16] C.F. Miller III, Decision problems for groups-survey and reflections. Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989), Math. Sci. Res. Inst. Publ.,
23, Springer, New York, 1–59 (1992).
[17] P. S. Novikov, On the algorithmic unsolvability of the word problem in group theory, Trudy
Mat. Inst. Steklov 44, 1–143 (1955).
[18] M. O. Rabin, Recursive unsolvability of group theoretic problems, Annals of Math. 67,
172–194 (1958).
[19] H. Rogers Jr, Theory of recursive functions and effective computability, MIT Press (1987).
[20] J. Rotman, An introduction to the theory of groups, Springer-Verlag, New York (1995).

Dipartimento di Matematica ‘Federigo Enriques’
Università degli Studi di Milano
Via Cesare Saldini 50, Milano, 20133, ITALIA
maurice.chiodo@unimi.it

