Applications of Fourier coefficients of modular forms

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.Ph.D