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:
-
for every
(if
is prime this is Fermat’s little theorem), in fact, if
belongs to an extension of
,
if and only if
;
-
is bijective in any extension field
;
-
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.
This is very nice! Thanks. There is a typo in your definition of Mangoldt’s function, I think. $\Gamma(n) = \log(p)$, rather than $p$ as written.
Dear Luca
The analogies:
1) Expansion property for graphs the prime number theorem for integers
2) The Ramanujan property for graphs The RH for integers
seems very appealing!
This is great,..thank you for share it… it really help me