\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{xcolor}
\usepackage{hyperref}
\definecolor{mylinkcolor}{rgb}{0.5,0.0,0.0}
\definecolor{myurlcolor}{rgb}{0.0,0.0,0.75}
\definecolor{mydeficolor}{rgb}{0.0,0.5,0.0}
\hypersetup{colorlinks=true,urlcolor=myurlcolor,citecolor=myurlcolor,filecolor=myurlcolor,linkcolor=mylinkcolor,linktoc=page}
\newcommand{\defi}[1]{{\color{mydeficolor}\textsf{#1}}}
\usepackage{courier}
\usepackage{tikz}
\usepackage{tikz-cd}
\usetikzlibrary{calc,matrix,arrows,decorations.markings}
\usepackage{array}
\usepackage{enumerate}
\usepackage{nicefrac}
\usepackage{listings}
\lstset{
	basicstyle=\small\ttfamily,
	keywordstyle=\color{blue},
	language=python,
	xleftmargin=16pt,
}

\textwidth=5.8in
\textheight=9in
\topmargin=-0.5in
\headheight=0in
\headsep=.5in
\hoffset  -.4in
\pagestyle{empty}

% growing list of useful macros, use these where appropriate and add to this list as needed
\newcommand{\kbar}{\bar{k}}
\newcommand{\Fp}{\mathbb{F}_p}
\newcommand{\Fpbar}{\overline{\mathbb{F}}_p}
\newcommand{\Fq}{\mathbb{F}_q}
\newcommand{\Fqbar}{\overline{\mathbb{F}}_q}
\newcommand{\Fqm}{\mathbb{F}_{q^m}}
\newcommand{\Fqn}{\mathbb{F}_{q^n}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Qbar}{\overline{\Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\H}{\mathbf{H}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Zhat}{\widehat\Z}
\newcommand{\Zbar}{\overline\Z}
\newcommand{\Kbar}{\overline K}
\newcommand{\Ksep}{{K^{\rm sep}}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Aut}{{\rm Aut}}
\newcommand{\Gal}{{\rm Gal}}
\newcommand{\SL}{{\rm SL}}
\newcommand{\SO}{{\rm SO}}
\newcommand{\GL}{{\rm GL}}
\newcommand{\PGL}{{\rm PGL}}
\newcommand{\PSL}{{\rm PSL}}
\newcommand{\dy}{\,dy}
\newcommand{\dx}{\,dx}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\kron}[2]{\bigl(\frac{#1}{#2}\bigr)}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\ceil}[1]{\lceil{#1}\frac{1}eil}
\newcommand{\Exp}{{\rm E}}
\renewcommand{\O}{\mathcal{O}}
\newcommand{\OK}{\O_K}
\newcommand{\T}{{\rm T}}
\newcommand{\N}{{\rm N}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\Li}{\operatorname{Li}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\Cl}{\operatorname{Cl}}
\newcommand{\disc}{\operatorname{disc}}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\q}{\mathfrak{q}}
\renewcommand{\r}{\mathfrak{r}}
\newcommand{\m}{{\mathfrak m}}
\renewcommand{\c}{{\mathfrak c}}
\renewcommand{\a}{{\mathfrak a}}
\newcommand{\Frob}{{\rm Frob}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\Res}{\operatorname{Res}}
\newcommand{\Div}{\operatorname{Div}}
\newcommand{\tor}{{\rm tors}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\D}{\mathbf{D}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\A}{\mathbb{A}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\CP}{\mathbb{CP}}
\newcommand{\RP}{\mathbb{RP}}
\newcommand{\ab}{{\rm ab}}
\newcommand{\Ind}{\operatorname{Ind}}
\newcommand{\CoInd}{\operatorname{CoInd}}
\newcommand{\Inf}{\operatorname{Inf}}
\newcommand{\inv}{\operatorname{inv}}
\newcommand{\cond}{\operatorname{cond}}
\newcommand{\smat}[4]{{\left(\begin{smallmatrix} #1 & #2 \\ #3 & #4 \end{smallmatrix}\right)}}
\newcommand{\abcd}{\smat{a}{b}{c}{d}}
\newcommand{\Rmat}{\smat{1}{-1}{1}{0}}
\newcommand{\Smat}{\smat{0}{-1}{1}{0}}
\newcommand{\Tmat}{\smat{1}{1}{0}{1}}
\newcommand{\Umat}{\smat{1}{0}{1}{1}}
\newcommand{\M}{\mathbb{M}}
\newcommand{\B}{\mathbb{B}}
\renewcommand{\S}{\mathbb{S}}
\renewcommand{\T}{\mathbb{T}}

\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem*{remark}{Remark}

\begin{document}
\setlength{\unitlength}{1in}
\begin{center}
\large
\textbf{18.786 Number Theory II\hfill Spring~2024}\\\vspace{2pt}
\textbf{Problem Set \#6\hfill Due: 5/7/2024}\vspace{-8pt}
\normalsize
\begin{picture}(5.8,.1) 
\put(0,0) {\line(1,0){5.8}}
\end{picture}
\end{center}
\vspace{-20pt}

\subsection*{Description}

Your solutions should be written up in latex and submitted as a pdf-file on \href{https://www.gradescope.com/courses/730173}{Gradescope} before midnight on the date due.
Collaboration is permitted/encouraged, but you must identify your collaborators or the name of your group on \href{https://psetpartners.mit.edu}{pset partners}, and any references you consulted. If there are none write ``\textbf{Sources consulted: none}'' at the top of your solution.

\textbf{Instructions}: Pick any combination of problems that sum to 100 points, then complete the survey problem.  Note that problems 2 and 3 have a computational component, and while you can solve them on paper, you are encouraged to use a computer algebra system to assist with the computations.  You are also (strongly) encouraged to check your results against examples in the \href{https://www.lmfdb.org}{LMFDB} before submitting your solutions.

\subsection*{Problem 1. Kernels of Hecke operators on $\boldsymbol{S_k(N,\chi)}$ (50 points)}

Throughout this problem we fix $N\in \Z_{\ge 1}$, $k\in \Z_{>2}$, a Dirichlet character $\chi$ of modulus $N$ for which $\chi(-1)=(-1)^k$, and we let $S_k(N,\chi):=S_k(\Gamma_0(N),\chi)$ and $S_k(N):=S_k(\Gamma_0(N))$.

For each positive integer $n$ define the sets
\begin{align*}
\Delta_n(N) &:= \left\{\abcd\in \mathrm{M}_2(\Z): c\equiv 0\bmod N, a\perp N, ad-bc=n\right\},\\
\Delta_n^*(N) &:= \left\{\abcd\in \mathrm{M}_2(\Z): c\equiv 0\bmod N, d\perp N, ad-bc=n\right\},
\end{align*}
(which we note coincide when $n\perp N$), and the function
\[
K_n(z_1,z_2,\chi) := n^{k-1}\sum_{\alpha\in \Delta_n^*(N)} \overline\chi(d)j(\alpha,z_1)^{-k}(\alpha z_1+z_2)^{-k},
\]
for $z_1,z_2\in \H:=\{z\in \C:\Im(z)>0\}$, with $j(\abcd,z):=cz+d$.


\begin{enumerate}[{\bf (a)}]
\item Prove that $K_n$ satisfies the identity
\[
K_n(z_1,-\bar z_2,\chi) = (-1)^k\overline{K_n(-\bar z_1,z_2,\overline\chi)},
\]
and that for any fixed $z_1,z_2\in \H$ we have $K_n(z,z_2,\chi),K_n(z_1,z,\overline\chi)\in S_k(N,\chi)$.
Conclude that $K_n(z,z,\chi)\in S_{2k}(N)$ (no matter what $\chi$ is).
\item Prove that for $n\perp N$ we also have the identities
\begin{align*}
K_n(z_2,z_1,\chi) &= \overline{\chi(n)}K_n(z_1,z_2,\overline\chi),\\
K_n(z_1,-\bar z_2,\chi) &= (-1)^k\overline{\chi(n)K_n(z_2,-\bar z_1,\chi)}.
\end{align*}
\end{enumerate}

If $\Delta_n(N) = \coprod_{i=1}^r\Gamma_0(N)\alpha_i$ with $\alpha_i=\smat{a_i}{b_i}{c_i}{d_i}$, we may define the action of the Hecke operator $T(n)$ on $f\in S_k(N,\chi)$ via
\[
f|_k T(n) = n^{k/2-1}\sum_i\chi (a_i)f|_k\alpha_i.
\]
Recall that for $n\perp N$ we have $f|_kT(n)= \chi(n)f|_kT^*(n)$ (see Lecture 12), in which case we could also have defined this action using a decomposition of $\Delta_n^*(N)$ and replacing $\chi(a_i)$ with $\overline\chi(d_i)$ (but this is not true when $\gcd(n,N) > 1$).

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{2}
\item Derive the following explicit expression for the action of $T(n)$ on $f\in S_k(N,\chi)$:
\[
f|_kT(n) = \frac{1}{n}\sum_{ad=n,a>0}\chi(a)a^k\sum_{0\le b< d} f(\tfrac{az+b}{d}).
\]
\item Let $q:=q(z)=e^{2\pi i z}$.  Show that if $f\in S_k(N,\chi)$ has $q$-expansion $f(z)=\sum_{m\ge 1} a_m q^m$ then $f|_kT(n)$ has $q$-expansion $\sum_{m\ge 1} b_mq^m$ where
\[
b_m = \sum_{d|\gcd(m,n),d>0}\chi(d)d^{k-1}a_{mn/d^2}.
\]
\end{enumerate}

As in lecture, we will work with the inner product on the Hilbert space $L_k^2(\Gamma_0(N),\chi)$
\[
\langle f,g\rangle := \int_{\Gamma_0(N)\backslash\H}\!\!\!\!\!\!\!\! f(z)\overline{g(z)}\Im(z)^kdv(z).
\]
which is equal to the Petersson inner product on $S_k(N,\chi)\subseteq L_k^2(\Gamma,\chi)$ multiplied by a factor of $v(\Gamma_0(N)/\H)=\frac{\pi}{3}\psi(N)$, where $\psi(N):=[\SL_2(\Z):\Gamma_0(N)]=N\prod_{p|N}(1-\tfrac{1}{p})$.

We note the following identity, valid for $z_2\in \H$ and $f\in S_k(N,\chi)$, which you are not required to prove:
\[
\int_\H f(z_1)\overline{(z_1+z_2)}^{-k}\Im(z_1)^kdv(z_1) = \frac{4\pi}{k-1}(i/2)^k f(-\bar z_2).
\]

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{4}
\item Prove that for $f\in S_k(N,\chi)$ and $z_2\in \H$ we have
\[
\langle f(z),K_n(z,z_2,\chi)\rangle = \frac{4\pi}{k-1}(i/2)^k (f|_kT(n))(-\bar z_2).
\]
\end{enumerate}

If $T$ is a linear operator on a Hilbert space $H$ of functions $X\to \C$, we call $K(x,y)$ a \defi{kernel function for $T$} if $(Tf)(y) = \langle f(x),K_y(x)\rangle$ for all $f\in H$, with $K_{y}(x):=K(x,y)\in H$ for all $y\in X$ (so a kernel function for $H$ is a kernel function for the identity operator).

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{5}
\item Prove that
\[
\mathrm K_n(z_1,z_2) := \frac{k-1}{4\pi}(2i)^kK_n(z_1,-\bar z_2,\chi)
\]
is the kernel function of the Hecke operator $T(n)$ on $S_k(N\,\chi)$, and in particular, $K_1(z_1,z_2)$ is the kernel function of $S_k(N,\chi)$.
\item Prove that for $n\perp N$ we have
\[
\langle f|_kT(n),g\rangle = \chi(n)\langle f, g|_kT(n)\rangle
\]
for all $f,g\in S_k(N,\chi)$, thus $T(n)$ is a \defi{$\chi$-Hermitian operator} on $S_k(N,\chi)$.
\item Let $f_1,\ldots,f_r$ be a basis of eigenforms for $S_k(N,\chi)$ normalized so $f_i|_kT(n)=a_n(f)f_i$ for $n\perp N$.
Show that for $n\perp N$ we have
\[
\mathrm K_n(z_1,z_2) = \sum_{i=1}^r \frac{\overline{a_n(f_i)}}{\langle f_i,f_i\rangle} f_i(z_1)\overline{f_i(z_2)}.
\]
\item Prove that for all $n$ (whether coprime to $N$ or not) we have
\[
\tr(T(n)|S_k(N,\chi)) = \int_{\Gamma_0(N)\backslash\H} \overline{\mathrm K_n(z,z)}\Im(z)^k dv(z).
\]
\end{enumerate}

\subsection*{Problem 2. Dirichlet characters and Conrey characters (50 points)}

Recall that a \defi{Dirichlet character} is a totally multiplicative periodic function $\chi\colon \Z\to\C$; this means that $\chi(1)=1$, $\chi(mn)=\chi(m)\chi(n)$ for all $m,n\in \Z$, and there exists a positive integer $q$ for which $\chi(n+q) = \chi(n)$ for all $n\in \Z$, in which case we say that $\chi$ is \defi{$q$-periodic}.  The least such $q$ is the \defi{period} of $\chi$.  A \defi{Dirichlet character of modulus $q$} is a $q$-periodic Dirichlet character for which $\chi(n)\ne 0$ if and only if $n\perp q$, equivalently the extension-by-zero of a character of $(\Z/q\Z)^\times$.

\begin{enumerate}[{\bf(a)}]
\item Show that a product of Dirichlet characters is a Dirichlet character, and that every Dirichlet character admits a unique factorization into Dirichlet characters whose periods are powers of distinct primes.
\item Show that every Dirichlet character of period $q$ is a Dirichlet character of modulus~$q$, but not every $q$-periodic Dirichlet character is a Dirichlet character of modulus $q$, and show that a Dirichlet character of modulus $q$ is also a Dirichlet character of modulus $q'$ for infinitely many distinct $q'$
\end{enumerate}

Thus every Dirichlet character $\chi$ is the extension by zero of a group character, but that group character is not uniquely determined unless the modulus is specified.  If $\chi$ is a Dirichlet character of modulus $q$ and $q'$ is a multiple of $q$, the extension-by-zero of the projection of $\chi$ to $(\Z/q'\Z)^\times$ is a Dirichlet character of modulus $q'$ with $\chi'(n)=\chi(n)$ for all $n\perp q'$.  We say that such a character $\chi'$ is \defi{induced} by $\chi$.  A Dirichlet character that is not induced by any character other than itself is \defi{primitive}.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{2}
\item Show that for every Dirichlet character $\chi$ there is a minimal $c\in \Z_{\ge 1}$ dividing the period $q$ of $\chi$ for which $\chi(n+cm)=\chi(n)$ for all $n,n+cm\perp q$, called the \defi{conductor} of $\chi$, denoted \defi{$\cond(\chi)$}.  Then show that the extension-by-zero $\chi'$ of the projection of $\chi$ to $(\Z/c\Z)^\times$ is the unique primitive Dirichlet character that induces $\chi$.
\end{enumerate}

Dirichlet characters of conductor $1$ are \defi{principal}.  The \defi{order} of a Dirichlet character~$\chi$ is the least $e\in \Z_{\ge 1}$ such that $\chi^e$ is principal.  The \defi{field of values} $\Q(\chi):=\Q(\chi(\Z))$ is the number field obtained by adjoining all values of $\chi$ to $\Q$.  The \defi{fixed field} of a Dirichlet character of period $q$ is the subfield of $\Q(\zeta_q)$ fixed by all automorphisms $\zeta_q\mapsto \zeta_q^a$ for which $\chi(a)=1$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{3}
\item Let $\chi$ be a Dirichlet character order $n$ and period $q$.  Show that $\Q(\chi) =\Q(\zeta_n)$ and its fixed field is a cyclic extension of $\Q$ of degree $n$.  Then show that the primitive character inducing $\chi$ has the same order, field of values, and fixed field as $\chi$ (even though it need not have the same period), and that the conductor $c:=\cond(\chi)$ is the least positive integer for which $\Q(\zeta_c)$ contains the fixed field of $\chi$.
\end{enumerate}

The \defi{parity} of a Dirichlet character $\chi$ is determined by the value of $\chi(-1)\in \{\pm 1\}$; we call $\chi$ \defi{even} if $\chi(-1)=1$ and \defi{odd} otherwise.
Dirichlet characters $\chi$ and $\psi$ are \defi{Galois conjugates} if $\psi=\sigma\circ\chi$ for some $\sigma\in \Gal(\overline{\Q}/\Q)$.  The set of Galois conjugates of a Dirichlet character $\chi$ is its \defi{Galois orbit}.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{4}
\item Show that Galois conjugate Dirichlet characters necessarily have the same period, conductor, parity, order, fixed field, and field of values, and that if $\chi$ and $\psi$ are Galois conjugates, then the primitive characters that induce them are Galois conjugates.
\item Show that if $\chi$ is a Dirichlet character of modulus $q$ and order $e$ then the size of its Galois orbit is determined by the \defi{Euler $\varphi$-function} $\varphi(e):=\#(\Z/e\Z)^\times$.  Then show we can count Galois orbits of Dirichlet characters of modulus $q$ via the formula
\[
\xi(q) := \sum_{e|\lambda(q)} \frac{\varphi(q,e)}{\varphi(e)},
\]
where $\lambda(q)$ is the \defi{exponent} of the group $(\Z/q\Z)^\times$ (the least common multiple of the orders of its elements), and
\[
\varphi(q,e):=\#\{n\in (\Z/q\Z)^\times:\ord(n)=e\}
\]
counts the elements of $(\Z/q\Z)^\times$ of order $e$.  Describe a polynomial-time algorithm to compute $\xi(q)$, given the prime factorizations of $q$ and $\lambda(q)$, and use it to compute $\xi(q)$ for $q=10^{100}$, $q=20!$, and $q = N$, where $N$ is your 9-digit student ID.
\end{enumerate}

\defi{Conrey characters} provide an explicit isomorphism between $(\Z/q\Z)^\times$ and the group of Dirichlet characters of modulus $q$.
For each modulus $q\in \Z_{\ge 1}$ and integers $n,m\in \Z$ coprime to $q$ we define the value $\chi_q(n,m)$ of the Dirichlet character $\chi_q(n,\cdot)$ associated to the image of $n$ in $(\Z/q\Z)^\times$ as follows.
\begin{itemize}
\item For each odd prime $p$. let $g_p$ be the least positive integer that is a primitive root modulo $p^e$ for all $p^e$, and for $n=g_p^a\bmod p^e$ and $m=g_p^b\bmod p^e$ coprime to $p$ let
\[
\chi_{p^e}(n,m) := \exp\left(\frac{2\pi a b i}{\varphi(p^e)}\right).
\]
\item We define $\chi_2(1,1)=\chi_4(1,1)=\chi_4(3,1)=1$ and $\chi_4(3,3)=-1$, and for $2^e>4$, if $n\equiv \epsilon_a 5^a\bmod 2^e$ and $m\equiv \epsilon_b 5^b\bmod 2^e$ with $\epsilon_a,\epsilon_b\in \{\pm1\}$ then
\[
\chi_{2^e}(n,m) := \exp\left(2\pi i \left(\frac{(1-\epsilon_a)(1-\epsilon_b)}{8} + \frac{ab}{2^{e-2}}\right)\right).
\]
\item For general $q$ with prime factorization $q=p_1^{e_1}\cdots p_r^{e_r}$ we define $\chi_q(m,n)$ to be the product of $\chi_{p_i^{e_i}}(n,m)$, and let $\chi_q(n,m):=0$ if either $n$ or $m$ is not coprime to $q$.
\end{itemize}

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{6}
\item Show that one can take $g_p$ to be the least positive integer that generates $(\Z/p^2\Z)^\times$, but the least positive integer that generates $(\Z/p\Z)^\times$ need not generate $(\Z/p^2\Z)^\times$ (hint: consider $p=40487$).
\end{enumerate}

The computation of $\chi_{p^e}(n,m)$ requires computing discrete logarithms in $(\Z/p^e\Z)^\times$ to obtain the values of $a$ and $b$ that are used in the formulas above.  This problem can be efficiently reduced to a discrete logarithm problem in $\Fp^\times =(\Z/p\Z)^\times$, which makes it easy to compute values of $\varphi_q(n,\cdot)$ as long as known of the primes $p|q$ are too large.  For large $p$ there are subexponential-time algorithms for computing discrete logarithms in $\Fp^\times$, but no polynomial-time algorithm is known.  In most practical situations the values of $q$ that arise are small enough (less than $10^{12}$, say) so that one can simply use a baby-steps giant-steps approach to obtain an $\tilde O(\sqrt{p})$ algorithm that is fast enough.

An attractive feature of Conrey characters is that most of the arithmetic invariants of $\chi_q(n,\cdot)$ that one is interested in, including its order, parity, and conductor, can be computed very quickly (in polynomial-time), provided one knows the factorization of~$q$ and the factorization of $p-1$ for primes $p|q$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{7}
\item Show that for $q=p_1^{e_1}\cdots p_r^{e_r}$ and $m,n\in \Z$ coprime to $q$ the following hold:
\begin{itemize}
\item $\chi_q(m,n)=\chi_q(n,m)$.
\item $\chi_q(n,\cdot) = \prod_i \chi_{p_i^{e_i}}(n,\cdot) = \prod_i \chi_{p_i^{e_i}}(n\bmod p^i,\cdot)$.
\item $\ord(\chi_q(n,\cdot)) = \lcm_i \{\ord(\chi_{p_i^{e_i}}(n,\cdot))\}$, with $\ord(\chi_{p^e}(n,\cdot))$ the order of $n$ in $(\Z/p^e\Z)^\times$.
\item $\cond(\chi_q(,\cdot)) = \prod_i\cond(\chi_{p_i^{e_i}}(n,\cdot))$, where
\[
\cond(\chi_{p^e}(n,\cdot)) = \begin{cases}
1 & \text{if }n\equiv 1\bmod p^e,\\
p^{a+2} & \text{if $n\not\equiv \pm 1\bmod p^e$ and $p=2$},\\
p^{a+1} & \text{otherwise},\\
\end{cases}
\]
with $a=v_p(\ord(\chi_{p^e}(n,\cdot)))$.
\item The value field of $\chi_q(n,\cdot)$ is real if and only if $n^2\equiv 1\bmod q$.
\item The parity of $\chi_q(n,\cdot)$ can be computed via
\[
\chi_q(n,-1)=\begin{cases}
\prod_{\text{odd }p|q}\left(\tfrac{n}{p}\right) & \text{if }4\nmid q\\
\left(\tfrac{-1}{n}\right)\prod_{\text{odd }p|q}\left(\tfrac{n}{p}\right) & \text{otherwise}.
\end{cases}
\]
where $p$ ranges over odd prime divisors of $q$ and $\left(\frac{a}{b}\right)$ is the Legendre symbol.
\end{itemize}
\item Give a polynomial-time algorithm to compute the parity, order, conductor of $\chi_q(n,\cdot)$, given the prime factorizations of $q$ and $p-1$ for primes $p|q$.  Use it to compute the parity, order, conductor of $\chi_q(n,\cdot)$ for $q=10^{100}$, $q=20!$, and $q = N$, for the least $n>1$ coprime to $q$, where~$N$ is your 9-digit student ID.
\end{enumerate}

\subsection*{Problem 3. The trace formula for $\boldsymbol{S_k(N,\chi)}$ (50 points)}
Fix $n,N\in \Z_{\ge 1}$, $k\in \Z_{\ge 2}$, and a Dirichlet character $\chi$ of modulus $N$ with $\chi(-1)=(-1)^k$.  
Using the results of Problem 1 it is possible (but highly non-trivial) to derive the following explicit \defi{trace formula} which appears in \cite[Theorem 3]{popa}:\footnote{There is a minor error in \cite[Lemma 4.5]{popa} that does not impact this theorem; see \cite[A.2]{assaf}.}
\begin{align*}
\tr\bigl(T(n)|S_k(N,\chi)\bigr) = &-\frac{1}{2}\sum_{t^2\le 4n}P_k(t,n)\sum_{u|N}H\left(\tfrac{4n-t^2}{u^2}\right)C(N,\chi,u,t,n)\\
& -\frac{1}{2}\sum_{ad=n}\min(a,d)^{k-1}\Phi(N,\chi,a,d)\ +\ 2\delta_{k=2,\chi=1}\sigma_1(N,n).
\end{align*}
where $t$ ranges over $\Z$ and $u,a,d$ range over $\Z_{\ge 1}$ and $P_k, H, C,\Phi,\delta,\sigma_1$ are defined by:
\begin{itemize}
\item $P_k(t,n)$ is the coefficient of $x^{k-2}$ in $(1-tx+nx^2)^{-1}\in \Z[[x]]$.\\
Equivalently, $P_k(t,n)=\frac{\alpha^{k-1}-\bar\alpha^{k-1}}{\alpha-\bar\alpha}$, where $\alpha,\bar\alpha\in \C$ are the roots of $x^2-tx+n$.
\item $H(n)$ is the \defi{Hurwitz class number}: $H(n) = 0$ unless $n\in \Z_{\ge 0}$ and $-n\equiv \square\bmod 4$, in which case $H(0)=-\frac{1}{12}$ and $H(-D)$ counts $\SL_2(\Z)$ equivalence classes of positive definite binary quadratic forms $ax^2+bxy+cy^2$ of discriminant $b^2-4ac=D<0$, weighted by $1/3$ and $1/2$ for $D=-3$ and $D=-4$, respectively.\\
Equivalently, for $D=v^2D_0<0$ with $D_0=\disc \Q(\sqrt{D})$ we have
\[
H(-D) = \sum_{u|v} \frac{2 h(D/u^2)}{w(D/u^2)},
\]
where $h(D')=\#\mathrm{cl}(\O)$ and $w(D')=\#\O^\times$ for the imaginary quadratic order $\mathcal O$ of discriminant $D'=D/u^2$ (so $\mathcal O$ has index $v/u$ in the ring of integers of $K=\Q(\sqrt{D})$).
\item $C(N,\chi,u,t,n)$ is defined for $u|N$ and $u^2|(t^2-4n)$ with $\tfrac{t^2-4n}{u^2}\equiv \square\bmod 4$ by
\begin{align*}
S(N,u,t,n) &:= \{m\in \Z\cap [1,N]: m\perp N\text{ and }m^2-tm+n\equiv 0\bmod Nu\}\\
B(N,\chi,u,t,n) &:= \frac{\psi(N)}{\psi(N/u)}\sum_{m\in S(N,u,t,n)}\hspace{-12pt}\chi(m)\\
C(N,\chi,u,t,n) &:= \sum_{a|u} \mu(a)B(N,\chi,u/a,t,n)
\end{align*}
where $\psi(N)=[\Gamma(1):\Gamma_0(N)]=N\prod_{p|N}(1+\tfrac{1}{p})$ and $\mu(a)$ is the M\"obius function.
\item $\Phi(N,\chi,a,d)$ is defined by
\[
\Phi(N,\chi,a,d) = \sum_{\substack{rs=N,\ m=\gcd(r,s)\\m|\tfrac{N}{\cond(\chi)}\\m|(a-d)}}\hspace{-20pt}\varphi(m)\chi(\hat\alpha_{r,s}(a,d))
\]
where $\alpha_{r,s}\colon \Z/r\Z \times \Z/s\Z\to \Z/\lcm(r,s)\Z$ is the map determined by the CRT and $\hat\alpha_{r,s}$ denotes any lift to $\Z$, and $\varphi(m)=\#(\Z/m\Z)^\times$ is Euler's $\varphi$-function.
\item $\delta_{k=2,\chi-1}\in \{0,1\}$ is 1 iff $k=2$ and $\chi$ is trivial, and  $\sigma_1(N,n)=\sum_{a|n,a\perp N}\tfrac{n}{a}\in \Z$.
\end{itemize}

\begin{enumerate}[{\bf(a)}]
\item Prove that $\tr(T(n)|S_k(N,\chi))\in \Q(\chi)$, where $\Q(\chi)$ is the value field of $\chi$, and that summing over the Galois orbit of $\chi$ yields an integer.  Conclude that if $f(z)=\sum a_n q^n$ is the $q$-expansion of a newform in $S_k(N,\chi)$, then the $a_n$ are algebraic numbers that generate a number field $\Q(f)$ that contains $\Q(\chi)$ (in fact the $a_n$ are algebraic integers, but you are not required to prove this).
\item Show that for any fixed $t,n\in \Z$ with $t^2\le 4n$, the function $g(k):=P_k(t,n)$ defines a sequence of integers satisfying a second order linear recurrence.  Use this to develop an algorithm to efficiently compute $P_k(t,n)$ using only integer arithmetic, with a running time that is quasilinear in $k\log(n)$ (assume that multiplying two $b$-bit integers take $O(b\log b)$ time and adding two $b$-bit integers takes $O(b)$ time).
\item Show that $C(N,\chi,u,t,n)$ is a multiplicative function of $N$ that can be computed using the values of $C(p^e,\chi',p^a,t,n)$, where $e=v_p(N)$, $a=v_p(u)$, and $\chi'$ is the Dirichlet character of modulus $p^e$ that appears in the factorization of $\chi$ into Dirichlet characters of prime power modulus, and give a similar argument for $\Phi(N,\chi,a,d)$.
\item By specializing the formula for $\tr(T(n)|S_k(N))$ to $n=1$ and $\chi=1$, derive a formula for computing $\dim S_k(N) = \tr\bigl(T(1)|S_k(N)\bigr)$ that has the form
\[
\dim S_k(N) = \tfrac{1}{12}w(k)\cdot\! \prod_{p^e\|N}v(p,e) + \delta_{k=2},
\]
where $w(k)$ and $v(p,e)$ are quadruples of integers, with the $v(p,e)$ multiplied point-wise, followed by a dot product with $v(k)$.  Use your formula to compute $\dim S_k(N)$ for $k\in \{2,10^{12}\}$ and $N=10^{20}$, $N=20!$, and $N$ equal to your 9-digit student ID.
\item Recall from Lecture 15 that we have a decomposition
\[
S_k(N)\simeq \bigoplus_{M|N} S_k^{\rm new}(M)^{\oplus \sigma_0(N/M)}
\]
where $\sigma_0(n)=\sum_{d|n}1$ counts the divisors of $n$.  This implies
\[
\dim S_k(N) = \sum_{M|N}\sum_{d|\tfrac{N}{M}}\dim S_k^{\rm new}(M).
\]
For each fixed $k$, part \textbf{(d)} implies that $\dim S_k(N)$ is a sum of multiplicative functions of $N$.
Use M\"obius inversion to express $\dim S_k^{\rm new}(N)$ as a sum of multiplicative functions of $N$ to a obtain a formula of the form
\[
\dim S_k^{\rm new}(N) = \tfrac{1}{12}w(k)\cdot\! \prod_{p^e\|N}u(p,e) + \delta_{k=2}\cdot\mu(N),
\]
where $w(k)$ and $u(p,e)$ are quadruples of integers as in \textbf{(d)}, and give explicit formulas for $u(p,e)$.
Then use your formulas to compute the dimension of $S_k^{\rm new}(N)$ for the values of $k$ and $N$ used in \textbf{(d)}.

\item Note that $\tr(T(n)|S_k(N,\chi))=0$ whenever $\chi(-1)\ne (-1)^k$, since $\dim S_k(N,\chi)=0$.
Show $C(N,\chi,u,t,n)=\chi(-1)C(N,\chi,u,-t,n)$ and $P_k(k,t,n) = (-1)^kP_k(k,-t,n)$, and conclude that if $\chi(-1)\ne (-1)^k$ then the double sum in the first line of the trace formula vanishes for $\chi(-1)\ne (-1)^k$.

Then show that $\Phi(N,\chi,-a,-d)= \chi(-1)\Phi(N,\chi,a,d)$ and conclude that if we replace $\Phi(N,\chi,a,d)$ with $(\Phi(N,\chi,a,d)+(-1)^k\Phi(N,\chi,-a,-d))/2$ in the trace formula it is then valid for all $\chi$, without any restriction on parity.  By summing this generalized trace formula over all $\chi$ of modulus $N$, show that for $N\ge 5$ we have
\[
\dim S_k(\Gamma_1(N)) = \frac{k-1}{24}\prod_{p^e\|N}\left(p^{2e}-p^{2e-2}\right) - \frac{1}{4}\prod_{p^e\|N}\bigl((p^2-1)+e(p-1)^2)p^{e-2}+ \delta_{k=2}.
\]
\end{enumerate}

\subsection*{Problem 4. Survey}
Complete the following survey by rating each problem you attempted on a scale of 1 to~10 according to how interesting you found it (1 = ``mind-numbing," 10 = ``mind-blowing"), and how difficult you found it (1 = ``trivial," 10 = ``brutal").  Also estimate the amount of time you spent on each problem to the nearest half hour.

\begin{center}
\begin{tabular}{l|r|r|r|}
& Interest & Difficulty & Time Spent\\\hline
Problem 1 & & & \\\hline
Problem 2 & & & \\\hline
Problem 3 & & & \\\hline
\end{tabular}
\end{center}


\noindent
Please rate each of the following lectures that you attended, according to the quality of the material (1=``useless", 10=``fascinating"), the quality of the presentation (1=``epic fail", 10=``perfection"), the pace (1=``way too slow", 10=``way too fast", 5=``just right") and the novelty of the material to you (1=``old hat", 10=``all new").

\begin{center}
\begin{tabular}{l|l|r|r|r|r|r}
Date & Lecture Topic & Material & Presentation & Pace & Novelty\\\hline
4/22 & Traces of Hecke operators & & & & \\\hline
4/24 & Modular abelian varieties & & & & \\\hline 
4/29 & Level structures on elliptic curves & & & & \\\hline 
5/1 & Modular curves & & & & \\\hline 
\end{tabular}
\end{center}

\noindent
Please feel free to record any additional comments you have on the problem sets and the lectures, in particular, ways in which they might be improved.

\begin{thebibliography}{99}
\bibitem{assaf}
Eran Assaf, \href{https://arxiv.org/abs/2311.03523}{\textit{A note on the trace formula}}, arXiv:2311.03523.
\bibitem{popa}
Alexandru A. Popa, \href{https://link.springer.com/article/10.1007/s40687-018-0125-5}{\textit{On the trace formula for Hecke operators on congruence subgroups, II}}, Res. Math. Sci. \textbf{5} (2018), article no. 3.
\end{thebibliography}

\end{document}