arXiv:1602.08723v1 [math.GR] 28 Feb 2016

FREE SUBGROUP NUMBERS MODULO PRIME POWERS: THE
NON-PERIODIC CASE
C. KRATTENTHALER† AND T. W. MÜLLER∗
Abstract. In [J. Algebra 452 (2016), 372–389], we characterise when the sequence
of free subgroup numbers of a finitely generated virtually free group Γ is ultimately
periodic modulo a given prime power. Here, we show that, in the remaining cases,
in which the sequence of free subgroup numbers is not ultimately periodic modulo a
given prime power, the number of free subgroups of index λ in Γ is — essentially —
congruent to a binomial coefficient times a rational function in λ modulo a power of a
prime that divides a certain invariant of the group Γ, respectively to a binomial sum
involving such numbers. These results, apart from their intrinsic interest, in particular
allow for a much more efficient computation of congruences for free subgroup numbers
in these cases compared to the direct recursive computation of these numbers implied
by the generating function results in [J. London Math. Soc. (2) 44 (1991), 75–94].

1. Introduction
For a finitely generated virtually free group Γ, denote by mΓ the least common
multiple of the orders of the finite subgroups in Γ. Moreover, for a positive integer
λ, let fλ (Γ) be the number of free subgroups of index λmΓ in Γ. In [6], a complete
characterisation is given of all pairs (Γ, pα ), where Γ is a finitely generated virtually free
group and pα is a proper prime power, for which the sequence (fλ (Γ))λ≥1 is ultimately
periodic modulo pα . As it turns out, somewhat surprisingly, this is always the case,
unless µp (Γ) = 0 and µ(Γ) ≥ 2,1 where µp (Γ) and µ(Γ) are certain invariants of Γ
defined in Section 2. See also [3], where more precise results are obtained for lifts of
the inhomogeneous modular group. Our present paper focuses on the latter case of
non-periodic behaviour. It is shown in [10] that, for µp (Γ) = 0 and µ(Γ) ≥ 2, the
function fλ (Γ) satisfies the congruence
 µ(Γ)λ 
(µ(Γ)−1)λ+1 1
p−1
p−1
fλ (Γ) ≡ (−1)
(mod p),
(1.1)
λ λ−1
p−1
where the binomial coefficient is defined to be zero whenever the lower argument is not
an integer; cf. [10, Eqn. (35)].
2010 Mathematics Subject Classification. Primary 05A15; Secondary 05E99 11A07 20E06 20E07
68W30.
Key words and phrases. virtually free groups, free subgroup numbers, congruences, Gosper–
Zeilberger algorithm.
†
Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S50N15, the latter 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.
1The condition µ(Γ) ≥ 2 is equivalent to the assertion that Γ contains a non-Abelian free subgroup.
1

2

C. KRATTENTHALER AND T. W. MÜLLER

The purpose of the present paper is to demonstrate that, under the same assumptions, the function fλ (Γ) satisfies a very similar congruence modulo an arbitrary p-power.
More precisely, if µ(Γ) ≡ 0, 1 (mod p), the function fλ (Γ), when reduced modulo any
fixed p-power, is congruent to a (quasi-)rational factor in λ times a binomial coefficient
(see Corollary 7 in Section 6), while in the remaining cases the right-hand side takes
the form of a sum of such expressions (see Corollary 11 in the same section). A remarkable consequence of these results is that, while it may be safely conjectured that the
generating function for the free subgroup numbers (which satisfies a highly non-linear
differential equation obtained from (2.8) via (2.6)) is not D-finite, implying that the
sequence of free subgroup numbers itself is not P-recursive,2 its reduction modulo any
fixed p-power is.
While the result obtained in Corollary 7 for arbitrary p-powers is ‘as good as’ the
mod p result (1.1), we show in Proposition 12 that the sum described in Corollary 11
satisfies an inhomogeneous linear recurrence of finite depth with constant coefficients
and leading coefficient 1 (which may be found automatically by means of the Gosper–
Zeilberger algorithm; cf. [11]). This leads again to an efficient computation of fλ (Γ)
modulo pα . All these results are presented in Section 6, and are illustrated there by
concrete examples.
The only known earlier results concerning congruences of free subgroup numbers
modulo prime powers in the non-periodic case covered the following scenarios: (i) lifts
of Hecke groups H(q) ∼
= C2 ∗ Cq with q a Fermat prime and p = 2, and (ii) lifts of
the classical modular group H(3) ∼
= PSL2 (Z) and p = 3; see Section 8, Corollary 34
and Theorem 35 in [2], and [4, Sec. 16]. In particular, the behaviour of fλ (Γ) modulo
p-powers in these known cases fits into the framework of the semi-automatic method
for obtaining congruences developed in [2, 4, 5], and further (unpublished) work. As
we show in this paper, for finitely generated virtually free groups Γ and primes p with
µp (Γ) = 0 and µ(Γ) ≥ 2, this is always the case.
This semi-automatic method is based on a generating function approach, featuring
a basic series — to be adapted for each class of applications — which is then used to
express the generating function for the sequence of numbers we have in mind, reduced
modulo a given p-power, as a polynomial in this basic series. We show in Theorem 6
in Section 5 that, if µp (Γ) = 0 and µ(Γ) ≥ 2, we may choose the series
 µ(Γ)n 
∞
X
(µ(Γ)−1)n+1 1
p−1
Φ(z) =
(−1) p−1
zn
(1.2)
n−1
n p−1
n=1
as basic series (i.e., the series formed out of the coefficients
on the right-hand side
P
f
(Γ)
z λ modulo p-powers
of (1.1)) in order to express the generating function ∞
λ=1 λ
as a polynomial in Φ(z). Corollaries 7 and 11 alluded to above are consequences of
Theorem 6. The proof of the theorem requires some auxiliary results which are presented
in Section 4. These include some interesting determinant evaluations, see Lemmas 4
and 5.
A remarkable feature of the present application of our semi-automatic generating
function method is that the P
degree of the polynomial in the basic series Φ(z) expressλ
α
ing the generating function ∞
λ=1 fλ (Γ) z modulo p does not increase with α. As a
2The

reader is referred to [13, Ch. 6] for information on D-finite series and P-recursive sequences.

FREE SUBGROUP NUMBERS MODULO PRIME POWERS

3

consequence, the complexity of the computation only mildly increases with α. This
is in sharp contrast to our previous applications of this method. The reason for the
above phenomenon lies in the fact that Φ(z) satisfies an exact functional equation over
the integers, namely (4.1), while in our previous applications the basic series satisfied
functional equations modulo pα of complexity increasing with α.
Our results concerning the function fλ (Γ) are complemented by Theorem 2 in Section 3, which precisely characterises those finitely generated virtually free groups Γ with
µ(Γ) ≥ 2 and µp (Γ) = 0 for a given prime number p.
2. Some preliminaries on finitely generated virtually free groups
Our notation and terminology concerning virtually free groups and their decomposition in terms of a graph of groups follows Serre’s book [12]; in particular, the category
of graphs used in the context of graphs of groups is described in [12, §2]. This category deviates slightly from the usual notions in graph theory. In order to distinguish
the objects of this category from graphs in the sense of graph theory, we call them
S-graphs. Specifically, an S-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(ē) = o(e). The reader should note that, according to the above definition,
S-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, 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) ∼
= Γ. Replacing the stabiliser groups of vertices and edges by their respective group orders and replacing each pair (e, ē) by one unoriented edge, we obtain
the corresponding order graph of Γ. Abstractly, an order graph is a finite connected
unoriented graph (in the sense of graph theory; multiple edges and loops are allowed)
whose vertices v and edges e carry positive integers, n(v), respectively n(e), as labels
such that n(e) | n(v) if v is incident to e. The labels of vertices and edges will frequently
be referred to as their respective order.
As in the introduction, denote by mΓ the least common multiple of the orders of the
finite subgroups in Γ, so that, in terms of the above Stallings decomposition of Γ,

mΓ = lcm |Γ(v)| : v ∈ V (X) .
(2.1)
(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)| κ .

(2.2)

4

C. KRATTENTHALER AND T. W. MÜLLER

(Here, O(X) is any orientation of the S-graph X.) 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. [9, 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. [8, Prop. 1] or [9, Lemma 2].
Inspection of (2.1) and (2.2) reveals that all ingredients of the type (that is, mΓ and
the ζκ ’s) depend only on the orders but not on the internal structure of the stabilisers of
vertices and edges of (Γ(−), X). Therefore it makes sense to attach the same invariants
to the order graph obtained from the graph of groups (Γ(−), X) in the way described
earlier, or, more generally, to an abstract order graph. Specifically, given an order
graph G, we define mG to be the least common multiple of the vertex orders n(v),
taken over all vertices of G, and, for a divisor κ of mG , we let


ζκ (G) = e ∈ E(G) : n(e) | κ − v ∈ V (G) : n(v) | κ ,
(2.3)
where V (G) denotes the set of vertices of G and E(G) the set of edges.

Define a torsion-free Γ-action on a set Ω to be a Γ-action on Ω which is free when
restricted to finite subgroups, and let
number of torsion-free Γ-actions on a set with λmΓ elements
, λ ≥ 0;
(λmΓ )!
(2.4)


in particular, g0 (Γ) = 1. The sequences fλ (Γ) λ≥1 and gλ (Γ) λ≥0 are related via the
Hall-type transformation formula3
gλ (Γ) :=

λ−1
X

gµ (Γ)fλ−µ (Γ) = mΓ λgλ (Γ),

λ ≥ 1.

(2.5)

µ=0

Introducing the generating functions
FΓ (z) :=

∞
X

λ

fλ (Γ)z and GΓ (z) :=

∞
X

gλ (Γ)z λ ,

λ=0

λ=1

Equation (2.5) is seen to be equivalent to the relation
FΓ (z) = mΓ z


d
log GΓ (z) .
dz

(2.6)

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 [12]; it need not be unique, though). It can be shown that
the free rank µ(Γ) may be expressed in terms of the type of Γ via
X
µ(Γ) = 1 +
ϕ(mΓ /κ)ζκ (Γ),
(2.7)
κ|mΓ

3See

[9, Cor. 1], or [1, Prop. 1] for a more general result.

FREE SUBGROUP NUMBERS MODULO PRIME POWERS

5

which shows in particular that µ(Γ) is well-defined. It is known 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)

+

µ(Γ)
X

(µ)

θµ (Γ)z µ GΓ (z) = 0

(2.8)

µ=2

of order µ(Γ) with integral coefficients θµ (Γ) given by
 
µ
Y Y
1 X
µ−j µ
(jmΓ +k)ζκ (Γ) ,
mΓ (j+1)
θµ (Γ) =
(−1)
µ! j=0
j
1≤k≤m
κ|mΓ

0 ≤ µ ≤ µ(Γ); (2.9)

Γ

(mΓ ,k)=κ

cf. [9, Prop. 5].
For a finitely generated virtually free group Γ and a prime number p, we introduce,
in formal analogy with formula (2.7), the p-rank µp (Γ) of Γ via the equation
X
µp (Γ) = 1 +
ϕ(mΓ /κ)ζκ (Γ).
(2.10)
p|κ|mΓ

Clearly, µp (Γ) ≥ 0, with equality occurring if, and only if, Γ is the fundamental group
of a tree of groups, p | mΓ , and ζκ (Γ) = 0 for p | κ | mΓ and κ < mΓ . Since the free
rank µ(Γ) and the p-rank µp (Γ) only depend on the type invariants mΓ and the ζκ ’s, in
view of our earlier discussion they may also be defined for abstract order graphs and,
in particular, for an order graph G of a finitely generated virtually free group Γ. Doing
so, one has µ(Γ) = µ(G) and µp (Γ) = µp (G). These conventions will be used in the
proof of Theorem 2.
In what follows, 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 auxiliary result.
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 that4
∆(e)e 6= ∆(t(e)) and ∆(e)ē 6= ∆(o(e)),

for e ∈ E(T ).

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

X is a finite S-graph,

(F2 )

Γ(v) is finite for every vertex v ∈ V (X),

or

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

notation used in Equation (2.11) follows Serre; see Déf. 8 in [12, Sec. 4.4].

(2.11)

6

C. KRATTENTHALER AND T. W. MÜLLER

6✉

42✉

❅
❅
❅ 504
❅

2 ✉

✉2

12
✉
❅
❅
❅
❅✉3

Figure 1. A divisor tree for p = 5
See [7, Sec. 3] for a proof of this useful result. Subsequently, we shall call a graph
of groups (∆(−), Y ) normalised, if it satisfies the conditions of the lemma for some
spanning tree T of Y . In our situation, normalised graphs of groups will always be
trees, so coincide with their respective spanning trees. We shall therefore suppress the
reference to the spanning trees from now on.
3. Characterisation of finitely generated virtually free groups Γ
with µp (Γ) = 0
Recall (see paragraph below (2.10)) that, if a finitely generated virtually free group
satisfies µp (Γ) = 0 for a given prime p, then, in particular, Γ is the fundamental group of
a tree of groups. Theorem 2 below tells us how a normalised (in the sense of Lemma 1)
order tree5 X underlying the Stallings decomposition (Γ(−), X) of a finitely generated
virtually free group Γ must be constructed so as to satisfy µp (Γ) = 0.
Given a fixed prime number p, the starting point of our construction are certain finite
rooted vertex-labelled trees which we call divisor trees. By definition, vertices of divisor
trees are labelled by positive integers coprime to p. Moreover, any two adjacent vertices,
say v1 and v2 , with v1 closer to the root than v2 , satisfy ℓ(v2 ) | ℓ(v1 ) and ℓ(v2 ) < ℓ(v1 ),
where ℓ(v1 ) and ℓ(v2 ) denote the labels of v1 and v2 . See Figure 6 for an example of
such a divisor tree. There, the prime number to be fixed from the very beginning is
p = 5. In the figure, the root is indicated by a square.
Given a divisor tree D, we fix a map f from the set of vertices of D into the set of
(ordinary, unlabelled) finite rooted trees with the property that non-root vertices are
mapped to non-trivial6 trees rooted at a leaf and, in case D consists of just the root,
this root must be mapped to a non-trivial tree (with no restriction on the location of
the root). Figure 2 shows an example of such a map f defined on the vertices of the
order tree in Figure 1. There, the roots of the image trees are indicated by little circles.
From D and f , we construct a certain class of order graphs. The reader is advised
to consult Figure 3 while reading the description of this construction in the following
paragraph. We remind the reader that, in that example, the fixed prime number is
p = 5.
If v1 and v2 are adjacent in D, where v1 is closer to the root than v2 , then we glue the
root of f (v2 ) to one of the leaves of f (v1 ). If this is done for all edges of D, we obtain
a rooted tree, U say, where the root of U is by definition the root of f (r), with r being
5Here,
6Here,

order tree means an order graph which has the form of a tree.
‘non-trivial’ means ‘at least two vertices’.

FREE SUBGROUP NUMBERS MODULO PRIME POWERS

−→

❡

6 ✉

−→

✉

✉

42 ✉

−→

✉

❡

−→
2
(left-bottom)

✉

504

✉

12 ✉

−→

❡

✉

−→

❡

✉

3 ✉

❡

✉
❍
❍
❍✉
✟
✟
✟
✉
✉
✟
✟
❡✟
❍❍
❍✉

2 ✉ −→
(right-top)

7

❡

✉

Figure 2. A function f on the vertices of the divisor tree of Figure 1
30✉

6

30✉

10 ✉

60
✉

❅
❅
42❅ 5040 60 12
❅
✉
12 ❅
❅
12
10✉ 2
❅
❅✉
✂❍❍
60
2❍❍❍✉
✂
2✂
10
✂
✂✉

6

2

210
✉

2

3

10
✉

2

10
✉

✉

15

10
Figure 3. An order tree resulting from the divisor tree of Figure 1 and
the function f from Figure 2
the root of D. In Figure 3, the root is again indicated by a square. Given some vertex
v in D, we label the edges in f (v) by ℓ(v) and the non-root vertices in f (v) by p · ℓ(v).
The root of U (that is, the root of f (r)) is assigned a number which is a multiple of
p · lcm{ℓ(v) : v ∈ D}.
Abusing notation, we write f (D) for the set of order graphs resulting from this construction. All of them are trees. We shall occasionally use the term order tree for these
order graphs.
Theorem 2. Let Γ ∼
= π1 (Γ(−), X) be a finitely generated virtually free group with
µ(Γ) ≥ 2, where X is an S-graph which is assumed to be normalised in the sense of
Lemma 1. Then µp (Γ) = 0 if, and only if, there exist a divisor tree D and a map f as

8

C. KRATTENTHALER AND T. W. MÜLLER

above from the set of vertices of D into the set of finite rooted trees such that the order
tree corresponding to (Γ(−), X) is in f (D).
Proof. We start with the proof of the forward implication. We consider the order
graph of (Γ(−), X), which we denote by G. By the characterisation of groups Γ with
µp (Γ) = 0 given in the paragraph after (2.10), we know that G is a tree, that, using
the identification of invariants of Γ and G discussed in Section 2, p | mG , and that
ζκ (G) = 0 for p | κ | mG and κ < mG . Also, since (Γ(−), X) is normalised, we have
n(e) < n(v) if v ∈ V (G) is incident with e ∈ E(G).
Let m be the minimal order of vertices and edges in G. Since (Γ(−), X) is assumed
to be normalised and µ(Γ) ≥ 2, this order must be the order of an edge. Furthermore,
m cannot be divisible by p since otherwise we would have

0 = ζm (G) = e ∈ E(G) : n(e) = m > 0,

a contradiction.
In order to proceed, we need to introduce an auxiliary object. Let ℓ be a positive
integer. We let Sℓ (G) be the collection of subtrees of G consisting of those vertices
and edges with orders dividing ℓ. It should be noted that the connected components of
Sℓ (G) need not be trees in the classical sense since they may contain edges with one or
both of their vertices removed.
Next we consider Spm (G). We claim that Spm (G) consists of all vertices and edges
with orders m or pm, but no other vertices or edges. Let us assume for a contradiction
that there is a vertex v ∗ with n(v ∗ ) = pm′ or an edge e∗ with n(e∗ ) = pm′ , m′ | m and
m′ < m, where m′ is minimal with this property. If there should be such a vertex v ∗ ,
then it is incident with an edge ẽ with n(ẽ) properly dividing n(v ∗ ) = pm′ . The order
n(ẽ) cannot be m′ since this would contradict minimality of m. Thus, n(ẽ) = pm′′ with
m′′ | m′ and m′′ < m′ , contradicting the minimality of m′ . On the other hand, if there
is an edge e∗ as above, then we have


0 = ζpm′ (G) = e ∈ E(G) : n(e) | pm′ − v ∈ V (G) : n(v) | pm′ .

Thus, there must be at least one vertex v with n(v) | pm′ . If n(v) < pm′ , then we have
again a contradiction to the minimality of m′ . If n(v) = pm′ , then the above argument
for v ∗ also produces a contradiction to the minimality of m′ .
If pm = mG , then Spm (G) = G and indeed µp (Γ) = µp (G) = 0.
If pm < mG , then the connected components of Spm (G) might be of two kinds:
either an edge with order pm without vertices, or a subtree of G consisting of edges
with order m and of some vertices of these edges, which have order pm. If all vertices of
the edges would be part of the component, then this would already be the complete tree
G, which is impossible by our assumption that pm < mG . We may therefore assume
that in each component there is at least one vertex of some edge missing. This vertex
must be a leaf of the tree structure. (If not, the subtree would actually decompose into
smaller trees.) In that case, each component contributes a non-negative number to


ζpm (G) = e ∈ E(G) : n(e) | pm − v ∈ V (G) : n(v) | pm .

Since ζpm (G) = 0, all components must actually contribute zero. This implies that
components of the first kind cannot exist, and all components consist of edges of order m
and an equal number of vertices with order pm, that is, exactly one of the vertices is
missing from the tree component.

FREE SUBGROUP NUMBERS MODULO PRIME POWERS

9

We now remove Spm (G) from G. What remains is another order tree, say G′ . It is
easy to see that our construction guarantees that ζκ (G′ ) = ζκ (G) for all κ.
We repeat the above construction for G′ , with a new minimal order m′ > m. This
process is continued until nothing remains from the original order tree G.
We now form a divisor tree out of the pieces of this construction. Each connected
component of Spm (G), of Spm′ (G′ ), . . . is interpreted as a vertex labelled by m, by
m′ , . . . , respectively, and two vertices, v1 and v2 say, are connected by an edge if the
(incomplete) tree, C(v2 ) say, corresponding to v2 was attached to the (incomplete) tree,
C(v1 ) say, corresponding to v1 in the original order tree G. The label of v2 divides the
one of v1 since the order of the leaf of C(v1 ) on which C(v2 ) was attached must be a
multiple of the order of the edges of C(v2 ).
Finally, to see the reverse implication, one has to convince oneself that the divisor
tree construction of the theorem always yields order trees G with µp (G) = 0, and that
we have µp (Γ) = 0 for any group Γ of the theorem with order graph equal to G, which
is not difficult.

4. auxiliary results
The purpose of this section is to provide the means for the proof of Theorem 6 in the
next section. Lemma 3 below demonstrates that the derivatives of our basic series Φ(z)
in (1.2) can be expressed as a polynomial in Φ(z) with rational coefficients, which is one
of the fundamental facts needed in the proof of Theorem 6. The proof of the lemma is
based on the evaluation of the determinant of a block matrix given in Lemma 4, which
itself uses another determinant evaluation, provided in Lemma 5. The determinant
evaluation of Lemma 4 also plays a crucial role in the proof of Theorem 6.
Let p be a given prime number. In all of this section, we write N for µ(Γ)/(p − 1).
Using this notation, the series Φ(z) in (1.2) becomes


∞
X
Nn
1
N n− n−1
p−1
Φ(z) =
(−1)
zn .
n−1
n
p−1
n=1

A straightforward application of the Lagrange inversion formula (cf. [13, Theorem 5.4.2])
shows that Φ(z) is the unique formal power series solution of the equation
N
Φ(z) − z Φp−1 (z) − 1 = 0.
(4.1)
Lemma 3. We have
Φ′ (z) =

(−1)(p−1)N

Pol(z, Φ(z))
(p−1)N
(p−1)N −1 ,
(p − 1)N
z p−1 + (p − 1)N − 1

(4.2)

where Pol(z, t) is a polynomial in z and t over the integers.

Proof. Differentiating both sides of (4.1), we obtain
N
N −1
Φ′ (z) − Φp−1 (z) − 1 − zN(p − 1)Φ′ (z)Φp−2 (z) Φp−1 (z) − 1
= 0.
Hence,

Φ′ (z) =

(Φp−1 (z) − 1)

N

1 − zN(p − 1)Φp−2 (z) (Φp−1 (z) − 1)N −1

.

(4.3)

10

C. KRATTENTHALER AND T. W. MÜLLER

We must now express the reciprocal of the denominator as a polynomial in Φ(z). In
order to do this, we make the Ansatz
(p−1)N −1

N −1  X
p−2
p−1
1 − zN(p − 1)Φ (z) Φ (z) − 1
bi (z)Φi (z) = 1,

(4.4)

i=0

with at this point undetermined coefficients bi (z), where the sum represents the reciprocal of the denominator in (4.3). We multiply both sides of the last equation by
(Φp−1 (z) − 1). Then, using (4.1), we obtain
(p−1)N −1



p−1

1 − N(p − 1) Φ

(z) − 1

X



bi (z)Φi (z) = Φp−1 (z) − 1,

(4.5)

i=0

We expand the product on the left-hand side and use (4.1) again to reduce Φ(p−1)N (z)
to a linear combination of lower powers of Φ(z). This leads to
(p−1)N −p

1 − N(p − 1)



+ 1 − N(p − 1)

X

bi (z)Φi+p−1 (z)

i=0

p−2

X



−1

i+1

bi+(p−1)(N −1) (z) z Φ

i=0

(z) −

N
−1 
X
k=0



N
N −k i+(p−1)k
(−1)
Φ
(z)
k

(p−1)N −1

−

X

bi (z)Φi (z) = Φp−1 (z) − 1,

i=0

Comparison of powers of Φ(z) then yields a system of equations of the form
M · b = c,

(4.6)

where b = (bi (z))0≤i≤(p−1)N −1 is the column vector of unknowns, c = (ci )0≤i≤(p−1)N −1
with c0 = −1, cp−1 = 1, and ci = 0 otherwise, and M is the (p − 1)N × (p − 1)N matrix
given by

Mi,j


−1





X
= Xz −1



(−1)N −k−1




N
k



X

if
if
if
if

0 ≤ i = j ≤ (p − 1)N − p,
p − 1 ≤ i = j + p − 1 ≤ (p − 1)N − 1,
1 ≤ i = j − (p − 1)(N − 1) + 1 ≤ p − 1,
0 ≤ i − (p − 1)k = j − (p − 1)(N − 1) ≤ p − 2,
for some k with 0 ≤ k ≤ N − 1,

X being short for 1 − (p − 1)N. The structure of the matrix M becomes clearer if we
reorder the rows and columns of the matrix simultaneously so that first come the rows
and columns indexed by i and j which are ≡ 0 (mod p − 1), respectively, then those
which are ≡ 1 (mod p − 1), . . . , and finally those which are ≡ p − 2 (mod p − 1). The

FREE SUBGROUP NUMBERS MODULO PRIME POWERS

11

result is the matrix
A 0
B A

0 B
.
 ..

0 ...
0 ...


where the block A is the N × N matrix

−1 0
0
 X −1 0

 0 X −1

A =  ..
..
 .
.

 0 ... 0
0 ...


0 ... 0 C
0 ... 0 0

A ... 0 0
,
.. 
.. ..
.
.
.

0 B A 0
0
0 B A
given by

...
...
...
..
.
X
0

B is the N × N matrix given by

0 ...
0 . . .
B=
 ...
0 ...


and C is the N × N matrix given by

0
0

0
C=
.
 ..
0

(4.7)


(−1)N −1 X 
(−1)N −2 X N1 

(−1)N −3 X N2 

,
..
.  

−1
−X NN−2 

X
X NN−1 − 1
0
0
0

(4.8)


0 Xz −1
0
0 
,
..
.. 
.
. 
0
0


... 0
0
. . . 0 Xz −1 

... 0
0 .
.. 
..
. 
.
... 0
0

The determinant of M (that is, of the matrix in (4.7)) is computed in Lemma 4. It is
obviously non-zero, therefore the system of linear equations satisfied by the coefficients
bi (z), i = 0, 1, . . . , N − 1, has a unique solution. In the end, we obtain (4.2).

Lemma 4. The determinant of the matrix in (4.7) equals
(−1)(p−1)N (p − 1)N

(p−1)N

+ (p − 1)N − 1

(p−1)N −1

z −p+1 .

Proof. We write the last column of (4.7) as the sum c1 + c2 , where c1 is the column with
Xz −1 as index-1 entry (the reader should remember that our indexing starts with 0)
and 0’s otherwise, and c2 is the “rest,” that is, the index i entry equals


N
N −(i−(p−2)N )−1)
X − δi,(p−1)N −1
(−1)
i − (p − 2)N

12

C. KRATTENTHALER AND T. W. MÜLLER

for i = (p − 2)N, (p − 2)N + 1, . . . , (p − 1)N − 1 and 0’s otherwise. Then, by linearity
in the last column, the determinant det M equals the sum of


A 0
0 ... 0 0
B A 0 . . . 0 0 


0 B A . . . 0 0

,
(4.9)
det  ..
.. 
.. ..
.
.
.

.
0 . . . 0 B A 0
0 ...

0

0

B A

and the determinant of a second matrix, which arises from (4.7) by replacing the last
column by c1 . Since the matrix in (4.9) is a lower triangular block matrix, its determinant equals
(det A)p−1 .
(4.10)
We are going to evaluate the determinant of A in Lemma 5.
In order to evaluate the determinant of the second matrix, we expand it along the
last column. This leads to the expression

 ′
A 0
0 ... 0 0
B A 0 . . . 0 0 


 0 B A ... 0 0 
(p−1)N
−1

,
(4.11)
(−1)
Xz det  ..
.. 
.. ..
.
.
.
. 


 0 ... 0 B A 0 
0

...

0

0

B A′′

where A′ is the matrix which arises from A by deleting its row with index 1 (it should
be remembered again that our indexing of rows starts with the index 0), and A′′ is the
matrix which arises from A be deleting its last column. Inspection of the matrix in
(4.11) reveals that it is an upper (sic!) triangular matrix, hence its determinant equals
the product of its diagonal entries, so that (4.11) equals
p−2
(p−1)N −1 −p+1
(−1)(p−1)N Xz −1 Xz −1
(−1)X (p−1)(N −1)−1 = (p − 1)N − 1
z
. 

Lemma 5. With the matrix A given by (4.8), We have
N
det A = (−1)N (p − 1)N .

Proof. We replace the 0-th row of A by
N
−1
X

X −j · (row j).

j=0

This is an operation which does not change the determinant. For the entry in the 0-th
row and (N − 1)-st column of the new matrix, we obtain
 
 
N
N
−1
X
X
−N +1
−N +1
N −j
N −j N
−j
N −j−1 N
X −X
= −X
X
(−1)
X (−1)
j
j
j=0
j=0
N
(p − 1)N
−N +1
N
= −X
(1 − X) = −
. (4.12)
X N −1

FREE SUBGROUP NUMBERS MODULO PRIME POWERS

Thus, after the operation described above, the

0 0
0 ... 0
X −1 0 . . . 0

 0 X −1 . . . 0

 ..
.. ..
.
.
.

 0 . . . 0 X −1
0 ...
0 X

13

new matrix reads

Y

(−1)N −2 X N1 

(−1)N −3 X N2 

..
,
.  

−X NN−2 

X NN−1 − 1

where Y denotes the quantity in (4.12). The determinant of this matrix, and thus the
determinant of A, equals
N
(−1)N −1 X N −1 Y = (−1)N (p − 1)N ,

establishing the claim.



5. A generating function approach
Given a finitely generated virtually
free group Γ, in this section we write F (z) for the
P
f
(Γ)
z λ of the number fλ (Γ) of subgroups of index
generating function FΓ (z) = ∞
λ=1 λ
mΓ λ in Γ. The theorem below shows that, under the conditions of Theorem 2, the
series F (z), when coefficients are reduced modulo any given p-power, can be expressed
as a polynomial in Φ(z).
Theorem 6. Let p be a prime and α a positive integer. Furthermore, let Γ be a finitely
generated virtually free group with µp (Γ) = 0 and µ(Γ) ≥ 2. As before, let Φ(z) be the
series in (1.2). Then the generating function F (z) for the free subgroup numbers of Γ,
when reduced modulo pα , can be expressed as a polynomial in Φ(z) of degree at most
µ(Γ) − 1, with coefficients in Z[z, z −1 , Y −1 (z)], where
(
−1
z p−1 − µ(Γ)
+ 1 , if p ≥ 3 and µ(Γ) 6≡ 0, 1 (mod p),
p−1
Y (z) =
1,
otherwise.
Proof. It is known from [10, Prop. 2] that F (z) satisfies a differential equation of the
form
µ(Γ)/(p−1)

F (z) = z F p−1(z) − 1
+ pP z, F (z), F ′ (z), . . . , F (µ(Γ)−1) (z) ,
(5.1)
where P(z, t0 , t1 , . . . , tµ(Γ)−1 ) is a polynomial in z, t0 , t1 , . . . , tµ(Γ)−1 over the integers.
(To be precise, this is the result of a careful p-adic analysis of the differential equation
arising from a combination of (2.6) and (2.8).) It is our goal to express F (z) modulo pα
as a polynomial in Φ(z) with coefficients in Z[z, z −1 , Y −1 (z)]. Since Φ(z) satisfies the
functional
equation
(4.1)
with
N = µ(Γ)/(p − 1), we have
F (z) = Φ(z) modulo p.
Here, given integral power series (or Laurent series) f (z) and g(z), we write
f (z) = g(z) modulo pγ
to mean that the coefficients of z i in f (z) and g(z) agree modulo pγ for all i.

14

C. KRATTENTHALER AND T. W. MÜLLER

We now suppose that we have already found a polynomial
µ(Γ)−1

Fβ (z) =

X

ai,β (z)Φi (z),

i=0

with coefficients ai,β (z) in Z[z, z

−1

,Y

−1

(z)], so that

F (z) = Fβ (z) modulo pβ .

(5.2)

We then make the Ansatz
µ(Γ)−1

F (z) = Fβ+1 (z) = Fβ (z) + pβ

X

bi,β+1 (z)Φi (z)

modulo pβ+1 ,

(5.3)

i=0

for certain, at this point undetermined, rational functions bi,β+1 (z) over the integers.
We substitute this Ansatz in the differential equation (5.1) and reduce the result modulo pβ+1 , to obtain
µ(Γ)−1

Fβ (z) + p

β

X

bi,β+1 (z)Φi (z)

i=0



µ(Γ)/(p−1)

µ(Γ)−1

X

− z Fβp−1 (z) + (p − 1)Fβp−2(z)pβ

i=0

bi,β+1 (z)Φi (z) − 1



(µ(Γ)−1)
′
− pP z, Fβ+1 (z), Fβ+1
(z), . . . , Fβ+1
(z) = 0

modulo pβ+1 . (5.4)

By Lemma 3, we have

µ(Γ)−1
(j)
Fβ+1 (z)

=

(j)
Fβ (z)

+p

β

X

ci,β+1;j (z)Φi (z)

(5.5)

i=0

for all non-negative integers j and certain rational functions ci,β+1;j (z). It should be
noted that the denominators of these rational functions are powers of
(p−1)N p−1
(p−1)N −1
,
(5.6)
(−1)(p−1)N (p − 1)N
z
+ (p − 1)N − 1

where we wrote again N = µ(Γ)/(p−1) for short. Since we are considering (5.4) modulo
pβ+1 , and since the sum on the right-hand side of (5.5) has the prefactor pβ , we may
reduce these denominators modulo p. Explicitly, we have
(p−1)N p−1
(p−1)N −1
(−1)(p−1)N (p − 1)N
z
+ (p − 1)N − 1

1 (mod p),
if p = 2 and N is even,





if p = 2 and N is odd,
z (mod p),
= −1 (mod p),
(5.7)
if p ≥ 3 and N ≡ 0 mod p


p−1

z
(mod p),
if p ≥ 3 and N ≡ −1 mod p


 p−1
−1
z
− (N + 1) (mod p), if p ≥ 3 and N 6≡ 0, 1 mod p
In all cases, the reciprocals of the polynomials on the right-hand side of (5.7) are
elements of Z[z, z −1 , Y −1 (z)]. (Here we use that N ≡ −1 (mod p) and µ(Γ) ≡ 1 (mod p)

FREE SUBGROUP NUMBERS MODULO PRIME POWERS

15

are equivalent.) Hence, in our computation, the coefficients ci,β+1;j (z) may be assumed
to lie in Z[z, z −1 , Y −1 (z)].
If relation (5.5) is substituted in (5.4), then one sees that this congruence reduces to
µ(Γ)−1

Fβ (z) + p

β

X

bi,β+1 (z)Φi (z)

i=0





µ(Γ)−1

− z (Fβp−1(z) − 1)N + pβ (p − 1)NFβp−2 (z)(Fβp−1 (z) − 1)N −1

X
i=0



(µ(Γ)−1)
′
− pP z, Fβ (z), Fβ (z), . . . , Fβ
(z) = 0

bi,β+1 (z)Φi (z)

modulo pβ+1 .

By definition of Fβ (z), we may divide both sides by pβ . This leads to the congruence
µ(Γ)−1

Gβ (z) +

X

bi,β+1 (z)Φi (z)

i=0

− (p −

µ(Γ)−1

1)NzFβp−2 (z)(Fβp−1 (z)

− 1)

N −1

X

bi,β+1 (z)Φi (z) = 0

modulo p,

i=0

for some explicitly given polynomial Gβ (z) in Φ(z) with coefficients in Z[z, z −1 , Y −1 (z)].
By construction, we have
Fβ (z) = Φ(z) modulo p.
Using this in the above congruence, we arrive at
p−2

Gβ (z) + 1 − (p − 1)NzΦ

p−1

(z)(Φ

(z) − 1)

N −1

µ(Γ)−1
 X

bi,β+1 (z)Φi (z) = 0

i=0

modulo p. (5.8)

By reducing “high” powers of Φ(z) by means of (4.1) and subsequently comparing
coefficients of powers of Φ(z), we obtain a system of linear equations over Z/pZ for
the unknown rational functions bi,β+1 (z), i = 0, 1, . . . , µ(Γ) − 1. As inspection shows,
the coefficient matrix of the system is exactly the same as the one arising from (4.5).
(The reader should in particular compare (5.8) and (4.4).) We have computed the
determinant of this coefficient matrix in the proof of Lemma 3. As a matter of fact, it
equals (5.6) divided by z p−1 . Since (5.8) is a congruence modulo p, we have to reduce
(5.6) modulo p, which we did in (5.7). We observed that the reciprocals of the reduced
expressions lie in Z[z, z −1 , Y −1 (z)] in all cases. In particular, they are all non-zero.
Hence, there are unique rational functions bi,β+1 (z), i = 0, 1, . . . , µ(Γ) − 1, solving (5.8),
and all of them are elements of Z[z, z −1 , Y −1 (z)]. This completes the proof of the
theorem.

6. The main results
Let again Γ be a finitely generated virtually free group and p a prime such that
µp (Γ) = 0 and µ(Γ) ≥ 2. We are now in the position to derive the main results of
this paper, which say that the number of free subgroups of index mΓ λ in Γ, when

16

C. KRATTENTHALER AND T. W. MÜLLER

reduced modulo any given p-power, is congruent to a binomial coefficient involving λ
times a rational function in λ, respectively a sum involving these quantities. These
results are made precise in Corollaries 7 and 11 below. We accompany these results by
concrete examples, given in Example 8 and 9, which illustrate Corollary 7, respectively
Example 13, illustrating Corollary 11. Moreover, we explain in Remarks 10 and 14 how
the earlier results in [2, 4] fit into the more general picture that we present here.
Corollary 7. Let r be a non-negative integer. With the assumptions of Theorem 6, if
µ(Γ) ≡ 0, 1 (mod p), then
 µ(Γ)λ 
p−1
fλ (Γ) ≡ RΓ,p,r (λ) λ−r
(mod pα ), for λ ≡ r (mod p − 1),
(6.1)
p−1

where, RΓ,p,r (λ) is a rational function in λ.
Proof. By Theorem 6, the generating function
µ(Γ)−1

X

bi,α (z)Φi (z)

P∞

λ=1

fλ (Γ) z λ equals

modulo pα ,

(6.2)

i=0

and the coefficients bi,α (z) are elements of Z[z, z −1 , Y −1 (z)]. According to the definition
of Y (z), under our assumption µ(Γ) ≡ 0, 1 we have Y (z) = 1. Consequently, the
coefficients bi,α (z) are actually Laurent polynomials over the integers.
We must now extract the coefficient of z λ in (6.2). In order to do so, we appeal again
to the Lagrange inversion formula (cf. [13, Theorem 5.4.2]), which shows that
 µ(Γ)n 
(µ(Γ)−1)n+m m
p−1
n
m
p−1
hz i Φ (z) = (−1)
.
(6.3)
n n−m
p−1
If this is used to extract the coefficient of z λ in (6.2) for λ ≡ r (mod p − 1), then one
arrives at the assertion (6.1).

Example 8. We let p = 3 and Γ1 a finitely generated virtually free group with order
graph given by the normalised tree in Figure 4. In this situation, we have mΓ1 = 6,
ζ1 (Γ1 ) = 2, ζ2 (Γ1 ) = 4, ζ3 (Γ1 ) = 0, and ζ6 (Γ1 ) = −1, and thus


µ3 (Γ1 ) = 1 + ϕ 36 ζ3 (Γ1 ) + ϕ 66 ζ6 (Γ1 ) = 1 + 0 + (−1) = 0

and

µ(Γ1 ) = 1+ϕ

6
1



ζ1 (Γ1 )+ϕ

6
2



ζ2 (Γ1 )+ϕ

6
3



ζ3 (Γ1 )+ϕ

6
6



ζ6 (Γ1 ) = 1+4+8+0−1 = 12.

The functional equation for F (z) = FΓ1 (z) that we get from (2.6) and (2.8), after
reduction of the coefficients modulo 81, is
63z 3 F 9 (z)F ′′ (z) + 72z 3 F 3 (z)F ′′ (z) + 27z 3 F (z)F ′′ (z) + 72z 2 F 10 (z)F ′ (z)
+ 36z 2 F 9 (z)F ′ (z) + 9z 2 F 4 (z)F ′ (z) + 18z 2 F 3 (z)F ′ (z) + 27z 2 F 2 (z)F ′ (z)
+ 27z 2 F (z)F ′ (z) + 54z 2 F ′ (z) + zF 12 (z) + 36zF 11 (z) + 15zF 10 (z) + 72zF 9 (z)
+ 54zF 8 (z) + 46zF 6 (z) + 18zF 5 (z) + 21zF 4 (z) + 63zF 3 (z)
+ 9zF 2 (z) + 54zF (z) + 80F (z) + 16z = 0

modulo 81.

FREE SUBGROUP NUMBERS MODULO PRIME POWERS

17

6 ✉❅

❅2
❅ 6
❅

3
1

6 ✉

✉

1

✉3

2

Figure 4. The order graph of the group Γ1 in Example 8
The algorithm given in the proof of Theorem 6 to find a solution to this congruence
yields
F (z) = 15z + (27z + 1)Φ(z) + 69zΦ2 (z) + 9zΦ3 (z) + 42zΦ4 (z) + 27zΦ5 (z)
+ 39zΦ6 (z) + 27zΦ7 (z) + 66zΦ8 (z) + 72zΦ9 (z) + 12zΦ10 (z)

modulo 81.

Coefficient extraction then yields
f2L+1 (Γ1 ) ≡ (−1)

L+1



P1 (L)
12L + 6
L
(12L + 1)6

(mod 81),

for L ≥ 1,

where
P1 (L) = 18(473007L5 + 969687L4 + 765456L3 + 308998L2 + 72732L + 9080),
and
f2L (Γ1 ) ≡ (−1)

L+1



12L − 6
P2 (L)
(12L − 6) (11L − 4)4 L − 1

(mod 81),

for L ≥ 1,

where
P2 (L) = 324(48L6 − 528L5 + 6079L2 + 9091L4 − 10582L3 − 1874L + 286),
with the Pochhammer symbol (α)m being defined by (α)m := α(α + 1) · · · (α + m − 1)
for m ≥ 1, and (α)0 := 1.
Example 9. We let p = 2 and Γ2 a finitely generated virtually free group with order
graph given by the normalised tree in Figure 5. In this situation, we have mΓ2 = 30,
ζ1 (Γ2 ) = 0, ζ2 (Γ2 ) = 0, ζ3 (Γ2 ) = 3, ζ5 (Γ2 ) = 1, ζ6 (Γ2 ) = 0, ζ10 (Γ2 ) = 0, ζ15 (Γ2 ) = 5,
and ζ30 (Γ2 ) = −1, and thus




30
µ2 (Γ2 ) = 1 + ϕ 30
ζ2 (Γ2 ) + ϕ 30
ζ6 (Γ2 ) + ϕ 10
ζ10 (Γ2 ) + ϕ 30
ζ30 (Γ2 )
2
6
30
= 1 + 0 + 0 + (−1) = 0

and
µ(Γ2 ) = 1 + ϕ

30
1




ζ1 (Γ2 ) + ϕ 30
ζ2 (Γ2 ) + ϕ 30
ζ3 (Γ2 ) + ϕ 30
ζ5 (Γ2 ) + ϕ
2
3
5



30
+ ϕ 10
ζ10 (Γ2 ) + ϕ 30
ζ15 (Γ2 ) + ϕ 30
ζ30 (Γ2 )
15
30


= 1 + 0 + 0 + 12 + 2 + 0 + 0 + 5 + (−1) = 19.

30
6



ζ6 (Γ2 )

18

C. KRATTENTHALER AND T. W. MÜLLER

10 ✉❅
6

❅5
❅ 30
✉
❅✉

6 ✉

3
3

30
15

3

✉6

Figure 5. The order graph of the group Γ2 in Example 9

The functional equation for F (z) = FΓ2 (z) that we get from (2.6) and (2.8), after
reduction of the coefficients modulo 16, is

4z 3 F 16 (z)F ′′ (z) + 8z 3 F 8 (z)F ′′ (z) + 4z 3 F ′′ (z) + 10z 2 F 17 (z)F ′ (z) + 10z 2 F 16 (z)F ′ (z)
+ 8z 2 F 13 (z)F ′ (z) + 8z 2 F 12 (z)F ′ (z) + 12z 2 F 9 (z)F ′ (z) + 12z 2 F 8 (z)F ′ (z)
+ 8z 2 F 5 (z)F ′ (z) + 8z 2 F 4 (z)F ′ (z) + 10z 2 F (z)F ′ (z) + 10z 2 F ′ (z) + zF 19 (z)
+ 13zF 18 (z) + 11zF 17 (z) + 7zF 16 (z) + 4zF 15 (z) + 4zF 14 (z) + 12zF 13 (z)
+ 12zF 12 (z) + 14zF 11 (z) + 6zF 10 (z) + 10zF 9 (z) + 2zF 8 (z) + 4zF 7 (z) + 4zF 6 (z)
+12zF 5 (z)+12zF 4 (z)+9zF 3 (z)+5zF 2 (z)+3zF (z)+15F (z)+15z = 0

modulo 16.

The algorithm given in the proof of Theorem 6 to find a solution to this congruence
yields

F (z) = 4z + 5Φ(z) + (12z + 2)Φ2 (z) + 8Φ3 (z) + 12Φ4 (z) + 8Φ5 (z) + 8zΦ8 (z)
+ 8zΦ10 (z) + 4zΦ16 (z) + 12zΦ18 (z)

modulo 16.

Coefficient extraction then yields

fλ (Γ2 )


Q(λ)
19λ
≡
3λ(6λ + 1)(9λ + 1)(9λ + 2)(18λ + 5)(19λ − 18)19 λ − 1

(mod 16),
for λ ≥ 2,

FREE SUBGROUP NUMBERS MODULO PRIME POWERS

19

where
Q(λ) = 41487381613117440000 + 1687131469740810240000λ
+ 11694465019743123456000λ2 + 292824544319204134118400λ3
− 2920284679646876757433344λ4 + 29139678526675320716647104λ5
− 208744430518331785363075776λ6 + 1109655351908161743775529040λ7
− 4529445293042933659974133664λ8 + 13823323659414730061860809764λ9
− 27457006500072077685531953836λ10 + 13774006864417015570820956495λ11
+ 106285230034124606189268827556λ12 − 297352958635465036740864629691λ13
− 141581261268484414672371284786λ14 + 3042215815187103665497014434600λ15
− 10200061275321550038724683325744λ16 + 20246947276823841509192253805174λ17
− 27403542237122957637017406285816λ18 + 26128885491619758888717502991655λ19
− 17392298204833244937049876124804λ20 + 7727636538613299232368005827649λ21
− 2065181275328822431645181305786λ22 + 251508577253835734501825269810λ23.
Remark 10. More generally, if p = 2, µ2 (Γ) = 0 and µ(Γ) ≥ 2, then we are always in the
case covered by Corollary 7, since, trivially, µ(Γ) ≡ 0 (mod 2) or µ(Γ) ≡ 1 (mod 2). In
particular, we see that the discussion of the subgroup numbers of lifts of Hecke groups
H(q) ∼
= C2 ∗ Cq with q a Fermat prime modulo powers of 2 in [2, Sec. 8 and second
part of Sec. 13] fits into the framework of Corollary 7, which can be regarded as a vast
generalisation. It has to be emphasised yet that the results for lifts of Hecke groups
in [2] go slightly further than Corollary 7 in that case as the basic series used there
— which is the mod-2-reduction of our basic series Φ(z) — allows for a very efficient
coefficient extraction, a point that we did not touch in the present paper.
Now we turn to the somewhat more complicated case when µ(Γ) 6≡ 0, 1 (mod p).
Corollary 11. Let r be an integer with 0 ≤ r ≤ p − 2. With the assumptions of
Theorem 6, if µ(Γ) 6≡ 0, 1 (mod p), then
λ/(p−1)
µ(Γ)
(1)
fλ (Γ) ≡
+1
RΓ,p,r (λ)
p−1

k
 µ(Γ)λ
⌊λ/(p−1)⌋ 
X
− µ(Γ)k
µ(Γ)
(2)
p−1
+
+ 1 RΓ,p,r (λ, k)
λ−r
p−1
−k
p−1


(mod pα ),

k=0

for λ ≡ r (mod p − 1), (6.4)

(1)

(2)

where RΓ,p,r (λ) and RΓ,p,r (λ, k) are rational functions in their respective arguments.
(2)
λ
− k.
Moreover, RΓ,p,r (λ, k) depends only on p−1
Proof. We begin as in the proof
11 by quoting Theorem 6, which tells us
P of Corollary
λ
that the generating function ∞
f
z
is
given
by (6.2) modulo pα . However, here we
λ
λ=1
p−1
−1
have Y (z) = z
− (N + 1) , with N = µ(Γ)/(p − 1).

20

C. KRATTENTHALER AND T. W. MÜLLER

Again, we must now extract the coefficient of z λ in (6.2). Here, we must first expand
fractions,

∞ 
X
1
q+k−1
1
q
q
q = (−1) (N + 1)
= p−1
(N + 1)k z (p−1)k .
Y q (z)
k
z
− (N + 1)−1
k=0

Subsequent coefficient extraction using (6.3) leads to the result in (6.4), where the term
(1)
containing RΓ,p,r (λ) comes from the summand b0,α (z) in (6.2), while the term containing
(2)
RΓ,p,r (λ, k) is generated by the remaining summands in (6.2).

We now show that the sum on the right-hand side of (6.4) satisfies a linear recurrence
with constant coefficients, so that the computation of this sum modulo pα can be
achieved in essentially linear time with growing λ by reducing results modulo pα after
each iteration of the recurrence. (We say “essentially” since the computation of the
inhomogeneous part of the recurrence does grow super-linearly.)
Proposition 12. Let r be an integer with 0 ≤ r ≤ p − 2, and let Sr (λ) denote the sum
on the right-hand side of (6.4). Then we have


d+1
X
j d+1
M d+1−j Sr (λ + (p − 1)j) = gr (λ), for λ ≡ r (mod p − 1), (6.5)
(−1)
j
j=0
(2)

where d is the numerator degree of RΓ,p,r (λ, k) in λ, M = µ(Γ)
+ 1, and gr (λ) is a
p−1
hypergeometric term, that is, g(λ + 1)/g(λ) equals a rational function in λ.

Proof. We fix r, and we write λ = (p − 1)L + r. Using this notation, the sum Sr (λ) has
the form
L
X
Sr (λ) = Sr ((p − 1)L + r) =
M k A(L − k, L) f (L − k),
(6.6)
k=0

where A(x, y) is a polynomial in x and y of degree d in y, and f (L − k) comprises
the binomial coefficient on the right-hand side of (6.4) as well as the denominator of
(2)
RΓ,p,r (λ, k). We chose to parametrise the polynomial A(L−k, L) in this slightly unusual
form since it will be of advantage during the following computation.
Let E denote the shift operator in L, that is, (Eh)(L) := h(L + 1). We now apply
(E − M · id)d+1 to (6.6). We obtain
(E − M · id)d+1 Sr ((p − 1)L + r)


L+j
d+1
X
X
d+1−j
d+1−j d + 1
M
M k A(L + j − k, L + j) f (L + j − k)
(−1)
=
j
j=0
k=0


L
d+1
X
X
d+1
M k+j A(L − k, L + j) f (L − k)
M d+1−j
=
(−1)d+1−j
j
j=0
k=−j


L
d+1
X
X
d+k+1
d+1−j d + 1
A(L − k, L + j) + Gr (L),
=
M
f (L − k)
(−1)
j
j=0
k=0

where Gr (L) is the hypergeometric term resulting from summands that we split off
when passing from the summation over k running from −j to L in the next-to-last line

FREE SUBGROUP NUMBERS MODULO PRIME POWERS

7

21

2
1

✉

Figure 6. The order graph of the group H(7) in Example 13
to the summation over k running from 0 to L in the last line. Using the difference
operator ∆t defined by (∆t h)(t) := h(t + 1) − h(t), this last expression can be rewritten
as
(E−M ·id)

d+1

Sr ((p−1)L+r) =

L
X

M d+k+1 f (L−k) ∆d+1
A(L−k, t)
t

t=L

+Gr (L). (6.7)

k=0

We assumed that A(x, y) is a polynomial of degree d in y, hence ∆d+1
kills A(L − k, t).
t
Consequently, on the right-hand side in (6.7) there remains only Gr (L), while, after
expansion of (E − M · id)d+1 , the left-hand side becomes the left-hand side of (6.5), as
desired.

Example 13. We consider the Hecke group H(7) = C2 ∗ C7 , whose order graph is shown
in Figure 6, and the prime p = 7. We have mH(7) = 14, ζ1 (H(7)) = 1, ζ2 (H(7)) = 0,
ζ7 (H(7)) = 0, and ζ14 (H(7)) = −1, and thus µ7 (H(7)) = 0 and µ(H(7)) = 6.
The functional equation for F (z) = FH(7) (z) that we get from (2.6) and (2.8) is
sufficiently small to be displayed here:
537824z 6 F (5) (z) + 230496z 5 F (z)F (4) (z) + 6991712z 5F (4) (z) + 41160z 4 F (z)2 F (3) (z)
2
+ 1959216z 4F (z)F (3) (z) + 24989608z 4 F (3) (z) + 384160z 5 F ′′ (z) + 3920z 3 F 3 (z)F ′′ (z)
3
+ 205800z 3F 2 (z)F ′′ (z) + 3874528z 3 F (z)F ′′ (z) + 25988424z 3F ′′ (z) + 41160z 4 F ′ (z)
2
2
2
+ 8820z 3 F 2 (z) F ′ (z) + 288120z 3 F (z) F ′ (z) + 2512132z 3 F ′ (z)
+ 210z 2 F 4 (z)F ′ (z) + 9800z 2 F 3 (z)F ′ (z) + 180516z 2 F 2 (z)F ′ (z) + 1561336z 2 F (z)F ′ (z)
+ 5336394z 2 F ′ (z) + 576240z 5 F (3) (z)F ′ (z) + 164640z 4 F (z)F ′ (z)F ′′ (z)
+ 3649520z 4 F ′ (z)F ′′ (z) + zF 6 (z) + 42zF 5 (z) + 679zF 4 (z) + 5292zF 3 (z)
+ 20335zF 2(z) + 34986zF (z) − F (z) + 19305z = 0.
The algorithm in the proof of Theorem 6 to find a solution to this congruence gives
7 8z 18 + 12z 17 + 7z 15 + 7z 13 + 48z 12 + 16z 11

+7z 10 + 35z 9 + 42z 7 + 23z 6 + 24z 5 + 21z 4 + 42z 3 + 14z

(1 − 2z 6 )3


7 35z 18 + 11z 17 + 30z 16 + 14z 14 + 14z 12 + 17z 11


+47z 10 + 14z 9 + 42z 8 + 21z 6 + z 5 + 32z 4 + 42z 3 
 Φ(z)
1
+
+


(1 − 2z 6 )3

22

C. KRATTENTHALER AND T. W. MÜLLER

+

7 28z 17 + 36z 16 + 31z 15 + 14z 14 + 7z 13 + 21z 11 + 20z 10

+18z 9 + 35z 8 + 28z 7 + 7z 5 + 30z 4 + 41z 3 + 28z 2 + 21z
2z 6 )3

7

42z 16

+

29z 15

+

+

(1 −
+
+ 7z 12 + 7z 10 + 27z 9

8
+48z + 35z 7 + 21z 6 + 35z 4 + 16z 3 + 2z 2 + 42z

22z 14

7z 13

2z 6 )3

7
+

+

42z 17

+

14z 15

Φ3 (z)

(1 −
+
+
+ 7z 12 + 42z 11

9
8
+35z + z + 23z 7 + 21z 6 + 42z 5 + 28z 3 + 26z 2 + 31z
41z 14

Φ2 (z)

19z 13

(1 − 2z 6 )3
7 22z 18 + 21z 17 + 21z 16 + 21z 14 + 34z 12 + 7z 11

+7z 10 + 28z 8 + 9z 6 + 28z 5 + 28z 4 + 42z 2
(1 −

2z 6 )3

Φ4 (z)

Φ5 (z)

modulo 343. (6.8)

Finally, we have to extract coefficients. We content ourselves with displaying here the
results for fλ (H(7)) for λ ≡ 0 (mod 6); for the other congruence classes for λ, similar
results are available. By comparing coefficients of z 6λ on both sides of (6.8), we obtain
f6λ (H(7)) ≡ 7 · 2λ−2 (49λ2 − 7λ + 4)


∞
X
k+λ k−4 5 (5k − 5λ + 1) (k − λ)S(λ) 6λ − 6k
(−1) 2
+7
λ−k
3 (6λ − 6k − 5)5
k=0

(mod 343), (6.9)

where

S(λ) = 22661k 4 − 45322k 3 λ + 70594k 3 + 22661k 2 λ2 − 110545k 2 λ + 92331k 2 + 39951kλ2
− 110913kλ + 56014k + 28424λ2 − 38696λ + 12528.
Let us denote the sum on the right-hand side of the congruence (6.9) by S(λ). Applying
Proposition 12 (or, more precisely, its proof; alternatively, one may use the Gosper–
Zeilberger algorithm; cf. [11]), we see that S(λ) satisfies the recurrence
S(λ + 3) − 6S(λ + 2) + 12S(λ + 1) − 8S(λ)
= 84 (−1)l+1 T (λ)

(l + 1)(2l − 1)(3l − 2)(3l − 1)(6l − 5)(6l − 1) (6l)! (6l − 6)!
,
(5l + 11)(5l + 12)(5l + 13) (l + 1)! (5l + 10)! (6l − 1)!

where
T (λ) = 7578375074183l12 + 110764942152696l11 + 719438896272607l10
+ 2739679993093800l9 + 6794561274739329l8 + 11525824255968648l7
+ 13662933657289381l6 + 11354903297697240l5 + 6532000464773588l4
+ 2520106018198656l3 + 613697061412512l2 + 83672481893760l + 4738762828800.
Remark 14. The discussion of free subgroup numbers of lifts Γm (3) of the classical
modular group H(3) ∼
= PSL2 (Z) in [4, Sec. 16] taken modulo powers of 3 fits into the
framework of Corollary 11. Indeed, for these lifts, we have µΓm (3) = 2, which is not
congruent to 0, 1 (mod 3). Consequently, according to Theorem 6, we must be prepared
to encounter denominators in the coefficients of the polynomial in Φ(z) that expresses

FREE SUBGROUP NUMBERS MODULO PRIME POWERS

23

the generating function for the free subgroup numbers when coefficients are reduced
modulo a power of 3. This is exactly what happened in [4], and this is also the reason
why coefficient extraction was considerably harder in [4] than in [2].
References
[1] A. Dress and T. W. Müller, Decomposable functors and the exponential principle, Adv. Math. 129
(1997), 188–221.
[2] M. Kauers, C. Krattenthaler, and T. W. Müller, A method for determining the mod-2k behaviour
of recursive sequences, with applications to subgroup counting, Electron. J. Combin. 18 (2012),
Art. #P37, 83 pp.
[3] C. Krattenthaler and T. W. Müller, A Riccati differential equation and free subgroup numbers for
lifts of PSL2 (Z) modulo prime powers, J. Combin. Theory Ser. A 120 (2013), 2039–2063.
[4] C. Krattenthaler and T. W. Müller, A method for determining the mod-3k behaviour of recursive
sequences, preprint, 83 pages; arχiv:1308.2856.
[5] C. Krattenthaler and T. W. Müller, A method for determining the mod-pk behaviour of recursive
sequences, preprint, 35 pages; arχiv:1508.02580.
[6] C. Krattenthaler and T. W. Müller, Periodicity of free subgroup numbers modulo prime powers,
J. Algebra 452 (2016), 372–389.
[7] C. Krattenthaler and T. W. Müller, Normalising graphs of groups, preprint.
[8] T. W. Müller, A group-theoretical generalization of Pascal’s triangle, Europ. J. Combin. 12 (1991),
43–49.
[9] T. W. Müller, Combinatorial aspects of finitely generated virtually free groups, J. London Math.
Soc. (2) 44 (1991), 75–94.
[10] T. W. Müller and J.-C. Schlage-Puchta, Modular arithmetic of free subgroups, Forum Math. 17
(2005), 375–405.
[11] M. Petkovšek, H. Wilf, and D. Zeilberger, A=B, A. K. Peters, Wellesley, 1996.
[12] J.-P. Serre, Arbres, Amalgames, SL2 , Astérisque, vol. 46, Société mathématique de France, Paris,
1977.
[13] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.
†
Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, A-1090
Vienna, 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.

