Enumerating limit groups
7 Enumerating limit groups
Daniel Groves and Henry Wilton
21st May 2007
Abstract
We prove that the set of limit groups is recursive, answering a
question of Delzant. One ingredient of the proof is the observation
that a finitely presented group with local retractions (à la Long and
Reid) is coherent and, furthermore, there exists an algorithm that
computes presentations for finitely generated subgroups. The other
main ingredient is the ability to algorithmically calculate centralizers
in relatively hyperbolic groups. Applications include the existence of
recognition algorithms for limit groups and free groups.
A limit group is a finitely generated, fully residually free group. Recent
research into limit groups has been motivated by their role in the theory of
the set of homomorphisms from a finitely presented group to a free group, and
in the logic of free groups. This research has culminated in the independent
solutions to Tarski’s problems on the elementary theory of free groups by
Z. Sela (see [21], [22] et seq.) and O. Kharlampovich and A. Miasnikov (see
[12], [13] et seq.). Sela’s work extends to the elementary theory of hyperbolic
groups [19].
We will be entirely concerned with finitely presentable groups. A class
of groups G is recursively enumerable if there exists a Turing machine that
outputs a list of presentations for every group G; it is recursive if, furthermore,
the Turing machine only outputs one presentation from each isomorphism
class of G. T. Delzant asked if the class of limit groups is recursive [20, I.13].
Theorem A (Corollary 3.8) The class of limit groups is recursive.
In [4] and [8, 7] it is shown that the isomorphism problem is solvable for
the class of limit groups. Therefore, if the class of limit groups is recursively
http://arxiv.org/abs/0704.0989v2
enumerable it is recursive. To enumerate limit groups, our approach is to
use the structure theory of limit groups developed in [13]. An equivalent
structure theory is described in [21], which could also be used. Either way,
two problems need to be solved. First, one needs to be able to compute
presentations for finitely generated subgroups of limit groups. We call this
property effective coherence. Secondly, one needs to be able to compute
centralizers of elements in limit groups. To solve the second problem we use
the relatively hyperbolic structure on limit groups found in [9] and [1]. Our
solution to the first problem relies on local retractions.
D. Long and A. Reid [14] defined a group to have local retractions or
property LR if every finitely generated subgroup is a retract of a finite-index
subgroup. A finitely presented group with local retractions is coherent. Fur-
thermore, one can compute presentations for subgroups.
Theorem B (Theorem 2.4) There exists an algorithm that, given a finite
presentation for a group G with local retractions and a finite set of elements
S, outputs a presentation for the subgroup generated by S.
It is a remarkable fact that limit groups are finitely presented. It was
proved in [23] that limit groups have local retractions. There is a lengthier
proof that limit groups are effectively coherent using the theorem, also proved
in [23], that iterated centralizer extensions are coset separable with respect
to their vertex groups.
As an application of Theorem A, in section 4 we prove the following
theorem.
Theorem C (Theorem 4.1) There exists an algorithm that, given as in-
put a presentation for a group G and a solution to the word problem in G,
determines whether or not G is a limit group.
In Corollary 4.3, we deduce the existence of a similar recognition algo-
rithm for free groups (pointed out to us by Gilbert Levitt).
This paper is the first of a series, in which we intend to prove algorith-
mic versions of Sela’s results. Specifically, enumerating limit groups will be
useful in the algorithmic construction of Makanin–Razborov diagrams over
free groups.
Acknowledgements
The authors would like to thank Zlil Sela for many insightful and generous
conversations, and also François Dahmani and Vincent Guirardel for pointing
out Corollary 4.2 to us. Thanks also to Gilbert Levitt for drawing Corollary
4.3 to our attention, and to Martin Bridson for explaining the ideas of the
paragraph before Theorem 3.5. The first author was supported in part by
NSF Grant DMS-0504251.
1 Effective coherence
A finitely generated group is coherent if all of its finitely generated subgroups
are finitely presented. We will be interested in the following algorithmic
version of coherence.
Definition 1.1 A coherent group G is effectively coherent if there exists an
algorithm that, given a finite subset S as input, outputs a presentation for
the subgroup generated by S.
A class G of coherent groups is uniformly effectively coherent if there
exists an algorithm that, given as input a presentation of a group G ∈ G and
a finite set S of elements of G, outputs a presentation for the subgroup of G
generated by S.
An appealing consequence of this property is that, under mild hypothe-
ses, one can decide if a homomorphism to an effectively coherent group is
injective.
Lemma 1.2 If a group G is effectively coherent then there exists an algo-
rithm that, given a presentation for a group H, a solution to the word problem
in H and a homomorphism f : H → G, determines whether f is injective.
Proof. Given a presentation for the image of f and a solution to the word
problem in H , it is easy to check whether f has a well-defined inverse and
hence is injective. Therefore, if G is effectively coherent it is easy to check if
f is injective. �
Remark 1.3 Even without a solution to the word problem in H, there exists
a Turing machine that will confirm in finite time if the homomorphism f is
injective. Indeed, if f is injective then we know what the inverse to f must
be. By effective coherence, it is possible to compute a presentation for the
image of f , and the inverse homomorphism exists if and only if the relations
for f(H) hold in H (under the supposed inverse map). Even though the word
problem for H may be unsolvable, it is straightforward to enumerate the words
which are equal to 1 in H, and if f is a homomorphism then the relations for
f(H) (interpreted as words in the generators for H) will eventually appear
on this list.
However, if the word problem in H is unsolvable then there will in general
be no Turing machine which terminates if the map f is not injective, since
we will not be able to tell, for example, if the group H is the trivial group.
Of course, a finitely generated subgroup of an effectively coherent group
is effectively coherent. If G is a class of groups, denote by S(G) the class of
finitely generated subgroups of groups in G. We are interested in effective
coherence because it allows the property of being recursively enumerable to
pass from G to S(G). Furthermore, uniform effective coherence also passes to
subgroups.
Lemma 1.4 If G is recursively enumerable and uniformly effectively coher-
ent then S(G) is recursively enumerable and uniformly effectively coherent.
Proof. Enumerating the presentations of groups G ∈ G and finite subsets
S ⊂ G, then using uniform effective coherence to compute presentations
for 〈S〉, one enumerates presentations for every group in S(G). So S(G) is
recursively enumerable.
Given a presentation for a group G ∈ S(G) and a finite subset S of G,
we can enumerate groups K ∈ G and homomorphisms f : G → K and check
whether f is an injection using the Turing machine described in Remark
1.3. Since G ∈ S(G) one will eventually find such an injection f . Using the
effective coherence of K, one can now compute a presentation for 〈f(S)〉. So
S(G) is uniformly effectively coherent. �
We approach effective coherence through local retractions.
2 Local retractions
A group G retracts onto a subgroup H if the inclusion map H →֒ G admits
a left-inverse ρ : G → H . The subgroup H is called a retract and the
map ρ is a retraction. Following [14], a group has local retractions if every
finitely generated subgroup is a retract of a finite-index subgroup. This has
immediate consequences for coherence.
Lemma 2.1 If H is a retract of a finitely presented group G then H is
finitely presented.
Proof. The proof of the lemma is a diagram chase. Let ρ : G → H be the
retraction. If B generates H then, since
G = H ker ρ
we can add elements from ker ρ to B to give a (finite) generating set A =
B ∪A′ for G. Furthermore, any finite presentation for G can be modified to
give a finite presentation with generators of this form.
Denote by FX the free group on a set X . Let ρ
′ be the obvious retraction
from FA = FB ∗ FA′ to FB that kills FA′. This gives a commutative square
−−−→ G
−−−→ H
where p and q are the natural surjections FA → G and FB → H respectively.
Denote the inclusion H →֒ G by i and the inclusion FB →֒ FA by i
′. The
lemma follows directly from the claim that ρ′ restricts to a retraction ker p →
ker q.
If l ∈ ker q then p◦ i′(l) = i◦q(l) = 1 so i′(l) ∈ ker p. Likewise, if k ∈ ker p
then q◦ρ′(k) = ρ◦p(k) = 1 so ρ′(k) ∈ ker q. This proves the claim and hence
the lemma. �
Since finite-index subgroups of finitely presented groups are finitely pre-
sented, coherence for finitely presented groups with local retractions follows
immediately.
Proposition 2.2 If a finitely presented group G has local retractions then
G is coherent.
Better still, Lemma 2.1 is effective.
Lemma 2.3 Let G be a finitely presented group with solvable word problem.
There is an algorithm that takes as input a finite presentation for G and a
collection of words which are the images of the generators under a homomor-
phism ρ : G → G that is a retract onto ρ(G), and outputs a presentation for
ρ(G).
Proof. Applying Tietze transformations, the given generating set for G will
eventually be of the form required in the proof of Lemma 2.1, namely the
union of some generators for ρ(G) and some elements of ker ρ, and since G has
solvable word problem we can tell when we have found such a presentation.
By the proof of Lemma 2.1, a presentation for ρ(G) is then obtained by
eliminating all the generators in ker ρ from the presentation of G. �
By [14, Theorem 2.4], groups with local retractions are residually finite
and hence have (uniformly) solvable word problem. Let LR be the class of
finitely presented groups with local retractions.
Theorem 2.4 The class LR is uniformly effectively coherent.
Proof. Given a finite presentation for a group G ∈ LR and a finite collection
of elements S ∈ G, we can enumerate all finite-index subgroups K of G using
the Reidemeister–Schreier Process (see, for instance, [15]). Since G ∈ LR,
there is a finite-index subgroup K of G so that 〈S〉 ⊆ K and so that there
exists a retraction ρ : K → 〈S〉.
We find such a retraction as follows. In parallel, consider each of the
finite-index subgroups of G. Given such a finite-index subgroup K, look
for the elements of S as words in the generators for K. Suppose we have
found a finite-index subgroup K so that 〈S〉 ⊆ K, and a finite presentation
〈X | R(X)〉 of K, with S = {s1(X), . . . , sn(X)} written as words in X
Now search for a collection of words Y in S± with a bijection ρ : X → Y so
that each of the relations of the form R(Y ) holds and so that for each i we
have si(Y ) = si(X). Then the map ρ extends to a retraction ρ : K → 〈S〉.
Since there is a retraction, we will eventually find such a K and Y .
The algorithm of Lemma 2.3 now computes a presentation for 〈S〉. �
3 Enumerating I and L
The class of iterated extensions of centralizers is defined inductively. If G is
a group, g ∈ G and Z(g) is the centralizer of g then an amalgamated free
product
G′ = G ∗Z(g) (Z(g)× Z
is said to be obtained from G by extension of centralizers.
Definition 3.1 The class I of iterated extensions of centralizers is the small-
est class of groups containing all finitely generated free groups and closed
under extension of centralizers. The class of limit groups is defined to be
L = S(I),
the class of finitely generated subgroups of iterated extensions of centralizers.
The usual definition of limit groups is as finitely generated fully residually
free groups.
Definition 3.2 A group G is fully residually free if, for every finite subset
X ⊂ G r 1, there exists a homomorphism to a free group G → F such that
1 /∈ f(X).
A finitely generated group is fully residually free if and only if it is in L, by
a theorem of [13]. Fully residually free groups are residually finite (since free
groups are) and so have solvable word problem. Using the fact that limit
groups are fully residually free, the following fact is well known and easy to
prove.
Lemma 3.3 If G is a limit group and g ∈ G then Z(g) is a free abelian
group.
By Theorem B of [23], limit groups have local retractions. It is clear that
all groups in I are finitely presented.
Corollary 3.4 The class I is uniformly effectively coherent.
By Lemma 1.4, to enumerate limit groups it remains only to enumerate
I. The crucial step is the ability to calculate centralizers.
For this we use the relatively hyperbolic structure of limit groups (found
independently by E. Alibegović [1] and F. Dahmani [9]). See [11] for an intro-
duction to relatively hyperbolic groups (where in Farb’s language we mean
‘relatively hyperbolic with BCP’). Limit groups are torsion-free and hyper-
bolic relative to a finite collection of maximal noncyclic abelian subgroups.
Dahmani [6] provides an algorithm which takes as input a finite presentation
of such a relatively hyperbolic group and outputs a basis for a representative
of each conjugacy class of noncyclic maximal abelian subgroup (Dahmani’s
algorithm takes as input an arbitrary finite presentation, and does not need
to be given the ‘relatively hyperbolic structure’ of the group).
Another important tool will be the universal theory of a group. The ele-
mentary theory of a group G is the set of all sentences in first-order predicate
logic (possibly with constants) that hold in G. For example, G is abelian if
and only if the sentence
∀x, y ∈ G [x, y] = 1
is in the elementary theory of G. A universal sentence is a sentence in the
elementary theory with a single universal quantifier. The universal theory of
G is the set of universal sentences in the elementary theory ofG. Deciding the
truth of universal sentences is equivalent to deciding whether finite systems
of equations and inequations (with constants) have solutions.
In [16], Makanin proved that the universal theory of a free group F is
decidable—that is, there exists an algorithm that, given as input a universal
sentence, determines whether or not it lies in the universal theory of F .
The universal theory of torsion-free relatively hyperbolic groups with abelian
parabolic subgroups is also decidable, by another algorithm of Dahmani [5]
(again the input is any finite presentation for the group, along with the
universal sentence).
There is an alternative approach to calculating centralizers using biauto-
matic structures. It follows from work of Rebbechi [18] that limit groups are
biautomatic, and the algorithm for finding automatic structures described
in [10] can be adapted to find biautomatic structures [3]. In particular, one
can calculate the fellow-traveller constant of the bicombing. Using the ideas
of [2], it is then easy to compute a presentation for the centralizer of an
arbitrary finite subset.
Theorem 3.5 There exists an algorithm that, given as input a presentation
for a group G ∈ I and an element g ∈ G, outputs a minimal set of generators
for Z(g).
Proof. Apply Dahmani’s algorithm from [6] to find a basis for a represen-
tative of each conjugacy class of maximal noncyclic abelian subgroup.
Let g ∈ G. There are two cases to consider: either g is parabolic (which
means conjugate into a noncyclic abelian subgroup) or else g is hyperbolic
(which means g is not parabolic).
It is possible to decide whether or not g is parabolic. This is because
the universal theory of G is decidable [5]. The element is parabolic if and
only if there exists an element h ∈ G so that hgh−1 commutes with each
element of one of the above bases for the noncyclic abelian subgroups. This
is a finite system of equations over G, which we can determine the truth of
by Dahmani’s algorithm from [5].
If g is parabolic, then we will find such an element h, and the conjugates
by h−1 of the basis for the maximal noncyclic abelian subgroup generates
the centralizer of g. In this case we have found a minimal generating set for
Z(g).
If g is hyperbolic then its centralizer is generated by a maximal root of g.
According to D. Osin [17, Theorem 1.16.(3)], it is possible to algorithmically
extract roots from hyperbolic elements of G. On the face of it, Osin’s algo-
rithm needs to be given as input the relatively hyperbolic structure of the
group. However, Dahmani’s algorithm from [6] will find this structure, so we
can make Osin’s algorithm take only the finite presentation as input. There-
fore, if g is hyperbolic we can find a maximal root of g, and this maximal
root is a minimal generating set for Z(g). �
Corollary 3.6 The set I is recursively enumerable.
Combining this with Theorem 3.4 it follows that the set of limit groups
L is recursively enumerable, by Lemma 1.4.
Corollary 3.7 The set of limit groups L is recursively enumerable and uni-
formly effectively coherent.
The results of [4] (see also [8, 7]) show that limit groups have solvable iso-
morphism problem. Hence we can improve recursively enumerable to recur-
sive: we can ensure that the list produced includes at most one presentation
for each isomorphism class of limit groups.
Corollary 3.8 The set of limit groups L is recursive.
On the other hand, by systematically applying Tietze transformations, it
is possible to effectively list all of the finite presentations of all limit groups.
We give a simple application to recognition algorithms here.
4 Recognition algorithms
Theorem 4.1 There exists an algorithm that, given as input a presentation
for a group G and a solution to the word problem in G, determines whether
or not G is a limit group.
Proof. Let P = 〈X | R〉 be the finite presentation defining G. We have
already noted that it is possible to enumerate all finite presentations of limit
groups. Thus if G is a limit group then P will eventually appear on this list.
Suppose then that G is not a limit group. Then G is not fully residually
free, so there is a finite set {g1, . . . , gr} of nontrivial elements of G so that
for any homomorphism φ from G to a free group F , at least one of the gi
is in ker(φ). This property of G can easily be translated into a system of
equations and inequations over F as follows. Consider both the elements
of R and each gi as a word in X
±, and write R = {r1, . . . , rk}. Then the
following sentence encodes the fact that at least one of {g1, . . . , gr} is in the
kernel of any homomorphism from G to F :
∀X ⊂ F
r1(X) = 1∧· · ·∧rk(X) = 1
g1(X) = 1∨· · ·∨gr(X) = 1
. (1)
By Makanin’s algorithm [16], it is possible to decide whether or not universal
sentences are true in a free group. Enumerate finite sets of nontrivial elements
of G (the solution to the word problem allows us to know that the elements
are nontrivial). Now, for each such finite set {r1, . . . , rk}, decide whether the
sentence (1) is true or not. If G is not a limit group, we will eventually find
a finite set for which (1) is true. �
Of course, one cannot recognize limit groups amongst arbitrary finitely
presented groups.
A cyclically pinched group is an amalgamated free product of two free
groups with cyclic amalgamated subgroup. Some, but not all, of these groups
are limit groups. In [20, I.3], Sela asks for necessary or sufficient conditions
for a cyclically pinched group to be a limit group. We do not have an answer
to this question. However, Theorem 4.1 implies that at least the question
has an answer. The following result was pointed to us by François Dahmani
and Vincent Guirardel (its proof contains the core of the proof of Theorem
4.1).
Corollary 4.2 There is an algorithm that takes as input a finite presentation
of a cyclically pinched group and decides whether or not the defined group is
a limit group.
It does not matter whether the input presentation exhibits the cyclically
pinched nature of the group, since by applying some finite number of Ti-
etze transformations it is possible to find such a presentation. Once such
a presentation is found, there is an explicit solution to the word problem.
Therefore Corollary 4.2 follows immediately from Theorem 4.1.
As remarked above, limit groups are torsion-free and hyperbolic relative
to their maximal abelian subgroups. There is an algorithm to distinguish
free groups among such relatively hyperbolic groups; indeed, it is proved in
[7, Theorem 1.4] that there exists an algorithm that computes the Grushko
decomposition from a presentation of such a group. Combining this with
Theorem 4.1, we obtain a similar recognition algorithm for free groups. This
corollary was pointed out to us by Gilbert Levitt.
Corollary 4.3 There exists an algorithm that, given as input a presentation
for a group G and a solution to the word problem in G, determines whether
or not G is free.
One can also deduce a similar result for surfaces. In [8, Theorem D] it
is shown that there exists an algorithm that computes a JSJ decomposition
for a torsion-free, freely indecomposable group that is hyperbolic relative
to its maximal abelian subgroups. In particular, combining this with the
algorithm from [7], one can decide whether or not a limit group is a surface
group. It follows as before that there exists an algorithm that, given as
input a presentation for a group G and a solution to the word problem in G,
determines whether or not G is a (fully) residually free surface group. (The
only surface groups that are not residually free are the fundamental groups
of the non-orientable surfaces of Euler characteristic 1, 0 and -1.)
References
[1] Emina Alibegović. A combination theorem for relatively hyperbolic
groups. Bull. London Math. Soc., 37(3):459–466, 2005.
[2] Martin R. Bridson. On the subgroups of semihyperbolic groups. In
Essays on geometry and related topics, Vol. 1, 2, volume 38 of Monogr.
Enseign. Math., pages 85–111. Enseignement Math., Geneva, 2001.
[3] Martin R. Bridson and Lawrence D. Reeves. On the algorithmic con-
struction of classifying spaces and the isomorphism problem for biauto-
matic groups. Preprint, 2007.
[4] I. Bumagin, O. Kharlampovich, and A. Miasnikov. Isomorphism prob-
lem for finitely generated fully residually free groups. J. Pure and Ap-
plied Algebra, 208(3):961–977, 2007.
[5] François Dahmani. Existential questions in (relatively) hyperbolic
groups. Preprint, 2006.
[6] François Dahmani. Finding relatively hyperbolic structures. Preprint,
2006.
[7] François Dahmani and Daniel Groves. Detecting free splittings in rela-
tively hyperbolic groups. TAMS, to appear.
[8] François Dahmani and Daniel Groves. The isomorphism problem for
toral relatively hyperbolic groups. Preprint, 2005.
[9] François Dahmani. Combination of convergence groups. Geom. Topol.,
7:933–963 (electronic), 2003.
[10] David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F.
Levy, Michael S. Paterson, and William P. Thurston. Word processing
in groups. Jones and Bartlett Publishers, Boston, MA, 1992.
[11] B. Farb. Relatively hyperbolic groups. Geom. Funct. Anal., 8(5):810–
840, 1998.
[12] O. Kharlampovich and A. Miasnikov. Irreducible affine varieties over a
free group. I. Irreducibility of quadratic equations and Nullstellensatz.
J. Algebra, 200(2):472–516, 1998.
[13] O. Kharlampovich and A. Miasnikov. Irreducible affine varieties over a
free group. II. Systems in triangular quasi-quadratic form and descrip-
tion of residually free groups. J. Algebra, 200(2):517–570, 1998.
[14] D. D. Long and A. W. Reid. Subgroup separability and virtual retrac-
tions of groups. Topology, to appear, 2006.
[15] Wilhelm Magnus, Abraham Karrass, and Donald Solitar. Combinato-
rial group theory: Presentations of groups in terms of generators and
relations. Interscience Publishers [John Wiley & Sons, Inc.], New York-
London-Sydney, 1966.
[16] G. S. Makanin. Decidability of the universal and positive theories of a
free group. Izv. Akad. Nauk SSSR Ser. Mat., 48(4):735–749, 1984.
[17] Denis V. Osin. Relatively hyperbolic groups: intrinsic geometry, alge-
braic properties, and algorithmic problems. Mem. Amer. Math. Soc.,
179(843):vi+100, 2006.
[18] D. Y. Rebbechi. Algorithmic properties of relatively hyperbolic groups.
Thesis, 2003. ArXiv: math/0302245.
[19] Z. Sela. Diophantine geometry over groups VIII: The elementary theory
of a hyperbolic group. Preprint.
[20] Zlil Sela. Diophantine geometry over groups: a list of research problems.
http://www.ma.huji.ac.il/~zlil/problems.dvi.
[21] Zlil Sela. Diophantine geometry over groups. I. Makanin-Razborov dia-
grams. Publ. Math. Inst. Hautes Études Sci., 93:31–105, 2001.
[22] Zlil Sela. Diophantine geometry over groups. II. Completions, closures
and formal solutions. Israel J. Math., 134:173–254, 2003.
[23] Henry Wilton. Hall’s Theorem for limit groups. Preprint, 2006.
Daniel Groves, Mathematics 253-37, California Institute of Tech-
nology, Pasadena, CA 91125
E-mail: groves@caltech.edu
http://arxiv.org/abs/math/0302245
Henry Wilton, Department of Mathematics, 1 University Sta-
tion C1200, Austin, TX 78712-0257
E-mail: henry.wilton@math.utexas.edu
	Effective coherence
	Local retractions
	Enumerating I and L
	Recognition algorithms
