Riemann zeta functions and linear operators

A conjectural approaches to the Riemann hypothesis is to find a correspondence between the zeroes of the zeta function and the eigenvalues of a linear operator. This was first conceived by Hilbert and by Pólya in the 1910s. (See this correspondence with Odlyzko.) In the subsequent century, there have been a number of rigorous results relating the zeroes of zeta functions in other settings to eigenvalues of linear operators. There is also a connection between the distribution of known zeroes of the Riemann zeta function, as derived from explicit calculations, and the distribution of eigenvalues of the Gaussian unitary ensemble.

In a previous post we talked about the definition of the Ihara zeta function of a graph, and Ihara’s explicit formula for it, in terms of a determinant that is closely related to the characteristic polynomial of the adjacency matrix of the graph, so that the zeroes of the zeta function determine the eigenvalue of the graph. And if the zeta function of the graph satisfies a “Riemann hypothesis,” meaning that, after a change of variable, all zeroes and poles of the zeta function are {1/\sqrt {d-1}} in absolute value, then the graph is Ramanujan. Conversely, if the graph is Ramnujan then its Ihara zeta function must satisfy the Riemann hypothesis.

As I learned from notes by Pete Clark, the zeta functions of curves and varieties in finite fields also involve a determinant, and the “Riemann hypothesis” for such curves is a theorem (proved by Weil for curves and by Deligne for varieties), which says that (after an analogous change of variable) all zeroes and poles of the zeta function must be {\sqrt q} in absolute value, where {q} is the size of the finite field. This means that one way to prove that a family of {(q+1)}-regular graphs is Ramanujan is to construct for each graph {G_n} in the family a variety {V_n} over {{\mathbb F}_q} such that the determinant that comes up in the zeta function of {G_n} is the “same” (up to terms that don’t affect the roots, and to the fact that if {x} is a root for one characteristic polynomial, then {1/x} has to be a root for the other) as the determinant that comes up in the zeta function of the variety {V_n}. Clark shows that one can constructs such families of varieties (in fact, curves are enough) for all the known algebraic constructions of Ramanujan graphs, and one can use families of varieties for which the corresponding determinant is well understood to give new constructions. For example, for every {d}, if {k} is the number of distinct prime divisors of {d-1} (which would be one if {d-1} is a prime power) Clark gets a family of graphs with second eigenvalue {2^k \sqrt{d-1}}. (The notes call {k} the number of distinct prime divisors of {d}, but it must be a typo.)

So spectral techniques underlie fundamental results in number theory and algebraic geometry, which then give us expander graphs. Sounds like something that we (theoretical computer scientists) should know more about.

The purpose of these notes is to explore a bit more the statements of these results, although we will not even begin to discuss their proofs.

One more reason why I find this material very interesting is that all the several applications of polynomials in computer science (to constructing error-correcting codes, secret sharing schemes, {k}-wise independent generators, expanders of polylogarithmic degree, giving the codes used in PCP constructions, self-reducibility of the permanent, proving combinatorial bounds via the polynomial method, and so on), always eventually rely on three things:

  • A multivariate polynomial restricted to a line can be seen as a univariate polynomial (and restricting to a {k}-dimensional subspace gives a {k}-variate polynomial); this means that results about multivariate polynomials can often be proved via a “randomized reduction” to the univariate case;
  • A univariate polynomial of degree {d} has at most {d} roots, which follows from unique factorization

  • Given {d} desired roots {a_1,\ldots,a_d} we can always find an univariate polynomial of degree {d} which has those roots, by defining it as {\prod_i (x-a_i)}.

This is enough to explain the remarkable pseudo-randomness of constructions that we get out of polynomials, and it is the set of principles that underlie much of what is below, except that we are going to restrict polynomials to the set of zeroes of another polynomial, instead of a line, and this is where things get much more complicated, and interesting.

Before getting started, however, I would like to work out a toy example (which is closely related to what goes on with the Ihara zeta function) showing how an expression that looks like the one defining zeta functions can be expressed as a characteristic polynomial of a linear operator, and how its roots (which are then the eigenvalues of the operator) help give bound to a counting problem, and how one can get such bounds directly from the trace of the operator.

If we have quantities {C_n} that we want to bound, then the “zeta function” of the sequence is

\displaystyle  z(T) := \exp\left( \sum_n \frac {C_n}{n} T^n \right)

For example, and this will be discussed in more detail below, if {P(\cdot,\cdot)} if a bivariate polynomial over {{\mathbb F}_q}, we may be interested in the number {C_1} of solutions of the equation {P(x,y) = 0} over {{\mathbb F}_q}, as well as the number of solutions {C_n} over the extension {{\mathbb F}_{q^n}}. In this case, the zeta function of the curve defined by {P} is precisely

\displaystyle  z(T) = \exp\left( \sum_n \frac {C_n}{n} T^n \right)  \ \ \ \ \ (1)

and Weil proved that {z(\cdot)} is a rational function, and that if {\alpha_1,\ldots,\alpha_{2g}} are the zeroes and poles of {z()}, that is, the roots of the numerator and the denominator, then they are all at most {\sqrt q} in absolute value, and one has

\displaystyle  | C_n - q^n | \leq \sum_i |\alpha_i|^n \leq 2g q^{n/2}  \ \ \ \ \ (2)

How does one get an approximate formula for {C_n} as in (2) from the zeroes of a function like (1), and what do determinants and traces have got to do with it?

Here is our toy example: suppose that we have a graph {G=(V,E)} and that {c_\ell} is the number of cycles of the graph of length {\ell}. Here by “cycle of length {\ell}” we mean a sequence {v_0,\ldots,v_\ell} of vertices such that {v_0=v_\ell} and, for {i=0,\ldots,\ell-1}, {\{ v_i,v_{i-1} \} \in E}. So, for example, in a graph in which the vertices {a,b,c} form a triangle, {a,b,c,a} and {a,c,b,a} are two distinct cycles of length 3, and {a,b,a} is a cycle of length 2.

We could define the function

\displaystyle  z(T) := \exp\left( \sum_\ell \frac {c_\ell}{\ell} T^\ell \right)

and hope that its zeroes have to do with the computation of {c_\ell}, and that {z} can be defined in terms of the characteristic polynomial.

Indeed, we have (remember, {T} is a complex number, not a matrix):

\displaystyle  z(T) = \frac 1 {\det (I - TA) }

and, if {\alpha_1,\ldots,\alpha_n} are the zeroes and poles of {z(T)}, then

\displaystyle  c_\ell \leq \sum_i |\alpha_i|^{-\ell}

How did we get these bounds? Well, we cheated because we already knew that {c_\ell = {\rm Tr}(A^\ell) = \sum_i \lambda_i^\ell}, where {\lambda_i} are the eigenvalues of {A}. This means that

\displaystyle  z(T) = \exp \left( \sum_\ell \sum_i \frac {\lambda_i^\ell}{\ell} T^\ell \right)

\displaystyle  = \prod_i \exp \left( \sum_\ell \frac {\lambda_i^\ell}{\ell} T^\ell \right)

\displaystyle  = \prod_i \frac 1 {1- T\lambda_i }

\displaystyle  = \frac 1 { \det(I - TA) }

Where we used {\frac 1 {1-x} = \exp\left( \sum_n \frac { x^n}{n} \right)}. Now we see that the poles of {z} are precisely the inverses of the eigenvalues of {A}.

Now we are ready to look more closely at various zeta functions.

I would like to thank Ken Ribet and Jared Weinstein for the time they spent answering questions. Part of this post will follow, almost word for word, this post of Terry Tao. All the errors and misconceptions below, however, are my own original creation.

Continue reading

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.

Continue reading

Neutronic Encryption

Via Boing Boing and Bruce Schneier, I bring you the web site of singularics corporation.

I cannot do justice to it, because every sentence on every page is very special, but here is about one of their products:

One very important result from our advances in mathematics is a new patent-pending encryption algorithm called Neutronic Encryption™. Unlike strong encryption algorithms widely used today, Neutronic Encryption is not based directly on fixed prime points, but rather on the Neutronic forces that govern the distribution of the primes themselves. The resulting encryption is theoretically impossible to break.

And, in more detail,

Singularics has advanced the state of the art in cryptography by developing a new theoretically unbreakable public-key algorithm called Neutronic Encryption™.

Our advances in Prime Number Theory have led to a new branch of mathematics called Neutronics. Neutronic functions make possible for the first time the ability to analyze regions of mathematics commonly thought to be undefined, such as the point where one is divided by zero. In short, we have developed a new way to analyze the undefined point at the singularity which appears throughout higher mathematics.

This new analytic technique has given us profound insight into the way that prime numbers are distributed throughout the integers. According to RSA’s website, the RSA public key encryption algorithm has an installed based of nearly one billion. Each of these instances of the prime number based RSA algorithm can now be deciphered using Neutronic analysis . Unlike RSA, Neutronic Encryption is not based on two large prime numbers but rather on the Neutronic forces that govern the distribution of the primes themselves. The encryption that results from Singularics’ Neutronic public-key algorithm is theoretically impossible to break.

And you know what else you can do with this newly discovered netronic forces of the primes, besides breaking RSA and realizing impossible-to-break encryption? Continue reading