\newif\ifOCW
%\OCWtrue
\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}
\hypersetup{colorlinks=true,urlcolor=blue,citecolor=blue,linkcolor=blue}
\usepackage{courier}
\usepackage{tikz}
\usepackage{tikz-cd}
\usetikzlibrary{calc,matrix,arrows,decorations.markings}
\usepackage{array}
\usepackage{color}
\usepackage{enumerate}
\usepackage{nicefrac}
\usepackage{listings}
\ifOCW\usepackage{soul}\let\oldhref\href\renewcommand{\href}[2]{\oldhref{#1}{\ul{#2}}}\fi
\ifOCW\newcommand{\due}[1]{\hfill\phantom{Due: #1}}\else\newcommand{\due}[1]{\hfill{Due: #1}}\fi
\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{plain}

% 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{\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}
\newcommand{\U}{\mathrm U}
\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~2025}\\\vspace{4pt}
\textbf{Problem Set \#10\due{11/26/2025}}\\\vspace{-6pt}
\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 Lectures 16--18.
Your solutions should be written up in latex and submitted as a pdf-file \ifOCW\else to \href{https://www.gradescope.com/courses/1110057}{Gradescope} \fi by midnight on the date due.
\medskip

\noindent
\textbf{Instructions:} Solve Problem 0, then pick any combination of problems that sum to 100 points. Collaboration is permitted/encouraged, but you must identify your collaborators (including any LLMs you consulted) and any references you consulted outside the course \ifOCW syllabus \else\href{https://math.mit.edu/classes/18.785/2025/syllabus.html}{syllabus}\fi.
Include this information after the \textbf{Collaborators/Sources} prompt at the end of the problem set  (if there are none, you should enter ``none'', do not leave it blank).
Note that each student is expected to write their own solutions; it is fine to discuss problems with others, but your writing must be your own.


\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^-}^x (1/\log t)d\vartheta(t)$ and $\vartheta(x):=\sum_{p\le x}\log p = \int_{2^-}^x \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)}{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. The explicit formula (49 points)}

Let $Z(s):=\pi^{-s/2}\Gamma(\frac{s}{2})\zeta(s)$ denote the completed zeta function; we proved in class that it has the integral representation
\[
Z(s)=\int_1^\infty\sum_{n=1}^\infty e^{-\pi n^2x}(x^{s/2}+x^{(1-s)/2})\frac{dx}{x}-\frac{1}{s}-\frac{1}{1-s},
\]
and extends to a meromorphic function on $\C$ with functional equation $Z(s)=Z(1-s)$.

Recall Hadamard's Factorization Theorem: if $f(s)$ is an entire function and $n$ is an integer for which there exists a positive $c < n+1$ such that $|f(s)|=O\bigl(\exp(|s|^c)\bigr)$ then
\begin{equation}\label{eq:hft}
f(s) = s^m e^{g(s)}\prod_\rho\left(1-\frac{s}{\rho}\right)E_n\left(\frac{s}{\rho}\right),
\end{equation}
where $m=\ord_0(f)$,  $g\in \C[s]$ has degree at most $n$, the product ranges over zeros $\rho\ne 0$ of $f(s)$ (with multiplicity), and $E_n(z)=\exp(\sum_{k=1}^n\frac{z^k}{k})$.

\begin{enumerate}[{\bf(a)}]
\item Prove that we can apply \eqref{eq:hft} to $f(s):=s(s-1)Z(s)$ with $n=1$ and $m=0$.
\item  Prove that we can apply \eqref{eq:hft} to $f(s):=\Gamma(s)^{-1}$ with $n=1$ and $m=1$.
\item Prove that
\[
(s-1)\zeta(s) =e^{a+bs}\prod_\rho\left(1-\frac{s}{\rho}\right)e^{\frac{s}{\rho}}\prod_{n=1}^\infty\left(1+\frac{s}{2n}\right)e^{-\frac{s}{2n}}
\]
for some $a,b\in \C$, where $\rho$ ranges over the zeros of $\zeta(s)$ in the critical strip.
\item Using (c) and the Euler product for $\zeta(s)$, show that $b=\frac{\zeta'(0)}{\zeta(0)}-1$ and
\[
\sum_p\sum_{m\ge 1}p^{-ms}\log p = \frac{s}{s-1}-\frac{\zeta'(0)}{\zeta(0)}-\sum_\rho\left(\frac{1}{s-\rho}+\frac{1}{\rho}\right) -\sum_{n\ge 1}\left(\frac{1}{s+2n}-\frac{1}{2n}\right)
\]
on $\Re(s)>1$.
\end{enumerate}

\noindent
We now recall the identity
\[
\frac{1}{2\pi i}\int_{\sigma-i\infty}^{\sigma+i\infty}\frac{x^s}{s}ds = \begin{cases}
1 & \text{if }x>1,\\
0 & \text{if }0<x<1,
\end{cases}
\]
valid for any $x,\sigma>0$, and define the \emph{Perron integral transform}
\[
f\mapsto \lim_{t\to\infty}\frac{1}{2\pi i}\int_{\sigma-it}^{\sigma+it}f(s)\cdot\frac{x^s}{s}ds.
\]
We also define an alternative version of Chebyshev's function
\[
\psi(x):=\sum_{p^n\le x}\log p,
\]
where the sum is over all prime powers $p^n\le x$ (but note that we take $\log p$ not $\log p^n$).

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{4}
\item Fix $x>1$ not a prime power.
By applying the Perron integral transform to both sides of the equation in (d), and assuming that the RHS can be computed by applying Cauchy's residue formula term by term to the sums (and that the Perron integral transform converges in each case), deduce the \emph{explicit formula}
\[
\psi(x) = x-\sum_\rho \frac{x^\rho}{\rho}-\frac{\zeta'(0)}{\zeta(0)} +\sum_n\frac{x^{-2n}}{2n},
\]
where $\rho$ ranges over the non-trivial zeros of $\zeta(s)$.
\item Fix $c\in [1/2,1)$ and suppose that $\zeta(s)$ has no zeros in the strip $c<\Re(s)<1$. 
Assume that the number of zeros $\rho$ with $|\Im(\rho)|\le T$ is bounded by $O(T\log T)$.
Derive the following bounds: $\psi(x)=x+ O(x^{c+\epsilon})$, $\vartheta(x)=x+O(x^{c+\epsilon})$, and $\pi(x)=\Li(x)+O(x^{c+\epsilon})$, for any $\epsilon > 0$ (in fact one can replace $\epsilon$ with $o(1)$).
\end{enumerate}

\begin{remark}
The explicit formula you obtained in (e) is a slight variation of the one given by Riemann (who also glossed over the somewhat delicate convergence issues you were told to ignore ---  to make this rigorous you actually need to specify the order in which the sum over $\rho$ is computed, it does not converge absolutely).  It is worth noting that even with the explicit formula in hand,  Riemann was unable to prove the prime number theorem because he could not (and we still cannot) prove that one can take $c<1$ in (f).
\end{remark}


\subsection*{Problem 2. 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 $F(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\, dF(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 3. 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 as 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 2), 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 3.f on Problem set 9).
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 2 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(x) = \log\log x + C+ O\left(\tfrac{1}{\log x}\right)$.
By plugging this into 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 4. Conrey characters (49 points)}
The fact that a finite abelian group $G$ is isomorphic to its dual group $\widehat G:=\Hom(G,\U(1))$ implies that the group of Dirichlet characters of modulus $m$ is isomorphic to $(\Z/m\Z)^\times$.  But as noted in lecture, this isomorphism is not canonical.  In this problem you will explore a particular isomorphism due to Brian Conrey that has many attractive features and is often used to identify Dirichlet characters.

The first step is to choose generators for $(\Z/m\Z)^\times$.  Let $m=p_1^{e_1}\cdots  p_r^{e_r}$ be the prime factorization of $m$. We have $\Z/m\Z\simeq \Z/p_1^{e_1}\Z\times \cdots \times \Z/p_r^{e_r}\Z$ by the Chinese remainder theorem, so $(\Z/m\Z)^\times\simeq (\Z/p_1^{e_1}\Z)^\times \times \cdots \times (\Z/p_r^{e_r}\Z)^\times$ and it suffices to consider $(\Z/p^e\Z)^\times$.

\begin{enumerate}[{\bf(a)}]
\item Let $p$ be an odd prime. Show that $(\Z/p^e\Z)^\times$ is cyclic for $e\ge 1$ and that any $g\in\Z$ that generates $(\Z/p^2\Z)^\times$ generates $(\Z/p^e\Z)^\times$ for all $e\ge 1$.  Give an example of an odd prime $p < 100$ and an integer $g\in\Z$ that generates $(\Z/p\Z)^\times$ but not $(\Z/p^2\Z)^\times$.
\item Show that $(\Z/2^e\Z)^\times$ is generated by $\{-1,5\}$ for all $e$.
\end{enumerate}

\noindent
For odd primes $p$, let $g(p)$ be the least positive integer that generates $(\Z/p^2\Z)^\times$, and for $n\in (\Z/p^e\Z)^\times$ let $\log_g(n)$ be the least $x\in \Z_{\ge 0}$ for which $g(p)^x\equiv n \bmod p^e$.  For $a,b\perp p$
\[
\chi_{p^e}(a,b):=\exp\left(2\pi i \frac{\log_g(a)\log_g(b)}{(p-1)p^{e-1}}\right)\in \U(1).
\]
For  $n\in (\Z/2^e\Z)^\times$ let $\log_5(n)$ be the least $x\in  \Z_{\ge 0}$ for which $n\equiv (-1)^{\epsilon(n)} 5^x\bmod 2^e$, with $\epsilon(n)\in \{0,1\}$. For $a,b\perp 2$
\[
\chi_{2^e}(a,b):=\exp\left(2\pi i  \frac{\epsilon(a)\epsilon(b)}{2}+2\pi  i\frac{\log_5(a)\log_5(b)}{2^{e-2}}\right)\in \U(1).
\]
(the second term in the sum vanishes for $e\le 2$).
Finally, for $m=p_1^{e_1}\cdots p_r^{e_r}$ we define
\[
\chi_m(a,b):=\chi_{p_1^{e_1}}(a,b)\cdots \chi_{p_r^{e_r}}(a,b),
\]
which we view as a function $(\Z/m\Z)^\times \times (\Z/m\Z)^\times\to \U(1)$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{2}
\item Let $n\perp m$.  Show that the function $\chi_m(n,\cdot)$ defined by $x\mapsto \chi_m(n,x)$ is a character of $(\Z/m\Z)^\times$ whose extension by zero is a Dirichlet character of modulus $m$.
\item Show that the map $n\mapsto \chi_m(n,\cdot)$ induces an isomorphism from $(\Z/m\Z)^\times$ to the group of Dirichlet characters of modulus $m$, and in particular, that the order of $\chi_m(n,\cdot)$ is equal to the order of $n$ in $(\Z/m\Z)^\times$
\end{enumerate}

\noindent
It follows from \textbf{(d)} that every Dirichlet character of modulus $m$ can be uniquely represented as $\chi_m(n,\cdot)$ with $n\in [1,m-1]$ coprime to $m$; these are called \emph{Conrey characters}.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{4}
\item Show that if $m=p_1^{e_1}\cdots p_r^{e_r}$ then $\cond \chi_m(n,\cdot) = \cond \chi_{p_1^{e_1}}(n,\cdot)\cdots\cond\chi_{p_r^{e_r}}(n,\cdot)$, where $\cond \chi$ denotes the conductor of the Dirichlet character $\chi$.
\item Fix $n>1$  coprime to $p$.
Show that if $p$ is an odd prime then $\cond \chi_{p^e}(n,\cdot)=p^{c+1}$, where $p^c$ is the order of $n^{p-1}$ in $(\Z/p^e\Z)^\times$.
Then show that $\cond \chi_{2^e}(n,\cdot) = 2^{c+2}$, where~$2^c$ is the order of $(-1)^{\epsilon(n)}n$ in $(\Z/2^e\Z)^\times$.
\end{enumerate}

\noindent
The \emph{parity} of a Dirichlet character $\chi$ refers to the sign of $\chi(-1)=\pm 1$.  When $\chi(-1)=1$ we say that $\chi$ is \emph{even} (or has \emph{even parity}) and if $\chi(-1)=-1$ we say  that $\chi$ is \emph{odd}.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{6}
\item Show that for odd primes $p$ the Conrey character $\chi_{p^e}(n,\cdot)$ is even if and only if $n$ is a square modulo $p$ and that the Conrey character $\chi_{2^e}(n,\cdot)$ is even if and only if $e=1$ or $n$ is a square modulo $4$.
\end{enumerate}

\noindent
The \emph{value field} of a Dirichlet character is the number field generated by its values.
The \emph{fixed field} of a Dirichlet character of modulus $m$ is the subfield of $\Q(\zeta_m)$ fixed by the elements of $\Gal(\Q(\zeta_m)/\Q)\simeq (\Z/m\Z)^\times$ that lie in its kernel, where we identify $\sigma \in \Gal(\Q(\zeta_m)/\Q)$ with the unique $a\in(\Z/m\Z)^\times$ for which $\sigma(\zeta_m)=\zeta_m^a$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{7}
\item Compute the parity, order, and conductor of the Conrey character $\chi_{1000}(7,\cdot)$, and determine its value field and fixed field.  If $\chi_{1000}(7,\cdot)$ is not primitive, determine the primitive Conrey character that induces it.
\end{enumerate}


\subsection*{Problem 5. 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 and define $\P_1:=\{\p \in \P:\N(\p)\text{ is prime}\}$.
Show that $d(\P_1)=1$ and in particular, that there are infinitely many degree one primes of $K$.
\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)$.\\ (Hint: Let $a_k:=\#\{\p:\N(\p)=k\}$ and $s_k:=\#\{\p\in S:\N(\p)=k\}$,  prove $\sum_{\p\in S}\N(\p)^{-s} = \sum_{n\ge 1}(s_1+\cdots+s_n)(n^{-s}-(n+1)^{-s})$ and use $\delta(S)$ to bound $\frac{s_1+\cdots+s_n}{a_1+\cdots+a_n}$.)
\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 Use Mertens (2) and your argument in (i) to show that $d(S_1)=\log_{10}(2)$.

\end{enumerate}

\subsection*{Problem 6. 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,a)\sim \frac{\pi(x)}{\phi(m)}\sim \frac{1}{\phi(m)}\frac{x}{\log x}.
\]
\end{enumerate}


\subsection*{Problem 7. 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
Problem 6 & & & \\\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.
\medskip

\noindent
\textbf{Collaborators/Sources}

\begin{thebibliography}{99}
\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}