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