\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}
\hypersetup{colorlinks=true,urlcolor=blue,citecolor=blue,linkcolor=blue}
\usepackage{courier}
\usepackage{tikz}
\usetikzlibrary{calc,matrix,arrows,decorations.markings}
\usepackage{array}
\usepackage{color}
\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}{\mathbb{H}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Zhat}{\widehat\Z}
\newcommand{\Zbar}{\overline\Z}
\newcommand{\Kbar}{\overline K}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Aut}{{\rm Aut}}
\newcommand{\Gal}{{\rm Gal}}
\newcommand{\SL}{{\rm SL}}
\newcommand{\GL}{{\rm GL}}
\newcommand{\PGL}{{\rm PGL}}
\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{\cond}{\operatorname{cond}}
\newcommand{\disc}{\operatorname{disc}}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\q}{\mathfrak{q}}
\newcommand{\m}{{\mathfrak m}}
\renewcommand{\c}{{\mathfrak c}}
\renewcommand{\a}{{\mathfrak a}}
\newcommand{\Frob}{{\rm Frob}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tor}{{\rm tors}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\A}{\mathcal A}
\renewcommand{\P}{\mathcal P}

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

\begin{document}
\setlength{\unitlength}{1in}
\begin{center}
\large
\textbf{18.785 Number Theory\hspace{228pt}Fall~2018}\\\vspace{4pt}
\textbf{Problem Set \#9\hspace{220pt}Due: 11/16/2018}
\normalsize
\begin{picture}(5.8,.1) 
\put(0,0) {\line(1,0){5.8}}
\end{picture}
\end{center}

\subsection*{Description}

These problems are related to the material covered in Lectures 16--18.
Your solutions are to be written up in latex (you can use the latex source for the problem set as a template) and submitted as a pdf-file with a filename of the form \texttt{SurnamePset9.pdf} via e-mail to \texttt{drew@math.mit.edu} by {\bf noon} on the date due.
Collaboration is permitted/encouraged, but you must identify your collaborators, and any references you consulted.
If there are none, write ``\textbf{Sources consulted:\ none}" at the top of your problem set.
The first person to spot each non-trivial typo/error in any of the problem sets or lecture notes will receive 1-5 points of extra credit.
\bigskip

\noindent
\textbf{Instructions:} First do the warm up problems, then pick two of problems 1--5 to solve and write up your answers in latex, then complete the survey problem 6.

\subsection*{Problem 0.}
These are warm up problems that do not need to be turned in.
\begin{enumerate}
\setlength\itemsep{0pt}
\item[(a)] Show $\pi(x):=\sum_{p\le x}1=\int_{2^-}^\infty (1/\log t)d\vartheta(t)$ and $\vartheta(x):=\sum_{p\le x}\log p = \int_{2^-}^\infty \log t d\pi(t)$, and use these identities to prove
\[
\vartheta(x)=\pi(x)\log x - \int_2^x\frac{\pi(t)}{t}dt,\qquad \pi(x)=\frac{\vartheta(x)}{\log x}+\int_2^x \frac{\vartheta(t)}{\log^2 t}dt,
\]
which provides an alternative proof that $\pi(x)\sim x/\log x$ if and only if $\vartheta(x)\sim x$.
\item[(b)] Let $\chi$ be a primitive Dirichlet character of conductor $m>1$.  Verify the identity
\[
\sum_{n\ge 1}\chi(n)x^n=\frac{1}{1-x^m}\sum_{n=1}^{m-1}\chi(n)x^n
\]
and use this to prove that $\Gamma(s)L(s,\chi)$ extends to a holomorphic function on $\C$.
Conclude that $L(s,\chi)$ has an analytic continuation to $\C$.
\end{enumerate}

\subsection*{Problem 1. Mertens' Theorems (49 points)}

In his 1874 paper Mertens' proved three asymptotic bounds on sums over primes; he necessarily did not rely on the Prime Number Theorem, which wasn't proved until 1896.

Define the constants
\[
\alpha :=-\sum_{n\ge 2}\frac{\mu(n)}{n}\log\zeta(n)\approx 0.315718,\qquad \gamma:=\lim_{x\to\infty} \left(\sum_{1\le n\le x}\frac{1}{n}-\log x\right)\approx 0.577216,
\]
where $\mu(n)$ is the M\"obius function from Problem Set 8:
\[
\mu(n):=\begin{cases}
(-1)^{\#\{p|n\}}&\text{if $n\ge 1$ is square free};\\
0&\text{otherwise}.
\end{cases}
\]
Let $\Lambda(n)$ denote the \emph{von Mangoldt function}:
\[
\Lambda(n):=\begin{cases}
\log p&\text{if $n>1$ is a power of a prime $p$};\\
0&\text{otherwise}.
\end{cases}
\]

\begin{theorem}[Mertens]
As $x\to \infty$ we have the following asymptotic bounds:
\begin{enumerate}
\item[{\rm (1)}] $\displaystyle{\sum_{p\le x}\tfrac{\log p}{p} = \log x + O(1)}$;
\item[{\rm (2)}] $\displaystyle{\sum_{p\le x}\tfrac{1}{p} = \log\log x + \gamma - \alpha + O\Bigl(\tfrac{1}{\log x}\Bigr)}$;
\item[{\rm (3)}] $\displaystyle{\sum_{p\le x}\log\Bigl(1\!-\!\tfrac{1}{p}\Bigr) = -\!\log\log x - \gamma + O\Bigl(\tfrac{1}{\log x}\Bigr)}$.
\end{enumerate}
\end{theorem}

\begin{remark}
Mertens showed that the $O(1)$ term in (1) has absolute value bounded by $2$, but we will not need this.
One often sees (3) written as $\prod_{p\le x} (1-\tfrac{1}{p}) = \tfrac{e^{-\gamma}+o(1)}{\log x}$ but our version is a slightly sharper statement that reflects what Mertens actually proved.
\end{remark}

\begin{enumerate}[{\bf(a)}]
\item Show that $\log(n)=\sum_{d|n}\Lambda(d)$ and derive the bounds
\[
\sum_{n\le x}\log n = \sum_{d\le x}\Lambda(d)\lfloor \tfrac{x}{d}\rfloor\qquad\text{and}\qquad \sum_{d\le x}\frac{\Lambda(d)}{d}=\log x + O(1).
\]
Use these bounds and Stirling's formula to prove (1).
\item Let $A(x)$ denote the sum in (1).  Prove that
\[
\sum_{p\le x}\frac{1}{p} = \frac{A(x)}{\log x}+\int_2^x\frac{A(t)}{t(\log t)^2} dt = \log\log x + c + O\Bigl(\tfrac{1}{\log x}\Bigr),
\]
for some constant $c$.
\item Prove that for $\Re(s)>1$ we have
\[
\frac{1}{s}\log \zeta(s) = \int_2^\infty\frac{\pi(t)\, dt}{t(t^s-1)},
\]
and for $t>1$ we have
\[
\frac{1}{t^2(t-1)} = -\sum_{n\ge 2}\frac{\mu(n)}{t(t^n-1)}.
\]
\item Prove that
\[
\sum_{n\ge 2}\sum_p\frac{1}{np^n} = \int_2^\infty\frac{\pi(t)\,dt}{t^2(t-1)} = \alpha
\]
and deduce that (2) and (3) are equivalent.
\end{enumerate}

\begin{remark}
Parts (b) and (d) imply that (3) holds if we replace $\gamma$ with $c'=c+\alpha$.
Problem~2 gives a proof that in fact $c'=\gamma$, so both (2) and (3) hold.
\end{remark}

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{4}
\item Let $P(x):=\sum_{p\le x}\frac{1}{p}=\log\log x +c + \epsilon(x)$ with $\epsilon(x)=O\bigl(\tfrac{1}{\log x}\bigr)$ as in (b).
Show that
\[
\pi(x) = \int_{2^-}^x t\, dP(t) = O\Bigl(\frac{x}{\log x}\Bigr),
\]
and that with the error bound $\epsilon(x)=o\bigl(\tfrac{1}{\log x}\bigr)$ one obtains $\pi(x)\sim\tfrac{x}{\log x}$.
Thus a slightly stronger version of Mertens' 2nd theorem implies the prime number theorem.
\end{enumerate}

\subsection*{Problem 2. Mellin transforms of Dirichlet series (49 points)}
Associated to any arithmetic function $f\colon \Z_{n\ge 1}\to \C$ is a Dirichlet series
\[
D_f(s):=\sum_{n\ge 1} f(n)n^{-s},
\]
which we may view a function of the complex variable $s$ on any region $\Re(s)>\sigma\ge 0$ in which the series converges; conversely, the coefficients of a Dirichlet series define an arithmetic function.

We also have the \emph{summatory function} $S_f\colon\R\to \C$ associated to $f$, defined by
\[
S_f(x):=\sum_{1\le n\le x}f(n),
\]
and the \emph{logarithmic summatory function} $L_f\colon \R\to \C$ defined by
\[
L_f(x):=\sum_{1\le n\le x}\frac{f(n)}{n}.
\]

\begin{enumerate}[{\bf(a)}]
\item Show that $D_f(s)$ is related to $S_f(x)$ and $L_f(x)$ via the formulas
\begin{align*}
D_f(s)&=s\int_1^\infty S_f(t)t^{-s-1}\,dt\qquad\quad\ \, (\Re(s) >\max(0,\sigma)),\\
D_f(s)&=(s-1)\int_1^\infty L_f(t)t^{-s}\,dt\qquad (\Re(s) > \max(1,\sigma)).
\end{align*}
\item By applying (a) to $f=1$, show that
\[
\zeta(s) = \frac{s}{s-1}-s\int_1^\infty \{t\}{t^{-s-1}}\,dt\qquad (\Re(s)>0),
\]
where $\{t\}:=t-\lfloor t\rfloor$.  Use this to show that as $s\to 1$ we have
\[
\zeta(s) = \frac{1}{s-1}+\gamma + O(|s-1|).
\]
\item Let
\[
P(x):=-\sum_{p\le x}\log(1-\tfrac{1}{p})
\]
be the negation of the sum in Mertens' 3rd theorem (see Problem 1), and let $\kappa(n)$ be the arithmetic function defined by $\kappa(n)=1/k$ when $n=p^k$ is a prime power $(k\ge 1)$ and $\kappa(n)=0$ otherwise (as in Problem 4.e on Problem set 8).
Show that
\[
P(x)=L_\kappa(x)+O\left(\tfrac{1}{\log x}\right).
\]
\item Show that $\log\zeta(s) = D_\kappa(s)$ and use (b) to prove that
\[
D_\kappa(s)=\log\frac{1}{s-1}+O(s-1)
\]
as $s\to 1^+$ (along the real line).
\end{enumerate}

\noindent
From parts (b) and (d) of Problem 1 we know that
\begin{equation}\label{eq:P}
P(x)=\log\log x + C + O\left(\tfrac{1}{\log x}\right)
\end{equation}
for some constant $C$ which, according to Mertens' 3rd theorem, is equal to Euler's constant $\gamma$.
You are now in a position to prove this.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{4}
\item From (c) and \eqref{eq:P} we know that $L_\kappa = \log\log x + C+ O\left(\tfrac{1}{\log x}\right)$.
By plugging this into to the formula relating $D_\kappa$ and $L_\kappa$ from (a), show that we have
\[
D_\kappa(s)=\log\frac{1}{s-1} + C + \int_0^\infty (\log t)e^{-t}dt + O\left((s-1)\log\tfrac{1}{s-1}\right)
\]
as $s\to 1^+$.
\item By combining (d) and (e) and letting $s\to 1^+$ show that
\[
C=-\int_0^\infty (\log t)e^{-t}dt.
\]
Then show that the integral is equal to $\Gamma'(1)$, and prove that $\Gamma'(1)=-\gamma$ (you can do this either by using (b) and the functional equation for $\zeta(s)$, or by evaluating the \emph{digamma function} $\Psi(s):=\Gamma'(s)/\Gamma(s)$ at $1$).
\end{enumerate}

\subsection*{Problem 3. Dirichlet density (49 points)}

Let $K$ be a global field and let $\mathcal P$ be the set of nonzero prime ideals of $\O_K$.
The \emph{natural density} of a set $S\subseteq \mathcal P$ is defined by
\[
\delta(S):=\lim_{x\to\infty} \frac{\#\{\p\in S:\N(\p)\le x\}}{\#\{\p \in \mathcal P:\N(\p)\le x\}}
\]
(whenever this limit exists), and its \emph{Dirichlet density} is defined by
\[
d(S):=\lim_{s\to1^+} \frac{\sum_{\p\in S}\N(\p)^{-s}}{\sum_{\p\in \mathcal P}\N(\p)^{-s}}
\]
(whenever this limit exists).  Here $\N(\p):=[\O_K:\p]$ is the absolute norm.

\begin{enumerate}[{\bf(a)}]
\item Show that the denominator in $d(S)$ is finite for real $s > 1$ and that
\[
\sum_{\p\in \P}\N(\p)^{-s} \sim \log\left(\frac{1}{s-1}\right)
\]
as $s\to 1^+$.
\item Let $S$ and $T$ be subsets of $\mathcal P$ with Dirichlet densities.
Show that $S\subseteq T$ implies $d(S)\le d(T)$, and that $d(S)=0$ when $S$ is finite.  Conclude that if $S$ and $T$ differ by a finite set (that is, the sets $S-T$ and $T-S$ are both finite), then $d(S)=d(T)$.
\item Suppose $S,T\subset\P$ have finite intersection.  Show that if any two of the set $S$, $T$, and $S\cup T$ have a Dirichlet density then so does the third and $d(S\cup T)=d(S)+d(T)$.
\item Suppose $K$ is a number field or a finite separable extension of $\Fp(t)$ and define $\P_1:=\{\p \in \P:\N(\p)\text{ is prime}\}$.
Show that $d(\P_1)=1$ and therefore $\P_1$ is infinite.
\item With $K$ and $\mathcal P_1$ as in (d) show for any $S\subseteq \P$, if $S$ has a Dirichlet density then $d(S)=d(S\cap \P_1)$ and otherwise $S\cap \P_1$ does not have a Dirichlet density.  Compute the density of the set of primes of $\Q(i)$ that lie above a prime $p\equiv 3\bmod 4$.
\item Show that if $S\subseteq \P$ has a natural density then it has Dirichlet density $d(S)=\delta(S)$.
\item Show that for $K=\Fq(t)$ the set of primes $(f)$ where $f$ is an irreducible polynomial of even degree has Dirichlet density $1/2$ but no natural density.
\item Show that for $K=\Q$ the set $S_1$ of primes whose leading decimal digit is equal to $1$ has no natural density.
\item Let $A$ be the set of positive integers with leading decimal digit equal to $1$.  Show that
\[
\lim_{s\to 1^+} \frac{\sum_{n\in A} n^{-s}}{\frac{1}{s-1}} = \lim_{s\to 1^+}\frac{\sum_{n\in A}n^{-s}}{\sum_{n\ge 1} n^{-s}} = \log_{10}(2).
\]
\item Adapt your argument in (i) to show that $d(S_1)=\log_{10}(2)$.

\end{enumerate}

\subsection*{Problem 4. PNT for arithmetic progressions (49 points)}
For each integer $m>1$ and integer $a$ coprime to $m$ we define the prime counting function
\[
\pi(x;m,a):=\sum_{\substack{p\le x\\ p\equiv a\bmod m}} 1.
\]
In this problem you will adapt the proof of the PNT in \cite{zagier} (which is essentially the same as given in class except for the argument to show that $\zeta(s)$ has no zeros on $\Re(s)=1$) to prove the PNT for arithmetic progressions, which states that
\[
\pi(x;m,a)\sim\frac{\pi(x)}{\phi(m)}\sim \frac{1}{\phi(m)}\frac{x}{\log x},
\]
where $\phi(m):=\#(\Z/m\Z)^\times$ is the Euler function.
We first set some notation.

Let $\chi$ denote a primitive Dirichlet character of conductor dividing $m$ and define
\[
L(s,\chi):=\sum_{n\ge 1}\chi(n)n^{-s},\qquad \theta_{m,a}(x):=\phi(m)\hspace{-12pt}\sum_{\substack{p\le x\\p\equiv a\bmod m}}\hspace{-12pt}\log p,
\]
\[
\phi(s,\chi):=\sum_p\chi(p)p^{-s}\log p,\quad\Phi_m(s):=\sum_\chi\phi(s,\chi),\quad \Phi_{m,a}(s):=\sum_\chi \overline{\chi(a)}\phi(s,\chi).
\]
Finally, let $K=\Q(\zeta_m)$ be the $m$th cyclotomic field with Dedekind zeta function $\zeta_K(s)$.

\begin{enumerate}[{\bf(a)}]
\item Show that $\theta_{m,a}(x)=O(x)$.
\item Show that for each $\chi$ we have
\[
-\frac{L'(s,\chi)}{L(s,\chi)}=\phi(s,\chi)+h(s,\chi),
\]
for some $h(s,\chi)$ holomorphic on $\Re(s)>1/2$, and conclude that
\[
-\frac{\zeta_K'(s)}{\zeta_K(s)} = \Phi_m(s)+h(s),
\]
for some $h(s)$ holomorphic on $\Re(s)>1/2$.
\item Show that $\zeta_K(s)$ is real-valued on real values of $s$ and proceed as in step (IV) of \cite{zagier} to show that $\zeta_K(s)$, and therefore each $L(s,\chi)$, has no zeros on $\Re(s)=1$.
\item Show that $\Phi_{m,a}(s)-\frac{1}{s-1}$ is holomorphic on $\Re(s)\ge 1$ and prove that
\[
\Phi_{m,a}(s)=s\int_0^\infty e^{-st}\theta_{m,a}(e^t)dt
\]
\item Show that the Laplace transform of $f(t)=\theta_{m,a}(e^t)e^{-t}-1$ extends to a holomorphic function on $\Re(s)\ge 0$ and use this to prove $\theta_{m,a}(x)\sim x$.
\item Show that (e) implies
\[
\pi(x,m)\sim \frac{\pi(x)}{\phi(m)}\sim \frac{1}{\phi(m)}\frac{x}{\log x}.
\]
\end{enumerate}

\subsection*{Problem 5. Factoring with the analytic class number formula (49 points)}

Let $K$ be an imaginary quadratic field with discriminant $D<0$.  Recall from Problem 2 of Problem Set 7 that each ideal class in $\cl\O_K$ can be uniquely represented by a reduced binary quadratic form
\[
f(x,y)=ax^2+bxy+cy^2
\]
which we compactly denote $f=(a,b,c)$.
The coefficients $a,b,c$ are integers with no common factor with $a>0$ and $b^2-4ac=D$ (so $f$ is integral, primitive, positive definite, and of discriminant $D$), and if
\[
-a <b\le a < c\qquad\text{or}\qquad 0\le b\le a = c,
\]
then we say that $f$ is \emph{reduced}, and in this case $a\le \sqrt{|D|/3}$.
Every form is \emph{equivalent} (under the action of $\SL_2(\Z)$) to a unique reduced form $(a,b,c)$ that corresponds to an ideal $I(f)=a\Z+a\tau\Z$ of norm $a$ in the class it represents, where
\[
\tau := \frac{-b+\sqrt{D}}{2a}
\]
and $\O_K=\Z+a\tau\Z$.
Let $\sigma$ be the non-trivial element of $\Gal(K/\Q)$.  If $\a$ is an ideal, then $\bar\a:=\sigma(\a)$ denotes its Galois conjugate.

Everything above also applies to orders $\O\subseteq \O_K$ that are not necessarily maximal, provided we restrict our attention to ideals whose norms are prime to the conductor $c:=[\O_K:\O]$.  We now work in this greater generality and consider binary quadratic forms of discriminant $D=c^2\disc\O_K$ and the class group $\cl\O$ (the group of ideals prime to the conductor modulo equivalence of principal ideals).

\begin{enumerate}[{\bf (a)}]
\item Show that the identity element in $\cl\O$ is represented by the form $(1,0,-D/4)$ when $D$ is even and $(1,1,(1-D)/4)$ when $D$ is odd.
\item Show that if $\a$ is an ideal with Galois conjugate $\bar{\a}$ then $\a\bar\a = (N(\a))$ and therefore $[\a]^{-1}=[\bar\a]$.
Show that in terms of forms, if $\a=I(f)$ with $f=(a,b,c)$ then $\bar\a$ corresponds to the form $(a,-b,c)$, and if $(a,-b,c)$ is not reduced then we must have $b=a$ or $a=c$, but in both these cases $(a,-b,c)$ is equivalent to $(a,b,c)$.
\item An \emph{ambiguous form} $f=(a,b,c)$ is a reduced form for which one of the following holds: $b=0$, $b=a$, or $c=a$.  Show that every ambiguous form corresponds to an ideal class that is equal to its inverse (hence has order $1$ or $2$), and conversely.
\item Show that if $D$ is odd then the ambiguous forms of discriminant $D$ are those of the form
\[
\left(\tfrac{u+v}{4},\tfrac{v-u}{2},\tfrac{u+v}{4}\right)
\]
with $uv=-D$, $\gcd(u,v)=1$, and $0<v/3\le u\le v$, and those of the form
\[
\left(u,u,\tfrac{u+v}{4}\right)
\]
with $uv=-D$, $\gcd(u,v)=1$, and $0<u\le v/3$.
\item Show that if $D$ is odd and has $k$ distinct prime factors then there are $2^{k-1}$ ambiguous forms, each representing a 2-torsion element of $\cl\O$ (an ideal class of order 1 or 2), and conversely, that every 2-torsion element of $\cl\O$ is represented by an ambiguous form.  Conclude that the $2$-torsion subgroup of $\cl\O$ is isomorphic to $(\Z/2\Z)^{k-1}$ and that every ideal class of order 1 or 2 is represented by an ambiguous form.
\item Let $n>1$ be an integer coprime to $6$, not a perfect power.  Show that if $n\equiv 3\bmod 4$ then for the discriminant $D=-n$ every ideal class in $\cl \O$ of order 2 (of which there is at least one) is represented by an ambiguous form whose coefficients yield a nontrivial factorization $uv$ of $n$; show that if $n\equiv 1\bmod 4$ then for the discriminant $D=-3n$ a similar statement holds for all but one ideal class of order 2 (of which there are at least 3).
\item Show that for $\O=\O_K$ we have $\#\cl\O=\frac{1}{\pi}\sqrt{|D|}L(1,\chi)$, where $\chi$ is the Dirichlet character defined by the Kronecker symbol $\left(\tfrac{D}{\cdot}\right)$ (so $\chi(n)=\left(\tfrac{D}{n}\right)$).  This also holds for $\O\subsetneq\O_K$, but you are not required to prove this.
\end{enumerate}
The Extended Riemann Hypothesis (ERH) states that the zeros of every Dirichlet $L$-function $L(s,\chi)$ all lie on the critical line $\Re(s)=\frac{1}{2}$.  Under this assumption there is an effectively computable constant $c_1$ such that if we compute the partial product
\[
L^*:=\prod_{p\le n^{1/5}}\left(1-\chi(p)p^{-1}\right)^{-1}
\]
of $L(1,\chi)$ and put $h^*:=\frac{1}{\pi}\sqrt{|D|}L^*$ (with $D<-4$), then for $h=\#\cl\O$ we have
\[
|h-h^*|<c_1n^{2/5}(\log n)^2;
\]
as shown in \cite{schoof}.
The ERH also implies the existence of an effectively computable constant $c_2$ for which the set of ideals of prime norm $a\le c_2\log^2|D|$ are enough to generate $\cl\O$; this follows from results in \cite{LMO} (for $\O=\O_K$ one can take $c_2=6$, see \cite{bach}).

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{7}
\item Describe a deterministic $O(n^{1/5+o(1)})$ algorithm that, given an integer $n>1$ does one of the following: (1) outputs a nontrivial factorization of $n$, (2) proves that $n$ is prime, (3) proves that the ERH is false.
Assume arithmetic operations on integers (and rational numbers) can be performed in quasi-linear time (i.e. $O(b^{1+o(1)})$ where~$b$ is the number of bits in the operands).  You do not need to spell out all the details of the algorithm, a summary of each step is sufficient (note: you will need to address the case where $n$ is a perfect power separately).
If you are not familiar with the baby-steps giant-steps algorithm, see section 8.8 in these \href{http://ocw.mit.edu/courses/mathematics/18-783-elliptic-curves-spring-2017/lecture-notes/MIT18_783S17_lec8.pdf}{notes} for a quick overview).
\end{enumerate}

\subsection*{Problem 6. Survey (2 points)}
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
Problem 4 & & & \\\hline
Problem 5 & & & \\\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
11/6 & Dirichlet L-functions & & & & \\\hline 
11/12 & Analytic class number formula & & & & \\\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{bach}
E. Bach, \href{http://www.ams.org/journals/mcom/1990-55-191/S0025-5718-1990-1023756-8/S0025-5718-1990-1023756-8.pdf}{\textit{Explicit bounds for primality testing and related problems}}, Math. Comp. \textbf{55} (1990), 335--380.
\bibitem{LMO}
J.C. Lagarias, H.L. Montgomery, and A.M. Odlyzko, \href{http://link.springer.com/article/10.1007%2FBF01390234}{\textit{A bound for the least prime ideal in the Chebotarev Density Theorem}}, Invent. Math. \textbf{54} (1979), 271--296.
\bibitem{schoof}
R. Schoof, \href{http://cr.yp.to/bib/1982/schoof.html}{\textit{Quadratic fields and factorization}}, in "Computational Methods in Number Theory", MC-Tracts 154/155, 1982, 235--286.
\bibitem{zagier}
D. Zagier, \href{http://people.mpim-bonn.mpg.de/zagier/files/doi/10.2307/2975232/fulltext.pdf}{\textit{Newman's short proof of the prime number theorem}}, Amer. Math. Monthly \textbf{104} (1997), 705--708.
\end{thebibliography}

\end{document}