In Search of Randomness: Distributions of Eigenvalues

Wen-Ching Winnie Li*

Abstract

In this article we review the current status regarding the distribution of Kloosterman sums, eigenvalues of Hecke operators and eigenvalues of Ramanujan graphs. The interrelationship of these eigenvalues are also discussed.

Introduction

The arithmetic of eigenvalues of Frobenius endomorphisms and eigenvalues of Hecke operators has long been of particular interest to number theorists. In the past decade, these eigenvalues also appear as eigenvalues of Ramanujan graphs, which have important applications to communication networks and computational complexity. This paper surveys recent progress on the distributions of these eigenvalues. We shall discuss what are to be

*Research supported in part by a grant from the National Security Agency no.

MDA904-95-H-1006

2 Wen-Ching Winnie Li

expected and what have been proved. We shall also see how eigenvalues of Frobenius endomorphisms and Hecke operators appear naturally and fit together nicely as eigenvalues of Ramanujan graphs.

§1. Distributions of Gauss Sums

We start with the most well-known character sums, namely, the Gauss sums. Let F be a finite field with q elements. Denote by χ (resp. ψ) a multiplicative (resp. additive) character of F. It is a homomorphism from the multiplicative group F^{×} (resp. additive group F) to the unit circle S^{1}. Given χ and ψ, the Gauss sum g(χ, ψ) is defined as

g(χ, ψ) = ∑_{x∈F^{×}} χ(x)ψ(x).

It is well known that, for χ and ψ both nontrivial, the Gauss sum has absolute value

|g(χ, ψ)| = \sqrt{q} = \sqrt{|F |}.

Hence we may write g(χ, ψ) = \sqrt{q}e^{iθ}, where θ is the argument of g(χ, ψ). A natural question is to study the distribution of the angles θ. When F is the prime field ℤ/pℤ, denote by ψ_{p} the additive character x ↦ e^{2πix/p}. Then for the quadratic character χ of ℤ/pℤ, Gauss showed that

g(χ, ψ_{p}) = \sqrt{p}\{ \begin{matrix}1 & if p ≡ 1 (mod 4), \\ i & if p ≡ 3 (mod 4). \end{matrix}

Distributions of Eigenvalues 3

Thus as p varies among odd primes, half of the quadratic Gauss sums have argument 0 and half have argument π/2. The situation is quite different for cubic characters. The celebrated result by Heath-Brown and Patterson [11] asserts that Theorem 1. For primes p ≡ 1 (mod 3) and χ cubic characters of ℤ/pℤ, the arguments of g(χ, ψ_{p}) are uniformly distributed with respect to the Lebesque measure on the unit circle as p tends to ∞.

Very little is known beyond these two cases.

The Gauss sum g(χ, ψ) varies in a simple way as ψ changes, however, its dependence on χ is nontrivial. The Jacobi sum

J(χ, ξ) = g(χ, ψ)g(ξ, ψ)/g(χξ, ψ)

measures the difference, where χ, ξ and χξ are all nontrivial multiplicative characters and J(χ, ξ) is independent of the choice of a nontrivial additive character ψ. Clearly, J(χ, ξ) has the same absolute value \sqrt{q} as each of the Gauss sum involved in its definition. One could also ask the distribution of the arguments of Jacobi sums. In a recent paper, Katz and Zheng [14] considered the distribution of the following three families of angles associated to a finite field F:

Family A: the argument of g(χ, ψ) for χ and ψ both nontrivial; Family B: the argument of g(χ, ψ) for χ nontrivial and ψ fixed;

Family C: the argument of J(χ, ξ) for χ, ξ, χξ all nontrivial.

They showed that

Theorem 2. The above three families of angles are uniformly distributed with respect to the Lebesque measure on the unit circle as the size of F tends to ∞.

So far, we have seen two kinds of limit procedure. The first is the result of Heath-Brown and Patterson, where, as p grows, more and more angles are added to the previous collection, this type of limit is called a horizontal limit. The second is the result of Katz and Zheng, where, as a field is replaced by another field with larger size, a new and larger set of angles, which may or may not be related to the previous set, is considered; this type of limit is called a vertical limit.

§2. Kloosterman Sums

Let K be a degree two étale algebra over a finite field F of q elements. Then K is isomorphic either to F +F (the split case) or to a degree two field extension F_{2} of F (the nonsplit case). Denote by N and T the norm and trace from K to F. In the nonsplit case, they are the usual norm and trace maps between fields, and in the split case, they are defined by N(x, y) = xy and T (x, y) = x + y, respectively. Given a nontrivial additive character ψ

Distributions of Eigenvalues 5

of F and a nonzero element a in F, consider the character sum

∑_{z∈K,N(z)=a} ψ(T z).

When K splits, this is called a Kloosterman sum, and Weil [25, 26] has shown that it is the sum of two eigenvalues α and ᾱ of some Frobenius endomorphism with |α| = \sqrt{q}. When K does not split, this is called a generalized Kloosterman sum, Deligne [5] has shown that the generalized Kloosterman sum is the opposite of the Kloosterman sum. Thus it suffices to study the Kloosterman sums.

Suppose the characteristic of F is p. We shall fix the choice of ψ to be ψ_{p} composed with the trace map from F to the prime field ℤ/pℤ. The Kloosterman sum defined above is equal to

Kl(F; a) = ∑_{\begin{matrix}x,y∈F \\ xy=a \end{matrix}} ψ(x + y) = \sqrt{q}(e^{iθ} + e^{−iθ}),

where 0 ≤ θ < π is called the argument of the Kloosterman sum. One is interested in the distribution of these arguments.

§3 Elliptic Curves

Another arithmetic subject related to eigenvalues of Frobenius is elliptic curves. An elliptic curve E defined over ℤ is the set of solutions to a cubic equation

y^{2} = x^{3} + Ax^{2} + Bx + C,

6 Wen-Ching Winnie Li

where the coefficients A, B, C are integers and the cubic polynomial on the right hand side has a nonzero discriminant D. If a prime p does not divide D, the equation modulo p also defines an elliptic curve E mod p, whose number of rational points is often written as

|E(ℤ/pℤ)| = p + 1 − a_{p},

with a_{p} being the error term when compared with the number of rational points, p + 1, of the projective line over ℤ/pℤ. Hasse [10] showed that a_{p} is the sum of two eigenvalues α_{p} and ᾱ_{p} of a Frobenius endomorphism and α_{p} = \sqrt{p}e^{iθ_{p}}. An interesting question arises naturally: Fix E, find the distribution of the angles θ_{p} as p tends to infinity.

§4. Modular Forms

Let N and k be two positive integers. A modular form f of weight k for the congruence subgroup

Γ_{0}(N) = \{( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ SL_{2}(ℤ) : N|c\}

is a function holomorphic on the Poincaré upper half-plane and at the cusps of Γ_{0}(N) which satisfies the transformation rule

f(z) = (cz + d)^{−k}f(\frac{az + b}{cz + d})

for all elements ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ Γ_{0}(N) and z in the upper half plane. It is called a cusp form if it vanishes at all the cusps. Such a form has a Fourier

Distributions of Eigenvalues 7

expansion

f(z) = ∑_{n=1}^{∞} a_{n}e^{2πinz}.

Assume that a_{1} = 1 and that f is an eigenfunction of the Hecke operators T_{p} for primes p ∤ N and of the operators U_{p} for primes p|N. This assumption can be rephrased in terms of the L-function attached to f being Eulerian at all primes:

L(s, f) = ∑_{n=1}^{∞} a_{n}n^{−s}

= ∏_{p∤N}(1 − a_{p}p^{−s} + p^{k−1−2s})^{−1} ∏_{p|N}(1 − a_{p}p^{−s})^{−1}.

It is known that for p ∤ N, a_{p} is the sum of two eigenvalues α_{p} and ᾱ_{p} of a Frobenius endomorphism and |α_{p}| = p^{(k−1)/2}. This is the former Ramanujan-Petersson conjecture, proved by Eichler and Shimura for k = 2, Deligne [6,7] for k ≥ 3 and Deligne and Serre [8] for k = 1. Therefore we may write, for p ∤ N,

a_{p} = p^{(k−1)/2}(e^{iθ_{p}} + e^{−iθ_{p}})

with 0 ≤ θ_{p} < π and ask the overall distribution of θ_{p} as p tends to ∞. The theory of newforms by Atkin and Lehner [2] implies that the space of cusp form for Γ_{0}(N) admits a basis consisting of newforms of levels dividing N as well as their “push-ups ”, and a newform has the aforementioned Eulerian property. Hence it suffices to consider newforms for each group Γ_{0}(N).

8 Wen-Ching Winnie Li

§5. The Expected Measure

In the above three sections, we exhibited situations where algebraic integers of particular arithmetic interest are in fact sums of two eigenvalues of certain Frobenius endomorphisms, and we are led to the study of the distribution of the angles of these eigenvalues. The first important step is to find out the measure expected to describe the distribution. To answer this question, we start with the general situation.

Let G be a compact topological group endowed with the Haar measure μ̄. Denote by X the space of conjugacy classes of G and by μ the measure on G induced from μ̄. A sequence {x_{n}} of points x_{n} in X is said to be equidistributed or uniformly distributed with respect to μ if for all class functions f on G, the average of f over points in the sequence approaches the overall average of f on G, that is,

lim_{N→∞} \frac{1}{N} ∑_{n≤N} f(x_{n}) = ∫_{G} f(g)μ̄(g).

The space of class functions on G admits a basis consisting of the characters χ_{ρ} of the irreducible representations ρ of G. In view of the orthogonality relation among the characters, we may restate the above definition as {x_{n}} is uniformly distributed with respect to μ if and only if for all nontrivial representations ρ of G,

lim_{N→∞} \frac{1}{N} ∑_{n≤N} χ_{ρ}(x_{n}) = 0.

Distributions of Eigenvalues 9

Quite often, we consider a sequence of conjugacy classes {x_{v}} parametrized by a countable set Σ = {v}, for instance, Σ is a subset of primes as in §§3 and 4 or a subset of places of a global field. In this case, the norm of v, noted Nv, is a positive integer. In general, suppose the integer Nv is defined for all v in Σ, then under certain situations, we may re-interpret the above condition analytically as follows. For an irreducible representation ρ of G, we attach the L-function

L(s, {x_{v}}_{v∈Σ}, ρ) = ∏_{v∈Σ} det(I − ρ(x_{v})Nv^{−s})^{−1}.

Note that this is well-defined since the characteristic polynomial of ρ(x) depends only on the conjugacy class of x. To proceed, we make the following three assumptions.

(5.1) ∏_{v∈Σ}(1 − Nv^{−s})^{−1} converges absolutely for ℜs > 1 and extends to a nonzero meromorphic function on ℜs ≥ 1 with only a pole at s = 1.

(5.2) L(s, {x_{v}}_{v∈Σ}, ρ) converges absolutely for ℜs > 1 and extends to a nonzero meromorphic function on ℜs ≥ 1 with neither zeros nor poles on the line ℜs = 1 except possibly at s = 1. Let

c_{ρ} = −ord_{s=1}L(s, {x_{v}}_{v∈Σ}, ρ).

(5.3) There exists a positive integer r such that for every n > 0, the number of v ∈ Σ with Nv = n is at most r.

10 Wen-Ching Winnie Li

We remark that the conditions (5.1) and (5.3) automatically hold when Σ consists of almost all places of a number field, while (5.1), but not (5.3), holds when Σ consists of almost all places of a function field of one variable over a finite field.

Serre in [22] proved that Theorem 3. If {x_{v}}_{v∈Σ} satisfies the assumptions (5.1)-(5.3), then

∑_{\begin{matrix}v∈Σ \\ Nv≤N \end{matrix}} χ_{ρ}(x_{v}) = c_{ρ} \frac{N}{log N} + o(\frac{N}{log N}) as N → ∞.

In particular, taking ρ to be the trivial representation of G, the above says that the number of v ∈ Σ with Nv ≤ N is approximately N/ log N for N large, a fact known to hold for the set of places of a global field. Consequently, if (5.1)-(5.3) holds, then {x_{v}}_{v∈Σ} is uniformly distributed with respect to μ if and only if c_{ρ} = 0 for all nontrivial irreducible representations ρ of G; in other words, for all nontrivial ρ, the L-function L(s, {x_{v}}_{v∈Σ}, ρ) is holomorphic on the line ℜs = 1 and nonvanishing at s = 1.

For the cases concerning us, the topological group is

G = SU_{2}(ℂ) = {g ∈ SL_{2}(ℂ) : ^{t}ḡg = id},

which is homeomorphic to the three-sphere topologically. Any element g in G is diagonalizable, and hence is conjugate to a matrix of the form

Distributions of Eigenvalues 11

( \begin{matrix}e^{iθ} & 0 \\ 0 & e^{−iθ} \end{matrix} ) and the conjugacy class of g is a two-sphere with radius | sin θ|. Since this diagonal matrix is conjugate to the one with θ replaced by −θ, the space X of conjugacy classes of G thus can be identified with the semi-circle \{e^{iθ} : 0 ≤ θ ≤ π\} and the measure on X is μ = \frac{2}{π} sin^{2} θdθ. Equivalently, by letting x = 2 cos θ, we get a measure on the interval [-2, 2] given by

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

This is the measure to be used in the study of the distribution of e^{iθ} + e^{−iθ} exhibited in sections 2 to 4. The measure μ_{ST} is well-studied in the literature, whose orthogonal polynomials are the Chebychev polynomials of the second kind. For number theorists, it is called the Sato-Tate measure because of its connection with elliptic curves which we shall elaborate in the next section.

The irreducible representations of G = SU_{2}(ℂ) are well-known, with exactly one representation for each degree. Denote by ρ_{1} the identity map of G. It is the degree two irreducible representation of G, and for n ≥ 1, Sym^{n−1}ρ_{1} is the degree n irreducible representation of G. In view of our analysis above, when Σ is the set of almost all primes, a sequence {θ_{p}}_{p∈Σ} of points in X is uniformly distributed with respect to the measure μ if and only if the sequence {2 cos θ_{p}}_{p∈Σ} is uniformly distributed with respect to the measure μ_{ST}, which in turn is equivalent to L(s, {θ_{p}}, Sym^{n−1}ρ_{1}) having a holomorphic continuation to the line ℜs = 1 and nonvanishing there for all n ≥ 1.

§5. The Distribution of Eigenvalues of Frobenius Endomorphisms

Let E be an elliptic curve defined over ℤ with discriminant D and a_{p}’s as defined in §3. The Sato-Tate conjecture asserts that

Conjecture 1. If E does not have complex multiplications, then \{a_{p}/\sqrt{p} : p ∤ D} is equidistributed with respect to the Sato-Tate measure μ_{ST}. In other words,

\frac{1}{|\{p ≤ x : p prime\}|} ∑_{\begin{matrix}p≤x \\ p∤D \end{matrix}} δ_{a_{p}/\sqrt{p}}

converges weakly to μ_{ST} as x tends to ∞.

Here δ_{x} denotes the Dirac measure supported at x. This conjecture is backed by good numerical evidences. We note that if E has complex multiplications from an imaginary quadratic extension K of ℚ, then a_{p}’s arise from an idèle class character of K. In this case, one considers the distribution of angles with respect to the places of K.

The Taniyama-Shimura conjecture states that any elliptic curve E defined over ℤ is modular. More precisely, there is a cuspidal new form of weight 2 for some congruence subgroup whose p-th Fourier coefficient is given by a_{p} of E for almost all primes p. So one expects the Fourier coef-

Distributions of Eigenvalues 13

ficients of newforms also distribute in a similar way. This is the Sato-Tate conjecture for newforms. The more precise statement is as follows.

Conjecture 2. Let f(z) = ∑_{n=1}^{∞} a_{n}e^{2πinz} be a newform of weight k for Γ_{0}(N). Assume that f does not arise from an idèle class character of an imaginary quadratic extension of ℚ. Then \{a_{p}/\sqrt{p^{k−1}} : p ∤ N\} is uniformly distributed with respect to the measure μ_{ST}.

In terms of the analytical conditions, this is equivalent to the L-function L(s, Sym^{n}f) attached to the n-th symmetric power of f to be holomorphic on the half plane ℜs ≥ 1 and nonvanishing on the line ℜs = 1 for n ≥ 1. To-date, this is proved for n ≤ 4: by Hecke for n = 1, Rankin and Shimura for n = 2 and Shahidi for n = 3, 4. Further, Shahidi proved the case n = 5 except that the L-function may have a simple zero or pole at s = 1. The reader is referred to the review article by Shahidi [24] for more details and references regarding this subject.

The limits discussed above are horizontal limits.

Concerning the Kloosterman sums in §2, Katz [13] proved

Theorem 4. The set \{Kl(F; a)/\sqrt{|F |} : a ∈ F^{×}\} is uniformly distributed with respect to the measure μ_{ST} as |F | tends to ∞.

Clearly, this is a vertical limit. For horizontal limit, there is the Sato-Tate conjecture for Kloosterman sums:

14 Wen-Ching Winnie Li

Conjecture 3. Fix a nonzero integer b. Then the set

\{Kl(ℤ/pℤ; b)/\sqrt{p} : p prime, p ∤ b\}

is equidistributed with respect to the measure μ_{ST}.

For Kloosterman sums, there is a conjecture relating them to eigenvalues of Hecke operators on real analytic Maass wave forms. The Maass forms are defined the same way as modular forms except that instead of being holomorphic functions, they are real analytic. The theory of newforms also exists for Maass wave forms. Langlands [16] has extended the Sato-Tate conjecture to representations, including Maass wave forms and certain automorphic forms over global fields. Kloosterman Conjecture over ℚ. Given a nonzero integer b, there exists a Maass wave form f which is an eigenfunction of the Hecke operator T_{p} for all primes p ∤ b with eigenvalue −Kl(ℤ/pℤ; b).

In the above conjecture, the finite field ℤ/pℤ may be viewed as the residue field of the completion of ℚ at p. We can also draw a similar connection between finite fields and function fields and surmise that the same conjecture could be true for function fields. Indeed, this is the case. Theorem 5. Let K be the rational function field F (T) over a finite field F of characteristic p. Given an element b in K but outside F, there exists an automorphic form f of GL_{2} over the adèle ring A_{K} of K such that at all

Distributions of Eigenvalues 15

places v of K 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} is the residue field of the completion of K at v.

This theorem was motivated by a paper of Moreno [21] in which he proved the case for p = 2 and b = T. In fact, his argument extends easily to a general choice of b in the case p = 2. The case of p = 3 was a joint work with Teitlebaum and p ≥ 5 a joint work with Chai. As a consequence of the proof we obtain the following result on the distribution of Kloostermans sums. Corollary 1. With the same notation as in Theorem 5, the set

\{Kl(F_{v}; b)/\sqrt{|F_{v}|} : v does not occur in b\}

is equidistributed with respect to the measure μ_{ST}. In other words, the Sato-Tate conjecture for f holds.

Taking b = T, we obtain Theorem 4.

We close this section by remarking that the “nonconstant” assumption over a rational function field corresponds to the condition “without complex multiplications” over the field of rational numbers. The Sato-Tate conjecture for elliptic curves defined over F (T) with nonconstant j-invariant was proved by Yoshida [27]. For p = 2 and 3, the automorphic form f comes from an elliptic curve over F (T), which is not the case for general p.

16 Wen-Ching Winnie Li

§6. The Distribution of Eigenvalues of Ramanujan Graphs

In this section we shall see applications of the previous results to graphs. For a graph X, denote by A = A_{X} the adjacency matrix of X. It may be regarded as the linear operator acting on the space of functions defined on the vertices of X by sending one function f to

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

where y runs through the outneighbors of x. The eigenvalues of A are called the eigenvalues of X or the spectrum of X. If X is k-regular (i.e., every vertex has exactly k out-neighbors), connected and undirected, then its eigenvalues are all real and lie between k and −k, denote them by λ_{i}, i = 1, ..., |X|. Call ±k trivial eigenvalues of X and the remaining ones nontrivial eigenvalues. Define

λ = λ(X) = max_{λ_{i}≠±k} |λ_{i}|.

A celebrated theorem of Alon and Boppana [18] states that Theorem 6. For k-regular undirected graphs X,

lim inf λ(X) ≥ 2\sqrt{k − 1} as |X| → ∞.

Following [18], a graph X is called a Ramanujan graph if

Distributions of Eigenvalues 17

(7.1) X is k-regular, (7.2) λ(X) ≤ 2\sqrt{k − 1}.

In other words, a Ramanujan graph is a regular graph with small nontrivial eigenvalues. These graphs are very close to random graphs, and are known to have good expanding properties. They have important applications to communication networks and computational complexity.

We investigate the distribution of eigenvalues of Ramanujan graphs. For this purpose, to a k-regular graph X we attach a measure

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

where λ runs through all eigenvalues of X. It is a measure supported on the interval [−M, M] with M = \sqrt{k − 1} + 1/\sqrt{k − 1}. We shall consider families of Ramanujan graphs {X_{m}} and study the limit of the measures attached to X_{m} as m tends to ∞. Clearly, these are vertical limits.

Although a randomly chosen regular graph has a high probability to be close to a Ramanujan graph, however, to actually prove that a given graph is Ramanujan is not easy when the size of the graph is large. Thus it is desirable to have explicitly constructed Ramanujan graphs. To-date, there are three methods, which are all number-theoretic. We shall briefly describe them below.

The first construction, initiated by Margulis [19] and Lubotzky, Phillips and Sarnak [18] independently, is based on definite quaternion algebras. Fix

18 Wen-Ching Winnie Li

a prime p. Let H be a quaternion algebra defined over ℚ ramified at ∞ and unramified at p. Denote by D the group H^{×} divided by its center. Let X be the double coset space of the adèlic points D(A_{ℚ}) of D divided by the rational points D(ℚ) on the left side and the product of real points D(ℝ) and the maximal compact subgroups D(ℤ_{q}) over all finite places q of ℚ on the right side. By the approximation theorem, such a double coset space can be seen locally at p as

X = D(ℤ[\frac{1}{p}])\P GL_{2}(ℚ_{p})/P GL_{2}(ℤ_{p}).

The quotient P GL_{2}(ℚ_{p})/P GL_{2}(ℤ_{p}) has a natural structure as a (p + 1)- regular infinite tree, of which X is a (p+1)-regular quotient graph. The first expression of X enables one to interpret the functions of X as automorphic functions for the quaternion group D, which, by the representation theory of Jacquet and Langlands [12], can be viewed as cusp forms of weight 2 for some congruence subgroup. The action of the adjacency operator A of X agrees with the action of the Hecke operator T_{p} on cusp forms of weight 2. The former Ramanujan-Petersson conjecture implies that the nontrivial eigenvalues of A are bounded by 2\sqrt{p}, showing that X is a Ramanujan graph. We get families of Ramanujan graphs by replacing Γ = D(ℤ[\frac{1}{p}]) by its congruence subgroups and by varying H.

For a positive integer ℓ and a graph X, denote by c_{ℓ}(X) the number of prime closed geodesics in X of length ℓ. The following theorem of McKay

Distributions of Eigenvalues 19

[20] says that if there are not many such prime closed geodesics in a family of graphs, then one gets the limit measure explicitly. More precisely,

Theorem 7. Let {X_{m}} be a family of k-regular connected undirected graphs with |X_{m}| → ∞ as m → ∞. Assume

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

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} + 1/\sqrt{k − 1}.

Remark. The condition (∗) is a mild assumption since, as shown in [20], it holds on average.

In [9] it was proved that the condition (∗) is satisfied when we take a family of Ramanujan graphs constructed with p fixed, H ramified only at ∞ and another prime ℓ, and Γ a congruence subgroup. For such a family, the limit measure is

μ_{p} = \frac{p + 1}{p + 2 + 1/p − x^{2}} · μ_{ST} .

This result was re-interpreted in [9] as

20 Wen-Ching Winnie Li

Theorem 8. The eigenvalues of the Hecke operator T_{p} on cusp forms of weight 2 and Γ_{0}(N), p ∤ N, are equidistributed with respect to the measure μ_{p}.

Using the trace formula, Serre [23] showed that the same is true if N +k tends to ∞.

The second explicit construction of Ramanujan graphs, appeared in the work of Chung [4] and Li [17], is based on finite abelian groups. We explain the general recipe. Let G be a finite abelian group, and let S be a k-element subset of G. With G and S we define two k-regular graphs with vertex set G, called the sum graph X_{s}(G, S) and the difference graph X_{d}(G, S), such that the outneighbors of an element x ∈ G are the elements y ∈ G satisfying y + x ∈ S for the sum graph and y − x ∈ S for the difference graph. The sum graph is clearly undirected, and the difference graph is also undirected if S is symmetric, that is, S = −S. The eigenvalues of these two graphs in absolute value are the same, given by | ∑_{s∈S} ψ(s)|, where ψ runs through all characters of G. Hence if we can find suitable G and S such that

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

then we have constructed Ramanujan graphs.

One such an example is to choose G = K, a quadratic field extension of a finite field F with q elements, and S the set of elements in K with norm 1

Distributions of Eigenvalues 21

to F. Then X_{d}(G, S) is a (q + 1)-regular undirected graph. The nontrivial eigenvalues of this graph are the generalized Kloosterman sums

∑_{\begin{matrix}Nx=a \\ x∈K \end{matrix}} ψ_{p} ∘ T r(x)

as a runs through the elements in F^{×} (with multiplicity q + 1). Here p is the characteristic of K and T r is the trace map from K to the prime field ℤ/pℤ. From Theorem 4 we see that the eigenvalues of X_{d}(G, S) are equidistributed with respect to the measure μ_{ST} as |G| tends to ∞. There are many other interesting examples of Ramanujan graphs based on different kinds of character sums; the distributions of their eigenvalues are not yet known.

Terras and her students gave the third construction of Ramanujan graphs, which are based on finite nonabelian groups. We sketch their method below. Let G be a finite nonabelian group and let K be a subgroup of G. Given a K-double coset S, there is the associated Cayley graph X_{S} = Cay(G/K, S/K) defined on the K-cosets of G with the neighbors of xK being xsK, where s runs through all coset representatives of S/K. Denote by A_{S} the adjacency matrix of X_{S}. Under the assumptions that all K-double cosets are symmetric and that A_{S} and A_{T} commute for all K-double cosets S and T, one gets an explicit formula of the eigenvalues of X_{S} in terms of the trace of irreducible representations of G containing nontrivial K-invariant vectors.

22 Wen-Ching Winnie Li

Indeed, by taking G to be GL_{2}(F), where F is a finite field with q elements, K to be an imbedding in G of the multiplicative group of a quadratic extension of F, and S a K-double coset containing more than |K| elements, Terras et al in [1] and [3] showed that the graph X_{S} is (q + 1)-regular with eigenvalues expressed in terms of certain character sums, which are shown to be bounded by 2\sqrt{q}. Thus X_{S} is a Ramanujan graph.

The K-double cosets of GL_{2}(F) are actually parametrized by elements in F, denote them by S_{a}, a ∈ F. It is easy to see that for all except 0 and another element depending on the imbedding of K in G, |S_{a}| > |K|. Fix a nonzero integer a and regard it as an element of F. Denote the Ramanujan graph with coset S_{a} by X(F, a). Kuang [15] showed that the first and the second moments of the measure attached to X(F, a) converge to the first and the second moments of μ_{ST} as |F | tends to ∞. Nothing else is known concerning the distribution of the eigenvalues of the Ramanujan graphs constructed using this method.

References

[1] J. Angel, N. Celniker, S. Poulos, A. Terras, C. Trimble, and E. Velasquez, Special Functions on Finite Upper Half Planes, Contemp.

Distributions of Eigenvalues 23

Math. 138 (1992), 1-26.

[2] A. O. L. Atkin and J. Lehner, Hecke Operators for Γ_{0}(m). Math. Ann. 185 (1970), 134-160.

[3] 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.

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

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

[6] P. Deligne, Formes Modulaires et Représentations ℓ-adiques, Séminaire Bourbaki vol. 1968/69, Lecture Notes in Math. 179, Springer-Verlag, Berlin-Heidelberg-New York (1971).

[7] P. Deligne, La Conjectures de Weil I , Inst. Hautes Etudes Sci. Publ. Math. 43 (1974), 273-307.

[8] P. Deligne and J.-P. Serre, Formes Modulaires de Poids 1 , Ann. Sci. E. N. S. 7 (1974), 507-530.

[9] K. Feng and W.-C. W. Li, Spectra of Hypergraphs and Applications, J. Number Theory, to appear.

[10] H. Hasse, Beweis des Analogons der Riemannschen Vermutung für die Artinschen und F. K. Schmidtschen Kongruenzzetafunktionen in gewis-

24 Wen-Ching Winnie Li

sen elliptischen Fällen, Ges. d. Wiss. Nachrichten. Math. Phys. Klasse, Heft 3 (1933), 253-262.

[11] D. R. Heath-Brown and S. J. Patterson, The Distribution of Kummer Sums at Prime Arguments, J. Reine angew. Math. 310 (1979), 111-130.

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

[13] N. Katz, Gauss Sums, Kloosterman Sums, and Monodromy Groups, Annals of Math. Studies 116, Princeton Univ. Press, Princeton, New Jersey (1988).

[14] N. Katz and Z. Zheng, On the Uniform Distribution of Gauss Sums and Jacobi Sums, Analytic Number Theory, Proc. of a conference in honor of Heini Halberstam, vol. 2, B. Berndt, H. Diamond and A. Hildebrand ed., Progress in Math. 139, Birkhäuser, Boston-Basel-Berlin, 537-558 (1996).

[15] J. Kuang, Eigenfunctions on the Finite Poincaré Planes, Math. Sci. Res. Inst. preprint no. 015-95, 1995.

[16] R. P. Langlands, Automorphic Representations, Shimura Varieties, and Motives: Ein Märchen, Automorphic Forms, Representations and L-Functions II, Proc. Symp. Pure Math., vol. 33, Amer. Math. Soc.,

Distributions of Eigenvalues 25

Providence, 1979, 205-246.

[17] W.-C. W. Li, Character Sums and Abelian Ramanujan Graphs, J. Number Theory 41 (1992), 199-217.

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

[19] 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.

[20] B. D. McKay, The Expected Eigenvalue Distribution of a Large Regular Graph, Linear Alg. and Its Appli. 40 (1981), 203-216.

[21] C. Moreno, The Kloosterman Conjecture in Characteristic Two, 1995, preprint.

[22] J.-P. Serre, Abelian ℓ-adic Representations and Elliptic Curves. Benjamin, New York, Amsterdam (1968).

[23] J.-P. Serre, Répartition Asymptotique des Valeurs Propres de L’opérateur de Hecke T_{p}, J. Amer. Math. Soc. 10 (1997), 75-102.

[24] F. Shahidi, Symmetric Power L-functions for GL(2), Elliptic Curves and Related Topics, Kisilevsky and Murty ed., CRM Proc. & Lecture Notes, vol. 4, Amer. Math. Soc., Providence (1994), 159-182.

[25] A. Weil, On Some Exponential Sums, Proc. Nat. Aca. Sci. 34 (1948), 204-207.

26 Wen-Ching Winnie Li

[26] A. Weil, Sur les Courbes Algébriques et les Variétés Qui S’en Déduisent, Hermann, Paris, 1948.

[27] H. Yoshida, On an Analogue of the Sato Conjecture, Invent. Math 19 (1973), 261-277.

Wen-Ching Winnie Li Department of Mathematics, Pennsylvania State University, University Park, PA 16802 U. S. A.