NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

arXiv:1309.7458v2 [math.GR] 12 Jan 2016

ILYA KAPOVICH AND RICHARD WEIDMANN

Abstract. We show that for every n ≥ 2 there exists a torsion-free one-ended
word-hyperbolic group G of rank n admitting generating n-tuples (a1 , . . . , an )
and (b1 , . . . , bn ) such that the (2n − 1)-tuples
(a1 , . . . , an , 1, . . . , 1 ) and (b1 , . . . , bn , 1, . . . , 1 )
| {z }
| {z }
n−1 times

n−1 times

are not Nielsen equivalent in G. The group G is produced via a probabilistic
construction.

Introduction
The notion of Nielsen equivalence goes back to the origins of geometric group
theory and the work of Jakob Nielsen in nineteen twenties [N1, N2]. If G is a group,
n ≥ 1 and τ = (g1 , . . . , gn ) is an n-tuple of elements of G, an elementary Nielsen
transformation on τ is one of the following three types of moves:
(1) For some i ∈ {1, . . . , n} replace gi in τ by gi−1 .
(2) For some i 6= j, i, j ∈ {1, . . . , n} interchange gi and gj in τ .
(3) For some i 6= j, i, j ∈ {1, . . . , n} replace gi by gi gj±1 in τ .
Two n-tuples τ = (g1 , . . . , gn ) and τ = (g10 , . . . , gn0 ) of elements of G are called
Nielsen equivalent, denoted τ ∼N E τ 0 , if there exists a finite chain of elementary
Nielsen transformations taking τ to τ 0 . Since elementary Nielsen transformations
are invertible it follows that Nielsen equivalence is an equivalence relation on the
set Gn of n-tuples of elements of G for every n ≥ 1.
Nielsen showed [N1, N2] that for the free group Fn := F (x1 , . . . , xn ) any generating n-tuple of Fn is Nielsen equivalent to the standard basis (x1 , . . . , xn ). This
fact implies, in particular, that the automorphism group of a finitely generated
free group is generated by so called “Nielsen automorphisms” that correspond to
the elementary equivalences discussed above. It follows that for any group G two
n-tuples τ = (g1 , . . . , gn ), τ 0 = (g10 , . . . , gn0 ) ∈ Gn are Nielsen equivalent in G if and
only if there exist ϕ ∈ Hom(Fn , G) and α ∈ Aut(Fn ) such that the following hold:
(1) gi = ϕ(xi ) for 1 ≤ i ≤ n.
(2) gi0 = ϕ ◦ α(xi ) for 1 ≤ i ≤ n.
Thus Nielsen equivalence classes of n-tuples in G correspond to orbits in Hom(Fn , G)
under the natural right action of Aut(Fn ). In the case of generating tuples these
are orbits in Epi(Fn , G) under the action of Aut(Fn ).
If hg1 , . . . , gn i = G then an arbitrary h ∈ G can be expressed as a product
of elements of {g1 , . . . , gn }±1 . Therefore the (n + 1)-tuples (g1 , . . . , gn , 1) and
(g1 , . . . , gn , h) are Nielsen-equivalent. For similar reasons, if k ≥ 1 and h1 , . . . , hk ∈
G are arbitrary, then (g1 , . . . , gn , 1, . . . , 1) ∼N E (g1 , . . . , gn , h1 , . . . , hk ). It follows
| {z }
k times

2000 Mathematics Subject Classification. Primary 20F65, Secondary 20F67, 57M07.
The first author was supported by he Collaboration Grant no. 279836 from the Simons Foundation, and by the National Science Foundation grant DMS-1405146.
1

2

ILYA KAPOVICH AND RICHARD WEIDMANN

that if (h1 , . . . , hn ) ∈ G is another generating tuple for G then
(g1 , . . . , gn , 1, . . . , 1) ∼N E (g1 , . . . , gn , h1 , . . . , hn ) ∼N E (h1 , . . . , hn , 1, . . . , 1)
| {z }
| {z }
n times

in G.

n times

Recall that for a finitely generated group G the rank of G, denoted rank(G), is
the smallest number of elements in a generating set of G. A generating n-tuple of
G is called minimal if n = rank(G).
The operation of transforming an n-tuple of elements of G into an (n + 1)tuple by appending the identity element as the (n + 1)-st entry is sometimes called
a stabilization move. As we observed above, any two generating n-tuples of a
group G become Nielsen equivalent after n stabilization moves. The main goal of
this paper is to show that there exist groups that have two generating n-tuples
that do not become Nielsen equivalent after n − 1 stabilizations. Evans previously
showed [E2, E3] that for any k there exists a metabelian group G and generating
n-tuples that do not become Nielsen equivalent after k stabilizations. However, in
these example n is much larger than k and the generating tuples are not minimal.
The main result of this paper is:
Theorem A. Let n ≥ 2 be an arbitrary integer. Then there exists a generic set R
of 2n-tuples
τ = (v1 , . . . , vn , u1 , . . . , un )
where for each τ ∈ R every vi is a freely reduced word in F (a1 , . . . , an ), every ui is
a freely reduced word in F (b1 , . . . , bn ), where |v1 | = · · · = |vn | = |u1 | = · · · = |un |
and such that for each τ = (v1 , . . . , vn , u1 , . . . , un ) ∈ R the following holds:
Let G be a group given by the presentation
(*)

G = ha1 , . . . , an , b1 , . . . , bn |ai = ui (b), bi = vi (a), for i = 1, . . . , ni.

Then G is a torsion-free one-ended word-hyperbolic group with rank(G) = n, and
the (2n − 1)-tuples (a1 , . . . , an , 1, . . . , 1 ) and (b1 , . . . , bn , 1, . . . , 1 ) are not Nielsen| {z }
| {z }
n−1 times

n−1 times

equivalent in G.
The precise meaning of R being generic is explained in Section 5. However, the
main point of Theorem A is to prove the existence of groups G with the above
properties. Genericity considerations are used as a tool for justifying existence
of tuples τ such that G given by presentation (*) satisfies the conclusion of Theorem A. In an earlier paper [KW3] we proved, using rather different arguments
from those deployed in the present article, a weaker related statement. Namely,
we proved that if G is given by presentation (*) corresponding to a generic tuple
τ = (v1 , . . . , vn , u1 , . . . , un ), then the (n+1)-tuples (a1 , . . . , an , 1) and (b1 , . . . , bn , 1)
are not Nielsen equivalent in G. In [KW3] we also conjectured that Theorem A
should hold.
It is in general quite difficult to distinguish Nielsen equivalence classes of tuples
of elements. Even in the algorithmically nice setting of torsion-free word-hyperbolic
groups the problem of deciding if two tuples are Nielsen equivalent is algorithmically
undecidable. Indeed, the subgroup membership problem is a special case of this
problem, as two tuples (g1 , . . . , gn , h) and (g1 , . . . , gn , 1) are Nielsen equivalent if and
only if h ∈ hg1 , . . . , gn i. Therefore Nielsen equivalence is not decidable for finitely
presented torsion-free small cancellation groups, since in general, by a result of
Rips [R], such groups have undecidable subgroup membership problem. Only in
the case of 2-tuples there is a test that works reasonably well for distinguishing
Nielsen equivalence: If two pairs (g1 , g2 ) and (h1 , h2 ) are Nielsen equivalent in a
group G, then, by a result of Nielsen [N1], the commutator [g1 , g2 ] is conjuate

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

3

to [h1 , h2 ] or two [h1 , h2 ]−1 . Thus having a solution to the conjugacy problem
often gives a way to distinguish Nielsen classes of pairs. This test is particularly
important in the theory of finite groups.
As noted above, there are no general methods that allow us to distinguish Nielsen
classes. However, Lustig and Moriah [LM1, LM2, LM3] and Evans [E1, E2, E3]
produced algebraic methods that work in many special situations. While the methods of Lustig and Moriah only work in the context of minimal generating tuples,
the methods of Evans also work for non-minimal and stabilized generating tuples;
see the discussion before the statement of Theorem A. The methods of Moriah and
Lustig are K-theoretic in nature. The approach of Evans generalizes some linear
algebra considerations in the context of solvable groups. Our approach, sketched
in the next section, is essentially geometric. Negatively curved features of groups
G, given by presentation (∗) in Theorem A, play a crucial role in the proof of this
theorem.
We are grateful to the two referees of this paper for useful suggestions.
1. Outline of the proof
In this section we outline the idea of the proof of Theorem A. First, we pass
from presentation (*) of G to the presentation
G = ha1 , . . . , an |U1 , . . . , Un i

(**)

where Ui is obtained by freely and cyclically reducing the word ui (v1 , . . . , vn )a−1
in
i
F (A), where A = {a1 , . . . , an }. Genericity of (*) implies that presentation (**) satisfies an arbitrarily strong small cancellation condition C 0 (λ), where λ ∈ (0, 1) is an
arbitrarily small fixed number. Suppose that the (2n−1)-tuples (a1 , . . . , an , 1, . . . , 1 )
| {z }
n−1 times

and (b1 , . . . , bn , 1, . . . , 1 ) are Nielsen-equivalent in G. Then in the free group F (A)
| {z }
n−1 times

the (2n − 1)-tuple (a1 , . . . , an , 1, . . . , 1 ) is Nielsen equivalent to a tuple of freely
| {z }
n−1 times

reduced F (A)-words (x1 , . . . , x2n−1 ) such that xi =G bi for i = 1, . . . , n. Among
all such tuples (x1 , . . . , x2n−1 ) we choose one of minimal complexity, in the appropriate sense. We then consider the labelled graph Γ given by a wedge of 2n − 1
loops labelled by the words x1 , . . . , x2n−1 . The fact that (a1 , . . . , an , 1, . . . , 1 ) ∼N E
| {z }
n−1 times

(x1 , . . . , x2n−1 ) in F (A) implies that the graph Γ admits a finite sequence of Stallings
folds taking it to the graph Rn which is the wedge of n loop-edges labelled a1 , . . . , an .
In this folding sequence we look at the last term ∆ such that ∆ does not contain
a copy of Rn as a subgraph. Then Γ folds onto ∆ and ∆ contains a subgraph Ψ
consisting of ≤ n + 2 edges such that Ψ transforms into a graph containing Rn
by a single fold. By construction, the first Betti number of ∆ is ≤ 2n − 1, which
puts combinatorial constrains on the topology of ∆ which we later exploit. The
F (A)-words x1 , . . . xn are readable in Γ and therefore they are also readable in ∆.
In Section 3 and Section 4 we study how generic words can be read in labeled
graphs of Betti number at most 2n − 1, in particular we show that a path reading
such a word only travels few edges more than once unless the graph contains Rn or
a 2-sheeted cover of Rn , see Theorem 4.3. This gives us control over how generic
words are read in ∆.
Using genericity and small cancellation theory considerations and the fact that
xi =G bi for 1 ≤ i ≤ n, we conclude (see Section 5) that generically one of the
following holds:

4

ILYA KAPOVICH AND RICHARD WEIDMANN
Γ
x2n−1
∆

x1

x3

x2

Rn

Figure 1. ∆ is the last graph in the folding sequence that doesn’t
contain a copy of Rn . Ψ is the fat subgraph of ∆.
(1) xi = vi for 1 ≤ i ≤ n.
(2) For some i ∈ {1, . . . , n} the word xi contains a subword Z which is almost
all of a cyclic permutation U∗ of some Uj±1 .
In Section 7 we show that both cases yield a contradiction to either the genericity
of the presentation or the minimality assumption mentioned above.
In case (1), genericity implies that for each i the path γvi in ∆, that reads the
word vi , runs over a long (subdivided) segment of ∆\Ψ that is not visited by γvj
for j 6= i. Therefore the Betti number of ∆/Ψ ist at least n, which is impossible as
b(∆) ≤ 2n − 1 and b(Ψ) ≥ n.
In case (2), the subword Z in the label of the i-th petal of Γ projects to a path
sZ with label Z in ∆. Since words readable in Ψ are highly non-generic, we exploit
the genericity properties of the presentation to conclude that there is some ”long”
(comprising a definite portion of the length of Uj ) arc Q0 in ∆\Ψ with label W such
that sZ runs over Q0 exactly once. We then perform a surgery on ∆ by replacing
Q0 in ∆ by an arc labelled by the word complimentary to W in U∗ word V (so that
U∗ ≡ W V −1 in F (A)), to obtain a graph ∆0 . Genericity considerations allow us to
conclude that the full pre-image of Q0 in Γ consists of a disjoint collections of arcs
labelled W inside the petals of Γ. We replace each such arc by an arc labelled V to
obtain a graph Γ0 which is a wedge of 2n − 1 circles labeled z1 , . . . , z2n−1 . Let x0i be
the word obtained from zi by free reduction. By construction the graph Γ0 still folds
onto ∆0 . Since ∆0 still contains the subgraph Ψ, it follows that ∆0 folds onto Rn
and hence Γ0 folds onto Rn as well. Therefore (x01 , . . . , x02n−1 ) is Nielsen equivalent
in F (A) to (a1 , . . . , an , 1, . . . , 1 ). We then use results established in Section 6 to
| {z }
n−1 times

show that the tuple (x01 , . . . , x02n−1 ) has strictly smaller complexity than the tuple
(x1 , . . . , x2n−1 ), yielding a contradiction to the minimal choice of (x1 , . . . , x2n−1 ).
2. Preliminaries
2.1. Conventions regarding graphs. By a graph Γ we mean a 1-dimensional
cell complex, equipped with the weak topology. We refer to 0-cells of Γ as vertices
and to open 1-cells of Γ as topological edges. The set of all vertices of Γ is denoted

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

5

V Γ and the set of topological edges of Γ is denoted Etop Γ. For each topological
edge e of Γ we fix a characteristic map τe : [0, 1] → Γ which is the attaching map
for e. Thus τe is a continuous map whose restriction to (0, 1) is a homeomorphism
between (0, 1) and the open 1-cell e, and the points τe (0), τe (1) are (not necessarily
distinct) vertices of Γ.
Each topological edge e is homeomorphic to (0, 1) and thus, being a connected
1-manifold, it admits exactly two possible orientations. An oriented edge or just
edge of Γ is a topological edge together with the choice of an orientation on it. We
denote by EΓ the set of all oriented edges of Γ. If e ∈ EΓ is an oriented edge,
we denote by e−1 ∈ EΓ the same topological edge with the opposite orientation.
Thus −1 : EΓ → EΓ is a fixed-point-free involution on EΓ. For every oriented edge
e ∈ EΓ the attaching map for the underlying topological edge naturally defines the
initial vertex α(e) ∈ V Γ and the terminal vertex ω(e) ∈ V Γ of Γ. Note that for
every e ∈ EΓ we have α(e) = ω(e−1 ) and ω(e) = α(e−1 ).
For a vertex v ∈ V Γ the degree deg(v) of v in Γ is the cardinality of the set
{e ∈ EΓ|α(e) = v}.
Let Γ and Γ0 be graphs. A morphism or a graph-map f : Γ → Γ0 is a continuous
map f such that f (V Γ) ⊆ V Γ0 and such that the restriction of f to any topological
edge (that is, an open 1-cell) e of Γ is a homeomorphism between e and some
topological edge e0 of Γ0 . Thus a morphism f : Γ → Γ naturally defines a function
(still denoted by f ) f : EΓ → EΓ0 . Moreover, for any e ∈ EΓ we have f (e−1 ) =
(f (e))−1 ∈ EΓ0 and α(f (e)) = f (α(e)), ω(f (e)) = f (ω(e)).
2.2. Paths, coverings and path-surjective maps. A combinatorial edge-path
or just an edge-path of length n ≥ 1 in a graph Γ is a sequence γ = e1 , . . . , en where
ei ∈ EΓ for i = 1, . . . , n and such that for all 1 ≤ i < n we have ω(ei ) = α(ei+1 ). We
denote the length n of γ as n = |γ| and also denote α(γ) := α(e1 ) and ω(γ) := ω(en ).
Also, for any vertex v ∈ V Γ we regard γ = v as an edge-path of length |γ| = 0 with
α(γ) = ω(γ) = v. An edge-path γ in Γ is called reduced if γ does not contain a
subpath of the form e, e−1 where e ∈ EΓ.
For a finite graph Γ (not necessarily connected), we denote by b(Γ) the first betti
number of Γ. If Γ is a graph and Γ0 ⊆ Γ is a subgraph, we denote by Γ/Γ0 the
graph obtained from Γ by collapsing every connected component of Γ0 to a vertex.
We will need the following elementary but useful lemma whose proof is left to
the reader:
Lemma 2.1. Let Γ be a finite graph and let Γ0 ⊆ Γ be a subgraph (not necessarily
connected). Then b(Γ) = b(Γ0 ) + b(Γ/Γ0 ).
If Γ is a connected non-contractible graph, the core of Γ, denoted by Core(Γ), is
the smallest connected subgraph Γ0 of Γ such that the inclusion map ι : Γ0 → Γ is a
homotopy equivalence. A connected graph Γ is called a core graph if Γ = Core(Γ).
Note that if Γ is a finite connected non-contractible graph then Γ is a core graph
if and only if for every v ∈ V Γ we have deg(v) ≥ 2. If Γ is a graph and v ∈ V Γ
a vertex then we call the pair (Γ, v) a core pair or a core graph with respect to v
if Γ contains no proper subgraph containing v such that the inclusion map is a
homotopy equivalence. Thus if (Γ, v) is a core graph then either Γ is a core graph
or Γ is obtained from a core graph Γ̄ by adding segment joining v and Γ̄.
Note that if f : ∆ → Γ is a morphism of graphs and if β = e1 , . . . , en is an
edge-path in ∆ of length n > 0 then f (β) := f (e1 ), . . . f (en ) is an edge-path in Γ
with |γ| = |β|. In this case we call β a lift of f (β) to ∆. Also, if u ∈ V ∆ and
v = f (u) ∈ V Γ then we call the length-0 path β = u a lift of the length-0 path
γ = v.

6

ILYA KAPOVICH AND RICHARD WEIDMANN

It is not hard to see that a graph morphism f : ∆ → Γ is a covering map (in
the standard topological sense) if and only if f is surjective and locally bijective.
It follows from the definitions that a surjective morphism f : ∆ → Γ is a covering
map if and only if for every vertex v ∈ V Γ, every edge-path γ in Γ with α(γ) = v
and every vertex u ∈ V ∆ with f (u) = v there exists a unique lift γ
e of γ such that
α(e
γ ) = u.
We will need to investigate the following weaker version of being a covering map:
Definition 2.2 (Path-surjective map). Let f : ∆ → Γ be a surjective morphism
of graphs. We say that f is path-surjective if for every reduced edge-path γ in Γ
there exists a lift γ
e of γ in ∆.
Let ∆ be a finite graph which contains at least one edge. A subgraph Λ of ∆
is an arc if ∆ is the image of a simple (possibly closed) edge-path γ = e1 , . . . , en ,
where n ≥ 1, such that for all 1 ≤ i < n the vertex ω(ei ) has degree 2 in ∆. If, in
addition, deg∆ (α(e1 )) 6= 2 and deg∆ (ω(en )) 6= 2, then Λ is called a maximal arc in
∆. An arc Λ in ∆ is semi-maximal if for the simple path γ = e1 , . . . , en defining Λ
either deg∆ (α(e1 )) 6= 2, deg∆ (ω(en )) = 2 or deg∆ (α(e1 )) = 2, deg∆ (ω(en )) 6= 2.
If ∆ is a finite connected graph with at least one edge and such that ∆ is
not a simplicially subdivided circle then every edge of ∆ is contained in a unique
maximal arc of ∆. Moreover in this case for every arc Λ of ∆ the simple edge-path
γ = e1 , . . . , en , whose image is equal to Λ, is unique up to inversion and the set of
its endpoints {α(e1 ), ω(en )} is uniquely determined by Λ.
3. A characterization of 2-sheeted covers of a rose
Definition 3.1 (Standard n-rose). For an integer n ≥ 1 we denote by Rn the
rose with n petals, i.e. the graph with a single vertex v0 and edge set ERn =
±1
{e±1
1 , . . . , en }. For 0 ≤ m < n we consider Rm as a subgraph of Rn in the obvious
way.
In this paper we will utilize some of the basic results about Stallings folds. We
refer the reader to [Sta, KM] for the relevant background information.
It is easy to explicitly characterize all the connected 2-fold covers of Rn . Namely,
a morphism p : Γ → Rn (where Γ is a connected graph) is a 2-fold cover if and only
if Γ has two distinct vertices v and w and for each i = 1, . . . , n there either exist
loop edges at v and w that map to ei or there exist two edges from v to w that
map to ei and e−1
i , respectively. The connectedness of Γ implies that for at least
one i the second option occurs.
e2
e1
e3

e1
e1

e3

p
e3

e2

e2

Figure 2. A 2-sheeted cover of R3
Note that if p : Γ → Rn is a morphism of graphs then p(V Γ) = {v0 } since Rn
is a graph with a single vertex v0 . Thus any such morphism p : Γ → Rn can be

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

7

uniquely encoded by specifying for every edge e ∈ EΓ its “label” p(e) ∈ ERn =
±1
{e±1
1 , . . . , en }. Moreover, a labelling of EΓ by elements of ERn determines a
morphism if and only if this labeling respects edge inversion.
The main purpose of this section is to characterize 2-fold covers of Rn in terms
of path-surjective maps:
Theorem 3.2. Let Γ be a connected finite core graph, n ≥ 2 and p : Γ → Rn be a
path surjective morphism such that the following hold:
(1) Rn does not lift to Γ, i.e. there exists no morphism f : Rn → Γ such that
p ◦ f = idRn .
(2) b(Γ) ≤ 2n − 1.
Then p is a 2-sheeted covering map.
Note that it is easy to find a finite connected core graph Γ and a path-surjective
map p : Γ → Rn such that Γ does not contain a finite-sheeted cover of Rn . Indeed
taking Γ to be rose with (2n)(2n − 1) loops of length 2 and choosing f to be the
map that maps the (2n)(2n − 1) loops of Γ to the (2n)(2n − 1) distinct reduced
paths of length 2 in Rn does the trick. Thus the hypothesis on the Betti number
in Theorem 3.2 cannot be dropped. However, we do not know whether 2n − 1 is
the best possible lower bound.
Convention 3.3. For the remainder of this section we assume that n ≥ 2 and
p : Γ → Rn is as in Theorem 3.2. For any nonempty subset S ⊂ ERn let ΓS be the
subgraph of Γ formed by the edges that get mapped by p to some edge in S ∪ S −1 .
For S = {e} we will write Γe instead of Γ{e} . Note that for every e ∈ ERn we have
Γe = Γe−1 = Γ{e,e−1 } .
Lemma 3.4. The following hold:
(1) For every e ∈ {e1 , . . . , en } we have b(Γe ) ≥ 1.
(2) There exists e ∈ {e1 , . . . , en } such that b(Γe ) = 1.
Proof. To see that (1) holds let e ∈ ERn be arbitrary. Put k = |EΓ| + 1 and
consider the path γ := ek = e, . . . , e in Rn . Since p is path-surjective, there exists
| {z }
k times

a lift γ
e of γ to Γ, and, by definition of Γe , this path γ
e is contained in Γe . By the
choice of k the path γ
e contains at least two occurrences of the same oriented edge,
and hence γ
e contains a simple circuit embedded in Γe . Therefore b(Γe ) ≥ 1, as
claimed. Thus part (1) of the lemma is established.
Suppose now that part (2) fails. By part (1) this means that b(Γe ) ≥ 2 for every
e ∈ {e1 , . . . , en }. Since Γ = ∪ni=1 Γei , this implies that b(Γ) ≥ 2n, contrary to the
assumptions about Γ in Theorem 3.2. Thus part (2) of the lemma also holds. 
In view of Lemma 3.4, after possibly permuting the indexing of the edges of Rn
we may assume that b(Γe1 ) = 1.
Lemma 3.5. There exists a permutation of {e1 , . . . , en } such that, after this permutation, for all k ∈ {1, . . . , n} we have
b(ΓSk ) ≤ 2k − 1
where Sk = {e1 , . . . , ek }.
Proof. The proof is by induction on k. As noted above, in view of Lemma 3.4 we
may assume that b(Γe1 ) = 1.
Suppose now that 2 ≤ k ≤ n and that we have already re-indexed the edges of
Rn so that b(ΓSi ) ≤ 2i − 1 for i = 1, . . . , k − 1. In particular, b(ΓSk−1 ) ≤ 2k − 3.
For 1 ≤ i < j ≤ n put Sij := {1, . . . , i} ∪ {j}.

8

ILYA KAPOVICH AND RICHARD WEIDMANN

Choose j ∈ {k, . . . , n} so that b(ΓS j

k−1

i
) = min{b(ΓSk−1
)|k ≤ i ≤ n}. Then re-

i
)
) ≤ b(ΓSk−1
index the edges ek , . . . , en so that j = k. Thus now b(ΓSk ) = b(ΓSk−1
k
for i = k, . . . , n.
By Lemma 2.1, we have

b(ΓSk ) − b(ΓSk−1 ) = b(ΓSk /ΓSk−1 ).
If b(ΓSk /ΓSk−1 ) ≤ 2 then b(Sk ) ≤ (2k − 3) + 2 = 2k − 1 and Sk has the properties
required by the lemma, completing the inductive step.
Thus suppose that b(ΓSk /ΓSk−1 ) ≥ 3. The minimality assumption in the choice
i
/ΓSk−1 ) ≥ 3. Thus for
of ek implies that for all i = k, . . . , n we have b(ΓSk−1
i = k, . . . , n the graph Γ/ΓSk−1 contains a graph of Betti number at least 3 all of
whose edges map to e±1
in Rn . Therefore
i
b(ΓSk /ΓSk−1 ) ≤ b(Γ/ΓSk−1 ) − 3(n − k).
Recall that by assumptions on Γ in Theorem 3.2 we have b(Γ) ≤ 2n − 1. Hence
b(ΓSk ) = b(ΓSk /ΓSk−1 ) + b(ΓSk−1 ) ≤ b(Γ/ΓSk−1 ) − 3(n − k) + b(ΓSk−1 ) =
= b(Γ) − 3(n − k) ≤ (2n − 1) − 3(n − k) ≤ 2k − 1,
as required. This completed the inductive step and the proof of the lemma.



Convention 3.6. For the remainder of the section we assume that the edges of
Rn are indexed so that b(Γe1 ) = 1 and that for every k = 1, . . . , n we have 1 ≤
b(ΓSk ) ≤ 2k − 1. Denote by Ce1 the unique embedded circuit in Γe1 and let Γ0e1 be
the component of Γe1 containing Ce1 .
For k = 1, . . . , n let ∆k be the core of the component of ΓSk containing Ce1 .
Thus b(∆k ) ≤ b(ΓSk ) ≤ 2k − 1.
Lemma 3.7. For every k = 1, . . . , n every reduced path γ in Rk lifts to a path in
∆k .
Proof. Let 1 ≤ k ≤ n and let γ be any reduced path in Rk . Choose , δ ∈ {−1, 1}
mδ
so that the path e1 γeδ1 is reduced. Put m = |EΓ| + 1. Thus γm = em
is a
1 γe1
reduced path in Rk . Since p : Γ → Rn is path-surjective, the path γm lifts to some
path γ
em in Γ. The choice of m implies that γ
em is contained in the component of
ΓSk containing Ce1 , that is, the component Y of ΓSk containing ∆k . Note that
∆k = core(Y ) and Ce1 ⊆ ∆k . Each of the two subpaths of γ
em corresponding to
mδ
the lifts of em
and
e
overlaps
C
and
hence
overlaps
core(Y
). Therefore the
e
1
1
1
portion of γ
em corresponding to the lift of γ is contained in core(Y ) = ∆k . Thus γ
lifts to ∆k , as claimed.

We now examine the properties of the graph ∆2 .
Proposition 3.8. One of the following holds:
(1) The restriction of p to ∆2 is a 2-sheeted cover onto R2 .
(2) R2 lifts to ∆2 .
Proof. Recall that Ce1 is the unique embedded circuit in Γe1 and that Γ0e1 is the
component of Γe1 containing Ce1 . Thus Ce1 is labelled by a power of e1 .
Note that there must exist a circuit Ce2 labeled by a power of e2 that lies in a
component Γ0e2 of Γe2 that intersects Γ0e1 in some (not necessarily unique) vertex v
as any path of type en1 en2 is assumed to lift to ΓS2 ⊂ Γ. We distinguish a number
of subcases, which cover all possibilities:
Subcase A: b(Γe2 ) = b(Γ0e2 ) = 2. In this case we have ∆2 ⊂ Γ0e1 ∪ Γ0e2 and
Γ0e1 ∩ Γ0e2 = {v} as ∆2 is a core graph with b(∆2 ) ≤ 3. It follows that R2 lifts to

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

9

∆2 as by Lemma 3.7 the path e1 , e2 , e1 , e2 must have a lift which implies that for
i = 1, 2 there must be a loop edge based at v that is mapped to ei .
Subcase B: b(Γe2 ) = 2 and b(Γ0e2 ) = 1. Again we must have Γ0e1 ∩ Γ0e2 = {v} for
Betti number reasons. Moreover there exists a component Γ1e2 of Γe2 with Γ1e2 6= Γ0e2
and b(Γ1e2 ) = 1.
If Γ0e1 ∩ Γ1e2 = ∅ then any path of type en1 , en2 , en1 , en2 with n ≥ |EΓ| must lift to
∪ Γ0e2 as lifts are connected and any subpath eni must lift to a component of
Γei that contains a non-trivial circuit. Thus any path eni must lift to a closed path
in Γ0ei based at v for all n ≥ |EΓ|. As b(Γ0e1 ) = b(Γ0e2 ) = 1 this implies that Γ0ei
contains a loop edge based at v that is mapped to ei for i = 1, 2, thus R2 lifts to
∆2 .
If Γ0e1 ∩ Γ1e2 6= ∅ then Γ0e1 ∩ Γ1e2 must consist of a single vertex w for Betti
number reasons. Moreover we have ∆2 ⊂ Γ0e1 ∪ Γ0e2 ∪ Γ1e2 . By Lemma 3.7 the path
e1 , e2 , e1 , e2 , e1 , e2 , e1 lifts to ∆2 and the lifts of the occurrences of e2 must be loop
edges based at v or w. If the lifts of two consecutive occurrence of e2 are identical
then there must also be a loop edge mapped to e1 at the same base vertex and it
follows that R2 lifts. Otherwise there must be an edge from v to w and also an
edge from w to v that is mapped to e1 in which case the restriction of p to ∆2 is a
2-sheeted cover onto R2 .
Γ0e1

Subcase C: b(Γe2 ) = b(Γ0e2 ) = 1 and Γ0e1 ∩ Γ0e2 = {v}. In this case any path of
type en1 , en2 , en1 , en2 with n ≥ |EΓ| must lift to Γ0e1 ∪ Γ0e2 and we argue as in Subcase
B that R2 lifts.
Subcase D: b(Γe2 ) = b(Γ0e2 ) = 1 and Γ0e1 ∩ Γ0e2 = {v, w}.
If ∆2 contains no loop edge at v or w then there must be edges from v to w that
−1
−1 −1
map to e1 , e2 , e−1
1 and e2 as, by Lemma 3.7, the path e1 , e2 , e1 , e2 , e1 , e2 lifts
to ∆2 , and the lift must alternate between v and w. It follows that the restriction
of p to ∆2 is a 2-sheeted cover of R2 .
In the remaining case we assume by symmetry that Γ0e1 has a loop edge based
at v. We may assume that Γ0e2 does not have a loop edge based at v, otherwise
R2 lifts to ∆2 . Let now f be the unique edge of Γ0e1 ∩ ∆2 with α(f ) = w. Choose
ε ∈ {−1, 1} such that p(f ) = eε1 . It follows that any lift of eεn
1 for n ≥ |EΓ| to ∆2
terminates at v. As eεn
e
e
lifts
to
∆
and
as
there
is
no
loop
edge in Γ0e2 based
2
1 2 1
at v it follows that any lift of eεn
e
to
∆
must
terminate
at
w.
It
follows that the
2
1 2
−ε
path eεn
e
e
does
not
lift
to
∆
,
thus
this
case
does
not
occur.

2
1 2 1
Proof of Theorem 3.2. We claim that for 2 ≤ k ≤ n one of the following holds:
(1) The restriction of p to ∆k is a 2-sheeted cover onto Rk .
(2) Rk lifts to ∆k .
For k = n the above claim implies the statement of Theorem 3.2 since Γ =
core(Γ) = ∆n . Note that the claim above is false for k = 1.
We establish the claim by induction on k. The base case, k = 2, is exactly the
conclusion of Proposition 3.8.
Suppose now that 3 ≤ k ≤ n and that the claim has been verified for k − 1. Thus
we know that ∆k−1 is either a 2-sheeted cover of Rk−1 or that ∆k−1 contains a lift
of Rk−1 . In the first case we may moreover assume that there is an edge with label
e−1
1 and an edge with label e1 connecting the two vertices of ∆k−1 .
Subcase A: ∆k−1 contains a lift R̃k−1 of Rk−1 . If ∆k contains a loop edge at the
base vertex of R̃k−1 that is mapped to ek then ∆k contains a lift of Rk and there
is nothing to show. Thus we may assume that such a loop edge does not exist. We
will show that this yields a contradiction.

10

ILYA KAPOVICH AND RICHARD WEIDMANN

Let Γ1k be the core of the component of the subgraph Γ{e1 ,ek } containing the
unique loop edge mapped to e1 . Moreover let R1k be the subgraph of Rn consisting
±1
of the edge pairs e±1
1 and ek . By an argument similar to the proof of Lemma 3.7,
any path γ in R1k must lift to Γ1k . It now follows from the case k = 2 and the
fact that R1k does not lift to Γ that Γ1k is either a 2-sheeted cover of R1k or that
b(Γ1k ) ≥ 4. As Γ1k does not contain a second loop edge mapped to e1 it cannot be
a 2-sheeted cover, thus b(Γ1k ) ≥ 4. Let now Γ0 := Γ1k ∪ R̃k−1 . It follows that
b(Γ0 ) ≥ 4 + (k − 2) = k + 2.
Claim: For 2 ≤ i ≤ k − 1 either ∆k contains a circuit that maps to ei and that is
distinct from the loop in R̃k−1 or there exist two edges in E∆k − EΓ0 originating
at Γ0 that map to ei and e−1
i , respectively.
Proof of Claim: Suppose that no such circuit exists for some i ∈ {2, . . . k − 1}. We
need to show that for ε ∈ {−1, 1} there exists an edge in E∆k − EΓ0 originating
at Γ0 that maps to eεi . Suppose that ε ∈ {−1, 1} and that no such edge exists. It
ε·|EΓ|
follows that any lift of the path ei
must terminate at the base vertex v0 of R̃k−1
ε·|EΓ|
and any lift of ei
ek must terminate at a vertex distinct from v0 . This implies
ε·|EΓ|
that the path ei
ek eεi does not lift to ∆k , a contradiction. The claim follows.2
Now each additional circuit gives a contribution of at least 1 to the Betti number
and two edges originating at Γ0 do the same as we are looking at a core graph, thus
the loose ends must close up. It follows that
b(Γk ) ≥ b(Γ0 ) + (k − 2) = (k + 2) + (k − 2) = 2k
which gives the desired contradiction.
Subcase B: ∆k−1 is a 2-sheeted cover of Rk−1 and the edges with label e1 span
a circuit of length 2. It follows in particular that b(Γk−1 ) = 2k − 3.
Define Γ1k as in Subcase A, again we apply the case k = 2 to this graph. As Γ
contains no loop edge with label e1 and as for Betti number reasons b(Γ1k ) ≤ 3 it
follows that Γ1k is a 2-sheeted cover of R1k . It follows that Γ1k consists either of
a circuit of length two with label e1 , e1 and two loop edges with label ek or of two
circuits of length 2 with label e1 , e1 and ek , ek with common vertices. In both cases
it is immediate that ∆k−1 ∪ Γ1k is a 2-sheeted cover of Rk .

4. Lifting random paths in Rn
In this section all edges are geometric edges, i.e. edge pairs. Theorem 3.2 is only
used in this section, specifically in the proof of Theorem 4.3.
Definition 4.1. Let α ∈ [0, 1]. We say that a path γ in some graph Γ is α-injective
if γ crosses at least α · |γ| distinct topological edges. Thus γ is 1-injective if and
only if γ travels no topological edge twice. In other words, γ is α-injective if its
image is of volume at least α · |γ|.
Definition 4.2. Let Γ be a graph and let γ = e1 , . . . , ek be an edge-path in Γ.
We say that the edge ei is γ-injective if the topological edge of Γ corresponding
to ei is traversed by γ exactly once. Similarly, a subpath γ 0 = eq . . . er (where
1 ≤ q ≤ r ≤ k) of γ is γ-injective if for every i = q, . . . , r the edge ei is γ-injective.
Similarly, let Υ be a graph which is a topological segment subdivided into finitely
many edges, let Γ be a graph and let f : Υ → Γ be a graph map. We say that
an edge e of Υ is Υ-injective if for the edge-path γ determined by Υ the edge e is
γ-injective. An arc of Υ is Υ-injective if every edge of this arc is Υ-injective.

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

11

In the following we denote the set of all reduced paths in Rn by Ω and the set
of all reduced paths of length N by ΩN . We further call a subset S ⊂ Ω generic if
N|
lim |S∩Ω
|ΩN | = 1. This definition of genericity agrees with the more detailed notions
N →∞

of genericity defined in Section 5 below.
Throughout this section we assume that n ≥ 2.
The purpose of this section is to establish the following theorem:
Theorem 4.3. Let α ∈ [0, 1). The set Ω of all reduced paths in Rn contains a
generic subset S such that the following holds:
Let s ∈ S and (Γ, v0 ) be a connected core graph with b(Γ) ≤ 2n − 1. Suppose
that f : Γ → Rn is a morphism such that Γ does not contain a finite subgraph Γ0
such that p|Γ0 : Γ0 → Rn is a covering (of degree 1 or 2). Then any lift s̃ of s is
α-injective.
Before we give the proof Theorem 4.3 we establish Proposition 4.4 and Proposition 4.8 which follow from elementary probabilistic considerations.
Proposition 4.4. For any ε > 0 there exists a constant L = L(ε, n) and a generic
subset S ⊂ Ω such that the following holds:
Suppose that s ∈ S and that γ is a path in Rn of length at least L such that γ
occurs as least twice as a subpath of s such that these two subpaths do not overlap.
Then the total length of any collection of non-overlapping subpaths of s that coincide
with γ is bounded from above by ε|s|.
For the remainder of this section, unless specified otherwise, we fix the following
conventions and notations.
Convention 4.5.
(1) Denote by ΩN the set of of all reduced paths of length N , endowed with the
uniform distribution. Let γ be a fixed path in Rn and put k := |γ|. Note that in
Rn there are exactly 2n(2n − 1)k−1 reduced paths of length k.
Now consider the random variable Y = Yγ,N : ΩN → R defined by
Yγ,N (s) := |γ| · max{l | s has l disjoint subpaths that coincide with γ}.
Thus Y assigns to any path s ∈ ΩN the total length of a maximal portion of s that
is covered by a collection of disjoint copies of γ. To prove Proposition 4.4 we will
need to estimate P (Y ≥ N ) from above. Our estimate will not depend on γ but
only on k = |γ|.
1
(2) Put p := (2n−1)
k . Note that for n ≥ 2 and k ≥ 1 we have 0 < 2p < 1. We
will also consider a random variable X = Xk that is binomially distributed with
parameters N and 2p.
In addition, let Ω0N = {0, 1}N with the distribution corresponding to performing
N independent tosses of a coin such that for a single toss the probability of the coin
landing ”heads” is 2p and of it landing ”tails” is 1 − 2p. Thus for a binary string
w ∈ Ω0N we have P (w) = (2p)t (1 − 2p)N −t where t is the number of 1’s in the string
w. Hence for every integer t ∈ [0, N ] P (Xk = t) is equal to the probability of the
event that a randomly chosen string w ∈ Ω0N contains exactly t entries 1.
(3) Consider the finite state Markov chain M generating freely reduced words in
Fn = F (a1 , . . . , an ). Thus the state set of M is Q = {a1 , . . . , an }±1 with transition
1
probabilities PM (a, b) = 2n−1
if a, b ∈ Q, b 6= a−1 and PM (a, b) = 0 if a, b ∈ Q
−1
and b = a . Note that M is an irreducible finite state Markov chain with the
stationary distribution being the uniform distribution on Q. Since n ≥ 2, whenever
a, b ∈ Q satisfy PM (a, b) > 0 then
1
4 1
3 1
(♣)
·
≤ PM (a, b) =
≤ ·
.
4 2n
2n − 1
3 2n

12

ILYA KAPOVICH AND RICHARD WEIDMANN

Lemma 4.6. There exists a constant C1 = C1 (n, ) ≥ 1 such that if k = |γ| ≥ C1
then for every N ≥ 1 and every integer t ∈ [0, N ] satisfying t ≥ N/k we have
(4/3)t pt ≤ (2p)t (1 − 2p)N .
Proof. Let n ≥ 2, N ≥ 1, k ≥ 1 be arbitrary integers and let  > 0. Recall that
p = 1/(2n − 1)k and that 0 < 1 − 2p < 1.
Let t ∈ [0, N ] be an integer satisfying t ≥ N/k, clearly t ≥ 1. As t > 0 the
inequality (4/3)t pt ≤ (2p)t (1 − 2p)N is equivalent to (4/3)p ≤ 2p(1 − 2p)N/t which
in turn is equivalent to
(∗)

2/3 ≤ (1 − 2p)N/t .

Thus we need to show that (∗) holds provided k is sufficiently large. Since
t ≥ N/k, we have N/t ≤ k/. As 0 < 1 − 2p < 1, it follows that (1 − 2p)k/ ≤
(1 − 2p)N/t .
For fixed n and  we have
k/

2
k→∞
(1 − 2p)k/ = 1 −
−−−−→ 1.
(2n − 1)k
Hence there exists a constant C1 = C1 (n, ) ≥ 1 such that for every k ≥ C1 we have
(1 − 2p)k/ ≥ 2/3. Then for any k ≥ C1
(1 − 2p)N/t ≥ (1 − 2p)k/ ≥ 2/3,
as required. Thus the lemma is proven.



Lemma 4.7. Let C1 = C1 (n, ) ≥ 1 be the constant provided by Lemma 4.6.
Suppose that k = |γ| ≥ C1 .
Then for every integer t ∈ [0, N ] such that t ≥ N/k we have
P (Yγ,N ≥ kt) ≤ P (Xk ≥ t).
Proof. For any integers 1 ≤ i1 < · · · < it ≤ N let V (i1 , . . . , it ) ⊆ ΩN be the event
that for s ∈ ΩN for each j = 1, . . . t the subpaths of s of length k starting in
positions i1 , . . . , it are equal to γ and that these subpaths do not overlap in s.
We first claim that for every tuple 1 ≤ i1 < · · · < it ≤ N we have
(♥)

P (V (i1 , . . . , it )) ≤ (4/3)t pt .

Note that the uniform distribution on ΩN is the same as the distribution on ΩN
obtained by taking the uniform distribution on Q, considered as giving the initial
letter of a word of length N , followed by applying the Markov chain M exactly
N − 1 times.
Choose a specific t-tuple 1 ≤ i1 < · · · < it ≤ N .
If N − it < k − 1, then the terminal segment of s starting with the letter in
position it has length < k and hence P (V (i1 , . . . , it )) = 0 ≤ (4/3)t pt . Similarly, if
there exists j such that ij − ij−1 ≤ k − 1 then the subpaths of s of length k starting
in positions ij−1 and ij overlap, and hence P (V (i1 , . . . , it )) = 0 ≤ (4/3)t pt . Thus
we assume that N − it ≥ k − 1 and that ij − ij−1 ≥ k. For similar reasons, we may
assume that whenever ij − ij−1 = k then the first letter of γ is not the inverse of
the last letter of γ since otherwise we again have P (V (i1 , . . . , it )) = 0.
By symmetry, the probability that the i1 -th letter of a random s ∈ ΩN is the
1
. Then, applying the Markov chain M defining
same as the first letter of γ is 2n
above we see that the probability of reading γ starting at letter number i1 in s is
1
1
1
equal to 2n(2n−1)
k−1 , so that P (V (i1 )) = 2n(2n−1)k−1 ≤ (2n−1)k = p.
Given that the event V (i1 ) occurred, consider the conditional distribution ν1 on
Q corresponding to the letter in s in the position i1 + k, i.e. the first letter in s
immediately after the last letter of the γ-subword that started in position i1 . By

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

13

1
(♣) it follows that for every a ∈ Q we have ν1 (a) ≤ (4/3) 2n
. For each a ∈ Q let
Ha,i1 +k be the event that for an element of ΩN the letter in position i1 + k is a.
Let P (V (i2 )|Ha,i1 +k ) be the conditional probability of V (i2 ) given Ha,i1 +k . Then
the conditional probability of V (i1 , i2 ) given that V (i1 ) occurred can be computed
as
X
P (V (i1 , i2 )|V (i1 )) =
ν1 (a)P (V (i2 )|Ha,i1 +k ).
a∈Q

Also,
the unconditional probability P (V (i2 )) can be computed as P (V (i2 )) =
P
1
a∈Q 2n P (V (i2 )|Ha,i1 +k ). The same argument as the argument above for com1
1
puting P (V (i1 )) shows that P (V (i2 )) = 2n(2n−1)
k−1 ≤ (2n−1)k = p. Since for every
1
a ∈ Q we have ν1 (a) ≤ (4/3) 2n
, it follows that
X
P (V (i1 , i2 )|V (i1 )) =
ν1 (a)P (V (i2 )|Ha,i1 +k ) ≤
a∈Q

X 1
≤ (4/3)
P (V (i2 )|Ha,i1 +k ) = (4/3)P (V (i2 )) ≤ (4/3)p.
2n
a∈Q

Similarly, P (V (i1 , i2 , i3 )|V (i1 , i2 )) ≤ (4/3)p and, so on, up to
P (V (i1 , i2 , i3 , . . . , it )|V (i1 , i2 , . . . , it−1 )) ≤ (4/3)p.
Hence
P (V (i1 , . . . , it )) =
P (V (i1 ))P (V (i1 , i2 )|V (i1 )) . . . P (V (i1 , i2 , i3 , . . . , it )|V (i1 , i2 , . . . , it−1 ))
≤ (4/3)t−1 pt ≤ (4/3)t pt
as required. Thus (♥) is verified.
For 1 ≤ i1 < · · · < it ≤ N let W (i1 , . . . , it ) ⊆ Ω0N be the event that for a
binary string w ∈ Ω0N the digits in the positions i1 , . . . , it are equal to 1 and for
all j < it , j 6= i1 , . . . , it the digit in position j in w is 0. Then, by independence,
P (W (i1 , . . . , it )) = (2p)t (1 − 2p)it −t . Hence, by Lemma 4.6 and by (♥), we have
P (V (i1 , . . . , it )) ≤ (4/3)t pt ≤ (2p)t (1−2p)N ≤ (2p)t (1−2p)it −t = P (W (i1 , . . . , it )).
The event ”Yγ,N ≥ kt” is the (non-disjoint) union of events V (i1 , . . . , it ) taken
over all t-tuples 1 ≤ i1 < · · · < it ≤ N . Also, the event that w ∈ Ω0N has at
least t digits 1 is the disjoint union of W (i1 , . . . , it ), again taken over all t-tuples
1 ≤ i1 < · · · < it ≤ N . Therefore
X
P (Yγ,N ≥ kt) ≤
P (V (i1 , . . . , it )) ≤
1≤i1 <···<it ≤N

X

P (W (i1 , . . . , it )) = P (Xk ≥ t),

1≤i1 <···<it ≤N

as required. This completes the proof of Lemma 4.7.



Having established Lemma 4.6 and Lemma 4.7, we can now prove Proposition 4.4.
Proof of Proposition 4.4. Mean and variance for kXk are given by
2
µ(kXk ) = k · µ(Xk ) = k · N · 2p = k · N ·
(2n − 1)k
and
var(kXk ) = k 2 · var(Xk ) = k 2 · N · 2p · (1 − 2p) =
2
2
2
= k2 · N ·
· (1 −
) < k2 · N ·
.
k
k
(2n − 1)
(2n − 1)
(2n − 1)k

14

ILYA KAPOVICH AND RICHARD WEIDMANN

Choose L > C1 (n, ) such that µ(kXk ) ≤ 2 · N for all k ≥ L. It now follows
from Lemma 4.7 and the Chebyshev inequality (as N > 2 N ≥ µ(kXk )) that for
any reduced path γ with |γ| = k ≥ L we have
P (Yγ,N ≥ N ) ≤ P (Xk ≥

var(kXk )
N
≤
) = P (kXk ≥ N ) ≤
k
(N − µ(kXk ))2

8
k 2 · N · (2n−1)
k
4 · var(kXk )
var(kXk )
k2
8
=
≤
≤
=
.
·

(N − 2 N )2
(N )2
2 N 2
2 N (2n − 1)k
By Proposition 2.2 of [M] we know that we can assume that no path γ of length
11
occurs twice in a random word of length
greater than C0 ln(N ) with C0 = ln(2n−1)
N . Thus we only need to sum up the probabilities for all paths γ of length up to
C0 ln(N ). Thus, taking into account that for each k there are only 2n(2n − 1)k−1
words to consider, the probability that a path of length at least L and at most
C0 ln(N ) covers the portion  · N of a path of ΩN is bounded from above by
C0 ln(N )

X

2n(2n − 1)k−1 ·

k=L

16n
8
k2
=
·
2
k
 N (2n − 1)
(2n − 1)2 N

C0 ln(N )

X

k2 ≤

k=L

16n
· (C0 ln(N ))3 .
≤
(2n − 1)2 N
Now this number converges to 0 as N tends to infinity which proves the proposition.

Proposition 4.8. Let α ∈ (0, 1] and γ be a reduced path in Rn . There exists a
constant δ > 0 and a generic subset Sγ ⊂ Ω such that the following hold:
If s ∈ Sγ can be written as a reduced product s = s0 t1 s1 · . . . · tq sq such that
(1) ti does not contain γ as a subpath for 1 ≤ i ≤ q and
q
P
(2)
|ti | ≥ α · |s|.
i=1

Then q ≥ δ · |s|
Proof. The idea of the proof is simple: As an average subpath of a generic path
that doesn’t contain γ as a subpath must be short, i.e. bounded in terms of n and
γ, and as the ti cover a definite portion of s it follows that q must be large is |s| is
large.
We sketch a proof but omit some of the details for brevity. Suppose that γ is
1
a reduced path of length k in Rn . Let p = 2n(2n−1)
k−1 . For any j ∈ N≥1 let f (j)
be the probability that in a random semi-infinite reduced path in Rn , a subpath
between two consecutive non-overlapping occurrences of γ is of length j.
This defines a probability distribution f on N≥1 . This distribution is essentially
geometric as the probability f (l + k − 1) is approximately (1 − p)l . Note that this
calculation ignores the fact that the events that distinct subpaths are of type γ are
(slightly) correlated. It follows in particular that the probability distribution f has
∞
∞
P
P
finite mean, i.e that the series
j · f (j) converges. Put µ :=
j · f (j) and choose
j=1

j0 ∈ N with j0 > 100k such that
∞
X
j=j0

j=1

j · f (j) ≤

α
µ.
10

Let now s ∈ Ω. We consider the collection of subpaths that make up the complement of the union of all subpath of s that are of type γ; we call these subpaths γcomplementary. Then there exists a generic subset Ω0 ⊆ Ω such that for any s ∈ Ω0
the collection of γ-complementary subsets is non-empty. For each s ∈ Ω0 we obtain

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

15

a probability distribution fs on N≥1 where fs (j) is the number of γ-complementary
subpaths of length j in s divided by the total number of γ-complementary subpaths
ns , i.e. fs is the relative frequency of γ-complementary subpaths of length j in s.
Then we have
∞
X
ns ·
j · fs (j) ≤ |s|
j=1

as the sum on the left is just the number of edges of s that lie in the γ-complementary
subpaths of s.
Claim: There exists some generic subset S ⊆ Ω0 ⊆ Ω such that for every s ∈ S we
have
∞
∞
X
α X
j · fs (j).
ns ·
j · fs (j) ≤ ns · ·
5 j=1
j=j
0

To verify the claim note first that it can be shown using the law of large numbers,
that there exists β ∈ [0, 1) such that for any  > 0 there exists a generic set S such
that the following hold:
(1) For any s ∈ S
∞
X
(β − )|s| ≤ ns ·
j · fs (j) ≤ (β + )|s|.
j=1

(2) For any j ∈ {1, . . . j0 − 1} and s ∈ S we have
j · f (j)
j · f (j)
· |s| ≤ ns · j · fs (j) ≤ (β + ε) ·
· |s|.
µ
µ
Indeed, the first assertion states for a generic path s the γ-complementary paths
of s cover roughly a fixed portion β of s, i.e. their total length is roughly β|s|. The
second assertion states that out of this γ-complementary portion of total length β|s|,
the portion that consists of γ-complementary path of length j is roughly j·fµ(j) , i.e.
(β − ε) ·

that total length of the γ-complementary paths of length j is roughly
This conclusion follows from the definition of f and µ.
Using (2) we get that for any s ∈ S we have
|s| ·

jX
0 −1

(β − ε) ·

j=1

j·f (j)
µ

· |s|.

jX
jX
0 −1
0 −1
j · f (j)
j · f (j)
≤
ns · j · fs (j) ≤ |s| ·
(β + ε) ·
.
µ
µ
j=1
j=1

It follows that
ns ·

∞
X
j=j0

j · fs (j) = ns ·

∞
X
j=1

j · fs (j) − ns ·

jX
0 −1

j · fs (j) ≤

j=1



j0 −1
β− X
β−
α
≤ |s| · (β + ) − |s| ·
·
j · f (j) ≤ |s| β +  −
(1 − ) · µ ≤
µ
µ
10
j=1




αβ
α
≤ |s| ·
+ 2−
.
10
10
For  sufficiently small we further have


∞

X
αβ
α
α
α
|s| ·
+ 2−
≤ (β − ) · |s| ≤ · ns ·
j · fs (j)
10
10
5
5
j=1
which proves the claim.
Let now s ∈ S and suppose that s = s0 t1 s1 · . . . · tq sq is as in the formulation of
the lemma. Note that for 1 ≤ i ≤ q either |ti | ≤ 2k − 2 or ti contains a subpath
t0i of length at least |ti | − 2k + 2 such that t0i is contained in a γ-complementary

16

ILYA KAPOVICH AND RICHARD WEIDMANN

subpath of s. It follows from the claim that the total length of all γ-complementary
subpaths of s of length greater than j0 is bounded from above by
ns ·

∞
X
j=j0

j · fs (j) ≤ ns ·

∞
α X
α
·
j · fs (j) ≤ · |s|.
5 j=1
5

Thus the sum of the lengths of those ti that contain a subpath of a γ-complementary
subpath of length at least j0 is bounded by
102k α
α
j0 + 2k α
· · |s| ≤
· · |s| ≤ · |s|.
j0
5
100k 5
4
It follows the sum of the length of those ti that are of length at most j0 + 2k
must be at least 3α
4 · |s| thus there must be at least
1
3α
3α
·
· |s| =
· |s|
j0 + 2k 4
4j0 + 8k
such edges. Thus the conclusion of the lemma holds for δ :=

3α
4j0 +8k .



We can now give the proof of the main result of this section.
Proof of Theorem 4.3. Put β := 1 − α. Recall that in Subsection 2.2 we introduced
the notion of arcs, maximal arcs and semi-maximal arcs in a finite graph. Note
that it suffices to consider core pairs (Γ, v0 ) with b(Γ) = 2n − 1 as we can otherwise
embed (Γ, v0 ) into a core pair (Γ0 , v0 ) with b(Γ0 ) = 2n − 1 that still satisfies the
hypothesis of Theorem 4.3 and the conclusion for (Γ0 , v0 ) then implies the conclusion
for (Γ, v0 ).
Note that if ∆ is a finite connected core graph with first Betti number m ≥ 2,
then ∆ has no degree-1 vertices and ∆ is the union of at most 3m − 3 maximal
arcs (which are obtained but cutting ∆ open at all vertices of degree ≥ 3). Also, if
(∆, v0 ) is a finite connected core pair with first Betti number m ≥ 2, then ∆ is the
union of at most 3m − 1 maximal arcs.
Now let (Γ, v0 ) be as in Theorem 4.3 with b(Γ) = 2n−1 ≥ 3. As (Γ, v0 ) is a finite
connected core graph the above remark implies that Γ decomposes as the union of at
most 3(2n − 1) − 1 = 6n − 4 distinct maximal arcs. If γ is a non-degenerate reduced
edge-path in Γ then after possibly subdividing the maximal arcs of Γ containing
endpoints of γ along those endpoints, we obtain a decomposition of Γ as the union
of distinct pairwise non-overlapping arcs Λ1 , . . . Λt such that t ≤ 6n − 2 < 6n and
such that γ admits a unique decomposition as a concatenation of simple (and hence
reduced) edge-paths
γ = γ0 γ1 . . . γr
such that for each i = 0, . . . , r there exists y(i) ≤ t such that the image of γi is equal
to the arc Λy(i) . Note that since the arcs Λ1 , . . . Λt are non-overlapping, for every
i, j ∈ {0, . . . , r} either γi = γj±1 or the paths γi and γi have no to topological edges
in common. We call the above factorization of γ the canonical arc decomposition
of γ. We also call the arcs Λ1 , . . . Λt the arc components of Γ adapted to γ.
Claim A. We will show that there exist constants `0 , `1 , . . . , `2n and generic sets
S2n ⊆ S2n−1 · · · ⊆ S1 ⊆ S0 ⊆ Ω
that only depend on n and α such that the following hold:
If k ∈ {0, 1, . . . , 2n}, s ∈ Sk , (Γ, v0 ) and f : Γ → Rn as in the statement of
the theorem with b(Γ) = 2n − 1 then for any non-α-injective lift s̃ of s there exist
connected subgraphs Γ0 ⊂ Γ1 ⊂ . . . ⊂ Γk of Γ with the following properties:
(1) The volume of Γi is bounded by above by `i for 0 ≤ i ≤ k.
(2) b(Γi ) ≥ i for 0 ≤ i ≤ k.

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

(3) If s̃ = e1 . . . eN then #{i|ei ∈ EΓ0 } ≥

β·N
6n

=

17

β·|s|
6n .

Note that for k = 2n this claim implies the theorem. Indeed it implies that the
generic set S := S2n has the property that for any s ∈ S any lift s̃ is α-injective as
a non-α-injective lift would imply the existence of a subgraphs of Γ of Betti number
2n which is impossible.
The proof of Claim A is by induction on k.
β
β
and let S and L = L(ε, n) = L( 6n
, n) be as in
The case k = 0. Let ε = 6n
the conclusion of Proposition 4.4. We will show that the claim holds for `0 := L
and S0 := S. Let s ∈ S0 , f : Γ → Rn as in the statement of Theorem 4.3, and let
s̃ a non-α-injective lift of s. As s̃ is not α-injective, it traverses fewer than α · |s|
distinct topological edges. This implies that there is a collection of subpaths of s̃
of total length at least β · |s| such that the image of these subpaths consists of all
the topological edges visited at least twice by s̃.

Since s is reduced and s̃ is a lift of s, the path s̃ is reduced as well. Let Λ1 , . . . , Λt ,
where t ≤ 6n, the the arc components of Γ adapted to s̃ and consider the canonical
arc decomposition of s̃. Then the union of topological edges visited at least twice by
s̃ is the union of some of the arcs Λi . Since t ≤ 6n, there exists i0 ≤ t such that the
subpaths of s̃ that map to Λi0 are of total length at least β·|s|
6n and that the number
of such subpaths is at least 2. It follows from the conclusion of Proposition 4.4 that
Λi0 has length at most L. Thus Claim A follows by choosing Γ0 = Λi0 and putting
`0 = L. Note that this choice of `0 is independent of the map f : Γ → Rn and s.
The case k ≥ 1. By induction we already have the constants `0 , . . . , `k−1 and
a generic set Sk−1 such that for any s ∈ Sk−1 and any non-α-injective lift s̃ of
s there exist subgraphs Γ0 ⊂ Γ1 ⊂ . . . ⊂ Γk−1 with the properties specified in
Claim A. Note that since the volume of Γk−1 is ≤ `k−1 , there are only finitely
many possibilities for Γk−1 and for the map f |Γk−1 : Γk−1 → Rn .
Claim B. We will now show that for any pair P := (Θ, pΘ ) consisting of a
graph Θ and a morphism pΘ : Θ → Rn there exists a constant `P and a generic set
SP ⊂ Sk−1 such that the following hold:
Suppose that f : Γ → Rn is as above, s ∈ SP , s̃ is a non-α-injective lift. Let Γk−1
be the subgraph of Γ whose existence is guaranteed by the induction hypothesis. If
P = (Γk−1 , f |Γk−1 ) then there exists a subgraph Γk of Γ containing Γk−1 such that
b(Γk ) > b(Γk−1 ) and that the volume of Γk is bounded by `P .
As there are only finitely many possibilities for P and as the intersection of
finitely many generic sets is generic, the conclusion of the inductive step for Claim A
follows from Claim B by taking `k to be the maximum of all occurring `P and taking
Sk to be the intersection of all SP .
To establish Claim B we need to show the existence of SP and `P for a fixed
pair P . Thus assume that f : Γ → Rn is as above, s ∈ Sk−1 , s̃ is a non-α-injective
lift and Γk−1 is as in the conclusion of the claim in the case k − 1 for s such that
P = (Γk−1 , f |Γk−1 ). By Theorem 3.2 there is a path γP in Rn that does not lift to
Γk−1 . Now write s̃ as a product
s0 t1 s1 · . . . · tq sq
where the ti are the path travelled in Γk−1 and where for 0 < i < q si is a nontrivial
(reduced) edge-path which does not pass through any edges of Γk−1 . Then the paths
ti do not contain a subpath that maps to γP as we assume that γP does not lift to

18

ILYA KAPOVICH AND RICHARD WEIDMANN

Γk−1 . The choice of Γ0 (see condition (3) above) implies that
q
X
i=1

|ti | ≥

β
· |s|.
6n

Proposition 4.8 implies that if s lies in the generic set SγP then q ≥ δ · |s| where
δ only depends on γP , n and α. By removing a finite subset from SγP (which
does not affect genericity of SγP ) we may assume that for every s ∈ SγP we have
δ|s| − 1 ≥ 1.
Then it follows that for the above decomposition of s̃ there exists i ∈ {1, . . . , q−1}
such that |si | ≤ |s|/(δ|s|−1). Indeed, if for all i = 1, . . . , q−1 |si | > |s|/(δ|s|−1) > 0
then
|s| ≥

q−1
X

|si | > (q − 1)|s|/(δ|s| − 1) ≥ (δ|s| − 1)|s|/(δ|s| − 1) = |s|

i=1

which is a contradiction.
Thus we can find i0 ∈ {1, . . . , q − 1} such that |si0 | ≤ |s|/(δ|s| − 1). Since
limN →∞ N/(δN − 1) = 1/δ > 0, by removing a finite set from SγP we may assume
that for every s ∈ SγP we have |s|/(δ|s|−1) ≤ 2/δ. Thus |si0 | ≤ |s|/(δ|s|−1) ≤ 2/δ.
By construction, the initial and terminal vertices of si0 are in Γk−1 = Θ, but
si0 does not traverse any edges of Γk−1 . Therefore for Γk := Γk−1 ∪ si0 we have
b(Γk ) ≥ b(Γk−1 ) + 1 ≥ (k − 1) + 1 = k. Thus the claim follows by taking `P :=
`k−1 + 2δ and SP = Sk−1 ∩ SγP . Thus Claim B is verified, which completes the
proof of Theorem 4.3.

5. Words representing bi .
Recall that we consider groups given by presentations of type
G = ha1 , . . . , an , b1 , . . . , bn |ai = ui (b), bi = vi (a)i

(*)

where n ≥ 2 and the ui and vi are freely reduced words of length N for some (large)
±1
by
N . If we now take the word/relator a−1
i ui (b) and replace all occurrences of bi
±1
vi (a) we obtain a relator in the ai . We denote by Ui the word obtained from this
word by free and cyclic cancellation. A simple application of Tietze transformations
shows that
G = ha1 , . . . , an | U1 , . . . , Un i.

(**)

We need an appropriate notion of genericity when working with groups given by
presentation (*). For A = {a1 , . . . , an }, with n ≥ 2, we think of F (A) as the set of
all freely reduced words over A±1 and we use the same convention for F (B) where
B = {b1 , . . . , bn }. Thus for N ≥ 1 there are exactly 2n(2n − 1)N −1 elements of
length N in F (A) (and same for F (B)). For N ≥ 1 we denote by T (A, N ) the set of
all n-tuples (v1 , . . . , vn ) ∈ F (A) such that |v1 | = · · · = |vn | = N . Similarly, T (B, N )
denotes the set of all n-tuples (u1 , . . . , un ) ∈ F (B) such that |u1 | = · · · = |un | = N .
Thus for every N ≥ 1 we have
n
#T (A, N ) = #T (B, N ) = 2n(2n − 1)N −1 = (2n)n (2n − 1)n(N −1) .
We denote by T (A, B, N ) the set of all 2n-tuples (v1 , . . . , vn , u1 , . . . , un ) such
that (v1 , . . . , vn ) ∈ T (A, N ) and (u1 , . . . , un ) ∈ T (B, N ). We also set T (A) =
∞
∞
∪∞
N =1 T (A, N ), T (B) = ∪N =1 T (B, N ) and T (A, B) = ∪N =1 T (A, B, N ).
Definition 5.1 (Generic sets). A subset S ⊆ F (A) is generic in F (A) if
lim

N →∞

#{v ∈ S : |v| = N }
#{v ∈ S : |v| = N }
= lim
=1
N
→∞
#{v ∈ F (A) : |v| = N }
2n(2n − 1)N −1

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

19

A property of elements of F (A) is said to hold generically if the set of all v ∈ F (A)
satisfying this property is a generic subset of F (A).
A subset Y ⊆ T (A) is called generic in T (A) if
lim

N →∞

#(Y ∩ T (A, N ))
#(Y ∩ T (A, N ))
= lim
=1
N
→∞
#T (A, N )
(2n)n (2n − 1)n(N −1)

The notions of genericity for subsets of F (B) and of T (B) are defined similarly.
A subset T ⊆ T (A, B) is called generic if
#(T ∩ T (A, B, N ))
#(T ∩ T (A, B, N ))
= 1.
= lim
N →∞
N →∞ (2n)2n (2n − 1)2n(N −1)
#T (A, B, N )
lim

Definition 5.2 (Genericity for presentations).
We say that some property P for groups given by presentation (*) holds generically if the set TP of all (v1 , . . . , vn , u1 , . . . , un ) ∈ T (A, B), such that the group
G = ha1 , . . . , an , b1 , . . . , bn |ai = ui , bi = vi , for i = 1, . . . , ni satisfies P, is a generic
subset of T (A, B).
The following fact is a straightforward consequence of known results about genericity. Lemma 5.3 below is essentially a reformulation of the fact that a generic presentation with a fixed number of generators and a fixed number of defining relations
satisfies arbitrarily strong small C 0 (λ) cancellation condition, see [AO, A, KS, M].
Lemma 5.3. Let 0 < α < 1 be arbitrary. Then there is a generic subset T ⊆
T (A, B) such that for every τ = (v1 , . . . , vn , u1 , . . . , un ) ∈ T with |v1 | = · · · =
|vn | = |u1 | = · · · = |vn | = N the following hold:
For every freely reduced z ∈ F (A) with |z| ≥ αN there exists at most one i ∈
{1, . . . , n} and at most one  ∈ {1, −1} such that z is a subword of vi . Moreover,
in this case there is at most one occurrence of z inside vi . Also, the same property
holds for every freely reduced z 0 ∈ F (B) with |z 0 | ≥ αN with respect to the words
u1 , . . . , un .
Lemma 5.3 implies in particular that generically there is very little cancellation
between the vi (a)±1 , and thus Ui is essentially just the concatenation of the vi (a)±1
introduced. The following statement is a straightforward consequence of standard
small cancellation arguments; see [AO, A, KS, M] for similar arguments.
Lemma 5.4. Generically the following hold:
1
(1) |Ui | ≥ N 2 (1 − 1010
n ) for 1 ≤ i ≤ n.
2ε1
1
(2) If W is a subword of length N 2 · 1010
and Uj2ε2 whose initial
n of both Ui
2ε1
2ε2
letter lies in the first half of Ui , respectively Uj , then i = j, ε1 = ε2
and the two occurrences of W in Uiε1 coincide, i.e. start at the same letter
of Uiε1 .
We refer the reader to [LS, O, Str] for basic results of small cancellation theory
and basic properties of small cancellation groups.
Lemma 5.3 implies that for any fixed L ≥ 1, generically, the above presentation
(*) is a C 0 ( L1 )-small cancellation presentation (note that the defining relations in
(*) are already cyclically reduced). This implies that for any α ∈ [0, 1) we may
assume that for any word in the a±1
and b±1
that represents the trivial element
i
i
in G there exists a subword R such that |R| ≥ α|RT −1 | where RT −1 is a cyclic
conjugate of a defining relator. In this case we call the process that replaces the
subword R by (its complementary word) T an α-small cancellation move (relative
to the relator RT −1 ). We will also consider α-small cancellation moves relative
to relators that are not cyclic conjugates of defining relators of (*); in particular
relative to the Ui , the defining relators of (**).

20

ILYA KAPOVICH AND RICHARD WEIDMANN

Lemma 5.5. Let α ∈ [0, 1). Let w be a reduced word in the a±1
such that w =G bi .
i
Then for generic G either w = vi or w admits a α-small cancellation move relative
to some cyclic conjugate of some Ui±1 .
In particular w can be transformed into vi by applying finitely many α-small
cancellation moves relative to cyclic conjugates of the relators Ui±1 and by free
cancellation.
Proof. This lemma can also be proven using the small cancellation properties of
(**); however we argue using the presentation (*).
The above discussion implies that the word b−1
i w can be transformed into the
trivial word by replacing subwords that are almost whole relators by the complementary word of the relator. If w 6= vi then this process can initially only involve
small cancellation moves relative to the relators b−1
i vi (a) as w is a word in the ai
and therefore b−1
w
does
not
contain
long
subwords
of the relators a−1
i
i ui (b).
±1
These initial moves introduce letters of type bj and possible remove the initial
±1
letter b−1
that were introi . Subsequent move of that type cannot remove the bj
duced as otherwise the original word w would have been non-reduced contradicting
the hypothesis.
We perform these moves as long as possible, in the end we must have a long word
in the bi with at most one ai in between that allows for a small cancellation move
with respect to some relation a−1
i ui (b) but then before the original moves almost
all of a cyclic conjugate of Ui must have occurred as a subword, indeed the origianl
subword can be obtainded by resubstituing the vi (a) for the bi , which gives almost
all of some Ui by definition of the Ui .

We also need to establish several basic algebraic properties of groups G given by
generic presentation (*). The proof of the following theorem follows the argument
of Arzhantseva and Ol’shanskii [AO, A] (see also [KS]).
Theorem 5.6. Let n ≥ 2. Then for the group G given by a generic presentation
(*) the following hold:
(1) Every subgroup of G, generated by ≤ n − 1 elements of G, is free.
(2) rank(G) = n.
(3) G is torsion-free, word-hyperbolic and one-ended.
Proof. By genericity of (*), given any 0 < λ < 1 we may assume that (∗) satisfies
the C 0 (λ) small cancellation condition.
(1) Choose a subgroup H ≤ G of rank ≤ n − 1. Thus H = hh1 , . . . , hk i ≤ G for
some h1 , . . . , hk ∈ G such that k ≤ n − 1.
Therefore there exists a finite connected graph Γ (e.g. a wedge of k circles labelled
by reduced words in A ∪ B representing h1 , . . . , hk ) with positively oriented edges
labelled by elements of A ∪ B such that the first Betti number of Γ is ≤ k and
such that for the natural “labeling homomorphism” µ : π1 (Γ) → G the subgroup
µ(π1 (Γ)) ≤ G is conjugate to H in G. Among all such graphs choose the graph Γ
with the smallest number of edges. Then, by minimality Γ is a folded core graph.
Since b(Γ) ≤ n − 1, Theorem 4.3 is applicable to Γ.
If µ : π1 (Γ) → G is injective, then H ∼
= π1 (Γ) is free, as required. Suppose
therefore that µ is non-injective. Then there exists a nontrivial closed circuit in Γ
whose label is a cyclically reduced word equal to 1 in G. Therefore there exists a
path γ̂ in Γ such that the label ẑ of γ̂ is a subword of some a cyclic permutation of
some defining relation r of (*) and that |ẑ| ≥ (1 − 3λ)|r| ≥ (1 − 3λ)N .
Without loss of generality, and up to a possible re-indexing, we may assume that
r is a cyclic permutation of b−1
1 v1 (a). Then ẑ contains a subword z such that z is

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

21

also a subword of v1 and that |z| ≥ ( 12 − 32 λ)|r| − 1. Thus we may assume that
9
|z| ≥ 20
|r|.
Let γ be the subpath of γ̂ corresponding to the occurrence of z in ẑ. This implies
9
|r|, so that |r| ≤ 20
that |γ| = |z| ≥ 20
9 |γ|.
By genericity of (*) and by Theorem 4.3 we may assume, given an arbitrary
0 < α0 < 1, that γ̂ is α0 -injective. Since γ comprises almost a half of γ̂, it follows
that almost all edges of γ are γ̂-injective. Therefore, for any fixed 0 < α < 1,
no matter how close to 1, we may assume that the portion of γ corresponding to
γ̂-injective edges of γ covers the length ≥ α|γ|. We choose 0 < α < 1 and 0 < λ < 1
so that (9n − 12)λ 20
9 < α.
There are at most 3(n − 1) − 3 = 3n − 6 maximal arcs of Γ. These maximal
0
arcs subdivide γ as a concatenation of non-degenerate arcs γ = γ00 γ10 . . . γm
where
0
0
for i 6= 0, m γi is a maximal arc of Γ and for i = 0, m γi is either maximal or
0
semi-maximal arc in Γ. The paths γ00 and γm
may, a priori, overlap in Γ which
0
happens if the initial vertex of γ is contained in the interior of γm
and the terminal
0
0
0
vertex of γ is contained in the interior of γ0 . By subdividing γ0 and γm
along the
initial and terminal vertices of γ if needed, we obtain a decomposition of γ as a
concatenation of nondegenerate arcs of Γ
γ = γ 0 . . . γk
such that for 2 ≤ i ≤ k − 3 the path γi is a maximal arc of Γ and such that for i 6= j
either γi = γj±1 or γi and γj have no topological edges in common. Let τ1 , . . . , τq be
all the distinct arcs in Γ given by the paths γ0 . . . γk Since Γ has ≤ 3n − 6 maximal
arcs, we have q ≤ 3n − 4. Recall that the sum of the lengths of γi such that the arc
γi is γ̂-injective, is ≥ α|γ|.
Suppose first that there exists i0 such that γi0 is γ̂-injective and that |γi0 | > 3λ|r|.
Then we remove the arc corresponding to γi0 from Γ and add an arc τ from the
terminal vertex of γ̂ to the initial vertex of γ̂ with label ŷ such that ẑ ŷ is a cyclic
permutation of r. Thus |ŷ| = |τ | < 3λ|r|. Denote the new graph by Γ0 . Then the
image of the labelling homomorphism π1 (Γ0 ) → G is still conjugate to H, but the
number of edges in Γ0 is smaller than the number of edges in Γ. This contradicts
the minimal choice of Γ. Therefore no i0 as above exists.
Thus for every i such that γi is a γ̂-injective arc we have |γi | ≤ 3λ|r|. Hence the
total length covered by the γ̂-injective γi is
≤ (3n − 4) · 3λ|r| ≤ (9n − 12)λ

20
|γ| < α|γ|,
9

yielding a contradiction.
Therefore µ : π1 (Γ) → G is injective, and H ∼
= π1 (Γ) is free, as required.
(2) From presentation(*) we see that G = ha1 , . . . , an i. Thus rank(G) ≤ n.
Suppose that k := rank(G) < n. Then, by part (1), G is free of rank k < n.
Hence there exists a graph Γ with edges labelled by elements of A ∪ B such
that the first betti number of Γ is ≤ k and such that the image of the labelling
homomorphism µ : π1 (Γ) → G is equal to G. Among all such graphs choose Γ with
the smallest number of edges. By minimality, Γ is a folded core graph.
Since the first betti number of Γ is ≤ k < n, there exists a letter x ∈ A ∪ B
such that Γ has no loop-edge labelled by x. Without loss of generality we may
assume that x = a1 . Since the image of µ is equal to G, there exists a reduced
path γ̃ in Γ of length > 2 whose label z̃ is a freely reduced word equal to a1 in
−1
G. Thus z̃a−1
is freely reduced, it follows
1 =G 1. Whether or not the word z̃a1
that γ̃ contains a subpath γ with label z such that z is also a subpath of a cyclic
permutation of some defining relation r of (*) with |γ| = |z| ≥ (1 − 3λ)|r| − 1. Then

22

ILYA KAPOVICH AND RICHARD WEIDMANN

exactly the same argument as in the proof of (1) yields a contradiction with the
minimal choice of Γ.
Thus rank(G) < n is impossible, so that rank(G) ≥ n. Since we have already
seen that rank(G) ≤ n, it follows that rank(G) = n, as required.
(3) The group G is given by presentation (**) as a proper quotient of Fn . Since
Fn is Hopfian, it follows that G is not isomorphic to Fn . The fact that rank(G) = n
implies that G is not isomorphic to Fr for any 1 ≤ r ≤ n − 1. Thus G is not free.
Also, since (*) is a C 0 (1/6) small cancellation presentation for G where the
defining relators are not proper powers, basic small cancellation theory [LS] implies
that G is a torsion-free non-elementary word-hyperbolic group.
We claim that G is one-ended. Indeed, suppose not. Since G is torsion free and
not cyclic, Stalling’s theorem then implies that G is freely decomposable, that is G =
G1 ∗ G2 where both G1 and G2 are nontrivial. Therefore by Grushko’s Theorem,
n = rank(G) = rank(G1 ) + rank(G2 ) and hence 1 ≤ rank(G1 ), rank(G2 ) ≤ n − 1.
Part (1) of the theorem then implies that G1 and G2 are free. Hence G = G1 ∗ G2 is
also free, which contradicts part (2). Thus G is indeed one-ended, as claimed. 
Remark 5.7. The proof of Theorem 5.6 can be elaborated further, following
a similar argument to that of [KS], to prove the following: For G given by a
generic presentation (*), if g1 , . . . , gn ∈ G are such that hg1 , . . . , gn i = G then
(g1 , . . . , gn ) ∼N E (a1 , . . . , an ) or (g1 , . . . , gn ) ∼N E (b1 , . . . , bn ) in G.
6. Reduction moves
Recall that for A = {a1 , . . . , an } we think of F (A) as the set of all freely reduced
words over A±1 .
We say that a word z ∈ F (A) is a U -word if z is a subword of of a power of some
Ui±1 (where Ui are the defining relators for the presentation (**)). Recall that by
1
Lemma 5.4 any U -word of length at least N 2 · 1010
n is a subword of a power of only
±1
one Ui . We say that a word V is U -complementary to a U -word W if W V −1 is a
power of a cyclic conjugate of some Ui±1 . Note that V is then also a U -word. Note
also that for a given U -word W , its U -complementary word is not uniquely defined.
Thus if W is an initial segment of U∗k , where k 6= 0 and U∗ is a cyclic permutation
of Ui±1 , and V is U -complimentary to W then for every integer m such that mk < 0
the word U∗m V is also U -complimentary to W .
We now introduce a partial order on F (A). First, for w ∈ F (A) we define c1 (w)
to be the minimum k such that w can be written as a reduced product of type
w1 · . . . · wk where each wi is a U -word. We call any such decomposition of w as
a product of c1 (w) U -words an admissible decomposition and we call the words
w1 , . . . , wk the U -factors of this admissible decomposition.
The number c1 (w) can be interpreted geometrically in the Cayley complex CC of
the presentation (**): If k = c1 (w), w1 · . . . · wk is as above and γw is a path reading
w then each wi is read by a subpath of γw that travels (possibly with multiplicity)
along the boundary of a 2-cell of CC.
Note that admissible decompositions are not unique. However the following
statement shows that the degree of non-uniqueness for admissible decompositions
can be controlled:
Lemma 6.1. Let w ∈ F (A), k = c1 (w) and let w = w1 · . . . · wk = w10 · . . . · wk0 be
admissible decompositions of w. Then the following hold:
(1) The subwords wi and wi0 overlap non-trivially in w for all i ∈ {1, . . . , k}.

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

23

(2) If V is the minimal subword of w that contains both wi and wi0 then both
wi and wi0 contain the subword V 0 obtained from V by removing the initial
1
2
and terminal subword of length 1010
nN .
(3) If wi is subword of a power of Ujε of length at least 1015 n N 2 then wi0 is
also a subword of a power of Ujε and the common subword of wi and wi0
differs from wi and wi0 by at most an initial and terminal segment of length
1
2
1010 n N .
Proof. (1) Suppose that this does not hold, i.e. that for some i ∈ {1, . . . , k} the
words wi and wi0 do not overlap. Without loss of generality we assume that wi comes
0
before wi0 when reading w. Therefore wi0 wi+1
·. . . wk0 is a subword of wi+1 wi+2 ·. . .·wk ,
0 0
0
and, in particular, wi wi+1 · . . . wk is a product of k − i U -words. It then follows
that w is product of (i − 1) + (k − i) = k − 1 U -words, contradicting the definition
of c1 (w).
(2) Suppose that the conclusion of part (2) of the lemma does not hold. Without
loss of generality we may assume that w1 · . . . · wi−1 has a suffix w̄i of length at
1
2
0
least 1010
n N that is a prefix of wi . The subword w̄i is in fact a suffix of wi−1 as
0
otherwise wi−1 and wi−1 do not overlap, contradicting (1).
Thus wi−1 = uw̄i for some word u and wi0 = w̄i v for some word v. Now as
1
2
wi−1 and wi0 are U -words and w̄i is of length at least 1010
n N , it follows from
Lemma 5.4(2) that z = uw̄i v is a U -word. It follows that
0
w = w1 · . . . wi−2 zwi+1
· . . . wk0 ,

contradicting the assumption that k = c1 (w).
(3) This part follows immediately from the arguments used to prove (1) and (2)
together with Lemma 5.4(2).

Now let w be a freely reduced word over {a1 , . . . , an }±1 with c1 (w) = k. For
1 ≤ i ≤ k we will define a number `w (i) that essentially measures the length of the
i-th factor in an admissible decomposition of w, provided this factor is almost of
length N 2 . The precise definition of `w (i) is independent of the chosen admissible
decomposition of w and is more robust under certain modifications of w that we
will introduce later on.
Lemma 6.2. Let w ∈ F (A) and k = c1 (w). Fix i ∈ {1, . . . , k}. Choose an
admissible decomposition w = w1 · . . . · wk of w. Suppose that for some j 6= i the
subword wj is a maximal U -subword of w with |wj | ≥ 1013 n N 2 . Choose a word
w̄j that is U -complementary to wj that is also of length at least 1013 n N 2 and let
w̄ := w1 · . . . wj−1 w̄j wj+1 · . . . · wk .
Then the following hold:
(1) w̄ is freely reduced.
(2) w̄j is a maximal U -subword of w̄.
(3) c1 (w̄) = c1 (w).
Proof. (1) and (2) follow from the maximality of the U -subword wj and the fact
that w is reduced and that wj w̄j−1 is cyclically reduced. (3) follows from (1) and (2)
as the assumption on the length of wj and w̄j together with Lemma 6.1(3) imply
that we can find admissible decompositions of w and w̄ such that wj , respectively
w̄j , occur as factors.

For every k ≥ 1 denote by F (A; k) the set of all w ∈ F (A) with c1 (w) = k.
Definition 6.3 (i-equivalence). If w ∈ F (A; k), i ∈ {1, . . . , k} and w̄ is obtained
from w as in Lemma 6.2, we say that w̄ is elementary i-equivalent to w. Lemma 6.2
implies that w̄ ∈ F (A; k).

24

ILYA KAPOVICH AND RICHARD WEIDMANN

We further say that w ∈ F (A; k) is i-equivalent to a word w0 ∈ F (A) if w can be
transformed into w0 by applying finitely many elementary i-equivalences (note that
in this definition the value of the index i is fixed). Thus for every i ∈ {1, . . . , k}
i-equivalence is equivalence relation on F (A; k).
Lemma 6.4. Suppose that w, w0 ∈ F (A; k) are i-equvalent for some 1 ≤ i ≤
c1 (w) = c1 (w0 ) and that w = w1 · . . . · wk and w0 = w10 · . . . · wk0 are admissible
decompositions of w, respectively w0 . Then the following hold:
(1) There exists a word V ∈ F (A) such that wi = xV y and wi0 = x0 V y 0 where
x, y, x0 , y 0 are words of length at most 10110 · N 2 .
(2) The lengths of wi and wi0 differ at most by 10210 · N 2 .
Proof. This statement follows from the fact that an elementary i-equivalence that
modifies a wj only affects the adjacent factors and increases or decreases their length
1
2
by at most 1010
n N by Lemma 6.1, and that another such elementary i-equivalence
applied to the j-th factor reverses theses changes.

Definition 6.5 (Complexity of a word in F (A)). Let w ∈ F (A), k = c1 (w). For
each i ∈ {1, . . . , k} we define `ˆw (i) to be the maximum over all |wi | where wi is the
i-th factor in some admissible decomposition of a word w0 that is i-equivalent to w.
Note that part (2) of Lemma 6.4 implies that `ˆw (i) < ∞.
We further define `w (i) = 0 if `ˆw (i) < (1 − 1013 n )N 2 and `w (i) = `ˆw (i) otherwise.
Note that `w (i) = `w̄ (i) if w and w̄ are i-equivalent. We now define
c2 (w) := `w (1) + . . . + `w (c1 (w)).
For w ∈ F (A) we define the complexity of w as c(w) = (c1 (w), c2 (w)) and order
complexities lexicographically. This order is a well-ordering on F (A)
It is not hard to verify that an α-small cancellation move relative to Uj for α
close to 1 decreases the complexity. We will need the following generalization of
this fact:
Lemma 6.6. Let w ∈ F (A) be a reduced word and let W ∈ F (A) be a U -word of
1
N 2 . Suppose that w has (as a word) a reduced product decomposition of
length 100n
type
w = x0 W ε1 x1 W ε2 · . . . W εq xq
with εt ∈ {−1, 1} for 1 ≤ t ≤ q. Choose V such that W V −1 is a cyclic conjugate
of some Uj±1 and let w0 be the word obtained from the word x0 V ε1 x1 V ε2 · . . . V εq xq
by free reduction. Then the following hold:
(1) c(w0 ) ≤ c(w).
(2) If one of the subwords W εi is contained in a U -subword of w of length at
least (1 − 1014 n )N 2 , then c(w0 ) < c(w).
Proof. We will first observe that we may choose an admissible decomposition w =
w1 · . . . · wk (with k = c1 (w)) such that any subword W εt of w occurs inside some
factor wj of w. Indeed in any admissible decomposition of w the subword W εt can
overlap with at most 3 U -factors of w, as otherwise an admissible decomposition
of w with fewer U -factors can be found. Thus W εt overlaps with some factor in
1
N 2 . Because of Lemma 6.1, we can expand this
a subword of length at least 300n
εt
factor to contain W . The claim follows by making this modifications for all W εt .
Let now w = w1 · . . . · wk be an admissible decomposition such that any subword
W εi occurs inside some factor wj of w. Note that possibly several W εt occur inside
the same wj . Note also that if some W εt is contained in a U -subword x of length at
least (1 − 1014 n )N 2 then it is a subword of some wj of length at least (1 − 1024 n )N 2 .

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

25

This conclusion can be established by first observing that by the argument before
another admissible decomposition w = z1 · . . . · zk (with U -factors zi ) can be chosen
such that x is contained in some zj , and then applying Lemma 6.1.
Replacing the W εt by the V εt inside each wj and performing free reduction
yields a new word wj0 , which is again a U -word. The word w0 is then obtained
from w10 · . . . · wk0 by free reduction. This construction implies, in particular, that
c1 (w0 ) ≤ c1 (w).
Thus we may assume that c1 (w) = c1 (w0 ) = k as there is nothing to show
otherwise. To prove the lemma it suffices to show that `w (i) ≥ `w0 (i) for all
1 ≤ i ≤ k and that `w (i) > `w0 (i) for some 1 ≤ i ≤ k if condition (2) is satisfied.
If condition (2) of the lemma is satisfied, there exists some factor wi of length
at least (1 − 1024 n )N 2 that contains one of the W εt . Therefore it is sufficient to
consider the following two cases:
Case 1: Suppose that wi contains at least one of the words W εt . Note that
`ˆw (i) = `w (i) ≥ N 2 if wi contains more than one such word.
Note first that `w0 (i) = 0 if `w (i) = 0, since the word obtained from wi be
replacing W ±1 with V ±1 followed by free cancellation is of length at most (1 −
2
1
2
2
100n )N and since i-equivalence cannot increase this length by more than 1010 n N
by Lemma 6.4.
If `w (i) 6= 0 then the replacements of W ±1 with V ±1 decrease the length of wi
2
2
0
by more than 1010
n N . Thus it follows from Lemma 6.4 that `w (i) < `w (i). This
holds in particular if wi is of length at least (1 − 1024 n )N 2 , which (by the above
discussion) is guaranteed to occur if condition (2) is satisfied.
Case 2:
Suppose that wi contains no subword W εt . To conclude the proof,
we need to show that `w (i) ≥ `w0 (i). Note that for any admissible decomposition
z1 · . . . · zk the words wi and zi have a non-trivial common subword that is not
touched by the replacement and free cancellations when going from w to w0 , since
otherwise c1 (w0 ) < k; this follows as in the proof of Lemma 6.1(1).
If w is i-equivalent to w0 then there is nothing to show as `w (i) = `w0 (i) by the
definition of `(i). However it may happen that w and w0 are not i-equivalent as
some of the U -words wj may be replaced by U -words that are too short for the
replacements to qualify as i-equivalences. This is the reason why the argument for
treating Case 2 is slightly more subtle.
Choose a word w00 that is i-equivalent to w0 such that w00 realizes `ˆw0 (i), i.e.
that w00 has an admissible decomposition w100 w200 · . . . · wk00 such that |wi00 | = `ˆw0 (i). It
suffices to establish:
Claim: The word w is i-equivalent to a word w̃ that has an admissible decomposition w̃1 w̃2 · . . . · w̃k such that |w̃i | = |wi00 |.
Indeed, the existence of such a word w̃ implies that
`ˆw (i) ≥ |w̃i | = |wi00 | = `ˆw0 (i)
which implies that `w (i) ≥ `w0 (i).
To verify the Claim, we first construct a word ẇ that is i-equivalent to w in the
following way: Start with w and perform the same replacements as when going from
w to w0 , but whenever one of the replacements results in a maximal U -subword v
of length less than 13 N 2 , multiply it with a cyclic conjugate of the appropriate Uj±1
to obtain a U -word longer than 13 N 2 that has v as both initial and terminal word
and such that the replacement is an elementary i-equivalence.
Call the resulting word ẇ. Note that ẇ is i-equivalent to w and all words that
occur as the i-th factors in any admissible decomposition of w0 also occur as i-th
factors in an admissible decomposition of ẇ. Now all elementary i-equivalences that

26

ILYA KAPOVICH AND RICHARD WEIDMANN

need to be applied to w0 to obtain w00 can be applied to ẇ. We obtain a word that
is i-equivalent to ẇ and that has wi00 as the i-th U -word. This proves the Claim
and completes the proof of the lemma.

7. Proof of the Main Theorem
In this section we establish Theorem A from the Introduction:
Theorem 7.1. Let n ≥ 2 be arbitrary. Then for the group G given by a generic presentation (*), the group G is torsion-free, word-hyperbolic, one-ended of rank(G) =
n, and the (2n−1)-tuples (a1 , . . . , an , 1, . . . 1) and (b1 , . . . , bn , 1, . . . 1) are not Nielsenequivalent in G.
Let G be given by a generic presentation (*). By Theorem 5.6 we know that G
is torsion-free, word-hyperbolic, one-ended and that rank(G) = n.
For a (2n − 1)-tuple τ = (w1 , . . . , w2n−1 ) of freely reduced words in F (A) define
the complexity c(τ ) of τ as
c(τ ) := (c(w1 ), . . . , c(wn )).
We order complexities lexicographically. Note that in this definition we completely
disregard the words wn+1 , . . . , w2n−1 .
We argue by contradiction. Suppose that the conclusion of Theorem 7.1 fails
for G, so that the (2n − 1)-tuples (a1 , . . . , an , 1, . . . 1) and (b1 , . . . , bn , 1, . . . 1) are
Nielsen-equivalent in G.
Then there exist elements x1 , . . . , x2n−1 in F (A) such that the (2n − 1)-tuple
(x1 , . . . , x2n−1 ) is Nielsen equivalent in F (A) to the (2n−1)-tuple (a1 , . . . , an , 1, . . . , 1)
and such that for some permutation σ ∈ Sn we have xi =G bσ(i) for 1 ≤ i ≤ n.
Minimality assumption: Among all (2n − 1)-tuples (x1 , . . . , x2n−1 ) of freely
reduced words in F (A) with the above property choose a tuple (x1 , . . . , x2n−1 ) of
minimal complexity.
This minimality assumption implies that c(xi ) ≤ c(xi+1 ) for i = 1, . . . , n − 1.
After a permutation of the bi we may moreover assume that σ = id. We fix
this minimal tuple (x1 , . . . , x2n−1 ) for the remainder of the proof. The minimality
assumption plays a crucial role in the argument and ultimately it will allow us to
derive a contradiction.
We choose k maximal such that xi = vi in F (A) for 1 ≤ i ≤ k. By convention if
x1 =
6 v1 , we set k = 0.
Note that if k < n (which we will show below) then it follows from Lemma 5.5
that xk+1 admits an α-small cancellation move relative to some Uj for α close to 1.
1
This implies in particular that we may assume that xk+1 is of length at least 99n
N 2.
Let now Γ be the wedge of 2n − 1 circles, wedged at a vertex pΓ , such that the
i-the circle is labeled by the word xi for 1 ≤ i ≤ 2n − 1. By assumption the xi form
a generating set of F (A), thus the natural morphism f from Γ to the rose Rn is
π1 -surjective as the loops of Γ map to a generating set of π1 (Rn ). It follows that Γ
folds onto Rn by a finite sequence of Stallings folds. Thus there exists a sequence
of graphs
Γ = Γ0 , Γ1 , . . . , Γl = Rn
and Stallings folds fi : Γi−1 → Γi for 1 ≤ i ≤ l such that f = fl ◦ . . . ◦ f1 . We may
choose this folding sequence such that we do not apply a fold that produces a lift
of Rn in Γi if another fold is possible. Choosing ∆ to be the last graph in such
a folding sequence that does not contain a lift of Rn it follows that there exists a
graph ∆ with the following properties:
(1) There exists a map f∆ : Γ → ∆ such that f : Γ → Rn factors through f∆ .

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

27

(2) ∆ does not contain a lift of Rn .
(3) Any fold applicable to ∆ produces a lift of Rn , thus ∆ contains a connected
subgraph Ψ with at most n + 2 edges that folds onto Rn .
Put p∆ := f∆ (pΓ ). Thus the petal-circles of Γ get mapped to closed paths based
at p∆ .
As the Betti number of ∆ is bounded by 2n − 1 and as ∆ folds onto Rn it follows
that ∆ does not contain a 2-sheeted cover of Rn . Indeed such a 2-sheeted cover
would be of Betti number 2n − 1 and therefore be the core of ∆ which implies that
∆ does not fold onto Rn . It follows that the hypothesis of Theorem 4.3 is satisfied
for ∆. Thus for α arbitrarily close to 1 we may assume that any lift of of the path
γvi in Rn with label vi = vi (a) to ∆ is α-injective.
Lemma 7.2. We have k < n.
Proof. For i ∈ {1, . . . , k} the i-th loop of Γ maps to the path γvi in Rn . Thus the
i-th loop of Γ maps to a path in ∆ that is a lift of γvi , thus by Theorem 4.3 we can
assume that this image in ∆ is α-injective for α arbitrarily close to 1.
This implies that for 1 ≤ i ≤ k the image of the i-th loop of Γ in ∆ contains an
1
1
|vi | = 100n
N as the image of σi is the union of at
arc σi of ∆ of length at least 100n
most 6n arcs of ∆. By genericity these arcs are travelled only once by the first k
loops, in particular they are pairwise distinct. Moreover they are disjoint from Ψ.
It follows that there exists a connected subgraph Ψ̄ of ∆ containing Ψ such that
the arcs σi meet Ψ̄ only in their endpoints. As the Betti number of Ψ is at least n
it follows that the the subgraph of ∆ spanned by Ψ̄ and the σi has Betti number
n + k. As ∆ has Betti number at most 2n − 1 this implies that k ≤ n − 1 < n. 
We now continue with the proof of Theorem 7.1.
Recall that Ui was obtained from the generic word a−1
i ui (b) by replacing each bj
by the respective vj (a). The genericity of the vj implies that there is very little cancellation in a freely reduced word in the vj , thus Ui is essentially the concatenations
of a−1
and the words vj that were introduced to replace the letters b1 , . . . , bn .
i
For each vj let vj0 be the subword of vj obtained by chopping-off small initial
and terminal segments of vi and such that for every occurrence of bj in a−1
i ui (b)
the word vj0 survives without cancellation when we replace b1 , .., bn by v1 , .., vn in
ai−1 ui (b) and then freely and cyclically reduce to obtain Ui .
As the cancellation is small relative to the length of the vj it follows that vj0
is almost all of vj . Moreover, we can choose vj0 so that |v10 | = · · · = |vn0 | = N 0 .
Choosing the vj from the appropriate generic set, we may assume that N ≥ N 0 ≥
N (1 − 0 ) for any fixed 0 < 0 < 1.
By Theorem 4.3 and by the genericity of the presentation (*), for any 0 < α0 < 1
we may assume that the conclusion of Theorem 4.3 holds for the words vj . It
follows that for any given 0 < α < 1 we may also assume that the words vj0
satisfy the conclusion of Theorem 4.3 as well. Indeed if we choose α0 = 12 (1 + α)
and 0 = 12 (1 − α) then any image of vj0 in some graph as in the hypothesis of
Theorem 4.3 contains at least α0 · N − 0 · N = α · N ≥ α · |vi0 | = αN 0 distinct
topological edges, so that the path corresponding to vj0 in the graph in question is
α-injective.
It follows from Lemma 5.5 that xk+1 , the label of the (k + 1)-st loop, admits an
α-small cancellation move with respect to some U
 i with α close to 1. Thus xk+1
contains a subword Z of length at least 1 − 1014 n N 2 that is a subword of a cyclic
conjugate of some Ui . After dropping a short suffix and prefix we can assume that Z
is a reduced product of remnants of some vj±1 in Ui , and each such remnant contains
the corresponding (vj0 )±1 . We refer to the sub-words (vj0 )±1 of Z (understood both

28

ILYA KAPOVICH AND RICHARD WEIDMANN

as words and as positions in Z where they occur) arising in this way as v-syllables
of Z. Denote the arc in the (k + 1)-st loop of Γ that corresponds to Z by s̃Z . Note
that Z is readable in ∆ since Z is the label of the path sZ := f∆ (s̃Z ).
Convention 7.3. We fix the word Z, the arc s̃Z in Γ and its image sZ in ∆ for
the remainder of the proof of Theorem 7.1.
In the following two lemmas we will establish some important properties of the
word Z and of the path sZ .
Lemma 7.4. For 1 ≤ j ≤ n there exists a non-trivial distinguished subword ṽj of
vj0 (this means both the abstract word and the position in vj0 where it occurs) such
that the following hold:
(1) For any v-syllable (vj0 ) of Z with corresponding subword ṽj the subpath of
sZ corresponding to ṽj is contained in an arc of ∆\Ψ. (This means the
word ṽj is read on an arc of ∆\Ψ).
(2) If 1 ≤ j1 , j2 ≤ n, j1 6= j2 and (vj0 1 ) and (vj0 2 )δ are two v-syllables of Z,
then the subpaths of sZ corresponding to their distinguished subwords ṽj1
and ṽjδ2 have no topological edges in common.
(3) Similarly, if 1 ≤ j ≤ n and v 0 , v 00 are two distinct (i.e. appearing in
different positions in Z) v-syllables of Z both representing (vj0 ) and (vj0 )δ ,
then the subpath of sZ corresponding to the distinguished subword (ṽj ) ,
(ṽj )δ are either disjoint or coincide if  = δ and are inverses if  = −δ.
Proof. For a finite graph Λ let f (Λ) be the number of paths e1 , . . . , ek in Λ such
that {ei , e−1
6 {ej , e−1
6 {1, k}. Thus f (Λ) is
i } =
j } for i 6= j ∈ {1, . . . , k} and {i, j} =
the number of path that travel no topological edge twice except possibly that the
first and the last edges may agree. Let f (n) be the maximal f (Λ) where Λ is a
graph with the following properties:
(1) There exists a vertex v ∈ V Λ such that (Λ, v) is a core graph with respect
to v of Betti number at most 2n − 1.
(2) Λ has no valence-2 vertex.
Choose α = α(n) < 1 (close to 1) and d = d(n) > 0 (close to 0) such that
1
.
2
As noted above, by genericity we may assume that any path corresponding to vj0 is
α-injective. Moreover by Lemma 5.3 we may assume that vj0 does not contain any
word of length d(n) · |vj0 | twice. Let Ψ0 be the union of all maximal arcs of ∆ of
length less than d(n)|vj0 | = d(n)N 0 . Note that Ψ0 contains Ψ.
For j = 1, . . . , n we say that a reduced decomposition
f (n) · ((1 − α) + 6 · n · d(n)) ≤

(!)
is basic
hold:
(1)
(2)
(3)

vj0 = y0 p1 y1 . . . pm ym
if m ≥ 1 and there exists a way to read vj0 in ∆ such that the following

|pt | ≥ d(n) · |vj0 | = d(n)N 0 for 1 ≤ i ≤ m and pt is read on an arc of ∆ \ Ψ0 .
For 1 ≤ t ≤ m − 1 each yt is read Ψ0 .
y0 = y00 y000 where y000 is read in Ψ0 , y00 is read on an arc (possibly degenerate)
of ∆ \ Ψ0 and |y00 | < d(n)N 0 .
0 00
0
00
(4) ym = ym
ym where ym
is read in Ψ0 , ym
is read on an arc of ∆ \ Ψ0 and
00
0
|ym | < d(n)N .
For a basic decomposition (!) of vj0 , we say that a path β in ∆ corresponding to
reading vj0 in ∆ as in the above definition, is a basic path representing (!).

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

29

Note that the yt may or may not be degenerate, i.e. may be single vertices of
∆. Note that whenever vj0 can be read in ∆ then the corresponding path is a basic
path corresponding to a basic decomposition. This implies that any subpath of sZ
corresponding to a subword of type vj0±1 is a basic path corresponding to a basic
decomposition.
Note that (2) implies that that the word pt is read along a maximal arc of ∆ \ Ψ0
if 2 ≤ t ≤ m − 1.
Moreover for any t1 6= t2 and {t1 , t2 } =
6 {1, m} the subpaths of β corresponding
to pt1 and pt2 have no topological edges in common by the choice of d(n). The
subpath corresponding to pm can overlap the subpath corresponding to p1 in a
subpath of length at most d(n)N 0 if they lie on the same arc of ∆ \ Ψ0 .
ˆ be the graph obtained from ∆ by collapsing all connected components
Let now ∆
of Ψ0 to points. If (!) is a basic decomposition of Vj0 and β is a basic path in ∆
00
ˆ is a path β̂ with label y 0 · p1 · . . . · pm · ym
representing (!), then the image of β in ∆
.
0
0
Moreover, the path β̂ is (d(n) · N )-almost edge-simple, that is, it travels at most
ˆ more than once. Note also that b1 (∆)
ˆ ≤ n − 1. Since
d(n) · N 0 topological edge of ∆
ˆ
ˆ
ˆ
(∆, p∆
ˆ ) is a core pair where p∆
ˆ is the image of p∆ in ∆, it now follows that ∆ has
at most 3n − 1 maximal arcs. Therefore for any basic decomposition (!) we have
m ≤ 3n as distinct pi lie on distinct maximal arcs, with the possible exception of
p1 and pm lying on the same maximal arc.
The number of tuples (p1 , . . . , pm ) (with each pt is understood as a subword
of vj0 occurring in a specific position in vj0 ) arising in basic decompositions of a
˜ be the
given vj0 , is bounded above by f (n). This can been as follows: Let ∆
ˆ
˜
graph obtained from ∆ by replacing maximal arcs by edges, ∆ has no vertex of
˜ where ei
valence 2. Now any tuple (p1 , . . . , pm ) gives rise to a path e1 , . . . , em in ∆
is the edge obtained from the arc on which pi was read by the basic path. This path
satisfies the condition given in the definition of f (n), and therefore there are at most
˜ ≤ f (n) different paths that occur. Each such path (e1 , . . . , em ) determines a
f (∆)
unique tuple (p1 , . . . , pm ): That pi is determined by ei is obvious for 2 ≤ i ≤ m − 1
as pi is simply the label of the maximal arc of ∆ corresponding to ei . For i = 1, m
this follows from the fact that subwords of length at least d(n)|vi0 | occur in only
one position of the word vi0 . This shows that at most f (n) tuples (p1 , . . . , pm ) can
occur.
We now show that the total length of all yt occurring in any fixed basic decompositions of vj0 is at most ((1 − α) + 6nd(n)) · |vj0 |.
Choose a fixed basic decomposition (!) of vj0 and let β be a basic path representing
(!). Each yt decomposes as a concatenation of arc subwords that are read along
00
maximal arcs in Ψ0 or the paths corresponding to y00 or ym
as β is read in ∆. Note
further that the sum of the lengths of y0 , . . . , ym exceeds the number of edges in
their image by at most (1 − α)|vj0 | as vj0 is α-injective. Each maximal arc in Ψ0
00
has length < d(n)|vj0 | and so do the paths corresponding to y00 and ym
. Thus the
number of edges in the image of the arcs corresponding to y0 , . . . , ym is bounded
00
from above by 6nd(n)|vj0 |, since ∆ has at most 6n − 1 maximal arcs and if y00 or ym
0
are non-degenerate then at most 6n − 2 of these arcs lie in Ψ . Therefore
m
X

|yt | ≤ ((1 − α) + 6nd(n)) · |vj0 |.

t=0

By definition of f (n), it follows that the total length of all yt occurring in all
possible basic decompositions of a given vj0 is at most
f (n) · ((1 − α) + 6nd(n)) · |vi0 | ≤

1 0
|v |.
2 j

30

ILYA KAPOVICH AND RICHARD WEIDMANN

Thus there exists a non-trivial subword ṽj of vj0 (we could actually choose ṽj
to be a 1-letter subword) such that in no basic decomposition of vj0 this subword
ṽj overlaps with any yt . Then the subwords ṽ1 , . . . , ṽn satisfy the requirements of
Lemma 7.4

Recall that in Definition 4.2 we defined the notions of an edge/arc of a graph
Υ being Υ-injective with respect to a graph map from Υ to another graph. Recall
also that in our situation the map f : Γ → Rn factors through f∆ : Γ → ∆. In the
following Υ-injectivity of some arc Υ in Γ refers to Υ-injectivity with respect to the
map f∆ . Recall that p∆ = f∆ (pΓ ) is the image of the base-vertex of Γ in ∆.
Recall that, as specified in Convention 7.3, the (k + 1)-st loop of Γ contains an
arc s̃Z labelled by a U -word Z of length at least (1 − 1014 n )N 2 , and that the path
sZ in ∆ is the image of s̃Z under p∆ .
1
Lemma 7.5. The arc s̃Z contains a s̃Z -injective subarc Q of length 100n
N 2 that
0
0
is mapped to an arc Q in ∆ such that Q does not contain the vertex p∆ in its
interior.

Proof. Let ṽ1 , . . . , ṽn be distinguished subwords of v10 , . . . vn0 provide by Lemma 7.4.
Let now Θ be the subgraph of ∆ consisting of the edges traversed by sZ .
We now construct a graph Θ̂ from Θ as follows:
First, collapse all edges of Θ that do not lie on the arcs that are images of the
subpaths of sZ corresponding to distinguished subwords ṽj of the v-syllables of Z.
The resulting graph Θ0 is the union of arcs labeled with the ṽj and two such arcs
intersect at most in the endpoints.
Now in Θ0 replace any such arc with label ṽj with an edge with label bj . We
±1
thus obtain a graph Θ̂ with edges labelled by letters of {b±1
1 , . . . , bn }. Note that Θ̂
has first Betti number at most n − 1, since all edges of Θ that lie in Ψ are collapsed
when constructing Θ0 .

Since Z is subword of length at least 1 − 1014 n N 2 of some cyclic permutation
of some Ui±1 , the word Z contains a subword Z 0 with the following properties:
49
(1) |Z 0 | ≥ 100
N 2.
0
(2) Z consists of the remnants of the vi after substituting the bi in ui .
Let sZ 0 be the subpath of sZ corresponding to the subword Z 0 of Z. Similarly
let s̃Z 0 be the subpath of s̃Z corresponding to Z 0 .
Now for j = 1, . . . , n replace in Z 0 any remnant of vjε by bεj . We thus obtain a
±1
±1
freely reduced word Ẑ in the {b±1
1 , . . . , bn } that is a subword of ui . Note that
49
|Ẑ| ≥ 100 N .
The word Ẑ is readable in Θ̂ by construction. Hence, by Theorem 4.3 and by
making the appropriate genericity assumptions on the ui , we may assume that the
corresponding path sẐ in Θ̂ is α-injective for some α > 1000n−1
1000n . It follows from
α-injectivity of sẐ that any subpath of sẐ of length
2(1 − α) · |Ẑ| + 1 ≤ (1 − α) · 3N
contains an sẐ -injective edge. This implies that any subpath of sZ 0 of length
1
1
((1 − α) · 3N + 1)N ≤ (1 − α) · 4N 2 =
N2 ≤
N2
250n
100n
contains an sZ 0 -injective edge.
Now write sZ 0 as the the product of 20n − 1 subpaths s1 , . . . , s20n−1 of length
1
49
greater or equal than 50n
N 2 . This can be done since |sZ 0 | ≥ 100
N 2 . By the
argument given above, it follows that every sj contains an sZ 0 -injective edge.
Since ∆ has at most 3(2n − 1) − 3 = 6n − 6 maximal arcs, it follows that the the
collection of all sZ 0 -injective edges in ∆ is the union of at most 6n − 5 sZ 0 -injective

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

31

arcs of ∆. At most one of these sZ 0 -injective arcs of ∆ can contain p∆ in its interior.
After possibly subdividing this arc by p∆ in two, it follows that the collection of
all sZ 0 -injective edges in ∆ is the union of pairwise non-overlapping arcs t1 , . . . , tk ,
with k ≤ 6n and such that p∆ does not lie in the interior of any ti .
Since each subpath si of sZ 0 contains an sZ 0 -injective edge, it follows that each
si nontrivially overlaps some tj . We claim that there exist k0 and j such that
each of sk0 −1 , sk0 , sk0 +1 nontrivially overlaps tj . Otherwise each tj would overlap
at most two of the paths s1 , . . . , s20n−1 , and hence the paths t1 , . . . , tk overall at
most 2 · 6n = 12n < 20n − 1 of the paths s1 , . . . , s20n−1 . This contradicts the fact
that each si intersects some tj . Thus indeed there exist k0 and j such that each of
sk0 −1 , sk0 , sk0 +1 overlaps tj , so that tj contains sk0 . Note that sk0 does not contain
the vertex p∆ in its interior, since p∆ does not belong to the interior of tj .
1
N 2.
Thus sk0 is an arc of ∆ which is sZ 0 -injective and which has length ≥ 50n
By genericity of presentation (∗) we may assume that there is no word W of
1
N 2 such that W ±1 occurs more than once in Z. Since sk0 is an arc of
length 500n
1
length ≥ 50n N 2 and since Z is freely reduced, the path sZ cannot run over the
entire arc sk0 more than once. We also know that sk0 does occur as a subpath of
sZ , so that at some point the path sZ does run over the entire arc sk0 . It may also
happen that, in addition, the initial and/or terminal segment of sZ overlaps the
1
N 2 . Therefore
arc sk0 nontrivially; however such overlaps must have length ≤ 500n
1
sk0 contains a sub arc Q0 of length 100n
N 2 such that Q0 is sZ -injective.
1
0
We put Q be the lift of Q to Γ. Since |Q| = |Q0 | = 100n
N 2 , the conclusion of
0
Lemma 7.5 holds with these choices of Q and Q . Thus Lemma 7.5 is established.

Concluding the proof of Theorem 7.1. We now have all tools to conclude the proof
of the Theorem 7.1. Recall that we argue by contradiction and that we have
assumed that the 2n − 1-tuples (a1 , . . . , an , 1 . . . , 1) and (b1 , . . . , bn , 1 . . . , 1) are
Nielsen-equivalent in G.
We will see that we can apply Lemma 6.6 to reduce the complexity of xk+1 while
maintaining the complexity of xi for 1 ≤ i ≤ k and preserving the fact that xi =G bi
for 1 ≤ i ≤ n. This will yield is a contradiction to the minimality assumption about
(x1 , . . . , x2n−1 ) made at the beginning of the proof.
Recall that k was maximal such that xi = vi in F (A) for all 1 ≤ i ≤ k and that
by Lemma 7.2 we know that k ≤ n − 1. By convention if x1 6= v1 , we set k = 0.
Thus we always have 1 ≤ k + 1 ≤ n.
1
Let W be the word that is the label of the arc Q of length 100n
N 2 provided
1
2
by Lemma 7.5. Thus W is of length 100nN . Note that W is a subword of the
U -subword Z of length at least 1 − 1014 n N 2 . Recall that Q is a sub-arc of the
(k + 1)-st petal of Γ and that under the map Γ → ∆ the arc Q maps injectively to
an arc Q0 of ∆.
By Lemma 7.5 the base-vertex p∆ = f∆ (pΓ ) does not belong to the interior of
Q0 . Since the petals of Γ are labelled by freely reduced words, it now follows that
the full preimage of Q0 in Γ under f∆ is the union of a collection of pairwise nonoverlapping arcs Q1 , . . . , Qm in Γ such that Q = Q1 and such that each of the arcs
Q1 , . . . , Qm maps bijectively to Q0 .
For 1 ≤ i ≤ 2n − 1 write xi as a reduced product
(‡)

x0,i W ε1,i x1,i W ε2,i · . . . W εqi ,i xqi ,i

with εj,i ∈ {−1, 1} where the W εj,i are the occurrences of W ±1 in xi corresponding
to all those of the arcs Q1 , . . . , Qm that are contained in the i-th petal-loop of Γ.

32

ILYA KAPOVICH AND RICHARD WEIDMANN

Note that for 1 ≤ i ≤ k the length of xi = vi is too short to contain W as a
subword. Therefore for 1 ≤ i ≤ k we have xi = x0,i and qi = 0.
We now perform the change described in Lemma 6.6 simultaneously for all xi ,
i = 1, . . . , 2n − 1. That is, we pick a word V ∈ F (A) such that W V −1 is a cyclic
permutation of one of the defining relations Us±1 of presentation (**). Then for
each xi we replace each W j,i in the decomposition (‡) of xi by V j,i . Denote
the resulting word by zi and denote the freely reduced form of zi by x0i , where
i = 1, . . . , 2n − 1.
By construction, xi is unchanged for 1 ≤ i ≤ k, that is xi = x0i for 1 ≤ i ≤ k.
Moreover the complexity of xk+1 decreases as the presence of subword Z of xk+1
triggers clause (2) of Lemma 6.6. Thus we have c(xi ) = c(x0i ) for 1 ≤ i ≤ k and
c(x0k+1 ) < c(xk+1 ).
Since W =G V , we have xi =G x0i for 1 ≤ i ≤ 2n − 1. In particular we have
0
xi =G bi for 1 ≤ i ≤ n. Thus to get the desired contradition to the minimal choice
of (x1 , . . . , x2n−1 ) we only need to verify that the tuple (x01 , . . . , x02n−1 ) is Nielsenequivalent to (a1 , . . . , an , 1, . . . , 1) in F (A). This fact follows from the following
considerations:
In the graph ∆ we replace the arc Q0 by an arc Y with label V and call the
resulting graph ∆0 . The graph ∆0 still folds onto Rn , since ∆0 contains Ψ.
By Lemma 7.5 the vertex p∆ = f∆ (pΓ ) does not belong to the interior of Q0 .
Since the petals of Γ are labelled by freely reduced words, it now follows that the
full preimage of Q0 in Γ under f∆ is the union of a collection of pairwise nonoverlapping arcs Q1 , . . . , Qm in Γ such that Q = Q1 and such that each of the arcs
Q1 , . . . , Qm maps bijectively to Q0 . Note also that each of the arcs Q1 , . . . , Qm is
labelled by W amd that the base-vertex pΓ of Γ does not belong to the interior of
any of Q1 , . . . , Qm .
We obtain a new graph Γ0 from Γ by replacing each Qj by an arc Yj labelled
by V . Then there is a natural label-preserving graph map f∆0 : Γ0 → ∆0 which
sends each arc Qj bijectively to Y , and which agrees with f∆ on the complement
of Y1 ∪ · · · ∪ Ym in Γ0 . The map f∆ : Γ → ∆ arose from a sequence of folds and
therefore f∆ is π1 -surjective.
Topologically f∆0 can be viewed as the same as the map f∆ and hence the map
f∆0 is π1 -surjective. As we noted earlier, the graph ∆0 folds onto Rn , and hence
the map ∆0 → Rn is π1 -surjective. By composing this map with f∆0 , we conclude
that the canonical map Γ0 → Rn preserving edge-labels is π1 -surjective.
The graph Γ0 is a wedge of 2n−1 circles with labels z1 , . . . , z2n−1 . As noted above,
the canonical map Γ0 → Rn is π1 -surjective. Since π1 (Γ0 ) is generated by the looppetals with labels z1 , . . . , z2n−1 and since each zi freely reduces to x0i , it follows that
the elements x01 , . . . , x02n−1 of F (A) generate the entire group F (A) = F (a1 , . . . , an ).
Therefore the (2n − 1)-tuple (x01 , . . . , x02n−1 ) is Nielsen-equivalent in F (A) to the
(2n − 1)-tuple (a1 , . . . , an , 1, . . . , 1).
Recall that xi = vi = x0i for i = 1, . . . , k (where k < n) and that c(x0k+1 ) < c(xk ).
Therefore c(x01 , . . . , x02n−1 ) < c(x1 , . . . , x2n−1 ), which contradicts the minimality
assumption on (x1 , . . . , x2n−1 ).
Hence the 2n − 1-tuples (a1 , . . . , an , 1, . . . , 1) and (b1 , . . . , bn , 1, . . . , 1) are not
Nielsen-equivalent in G, and Theorem 7.1 is proved.


References
[A]

G. Arzhantseva, On groups in which subgroups with a fixed number of generators are
free, Fundam. Prikl. Mat. 3 (1997), no. 3, 675–683.

NIELSEN EQUIVALENCE IN A CLASS OF RANDOM GROUPS

[AO]

[D]

[E1]
[E2]
[E3]
[G]
[KM]
[KS]
[KW1]
[KW2]
[KW3]
[LGM]

[L]
[LP]
[LM1]
[LM2]
[LM3]
[LS]
[No]
[M]
[N1]
[N2]
[O]

[Pa]

[PRZ]
[R]
[Sta]
[Str]

[W]

33

G. Arzhantseva and A. Yu. Ol’shanskii, Generality of the class of groups in which
subgroups with a lesser number of generators are free. Mat. Zametki 59 (1996), no. 4,
489–496
T. Delzant Sous-groupes a deux generateurs des groupes hyperboliques. E. Ghys,
A. Haefliger and A. Verjovsky, (editors), Group theory from a geometrical viewpoint.
Proceedings of a workshop, held at the International Centre for Theoretical Physics in
Trieste, Italy, 26 March to 6 April 1990. Singapore, World Scientific, 1991, 177–189.
M.J. Evans Presentations of Groups involving more Generators than are neceessary,
Proc. London Math. Soc. 67 (1993), 106–126.
M.J. Evans Presentations of Groups involving more Generators than are neceessary
II, Cont. Math. 421(2006), 101–112.
M.J. Evans Nielsen equivalence classes and stability graphs of finitely generated groups,
Ischia Group theory 2006, World Scientific, 2007.
I. Grushko, On the bases of a free product of groups Mat. Sbornik 8 (1940), 169–182.
I. Kapovich, and A. Myasnikov, Stallings foldings and subgroups of free groups. J.
Algebra 248 (2002), no. 2, 608–668
I. Kapovich, and P. Schupp, Genericity, the Arzhantseva-Olshanskii method and the
isomorphism problem for one-relator groups. Math. Ann. 331 (2005), no. 1, 1–19
I. Kapovich and R. Weidmann, Freely indecomposable groups acting on hyperbolic
spaces, Internat. Jour. Algebra Comput. 14 (2004), 115–171
I. Kapovich and R. Weidmann, Kleinian groups and the rank problem, Geometry &
Topology 9 (2005), 375–402
I. Kapovich and R. Weidmann, Nielsen equivalence in small cancellation groups,
preprint, 2010; arXiv:1011.5862
C. Leedham-Green and S. Murray, Variants of product replacement. Computational
and statistical group theory (Las Vegas, NV/Hoboken, NJ, 2001), 97–104, Contemp.
Math., 298, Amer. Math. Soc., Providence, RI, 2002
L. Louder, Nielsen equivalence of generating sets for closed surface groups, preprint,
http://arxiv.org/abs/1009.0454
A. Lubotzky and I. Pak, The product replacement algorithm and Kazhdan’s property
(T). J. Amer. Math. Soc. 14 (2001), no. 2, 347–363
M. Lustig and Y. Moriah, Nielsen equivalence and simple homotopy type, Proc. London
Math. Soc. 62 (1991), 537–562
M. Lustig and Y. Moriah, Nielsen equivalence in Fuchsian groups and Seifert fibered
spaces, Topology 30 (1991) 191–204
M. Lustig and Y. Moriah, Generating systems of groups and Reidemeister-Whitehead
torsion, J. Algebra 157 (1993), 170–198
R. Lyndon and P. Schupp, Cominatorial Group Theory, Springer-Verlag, 1977
G.A. Noskov, Primitive elements in a free group, Math. Zametki 30 (1981), no. 4,
497–500
J. MacKay Conformal dimension and random groups, Geom. Funct. Anal. (GAFA),
22 (2012), 213–239
J. Nielsen Die Isomorphismen der allgemeinen, unendlichen Gruppe mit zwei Erzeugenden, Math. Ann. 78 (1917), no. 1, 385–397.
J. Nielsen Über die Isomorphismen unendlicher Gruppen ohne Relation, Math. Ann.
79 (1918), no. 3, 269–272.
A. Yu. Ol’shanskii, Geometry of defining relations in groups. Translated from the 1989
Russian original by Yu. A. Bakhturin. Mathematics and its Applications (Soviet Series),
70. Kluwer Academic Publishers Group, Dordrecht, 1991
I. Pak, What do we know about the product replacement algorithm?, Groups and computation, III (Columbus, OH, 1999), 301–347, Ohio State Univ. Math. Res. Inst. Publ.,
8, de Gruyter, Berlin, 2001
N. Peczynski, G. Rosenberger and H. Zieschang Über Erzeugende ebener diskontinuierlicher Gruppen Invent. Math. 29 (975), 161–180.
E. Rips, Subgroups of small cancellation groups, Bull. Lond. Math. Soc. 14 (1982),
45–47
J. R. Stallings Topology of Finite Graphs Invent. Math. 71 (1983), 551–565
Ralph Strebel, Small cancellation groups, in: “Sur les groupes hyperboliques d’apres
Mikhael Gromov.” Papers from the Swiss Seminar on Hyperbolic Groups held in Bern,
1988. Edited by E. Ghys and P. de la Harpe. Appendix, 227–273. Progress in Mathematics, 83. Birkhauser Boston, 1990
R. Weidmann, Generating tuples of free products, Bull. London Math. Soc., 39 (2007),
393–403.

34

[Z]

ILYA KAPOVICH AND RICHARD WEIDMANN

H. Zieschang, Über der Nielsensche Kürzungsmethode in freien Produkten mit Amalgam, Inventiones Math. 10 (1970), 4–37

Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 West Green
Street, Urbana, IL 61801, USA
http://www.math.uiuc.edu/~kapovich/
E-mail address: kapovich@math.uiuc.edu
Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Ludewig-Meyn Str. 4,
24098 Kiel, Germany
E-mail address: weidmann@math.uni-kiel.de

