Combinatorics of traces of Hecke operators

1. Introduction and Statement of Results

Throughout this article, let k be a positive integer, and let S _{2 k}(Γ₀(N)) [respectively (resp.), ] denote the space generated by the weight 2k cusp forms (resp. newforms) on the congruence subgroup Γ₀(N) (see refs. 1 and 2 for background on modular forms). For positive integers n and N, which are coprime, define the integers Tr_{2 k}(Γ₀(N), n) and by the following: Recent works (for example, see refs. 3–7) have proven congruences between such traces and combinatorial numbers, such as the Apéry numbers. For example, Ahlgren and K.O. (3) confirmed the following conjecture of Beukers: for every odd prime p. Many more such congruences for traces are obtained in ref. 4.

In view of these congruences, it is natural to investigate the intrinsic combinatorial properties of these traces. In the n aspect (i.e., where 2k and N are fixed), one does not expect to find a simple combinatorial description of these traces. However, in the weight aspect, these traces are combinatorial numbers. We begin by presenting four examples of this phenomenon.

There are many instances in which these traces are combinatorial numbers analogous to the Apéry numbers. For example, we establish the following fact.

Theorem 1.1. If k ≥ 2, then

Theorem 1.1 provides a combinatorial formula for the trace of T ₂ on the space of cusp forms for the congruence subgroup Γ₀(7). Such formulas are often connected closely to hypergeometric functions. First, we recall the traditional notation for these functions. If n is a positive integer, then define (a)_n by the following: If n = 0, then let (a)_n:= 1. Gauss' ₂ F ₁ hypergeometric functions are defined by the following: We establish the following formula involving ₂ F ₁ functions (which are Gegenbauer polynomials).

Theorem 1.2. If k ≥ 3, then

In general, we will demonstrate that, apart from certain simple summands, Hecke traces are almost always sums of such ₂ F ₁ evaluations.

In view of the combinatorial formulas in Theorems 1.1 and 1.2, it is natural to wonder whether these traces are connected to classical topics in enumerative combinatorics. The next two examples confirm this speculation.

If n is a nonnegative integer, then let For example, Fig. 1 shows the five tilings when n = 3.

It turns out that Tr₁₂(Γ₀(3), 2) = 6·T(3) = 30, which is an example of the following more general result.

Theorem 1.3. If k ≥ 3, then

As another example, we consider Motzkin paths. An elevated Motzkin path of length n is a lattice path that lies strictly above the x axis, apart from its endpoints (0, 0) and (n, 0), with steps of the form (1, 1), (1, –1), and (1, 0). If n ≥ 2, then let For example, Fig. 2 shows the four elevated Motzkin paths of length 5.

Therefore, M_a(5) = 20. It results that Tr₁₂(Γ₀(4), 3) = 12·M_a(5) = 240. This formula also generalizes to other weights, as given in the following result.

Theorem 1.4. If k ≥ 3, then

The four theorems given above are special cases of a general theorem concerning the combinatorial properties of the traces of Hecke operators in weight aspect. To illustrate this general phenomenon, consider the cusp forms given by the following: (note that q:= e ^2πiz throughout). By the Atkin–Lehner theory, such a cusp form is essentially (and often exactly) the sum of the newforms in the space .

To study the coefficients of these cusp forms, it is convenient to employ the Eichler–Selberg trace formula (for example, see refs. 8–10). Although these formulas are quite formidable at first glance, we make some elementary observations that reveal some surprisingly simple properties leading to results such as the theorems given above.

For the group Γ₀(8), consider the forms :

For general N, we use these coefficients, grouped by column, to define the following power series: Similarly, we consider the following power series: For the forms in 1.8, calculations suggest that these series are rational functions. In particular, for levels 3, 5, and 7, calculations suggest the following formulas: and These formulas prove to be correct, and indeed more is true. For generating functions of traces in general, we prove the following result.

Theorem 1.5. If N is a positive integer, and if n ≥ 2 is prime to N, then R ^new(Γ₀(N), n; x) and R(Γ₀(N), n; x) are both rational functions in (x). Moreover, all of their poles are simple and are algebraic numbers of degree ≤ 2 over .

In section 3, we obtain Theorem 3.3, which is a result describing a basis of rational functions that are summands for R(Γ₀(N), n; x). By the Atkin–Lehner theory of newforms, Theorem 1.5 follows as an immediate corollary. The most complicated rational functions appearing in Theorem 3.3 are of the following form: By using the well known generating functions for the Gegenbauer (also known as ultraspherical) polynomials (for example, see section 6.4.10 in ref. 11), and the fact that (for example, see section 6.4.12 in ref. 11), it is not difficult to deduce the following: Consequently, it follows in general that Hecke traces are essentially simple sums of values of Gegenbauer polynomials as in Theorem 1.2.

Theorem 3.3, which is not difficult to prove, follows from an analysis of the intrinsic combinatorial structure of the Eichler–Selberg trace formula for Hecke operators. In section 2, we recall a formulation of this result, and we make some key observations. In the last section, we derive Theorems 1.1–1.4.

2. The Eichler–Selberg Trace Formula

Our methods involve reformulating the Eichler–Selberg trace formula for Tr_{2 k}(Γ₀(N), n) (see refs. 8–10). We use the version of this trace formula due to Hijikata (see refs. 9 and 12). Fix throughout positive integers k, N, and n. Let Decompose E into the disjoint union E = E′ ∪ E″, where (s ∈ E′ (resp., s ∈ E″) if the discriminant of is 1 modulo 4 (resp., 0 modulo 4). For each s ∈ E ∪ H ∪ P, define the nonnegative integer t = t(s) by the following: Then define the following sets of integers: Furthermore, for s ∈ E ∪ H ∪ P, define y and ȳ to be the roots of X ² – sX + n = 0, and accordingly let Finally, let and, if n is a perfect square, otherwise, σ(k, N, n):= 0.

Theorem 2.1 (ref. 12 , theorem 0.1). If N and n are positive coprime integers, and k ≥ 1, then where b(s, f, n), c(s, f, N, n) are rational numbers depending only on s, f, N, and n, and they are given explicitly (see refs. 9 , section 2, and 12 , section 0).

Remark: The numbers b(s, f, n) in the statement of the theorem are given in terms of class numbers of orders of imaginary quadratic fields if s ∈ E and in terms of Euler's φ-function if s ∈ H. The numbers c(s, f, N, n) are calculated by counting solutions to certain congruences. In both cases, the numbers can be calculated explicitly, but for brevity, we do not repeat their definitions here. The main observation is that their values are independent of the weight 2k.

3. Proof of Theorem 1.5

Throughout this section we fix coprime positive integers n and N, and we recall the definition of the following generating function: from 1.10. In this section, we explore the combinatorics of the variation of Tr_{2 k}(Γ₀(N), n) in k. By the Atkin–Lehner theory of newforms, R ^new(Γ₀(N), n; x) is an integral linear combination of R(Γ₀(M), n; x), where M|N. Hence, it suffices to examine R(Γ₀(N), n; x). In particular, in Theorem 3.3, which is a more precise version of Theorem 1.5, we determine an explicit formula for R(Γ₀(N), n; x).

Continuing with the notation of section 2, we first make the following observation about the coefficients a(s, k, n) for s ∈ E.

Proposition 3.1. If s ∈ E, then

Proof: From 2.6, when s ∈ E, This sum can be expressed in terms of powers of yȳ and y + ȳ by using the following relation: Then, a straightforward induction, in conjunction with the relations y + ȳ = s and yȳ = n, yields the desired expression.

We next determine the generating function for the power series with coefficients a(s, k, n), for s ∈ E.

Lemma 3.2. If s ∈ and s ² – 4n < 0, then

Proof: The proof follows from Proposition 3.1 and from the following: which is simply the binomial theorem. More specifically, we have the following: where the first equality follows from Proposition 3.1, the second equality follows after reindexing the sums, and the third equality follows from 3.3.

Now, let and where c(, 1, N, n) is defined as in ref. 12, section 0.

Theorem 3.3. If N and n are coprime positive integers, then

Proof: We proceed by using the trace formula from Theorem 2.1. The first and second terms in the proposed formula for R(Γ₀(N), n; x) follow easily from 2.7 and 2.8. The third term arises from the terms in the trace formula corresponding to s ∈ P. (We use the fact that b(s, 1, n) = 1, as in section 0 of ref. 12.) The sum on divisors d of n with corresponds to the terms in the trace formula coming from s ∈ H. Finally, by using Lemma 3.2, the last sum corresponds to the sum on s ∈ E in the trace formula.

Remark: By taking n = 1, Theorem 3.3 provides generating functions for dimensions of spaces of modular forms. For example,

4. Combinatorial Theorems

Here, we prove Theorems 1.1–1.4. These results follow from an analysis of the generating functions described in Theorem 3.3.By using this result, it is straightforward to verify the following proposition.

Proposition 4.1. With the notation as in 1.10, we have

Proof of Theorem 1.1: By Proposition 4.1, we have the following: To prove the theorem, it suffices to show the following: where the integers a(n) are defined by the following: This is a straightforward calculation involving recurrence relations.

Proof of Theorem 1.2: By Proposition 4.1, we have the following: The theorem follows from 1.11.

Proof of Theorem 1.3: By Proposition 4.1, we have the following: By replacing x by –x, we obtain the known recurrence for 6T(n) (see ref. 13, theorem 1).

Proof of Theorem 1.4: By Proposition 4.1, we have the following: By replacing x by –x, we obtain the known recurrence for 12M_a(n) (see ref. 14, propositions 1 and 2).

In view of the results presented here, it is natural to revisit the properties of the Hecke operators from a purely combinatorial perspective. For example, it is natural to ask the following question.

Question. Are there direct combinatorial proofs of Theorems 1.1–1.4 using the theory of modular symbols?