The Riemann hypothesis for graphs

A regular connected graph is Ramanujan if and only if its Ihara zeta function satisfies a Riemann hypothesis.

The purpose of this post is to explain all the words in the previous sentence, and to show the proof, except for the major step of proving a certain identity.

There are at least a couple of reasons why more computer scientists should know about this result. One is that it is nice to see a connection, even if just at a syntactic level, between analytic facts that imply that the primes are pseudorandom and analytic facts that imply that good expanders are pseudorandom (the connection is deeper in the case of the Ramanujan Cayley graphs constructed by Lubotzky, Phillips and Sarnak). The other is that the argument looks at eigenvalues of the adjacency matrix of a graph as roots of a characteristic polynomial, a view that is usually not very helpful in achieving quantitative result, with the important exception of the work of Marcus, Spielman and Srivastava on interlacing polynomials.

Let us start with the Riemann zeta function. I apologize in advance to anybody who is familiar with the subject because I will probably say that analytic number theory equivalent of “by definition, a problem is NP-complete if it requires exponential time to be solved,” or worse.

One can define, for every real number

 

And in fact the right-hand side above is well defined also if is complex, provided .

It turns out that, just as you can specify a polynomial at a few points and have it uniquely defined at all points, it is possible to specify a complex function in a small range and, if one insists that the function be “nice,” this will fix it everywhere. A complex function is holomorphic if it is differentiable in a neighborhood of every point, which implies that it is infinitely differentiable and always equal to its Taylor series. It is meromorphic if this happens except at a set of isolated points. As it happens, there is only one meromorphic function that agrees with (as defined in (1)) on all complex numbers with , and that is defined on the whole complex plane, and we will now use to denote this extended function.

There are several interesting facts about , after this extension, some going back to Euler (who worked them out before there were satisfactory definitions for what he was doing), such as the fact that , which one could state dramatically as

as in this much watched video.

One connection between the function and primes is the Euler formula

 

The reason the function comes up in number theory is that when one tries to bound how many primes there are between and , after writing an expression for it, and taking a Dirichlet transform, one ends up with terms that blow up if is zero for certain values of .

I will give some intuition for this connection, so that we can see that this is somewhat different, even syntactically, from the result for graphs that is the focus of this post.

Consider the von Mangoldt function defined so that if is a power of the prime and otherwise. (For example, ). Then it is not difficult to prove that

so proving that the number of primes up to is (the prime number theorem) is equivalent to proving

And proving that the number of primes up to is is equivalent to proving

After some work one gets

which already suggests that the values for which are a problem, and the integral evaluates to

The get bounds on the sum above, one needs to understand how big is the real part of zeroes of having real part between 0 and 1.

If whenever , this information is already enough to prove that the sum above is , and this is how one proves the prime number theorem. (In fact, the two statements are equivalent.)

The Riemann hypothesis is that if and , then , and this implies that the sum is .

Several generalizations of the zeta functions have been defined over other mathematical objects generalizing the integers and the primes, and a particularly successful direction was the setting of curves over finite fields, where Weil proved the analog of the Riemann hypothesis. In 1949 Weil formulated the Weil conjectures, which apply to zeta functions defined over varieties in finite fields. The conjectures were that such zeta functions were rational functions (analogous to the fact that in the complex case the zeta function it is a ratio of holomorphic functions, and a holomorphic function can be seen as an infinitary version of a polynomial; the Euler product formula can also be seen an infinitary version of a rational function), that they satisfied certain symmetries (the functional equation), and that they satisfied a, properly defined, Riemann hypothesis.

On the one hand, the Weil conjectures were related to very concrete questions, such as counting solutions to polynomial equations in finite fields, and, via the fact that their resolution was used to prove the Ramanujan conjecture, they are part of the lineage that led to expander constructions. Their eventual proof, however, had a great impact in the development of some of the most abstract parts of contemporary mathematics.

Bernard Dwork (yes, Cynthia Dwork’s father) made the first progress, by proving the conjecture that Weil’s zeta functions are rational functions. Grothendieck took a long view and worked on developing a cohomology theory that would yield the result. (A cohomology is something that can be used to transfer certain results from one mathematical framework to another, especially results involving formulas that count things; here the goal was to develop a cohomology that would get the Weil conjectures for varieties over finite fields by transferring the result from other setting where proofs were already known.) Grothendieck developed étale cohomology (that the autocorrect of my text editor tried to change to “stale cohomology”) toward this goal (now it is one of the foundations of modern algebraic geometry) and proved the rest of the conjectures except the Riemann hypothesis.

Deligne, who was a student of Grothendieck’s, found a way around Grothendieck’s full program, which remains incomplete, and proved the Riemann’s hypothesis.

I refer the interested reader to this awesome post by Terry Tao, which gives a whirlwind tour of zeta functions and Riemann hypotheses all over mathematics, and we now come to expander graphs.

We will call a cycle of length a prime cycle if it does not backtrack and it is not derived by going times around a cycle of length . (A prime cycle can use the same edge multiple times, just not twice in a row.)

For a -regular graph , here is its Ihara zeta function:

Note the similarity with the Euler product (2).

Here is a bit of magic; Ihara proved the identity

 

where is the adjacency matrix of . Don’t panic! Things are getting really simple from this point on.

We know that is an eigenvalue of if and only if

and we see that is a pole of (a point in which the formula for involves a division by zero) when

which is equivalent to

so we have

Fact 1 A complex number is a pole for if and only if is an eigenvalue of .

In particular, we see that for every pole of it must be the case that is real, and it is at most in absolute value. Now we can introduce the Riemann hypothesis for Ihara function.

Definition 2 The Ihara function of a graph satisfies the Riemann hypothesis if for every pole such that we have .

Recall that a connected -regular graph is Ramanujan if and only if for every eigenvalue of we have that either or .

Now we can prove Ihara’s result.

Theorem 3 (Finally!) A regular connected graph is Ramanujan if and only if its Ihara zeta function satisfies the Riemann hypothesis.

Proof: We first do a couple of preliminary calculations. Say that is a pole of , and so is real. If , this means that . If , a short calculation shows that .

Now we have:

• If the Ihara function does not satisfy the Riemann hypothesis, is not Ramanujan. Let be a pole such that and . So we have an eigenvalue such that . The function , in the interval has a unique minimum at , where it takes the value , and then it attains maxima at 0 and 1, when it takes the value . Now it follows from our constraints on that it must be and so is not Ramanujan.
• If the Ihara function satisfies the Riemann hypothesis, is Ramanujan. Let be an eigenvalue of ; then there must be a pole such that . We consider two cases. If , then we must have either or , and we must also have ; by the previous analysis it follows that , and so . If , then , so clearly .

This survey paper has a lot more information. I took the exposition of Ihara’s proof above from this high school (!!) project. (Note that, in the latter link, the definition of Ramanujan graph is wrong, but the proof is correct.)

I should also note that Murty’s survey attributes the above theorem to Ihara, but this wikipedia page (I know, I know . . . ) attributes only the formula (6) to Ihara, and attributes the above theorem to Sunada. I have not had a chance to look at the primary sources yet.