arXiv:1501.03097v6 [math.GR] 18 Apr 2016

Effective construction of canonical Hom-diagrams
for equations over torsion-free hyperbolic groups
Olga Kharlampovich, Alexei Myasnikov, Alexander Taam
February 12, 2018
Abstract
We show that, given a finitely generated group G as the coordinate
group of a finite system of equations over a torsion-free hyperbolic group
Γ, there is an algorithm which constructs a canonical solution diagram by
constructing canonical (corrective extensions of) Γ-NTQ-groups. These
groups are toral relatively hyperbolic Γ-limit groups. The diagram encodes all homomorphisms from G to Γ as compositions of factorizations
through Γ-limit quotients (constructed by defining their generators inside canonical NTQ groups) and canonical automorphisms induced on
the freely indecomposable factors of these quotients by canonical automorphisms of the corresponding NTQ-subgroups. Additionally, we show
that a group is a Γ-limit group if and only if it is an iterated generalized
double over Γ.

1

Introduction

Given a group G, another group L is said to be fully residually G (or discriminated by G) if, given any finite subset A ⊂ L, 1 ∈
/ A, there exists a
homomorphism φ : L → G, such that φ(a) 6= 1 for all a ∈ A. The study of
groups discriminated by various classes of groups has been ongoing since the
early twentieth century, with increased activity often occuring as other equivalent characterizations of such groups, and applications in different fields, are
found. For example, the development of algebraic geometry over groups allowed
finitely generated groups discriminated by a free group F to be understood as
coordinate groups of irreducible systems of equations over F . This helped enable solutions to Tarski’s problems on the elementary theory of free groups,
given independently by Kharlampovich-Myasnikov and Sela ([17] and [26]).
Throughout, we let Γ be an arbitrary fixed torsion-free hyperbolic group.
While some of the theory of fully residually free groups can be generalized
easily to groups discriminated by Γ, in general groups discriminated by Γ are
more difficult to work with for several reasons. Unlike finitely generated fully
residually free groups, finitely generated fully residually Γ groups may be not
finitely presented and can contain finitely generated subgroups with no finite
presentation, so algorithmic results are often be more difficult to obtain.
1

For a group G which is equationally Noetherian (i.e. every system of equations over G with n variables is equivalent to a finite sub-system), there are
many descriptions of the class of finitely generated fully residually G groups.
Let L be a finitely generated group and G an equationally Noetherian group.
The following are equivalent:
1. L is a G-limit group (in the space of marked groups, see [9] for definition)
2. L is fully residually G
3. L embeds in an ultrapower of G
4. T h∀ (G) ⊆ T h∀ (L) (T h∀ is universal first order theory)
5. T h∃ (G) ⊇ T h∃ (L) (T h∃ is existential first order theory)
6. L is the coordinate group GR(S) (see Section 2.1) of an irreducible (in the
Zariski topology) algebraic set over G defined by a system S of coefficientfree equations (call such a system an irreducible system)
There are analagous equivalent characterizations for the case with coefficients (see [18] Theorem B).
Given a group G, a free rank one extension of centralizer over G is a group
E = hG, t|[CG (U ), t] = 1i, where U ⊆ G is finite. Note that E ∼
= G∗CG (U) ∼
=
G ∗CG (U) (CG (U ) × Z). A free rank n extension of centralizer is defined similarly
as G ∗CG (U) (CG (U ) × Zn ). A group is called an iterated extension of centralizer over G if it may be obtained from G by a finite sequence of extension of
centralizers (each centralizer in the previous group).
Proposition 1. (Theorem E in [18]) Given a fixed toral relatively hyperbolic
group G, a group L is a G-limit group if and only if it embeds into an iterated
extension of centralizer over G.
In fact, the embeddings into iterated extentions of centralizers are obtained
via embeddings into G-NTQ groups, which are coordinate groups of nicely structured systems of equations (see Section 2.1.2). Some relevant details of such
embeddings are described in Section 5, along with other related constructions.
Our first main theorem shows that, for a fixed torsion-free hyperbolic group
Γ, the class of iterated generalized doubles over Γ (terminology introduced by
Champetier and Guirardel in [3] for free groups) is also equivalent to the class
of Γ-limit groups.
Definition 1. A group G is a generalized double over a Γ-limit group L if it
splits as G = A ∗C B, or G = A∗C , where A and B are finitely generated such
that:
1. C is a non-trivial abelian group whose images are maximal abelian subgroups in the vertex groups.
2. there is an epimorphism φ : G → L which is injective on each vertex group
2

Note that each vertex group is discriminated by Γ.
Definition 2. A group is an iterated generalized double over Γ if it belongs to
the smallest class of groups IGD − Γ that contains groups isomorphic to subgroups of Γ, and is stable under free products and the construction of generalized
doubles over groups in IGD − Γ.
Champetier and Guirardel showed in [3] that IGD − F is the class of F -limit
groups. Our first main theorem shows that the same holds for Γ-limit groups.
Theorem 1. G is a Γ-limit group if and only if it is an iterated generalized
double over Γ
Theorem 1 is proved in Section 3. The proof uses Bass-Serre theory and
the fact that Γ-limit groups are exactly the groups which embed into iterated
extensions of centralizers over Γ.
Recall that the Grushko decomposition of a finitely generated group G is the
free product decomposition G = Fr ∗A1 ∗· · · Ak , where Fr is a free group of finite
rank, and each Ai is non-trivial, freely indecomposable, and not infinite cyclic
(see [12]). This decomposition is unique up to permutation of the conjugacy
classes of the Ai in G. In section 4.2, we describe a canonical decomposition
of a certain type, called a primary JSJ decomposition, for a freely indecomposable Γ-limit group, which encodes all of its abelian splittings. Primary JSJ
decompositions were shown to exist for Γ-limit groups in [27].
Our second main theorem gives an algorithm that, given a finite system of
equations over Γ, constructs a finite diagram with associated groups which has
certain canonical properties. Such a canonical Hom-diagram (which is described
more precisely in Section 5.5) encodes all homomorphisms from the coordinate
group ΓR(S) to Γ as compositions of factorizations through Γ-limit quotients, and
certain canonical automorphisms which correspond to JSJ decompositions of
freely indecomposable factors of those quotients. Furthermore certain canonical
NTQ groups are associated to such a diagram (through a process also described
in Section 5.5).
Theorem 2. Let S(Z, A) = 1 be a finite system of equations over Γ. There is an
algorithm to construct a complete set of canonical (corrective extensions of ) ΓNTQ groups that are, in particular, toral relatively hyperbolic Γ-limit groups, and
associated completed canonical Hom-diagram and canonical Hom-diagram for
ΓR(S) . All solutions of S(Z, A) = 1 in Γ factor through the strict fundamental
sequences corresponding to these (corrective extensions of ) Γ-NTQ groups.
NTQ Γ-limit groups Ni in the completed diagram with branches (7) are toral
relatively hyperbolic and constructed by their finite presentations, and canonical groups of automorphisms are given by their generators (and we know their
presentation).
Γ-limit groups Gi in the branch (6) of the Hom-diagram are constructed by
defining their generators inside corresponding N T Q-groups Ni and canonical
automorphisms of these Γ-limit groups are induced on their freely indecomposable factors by canonical automorphisms of Ni .
3

Theorem 2 is proved in Section 6.
We thank D. Groves and H. Wilton for constructing “cautionary examples”
[11] that helped us to improve the exposition of this work, through necessary
clarifications and error corrections.

2
2.1

Preliminaries
Algebraic geometry over groups

We start with some basic theory of algebraic geometry over groups. For more
background, see [1]. Let G be a group generated by a finite set A and F (X)
the free group on X = {x1 , . . . , xn }. For S ⊂ G[X] = G ∗ F (X), the expression S(X, A) = 1 is called a system of equations over G, and a solution of
S(X, A) = 1 in G, is a G-homomorphism φ : G[X] → G such that φ(S) = 1 (a
G-homomorphism is determined by Z = φ(X) ∈ Gn ; the notation S(Z, A) = 1
means that Z corresponds to a solution of S).
Denote the set of all solutions of S(X, A) = 1 in G by VG (S), the algebraic
set defined by S. Define the Zariski topology on Gn by taking algebraic sets as a
pre-basis of closed sets. Note that the algebraic set VG (S) uniquely corresponds
to the normal subgroup R(S) = {T (X, A) ∈ G[X]|∀Z ∈ Gn (S(Z, A) = 1 →
T (Z, A) = 1)} in G[X], called the radical of S. Call GR(S) = G[X]/R(S) the
coordinate group of S. Every solution of S(X, A) = 1 in G can be described as
a G-homomorphism GR(S) → G.
2.1.1

Quadratic equations

A system of equations S(X, A) = 1 is said to be (strictly) quadratic if each
xi ∈ X that appears in S, appears at most (exactly) twice, where x−1
also
i
counts as an appearance. There are four standard quadratic equations:
n
Y

[xi , yi ] = 1; n ≥ 1

(1)

i=1
n
Y

[xi , yi ]

m
Y

czi i d = 1; n, m ≥ 0, n + m ≥ 1

(2)

n
Y

(3)

i=1

i=1

x2i = 1; n ≥ 1

i=1
n
Y

i=1

x2i

m
Y

czi i d = 1; n, m ≥ 0, n + m ≥ 1

(4)

i=1

where ci and d are non-trivial elements of G. Note that for any strictly quadratic
word S ∈ G[X], there is a G-automorphism of G[X] that takes S to a standard
quadratic word. Also, there is a surface with boundary associated to each
standard quadratic equation, specifically an orientable surface of genus n with
4

zero punctures for (1), an orientable surface of genus n with m + 1 punctures
for (2), a non-orientable surface of genus n and zero punctures for (3), and a
non-orientable surface of genus n with m + 1 punctures for (4). For a standard
quadratic equation S, let χ(S) be the Euler characteristic of the associated
surface.
2.1.2

G-NTQ groups

General systems of equations can exhibit some properties similar to those of
quadratic systems. This can be seen when systems are in a particular quasiquadratic form.
Definition 3. A system of equations S(X, A) = 1 over a group G generated by
A, is called triangular quasi-quadratic over G or G-TQ, if it can be partitioned
into subsystems:
S1 (X1 , C1 ) = 1
S2 (X2 , C2 ) = 1
..
.
Sn (Xn , Cn ) = 1
where:
(i) {X1 , . . . , Xn } is a partition of X
(ii) Gi = G[Xi , . . . , Xn , A]/RG (Si , . . . , Sn ) for 1 ≤ i ≤ n
(iii) Gn+1 = G ∗ F (where F is a free group of finite rank) or a subgroup of
this group that is a free product of F , G and conjugates of G by some
generators of F .
(iv) Ci = Xi+1 ∪ . . . ∪ Xn ∪ A ⊂ Gi+1 for 1 ≤ i ≤ n − 1 and Cn = A.
Furthermore, for each i the subsystems Si must have one of the following
forms:
(I) Si is quadratic in Xi
(II) Si = {[x, y] = 1, [x, u] = 1|x, y ∈ Xi , u ∈ U } where U is a maximal cyclic
subgroup of F (Xi+1 , . . . , Xn , A)
(III) Si = {[x, y] = 1|x, y ∈ Xi }
(IV) Si is empty
The number n is called the depth of the system.

5

Notice that it may be assumed that every subsystem of form (I) is actually
a single quadratic equation in standard form. Also, it can be checked directly
that Gi ≃ Gi+1 [Xi ]/RGi+1 (Si ). S(X, A) = 1 is called non-degenerate triangular
quasi-quadratic over G or G-NTQ if it is G-TQ and for every i, the system
Si (Xi , Ci ) = 1 has a solution in Gi+1 , and if Si is of form (II) the set U
generates a centralizer in Gi+1 . A regular G-NTQ system is a G-NTQ system
in which each non-empty quadratic equation Si is in standard form, and either
χ(Si ) ≤ −2 and the quadratic equation has a non-commutative solution in Gi+1 ,
or it is an equation of the form [x, y]d = 1 or [x1 , y1 ][x2 , y2 ] = 1.
Finally a group is called a (regular) G-NTQ group if it is isomorphic to the
coordinate group of a (regular) G-NTQ system of equations. Note that in Sela’s
work [26], ω-residually free towers provide an analagous structure to F -NTQ
groups, and in the work of Casals-Ruiz and Kazachkov [2], graph towers are, in
a certain sense, higher dimensional analogues of NTQ systems for working with
right angle Artin groups.
Suppose G is a toral relatively hyperbolic group. Every G-NTQ group is
also toral relatively hyperbolic [18]. In certain circumstances, when the bottom
level Gn+1 is clear from the context we will be talking (abusing the language)
about N T Q groups, not specifying Gn+1 .

2.2

Graphs of groups

A graph of groups G(X) is a connected graph X(V, E) labelled with a group Gv
for each vertex v ∈ V , and a group Ge with monomorphisms αe : Ge → G∂0 (e) ,
βe : Ge → G∂1 (e) for each edge e ∈ E (∂0 (e) and ∂1 (e) denote the initial and
terminal vertices of e respectively). Note that X is considered to be a nonoriented graph, (i.e. there is an involution ¯ : E → E with ∂0 (e) = ∂1 (ē) for
each e ∈ E), so the monomorphisms of a graph of groups must also satisfy
αe (Ge ) = βē (Gē ).
Let T be a maximal subtree of X. The fundamental group of X(V, E) with
respect to T is the group π(G(X), T ) which is generated by h∗v∈V Gv , ∗e∈E te i
with relations {te = 1∀e ∈ T, te tē = 1∀e ∈ E, tē α(g)te = β(g)∀g ∈ Ge , ∀e ∈ E}.
Any choice of maximal subtree gives an isomorphic fundamental group of the
graph of groups. A splitting of a group G over some class of group E is an
isomorphism from G to π(G(X(V, E)), T ) where each Ge is in E. Splittings are
discussed in further detail in Section 4.
Graphs of groups are closely related to the Bass-Serre theory of groups acting
without inversion on trees. We note here one significant consequence which will
be used later.
Proposition 2. (see [4], Theorem 3.7 in [24]) Given G the fundamental group
of a graph of groups, and H ≤ G. Then H is the fundamental group of the
induced graph of groups with vertex and edge groups given by intersections of H
with conjugates of vertex and edge groups of G, respectively.

6

3

Iterated generalized doubles

We can now prove Theorem 1. We start with the following useful elementary
example of a generalized double.
Lemma 1. A free rank one extension of centralizer over Γ1 , where Γ1 ≤ Γ, is
a generalized double over Γ.
Proof. Given G =< Γ1 , t|[CΓ1 (U ), t] = 1 >= Γ1 ∗CΓ1 (U) , let φ : G → Γ1
φ(x) =



x
1

; x ∈ Γ1
;x = t

φ is injective on Γ1 and by definition a centralizer is maximal abelian in
Γ1 .
With Proposition 1, this is enough to prove one direction of Theorem 1.
Proposition 3. Let G be a generalized double over a Γ-limit group L. Then G
is a Γ-limit group.
Proof. First consider the case where G is an amalgamated product. Let φ be the
map from G to L as in the definition of generalized double. Denote the images of
A, B, C under φ by Aφ , B φ , and C φ respectively. Let Ĉ be the maximal abelian
subgroup of L containing C φ . Consider the group L̂ =< L, t|[c, t] = 1, c ∈ Ĉ >.
Since L embeds into an iterated centralizer extension of Γ, so does L̂. Let
Ĝ = Aφ ∗C φ (B φ )t ; clearly Ĝ ≤ L̂. We claim that G ∼
= Ĝ.
This can be showed using normal forms. In particular, the maps φ|ˆA : A → Ĝ
and φ|ˆB : B → Ĝ defined by composing the restrictions of φ to A and B
respectively with the natural embedding of Aφ and B φ into Ĝ (and in the
case of φ|ˆB : B → Ĝ, composing with conjugation by the stable letter t in
between), are injective (only the conjugation need be checked, and this follows
since t is stable letter for L̂) by Theorem 1.6 of [24]. So define φ̂ : G → Ĝ
by a1 b1 . . . an bn 7→ aφ1 t−1 bφ1 t . . . aφn t−1 bφn t for each word in G in normal form
(ai , bi ∈
/ C). Since if bi ∈ C then t−1 bφi t = bφi and ai ∈
/ C so aφi ∈
/ Ĉ, we have
φ −1 φ
φ −1 φ
a1 t b1 t . . . an t bn t in normal form. Since every element of Ĝ has normal form
of aφ1 t−1 bφ1 t . . . aφn t−1 bφn t = φa1 b1 . . . an bn , φ is an isomorphism. Then G embeds
into L̂ and so by Proposition 1, G is a Γ-limit group. The case for G = A∗C is
similar, since Ĝ = Aφ ∗C φ (and using the fact that if images of C φ don’t coincide
then they must be conjugate by commutative transitivity) again embeds into
L̂.
To prove the converse, we use the Bass-Serre tree.
Proposition 4. Every Γ-limit group can be constructed by iterated generalized
doubles over Γ.

7

g1 t2 g2 tL

g 1 t2 g 2 C
g 1 t2 L

g 1 t3 L
g 1 t2 C

g1 tg2 tL
g1 tC

tg1 tg2 tL

g1 tg2 C

tg1 tg2 C
tg1 tL

g1 tL

tg1 tC

tg1 C

tg1 t2 L
tL

gn tL

tC

g1 C
gn C

t2 L

C

t2 C
L

t2 g 1 C
t2 g1 tL

t3 L

Figure 1: Bass-Serre tree
Proof. Given a freely indecomposable Γ-limit group, by Proposition 1, it may be
embedded into an iterated extension of centralizers G over Γ. G is an iterated
generalized double over Γ. We claim that every subgroup of G is also an iterated
generalized double.
We proceed by induction. Let H ≤ G =< L, t|[CL (u), t] = 1 > for some
Γ-limit group L and u ∈ L. Let C = CL (u). So G is an HNN extension
G = L∗C . Now by Proposition 2, H acts (without inversions) on a tree with
vertices given by the cosets gL (stabilizers are the groups Lg ∩ H), and edges
gC (corresponding to groups C g ∩ H), for each coset representative g ∈ G. In
particular the initial vertex of the edge gC is gL and terminal vertex of gC is
gtL.
Every coset gL has a representative of the form tr0 g1 tr1 . . . gn trn where the
gi ∈ L are representatives for cosets of C in L, gn 6= 1 and the ri are non-zero
except possibly r0 and rn . Now for each edge tr0 g1 tr1 . . . gn trn C, the terminal vertex is tr0 g1 tr1 . . . gn trn +1 L and the initial vertex is tr0 g1 tr1 . . . gn trn L if
rn 6= 0, and tr0 g1 tr1 . . . gn−1 trn−1 L if rn = 0. See Figure 1 (vertex cosets are in
red, edge cosets in blue). We want to show that the corresponding edge group
8

in the quotient graph of groups is maximal abelian in one of the correspond−1 −r0
−rn −1
and
ing vertex groups. Now Stab(tr0 g1 tr1 . . . gn trn L) = H ∩ Lt gn ...g1 t
−1 −r0
−rn −1
gn ...g1 t
t
rn
r1
r0
.
Stab(t g1 t . . . gn t C) = H ∩ C
−1 −r0
−1 −r0
−rn −1
−rn −1
≤ Lt gn ...g1 t , and since C t = C we have
Clearly C t gn ...g1 t
−1 −r0
−rn −1 −1
−rn −1 −1
−rn −1
gn ...g1−1 t−r0
gn ...g1−1 t−r0
= Ct
≤ Lt
.
C t gn ...g1 t
−1 −r0
−1 −r0
−rn−1
−1 −rn−1
−1 −rn−1
...g1 t
...g1 t
...g1−1 t−r0
Finally, C gn t
≤ Lgn t
= Lt
.
A conjugate of a centralizer is again a centralizer in the corresponding conjugate of the ambient group (this can be easily checked directly), and centralizers
are maximal abelian. So intersecting a maximal abelian subgroup and it’s ambient group with H preserves maximality of the abelian subgroup (again, this
can be easily checked directly).
−1 −1
Also, clearly every conjugate Lt g is isomorphic to L, and so each H ∩
−1 −1
Lt g can be mapped monomorphically to L. Since any free factor of a Γ-limit
group is a Γ-limit group, the proposition is proved.
Theorem 1 follows (since free products of Γ limit groups are also Γ-limit
groups).

4

Further background on splittings

In this section we describe properties of JSJ decompositions of groups. We
refer to [23], [7], [8], and [13] for further background on other notions of JSJ
decompositions for groups.
Recall that an abelian splitting of a group G is an isomorphism to the fundamental group of a graph of groups with all abelian edge groups. It is often
convenient to slightly abuse terminology and allow a splitting to refer to the
graph of groups itself. An elementary splitting is one in which the graph of
groups has exactly one edge. A splitting is reduced if the image of each edge
group is a proper subgroup of the corresponding vertex group. A splitting of
a group G is essential if it is reduced, all edge groups are abelian and for each
edge group E, if γ ∈ G, γ k ∈ E for some k 6= 0, then γ ∈ E.
A subgroup H ≤ G is said to be elliptic with respect to a given splitting, if
it is conjugate to a subgroup of some vertex group of the splitting. If H is not
elliptic, then it is called hyperbolic with respect to the splitting.
There are certain elementary transformations of graphs of groups which preserve the fundamental group.
An unfolding of an elementary splitting G ∼
= A ∗C B is another splitting
G ∼
= A ∗C1 B1 where C1 is a proper subgroup of C and B = C ∗C1 B1 . An
unfolding of an elementary splitting G ∼
= A∗C is another splitting G ∼
= A1 ∗C1
where the image of C1 in A1 is a proper subgroup of C, and A = A1 ∗C1 (tCt−1 )
where t is the stable letter of A∗C . We say a splitting is unfolded if there is no
unfolding of any induced elementary splitting.

9

4.1

Classification of vertex groups

Vertex groups may be divided into three classes.
1. Abelian vertex groups
2. Quadratically hanging vertex groups. A vertex group Gv is quadratically
hanging (or QH), if it admits either of the presentations (i.e. it is the
fundamental group of a surface with finitely many punctures):
(i) ha1 , . . . , ag , b1 , . . . , bg |

g
Y

[ai , bi ]

m
Y

pj i where g ≥ 0, m ≥ 1, and if

j=1

i=1

g = 0 then m ≥ 4
(ii) ha1 , . . . , ag , p1 , . . . , pm |

g
Y

i=1

a2i

m
Y

pj i where g ≥ 1, m ≥ 1

j=1

and furthermore:
• for each edge group Ge with ∂0 (e) = v, αe (Ge ) is conjugate to hpj i
in Gv for some j = 1, . . . , m
• and for each j = 1, . . . , m there is some edge ej with ∂0 (ej ) = v and
αej (Gej ) conjugate to hpj i in Gv .
3. Vertex groups which are non-abelian and non-QH are called rigid vertex
groups.
Any subgroup H ≤ G which is a QH vertex group in some splitting of G is
called a QH subgroup of G. A QH subgroup Q ≤ G is a maximal quadratically
hanging subgroup (or MQH subgroup), if given any elementary splitting of G
with edge group Ge , either Q is elliptic in that splitting, or Ge can be conjugated
into Q and that elementary splitting is induced by splitting Q along the image
of Ge .

4.2

JSJ decompositions

There are various definitions of splittings which are called JSJ decompositions
(after the topological notion of decomposing 3-manifolds along essential tori due
to Jaco, Shalen, and Jacobsen) for various classes of groups. All of them are
canonical in that they encode all other splittings (of a certain type) in some
sense. We will use some particular qualifications for the canonical decompositions of Γ-limit groups.
Definition 4. Given a reduced unfolded abelian splitting D of a freely indecomposable Γ-limit group L, call D a JSJ decomposition of L, if the following
properties are satisfied:

10

(i) Every MQH subgroup of L is conjugate to a vertex group of the D, (so
every QH subgroup of L can be conjugated into a vertex group of the JSJ),
and every vertex group of the D which is not conjugate to a MQH subgroup
of L is elliptic in any abelian subgroup of L.
(ii) Any elementary abelian splitting of L which is hyperbolic in another elementary abelian splitting, can be obtained from D by the splitting of an
MQH subgroup, which is induced by cutting the corresponding surface along
an essential simple closed curve, and collapsing all other edges.
(iii) Any elementary abelian splitting of L which is elliptic with respect to every
other elementary elementary abelian splitting of L, can be obtained from
D by a sequence of collapsings, foldings, and conjugations.
(iv) Any two reduced unfolded abelian splittings of L satisfying the above three
properties can be obtained from one another by a sequence of slidings, conjugations, and modification of boundary monomorphisms by conjugations.
(v) All non-cyclic abelian subgroups of L are elliptic in D.
In [27] (Theorem 1.10), every freely indecomposable Γ-limit group is shown
to have such a JSJ decomposition.

5

Hom-diagrams and Γ-NTQ groups

We present here some constructions from [18] and [14], along with some similar
background from [17] in the free group case. Building on those foundations,
we define and prove the existence of canonical Hom-diagrams and associated
canonical NTQ groups.
Unless otherwise stated, for systems with coefficients in Γ, all homomorphisms in Hom-diagrams for the system are assumed to be Γ-homomorphisms.

5.1

Canonical automorphisms

Consider an elementary abelian splitting of a group G. If we have G = A ∗C B,
for c ∈ C define an automorphism φc : G → G such that φc (a) = a for a ∈ A
and φc (b) = bc = c−1 bc for b ∈ B. If instead we have G = A∗c then for c ∈ C
we define φc : G → G such that φc (a) = a for a ∈ A and φc (t) = ct.
Call the φc a Dehn twist obtained from the corresponding elementary abelian
splitting of G. If G is an Γ-group, where Γ is a subgroup of one of the factors A
or B, then Dehn twists that fix elements of the group Γ ≤ A are called canonical
Dehn twists. Similarly, one can define canonical Dehn twists with respect to an
arbitrary fixed subgroup K of G. Let D(G) [resp. DΓ (G)] be the set of all
abelian splittings of G [resp. the set of all abelian splittings such that Γ ≤ G is
elliptic].

11

Definition 5. Let D ∈ D(G) [D ∈ DΓ (G)] be an abelian splitting of a group
G and Gv be either a QH or an abelian vertex of D. Then an automorphism
ψ ∈ Aut(G) is called a canonical automorphism corresponding to the vertex Gv
if ψ satisfies the following conditions:
(i) ψ fixes (up to conjugation) element-wise all vertex group in D, other than
Gv . If Γ ≤ Gv then ψ also fixes each element of Γ. Note that ψ also fixes
(up to conjugation) all the edge groups.
(ii) If Gv is a QH vertex in D, then ψ is a Dehn twist (canonical Dehn twist)
corresponding to some essential Z-splitting of G along a cyclic subgroup of
Gv .
(iii) If Gv is an abelian subgroup then ψ acts as an automorphism on Gv which
fixes all the edge subgroups of Gv .
Definition 6. Let e be an edge in an abelian splitting D of a group G. Let
ψ ∈ Aut(G). Call ψ a canonical automorphism corresponding to the edge e if
ψ is a Dehn twist of G with respect to the elementary splitting of G along the
edge e, induced from the splitting D. If D ∈ DΓ (G), then ψ must fix Γ element
wise.
Definition 7. The group of canonical automorphisms of a closed surface group
G with respect to a trivial splitting D (ie. G is the only vertex group) is AD (G) =
M CG(Σ) (the mapping class group of the surface).
Otherwise, the group of canonical automorphisms of a freely indecomposable
group G with respect to an abelian splitting D is the subgroup AD (G) ≤ Aut(G),
generated by all canonical automorphisms of G corresponding to all edges, all
QH vertices, and all abelian vertices of D. If G is not a Γ − group then include
conjugation as well. The group of canonical automorphisms of a free product is
the direct product of the canonical automorphism groups of factors.

5.2

Solution tree T (S, Γ)

In this section we describe how to encode solutions to equations over Γ using
a Hom-diagram. We begin by describing a Hom-diagram for generalized equations [16] over free groups. There is an algorithm described in [16] that, given
a generalized equation Ω(X, A) over the free group F = F (A), constructs a diagram, which encodes the solutions of Ω. Let G be the coordinate group FR(Ω)
of Ω considered as a system of equations over F . Specifically, the algorithm
constructs a directed, finite, rooted tree T that has the following properties:
(i) Each vertex v of T is labelled by a pair (Gv , Qv ), where Gv is an F -quotient
of G and Qv the subgroup of canonical automorphisms in AutF (Gv ) corresponding to a splitting of Gv as a fundamental group of a grapg of groups,
that we find from the Elimination process of Ω. The root vo is labelled by
(FR(Ω) , 1) and every leaf is labelled by (F (Y ) ∗ F (A), 1) where Y is some
finite set (called free variables). Each Gv , except possibly Gv0 , is fully
residually F .
12

(ii) Every (directed) edge v → v ′ is labelled by a proper surjective
F -homomorphism π(v, v ′ ) : Gv → Gv′ .
(iii) For every φ ∈ HomF (FR(Ω) , F ), that is a solution of Ω (that must be
non-cancellable in F ) there is a path p = v0 v1 . . . vk , where vk is a leaf
labelled by (F (Y ) ∗ F (A), 1), elements σi ∈ Qvi , and a F -homomorphism
φ0 : F (Y ) ∗ F (A) → F (A) such that
φ = π(v0 , v1 )σ1 π(v1 , v2 )σ2 . . . π(vk−2 , vk−1 )σk−1 π(vk−1 , vk )φ0

(5)

Considering all such F -homomorphisms φo , the family of the above sequences of homomorphisms is called the fundamental sequence over F corresponding to p.
Considering all such F -homomorphisms φo that produce solutions of Ω
the family of the solutions of Ω factoring through the above fundamental
sequence is called the fundamental sequence for the generalized equation Ω
over F corresponding to p.
(iv) The splitting of each fully residually free group Gv is its Grushko decomposition followed by the abelian splittings of the factors that are found by
the Elimination process. If Cvi is such a factor, then the splitting is not
necessarily the JSJ decomposition of Cvi , but it is maximal in a sense that
it encodes all elementary abelian splittings of Cvi that can be found by
the Elimination process, and has maximal QH and abelian vertex groups
that can be found by the elimination process for Gv .
Notice that not all the homomorphisms that factor through (5) are solutions
of Ω, but they all are homomorphisms from FR(Ω) to F .
In [19] it is shown, given a finite system of equations S(Z, A) = 1 over Γ,
how to construct a similar diagram encoding Hom(ΓR(S) , Γ). We briefly review
the construction here.
First construct the generalized equations S1 (X1 , A), . . . , Sn (Xn , A) over F
from the system S(Z, A) = 1 over Γ by taking canonical representatives in
F (A) for elements of Γ (which exists by Theorem 4.5 of [22]), see Lemma 3
in [19] for more details on the construction of these systems. Construct the
free group solution tree Ti as described above, for each generalized equation
Si (Xi , A). We form a new, larger tree T by taking a root vertex vo labelled
by F (Z, A), attaching it to the root vertex of each Ti by an edge labelled by
ρi , where ρi : F (Z, A) → FR(Si ) is the homomorphism induced by canonical
representatives. For each leaf v of Ti , labelled by F (Y ) ∗ F , build a new vertex
w labelled by F (Y ) ∗ Γ and an edge v → w labelled by the epimorphism πY :
F (Y ) ∗ F (A) → F (Y ) ∗ Γ which is induced from π : F → Γ by acting as the
identity on F (Y ). We call a path b = v0 v1 . . . vk from the root v0 to a leaf vk a
branch b of T .
Now associate to each branch b the set Φb consisting of all homomorphisms
F (Z, A) → Γ of the form
ρi π(v1 , v2 )σ2 · · · π(vk−2 , vk−1 )σk−1 π(vk−1 , vk )πY φ,
13

where
ρi π(v1 , v2 )σ2 · · · π(vk−2 , vk−1 )σk−1 π(vk−1 , vk )
is a solution of the generalized equation, and where σj ∈ Qvj and φ ∈ HomΓ (F (Y )∗
Γ, Γ). Since HomΓ (F (Y ) ∗ Γ, Γ) is in bijective correspondence with the set of
functions ΓY , all elements of Φb can be effectively constructed.
Notice, that Φb is not a fundamental sequence over Γ, it is a fundamental
sequence of solutions of a generalized equation over F , followed by a homomorphism πY φ.

5.3

F -NTQ to Γ-NTQ reworking process

In this section we recall the construction that first was used in [14] and was
developed in [19] that for each Φb constructs a strict fundamental sequence over
Γ.
Definition 8. A fundamental sequence or a fundamental set of homomorphisms over Γ corresponding to the diagram
ΓR(S) →π0 G1 →π1 G2 → . . . →πn−1 Gn = F ∗ Γ ∗ H1 ∗ . . . ∗ Hk
where
1. H1 , . . . , Hk are freely indecomposable groups isomorphic to subgroups of
Γ, and G1 , . . . , Gn are Γ-limit groups.
2. πi , 0 < i < n − 1 are fixed proper epimorphisms, πn−1 is an epimorphism
but may not be proper.
3. The homomorphisms in this sequence are compositions π0 σ1 π1 . . . σn−1 πn−1 τ ,
where σi is a canonical automorphism of Gi corresponding to a Grushko
decomposition of Gi followed by some abelian decompositions of the freely
indecomposable factors where all non-cyclic abelian subgroups are elliptic.
Canonical automorphisms are identical on the free factor of this Grushko
decomposition.
4. τ is a homomorphism that maps each Hi monomorphically into a conjugate
of a fixed subgroup of Γ (and for each Hi it is a fixed monomorphism
followed by a conjugation) and maps F into Γ.
Definition 9. A fundamental sequence defined above is called strict if it
has the following properties:
1. The image of each non-abelian vertex group of Gi under πi is non-abelian.
2. For each 1 ≤ i < n, πi is injective on rigid subgroups, edge groups, and
subgroups generated by the images of edge groups in abelian vertex groups
in Gi−1 .

14

3. For each 1 ≤ i < n, if R is a rigid subgroup in Gi and {Aj }, 1 ≤ j ≤ m, the
abelian vertex groups in Gi connected to R by edge groups Ej with the maps
ηj : Ej → Aj , then πi is injective on the subgroup hR, η1 (E1 ), . . . , ηm (Em )i
which we will call the envelop of R.
4. The images of different factors in the Grushko decomposition of Gi under
πi are different factors in the free decomposition of Gi+1 .
The construction of the tree of strict fundamental sequences over Γ, T (S, Γ)
relies on a ‘reworking process’, which converts F -NTQ systems into appropriate
Γ-NTQ systems. In T (S, Γ), each strict fundamental sequence Φ̄b corresponds
to a Γ-NTQ group Nb (with depth of Γ-NTQ system equal to the length of the
branch b) into which ΓR(S) maps by a homomorphism φb : ΓR(S) → Nb . We
briefly summarize the construction and important properties of T (S, Γ) here.
Each branch of T has a corresponding F -NTQ system that comes from a generalized equation for canonical representatives. Considering the F -NTQ system
as a system of equations over Γ does give groups through which all homomorphisms from ΓR(S) to Γ factor, but the systems may not be in Γ-NTQ form (as
a result of the map F → Γ trivializing some vertex or edge groups). The reworking process fixes those degenerate portions, while maintaining the factoring
of all homomorphisms ΓR(S) → Γ. For each F -NTQ system N (X, A) = 1, the
reworking process constructs a new Γ-NTQ system of equations L1 (X ′ , A) = 1
over Γ (see [14], section 3.3 and [19]. The following proposition is proved in [19],
and it follows from the construction in [14].
Proposition 5. Each branch of T (S, Γ) has the following form
ΓR(S) →ψ0 L1 →ψ1 L2 → . . . →ψn−1 Ln = F ∗ Γ ∗ K1 ∗ . . . ∗ Kk ,
where K1 , . . . , Kk are freely indecomposable groups isomorphic to freely indecomposable factors in the Grushko decomposition of Γ; L1 , . . . , Ln are NTQ Γ-limit
groups; ψ0 is a fixed homomorphism; and ψi are fixed proper epimorphisms
which are retractions onto Li+1 for 0 < i ≤ n − 1.
There is a strict fundamental sequence assigned to each branch. The homomorphisms in this sequence are compositions ψ0 σ1 ψ1 . . . σn−1 ψn−1 τ where σi is
a canonical automorphism corresponding to Li , and τ is a homomorphism that
maps each Ki monomorphically onto a conjugate of the corresponding subgroup
of Γ (and for each Ki it is a fixed monomorphism followed by a conjugation),
and maps F into Γ.
Every homomorphism from ΓR(S) to Γ factors through one of the fundamental sequences corresponding to the branches of T (S, Γ). Factors in the Grushko
decomposition of Li are mapped into different factors in the Grushko decomposition of Li+1 .
Each branch of T (S, Γ) can be effectively constructed.

5.4

Quasi-convex closure

Let Γ be a torsion-free non-elementary hyperbolic group, and H a subgroup of
Γ given by generators. We describe a certain procedure that constructs a group
15

K, H ≤ K ≤ Γ such that K is quasi-convex in Γ and every abelian splitting of
K induces a splitting of H.
If H is hyperbolic in every cyclic splitting of Γ, then let K = Γ.
If H is elliptic in a cyclic splitting of Γ, we consider instead of Γ a vertex
group Γ1 containing a conjugate of H. Such a subgroup Γ1 is quasi-convex and
so hyperbolic, as it is a vertex group, and the quasi-convexity constants can be
found effectively. If H is elliptic in a cyclic splitting of Γ1 , continue this process
until H is not elliptic in any decomposition of the corresponding vertex group
Γj . So let K be the corresponding conjugate of Γj such that H ≤ K. This
subgroup K is a quasi-convex closure of H. K is relatively quasi-convex, so
therefore hyperbolic. Note that hierarchical accessibility for hyperbolic groups
was proved by Louder and Touikan in [20].

5.5

A complete set of canonical NTQ groups

In Section 5.2 we constructed a tree of strict fundamental sequences (or a Homdiagram) encoding all solutions of a finite system S(Z, A) = 1 of equations over
Γ using the tree of fundamental sequences for “covering” systems of equations
over F . A canonical Hom-diagram is a tree of “canonical” strict fundamental sequences (in [17], Section 7.6, a similar tree was called the (augmented)
canonical embedding tree TCE (FR(S) )) which satisfy certain properties.
We define a canonical Hom-diagram iteratively. All the homomorphisms
from ΓR(S) into Γ factor through a finite number of maximal Γ-limit quotients
of ΓR(S) . We continue with each maximal Γ-limit quotient (that we denote by
G1 ) in parallel. We factor G1 into freely indecomposable factors G11 , . . . G1t
and the free factor Fr . Homomorphisms from each G1i to Γ in a canonical
Hom-diagram are given by compositions of canonical automorphisms corresponding to a JSJ decomposition of G1i with one of the finite number of fixed
epimorphisms from G1i onto its maximal standard (proper) Γ-limit quotients
G1i,1 , . . . G1i,,p and with homomorphisms from these proper Γ-limit quotients
to Γ that are constructed iteratively. Namely, we factor again each G1i,j into
a free product of freely indecomposable factors and the free factor, etc. Since
each proper sequence of Γ- limit quotients is finite, the construction of Homdiagram terminates after finitely many steps. It terminates with either a fixed
embedding of a Γ-limit group in the diagram into Γ followed by a conjugation
in Γ and substitutions of the terminal free groups that appear in the diagram,
into Γ.
The canonical Hom-diagram is a tree. For each branch of this tree
ΓR(S) →π0 G1 →π1 G2 → . . . →πn−1 Gn = F ∗ Γ ∗ H1 ∗ . . . ∗ Hk ,

(6)

there is a strict fundamental sequence assigned. Here
1) H1 , . . . , Hk are freely indecomposable groups isomorphic to subgroups of
Γ,
2) πi , 0 < i < n − 1 are fixed proper epimorphisms, πn−1 may not be proper.

16

3) The homomorphisms in this sequence are compositions π0 σ1 π1 . . . σn−1 πn−1 τ ,
where σi is a canonical automorphism of Gi corresponding to a Grushko decomposition of Gi followed by the JSJ decompositions of the freely indecomposable
factors,
4) τ is a homomorphism that maps each Hi monomorphically onto a conjugate of a fixed subgroup of Γ (and for each Hi it is a fixed monomorphism
followed by a conjugation) and maps F into Γ.
The existence of such a diagram can be obtained from [27] and [14]. Indeed, the difference between the diagram that we described and the diagram
constructed in [27] is that in [27] the homomorphism πn−1 must be proper and
homomorphism τ can be an arbitrary embedding of groups H1 , . . . , Hk into Γ.
In our diagram, if Hi has a non-trivial abelian splitting, then Hi appears as a
factor in the Grushko decomposition of Gn−1 , and in the leaves of the diagram
we have a fixed (up to conjugacy) monomorphism of Hi into a conjugate of Γ.
Notice that (non-canonical) fundamental sequences from Proposition 5 terminate with fixed conjugacy classes of monomorphisms of Kt into Γ, and we are
going to use this fact to prove that canonical fundamental sequences satisfy the
same property. Notice also that by [10], Lemma 7.2, Hi has infinitely many
conjugacy classes of monomorphisms into Γ if and only if Hi has a non-trivial
cyclic splitting. We define two embeddings of Hi into Γ to be equivalent if one is
obtained from the other by pre-composing with an automorphism of Hi generated by Dehn twists corresponding to cyclic splittings of Hi and post-composing
with a conjugation.
We claim that there is only a finite number of non-equivalent embeddings of
each H = Hi that appear in the diagram, into Γ. We will follow [10]. Suppose to
the contrary, that there is an infinite family of non-equivalent monomorphisms.
Let {hi } be a fixed system of generators of H. Consider a sequence (αj : H → Γ)
of non-equivalent minimal monomorphisms (corresponding to minimal in the
equivalence class sum of lengths of the images of {hi }). After passing to a
subsequence, the sequence can be taken to be stable, it converges to a stable
isometric action of H on a real tree. Since H = H/Ker→ (αj ), one can use Rips
machine and the shortening argument to show that H has an essential cyclic
splitting such that some of the monomorphisms in the sequence can be shorten
by pre-composing with Dehn’s twists corresponding to this splitting. Since the
sequence consists of minimal monomorphisms, we have a contradiction with the
assumption about infinite number of equivalence classes.
Construction of the NTQ group for a strict fundamental sequence.
We can assume (combining foldings and slidings) that all JSJ decompositions
have the property that each vertex with non-cyclic abelian vertex group that is
connected to a rigid subgroup is connected to only one rigid subgroup.
We assign an NTQ system to this branch as follows. First, replace each
subgroup Hi that is not a hyperbolic closed surface group by its quasi-convex
closure Γi , then Gn is replaced by Ĝn = F ∗ Γ ∗ Γ1 ∗ . . . ∗ Γk , Gn ≤ Ĝn . Notice
that Ĝn is a hyperbolic group. Let Dn−1 be an abelian JSJ decomposition of
Gn−1 (we mean the decomposition into a free product of freely indecomposable
factors followed by the JSJ decompositions of the factors). We order the edges
17

e1 , . . . ek between rigid subgroups. We extend the centralizer of the image of
(1)
the edge group of e1 in Ĝn by a new letter, and obtain a new group Ĝn , then
iteratively for each i ≤ k we extend by a new letter the centralizer of the image
(i−1)
of the edge group of ei in Ĝn
(see [17] for precise description).
Then the fundamental group of the subgraph of groups generated by the
rigid subgroups in Dn−1 will be embedded into this iterated centralizer exten(k)
sion G̃n = Ĝn of Ĝn . We also attach abelian vertex groups of Dn−1 to G̃n
the following way. Consider edges (with maximal cyclic edge groups) that connect non-cyclic abelian vertex groups in Dn−1 to a non-abelian non-QH vertex
group. Some of the centralizers of the images of the edge groups may become
conjugate in G̃n . We join all edges with conjugate centralizers of the images
of the edge groups into an equivalence class. For each equivalence class we do
the following. Denote the edges in the class by ē1 , . . . , ēs . Let m be the sum of
the ranks of abelian vertex groups connected to ē1 , . . . , ēs . We extend only the
centralizer of the image of the edge group corresponding to ē1 by new m − s
commuting letters (free rank m − s extension ...
of a centralizer defined in the
introduction). Denote the obtained group by Gn . We attach QH subgroups
of Dn−1 identifying boundary components with their images in Ḡn , and obtain
the new group Gn−1 such that Gn−1 is embedded into Gn−1 . Notice that since
Gn−1 is a Γ-limit group, edge groups corresponding to edges adjacent to QH
subgroups are maximal
cyclic in QH subgroups.
...
The group Gn is a Γ-limit group as the iterated extension of centralizers
of the Γ-limit group Ĝn . The group Gn−1 is a Γ-limit group because
... it is a
fundamental group of a family of regular quadratic equations over Gn . The
group Gn−1 is an NTQ group by definition. It is also toral relatively hyperbolic
by Dahmani’s Combination Theorem 0.1, items (1) and (2) [5].
We denote Ĝn by Nn and Gn−1 by Nn−1 , then Gn−1 ≤ Nn−1 .
Remark: Subgroups H1 , . . . Hk may appear on different levels of the fundamental sequence as free factors in the Grushko decomposition of groups Gi .
If Hs first time appears as a free factor of Gi (and not in Gi−1 ), then we
consider its JSJ decomposition as part of the decomposition of Gi but not of
Gi+1 , . . . , Gn−1 . So we will consider the restrictions of all the maps πi , . . . , πn−1
on Hs as identical isomorphisms, and we will be extending centralizers of images
of the edge groups of Hs in Γs only on level i.
Suppose we have already constructed the group Ni . We will show now how
to construct Ni−1 . Let Di−1 be an abelian JSJ decomposition of Gi−1 (we mean
the decomposition into a free product of freely indecomposable factors followed
by the JSJ decompositions of the factors). For each freely indecomposable
factor of Gi−1 that is not a closed surface group and not a free abelian group
we perform the construction in parallel and then take the free product of the
constructed groups and all the factors that are closed surface groups and free
abelian groups.
To simplify notation we now suppose that Gi−1 is freely indecomposable and
D̄i−1 is its abelian JSJ decomposition. We order the edges e1 , . . . ek between
rigid subgroups in D̄i−1 . We freely extend the centralizer of the image of the

18

edge group of e1 in Ni by a new letter, and obtain a new group Ni (1) , then
iteratively for each j ≤ k we freely extend by a new letter the centralizer of the
image of the edge group of ei in the previously constructed group Ni (j−1) .
Then the fundamental group of the subgraph of groups generated by the
envelopes of rigid subgroups in D̄i−1 will be embedded into this iterated centralizer extension Ñi = Ni (k) of Ni . We also attach abelian vertex groups of
D̄i−1 to Ñi the following way. Consider edges that connect non-cyclic abelian
vertex groups in D̄n−1 to non-abelian non-QH vertex groups. Some centralizers of the images of the edge groups may become conjugate to centralizers of
some other edge groups in Ñi . We put two edges into the same equivalence
class if some conjugates of the images of their edge groups in Ñi commute. For
each equivalence class we do the following. Denote the edges in the class by
ē1 , . . . , ēs . Let m be the sum of the ranks of abelian vertex groups connected to
ē1 , . . . , ēs , and p the sum of the ranks of their direct summands containing finite
index subgroups generated by edge groups. We extend only the centralizer of
the image in Ñi of the edge group corresponding
to ē1 by new m − p commuting
...
letters.
Denote
the
obtained
group
by
.
We
attach
QH subgroups of D̄n−1 to
N
i
...
identifying boundary components with their images in Ñi that is a subgroup
N i ...
of N i , and obtain the new toral relatively hyperbolic NTQ Γ-limit group Ni−1
such that Gi−1 is embedded into Ni−1 .
We construct iteratively the group N = N1 , which is NTQ, and, therefore,
a Γ-limit group, toral relatively hyperbolic and contains G1 as a subgroup.
The set of all NTQ groups corresponding to a canonical Hom-diagram is a
complete set of canonical NTQ groups. We often also consider a complete set of
canonical Γ-NTQ groups, when the bottom level is a free product of F , Γ and
several conjugates of freely indecomposable factors in the Grushko decomposition of Γ by new generators. Namely, in the beginning of the construction of the
canonical NTQ group we can take this free product istead of F ∗ Γ ∗ Γ1 ∗ . . . ∗ Γk ,
and then apply the construction.
Definition 10. The group of canonical automorphisms of the NTQ group Ni
(i = 1, . . . , n − 1) is the group of canonical automorphisms with respect to the
Grushko decomposition of Ni followed by the abelian splitting such that MQH
subgroups correspond to MQH subgroups of Gi abelian vertex groups correspond
to the abelian vertex groups of Ni and non-QH non-abelian vertex groups are
freely indecomposable factors in the Grushko decomposition of the group Ni+1 .
For each fundamental sequence (6) of the canonical Hom-diagram we assign
the following fundamental sequence of the completed canonical Hom-diagram
ΓR(S) →π0 N1 →π̄1 N2 → . . . →π̄n−1 Nn = F ∗ Γ ∗ Γ1 ∗ . . . ∗ Γk ,

(7)

1) π̄i , 0 < i ≤ n − 1 is a retraction on Ni+1 ,
2) The homomorphisms in this completed fundamental sequence are compositions π0 σ̄1 π̄1 . . . σ̄n−1 π̄n−1 τ, where σ̄i is a canonical automorphism of Ni ,
3) τ is a homomorphism that maps each Γi monomorphically onto a conjugate of a fixed subgroup of Γ (and for each Γi it is a fixed monomorphism
followed by a conjugation) and maps F into Γ.
19

All Γ-homomorphisms from ΓR(S) to Γ that factor through the fundamental
sequence (6) naturally factor through (7).
The set of all NTQ groups corresponding to a canonical Hom-diagram is
a complete set of canonical NTQ groups. We often also consider a complete
set of canonical Γ-NTQ groups, when the bottom level is a free product of F
and several conjugates of Γ by new generators. Namely, in the beginning of the
construction of the canonical NTQ group we can take this free product istead
of F ∗ Γ ∗ Γ1 ∗ . . . ∗ Γk , and then apply the construction.
Remark 1. When considering fundamental sequences for NTQ groups (not
necessary canonical NTQ groups) we only consider fundamental sequences such
that canonical epimorphisms between the levels are retractions onto the lower
level. They will be necessarily strict.
An algorithm is given in the next section, which constructs a complete set of
canonical Γ-NTQ groups (and systems) for ΓR(S) and the corresponding canonical Hom-diagram proving Theorem 2.

5.6

Implicit function theorem, formal solutions and generic
families

Let S(X, A) = 1 be a system of equations with a solution in a group G. We
say that a system of equations T (X, Y, A) = 1 is compatible with S(X, A) = 1
over G, if for every solution U of S(X, A) = 1 in G, the equation T (U, Y, A) = 1
also has a solution in G. More generally, a formula Φ(X, Y ) is compatible with
S(X, A) = 1 over G, if for every solution ā of S(X, A) = 1 in G there exists a
tuple b̄ over G such that the formula Φ(ā, b̄) is true in G.
Suppose now that a formula Φ(X, Y, A) is compatible with S(X, A) = 1 over
G. We say that Φ(X, Y, A) admits a lift into a group L such that ΓR(S) ≤ L, if
the formula ∃Y Φ(X, Y, A) is true in L (here Y are variables and X are constants
from GR(S) ). We say that the lift ( is effective if there is an algorithm to
decide for any formula T (X, Y, A) = 1 ∧ W (X, Y, A) 6= 1 whether the formula
T (X, Y, A) = 1 ∧ W (X, Y, A) 6= 1) admits a-lift into L, and if it does, to
construct a solution in L.
Let N be an NTQ group. Corrective extensions of N are obtained by:
(i) Replacing each of the terminal factors Hi by a freely indecomposable
quasi-convex subgroup Γi of Γ, where Hi ≤ Γi and the fixed monomorphism
from Hi to the conjugate of Γ is extended to the fixed monomorphism from Γi
to this conjugate of Γ.
(ii) Replacing each of the free abelian groups that appear in the Grushko
decompositions on different levels of the NTQ group by a free abelian group of
the same rank, that contains the original one as a subgroup of finite index.
Replacing each of the free abelian vertex groups that appear in the abelian
decompositions of freely indecomposable factors on different levels of the NTQ
group by a free abelian group of the same rank, that contains the original one
as a subgroup of finite index.

20

(iii) Embedding the obtained group into the commutative transitive group
using the procedure similar to the construction of the NTQ group for a strict
fundamental sequence in Section 5.5. We do have a completed strict fundamental sequence corresponding to the NTQ system S(X, A) = 1 here, but since the
subgroups at the base level were extended, we have to complete it again because
centralizers of some abelian vertex groups that were not conjugate, may become
conjugate.
We define the abelian size of N , denoted ab(N ), as the sum of the ranks of
the abelian vertex groups in decompositions corresponding to different levels of
N minus the sum of the ranks of their direct summands containing edge groups
as subgroups of finite index. Then ab(N ) is the same as ab(Ncorr ) for each
corrective extension (Ncorr ) of N .
Theorem 3. (Implicit Function Theorem) Let S(X, A) = 1 be an NTQ system over a non-elementary torsion free hyperbolic group Γ. Suppose a formula
T (X, Y, A) = 1 ∧ W (X, Y, A) 6= 1 is compatible with S(X, Y ) = 1. Then this
formula admits a lift into a family of N T Q groups N1 , . . . , Nk that are corrective extensions of ΓR(S) , and toral relatively hyperbolic. Every solution from
the fundamental sequence of solutions of S(X, Y ) = 1 (see Remark 1) factors
through the fundamental sequence for the NTQ system corresponding to one of
the corrective extensions.
This theorem is similar to the Parametrization Theorem, also called the
Implicit function theorem ([16],Theorem 12) for free groups. A similar result is
also formulated in [27], Theorem 2.3 for hyperbolic groups, but the formulation
in [27] contains an error (see [19] for comments).
We now decribe the construction of particular families of solutions, called
generic families, of an NTQ system which imply nice lifting properties over
that system. Consider a fundamental sequence with corresponding NTQ system
S(X, A) = 1 of depth N . We construct generic families iteratively for each level
k of the system, starting at k = N and decreasing k. There is an abelian
(k)
(k)
decomposition of Gk corresponding to the NTQ structure. Let V1 , . . . , VMk
be the vertex groups of this decomposition given some arbitrary order. We
construct a generic family for level k, denoted Ψ(k), by constructing generic
families for each vertex group in order. We denote a generic family for the
(k)
(k)
vertex group Vi by Ψ(Vi ). If there are no vertex groups, in other words the
equation Sk = 1 is empty (Gk = Gk+1 ∗ F (Xk )) we take Ψ(k) to be a sequence
of growing different Merzljakov’s words (defined in [16], Section 4.4). If the base
group G is a free product F (Xk ) ∗ Γ ∗ H1 ∗ . . . ∗ Hs , where H1 , ∗ . . . ∗ Hs are
conjugates of subgroups of the torsion free hyperbolic group Γ, and there are
fixed embedding µi : Hi → Γ, then the Ψ(k) restricted to each Hi consists is
µi (Hi ) conjugated by a family of growing Merzliakov’s words.
Remark 2. When using generic families in this paper, by [27], Proposition 2.1,
instead of a family of growing Merzliakov’s words in Γ, one can just take µi (Hi )
conjugated by a new letter, as well as one can take new letters for the basis of

21

F (Xk ). So instead of a family of homomorphisms in G or Γ, we can consider
generic family as a family of solutions into G ∗ F or Γ ∗ F .
(k)

If Vr is an abelian group then it corresponds to equations of the form
[xi , xj ] = 1 or [xi , u] = 1, 1 ≤ i, j ≤ s, where u ∈ U runs through a generating
set of a centralizer in Gk+1 . A solution σ in Gk+1 to equations of these forms
is called B-large if there is some b1 , . . . , bs with each bi > B such that σ(xi ) =
(σ(x1 ))b1 ...bi or σ(xi ) = ub1 ...bi , for 1 ≤ i ≤ s (possibly renaming x1 ). A generic
(k)
(k)
family of solutions for an abelian subgroup Vr is a family Ψ(Vr ) such that
for each Bi in any increasing sequence of positive integers {Bi }∞
i=1 there is a
(k)
solution in Ψ(Vr ) which is Bi -large.
(k)
If Vr is a QH vertex group of this decomposition, let S be the surface associ(k)
ated to Vr . We associate two collections of non-homotopic, non-boundary parallel, simple closed curves {b1 , . . . bq } and {d1 , . . . dt }. These collections should
have the property that S − {b1 ∪ · · · ∪ bq } is a disjoint union of three-punctures
spheres and one-punctured Mobius bands, each of the curves di intersects at least
one of the curves bj non-trivially, and their union fills the surface S (meaning
the collection {b1 , . . . bq , d1 , . . . , dt } have minimal number of intersections and
S − {b1 , ∪ · · · ∪ bq ∪ d1 ∪ · · · ∪ dt } is a union of topological disks).
(k)
Let β1 , . . . , βq be automorphisms of Vr that correspond to Dehn twists
(k)
along b1 , . . . bq , and δ1 , . . . , δt be automorphisms of Vr that correspond to
Dehn twists along d1 , . . . dt . We define iteratively a basic sequence of automorphisms {γL,n , φL,n } (compare with Section 7.1 of [16] where one particular
basic sequence of automorphisms is used), which is determined by a sequence
of t + q-tuples L = {(p1,n , . . . , pt,n , m1,n , . . . , mq,n )}∞
n=1
Let
φL,0 = 1
m1,n

γL,n = φL,n−1 δ1
p

. . . δqmq,n , n ≥ 1
p

φL,n = γL,n β1 1,n . . . βt t,n , n ≥ 1
(k)

Assuming generic families have already been constructed for Vi , i < r, and
for every vertex group in levels k ′ > k, and that Θk is a family of growing powers
(k′ )
of Dehn twists for edges on level k, set Ψ(k ′ ) = Ψ(VMk′ )Θk′ for k < k ′ ≤ N
(in other words the generic family for level k ′ is the generic family of the last
vertex group at that level) and set Ψ(N + 1) = {1}. Let πk : Gk → Gk+1 be the
(k)
(k)
canonical epimorphism. Let Σr = {ψ1 · · · ψr−1 |ψi ∈ Ψ(Vi )} be the collection
of all compositions of generic solutions for previous vertex groups. We then say
that
∞
Ψ(Vr(k) ) = {µL,n,λn = φL,n δ1λn . . . δqλn σn πk τ |σn ∈ Σ(k)
r , τ ∈ Ψ(k + 1)}n=1
(k)

where each λn is some positive integer, is a generic family for Vr if it has
→
−
the following property: Given any n and any tuple of positive numbers A =
22

(A1 , . . . , Ant+nq+1 ) with Ai < Aj for i < j, Ψ contains a homomorphism µn,L,λn
such that the tuple
−
→
L n,rn = (p1,1 , . . . , pt,1 , m1,2 , . . . , mq,2 , . . . , m1,n , . . . , mq,n , p1,n , . . . , pt,n , λn )
= (L1 , . . . , Lnt+nq+1 )
→
−
grows faster than A in the sense that L1 ≥ A1 and Li+1 − Li ≥ Ai+1 − Ai .
(1)
Finally we set Ψ(S) = Ψ(VM1 ) to be a generic family of solutions for the
G-NTQ system S(X, A) = 1. Notice that Ψ(S) Γ-discriminates ΓR(S) .
The following is a technical lemma that is used to prove Theorem 3.
Lemma 2. If Ψ(W ) is a generic family of solutions for a regular NTQ system W (X, A) = 1, then for any formula Φ(X, Y, A) = U (X, Y, A) = 1 ∧
W (X, Y, A) 6= 1 the following is true: if for any solution ψ ∈ Ψ(W ) there exists
a solution of Φ(X ψ , Y, A) = 1, then Φ admits a lift into ΓR(W ) . If the NTQsystem W (X, A) = 1 is not regular, then for any such formula Φ(X, Y, A) = 1
the following is true: if for any solution ψ ∈ Ψ(W ) there exists a solution of
Φ(X ψ , Y, A) = 1, then Φ admits a lift into a family of corrective extensions
of ΓR(W ) . There is a finite number of these extensions, and any solution of
W (X, A) = 1 factors through one of them.
Example 1. Consider the equation [x, y] = [a, b] over a torsion-free hyperbolic
group Γ. Define the following Γ-automorphisms of Γ[X] = Γ ∗ F (X):
β : x → x, y → xy
δ : x → yx, y → y
Notice that big powers of these automorphisms produce big powers of elements.
Let n = 2a for some positive integer a, and define:
φp,n = δ m1 β p1 · · · δ ma β pa
where p = (p1 , m1 . . . , pa , ma ). Now take the solution τ of [x, y] = [a, b] with
τ (x) = a, τ (y) = b and consider the family of mappings
Ψ = {µp,n = φp,n τ, p ∈ Pn }∞
n=1
where for each n, Pn is an infinite set of n-tuples of large natural numbers.
Then Ψ is a generic family of solutions in Γ for [x, y] = [a, b].
Finally, if H is maximal Γ-limit quotient of ΓR(S) (there is no other Γ-limit
quotient H1 such that the map sending images of generators of ΓR(S) in H1 into
their images in H can be extended to a proper homomorphism), then since a
discriminating family of homomorphisms for H factors through some branch b
of T (S, Γ), there is some φb : ΓR(S) → Nb with φb (ΓR(S) ) = H.
Each maximal Γ-limit quotient is isomorphic to ΓR(S1 ) , with S1 = 1 an
irreducible system, so there is a (canonical) fundamental sequence, with automorphisms on the top level corresponding to a JSJ decomposition of ΓR(S1 ) ,
23

which factors through a Γ-NTQ groups N (as in Section 7 of [17]). This gives
the canonical embeddings of each Γ-limit group L into some Γ-NTQ group, as
mentioned in the introduction. We then define a generic family of homomorphisms for such a Γ-limit group ΓR(S1 ) to be a generic family for a Γ-NTQ group
N into which it embeds canonically in this manner.
The following is a simple but useful observation.
Lemma 3. Let S(Z, A) = 1 be a finite system of equations over Γ. Let H be
the image of the group ΓR(S) in a Γ-NTQ group N corresponding to a strict
fundamental sequence in T (S, Γ). Then a generic family of Γ-homomorphisms
from H to Γ corresponding to the JSJ decompositions of H and its images on
all levels, factors through one of the branches of T (S, Γ).
Proof. By construction of the solution tree for S(Z, A) = 1, there is some generic
family of solutions for H. For this family, at each level of the solution tree, since
there is finitely many branchings, some family factoring through at least one
must be a generic family as well.

6

Constructing a complete set of (corrective extensions of ) canonical Γ-NTQ groups

The proof of Theorem 2 is based on the observation that branches of the tree
T (S, Γ) which contain generic families of homomorphisms for maximal Γ-limit
quotients of ΓR(S) , correspond to (almost) canonical NTQ systems.

6.1

Sol-maximal Γ-limit quotients

We define a partial order on the set of Γ-limit groups {Hbi = φbi (ΓR(S) ) ≤ Nbi }
over all branches bi of T (S, Γ), with Nbi the Γ-NTQ group corresponding to b,
as in Section 5.3. It’s often notationally convenient to denote Hbi , Nbi , φbi by
Hi , Ni , φi . For given elements H1 , H2 we say that H2 ≤Sol H1 if for every homomorphism ψ2 : H2 → Γ that factors through N2 there exists a homomorphism
ψ1 : H1 → Γ that factors through N1 such that φ1 ψ1 = φ2 ψ2 . In this case the
canonical map φ2 : ΓR(S) → H2 can be split as τ φ1 , where φ1 is the canonical
homomorphism φ1 : ΓR(S) → H1 and τ is a Γ-epimorphism from H1 to H2 .
Proposition 6. There is an algorithm to find all homomorphisms φb : ΓR(S) →
Nb , where Nb is a Γ-NTQ group corresponding to a strict fundamental sequence
in T (S, Γ) for a maximal Γ-limit quotient H of ΓR(S) such that H = φb (ΓR(S) ).
Proof. Let {ℓ1 , . . . , ℓn } generate ΓR(S) , and for each branch b in T (S, Γ), let
Hb = φb (ΓR(S) ) be the images of the homomorphisms into the corresponding
Γ-NTQ groups. We proceed by considering the finite collection {Hb }, and the
finite collection of pairs {(Hi , Hj )}.
First we describe an algorithm which tests a pair (H1 , H2 ) if H2 ≤Sol H1 .
Let N1 (X, A) = 1, X = {x1 , . . . , xr }, and N2 (Y, A) = 1, Y = {y1 , . . . , ys }, be
24

Γ-NTQ systems such that N1 = ΓR(N1 ) and N2 = ΓR(N2 ) . There are words
φ1 (ℓi ) = υi (X, A) ∈ ΓR(N1 ) and φ2 (ℓi ) = µi (Y, A) ∈ ΓR(N2 ) for 1 ≤ i ≤ n.
Then the following first order formula is true in Γ, if and only if H2 ≤Sol H1 :
∀h1 , . . . , hs ∃g1 , . . . , gr (N2 (h1 , . . . , hs , A) = 1 → (N1 (g1 , . . . , gr , A) = 1
∧υ1 (g1 , . . . , gr , A) = µ1 (h1 , . . . , hs , A)∧. . .∧υs (g1 , . . . , gr , A) = µs (h1 , . . . , hs , A))).

In other words, for each Γ-homomorphism α : ΓR(N2 ) → Γ there is a Γhomomorphism β : ΓR(N1 ) → Γ such that βH1 = τ αH2 (here α and β are
restricted to H2 and H1 .
Denote the above formula in Γ, as constructed from the pair H1 , H2 , by
Ψ(H1 , H2 ). We now describe an algorithm to test if Ψ(H1 , H2 ) is true. Every
conjunction of equations is equivalent to some single equation, so let SΨ =
SΨ (h1 , . . . , hs , g1 , . . . , gr ) = 1 be an equation equivalent to
N1 (g1 , . . . , gr , A) = 1 ∧ υ1 (g1 , . . . , gr , A) = µ1 (h1 , . . . , hs , A) ∧ . . . ∧
υs (g1 , . . . , gr , A) = µs (h1 , . . . , hs , A).
By Theorem 3, Ψ(H1 , H2 ) is true in Γ if and only if the corresponding
equation SΨ (with h1 , . . . , hs considered as coefficients in N2∗ ) has a solution in
each N2∗ , where N2∗ belongs to the (canonical) set of corrective extensions of N2 .
To obtain each corrective extension, for some abelian vertex groups Ai of N2 ,
abelian groups Ai with Ai ≤f.i Ai are constructed exactly by adding particular
roots to each Ai . Notice, that since N1 , N2 are Γ-NTQ groups, the free products
at their bases are free products of Γ ∗ F and some conjugates of factors in the
Grushko decomposition of Γ, therefore a corrective extension does not extend the
base group. However, Theorem 3 does not directly imply what those particular
roots are. To find which roots to add, and construct the corrective extensions
and check them for solutions, we use Dahmani’s construction ([6]) of ’canonical
representatives’ for elements in N2 (since it is toral relatively hyperbolic with
parabolic subgroups given by the abelian vertex groups A1 , . . . , Ak of the NTQ
structure) in the free product F ∗ A1 ∗ · · · ∗ Ak (Theorem 4.4 in [6]). These
(N )
(1)
canonical representatives give a disjunction of equations SΨ ∨ · · · ∨ SΨ , which
can
is equivalent to a single equation SΨ , over F ∗ A1 ∗ · · · ∗ Ak .
can
Solutions for SΨ exist in N2 if and only if solutions for SΨ
exist in F ∗ A1 ∗
∗
· · · ∗ Ak . Canonical representives also exist for N2 (toral relatively hyperbolic
as well), and using those, the equation SΩ over N2∗ (with h1 , . . . , hs considcan
ered as coefficients in N2∗ ) induces the same equation SΩ
over a free product
F ∗ A1 ∗ · · · ∗ Ak with the same roots added to the same abelian subgroups.
This is because Dahmani’s construction of canonical representatives, applied to
equivalent systems of triangular equations, give new equations corresponding to
the “middles” of the triangles which, if the middles are “short” (as in hyperbolic
case), are determined by SΩ , and if the middles belong to parabolic subgroups,
are just commuting equations. So similarly, solutions for SΩ exist in N2∗ if and
can
only if solutions for SΨ
exist in F ∗ A1 ∗ · · · ∗ Ak . It is these free product extensions which can be found and checked algorithmically, since solving equations in
25

F ∗A1 ∗· · ·∗Ak is just solving equations in each factor, and in the abelian factors,
conventional linear algebraic methods of finding solutions determine the finite
index extensions (by giving which roots of elements are needed for solutions).
Then checking for a solution in F ∗ A1 ∗ · · · ∗ Ak is just checking in F , which
can be done algorithmically by [21].
If H2 ≤Sol H1 we remove H2 , N2 and the corresponding branch from T (S, Γ).
We now show that every non-Sol-maximal Γ-limit quotient is removed. If H1 is
not a Sol-maximal Γ-limit quotient, then there exists a Γ-NTQ group N3 such
that H1 ≤Sol H3 and Ψ(H3 , H1 ). So H1 is then removed from the collection
{Hb }, and the proposition is proved.
Recall that the Grushko decomposition of a finitely generated group G is the
free product decomposition G = Fr ∗A1 ∗· · · Ak , where Fr is a free group of finite
rank, and each Ai is non-trivial, freely indecomposable, and not infinite cyclic
(see [12]). This decomposition is unique up to permutation of the conjugacy
classes of the Ai in G.
Proposition 7. Given a finite system of equations S(Z, A) = 1 over Γ, there
is an algorithm which finds the Grushko decomposition of each such maximal
Γ-limit quotient H.
Proof. We show how to construct a free decomposition of the image H of φb :
ΓR(S) → Nb , for each strict fundamental sequence Φb . If H is a free product
then there is a solution of the system S(Z, A) = 1 in Γ ∗ Γ. Therefore we
can solve the corresponding systems induced by canonical representatives of
elements from Γ ∗ Γ in the group F (A) ∗ F (A). Then we will see the free product
decomposition of the corresponding NTQ group over Γ ∗ Γ (since generators of
each copy of Γ do not interact in the NTQ structure). The same NTQ group
can be considered as an NTQ group over Γ if instead of the second copy of Γ
we take Γ conjugated by a new element. Since H is a maximal Γ-limit quotient,
the NTQ group corresponding to H must be freely decomposable, and we will
obtain the induced free product decomposition of H (given by generators in the
free factors of the NTQ group).

6.2

Corrective extensions of canonical Γ-NTQ groups

Proposition 8. Suppose a branch b of the tree T (S, Γ) contains a generic family of homomorphisms such that the automorphisms for QH subgroups are constructed in [16], Sections 7.1,7.2, for a canonical Γ-NTQ group N of a Solmaximal Γ-limit quotient H of ΓR(S) . Then the NTQ group Nb corresponding
to the branch b is a free product of Γ-NTQ groups such that one of these Γ-NTQ
groups M is a corrective extension of N .
Proof. Since we know how to obtain a free decomposition of H, we can suppose
now that H is freely indecomposable.
By Theorem 3, every solution of M in Γ can be obtained from a formula
solution of M in a corrective extension Ncorr of N (which is a retract on N )
26

composed with a solution of Ncorr ,. All solutions of M in Ncorr should be
contained in a finite number of fundamental sequences over Ncorr .
Let M = M1 > M2 > . . . > Mn be a sequence of Γ-NTQ groups corresponding to different levels of M . The graph of groups decomposition ∆1 corresponding to the top level may contain QH subgroups, abelian vertex groups and a
free product of non-QH non-abelian vertex groups which is M2 .
Lemma 4. M does not have an abelian splitting where N and non-QH nonabelian vertex groups of ∆1 are elliptic.
Proof. All splittings of M are obtained from the Elimination process (which is
a generalization of Makanin’s process) for one of the generalized equations for
canonical representatives. We denote by K the NTQ group constructed as a
result of the Elimination process, such that M was re-worked from K. Then
M cannot have a splitting containing a QH subgroup such that N is conjugate
in the graph of groups corresponding to other vertex groups. Indeed, the QH
subgroup has a pre-image QH subgroup in K and, therefore, big powers of Dehn
twists corresponding to the generic family constructed in [16] are, actually, seen
as big powers in canonical representatives, since they are (λ, µ)-quasi-geodesics.
Hence there must be the induced splittings of H and, therefore, of N . Moreover,
only some subwords of length bounded by µ of canonical representatives can
become trivial in Γ, canonical representatives cannot contain unbounded powers
of words that become trivial in Γ. Therefore there are no edges connected to
QH subgroups in K that are mapped to the identity in the reworking process
from K to M . Similarly, M cannot be a free extension of a centralizer of a
group containing N because in solutions the new letters can be mapped into big
powers that are much larger than the powers of the image of the corresponding
centralizer in N . This, again will be seen in canonical representatives.
We recall a lemma from [15].
Lemma 5. (Lemma 2.13 in [15]) If Q is a QH-subgroup of G and H ≤ G,
and not conjugate into the fundamental group of the graph of groups obtained
by removing Q, then either H ∩ Q has finite index in Q and is a QH subgroup
of H or H is a non-trivial free product.
Therefore for each MQH subgroup Q of M , the intersection N ∩ Q is a finite
index subgroup of Q, and there is a retract from Q to N ∩ Q. This implies that
Q = N ∩ Q. Therefore MQH subgroups of N and M coincide.
On the second level, N and M may be freely decomposable, but will have
the same number of free factors because their MQH subgroups are the same.
Moreover, since the generalized equation for K was constructed from solutions
corresponding to the generic family for N , the generalized equation corresponding to the second level of K can be transformed by a finite number of elementary
transformations into a generalized equation on a disjoint family of intervals, each
corresponding to a free factor. Going inductively from the top to the bottom we
compare all levels of N and M . Their QH subgroups on all the levels are the
same. If ∆i is the abelian decomposition of a freely indecomposable factor P of
27

Mi on level i, then there is no abelian decomposition of P such that the corresponding freely indecomposable factor of Ni and non-QH nonabelian subgroups
of Mi are elliptic. For each Mi there is a retraction from Mi onto Ni .
Notice, that since N is a Γ-NTQ group, the groups Γj that are conjugates of
freely indecomposable factors in the Grushko decomposition of Γ at the bottom
level of N are not extended in M , and the free products at the bottom of N
and M are the same. This proves the proposition.
Recall that every Sol-maximal Γ-limit quotient H of ΓR(S) is isomorphic to
the image of at least one homomorphisms φb : ΓR(S) → Nb , corresponding to a
strict fundamental sequence in T (S, Γ), with notation as in Section 5.6. Moreover, in this case a generic family of solutions for a canonical Γ-NTQ group N of
this Sol-maximal Γ-limit quotient H factors through Nb . But then a generic family of homomorphisms such that the automorphisms for QH subgroups are constructed in [16], Sections 7.1,7.2 also factors through Nb . Therefore by Proposition 8 we constructed corrective extensions for all canonical Γ-NTQ groups
for all Sol-maximal Γ-limit quotients of ΓR(S) . Moreover, by construction, all
solutions of S(X, A) = 1 that factor through canonical Γ-NTQ systems for Solmaximal Γ-limit quotients, factor through the algorithmically constructed their
corrective extensions.
Theorem 2 is proved.
Remark 3. We can also replace corrective extensions of Γ-NTQ groups (when
the bottom level is a free product of F , Γ and several conjugates of freely indecomposable factors in the Grushko decomposition of Γ by new generators) in
the formulation of Theorem 2 by corrective extensions of NTQ Γ-limit groups
(when the bottom level is a free product of F , Γ and several conjugates of freely
indecomposable quasi-convex subgroups of Γ).

References
[1] G. Baumslag, A. Myasnikov, and V. Remeslennikov, Algebraic geometry
over groups. I. Algebraic sets and ideal theory, J. Algebra 219 (1999), no. 1,
16–79. MR 1707663 (2000j:14003)
[2] M. Casals-Ruiz and I. Kazachkov, Limit groups over partially commutative
groups and group actions on real cubings, Geom. Topol. 19 (2015), no. 2,
725–852. MR 3336274
[3] C. Champetier and V. Guirardel, Limit groups as limits of free groups,
Israel J. Math. 146 (2005), 1–75. MR 2151593 (2006d:20045)
[4] D. Cohen, Combinatorial group theory: a topological approach, London
Mathematical Society Student Texts, vol. 14, Cambridge University Press,
Cambridge, 1989. MR 1020297 (91d:20001)
[5] F. Dahmani, Combination of convergence groups, Geom. Topol. 7 (2003),
933–963 (electronic). MR 2026551 (2005g:20063)
28

[6] F. Dahmani and D. Groves, The isomorphism problem for toral relatively
hyperbolic groups, Publ. Math. Inst. Hautes Études Sci. (2008), no. 107,
211–290. MR 2434694 (2009i:20081)
[7] M. Dunwoody and M. Sageev, Jsj-splittings for finitely presented groups
over slender groups, Invent. Math. 135 (1999), no. 1, 25–44. MR 1664694
(2000b:20050)
[8] K. Fujiwara and P. Papasoglu, JSJ-decompositions of finitely presented
groups and complexes of groups, Geom. Funct. Anal. 16 (2006), no. 1,
70–125. MR 2221253 (2007c:20100)
[9] R. Grigorchuk, Degrees of growth of finitely generated groups and the theory
of invariant means, Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), no. 5, 939–
985. MR 764305 (86h:20041)
[10] D. Groves and H. Wilton, Conjugacy classes of solutions to equations and
inequations over hyperbolic groups, J. Topol. 3 (2010), no. 2, 311–332. MR
2651362 (2012a:20067)
[11] D. Groves and H. Wilton, The structure of limit groups over hyperbolic
groups, ArXiv e-prints (2016).
[12] I. Gruschko, Über die Basen eines freien Produktes von Gruppen, Rec.
Math. [Mat. Sbornik] N.S. 8 (50) (1940), 169–182. MR 0003412 (2,215a)
[13] V. Guirardel and G. Levitt, JSJ decompositions: definitions, existence, uniqueness. I: The JSJ deformation space, e-print, arXiv:0911.3173
[math.GR] (2009).
[14] O. Kharlampovich and J. Macdonald, Effective embedding of residually hyperbolic groups into direct products of extensions of centralizers, J. Group
Theory 16 (2013), no. 5, 619–650. MR 3101004
[15] O. Kharlampovich and A. Myasnikov, Effective JSJ decompositions,
Groups, languages, algorithms, Contemp. Math., vol. 378, Amer. Math.
Soc., Providence, RI, 2005, pp. 87–212. MR 2159316 (2006m:20045)
[16]

, Implicit function theorem over free groups, J. Algebra 290 (2005),
no. 1, 1–203. MR 2154989 (2007b:20047)

[17]

, Elementary theory of free non-abelian groups, J. Algebra 302
(2006), no. 2, 451–552. MR 2293770 (2008e:20033)

[18]

, Limits of relatively hyperbolic groups and Lyndon’s completions, J.
Eur. Math. Soc. (JEMS) 14 (2012), no. 3, 659–680. MR 2911880

[19]

, Decidability of the Elementary Theory of a Torsion-Free Hyperbolic
Group, e-print, arXiv:1303.0760 [math.GR] (2013).

29

[20] L. Louder and N. Touikan, Strong accessibility for finitely presented groups,
e-print, arXiv:1302.5451 [math.GR] (2013).
[21] G. Makanin, Decidability of the universal and positive theories of a free
group, Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), no. 4, 735–749. MR
755956 (86c:03009)
[22] E. Rips and Z. Sela, Canonical representatives and equations in hyperbolic
groups, Invent. Math. 120 (1995), no. 3, 489–512. MR 1334482 (96c:20053)
[23]

, Cyclic splittings of finitely presented groups and the canonical JSJ
decomposition, Ann. of Math. (2) 146 (1997), no. 1, 53–109. MR 1469317
(98m:20044)

[24] Peter Scott and Terry Wall, Topological methods in group theory, Homological group theory (Proc. Sympos., Durham, 1977), London Math. Soc.
Lecture Note Ser., vol. 36, Cambridge Univ. Press, Cambridge-New York,
1979, pp. 137–203. MR 564422 (81m:57002)
[25] Z. Sela, Diophantine geometry over groups. II. Completions, closures
and formal solutions, Israel J. Math. 134 (2003), 173–254. MR 1972179
(2004g:20061)
[26]

, Diophantine geometry over groups. VI. The elementary theory of
a free group, Geom. Funct. Anal. 16 (2006), no. 3, 707–730. MR 2238945
(2007j:20063)

[27]

, Diophantine geometry over groups. VII. The elementary theory of
a hyperbolic group, Proc. Lond. Math. Soc. (3) 99 (2009), no. 1, 217–273.
MR 2520356 (2010k:20068)

30

