Using the Eichler-Selberg Trace formula to compute class numbers?

The Eichler-Selberg trace formula (Theorem 2.2 here) gives a relation between the trace of a Hecke operator acting on the space of cusp forms and sums of weighted class numbers of imaginary quadratic orders. For example, by putting $$N = 1$$, $$k = 2$$ and $$\omega'$$ to be the trivial character, we get $$H(-4n) + 2\sum_{t = 1}^{\lceil\sqrt{4n}\rceil - 1} H(t^2 - 4n) = 2\left(\sum_{d|n} d\right) - 2\left(\sum_{\substack{d|n \\ d<\sqrt{n}}} d\right) - \chi(n)\sqrt{n} + \frac{1}{6}\chi(n),$$ where $$H(D)$$ denotes the Hurwitz class number and $$\chi(n)$$ is $$1$$ if $$n$$ is a square and $$0$$ otherwise. Here are a few questions that I would like to ask:

1. Is there some source listing more interesting relations like this which can be obtained by plugging in suitable parameters in the trace formula?
2. Can such equations be used to compute class numbers efficiently? I am aware of algorithms above which uses the above formula for verifying its correctness (see here), but I don't know if such formulas themselves can be used to compute the class numbers. If so, are they able to match the efficiency of other state-of-the-art algorithms? The only such algorithm I am aware of is Corollary 5.3.9 in Cohen's Computational Algebraic Number Theory, but that one is not so fast.

Where should I be looking to find more research on this? Thanks!

Generally speaking, formulas like the trace formula admit an uncertainty principle: To obtain an identity where one side is highly concentrated (e.g. a sum over a small number of class numbers, or even a single one) the other side must be highly spread out (involving contributions from many different modular forms). So their power to compute an individual value on one side is limited, requiring computing many values on the other side to obtain the answer. (Contrastingly, if your goal is to evaluate certain long sums, they can be highly computationally efficient.)

Formulas like yours will arise from any $$N,k$$ where there are not any cusp forms. This requires $$N,k$$ small (except maybe if $$k=1$$, but then computing if there are any cusp forms is itself nontrivial). For some other $$N,k$$ there will be nice presentations of all the cusp forms in terms of theta series, so you'll get formulas like this but also involving the number of ways of representing an integer as a quadratic forms. For other $$N,k$$ you can cancel all the cusp forms by inserting some polynomial in the Hecke operators (if the only cusp forms of a given weight and level have $$T_2$$ eigenvalues equal to $$1, 0, -1$$ then the trace of $$(T_2^3-T_2) T_n$$ can be expressed without using any cusp forms, and this gives something on the geometric side). However, none of these will be particularly effective for isolating a single class number.

If your goal is to isolate a single class number, the technique I know is to apply a version of the trace formula that incorporates both Hecke and Atkin-Lehner operators. Atkin-Lehner operators on the spectral side give on the geometric side congruence conditions on the parameter $$t$$. In favorable cases these congruence conditions result in only a single class number appearing.

An example is provided on p. 5 of the paper Murmurations by Nina Zubrilina. When the paramaters $$P, N$$ of the first displayed equation satisfy $$P< 4N$$ then the right hand side consists only of the Hurwitz class number $$H_1(-4 PN )$$. This uses a trace formula due to Yamauchi together with corrections due to Skoruppa and Zagier of computational errors. However, the other side of this formula involves sums over modular forms of level $$N$$. This is a sum of length, very roughly, $$N$$ which is of size at least the square-root of the discriminant $$4PN$$ of the class number.

I'm not sure how this compares to the direct algorithms for computing the class number.

• Thanks for the answer! I was originally wondering if we have more linear recurrences like the one in my post, maybe it becomes easier to compute the class number. But I never knew you can isolate a single class number like this! I definitely have more directions to look at now. Mar 4 at 16:04
• Also, can you elaborate more about "if your goal is to evaluate certain long sums, they can be highly computationally efficient"? Are there any good non-trivial examples of this? Mar 4 at 16:06
• @KyawShinThant What I mean is that you may start with a question about the distribution of the class numbers of a large family of number fields, or the distribution of the Hecke eigenvalues of a large family of modular forms, and reduce the question to a sum of Hecke eigenvalues or a sum of class numbers. Then the trace formula might turn that into a short sum that is easy to compute. From one point of view these questions may be artificial (is that what you mean by trivial?) but from another they are very natural. Mar 4 at 17:45
• @KyawShinThant In concrete terms I'm thinking about things like Serre's equidistribution theorem for eigenvalues of Hecke operators, which is not a computational statement but rather an analytic result. But the nature of the method is that the trace formula gives you a formula for some natural sums of Hecke eigenvalues, and then you bound the terms in the formula. Computing the terms in the formula instead would give an algorithm to compute something. Mar 4 at 17:47
• @WillSawin's point is well-illustrated by "explicit formulas", e.g., Guinand's explication of Riemann (-vonMangoldt)'s formula. There is indeed a Fourier duality, even with the simplest zetas and such things. So the "Heisenberg uncertainty" (really a simple theorem about Fourier transforms) principle applies. :) Mar 4 at 21:56

A similar approach, using the closely related Selberg Trace Formula, is used by Ce Bian, Andrew R. Booker, Austin Docherty, Michael J. Jacobson, Jr., and Andrei Seymour-Howell in their paper Unconditional computation of the class groups of real quadratic fields (link to paper, to appear in LuCANT's proceedings; it's not on the arxiv).

As Will notes, they have to fight against an uncertainty principle and compute a large amount of data on one side to determine class numbers. They work rather hard to devise explicit, computationally amenable combinations of test functions to actually determine these class numbers.