PARITY PATTERNS ASSOCIATED WITH LIFTS OF HECKE GROUPS

CHRISTIAN KRATTENTHALER^{†} AND THOMAS W. MÜLLER

Abstract. Let q be an odd prime, m a positive integer, and let Γ_{m}(q) be the group generated by two elements x and y subject to the relations x^{2m} = y^{qm} = 1 and x^{2} = y^{q}; that is, Γ_{m}(q) is the free product of two cyclic groups of orders 2m respectively qm, amalgamated along their subgroups of order m. Our main result determines the parity behaviour of the generalized subgroup numbers of Γ_{m}(q) which were defined in [T. W. Müller, Adv. in Math. 153 (2000), 118–154], and which count all the homomorphisms of index n subgroups of Γ_{m}(q) into a given finite group H, in the case when gcd(m, |H|) = 1. This computation depends upon the solution of three counting problems in the Hecke group ℌ(q) = C_{2} ∗ C_{q}: (i) determination of the parity of the subgroup numbers of ℌ(q); (ii) determination of the parity of the number of index n subgroups of ℌ(q) which are isomorphic to a free product of copies of C_{2} and of C_{∞}; (iii) determination of the parity of the number of index n subgroups in ℌ(q) which are isomorphic to a free product of copies of C_{q}. The first problem has already been solved in [T. W. Müller, in: Groups: Topological, Combinatorial and Arithmetic Aspects, (T. W. Müller ed.), LMS Lecture Notes Series 311, Cambridge University Press, Cambridge, 2004, pp. 327–374]. The bulk of our paper deals with the solution of Problems (ii) and (iii).

1. Introduction

1.1. The study of congruences for subgroup numbers and related numerical quantities of groups is almost as old as group theory itself. The reader might think for instance of Frobenius’ refinement in [8] of one of Sylow’s fundamental theorems:

(I) the number N_{p,r}(G) of subgroups of order p^{r} in a finite group G, whose order is divisible by p^{r}, satisfies N_{p,r}(G) ≡ 1 mod p.

Related results concern the number of solutions of equations in finite groups. The model result here is again due to Frobenius, [9]:

(II) the number of solutions of the equation x^{m} = 1 in a finite group G is a multiple of gcd(m, |G|).

2000 Mathematics Subject Classification. Primary 20E06; Secondary 05A15 05E99 16W22 20E07. Key words and phrases. modular group, Hecke groups, amalgamated products, generalized subgroup

numbers, parity patterns, involution numbers, Fermat primes.

†Research partially supported by the Austrian Science Foundation FWF, grant S9607-N13, in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

The last result was considerably extended and sharpened by P. Hall [14], building heavily on his groundbreaking work [13] concerning the structure of finite p-groups.

From a somewhat more abstract point of view, Frobenius’ theorem (II) provides congruences for the number of homomorphisms of a finite cyclic group into a finite group G; and it is this point of view, which explains the connection between results of types (I) and (II). Certain sequences {G_{n}}_{n≥0} of finite groups, like the sequence G_{n} = S_{n} of symmetric groups or, more generally, a sequence of full monomial groups G_{n} = H ≀ S_{n}, have the power of relating the enumeration of finite index subgroups by index (or similar counting functions) in an arbitrary finitely generated group Γ to the counting of homomorphisms Γ → G_{n}. On the level of generating functions, this relationship is of exponential type; see Formula (5.3) for a concrete example in this direction.

To some extent, divisibility properties of subgroup numbers of a (finitely generated) infinite group may be viewed as a kind of analogue to these classical results for finite groups. Further motivation comes from subgroup growth theory, which studies growth, asymptotics, and more delicate number-theoretic properties of subgroup counting functions; cf. the monograph [17] for an overview of results up to about 2002. As far as divisibility properties are concerned, it was a, by now classical, result of Stothers concerning the modular group Γ = PSL_{2}(ℤ), which prompted the quest that led to the delicate congruence patterns exhibited by Hecke groups and other free products. Stothers [33] showed that

(III) the number of index n subgroups in the modular group is odd if, and only if, n is of the form 2-power minus 3 or 2-power minus 6.

The present paper continues this line of research by investigating the parity of (generalized) subgroup numbers of certain free products with amalgamation, which may be viewed as lifts of an underlying Hecke group. We now turn to a more precise description of the contents of this paper.

1.2. For an odd prime q, let

ℌ(q) = ⟨x, y | x^{2} = y^{q} = 1⟩ ≅ C_{2} ∗ C_{q}  (1.1)

be the standard Hecke group attached to q, and for a positive integer m, let

Γ_{m} = Γ_{m}(q) = ⟨x, y | x^{2m} = y^{qm} = 1, x^{2} = y^{q}⟩ ≅ C_{2m} ∗_{C_{m}} C_{qm}

be the associated sequence of lifts in the sense of [22, Eq. (40)]. Moreover, for a finitely generated group Γ, a finite group H, and a positive integer n, set

s_{Γ}^{H}(n) := ∑_{(Γ:Δ)=n}| Hom(Δ, H)|.

The family {s_{Γ}^{H}(n)}_{n,H} is the collection of generalized subgroup numbers of Γ. For H = {1}, the quantity s_{Γ}^{H}(n) is the number of index n subgroups of Γ, which we denote by s_{Γ}(n).

The present paper focusses on the parity behaviour of the numbers s_{Γ}^{H}(n) in the case when Γ = Γ_{m}(q) for m, q as above.

The systematic investigation of divisibility properties of subgroup counting functions begins with [28] (which had circulated in the subgroup growth community for some years), where the parity of s_{q}(n) := s_{ℌ(q)}(n) and of the number of free subgroups in ℌ(q) of given finite index is determined. These results have been generalized to larger classes of groups and primes not necessarily equal to 2 in [26, 29]. For a survey of these and related developments up to 2001, the reader may consult [27].

The present paper is a first attempt to study divisibility properties of (generalized) subgroup numbers for amalgamated products. Our main result (see Theorem 26 in Section 6) determines the parity behaviour of the generalized subgroup numbers s_{Γ_{m}(q)}^{H}(n) in the case when gcd(m, |H|) = 1. As Proposition 1 in the next section shows, this computation can be reduced to the solution of three counting problems in the Hecke group ℌ(q) = C_{2} ∗ C_{q}:

(i) determination of the parity of the subgroup numbers s_{q}(n) of ℌ(q); (ii) determination of the parity of the numbers M_{q}(n), where, by definition, M_{q}(n) is the number of index n subgroups of ℌ(q) isomorphic to a free product of copies of C_{2} and of C_{∞};

(iii) determination of the parity of the numbers N_{q}(n), where, by definition, N_{q}(n) is the number of index n subgroups of ℌ(q) isomorphic to a free product of copies of C_{q}.

The first problem has already been solved in [28, Cor. 4]. The corresponding result is recalled here as Theorem 2 in the next section. Problem (ii) is solved in Theorem 16 in Section 4, which, perhaps somewhat surprisingly, shows that the numbers M_{q}(n) are always even, and Problem (iii) is solved in Theorem 24 in Section 5.

The purpose of Section 3 is to develop in some detail the language of coset diagrams for the groups ℌ(q), in order to prepare for the proof of Theorem 16. This proof needs several partial results, which are the subject of Section 4. The first observation is that M_{q}(n) = 0 if q does not divide n, see (4.2). It therefore suffices to investigate the parity of the numbers M_{q}(qk), where k is some positive integer. The enumerative relation between the coset diagrams and subgroup numbers is made precise in Subsection 4.1. This is done in greater generality than actually needed in our paper, in order to record the corresponding facts for possible use elsewhere. Lemma 6 expresses the numbers of index n subgroups of ℌ(q) which are isomorphic to C_{2}^{∗λ}∗C_{q}^{∗μ}∗F_{ν} for fixed λ, μ, ν in terms of the number of certain mixed graphs. The enumeration of these graphs is subsequently reduced in Lemma 7 to graphs where the number of vertices is divisible by q. Then Corollary 8 summarizes specifically the implications for the subgroup numbers M_{q}(qk) and s_{q}(n). The main result of Subsection 4.2 is an explicit formula for the number of (mixed) graphs that appear in the corollary, see Proposition 9. This formula allows us to undertake a 2-adic study of the numbers M_{q}(qk) for q ≥ 5 in Subsection 4.3, by using known results on the 2-adic valuation of the number of involutions in symmetric groups. The corresponding result, which we prove in Proposition 12, is stronger than actually needed, as it exhibits a rapidly growing lower bound for the 2-adic valuation of the numbers M_{q}(qk). On the other hand, a similar result cannot be expected for q = 3. Moreover, our explicit formula from Subsection 4.2 does not seem to be suited for the 2-adic analysis in this case. Instead, we use results of Stothers [33] to prove in Proposition 15, also in Subsection 4.3, that M_{3}(3k) is even as well.

Section 5 puts together the ingredients for the proof of Theorem 24. The starting point is the observation that the parity of N_{q}(n) is the same as the parity of the generalized subgroup numbers s_{q}^{H}(n) := s_{ℌ(q)}^{H}(n) with |H| even, see (5.2). Just as subgroup numbers are connected with the enumeration of permutation representations, by [23, Cor. 1] the generalized subgroup numbers s_{Γ}^{H}(n) of a finitely generated group Γ are related to the function | Hom(Γ, H ≀ S_{n})|, counting monomial representations of Γ, via an identity of exponential type, which is restated here in (5.3). This identity is exploited in Subsections 5.1–5.3 to compute the generalized subgroup numbers s_{q}^{H}(n) via a generating function approach, and to determine their parity in the case when H has even order in Subsection 5.5, thereby also determining the parity of N_{q}(n). As a side result, we actually obtain a formula leading to an integral recurrence relation for the numbers s_{q}^{H}(n), n = 0, 1, …, for each fixed q; see (5.26). This aspect is illustrated in Subsection 5.4 with the modular group ℌ(3); see Proposition 23.

Since the proofs of some auxiliary results in Sections 4 and 5 are tedious, involving however relatively straightforward calculations, we have put these proofs in an appendix, so that they do not distract from or obscure the main line of argument.

The final section, Section 6, contains our main result, Theorem 26, determining the parity behaviour of the generalized subgroup numbers s_{Γ_{m}(q)}^{H}(n) in the case when gcd(m, |H|) = 1, as well as its specialization to the case when q is a Fermat prime, in which case one can be much more precise (see Corollary 27), together with further simplifications when m and/or n satisfy some more specific properties.

2. A reduction result

For an odd prime q, let Γ_{m} = Γ_{m}(q) be as in the introduction. We note that Γ_{m}(q) ≅ Γ̸_{m′}(q′) for (m, q) ≠ (m′, q′). In this section we will show that the parity behaviour of the generalized subgroup numbers of these groups can be computed in terms of certain subgroup numbers pertaining to the base group ℌ(q); see Proposition 1.

Set

ζ := x^{2} = y^{q},

so that ζ is a primitive element for the centre of Γ_{m}. For a positive integer n, a divisor d of m, and a finite group H, define

s_{Γ_{m}}^{H}(d, n) := _{∑_{Δ} ; (Γ_{m}:Δ)=n ; Δ∩⟨ζ⟩=⟨ζ^{m/d}⟩}| Hom(Δ, H)|,

so that

s_{Γ_{m}}^{H}(n) = ∑_{d|m} s_{Γ_{m}}^{H}(d, n).  (2.1)

In what follows, we shall find it necessary to suppose that gcd(m, |H|) = 1. Under the natural projection

π_{d} : Γ_{m} ⟶ Γ_{m}/⟨ζ^{m/d}⟩ ≅ Γ_{m/d}

the subgroups Δ of index n in Γ_{m} having the property that Δ ⊇ ⟨ζ^{m/d}⟩ correspond bijectively to the totality of index n subgroups in Γ_{m/d}. Moreover, since gcd(m, |H|) = 1, every homomorphism φ : Δ → H factors through the canonical projection π_{d}^{Δ} : Δ → Δ/⟨ζ^{m/d}⟩. Hence, for d | m,

s_{Γ_{m/d}}^{H}(n) = _{∑_{Δ̄} ; (Γ_{m/d}:Δ̄)=n}| Hom(Δ̄, H)|

= _{∑_{Δ} ; (Γ_{m}:Δ)=n ; Δ⊇⟨ζ^{m/d}⟩}| Hom(Δ, H)|

= _{∑_{d′} ; d|d′|m} _{∑_{Δ} ; (Γ_{m}:Δ)=n ; Δ∩⟨ζ⟩=⟨ζ^{m/d′}⟩}| Hom(Δ, H)|,

and thus

s_{Γ_{m/d}}^{H}(n) = _{∑_{d′} ; d|d′|m}s_{Γ_{m}}^{H}(d′, n), d | m.  (2.2)

Fixing q, m, n, and H, and setting

g(x) := \begin{cases}s_{Γ_{m/x}}^{H}(n), & x | m \\ 0, & otherwise \end{cases}\} (x ∈ ℕ),

f(x) := \begin{cases}s_{Γ_{m}}^{H}(x, n), & x | m \\ 0, & otherwise \end{cases}\} (x ∈ ℕ),

and letting P be the poset with ground-set ℕ and partial order defined by x ≤ y if, and only if, y | x, Equation (2.2) translates into

g(x) = ∑_{y≤x} f(y), x ∈ P,

and, by definition of the function f, we have f(x) = 0 unless x ≥ m. By Möbius inversion (cf. [31, Propositions 2–3]), we find that

s_{Γ_{m}}^{H}(d, n) = _{∑_{d′} ; d|d′|m}μ_{P} (d, d′) s_{Γ_{m/d′}}^{H}(n), d | m,

where μ_{P} (x, y) is the Möbius function in the poset P. It is well-known that μ_{P} (x, y) = μ(x/y) for x ≤ y (that is, y | x), where μ(·) is the classical Möbius function of number theory. Hence, we have

s_{Γ_{m}}^{H}(d, n) = _{∑_{d′} ; d|d′|m}μ(d′/d) s_{Γ_{m/d′}}^{H}(n), d | m.  (2.3)

On the other hand, if we set d = 1 in (2.3) and apply Möbius inversion in the other direction, we obtain

s_{Γ_{m}}^{H}(n) = ∑_{d|m} s_{Γ_{d}}^{H}(1, n), gcd(m, |H|) = 1.  (2.4)

Our next task is to compute s_{Γ_{m}}^{H}(1, n) modulo 2. If there exists a subgroup Δ ≤ Γ_{m} with (Γ_{m} : Δ) = n and Δ ∩ ⟨ζ⟩ = 1, then

Δ̃ := Δ · ⟨ζ⟩ = Δ × ⟨ζ⟩;

hence, m must divide n. Thus,

s_{Γ_{m}}^{H}(1, n) = 0, m ∤ n.  (2.5)

Suppose now that m | n. Given a subgroup Δ ≤ Γ_{m} with (Γ_{m} : Δ) = n and Δ∩⟨ζ⟩ = 1, consider the diagram

Δ ⟶^{m} Δ̃ = Δ · ⟨ζ⟩ ⟶^{n/m} Γ_{m}
π_{m}↓  ^{π_{m}}↓  ↓^{π_{m}}
Δ̄ ⟶^{id}  Δ̄  ⟶_{n/m} Γ̄ ≅ Γ_{1} = ℌ(q)

(2.6)

(a number next to an arrow indicates the index of the corresponding embedding). Reading Diagram (2.6) from bottom to top, we can describe Δ as a complement to ⟨ζ⟩ in the lift Δ̃ = π_{m}^{−1}(Δ̄) of a subgroup Δ̄ in Γ̄ ≅ ℌ(q) with (Γ̄ : Δ̄) = n/m. Hence,

s_{Γ_{m}}^{H}(1, n) = _{∑_{Δ̄} ; (Γ̄:Δ̄)=n/m} | Hom(Δ̄, H)| · |ℭ(π_{m}^{−1}(Δ̄); ⟨ζ⟩)|, m | n,  (2.7)

where ℭ(π_{m}^{−1}(Δ̄); ⟨ζ⟩) is the (possibly empty) set of complements of ⟨ζ⟩ in π_{m}^{−1}(Δ̄).

Given Δ̄ ≤ Γ̄ of index n/m, when does ⟨ζ⟩ split in π_{m}^{−1}(Δ̄)? To answer this question, we make use of the long exact (Mayer–Vietoris) sequence

⋯ → H^{k}(G; A) ⟶_{(res,res)} H^{k}(G_{1}; A) ⊕ H^{k}(G_{2}; A)

⟶_{(res,−res)} H^{k}(S; A) ⟶_{δ} H^{k+1}(G; A) → ⋯ (2.8)

associated with an amalgamated product G = G_{1} ∗_{S} G_{2} and a left RG-module A; cf. [2,

Theorem 2.10] or [4, Theorem 2]. By the Kurosh subgroup theorem, Δ̄ is of the form

Δ̄ ≅ C_{2}^{∗λ(Δ̄)} ∗ C_{q}^{∗μ(Δ̄)} ∗ F_{ν(Δ̄)}

with non-negative integers λ(Δ̄), μ(Δ̄), ν(Δ̄) (these cardinal numbers are seen to be finite through a comparison of Euler characteristics; cf. Equation (3.3) below). Applying (2.8) together with the fact that every extension by a free group splits, we see that

H^{2}(Δ̄; C_{m}) ≅ λ(Δ̄)H^{2}(C_{2}; C_{m}) ⊕ μ(Δ̄)H^{2}(C_{q}; C_{m}).  (2.9)

We now distinguish four cases.

(i) 2 ∤ m and q | m. Suppose that, for some subgroup Δ̄ ≤ Γ̄ of index (Γ̄ : Δ̄) = n/m, ⟨ζ⟩ splits in π_{m}^{−1}(Δ̄), and that μ(Δ̄) > 0. Then C_{m} × C_{q}, an Abelian group of rank 2, would embed into Γ_{m}, which is impossible. Hence, if ⟨ζ⟩ splits in π_{m}^{−1}(Δ̄), then μ(Δ̄) = 0. Conversely, if μ(Δ̄) = 0, then every extension of C_{m} by Δ̄ splits, since H^{2}(C_{2}; C_{m}) = 0 by the Schur–Zassenhaus theorem plus the fact that 2 ∤ m; cf. for instance [34, Chapter 3]. To summarize, we have shown that

if 2 ∤ m and q | m, then ⟨ζ⟩ splits in π_{m}^{−1}(Δ̄) if, and only if, μ(Δ̄) = 0.  (2.10)

(ii) 2 ∤ m and q ∤ m. In this case, again by the Schur–Zassenhaus theorem and the isomorphism (2.9), we find that H^{2}(Δ̄; C_{m}) = 0. Hence,

if 2 ∤ m and q ∤ m, then the lift π_{m}^{−1}(Δ̄)

of every subgroup Δ̄ ≤_{n/m} Γ̄ splits the centre ⟨ζ⟩. (2.11)

(iii) 2 | m and q ∤ m. Arguing as in (i), we find that

if 2 | m and q ∤ m, then ⟨ζ⟩ splits in π_{m}^{−1}(Δ̄) if, and only if, λ(Δ̄) = 0.  (2.12)

(iv) 2q | m. In this case, we find by similar arguments that

if 2q | m, then ⟨ζ⟩ splits in π_{m}^{−1}(Δ̄) if, and only if, λ(Δ̄) = μ(Δ̄) = 0.  (2.13)

Given the information in (2.10)–(2.13), we can now evaluate the quantities s_{Γ_{m}}^{H}(1, n) modulo 2 in terms of data associated with the base group Γ̄ alone. Denote by M_{q}(n) the number of index n subgroups Δ̄ in Γ̄ = ℌ(q) with the property that μ(Δ̄) = 0, by N_{q}(n) the number of subgroups of index n in Γ̄ which are isomorphic to a free power of C_{q}, and recall that s_{q}(n) denotes the number of index n subgroups in ℌ(q).

Proposition 1. For m, n ≥ 1, an odd prime q, and a finite group H, we have

s_{Γ_{m}(q)}^{H}(1, n) ≡ \begin{cases}N_{q}(n/m); & 2 | m | n and q ∤ m \\ s_{q}(n/m); & 2 ∤ m, q ∤ m, m | n, and 2 ∤ |H| \\ N_{q}(n/m); & 2 ∤ m, q ∤ m, m | n, and 2 | |H| \\ M_{q}(n/m); & q | m | n, 2 ∤ m, and 2 ∤ |H| \\ 0; & otherwise \end{cases}\} mod 2.

Proof. This is straightforward. For instance, in the first case (2 | m | n and q ∤ m), the computation runs as follows:

s_{Γ_{m}}^{H}(1, n) = _{∑_{Δ̄} ; (Γ̄:Δ̄)=n/m} | Hom(Δ̄, H)| · |ℭ(π_{m}^{−1}(Δ̄); ⟨ζ⟩)|

= _{∑_{Δ̄} ; (Γ̄:Δ̄)=n/m_{λ(Δ̄)=0}} | Hom(Δ̄, H)| · | Hom(Δ̄, C_{m})|

= _{∑_{Δ̄} ; (Γ̄:Δ̄)=n/m_{λ(Δ̄)=0}} m^{ν(Δ̄)} | Hom(Δ̄, H)|

≡ _{∑_{Δ̄} ; (Γ̄:Δ̄)=n/m_{λ(Δ̄)=ν(Δ̄)=0}} | Hom(Δ̄, H)|

≡ _{∑_{Δ̄} ; (Γ̄:Δ̄)=n/m_{λ(Δ̄)=ν(Δ̄)=0}} 1

= N_{q}(n/m),

where Γ̄ = ℌ(q), and where we have made use of (2.7), (2.12), and the fact that

| Hom(C_{q}, H)| = 1 + (q − 1) · |{U ≤ H : U ≅ C_{q}}|

is always odd. Computations for the other cases are similar, and are left to the reader. □

Combining Equation (2.4) with Proposition 1, the calculation of the generalized subgroup numbers s_{Γ_{m}(q)}^{H}(n) modulo 2 has been reduced to the mod 2 calculation of the numbers s_{q}(n), M_{q}(n), and N_{q}(n). The first problem has already been solved in [28, Cor. 4]. The result reads as follows.

Theorem 2. Let q be an odd prime. Then

s_{q}(n) ≡ 1 (mod 2) if, and only if, n = 1 + 2(q − 1)η or n = 2 + 4(q − 1)η, where

𝔰_{2}((q − 1)η + 1) = 𝔰_{2}(η) + 𝔰_{2}((q − 2)η + 1), and η ∈ ℕ_{0}.  (2.14)

Here, 𝔰_{2}(x) denotes the sum of digits in the binary expansion of the positive integer x. In particular, if q is a Fermat prime, then

s_{q}(n) ≡ 1 (mod 2) if, and only if,

n = \frac{2(q − 1)^{σ} − q}{q − 2} or n = \frac{4(q − 1)^{σ} − 2q}{q − 2} for some σ ≥ 1. (2.15)

3. Coset diagrams associated with Hecke groups

There is a well-known connection between the subgroups of index n in a group Γ and the transitive permutation representations of Γ of degree n, which is sometimes useful to obtain information concerning various subgroup numbers of Γ. As the details of this relationship are somewhat hard to find in the literature, we provide a brief discussion of the general facts in Subsection 3.1 for the convenience of the reader, after which we focus on the special case of Hecke groups and their diagrams in Subsection 3.2. This discussion will provide the basis for the mod 2 determination of the numbers M_{q}(n) in Section 4.

3.1. Transitive permutation representations versus finite-index subgroups. Here, and in the rest of the paper, for a non-negative integer n, the symbol [n] will always denote the standard set {1, 2, …, n} of size n. Let S_{n} = Sym([n]) be the symmetric group of degree n acting on the standard set [n], endowed with geometric multiplication, let U_{n} = stab_{S_{n}}(1) be the stabilizer of the letter 1 in S_{n}, and, for a group Γ, denote by T_{n}(Γ) the set of all transitive permutation representations φ : Γ → S_{n}. For a permutation σ ∈ S_{n}, let ι_{σ} be the inner automorphism of S_{n} induced by σ,

ι_{σ}(π) = σ ∘ π ∘ σ^{−1}, π ∈ S_{n},

and define a left action of U_{n} on T_{n}(Γ) via the commutative diagram

\begin{matrix}Γ & ⟶^{φ} & S_{n} \\ ^{id}_{Γ}↓ & & ↓^{ι_{σ}} \\ Γ & ⟶_{σ·φ} & S_{n} \end{matrix} (σ ∈ U_{n}, φ ∈ T_{n}(Γ)),

where id_{Γ} is the identity map on Γ. The basic observation is now the following.

Proposition 3. (i) The action of U_{n} on T_{n}(Γ) is free; in particular, each equivalence class of T_{n}(Γ) modulo U_{n} contains precisely (n − 1)! elements.

(ii) There is a one-to-one correspondence between the subgroups of index n in Γ and the equivalence classes of T_{n}(Γ) under the action of U_{n}.

Proof. (i) Suppose that σ · φ = φ for some σ ∈ U_{n} and some φ ∈ T_{n}(Γ). By transitivity, given j ∈ [n], there exists γ_{j} ∈ Γ such that φ(γ_{j})(1) = j, and hence

σ(j) = σ(φ(γ_{j})(σ^{−1}(1)))
= (σ · φ)(γ_{j})(1)
= φ(γ_{j})(1)
= j.

Since j was arbitrary, we conclude that σ = id_{[n]}; thus, the action of U_{n} on T_{n}(Γ) is free as claimed. The particular statement follows from this and the fact that U_{n} ≅ S_{n−1}.

(ii) Given φ ∈ T_{n}(Γ), the subgroup

Δ_{φ} := stab_{φ}(1) = φ^{−1}(U_{n})

has index n in Γ, since a set of elements {γ_{1}, γ_{2}, …, γ_{n}} chosen as in Part (i) forms a system of (left) coset representatives for Γ modulo Δ_{φ}. Further, if φ_{2} = σ · φ_{1} for some σ ∈ U_{n}, then

Δ_{φ_{2}} = φ_{2}^{−1}(U_{n})
= (ι_{σ} ∘ φ_{1})^{−1}(U_{n})
= φ_{1}^{−1}(ι_{σ^{−1}}(U_{n}))
= φ_{1}^{−1}(U_{n})
= Δ_{φ_{1}}.

Hence, the assignment φ ↦ Δ_{φ} induces a well-defined map

Φ : U_{n}\T_{n}(Γ) ⟶ {Δ : Δ ≤ Γ, (Γ : Δ) = n}.

A subgroup Δ ≤ Γ of index n in Γ induces a transitive Γ-action by left multiplication on the n-set Γ/Δ of left cosets which, after suitable renaming, becomes a transitive Γ-action on [n] with the property that stab(1) = Δ. This shows that Φ is surjective.

To prove injectivity, suppose that φ_{1}, φ_{2} ∈ T_{n}(Γ) are two transitive permutation representations of Γ on [n], such that Δ_{φ_{1}} = Δ_{φ_{2}}. As before, choose elements γ_{1}, γ_{2}, …, γ_{n} ∈ Γ such that

φ_{1}(γ_{j})(1) = j, 1 ≤ j ≤ n,

and define a permutation σ_{0} ∈ U_{n} via

σ_{0}(j) := φ_{2}(γ_{j})(1), 1 ≤ j ≤ n.

Then, for γ ∈ Γ and j ∈ [n], and with γγ_{j} ∼_{Δ_{φ_{1}}} γ_{k}, we have

σ_{0}(φ_{1}(γ)(j)) = σ_{0}(φ_{1}(γ)(φ_{1}(γ_{j})(1)))
= σ_{0}(φ_{1}(γγ_{j})(1))
= σ_{0}(φ_{1}(γ_{k})(1))
= σ_{0}(k)
= φ_{2}(γ_{k})(1)
= φ_{2}(γγ_{j})(1)
= φ_{2}(γ)(φ_{2}(γ_{j})(1))
= φ_{2}(γ)(σ_{0}(j)).

Since j and γ were arbitrary, this shows that σ_{0} · φ_{1} = φ_{2}; that is, φ_{1} and φ_{2} are equivalent under the action of U_{n}, as required. □

3.2. The case of Hecke groups. Now let q be an odd prime number, and let

ℌ(q) = ⟨x, y | x^{2} = y^{q} = 1⟩  (3.1)

be the standard Hecke group attached to q. By Kurosh’s subgroup theorem, a subgroup Δ ≤ ℌ(q) is of the form

Δ ≅ C_{2}^{∗λ(Δ)} ∗ C_{q}^{∗μ(Δ)} ∗ F_{ν(Δ)}  (3.2)

with cardinal numbers λ(Δ), μ(Δ), and ν(Δ). Moreover, if Δ has finite index in ℌ(q), comparing the Euler characteristic of Δ with that of ℌ(q) shows that λ(Δ), μ(Δ), ν(Δ) are finite, and are connected to the index (ℌ(q) : Δ) via the relation

qλ(Δ) + 2(q − 1)μ(Δ) + 2q(ν(Δ) − 1) = (q − 2)(ℌ(q) : Δ).  (3.3)

Our next result which, in the case of the modular group, goes back to Millington [19, Theorem 1], provides a refinement of the bijection Φ in the proof of Proposition 3(ii) by taking into account the isomorphism type

t(Δ) = (λ(Δ), μ(Δ), ν(Δ))

of a finite-index subgroup Δ in ℌ(q).

Proposition 4. Let q be an odd prime, let Δ be a subgroup of finite index n in ℌ(q), and let φ : ℌ(q) → S_{n} be a transitive permutation representation of ℌ(q) such that Δ_{φ} = Δ. Then φ(x) has precisely λ(Δ) fixed points, and φ(y) has exactly μ(Δ) fixed points, where x, y are as in (3.1).

Proof. As in the proof of Proposition 3, choose elements γ_{1}, γ_{2}, …, γ_{n} ∈ ℌ(q) such that

φ(γ_{j})(1) = j, 1 ≤ j ≤ n;

i.e., {γ_{1}, γ_{2}, …, γ_{n}} is a left transversal for ℌ(q) modulo Δ. The equation φ(x)(j) = j is equivalent to the condition that x^{γ_{j}} ∈ Δ; in particular, the assignment

j ↦ C_{j} := {δ^{−1}x^{γ_{j}}δ : δ ∈ Δ}

defines a mapping Φ_{x} from the set of fixed points of φ(x) to the set of conjugacy classes of elements of order 2 in Δ. If

C = {δ^{−1}x′δ : δ ∈ Δ} ⊆ Δ

is such a conjugacy class, then x′ is in Δ and has order 2; thus, by the torsion theorem for free products (cf., for instance, Theorem 1.6 in Chapter IV of [18]), there exists an element γ = γ_{j}δ such that

x′ = γ^{−1}xγ = δ^{−1}x^{γ_{j}}δ.

It follows that x^{γ_{j}} ∈ Δ, i.e., φ(x)(j) = j, and C = C_{j}; that is, Φ_{x} is surjective. To prove injectivity, let j and k be fixed points of φ(x), and suppose that C_{j} = C_{k}; that is,

δ^{−1}x^{γ_{j}}δ = x^{γ_{k}}.

Consequently, the element γ_{j}δγ_{k}^{−1} centralizes the generator x, implying γ_{j}δγ_{k}^{−1} = x^{ϵ} with ϵ ∈ {0, 1} by [20, Cor. 4.1.6]. Hence,

j = φ(γ_{j}δγ_{k}^{−1})(k) = φ(x^{ϵ})(k) = k,

as desired. We conclude that the fixed points of φ(x) are in one-to-one correspondence with the λ(Δ) conjugacy classes of elements of order 2 in Δ. By a similar argument, the fixed points of φ(y) are in one-to-one correspondence with the μ(Δ) conjugacy classes of cyclic subgroups of order q in Δ, completing the proof. □

It is customary to translate these facts into a geometric language. To every transitive permutation representation φ : ℌ(q) → S_{n} there corresponds a diagram D_{φ} consisting of n labelled vertices, red undirected loops, blue undirected loops, red undirected edges, and blue directed edges, constructed as follows: the vertices of D_{φ} are labelled with the elements of the standard set [n]; for i, j ∈ [n] such that φ(x)(i) = j, the vertices labelled i and j are joined by an undirected red edge (a loop if i = j); for i, j ∈ [n] with i ≠ j and φ(y)(i) = j, we draw a directed blue edge from vertex i to vertex j, while, for i = j, we attach an undirected blue loop to vertex i. In this way, the set T_{n}(ℌ(q)) is in bijective correspondence with the set D_{n,q} of diagrams on n vertices labelled with the elements of the standard set [n], such that

(a) each vertex has a red loop, or is incident with exactly one red edge,

(b) each vertex has a blue loop, or is contained in precisely one oriented blue q-gon,

(c) the red and blue edges together give a connected figure.

The elements of D_{n,q} are the coset diagrams of order n associated with the Hecke group ℌ(q). A permutation σ ∈ S_{n} induces a map σ : D_{n,q} → D_{n,q}; two diagrams D_{1}, D_{2} are called equivalent, if σ(D_{1}) = D_{2} for some permutation σ ∈ U_{n}. The set of orbits U_{n}\D_{n,q} is in bijective correspondence with the subgroups of index n in ℌ(q), and each equivalence class of diagrams has (n − 1)! elements. Further, if D is a diagram corresponding to the index n subgroup Δ_{D} ≤ ℌ(q), then D contains precisely λ(Δ_{D}) red loops and μ(Δ_{D}) blue loops. Our next result, while spelling out certain numerical constraints, also provides a geometric interpretation for the quantity ν(Δ_{D}).

Proposition 5. If D ∈ D_{n,q} is a diagram containing k blue q-gons and e red edges, and with associated subgroup Δ_{D}, then

(i) \frac{n}{q} ≥ k ≥ \frac{n − e − 1}{q − 1},

(ii) \frac{n}{2} ≥ e ≥ n − (q − 1)k − 1,

(iii) e + (q − 1)k − n + 1 = ν(Δ_{D}).

Proof. If n = 1, then D consists of one vertex labelled 1, with a red and a blue loop attached to it. Thus, k = e = 0 and, by (3.3), ν(Δ_{D}) = 0. Similarly, for n = 2, the diagram D consists of two vertices labelled 1 and 2, respectively, each having a blue loop attached to it, and joined by a red edge. Thus, k = 0, e = 1, and, by (3.3), ν(Δ_{D}) = 0. One checks that in both cases assertions (i)–(iii) hold true. Hence, for the rest of the proof, we may assume that n > 2.

Since, by (b), the q-gons are disjoint, we must have kq ≤ n; the n − qk vertices not involved in a q-gon must carry blue loops. By (c), there exist at least k − 1 red edges joining vertices of distinct blue q-gons, and a further n − qk red edges, each joining a vertex with a blue loop to a vertex of a q-gon (here we need that n > 2). Thus, there are at least n − (q − 1)k − 1 red edges. Since

μ(Δ_{D}) = n − qk

and, in view of (a),

λ(Δ_{D}) = n − 2e,

Equation (3.3) shows that indeed e + (q − 1)k − n + 1 = ν(Δ_{D}). The remaining inequalities follow since λ(Δ_{D}), ν(Δ_{D}) ≥ 0. □

It is not hard to see that, conversely, whenever inequalities (i) and (ii) are satisfied, a diagram D with specifications as described in Proposition 5 does indeed exist.

4. Counting finite-index subgroups in Hecke groups via coset diagrams

The main purpose of this section is to establish the fact that, for every odd prime q and each integer n ≥ 1, we have

M_{q}(n) ≡ 0 mod 2,  (4.1)

so that these numbers do in fact not enter into the mod 2 calculation of s_{Γ_{m}(q)}^{H}(n), despite their appearance in Proposition 1; cf. Theorem 16.

If Δ is a subgroup of index n in ℌ(q) with μ(Δ) = 0, then we must have q | n by Equation (3.3) plus the fact that q is a prime. Hence,

M_{q}(n) = 0, q ∤ n;  (4.2)

in particular, M_{q}(n) ≡ 0 (mod 2) in this case. We are thus reduced to checking the case where n = qk with k ≥ 1. Using coset enumeration techniques, the numbers M_{q}(qk) are expressed as a sum of certain combinatorially defined quantities M_{q}(qk; e, k) divided by q^{k−1}(k − 1)!, see Corollary 8(ii). As a next step, an explicit formula for M_{q}(qk; e, k) is found in Proposition 9. Subsequently, this explicit formula is used to show that M_{q}(qk) is always even for q ≥ 5; see Proposition 12. Finally, the corresponding fact for q = 3 is established in Proposition 15, building on the work of Stothers [33]. A curious side result is Proposition 10, which provides a closed form product formula for M_{q}(qk; e, k) in the minimal case e = k − 1. As already mentioned in the introduction, the next subsection addresses, in complete generality, the problem of enumerating the index n subgroups in ℌ(q) which are isomorphic to C_{2}^{∗λ} ∗ C_{q}^{∗μ} ∗ F_{ν} for fixed λ, μ, ν.

4.1. Enumerating finite-index subgroups of given type. Let n, m_{1}, m_{2} be integers with n > 0 and m_{1}, m_{2} ≥ 0. Suppose that we are given a set of m_{2} disjoint oriented blue q-gons, the vertices of the i-th one being labelled q(i−1)+1, …, qi−1, qi in order, as well as n − qm_{2} additional vertices labelled qm_{2} + 1, qm_{2} + 2, …, n. We consider (mixed) graphs resulting from the previously described q-gons and additional vertices by drawing m_{1} undirected red edges, such that each vertex is incident with at most one red edge, and such that a connected graph is obtained. (Here, for connectivity, both the blue and red edges are taken into account.) Let M_{q}(n; m_{1}, m_{2}) be the set of all these graphs, and let M_{q}(n; m_{1}, m_{2}) be the cardinality of M_{q}(n; m_{1}, m_{2}).

Denote by s_{q}(n; m_{1}, m_{2}) the number of index n subgroups Δ in ℌ(q) of representation type

m(Δ) = (\begin{matrix}m_{1} & n − 2m_{1} \\ m_{2} & n − qm_{2} \end{matrix});  (4.3)

that is, the generator x in (3.1) acts as a product of m_{1} 2-cycles and n − 2m_{1} fixed points on the coset space ℌ(q)/Δ, while the generator y in (3.1) acts as a product of m_{2} q-cycles and n − qm_{2} fixed points on ℌ(q)/Δ. We note that in our situation the representation type m(Δ) and the isomorphism type t(Δ) of a finite index subgroup Δ determine each other. More precisely, if Δ is of index n in ℌ(q), then m(Δ) is given by (4.3) if and only if t(Δ) is given by

t(Δ) = (n − 2m_{1}, n − qm_{2}, m_{1} + (q − 1)m_{2} − n + 1).  (4.4)

The numbers M_{q}(n; m_{1}, m_{2}) and s_{q}(n; m_{1}, m_{2}) are related in the following way.

Lemma 6. For an odd prime q and integers n, m_{1}, m_{2} with n > 0 and m_{1}, m_{2} ≥ 0, we have

s_{q}(n; m_{1}, m_{2}) = \frac{nM_{q}(n; m_{1}, m_{2})}{q^{m_{2}}m_{2}! (n − qm_{2})!}.  (4.5)

Proof. Clearly, a graph G ∈ M_{q}(n; m_{1}, m_{2}) can be made into a coset diagam D ∈ D_{n,q} by adding a red loop at each vertex not incident with a red edge and a blue loop at each vertex not incident with a blue q-gon. The subgroup Δ_{D} corresponding to such a diagram has index n and representation type ( \begin{matrix}m_{1} & n−2m_{1} \\ m_{2} & n−qm_{2} \end{matrix} ). Conversely, such a subgroup leads to a graph G ∈ M_{q}(n; m_{1}, m_{2}) for some labelling of the vertices by deleting all red and blue loops in a corresponding coset diagram.

In order to construct all possible labellings, first choose labels for the vertices involved in some q-gon in \binom{n}{qm_{2}} ways. These chosen labels can be used to label the m_{2} q-gons in

\frac{1}{m_{2}!}\binom{qm_{2}}{q, …, q}(q − 1)!^{m_{2}} = \frac{(qm_{2})!}{m_{2}! q^{m_{2}}}

ways. On the other hand, there is only one way to label the additional (n − qm_{2}) vertices by the remaining labels, these being completely indistinguishable. Hence, the number of coset diagrams corresponding to subgroups of index n and representation

type ( \begin{matrix}m_{1} & n−2m_{1} \\ m_{2} & n−qm_{2} \end{matrix} ) is

\binom{n}{qm_{2}} \frac{(qm_{2})!}{m_{2}! q^{m_{2}}} M_{q}(n; m_{1}, m_{2}).

Our claim follows now from Proposition 3 upon little simplification. □

Relation (4.5) allows us to compute the subgroup numbers s_{q}(n; m_{1}, m_{2}) in terms of the geometrically defined quantities M_{q}(n; m_{1}, m_{2}). As our next result shows, it is enough to consider the latter numbers in the case when q | n.

Lemma 7. For an odd prime q and integers n, m_{1}, m_{2} with n > 0 and m_{1}, m_{2} ≥ 0, we have

M_{q}(n; m_{1}, m_{2}) = \frac{(2n − 2m_{1} − qm_{2})!}{(n − 2m_{1})!}M_{q}(qm_{2}; m_{1} + qm_{2} − n, m_{2}).  (4.6)

Proof. Given a graph in M_{q}(n; m_{1}, m_{2}), removal of all vertices not involved in some qgon together with all incident (red) edges leaves a graph in M_{q}(qm_{2}; m_{1} +qm_{2} −n, m_{2}). Conversely, starting from a graph in M_{q}(qm_{2}; m_{1} + qm_{2} − n, m_{2}), among the vertices involved in a q-gon there are qm_{2}−2(m_{1}+qm_{2}−n) = 2n−2m_{1}−qm_{2} vertices not incident with a red edge. From these vertices we choose n − qm_{2} vertices in \binom{2n−2m_{1}−qm_{2}}{n−qm_{2}} ways and, having chosen them, we connect each of them by means of a red edge to exactly one of a new set of vertices labelled {qm_{2} + 1, qm_{2} + 2, …, n}. This last step can be done in (n − qm_{2})! different ways. Hence, in total we obtain the relation (4.6). □

Since we shall make use of it later on, we point out that a combination of Lemmas 6 and 7 yields the relation

s_{q}(n; m_{1}, m_{2}) = \frac{n (2n − 2m_{1} − qm_{2})!}{q^{m_{2}}m_{2}! (n − qm_{2})! (n − 2m_{1})!}M_{q}(qm_{2}; m_{1} + qm_{2} − n, m_{2}). (4.7)

Corollary 8. (i) Let k and e be integers with k ≥ 1 and 0 ≤ e ≤ qk/2. Then the number of subgroups Δ in ℌ(q) of index qk and type

t(Δ) = (qk − 2e, 0, e − k + 1)  (4.8)

is

\frac{M_{q}(qk; e, k)}{q^{k−1}(k − 1)!}.

In particular, we have

M_{q}(2q(e − k)/(q − 2); e, \frac{2(e − k)}{q − 2}) = q^{\frac{2(e−k+1)−q}{q−2}} (\frac{2(e − k + 1) − q}{q − 2} )! f_{q}(\frac{2q(e − k)}{q − 2}),

e ≥ k + 1, e ≡ k (mod q − 2), (4.9)

where f_{q}(n) is the number of free subgroups of index n in ℌ(q).

(ii) For k ≥ 1, the number M_{q}(qk) of subgroups Δ ≤ ℌ(q) of index qk and with μ(Δ) = 0 is given by

M_{q}(qk) = \frac{1}{q^{k−1}(k − 1)!} ∑_{0≤e≤ \frac{qk}{2}} M_{q}(qk; e, k).  (4.10)

(iii) We have s_{q}(1) = s_{q}(2) = 1, and, for n > 2,

s_{q}(n) = ∑_{1≤k≤ \frac{n}{q}} ∑_{0≤e≤ \frac{n}{2}} \frac{n}{q^{k}k!} \binom{qk − 2e}{n − qk} M_{q}(qk; e, k).  (4.11)

Proof. Setting (ℌ(q) : Δ) = qk, λ(Δ) = qk − 2e, and μ(Δ) = 0 in Equation (3.3), we find that ν(Δ) = e − k + 1, so that t(Δ) agrees with (4.8). Hence, setting n = qk, m_{1} = e, and m_{2} = k in (4.7), the first part of (i) follows. The particular statement in (i) as well as Assertion (ii) are immediate consequences. Finally, Assertion (iii) results upon setting m_{1} = e + n − qk and m_{2} = k in (4.7) and summing over all e and k. □

4.2. Calculation of the numbers M_{q}(qk; e, k). Our next result provides a rather complicated looking but explicit formula for the quantities mentioned in the title. This formula in turn will enable us to determine the parity of the numbers M_{q}(n) for q ≥ 5.

Proposition 9. For k ≥ 1 and k − 1 ≤ e ≤ \frac{qk}{2}, we have

M_{q}(qk; e, k) = ∑_{γ=1}^{k} \frac{(−1)^{γ−1}}{γ}_{∑_{α_{1},...,α_{γ}≥0} ; α_{1}+···+α_{γ}=e}_{∑_{ρ_{1},...,ρ_{γ}≥1} ; ρ_{1}+···+ρ_{γ}=k}\binom{k}{ρ_{1}, …, ρ_{γ}} ∏_{i=1}^{γ} \frac{(qρ_{i})!}{2^{α_{i}}α_{i}! (qρ_{i} − 2α_{i})!}.

(4.12)

Proof. According to the definition of M_{q}(qk; e, k), we want to enumerate the elements of the set M_{q}(qk; e, k); that is, connected graphs consisting of k oriented blue q-gons and e (unoriented) red edges connecting vertices of the q-gons in such a way that no two red edges share a vertex.

Let the q-gons be denoted by P_{1}, P_{2}, …, P_{k} in order (according to their smallest vertex label), and let Π(k) be the set of all partitions of the standard set [k].

For a partition π ∈ Π(k) with γ blocks, we write M_{=π}(k; e_{1}, e_{2}, …, e_{γ}) for the number of ways to draw e = e_{1} + e_{2} + ⋯ + e_{γ} red edges among the vertices of the q-gons in such a way that no two edges share a vertex, and such that the connectivity structure of the resulting graph corresponds to the partition π; that is, if {i_{1}, i_{2}, …, i_{j}} is the l-th block of π (the blocks can be canonically ordered with respect to their smallest elements), the q-gons P_{i_{1}}, P_{i_{2}}, …, P_{i_{j}} form a connected component of the graph and, moreover, there are exactly e_{l} red edges in this component. Analogously, let M_{≤π}(k; e_{1}, e_{2}, …, e_{γ}) be the number of ways to draw e = e_{1} +e_{2} +⋯+e_{γ} red edges such that no two edges share a vertex and such that the connectivity structure of the resulting graph is described by a partition which is equal to or finer than π (in the usual partial order on set partitions; cf., for instance, [32, Example 3.1.1(d)]), and such that the same condition is satisfied with regard to the distribution of the red edges.

Clearly, for fixed e and π ∈ Π(k), and denoting by |π| the number of blocks of π, we have

∑_{e_{1}+···+e_{|π|}=e} M_{≤π}(k; e_{1}, e_{2}, …, e_{|π|}) = ∑_{σ≤π} ∑_{f_{1}+···+f_{|σ|}=e} M_{=σ}(k; f_{1}, f_{2}, …, f_{|σ|}).

Möbius inversion (cf. [31, Propositions 2–3]) yields

∑_{e_{1}+···+e_{|π|}=e} M_{=π}(k; e_{1}, e_{2}, …, e_{|π|}) = ∑_{σ≤π} ∑_{f_{1}+···+f_{|σ|}=e} μ(σ, π) M_{≤σ}(k; f_{1}, f_{2}, …, f_{|σ|}),

where μ denotes the Möbius function of the partition lattice Π(k). In particular, for

π = {[k]} =: ˆ1

(the maximum element in the partition lattice Π(k)), we have

M_{q}(qk; e, k) = M_{=ˆ1}(k; e) = ∑_{σ∈Π(k)} ∑_{f_{1}+···+f_{|σ|}=e} μ(σ, ˆ1) M_{≤σ}(k; f_{1}, f_{2}, …, f_{|σ|}). (4.13)

The numbers M_{≤σ}(k; f_{1}, f_{2}, …, f_{|σ|}) are easily determined: if {i_{1}, i_{2}, …, i_{j}} is the l-th block of σ, then this means that f_{l} edges are to be drawn arbitrarily among the vertices of the q-gons P_{i_{1}}, P_{i_{2}}, …, P_{i_{j}}, subject only to the restriction that no two edges are allowed to share a vertex. The number of ways to do this is

\frac{(jq)(jq − 1) ⋯ (jq − 2f_{l} + 1)}{2^{f_{l}}f_{l}!}.

Hence, if ρ_{1}, ρ_{2}, …, ρ_{|σ|} are the block sizes of σ, we have

M_{≤σ}(k; f_{1}, f_{2}, …, f_{|σ|}) = ∏_{i=1}^{|σ|} \frac{(qρ_{i})!}{2^{f_{i}}f_{i}! (qρ_{i} − 2f_{i})!}.

The Möbius function μ(σ, ˆ1) is known as well, namely one has

μ(σ, ˆ1) = (−1)^{|σ|−1}(|σ| − 1)!;

cf., for instance, [32, Example 3.10.4]. Finally, for fixed ρ_{1}, ρ_{2}, …, ρ_{γ} with ρ_{1} + ρ_{2} + ⋯ + ρ_{γ} = k, the number of ordered partitions of {1, 2, …, k} (here, “ordered” means that the order of the blocks matters), the block sizes of which are ρ_{1}, ρ_{2}, …, ρ_{γ}, is given by \binom{k}{ρ_{1},ρ_{2},...,ρ_{γ}}. Every partition in Π(k) with γ blocks giving rise to exactly γ! ordered partitions of {1, 2, …, k} by permuting the blocks, we must in the end divide by γ! in order to get rid of the overcounting. If everything is put together, (4.13) transforms into (4.12). □

Remark. A combination of (4.7) and Proposition 9 yields an explicit formula for the number s_{q}(n; m_{1}, m_{2}) of index n subgroups in ℌ(q) of representation type ( \begin{matrix}m_{1} & n−2m_{1} \\ m_{2} & n−qm_{2} \end{matrix} ).

Although this is not apparent from (4.12), the number M_{q}(qk; e; k) admits a simple product formula representation in the case when e = k −1; that is, when the underlying graph formed by the red edges and the q-gons (collapsed to vertices) is a tree. Rather embarrassingly, we have not been able to deduce Formula (4.14) below directly from the formula of Proposition 9.

Proposition 10. We have M_{q}(q; 0, 1) = 1, and for k ≥ 2,

M_{q}(qk; k − 1, k) = q^{k}((q − 1)k)((q − 1)k − 1) ⋯ (qk − 2k + 3),  (4.14)

where an empty product must be interpreted as 1.

Proof. The proof consists in converting the problem of counting the elements of M_{q}(qk; k − 1, k) into a counting problem for certain planar maps. The latter problem has already been solved by Goulden and Jackson in [11] in connection with the computation of connection coefficients for the symmetric group.

Indeed, recall that the set M_{q}(qk; k −1, k) consists only of connected graphs. Thus, the only way to generate an element of M_{q}(qk; k − 1, k) out of k blue q-gons and k − 1 red edges is by starting from a tree with vertices labelled v_{1}, v_{2}, …, v_{k} (and, hence, k − 1 edges, which we assume to be red), blowing up the vertices of the tree to q-gons, and gluing one end of a red edge originally connecting v_{i} and v_{j} to a vertex of the polygon corresponding to v_{i}, the other to a vertex of the polygon corresponding to v_{j}, in such a way that no two red edges share a vertex. Finally, we label the vertices of the polygon corresponding to v_{i} by qi − q + 1, …, qi − 1, qi in circular order.

Such an object can be embedded canonically in the plane without crossings of edges by requiring that all polygons are embedded with clockwise circular labelling. Deleting all labels and marking the vertex originally labelled by 1, we obtain a certain set M̃(q, k) of graphs in which one vertex is marked. Figure 1.a shows such a graph in M̃(3, 5); there, the marked vertex is indicated by a black square, red edges are indicated as undirected edges, while the blue edges are the directed edges. We observe that

M_{q}(qk; k − 1, k) = q^{k−1}(k − 1)! |M̃(q, k)|,

[figure: ■; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; 3; 4; 2; 1; 9; 5; 8; 7; 6; 14; 10; 15; 13; 11; 12]

a. An element of M̃(3, 5) b. The labelling of vertices

Figure 1

since, starting with an object from M̃(q, k), we have (k − 1)! possibilities to decide from which set of the form {qi − q + 1, …, qi − 1, qi} to take the labels for a given unmarked q-gon, and subsequently, for each of the k − 1 unmarked q-gons, we have q possibilities where to start the clockwise labelling. The problem of counting the elements of M_{q}(qk; k − 1, k) has thus been reduced to the problem of finding the cardinality of the set M̃(q, k).

To make the link with [11], given an element of M̃(q, k), we translate it into a factorization

(1, 2, …, qk) = π_{1} ∘ π_{2}  (4.15)

of the “long” cycle (1, 2, …, qk) into the product of two permutations in S_{qk}, π_{1} consisting of k cycles of length q, and π_{2} consisting of k − 1 cycles of length 2 and fixed points otherwise. To explain this translation, consider Figure 1, which illustrates an example for q = 3 and k = 5. Given an element of M̃(q, k), we determine labels for all vertices in the following way: the marked vertex is labelled 1. Now we suppose that we already have labelled i vertices by 1, 2, …, i. Placing ourselves in the vertex labelled i, v_{i} say, there are two possibilities: either this vertex is incident to a red edge or not. In the first case, we move from v_{i} along the red edge, arriving in the vertex u, say, and then continue along the blue edge emanating from u. The vertex which we reach at the other end of this blue edge is labelled i + 1. In the second case, we simply move along the blue edge emanating from v_{i}, and we label the vertex which we reach at the other end of this blue edge by i + 1. Figure 1.b shows the resulting labelling in our example. From the labelling we can read off a factorization (4.15) by interpreting a q-gon with vertices labelled j_{1}, j_{2}, …, j_{q} in clockwise order as the cycle (j_{1}, j_{2}, …, j_{q}) and letting π_{1} be the product of all these cycles, and by interpreting a red edge with end vertices j_{1}, j_{2} as the transposition (j_{1}, j_{2}) and letting π_{2} be the product of all these transpositions. In this way, our example in Figure 1 corresponds to the factorization

(1, 2, …, 15) = π_{1} ∘ π_{2},

where

π_{1} = (1, 5, 9)(2, 3, 4)(6, 7, 8)(10, 14, 15)(11, 12, 13)

and

π_{2} = (1, 4)(5, 8)(9, 15)(10, 13).

It is not difficult to see that this translation defines a bijection between elements of M̃(q, k) and factorizations (4.15) where the disjoint cycle factorization of π_{1} consists of k cycles of length q, and where the disjoint cycle factorization of π_{2} consists of k − 1 cycles of length 2 and fixed points otherwise. The solution of the enumeration problem for these objects is then found in [11, Theorem 3.2] by specializing n = qk, m = 2, α_{1} = (q^{k}), and α_{2} = (2^{k−1}, 1^{qk−2k+2}). □

4.3. The parity of the numbers M_{q}(n). Let I_{n} denote the number of solutions of the equation x^{2} = 1 in the symmetric group S_{n}. It is well known that

I_{n} = ∑_{α≥0} \frac{n!}{2^{α}α! (n − 2α)!},  (4.16)

if we set \frac{1}{n!} = 0 for integers n < 0 in accordance with the behaviour of the gamma function; cf. [5, Equation (4)]. The exact value of the 2-adic valuation of I_{n} has been determined by Ochiai [30, Sec. 3.2]. The result is that

v_{2}(I_{n}) = \begin{cases}n/4, & if n ≡ 0 (mod 4), \\ (n − 1)/4, & if n ≡ 1 (mod 4), \\ (n + 2)/4, & if n ≡ 2 (mod 4), \\ (n + 5)/4, & if n ≡ 3 (mod 4), \end{cases}

where, as usual, v_{2}(α) stands for the 2-adic valuation of α. For our purposes, the weaker estimate

v_{2}(I_{n}) ≥ \begin{cases}n/4, & if n ≢ 1 (mod 4), \\ (n − 1)/4, & if n ≡ 1 (mod 4). \end{cases}  (4.17)

suffices, which already follows from [5, Theorem 10].

The following auxiliary result (Lemma 11), whose proof will be given in Section A.1 in the appendix, is needed to bound the 2-adic valuation of the numbers M_{q}(qk) in the case when q ≥ 5; see Proposition 12.

Lemma 11. If ρ_{1} ≡ ρ_{2} ≡ ⋯ ≡ ρ_{α} ≡ 1 (mod 4), then

v_{2} (\binom{ρ_{1} + ρ_{2} + ⋯ + ρ_{α}}{ρ_{1}, ρ_{2}, …, ρ_{α}}) ≥ v_{2}(α!).  (4.18)

If ρ_{1} ≡ ρ_{2} ≡ ⋯ ≡ ρ_{α} ≡ 3 (mod 4), then

v_{2} (\binom{ρ_{1} + ρ_{2} + ⋯ + ρ_{α}}{ρ_{1}, ρ_{2}, …, ρ_{α}}) ≥ v_{2}((3α)!) − α.  (4.19)

Proposition 12. For a prime number q ≥ 5 and an integer k ≥ 1, the number M_{q}(qk) of subgroups in ℌ(q) of index qk and with μ(Δ) = 0 satisfies

v_{2}(M_{q}(qk)) ≥ \frac{qk − 1}{4} − v_{2}((k − 1)!) − ⌊log_{2} k⌋ .  (4.20)

In particular, M_{q}(qk) is even for q ≥ 5 and k ≥ 1.

Proof. By Part (ii) of Corollary 8, Proposition 9, and (4.16), we have

M_{q}(qk) = \frac{1}{q^{k−1}(k − 1)!} ∑_{0≤e≤ \frac{qk}{2}} ∑_{γ=1}^{k} \frac{(−1)^{γ−1}}{γ}

·_{∑_{α_{1},...,α_{γ}≥0} ; α_{1}+···+α_{γ}=e} _{∑_{ρ_{1},...,ρ_{γ}≥1} ; ρ_{1}+···+ρ_{γ}=k}\binom{k}{ρ_{1}, …, ρ_{γ}} ∏_{i=1}^{γ} \frac{(qρ_{i})!}{2^{α_{i}}α_{i}! (qρ_{i} − 2α_{i})!}

= ∑_{γ=1}^{k} _{∑_{ρ_{1},...,ρ_{γ}≥1} ; ρ_{1}+···+ρ_{γ}=k} \frac{1}{q^{k−1}(k − 1)!} \frac{(−1)^{γ−1}}{γ} \binom{k}{ρ_{1}, …, ρ_{γ}} ∏_{i=1}^{γ} I_{qρ_{i}}.  (4.21)

For fixed γ and ρ_{1}, ρ_{2}, …, ρ_{γ}, we bound the 2-adic valuation of the corresponding summand in the sum in the last line, S(γ; ρ_{1}, …, ρ_{γ}) say. Namely, without loss of generality, let ρ_{1}, ρ_{2}, …, ρ_{α} be the ρ_{j}’s for which qρ_{j} ≡ 1 (mod 4). Then we have

\binom{k}{ρ_{1}, …, ρ_{γ}} = \binom{ρ_{1} + ρ_{2} + ⋯ + ρ_{α}}{ρ_{1}, …, ρ_{α}}\binom{k}{ρ_{1} + ⋯ + ρ_{α}, ρ_{α+1}, …, ρ_{γ}},

and hence, by a combination of (4.17) and Lemma 11,

v_{2}(S(γ; ρ_{1}, …, ρ_{γ}))

≥ −v_{2}((k − 1)!) − ⌊log_{2} γ⌋ + v_{2} (\binom{ρ_{1} + ρ_{2} + ⋯ + ρ_{α}}{ρ_{1}, …, ρ_{α}}) + ∑_{i=1}^{γ} v_{2}(I_{qρ_{i}})

≥ −v_{2}((k − 1)!) − ⌊log_{2} k⌋ + \frac{max\{α − 1, 0\}}{2} + \frac{q(ρ_{1} + ρ_{2} + ⋯ + ρ_{γ}) − α}{4}

≥ −v_{2}((k − 1)!) − ⌊log_{2} k⌋ + \frac{max\{α − 2, −α\}}{4} + \frac{qk}{4} .

The 2-adic valuation of M_{q}(qk) is at least the minimum of the expression displayed in the last line taken over all possible choices of α. This minimum is exactly the expression on the right-hand side of (4.20).

To see that the right-hand side of (4.20) is always positive for q ≥ 5, one observes that v_{2}((k − 1)!) ≤ k − 2 as long as k ≥ 2, and thus

v_{2}(M_{q}(qk)) ≥ \frac{(q − 4)k + 7}{4} − ⌊log_{2} k⌋ ≥ \frac{k + 7}{4} − ⌊log_{2} k⌋ > 0,

provided that k ≥ 2. For k = 1, it can be verified directly that the right-hand side of (4.20) is positive. □

Proposition 12 leaves open the case when q = 3, which is settled in Proposition 15 below, making use of results in [33]. The following auxiliary result (Lemma 13) will be used in the proof of Proposition 15; it also bears on the parity of the numbers M_{q}(qk; k − 1, k)/(k − 1)! in the case when q is a Fermat prime; see Corollary 14. The (straightforward but somewhat lengthy) proof of Lemma 13 is recorded in Section A.2 in the appendix.

Lemma 13. Let λ, k ≥ 1 be integers. Then

\binom{2^{λ}k + 1}{k − 1} ≡ 1 (mod 2) if, and only if,

k = \frac{2^{λσ} − 1}{2^{λ} − 1} or k = \frac{2^{λσ+1} − 2}{2^{λ} − 1} for some σ ≥ 1. (4.22)

Corollary 14. Let q be a Fermat prime, and let k be a positive integer. Then

\frac{M_{q}(qk; k − 1, k)}{(k − 1)!} ≡ 1 (mod 2)

if, and only if, k = \frac{(q − 1)^{σ} − 1}{q − 2} or k = 2\frac{(q − 1)^{σ} − 1}{q − 2} for some σ ≥ 1.

Proof. For k ≥ 2, Equation (4.14) gives

M_{q}(qk; k − 1, k) = q^{k} ((q − 1)k + 1)((q − 1)k) ⋯ ((q − 1)k − k + 3) \frac{1}{(q − 1)k + 1}

so that, modulo 2,

\frac{M_{q}(qk; k − 1, k)}{(k − 1)!} = q^{k}\binom{(q − 1)k + 1}{k − 1}\frac{1}{(q − 1)k + 1} ≡ \binom{(q − 1)k + 1}{k − 1},

a congruence which is also seen to hold for k = 1. Since q is a Fermat prime, we have q − 1 = 2^{λ} for some λ ≥ 1, and our claim follows from Lemma 13. □

Proposition 15. For k ≥ 1, the number M_{3}(3k) of subgroups Δ of index 3k in the modular group ℌ(3) = PSL_{2}(ℤ) with the property that μ(Δ) = 0, is even.

Proof. Our starting point is again Corollary 8 (ii), more precisely, the fact that

M_{3}(3k) = 3^{−(k−1)} ∑_{k−1≤e≤ \frac{3k}{2}} \frac{M_{3}(3k; e, k)}{(k − 1)!}, k ≥ 1.  (4.23)

Concerning the summands occurring on the right-hand side of (4.23), Stothers shows the following:

\frac{M_{3}(3k; k − 1, k)}{(k − 1)!} = \frac{3^{k} (2k)!}{(k − 1)! (k + 2)!}, k ≥ 1,  (4.24)

\frac{M_{3}(3k; k, k)}{(k − 1)!} = 2^{2k−2} 3^{k}, k ≥ 1,  (4.25)

\frac{M_{3}(6ℓ; 3ℓ, 2ℓ)}{(2ℓ − 1)!} = 3^{2ℓ−1} f_{3}(6ℓ), ℓ ≥ 1,  (4.26)

and

\frac{M_{3}(3k; e, k)}{(k − 1)!} = 2^{3k−2e−1} 3^{k} k \frac{∏_{ℓ=0}^{3k−2e−2}(3k − e − 2ℓ − 2)}{(3k − 2e)!} f_{3}(6(e − k)), k < e < \frac{3k}{2} ,

(4.27)

where f_{3}(n) is the number of free subgroups of index n in ℌ(3), and the product in (4.27) has to be evaluated as 1 if 2e = 3k − 1; cf. Propositions 1.7 and 1.8 and Formula (3) in [33]. Of course, Equation (4.24) also follows from our Proposition 10. By (4.27) and Legendre’s formula for the p-adic valuation of factorials, we have,

v_{2}(\frac{M_{3}(3k; e, k)}{(k − 1)!}) = (𝔰_{2}(3k − 2e) − 1) + v_{2}(k) + v_{2}(f_{3}(6(e − k)))

+ ∑_{ℓ=0}^{3k−2e−2} v_{2}(3k − e − 2ℓ − 2), k < e < \frac{3k}{2} , (4.28)

where 𝔰_{2}(x) is the sum of digits in the binary expansion of x. Further, it is known that f_{3}(6λ) is odd if, and only if, λ + 1 is a non-trivial 2-power; cf. [33, Cor. 1.11] or [21, Proposition 6]. Using this fact together with (4.28), one finds that, for k < e < \frac{3k}{2},

\frac{M_{3}(3k; e, k)}{(k − 1)!} ≡ 1 (mod 2) if, and only if,

e = 2^{σ+1} + 2^{σ} − 2 and k = 2^{σ+1} − 1 for some σ ≥ 1. (4.29)

Indeed, since 2e < 3k, we have 𝔰_{2}(3k − 2e) ≥ 1; hence, all summands on the right-hand side of (4.28) are non-negative. For this right-hand side to vanish, it is thus necessary and sufficient that (i) k is odd, (ii) e − k + 1 = 2^{σ} for some σ ≥ 1, and (iii) 3k − 2e = 2^{λ} for some λ ≥ 0. It follows from (ii) and (iii) that k = 2^{σ+1} + 2^{λ} − 2, which is odd only for λ = 0, whence (4.29).

The parity behaviour of f_{3}(6λ) also gives that

\frac{M_{3}(6ℓ; 3ℓ, 2ℓ)}{(2ℓ − 1)!} ≡ 1 (mod 2) if, and only if, ℓ + 1 = 2^{σ} for some σ ≥ 1.  (4.30)

From (4.23)–(4.25), (4.29), and (4.30), we deduce that, modulo 2,

M_{3}(3k) = \frac{3(2k)!}{(k − 1)! (k + 2)!} + 3 · 2^{2k−2}

+ ∑_{k<e< \frac{3k}{2}} \frac{M_{3}(3k; e, k)}{3^{k−1} (k − 1)!} + \begin{cases}\frac{M_{3}(3k; \frac{3k}{2} , k)}{3^{k−1} (k − 1)!}, & 2 | k \\ 0, & 2 ∤ k \end{cases} \}

≡ \binom{2k + 1}{k − 1} + \begin{cases}1; & k = 2^{τ} − 1, τ ≥ 2 \\ 0; & otherwise \end{cases}\} + \begin{cases}1; & k = 2(2^{σ} − 1), σ ≥ 1 \\ 0; & otherwise, \end{cases}\}

provided that k ≥ 2. By Lemma 13 with λ = 1, we have

\binom{2k + 1}{k − 1} ≡ 1 (mod 2) if, and only if, k = 2^{σ} − 1 or k = 2(2^{σ} − 1) for some σ ≥ 1.

Combining the last two assertions, we find that

M_{3}(3k) ≡ 0 mod 2, k ≥ 2.

Finally,

M_{3}(3) = M_{3}(3; 0, 1) + M_{3}(3; 1, 1) = 1 + 3 ≡ 0 mod 2,

and the proof is complete. □

Putting together the observation that M_{q}(n) = 0 whenever q ∤ n (see the start of this section) with Propositions 12 and 15, we obtain the main result of this section.

Theorem 16. For each odd prime q and every integer n ≥ 1, the number M_{q}(n) of index n subgroups Δ in ℌ(q) with the property that μ(Δ) = 0, is even.

5. Generalized parity patterns of Hecke groups

The main result of this section computes the parity behaviour of the generalized subgroup numbers of ℌ(q), with q an odd prime, in the case when H is of even order; see Theorem 24. Our interest in this computation stems from the fact that, in this setting, s_{q}^{H}(n) := s_{ℌ(q)}^{H}(n) ≡ N_{q}(n) (mod 2), where the N_{q}(n)’s enter into the mod 2 calculation of s_{Γ_{m}(q)}^{H}(n) via Proposition 1. Indeed, writing

𝔘 ≅ C_{2}^{∗λ(𝔘)} ∗ C_{q}^{∗μ(𝔘)} ∗ F_{ν(𝔘)}

for a subgroup 𝔘 in ℌ(q), in accordance with Kurosh’s subgroup theorem, we have

s_{q}^{H}(n) = ∑_{(ℌ(q):𝔘)=n} | Hom(C_{2}, H)|^{λ(𝔘)} · | Hom(C_{q}, H)|^{μ(𝔘)} · |H|^{ν(𝔘)}.

By Frobenius’ theorem (cf. [9] or [12, Theorem 9.1.2]) concerning the equation x^{n} = 1 in a finite group, the assumption |H| ≡ 0 (mod 2) implies that | Hom(C_{2}, H)| is even. Furthermore, we have

| Hom(C_{q}, H)| = 1 + (q − 1) × (number of subgroups U ≅ C_{q} in H) ≡ 1 mod 2. (5.1)

Hence, if |H| is even, it follows that, modulo 2,

s_{q}^{H}(n) ≡ _{∑_{𝔘} ; (ℌ(q):𝔘)=n ; λ(𝔘)=ν(𝔘)=0}1 = N_{q}(n),  (5.2)

as claimed.

On the other hand, it was shown in particular in [23] that — just as subgroup numbers are connected with the enumeration of permutation representations — the generalized subgroup numbers s_{Γ}^{H}(n) of a finitely generated group Γ are related to the function | Hom(Γ, H ≀ S_{n})| counting monomial representations of Γ via the identity

∑_{n=0}^{∞} | Hom(Γ, H ≀ S_{n})|\frac{z^{n}}{|H|^{n}n!} = exp (\frac{1}{|H|} ∑_{n=1}^{∞} s_{Γ}^{H}(n)\frac{z^{n}}{n} ),  (5.3)

or, what comes to the same thing, via the recurrence relation

n |H| h_{Γ}^{H}(n) = ∑_{k≥1} s_{Γ}^{H}(k)h_{Γ}^{H}(n − k), n ∈ ℤ,  (5.4)

where

h_{Γ}^{H}(n) := \begin{cases}| Hom(Γ, H ≀ S_{n})|/(|H|^{n}n!), & n ≥ 0 \\ 0, & n < 0. \end{cases}

This follows from [23, Cor. 1] by setting Σ = ∅, Λ = ℕ, M = ℕ_{0}, and replacing the variable z by z/|H|. For a (relatively) untechnical account of the theory of generalized permutation representations, which gives rise (among other things) to Formula (5.3), the reader may consult the survey papers [24] and [25]. Introducing the series

H_{Γ}^{H}(z) := ∑_{n=0}^{∞} | Hom(Γ, H ≀ S_{n})|\frac{z^{n}}{|H|^{n}n!}

and

S_{Γ}^{H}(z) := ∑_{n=0}^{∞} s_{Γ}^{H}(n + 1)z^{n},

Identity (5.3) takes the form

H_{Γ}^{H}(z) = exp (\frac{1}{|H|} ∫ S_{Γ}^{H}(z) dz).  (5.5)

In view of the preceding observations, our next goal will be to derive a linear differential equation with polynomial coefficients for the generating function H_{ℌ(q)}^{H}(z). Using Relation (5.5) together with the Faà di Bruno formula (see (A.18) below), this linear differential equation will give rise to a Riccati-type differental equation for the generating function S_{ℌ(q)}^{H}(z). It is the latter differential equation that we are actually interested in; see (5.26).

5.1. A system of linear differential equations for generating functions related to H_{ℌ(q)}^{H}(z). The starting point for our computations concerning the series H_{ℌ(q)}^{H}(z) is the observation that, by the universal mapping property of free products,

| Hom(ℌ(q), H ≀ S_{n})| = | Hom(C_{2}, H ≀ S_{n})| · | Hom(C_{q}, H ≀ S_{n})|.  (5.6)

Setting h := |H|, a := | Hom(C_{2}, H)|, b := | Hom(C_{q}, H)|,

α_{n} := \begin{cases}| Hom(C_{2}, H ≀ S_{n})|, & n ≥ 0 \\ 0, & n < 0, \end{cases}

and

β_{n} := \begin{cases}| Hom(C_{q}, H ≀ S_{n})|, & n ≥ 0 \\ 0, & n < 0, \end{cases}

Equation (5.4) specializes to the relations

α_{n+1} = aα_{n} + hnα_{n−1}, n ≠ −1  (5.7)

and

β_{n+1} = bβ_{n} + h^{q−1} \frac{n!}{(n − q + 1)!}β_{n−q+1}, n ≠ −1,  (5.8)

where we use the same convention concerning \frac{1}{n!} as in Formula (4.16). For n, k ∈ ℤ, let

A_{k}(n) := \frac{α_{n} β_{n−k}}{h^{n−k} (n − k)!},

still making use of the same convention concerning \frac{1}{n!}, and set

F_{k}(z) := ∑_{n∈ℤ}A_{k}(n)z^{n}.

The reader should note that, in view of (5.6), we have F_{0}(z) = H_{ℌ(q)}^{H}(z).

Multiplying (5.7) by β_{n−k}/(h^{n−k}(n − k)!) and (5.8) by α_{n+k}/(h^{n}n!), we obtain the relations

A_{k+1}(n + 1) = aA_{k}(n) + hnA_{k−1}(n − 1), n, k ∈ ℤ, k ≥ 0,  (5.9)

respectively

h(n + 1)A_{k−1}(n + k) = bA_{k}(n + k) + A_{k+q−1}(n + k), n, k ∈ ℤ.  (5.10)

Multiplication by z^{n+1} and summation over n ∈ ℤ, transforms Equation (5.9) into the relation

F_{k+1}(z) = azF_{k}(z) + hz^{2}F_{k−1}(z) + hz^{3}F′_{k−1}(z), k ≥ 0,  (5.11)

while multiplication by z^{n+k} and summation over n ∈ ℤ turns (5.10) into

hzF′_{k−1}(z) = h(k − 1)F_{k−1}(z) + bF_{k}(z) + F_{k+q−1}(z), k ∈ ℤ.  (5.12)

Clearly, by iterating Relation (5.11), we can express every function F_{k} with k ≥ 0 in terms of derivatives of F_{0} and F_{1} alone; more precisely, define integral coefficient systems (c_{k}^{(μ)}) and (d_{k}^{(ν)}) for k ≥ 0 and 0 ≤ μ ≤ ⌊\frac{k}{2}⌋, respectively k ≥ 1 and 0 ≤ ν ≤ ⌊\frac{k−1}{2}⌋, via

c_{0}^{(0)} = 1, c_{1}^{(0)} = 0, c_{2}^{(0)} = h, c_{2}^{(1)} = 1,
d_{1}^{(0)} = 1, d_{2}^{(0)} = a,

c_{k+1}^{(μ)} = \begin{cases}ac_{k}^{(0)} + hkc_{k−1}^{(0)}, & μ = 0 \\ ac_{k}^{(μ)} + h(k + μ)c_{k−1}^{(μ)} + c_{k−1}^{(μ−1)}, & 1 ≤ μ ≤ ⌊\frac{k−1}{2}⌋ \\ c_{k−1}^{( \frac{k−1}{2} )}, & μ = ⌊\frac{k+1}{2}⌋, k odd \\ ac_{k}^{(k/2)} + c_{k−1}^{( \frac{k−2}{2} )}, & μ = ⌊\frac{k+1}{2}⌋, k even \end{cases}\} (k ≥ 2),

and

d_{k+1}^{(ν)} = \begin{cases}ad_{k}^{(0)} + h(k − 1)d_{k−1}^{(0)}, & ν = 0 \\ ad_{k}^{(ν)} + h(k + ν − 1)d_{k−1}^{(ν)} + d_{k−1}^{(ν−1)}, & 1 ≤ ν ≤ ⌊\frac{k−2}{2}⌋ \\ ad_{k}^{( \frac{k−1}{2} )} + d_{k−1}^{( \frac{k−3}{2} )}, & ν = ⌊\frac{k}{2}⌋, k odd \\ d_{k−1}^{( \frac{k−2}{2} )}, & ν = ⌊\frac{k}{2}⌋, k even \end{cases}\} (k ≥ 2).

Then we have the following.

Lemma 17. With (c_{k}^{(μ)}) and (d_{k}^{(ν)}) as above,

F_{k}(z) = ∑_{μ=0}^{⌊ \frac{k}{2} ⌋} c_{k}^{(μ)}h^{μ}z^{k+μ}F_{0}^{(μ)}(z) + ∑_{ν=0}^{⌊ \frac{k−1}{2} ⌋} d_{k}^{(ν)}h^{ν}z^{k+ν−1}F_{1}^{(ν)}(z), k ≥ 0.  (5.13)

The proof of Lemma 17, which, again, is straightforward but somewhat technical, will be given in Section A.3 in the appendix.

For later usage, we record evaluations of c_{k}^{(μ)} and d_{k}^{(ν)} modulo 2 as given by the following two lemmas.

Lemma 18. For h ≡ 0 (mod 2), we have

c_{k}^{(μ)} ≡ δ_{2μ,k} mod 2, μ ≥ 0, k ≥ 2μ,  (5.14)
d_{k}^{(ν)} ≡ δ_{2ν+1,k} mod 2, ν ≥ 0, k ≥ 2ν + 1,  (5.15)

where δ_{s,t} is the Kronecker delta.

Proof. As we observed at the start of this section, the assumption h ≡ 0 mod 2 implies that a ≡ 0 mod 2. Hence, the definition of c_{k}^{(μ)} simplifies modulo 2 to

c_{0}^{(0)} ≡ c_{2}^{(1)} ≡ 1
c_{1}^{(0)} ≡ c_{2}^{(0)} ≡ 0

c_{k}^{(μ)} ≡ \begin{cases}0, & μ = 0 \\ c_{k−2}^{(μ−1)}, & μ ≥ 1 \end{cases}\} (k ≥ 3).

We now argue by induction on k. For k ≤ 2, Formula (5.14) clearly holds. Supposing that (5.14) holds true for k < K with some K ≥ 3, the inductive hypothesis gives

c_{K}^{(μ)} ≡ \begin{cases}0, & μ = 0 \\ δ_{2(μ−1),K−2}, & μ ≥ 1 \end{cases}\} = δ_{2μ,K} mod 2, μ ≤ ⌊\frac{K}{2} ⌋,

as required. The proof of Formula (5.15) is similar. □

Lemma 19. For h ≡ 1 (mod 2), we have

c_{k}^{(μ)} ≡ \begin{cases}δ_{2μ,k} + δ_{2μ+1,k}; & if μ is odd \\ δ_{2μ,k} + δ_{2μ+2,k} + δ_{2μ+3,k}; & if μ is even \end{cases}\} mod 2, μ ≥ 0, k ≥ 2μ, (5.16)

d_{k}^{(ν)} ≡ \begin{cases}δ_{2μ+1,k}; & if μ is odd \\ δ_{2μ+1,k} + δ_{2μ+2,k}; & if μ is even \end{cases}\} mod 2, ν ≥ 0, k ≥ 2ν + 1,  (5.17)

where, again, δ_{s,t} is the Kronecker delta.

Proof. The assumption h ≡ 1 (mod 2) implies that a = 1. The rest of the proof is similar to the proof of the preceding lemma, and is omitted. □

Multiplying (5.12) for k = 0 by z^{2}, substituting (5.11) with k = 0, and computing F_{q−1}(z) by means of Lemma 17, we find that

(d_{q−1}^{(0)}z^{q} − 1)F_{1}(z) + ∑_{ν=1}^{\frac{q−3}{2}} d_{q−1}^{(ν)}h^{ν}z^{q+ν}F_{1}^{(ν)}(z) = −(az + bz^{2} + c_{q−1}^{(0)}z^{q+1})f(z)

− ∑_{μ=1}^{\frac{q−1}{2}} c_{q−1}^{(μ)}h^{μ}z^{q+μ+1}f^{(μ)}(z) (5.18)

with f(z) := F_{0}(z). Next, taking k = 1 in (5.12) and computing F_{q}(z) by means of Lemma 17, we obtain the equation

(d_{q}^{(0)}z^{q−1} + b)F_{1}(z) + ∑_{ν=1}^{\frac{q−1}{2}} d_{q}^{(ν)}h^{ν}z^{q+ν−1}F_{1}^{(ν)}(z) = −c_{q}^{(0)}z^{q}f(z) − h(c_{q}^{(1)}z^{q+1} − z)f′(z)

− ∑_{μ=2}^{\frac{q−1}{2}} c_{q}^{(μ)}h^{μ}z^{q+μ}f^{(μ)}(z). (5.19)

Similarly, combining Equation (5.12) for k = 2, 3, …, q − 2 with Lemma 17, we obtain further equations, which together with (5.18) and (5.19) form a system of q − 1 linear equations over the field ℚ((z)) in the variables F_{1}^{(0)}(z), F_{1}^{(1)}(z), …, F_{1}^{(q−2)}(z). More specifically, we find that

Δ̄_{q} ( F_{1}^{(0)}(z) ; ⋮ ; F_{1}^{(q−2)}(z)) = ( b_{0}(z) ; ⋮ ; b_{q−2}(z)) ,  (5.20)

where Δ̄_{q} = (h^{λ}ω_{κ,λ})_{0≤κ,λ≤q−2}, with ω_{κ,λ} and b_{κ}(z) given explicitly in terms of b, h, the c_{k}^{(ν)}’s, the d_{k}^{(ν)}’s, and the derivatives of f(z), as described in Section A.4 in the appendix.

5.2. The determinant of the system, and its minors. Denote by _{0}Δ̄_{q} the matrix obtained from Δ̄_{q} by replacing the 0-th column with the right-hand side of (5.20), and by _{0}Δ_{q} the corresponding matrix obtained from Δ_{q} := (ω_{κ,λ}) via the same operation. Then det Δ̄_{q} = h^{\binom{q−1}{2}} det Δ_{q}, det_{0}Δ̄_{q} = h^{\binom{q−1}{2}} det_{0}Δ_{q}, and, according to Cramer’s Rule and Laplace’s expansion theorem,

F_{1}(z) = \frac{det_{0}Δ_{q}}{det Δ_{q}} = (det Δ_{q})^{−1} ∑_{κ=0}^{q−2}(−1)^{κ}(det Δ_{κ,0})b_{κ}(z),

where Δ_{κ,0} is the matrix obtained from Δ_{q} by deleting the κ-th row and 0-th column. We are assuming here, of course, that det Δ_{q} ≠ 0, a fact which follows, among other things, from our next two auxiliary results, whose proofs will be given in Sections A.5 and A.6 in the appendix, respectively.

Lemma 20. For h ≡ 0 (mod 2), we have

(i) det Δ_{q} ≡ det Δ_{0,0} ≡ z^{\frac{3q^{2}−11q+12}{2}} mod 2,
(ii) det Δ_{κ,0} ≡ 0 mod 2, 1 ≤ κ ≤ q − 2.

Lemma 21. For h ≡ 1 (mod 2), we have

(i) det Δ_{q} ≡ \begin{cases}z^{\frac{3q^{2}−11q+12}{2}} ; & if q ≡ 1 (mod 4) \\ z^{\frac{3q^{2}−11q+12}{2}} + z^{\frac{3q^{2}−8q+9}{2}} ; & if q ≡ 3 (mod 4) \end{cases}\} mod 2;

(ii) det Δ_{0,0} ≡ z^{\frac{3q^{2}−11q+12}{2}} (mod 2), det Δ_{1,0} ≡ 0 (mod 2), and for 2 ≤ κ ≤ q − 2,

det Δ_{κ,0} ≡ \begin{cases}0; & if κ ≥ 2 and q ≡ 1 (mod 4) \\ 0; & if κ ≡ 1 (mod 4) and q ≡ 3 (mod 4) \\ z^{\frac{3q^{2}−8q+5−12κ′}{2}} ; & if κ = 4κ′ + 2 and q ≡ 3 (mod 4) \\ z^{\frac{3q^{2}−8q+3−12κ′}{2}} ; & if κ = 4κ′ + 3 and q ≡ 3 (mod 4) \\ z^{\frac{3q^{2}−8q+1−12κ′}{2}} ; & if κ = 4κ′ + 4 and q ≡ 3 (mod 4) \end{cases}\} mod 2.

5.3. A functional equation for S_{ℌ(q)}^{H}(z). The following auxiliary result, whose proof is recorded in Section A.7 in the appendix, is concerned with computing the expressions

h^{ν}(\frac{d^{ν}}{dz^{ν}} H_{Γ}^{H}(z))/H_{Γ}^{H}(z), ν ∈ ℕ_{0}  (5.21)

over ℤ and modulo 2 in terms of the series S_{Γ}^{H}(z). (The reader should recall (5.5).)

Lemma 22. Let Γ be a finitely generated group, H a finite group, and let h = |H|.

(i) For each ν ∈ ℕ_{0}, we have

h^{ν}(\frac{d^{ν}}{dz^{ν}} H_{Γ}^{H}(z))/H_{Γ}^{H}(z)

= _{∑_{π_{1},...,π_{ν}≥0} ; π_{1}+2π_{2}+···+νπ_{ν}=ν}h^{ν−π_{1}−···−π_{ν}} \frac{ν!}{∏_{j≥1}(j!)^{π_{j}}π_{j}!} ∏_{j≥1} ((S_{Γ}^{H}(z))^{(j−1)})^{π_{j}}, (5.22)

and the coefficients ν!/(∏_{j≥1}(j!)^{π_{j}}π_{j}!) are integers.

(ii) For each ν ∈ ℕ_{0}, the series (5.21) is an integral power series in z, and satisfies the congruence

h^{ν}(\frac{d^{ν}}{dz^{ν}} H_{Γ}^{H}(z))/H_{Γ}^{H}(z) ≡ ∑_{μ=0}^{⌊ \frac{ν}{2} ⌋} h^{μ}\binom{ν}{2μ}((S_{Γ}^{H}(z))′)^{μ}(S_{Γ}^{H}(z))^{ν−2μ} mod 2. (5.23)

In particular, if h ≡ 0 (mod 2), then

h^{ν}(\frac{d^{ν}}{dz^{ν}} H_{Γ}^{H}(z))/H_{Γ}^{H}(z) ≡ (S_{Γ}^{H}(z))^{ν} mod 2, ν ≥ 0.  (5.24)

Write

((det Δ_{q})^{−1})^{(ν)} = \frac{Θ_{ν}(z)}{(det Δ_{q})^{ν+1}} , ν ≥ 0,

where {Θ_{ν}(z)}_{ν≥0} is the family of polynomials in z determined recursively via

Θ_{ν+1}(z) = (det Δ_{q})Θ′_{ν}(z) − (ν + 1)(det Δ_{q})′Θ_{ν}(z), ν ≥ 0
Θ_{0}(z) = 1.

Then, by Leibniz’s formula for the derivatives of a product function, we have

F_{1}^{(ν)}(z) = ∑_{λ=0}^{ν} \binom{ν}{λ} \frac{Θ_{ν−λ}(z)}{(det Δ_{q})^{ν−λ+1}} (det_{0}Δ_{q})^{(λ)}, ν ≥ 0.  (5.25)

Inserting (5.25) into (5.19), multiplying throughout by (det Δ_{q})^{\frac{q+1}{2}} , and dividing by the series f(z), we obtain the relation

c_{q}^{(0)}z^{q}(det Δ_{q})^{\frac{q+1}{2}} + z(c_{q}^{(1)}z^{q} − 1)(det Δ_{q})^{\frac{q+1}{2}} hf′(z)/f(z)

+ ∑_{μ=2}^{\frac{q−1}{2}} c_{q}^{(μ)}z^{q+μ}(det Δ_{q})^{\frac{q+1}{2}} h^{μ}f^{(μ)}(z)/f(z)

+ (d_{q}^{(0)}z^{q−1} + b)(det Δ_{q})^{\frac{q−1}{2}} (det_{0}Δ_{q})/f(z)

+ ∑_{ν=1}^{\frac{q−1}{2}} ∑_{λ=0}^{ν} \binom{ν}{λ}d_{q}^{(ν)}z^{q+ν−1}Θ_{ν−λ}(z)(det Δ_{q})^{\frac{q+1}{2} −(ν−λ+1)}h^{ν}(det_{0}Δ_{q})^{(λ)}/f(z) = 0, (5.26)

where the reader should recall that f(z) = F_{0}(z) = H_{ℌ(q)}^{H}(z). Two kinds of results may be derived from the last identity: first, an integral recurrence relation for the function s_{ℌ(q)}^{H}(n) for each given q in terms of the parameters h = |H|, a = | Hom(C_{2}, H)|, and b = | Hom(C_{q}, H)|; second, a description of the parity behaviour of s_{ℌ(q)}^{H}(n) for all q. We illustrate the first type of result below with the case of the modular group ℌ(3). As concerns the second kind of result, we note that s_{ℌ(q)}^{H}(n) ≡ s_{q}(n) (mod 2) for |H| odd. Since the parity behaviour of s_{q}(n) is known (see Theorem 2), we shall concentrate here on the case where |H| is even, which yields the parity of the numbers N_{q}(n).

5.4. The case of ℌ(3). For q = 3, Eq. (5.26) reduces to

c_{3}^{(0)}z^{3}(det Δ_{3})^{2} + z(c_{3}^{(1)}z^{3} − 1)(det Δ_{3})^{2}hf′(z)/f(z)

+ {(d_{3}^{(0)}z^{2} + b)(det Δ_{3}) + d_{3}^{(1)}hz^{3}Θ_{1}(z)}(det_{0}Δ_{3})/f(z)

+ d_{3}^{(1)}z^{3}(det Δ_{3})h(det_{0}Δ_{3})′/f(z) = 0. (5.27)

30 C. KRATTENTHALER AND T. W. MÜLLER

We have

c_{3}^{(0)} = ac_{2}^{(0)} + 2hc_{1}^{(0)} = ah,
c_{3}^{(1)} = ac_{2}^{(1)} + c_{1}^{(0)} = a,
d_{3}^{(0)} = ad_{2}^{(0)} + hd_{1}^{(0)} = a^{2} + h,
d_{3}^{(1)} = d_{1}^{(0)} = 1,
det Δ_{3} = det (\begin{matrix}az^{3} − 1 & 0 \\ (a^{2} + h)z^{2} + b & z^{3} \end{matrix}) = z^{3}(az^{3} − 1),
Θ_{1}(z) = −(det Δ_{3})′ = −3z^{2}(2az^{3} − 1),

and

det_{0}Δ_{3} = det (\begin{matrix}−z(a + bz + hz^{3})f(z) − hz^{5}f′(z) & 0 \\ −ahz^{3}f(z) − hz(az^{3} − 1)f′(z) & z^{3} \end{matrix})
= −z^{4}(a + bz + hz^{3})f(z) − hz^{8}f′(z).

Inserting these values into (5.27), dividing both sides by z^{7}, and collecting terms, we find that

(z^{7}−az^{10})h^{2}f′′(z)/f(z)+(−1+4az^{3}+2bz^{4}+(7h−3a^{2})z^{6}−2abz^{7}−4ahz^{9})hf′(z)/f(z) + ab + b^{2}z + a(a^{2} + 3h)z^{2} + 4bhz^{3} − ab^{2}z^{4} + (5h^{2} − a^{4})z^{5} − ab(a^{2} + h)z^{6} − 2ah^{2}z^{8} = 0. (5.28)

Substituting

S_{3}^{H}(z) = hf′(z)/f(z)

and

h(S_{3}^{H}(z))′ + (S_{3}^{H}(z))^{2} = h^{2}f′′(z)/f(z)

in (5.28) according to Lemma 22(i), we find the Riccati-type differential equation

(z^{7} − az^{10})(h(S_{3}^{H}(z))′ + (S_{3}^{H}(z))^{2})

+ ( − 1 + 4az^{3} + 2bz^{4} + (7h − 3a^{2})z^{6} − 2abz^{7} − 4ahz^{9})S_{3}^{H}(z)

+ ab + b^{2}z + a(a^{2} + 3h)z^{2} + 4bhz^{3} − ab^{2}z^{4} + (5h^{2} − a^{4})z^{5} − ab(a^{2} + h)z^{6} − 2ah^{2}z^{8} = 0 (5.29)

for the generating function S_{3}^{H}(z) := S_{ℌ(3)}^{H}(z). Comparing coefficients in (5.29), we finally obtain the following result, which generalizes Theorem 1 in [10]. Proposition 23. The function s_{3}^{H}(n) := s_{ℌ(3)}^{H}(n) satisfies the recurrence relation

s_{3}^{H}(n) = 4as_{3}^{H}(n − 3) + 2bs_{3}^{H}(n − 4) + (hn − 3a^{2})s_{3}^{H}(n − 6) − 2abs_{3}^{H}(n − 7)

− ah(n−6)s_{3}^{H}(n−9) + ∑_{μ=1}^{n−7} s_{3}^{H}(μ)s_{3}^{H}(n−μ−6) − a ∑_{μ=1}^{n−10} s_{3}^{H}(μ)s_{3}^{H}(n−μ−9), n ≥ 10, (5.30)

with initial values

s_{3}^{H}(1) = ab,
s_{3}^{H}(2) = b^{2},
s_{3}^{H}(3) = a(a^{2} + 3h),
s_{3}^{H}(4) = 4b(a^{2} + h),
s_{3}^{H}(5) = 5ab^{2},
s_{3}^{H}(6) = 3a^{4} + 2b^{3} + 5h^{2} + 12a^{2}h,
s_{3}^{H}(7) = 14ab(a^{2} + 2h),
s_{3}^{H}(8) = 8b^{2}(3a^{2} + 2h),
s_{3}^{H}(9) = 3a(3a^{4} + 6b^{3} + 15h^{2} + 16a^{2}h).

5.5. The parity behaviour of N_{q}(n). We now use Lemmas 18, 20, and 22(ii) to simplify identity (5.26) under the assumption that h = |H| ≡ 0 (mod 2). Throughout, we set S_{ℌ(q)}^{H}(z) =: S_{q}^{H}(z) and α_{0} := 3q^{2} − 11q + 12.

First, c_{q}^{(0)} ≡ c_{q}^{(1)} ≡ 0 (mod 2), since q > 2; hence,

c_{q}^{(0)}z^{q}(det Δ_{q})^{\frac{q+1}{2}} ≡ 0 mod 2

and

z(c_{q}^{(1)}z^{q} − 1)(det Δ_{q})^{\frac{q+1}{2}} hf′(z)/f(z) ≡ z^{\frac{q+1}{4} α_{0}+1}S_{q}^{H}(z) mod 2.

Similarly, we have c_{q}^{(μ)} ≡ 0 (mod 2) for μ < q/2; thus

∑_{μ=2}^{\frac{q−1}{2}} c_{q}^{(μ)}z^{q+μ}(det Δ_{q})^{\frac{q+1}{2}} h^{μ}f^{(μ)}(z)/f(z) ≡ 0 mod 2.

Next, inspection shows that, in view of Lemma 22(ii), b_{κ}(z)/f(z) is always an integral power series; hence, (det_{0}Δ_{q})/f(z) is an integral power series, and modulo 2 we have

(det_{0}Δ_{q})/f(z) = ∑_{κ=0}^{q−2}(−1)^{κ}(det Δ_{κ,0})b_{κ}(z)/f(z)
≡ (det Δ_{0,0})b_{0}(z)/f(z)
≡ z^{α_{0}/2}\{z^{2} + z^{\frac{3q+1}{2}} h^{\frac{q−1}{2}} f^{( \frac{q−1}{2} )}(z)/f(z)\}
≡ z^{2+α_{0}/2} + z^{\frac{α_{0}+3q+1}{2}} (S_{q}^{H}(z))^{\frac{q−1}{2}} ,

and so, modulo 2,

(d_{q}^{(0)}z^{q−1} + b)(det Δ_{q})^{\frac{q−1}{2}} (det_{0}Δ_{q})/f(z) ≡ (det Δ_{q})^{\frac{q−1}{2}} (det_{0}Δ_{q})/f(z)
≡ z^{\frac{α_{0}}{2} ( \frac{q+1}{2} −1)}\{z^{2+α_{0}/2} + z^{\frac{α_{0}+3q+1}{2}} (S_{q}^{H}(z))^{\frac{q−1}{2}} \}
= z^{2+ \frac{q+1}{4} α_{0}} + z^{( \frac{q+1}{2} α_{0}+3q+1)/2}(S_{q}^{H}(z))^{\frac{q−1}{2}} .

Here we have used Lemma 20 to evaluate det Δ_{q} and det Δ_{κ,0} modulo 2, the facts, following from Lemma 18, that d_{q}^{(0)} ≡ 0 (mod 2) and that

c_{q−1}^{(μ)} ≡ 1 (mod 2) if, and only if, μ = \frac{q − 1}{2}, 0 ≤ μ ≤ \frac{q − 1}{2},

plus Part (ii) of Lemma 22 to rewrite the term h^{\frac{q−1}{2}} f^{( \frac{q−1}{2} )}(z)/f(z). This leaves the double sum Σ on the right-hand side of (5.26). Clearly, for 0 ≤ κ ≤ q−2 and 0 ≤ η ≤ ν, the term h^{ν}b_{κ}^{(η)}(z)/f(z) is an integral power series, and we have

h^{ν}b_{κ}^{(η)}(z)/f(z) ≡ 0 mod 2, η < ν.

From this observation it follows that, for 0 ≤ λ ≤ ν, the expression

h^{ν}(det_{0}Δ_{q})^{(λ)}/f(z) = ∑_{κ=0}^{q−2} ∑_{η=0}^{λ}(−1)^{κ}\binom{λ}{η}(det Δ_{κ,0})^{(λ−η)}h^{ν}b_{κ}^{(η)}(z)/f(z)

is an integral power series, and that

h^{ν}(det_{0}Δ_{q})^{(λ)}/f(z) ≡ \begin{cases}z^{α_{0}/2}h^{ν}b_{0}^{(ν)}(z)/f(z), & λ = ν \\ 0, & λ < ν \end{cases}\} mod 2.  (5.31)

From (5.31) in turn, we conclude that each summand of Σ (and hence Σ itself) is an integral power series, and that

Σ ≡ ∑_{ν=1}^{\frac{q−1}{2}} d_{q}^{(ν)}z^{q+ν−1}(det Δ_{q})^{\frac{q+1}{2} −1}h^{ν}(det_{0}Δ_{q})^{(ν)}/f(z) mod 2.  (5.32)

Next, using the fact that, by Lemma 18,

d_{q}^{(ν)} ≡ 1 (mod 2) if, and only if, ν = \frac{q − 1}{2}, 0 ≤ ν ≤ \frac{q − 1}{2},

the right-hand side of (5.32) in its turn is congruent modulo 2 to

z^{\frac{3q−3}{2}} (det Δ_{q})^{\frac{q−1}{2}} h^{\frac{q−1}{2}} (det_{0}Δ_{q})^{( \frac{q−1}{2} )}/f(z),

which, in view of (5.31) and Lemmas 20(i) and 22(ii), simplifies further to give

Σ ≡ z^{\frac{α_{0}+3q−3}{2}} (det Δ_{q})^{\frac{q−1}{2}} h^{\frac{q−1}{2}} b_{0}^{( \frac{q−1}{2} )}(z)/f(z)
≡ z^{\frac{\frac{q+1}{2} α_{0}+3q−3}{2}} \{z^{2}h^{\frac{q−1}{2}} f^{( \frac{q−1}{2} )}(z)/f(z) + z^{\frac{3q+1}{2}} h^{q−1}f^{(q−1)}(z)/f(z)\}

≡ z^{\frac{\frac{q+1}{2} α_{0}+3q+1}{2}} (S_{q}^{H}(z))^{\frac{q−1}{2}} + z^{\frac{\frac{q+1}{2} α_{0}+6q−2}{2}} (S_{q}^{H}(z))^{q−1}.

Putting all the pieces together and dividing by z^{\frac{q+1}{4} α_{0}+1}, we obtain the surprisingly elegant congruence

z + S_{q}^{H}(z) + z^{3q−2}(S_{q}^{H}(z))^{q−1} ≡ 0 mod 2, |H| ≡ 0 (mod 2).  (5.33)

We are now in a position to establish our second main result.

Theorem 24. Let q be an odd prime number. Then the number N_{q}(n) of index n subgroups in the Hecke group ℌ(q) isomorphic to a free product of cyclic groups of order q is odd if, and only if, n = 2 + 4(q − 1)η, where η is a non-negative integer satisfying the condition that

𝔰_{2}((q − 1)η + 1) = 𝔰_{2}(η) + 𝔰_{2}((q − 2)η + 1).  (5.34)

Here, as before, 𝔰_{2}(x) is the sum of digits in the binary expansion of the positive integer x.

Proof. Recall that, by (5.2), the number N_{q}(n) is the same modulo 2 as the number s_{q}^{H}(n) for a group H of even order. On the other hand, Equation (5.33) is a functional equation for the generating function of the s_{q}^{H}(n)’s, taken modulo 2. We now use this functional equation to determine s_{q}^{H}(n) modulo 2, and thereby N_{q}(n) modulo 2 as well.

Define an integral power series Ŝ_{q}^{H}(z) by means of the equation

Ŝ_{q}^{H}(z) = z + z^{3q−2}(Ŝ_{q}^{H}(z))^{q−1}.

Then, in view of (5.33), we have

Ŝ_{q}^{H}(z) ≡ S_{q}^{H}(z) mod 2.

Setting

T̂_{q}^{H}(z) := z^{−1}Ŝ_{q}^{H}(z) = 1 + ∑_{n≥1} t̂_{q}^{H}(n)z^{n},

we obtain an integral power series with functional equation

T̂_{q}^{H}(z) = 1 + z^{4(q−1)}(T̂_{q}^{H}(z))^{q−1}.  (5.35)

From the functional equation it is obvious that T̂_{q}^{H}(z) must be a power series in z^{4(q−1)}; that is, the coefficients t̂_{q}^{H}(n) must satisfy

n ≢ 0 mod 4(q − 1) ⟹ t̂_{q}^{H}(n) = 0, n ≥ 1.  (5.36)

Hence, introducing a series Û_{q}^{H}(v) via

Û_{q}^{H}(v) = ∑_{η≥1} t̂_{q}^{H}(4(q − 1)η)v^{η},

we have

T̂_{q}^{H}(z) − 1 = Û_{q}^{H}(z^{4(q−1)}),

and, setting v = z^{4(q−1)}, we find from (5.35) that Û_{q}^{H}(v) satisfies the functional equation

\frac{Û_{q}^{H}(v)}{(Û_{q}^{H}(v) + 1)^{q−1}} = v.

34 C. KRATTENTHALER AND T. W. MÜLLER

Using the notation ⟨v^{η}⟩f(v) for the coefficient of v^{η} in the power series f(v), Lagrange inversion (cf. [32, Theorem 5.4.2]) implies that, for η ≥ 1, we have

⟨v^{η}⟩Û_{q}^{H}(v) = η^{−1}⟨ζ^{η−1}⟩(1 + ζ)^{(q−1)η}

= η^{−1}\binom{(q − 1)η}{η − 1}

= \frac{1}{(q − 1)η + 1}\binom{(q − 1)η + 1}{η}.

Substituting back, Ŝ_{q}^{H}(z) is found to be given explicitly by

Ŝ_{q}^{H}(z) = ∑_{η≥0} \frac{1}{(q − 1)η + 1} \binom{(q − 1)η + 1}{η} z^{4(q−1)η+1},

which in turn allows us to deduce that

s_{q}^{H}(n) ≡ \begin{cases}0; & n ≢ 2 (mod 4q − 4) \\ \frac{1}{(q−1)η+1} \binom{(q−1)η+1}{η}; & n = 2 + 4(q − 1)η, η ≥ 0 \end{cases}\} mod 2, n ≥ 1. (5.37)

Since q is an odd prime, and, hence, (q − 1)η + 1 is odd, we have shown that, for |H| even, s_{q}^{H}(n) is odd if, and only if, n = 2 + 4(q − 1)η for some η ≥ 0 satisfying

v_{2} (\binom{(q − 1)η + 1}{η}) = 0.

Applying Kummer’s formula (cf. [16, pp. 115–116])

v_{2} (\binom{a}{b}) = 𝔰_{2}(b) + 𝔰_{2}(a − b) − 𝔰_{2}(a)

for the 2-adic valuation of a binomial coefficient, we find that

v_{2} (\binom{(q − 1)η + 1}{η}) = 𝔰_{2}(η) + 𝔰_{2}((q − 2)η + 1) − 𝔰_{2}((q − 1)η + 1),

and our statement concerning s_{q}^{H}(n) can be rewritten as s_{q}^{H}(n) ≡ 1 (mod 2) if, and only if, n = 2 + 4(q − 1)η for some η ≥ 0 satisfying (5.34). In view of (5.2), this establishes the theorem. □ In the case where q is a Fermat prime we can be more explicit. Corollary 25. If q is a Fermat prime, then N_{q}(n) is odd if, and only if, n = \frac{4(q−1)^{σ+1}−2q}{q−2} for some σ ≥ 0. Proof. If q is a Fermat prime, that is, q − 1 = 2^{λ} is a non-trivial 2-power, then

𝔰_{2}((q − 1)η + 1) = 1 + 𝔰_{2}(η),

and Equation (5.34) simplifies to

𝔰_{2}((q − 2)η + 1) = 1.  (5.38)

Therefore (q − 2)η + 1 must be a 2-power, (q − 2)η + 1 = 2^{τ}, say. Equivalently, this is

(2^{λ} − 1)η = 2^{τ} − 1,

from which we infer that τ must be a multiple of λ, τ = λσ say. Hence, we find that η must be of the form

η = \frac{2^{λσ} − 1}{2^{λ} − 1}, σ ≥ 0;

and, conversely, for these values of η, Equation (5.38) indeed holds true. We conclude that, in the case when q is a Fermat prime, N_{q}(n) is odd if, and only if,

n = 2 + 4(q − 1)\frac{(q − 1)^{σ} − 1}{q − 2} = \frac{4(q − 1)^{σ+1} − 2q}{q − 2} , σ ≥ 0,

and the corollary is proven. □

Remark. A detailed analysis of (5.26) in the case when h = |H| is odd, making use of Lemma 21, eventually leads to a new proof of Theorem 2, the case where q ≡ 3 (mod 4) being particularly involved.

6. The main result

Here we summarize our findings concerning the parity behaviour of the generalized subgroup numbers of the groups Γ_{m}(q) from the previous sections. If we combine Proposition 1 with Theorems 2, 16, and 24, then we obtain the following result.

Theorem 26. For m, n ≥ 1, an odd prime q, and a finite group H with gcd(m, |H|) = 1 we have

s_{Γ_{m}(q)}^{H}(n) = ∑_{d|m} s_{Γ_{d}(q)}^{H}(1, n),

where s_{Γ_{d}(q)}^{H}(1, n) ≡ 1 (mod 2) if, and only if,

n = 2d(1 + 2(q − 1)η) with 𝔰_{2}((q − 1)η + 1) = 𝔰_{2}(η) + 𝔰_{2}((q − 2)η + 1) and q ∤ d,

or

n = d(1+2(q−1)η) with 𝔰_{2}((q−1)η+1) = 𝔰_{2}(η)+𝔰_{2}((q−2)η+1) and 2 ∤ d, q ∤ d, 2 ∤ |H|.

In the case where q is a Fermat prime, we can be more explicit. Namely, if we combine Proposition 1 with the particular statement in Theorem 2, Theorem 16, and Corollary 25, we arrive at the following conclusion.

Corollary 27. For m, n ≥ 1, a Fermat prime q, and a finite group H with gcd(m, |H|) = 1 we have

s_{Γ_{m}(q)}^{H}(n) = ∑_{d|m} s_{Γ_{d}(q)}^{H}(1, n),

where s_{Γ_{d}(q)}^{H}(1, n) ≡ 1 (mod 2) if, and only if,

n = 2d \frac{2(q − 1)^{σ} − q}{q − 2} with σ ≥ 1 and q ∤ d,

or

n = d \frac{2(q − 1)^{σ} − q}{q − 2} with σ ≥ 1, 2 ∤ d, q ∤ d, and 2 ∤ |H|.

Let us fix a Fermat prime q = 2^{λ} +1. Suppose that p is an odd prime with the property that

the multiplicative group generated by q − 1 does not contain 2^{−1}q modulo p. (6.1)

Then the equation

t_{1}(2(q − 1)^{σ_{1}} − q) = t_{2}(2(q − 1)^{σ_{2}} − q)  (6.2)

has no solutions (t_{1}, t_{2}, σ_{1}, σ_{2}) where p | t_{1}, but p ∤ t_{2}, since otherwise we would have

2(q − 1)^{σ_{2}} ≡ q mod p,

contrary to our assumption on p. Hence, if q is a Fermat prime, and if the prime divisors of m are among the set consisting of 2, q, and primes p satisfying Condition (6.1), then we obtain for all H with gcd(m, |H|) = 1 that

s_{Γ_{m}(q)}^{H}(n) ≡ 1 (mod 2) if, and only if, n = t \frac{2(q − 1)^{σ} − q}{q − 2} with σ ≥ 1, t | 2m, q ∤ t,

and t even for |H| even. (6.3)

Statement (6.3) raises the question which primes satisfy Condition (6.1) for a given Fermat prime q. This problem is addressed in our next result, for q = 3, 5, 17. For larger Fermat primes the calculations involved, though essentially trivial, become unwieldy, and are omitted.

Proposition 28.

(i) All prime numbers p ≡ 7, 17 (mod 24) satisfy Condition (6.1) with q = 3. (ii) All prime numbers p ≡ 7, 11, 17, 19, 21, 23, 29, 33 (mod 40) satisfy Condit-

ion (6.1) with q = 5. (iii) All prime numbers

p ≡ 7, 13, 19, 21, 23, 31, 35, 39, 41, 43, 53, 57, 59, 63, 65, 67, 69, 71, 73, 77, 79, 83, 93, 95, 97, 105, 113, 115, 117, 123, 125, 129 (mod 136)

satisfy Condition (6.1) with q = 17.

Proof. This is a simple application of quadratic reciprocity. Let us first consider the case when q = 3. If p ≠ 3 is an odd prime not satisfying Condition (6.1) with q = 3, then we have

2^{α} ≡ 3 mod p

for some α ≥ 1, implying (\frac{3}{p}) = +1 or (\frac{6}{p}) = +1, according to whether or not α is even. Hence, every prime p ≡ ±1 (mod 8) not satisfying (6.1) with q = 3 has the property that (\frac{3}{p}) = +1. By quadratic reciprocity,

(\frac{p}{3}) = \begin{cases}+1, & p ≡ 1 (mod 4), \\ −1, & p ≡ 3 (mod 4), \end{cases}

for each prime p not satisfying (6.1) with q = 3 and such that p ≡ ±1 (mod 8). It follows from this that every prime p such that

p ≡ ±1 (mod 8) and (\frac{p}{3}) = \begin{cases}−1, & p ≡ 1 (mod 4), \\ +1, & p ≡ 3 (mod 4), \end{cases}

will satisfy Condition (6.1) with q = 3. Thus, both

p ≡ 1 (mod 8) and p ≡ 2 (mod 3)

as well as p ≡ 7 (mod 8) and p ≡ 1 (mod 3)

are hypotheses sufficient to ensure that p meets Condition (6.1) with q = 3. The first pair of congruences is equivalent to p ≡ 17 (mod 24), while the second one is equivalent to p ≡ 7 (mod 24), whence Assertion (i).

For a Fermat prime q with q > 3, we have q ≡ 1 (mod 4), so

(\frac{p}{q}) = (\frac{q}{p})

for any odd prime p ≠ q by quadratic reciprocity. Consequently, if p is such that p ≡ ±1 (mod 8) and (6.1) does not hold for p, then we find that

1 = (\frac{2q}{p} ) = (\frac{2}{p})(\frac{q}{p}) = (\frac{q}{p}) = (\frac{p}{q}),

while for p ≡ ±3 (mod 8) such that (6.1) does not hold, we obtain (\frac{p}{q}) = −1. Hence, every prime p satisfying either

p ≡ ±1 (mod 8) and (\frac{p}{q}) = −1

or

p ≡ ±3 (mod 8) and (\frac{p}{q}) = +1

will meet Condition (6.1). Thus, it only remains to translate the statement concerning (\frac{p}{q}) into a congruence condition modulo q, and to solve the resulting pairs of congruences, each pair leading to an equivalent congruence conditon for p modulo 8q.

For q = 5, we have

(\frac{p}{5}) = +1 if, and only if, p ≡ ±1 (mod 5),

so both

p ≡ ±1 (mod 8) and p ≡ 2, 3 (mod 5)

as well as

p ≡ ±3 (mod 8) and p ≡ 1, 4 (mod 5)

ensure that p meets Condition (6.1) with q = 5. This yields Part (ii), while a corresponding calculation for q = 17 gives Assertion (iii). □

For q a Fermat prime and m subject only to the condition that gcd(m, |H|) = 1, we claim that (6.3) holds true for n ≥ \frac{4m^{2}}{q−2} . To prove this, it suffices to give an upper bound for non-diagonal solutions of Equation (6.2). Assume that t_{2} > t_{1}. Then

0 < σ_{1} − σ_{2} < \frac{log t_{2}/t_{1}}{log(q − 1)},  (6.4)

and we compute:

t_{2}(2(q − 1)^{σ_{2}} − q) = gcd (t_{1}(2(q − 1)^{σ_{1}} − q), t_{2}(2(q − 1)^{σ_{2}} − q))
≤ gcd (t_{1}t_{2}(2(q − 1)^{σ_{1}} − q) − t_{1}t_{2}(2(q − 1)^{σ_{1}} − q(q − 1)^{σ_{1}−σ_{2}}),
t_{2}(2(q − 1)^{σ_{2}} − q))
≤ gcd (qt_{1}t_{2}((q − 1)^{σ_{1}−σ_{2}} − 1), t_{2}(2(q − 1)^{σ_{2}} − q))
≤ t_{2} gcd (t_{1}((q − 1)^{σ_{1}−σ_{2}} − 1), 2(q − 1)^{σ_{2}} − q)
< t_{2}^{2},

where we have used (6.4) in the last step. Our claim follows now from Corollary 27 and the fact that t_{2} ≤ 2m.

In particular, we see from the last observation and (6.3), that the parity behaviour of s_{Γ_{m}}^{H}(n) as a function in n determines m up to a power of q, provided that gcd(m, |H|) = 1.

As a final example, we compute the parity behaviour of s_{Γ_{m}(q)}^{H}(n) for q = 3 and m = 625. We have to determine the non-diagonal solutions of the equation

t_{1}(2^{σ_{1}+1} − 3) = t_{2}(2^{σ_{2}+1} − 3)  (6.5)

for σ_{1}, σ_{2} ≥ 1 and t_{1}, t_{2} | 1250. We have t_{1} ≡ t_{2} (mod 2); thus, we may concentrate on the case when both t_{1} and t_{2} are odd, bearing in mind that each non-diagonal solution of (6.5) with t_{1}, t_{2} odd gives rise to two non-diagonal solutions, namely (t_{1}, t_{2}, σ_{1}, σ_{2}) and (2t_{1}, 2t_{2}, σ_{1}, σ_{2}).

Suppose without loss of generality that t_{2} > t_{1}, and let δ := v_{5}(t_{2}) − v_{5}(t_{1}). For δ = 1, we deduce that 2^{σ_{1}+1} ≡ 3 (mod 5), which is equivalent to σ_{1} ≡ 2 (mod 4). The case where σ_{1} = 2 leads to the solutions

(t_{1}, t_{2}, σ_{1}, σ_{2}) = (5^{a}, 5^{a+1}, 2, 1), a = 0, 1, 2, 3.  (6.6)

If σ_{1} = 6, 10, then 2^{σ_{2}+1} would have to equal 28 respectively 412, which is impossible; while for σ_{1} ≥ 14, we deduce that

2^{σ_{2}+1} − 3 ≥ \frac{2^{15} − 3}{5} = 6553,

contradicting the estimate

2^{σ_{2}+1} − 3 < t_{2} ≤ 625

obtained above. Hence, the only non-diagonal solutions of (6.5) with t_{1} and t_{2} odd and δ = 1 are given by (6.6).

For δ = 2, we get that 2^{σ_{1}+1} ≡ 3 (mod 25), which is equivalent to σ_{1} ≡ 6 (mod 20). The case where σ_{1} = 6 leads to the solutions

(t_{1}, t_{2}, σ_{1}, σ_{2}) = (5^{a}, 5^{a+2}, 6, 2), a = 0, 1, 2.  (6.7)

If σ_{1} ≥ 26, then we deduce that

2^{σ_{2}+1} − 3 ≥ \frac{2^{27} − 3}{5^{2}} = 5368709,

again contradicting the estimate 2^{σ_{2}+1} − 3 < t_{2}. Consequently (6.7) describes the only non-diagonal solutions of (6.5) with t_{1}, t_{2} odd and δ = 2.

For δ = 3, we have 2^{σ_{1}+1} ≡ 3 (mod 125), which is equivalent to σ_{1} ≡ 6 (mod 100), leading to the solutions

(t_{1}, t_{2}, σ_{1}, σ_{2}) = (5^{a}, 5^{a+3}, 6, 1), a = 0, 1.  (6.8)

Finally, for δ = 4, we have 2^{σ_{1}+1} ≡ 3 (mod 625), which is equivalent to σ_{1} ≡ 106 (mod 500). But 106 is already well above the range allowed for σ_{1}. Hence, there is precisely one non-diagonal solution of (6.5) for n = 5, 10, 25, 50, 3125, 6250; there are exactly three non-diagonal solutions for n = 125, 250, 625, 1250; and there are no nondiagonal solutions for other values of n. Consequently, for gcd(5, |H|) = 1, Assertion (6.3) holds true for n > 6250, while for n ≤ 6250 we have

s_{Γ_{625}(3)}^{H}(n) ≡ 1 mod 2 if, and only if, n = 1, 2, 13, 26, 29, 58, 61, 65, 122, 125, 130, 145, 250, 253, 290, 305, 325, 506,

509, 610, 625, 650, 725, 1018, 1021, 1250, 1265, 1450, 1525, 1625, 2042, 2045,
2530, 2545, 3050, 3250, 3625, 4090, 4093, 5090, 5105

if |H| is odd, and

s_{Γ_{625}(3)}^{H}(n) ≡ 1 mod 2 if, and only if,

n = 2, 26, 58, 122, 130, 250, 290, 506, 610, 650, 1018, 1250, 1450, 2042, 2530,

3050, 3250, 4090, 5090

for |H| even.

Acknowledgements

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

Appendix. Proofs of some auxiliary results

A.1. Proof of Lemma 11. Suppose first that ρ_{1} ≡ ρ_{2} ≡ ⋯ ≡ ρ_{α} ≡ 1 (mod 4). It is well known that the 2-adic valuation of the multinomial coefficient \binom{ρ_{1}+ρ_{2}+...+ρ_{α}}{ρ_{1},ρ_{2}...,ρ_{α}} is equal to the number of carries, C say, occurring during addition of the numbers ρ_{1}, ρ_{2} …, ρ_{α}. If we assume that, in total, we find E_{ℓ} 1’s as the ℓ-th digit in the binary representations of ρ_{1}, ρ_{2} …, ρ_{α}, then

C = ⌊\frac{E_{0}}{2} ⌋ + ⌊\frac{E_{1} + ⌊\frac{E_{0}}{2} ⌋}{2}⌋ + ⌊\frac{E_{2} + ⌊\frac{E_{1}+⌊\frac{E_{0}}{2} ⌋}{2}⌋}{2}⌋ + ⋯

≥ ⌊\frac{E_{0}}{2} ⌋ + ⌊\frac{⌊\frac{E_{0}}{2} ⌋}{2}⌋ + ⌊\frac{⌊\frac{⌊\frac{E_{0}}{2} ⌋}{2}⌋}{2}⌋ + ⋯ = ∑_{ℓ≥1} ⌊\frac{E_{0}}{2^{ℓ}} ⌋ .

According to our assumption, we have E_{0} = α, whence

v_{2} (\binom{ρ_{1} + ρ_{2} + … + ρ_{α}}{ρ_{1}, ρ_{2} …, ρ_{α}}) = C ≥ ∑_{ℓ≥1} ⌊\frac{α}{2^{ℓ}} ⌋ = v_{2}(α!).

The second assertion is established in a similar manner. □

A.2. Proof of Lemma 13. Let k = ∑_{j≥0} k_{j}2^{j} be the 2-adic expansion of k. Then

2^{λ}k + 1 = 1 · 2^{0} + 0 · 2^{1} + ⋯ + 0 · 2^{λ−1} + ∑_{j≥0} k_{j}2^{j+λ}

is the 2-adic expansion of 2^{λ}k + 1. Suppose first that k is odd. Then k_{0} = 1, and so

k − 1 = 0 · 2^{0} + ∑_{j≥1} k_{j}2^{j}.

By Lucas’ congruence (cf., for instance, [3, Theorem 3.4.1]), \binom{2^{λ}k+1}{k−1} ≡ 1 (mod 2) is equivalent to the conjunction of

k_{1} = k_{2} = ⋯ = k_{λ−1} = 0  (A.1)

and

k_{μ+λ} ≤ k_{μ}, μ ≥ 0.  (A.2)

The conjunction of (A.1) and (A.2) in turn is equivalent to

k_{j} = 0 (j ≢ 0 (mod λ)) and k_{μλ} ≤ k_{(μ−1)λ} (μ ≥ 1).  (A.3)

Let σ ≥ 1 be smallest with the property that k_{σλ} = 0. Then k_{μλ} = 1 for μ = 0, 1, …, σ − 1 and k_{μλ} = 0 for μ ≥ σ, so, by (A.3),

k = ∑_{0≤μ≤σ−1} 2^{λμ} = \frac{2^{λσ} − 1}{2^{λ} − 1}, σ ≥ 1.

Hence,

\binom{2^{λ}k + 1}{k − 1} ≡ 1 (mod 2) if, and only if, k = \frac{2^{λσ} − 1}{2^{λ} − 1} for some σ ≥ 1, k odd. (A.4)

Now suppose that k is even, and write

k = 0 · 2^{0} + ⋯ + 0 · 2^{r−1} + 1 · 2^{r} + ∑_{j>r} k_{j}2^{j}

with some r ≥ 1 (such r must exist since k > 0). Then

k − 1 = 1 · 2^{0} + ⋯ + 1 · 2^{r−1} + 0 · 2^{r} + ∑_{j>r} k_{j}2^{j}

is the 2-adic expansion of k − 1 in this case. We now distinguish two cases, according to whether or not λ = 1.

(i) If λ > 1, then the coefficient of 2^{1} in 2^{λ}k + 1 vanishes, while, for r ≥ 2, the corresponding coefficient of k − 1 equals 1. Hence, \binom{2^{λ}k+1}{k−1} ≡ 1 (mod 2) together with λ > 1 forces r = 1, so that the expansion of k − 1 reads

k − 1 = 1 · 2^{0} + 0 · 2^{1} + ∑_{j≥2} k_{j}2^{j}.

Now, again by Lucas’ theorem, \binom{2^{λ}k+1}{k−1} ≡ 1 (mod 2) is equivalent to the conjunction of

k_{0} = k_{2} = ⋯ = k_{λ−1} = 0, k_{1} = 1  (A.5)

and

k_{j} ≤ k_{j−λ}, j ≥ λ.  (A.6)

The conjunction of (A.5) and (A.6) in turn is equivalent to

k_{j} = 0 (j ≢ 1 (mod λ)) and k_{μλ+1} ≤ k_{(μ−1)λ+1} (μ ≥ 1).  (A.7)

Let σ ≥ 1 be smallest with the property that k_{σλ+1} = 0, so that k_{μλ+1} = 1 for 0 ≤ μ ≤ σ − 1 and k_{μλ+1} = 0 for μ ≥ σ. Thus, by (A.7),

k = ∑_{0≤μ≤σ−1} 2^{λμ+1} = 2( ∑_{0≤μ≤σ−1} 2^{λμ}) = \frac{2^{λσ+1} − 2}{2^{λ} − 1}.

Hence,

\binom{2^{λ}k + 1}{k − 1} ≡ 1 (mod 2) if, and only if,

k = \frac{2^{λσ+1} − 2}{2^{λ} − 1} for some σ ≥ 1, (2 | k, λ ≥ 2). (A.8)

(ii) Now let λ = 1, so that

2^{λ}k + 1 = 1 · 2^{0} + ∑_{j≥0} k_{j}2^{j+1}.

Application of Lucas’ congruence shows that, in this case, \binom{2^{λ}k+1}{k−1} ≡ 1 (mod 2) is equivalent to the conjunction of

k_{0} = k_{1} = ⋯ = k_{r−2} = 1, k_{r−1} = 0, k_{r} = 1,  (A.9)

and

k_{j} ≤ k_{j−1}, j > r.  (A.10)

Since, by definition of r, we have k_{j} = 0 for 0 ≤ j < r, we again conclude that r = 1, so that the conjunction of (A.9) and (A.10) is now equivalent to

k_{0} = 0, k_{1} = 1, k_{j} ≤ k_{j−1} (j ≥ 2).  (A.11)

Let σ ≥ 1 be smallest with the property that k_{σ+1} = 0. Then k_{μ} = 1 for 1 ≤ μ ≤ σ, and k_{μ} = 0 for μ > σ, and so, by (A.11),

k = ∑_{1≤μ≤σ} 2^{μ} = 2^{σ+1} − 2.

Thus,

\binom{2^{λ}k + 1}{k − 1} ≡ 1 (mod 2) if, and only if, k = 2^{σ+1} − 2 for some σ ≥ 1, (2 | k, λ = 1).

(A.12)

Our claim (4.22) follows now from (A.4), (A.8), and (A.12). □

A.3. Proof of Lemma 17. We use induction on k. For k = 0, 1, Equation (5.13) is trivial, while for k = 2 it follows from (5.11) with k = 1. Suppose that (5.13) holds for k ≤ K with some integer K ≥ 2. Then, by (5.11) with k = K, the inductive hypothesis, and the definition of the coefficient systems (c_{k}^{(μ)}) and (d_{k}^{(ν)}), we have

F_{K+1} = azF_{K}(z) + hz^{2}F_{K−1}(z) + hz^{3}F′_{K−1}(z)

= az\{ ∑_{μ=0}^{⌊ \frac{K}{2} ⌋} c_{K}^{(μ)}h^{μ}z^{K+μ}F_{0}^{(μ)} + ∑_{ν=0}^{⌊ \frac{K−1}{2} ⌋} d_{K}^{(ν)}h^{ν}z^{K+ν−1}F_{1}^{(ν)}\}

+ hz^{2}\{ ∑_{μ=0}^{⌊ \frac{K−1}{2} ⌋} c_{K−1}^{(μ)}h^{μ}z^{K+μ−1}F_{0}^{(μ)} + ∑_{ν=0}^{⌊ \frac{K−2}{2} ⌋} d_{K−1}^{(ν)}h^{ν}z^{K+ν−2}F_{1}^{(ν)}\}

+ hz^{3}\{ ∑_{μ=0}^{⌊ \frac{K−1}{2} ⌋} c_{K−1}^{(μ)}h^{μ}z^{K+μ−1}F_{0}^{(μ)} + ∑_{ν=0}^{⌊ \frac{K−2}{2} ⌋} d_{K−1}^{(ν)}h^{ν}z^{K+ν−2}F_{1}^{(ν)}\}′

= (ac_{K}^{(0)} + hKc_{K−1}^{(0)})z^{K+1}F_{0}(z)

+ ∑_{μ=1}^{⌊ \frac{K−1}{2} ⌋}(ac_{K}^{(μ)} + h(K + μ)c_{K−1}^{(μ)} + c_{K−1}^{(μ−1)})h^{μ}z^{K+μ+1}F_{0}^{(μ)}(z)

+ h^{⌊ \frac{K+1}{2} ⌋}z^{K+⌊ \frac{K+1}{2} ⌋+1}F_{0}^{(⌊ \frac{K+1}{2} ⌋)}(z) × \begin{cases}c_{K−1}^{( \frac{K−1}{2} )}, & K odd \\ ac_{K}^{(K/2)} + c_{K−1}^{( \frac{K−2}{2} )}, & K even \end{cases}

+ (ad_{K}^{(0)} + h(K − 1)d_{K−1}^{(0)})z^{K}F_{1}(z)

+ ∑_{ν=1}^{⌊ \frac{K−2}{2} ⌋}(ad_{K}^{(ν)} + h(K + ν − 1)d_{K−1}^{(ν)} + d_{K−1}^{(ν−1)})z^{K+ν}h^{ν}F_{1}^{(ν)}(z)

+ h^{⌊ \frac{K}{2} ⌋}z^{K+⌊ \frac{K}{2} ⌋}F_{1}^{(⌊ \frac{K}{2} ⌋)}(z) × \begin{cases}ad_{K}^{( \frac{K−1}{2} )} + d_{K−1}^{( \frac{K−3}{2} )}, & K odd \\ d_{K−1}^{( \frac{K−2}{2} )}, & K even \end{cases}

= c_{K+1}^{(0)}z^{K+1}F_{0}(z) + ∑_{μ=1}^{⌊ \frac{K−1}{2} ⌋} c_{K+1}^{(μ)}h^{μ}z^{K+μ+1}F_{0}^{(μ)}(z)

+ c_{K+1}^{(⌊ \frac{K+1}{2} ⌋)}h^{⌊ \frac{K+1}{2} ⌋}z^{K+⌊ \frac{K+1}{2} ⌋+1}F_{0}^{(⌊ \frac{K+1}{2} ⌋)}(z)

+ d_{K+1}^{(0)}z^{K}F_{1}(z) + ∑_{ν=1}^{⌊ \frac{K−2}{2} ⌋} d_{K+1}^{(ν)}h^{ν}z^{K+ν}F_{1}^{(ν)}(z)

+ d_{K+1}^{(⌊ \frac{K}{2} ⌋)}h^{⌊ \frac{K}{2} ⌋}z^{K+⌊ \frac{K}{2} ⌋}F_{1}^{(⌊ \frac{K}{2} ⌋)}(z)

= ∑_{μ=0}^{⌊ \frac{K+1}{2} ⌋} c_{K+1}^{(μ)}h^{μ}z^{K+μ+1}F_{0}^{(μ)}(z) + ∑_{ν=0}^{⌊ \frac{K}{2} ⌋} d_{K+1}^{(ν)}h^{ν}z^{K+ν}F_{1}^{(ν)}(z),

as required. □

A.4. Explicit description of the coefficients ω_{κ,λ} and b_{κ}(z). We have

ω_{κ,λ} =

d_{q−1}^{(0)}z^{q} − 1;  κ = λ = 0
d_{q−1}^{(λ)}z^{λ+q};  κ = 0, λ = 1, …, \frac{q−3}{2}
d_{q}^{(0)}z^{q−1} + b;  κ = 1, λ = 0
d_{q}^{(λ)}z^{λ+q−1};  κ = 1, λ = 1, …, \frac{q−1}{2}

d_{κ−1}^{(0)}hz^{κ−2} + bd_{κ}^{(0)}z^{κ−1}

+d_{κ+q−1}^{(0)}z^{κ+q−2};  3 ≤ κ ≤ q − 2, κ odd, λ = 0

−((λ − 1)d_{κ−1}^{(λ)}h + d_{κ−1}^{(λ−1)})z^{κ+λ−2}

+bd_{κ}^{(λ)}z^{κ+λ−1} + d_{κ+q−1}^{(λ)}z^{κ+λ+q−2}; 3 ≤ κ ≤ q − 2, κ odd, λ = 1, …, \frac{κ−3}{2}

−d_{κ−1}^{( \frac{κ−3}{2} )}z^{\frac{3κ−5}{2}} + bd_{κ}^{( \frac{κ−1}{2} )}z^{\frac{3κ−3}{2}}

+d_{κ+q−1}^{( \frac{κ−1}{2} )}z^{\frac{3κ+2q−5}{2}} ;  3 ≤ κ ≤ q − 2, κ odd, λ = \frac{κ−1}{2}
d_{κ+q−1}^{(λ)}z^{κ+λ+q−2};  3 ≤ κ ≤ q − 2, κ odd, λ = \frac{κ+1}{2}, …, \frac{κ+q−2}{2}

d_{κ−1}^{(0)}hz^{κ−2} + bd_{κ}^{(0)}z^{κ−1}

+d_{κ+q−1}^{(0)}z^{κ+q−2};  2 ≤ κ ≤ q − 3, κ even, λ = 0

−((λ − 1)d_{κ−1}^{(λ)}h + d_{κ−1}^{(λ−1)})z^{κ+λ−2}

+bd_{κ}^{(λ)}z^{κ+λ−1} + d_{κ+q−1}^{(λ)}z^{κ+λ+q−2}; 2 ≤ κ ≤ q − 3, κ even, λ = 1, …, \frac{κ−2}{2}
−d_{κ−1}^{( \frac{κ−2}{2} )}z^{\frac{3κ−4}{2}} + d_{κ+q−1}^{(κ/2)}z^{\frac{3κ+2q−4}{2}} ;  2 ≤ κ ≤ q − 3, κ even, λ = \frac{κ}{2}
d_{κ+q−1}^{(λ)}z^{κ+λ+q−2};  2 ≤ κ ≤ q − 3, κ even, λ = \frac{κ+2}{2}, …, \frac{κ+q−3}{2}
0;  otherwise,

and

b_{κ}(z) =

\begin{cases}−(az + bz^{2} + c_{q−1}^{(0)}z^{q+1})f(z) − ∑_{μ=1}^{\frac{q−1}{2}} c_{q−1}^{(μ)}h^{μ}z^{μ+q+1}f^{(μ)}(z); & κ = 0 \\ −c_{q}^{(0)}z^{q}f(z) − h(c_{q}^{(1)}z^{q+1} − z)f′(z) − ∑_{μ=2}^{\frac{q−1}{2}} c_{q}^{(μ)}h^{μ}z^{μ+q}f^{(μ)}(z); & κ = 1 \\ −(bc_{κ}^{(0)}z^{κ} + c_{κ+q−1}^{(0)}z^{κ+q−1})f(z) \\ − ∑_{μ=1}^{\frac{κ−1}{2}}((c_{κ−1}^{(μ−1)} − μhc_{κ−1}^{(μ)})z^{κ+μ−1} \\ +bc_{κ}^{(μ)}z^{κ+μ} + c_{κ+q−1}^{(μ)}z^{κ+μ+q−1})h^{μ}f^{(μ)}(z) \\ −(c_{κ−1}^{( \frac{κ−1}{2} )}z^{\frac{3κ−1}{2}} + c_{κ+q−1}^{( \frac{κ+1}{2} )}z^{\frac{3κ+2q−1}{2}} )h^{\frac{κ+1}{2}} f^{( \frac{κ+1}{2} )}(z) \\ − ∑_{μ= \frac{κ+3}{2}}^{\frac{κ+q−2}{2}} c_{κ+q−1}^{(μ)}h^{μ}z^{κ+μ+q−1}f^{(μ)}(z); & 3 ≤ κ ≤ q − 2, κ odd \\ −(bc_{κ}^{(0)}z^{κ} + c_{κ+q−1}^{(0)}z^{κ+q−1})f(z) \\ − ∑_{μ=1}^{\frac{κ−2}{2}}((−μhc_{κ−1}^{(μ)} − c_{κ−1}^{(μ−1)})z^{κ+μ−1} \\ +bc_{κ}^{(μ)}z^{κ+μ} + c_{κ+q−1}^{(μ)}z^{κ+μ+q−1})h^{μ}f^{(μ)}(z) \\ −(−c_{κ−1}^{( \frac{κ−2}{2} )}z^{\frac{3κ−2}{2}} + bc_{κ}^{(κ/2)}z^{3κ/2} + c_{κ+q−1}^{(κ/2)}z^{\frac{3κ+2q−2}{2}} )h^{κ/2}f^{(κ/2)}(z) \\ − ∑_{μ= \frac{κ+2}{2}}^{\frac{κ+q−1}{2}} c_{κ+q−1}^{(μ)}h^{μ}z^{κ+μ+q−1}f^{(μ)}(z); & 2 ≤ κ ≤ q − 3, κ even. \end{cases}

A.5. Proof of Lemma 20. Using Lemma 18 plus the facts that h is even and that b is odd (recall (5.1)), we find that, for 0 ≤ κ, λ ≤ q − 2,

ω_{κ,λ} ≡ \begin{cases}1; & κ = λ = 0 \\ z^{\frac{3κ−3}{2}} ; & 1 ≤ κ ≤ q − 2, κ odd, λ = \frac{κ−1}{2} \\ z^{\frac{3κ+3q−6}{2}} ; & 1 ≤ κ ≤ q − 2, κ odd, λ = \frac{κ+q−2}{2} \\ z^{\frac{3κ−4}{2}} ; & 2 ≤ κ ≤ q − 3, κ even, λ = \frac{κ}{2} \\ 0; & otherwise \end{cases}\} mod 2.  (A.13)

(i) Writing

det Δ_{q} ≡ ∑_{σ∈Sym({0,1,...,q−2})} ω_{0,σ(0)}ω_{1,σ(1)} ⋯ ω_{q−2,σ(q−2)} mod 2,  (A.14)

we see that the only non-zero contribution on the right-hand side occurs for the permutation σ given by

σ(κ) = \begin{cases}\frac{κ+q−2}{2}; & 1 ≤ κ ≤ q − 2, κ odd \\ \frac{κ}{2}; & 0 ≤ κ ≤ q − 3, κ even. \end{cases}  (A.15)

Indeed, we clearly must have σ(0) = 0, which in turn forces σ(1) = \frac{q−1}{2}; further, for κ ≥ 2 even, we must have σ(κ) = κ/2, and this in turn forces σ(κ) = \frac{κ+q−2}{2} for κ ≥ 3 odd, since the alternative value \frac{κ−1}{2} already occurs as image of the even number κ − 1. It follows that, modulo 2,

det Δ_{q} ≡ z^{\frac{3q−3}{2}} ·_{∏_{3≤κ≤q−2} ; κ odd}z^{\frac{3κ+3q−6}{2}} ·_{∏_{2≤κ≤q−3} ; κ even}z^{\frac{3κ−4}{2}} ≡ z^{e},

where

e = \frac{3(q − 1)}{2} + _{∑_{3≤κ≤q−2} ; κ odd} \frac{3κ + 3q − 6}{2} + _{∑_{2≤κ≤q−3} ; κ even} \frac{3κ − 4}{2}

= \frac{3(q − 1)}{2} + \frac{9(q − 1)(q − 3)}{8} + \frac{3(q − 1)(q − 3)}{8} − (q − 3)

= \frac{3q^{2} − 11q + 12}{2}.

The fact that

det Δ_{q} ≡ det Δ_{0,0} mod 2

follows immediately by expanding det Δ_{q} modulo 2 with respect to the 0-th row.

(ii) For 1 ≤ κ ≤ q − 2, we have

det Δ_{κ,0} ≡ ∑_{σ} ω_{0,σ(0)} ⋯ ω_{κ−1,σ(κ−1)}ω_{κ+1,σ(κ+1)} ⋯ ω_{q−2,σ(q−2)} ≡ 0 mod 2.

Here, σ runs through all bijections of the set {0, …, κ − 1, κ + 1, …, q − 2} onto the set {1, 2, …, q − 2}, and ω_{0,σ(0)} ≡ 0 (mod 2) for each such σ. □

A.6. Proof of Lemma 21 (sketch). Using Lemma 18 plus the facts that h and b are odd, we find that, for 0 ≤ κ, λ ≤ q − 2,

ω_{κ,λ} ≡ \begin{cases}1; & κ = λ = 0 \\ z^{\frac{3q−3}{2}} ; & κ = 0, λ = \frac{q−3}{2} even \\ z^{\frac{3κ−7}{2}} ; & 3 ≤ κ ≤ q − 2, κ odd, λ = \frac{κ−3}{2} even \\ z^{\frac{3κ−5}{2}} + z^{\frac{3κ−3}{2}} ; & 3 ≤ κ ≤ q − 2, κ odd, λ = \frac{κ−1}{2} odd \\ z^{\frac{3κ−3}{2}} ; & 1 ≤ κ ≤ q − 2, κ odd, λ = \frac{κ−1}{2} even \\ z^{\frac{3κ+3q−6}{2}} ; & 1 ≤ κ ≤ q − 2, κ odd, λ = \frac{κ+q−2}{2} \\ z^{\frac{3κ−6}{2}} + z^{\frac{3κ−4}{2}} ; & 2 ≤ κ ≤ q − 3, κ even, λ = \frac{κ−2}{2} even \\ z^{\frac{3κ−4}{2}} ; & 2 ≤ κ ≤ q − 3, κ even, λ = \frac{κ}{2} \\ z^{\frac{3κ+3q−7}{2}} ; & 2 ≤ κ ≤ q − 3, κ even, λ = \frac{κ+q−3}{2} even \\ 0; & otherwise \end{cases}\} mod 2. (A.16)

First suppose that q ≡ 1 (mod 4). For illustration, we display Δ_{13} modulo 2:

(\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & z^{18} & 0 & 0 & 0 & 0 & 0 \\ 1 + z & z & 0 & 0 & 0 & 0 & z^{19} & 0 & 0 & 0 & 0 & 0 \\ z & z^{2} + z^{3} & 0 & 0 & 0 & 0 & 0 & z^{21} & 0 & 0 & 0 & 0 \\ 0 & 0 & z^{4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & z^{6} & 0 & 0 & 0 & 0 & 0 & z^{24} & 0 & 0 & 0 \\ 0 & 0 & z^{6} + z^{7} & z^{7} & 0 & 0 & 0 & 0 & z^{25} & 0 & 0 & 0 \\ 0 & 0 & z^{7} & z^{8} + z^{9} & 0 & 0 & 0 & 0 & 0 & z^{27} & 0 & 0 \\ 0 & 0 & 0 & 0 & z^{10} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & z^{12} & 0 & 0 & 0 & 0 & 0 & z^{30} & 0 \\ 0 & 0 & 0 & 0 & z^{12} + z^{13} & z^{13} & 0 & 0 & 0 & 0 & z^{31} & 0 \\ 0 & 0 & 0 & 0 & z^{13} & z^{14} + z^{15} & 0 & 0 & 0 & 0 & 0 & z^{33} \end{matrix})

In the same way as in the proof of the preceding lemma, it can be seen that there is exactly one permutation in Sym({0, 1, …, q − 2}) leading to a non-zero contribution in the expansion (A.14) of the determinant of Δ_{q} modulo 2. This permutation is in fact the one in (A.15). The rest of the argument is completely analogous to the one before.

Now let q ≡ 3 (mod 4). We illustrate this situation by displaying Δ_{11} modulo 2:

(\begin{matrix}1 & 0 & 0 & 0 & z^{15} & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & z^{15} & 0 & 0 & 0 & 0 \\ 1 + z & z & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ z & z^{2} + z^{3} & 0 & 0 & 0 & 0 & z^{18} & 0 & 0 & 0 \\ 0 & 0 & z^{4} & 0 & 0 & 0 & z^{19} & 0 & 0 & 0 \\ 0 & 0 & z^{6} & 0 & 0 & 0 & 0 & z^{21} & 0 & 0 \\ 0 & 0 & z^{6} + z^{7} & z^{7} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & z^{7} & z^{8} + z^{9} & 0 & 0 & 0 & 0 & z^{24} & 0 \\ 0 & 0 & 0 & 0 & z^{10} & 0 & 0 & 0 & z^{25} & 0 \\ 0 & 0 & 0 & 0 & z^{12} & 0 & 0 & 0 & 0 & z^{27} \end{matrix}) .  (A.17)

Here, there are more permutations leading to non-zero contributions in the expansion (A.14) of det Δ_{q} modulo 2. Namely, there are precisely two non-zero entries modulo 2 in the 0-th row, occurring in columns 0 and (q − 3)/2. If we decree that σ(0) = 0, then there is precisely one way to complete this into a permutation leading to a non-zero contribution in the expansion of det Δ_{q} modulo 2, namely the permutation (A.15). If, on the other hand, we set σ(0) = \frac{q−3}{2}, then the sum of the contributions corresponding to this subset of permutations is given by the minor of Δ_{q} formed by deleting the 0th row and the \frac{q−3}{2}-th column. This minor can be further reduced by observing that every other column in the right half of the minor contains precisely one non-zero entry modulo 2. (In (A.17), these are the 5-th, 7-th, and 9-th column.) In our running example, it is seen in this way that det Δ_{11} modulo 2 equals the determinant

det (\begin{matrix}1 + z & z & 0 & 0 & 0 & 0 \\ z & z^{2} + z^{3} & 0 & 0 & z^{18} & 0 \\ 0 & 0 & z^{4} & 0 & z^{19} & 0 \\ 0 & 0 & z^{6} + z^{7} & z^{7} & 0 & 0 \\ 0 & 0 & z^{7} & z^{8} + z^{9} & 0 & z^{24} \\ 0 & 0 & 0 & 0 & 0 & z^{25} \end{matrix}) .

From the form of the above matrix, it is obvious that its determinant is equal to

det (\begin{matrix}1 + z & z \\ z & z^{2} + z^{3} \end{matrix}) · z^{19} · det (\begin{matrix}z^{6} + z^{7} & z^{7} \\ z^{7} & z^{8} + z^{9} \end{matrix}) · z^{25} = ±z^{60}(z^{2} + 2z)^{2} ≡ z^{64} mod 2.

In general, this pattern that the minor under consideration can be expanded as a product of powers of z and 2 × 2-minors, each of which contributes only a power of z, persists and, in the end, leads to the result asserted in (i).

The argument for establishing the formulae for the minors is similar. □

A.7. Proof of Lemma 22. We shall use the formula

\frac{d^{ν}}{dz^{ν}} A(B(z)) = _{∑_{π_{1},...,π_{ν}≥0} ; π_{1}+2π_{2}+···+νπ_{ν}=ν} \frac{ν!}{∏_{j≥1}(j!)^{π_{j}}π_{j}!} [ ∏_{j≥1} (B^{(j)}(z))^{π_{j}}] A^{(π_{1}+···+π_{ν})}(B(z))

(A.18)

for the derivatives of a composite function, which is known as the Faà di Bruno formula (cf. [6, Sec. 3.4]; but see also [7, 15]). In view of the left-hand side, Formula (A.18) implies in particular the integrality assertion in Item (i). In fact, the coefficients occurring in (A.18) have a natural combinatorial interpretation (see [1, Theorem 13.2]).

Applying (A.18) with A(t) = e^{t} and B(z) = h^{−1} ∫ S_{Γ}^{H}(z) dz, Equation (5.22) follows immediately in view of (5.5).

Finally, using the facts that (S_{Γ}^{H}(z))^{(j)} ≡ 0 (mod 2) for j ≥ 2, and that

\frac{ν!}{(ν − 2μ)!2^{μ}μ!} = \binom{ν}{2μ} · ∏_{1≤k≤μ}(2k − 1) ≡ \binom{ν}{2μ} mod 2,

we find from (5.22) that, modulo 2,

h^{ν}(\frac{d^{ν}}{dz^{ν}} H_{Γ}^{H}(z))/H_{Γ}^{H}(z) ≡ _{∑_{π_{1},π_{2}≥0} ; π_{1}+2π_{2}=ν}h^{ν−π_{1}−π_{2}} \frac{ν!}{∏_{j=1}^{2}(j!)^{π_{j}}π_{j}!} ∏_{j=1}^{2} ((S_{Γ}^{H}(z))^{(j−1)})^{π_{j}}

≡ ∑_{μ=0}^{⌊ \frac{ν}{2} ⌋} h^{μ}\binom{ν}{2μ}((S_{Γ}^{H}(z))′)^{μ}(S_{Γ}^{H}(z))^{ν−2μ},

in accordance with (5.23). Our last claim (5.24) is an immediate consequence of (5.23). □

References

[1] G. E. Andrews, The Theory of Partitions, Encyclopedia of Math. and its Applications, Vol. 2, Addison–Wesley, Reading, 1976; reprinted by Cambridge University Press, Cambridge, 1998.

[2] R. Bieri, Homological Dimension of Discrete Groups, Queen Mary College Mathematics Notes, second edition, London, 1981 (first edition 1976).

[3] P. J. Cameron, Combinatorics, Cambridge University Press, 1994.

[4] I. M. Chiswell, Exact sequences associated with a graph of groups, J. Pure and Appl. Algebra 8 (1976), 63–74.

[5] S. Chowla, I. N. Herstein, and W. K. Moore, On recursions connected with symmetric groups I, Can. J. Math. 3 (1951), 328–334.

[6] L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht, Holland, 1974.

[7] A. D. D. Craik, Prehistory of Faà di Bruno’s formula, Amer. Math. Monthly 112 (2005), 119–130.

[8] G. Frobenius, Verallgemeinerung des Sylow’schen Satzes, Sitz.ber. Königl. Preuss. Akad. Wiss. Berlin (1895), 981–993.

[9] G. Frobenius, Über einen Fundamentalsatz der Gruppentheorie, Sitz.ber. Königl. Preuss. Akad. Wiss. Berlin 44 (1903), 987–991.

[10] C. Godsil, W. Imrich, and R. Razen, On the number of subgroups of given index in the modular group, Monatshefte Math. 87 (1979), 273–280.

[11] I. P. Goulden and D. M. Jackson, The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group, Europ. J. Combin. 13 (1992), 357–365.

[12] M. Hall, The Theory of Groups, 2nd edition, Chelsea Publishing Company, New York, 1976.

[13] P. Hall, A contribution to the theory of groups of prime-power order, Proc. London Math. Soc. (2) 36 (1934), 29–95.

[14] P. Hall, On a theorem of Frobenius, Proc. London Math. Soc. (2) 40 (1935), 468–501.

[15] W. P. Johnson, The curious history of Faà di Bruno’s formula, Amer. Math. Monthly 109 (2002), 217–234.

[16] E. Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math. 44 (1852), 93–146. Reprinted in: Collected Papers (edited by A. Weil), Vol. I, 485–538, Springer, New York, 1975.

[17] A. Lubotzky and D. Segal, Subgroup Growth, Progress in Math., vol. 212, Birkhäuser, Basel, 2003.

[18] R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, Springer, New York, 1977.

[19] M. H. Millington, Subgroups of the classical modular group, J. London Math. Soc. (2) 1 (1969), 351–357.

[20] W. Magnus, A. Karrass, and D. Solitar, Combinatorial Group Theory, John Wiley & Sons, New York, 1966.

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

[22] T. W. Müller, Subgroup growth of free products, Invent. math. 126 (1996), 111–131.

[23] T. W. Müller, Enumerating representations in finite wreath products, Adv. in Math. 153 (2000), 118–154.

[24] T. W. Müller, Representations in finite wreath products: Enumerative theory and applications, in: Proc. Groups Korea ’98 (Y. G. Baik, D. L. Johnson, and A. C. Kim eds.), Walter de Gruyter, Berlin, 2000, 243–290.

[25] T. W. Müller, Five lectures on generalized permutation representations, Mat. Contemp. 20 (2001), 227–272.

[26] T. W. Müller, Modular subgroup arithmetic in free products, Forum Math. 15 (2003), 759–810.

[27] T. W. Müller, Modular subgroup arithmetic, in: Groups, Combinatorics and Geometry (Durham 2001; A. A. Ivanov, M. W. Liebeck, and J. Saxl, eds.), World Scientific, Singapore, 2003, pp. 193– 225.

[28] T. W. Müller, Parity patterns in Hecke groups and Fermat primes, in: Groups: Topological, Combinatorial and Arithmetic Aspects, (T. W. Müller ed.), LMS Lecture Notes Series 311, Cambridge University Press, Cambridge, 2004, 327–374.

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

[30] H. Ochiai, A p-adic property of the Taylor series of exp(x + x^{p}/p), Hokkaido Math. J. 28 (1999), 71–85.

[31] G.-C. Rota, On the foundations of combinatorial theory I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie 2 (1964), 340–368.

[32] R. P. Stanley, Enumerative Combinatorics I, Wadsworth, Belmont (California), 1986.

[33] W. Stothers, The number of subgroups of given index in the modular group, Proc. Royal Soc. Edinburgh, Sec. A 78 (1977), 105–112.

[34] B. A. F. Wehrfritz, Finite Groups, World Scientific, Singapore, 1999.

Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria

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