## Departmental PhD Thesis Exam – Aaron Chow

Everyone is welcome to attend.  Refreshments will be served in the Math Lounge before the exam.

Monday, May 4, 2015
2:10 p.m.
BA6183

PhD Candidate: Aaron Chow
Supervisor:  Kumar Murty
Thesis title:  Applications of Fourier coefficients of modular forms

********************

Abstract:

Let $f$ be a modular form of even weight $k$ and level $N$ which is a normalized eigen-form for the Hecke operators, and write $f(z) = \sum_{n=1}^{\infty} a_f(n) e^{2 \pi i n z}$ for its Fourier expansion at $i \infty$. We assume the Fourier coefficients $\{ a_f(n) \}_{n=1}^{\infty}$ are rational integers. A notable example of such a form is Ramanujan’s cusp form $\Delta$ of weight 12 and level 1. In this case, the Fourier coefficients are given by the famous Ramanujan $\tau$ function:

$\Delta(z) = e^{2 \pi i z} \prod_{n=1}^{\infty} (1 – e^{2 \pi i n z})^{24} = \sum_{n=1}^{\infty} \tau(n) e^{2 \pi i n z} .$

In this thesis, we study applications of the Fourier coefficients $\tau(n)$, and more generally, $a_f(n)$.

First, we present a factoring algorithm that uses an oracle that outputs $a_f(n)$. We show that the algorithm runs in polynomial time for squarefree integers on average, and quasi-polynomial time for non-squarefree integers on average. We note that current factoring algorithms have sub-exponential runtimes. More importantly, when combined with Edixhoven’s (conditional) polynomial time algorithm for computing $a_f(p)$, we get an equivalence between factoring and computing $a_f(n)$.

Secondly, we present an algorithm that uses an oracle that outputs $a_f(n)$ for testing the squarefree-ness of an integer. This algorithm exploits the greatest common divisor of sequences of the form $(a_f(p^r))_{r \in A}$ where $p$ is a prime and $A \subset \mathbb{N}$.

Thirdly, we present a primality testing algorithm that uses an oracle that outputs $\tau(n)$ and $a_{f_E}(n)$ where $f_E$ is a form of weight 2 corresponding to an elliptic curve. As a corollary, we use such an oracle to compute in polynomial time the value of the M\”{o}bius function in the squarefree case.

A copy of the the thesis can be found here:  individual.utoronto.ca/aaronchow/thesis/