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.

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 {{\mathbb F}_q},” in which integers are replaced by univariate polynomials in {{\mathbb F}_q} and primes are irreducible polynomials. We will get the “prime number theorem” that approximately a {1/n} fraction of degree-{n} 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 {{\mathbb F}_{q^n}} instead of {{\mathbb F}_q}, for various choices of {n}. This can also be seen as counting the number of fixed points of the {n}-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 {\sqrt q}.

1. The zeta function for the integers

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

\displaystyle  \zeta(s) := \sum_{n\geq 1} \frac 1 {n^s} = \prod_{p \ \rm prime} (1 - p^{-s})^{-1}

which is well defined for all complex numbers {s} such that {Re(s) > 1}. There is a unique function that agrees with the above definition for all {s} such that {Re(s)>1}, 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 {\zeta} 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 {\Lambda(n)} such that {\Lambda(n) = p} if {n=p^k} is a power of the prime {p}, and {\Lambda(n) = 0} if {n} has at least two distinct prime factors. We have

\displaystyle  \log n = \sum_{d | n} \Lambda(d)

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

\displaystyle  \zeta (n) = \exp \left ( \sum_n \frac { \Lambda(n)}{\log n} n^{-s} \right)

which in turn leads to the explicit formula

\displaystyle  \sum_{1 \leq n \leq N} \Lambda (n) = N - \sum_{\rho} \frac {N^{\rho}}{\rho} + O(1)

where the summation ranges over the roots {\rho} of the zeta function such that {0< Re(\rho) \leq 1} and, so if the Riemann hypothesis is true, which holds that such roots must have {Re(\rho) = 1/2}, we would have

\displaystyle  \sum_{1 \leq n \leq N} \Lambda (n) = N \pm N^{1/2+o(1)}

we also have

\displaystyle  \sum_{1 \leq n \leq N} \Lambda (n) = \log N \cdot ( \# {\rm primes} \ \leq N) \pm N^{1/2 + o(1)}

and so, if the Riemann hypothesis is true, the number of primes between {1} and {N} would be {N/\log N} plus or minus {N^{1/2 + o(1)}}. (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 {{\mathbb F}_q} 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 {{\mathbb F}_q} which, as a 1-dimensional linear space, is a “line.” Our polynomials, however have arbitrary degree!

So {{\mathbb Z}} is replaced by {{\mathbb F}_q[x]}. Factorization, however, is defined over the natural numbers, not over {{\mathbb Z}}. What should take the place of {{\mathbb N}}? 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 {{\mathbb Z}} and {{\mathbb F}_q[x]}, 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 {n}, written {(n)}, is the set of all multiples of {n}, and it is called a principal ideal. It is easy to see, over the integers, that all ideals are principal.

(For a given ideal {I}, compute the gcd {g} of all the nonzero elements of the ideal: it is clear that {I} is a subset of {(g)}, because all elements of {I} are multiples of {g}, but {g} can be obtained, using Euclid’s algorithm, as sums and products of elements of {I}, and so it is in {I}, which means that {(g)} is a subset of {I}.) The same is true in {{\mathbb F}_q[x]}: 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 {(n)} corresponds to the integer {n} that generates it, and two different integers always define different ideals, except for {(-n) = (n)}. So we can use positive integers as representative for the ideals. In the case of polynomials, we have the same reasoning, except that {(f) = (g)} iff {f} is a scalar multiple of {g}. 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 {1/n^s}; if {f}is a monic polynomial, is this going to be replaced by {1/f^s}? But {s} is a complex number and {f} 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 {n} appearing in the formula for the zeta function as a representative of the ideal {(n)}. Now, every ideal {I} in a ring {R} 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 {|R/ I|}. Clearly, the cardinality of the quotient {{\mathbb Z} / (n)} is {n}, because the quotient of {{\mathbb Z}} by the multiples of {n} is just the ring of integers mod {n}, {{\mathbb Z}/ n{\mathbb Z}}. What is the norm of a monic polynomial {f} of degree {d} over {{\mathbb F}_q [x]}? Think about this for a minute. The ring {{\mathbb F}_q [x]/(f)} is made of polynomials with operations mod {f}, so every element {g} of {{\mathbb F}_q[x]/(f)} is identified by the remainder of the division of {g} by {f}. This remainder is a polynomial of degree {d-1}, defined by {d} coefficients, and there are {q^d} such possible remainders.

We conclude that the norm of {f} is {|f| = q^{deg(f)}} and we can finally write our zeta function

\displaystyle  z(s) := \sum_{f\ \rm monic} q^{-s \cdot deg(f)}

and it is common to make the change variable {T:= q^{-s}} and work with

\displaystyle   Z(T) := \sum_{f\ \rm monic} T^{deg(f)} \ \ \ \ \ (3)

Now our “primes” are irreducible (in {{\mathbb F}_q}) monic polynomials.

We still have a von Malgoldt function {\Lambda (f) = deg(g)} if {f = g^k} and {g} is irreducible, and {\Lambda(f) = 0} otherwise. We have, for every monic polynomial {f},

\displaystyle  \log_q |f| = \sum_{g \ {\rm divides} \ f} \Lambda (g)

and the exponential identity

\displaystyle  Z(T) = \exp \left( \sum_{f \ {\rm monic}} \frac { \Lambda(f)} {deg |f| } T^{deg f}\right)

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

\displaystyle  \sum_{f : deg(f) = n} \Lambda(f) = q^n \pm \sum_\alpha |\alpha|^n + \Theta(1)

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

\displaystyle   Z(T) = \sum_{n\geq 1} q^n T^{n} = \frac 1 {1-qT} \ \ \ \ \ (4)

so there are no roots. One could view {1-qT} as {det (I - T M)} where {I} is the 1-dimensional identity matrix and {M} is the 1-dimensional matrix whose only entry is {q}. From (4), the explicit formula becomes

\displaystyle  \sum_{f : deg(f) = n} \Lambda(f) = q^n  \ \ \ \ \ (5)

from which we get that {q^n/n \pm O(q^{n/2})} degree-{n} 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 {f} over {{\mathbb F}_q} of degree {n} is going to have {n} roots {a_1,\ldots,a_n} in the algebraic closure of {{\mathbb F}_q}, counting multiplicities, and so it can be written as

\displaystyle  f(x) = (x-a_1) \cdot (x- a_2) \cdots (x-a_n)

note that while the roots {a_i} may or may not belong to {{\mathbb F}_q}, all the coefficients of {f(\cdot)} do belong to {{\mathbb F}_q}, once we expand the product. We can certainly take the roots {(a_1,\ldots,a_n)} to be a unique representation of {f}, although we should be aware that not all {n}-tuples {(a_1,\ldots,a_n)} of elements from the algebraic closure of {{\mathbb F}_q} represent a monic polynomial {P} of degree {n} with coefficients in {{\mathbb F}_q}. (There are infinitely many such tuples but only {q^n} such polynomials.)

To understand which tuples correspond to monic polynomials in {{\mathbb F}_q[x]}, in a way that will also gives a good understanding of the right-hand side of (5), we introduce the Frobenius function {{\rm Fr} (x) := x^q}, which is well defined for every {x\in {\mathbb F}_q} but also for every {x} in any extension of {{\mathbb F}_q}. Three useful properties of this function are that:

  1. {{\rm Fr}(x) = x} for every {x\in {\mathbb F}_q} (if {q} is prime this is Fermat’s little theorem), in fact, if {x} belongs to an extension of {{\mathbb F}_q}, {{\rm Fr}(x) = x} if and only if {x\in {\mathbb F}_q};
  2. {{\rm Fr}} is bijective in any extension field {{\mathbb F}_{q^n}};
  3. {{\rm Fr}} is periodic with period {n} in {{\mathbb F}_{q^n}}. This is just another way of saying that {x^{q^n} = x} in {{\mathbb F}_{q^n}}, 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 {n}, the Galois group {Gal({\mathbb F}_{q^n}/ {\mathbb F}_q)} is cyclic of order {n}, and that {{\rm Fr}} is a generator.)

From the first property we get that if {a} is a root of {f} and {f} has coefficients in {{\mathbb F}_q}, then {{\rm Fr}(a)} is also a root; but then also {{\rm Fr}({\rm Fr} (a))} and so on. From the second property, we get that if we look at all the roots {a_1,\ldots,a_n} of {f}, they all live in {{\mathbb F}_{q^n}}, and so the Frobenius function {{\rm Fr}} is going to be a permutation over {a_1,\ldots,a_n} (because it maps roots to roots, and it does so injectively).

Let us look at the cycles defined by {{\rm Fr}} over the multi-set {a_1,\ldots,a_n}. Each cycle needs to have a length {d} that divides {n}, because {{\rm Fr}} is {n}-periodic by the third property. Let’s call two roots in the same cycle equivalent and let pick representatives {b_1,\ldots,b_k}, of classes of size {d_1,\ldots,d_k}, respectively. We see that each {b_i} lives in {{\mathbb F}_{q^{d_i}}} and that, if we are given the {b_i} we are implicitly being told all the roots (which we can rediscover by applying {{\rm Fr}}) 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 {n} correspond to a single closed point of size {n}, and the representation of a generic monic polynomial {f} as a collection of closed points corresponds to the factorization of {f} into a product of monic polynomials. Notice also that this argument shows that there can be at most {q^n / n} monic polynomials of degree {n} over {{\mathbb F}_q}. (Why?)

Now let’s forget about any specific polynomial {f}, and let us look at all the closed points in {{\mathbb F}^q_n}. Suppose that we find {k} closed points {b_1,\ldots,b_k}, each of size {d_i}, where each {d_i} must divide {n}. Note that {\sum_i d_i = q^n}. Then each {b_i} corresponds to an irreducible monic polynomial {f_i} of degree {d_i} such that {f^{n/d_i}_i} is a polynomial of degree {n} such that {\Lambda (f^{n/d_i}) = d_i}. In turn, these are all the monic polynomial of degree {n} which are powers of irreducible polynomials, and so we have proved the exact formula

\displaystyle  \sum_{f \ {\rm monic}} \Lambda (f) = \sum_i d_i = q^n

3. The zeta function for an affine curve

Now we have an affine irreducible curve {C} in {{\mathbb F}_q^2}, that is, the set of points {(x,y) \in F_q^2} such that {P(x,y)=0}, where {P} is a bivariate polynomial that is absolutely irreducible, that is, it has no non-trivial divisor even in the algebraic closure of {{\mathbb F}_q}. For example, the curve might be {y^2 = x^3 - x -1}.

The role of the integers is now played by the coordinate ring of {C}, which is {{\mathbb F}_q [x,y] / (P)}. 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 {P}. (In particular they need to agree on the zeroes of {P}.) The other is to thing of an element of the coordinate ring as being a function defined on {C} that is expressed as a polynomial. If {C} 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 {C} 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 {C} that is Frobenius-invariant. The prime ideals will be closed points: divisors that are a single orbit of the Frobenius. Each divisor {D} has a degree {deg(D)} (the number of points counted with multiplicities) and its norm is {q^{deg(D)}}.

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

\displaystyle  \zeta(s) := \sum_{D \ \rm divisor} \frac 1 {q^{s\cdot deg(D)}}

that after the change of variable {T= q^{-s}} becomes

\displaystyle  Z(T) := \sum_{D \ \rm divisor} T^{deg(D)}

we have the von Malgoldt function {\Lambda(D)} which is equal to {deg(A)} if {D} is a power of {A} and {A} is prime, and {\Lambda(D) =0} if {D} has at least two distinct prime divisors. We have the exponential formula of {Z}

\displaystyle  Z(T) = \exp \left( \sum_D \frac{\Lambda (D)}{deg(D)} T^{deg (D)) } \right)

which can be rewritten as

\displaystyle  Z(T) = \exp \left( \sum_{n\geq 1} \frac{ \sum_{D: deg(D) = n} \Lambda (D)}{n} \cdot T^{n} \right)

and finally we have

\displaystyle  \sum_{D: deg(D) = n} \Lambda(D) = | C( {\mathbb F}_{q^n} ) |

where the right-hand side is the number of points of {C} –that is, solutions of {P(x,y) = 0}) in {{\mathbb F}_{q^n}}. If {C} was a line, this number would just be {q^n}. The end of the story of the Riemann hypothesis for curves is that it is more or less the same for every absolutely irreducible {P}; the number of points will be {q^n \pm O( q^{n/2})} where the implied constant depends only on {P}, as proved by Weil. His bound is {q^n \pm 2g q^{n/2} + O(1) } where {g} 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 {C({\mathbb F}_{q^n})} is that if one can write the zeta function as a rational function and {a_1,\ldots,a_k} is the collection of roots, with multiplicities, of the polynomial in the numerator and the one in the denominator, one has

\displaystyle  | C( {\mathbb F}_{q^n} ) | = q^n \pm \sum_i |a_i|^n + O(1)

and Weil’s proof establishes that there at most {2g} roots, each of absolute value at most {\sqrt q}, thus the bound claimed above.

Although Stepanov’s technique gives an elementary way to bound {|C({\mathbb F}_{q^n} )|}, recall that our interest in this story is how to understand just the statement of Weil’s result as it concern a bound of {\sqrt q} 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: ({x,y)} maps to {(x^q,y^q)}. Define {{\rm Fr}^{(n)}} to be the application of the Frobenius function {n} times, thus {{\rm Fr}^{(n)} (x,y) = (x^{q^n},y^{q^n} )}. Recall that one of the properties of the Frobenius function is that {{\rm Fr}^{(n)} (x) = x} if and only if {x\in {\mathbb F}_{q^n}}. Consider {C(\overline {\mathbb F}_q)}, the set of points of {C} in the algebraic closure of {{\mathbb F}_q}. Then {|C({\mathbb F}_{q^n})|} is the number of fixed points of {{\rm Fr}^{(n)}} in the space {C(\overline {\mathbb F}_q)}.

In the complex case, if we have a curve {C = \{ (x,y) \in {\mathbb C}^2 : P(x,y) = 0 \}}, an algebraic function {F: C \rightarrow C}, and we want to count the number of fixed points of {F}, we have the Lefschetz trace formula, which says that all we need to do is to estimate the eigenvalues of {F} when viewed as a linear operator over the first homology group of {C} — 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 {C} (the formula involves the zero-th, the first, and the second homology group of {C}, 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 {p}-adic numbers for {p} coprime with {q}. The dimension is {2g}, 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 {\sqrt q} 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.

3 thoughts on “Riemann zeta functions and linear operators

  1. 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.

  2. 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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s