In Discrete groups, expanding graphs, and invariant measures (in the notes at the end of Chapter 7), Lubotzky mentions that certain estimates for the number of spanning trees $\kappa(G)$ of a $k$-regular graph $G$ have nontrivial arithmetic consequences such as estimates for the class number of certain interesting function fields, citing an unpublished paper of Sarnak from 1988, Number theoretic graphs, which I can't find anywhere on the internet.

I have heard that the class number for the function field of the modular curve $X(N)$ over $\mathbb{F}_p$ is related to the number of spanning trees in the $(p+1)$-regular supersingular isogeny graph $G(N,p)$, whose vertices are supersingular elliptic curves over $\mathbb{F}_N$ and edges are degree $p$ isogenies. I'm not sure about the details of this, so please correct me if I'm wrong here.

Is this the connection Lubotzky was talking about? If so I must be misunderstanding something because Lubotzky mentions that the combinatorial result which has arithmetic corollaries is the following lower bound due to Alon: $$\beta(k)=k-O\left(k \frac{(\log \log k)^2}{\log k}\right)$$ where $\beta(k)$ is the limit inferior of $\kappa(G)^\frac{1}{|G|}$ over all $k$-regular graphs. On the other hand, I believe that, for supersingular isogeny graphs, as $N$ goes to infinity the girth also goes to infinity (correct me if I'm wrong), and for graphs with girth going to infinity it is known that $\kappa(G)^\frac{1}{|G|}$ approaches the constant $\frac{(k-1)^{k-1}}{(k(k-2))^{\frac{k}{2}-1}}$ (see e.g. Lyons, Russell, Asymptotic enumeration of spanning trees), so Alon's result doesn't tell us anything in this case.

Question 1: Does anyone know where I can find this paper of Sarnak, to help sort this out?

Question 2: Am I right that Alon's estimate doesn't say anything about supersingular isogeny graphs, and if so what is the application of Alon's estimate that Lubotzky had in mind?

Edit: I believe that my claim that the girth of supersingular isogeny graphs go to infinity with $N$ is actually false (I confused with other related graphs). On the other hand, I think it is still true that these graphs converge in the Benjamini-Schramm sense to the $k$-regular tree, so we still have that $\kappa(G)^\frac{1}{|G|}$ approaches $\frac{(k-1)^{k-1}}{(k(k-2))^{\frac{k}{2}-1}}$.

  • 1
    $\begingroup$ I started to write up an answer pointing you to arxiv.org/abs/math/0701075 , but on reflection it isn't as relevant as I thought it was. So I'll make it a more brief comment. Let $R$ be a dvr and let $\mathcal{X}$ be a regular semistable curve over $\text{Spec}(R)$. Let $X$ be the general fiber and $X_0$ the special fiber. Let Let $\Gamma$ be the graph whose vertices are the components of $X_0$ and whose edges are the nodes of $X_0$. $\endgroup$ Jul 15 at 15:53
  • 1
    $\begingroup$ Then there is an abelian group called $\text{Pic}^0(\Gamma)$ whose cardinality is the number of spanning trees of $\Gamma$, and there is a specialization map $\text{Pic}^0(X)(K) \to \text{Pic}^0(\Gamma)$. $\endgroup$ Jul 15 at 15:54
  • 1
    $\begingroup$ But the graph $\Gamma$ for the modular curve isn't the isogeny graph; it is the graph with two vertices and $g+1$ edges between them, where $g \approx \tfrac{p}{24}$ is the genus of the modular curve. So I don't actually know if this is relevant to you. $\endgroup$ Jul 15 at 15:56

1 Answer 1


I think you remembered correctly except that it should be the modular curve $X_0(N)$. Note that $N$ is prime here.

The Eichler-Shimura relation says the eigenvalues of Frobenius on the Tate module of the modular curve $X_0(N)$ come in pairs $\alpha, \overline{\alpha}$ satisfying $\alpha \overline{\alpha}=p$ and $\alpha \overline{\alpha} =a_p(f)$ for a modular form $f$ (on the same modular curve), where $a_p$ is the $p$th Hecke eigenvalue.

The class number of the function field of a curve is the product of $\alpha-1$ over the Frobenius eigenvalues $\alpha$, which if you put them in pairs gives $(\alpha-1) (\overline{\alpha}-1)= p - a_p(f)+1$.

The number of spanning trees is equal to the product of the nonzero eigenvalues of the Laplacian divided by the number of vertices of the graph. The eigenvalues of the Laplacian are $p+1-\lambda_i$ where $\lambda_i$ are the eigenvalues of the graph, so these match up if and only if the Hecke eigenvalues $a_p(f_i)$ of modular forms match up the eigenvalues $\lambda_i$ of the adjacency matrix.

Jacquet-Langlands relates eigenvectors of the adjacency matrix of the supersingular isogeny graph in characteristic $N$ to modular forms on $X_0(N)$ that don't come from $X(1)$, which is all of them (but the condition is important for more general versions of the statement), and the relation is exactly that the eigenvalue matches up with the Hecke operator.

One way to understand the formula you give is that for $k$-regular graphs with girth going to $\infty$, the distribution of their eigenvalues follows the Plancherel measure of a $k$-regular tree, because the traces of powers of the adjacency matrix match the diagonal of powers of the adjacency matrix of a $k$-regular tree. Integrating the log of $k$ minus the eigenvalue against this measure gives the constant. Of course rigorously establishing this takes more work.

Since the eigenvalues of the adjacency matrix are the eigenvalues of Hecke operators, this corresponds to studying the spectrum of Hecke operators using traces of their powers. This approach to understanding the eigenvalues of the Hecke operators is very natural from the number-theoretic perspective, in part because the trace of Hecke operators can be computed by the crucial trace formula. For example, Sarnak was studying this kind of thing in 1987 in Statistical Properties of Eigenvalues of the Hecke Operators.

I don't know exactly what Lubotzky is referring to, but this might be a situation where saying that a nontrivial arithmetic result can be obtained from a combinatorial one does not mean that this is the best possible arithmetic result for this problem or that the result can't also be obtained in a more uniformly arithmetic way, but just that the combinatorial result does in fact give you something which isn't obvious on the arithmetic side.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.