ANALYTIC AND GEOMETRIC NUMBER THEORY SEMINAR | |

Topic: | Analytic Methods to Compute Dirichlet L-Functions and Character Sums |

Speaker: | Ghaith Hiary |

Affiliation: | University of Waterloo, Ontario and Member, School of Mathematics |

Date: | Thursday, February 25 |

Time/Room: | 2:00pm - 3:00pm/S-101 |

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