The IV AMMCS International Conference

Waterloo, Ontario, Canada | August 20-25, 2017

AMMSCS 2017 Plenary Talk

Computing Zeta Functions in Average Polynomial Time

Andrew Sutherland (MIT)

Let $ X $ be a smooth projective curve defined over a finite field of prime order $ p $. Determining the number of rational points on $ X $, or more generally, computing the zeta function of $ X $, is a core problem in computational number theory with many applications. For curves of genus $ g = 1 $, Schoof uses a CRT approach to obtain a polynomial-time algorithm; Schoof's algorithm has been generalized to curves of higher genus by Pila, with a running time that is polynomial in log $ p $ but exponential in $ g $. Alternatively, $ p $-adic approaches based on generalizations of Kedlaya's algorithm yield a running time that is polynomial in $ g $ but exponential in log $ p $. No algorithm with a running time that is polynomial in both $ g $ and log p is currently known.
Now suppose $ X $ is instead defined over the rational numbers, and consider the sequence of curves $ X_p $ obtained by taking the reductions of $ X $ modulo primes $ p $ of good reduction up to some bound $ N $. The problem of computing the zeta functions of all the $ X_p $ naturally arises when one wishes to compute the $ L $-function of $ X $, or to study its Sato-Tate distribution. Harvey has shown that this problem can be solved in time quasi-linear in $ N $; the average time to compute the zeta function of each of the curves $ X_p $ is polynomial in both $ g $ and log $ p $.
I will report on practical implementations of this algorithm, focusing in particular on curves of genus 3, both hyperelliptic and non-hyperelliptic, where we have recently obtained results that are dramatically faster than using either a CRT or $ p $-adic approach to compute the zeta function of each $ X_p $ individually.
Andrew Sutherland received his undergraduate degree in mathematics from MIT in 1990. Following a successful career as an entrepreneur in the software industry, he returned to MIT and completed his Ph.D. in 2007, winning the George M. Sprowles Prize for his thesis on order computations in generic groups. Sutherland is currently a Principal Research Scientist at MIT with a research focus in computational number theory and was recently awarded the Selfridge Prize for his work in this area. He has played a leading role in a number of large scale collaborations in open mathematics, including the polymath project on prime gaps and the L-functions and Modular Forms Database (LMFDB), and he serves on the editorial board of several journals, including Mathematics of Computation.