FREE SUBGROUP NUMBERS MODULO PRIME POWERS: THE NON-PERIODIC CASE

C. KRATTENTHALER^{†} AND T. W. MÜ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 Γ. A concrete example of a (non-free) finitely generated virtually free group that the reader may want to keep in mind is the inhomogeneous modular group Γ_{0} = PSL_{2}(ℤ) ≅ C_{2} ∗ C_{3}, where C_{m} denotes the cyclic group of order m. Here, we have m_{Γ_{0}} = lcm{2, 3} = 6, and the first few terms of the sequence (f_{λ}(Γ_{0}))_{λ≥1} are

5, 60, 1105, 27120, 828250, 30220800, 1282031525, 61999046400, 3366961243750, …

In [6], a complete characterisation is given of all pairs (Γ, p^{α}) for which the sequence (f_{λ}(Γ))_{λ≥1} is ultimately periodic modulo p^{α}, where Γ is a finitely generated virtually free group, p is a prime number, and α is a positive integer. 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. In our running example Γ_{0} = PSL_{2}(ℤ), we have μ(Γ_{0}) = 2, μ_{2}(Γ_{0}) = μ_{3}(Γ_{0}) = 0, and μ_{p}(Γ_{0}) = 1 for p ≥ 5. Indeed, the sequence (f_{λ}(PSL_{2}(ℤ)))_{λ≥1} is ultimately periodic modulo p^{α} for p ≥ 5 and all α, and non-periodic for p = 2, 3; see [3], [2, Sec. 8], [4, Sec. 16], where more precise

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 S50-N15, 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.

results are obtained for the free subgroup numbers of the inhomogeneous modular group and certain lifts thereof.

Our present paper focuses on the case of non-periodic behaviour. It is shown in [10] that, for μ_{p}(Γ) = 0 and μ(Γ) ≥ 2, the function f_{λ}(Γ) satisfies the congruence

f_{λ}(Γ) ≡ (−1)^{\frac{(μ(Γ)−1)λ+1}{p−1}} \frac{1}{λ}(\frac{μ(Γ)λ}{p−1} ; \frac{λ−1}{p−1}) (mod p),  (1.1)

where the binomial coefficient is defined to be zero whenever the lower argument is not an integer; cf. [10, Eqn. (35)].

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 8 in Section 6), while in the remaining cases the right-hand side takes the form of a sum of such expressions (see Corollary 12 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 (see Corollary 7).

While the result obtained in Corollary 8 for arbitrary p-powers is ‘as good as’ the mod p result (1.1), we show in Proposition 13 that the sum described in Corollary 12 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 ℌ(q) ≅ C_{2} ∗ C_{q} with q a Fermat prime and p = 2, and (ii) lifts of the classical modular group ℌ(3) ≅ PSL_{2}(ℤ) 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

Φ(z) = ∑_{n=1}^{∞}(−1)^{\frac{(μ(Γ)−1)n+1}{p−1}} \frac{1}{n}(\frac{μ(Γ)n}{p−1} ; \frac{n−1}{p−1}) z^{n}  (1.2)

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

as basic series (i.e., the series formed out of the coefficients on the right-hand side of (1.1)) in order to express the generating function ∑_{λ=1}^{∞} f_{λ}(Γ) z^{λ} modulo p-powers as a polynomial in Φ(z). Corollaries 8 and 12 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 degree of the polynomial in the basic series Φ(z) expressing the generating function ∑_{λ=1}^{∞} f_{λ}(Γ) z^{λ} modulo p^{α} does not increase with α. As a 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(ē) = 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, ē} (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. For our running example Γ_{0} = PSL_{2}(ℤ) ≅ C_{2} ∗ C_{3}, we may choose V (X) = {v_{1}, v_{2}} and E(X) = {e, ē}. Figure 1.a shows the corresponding S-graph X.

•  •_{v_{1}}  _{v_{2}}_{e}^{ē}_{→}_{←}  •  •_{C_{2}}  _{C_{3}}_{1}_{→}_{←}  •  •_{2}  _{3}_{1}

Figure 1. a. An S-graph, b. a graph of groups, c. an order graph for PSL_{2}(ℤ)

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) ≅ Γ. Figure 1.b shows a graph of groups with fundamental group PSL_{2}(ℤ) ≅ C_{2} ∗ C_{3}. Replacing the stabiliser groups of vertices and edges by their respective group orders and replacing each pair (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. Figure 1.c shows the order graph for PSL_{2}(ℤ) corresponding to the graph of groups in Figure 1.b.

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)

(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]. In our running example of the inhomogeneous modular group Γ_{0} = PSL_{2}(ℤ), we have m_{Γ_{0}} = lcm{2, 3} = 6, ζ_{1}(Γ_{0}) = 1, ζ_{2}(Γ_{0}) = ζ_{3}(Γ_{0}) = 0, and ζ_{6}(Γ_{0}) = −1.

Inspection of (2.1) and (2.2) reveals the noteworthy fact 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 m_{G} to be the least common multiple of the vertex orders n(v), taken over all vertices of G, and, for a divisor κ of m_{G}, 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

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

(2.4)

in particular, g_{0}(Γ) = 1. (There exists an explicit product formula for g_{λ}(Γ) in terms of a corresponding graph of groups, see [9, Prop. 3].) The sequences (f_{λ}(Γ))_{λ≥1} and (g_{λ}(Γ))_{λ≥0} are related via the Hall-type transformation formula^{3}

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

Introducing the generating functions

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

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

F_{Γ}(z) = m_{Γ}z \frac{d}{dz} ( log G_{Γ}(z)).  (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

μ(Γ) = 1 + ∑_{κ|m_{Γ}} φ(m_{Γ}/κ)ζ_{κ}(Γ),  (2.7)

where φ is Euler’s totient function. This formula implies in particular that μ(Γ) is well-defined. In our running example Γ_{0} = PSL_{2}(ℤ), we have

μ(Γ_{0}) = 1 + φ(6)ζ_{1}(Γ_{0}) + φ(3)ζ_{2}(Γ_{0}) + φ(2)ζ_{3}(Γ_{0}) + φ(1)ζ_{6}(Γ_{0}) = 2.

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) + ∑_{μ=2}^{μ(Γ)} θ_{μ}(Γ)z^{μ}G_{Γ}^{(μ)}(z) = 0  (2.8)

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

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

cf. [9, Prop. 5]. The linear differential equation (2.8) can subsequently be translated into a Riccati-type differential equation for F (z) via the relation (2.6). In our running example Γ_{0} = PSL_{2}(ℤ), the differential equation (2.8) becomes

5G(z) + (72z − 6)G′(z) + 36z^{2}G′′(z) = 0,

which translates into the differential equation

5z + (6z − 1)F (z) + zF^{2}(z) + 6z^{2}F′(z) = 0

satisfied by the generating function F (z) for the free subgroup numbers f_{λ}(PSL_{2}(ℤ)).

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

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

μ_{p}(Γ) = 1 + ∑_{p|κ|m_{Γ}} φ(m_{Γ}/κ)ζ_{κ}(Γ).  (2.10)

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_{Γ}. As already mentioned in the introduction, for Γ_{0} = PSL_{2}(ℤ) we have μ(Γ_{0}) = 2, μ_{2}(Γ_{0}) = μ_{3}(Γ_{0}) = 0, and μ_{p}(Γ_{0}) = 1 for p ≥ 5. 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 that^{4}

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

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

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

or

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

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

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 tree^{5} X underlying the Stallings decomposition (Γ(−), X) of a finitely generated virtually free group Γ must be constructed so as to satisfy μ_{p}(Γ) = 0.

4The notation used in Equation (2.11) follows Serre; see Déf. 8 in [12, Sec. 4.4].

5Here, order tree means an order graph which has the form of a tree.

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 v_{1} and v_{2}, with v_{1} closer to the root than v_{2}, satisfy ℓ(v_{2}) | ℓ(v_{1}) and ℓ(v_{2}) < ℓ(v_{1}), where ℓ(v_{1}) and ℓ(v_{2}) denote the labels of v_{1} and v_{2}. See Figure 2 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.

[figure: 2; 3; 12; 504; 42; 6; 2]

Figure 2. A divisor tree for p = 5

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-trivial^{6} 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 3 shows an example of such a map f defined on the vertices of the divisor tree in Figure 2. 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 4 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 v_{1} and v_{2} are adjacent in D, where v_{1} is closer to the root than v_{2}, then we glue the root of f(v_{2}) to one of the leaves of f(v_{1}). 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 the root of D. In Figure 4, 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 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).

6Here, ‘non-trivial’ means ‘at least two vertices’.

[figure: ⟶; ⟶; ⟶; ⟶; ⟶; ⟶; ⟶; 504; 6; 12; 2; (left-bottom); 42; 2; (right-top); 3]

Figure 3. A function f on the vertices of the divisor tree of Figure 2

[figure: 10; 10; 60; 15; 60; 60; 5040; 210; 30; 30; 10; 10; 10; 10; 2; 2; 3; 12; 12; 12; 2; 2; 2; 2; 42; 6; 6]

Figure 4. An order tree resulting from the divisor tree of Figure 2 and the function f from Figure 3

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 | m_{G}, and that ζ_{κ}(G) = 0 for p | κ | m_{G} and κ < m_{G}. 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 S_{pm}(G). We claim that S_{pm}(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 ẽ with n(ẽ) properly dividing n(v^{∗}) = pm′. The order n(ẽ) cannot be m′ since this would contradict minimality of m. Thus, n(ẽ) = 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 = m_{G}, then S_{pm}(G) = G and indeed μ_{p}(Γ) = μ_{p}(G) = 0.

If pm < m_{G}, then the connected components of S_{pm}(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 < m_{G}. 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.

We now remove S_{pm}(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 S_{pm}(G), of S_{pm′}(G′), … is interpreted as a vertex labelled by m, by m′, …, respectively, and two vertices, v_{1} and v_{2} say, are connected by an edge if the (incomplete) tree, C(v_{2}) say, corresponding to v_{2} was attached to the (incomplete) tree, C(v_{1}) say, corresponding to v_{1} in the original order tree G. The label of v_{2} divides the one of v_{1} since the order of the leaf of C(v_{1}) on which C(v_{2}) was attached must be a multiple of the order of the edges of C(v_{2}).

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

Φ(z) = ∑_{n=1}^{∞}(−1)^{Nn− \frac{n−1}{p−1}} \frac{1}{n}\binom{Nn}{\frac{n−1}{p−1}} z^{n}.

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

Φ(z) − z (Φ^{p−1}(z) − 1)^{N} = 0.  (4.1)

Lemma 3. We have

Φ′(z) = \frac{Pol(z, Φ(z))}{(−1)^{(p−1)N}((p − 1)N)^{(p−1)N}z^{p−1} + ((p − 1)N − 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

Φ′(z) − (Φ^{p−1}(z) − 1)^{N} − zN(p − 1)Φ′(z)Φ^{p−2}(z) (Φ^{p−1}(z) − 1)^{N−1} = 0.

Hence,

Φ′(z) = \frac{(Φ^{p−1}(z) − 1)^{N}}{1 − zN(p − 1)Φ^{p−2}(z) (Φ^{p−1}(z) − 1)^{N−1}} .  (4.3)

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

(1 − zN(p − 1)Φ^{p−2}(z) (Φ^{p−1}(z) − 1)^{N−1}) ∑_{i=0}^{(p−1)N−1} b_{i}(z)Φ^{i}(z) = 1,  (4.4)

with at this point undetermined coefficients b_{i}(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

((1 − N(p − 1))Φ^{p−1}(z) − 1) ∑_{i=0}^{(p−1)N−1} b_{i}(z)Φ^{i}(z) = Φ^{p−1}(z) − 1.  (4.5)

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

(1 − N(p − 1)) ∑_{i=0}^{(p−1)N−p} b_{i}(z)Φ^{i+p−1}(z)

+ (1 − N(p − 1)) ∑_{i=0}^{p−2} b_{i+(p−1)(N−1)}(z)(z^{−1}Φ^{i+1}(z) − ∑_{k=0}^{N−1} \binom{N}{k}(−1)^{N−k}Φ^{i+(p−1)k}(z))

− ∑_{i=0}^{(p−1)N−1} b_{i}(z)Φ^{i}(z) = Φ^{p−1}(z) − 1.

Comparison of powers of Φ(z) then yields a system of equations of the form

M · b = c,  (4.6)

where b = (b_{i}(z))_{0≤i≤(p−1)N−1} is the column vector of unknowns, c = (c_{i})_{0≤i≤(p−1)N−1} with c_{0} = −1, c_{p−1} = 1, and c_{i} = 0 otherwise, and M is the (p − 1)N × (p − 1)N matrix given by

M_{i,j} = \begin{cases}−1 & if 0 ≤ i = j ≤ (p − 1)N − p, \\ X & if p − 1 ≤ i = j + p − 1 ≤ (p − 1)N − 1, \\ Xz^{−1} & if 1 ≤ i = j − (p − 1)(N − 1) + 1 ≤ p − 1, \\ (−1)^{N−k−1}\binom{N}{k}X & if 0 ≤ i − (p − 1)k = j − (p − 1)(N − 1) ≤ p − 2, \\ & for some k with 0 ≤ k ≤ N − 1, \end{cases}

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 result is the matrix

(\begin{matrix}A & 0 & 0 & … & 0 & C \\ B & A & 0 & … & 0 & 0 \\ 0 & B & A & … & 0 & 0 \\ ⋮ & & ... & ... & & ⋮ \\ 0 & … & 0 & B & A & 0 \\ 0 & … & 0 & 0 & B & A \end{matrix}) ,  (4.7)

where the block A is the N × N matrix given by

A = (\begin{matrix}−1 & 0 & 0 & … & 0 & (−1)^{N−1}X \\ X & −1 & 0 & … & 0 & (−1)^{N−2}X\binom{N}{1} \\ 0 & X & −1 & … & 0 & (−1)^{N−3}X\binom{N}{2} \\ ⋮ & & ... & ... & & ⋮ \\ 0 & … & 0 & X & −1 & −X\binom{N}{N−2} \\ 0 & … & & 0 & X & X\binom{N}{N−1} − 1 \end{matrix}) ,  (4.8)

B is the N × N matrix given by

B = (\begin{matrix}0 & … & 0 & Xz^{−1} \\ 0 & … & 0 & 0 \\ ⋮ & & ⋮ & ⋮ \\ 0 & … & 0 & 0 \end{matrix}) ,

and C is the N × N matrix given by

C = (\begin{matrix}0 & … & 0 & 0 \\ 0 & … & 0 & Xz^{−1} \\ 0 & … & 0 & 0 \\ ⋮ & & ⋮ & ⋮ \\ 0 & … & 0 & 0 \end{matrix}) .

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 b_{i}(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 c_{1} +c_{2}, where c_{1} 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 c_{2} is the “rest,” that is, the index i entry equals

(−1)^{N−(i−(p−2)N)−1)}\binom{N}{i − (p − 2)N}X − δ_{i,(p−1)N−1}

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

det (\begin{matrix}A & 0 & 0 & … & 0 & 0 \\ B & A & 0 & … & 0 & 0 \\ 0 & B & A & … & 0 & 0 \\ ⋮ & & ... & ... & & ⋮ \\ 0 & … & 0 & B & A & 0 \\ 0 & … & 0 & 0 & B & A \end{matrix}) ,  (4.9)

and the determinant of a second matrix, which arises from (4.7) by replacing the last column by c_{1}. 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

(−1)^{(p−1)N}Xz^{−1} det (\begin{matrix}A′ & 0 & 0 & … & 0 & 0 \\ B & A & 0 & … & 0 & 0 \\ 0 & B & A & … & 0 & 0 \\ ⋮ & & ... & ... & & ⋮ \\ 0 & … & 0 & B & A & 0 \\ 0 & … & 0 & 0 & B & A′′ \end{matrix}) ,  (4.11)

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

(−1)^{(p−1)N}Xz^{−1} (Xz^{−1})^{p−2} (−1)X^{(p−1)(N−1)−1} = ((p − 1)N − 1)^{(p−1)N−1}z^{−p+1}. □

Lemma 5. With the matrix A given by (4.8), We have

det A = (−1)^{N}((p − 1)N)^{N}.

Proof. We replace the 0-th row of A by

∑_{j=0}^{N−1} X^{−j} · (row j).

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

∑_{j=0}^{N−1} X^{−j}(−1)^{N−j−1}\binom{N}{j}X − X^{−N+1} = −X^{−N+1} ∑_{j=0}^{N} X^{N−j}(−1)^{N−j}\binom{N}{j}

= −X^{−N+1}(1 − X)^{N} = −\frac{((p − 1)N)^{N}}{X^{N−1}} . (4.12)

Thus, after the operation described above, the new matrix reads

(\begin{matrix}0 & 0 & 0 & … & 0 & Y \\ X & −1 & 0 & … & 0 & (−1)^{N−2}X\binom{N}{1} \\ 0 & X & −1 & … & 0 & (−1)^{N−3}X\binom{N}{2} \\ ⋮ & & ... & ... & & ⋮ \\ 0 & … & 0 & X & −1 & −X\binom{N}{N−2} \\ 0 & … & & 0 & X & X\binom{N}{N−1} − 1 \end{matrix}) ,

where Y denotes the quantity in (4.12). The determinant of this matrix, and thus the determinant of A, equals

(−1)^{N−1}X^{N−1}Y = (−1)^{N}((p − 1)N)^{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 generating function F_{Γ}(z) = ∑_{λ=1}^{∞} f_{λ}(Γ) z^{λ} of the number f_{λ}(Γ) of subgroups of index λ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^{−1}, Y^{−1}(z)], where

Y (z) = \begin{cases}z^{p−1} − (\frac{μ(Γ)}{p−1} + 1)^{−1}, & if p ≥ 3 and μ(Γ) ≢ 0, 1 (mod p), \\ 1, & otherwise. \end{cases}

Proof. It is known from [10, Prop. 2] that F (z) satisfies a differential equation of the form

F (z) = z (F^{p−1}(z) − 1)^{μ(Γ)/(p−1)} + pP (z, F (z), F′(z), …, F^{(μ(Γ)−1)}(z)) ,  (5.1)

where P(z, t_{0}, t_{1}, …, t_{μ(Γ)−1}) is a polynomial in z, t_{0}, t_{1}, …, 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^{−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. We now suppose that we have already found a polynomial

F_{β}(z) = ∑_{i=0}^{μ(Γ)−1} a_{i,β}(z)Φ^{i}(z),

with coefficients a_{i,β}(z) in ℤ[z, z^{−1}, Y^{−1}(z)], so that

F (z) = F_{β}(z) modulo p^{β}.  (5.2)

We then make the Ansatz

F (z) = F_{β+1}(z) = F_{β}(z) + p^{β} ∑_{i=0}^{μ(Γ)−1} b_{i,β+1}(z)Φ^{i}(z) modulo p^{β+1},  (5.3)

for certain, at this point undetermined, rational functions b_{i,β+1}(z) over the integers. We substitute this Ansatz in the differential equation (5.1) and reduce the result modulo p^{β+1}, to obtain

F_{β}(z) + p^{β} ∑_{i=0}^{μ(Γ)−1} b_{i,β+1}(z)Φ^{i}(z)

− z (F_{β}^{p−1}(z) + (p − 1)F_{β}^{p−2}(z)p^{β} ∑_{i=0}^{μ(Γ)−1} b_{i,β+1}(z)Φ^{i}(z) − 1)^{μ(Γ)/(p−1)}

− pP (z, F_{β+1}(z), F′_{β+1}(z), …, F_{β+1}^{(μ(Γ)−1)}(z)) = 0 modulo p^{β+1}. (5.4)

By Lemma 3, we have

F_{β+1}^{(j)}(z) = F_{β}^{(j)}(z) + p^{β} ∑_{i=0}^{μ(Γ)−1} c_{i,β+1;j}(z)Φ^{i}(z)  (5.5)

for all non-negative integers j and certain rational functions c_{i,β+1;j}(z). It should be noted that the denominators of these rational functions are powers of

(−1)^{(p−1)N}((p − 1)N)^{(p−1)N}z^{p−1} + ((p − 1)N − 1)^{(p−1)N−1},  (5.6)

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

(−1)^{(p−1)N}((p − 1)N)^{(p−1)N}z^{p−1} + ((p − 1)N − 1)^{(p−1)N−1}

= \begin{cases}1 (mod p), & if p = 2 and N is even, \\ z (mod p), & if p = 2 and N is odd, \\ −1 (mod p), & if p ≥ 3 and N ≡ 0 mod p \\ z^{p−1} (mod p), & if p ≥ 3 and N ≡ −1 mod p \\ z^{p−1} − (N + 1)^{−1} (mod p), & if p ≥ 3 and N ≢ 0, 1 mod p \end{cases} (5.7)

In all cases, the reciprocals of the polynomials on the right-hand side of (5.7) are elements of ℤ[z, z^{−1}, Y^{−1}(z)]. (Here we use that N ≡ −1 (mod p) and μ(Γ) ≡ 1 (mod p) are equivalent.) Hence, in our computation, the coefficients c_{i,β+1;j}(z) may be assumed to lie in ℤ[z, z^{−1}, Y^{−1}(z)].

If relation (5.5) is substituted in (5.4), then one sees that this congruence reduces to

F_{β}(z) + p^{β} ∑_{i=0}^{μ(Γ)−1} b_{i,β+1}(z)Φ^{i}(z)

− z ((F_{β}^{p−1}(z) − 1)^{N} + p^{β}(p − 1)NF_{β}^{p−2}(z)(F_{β}^{p−1}(z) − 1)^{N−1} ∑_{i=0}^{μ(Γ)−1} b_{i,β+1}(z)Φ^{i}(z))

− pP (z, F_{β}(z), F′_{β}(z), …, F_{β}^{(μ(Γ)−1)}(z)) = 0 modulo p^{β+1}.

By definition of F_{β}(z), we may divide both sides by p^{β}. This leads to the congruence

G_{β}(z) + ∑_{i=0}^{μ(Γ)−1} b_{i,β+1}(z)Φ^{i}(z)

− (p − 1)NzF_{β}^{p−2}(z)(F_{β}^{p−1}(z) − 1)^{N−1} ∑_{i=0}^{μ(Γ)−1} b_{i,β+1}(z)Φ^{i}(z) = 0 modulo p,

for some explicitly given polynomial G_{β}(z) in Φ(z) with coefficients in ℤ[z, z^{−1}, Y^{−1}(z)]. By construction, we have

F_{β}(z) = Φ(z) modulo p.

Using this in the above congruence, we arrive at

G_{β}(z) + (1 − (p − 1)NzΦ^{p−2}(z)(Φ^{p−1}(z) − 1)^{N−1}) ∑_{i=0}^{μ(Γ)−1} b_{i,β+1}(z)Φ^{i}(z) = 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 ℤ/pℤ for the unknown rational functions b_{i,β+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^{−1}, Y^{−1}(z)] in all cases. In particular, they are all non-zero. Hence, there are unique rational functions b_{i,β+1}(z), i = 0, 1, …, μ(Γ)−1, solving (5.8), and all of them are elements of ℤ[z, z^{−1}, Y^{−1}(z)]. This completes the proof of the theorem. □

Theorem 6 has a remarkable consequence concerning the nature of the generating function F (z) for the free subgroup numbers of a finitely generated virtually free group Γ. In the proof of the theorem, we used that F (z) satisfies an algebraic differential equation of the form (5.1). The technical term which is commonly used for this situation is that the generating function F (z) is differentially algebraic. On the other hand, it may be safely conjectured that it does not belong to the more restrictive class of D-finite power series, that is, it does not satisfy a linear differential equation with polynomial coefficients. Equivalently, we conjecture that the sequence of free subgroup numbers of Γ is not P-recursive, that is, it does not satisfy a linear recurrence with polynomial coefficients. (The reader is referred to [13, Ch. 6] for information on D-finite series and P-recursive sequences.) Theorem 6 implies that the situation changes drastically when one reduces the free subgroup numbers modulo a given prime power. (The reader should recall that algebraic power series are automatically D-finite.)

Corollary 7. Under the assumptions of Theorem 6, we have

F (z) = A_{p,α}(z) modulo p^{α},

where A_{p,α}(z) is an algebraic power series, that is, it satisfies an equation of the form Pol(A_{p,α}(z), z) = 0, where Pol(y, z) is a polynomial in y and z.

Proof. Theorem 6 says that F (z) can be expressed as a polynomial in Φ(z), z, z^{−1}, and Y^{−1}(z). The series Φ(z) is algebraic by (4.1), as are z, z^{−1}, and Y^{−1}(z). The assertion of the corollary then follows from the closure properties of the class of algebraic series. □

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 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 8 and 12 below. We accompany these results by concrete examples, given in Example 9 and 10, which illustrate Corollary 8, respectively Example 14, illustrating Corollary 12. Moreover, we explain in Remarks 11 and 15 how the earlier results in [2, 4] fit into the more general picture that we present here.

Corollary 8. Let r be a non-negative integer. With the assumptions of Theorem 6, if μ(Γ) ≡ 0, 1 (mod p), then

f_{λ}(Γ) ≡ R_{Γ,p,r}(λ)(\frac{μ(Γ)λ}{p−1} ; \frac{λ−r}{p−1}) (mod p^{α}), for λ ≡ r (mod p − 1),  (6.1)

where, R_{Γ,p,r}(λ) is a rational function in λ. Furthermore, the right-hand side of the above congruence is always integral.

Proof. By Theorem 6, the generating function ∑_{λ=1}^{∞} f_{λ}(Γ) z^{λ} equals

∑_{i=0}^{μ(Γ)−1} b_{i,α}(z)Φ^{i}(z) modulo p^{α},  (6.2)

and the coefficients b_{i,α}(z) are elements of ℤ[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 b_{i,α}(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

⟨z^{n}⟩ Φ^{m}(z) = (−1)^{\frac{(μ(Γ)−1)n+m}{p−1}} \frac{m}{n}(\frac{μ(Γ)n}{p−1} ; \frac{n−m}{p−1}).  (6.3)

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). The integrality claim follows from the fact that the expression on the right-hand side of (6.1) is an integral linear combination of terms (6.3), all of which are integral. □

Example 9. We let p = 3 and Γ_{1} a finitely generated virtually free group with order graph given by the normalised tree in Figure 5. 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 + φ(\frac{6}{3}) ζ_{3}(Γ_{1}) + φ(\frac{6}{6}) ζ_{6}(Γ_{1}) = 1 + 0 + (−1) = 0

[figure: 2; 2; 1; 1; 3; 3; 6; 6; 6]

Figure 5. The order graph of the group Γ_{1} in Example 9

and

μ(Γ_{1}) = 1+φ(\frac{6}{1}) ζ_{1}(Γ_{1})+φ(\frac{6}{2}) ζ_{2}(Γ_{1})+φ(\frac{6}{3}) ζ_{3}(Γ_{1})+φ(\frac{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.

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

f_{2L+1}(Γ_{1}) ≡ (−1)^{L+1} \frac{P_{1}(L)}{(12L + 1)_{6}} \binom{12L + 6}{L} (mod 81), for L ≥ 1,

where

P_{1}(L) = 18(473007L^{5} + 969687L^{4} + 765456L^{3} + 308998L^{2} + 72732L + 9080),

and

f_{2L}(Γ_{1}) ≡ (−1)^{L+1} \frac{P_{2}(L)}{(12L − 6) (11L − 4)_{4}} \binom{12L − 6}{L − 1} (mod 81), for L ≥ 1,

where

P_{2}(L) = 324(48L^{6} − 528L^{5} + 6079L^{2} + 9091L^{4} − 10582L^{3} − 1874L + 286),

with the Pochhammer symbol (α)_{m} being defined by (α)_{m} := α(α + 1) ⋯ (α + m − 1) for m ≥ 1, and (α)_{0} := 1.

Example 10. We let p = 2 and Γ_{2} a finitely generated virtually free group with order graph given by the normalised tree in Figure 6. In this situation, we have m_{Γ_{2}} = 30,

[figure: 3; 5; 15; 3; 3; 6; 30; 30; 10; 6; 6]

Figure 6. The order graph of the group Γ_{2} in Example 10

ζ_{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

μ_{2}(Γ_{2}) = 1 + φ(\frac{30}{2}) ζ_{2}(Γ_{2}) + φ(\frac{30}{6}) ζ_{6}(Γ_{2}) + φ(\frac{30}{10}) ζ_{10}(Γ_{2}) + φ(\frac{30}{30}) ζ_{30}(Γ_{2})
= 1 + 0 + 0 + (−1) = 0

and

μ(Γ_{2}) = 1 + φ(\frac{30}{1}) ζ_{1}(Γ_{2}) + φ(\frac{30}{2}) ζ_{2}(Γ_{2}) + φ(\frac{30}{3}) ζ_{3}(Γ_{2}) + φ(\frac{30}{5}) ζ_{5}(Γ_{2}) + φ(\frac{30}{6}) ζ_{6}(Γ_{2})
+ φ(\frac{30}{10}) ζ_{10}(Γ_{2}) + φ(\frac{30}{15}) ζ_{15}(Γ_{2}) + φ(\frac{30}{30}) ζ_{30}(Γ_{2})
= 1 + 0 + 0 + 12 + 2 + 0 + 0 + 5 + (−1) = 19.

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}) ≡ \frac{Q(λ)}{3λ(6λ + 1)(9λ + 1)(9λ + 2)(18λ + 5)(19λ − 18)_{19}} \binom{19λ}{λ − 1} (mod 16),

for λ ≥ 2, 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 11. More generally, if p = 2, μ_{2}(Γ) = 0 and μ(Γ) ≥ 2, then we are always in the case covered by Corollary 8, 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 ℌ(q) ≅ C_{2} ∗ C_{q} 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 8, 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 8 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 μ(Γ) ≢ 0, 1 (mod p).

Corollary 12. Let r be an integer with 0 ≤ r ≤ p − 2. With the assumptions of Theorem 6, if μ(Γ) ≢ 0, 1 (mod p), then

f_{λ}(Γ) ≡ (\frac{μ(Γ)}{p − 1} + 1)^{λ/(p−1)} R_{Γ,p,r}^{(1)}(λ)

+ ∑_{k=0}^{⌊λ/(p−1)⌋} (\frac{μ(Γ)}{p − 1} + 1)^{k} R_{Γ,p,r}^{(2)}(λ, k)\binom{\frac{μ(Γ)λ}{p−1} − μ(Γ)k}{\frac{λ−r}{p−1} − k} (mod p^{α}),

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

where R_{Γ,p,r}^{(1)}(λ) and R_{Γ,p,r}^{(2)}(λ, k) are rational functions in their respective arguments. Moreover, R_{Γ,p,r}^{(2)}(λ, k) depends only on \frac{λ}{p−1} − k, and the right-hand side of the above congruence is always integral.

Proof. We begin as in the proof of Corollary 12 by quoting Theorem 6, which tells us that the generating function ∑_{λ=1}^{∞} f_{λ} z^{λ} is given by (6.2) modulo p^{α}. However, here we have Y (z) = z^{p−1} − (N + 1)^{−1}, with N = μ(Γ)/(p − 1).

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

\frac{1}{Y^{q}(z)} = \frac{1}{(z^{p−1} − (N + 1)^{−1})^{q}} = (−1)^{q}(N + 1)^{q} ∑_{k=0}^{∞} \binom{q + k − 1}{k}(N + 1)^{k}z^{(p−1)k}.

Subsequent coefficient extraction using (6.3) leads to the result in (6.4), where the term containing R_{Γ,p,r}^{(1)}(λ) comes from the summand b_{0,α}(z) in (6.2), while the term containing R_{Γ,p,r}^{(2)}(λ, k) is generated by the remaining summands in (6.2). The integrality claim follows from the fact that the expression on the right-hand side of (6.4) is an integral linear combination of terms, all of which are integral. □

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 13. Let r be an integer with 0 ≤ r ≤ p − 2, and let S_{r}(λ) denote the sum on the right-hand side of (6.4). Then we have

∑_{j=0}^{d+1}(−1)^{j}\binom{d + 1}{j}M^{d+1−j}S_{r}(λ + (p − 1)j) = g_{r}(λ), for λ ≡ r (mod p − 1), (6.5)

where d is the numerator degree of R_{Γ,p,r}^{(2)}(λ, k) in λ, M = \frac{μ(Γ)}{p−1} + 1, and g_{r}(λ) is a hypergeometric term, that is, g_{r}(λ + 1)/g_{r}(λ) equals a rational function in λ.

Proof. We fix r, and we write λ = (p − 1)L + r. Using this notation, the sum S_{r}(λ) has the form

S_{r}(λ) = S_{r}((p − 1)L + r) = ∑_{k=0}^{L} M^{k}A(L − k, L) f(L − k),  (6.6)

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 R_{Γ,p,r}^{(2)}(λ, 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}S_{r}((p − 1)L + r)

= ∑_{j=0}^{d+1}(−1)^{d+1−j}\binom{d + 1}{j}M^{d+1−j} ∑_{k=0}^{L+j} M^{k}A(L + j − k, L + j) f(L + j − k)

= ∑_{j=0}^{d+1}(−1)^{d+1−j}\binom{d + 1}{j}M^{d+1−j} ∑_{k=−j}^{L} M^{k+j}A(L − k, L + j) f(L − k)

= ∑_{k=0}^{L} M^{d+k+1}f(L − k) ∑_{j=0}^{d+1}(−1)^{d+1−j}\binom{d + 1}{j}A(L − k, L + j) + G_{r}(L),

2 7 1

Figure 7. The order graph of the group ℌ(7) in Example 14

where G_{r}(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 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}S_{r}((p−1)L+r) = ∑_{k=0}^{L} M^{d+k+1}f(L−k) Δ_{t}^{d+1}A(L−k, t)|_{t=L}+G_{r}(L). (6.7)

We assumed that A(x, y) is a polynomial of degree d in y, hence Δ_{t}^{d+1} kills A(L − k, t). Consequently, on the right-hand side in (6.7) there remains only G_{r}(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 14. We consider the Hecke group ℌ(7) = C_{2} ∗ C_{7}, whose order graph is shown in Figure 7, and the prime p = 7. We have m_{ℌ(7)} = 14, ζ_{1}(ℌ(7)) = 1, ζ_{2}(ℌ(7)) = 0, ζ_{7}(ℌ(7)) = 0, and ζ_{14}(ℌ(7)) = −1, and thus μ_{7}(ℌ(7)) = 0 and μ(ℌ(7)) = 6.

The functional equation for F (z) = F_{ℌ(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^{5}F^{(4)}(z) + 41160z^{4}F (z)^{2}F^{(3)}(z)

+ 1959216z^{4}F (z)F^{(3)}(z) + 24989608z^{4}F^{(3)}(z) + 384160z^{5}(F′′(z))^{2} + 3920z^{3}F^{3}(z)F′′(z)

+ 205800z^{3}F^{2}(z)F′′(z) + 3874528z^{3}F (z)F′′(z) + 25988424z^{3}F′′(z) + 41160z^{4}(F′(z))^{3}

+ 8820z^{3}F^{2}(z)(F′(z))^{2} + 288120z^{3}F (z)(F′(z))^{2} + 2512132z^{3}(F′(z))^{2}

+ 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

\frac{\begin{matrix}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) \end{matrix}}{(1 − 2z^{6})^{3}}

+ (1 + \frac{\begin{matrix}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}) \end{matrix}}{(1 − 2z^{6})^{3}} ) Φ(z)

+ \frac{\begin{matrix}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) \end{matrix}}{(1 − 2z^{6})^{3}}Φ^{2}(z)

+ \frac{\begin{matrix}7 (42z^{16} + 29z^{15} + 22z^{14} + 7z^{13} + 7z^{12} + 7z^{10} + 27z^{9} \\ +48z^{8} + 35z^{7} + 21z^{6} + 35z^{4} + 16z^{3} + 2z^{2} + 42z) \end{matrix}}{(1 − 2z^{6})^{3}} Φ^{3}(z)

+ \frac{\begin{matrix}7 (42z^{17} + 14z^{15} + 41z^{14} + 19z^{13} + 7z^{12} + 42z^{11} \\ +35z^{9} + z^{8} + 23z^{7} + 21z^{6} + 42z^{5} + 28z^{3} + 26z^{2} + 31z) \end{matrix}}{(1 − 2z^{6})^{3}}Φ^{4}(z)

+ \frac{\begin{matrix}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}) \end{matrix}}{(1 − 2z^{6})^{3}}Φ^{5}(z)

modulo 343. (6.8)

Finally, we have to extract coefficients. We content ourselves with displaying here the results for f_{λ}(ℌ(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

f_{6λ}(ℌ(7)) ≡ 7 · 2^{λ−2}(49λ^{2} − 7λ + 4)

+ 7 ∑_{k=0}^{∞}(−1)^{k+λ}2^{k−4} \frac{5 (5k − 5λ + 1) (k − λ)P (λ)}{3 (6λ − 6k − 5)_{5}} \binom{6λ − 6k}{λ − k} (mod 343), (6.9)

where

P (λ) = 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 13 (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(λ) = 7 (−1)^{λ+1} T (λ)\frac{(6λ)!}{λ! (5λ + 13)!},

where

T (λ) = 7578375074183λ^{12} + 110764942152696λ^{11} + 719438896272607λ^{10}

+ 2739679993093800λ^{9} + 6794561274739329λ^{8} + 11525824255968648λ^{7}
+ 13662933657289381λ^{6} + 11354903297697240λ^{5} + 6532000464773588λ^{4}

+ 2520106018198656λ^{3} + 613697061412512λ^{2} + 83672481893760λ + 4738762828800.

Remark 15. The discussion of free subgroup numbers of lifts Γ_{m}(3) of the classical modular group ℌ(3) ≅ PSL_{2}(ℤ) in [4, Sec. 16] taken modulo powers of 3 fits into the framework of Corollary 12. 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 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].

Acknowledgement

The authors are indebted to the anonymous referees for a careful reading of the manuscript, and for helpful suggestions concerning the presentation of the material.

References

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

[2] M. Kauers, C. Krattenthaler, and T. W. Müller, A method for determining the mod-2^{k} behaviour of recursive sequences, with applications to subgroup counting, Electron. J. Combin. 18 (2012), Art. #P37, 83 pp.

[3] C. Krattenthaler and T. W. Müller, A Riccati differential equation and free subgroup numbers for lifts of PSL_{2}(ℤ) modulo prime powers, J. Combin. Theory Ser. A 120 (2013), 2039–2063.

[4] C. Krattenthaler and T. W. Müller, A method for determining the mod-3^{k} behaviour of recursive sequences, preprint, 83 pages; arχiv:1308.2856.

[5] C. Krattenthaler and T. W. Müller, A method for determining the mod-p^{k} behaviour of recursive sequences, preprint, 35 pages; arχiv:1508.02580.

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

[7] C. Krattenthaler and T. W. Müller, Normalising graphs of groups, Monatsh. Math. (to appear).

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

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

[10] T. W. Müller and J.-C. Schlage-Puchta, Modular arithmetic of free subgroups, Forum Math. 17 (2005), 375–405.

[11] M. Petkovšek, H. Wilf, and D. Zeilberger, A=B, A. K. Peters, Wellesley, 1996.

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

[13] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

†Fakultät für Mathematik, Universitä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.