NORMALISING GRAPHS OF GROUPS

C. KRATTENTHALER^{†} AND THOMAS MÜLLER^{∗}

Abstract. We discuss a partial normalisation of a finite graph of finite groups (Γ(−), X) which leaves invariant the fundamental group. In conjunction with an easy graph-theoretic result, this provides a flexible and rather useful tool in the study of finitely generated virtually free groups. Applications discussed here include (i) an important inequality for the number of edges in a Stallings decomposition Γ ≅ π_{1}(Γ(−), X) of a finitely generated virtually free group, (ii) the proof of equivalence of a number of conditions for such a group to be ‘large’, as well as (iii) the classification up to isomorphism of virtually free groups of (free) rank 2. We also discuss some number-theoretic consequences of the last result.

1. Introduction

The purpose of this paper is to introduce, and demonstrate the usefulness of, a technique for partially normalising the presentation of a finitely generated virtually free group as the fundamental group of a finite graph of finite groups. Roughly speaking, our method avoids trivial amalgamations along a maximal tree of the connected graph underlying such a representation. This result, Lemma 1, in conjunction with an almost trivial graph-theoretic result (Lemma 2), provides us with a flexible and rather powerful tool in the study of such groups. We demonstrate the usefulness of our approach by describing various applications: (i) a short and elegant argument establishing the (well-known) classification of virtually infinite-cyclic groups due originally to Stallings and Wall, (ii) the classification of virtually free groups of free rank 2 together with some numbertheoretic consequences,^{1} and (iii) the equivalence of a number of conditions on a finitely generated virtually free group Γ expressing, in one way or other, the fact that Γ is large; cf. Propositions 4, 7, and 11. In Section 5, we also show that, (iv) for a normalised decomposition (Γ(−), X) of a finitely generated virtually free group Γ, the number of geometric edges of the graph X is bounded above by the free rank of Γ; cf. Lemma 3. This important observation plays a role in the proof of Proposition 7 below, as well as in establishing certain finiteness results for the class of finitely generated virtually free groups with specified information concerning the number of free subgroups of finite index. For another, recent application of the normalisation provided by Lemma 1 see [9].

2010 Mathematics Subject Classification. Primary 20E06; Secondary 20E08.

Key words and phrases. Graphs of groups, fundamental group, amalgamation.

†Research partially supported by the Austrian Science Foundation FWF, grant S50-N15, in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics”

∗Research supported by Lise Meitner Grant M1661-N25 of the Austrian Science Foundation FWF.

1See Section 2 for the definition of the free rank.

2. Some preliminaries on finitely generated virtually free groups

Our notation and terminology here follows Serre’s book [20]; in particular, the category of graphs used is described in [20, §2]. This category deviates slightly from the usual notions in graph theory. Specifically, a graph X consists of two sets: E(X), the set of (directed) edges, and V (X), the set of vertices. The set E(X) is endowed with a fixed-point-free involution ^{−} : E(X) → E(X) (reversal of orientation), and there are two functions o, t : E(X) → V (X) assigning to an edge e ∈ E(X) its origin o(e) and terminus t(e), such that t(ē) = o(e). The reader should note that, according to the above definition, graphs may have loops (that is, edges e with o(e) = t(e)) and multiple edges (that is, several edges with the same origin and the same terminus). An orientation O(X) consists of a choice of exactly one edge in each pair {e, ē} (this is indeed always a pair – even for loops – since, by definition, the involution ^{−} is fixed-point-free). Such a pair is called a geometric edge.

Let Γ be a finitely generated virtually free group with Stallings decomposition (Γ(−), X); that is, (Γ(−), X) is a finite graph of finite groups with fundamental group π_{1}(Γ(−), X) ≅ Γ. If 𝔉 is a free subgroup of finite index in Γ then, following an idea of C. T. C. Wall, one defines the (rational) Euler characteristic χ(Γ) of Γ as

χ(Γ) = −\frac{rk(𝔉) − 1}{(Γ : 𝔉)}.  (2.1)

(This is well-defined in view of Schreier’s index formula in [17].) In terms of the above decomposition of Γ, we have

χ(Γ) = ∑_{v∈V (X)} \frac{1}{|Γ(v)|} − ∑_{e∈O(X)} \frac{1}{|Γ(e)|}.  (2.2)

Equation (2.2) reflects the fact that, in our situation, the Euler characteristic in the sense of Wall coincides with the equivariant Euler characteristic χ_{T} (Γ) of Γ relative to the tree T canonically associated with Γ in the sense of Bass–Serre theory; cf. [1, Chap. IX, Prop. 7.3] or [19, Prop. 14]. We remark that a finitely generated virtually free group Γ is largest among finitely generated groups in the sense of Pride’s preorder [16] (i.e., Γ has a subgroup of finite index, which can be mapped onto the free group of rank 2) if, and only if, χ(Γ) < 0; see Proposition 11 in Section 8.

Denote by m_{Γ} the least common multiple of the orders of the finite subgroups in Γ, so that, again in terms of the above Stallings decomposition of Γ,

m_{Γ} = lcm {|Γ(v)| : v ∈ V (X)}.

(This formula essentially follows from the well-known fact that a finite group has a fixed point when acting on a tree.) The type τ(Γ) of a finitely generated virtually free group Γ ≅ π_{1}(Γ(−), X) is defined as the tuple

τ(Γ) = (m_{Γ}; ζ_{1}(Γ), …, ζ_{κ}(Γ), …, ζ_{m_{Γ}}(Γ)),

where the ζ_{κ}(Γ)’s are integers indexed by the divisors of m_{Γ}, given by

ζ_{κ}(Γ) = |{e ∈ O(X) : |Γ(e)| | κ}| − |{v ∈ V (X) : |Γ(v)| | κ}|.

It can be shown that the type τ(Γ) is in fact an invariant of the group Γ, i.e., independent of the particular decomposition of Γ in terms of a graph of groups (Γ(−), X), and that two finitely generated virtually free groups Γ_{1} and Γ_{2} contain the same number of free subgroups of index n for each positive integer n if, and only if, τ(Γ_{1}) = τ(Γ_{2}); cf. [13, Theorem 2]. We have ζ_{κ}(Γ) ≥ 0 for κ < m_{Γ} and ζ_{m_{Γ}}(Γ) ≥ −1 with equality occurring in the latter inequality if, and only if, Γ is the fundamental group of a tree of groups; cf. [12, Prop. 1] or [13, Lemma 2]. We observe that, as a consequence of (2.2), the Euler characteristic of Γ can be expressed in terms of the type τ(Γ) via

χ(Γ) = −m_{Γ}^{−1} ∑_{κ|m_{Γ}} φ(m_{Γ}/κ) ζ_{κ}(Γ),  (2.3)

where φ is Euler’s totient function. It follows in particular that, if two finitely generated virtually free groups have the same number of free subgroups of index n for every n, then their Euler characteristics must coincide.

Define a torsion-free Γ-action on a set Ω to be a Γ-action on Ω which is free when restricted to finite subgroups, and let

g_{λ}(Γ) := \frac{number of torsion-free Γ-actions on a set with λm_{Γ} elements}{(λm_{Γ})!}, λ ≥ 0;

(2.4)

in particular, g_{0}(Γ) = 1. The sequences (f_{λ}(Γ))_{λ≥1} and (g_{λ}(Γ))_{λ≥0} are related via the Hall-type convolution formula^{2}

∑_{μ=0}^{λ−1} g_{μ}(Γ)f_{λ−μ}(Γ) = m_{Γ}λg_{λ}(Γ), λ ≥ 1.  (2.5)

Introducing the generating functions

F_{Γ}(z) := ∑_{λ≥0} f_{λ+1}(Γ)z^{λ} and G_{Γ}(z) := ∑_{λ≥0} g_{λ}(Γ)z^{λ},

Equation (2.5) is seen to be equivalent to the relation

F_{Γ}(z) = m_{Γ} \frac{d}{dz} ( log G_{Γ}(z)).  (2.6)

Moreover, a careful analysis of the universal mapping property associated with the presentation Γ ≅ π_{1}(Γ(−), X) leads to the explicit formula

g_{λ}(Γ) = \frac{∏_{e∈O(X)}(λm_{Γ}/|Γ(e)|)! |Γ(e)|^{λm_{Γ}/|Γ(e)|}}{∏_{v∈V (X)}(λm_{Γ}/|Γ(v)|)! |Γ(v)|^{λm_{Γ}/|Γ(v)|}} , λ ≥ 0,  (2.7)

for g_{λ}(Γ), where O(X) is any orientation of X; cf. [13, Prop. 3].

Define the free rank μ(Γ) of a finitely generated virtually free group Γ to be the rank of a free subgroup of index m_{Γ} in Γ (existence of such a subgroup follows, for instance, from Lemmas 8 and 10 in [20]; it need not be unique, though). We note that, in view of (2.1), the quantity μ(Γ) is connected with the Euler characteristic of Γ via

μ(Γ) + m_{Γ}χ(Γ) = 1,  (2.8)

2See [13, Cor. 1], or [4, Prop. 1] for a more general result.

which shows in particular that μ(Γ) is well-defined. From Formula (2.7) it may be deduced that the sequence g_{λ}(Γ) is of hypergeometric type and that its generating function G_{Γ}(z) satisfies a homogeneous linear differential equation

θ_{0}(Γ)G_{Γ}(z) + (θ_{1}(Γ)z − m_{Γ})G′_{Γ}(z) + ∑_{μ=2}^{μ(Γ)} θ_{μ}(Γ)z^{μ}G_{Γ}^{(μ)}(z) = 0  (2.9)

of order μ(Γ) with integral coefficients θ_{μ}(Γ) given by

θ_{μ}(Γ) = \frac{1}{μ!} ∑_{j=0}^{μ}(−1)^{μ−j}\binom{μ}{j}m_{Γ}(j + 1) ∏_{κ|m_{Γ}} _{∏_{1≤k≤m_{Γ}} ; (m_{Γ},k)=κ}(jm_{Γ} + k)^{ζ_{κ}(Γ)}, 0 ≤ μ ≤ μ(Γ);

(2.10)

cf. [13, Prop. 5].

3. Normalising a finite graph of groups

It will be important to be able to represent a finitely generated virtually free group Γ by a graph of groups avoiding trivial amalgamations along a maximal tree. This is achieved via the following.

Lemma 1 (Normalisation). Let (Γ(−), X) be a (connected) graph of groups with fundamental group Γ, and suppose that X has only finitely many vertices. Then there exists a graph of groups (Δ(−), Y) with |V (Y)| < ∞ and a spanning tree T in Y, such that π_{1}(Δ(−), Y) ≅ Γ, and such that^{3}

Δ(e)^{e} ≠ Δ(t(e)) and Δ(e)ē ≠ Δ(o(e)), for e ∈ E(T).  (3.1)

Moreover, if (Γ(−), X) satisfies the finiteness condition

(F_{1}) X is a finite graph,

or

(F_{2}) Γ(v) is finite for every vertex v ∈ V (X),

then we may choose (Δ(−), Y) so as to enjoy the same property.

Proof. Choose a spanning tree S in X, and call an edge e ∈ E(S) trivial, if at least one of the associated embeddings e : Γ(e) → Γ(t(e)) and ē : Γ(e) → Γ(o(e)) is an isomorphism. If S contains a trivial edge e_{1} — to fix ideas, say Γ(e_{1})^{e_{1}} = Γ(t(e_{1})) — then we contract the edge e_{1} into the vertex o(e_{1}) and re-define incidence and embeddings where necessary, to obtain a new graph of groups (Γ′(−), X′) with spanning tree S′ in X′. More precisely, this means that we let

E(X′) = E(X) \ {e_{1}, ē_{1}},
E(S′) = E(S) \ {e_{1}, ē_{1}},
V (X′) = V (S′) = V (X) \ {t(e_{1})},

3The notation used in Equation (3.1) follows Serre; see Déf. 8 in [20, Sec. 4.4].

set

t′(e) := o(e_{1}), for e ∈ E(X′) with t(e) = t(e_{1}),

and define new embeddings via

Γ(e) ⟶^{e} Γ(t(e_{1})) ⟶^{e_{1}^{−1}} Γ(e_{1}) ⟶^{ē_{1}} Γ(o(e_{1})) = Γ(t′(e)), for e ∈ E(X′) with t(e) = t(e_{1}),

(3.2)

leaving incidence and embeddings unchanged wherever possible. Clearly, S′, the result of contracting the geometric edge {e_{1}, ē_{1}} and deleting the vertex t(e_{1}), is still a spanning tree for X′ and, if (Γ(−), X) has property (F_{1}) or (F_{2}), then so does (Γ′(−), X′) by construction.

It remains to see that the fundamental group of the new graph of groups (Γ′(−), X′) is isomorphic to Γ. The fundamental group

π_{1}(Γ(−), X, S)

of the graph of groups (Γ(−), X) at the spanning tree S is generated by the groups Γ(v) for v ∈ V (X) plus extra generators γ_{e} for e ∈ O(X) − E(S), where O(X) is any orientation of X, subject to the relations

a^{e} = aē, for e ∈ O(S) and a ∈ Γ(e),  (3.3)
γ_{e}a^{e}γ_{e}^{−1} = aē, for e ∈ O(X) − E(S) and a ∈ Γ(e),  (3.4)

where O(S) is the orientation of the tree S induced by O(X), with a corresponding presentation for π_{1}(Γ′(−), X′, S′); see §5.1 in [20, Chap. I]. The relations (3.3) corresponding to the geometric edge {e_{1}, ē_{1}} identify Γ(t(e_{1})) isomorphically with a subgroup of Γ(o(e_{1})); we can thus delete the generators γ ∈ Γ(t(e_{1})) against those relations by Tietze moves. This yields a presentation for π_{1}(Γ(−), X, S) with the same set of generators as π_{1}(Γ′(−), X′, S′). Moreover, those relations (3.3)–(3.4) coming from edges e with t(e) = t(e_{1}) have to be re-expressed in terms of elements of Γ(o(e_{1})), which leads exactly to the corresponding relations of π_{1}(Γ′(−), X′, S′) obtained by extending the embedding e : Γ(e) → Γ(t(e_{1})) in the natural way as given in (3.2). Hence, π_{1}(Γ(−), X, S) ≅ π_{1}(Γ′(−), X′, S′). Since V (X) is finite, the tree S is finite; thus, proceeding in the manner described, we obtain, after finitely many steps, a graph of groups (Δ(−), Y) with fundamental group Γ and a spanning tree T in Y without trivial edges, such that (Δ(−), Y) enjoys the finiteness properties (F_{1}), (F_{2}) whenever (Γ(−), X) does. □

4. A graph-theoretic lemma

The following auxiliary result, which is of an entirely graph-theoretic nature, will be used frequently in the rest of the paper.

Lemma 2. Let T be a tree, and let v_{0} ∈ V (T) be any vertex. Then there exists one, and only one, orientation O(T) of T, such that the assignment e ↦ t(e) defines a bijection ψ_{v_{0}} : O(T) → V (T) \ {v_{0}}. This orientation is obtained by orienting each geometric edge so as to point away from the root v_{0}; that is, travelling along an edge of O(X), the distance from v_{0} in the path metric always increases.

Lemma 2 is easy to show, even in this generality. Moreover, for our present purposes, the trees considered will all be finite, in which case the assertion of Lemma 2 may be proved by a straightforward induction on |V (T)|, which we sketch briefly: by our condition on the map ψ_{v_{0}}, all (geometric) edges incident with v_{0} will have to be oriented away from the root v_{0}. Delete v_{0} together with edges incident to v_{0}. The result is a disjoint union of finitely many subtrees, in which we choose the (previous) neighbours of v_{0} as new roots. An application of the induction hypothesis to these rooted subtrees now finishes the proof.

In what follows, the orientation of a tree T with respect to a base point v_{0} described in Lemma 2 will be denoted by O_{v_{0}}(T).

5. An inequality for the number of edges of a graph of groups

An important consequence of normalisation is the following.

Lemma 3. Let (Γ(−), X, T) be a finite graph of finite groups with maximal tree T ≤ X and fundamental group π_{1}(Γ(−), X) ≅ Γ. If (Γ(−), X, T) satisfies the normalisation condition (3.1), then the number of edges |E(X)| of the graph X is bounded above in terms of the free rank of Γ via

|E(X)| ≤ 2μ(Γ).  (5.1)

Proof. We distinguish two cases.

(a) |V (X)| = 1. Then m_{Γ} = |Γ(v)|, where V (X) = {v}, and the Euler characteristic of Γ becomes

χ(Γ) = \frac{1}{|Γ(v)|} − ∑_{e∈O(X)} \frac{1}{|Γ(e)|}

= m_{Γ}^{−1}(1 − ∑_{e∈O(X)} (Γ(v) : Γ(e)^{e}))

≤ −m_{Γ}^{−1}(|O(X)| − 1),

where O(X) is an arbitrary orientation of X. It follows that

μ(Γ) = 1 − m_{Γ}χ(Γ) ≥ |O(X)|,

whence our claim in this case.

(b) |V (X)| ≥ 2. Then E(T) ≠ ∅, and we may choose some edge e_{1} ∈ E(T). Consider the tree T as rooted with root v_{1} = o(e_{1}) and associated orientation O_{v_{1}}(T) in the sense of Lemma 2. Extending O_{v_{1}}(T) to an orientation O(X) of X, we write

χ(Γ) = (\frac{1}{|Γ(o(e_{1}))|} + \frac{1}{|Γ(t(e_{1}))|} − \frac{1}{|Γ(e_{1})|})

+ ∑_{e∈O_{v_{1}}(T)\\{e_{1}\}} (\frac{1}{|Γ(t(e))|} − \frac{1}{|Γ(e)|}) − ∑_{e∈O(X)\O_{v_{1}}(T)} \frac{1}{|Γ(e)|}.

Since the edge e_{1} is not trivial, we have 2|Γ(e_{1})| ≤ |Γ(o(e_{1}))| as well as 2|Γ(e_{1})| ≤ |Γ(t(e_{1}))|, thus

\frac{1}{|Γ(o(e_{1}))|} + \frac{1}{|Γ(t(e_{1}))|} ≤ \frac{1}{|Γ(e_{1})|}.

For the same reason, for e ∈ O_{v_{1}}(T) \ {e_{1}}, we have

\frac{1}{|Γ(t(e))|} − \frac{1}{|Γ(e)|} = \frac{1 − (Γ(t(e)) : Γ(e)^{e})}{|Γ(t(e))|} ≤ −\frac{1}{|Γ(t(e))|} ≤ −\frac{1}{m_{Γ}} .

Putting together these observations, we find that

χ(Γ) ≤ −m_{Γ}^{−1}(|O_{v_{1}}(T)| − 1) − m_{Γ}^{−1}|O(X) \ O_{v_{1}}(T)| = −m_{Γ}^{−1}(|O(X)| − 1),

from which our claim follows as before. □

6. Classifying virtually infinite-cyclic groups

Virtually infinite-cyclic groups play a certain role in topology as they are precisely the finitely generated groups with two ends. Their structure is well-known; cf. [22, 5.1] or [23, Lemma 4.1]. In this section, we shall give a short proof of the corresponding result (Proposition 4) based on the tools developed in Sections 3 and 4. As a consequence of this classification result, we find that the function f_{λ}(Γ) is constant for μ(Γ) = 1; cf. Corollary 6.

Proposition 4. A virtually infinite-cyclic group Γ falls into one of the following two classes:

(i) Γ has a finite normal subgroup with infinite-cyclic quotient.

(ii) Γ is a free product Γ = G_{1} ∗_{A} G_{2} of two finite groups G_{1} and G_{2}, with an amalgamated subgroup A of index 2 in both factors.

Proof. Let (Γ(−), X) be a finite graph of finite groups with fundamental group Γ and spanning tree T, chosen according to Lemma 1. The reader should observe that the assumption that Γ is virtually infinite-cyclic in combination with (2.8) implies that χ(Γ) = 0.

If |V (X)| = 1, V (X) = {v} say, then the above observation together with Formula (2.2) shows that X has exactly one geometric edge {e, ē}, and that the associated embeddings e, ē : Γ(e) → Γ(v) are isomorphisms. Hence, Γ(v) ⊴ Γ and Γ/Γ(v) ≅ C_{∞}, which gives the desired result in Case (i).

If |V (X)| > 1, we choose an edge e_{1} ∈ E(T), introduce the orientation O_{v_{0}}(T) with respect to the base point v_{0} = o(e_{1}), extend it to an orientation O(X) of X, and let v_{1} = t(e_{1}). We then split the Euler characteristic of Γ as follows:

0 = χ(Γ) = _{∑_{v∈V (X)} ; v≠v_{0},v_{1}} \frac{1}{|Γ(v)|} − _{∑_{e∈O_{v_{0}}(T)} ; e≠e_{1}} \frac{1}{|Γ(e)|} + (\frac{1}{|Γ(v_{0})|} + \frac{1}{|Γ(v_{1})|} − \frac{1}{|Γ(e_{1})|})

− ∑_{e∈O(X)\O_{v_{0}}(T)} \frac{1}{|Γ(e)|}. (6.1)

By the normalisation condition (3.1) on (Γ(−), X, T), we have

2|Γ(e_{1})| ≤ γ := min {|Γ(v_{0})|, Γ(v_{1})|},

so

\frac{1}{|Γ(v_{0})|} + \frac{1}{|Γ(v_{1})|} − \frac{1}{|Γ(e_{1})|} ≤ \frac{2}{γ} − \frac{1}{|Γ(e_{1})|} ≤ 0.  (6.2)

Clearly, equality in (6.2) occurs if, and only if, Γ(e_{1}) is of index 2 in both Γ(v_{0}) and Γ(v_{1}). Similarly, by the normalisation condition (3.1) and Lemma 2, we have

∑_{v∈V (X)} ; v≠v_{0},v_{1} \frac{1}{|Γ(v)|} − _{∑_{e∈O_{v_{0}}(T)} ; e≠e_{1}} \frac{1}{|Γ(e)|} = _{∑_{e∈O_{v_{0}}(T)} ; e≠e_{1}}(\frac{1}{|Γ(t(e))|} − \frac{1}{|Γ(e)|}) ≤ 0,

with equality if, and only if, O_{v_{0}}(T) = {e_{1}}. Also, trivially, the last sum on the righthand side of (6.1) is non-negative, and vanishes if, and only if, O(X) = O_{v_{0}}(T). Given this discussion, we conclude from (6.1) that Γ = Γ(v_{0}) ∗_{Γ(e_{1})} Γ(v_{1}), the amalgam being

formed with respect to the embeddings e_{1} : Γ(e_{1}) → Γ(v_{1}) and ē_{1} : Γ(e_{1}) → Γ(v_{0}), and that (Γ(v_{0}) : Γ(e_{1})ē_{1}) = 2 = (Γ(v_{1}) : Γ(e_{1})^{e_{1}}), whence the result in Case (ii). □

Remarks 5. 1. In Case (i) of Proposition 4, we have ζ_{κ} = 0 for all κ | m_{Γ} whereas, in Case (ii), ζ_{m_{Γ}} = −1. Hence, groups occurring in Case (i) are not isomorphic to groups belonging to Case (ii).

2. In Part (ii) of Proposition 4, A is a finite normal subgroup of Γ with quotient C_{2} ∗C_{2}, the infinite dihedral group.

Corollary 6. If Γ is virtually infinite-cyclic, then the function f_{λ}(Γ) is constant. More precisely, we have f_{λ}(Γ) = m_{Γ} for λ ≥ 1 in Case (i) of Proposition 4, while in Case (ii) we have f_{λ}(Γ) = |A| = m_{Γ}/2.

Proof. If Γ is as described in Case (i) of Proposition 4, then (2.7) shows that g_{λ}(Γ) = 1 for λ ≥ 0, leading to f_{λ}(Γ) = m_{Γ} for all λ ≥ 1 by (2.5) and an immediate induction on λ.

For Γ as in Case (ii), Equation (2.7) yields

g_{λ}(Γ) = 2^{−2λ}\binom{2λ}{λ}, λ ≥ 0.

By the binomial theorem applied to the generating function G_{Γ}(z) of the g_{λ}(Γ)’s, we obtain G_{Γ}(z) = (1 − z)^{−1/2}, which transforms into the relation

F_{Γ}(z) = \frac{|m_{Γ}|}{2(1 − z)} = \frac{|A|}{1 − z}

via (2.6). The desired result follows from this last equation by comparing coefficients. □

7. The case where μ(Γ) = 2

7.1. The classification result.

Proposition 7. A virtually free group Γ of rank μ(Γ) = 2 falls into one of the following five classes:

(i) Γ is an HNN-extension Γ = G ∗_{A,ϕ} with finite base group G, associated subgroups

A and B = ϕ(A), associated isomorphism ϕ : A → B, and (G : A) = 2.

(ii) Γ contains a finite normal subgroup G with quotient Γ/G ≅ F_{2} free of rank 2.

(iii) Γ is a free product Γ = G_{1} ∗_{S} G_{2} of two finite groups G_{i} with an amalgamated subgroup S, whose indices (G_{i} : S) satisfy one of the conditions

(iii)_{1} {(G_{1} : S), (G_{2} : S)} = {2, 3}, (iii)_{2} (G_{1} : S) = 3 = (G_{2} : S), (iii)_{3} {(G_{1} : S), (G_{2} : S)} = {2, 4}.

(iv) Γ is a free product Γ = G_{1} ∗_{S}Γ_{2}, where G_{1} is finite, Γ_{2} is a virtually infinite-cyclic group of type (i) (see Proposition 4), and (G_{1} : S) = 2 = (G_{2} : S), where G_{2} is the base group of the HNN-extension Γ_{2}.

(v) Γ is of the form Γ = (G_{1} ∗_{S_{1}} G_{2}) ∗_{S_{2}} G_{3} with finite factors G_{1}, G_{2}, G_{3} and subgroups

S_{1}, S_{2} satisfying |G_{1}| = |G_{2}| = |G_{3}| = 2|S_{1}| = 2|S_{2}|.

Proof. Let Γ be a virtually free group of free rank μ(Γ) = 2, let (Γ(−), X) be a Stallings decomposition of Γ, and let T be a spanning tree in X satisfying the normalisation condition (3.1) of Lemma 1. By Lemma 3, X has at most two geometric edges, while, by Equation (2.8), we have χ(Γ) = −\frac{1}{m_{Γ}} . There are five possibilities for the isomorphism type of the graph X underlying the decomposition of Γ, and the proof of the proposition (as well as its statement) breaks into cases accordingly.

(i) X consists of a single loop e with o(e) = t(e) = v. Setting G := Γ(v) and S := Γ(e), we have m_{Γ} = |G| and

χ(Γ) = \frac{1}{|G|} − \frac{1}{|S|} = \frac{1 − (G : S^{e})}{m_{Γ}} = −\frac{1}{m_{Γ}} ,

implying (G : S^{e}) = 2. Thus, setting A := S^{e}, B := Sē, and with the isomorphism ϕ : A → B given by x^{e} ↦ xē (in keeping with the notation of [11, Chap. IV.2]), the definition of π_{1}(Γ(−), X) yields that

Γ ≅ ⟨G, t | tat^{−1} = ϕ(a), a ∈ A⟩,

whence the result in that case.

(ii) X consists of a single vertex v, supporting two loops e_{i}, i = 1, 2. Set G := Γ(v) and S_{i} := Γ(e_{i}). Then m_{Γ} = |G|, and

χ(Γ) = \frac{1}{|G|} − \frac{1}{|S_{1}|} − \frac{1}{|S_{2}|} = \frac{1 − (G : S_{1}^{e_{1}}) − (G : S_{2}^{e_{2}})}{m_{Γ}} = −\frac{1}{m_{Γ}} ,

implying

(G : S_{1}^{e_{1}}) = 1 = (G : S_{2}^{e_{2}}).

Hence, the maps e_{i} : S_{i} → G are isomorphisms, and we obtain the presentation

Γ ≅ ⟨G, s_{1}, s_{2} | s_{1}a_{1}^{e_{1}}s_{1}^{−1} = aē_{1} ; 1 (a_{1} ∈ S_{1}), s_{2}a_{2}^{e_{2}}s_{2}^{−1} = aē_{2} ; 2 (a_{2} ∈ S_{2})⟩.

It follows that the finite group G is normal in Γ with quotient a free group of rank two, as claimed.

(iii) X = T is a segment e with vertices v_{1}, v_{2}, say t(e) = v_{2}. Set G_{i} := Γ(v_{i}), i = 1, 2, and S := Γ(e). Then Γ = G_{1} ∗_{S} G_{2}, with the canonical embeddings given by ē: S → G_{1} and e : S → G_{2}. Moreover, let a_{1} := (G_{1} : Sē) and a_{2} := (G_{2} : S^{e}). By symmetry, we may suppose that a_{1} ≤ a_{2}, we have a_{1} ≥ 2 by our assumption that (Γ(−), X, T) is normalised, and the requirement that μ(Γ) = 2 boils down to the (equivalent) equation

a_{1}a_{2} − a_{1} − a_{2} = gcd(a_{1}, a_{2}).  (7.1)

Since gcd(a_{1}, a_{2}) ≤ a_{1}, Equation (7.1) implies that

a_{1} ≤ a_{2} ≤ \frac{2a_{1}}{a_{1} − 1},  (7.2)

which in turn leads to a_{1}^{2} ≤ 3a_{1}. Given our present constraints, the last inequality is satisfied only for a_{1} = 2 and a_{1} = 3. If a_{1} = 2, then we find from (7.2) that 2 ≤ a_{2} ≤ 4, while, for a_{1} = 3, we get a_{2} = 3. Thus, the only possibilities are

(a_{1}, a_{2}) = (2, 2), (2, 3), (2, 4), (3, 3),

and, inserting these into (7.1), the possible solution a_{1} = 2 = a_{2} is eliminated, while the remaining three pairs all solve (7.1), whence the result in that case.

(iv) X consists of a segment e_{1} with vertices v_{1} and v_{2}, say t(e_{1}) = v_{2}, with a loop e_{2} attached at v_{2}. For i = 1, 2, set G_{i} := Γ(v_{i}), and let S_{i} := Γ(e_{i}). Then Γ = G_{1} ∗_{S_{1}} Γ_{2},

where Γ_{2} is the fundamental group of the loop e_{2} with bounding vertex v_{2}, and the canonical embeddings are given by the maps ē_{1} : S_{1} → G_{1} and ẽ_{1} : S_{1} →^{e_{1}} G_{2} → Γ_{2}. Let

a_{1} := (G_{1} : Sē_{1} ; 1), a_{2} := (G_{2} : S_{1}^{e_{1}}), and a′_{2} := (G_{2} : S_{2}^{e_{2}}). Then

m_{Γ} = lcm(|G_{1}|, |G_{2}|) = |S_{1}| · lcm(a_{1}, a_{2}) = |S_{2}| · lcm(a_{1}, a_{2})a′_{2}/a_{2},

and the condition that μ(Γ) = 2 translates into the equation

a_{1}a_{2} + a_{1}a′_{2} − a_{1} − a_{2} = gcd(a_{1}, a_{2}).  (7.3)

Moreover, we have a_{1}, a_{2} ≥ 2 by our assumption that (Γ(−), X, T) is normalised, where T is the unique spanning tree of X. Suppose first that a_{1} ≤ a_{2}. Then (7.3) gives

2 ≤ a_{1} ≤ a_{2} ≤ \frac{(2 − a′_{2})a_{1}}{a_{1} − 1} ≤ \frac{a_{1}}{a_{1} − 1} ≤ 2.

This forces a_{1} = a_{2} = 2, and from (7.3) we deduce that a′_{2} = 1. Now suppose that a_{1} ≥ a_{2}. Then (7.3) yields

2 ≤ a_{2} ≤ a_{1} ≤ \frac{2a_{2}}{a_{2} + a′_{2} − 1} ≤ 2,

which again leads to the solution a_{1} = a_{2} = 2 and a′_{2} = 1. Assertion (iv) now follows.

(v) X = T is a path (v_{1}, e_{1}, v_{2}, e_{2}, v_{3}) of length 2. For i = 1, 2, 3, set G_{i} := Γ(v_{i}), and let S_{j} := Γ(e_{j}) for j = 1, 2. Then Γ = (G_{1} ∗_{S_{1}} G_{2}) ∗_{S_{2}} G_{3}. Since μ(Γ) = 2, we have

\frac{m_{Γ}}{|S_{1}|} + \frac{m_{Γ}}{|S_{2}|} − \frac{m_{Γ}}{|G_{1}|} − \frac{m_{Γ}}{|G_{2}|} − \frac{m_{Γ}}{|G_{3}|} = 1.  (7.4)

As (Γ(−), X, T) is normalised, we have

\frac{m_{Γ}}{|G_{1}|} ≤ \frac{m_{Γ}}{2|S_{1}|} and \frac{m_{Γ}}{|G_{2}|} ≤ \frac{m_{Γ}}{2|S_{2}|},

so that (7.4) gives

\frac{m_{Γ}}{2|S_{1}|} + \frac{m_{Γ}}{2|S_{2}|} − \frac{m_{Γ}}{|G_{3}|} ≤ 1.

Again by normalisation,

\frac{m_{Γ}}{|G_{3}|} ≤ \frac{m_{Γ}}{2|S_{2}|},

thus

1 ≤ max \{\frac{|G_{1}|}{2|S_{1}|}, \frac{|G_{2}|}{2|S_{1}|}\} ≤ \frac{m_{Γ}}{2|S_{1}|} ≤ 1,

implying

m_{Γ} = |G_{1}| = |G_{2}| = 2|S_{1}|.

Using this information in (7.4), we now find that

m_{Γ} (\frac{1}{|S_{2}|} − \frac{1}{|G_{3}|}) = 1,

implying first m_{Γ} = 2|S_{2}| by normalisation, and then |G_{3}| = m_{Γ}. □

Remark 8. By considering the type and the number of conjugacy classes of maximal finite subgroups, one shows again that any two groups from different classes in Proposition 7 are not isomorphic.

7.2. Some consequences of Proposition 7. Using the structural classification afforded by Proposition 7 in conjunction with (2.6), (2.9), and (2.10), we obtain, for each of the five cases in Proposition 7, a recurrence relation for the corresponding function f_{λ}(Γ). The result is as follows:

(a) In Cases (i) and (iv),

f_{λ+1}(Γ) = \frac{2λ + 3}{2}m_{Γ}f_{λ}(Γ) + ∑_{μ=1}^{λ−1} f_{μ}(Γ)f_{λ−μ}(Γ), λ ≥ 1.  (7.5)

(b) In Case (ii),

f_{λ+1}(Γ) = (λ + 2)m_{Γ}f_{λ}(Γ) + ∑_{μ=1}^{λ−1} f_{μ}(Γ)f_{λ−μ}(Γ), λ ≥ 1.  (7.6)

(c) In Cases (iii) and (v),

f_{λ+1}(Γ) = (λ + 1)m_{Γ}f_{λ}(Γ) + ∑_{μ=1}^{λ−1} f_{μ}(Γ)f_{λ−μ}(Γ), λ ≥ 1,  (7.7)

with corresponding initial conditions

(a) f_{1}(Γ) = m_{Γ}^{2}/2,

(b) f_{1}(Γ) = m_{Γ}^{2},

(c) f_{1}(Γ) = \begin{cases}(m_{Γ} − |S|)|S|, & Case (iii), \\ (m_{Γ}/2)^{2}, & Case (v). \end{cases}

We record two applications of Equations (7.5)–(7.7) (and their initial conditions).

Corollary 9. For a virtually free group Γ with μ(Γ) = 2 and Γ ≅ C̸_{2} ∗ C_{2} ∗ C_{2}, we have

f_{λ+1}(Γ) − f_{λ}(Γ) ≥ m_{Γ}(λ + 1)!  (7.8)

for all λ ≥ 1. For Γ ≅ C_{2} ∗ C_{2} ∗ C_{2}, the estimate (7.8) holds for all λ ≥ 2.

Proof. This follows from the above recurrence relations plus initial conditions by an immediate induction on λ. □

Corollary 10. Let Γ be virtually free of rank μ(Γ) = 2. In the cases (iii)_{1}, (iii)_{3}, and (v), we have, with |S| ≡ 1 (mod 2) respectively |S_{1}| ≡ 1 (mod 2),

f_{λ}(Γ) ≡ 1 (mod 2) if, and only if, λ = 2^{m} − 1 for some integer m ≥ 1.

In all other cases, the function f_{λ}(Γ) is constant modulo 2.

Proof. We focus on Case (iii)_{1} with |S| ≡ 1 (mod 2); the proof in Cases (iii)_{3} and (v) is completely analogous, while the fact that f_{λ}(Γ) is constant modulo 2 in all other cases is immediate.

We denote by Λ the set of integers of the form λ = 2^{m} − 1, m = 1, 2, …, and prove the equivalence

f_{λ}(Γ) ≡ 1 (mod 2) if, and only if, λ ∈ Λ,  (7.9)

for λ ≥ 1 by induction on λ. The assumption that |S| ≡ 1 (mod 2) implies that

f_{1}(Γ) = 5|S|^{2} ≡ 1 (mod 2),

so that (7.9) is true for λ = 1. Suppose that (7.9) is true for all λ ≤ L with some L ≥ 1, and consider λ = L + 1. From (7.7) and the fact that m_{Γ} = 6|S| ≡ 0 (mod 2), we infer that, for λ ≥ 1,

f_{λ+1}(Γ) ≡ \begin{cases}f_{λ/2}(Γ) (mod 2), & 2 | λ, \\ 0 (mod 2), & 2 ∤ λ. \end{cases}

If L + 1 ∈ Λ, i.e., L + 1 = 2^{m} − 1 for some m ≥ 2, then L = 2(2^{m−1} − 1) ≡ 0 (mod 2) and L/2 ∈ Λ, thus f_{L+1}(Γ) ≡ 1 (mod 2) by the induction hypothesis. Suppose, on the other hand, that L + 1 ∉ Λ. If L ≡ 1 mod 2), then f_{L+1}(Γ) ≡ 0 mod 2). Thus we are left with the case where L + 1 ∉ Λ and L ≡ 0 mod 2). But then L/2 ∉ Λ, and the induction hypothesis gives

f_{L+1}(Γ) ≡ f_{L/2}(Γ) ≡ 0 (mod 2),

completing the proof. □

Corollary 10 serves well to illustrate the main result of [8]:

(1) In Case (i) of Proposition 7, we have 2 | m_{Γ} and

μ_{2}(Γ) = \begin{cases}1, & |A| ≡ 1 (mod 2), \\ 2, & |A| ≡ 0 (mod 2). \end{cases}

In particular, we obtain that μ_{2}(Γ) > 0, so Case (III)_{2} of [8, Theorem 1] applies, asserting that f_{λ}(Γ) is ultimately periodic modulo 2 in this case. Indeed, by Corollary 10, f_{λ}(Γ) is constant modulo 2.

(2) In Case (ii) of Proposition 7, we either have 2 ∤ m_{Γ}, or 2 | m_{Γ} and μ_{2}(Γ) = 2 > 0, so f_{λ}(Γ) is ultimately periodic modulo 2 in this case according to Case (III)_{1} respectively (III)_{2} of [8, Theorem 1]. Indeed, f_{λ}(Γ) is again constant modulo 2 by Corollary 10.

(3) In Case (iii)_{1} of Proposition 7, we have 2 | m_{Γ} and

μ_{2}(Γ) = \begin{cases}0, & |S| ≡ 1 (mod 2), \\ 2, & |S| ≡ 0 (mod 2), \end{cases}

so f_{λ}(Γ) is ultimately periodic modulo 2 according to [8, Theorem 1] if, and only if, |S| ≡ 0 (mod 2), which coincides with the corresponding assertion of Corollary 10.

(4) In Case (iii)_{2} of Proposition 7, we either have |S| ≡ 1 (mod 2), and so 2 ∤ m_{Γ} = 3|S|, or |S| ≡ 0 (mod 2), in which case 2 | m_{Γ} and μ_{2}(Γ) = 2 > 0. Hence, ultimate periodicity of the function f_{λ}(Γ) modulo 2 follows again from Case (III)_{1} respectively Case (III)_{2} of [8, Theorem 1], while Corollary 10 asserts that f_{λ}(Γ) is constant modulo 2 in that case.

(5) In Case (iii)_{3} of Proposition 7, we have 2 | m_{Γ} = 4|S| and

μ_{2}(Γ) = \begin{cases}0, & |S| ≡ 1 (mod 2), \\ 2, & |S| ≡ 0 (mod 2). \end{cases}

Hence, according to [8, Theorem 1], the function f_{λ}(Γ) is ultimately periodic modulo 2 if, and only if, |S| ≡ 0 (mod 2), which is in accordance with the corresponding assertion of Corollary 10.

(6) In Case (iv) of Proposition 7, we have 2 | m_{Γ} = 2|S| and

μ_{2}(Γ) = \begin{cases}1, & |S| ≡ 1 (mod 2), \\ 2, & |S| ≡ 0 (mod 2). \end{cases}

In particular, we obtain that μ_{2}(Γ) > 0, so that ultimate periodicity of f_{λ}(Γ) follows from Case (III)_{2} of [8, Theorem 1], while Corollary 10 asserts that f_{λ}(Γ) is constant modulo 2 in that case.

(7) Finally, in Case (v) of Proposition 7, we have 2 | m_{Γ} = 2|S_{1}| and

μ_{2}(Γ) = \begin{cases}0, & |S_{1}| ≡ 1 (mod 2), \\ 2, & |S_{1}| ≡ 0 (mod 2). \end{cases}

Hence, according to [8, Theorem 1], the function f_{λ}(Γ) is ultimately periodic modulo 2 if, and only if, |S_{1}| ≡ 0 (mod 2), in accordance with the corresponding assertion of Corollary 10.

8. Some criteria for a virtually free group to be ‘large’

Our final result collects together a number of equivalent conditions on a finitely generated virtually free group Γ which all say, in one way or another, that Γ is ‘large’ in some particular sense. Perhaps the most obvious condition in this direction is given by Pride’s concept of being ‘as large as a free group of rank 2’. The concept of ‘largeness’ for groups, first introduced by S. Pride in [16], and further developed in [5], depends on a certain preorder ⪯ on the class of groups, defined in [5] as follows: let G and H be groups. Then we write H ⪯ G, if there exist

(a) a subgroup G^{0} of finite index in G;

(b) a subgroup H^{0} of finite index in H, and a finite normal subgroup N^{0} of H^{0};

(c) a homomorphism from G^{0} onto H^{0}/N^{0}.

We write H ∼ G if H ⪯ G and G ⪯ H, and we denote by [G] the equivalence class of the group G under ∼. By abuse of notation, we also denote by ⪯ the preorder induced on the class of equivalence classes of groups. The finitely generated groups which are ‘largest’ in Pride’s sense are the ones having a subgroup of finite index which can be mapped homomorphically onto the free group F_{2} of rank 2.

Another, more topological, way of saying that a finitely generated virtually free group is ‘large’, is that it has infinitely many ends. Here, the number e(Γ) of ends of a group Γ is defined as

e(Γ) = \begin{cases}dim H^{0}(Γ, Hom_{ℤ}(ℤΓ, ℤ_{2})/ℤ_{2}Γ), & if Γ is infinite, \\ 0, & if Γ is finite. \end{cases}

The reader is referred to [2] or [3, Sec. 2] for an introduction to the theory of ends of a group from an algebraic point of view; for a discussion from a more topological viewpoint, see, for instance, [6], [7], or [21].

Proposition 11. Let Γ be a finitely generated virtually free group, and let (Γ(−), X) be a finite graph of finite groups with fundamental group Γ, chosen so as to satisfy the normalisation condition (3.1) of Lemma 1. Then the following assertions on Γ are equivalent:

(i) χ(Γ) < 0.

(ii) μ(Γ) ≥ 2.

(iii) Γ has infinitely many ends.

(iv) The function f_{λ}(Γ) is strictly increasing.

(v) Γ ∼ F_{2} in the sense of Pride’s preorder ⪯ on groups, where F_{2} denotes the free group of rank 2.

(vi) Γ has fast subgroup growth in the sense that the inequality s_{nj}(Γ) ≥ c · n! holds for some fixed positive integer j, some constant c > 0, and all n ≥ 1. Here s_{m}(Γ) denotes the number of subgroups of index m in Γ.

(vii) If X has only one vertex v, then either X has more than one geometric edge, or E(X) = {e_{1}, ē_{1}} and (Γ(v) : Γ(e_{1})^{e_{1}}) ≥ 2; if |V (X)| ≥ 2, then X is not a tree, or X is a tree with more than one geometric edge, or E(X) = {e_{1}, ē_{1}} and

χ(Γ_{0}) < 0, where Γ_{0} := Γ_{o(e_{1})} ∗_{Γ(e_{1})} Γ_{t(e_{1})}.

Proof. (i) ⇔ (ii). This is immediate from Formula (2.8) plus the fact that μ(Γ) is integral.

(ii) ⇔ (iii). This follows from [3, Prop. 2.1] (i.e., the fact that the number of ends is invariant when passing to a subgroup of finite index) and Examples 1 and 2 in [3] computing the number of ends of a free product, respectively of C_{∞}.

(ii) ⇔ (iv). This follows from [13, Theorem 4] in conjunction with Corollary 6.

(ii) ⇒ (v). If μ(Γ) ≥ 2, then Γ contains a free group F of rank at least 2, with (Γ : F) = m_{Γ} < ∞; in particular, F_{2} ⪯ Γ. Since [F_{2}] is largest with respect to the preorder ⪯ among all equivalence classes of finitely generated groups, we also have Γ ⪯ F_{2}, so Γ ∼ F_{2}, as claimed.

(v) ⇒ (vi). Suppose that Γ ∼ F_{2}. Then there exists a subgroup Δ ≤ Γ of index (Γ : Δ) = j < ∞ and a surjective homomorphism φ : Δ → F_{2}. From this plus Newman’s asymptotic estimate [15, Theorem 2]

s_{n}(F_{r}) ∼ n(n!)^{r−1} as n → ∞, r ≥ 2,

it follows that

s_{jn}(Γ) ≥ s_{n}(Δ) ≥ s_{n}(F_{2}) ≥ c · n · n! ≥ c · n!

for n ≥ 1 and some constant c > 0, whence (vi).

(vi) ⇒ (ii). If μ(Γ) ≤ 1, then either Γ is finite, so s_{n}(Γ) = 0 for sufficiently large n, or Γ is virtually infinite-cyclic, implying

s_{n}(Γ) ≤ n^{α}, n ≥ 1,

for some constant α, by [10, Cor. 1.4.3]; see also [18]. In both cases, Condition (vi) does not hold.

(ii) ⇔ (vii). This follows by splitting the Euler characteristic χ(Γ) as in the proof of Proposition 4, making use of Lemmas 1 and 2. □

References

[1] K. S. Brown, Cohomology of groups, Springer-Verlag, New York, 1982.

[2] D. E. Cohen, Ends and free products of groups, Math. Zeitschr. 114 (1970), 9–18.

[3] D. E. Cohen, Groups of Cohomological Dimension One, Lecture Notes in Mathematics, vol. 245, Springer-Verlag, Berlin–Heidelberg–New York, 1972.

[4] A. Dress and T. W. Müller, Decomposable functors and the exponential principle, Adv. Math. 129 (1997), 188–221.

[5] M. Edjvet and S. J. Pride, The concept of “largeness” in group theory II. In: Proc. Groups-Korea 1983, Lecture Notes in Math., vol. 1098, Springer-Verlag, Berlin-Heidelberg-New York, 1985, pp. 29–54.

[6] H. Freudenthal, Über die Enden diskreter Räume und Gruppen, Comment. Math. Helv. 17 (1944), 1–38.

[7] H. Hopf, Enden offener Räume und unendliche diskontinuierliche Gruppen, Comment. Math. Helv. 16 (1943), 81–100.

[8] C. Krattenthaler and T. W. Müller, Periodicity of free subgroup numbers modulo prime powers, J. Algebra 452 (2016), 372–389.

[9] C. Krattenthaler and T. W. Müller, Free subgroup numbers modulo prime powers: the nonperiodic case, preprint; arχiv.org:1602.08723.

[10] A. Lubotzky and D. Segal, Subgroup Growth, Progress in Mathematics, vol. 212, Birkhäuser– Verlag, Basel-Boston-Berlin, 2003.

[11] R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, Springer-Verlag Berlin-Heidelberg-New York, 1977.

[12] T. W. Müller, A group-theoretical generalization of Pascal’s triangle, Europ. J. Conbinatorics 12 (1991), 43–49.

[13] T. W. Müller, Combinatorial aspects of finitely generated virtually free groups, J. London Math. Soc. (2) 44 (1991), 75–94.

[14] T. W. Müller, Parity patterns in Hecke groups and Fermat primes, in: Groups: Topological, Combinatorial and Arithmetic Aspects, Proceedings of a conference held 1999 in Bielefeld (T. W. Müller, ed.), LMS Lecture Note Series, vol. 311, Cambridge University Press, Cambridge, 2004, pp. 327– 374.

[15] M. Newman, Asymptotic formulas related to free products of cyclic groups, Math. Comp. 30 (1976), 838–846.

[16] S. J. Pride, The concept of largeness in group theory. In: Word Problems II, North Holland Publishing Company, 1980, pp. 299–335.

[17] O. Schreier, Die Untergruppen der freien Gruppen, Abh. Math. Sem. Univ. Hamburg 5 (1927), 161–183.

[18] D. Segal, Subgroups of finite index in soluble groups I. In: Groups St Andrews 1985, London Math. Soc. Lecture Note Series, vol. 121, Cambridge University Press, Cambridge, 1986, pp. 307–314.

[19] J.-P. Serre, Cohomologie des groupes discrets. In: Prospects in Mathematics, Ann. Math. Stud., vol. 70, Princeton University Press, 1971, pp. 77–169.

[20] J.-P. Serre, Arbres, Amalgames, SL_{2}, Astérisque, vol. 46, Société mathématique de France, Paris, 1977.

[21] E. Specker, Die erste Cohomologiegruppe von Überlagerungen und Homotopieeigenschaften dreidimensionaler Mannigfaltigkeiten, Comment. Math. Helv. 23 (1949), 303–333.

[22] J. Stallings, On torsion-free groups with infinitely many ends, Ann. Math. 88 (1968), 312–334.

[23] C. T. C. Wall, Poincaré complexes: I, Ann. Math. 86 (1967), 213–245.

†Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, A-1090 Vi-

enna, Austria. WWW: http://www.mat.univie.ac.at/~kratt.

∗School of Mathematical Sciences, Queen Mary & Westfield College, University of London, Mile End Road, London E1 4NS, United Kingdom.