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 ${s>1}$

$\displaystyle \zeta (s) := \sum_{n=1}^{\infty} \frac 1 {n^s} \ \ \ \ \ (1)$

And in fact the right-hand side above is well defined also if ${s}$ is complex, provided ${Re(s) > 1}$ .

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 ${\zeta}$ (as defined in (1)) on all complex numbers ${s}$ with ${Re(s) > 1}$ , and that is defined on the whole complex plane, and we will now use ${\zeta}$ to denote this extended function.

There are several interesting facts about ${\zeta}$ , 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 ${\zeta(-1) = -\frac 1 {12}}$ , which one could state dramatically as

$\displaystyle 1 + 2 + 3 + \ldots + n + \ldots = - \frac 1 {12}$

as in this much watched video.

One connection between the ${\zeta}$ function and primes is the Euler formula

$\displaystyle \zeta(s) = \prod_{p \ \rm prime} \frac { 1 } { 1 - p^{-s}} \ \ \ \ \ (2)$

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

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 ${\Lambda}$ defined so that ${\Lambda(n) = \log p}$ if ${n}$ is a power of the prime ${p}$ and ${\Lambda(n) = 0}$ otherwise. (For example, ${\Lambda( 31) = \log 31, \Lambda ( 32 ) = \log 2, \Lambda ( 33 )=0}$ ). Then it is not difficult to prove that

$\displaystyle \# ( \mbox{ primes } \leq N ) = \frac 1 {\log N} \sum_{n=1}^N \Lambda(n) + N^{.5 + o(1)}$

so proving that the number of primes up to ${N}$ is ${(1 + o(1)) N /\log N}$ (the prime number theorem) is equivalent to proving

$\displaystyle \sum_{n=1}^N \Lambda(n ) = (1+o(1)) \cdot N \ \ \ \ \ (3)$

And proving that the number of primes up to ${N}$ is ${N/\log N \pm N^{.5 + o(1) }}$ is equivalent to proving

$\displaystyle \sum_{n=1}^N \Lambda(n ) = N \pm N^{.5 +o(1)} \ \ \ \ \ (4)$

After some work one gets

$\displaystyle \sum_{n=1}^N \Lambda(n ) = \frac 1 {2\pi i} \int_{0}^\infty \left ( - \frac {\zeta'(s)}{\zeta(s)} \right) \frac {x^s}{s} ds$

which already suggests that the values ${s}$ for which ${\zeta(s)=0}$ are a problem, and the integral evaluates to

$\displaystyle N + \sum_{\rho : \zeta(\rho) = 0, 0 \leq Re(\rho) \leq 1} \frac {N^\rho }{\rho} + O(1)$

The get bounds on the sum ${\sum \frac {N^\rho }{\rho}}$ above, one needs to understand how big is the real part of zeroes of ${\zeta}$ having real part between 0 and 1.

If ${\zeta(s) \neq 0}$ whenever ${Re(s) = 1}$ , this information is already enough to prove that the sum above is ${o(N)}$ , and this is how one proves the prime number theorem. (In fact, the two statements are equivalent.)

The Riemann hypothesis is that if ${\zeta(s) = 0}$ and ${0 \leq Re(s) \leq 1}$ , then ${Re(s) = 1/2}$ , and this implies that the sum is ${N^{.5 + o(1)}}$ .

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 ${\ell}$ a prime cycle if it does not backtrack and it is not derived by going ${k\geq 2}$ times around a cycle of length ${\ell/k}$ . (A prime cycle can use the same edge multiple times, just not twice in a row.)

For a ${(q+1)}$ -regular graph ${G=(V,E)}$ , here is its Ihara zeta function:

$\displaystyle z(s) = \prod_{p \ \rm prime\ cycle} \frac 1 { 1 - q^{-s | p|}} \ \ \ \ \ (5)$

Note the similarity with the Euler product (2).

Here is a bit of magic; Ihara proved the identity

$\displaystyle z(s) = ( 1- q^{-2s} ) ^{|V|-|E|} \cdot ( \det ( I - A q^{-s} + q^{1-2s} I ) )^{-1} \ \ \ \ \ (6)$

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

We know that ${\lambda}$ is an eigenvalue of ${A}$ if and only if

$\displaystyle \det( \lambda I - A) = 0$

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

$\displaystyle \det ( ( 1+ q^{1-2s} ) I - q^{-s} A ) = 0$

which is equivalent to

$\displaystyle \det ( (q^s + q^{1-s} ) I - A ) = 0$

so we have

Fact 1 A complex number ${s}$ is a pole for ${z}$ if and only if ${q^s + q^{1-s}}$ is an eigenvalue of ${A}$ .

In particular, we see that for every pole ${s}$ of ${z}$ it must be the case that ${q^s + q^{1-s}}$ is real, and it is at most ${q+1}$ in absolute value. Now we can introduce the Riemann hypothesis for Ihara function.

Definition 2 The Ihara function ${z}$ of a graph ${G}$ satisfies the Riemann hypothesis if for every pole ${s}$ such that ${0< Re(s) < 1}$ we have ${Re(s) = \frac 12 }$ .

Recall that a connected ${d}$ -regular graph ${G}$ is Ramanujan if and only if for every eigenvalue ${\lambda}$ of ${A}$ we have that either ${|\lambda| = d}$ or ${|\lambda| \leq 2 \sqrt { d-1}}$ .

Now we can prove Ihara’s result.

Theorem 3 (Finally!) A regular connected graph ${G}$ 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 ${s=a+ib}$ is a pole of ${z}$ , and so ${\lambda = q^{s} + q^{1-s}}$ is real. If ${Re(s) =a= \frac 12}$ , this means that ${\lambda = \sqrt q \cdot (q^{ib} + q^{-ib}) = 2 \sqrt q \cos (b \log q)}$ . If ${ a\neq \frac 12}$ , a short calculation shows that ${\lambda^2 = q^{2-2a} + q^{2a} + 2q}$ .

Now we have:

If the Ihara function does not satisfy the Riemann hypothesis, ${G}$ is not Ramanujan. Let ${s = a+ib }$ be a pole such that ${0 < a <1}$ and ${a \neq \frac 12}$ . So we have an eigenvalue ${\lambda}$ such that ${\lambda^2 = q^{2-2a} + q^{2a} + 2q}$ . The function ${q \rightarrow q^{2-2a} + q^{2a} + 2q}$ , in the interval ${[0,1]}$ has a unique minimum at ${a = 1/2}$ , where it takes the value ${4q}$ , and then it attains maxima at 0 and 1, when it takes the value ${(q+1)^2}$ . Now it follows from our constraints on ${a}$ that it must be ${2 \sqrt q < |\lambda| < q+1}$ and so ${G}$ is not Ramanujan.
If the Ihara function satisfies the Riemann hypothesis, ${G}$ is Ramanujan. Let ${\lambda}$ be an eigenvalue of ${A}$ ; then there must be a pole ${s = a + ib}$ such that ${\lambda = q^s +q^{1-s}}$ . We consider two cases. If ${a \neq 1/2}$ , then we must have either ${a\leq 0}$ or ${a \geq 1}$ , and we must also have ${\lambda^2 = q^{2-2a} + q^{2a} + 2q}$ ; by the previous analysis it follows that ${|\lambda| \geq q+1}$ , and so ${|\lambda| = q+1}$ . If ${a = 1/2}$ , then ${\lambda = 2 \sqrt q \cos (b\log q)}$ , so clearly ${|\lambda| \leq 2 \sqrt q}$ .

$\Box$

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.

10 thoughts on “The Riemann hypothesis for graphs”

Mohammad on August 18, 2014 at 5:25 pm said:

> Deligne, …, and proved the Riemann’s hypothesis.

s/Reimann’s hypothesis/Weil’s conjecture/ ?
Paul Rio on August 19, 2014 at 7:29 am said:

Serious paper about the P versus NP Problem

http://hal.archives-ouvertes.fr/hal-00984866
Paul Rio on August 20, 2014 at 5:52 am said:

Serious paper about the P versus NP Problem

Abstract:$UNIQUE \ SAT$ is the problem of deciding whether a

given Boolean formula has exactly one satisfying truth

assignment. The $UNIQUE \ SAT$ is $coNP-hard$. We prove the

$UNIQUE \ SAT$ is in $NP$, and therefore, $NP = coNP$.

Furthermore, we prove if $NP = coNP$, then some problem in

$coNPC$ is in $P$, and thus, $P = NP$. In this way, the $P$

versus $NP$ problem is solved with a positive answer.

Paper: http://hal.archives-ouvertes.fr/hal-00984866
kris on August 22, 2014 at 12:39 pm said:

This is really nice! Thanks.
Pingback: Riemann zeta functions and linear operators | in theory
Sasho Nikolov on October 1, 2014 at 4:56 pm said:

Small note: should the function in the proof of Theorem 3 be $a \to q^{2-2a} + q^{2a} + 2a$ ?
draks2357 on December 7, 2015 at 10:39 pm said:

Why is $q^{1-2s}$ and not just $q^{-2s}$?
draks2357 on April 7, 2017 at 3:42 am said:

The link to the high school (!!) doesn’t work anymore.

Click to access zeta_on_graph_write-up.pdf

Do you have a local copy of it?
Pingback: To cheer you up in difficult times 5: A New Elementary Proof of the Prime Number Theorem by Florian K. Richter | Combinatorics and more
Pingback: Riemann vs. Ihara’s ζzeta Function Variable Question – Math Solution

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

The Riemann hypothesis for graphs

10 thoughts on “The Riemann hypothesis for graphs”

Leave a comment

Share this:

Related

10 thoughts on “The Riemann hypothesis for graphs”

Leave a comment