Analytic and Geometric Number Theory Seminar

I first present an algorithm to compute the truncated theta function in poly-log time. The algorithm is elementary and suited for computer implementation. The algorithm is a consequence of the periodicity of the complex exponential, and the self-similarity of the Gaussian (modular properties of the theta function). I then present several applications. One is a method to compute the Riemann zeta function at height t. The time complexity of this method has exponent 1/3. Another application is a method to compute a Dirichlet character sum to a modulus q, when q is not cube free. The complexity exponent of this method can be as small as 1/3. I also present a hybrid method to compute Dirichlet L-functions. I show how the theta algorithm can be pushed further to handle cubic exponential sums with small cubic argument. I show how that yields yet another method to compute the zeta function, but this time with complexity exponent 4/13 (approximately, 0.307).