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 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 in absolute value, where is the size of the finite field. This means that one way to prove that a family of -regular graphs is Ramanujan is to construct for each graph in the family a variety over such that the determinant that comes up in the zeta function of is the “same” (up to terms that don’t affect the roots, and to the fact that if is a root for one characteristic polynomial, then has to be a root for the other) as the determinant that comes up in the zeta function of the variety . 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 , if is the number of distinct prime divisors of (which would be one if is a prime power) Clark gets a family of graphs with second eigenvalue . (The notes call the number of distinct prime divisors of , 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, -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 -dimensional subspace gives a -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 has at most roots, which follows from unique factorization

• Given desired roots we can always find an univariate polynomial of degree which has those roots, by defining it as .

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 that we want to bound, then the “zeta function” of the sequence is

For example, and this will be discussed in more detail below, if if a bivariate polynomial over , we may be interested in the number of solutions of the equation over , as well as the number of solutions over the extension . In this case, the zeta function of the curve defined by is precisely

and Weil proved that is a rational function, and that if are the zeroes and poles of , that is, the roots of the numerator and the denominator, then they are all at most in absolute value, and one has

How does one get an approximate formula for 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 and that is the number of cycles of the graph of length . Here by “cycle of length ” we mean a sequence of vertices such that and, for , . So, for example, in a graph in which the vertices form a triangle, and are two distinct cycles of length 3, and is a cycle of length 2.

We could define the function

and hope that its zeroes have to do with the computation of , and that can be defined in terms of the characteristic polynomial.

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

and, if are the zeroes and poles of , then

How did we get these bounds? Well, we cheated because we already knew that , where are the eigenvalues of . This means that

Where we used . Now we see that the poles of are precisely the inverses of the eigenvalues of .

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.

We will work up to the definition of the zeta function of curves in three steps: first we look at the zeta function for the integers, and review (all without proof) the formulas that relate it to the distribution of the primes. This will give us an idea of what to expect in other settings.

Then we define the zeta function for “the affine line over ,” in which integers are replaced by univariate polynomials in and primes are irreducible polynomials. We will get the “prime number theorem” that approximately a fraction of degree- polynomials are irreducible. The zeta function ends up being just (the inverse of) a linear function, and it has no roots whatsoever.

Finally, we get to curves: here the place of integers is taken by polynomial functions over the curve, and the primes are the prime ideals of the ring of those polynomial functions. After a few more miracles happen, understanding the zeta function will come down to understanding how many points are there on our curve when we think of it as being defined in instead of , for various choices of . This can also be seen as counting the number of fixed points of the -th power of the Frobenius function, and several more miracles allow us to count the number of such fixed points in terms of a polynomial which is in fact the characteristic polynomial of a linear operator, finally!, but there is a catch: this linear operator acts on the first homology group of the curve, and the stuff which is in that group is not vectors over the reals, so it’s not like our operator is a matrix of which we can compute the determinant just like that. Luckily, there is still a characteristic polynomials, and its roots are algebraic integers that happen to be roots of unity times .

1. The zeta function for the integers

Let’s start again with the zeta function defined over the integers. We have

which is well defined for all complex numbers such that . There is a unique function that agrees with the above definition for all such that , which is defined for all complex numbers, and which is meromorphic, meaning that is very nice (infinitely differentiable, equal to its Taylor series) except at a bounded number of place; we will call this extended function from now on. Whenever we define functions that don’t seem to make sense for some choice of inputs, such an extension is assumed.

We also define a normalized (and “smoothed”) indicator function of the primes, the von Mangoldt function such that if is a power of the prime , and if has at least two distinct prime factors. We have

and after some manipulations one gets the following relation between zeta function and von Mangoldt function:

which in turn leads to the explicit formula

where the summation ranges over the roots of the zeta function such that and, so if the Riemann hypothesis is true, which holds that such roots must have , we would have

we also have

and so, if the Riemann hypothesis is true, the number of primes between and would be plus or minus . (This is in fact an if-and-only-if.)

2. The zeta function of the affine line

Now we think about univariate polynomials over a finite field as taking the place of the integers. This is the case of the “affine line,” because we are talking about polynomials defined over all of which, as a 1-dimensional linear space, is a “line.” Our polynomials, however have arbitrary degree!

So is replaced by . Factorization, however, is defined over the natural numbers, not over . What should take the place of ? There is a simple answer (spoiler alert: monic polynomials), but let’s get there in a way that is easy to generalize.

When we are in a ring, like and , that is a set where we have operations of addition and multiplication, and where division is not always well defined (and hence factorization is interesting), the right objects to think about from the point of view of factorization are the ideals of the ring. An ideal is a subset that is a subgroup for addition and that is closed under multiplication. An ideal generated by an element , written , is the set of all multiples of , and it is called a principal ideal. It is easy to see, over the integers, that all ideals are principal.

(For a given ideal , compute the gcd of all the nonzero elements of the ideal: it is clear that is a subset of , because all elements of are multiples of , but can be obtained, using Euclid’s algorithm, as sums and products of elements of , and so it is in , which means that is a subset of .) The same is true in : all ideals are principal, and for the same reason: there is a version of Euclid’s algorithm for finding the gcd of polynomials. One can properly define factorization and primes only for ideals; in the case of integers, every ideal corresponds to the integer that generates it, and two different integers always define different ideals, except for . So we can use positive integers as representative for the ideals. In the case of polynomials, we have the same reasoning, except that iff is a scalar multiple of . So our representative for ideals will the monic polynomials, that is, polynomials whose leading coefficient is one. This answer our first question. Now comes another question: the formula for the zeta function over integers involves the number ; if is a monic polynomial, is this going to be replaced by ? But is a complex number and is a polynomial over a finite field, so how is that going to work out? Again, we look at this question in a general setting: we already said that we should think of the integer appearing in the formula for the zeta function as a representative of the ideal . Now, every ideal in a ring has a norm, which is the number of shifted copies of the ideal that we need to cover the whole ring, or, more precisely, the cardinality of the quotient . Clearly, the cardinality of the quotient is , because the quotient of by the multiples of is just the ring of integers mod , . What is the norm of a monic polynomial of degree over ? Think about this for a minute. The ring is made of polynomials with operations mod , so every element of is identified by the remainder of the division of by . This remainder is a polynomial of degree , defined by coefficients, and there are such possible remainders.

We conclude that the norm of is and we can finally write our zeta function

and it is common to make the change variable and work with

Now our “primes” are irreducible (in ) monic polynomials.

We still have a von Malgoldt function if and is irreducible, and otherwise. We have, for every monic polynomial ,

and the exponential identity

and manipulations as in the integer case lead to the explicit formula

where ranges over the roots of and the constant term depends on poles of . Nicely, we can just figure out what the zeta function is: there are exactly monic polynomials of degree , and plugging this fact into (3) we have

so there are no roots. One could view as where is the 1-dimensional identity matrix and is the 1-dimensional matrix whose only entry is . From (4), the explicit formula becomes

from which we get that degree- monic polynomials are irreducible.

This gives the analogy with the case of the integers, but there is a much more direct way of seeing that (5) is true.

Every monic polynomial over of degree is going to have roots in the algebraic closure of , counting multiplicities, and so it can be written as

note that while the roots may or may not belong to , all the coefficients of do belong to , once we expand the product. We can certainly take the roots to be a unique representation of , although we should be aware that not all -tuples of elements from the algebraic closure of represent a monic polynomial of degree with coefficients in . (There are infinitely many such tuples but only such polynomials.)

To understand which tuples correspond to monic polynomials in , in a way that will also gives a good understanding of the right-hand side of (5), we introduce the Frobenius function , which is well defined for every but also for every in any extension of . Three useful properties of this function are that:

1. for every (if is prime this is Fermat’s little theorem), in fact, if belongs to an extension of , if and only if ;
2. is bijective in any extension field ;
3. is periodic with period in . This is just another way of saying that in , which is a special case of the first property.

(Many readers will recognize the above as a clumsy statement of the fact that, for every , the Galois group is cyclic of order , and that is a generator.)

From the first property we get that if is a root of and has coefficients in , then is also a root; but then also and so on. From the second property, we get that if we look at all the roots of , they all live in , and so the Frobenius function is going to be a permutation over (because it maps roots to roots, and it does so injectively).

Let us look at the cycles defined by over the multi-set . Each cycle needs to have a length that divides , because is -periodic by the third property. Let’s call two roots in the same cycle equivalent and let pick representatives , of classes of size , respectively. We see that each lives in and that, if we are given the we are implicitly being told all the roots (which we can rediscover by applying ) and now this is a much more economical representation of the polynomial. In fact this is a unique representation up to the choice of representatives, that is, a polynomial may be identified with the (multi)-set of equivalence classes described above. Each equivalence class is called a closed point.

We have reached a punchline: a monic polynomial of degree correspond to a single closed point of size , and the representation of a generic monic polynomial as a collection of closed points corresponds to the factorization of into a product of monic polynomials. Notice also that this argument shows that there can be at most monic polynomials of degree over . (Why?)

Now let’s forget about any specific polynomial , and let us look at all the closed points in . Suppose that we find closed points , each of size , where each must divide . Note that . Then each corresponds to an irreducible monic polynomial of degree such that is a polynomial of degree such that . In turn, these are all the monic polynomial of degree which are powers of irreducible polynomials, and so we have proved the exact formula

3. The zeta function for an affine curve

Now we have an affine irreducible curve in , that is, the set of points such that , where is a bivariate polynomial that is absolutely irreducible, that is, it has no non-trivial divisor even in the algebraic closure of . For example, the curve might be .

The role of the integers is now played by the coordinate ring of , which is . There are a couple of ways of thinking about it. One is the definition: an element is an equivalence class of polynomials, where two polynomials are equivalent if their difference is a multiple of . (In particular they need to agree on the zeroes of .) The other is to thing of an element of the coordinate ring as being a function defined on that is expressed as a polynomial. If were a line, then every element of the coordinate ring would just be a bivariate polynomial restricted to a line, and thus would be essentially a univariate polynomial. That is the case studied in the previous section.

When is not a line, the coordinate ring is more complex, and, in particular, it is not true that all ideals are principal. Although it is not possible any more to think of the ideals as polynomials, we can still think of them as being multi-sets of points. This time an ideal will be a rational effective divisor, that is a multi-set of points of that is Frobenius-invariant. The prime ideals will be closed points: divisors that are a single orbit of the Frobenius. Each divisor has a degree (the number of points counted with multiplicities) and its norm is .

We can then construct analogs of all the expressions we saw in the previous section. We have the definition of zeta function

that after the change of variable becomes

we have the von Malgoldt function which is equal to if is a power of and is prime, and if has at least two distinct prime divisors. We have the exponential formula of

which can be rewritten as

and finally we have

where the right-hand side is the number of points of –that is, solutions of ) in . If was a line, this number would just be . The end of the story of the Riemann hypothesis for curves is that it is more or less the same for every absolutely irreducible ; the number of points will be where the implied constant depends only on , as proved by Weil. His bound is where is the genus of the curve.

If this were all that we are interested in, Stepanov has given a fully elementary proof, and one can read about it in this monograph by Chen, Kayal and Wigderson in a treatment that does not talk about zeta functions, divisors, ideals and so on. The connection between zeroes of the zeta function and the size of is that if one can write the zeta function as a rational function and is the collection of roots, with multiplicities, of the polynomial in the numerator and the one in the denominator, one has

and Weil’s proof establishes that there at most roots, each of absolute value at most , thus the bound claimed above.

Although Stepanov’s technique gives an elementary way to bound , recall that our interest in this story is how to understand just the statement of Weil’s result as it concern a bound of to the absolute value of the eigenvalues of a certain operator.

Extend the Frobenius function to be defined over pairs of elements in the obvious way: ( maps to . Define to be the application of the Frobenius function times, thus . Recall that one of the properties of the Frobenius function is that if and only if . Consider , the set of points of in the algebraic closure of . Then is the number of fixed points of in the space .

In the complex case, if we have a curve , an algebraic function , and we want to count the number of fixed points of , we have the Lefschetz trace formula, which says that all we need to do is to estimate the eigenvalues of when viewed as a linear operator over the first homology group of — whatever that is. (See this blog post.)

Luckily, a Lefschetz trace formula exists in the finite fields case. Unfortunately, I need to end this post on a cliffhanger, because I don’t know how to describe the first homology group of (the formula involves the zero-th, the first, and the second homology group of , but only the first gives a non-trivial contribution).

So far, I am being told that it is not a vector space but a module, and that its ring of coefficients is made of -adic numbers for coprime with . The dimension is , and the Frobenius operator acts as a linear operator. I am also being told that “ what exactly are the elements of the group” is not the right question to ask, and that one should start from the properties that one wants this group to satisfy, verify that there is a construction that meets these properties, and then work with the properties and forget the construction.

In modules, one can still define a determinant and a characteristic polynomial for a linear operator, and here another miracle happens, and the coefficients of this polynomial end up being standard integers, its roots are algebraic integers, and so we talk about the roots being in absolute value.

I hope that there will be a future installment of this ongoing series, in which I explain what is the first homology group and I give some intuition about fixed point formulas in various settings, and, while I am there, maybe even explain what the Riemann-Roch theorem states.