1549380232-Automorphic_Forms_and_Applications__Sarnak_

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

When used as communication networks, Ramanujan graphs transmit informa-

tion efficiently; they are good expanders. These graphs have diverse applications

in computer science and real world.

The terminology of Ramanujan graph , originally coined by Lubotzky-Phillips-

Sarnak in [25], is motivated by its connection with the Ramanujan- Petterson

conjecture on the classical cusp forms, as we shall discuss in the next section. Here

we want to point out its connection with another very important topic in number

theory, the Riemann hypothesis.

Ihara introduced the following zeta function attached to a k-regular graph X:

Zx(s) =IT (1-q-si(P))-l'

p

where q = k - 1, P runs through the prime geodesic cycles in X , and C(P) is the

length of P. He showed that, by letting u = q-s, the zeta function h as the form

(1 - u2)X

Zx(u)= det(l-Au+qu^2 ) '

where x = -~ IX I is the Euler characteristic of the graph X. Note that the poles

of Z x ( s) in the vertical strip 0 < ~( s) < 1 all fall on the line ~( s) = ~, that is,

the Riemann hypothesis holds, if and only if X is Ramanujan. This is analogous

to the situation with the Selberg zeta function.

1.2. Explicit construction of Ramanujan graphs and automorphic

forms

To explicitly compute the eigenvalues of a graph is not practical when the graph

size is large. Thus it would be desirable to have explicit constructions of graphs for

which the nontrivial eigenvalues are guaranteed to have small absolute values. Here

we exhibit three explicit constructions of Ramanujan graphs. The first gives infinite

families of k-regular Ramanujan graphs with fixed k, while the second and third

only construct finitely many k-regular Ramanujan graphs with fixed k. The families

from the first construction have applications as good expanders: the graphs from

the second and third constructions are in fact related to the first construction, and

their spectra are explicitly given as character sums, which lead to the construction

of automorphic forms whose Fourier coefficients are character sums arising from

eigenvalues of Ramanujan graphs.

Let K be either Q or a function field of one variable with finitely many elements

in its field of constants. Fix a place oo of K, which is the archimedean place if

K = Q. Fix another place v of K different from oo. Let H be a quaternion algebra

over K which is ramified at oo and unramified at v. Write D for the multiplicative

group of H divided by its center, and regard it as an algebraic group.

The vertices of our graph is a double coset space of the adelic points of D:

Hereafter, for a place w of K, denote by Kw the completion of Kat w , and if w is
nonarchimedean, denote by Ow the ring of integers of Kw· The group IC is an open