PERIODICITY OF FREE SUBGROUP NUMBERS MODULO PRIME POWERS

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

Abstract. We characterise when the sequence of free subgroup numbers of a finitely generated virtually free group is ultimately periodic modulo a given prime power.

1. Introduction

For a finitely generated virtually free group Γ, denote by m_{Γ} the least common multiple of the orders of the finite subgroups in Γ and, for a positive integer λ, let f_{λ}(Γ) be the number of free subgroups of index λm_{Γ} in Γ. In [4], the authors show, among other things, that the number f_{λ}(PSL_{2}(ℤ)) of free subgroups of index 6λ in the inhomogeneous modular group PSL_{2}(ℤ), considered as a sequence indexed by λ, is ultimately periodic modulo any fixed prime power p^{α}, if p is a prime number with p ≥ 5. More precise results on the length of the period, and an explicit formula for the linear recurrence satisfied by these numbers modulo p^{α} are also provided in [4]. As is well known, ultimate periodicity of the sequence (f_{λ}(Γ))_{λ≥1} is equivalent to rationality of the corresponding generating function F_{Γ}(z) = ∑_{λ≥0} f_{λ+1}(Γ)z^{λ}.

The purpose of the present paper is to demonstrate that the periodicity phenomenon discovered in [4] holds in a much wider context, namely that of finitely generated virtually free groups. Indeed, our main result (Theorem 1) provides an explicit characterisation of all pairs (Γ, p^{α}), where Γ is a finitely generated virtually free group and p^{α} is a proper prime power, for which the sequence of free subgroup numbers of Γ is ultimately periodic modulo p^{α}. Roughly speaking, for “almost all” pairs (Γ, p) the sequence (f_{λ}(Γ))_{λ≥0} is ultimately periodic modulo p^{α} for all α ≥ 1, the only exception occurring when p | m_{Γ} and μ_{p}(Γ) = 0, where μ_{p}(Γ) is a certain invariant defined in (2.10) and discussed in the paragraph following that formula.

In order to further place our results into context, we point out that, for primes p dividing the constant m_{Γ}, an elaborate theory is presented in [9] for the behaviour of the arithmetic function f_{λ}(Γ) modulo p. Recently, this theory has been supplemented by congruences modulo (essentially arbitrary) 2-powers and 3-powers for the number of free subgroups of finite index in lifts of the classical modular group; that is, amalgamated products of the form

2010 Mathematics Subject Classification. Primary 05A15; Secondary 05E99 11A07 20E06 20E07.

Key words and phrases. virtually free groups, free subgroup numbers, modular group, periodic sequences.

†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.

Γ_{ℓ} = C_{2ℓ} ∗_{C_{ℓ}} C_{3ℓ}, ℓ ≥ 1;

cf. Theorems 19 and 20 in [3, Sec. 8], and Section 16 in [5], in particular, [5, Thms. 49– 52]. These results demonstrate a highly non-trivial behaviour of the sequences (f_{λ}(Γ_{ℓ}))_{λ≥1} modulo powers of 2 if ℓ is odd (in which case μ_{2}(Γ_{ℓ}) = 0), and modulo powers of 3 for 3 ∤ ℓ (in which case μ_{3}(Γ_{ℓ}) = 0). For instance, for the sequence (f_{λ} = f_{λ}(Γ_{1}))_{λ≥1} of free subgroup numbers of the group PSL_{2}(ℤ), one finds that:

(1) f_{λ} ≡ −1 (mod 3) if, and only if, the 3-adic expansion of λ is an element of {0, 2}^{∗}1;

(2) f_{λ} ≡ 1 (mod 3) if, and only if, the 3-adic expansion of λ is an element of

{0, 2}^{∗}100^{∗} ∪ {0, 2}^{∗}122^{∗};

(3) for all other λ, we have f_{λ} ≡ 0 (mod 3);

cf. [5, Cor. 53]. Here, for a set Ω, we denote by Ω^{∗} the free monoid generated by Ω. All this is in sharp contrast to “most” of the cases in the classification result in Theorem 1, which exhibit “simple” (ultimate) periodicity.

The proof of Theorem 1 has two main steps. The first consists in showing that, if p is a prime number not dividing m_{Γ}, then the sequence (f_{λ}(Γ))_{λ≥1} is ultimately periodic modulo p^{α} for every integer α ≥ 1; this is the contents of Theorem 2. Its proof is based on a folklore fact concerning linear recurrence relations with constant coefficients stated in Section 4, on a bound for the p-divisibility of the function g_{λ}(Γ) provided by Lemma 6 in Section 5, and the (well-known) classification of virtually infinite-cyclic groups recalled in Section 6. The proof of Theorem 2 appears in Section 7. The second step concerns the case where p | m_{Γ}, and is largely taken care of by Theorem 3. The proof of the latter theorem in Section 8 is by an inductive argument, which is based on an earlier generating function result in [9]. The proof of Theorem 1 itself is given in Section 9. Precise formulations of our main results are found in Section 3, while the next section collects together definitions as well as some background material on virtually free groups.

2. Some preliminaries on virtually free groups

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

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

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

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

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

Equation (2.2) reflects the fact that, in our situation, the Euler characteristic in the sense of Wall coincides with the equivariant Euler characteristic χ_{T} (Γ) of Γ relative to the tree T canonically associated with Γ in the sense of Bass–Serre theory; cf. [1, Chap. IX, Prop. 7.3] or [11, Prop. 14].

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

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

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

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

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

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

It can be shown that the type τ(Γ) is in fact an invariant of the group Γ, i.e., independent of the particular decomposition of Γ in terms of a graph of groups (Γ(−), X), and that two finitely generated virtually free groups Γ_{1} and Γ_{2} contain the same number of free subgroups of index n for each positive integer n if, and only if, τ(Γ_{1}) = τ(Γ_{2}); cf. [8, 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. [7, Prop. 1] or [8, Lemma 2]. We observe that, as a consequence of (2.2), the Euler characteristic of Γ can be expressed in terms of the type τ(Γ) via

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

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

The proof of Theorem 2, as given in Section 7, is based on the analysis of a second arithmetic function associated with the group Γ. Define a torsion-free Γ-action on a set Ω to be a Γ-action on Ω which is free when restricted to finite subgroups, and let

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

(2.4)

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

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

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

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

for g_{λ}(Γ), where O(X) is any orientation of X; cf. [8, Prop. 3]. Introducing the generating functions

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

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

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

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). We note that, in view of (2.1), the quantity μ(Γ) is connected with the Euler characteristic of Γ via

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

which shows in particular that μ(Γ) is well-defined. Combining Equations (2.3) and (2.8), we see that the free rank μ(Γ) can be expressed in terms of the type of Γ via

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

Given a finitely generated virtually free group Γ and a prime number p, we introduce, in analogy with formula (2.9), the p-rank μ_{p}(Γ) of Γ via the equation

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

Clearly, μ_{p}(Γ) ≥ 0, with equality occurring in this inequality if, and only if, Γ is the fundamental group of a tree of groups, p | m_{Γ}, and ζ_{κ}(Γ) = 0 for p | κ | m_{Γ} and κ < m_{Γ}. Similarly, we have μ_{p}(Γ) = 1 if, and only if, (i) ζ_{κ}(Γ) = 0 for all κ with p | κ | m_{Γ}, or (ii) Γ is the fundamental group of a tree of groups, m_{Γ} is even, p | m_{Γ}/2, ζ_{m_{Γ}/2}(Γ) = 1, and ζ_{κ}(Γ) = 0 for p | κ | m_{Γ} and κ < m_{Γ}/2. To give some concrete examples, if p is an odd prime number, then the groups

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

Γ_{p,α} = C_{2} ∗ C_{2p} ∗ \underbrace{C_{p} ∗ ⋯ ∗ C_{p}}_{α copies}, α ≥ 0

satisfy μ_{p}(Γ_{p,α}) = 1, while the groups

Γ_{2,α} = C_{4} ∗ C_{4} ∗ \underbrace{C_{2} ∗ ⋯ C_{2}}_{α copies}, α ≥ 0

satisfy μ_{2}(Γ_{2,α}) = 1.

3. Periodicity results for f_{λ}(Γ)

Here and in the sequel, given power 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; in particular, the phrase “F_{Γ}(z) is rational modulo p^{α}” means that F_{Γ}(z) equals a certain rational function modulo p^{α} in the sense of the above definition. (It is well known that rationality of the generating function F_{Γ}(z) is equivalent to ultimate periodicity of its sequence of coefficients (f_{λ}(Γ))_{λ≥1}.) The main result of this section, which completely characterises rationality of the generating function F_{Γ}(z) modulo prime powers, is as follows.

Theorem 1. Let Γ be a finitely generated virtually free group, let p be a prime number, and let F_{Γ}(z) denote the generating function ∑_{λ≥0} f_{λ+1}(Γ)z^{λ} for the free subgroup numbers of Γ. Then the following assertions are equivalent:

(I) the series F_{Γ}(z) is rational modulo p^{α} for each positive integer α;

(II) the series F_{Γ}(z) is rational modulo p;

(III) The pair (Γ, p) satisfies one of the following mutually exclusive conditions: (III)_{1} p ∤ m_{Γ}; (III)_{2} p | m_{Γ} and μ_{p}(Γ) > 0; (III)_{3} Γ is finite; (III)_{4} Γ is virtually infinite-cyclic and p = 2.

The proof of Theorem 1 is broken up into two main steps, each of which is a meaningful result in its own right. Case (III)_{1} is taken care of by the following result.

Theorem 2. Let Γ be a finitely generated virtually free group, let p be a prime number not dividing m_{Γ}, and let α be a positive integer. Then the sequence (f_{λ}(Γ))_{λ≥1} is ultimately periodic modulo p^{α}. Its (minimal) period length is less than

p^{α(p(\frac{α}{μ(Γ)−1} +⌊log_{p} α⌋+2)−2)}.  (3.1)

Case (III)_{2}, where p | m_{Γ} and μ_{p}(Γ) > 0, is dealt with in our last result.

Theorem 3. Let Γ be a finitely generated virtually free group, let p be a prime number such that p | m_{Γ} and μ_{p}(Γ) > 0, and let α be a positive integer. Then the generating function F_{Γ}(z) for the free subgroup numbers of Γ is rational modulo p^{α}. More precisely, if μ_{p}(Γ) = 1, then F_{Γ}(z) is a proper rational function modulo p^{α}, whose denominator may be chosen as a power of 1 − z or 1 + z, respectively, depending on whether the expression

(μ(Γ) − μ_{p}(Γ))/(p − 1)

is even or odd. If μ_{p}(Γ) ≥ 2, then F_{Γ}(z) is a polynomial modulo p^{α}.

Other ingredients in the proof of Theorem 1 (given in Section 9) are Corollary 10, which describes the function f_{λ}(Γ) in the case where Γ is virtually infinite-cyclic, as well as [9, Prop. 2] and [9, Theorem 2].

The proof of Theorem 2, as given in Section 7, is based on the analysis of the rationalvalued arithmetic function g_{λ} defined in (2.4). A careful analysis of the expression (2.6) for g_{λ}(Γ), combined with Equation (2.5) connecting the f_{λ}(Γ)’s and the g_{λ}(Γ)’s, will show that the numbers f_{λ}(Γ) satisfy a linear recurrence of finite order with constant coefficients modulo any fixed prime power p^{α} if p does not divide m_{Γ}. By a standard result on linear recurring sequences (see Lemma 5 in Section 4), Theorem 2 then follows immediately.

The proof of Theorem 3 is given in Section 8. It is based on a functional equation modulo p (with p | m_{Γ}) satisfied by the generating function F_{Γ}(z) for the free subgroup numbers f_{λ}(Γ) established in [9].

We conclude this section with some remarks.

Remarks 4. (1) It is shown in [9] that, if Γ is a finitely generated virtually free group with μ_{p}(Γ) = 0 for a given prime p, then the function f_{λ}(Γ) satisfies the congruence

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

cf. [9, Eqn. (35)]. In general, it remains an open problem how the free subgroup numbers of a finitely generated virtually free group Γ with μ_{p}(Γ) = 0 behave modulo higher ppowers. The only results known in this direction concern (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}(ℤ) with p = 3; see Corollary 34 and Theorem 35 in [3], and [5, Sec. 16].

(2) By a cyclic cover, we mean the fundamental group Γ of a finite graph (Γ(−), X) of finite cyclic groups. To fix ideas, we shall assume that the canonical embeddings associated with (Γ(−), X) are induced by the identity maps of the corresponding vertex stabilisers. Let Γ = π_{1}(Γ(−), X) be a cyclic cover, and let ℓ be a positive integer. Then we define the ℓ-th lift Γ_{ℓ} of Γ as the cyclic cover resulting from (Γ(−), X) by multiplying the order of each (vertex or edge) stabiliser by a factor ℓ. The last assertion in Theorem 3 implies that F_{Γ_{ℓ}}(z) is a polynomial modulo all proper p-powers for all lifts Γ_{ℓ} of cyclic covers Γ with μ(Γ_{ℓ}) = μ(Γ) ≥ 2, and p | ℓ, even if p ∤ m_{Γ}.

(3) In order to illustrate Theorem 3, let us consider the case where Γ = ℌ(6) ≅ C_{2}∗C_{6} and p = 3. Indeed, in this example, we have 3 | m_{ℌ(6)} = 6 and μ_{3}(ℌ(6)) = 1. If one applies the algorithm which is implicit in the proof of Theorem 3 given in Section 8, then, modulo 3^{9} = 19683, one obtains

F_{ℌ(6)}(z) = \frac{1}{(1 + z)^{10}} (19680z^{9} + 585z^{8} + 1926z^{7} + 6165z^{6} + 7326z^{5}

+ 1584z^{4} + 1566z^{3} + 17433z^{2} + 1845z + 15) modulo 3^{9}.

From this expression, it is not difficult to deduce that the sequence (f_{λ}(ℌ(6)))_{λ≥1}, when taken modulo 3^{9}, is in fact purely periodic with minimal period length 2 · 3^{11} = 354294. Namely, we have

\frac{1}{(1 + z)^{10}} = ∑_{n≥0}(−1)^{n}\binom{n + 9}{9}z^{n}.  (3.2)

Furthermore,

∏_{ℓ=1}^{9}(n + 3^{11} + ℓ) − ∏_{ℓ=1}^{9}(n + ℓ) ≡ 3^{11} (∏_{ℓ=1}^{9}(n + ℓ)) ∑_{ℓ=1}^{9} \frac{1}{n + ℓ} (mod 3^{13})
≡ 0 (mod 3^{13}),

since each product ∏_{ℓ=1}^{9}(n+ℓ) contains at least three factors divisible by 3, at most one of which is divided out by a fraction \frac{1}{n+ℓ}. Since 9! = 3^{4} · 4480 with 4480 not divisible by 3, the above calculation implies

\binom{n + 3^{11} + 9}{9} ≡ \binom{n + 9}{9} (mod 3^{9}),

and it is easy to see that there is no period smaller than 3^{11} of the binomial coefficient \binom{n+9}{9}. Using this observation in (3.2), we conclude that the coefficients in the series 1/(1 + z)^{10} are periodic with minimal period length 2 · 3^{11}, implying our claim.

(4) For a finitely generated virtually free group Γ, denote by Γ̂ the isomorphism class of Γ. Given a prime number p, define a density 𝔇_{p} of isomorphism classes of groups Γ with μ_{p}(Γ) = 0 in all isomorphism classes by

𝔇_{p} := lim_{M→∞} \frac{|\{Γ̂ : m_{Γ} ≤ M, μ(Γ) ≤ M, μ_{p}(Γ) = 0\}|}{|\{Γ̂ : m_{Γ} ≤ M, μ(Γ) ≤ M\}|}.

Note that this definition makes sense in view of [8, Prop. 4] and Equation (2.8). We conjecture that 𝔇_{p} = 0 for all prime numbers p.

4. Periodicity of sequences over finite rings

In this section we review a standard result on linear recurring sequences (usually only formulated over finite fields), which will be used in a crucial manner in the proof of Theorem 2 in Section 7.

Let Λ be a finite commutative ring with identity, and let S = (s_{n})_{n≥0} be a sequence of elements of Λ. Suppose that there exist a positive integer d and elements α_{0}, α_{1}, …, α_{d−1} ∈ Λ, such that S satisfies the relation

s_{n+d} = α_{d−1}s_{n+d−1} + α_{d−2}s_{n+d−2} + ⋯ + α_{0}s_{n}, n ≥ 0.  (4.1)

Then S is termed a (homogeneous) linear recurring sequence over Λ of order d, a relation of the form (4.1) itself is called a (homogeneous) linear recurrence relation (or difference relation) of order d.

The sequence S = (s_{n})_{n≥0} is termed ultimately periodic, if there exist integers ω > 0 and n_{0} ≥ 0, such that s_{n+ω} = s_{n} holds for all n ≥ n_{0}. The integer ω is then called a period of S. The smallest number among all the possible periods ω of an ultimately periodic sequence S is called the least period ω_{0} = ω_{0}(S) of S. If S = (s_{n})_{n≥0} is ultimately periodic with least period ω_{0}, then the least non-negative integer n_{0} such that s_{n+ω_{0}} = s_{n} for all n ≥ n_{0} is called the preperiod of S. An ultimately periodic sequence S = (s_{n})_{n≥0} with least period ω_{0}(S) is termed purely periodic, if s_{n+ω_{0}(S)} = s_{n} for all n ≥ 0. It is easy to see that a sequence S = (s_{n})_{n≥0} is purely periodic, if, and only if, there exists an integer ω > 0 such that s_{n+ω} = s_{n} for all n ≥ 0. Also, every period of an ultimately periodic sequence is divisible by the least period.

Linear recurring sequences over finite rings are always (ultimately) periodic. The precise fact that we are going to use in the proof of Theorem 2 is the following.

Lemma 5. Let S = (s_{n})_{n≥0} be a homogeneous linear recurring sequence of order d ≥ 1 over a finite commutative ring Λ with identity. Then S is ultimately periodic with least period ω_{0}(S) < |Λ|^{d}.

The proof of Lemma 5 is virtually identical with that in the case of finite fields; see [6, Theorem 8.7].

5. A bound on the p-divisibility of g_{λ}(Γ)

We use the standard notation for the p-adic valuation of rational numbers. That is, if α = r/s, then v_{p}(α) = v_{p}(r) − v_{p}(s), where v_{p}(r) is the exponent of the highest p-power dividing r, with v_{p}(s) being defined in an analogous way.

Lemma 6. Let Γ be a finitely generated virtually free group of free rank μ(Γ) ≥ 2, and let p be a prime number not dividing m_{Γ}. Then we have

v_{p}(g_{λ}(Γ)) ≥ (μ(Γ) − 1) · v_{p}(λ!), λ ≥ 0.  (5.1)

In particular, the function v_{p}(g_{λ}(Γ)) is non-negative, and unbounded as λ → ∞.

Proof. Let (Γ(−), X) be a Stallings decomposition of Γ, and let O(X) be any orientation of the graph X. In proving (5.1), we may ignore the factor

\frac{∏_{e∈O(X)} |Γ(e)|^{λm_{Γ}/|Γ(e)|}}{∏_{v∈V (X)} |Γ(v)|^{λm_{Γ}/|Γ(v)|}}  (5.2)

in the expression (2.6) for g_{λ}(Γ), since p ∤ m_{Γ} by assumption. We shall in fact show that the remaining expression in (2.6) is an integer, and that (λ!)^{−m_{Γ}·χ(Γ)} divides that integer. In symbols:

(λ!)^{−m_{Γ}·χ(Γ)} divides \frac{∏_{e∈O(X)}(λm_{Γ}/|Γ(e)|)!}{∏_{v∈V (X)}(λm_{Γ}/|Γ(v)|)!}.  (5.3)

Since, by (2.8), we have μ(Γ) − 1 = −m_{Γ} · χ(Γ), in combination with the above remark this would establish (5.1).

For the proof of (5.3), we regard the graph X as undirected, in the sense that each pair {e, ē} is considered as one (undirected) edge, and we consider the edge and vertex labels as abstract labels satisfying the condition that an edge label divides the vertex labels of the vertices incident with the edge. By abuse of notation, we still write |Γ(e)| for the label of the edge e and |Γ(v)| for the label of the vertex v.

We shall build up the graph X by adding edges and vertices one by one, and at each step record the contributions of the added edges and vertices to (5.3).

We distinguish two cases, depending on whether X contains a cycle or not. Suppose first that X contains a cycle

v_{1}, e_{1}, v_{2}, e_{2}, …, v_{m}, e_{m}, v_{1},

where v_{i} and v_{i+1} are the vertices incident with the (undirected) edge e_{i}, i = 1, 2, …, m (where v_{m+1} is identified with v_{1}), and v_{1}, v_{2}, …, v_{m} are pairwise distinct. Since, by the definition of a graph of groups, we have |Γ(e_{i})| divides |Γ(v_{i})|, i = 1, 2, …, m, it follows that

(m_{Γ} (\frac{1}{|Γ(e_{i})|} − \frac{1}{|Γ(v_{i})|}) λ)! divides \frac{(λm_{Γ}/|Γ(e_{i})|)!}{(λm_{Γ}/|Γ(v_{i})|)!}, i = 1, 2, …, m,  (5.4)

by integrality of binomial coefficients.

Let G be the graph consisting of this cycle. If G is already all of X, then our construction stops here. Otherwise, there must be an edge e that is not yet included in G which emanates from some vertex of G. There are two possible cases: either the other vertex incident with e, say v, is not yet in G, in which case we have

(m_{Γ} (\frac{1}{|Γ(e)|} − \frac{1}{|Γ(v)|}) λ)! divides \frac{(λm_{Γ}/|Γ(e)|)!}{(λm_{Γ}/|Γ(v)|)!},  (5.5)

or v is already in G, in which case we have (trivially)

(m_{Γ} \frac{1}{|Γ(e)|}λ)! divides (λm_{Γ}/|Γ(e)|)!.  (5.6)

We add e and v (in the case it is not yet in G) to G. If G is already all of X, then we stop. Otherwise, we iterate the above step of adding an edge and possibly a vertex to G until we have obtained all of X.

Now we “multiply” all divisor relations (5.4)–(5.6) together, to obtain

( ∏_{e∈S_{1}} (m_{Γ} \frac{1}{|Γ(e)|}λ)! ∏_{(e,v)∈S_{2}} (m_{Γ} (\frac{1}{|Γ(e)|} − \frac{1}{|Γ(v)|}) λ)!) divides \frac{∏_{e∈O(X)}(λm_{Γ}/|Γ(e)|)!}{∏_{v∈V (X)}(λm_{Γ}/|Γ(v)|)!},

(5.7)

where S_{1} is the set of all those edges e of X which, in the above algorithm, were added to G without a vertex being added at the same time, and where S_{2} is the set of all pairs (e, v) of an edge e and a vertex v which are either a pair of the form (e_{i}, v_{i}), i = 1, 2, …, m, or were added together in the same step of the above algorithm. Since (λ!)^{m} divides (mλ)! for any positive integer m, our claim (5.3) follows, and thus the assertion (5.1).

If X does not contain a cycle, then we proceed in a similar fashion. The initial step has to be modified, however. To start with, we claim that there must exist an edge e_{0} such that |Γ(e_{0})| is less than |Γ(v_{0})| and less than |Γ(v_{1})|, where v_{0} and v_{1} are the two vertices incident with e_{0}. Indeed, any edge e in X with |Γ(e)| = |Γ(v)| for a vertex v incident with e could actually be contracted “into the other vertex,” by which we mean that upon contraction of e the vertex v “disappears” and only the other vertex incident with e is retained. This contraction generates a new graph X′ with the same Euler characteristic (cf. (2.2)) and the same associated function g_{λ} (cf. (2.6)). If the graph X would only consist of such edges, then, after contraction of all the edges, only a single labelled vertex would remain, which has positive Euler characteristic (again, in the sense of (2.2)), namely 1/m_{Γ}. By (2.8), it would follow that μ(Γ) = 0, a contradiction.

Let now e_{0} be an edge with |Γ(e_{0})| < |Γ(v_{0})| and |Γ(e_{0})| < |Γ(v_{1})|, where v_{0} and v_{1} are the vertices incident with e_{0}. We let G be the graph consisting of e_{0}, v_{0} and v_{1}. We have

(m_{Γ} (\frac{1}{|Γ(e_{0})|} − \frac{1}{|Γ(v_{0})|} − \frac{1}{|Γ(v_{1})|}) λ)! divides \frac{(λm_{Γ}/|Γ(e_{0})|)!}{(λm_{Γ}/|Γ(v_{0})|)! (λm_{Γ}/|Γ(v_{1})|)!}. (5.8)

The subsequent steps are the same as before: that is, if the graph G obtained so far should not yet be all of X, we choose an edge e not yet in G that is incident with one of the vertices in G, and we add it to G together with the other vertex incident with e. In each of these addition steps (5.5) holds. Finally, again, all divisibility relations (5.8) and (5.5), are “multiplied” together. The result is (5.7) (with an empty set S_{1}), from which the claim (5.3) results in the same way as before. □

1  2 2 2 1 1 1  } r edges

Figure 1. The graph of (C_{2})^{∗r}

Remarks 7. (1) It is easy to see that the estimate (5.1) in Lemma 6 is, in general, best possible for odd primes p. For instance, let Γ = (C_{2})^{∗r}, where r ≥ 2. The corresponding graph of groups is shown in Figure 1 together with its vertex and edge labels. We have

g_{λ}(Γ) = \frac{(2λ)!^{r−1}}{λ!^{r} 2^{rλ}} ,

and, for a prime p ≥ 3 and λ = p^{s} with s ≥ 0, we have

v_{p}(g_{λ}(Γ)) = (2(r − 1) − r)\frac{p^{s} − 1}{p − 1} = (r − 2)v_{p}(λ!) = (μ(Γ) − 1)v_{p}(λ!).

(2) The reader should observe that, in the proof of Lemma 6, we actually proved a slightly stronger result, namely the divisibility relation (5.7), the factor (5.2) not contributing anything to (5.1). However, since there is no elegant way to write down the result (as a matter of fact, there are several inequivalent results that can be derived from different parsings of the graph X), we refrain from exploiting this relation.

6. The classification of virtually infinite-cyclic groups

Virtually infinite-cyclic groups play a certain role in topology as they are precisely the finitely generated groups with two ends. Their structure is well-known; cf. [13, 5.1] or [14, Lemma 4.1].

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

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

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

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

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

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

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

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

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

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

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

□

7. Proof of Theorem 2

Theorem 2 follows from Lemmas 5 and 6. Indeed, if μ(Γ) = 0, then Γ is finite, we have m_{Γ} = |Γ|, and thus f_{1}(Γ) = 1 and f_{λ}(Γ) = 0 for λ ≥ 2, so that f_{λ}(Γ) is ultimately periodic with period and preperiod equal to 1 modulo any prime power. If μ(Γ) = 1, then, by Corollary 10, f_{λ}(Γ) is constant, thus purely periodic with period equal to 1, again modulo any prime power. Now suppose that μ(Γ) ≥ 2. Given a positive integer α, let λ_{0}(α) be chosen according to Lemma 6 such that v_{p}(g_{λ}(Γ)) ≥ α for all λ ≥ λ_{0}(α) and v_{p}(g_{λ_{0}(α)−1}(Γ)) < α. Then consider Equation (2.5) for λ ≥ λ_{0}(α). All summands on the left-hand side corresponding to indices μ ≥ λ_{0}(α) will vanish modulo p^{α}, as does the right-hand side, and we obtain the congruence

f_{λ+λ_{0}(α)}(Γ) ≡ −(g_{1}(Γ)f_{λ+λ_{0}(α)−1}(Γ) + ⋯ + g_{λ_{0}(α)−1}(Γ)f_{λ+1}(Γ)) (mod p^{α}), λ ≥ 0.

(7.1)

This provides a homogeneous linear recurrence with constant coefficients in ℤ/p^{α}ℤ of order λ_{0}(α) − 1 for the sequence (f_{λ}(Γ))_{λ≥1}. Applying Lemma 5 with Λ = ℤ/p^{α}ℤ and S = (f_{λ+1}(Γ))_{λ≥0}, we find that, in this last case, f_{λ}(Γ) is ultimately periodic modulo p^{α} with least period ω_{0} < p^{α(λ_{0}(α)−1)}.

For proving the claimed upper bound on the (minimal) period length, we need to bound λ_{0}(α) from above. We start by using the estimation (5.1), i.e.,

v_{p}(g_{λ}(Γ)) ≥ (μ(Γ) − 1)v_{p}(λ!).  (7.2)

Thus, we need to bound v_{p}(λ!) from below. We have

v_{p}(λ!) = ∑_{ℓ≥1} ⌊\frac{λ}{p^{ℓ}} ⌋ ≥ ∑_{ℓ=1}^{⌊log_{p} λ⌋} (\frac{λ}{p^{ℓ}} − \frac{p^{ℓ} − 1}{p^{ℓ}}) = \frac{(λ + 1)}{(p − 1)} \frac{(p^{⌊log_{p} λ⌋} − 1)}{p^{⌊log_{p} λ⌋}} − ⌊log_{p} λ⌋ . (7.3)

We claim that, if we substitute

λ_{1}(α) := p (\frac{α}{μ(Γ) − 1} + ⌊log_{p} α⌋ + 2) − 1

for λ in the right-hand side of (7.3), then the result is at least α/(μ(Γ) − 1). If one then combines (7.2) with (7.3) and observes that the right-hand side of (7.3) is monotone increasing for λ > p, then one sees that one has proved v_{p}(g_{λ}(Γ)) ≥ α for all λ ≥ λ_{1}(α). This shows that λ_{0}(α) ≤ λ_{1}(α), and, in combination with Lemma 5, will establish the upper bound in (3.1) on the period length of the sequences (f_{λ}(Γ))_{λ≥1}.

If one substitutes λ_{1}(α) for λ in the right-hand side of (7.3), then one obtains

(\frac{α}{μ(Γ) − 1} + ⌊log_{p} α⌋ + 2) \frac{p}{(p − 1)} \frac{(p^{L} − 1)}{p^{L}} − L,  (7.4)

where L = ⌊log_{p} λ_{1}(α)⌋. We have

(\frac{α}{μ(Γ) − 1} + ⌊log_{p} α⌋ + 2) \frac{p}{(p − 1)} \frac{(p^{L} − 1)}{p^{L}} − L

≥ (\frac{α}{μ(Γ) − 1} + ⌊log_{p} α⌋ + 2) − ⌊log_{p} (p (α + ⌊log_{p} α⌋ + 2) )⌋

≥ \frac{α}{μ(Γ) − 1} + ⌊log_{p} α⌋ + 1 − ⌊log_{p} α + log_{p} (1 + \frac{⌊log_{p} α⌋ + 2}{α})⌋ . (7.5)

In order to demonstrate our claim, we have to show

⌊log_{p} α⌋ + 1 − ⌊log_{p} α + log_{p} (1 + \frac{⌊log_{p} α⌋ + 2}{α})⌋ ≥ 0.  (7.6)

If α = 1, then, from (7.5), we obtain that the expression (7.6) is bounded below by

1 − ⌊log_{p} 3⌋ ≥ 0.

If α = 2, then (7.6) becomes

⌊log_{p} 2⌋ + 1 − ⌊log_{p} 2 + log_{p} (1 + \frac{⌊log_{p} 2⌋ + 2}{2})⌋ ≥ 0,

which indeed holds true. (More precisely, the expression on the left-hand side above equals 0 if p = 2, and otherwise it equals 1.) On the other hand, if α ≥ 3, then the left-hand side of (7.6) can be bounded below by

⌊log_{p} α⌋ + 1 − ⌊log_{p} α + log_{p} (1 + \frac{⌊log_{p} 3⌋ + 2}{3})⌋
≥ ⌊log_{p} α⌋ + 1 − ⌊log_{p} α + log_{p} 2⌋
≥ ⌊log_{p} α⌋ + 1 − ⌊log_{p} α + 1⌋
≥ 0.

Thus, in all cases, the expression (7.4) is bounded below by α/(μ(Γ)−1). In combination with (7.2) and (7.3) this establishes the inequality v_{p}(g_{λ}(Γ)) ≥ α for λ ≥ λ_{1}(α) ≥ λ_{0}(α). This completes the proof of the bound (3.1) on the minimal period length and, thus, of the theorem.

8. Proof of Theorem 3

If p | m_{Γ}, then, by [9, Eq. (3)], the generating function F_{Γ}(z) satisfies the congruence

F_{Γ}(z) = z^{μ_{p}(Γ)}F_{Γ}^{μ_{p}(Γ)}(z) (z^{p−1}F_{Γ}(z)^{p−1} − 1)^{(μ(Γ)−μ_{p}(Γ))/(p−1)} modulo p.  (8.1)

As is argued in [9], if p | m_{Γ} and μ_{p}(Γ) > 0, then it is clear from this congruence that F_{Γ}(z) = 0 modulo p. We shall now demonstrate by an induction on α that, for all integers α ≥ 1, the generating function F_{Γ}(z) is rational when coefficients are reduced modulo p^{α}.

For α = 1 this last statement is true due to the above remark. Let us suppose that we have already shown that F_{Γ}(z) is rational when coefficients are reduced modulo p^{α}, say F_{Γ}(z) = R(z) modulo p^{α}, for some rational function R(z) over the integers whose denominator is not divisible by p. By [9, Eq. (12)] and (8.1), we know that

F_{Γ}(z) = z^{μ_{p}(Γ)}F_{Γ}^{μ_{p}(Γ)}(z) (z^{p−1}F_{Γ}(z)^{p−1} − 1)^{(μ(Γ)−μ_{p}(Γ))/(p−1)}

+ p · P(z, F_{Γ}(z), F′_{Γ}(z), F′′_{Γ}(z), …, F_{Γ}^{(μ(Γ−1))}(z)), (8.2)

where P(z, F_{Γ}(z), F′_{Γ}(z), …, F_{Γ}^{(μ(Γ)−1)}(z)) is a polynomial in z, F_{Γ}(z), F′_{Γ}(z), …, F_{Γ}^{(μ(Γ)−1)}(z) over the rationals. However, it is proven in [9, Sections 3 and 5] that, if p | m_{Γ}, the rational coefficients can be written with denominators which are relatively prime to p, a fact that we shall tacitly use in the sequel.

We now make the Ansatz F_{Γ}(z) = R(z) + p^{α}Y (z), for some unknown formal power series Y (z), we substitute in (8.2), and then consider the result modulo p^{α+1}. Since

(R(z) + p^{α}Y (z))^{e} = R^{e}(z) + ep^{α}R^{e−1}(z)Y (z) modulo p^{α+1},

we arrive at the congruence

R(z) + p^{α}Y (z) = ∑_{i=0}^{M}(−1)^{M−i}\binom{M}{i}z^{μ_{p}(Γ)+i(p−1)}

· (R^{μ_{p}(Γ)+i(p−1)}(z) + p^{α}(μ_{p}(Γ) + i(p − 1))R^{μ_{p}(Γ)+i(p−1)−1}(z)Y (z))

+ p · P(z, R(z), R′(z), …, R^{(μ(Γ)−1)}(z)) modulo p^{α+1}, (8.3)

where M is short for (μ(Γ) − μ_{p}(Γ))/(p − 1). By rearranging terms, we transform this congruence into

p^{α}Y (z) · ( − 1 + ∑_{i=0}^{M}(−1)^{M−i}\binom{M}{i}z^{μ_{p}(Γ)+i(p−1)}(μ_{p}(Γ) + i(p − 1))R^{μ_{p}(Γ)+i(p−1)−1}(z))

= R(z) − ∑_{i=0}^{M}(−1)^{M−i}\binom{M}{i}z^{μ_{p}(Γ)+i(p−1)}R^{μ_{p}(Γ)+i(p−1)}(z)

− p · P(z, R(z), R′(z), …, R^{(μ(Γ)−1)}(z)) modulo p^{α+1}. (8.4)

By induction hypothesis, the right-hand side is divisible by p^{α}. We may hence divide both sides by p^{α}, to obtain the congruence

Y (z) · ( − 1 + ∑_{i=0}^{M}(−1)^{M−i}\binom{M}{i}z^{μ_{p}(Γ)+i(p−1)}(μ_{p}(Γ) − i)R^{μ_{p}(Γ)+i(p−1)−1}(z)) = S(z)

modulo p,

where S(z) can be written as an explicit rational function in z over the integers with denominator not divisible by p. If we remember that, from the base case of the induction (see the sentence below (8.1)), it follows that R(z) = 0 modulo p, then we see that the above congruence simplifies further to

Y (z) · ( − 1 + (−1)^{M}μ_{p}(Γ)z^{μ_{p}(Γ)}R^{μ_{p}(Γ)−1}(z)) = S(z) modulo p.  (8.5)

We can therefore determine Y (z) modulo p by dividing both sides of the congruence by the term in parentheses on the left-hand side. Hence Y (z) is a rational function modulo p, and therefore F_{Γ}(z) = R(z)+p^{α}Y (z) is rational modulo p^{α+1}. This concludes the induction argument.

The additional assertions in Theorem 3 are now obvious: if μ_{p}(Γ) = 1, then each time we divide by 1−(−1)^{M}z, and the induction hypothesis guarantees that all denominators of fractions in the congruence (8.5) are powers of 1 − (−1)^{M}z, cf. the implicit definition of S(z) via (8.4). If, on the other hand, μ_{p}(Γ) ≥ 2, then let us suppose as induction hypothesis that R(z) is actually a polynomial modulo p^{α}. Again using the fact that R(z) = 0 modulo p, we see that, since μ_{p}(Γ) + i(p − 1) > 0 for all i ≥ 0 in the current case, the congruence (8.5) reduces to

−Y (z) = S(z) modulo p.

Here, the rational function S(z) is actually a polynomial. Consequently, Y (z) is a polynomial modulo p, and thus F_{Γ}(z) = R(z) + p^{α}Y (z) is a polynomial modulo p^{α+1}. This completes the proof of the theorem.

9. Proof of Theorem 1

(I) implies (II). This is obvious.

(II) implies (III). We may have p ∤ m_{Γ} (Case (III)_{1}), or p | m_{Γ} and μ_{p}(Γ) > 0 (Case (III)_{2}), or p | m_{Γ} and μ_{p}(Γ) = 0. Due to the definition (2.10) of μ_{p}, the condition μ_{p}(Γ) = 0 already implies that p | m_{Γ} (in the sum on the right-hand side of (2.10) only the term for κ = m_{Γ} can be negative). Thus, it remains to consider the case where μ_{p}(Γ) = 0. In this case, Theorem A(iii) in [9] says that either μ(Γ) = 0, or μ(Γ) = 1 and p = 2. In the former case, the group Γ is finite (Case (III)_{3}), while in the latter case Γ is virtually infinite-cyclic (Case (III)_{4}).

(III) implies (I). We have to distinguish between the various subcases given in this item. In each case, we have to show that the generating function F_{Γ}(z) is rational modulo p^{α} for every α ≥ 1.

Case (III)_{1}. This is taken care of by Theorem 2.

Case (III)_{2}. This is dealt with by Theorem 3.

Case (III)_{3}. This is obvious since in this case F_{Γ}(z) = 1.

Case (III)_{4}. Corollary 10 says that in this case the sequence of free subgroup numbers f_{λ}(Γ) is constant. Consequently, the corresponding generating function F_{Γ}(z) is rational even over the integers.

Acknowledgements

The authors thank the anonymous referee for helpful suggestions which have led to a streamlined and improved version of this paper.

References

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

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

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

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

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

[6] R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, vol. 20, 2nd edition, Cambridge University Press, 1997.

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

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

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

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

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

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

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

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

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

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.