LECTURE 1. RAMANUJAN GRAPHS 407compact subgroup of I1w#oo,v D(Ow)· By strong approximation theory, the above
double cosets can also be seen locally at v aswhere
rx:: = D(K) nJC
is a discrete subgroup of D(Kv)· When K = Q and v = p, fx:: is a congruence sub-
group of D(Z[l/p]) of finite index. Since His unramified at v, D(Kv) is isomorphic
to PGL 2 (Kv) and we have the third expression of Xx::
Xx:= fx::\PGL2(Kv)/PGL2(0v)·Recall that PGL2(Kv)/PGL2(0v) has the natural structure of a (q + 1)-regular
tree, where q is the cardinality of the residue field at v. This gives Xx: the graph
structure. The graph Xx: is finite since H is ramified at oo. The first expression
of Xx: allows us to view the functions on Xx: as automorphic functions of D(Ax).
The adjacency matrix on the space A(D, JC) of these functions are nothing but
the Hecke operator Tv at the place v, so that the eigenvalues of Xx: are eigenval-
ues of Tv on A(D, JC). The space A(D, JC) contains the constant functions, which
have eigenvalue q + 1. Depending on JC, it may or may not contain alternating
constant functions, which have eigenvalue -(q + 1). These are the only functions
in A(D, JC) corresponding to finite dimensional automorphic representations. Their
orthogonal complement, A( D, JC)l., consists of automorphic forms corresponding to
infinite dimensional automorphic representations of D(Ax). By Jacquet-Langlands
correspondence [15], they can also be interpreted as cuspidal automorphic forms
on GL 2 (Ax). When K = Q, these forms are classical cusp forms of weight 2; the
papers of Eichler [12], Shimura [35], and Igusa [14] have established the Ramanu-
jan conjecture, which implies that the eigenvalues of Tp on A(D, JC)l. have absolute
value bounded by 2/P = 2v'k=l. When K is a function field, the Ramanujan con-
jecture was proved by Drinfeld [11], which yields the same bound 2fo = 2v'k=l.
Hence Xx: is a Ramanujan graph. We get an infinite family of Ramanujan graphs
by varying Hand JC.
This kind of families was first considered for K = Q by Lubotzky-Phillips-
Sarnak [25], and independently by Margulis [28] taking H to be the Hamiltonian
quaternion algebra. Mestre and Oesterle [29] obtained an infinite family {Xe} by
taking the quaternion algebra H over Q to be the quaternion algebra He ramified
only at oo and a prime f =f. p, and JC to be the maximal compact subgroup. Following
the method of Lubotzky-Phillips-Sarnak, Morgenstern [30] did the case K = lFq(t)
with q odd.
To give a more concrete description and to prepare for connections with other
methods, we discuss Morgenstern graph in more details. Fix a nonsquare o in
lFq. Define H to be the quaternion algebra over K generated by i,j satisfying the
conditions
i^2 =o, J2=t-1, and ij=-ji
(with uniformizer t ). Then H is ramified only at oo and t - 1, and H has class
number 1, that is,