Eigenvalues of Ramanujan Graphs

Wen-Ching Winnie Li*

§1. Introduction

The adjacency matrix of a finite graph X is a square matrix A = A_{X} with rows and columns parametrized by the vertices of X such that the xy entry of A records the number of edges from the vertex x to the vertex y. It may be regarded as a linear operator on the space of functions on vertices of X which sends a function f to Af whose value at a vertex x is given by

(Af)(x) = ∑_{y} f(y),

where y runs through all ending points of the edges starting from x. The eigenvalues of A are called the eigenvalues of X. Call X a k-regular graph if at every vertex of X there are k edges going out and k edges coming in. If X is undirected and k-regular, then the eigenvalues of X are real and bounded between k and −k. The multiplicity of k as an eigenvalue of X is equal to the number of connected components of X, and −k is an eigenvalue if and only if X is a bipartite graph. In general, the eigenvalues λ_{i} of X provide lots of information about the graph G. An eigenvalue of X with absolute value k is called a trivial eigenvalue, we are interested in the nontrivial eigenvalues. For this matter, define

λ = λ(X) = max_{λ_{i} nontrivial} |λ_{i}|.

Assume X connected. It turns out that the smaller λ(X) is, the larger the magnifying constant X has, and hence the more ”expanding” X is. It is also known that the smaller λ(X) is, the smaller the diameter of X is. In the case that X represents a communication network, the transmission efficiency is measured by the magnifying constant, and the transmission delay is measured by the diameter. Thus regular graphs with small λ have important applications in communication networks and in computer science.

How small can λ be? A celebrated theorem by Alon and Boppana asserts that

Theorem 1.([LPS]) For connected, k-regular, and undirected graphs X,

lim inf λ(X) ≥ 2\sqrt{k − 1}

as the size of G tends to infinity.

It was shown in [L1] that the above inequality also holds if X varies among directed graphs whose adjacency matrices are diagonalizable by unitary matrices, and it is false if

Typeset by AMS-TEX

*Research supported in part by a grant from the National Security Agency no. MDA904-95-H-1006 and a grant from the National Science Foundation no. DMS-9622938

the diagonalization condition is dropped. In fact, one can construct an infinite family of k-regular connected directed graphs whose nontrivial eigenvalues all have absolute value one. As in [LPS] and [L1], we call a regular graph with small nontrivial eigenvalues a Ramanujan graph. More precisely, a connected graph X is called a Ramanujan graph if

(i) X is k-regular; (ii) λ(X) ≤ 2\sqrt{k − 1}; (iii) The adjacency matrix of X is diagonalizable by a unitary matrix. Note that the third condition is automatically satisfied if X is undirected since its

adjacency matrix is symmetric and hence diagonalizable by an orthogonal matrix.

In real applications it is highly desirable to have explicitly constructed Ramanujan graphs since to verify if a given graph is Ramanujan takes a lot of time when the graph size is large. To date, there are three systematic methods to construct Ramanujan graphs. The first method, introduced by Lubotzky, Phillips and Sarnak [LPS], and independently by Margulis [Ma], is based on definite quaternion algebras over ℚ. The same construction also works over a rational function field, as done by Morgenstern [Mn]. The nontrivial eigenvalues of a graph constructed using this method are in fact eigenvalues of the Hecke operator at a certain place of the underlying global field on automorphic forms, for which the Ramanujan-Petersson conjecture is known to hold. This is the reason for getting Ramanujan graphs. The second construction is based on finite abelian groups, which can be found in the papers by Alon [A], Chung [C] and Li [L1]. The eigenvalues of such graphs are character sums, which can be estimated using the Riemann hypothesis for curves over finite fields proved by Weil [W1, W2]. The third construction is based on finite nonabelian groups. Under certain conditions, the eigenvalues of graphs so constructed can be expressed as sums of the traces of certain kind of representations of the underlying group. The Ramanujan graphs arising from finite upper-half planes constructed by Terras ([ACPTTV] and [CPTTV] ) and Evans [E] fall in this category. The eigenvalues of such graphs are also expressed as character sums, which can be estimated using some geometric means [K1], [K2] or the Riemann hypothesis for curves over finite fields [L2], just like the second method. It should be pointed out that the first construction gives infinitely many Ramanujan graphs with given valency, while the graphs constructed by the second and third methods only give rise to finitely many Ramanujan graphs with given valency. On the other hand, not much is known about the eigenvalues of the graphs based on quaternions except that they are algebraic integers satisfying the required bound, while the eigenvalues of the graphs constructed based on finite groups are explicit character sums. In [LR1, LR2] some numerical investigation of the distribution of eigenvalues of certain quaternion graphs were made.

The purpose of this paper is to explore the relation among the graphs constructed using these three methods. In particular, we show that the norm graphs constructed by the second method in [L1] can also be obtained using the first method with suitable quaternion algebras over rational function fields, and the Terras graphs are in fact quotient graphs of Morgenstern graphs. Consequently, the explicit eigenvalues of norm graphs and Terras graphs are also eigenvalues of Hecke operators of automorphic forms of the quaternion groups (and hence of GL_{2}) over rational function fields. One is then naturally led to the question of finding automorphic forms realizing such eigenvalues. The eigenvalues of the norm graphs are generalized Kloosterman sums. The Kloosterman conjecture predicts the existence of an automorphic form of GL_{2} over the field of rational numbers or a function field of one variable over a finite field which is an eigenfunction of Hecke operators with prescribed eigenvalues given by generalized Kloosterman sums determined by an element of the underlying field. This conjecture over rational function fields was proved in [L3] for the case of characteristic 2 and 3 with help from J. Teitlebaum, and in a forthcoming joint paper with C. Chai for general positive characteristic. By carefully computing the conductors of the automorphic forms so obtained, one can prove, using Jacquet-Langlands correspondence [JL], that they are also automorphic forms of the quaternion groups from which the norm graphs arise. Thus we have found automorphic forms for quaternion groups realizing generalized Kloosterman sums as eigenvalues of Hecke operators. We remark that what we found is more than what is asked: to answer the question we only need to find automorphic forms which are eigenfunctions of the Hecke operator at a particular place with generalized Kloosterman sums as eigenvalues, the functions we found are actually eigenfunctions of the Hecke operators with generalized Kloosterman sums as eigenvalues at almost all places of the underlying function field. For Terras graphs, we propose an analogous statement, which we believe should be true although it is not fully proved at present. The distribution of the eigenvalues of the explicitly constructed Ramanujan graphs will also be discussed briefly.

This paper is organized as follows. In §2 we review the construction based on quaternion groups with more details given to the construction of Morgenstern graphs since they will be used in later sections for comparison with the norm graphs and Terras graphs. The construction of Ramanujan graphs based on abelian groups will be reviewed in §3, where we shall show that the norm graphs also arise from quaternion groups. In §4 we survey the construction of Ramanujan graphs based on finite nonabelian groups. We discuss Terras graphs with detail and show how these graphs arise as quotient graphs of Morgenstern graphs. For more details of the number-theoretic constructions of Ramanujan graphs, the reader is referred to [L4]. This paper is a sequel of the survey paper [L5].

§2. Ramanujan graphs based on quaternion groups

Let M be the field of rational numbers ℚ or the field of rational functions F (t) over a finite field F with q elements. The function field F (t) may be regarded as the field of rational functions on the projective line ℙ^{1} over F. Denote by ∞ the “place at infinity” of M, which is the archimedean place of ℚ with completion ℝ or the infinite place of F (t) corresponding to the point at infinity of ℙ^{1} with completion F ((1/t)). The other places of M are “finite”, which may be identified with the (positive) primes in the ring of integers ℤ if M = ℚ or the monic irreducible polynomials in the polynomial ring F [t] if M = F (t). At such a place w let ℤ_{w} denote the ring of integers of the completion M_{w} of M at w. Fix a place v of M other than ∞. Let H be a quaternion algebra over M ramified at ∞ but unramified at v. Write D for the multiplicative group H^{×} divided by its center. Regard D as an algebraic group. The vertices of our graph X are the double coset space of the adèlic points D(A_{M}) of D, divided on the left by the rational points D(M) and on the right by the product of the full group D(M_{∞}) at ∞ and the maximal compact subgroups D(ℤ_{w}) at all finite places w of M. By approximation theory, such global double coset space can also be seen locally at v as Γ \ D(M_{v})/D(ℤ_{v}), where Γ is the ℤ[\frac{1}{p}] points of D if M = ℚ and v = p, and it is the F [t][\frac{1}{P (t)}] points of D if M = F (t) and v = P (t). Since H is unramified at v, the group D(M_{v}) is P GL_{2}(M_{v}) and D(ℤ_{v}) = P GL_{2}(ℤ_{v}) so that the quotient D(M_{v})/D(ℤ_{v}) = P GL_{2}(M_{v})/P GL_{2}(ℤ_{v}) has a natural structure as a k-regular infinite tree. Here k − 1 is the cardinality of the residue field of M_{v}. More precisely, k − 1 = p if v = p and k − 1 = q^{deg P (t)} if v = P (t). The group Γ acts on this tree by left translations, yielding the quotient graph X. We may replace Γ by its congruence subgroups to obtain an infinite family of graphs with the same valency k. The resulting graphs are finite because the quaternion algebras we chose are ramified at ∞.

To study the eigenvalues of these graphs, we view the vertices as global double cosets. Then the functions on such a graph may be interpreted as automorphic functions of the quaternion group D right invariant by D(M_{∞}), and the action of the adjacency matrix is nothing but the action of the Hecke operator T_{v} on automorphic forms. By the theory of Jacquet and Langlands [JL], those forms orthogonal to the constant functions can be interpreted as cusp forms of GL_{2} over M, of weight two if M = ℚ, and the nontrivial eigenvalues of the graph are among eigenvalues of T_{v} on such cusp forms. The latter are known to satisfy the Ramanujan-Petersson conjecture, due to the works by Eichler-Shimura for weight two forms over M = ℚ and by Drinfeld [Dr] for forms over M = k(t). Therefore we find the nontrivial eigenvalues in absolute value majorized by 2\sqrt{k − 1}.

The graphs constructed by Margulis [Ma], Lubotzky-Phillips-Sarnak [LPS], and Morgenstern [Mn] used this method with a fixed quaternion group and varying congruence subgroups; while the graphs constructed by Mestre and Oesterlé [Me] used quaternion algebras over ℚ, ramified only at ∞ and a prime ℓ ≠ p, and dividing by the maximal compact subgroups. Denote the graph so constructed by X_{ℓ}. In general, we may both vary the quaternion groups and congruence subgroups to get an infinite family of Ramanujan graphs.

Next we give a more concrete description of the graphs constructed using quaternion groups over a rational function field F (t) of odd characteristic. Details can be found in [Mn]. Choose a nonsquare δ in F. Let H be the quaternion algebra over F (t) with basis 1, i, j, ij satisfying the conditions

i^{2} = δ,  j^{2} = t − 1,  ij = −ji.

It can be shown that H is ramified only at ∞ and t − 1 and it has class number 1, that is, the F [t] linear combination of the basis elements form a principal ideal domain A. Among the elements in A with reduced norm t, consider the following subset with cardinality q+1:

S = {1 + (c + di)j : c, d ∈ F, c^{2} − d^{2}δ = −1}.

One checks easily that modulo the center of H, the inverse of an element in S is again in S, so we may index the elements of S as s_{1}, …, s_{(q+1)/2}, s_{1}^{−1}, …, s_{(q+1)/2}^{−1}. Morgenstern showed that

Theorem 2.([Mn]) The elements s_{1}, …, s_{(q+1)/2} generate a free group Λ. Further, Λ represents P GL_{2}(M_{v})/P GL_{2}(ℤ_{v}) such that the natural tree structure on this coset space coincides with the Cayley graph on Λ with generator set S.

Denoted by Cay(Λ, S) the Cayley graph in Theorem 2. Since Λ is contained in A, it makes sense to consider the residue classes of Λ modulo a polynomial g prime to t, and the quotient graph Cay(Λ mod g, S mod g) is the graph resulting from dividing on the left of P GL_{2}(F (t)_{v})/P GL_{2}(ℤ_{v}) by the principal congruence subgroup of Γ = D(F [t][\frac{1}{t}]) consisting of elements in Γ congruent to 1 mod g. For a monic irreducible polynomial P (t), the residue field of F (t) at the place P is the finite extension of F obtained by joining the roots of P, which we denote by F_{P}. If we take g to be P ≠ t, t−1, then the quotient graph Cay(Λ mod P, S mod P) can also be described as a (q +1)-regular graph on P GL_{2}(F_{P}) (resp. P SL_{2}(F_{P})) if t is not (resp. is) a square modulo P.

The Morgenstern graphs Cay(Λ mod P, S mod P) are the function field analogue of the graphs X^{p,q} in the paper by Lubotzky, Phillips and Sarnak [LPS], which dealt with the Hamiltonian quaternion algebra over ℚ with fixed place at an odd prime p and taking congruence subgroups modulo odd primes q ≠ p.

In order to study the distribution of eigenvalues of Ramanujan graphs, attach, to each k-regular graph X, the measure

μ_{X} = \frac{1}{|X|} ∑_{λ} δ_{λ/\sqrt{k−1}},

where λ runs through the eigenvalues of X and δ_{x} is the Dirac measure supported at x. Clearly, μ_{X} is supported on the interval [−M, M], with M = \sqrt{k − 1}+1/\sqrt{k − 1}. We shall consider the limit measure of families of graphs of interest to us. For this purpose, we start with a general result proved by McKay, which gives the limit measure provided that the graphs in a family do not contain too many closed geodesics. More precisely, given a positive integer i, denote by c_{i}(X) the number of closed geodesics of length i in a graph X. Then

Theorem 3.([Mc]) Let {X_{m}} be a family of connected undirected k–regular graphs with |X_{m}| → ∞ as m → ∞. Assume

For each integer i ≥ 1, c_{i}(X_{m})/|X_{m}| → 0 as m → ∞.  (1)

Then the sequence of measures {μ_{X_{m}}} converges weakly to the measure μ supported on [−2, 2] given by

μ = \frac{k}{M^{2} − x^{2}} · μ_{ST} ,

where M = \sqrt{k − 1} + \frac{1}{\sqrt{k−1}} and μ_{ST} is the Sato-Tate measure

μ_{ST} = \frac{1}{π} \sqrt{1 − \frac{x^{2}}{4}} dx.

McKay showed in [Mc] that the assumption (1) holds on average, hence it is not a serious constraint. A generalization of Theorem 3 to hypergraphs can be found in [FL]. In our case, the family of graphs constructed using quaternion groups over M, such as {X^{p,q}} as the prime q tends to ∞, {Cay(Λ mod P, S mod P)} as the degree of the irreducible polynomial P tends to ∞, and {X_{ℓ}} as the prime ℓ tends to ∞, satisfy the condition (1). This can be seen from several ways. The first is the explicit computation that the girth of a quaternion graph X is at least \frac{4}{3} log_{k−1} |X|, proved in [LPS] for M = ℚ and in [Mo] for M = F (t). The second is the explicit bound of the number of geodesics of length i, computed by Tillich and Zémor in their paper [TZ]. For the graph X^{p,q}, the bound is O(max(1, p^{i/2}/q^{2})q^{2}p^{i/2} log(p^{i}/q^{2})), while the size of X^{p,q} is O(q^{3}). Hence the condition (1) holds as q tends to infinity. Similar bounds and conclusion hold for Morgenstern graphs. The third way comes from a geometric interpretation of X_{ℓ}, namely, each vertex of X_{ℓ} represents an equivalence class of supersingular elliptic curves defined over ℤ/ℓℤ, and two vertices are adjacent if and only if they are represented by elliptic curves which are isogenous by a cyclic group of order p. The number of geodesics in X_{ℓ} of length i is essentially the number of equivalence classes of supersingular elliptic curves in characteristic ℓ which are self-isogenous by a cyclic group of order p^{i}, which is known to be bounded and independent of ℓ. This is shown in [FL], where it is also proved that the conclusion (1) holds if X_{ℓ} is replaced by its finite cover obtained from taking a congruence subgroup (instead of the maximal compact subgroup). Hence we have

Theorem 4. For the family of k-regular graphs {X^{p,q}} as the prime q tends to ∞, {X_{ℓ}} as the prime ℓ tends to ∞, and {Cay(Λ mod P, S mod P)} as the degree of the irreducible polynomial P tends to ∞ , the limit measure is

μ_{k−1} = \frac{k}{(\sqrt{k − 1} + \frac{1}{\sqrt{k−1}})^{2} − x^{2}} μ_{ST} .

Here k − 1 = p for the first two families of graphs and k − 1 = |F | for the third family.

As the functions on quaternion graphs are automorphic forms on quaternion groups, which correspond to automorphic forms of GL_{2} over M, the result above can be interpreted as distribution of eigenvalues of Hecke operators. For instance, we have that the eigenvalues of the Hecke operator T_{p} on cusp forms of weight 2 and level N, where p ∤ N, are equidistributed with respect to μ_{p} as N → ∞. See [FL] and [L6, p. 220] for more detail. In a recent paper [Se] Serre showed that the same limit holds provided k + N → ∞ by using the trace formula. Back in 1980’s, Sarnak [Sa] proved that the eigenvalues of the Hecke operator T_{p} on Maass wave forms for the modular group SL_{2}(ℤ) are equidistributed with respect to μ_{p} as the eigenvalue of the Laplacian approaches ∞.

Another application of the bound of the girth of X^{p,q} is the distribution of eigenvalues of the Hecke operator T_{p} on weight 2 cusp forms for the principal congruence subgroup Γ(16q^{2}) given in [LS].

§3. Ramanujan graphs based on finite abelian groups

We start by giving a general recipe. Let G be a finite abelian group and S a k-element subset of G. Define two k-regular graphs on G, called the sum graph X_{s}(G, S) and the difference graph X_{d}(G, S) as follows : the out-neighbors of x ∈ G in the sum graph are elements in {y ∈ G : x + y ∈ S} = −x + S, and those in the difference graph are in {y ∈ G : y − x ∈ S} = x + S, respectively. Thus the sum graph and the difference graph are k-regular, the sum graph is undirected and the difference graph is usually directed unless the set S is symmetric, that is, S = −S. Furthermore, the difference graph is the Cayley graph Cay(G, S). For X_{s} and X_{d} so constructed, one can show that their adjacency matrices are diagonalizable by unitary matrices and the eigenvalues of their adjacency matrices, although different, have the same absolute value given explicitly by

| ∑_{s∈S} ψ(s)| for characters ψ of G.

Hence if we can find a suitable group G and a subset S such that

| ∑_{s∈S} ψ(s)| ≤ 2\sqrt{k − 1}

for all nontrivial characters ψ of G, then we will have constructed two Ramanujan graphs X_{s}(G, S) and X_{d}(G, S). This observation converts a combinatorial problem to a numbertheoretic problem.

For a finite field F with q elements, denote by F_{2} a quadratic field extension of F and by N_{a} the set of elements in F_{2} with norm to F equal to a. In [De], Deligne estimated generalized Kloosterman sums attached to finite extensions of F. Here we only extract the part which will be used in our construction. Theorem 5. ([De]) For a ∈ F^{×} and all nontrivial additive character ψ of F_{2}, we have

| ∑_{s∈N_{a}} ψ(s)| ≤ 2 q^{\frac{1}{2}} .

Observe that N_{a} has cardinality q + 1 = k for a ∈ F^{×}. The above theorem implies that X_{s}(F_{2}, N_{a}) and X_{d}(F_{2}, N_{a}) are (q + 1)-regular Ramanujan graphs. Note that as a varies among the nonzero elements of F, we get different Ramanujan graphs but with the same eigenvalues. Between these two kinds of graphs, we favor the difference graphs because they are undirected Cayley graphs with eigenvalues (instead of the absolute value of eigenvalues) explicitly given by the generalized Kloosterman sums as in Theorem 5. This allows us to compare them with quaternion Ramanujan graphs. Call such difference graphs norm graphs.

In [L1], several kinds of character sums were estimated using the Riemann hypothesis for curves over finite fields, which led to the constructions of Ramanujan sum and difference graphs. It was also shown that the character sums occurred in Chung’s construction [C] and in Theorem 5 above, which were proved by geometric means, actually followed from the Riemann hypothesis for curves. To keep life simple, we shall concentrate on the norm graphs, study its connection with quaternion graphs and investigate the distribution of the eigenvalues.

The comparison will be with quaternion graphs over function fields. In order to use the quaternion algebra H over F (t) and the group Λ already explained in §2, we assume F has odd characteristic and consider the norm graph Cay(F_{2}, N_{−1}).

Proposition 1. Cay(Λ mod (t − 1), S mod (t − 1)) is isomorphic to Cay(F_{2}, N_{−1}).

Proof. Represent the quaternion a + bi + (c + di)j in H with a, b, c, d in F (t) by the

matrix ( \begin{matrix}a + bi & (t − 1)(c − di) \\ c + di & a − bi \end{matrix} ) with coefficients in the quadratic extension F (t)(i) of

F (t). Then s = 1 + (c + di)j in S is represented by the matrix ( \begin{matrix}1 & (t − 1)(c − di) \\ c + di & 1 \end{matrix} ).

Hence s mod t − 1 has coefficients in the quadratic extension F_{2} = F (i) of F represented

by the matrix ( \begin{matrix}1 & 0 \\ c + di & 1 \end{matrix} ), and S mod (t−1) clearly generates \{( \begin{matrix}1 & 0 \\ x & 1 \end{matrix} ) : x ∈ F_{2}\} = Λ

mod (t − 1). Therefore the graph Cay(Λ mod (t − 1), S mod (t − 1)) is isomorphic to Cay(F_{2}, N_{−1}).

It follows from the construction of Λ that the functions on the Cayley graph Cay(Λ mod (t − 1), S mod (t − 1)) may be seen adèlically as automorphic forms on D(A_{F (t)}) trivial on D(F (t)_{∞}) and right invariant by the standard maximal compact subgroup everywhere except at the place t − 1 where it is right invariant by (t − 1) times the integral elements at t − 1. As a result of Proposition 1, the eigenvalues of such automorphic forms are the eigenvalues of Cay(F_{2}, N_{−1}), which are, as computed in [L1], q + 1 with multiplicity one, and generalized Kloosterman sums ∑\begin{matrix}y∈F_{2} \\ N(y)=a \end{matrix} ψ(y) with multiplicity q + 1 for each

a ∈ F^{×}. Here ψ is any nontrivial additive character of F_{2} and N(y) is referring to the norm from F_{2} to F of y. The eigenfunctions with eigenvalue q + 1 are the constant functions. The eigenfunctions of Cay(F_{2}, N_{−1}) with nontrivial eigenvalues were also computed in [L1], hence we know how the corresponding automorphic forms are defined on each double coset of D(A_{F (t)}). However, from the viewpoint of arithmetic, it is customary to describe automorphic forms by their Fourier coefficients, or equivalently, by the eigenvalues of the Hecke operators. Therefore we are naturally led to the following two questions:

(1) Describe automorphic forms realizing the generalized Kloosterman sums as eigenvalues of the Hecke operator at t;

(2) Study the distribution of the eigenvalues.

Denote by p the characteristic of F (t). Fix a choice of the additive character ψ_{p} of ℤ/pℤ to be ψ_{p}(x) = e^{2πix/p}. For any finite extension k of ℤ/pℤ, we shall choose the standard additive character ψ_{k} of k to be ψ_{p} composed with the trace map from k to ℤ/pℤ. Given a nonzero element a ∈ k, define the Kloosterman sum

Kl(k; a) = ∑_{\begin{matrix}x,y∈k \\ xy=a \end{matrix}} ψ_{k}(x + y).

Deligne showed in [De] that the generalized Kloosterman sum obtained by summing over elements in F_{2} with norm equal to a ∈ F^{×} is the opposite of the Kloosterman sum Kl(F; a) if the standard additive characters are used. Hence it suffices to study the distribution of Kloosterman sums. This was done by N. Katz.

Theorem 6.([K3]) The measures \frac{1}{|F |} ∑_{a∈F^{×}} δ_{Kl(F,a)/\sqrt{|F |}} converge weakly to the Sato-Tate measure μ_{ST} as |F | approaches infinity.

Since μ_{ST} is symmetric with respect to the origin, the measure attached to the graph Cay(F_{2}, N_{−1}) approaches μ_{ST} as the size of F tends to infinity. This answers the second question. As for the first question, the recently proved Kloosterman conjecture over function fields provides an affirmative answer of realizing generalized Kloosterman sums as eigenvalues of Hecke operators.

Theorem 7. Let F (t) be a rational function field over a finite field F of characteristic p. Given an element b in F (t) but outside F, there exists an automorphic form f of GL_{2} over the adèle ring A_{F (t)} of F (t) such that at all places v of F (t) which is neither a zero nor a pole of b, f is an eigenfunction of the Hecke operator T_{v} with eigenvalue −Kl(F_{v}, b). Here F_{v}, as defined in §2, is the residue field of the completion of F (t) at v, and b is viewed as an element in F_{v} by passing to the residue field.

This theorem was inspired by the work of Moreno [Mo], who proved the conjecture for the case p = 2 and b = t. The cases of p = 2 and 3 were proved in [L3] with an appendix by J. Teitlebaum, and for general odd p, it is proved in a forthcoming joint paper by Chai and Li. In particular, by choosing b to be a/(t − 1) where a runs through the nonzero elements of F, we obtain q−1 automorphic forms on D(A_{F (t)}) as described above which are eigenfunctions of the Hecke operator T_{t} at t with eigenvalues the generalized Kloosterman sums −Kl(F; a). Note that these automorphic forms have stronger property than needed to answer question (1): they are eigenfunctions of Hecke operators at all places except t−1 and ∞ with generalized Kloosterman sums as eigenvalues. On the other hand, they only provide a partial answer to question (1) since each generalized Kloosterman sum appears as an eigenvalue of the Hecke operator T_{t} with multiplicity q + 1, and we only found one eigenfunction for this eigenvalue. It would be interesting to explore the values of these automorphic forms on double coset representatives of D(A_{F (t)}), and compare them to the explicit eigenfunctions on Cay(F_{2}, N_{−1}) given by additive characters of F_{2}.

As a by-product of the proof, one gets the distribution of the Kloosterman sums parametrized by b:

Corollary 2. With notation as in Theorem 7, the normalized eigenvalues Kl(F_{v}, b)/\sqrt{|F_{v}|} as v runs through all places of F (t) not occurring in b are uniformly distributed with respect to the Sato-Tate measure μ_{ST}.

§4. Ramanujan graphs based on finite nonabelian groups

As in the previous section, we begin by a brief description of the general recipe. Let G be a finite nonabelian group and K a subgroup of G. Given a K-double coset S of G, we define the Cayley graph X_{S} = Cay(G/K, S/K) on K-cosets of G such that the outneighbors of xK are xsK, where s runs through all coset representatives of S/K. Clearly, X_{S} is |S|/|K|-regular. Denote by A_{S} the adjacency matrix of X_{S} and regard it as an operator on the space of functions on G/K. If all K-double cosets S are symmetric and all adjacency operators A_{S} commute with each other, then the eigenvalues of X_{S} can be expressed explicitly in terms of the trace of the representations of G as follows:

λ_{S,π} = \frac{|S|}{|K|^{2}} ∑_{k∈K} trπ(ks),

where S = KsK and π runs through all irreducible representations of G with nonzero K-invariant vectors. Thus the problem is to find suitable G and K so that the eigenvalues of X_{S} can be estimated. The reader is referred to [L4] for more details.

Terras and her students took G to be GL_{2}(F), where F is a finite field with q elements, q odd. Fix an element δ in F but not in F^{2}. Thus one obtains a quadratic extension F_{2} = F (\sqrt{δ}). Its multiplicative group may be identified with the subgroup

K_{δ} = \{( \begin{matrix}a & bδ \\ b & a \end{matrix} ) ∈ G : a, b ∈ F \}

of G. The coset space G/K_{δ} may be represented by the subgroup

H = \{( \begin{matrix}y & x \\ 0 & 1 \end{matrix} ) : y ∈ F^{×}, x ∈ F \},

which resembles the classical Poincaré upper-half plane, and hence was called finite upperhalf plane by Terras. Let S be a K_{δ}-double coset of G with cardinality greater than that of

K_{δ}. It can be shown that S has coset representatives ( \begin{matrix}y & x \\ 0 & 1 \end{matrix} ), where (x, y) runs through

all F -rational points of an ellipse x^{2} = ay + δ(y − 1)^{2} for some a ∈ F. Further, such double cosets are parametrized by the elements a in F other than 0 and 4δ. Hence we denote the double cosets by S_{a} and write X_{a} for the Cayley graph Cay(G/K_{δ}, S_{a}/K_{δ}). There are two types of nontrivial irreducible representations of G containing nonzero K_{δ}- invariant vectors. The first type arises from a nontrivial character χ of F^{×}, which yields the eigenvalue

λ_{S_{a},χ} = ∑_{\begin{matrix}x,y∈F \\ ay+δ(y−1)^{2}=x^{2} \end{matrix}} χ(y)

of X_{a}. The second type arises from a regular character ω of F_{2}^{×}, which yields the eigenvalue

λ_{S_{a},ω} = ∑_{\begin{matrix}z∈F_{2} \\ N(z)=1 \end{matrix}} ε(\frac{a}{δ} − 2 − T (z))ω(z),

where T (z) and N(z) are referring to the trace and norm of z from F_{2} to F, and ε(x) is 1, 0, -1 according to x ∈ (F^{×})^{2}, x = 0 or x ∈ F \ F^{2}. It follows from the Riemann hypothesis for curves over finite fields that these eigenvalues have absolute values bounded from above by 2\sqrt{q}. Hence X_{a} is a Ramanujan graph. See [ACPTTV] and [CPTTV] for more details. The same construction over F with characteristic 2 was given by R. Evans [E].

The construction of Terras graphs has something in common with the first and the second methods, namely, it uses representations of GL_{2} and the eigenvalues were expressed as character sums which were estimated using Riemann hypothesis for curves. In view of what we did for the norm graphs, it is natural to seek relations between Terras graphs and Morgenstern graphs. As we shall see from the explanation below that Terras graphs are quotients of Morgenstern graphs.

Let g be a monic irreducible polynomial in F [t] not equal to t and t − 1. We may regard t − 1 as an element in F_{g} by identifying F_{g} with the residue field of F (t) completed at g. Recall the quaternion algebra H defined in §2 obtained by adjoining to F (t) a square root i of δ and a square root j of t − 1 satisfying ij = −ji, and the group Λ generated by

S = {1 + (c + di)j : c, d ∈ F, c^{2} − d^{2}δ = −1}.

Choose A, B in F_{g} such that A^{2} − δB^{2} = t − 1. The map sending i to ( \begin{matrix}0 & δ \\ 1 & 0 \end{matrix} ) and j

to ( \begin{matrix}A & −δB \\ B & −A \end{matrix} ) induces an imbedding ϕ_{g} of Λ mod g in P GL_{2}(F_{g}) since H splits at the

place g. Let

K_{δ} = \{( \begin{matrix}a & bδ \\ b & a \end{matrix} ) ∈ GL_{2}(F_{g}) : a, b ∈ F_{g}\}.

Note that K_{δ} contains the center of GL_{2}(F_{g}) so it makes sense to consider ϕ_{g}(S) in GL_{2}(F_{g})/K_{δ}. Further, if the degree of g is odd, then δ is not a square in F_{g} and GL_{2}(F_{g})/K_{δ} can be represented by the finite upper-half plane over F_{g} as discussed earlier.

Proposition 2. Suppose the degree of g is odd. Then

(i) The image ϕ_{g}(s) of an element s = 1 + (c + di)j ∈ S can be written as ( \begin{matrix}y & x \\ 0 & 1 \end{matrix} ) α

for some α ∈ K_{δ} and x, y ∈ F_{g} satisfying the relation

x^{2} = δ(y − 1)^{2} + \frac{4δ(t − 1)}{t}y.  (2)
(ii) No two elements in ϕ_{g}(S) belong to the same K_{δ}-coset in GL_{2}(F_{g}).

Proof. By definition,

ϕ_{g}(s) = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) + ( \begin{matrix}c & dδ \\ d & c \end{matrix} ) ( \begin{matrix}aA & −Bδ \\ B & −A \end{matrix} ) = ( \begin{matrix}1 + cA + δdB & −δ(dA + cB) \\ dA + cB & 1 − cA − δdB \end{matrix} ) ,

which can be expressed as ( \begin{matrix}y & x \\ 0 & 1 \end{matrix} ) α for some element α = ( \begin{matrix}a & bδ \\ b & a \end{matrix} ) ∈ K_{δ}. Denote by

Δ the determinant a^{2} − δb^{2} of α. Since det(ϕ_{g}(s)) = t, the reduced norm of s, we get y = t/Δ. On the other hand, from the second row of ϕ_{g}(s) we find a = 1 − cA − δdB and b = dA + cB, which in turn implies Δ = 1 − A^{2} + δB^{2} − 2cA − 2δdB = −t + 2a after using the relation A^{2} − δB^{2} = t − 1. This yields the solution x = −2δb/Δ. A direct computation shows

x^{2} − δ(y − 1)^{2} = \frac{4δ}{Δ^{2}} (δb^{2} − (t − a)^{2}) = \frac{4δ}{Δ} (t − 1) = \frac{4δ(t − 1)}{t}y,

which proves the first assertion. For (ii), suppose s = 1+(c+di)j and s′ = 1+(c′+d′i)j in S

are sent by ϕ_{g} to the same K_{δ}-coset. Write ϕ_{g}(s) = ( \begin{matrix}y & x \\ 0 & 1 \end{matrix} ) α and ϕ_{g}(s′) = ( \begin{matrix}y′ & x′ \\ 0 & 1 \end{matrix} ) α′

with α, α′ ∈ K_{δ} as in (i). Then ϕ_{g}(s)K_{δ} = ϕ_{g}(s′)K_{δ} implies x = x′ and y = y′. In other words,

cA + δdB = c′A + δd′B  (3)

and

dA + cB = d′A + c′B.  (4)

If one of A, B is zero, then the other one is nonzero and it follows immediately from (3) and (4) that s = s′. Suppose AB ≠ 0. Then the difference of c times equation (4) and d times equation (3) together with c^{2} − δd^{2} = −1 yields

−B = (cd′ − c′d)A + (cc′ − δdd′)B  (5)

and by symmetry we also have

−B = (c′d − cd′)A + (c′c − δd′d)B.  (6)

Comparing (5) and (6), we get cd′ = c′d and cc′−δdd′ = −1. Combined with c^{2}−δd^{2} = −1, these imply c = c′ and d = d′, that is, s = s′, as desired.

Consequently, ϕ_{g}(S) gives rise to q + 1 distinct F_{g}-points of the quadric defined by (2). When g = t − b, b ∈ F, and b ≠ 0, 1, it has degree 1, δ is not a square in F_{g} = F and the image of t in F_{g} is b. The equation (2) with t = b defines an ellipse which has exactly q + 1 F -rational points, and hence they all come from ϕ_{t−b}(S) mod K_{δ}. Thus the union of the cosets ϕ_{t−b}(s)K_{δ} over s ∈ S is the K_{δ}-double coset S_{a} parametrized by a = 4δ(b−1)/b. On the other hand, recall that the Morgenstern graph Cay(Λ mod (t−b), S mod (t−b)) can be identified with the Cayley graph Cay(P GL_{2}(F), ϕ_{t−b}(S)) or Cay(P SL_{2}(F), ϕ_{t−b}(S)) depending upon b being a quadratic nonresidue or a quadratic residue in F. Denote by P K_{δ} the quotient of K_{δ} by its center. In the former case, it is clear that the Terras graph Cay(GL_{2}(F)/K_{δ}, S_{4δ(b−1)/b}/K_{δ}) is the quotient of Cay(P GL_{2}(F), ϕ_{t−b}(S)) by P K_{δ}. In the latter case, let K_{δ}^{1} be the intersection of K_{δ} with SL_{2}(F) and let P K_{δ}^{1} be the quotient of K_{δ}^{1} by its center. As K_{δ} contains an element whose determinant is not a square in F, we may represent P GL_{2}(F)/P K_{δ} and P SL_{2}(F)/P K_{δ}^{1} by the same matrices. Therfore the Terras graph is the quotient of Cay(P SL_{2}(F), ϕ_{t−b}(S)) by P K_{δ}^{1}. We have shown that the Terras graph Cay(GL_{2}(F)/K_{δ}, S_{4δ(b−1)/b}/K_{δ}) is a quotient of the Morgenstern graph Cay(Λ mod (t−b), S mod (t−b)) in both cases. Note that as b runs through the elements in F other than 0 and 1, the parameter 4δ(b − 1)/b runs through all elements of F other than 0 and 4δ. In other words, these are all Terras graphs based on GL_{2}(F)/K_{δ}. We have shown

Theorem 8. Let F be a finite field with odd characteristic and let δ be a nonsquare in

F. Write K_{δ} for the subgroup of GL_{2}(F) consisting of elements of the form ( \begin{matrix}a & bδ \\ b & a \end{matrix} )

with a, b ∈ F. For b ∈ F, b ≠ 0, 1, the Terras graph Cay(GL_{2}(F)/K_{δ}, S_{4δ(b−1)/b}/K_{δ}) is a quotient of the Morgenstern graph Cay(Λ mod (t − b), S mod (t − b)). Therefore all Terras graphs are quotients of Morgenstern graphs.

Consequently, the eigenvalues of the Terras graph Cay(GL_{2}(F)/K_{δ}, S_{4δ(b−1)/b}/K_{δ}) are part of the eigenvalues of the Morgenstern graph Cay(Λ mod (t−b), S mod (t−b)), which are eigenvalues of the Hecke operator T_{t} acting on automorphic forms on D(A_{F (t)}) which are trivial at D(F (t)_{∞}) and right invariant under the standard maximal compact subgroup at every place of F (t) except at t − b where it is invariant under a congruence subgroup Γ_{0}(t − b). Similar to the case of norm graphs, one would like to find automorphic forms which realize the eigenvalues and to study the distribution of the eigenvalues of Terras graphs.

Given a character χ of F^{×}, a finite extension k of F and an element a ∈ k^{×}, define the character sum

S_{χ}(k; a) = ∑_{\begin{matrix}x,y∈k \\ x^{2}=(y−1)^{2}+4ay \end{matrix}} χ ∘ N_{k/F} (y).

We conjecture that the following analogue of Theorem 7 should hold:

Given b ∈ F (t) but not in F and a nontrivial character χ of F^{×}, there is an automorphic form f of GL_{2}(A_{F (t)}) such that at all places v of F (t) other than 1/t, t − 1 and those occurring in b, f is an eigenfunction of the Hecke operator T_{v} at v with eigenvalue −S_{χ}(F_{v}; b).

As remarked by R. Evans in [E], for any γ in k which is not a square, one has

−S_{χ}(k; a) = ∑_{\begin{matrix}x,y∈k \\ x^{2}=γ(y−1)^{2}+4γay \end{matrix}} χ ∘ N_{k/F} (y).

Therefore by choosing a nonsquare γ in F_{v}, we find −S_{χ}(F_{v}; b) = λ_{S_{4γb},χ} is an eigenvalue of the Terras graph Cay(GL_{2}(F_{v})/K_{γ}, S_{4γb}/K_{γ}). Applying the above conjectural statement to b = (t − 1)/t, we would get an automorphic form whose eigenvalues at all places other than t, t − 1 are eigenvalues of Terras graphs. We expect the analogue of Corollary 2 with S_{χ}(F_{v}; b) replacing Kl(F_{v}; b) to remain true.

As for the overall distribution of eigenvalues of Terras graphs, not much is known except the following result by Kuang [Ku]. Take a nonzero integer a in ℤ. Regard a as an element in a finite field F as long as the characteristic of F does not divide a. For most of such fields F, there is a nonsquare element δ in F such that one of the K_{δ}-double cosets in GL_{2}(F) is what we called S_{a} before. Kuang showed that the first and second moments of the measure attached to the Terras graph Cay(GL_{2}(F)/K_{δ}, S_{a}/K_{δ}) converge to the first and second moments of the Sato-Tate measure μ_{ST} as the cardinality of F tends to infinity.

References

[A] N. Alon, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Combinatorica 6, No. 3 (1986), 207-219.

[ACPTTV] J. Angel, N. Celniker, S. Poulos, A. Terras, C. Trimble, and E. Velasquez, Special functions on finite upper half planes, Contemp. Math., 138 (1992), 1-26.

[CPTTV] N. Celniker, S. Poulos, A. Terras, C. Trimble, and E. Velasquez, Is there life on finite upper half planes? Contemp. Math., 143 (1993), 65-88.

[C] F. R. K. Chung, Diameters and eigenvalues, J. Amer. Math. Soc. 2 (1989), 187-196.

[De] P. Deligne, Cohomologie Etale (SGA 4\frac{1}{2}), Lecture Notes in Math. 569, Springer-Verlag, Berlin-Heidelberg-New York (1977).

[Dr] V. G. Drinfeld, The proof of Petersson’s conjecture for GL(2) over a global field of characteristic p, Functional Anal. Appl. 22 (1988), 28-43.

[E] R. Evans, Character sums as orthogonal eigenfunctions of adjancency operators for Cayley graphs, Contemporary Math., vol. 168, Amer. Math. Soc., Providence, RI. (1994), 33-50.

[FL] K. Feng and W.-C. W. Li, Spectra of hypergraphs and applications, J. Number Theory, vol. 60 (1996), 1-22.

[JL] H. Jacquet and R. P. Langlands, Automorphic Forms on GL(2), Lecture Notes in Math. 114, Springer-Verlag, Berlin-Heidelberg-New York (1970).

[K1] N. Katz, Estimates for Soto-Andrade sums, J. reine angew. Math. 438 (1993), 143-161.

[K2] N. Katz, A note on exponential sums, Finite Fields and Their Applications, vol. 1, No. 3 (1995), 395-398.

[K3] N. Katz, Gauss Sums, Kloosterman Sums, and Monodromy Groups, Annals of Math. Studies 116, Princeton Univ. Press, Princeton, 1988.

[Ku] J. Kuang, Eigenfunctions on the finite Poincare planes, MSRI preprint no. 015-95, 1995.

[LR1] J. Lafferty and D. Rockmore, Fast Fourier analysis for SL_{2} over a finite field and related numerical experiments, Experimental Math., vol 1 (1992), No. 2, 115-139.

[LR2] J. Lafferty and D. Rockmore, Numerical investigation of the spectrum for certain families of Cayley graphs, DIMACS Series in Discrete Math. and Theoretical Comp. Sci., vol. 10 (1993), 63-73.

[L1] W.-C. W. Li,, Character sums and abelian Ramanujan graphs, J. Number Theory, vol. 41 (1992), 199-217.

[L2] W.-C. W. Li, Estimates of character sums arising from finite upper half planes. In: Finite Fields and Applications, Proc. of the third international conference, Glasgow, 11-14 July, 1995, S. Cohen and H. Niederreiter eds., Lecture Notes in Math., vol. 233, London Math. Soc., Cambridge Univ. Press, 219-228, 1996.

[L3] W.-C. W. Li, Elliptic curves, Kloosterman sums and Ramanujan graphs, preprint.

[L4] W.-C. W. Li, Number-theoretic constructions of Ramanujan graphs. In: Columbia University Number Theory Seminar, New York 1992, Astérisque, vol. 228 (1995), Soc. Math. de France, 101-120.

[L5] W.-C. W. Li, A survey of Ramanujan graphs. In: Arithmetic, Geometry and Coding Theory, Proceedings of International Conference held at Luminy, France, June 28 - July 2, 1993, de Gruyter, Berlin-New York, 127-143, 1996.

[L6] W.-C. W. Li, Number Theory with Applications, World Scientific, Singapore,

[LS] W-C. W. Li and P. Solé, Spectra of regular graphs and hypergraphs and orthogonal polynomials, Europ. J. Combinatorics, vol. 17 (1996), 461-477.

[LPS] A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261-277.

[Ma] G. Margulis, Explicit group theoretic constructions of combinatorial schemes and their application to the design of expanders and concentrators, J. Prob. of Info. Trans. (1988), 39-46.

[Mc] B. D. McKay, The expected eigenvalue distribution of a large regular graph, Linear Alg. and Its Appli. 40(1981), 203-216.

[Me] J.-F. Mestre, La méthode des graphes. Exemples et applications, Proc. Int. Conf. on Class Numbers and Fundamental Units of Algebraic Number Fields, June 24-28, 1986, Katata, Japan, 217-242.

[Mo] C. Moreno, The Kloosterman conjecture in characteristic two, preprint.

[Mn] M. Morgenstern: Existence and explicit constructions of q +1 regular Ramanujan graphs for every prime power q, J. Comb. Theory, series B, vol. 62 (1994), 44-62.

[Sa] P. Sarnak, Statistical properties of eigenvalues of the Hecke operators. In: Analytic Number Theory and Diophantine Problems, A. Adolphson, J. Conrey, A. Ghosh, and R. Yager edited, Progress in Math. 70, Birkhäuser, Boston-Basel-Stuttgart, 321-331 (1987).

[Se] J-P. Serre, Répartition Asymptotique des Valeurs Propres de L’opéra-teur de Hecke T_{p}, J. Amer. Math. Soc., to appear.

[TZ] J.-P. Tillich and G. Zémor, Optimal cycle codes constructed from Ramanujan graphs, preprint, 1996.

[W1] A. Weil, On some exponential sums, Proc. Nat. Aca. Sci., 34 (1948), 204-207.

[W2] A. Weil, Dirichlet Series and Automorphic Forms, Lecture Notes in Math. 189, Springer-Verlag, Berlin-Heidelberg-New York, 1971.

Wen-Ching Winnie Li Department of Mathematics, Pennsylvania State University, University Park, PA 16802 U. S. A. e-mail address: wli@math.psu.edu