1549380232-Automorphic_Forms_and_Applications__Sarnak_

408 W.-C. W. LI, RAMANUJAN GRAPHS AND RAMANUJAN HYPERGRAPHS

is a principal ideal. Choose the place v to be the place with t as a uniformizer.

Among the elements in A with reduced norm t, consider the set

S = { 1 + ( c + d i) j : c, d E lF q, c^2 - d^2 O = -1},

which has cardinality q + l. One checks easily that modulo the center of H, the

inverse of an element in S is again in S. Hence we may index the elements in S as

S1, ... , S.2.±..!_, S1 -1 , ... , Sq+l -1

2 2

Theorem 1.4. [Morgenstern [30]] The elements s 1 , ... , s .2.±..!. generate a free group

2

A. Further, A represents PGL 2 (Kv)/PGL 2 (0v) such that the natural tree structure

is isomorphic to the Cayley graph Cay( A, S).

A Cayley graph on a group G with generator set S has as vertices the elements

of the group and the outneighbors of a vertex x are xs for all s E S. When the set

Sis symmetric, as is ours, the resulting Cayley graph is undirected.

Since A is contained in A , it makes sense to consider the residue class of A mod a

polynomial g E lFq[t] prime tot, and the quotient graph Cay(A mod g, S mod g) is

nothing but fqg) \PGL 2 (Kv)/PGL 2 (0v), where fq 9 ) is the principal congruence

subgroup of PGL 2 (1Fq[tl[t]) mod g.

The second construction is based on finite abelian groups. Here we exhibit

one example by co nsidering the Cayley graph Cay(JF q2, N a), where a E lF; and Na

consists of elements of lF q2 with norm to lF q equal to a. These graphs are q + 1

regular and isomorphic to each other. Call them norm graphs. The eigenvalues of

the norm graph Cay(lFq2, N_ 1 ) are

{

q^2 + 1 with multiplicity 1,

kl(lFq,a) := L xENa '1/Jp oTrIFq 2 /IFp(x) with multiplicity q+ 1, for a E JF;.

Here p is the characteristic of lF q and '1/Jp is the character of Z / p Z given by '1/Jp ( x) =
e^2 rrix/p. When composed with the trace map from 1Fq2 to lFP, it yields a nontrivial
additive character of lF q2. Deligne showed that the generalized Kloosterman sum
kl(lFq, a) is the opposite of the Kloosterman sum

kl(lFq,a) = -Kl(lFq,a) = - L '1/JpoTrIFq/IFp(x+ ~),

xEIF~

and Weil showed that IKl(lFq, a)I::::; 2 ...;q_. Therefore a norm graph is Ramanujan. It
is a Ramanujan graph with expli cit eigenvalues given by generali zed Kloosterman
sums. The reader is referred to [24] for more Ramanujan graphs based on abelian
groups. Its relation to the Ramanujan graphs constructed via quaternion algebras
is as follows.

Proposition 1.5. [Li [21]] The norm graph Cay(lFq2,N_ 1 ) is isomorphic to

Cay(A mod t - 1, S mod (t - 1)).

Adelically, this can be identified with XK., where

II

w,t:oo,v,t-1