356 AUDREY TERRAS, ARITHMETICAL QUANTUM CHAOSTerras [73], [74] for some elementary ones. A survey with lots of references is to
be found in Hurt [39].
Example. The Ihara zeta function of the tetrahedron.
(K 4 (u)-^1 = (1 - u^2 )^2 (1 -u)(l - 2u)(l + u + 2u^2 )^3.Exercise 7. a) For a regular graph show that r - 1 = IVl(q -1)/2, where IVI is
the number of vertices, r is the rank of the fundamental group, q + 1 is the degree.
b) Compute the !hara zeta function of the finite upper half plane graph over the
fi eld with 3 elements.
c) For a (q + 1)-regular graph, find a functional equation relating the values
(x(u) and (x(l/(qu)).Note that since the Ihara zeta function is the reciprocal of a polynomial, it has
no zeros. Thus when discussing the Riemann hypothesis we consider only poles.
When X is a finite connected (q + 1)-regular graph, there are many analogues of
the facts about the other zeta functions. For any unramified graph covering Y of
X (not necessarily normal, or even involving regular graphs) it is easy to show that
the reciprocal of the zeta function of X divides that of Y (see Stark and Terras
[73]). The analogue of this for Dedekind zeta functions of extensions of number
fields is still unproved. Analogously to the Dedekind zeta function of a number
field, special values of the Ihara zeta function give graph theoretic constants such
as the number of spanning trees. See Exercise 8. There is also an analogue of the
Chebotarev density theorem (see Hashimoto [35]).
Exercise 8. Show that defining the. "complexity" of the graph 11:(X) = the number
of spanning trees of X, we have the formula(-1r+ir2r11:(X) = dr((x)-l (1).
dur
There are hints on the last page of [82].
When Xis a finite connected (q + 1)-regular graph, we say that (x(q-^8 ) sat-
isfies the Riemann hypothesis iff
1
(1.1) for 0 <Res< 1, (x(q-s)-^1 = 0 {::=}Res= 2·Exercise 9. Show that the Riemann hypothesis (1.1) is equivalent to saying that
X is a Ramanujan graph in the sense of Lubotzky, Phillips, and Barnak [53].
This means that when >-is an eigenvalu e of the adjacency matrix of X such that
l>-1 -/= q + 1, then l>-1 .S 2vq_.Remark 2. Lubotzky [54] has defined what it means for a finite irregular graph Y
covered by an infinite graph X to be X -Ramanujan. It would be useful to reinterpret
this in t erms of the poles of the !hara zeta function of the graph. It would also be
nice to know if there is a functional equation for the !hara ze ta of an irregular graph.
Table 1 below is a zoo of zetas, comparing three types of zeta functions: number
field zetas (or Dedekind zetas), zetas for function fields over finite fields, and finally
the Ihara zeta function of a graph. Thus it adds a new column to Table 2 in Katz
and Sarnak [45]. In Table 1 it is assumed that our graphs are finite, connected