Normalising graphs of groups

Abstract

We discuss a partial normalisation of a finite graph of finite groups $(\Gamma (-), 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: (1) an important inequality for the number of edges in a Stallings decomposition $\Gamma \cong \pi _1(\Gamma (-), X)$ of a finitely generated virtually free group, (2) the proof of equivalence of a number of conditions for such a group to be ‘large’, as well as (3) 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: (1) a short and elegant argument establishing the (well-known) classification of virtually infinite-cyclic groups due originally to Stallings and Wall, (2) the classification of virtually free groups of free rank 2 together with some number-theoretic consequences,¹ and (3) the equivalence of a number of conditions on a finitely generated virtually free group $\Gamma$ expressing, in one way or other, the fact that $\Gamma$ is large; cf. Propositions 4, 7, and 11. In Sect. 5, we also show that, (4) for a normalised decomposition $(\Gamma (-), X)$ of a finitely generated virtually free group $\Gamma$, the number of geometric edges of the graph X is bounded above by the free rank of $\Gamma$; 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].

2 Some preliminaries on finitely generated virtually free groups

Our notation and terminology here follows Serre’s book [19]; in particular, the category of graphs used is described in [19, §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) \rightarrow E(X)$ (reversal of orientation), and there are two functions $o,t: E(X)\rightarrow V(X)$ assigning to an edge $e\in E(X)$ its origin o(e) and terminus t(e), such that $t(\bar{e}) = 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 $\mathcal {O}(X)$ consists of a choice of exactly one edge in each pair $\{e, \bar{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 $\Gamma$ be a finitely generated virtually free group with Stallings decomposition$(\Gamma (-), X)$; that is, $(\Gamma (-), X)$ is a finite graph of finite groups with fundamental group $\pi _1(\Gamma (-), X) \cong \Gamma$. If $\mathfrak {F}$ is a free subgroup of finite index in $\Gamma$ then, following an idea of C. T. C. Wall, one defines the (rational) Euler characteristic $\chi (\Gamma )$ of $\Gamma$ as

$$\begin{aligned} \chi (\Gamma ) = - \frac{\mathrm {rk}(\mathfrak {F}) - 1}{(\Gamma :\mathfrak {F})}. \end{aligned}$$

(2.1)

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

$$\begin{aligned} \chi (\Gamma ) = \sum _{v\in V(X)} \frac{1}{\vert \Gamma (v)\vert }\,-\,\sum _{e\in \mathcal {O}(X)} \frac{1}{\vert \Gamma (e)\vert }. \end{aligned}$$

(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 $\chi _T(\Gamma )$ of $\Gamma$ relative to the tree T canonically associated with $\Gamma$ in the sense of Bass–Serre theory; cf. [1, Chap. IX, Prop. 7.3] or [18, Prop. 14]. We remark that a finitely generated virtually free group $\Gamma$ is largest among finitely generated groups in the sense of Pride’s preorder [15] (i.e., $\Gamma$ has a subgroup of finite index, which can be mapped onto the free group of rank 2) if, and only if, $\chi (\Gamma )<0$; see Proposition 11 in Sect. 8.

Denote by $m_\Gamma$ the least common multiple of the orders of the finite subgroups in $\Gamma$, so that, again in terms of the above Stallings decomposition of $\Gamma$,

$$\begin{aligned} m_\Gamma = {\text {lcm}}\big \{\vert \Gamma (v)\vert :\, v\in V(X)\big \}. \end{aligned}$$

(This formula essentially follows from the well-known fact that a finite group has a fixed point when acting on a tree.) The type $\tau (\Gamma )$ of a finitely generated virtually free group $\Gamma \cong \pi _1(\Gamma (-), X)$ is defined as the tuple

$$\begin{aligned} \tau (\Gamma ) = \big (m_\Gamma ; \zeta _1(\Gamma ), \ldots , \zeta _\kappa (\Gamma ), \ldots , \zeta _{m_\Gamma }(\Gamma )\big ), \end{aligned}$$

where the $\zeta _\kappa (\Gamma )$’s are integers indexed by the divisors of $m_\Gamma$, given by

$$\begin{aligned} \zeta _\kappa (\Gamma ) = \big \vert \big \{e\in \mathcal {O}(X):\, \vert \Gamma (e)\vert \,\big \vert \, \kappa \big \}\big \vert \,-\, \big \vert \big \{v\in V(X):\, \vert \Gamma (v)\vert \,\big \vert \, \kappa \big \}\big \vert . \end{aligned}$$

It can be shown that the type $\tau (\Gamma )$ is in fact an invariant of the group $\Gamma$, i.e., independent of the particular decomposition of $\Gamma$ in terms of a graph of groups $(\Gamma (-), X)$, and that two finitely generated virtually free groups $\Gamma _1$ and $\Gamma _2$ contain the same number of free subgroups of index n for each positive integer n if, and only if, $\tau (\Gamma _1) = \tau (\Gamma _2)$; cf. [13, Theorem 2]. We have $\zeta _\kappa (\Gamma )\ge 0$ for $\kappa <m_\Gamma$ and $\zeta _{m_\Gamma }(\Gamma )\ge -1$ with equality occurring in the latter inequality if, and only if, $\Gamma$ 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 $\Gamma$ can be expressed in terms of the type $\tau (\Gamma )$ via

$$\begin{aligned} \chi (\Gamma ) = - m_\Gamma ^{-1} \sum _{\kappa \mid m_\Gamma } \varphi (m_\Gamma /\kappa ) \,\zeta _\kappa (\Gamma ), \end{aligned}$$

(2.3)

where $\varphi$ 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 $\Gamma$ -action on a set $\Omega$ to be a $\Gamma$-action on $\Omega$ which is free when restricted to finite subgroups, and let

$$\begin{aligned} g_\lambda (\Gamma ):= \frac{\text{ number } \text{ of } \text{ torsion-free } \Gamma \text{-actions } \text{ on } \text{ a } \text{ set } \text{ with } \lambda m_\Gamma \text{ elements }}{(\lambda m_\Gamma )!},\quad \lambda \ge 0; \end{aligned}$$

(2.4)

in particular, $g_0(\Gamma )=1$. The sequences $\big (f_\lambda (\Gamma )\big )_{\lambda \ge 1}$ and $\big (g_\lambda (\Gamma )\big )_{\lambda \ge 0}$ are related via the Hall-type convolution formula²

$$\begin{aligned} \sum _{\mu =0}^{\lambda -1} g_\mu (\Gamma ) f_{\lambda -\mu }(\Gamma ) = m_\Gamma \lambda g_\lambda (\Gamma ),\quad \lambda \ge 1. \end{aligned}$$

(2.5)

Introducing the generating functions

$$\begin{aligned} F_\Gamma (z) := \sum _{\lambda \ge 0} f_{\lambda +1}(\Gamma ) z^\lambda \, \text{ and } \, G_\Gamma (z):= \sum _{\lambda \ge 0} g_\lambda (\Gamma ) z^\lambda , \end{aligned}$$

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

$$\begin{aligned} F_\Gamma (z) = m_\Gamma \frac{d}{dz}\big (\log G_\Gamma (z)\big ). \end{aligned}$$

(2.6)

Moreover, a careful analysis of the universal mapping property associated with the presentation $\Gamma \cong \pi _1(\Gamma (-), X)$ leads to the explicit formula

$$\begin{aligned} g_\lambda (\Gamma ) = \frac{\prod \nolimits _{e\in \mathcal {O}(X)} (\lambda m_\Gamma /\vert \Gamma (e)\vert )!\,\vert \Gamma (e)\vert ^{\lambda m_\Gamma /\vert \Gamma (e)\vert }}{\prod \nolimits _{v\in V(X)}(\lambda m_\Gamma /\vert \Gamma (v)\vert )!\,\vert \Gamma (v)\vert ^{\lambda m_\Gamma /\vert \Gamma (v)\vert }},\quad \lambda \ge 0 , \end{aligned}$$

(2.7)

for $g_\lambda (\Gamma )$, where $\mathcal {O}(X)$ is any orientation of X; cf. [13, Prop. 3].

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

$$\begin{aligned} \mu (\Gamma ) + m_\Gamma \chi (\Gamma ) = 1, \end{aligned}$$

(2.8)

which shows in particular that $\mu (\Gamma )$ is well-defined. From Formula (2.7) it may be deduced that the sequence $g_\lambda (\Gamma )$ is of hypergeometric type and that its generating function $G_\Gamma (z)$ satisfies a homogeneous linear differential equation

$$\begin{aligned} \theta _0(\Gamma ) G_\Gamma (z) \,+ \,(\theta _1(\Gamma ) z - m_\Gamma ) G'_\Gamma (z) \,+ \,\sum _{\mu =2}^{\mu (\Gamma )} \theta _\mu (\Gamma ) z^\mu G^{(\mu )}_\Gamma (z) = 0 \end{aligned}$$

(2.9)

of order $\mu (\Gamma )$ with integral coefficients $\theta _\mu (\Gamma )$ given by

$$\begin{aligned} \theta _\mu (\Gamma )&= \frac{1}{\mu !} \sum _{j=0}^\mu (-1)^{\mu -j} \left( {\begin{array}{c}\mu \\ j\end{array}}\right) m_\Gamma (j+1) \prod _{\kappa \mid m_\Gamma }\,\underset{(m_\Gamma , k) = \kappa }{\prod _{1\le k\le m_\Gamma }} (jm_\Gamma + k)^{\zeta _\kappa (\Gamma )},\nonumber \\&\quad 0\le \mu \le \mu (\Gamma ); \end{aligned}$$

(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 $\Gamma$ by a graph of groups avoiding trivial amalgamations along a maximal tree. This is achieved via the following.

Lemma 1

(Normalisation) Let $(\Gamma (-), X)$ be a (connected) graph of groups with fundamental group $\Gamma ,$ and suppose that X has only finitely many vertices. Then there exists a graph of groups $(\Delta (-), Y)$ with $\vert V(Y)\vert < \infty$ and a spanning tree T in Y,  such that $\pi _1(\Delta (-),Y) \cong \Gamma$, and such that³

$$\begin{aligned} \Delta (e)^e \ne \Delta (t(e))\, \text{ and } \, \Delta (e)^{\bar{e}} \ne \Delta (o(e)),\quad \text{ for } e\in E(T). \end{aligned}$$

(3.1)

Moreover, if $(\Gamma (-), X)$ satisfies the finiteness condition

• $(F_1)$       X is a finite graph,

or

• $(F_2)$       $\Gamma (v)$ is finite for every vertex $v\in V(X),$

then we may choose $(\Delta (-), Y)$ so as to enjoy the same property.

Proof

Choose a spanning tree S in X, and call an edge $e\in E(S)$ trivial, if at least one of the associated embeddings $e: \Gamma (e) \rightarrow \Gamma (t(e))$ and $\bar{e}: \Gamma (e) \rightarrow \Gamma (o(e))$ is an isomorphism. If S contains a trivial edge $e_1$—to fix ideas, say $\Gamma (e_1)^{e_1} = \Gamma (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 $(\Gamma '(-), X')$ with spanning tree $S'$ in $X'$. More precisely, this means that we let

$$\begin{aligned} E(X')&= E(X) {\setminus } \{e_1, \bar{e}_1\},\\ E(S')&= E(S) {\setminus } \{e_1, \bar{e}_1\},\\ V(X')&= V(S') = V(X){\setminus } \{t(e_1)\}, \end{aligned}$$

set

$$\begin{aligned} t'(e):= o(e_1), \quad \text{ for } e\in E(X') \text{ with } t(e) = t(e_1), \end{aligned}$$

and define new embeddings via

$$\begin{aligned}&\Gamma (e) \overset{e}{\longrightarrow } \Gamma (t(e_1)) \overset{e_1^{-1}}{\longrightarrow } \Gamma (e_1) \overset{\bar{e}_1}{\longrightarrow } \Gamma (o(e_1)) = \Gamma (t'(e)),\nonumber \\&\quad \text{ for } e\in E(X') \text{ with } t(e)=t(e_1), \end{aligned}$$

(3.2)

leaving incidence and embeddings unchanged wherever possible. Clearly, $S'$, the result of contracting the geometric edge $\{e_1, \bar{e}_1\}$ and deleting the vertex $t(e_1)$, is still a spanning tree for $X'$ and, if $(\Gamma (-),X)$ has property $(F_1)$ or $(F_2)$, then so does $(\Gamma '(-), X')$ by construction.

It remains to see that the fundamental group of the new graph of groups $(\Gamma '(-), X')$ is isomorphic to $\Gamma$. The fundamental group

$$\begin{aligned} \pi _1(\Gamma (-),X,S) \end{aligned}$$

of the graph of groups $(\Gamma (-),X)$ at the spanning tree S is generated by the groups $\Gamma (v)$ for $v\in V(X)$ plus extra generators $\gamma _e$ for $e\in \mathcal {O}(X)-E(S)$, where $\mathcal {O}(X)$ is any orientation of X, subject to the relations

$$\begin{aligned} a^e= & {} a^{\bar{e}},\quad \text{ for } e\in \mathcal {O}(S) \text{ and } a\in \Gamma (e), \end{aligned}$$

(3.3)

$$\begin{aligned} \gamma _e a^e \gamma _e^{-1}= & {} a^{\bar{e}},\quad \text{ for } e\in \mathcal {O}(X)-E(S) \text{ and } a\in \Gamma (e), \end{aligned}$$

(3.4)

where $\mathcal {O}(S)$ is the orientation of the tree S induced by $\mathcal {O}(X)$, with a corresponding presentation for $\pi _1(\Gamma '(-),X',S')$; see §5.1 in [19, Chap. I]. The relations (3.3) corresponding to the geometric edge $\{e_1, \bar{e}_1\}$ identify $\Gamma (t(e_1))$ isomorphically with a subgroup of $\Gamma (o(e_1))$; we can thus delete the generators $\gamma \in \Gamma (t(e_1))$ against those relations by Tietze moves. This yields a presentation for $\pi _1(\Gamma (-), X,S)$ with the same set of generators as $\pi _1(\Gamma '(-), 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 $\Gamma (o(e_1))$, which leads exactly to the corresponding relations of $\pi _1(\Gamma '(-), X',S')$ obtained by extending the embedding $e: \Gamma (e) \rightarrow \Gamma (t(e_1))$ in the natural way as given in (3.2). Hence, $\pi _1(\Gamma (-), X,S) \cong \pi _1(\Gamma '(-), 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 $(\Delta (-), Y)$ with fundamental group $\Gamma$ and a spanning tree T in Y without trivial edges, such that $(\Delta (-),Y)$ enjoys the finiteness properties $(F_1), (F_2)$ whenever $(\Gamma (-),X)$ does. $\square$

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\in V(T)$ be any vertex. Then there exists one, and only one, orientation $\mathcal {O}(T)$ of T,  such that the assignment $e\mapsto t(e)$ defines a bijection $\psi _{v_0}: \mathcal {O}(T) \rightarrow V(T){\setminus }\{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 $\mathcal {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 $\vert V(T)\vert$, which we sketch briefly: by our condition on the map $\psi _{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 $\mathcal {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 $(\Gamma (-), X, T)$ be a finite graph of finite groups with maximal tree $T\le X$ and fundamental group $\pi _1(\Gamma (-), X) \cong \Gamma$. If $(\Gamma (-), X, T)$ satisfies the normalisation condition (3.1), then the number of edges $\vert E(X)\vert$ of the graph X is bounded above in terms of the free rank of $\Gamma$ via

$$\begin{aligned} \vert E(X)\vert \le 2 \mu (\Gamma ). \end{aligned}$$

(5.1)

Proof

We distinguish two cases.

• (a) $\vert V(X)\vert = 1$. Then $m_\Gamma = \vert \Gamma (v)\vert$, where $V(X) = \{v\}$, and the Euler characteristic of $\Gamma$ becomes

  $$\begin{aligned} \chi (\Gamma )&= \frac{1}{\vert \Gamma (v)\vert }\,-\, \sum _{e\in \mathcal {O}(X)} \frac{1}{\vert \Gamma (e)\vert }\\&= m_\Gamma ^{-1} \bigg (1 - \sum _{e\in \mathcal {O}(X)} \big (\Gamma (v) : \Gamma (e)^e\big )\bigg )\\&\le - m_\Gamma ^{-1} \big (\vert \mathcal {O}(X)\vert - 1\big ), \end{aligned}$$

  where $\mathcal {O}(X)$ is an arbitrary orientation of X. It follows that

  $$\begin{aligned} \mu (\Gamma ) = 1 - m_\Gamma \chi (\Gamma ) \ge \vert \mathcal {O}(X)\vert , \end{aligned}$$

  whence our claim in this case.

• (b) $\vert V(X)\vert \ge 2$. Then $E(T) \ne \emptyset$, and we may choose some edge $e_1\in E(T)$. Consider the tree T as rooted with root $v_1 = o(e_1)$ and associated orientation $\mathcal {O}_{v_1}(T)$ in the sense of Lemma 2. Extending $\mathcal {O}_{v_1}(T)$ to an orientation $\mathcal {O}(X)$ of X, we write

  $$\begin{aligned} \chi (\Gamma )= & {} \Big (\frac{1}{\vert \Gamma (o(e_1))\vert } + \frac{1}{\vert \Gamma (t(e_1))\vert } - \frac{1}{\vert \Gamma (e_1)\vert }\Big )\\&\quad +\sum _{e\in \mathcal {O}_{v_1}(T){\setminus }\{e_1\}}\Big (\frac{1}{\vert \Gamma (t(e))\vert } - \frac{1}{\vert \Gamma (e)\vert }\Big ) - \sum _{e\in \mathcal {O}(X){\setminus }\mathcal {O}_{v_1}(T)} \frac{1}{\vert \Gamma (e)\vert }. \end{aligned}$$

  Since the edge $e_1$ is not trivial, we have $2\vert \Gamma (e_1)\vert \le \vert \Gamma (o(e_1))\vert$ as well as $2\vert \Gamma (e_1)\vert \le \vert \Gamma (t(e_1))\vert$, thus

  $$\begin{aligned} \frac{1}{\vert \Gamma (o(e_1))\vert } + \frac{1}{\vert \Gamma (t(e_1))\vert }\, \le \, \frac{1}{\vert \Gamma (e_1)\vert }. \end{aligned}$$

  For the same reason, for $e\in \mathcal {O}_{v_1}(T){\setminus }\{e_1\}$, we have

  $$\begin{aligned} \frac{1}{\vert \Gamma (t(e))\vert } - \frac{1}{\vert \Gamma (e)\vert } = \frac{1-(\Gamma (t(e)) : \Gamma (e)^e)}{\vert \Gamma (t(e))\vert } \,\le \, - \frac{1}{\vert \Gamma (t(e))\vert }\, \le \, -\frac{1}{m_\Gamma }. \end{aligned}$$

  Putting together these observations, we find that

  $$\begin{aligned} \chi (\Gamma ) \le -m_\Gamma ^{-1}\big (\vert \mathcal {O}_{v_1}(T)\vert - 1\big ) - m_\Gamma ^{-1} \vert \mathcal {O}(X){\setminus }\mathcal {O}_{v_1}(T)\vert = -m_\Gamma ^{-1}\big (\vert \mathcal {O}(X)\vert - 1\big ), \end{aligned}$$

  from which our claim follows as before.$\square$

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. [21, 5.1] or [22, Lemma 4.1]. In this section, we shall give a short proof of the corresponding result (Proposition 4) based on the tools developed in Sects. 3 and 4. As a consequence of this classification result, we find that the function $f_\lambda (\Gamma )$ is constant for $\mu (\Gamma ) = 1$; cf. Corollary 6.

Proposition 4

A virtually infinite-cyclic group $\Gamma$ falls into one of the following two classes:

• (i) $\Gamma$ has a finite normal subgroup with infinite-cyclic quotient.

• (ii) $\Gamma$ is a free product $\Gamma = G_1 \underset{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 $(\Gamma (-),X)$ be a finite graph of finite groups with fundamental group $\Gamma$ and spanning tree T, chosen according to Lemma 1. The reader should observe that the assumption that $\Gamma$ is virtually infinite-cyclic in combination with (2.8) implies that $\chi (\Gamma )=0$.

If $\vert V(X)\vert = 1$, $V(X)=\{v\}$ say, then the above observation together with Formula (2.2) shows that X has exactly one geometric edge $\{e, \bar{e}\}$, and that the associated embeddings $e, \bar{e}: \Gamma (e)\rightarrow \Gamma (v)$ are isomorphisms. Hence, $\Gamma (v) \unlhd \Gamma$ and $\Gamma /\Gamma (v) \cong C_\infty$, which gives the desired result in Case (i).

If $\vert V(X)\vert >1$, we choose an edge $e_1\in E(T)$, introduce the orientation $\mathcal {O}_{v_0}(T)$ with respect to the base point $v_0=o(e_1)$, extend it to an orientation $\mathcal {O}(X)$ of X, and let $v_1=t(e_1)$. We then split the Euler characteristic of $\Gamma$ as follows:

$$\begin{aligned} 0 = \chi (\Gamma )= & {} \underset{v\ne v_0, v_1}{\sum _{v\in V(X)}} \frac{1}{\vert \Gamma (v)\vert }-\underset{e\ne e_1}{\sum _{e\in \mathcal {O}_{v_0}(T)}} \frac{1}{\vert \Gamma (e)\vert }+\left( \frac{1}{\vert \Gamma (v_0)\vert } + \frac{1}{\vert \Gamma (v_1)\vert } - \frac{1}{\vert \Gamma (e_1)\vert }\right) \nonumber \\&\quad -\sum _{e\in \mathcal {O}(X){\setminus } \mathcal {O}_{v_0}(T)} \frac{1}{\vert \Gamma (e)\vert }. \end{aligned}$$

(6.1)

By the normalisation condition (3.1) on $(\Gamma (-), X, T)$, we have

$$\begin{aligned} 2 \vert \Gamma (e_1)\vert \, \le \gamma := \min \big \{\vert \Gamma (v_0)\vert , \,\Gamma (v_1)\vert \big \}, \end{aligned}$$

so

$$\begin{aligned} \frac{1}{\vert \Gamma (v_0)\vert }\, +\, \frac{1}{\vert \Gamma (v_1)\vert }\, -\, \frac{1}{\vert \Gamma (e_1)\vert }\, \le \, \frac{2}{\gamma }\, -\, \frac{1}{\vert \Gamma (e_1)\vert }\, \le \, 0. \end{aligned}$$

(6.2)

Clearly, equality in (6.2) occurs if, and only if, $\Gamma (e_1)$ is of index 2 in both $\Gamma (v_0)$ and $\Gamma (v_1)$. Similarly, by the normalisation condition (3.1) and Lemma 2, we have

$$\begin{aligned} \underset{v\ne v_0, v_1}{\sum _{v\in V(X)}} \frac{1}{\vert \Gamma (v)\vert }-\underset{e\ne e_1}{\sum _{e\in \mathcal {O}_{v_0}(T)}} \frac{1}{\vert \Gamma (e)\vert }= \underset{e\ne e_1}{\sum _{e\in \mathcal {O}_{v_0}(T)}} \left( \frac{1}{\vert \Gamma (t(e))\vert } - \frac{1}{\vert \Gamma (e)\vert }\right) \le 0, \end{aligned}$$

with equality if, and only if, $\mathcal {O}_{v_0}(T) = \{e_1\}$. Also, trivially, the last sum on the right-hand side of (6.1) is non-negative, and vanishes if, and only if, $\mathcal {O}(X)=\mathcal {O}_{v_0}(T)$. Given this discussion, we conclude from (6.1) that $\Gamma = \Gamma (v_0) \underset{\Gamma (e_1)}{*} \Gamma (v_1)$, the amalgam being formed with respect to the embeddings $e_1: \Gamma (e_1) \rightarrow \Gamma (v_1)$ and $\bar{e}_1: \Gamma (e_1)\rightarrow \Gamma (v_0)$, and that $(\Gamma (v_0):\Gamma (e_1)^{\bar{e}_1}) = 2 = (\Gamma (v_1):\Gamma (e_1)^{e_1})$, whence the result in Case (ii). $\square$

Remark 5

• 1. In Case (i) of Proposition 4, we have $\zeta _\kappa =0$ for all $\kappa \mid m_\Gamma$ whereas, in Case (ii), $\zeta _{m_\Gamma }=-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 $\Gamma$ with quotient $C_2*C_2$, the infinite dihedral group.

Corollary 6

If $\Gamma$ is virtually infinite-cyclic, then the function $f_\lambda (\Gamma )$ is constant. More precisely, we have $f_\lambda (\Gamma )=m_\Gamma$ for $\lambda \ge 1$ in Case (i) of Proposition  4, while in Case (ii) we have $f_\lambda (\Gamma ) = \vert A\vert = m_\Gamma /2$.

Proof

If $\Gamma$ is as described in Case (i) of Proposition 4, then (2.7) shows that $g_\lambda (\Gamma )=1$ for $\lambda \ge 0$, leading to $f_\lambda (\Gamma )=m_\Gamma$ for all $\lambda \ge 1$ by (2.5) and an immediate induction on $\lambda$.

For $\Gamma$ as in Case (ii), Eq. (2.7) yields

$$\begin{aligned} g_\lambda (\Gamma ) = 2^{-2\lambda } \left( {\begin{array}{c}2\lambda \\ \lambda \end{array}}\right) ,\quad \lambda \ge 0. \end{aligned}$$

By the binomial theorem applied to the generating function $G_\Gamma (z)$ of the $g_\lambda (\Gamma )$’s, we obtain $G_\Gamma (z)=(1-z)^{-1/2}$, which transforms into the relation

$$\begin{aligned} F_\Gamma (z) = \frac{\vert m_\Gamma \vert }{2(1-z)} = \frac{\vert A\vert }{1-z} \end{aligned}$$

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

7 The case where $\mu (\Gamma )=2$

7.1 The classification result

Proposition 7

A virtually free group $\Gamma$ of rank $\mu (\Gamma )=2$ falls into one of the following five classes:

• (i) $\Gamma$ is an HNN-extension $\Gamma = G\underset{A,\phi }{*}$ with finite base group G,  associated subgroups A and $B=\phi (A),$ associated isomorphism $\phi : A\rightarrow B,$ and $(G:A)=2$.

• (ii) $\Gamma$ contains a finite normal subgroup G with quotient $\Gamma /G \cong F_2$ free of rank 2.

• (iii) $\Gamma$ is a free product $\Gamma = G_1 \underset{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) $\Gamma$ is a free product $\Gamma = G_1\underset{S}{*} \Gamma _2,$ where $G_1$ is finite, $\Gamma _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 $\Gamma _2$.

• (v) $\Gamma$ is of the form $\Gamma = (G_1 \underset{S_1}{*} G_2) \underset{S_2}{*} G_3$ with finite factors $G_1, G_2, G_3$ and subgroups $S_1, S_2$ satisfying $\vert G_1\vert = \vert G_2\vert = \vert G_3\vert = 2\vert S_1\vert = 2\vert S_2\vert$.

Proof

Let $\Gamma$ be a virtually free group of free rank $\mu (\Gamma )=2$, let $(\Gamma (-), X)$ be a Stallings decomposition of $\Gamma$, 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 Eq. (2.8), we have $\chi (\Gamma ) = - \frac{1}{m_\Gamma }$. There are five possibilities for the isomorphism type of the graph X underlying the decomposition of $\Gamma$, 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:= \Gamma (v)$ and $S:= \Gamma (e)$, we have $m_\Gamma = \vert G\vert$ and

  $$\begin{aligned} \chi (\Gamma ) = \frac{1}{\vert G\vert } - \frac{1}{\vert S\vert } = \frac{1 - (G:S^e)}{m_\Gamma } = -\frac{1}{m_\Gamma }, \end{aligned}$$

  implying $(G:S^e)=2$. Thus, setting $A:=S^e$, $B:=S^{\bar{e}}$, and with the isomorphism $\phi : A \rightarrow B$ given by $x^e \mapsto x^{\bar{e}}$ (in keeping with the notation of [11, Chap. IV.2]), the definition of $\pi _1(\Gamma (-), X)$ yields that

  $$\begin{aligned} \Gamma \cong \big \langle G, t\,\big \vert \,tat^{-1} = \phi (a),\, a\in A\big \rangle , \end{aligned}$$

  whence the result in that case.

• (ii) X consists of a single vertex v,  supporting two loops $e_i$, $i=1,2$. Set $G:= \Gamma (v)$ and $S_i:= \Gamma (e_i)$. Then $m_\Gamma = \vert G\vert$, and

  $$\begin{aligned} \chi (\Gamma ) = \frac{1}{\vert G\vert } - \frac{1}{\vert S_1\vert } - \frac{1}{\vert S_2\vert } = \frac{1 - (G:S_1^{e_1}) - (G:S_2^{e_2})}{m_\Gamma } = -\frac{1}{m_\Gamma }, \end{aligned}$$

  implying

  $$\begin{aligned} (G: S_1^{e_1}) = 1 = (G: S_2^{e_2}). \end{aligned}$$

  Hence, the maps $e_i: S_i \rightarrow G$ are isomorphisms, and we obtain the presentation

  $$\begin{aligned} \Gamma \cong \big \langle G, s_1, s_2\,\big \vert \,s_1 a_1^{e_1} s_1^{-1} = a_1^{\bar{e}_1}\, (a_1\in S_1),\, s_2 a_2^{e_2} s_2^{-1} = a_2^{\bar{e}_2}\, (a_2\in S_2)\big \rangle . \end{aligned}$$

  It follows that the finite group G is normal in $\Gamma$ 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:= \Gamma (v_i), \,i=1,2,$ and $S:= \Gamma (e)$. Then $\Gamma = G_1 \underset{S}{*} G_2$, with the canonical embeddings given by $\bar{e}: S\rightarrow G_1$ and $e: S\rightarrow G_2$. Moreover, let $a_1:= (G_1:S^{\bar{e}})$ and $a_2:= (G_2:S^e)$. By symmetry, we may suppose that $a_1\le a_2$, we have $a_1\ge 2$ by our assumption that $(\Gamma (-), X, T)$ is normalised, and the requirement that $\mu (\Gamma )=2$ boils down to the (equivalent) equation

  $$\begin{aligned} a_1a_2 - a_1 - a_2 = \gcd (a_1, a_2). \end{aligned}$$

  (7.1)

  Since $\gcd (a_1, a_2) \le a_1$, Eq. (7.1) implies that

  $$\begin{aligned} a_1 \le a_2 \le \frac{2a_1}{a_1-1}, \end{aligned}$$

  (7.2)

  which in turn leads to $a_1^2\le 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\le a_2\le 4$, while, for $a_1=3$, we get $a_2=3$. Thus, the only possibilities are

  $$\begin{aligned} (a_1, a_2) = (2,2),\, (2,3),\, (2,4),\, (3,3), \end{aligned}$$

  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:= \Gamma (v_i)$, and let $S_i:= \Gamma (e_i)$. Then $\Gamma = G_1 \underset{S_1}{*} \Gamma _2$, where $\Gamma _2$ is the fundamental group of the loop $e_2$ with bounding vertex $v_2$, and the canonical embeddings are given by the maps $\bar{e}_1: S_1\rightarrow G_1$ and $\tilde{e}_1: S_1\overset{e_1}{\rightarrow } G_2\rightarrow \Gamma _2$. Let $a_1:= (G_1:S_1^{\bar{e}_1})$, $a_2:= (G_2:S_1^{e_1})$, and $a_2':= (G_2:S_2^{e_2})$. Then

  $$\begin{aligned} m_\Gamma = {\text {lcm}}\!\big (\vert G_1\vert , \vert G_2\vert \big ) = \vert S_1\vert \cdot {\text {lcm}}(a_1, a_2) = \vert S_2\vert \cdot {\text {lcm}}(a_1, a_2) a_2'/a_2, \end{aligned}$$

  and the condition that $\mu (\Gamma )=2$ translates into the equation

  $$\begin{aligned} a_1a_2 + a_1a_2' - a_1 - a_2 = \gcd (a_1, a_2). \end{aligned}$$

  (7.3)

  Moreover, we have $a_1, a_2\ge 2$ by our assumption that $(\Gamma (-), X, T)$ is normalised, where T is the unique spanning tree of X. Suppose first that $a_1 \le a_2$. Then (7.3) gives

  $$\begin{aligned} 2 \le a_1 \,\le \, a_2 \le \frac{(2-a_2')a_1}{a_1-1} \,\le \,\frac{a_1}{a_1-1}\, \le \, 2. \end{aligned}$$

  This forces $a_1=a_2=2$, and from (7.3) we deduce that $a_2'=1$. Now suppose that $a_1\ge a_2$. Then (7.3) yields

  $$\begin{aligned} 2 \le a_2 \,\le \, a_1 \,\le \, \frac{2a_2}{a_2 + a_2'-1} \, \le \, 2, \end{aligned}$$

  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:=\Gamma (v_i)$, and let $S_j:=\Gamma (e_j)$ for $j=1,2$. Then $\Gamma = \big (G_1 \underset{S_1}{*} G_2\big ) \underset{S_2}{*} G_3$. Since $\mu (\Gamma )=2$, we have

  $$\begin{aligned} \frac{m_\Gamma }{\vert S_1\vert }\, + \,\frac{m_\Gamma }{\vert S_2\vert }\, -\, \frac{m_\Gamma }{\vert G_1\vert }\, - \,\frac{m_\Gamma }{\vert G_2\vert }\, -\, \frac{m_\Gamma }{\vert G_3\vert } = 1. \end{aligned}$$

  (7.4)

  As $(\Gamma (-), X, T)$ is normalised, we have

  $$\begin{aligned} \frac{m_\Gamma }{\vert G_1\vert } \,\le \, \frac{m_\Gamma }{2\vert S_1\vert } \, \text{ and } \, \frac{m_\Gamma }{\vert G_2\vert }\, \le \, \frac{m_\Gamma }{2\vert S_2\vert }, \end{aligned}$$

  so that (7.4) gives

  $$\begin{aligned} \frac{m_\Gamma }{2\vert S_1\vert } \,+\,\frac{m_\Gamma }{2\vert S_2\vert } - \frac{m_\Gamma }{\vert G_3\vert }\, \le \,1. \end{aligned}$$

  Again by normalisation,

  $$\begin{aligned} \frac{m_\Gamma }{\vert G_3\vert } \,\le \, \frac{m_\Gamma }{2\vert S_2\vert }, \end{aligned}$$

  thus

  $$\begin{aligned} 1\,\le \,\max \left\{ \frac{\vert G_1\vert }{2\vert S_1\vert },\, \frac{\vert G_2\vert }{2\vert S_1\vert }\right\} \,\le \, \frac{m_\Gamma }{2\vert S_1\vert } \,\le \, 1, \end{aligned}$$

  implying

  $$\begin{aligned} m_\Gamma = \vert G_1\vert = \vert G_2\vert = 2\vert S_1\vert . \end{aligned}$$

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

  $$\begin{aligned} m_\Gamma \left( \frac{1}{\vert S_2\vert } \,-\,\frac{1}{\vert G_3\vert }\right) = 1, \end{aligned}$$

  implying first $m_\Gamma = 2 \vert S_2\vert$ by normalisation, and then $\vert G_3\vert = m_\Gamma$. $\square$

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_\lambda (\Gamma )$. The result is as follows:

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

  $$\begin{aligned} f_{\lambda +1}(\Gamma ) = \frac{2\lambda +3}{2} m_\Gamma f_\lambda (\Gamma ) \,+\,\sum _{\mu =1}^{\lambda -1} f_\mu (\Gamma ) f_{\lambda -\mu }(\Gamma ),\quad \lambda \ge 1. \end{aligned}$$

  (7.5)

• (b) In Case (ii),

  $$\begin{aligned} f_{\lambda +1}(\Gamma ) = (\lambda +2) m_\Gamma f_\lambda (\Gamma )\,+\,\sum _{\mu =1}^{\lambda -1} f_\mu (\Gamma ) f_{\lambda -\mu }(\Gamma ),\quad \lambda \ge 1. \end{aligned}$$

  (7.6)

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

  $$\begin{aligned} f_{\lambda +1}(\Gamma ) = (\lambda +1) m_\Gamma f_\lambda (\Gamma )\,+\,\sum _{\mu =1}^{\lambda -1} f_\mu (\Gamma ) f_{\lambda -\mu }(\Gamma ),\quad \lambda \ge 1, \end{aligned}$$

  (7.7)

with corresponding initial conditions

• (a) $f_1(\Gamma ) = m_\Gamma ^2/2$,

• (b) $f_1(\Gamma ) = m_\Gamma ^2$,

• (c) $f_1(\Gamma ) = {\left\{ \begin{array}{ll} (m_\Gamma -\vert S\vert )\vert S\vert ,&{} \text{ Case } \text{(iii) },\\ (m_\Gamma /2)^2,&{} \text{ Case } \text{(v). } \end{array}\right. }$

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

Corollary 9

For a virtually free group $\Gamma$ with $\mu (\Gamma )=2$ and $\Gamma \not \cong C_2*C_2*C_2,$ we have

$$\begin{aligned} f_{\lambda +1}(\Gamma ) - f_\lambda (\Gamma )\,\ge \, m_\Gamma (\lambda + 1)! \end{aligned}$$

(7.8)

for all $\lambda \ge 1$. For $\Gamma \cong C_2*C_2*C_2,$ the estimate (7.8) holds for all $\lambda \ge 2$.

Proof

This follows from the above recurrence relations plus initial conditions by an immediate induction on $\lambda$. $\square$

Corollary 10

Let $\Gamma$ be virtually free of rank $\mu (\Gamma )=2$. In the cases (iii) $_1,$ (iii) $_3,$ and (v), we have, with $\vert S\vert \equiv 1\ (\text {mod }2)$ respectively $\vert S_1\vert \equiv 1\ (\text {mod }2),$

$$\begin{aligned} f_\lambda (\Gamma ) \equiv 1\ (\text {mod }2)\quad \text{ if, } \text{ and } \text{ only } \text{ if, } \quad \lambda =2^m-1 \text{ for } \text{ some } \text{ integer } m\ge 1. \end{aligned}$$

In all other cases, the function $f_\lambda (\Gamma )$ is constant modulo 2.

Proof

We focus on Case (iii)$_1$ with $\vert S\vert \equiv 1\ (\text {mod }2)$; the proof in Cases (iii)$_3$ and (v) is completely analogous, while the fact that $f_\lambda (\Gamma )$ is constant modulo 2 in all other cases is immediate.

We denote by $\Lambda$ the set of integers of the form $\lambda = 2^m-1,$ $m=1, 2, \ldots$, and prove the equivalence

$$\begin{aligned} f_\lambda (\Gamma ) \equiv 1\ (\text {mod }2) \quad \text {if, and only if,}\quad \lambda \in \Lambda , \end{aligned}$$

(7.9)

for $\lambda \ge 1$ by induction on $\lambda$. The assumption that $\vert S\vert \equiv 1\ (\text {mod }2)$ implies that

$$\begin{aligned} f_1(\Gamma ) = 5\vert S\vert ^2 \equiv 1\ (\text {mod }2), \end{aligned}$$

so that (7.9) is true for $\lambda =1$. Suppose that (7.9) is true for all $\lambda \le L$ with some $L\ge 1$, and consider $\lambda =L+1$. From (7.7) and the fact that $m_\Gamma =6\vert S\vert \equiv 0\ (\text {mod }2)$, we infer that, for $\lambda \ge 1$,

$$\begin{aligned} f_{\lambda +1}(\Gamma ) \equiv \left. {\left\{ \begin{array}{ll} f_{\lambda /2}(\Gamma )\ (\text {mod }2),&{} 2\mid \lambda ,\\ 0\ (\text {mod }2),&{} 2\not \mid \lambda .\end{array}\right. }\right. \end{aligned}$$

If $L+1\in \Lambda$, i.e., $L+1 = 2^m-1$ for some $m\ge 2$, then $L=2(2^{m-1}-1)\equiv 0\ (\text {mod }2)$ and $L/2\in \Lambda$, thus $f_{L+1}(\Gamma ) \equiv 1\ (\text {mod }2)$ by the induction hypothesis. Suppose, on the other hand, that $L+1\not \in \Lambda$. If $L\equiv 1\ \text {mod }2)$, then $f_{L+1}(\Gamma ) \equiv 0\ \text {mod }2)$. Thus we are left with the case where $L+1\not \in \Lambda$ and $L\equiv 0\ \text {mod }2)$. But then $L/2\not \in \Lambda$, and the induction hypothesis gives

$$\begin{aligned} f_{L+1}(\Gamma ) \equiv f_{L/2}(\Gamma ) \equiv 0\ (\text {mod }2), \end{aligned}$$

completing the proof. $\square$

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

• (1) In Case (i) of Proposition 7, we have $2\mid m_\Gamma$ and

  $$\begin{aligned} \mu _2(\Gamma ) = {\left\{ \begin{array}{ll} 1,&{}\vert A\vert \equiv 1\ (\text {mod }2),\\ 2,&{} \vert A\vert \equiv 0\ (\text {mod }2).\end{array}\right. } \end{aligned}$$

  In particular, we obtain that $\mu _2(\Gamma )>0$, so Case (III)$_2$ of [8, Theorem 1] applies, asserting that $f_\lambda (\Gamma )$ is ultimately periodic modulo 2 in this case. Indeed, by Corollary 10, $f_\lambda (\Gamma )$ is constant modulo 2.

• (2) In Case (ii) of Proposition 7, we either have $2\not \mid m_\Gamma$, or $2\mid m_\Gamma$ and $\mu _2(\Gamma )=2>0$, so $f_\lambda (\Gamma )$ is ultimately periodic modulo 2 in this case according to Case (III)$_1$ respectively (III)$_2$ of [8, Theorem 1]. Indeed, $f_\lambda (\Gamma )$ is again constant modulo 2 by Corollary 10.

• (3) In Case (iii)$_1$ of Proposition 7, we have $2\mid m_\Gamma$ and

  $$\begin{aligned} \mu _2(\Gamma ) = {\left\{ \begin{array}{ll} 0,&{}\vert S\vert \equiv 1\ (\text {mod }2),\\ 2, &{} \vert S\vert \equiv 0\ (\text {mod }2),\end{array}\right. } \end{aligned}$$

  so $f_\lambda (\Gamma )$ is ultimately periodic modulo 2 according to [8, Theorem 1] if, and only if, $\vert S\vert \equiv 0\ (\text {mod }2)$, which coincides with the corresponding assertion of Corollary 10.

• (4) In Case (iii)$_2$ of Proposition 7, we either have $\vert S\vert \equiv 1\ (\text {mod }2)$, and so $2\not \mid m_\Gamma = 3\vert S\vert$, or $\vert S\vert \equiv 0\ (\text {mod }2)$, in which case $2\mid m_\Gamma$ and $\mu _2(\Gamma ) =2>0$. Hence, ultimate periodicity of the function $f_\lambda (\Gamma )$ modulo 2 follows again from Case (III)$_1$ respectively Case (III)$_2$ of [8, Theorem 1], while Corollary 10 asserts that $f_\lambda (\Gamma )$ is constant modulo 2 in that case.

• (5) In Case (iii)$_3$ of Proposition 7, we have $2\mid m_\Gamma = 4\vert S\vert$ and

  $$\begin{aligned} \mu _2(\Gamma ) = {\left\{ \begin{array}{ll} 0,&{} \vert S\vert \equiv 1\ (\text {mod }2),\\ 2,&{} \vert S\vert \equiv 0\ (\text {mod }2).\end{array}\right. } \end{aligned}$$

  Hence, according to [8, Theorem 1], the function $f_\lambda (\Gamma )$ is ultimately periodic modulo 2 if, and only if, $\vert S\vert \equiv 0\ (\text {mod }2)$, which is in accordance with the corresponding assertion of Corollary 10.

• (6) In Case (iv) of Proposition 7, we have $2\mid m_\Gamma = 2\vert S\vert$ and

  $$\begin{aligned} \mu _2(\Gamma ) = {\left\{ \begin{array}{ll} 1,&{} \vert S\vert \equiv 1\ (\text {mod }2),\\ 2, &{} \vert S\vert \equiv 0\ (\text {mod }2).\end{array}\right. } \end{aligned}$$

  In particular, we obtain that $\mu _2(\Gamma )>0$, so that ultimate periodicity of $f_\lambda (\Gamma )$ follows from Case (III)$_2$ of [8, Theorem 1], while Corollary 10 asserts that $f_\lambda (\Gamma )$ is constant modulo 2 in that case.

• (7) Finally, in Case (v) of Proposition 7, we have $2\mid m_\Gamma = 2\vert S_1\vert$ and

  $$\begin{aligned} \mu _2(\Gamma ) = {\left\{ \begin{array}{ll} 0, &{} \vert S_1\vert \equiv 1\ (\text {mod }2),\\ 2,&{} \vert S_1\vert \equiv 0\ (\text {mod }2).\end{array}\right. } \end{aligned}$$

Hence, according to [8, Theorem 1], the function $f_\lambda (\Gamma )$ is ultimately periodic modulo 2 if, and only if, $\vert S_1\vert \equiv 0\ (\text {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 $\Gamma$ which all say, in one way or another, that $\Gamma$ 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 Pride in [15], and further developed in [5], depends on a certain preorder $\preceq$ on the class of groups, defined in [5] as follows: let G and H be groups. Then we write $H\preceq 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\sim G$ if $H\preceq G$ and $G\preceq H$, and we denote by [G] the equivalence class of the group G under $\sim$. By abuse of notation, we also denote by $\preceq$ 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(\Gamma )$ of ends of a group $\Gamma$ is defined as

$$\begin{aligned} e(\Gamma ) = {\left\{ \begin{array}{ll} \dim H^0(\Gamma , \mathrm {Hom}_\mathbb {Z}(\mathbb {Z}\Gamma , \mathbb {Z}_2)/\mathbb {Z}_2\Gamma ),&{} \text{ if } \Gamma \text{ is } \text{ infinite, }\\ 0,&{} \text{ if } \Gamma \text{ is } \text{ finite. } \end{array}\right. } \end{aligned}$$

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 [20].

Proposition 11

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

• (i) $\chi (\Gamma ) < 0$.

• (ii) $\mu (\Gamma ) \ge 2$.

• (iii) $\Gamma$ has infinitely many ends.

• (iv) The function $f_\lambda (\Gamma )$ is strictly increasing.

• (v) $\Gamma \sim F_2$ in the sense of Pride’s preorder $\preceq$ on groups, where $F_2$ denotes the free group of rank 2.

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

• (vii) If X has only one vertex v,  then either X has more than one geometric edge, or $E(X) = \{e_1, \bar{e}_1\}$ and $(\Gamma (v): \Gamma (e_1)^{e_1}) \ge 2;$ if $\vert V(X)\vert \ge 2,$ then X is not a tree, or X is a tree with more than one geometric edge, or $E(X) = \{e_1, \bar{e}_1\}$ and $\chi (\Gamma _0)<0,$ where $\Gamma _0:= \Gamma _{o(e_1)} \underset{\Gamma (e_1)}{*} \Gamma _{t(e_1)}$.

Proof

• (i) $\Leftrightarrow$ (ii). This is immediate from Formula (2.8) plus the fact that $\mu (\Gamma )$ is integral.

• (ii) $\Leftrightarrow$ (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_\infty$.

• (ii) $\Leftrightarrow$ (iv). This follows from [13, Theorem 4] in conjunction with Corollary 6.

• (ii) $\Rightarrow$ (v). If $\mu (\Gamma )\ge 2$, then $\Gamma$ contains a free group F of rank at least 2, with $(\Gamma :F) = m_\Gamma <\infty$; in particular, $F_2 \preceq \Gamma$. Since $[F_2]$ is largest with respect to the preorder $\preceq$ among all equivalence classes of finitely generated groups, we also have $\Gamma \preceq F_2$, so $\Gamma \sim F_2$, as claimed.

• (v) $\Rightarrow$ (vi). Suppose that $\Gamma \sim F_2$. Then there exists a subgroup $\Delta \le \Gamma$ of index $(\Gamma :\Delta )=j<\infty$ and a surjective homomorphism $\varphi : \Delta \rightarrow F_2$. From this plus Newman’s asymptotic estimate [14, Theorem 2]

  $$\begin{aligned} s_n(F_r) \sim n (n!)^{r-1} \text{ as } n\rightarrow \infty ,\quad r\ge 2, \end{aligned}$$

  it follows that

  $$\begin{aligned} s_{jn}(\Gamma ) \ge s_n(\Delta ) \ge s_n(F_2) \ge c\cdot n\cdot n! \ge c\cdot n! \end{aligned}$$

  for $n\ge 1$ and some constant $c>0$, whence (vi).

• (vi) $\Rightarrow$ (ii). If $\mu (\Gamma )\le 1$, then either $\Gamma$ is finite, so $s_n(\Gamma )=0$ for sufficiently large n, or $\Gamma$ is virtually infinite-cyclic, implying

  $$\begin{aligned} s_n(\Gamma ) \le n^\alpha ,\quad n\ge 1, \end{aligned}$$

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

• (ii) $\Leftrightarrow$ (vii). This follows by splitting the Euler characteristic $\chi (\Gamma )$ as in the proof of Proposition 4, making use of Lemmas 1 and  2.$\square$