\documentclass[%
version=last,%
a5paper,
12pt,%
headings=small,%
bibliography=totoc,%
index=totoc,%
listof=leveldown,%
listof=nochaptergap,%
%abstract=true,%
twoside,%
reqno,%
cleardoublepage=empty,%
open=any,%
titlepage=false,%
%draft=false,%
draft=true,%
%DIV=classic,%
DIV=12,%
headinclude=false,%
pagesize]%
{scrbook}
%{scrreprt}
%{scrartcl}

%\usepackage{layout}
%\usepackage[notref,notcite]{showkeys}

\usepackage{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\refoot{The Riemann Hypothesis}
\lofoot{\leftmark}
\ofoot{\pagemark}
%\ifoot{\headmark}

\usepackage{moredefs,lips}
%\makeindex
%\usepackage{makeidx}

\usepackage[perpage,symbol]{footmisc}
%\renewcommand{\captionformat}{. }

\usepackage{graphicx} % allows \rotatebox
\usepackage{verbatim}
%\usepackage{subfig}
%\usepackage{float}
%\floatplacement{figure}{t}
%\usepackage[section]{placeins} % floats do not cross sectional divisions
%\usepackage{placeins} % floats do not cross \FloatBarrier
%\usepackage{afterpage}

\usepackage{relsize} % Here \smaller scales by 1/1.2; \relscale{X} scales by X

\newenvironment{mynotequote}%
{\begin{quotation}%
\setlength{\parindent}{0pt}
\raggedright%
\sffamily%
\noindent}{\end{quotation}}

%\begin{comment}

\renewenvironment{quote}{\begin{list}{}
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}}
\item\relax}
{\end{list}}

\renewenvironment{quotation}{\begin{list}{}%
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}
\setlength{\listparindent}{1em}
\setlength{\itemindent}{\listparindent}
\setlength{\parsep}{\parskip}}
\item\relax}
{\end{list}}

%\end{comment}

%\usepackage{verse}

%\usepackage{multicol}
\usepackage{pstricks,pst-plot,pst-math,xcolor,pst-tree}

\usepackage{amsmath,amsthm,amssymb,bm,upgreek}
\allowdisplaybreaks
\DeclareMathOperator{\ekok}{ekok}
\DeclareMathOperator{\lcm}{lcm}

\newcommand{\mi}{\mathrm i\,}
%\newcommand{\midotless}{\mathrm{\i}\,} gives eszet
%\newcommand{\midotless}{\text{\i}\,}
\newcommand{\me}{\mathrm e}
\newcommand{\C}{\mathbb C}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\T}{\mathbb T}
\newcommand{\D}{\mathbb D}
\newcommand{\units}[1]{#1^{\times}}
\newcommand{\pru}[1][n]{\upomega_{#1}{}}
\newcommand{\Zmod}[1][n]{\Z/#1\Z}
\DeclareMathOperator{\dee}{d}
%\DeclareMathOperator{\Dee}{D}
%\DeclareMathOperator{\deeA}{dA}
\DeclareMathOperator{\Li}{Li}
\renewcommand{\setminus}{\smallsetminus}
\newcommand{\conj}[1]{\overline{#1}}
%\newcommand{\doubtful}{\textsuperscript?}

%\newcommand{\Exists}[1]{\exists#1\;}
%\newcommand{\Forall}[1]{\forall#1\;}
%\newcommand{\The}[1]{\text{\rotatebox[origin=c]{180}{$\iota$}}#1\;}

\newtheorem{theorem}{Theorem}
%\newtheorem*{porism}{Porism}
\newtheorem*{corollary}{Corollary}

\renewcommand{\vec}[1]{\bm{#1}}
\newcommand{\Ham}{\mathbb H}
\DeclareMathOperator{\cont}{C}
\newcommand{\lto}{\Rightarrow}
\newcommand{\liff}{\Leftrightarrow}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\divides}{\mid}
\newcommand{\ndivides}{\nmid}
\DeclareMathOperator{\bigO}{O}
\DeclareMathOperator{\littleo}{o}
\newcommand{\included}{\subseteq}
\DeclareMathOperator{\Ball}{B}
\newcommand{\ball}[1][a;\epsilon]{\Ball(#1)}

\newcommand{\inv}{^{-1}}

\newcommand{\figref}[1]{Fig.\ \ref{#1}}

\usepackage[turkish,polutonikogreek,english]{babel}
\usepackage{gfsporson}
\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}{%
%\relscale{0.9}
\textporson{#1}}}

\newcommand{\enquote}[1]{``#1''}

\newcommand{\abs}[1]{\left\lvert#1\right\rvert}

\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}
\usepackage{url}

%\usepackage{chngcntr}
%\counterwithout{figure}{section}
%\counterwithout{figure}{chapter}

\begin{document}

\title{Prime Numbers}
\subtitle{A Nesin Mathematics Village course}
\author{David Pierce}
\date{February 4--10, 2019\\
Last edited February 14, 2019}
\publishers{Matematik B\"ol\"um\"u\\
Mimar Sinan G\"uzel Sanatlar \"Universitesi\\
\url{dpierce@msgsu.edu.tr}\\
\url{mat.msgsu.edu.tr/~dpierce/}\\
\url{polytropy.com}}

\maketitle

\addchap*{Preface}

Here are notes for the second offering
of my course on the Prime Number Theorem.
In preparing and delivering my lectures,
I used the typeset notes from the first offering.
I had arranged those according to topic,
though the Preface described what I had done each day.
The present notes are given by day
and cover only what I actually talked about in class.
Therefore the earlier notes are still useful.

The second time around,
on the first day of my course,
I was given a list of 47 registered students.
I was told that more might attend, unofficially.
I did not count, but there were a lot of students
in the audience of the Ni\c sanyan Library.
Their numbers shrunk, day by day.
On the seventh day, there was one student,
and I talked with him about algebraic number theory,
since he expressed curiosity about number theory in general.
Other students from previous days were still in the Village,
but said they hadn't known there would be class.
Had they come too,
I would have summarized the material relegated to the appendices.

Two days of material is so relegated,
judging by page count.
Another time I may skip Bertrand's Postulate,
which took up part of Tuesday and the entirety of Wednesday.


\tableofcontents

\listoffigures

\chapter{Monday}

Let $p_n$ be the $n$th prime number, thus:
\begin{equation*}
  \begin{array}{*{13}{c|}c}
      n&1&2&3&4& 5& 6& 7& 8& 9&10&11&12&\dots\\\hline
    p_n&2&3&5&7&11&13&17&19&23&29&31&37&\dots
  \end{array}
\end{equation*}
If $x\in\R$, we define
\begin{equation*}
  \max\bigl(\{k\in\N\colon p_k\leq x\}\cup\{0\}\bigr)=\uppi(x).
\end{equation*}
Thus $\uppi(x)$ is the number of primes that do not exceed $x$:
\begin{equation*}
  \uppi(x)
=\abs{\{p\colon p\leq x\}}
=\sum_{p\leq x}1.
\end{equation*}
We aim to understand $\uppi$,
whose graph is in \figref{fig:pi}.
\begin{figure}
  \centering
  \psset{unit=5mm}
  \begin{pspicture}(-1,-1)(20,9)
    \psline{->}(0,0)(20,0)
    \psline{->}(0,0)(0,9)
    \psset{linewidth=1.2pt}
    \psline{-o}(0,0)(2,0)
    \psline{*-o}(2,1)(3,1)
    \psline{*-o}(3,2)(5,2)
    \psline{*-o}(5,3)(7,3)
    \psline{*-o}(7,4)(11,4)
    \psline{*-o}(11,5)(13,5)
    \psline{*-o}(13,6)(17,6)
    \psline{*-o}(17,7)(19,7)
    \psline{*-}(19,8)(20,8)
    \uput[d](2,0){$2$}
    \uput[d](3,0){$3$}
    \uput[d](5,0){$5$}
    \uput[d](7,0){$7$}
    \uput[d](11,0){$11$}
    \uput[d](13,0){$13$}
    \uput[d](17,0){$17$}
    \uput[d](19,0){$19$}
    %\uput[l](0,1){$1$}
    \uput[l](0,2){$2$}
    %\uput[l](0,3){$3$}
    \uput[l](0,4){$4$}
    %\uput[l](0,5){$5$}
    \uput[l](0,6){$6$}
    %\uput[l](0,7){$7$}
    \uput[l](0,8){$8$}
  \end{pspicture}
  \caption{$y=\uppi(x)$}\label{fig:pi}
  
\end{figure}

\begin{theorem}
  [Euclid \protect{\cite[\textsc{ix}.20]{MR1932864}}]\label{thm:Euclid}
$\lim_{x\to\infty}\uppi(x)=\infty$.
\end{theorem}

\begin{proof}
  We show that
  $p_k$ exists for each $k$ in $\N$.
  We use strong induction.
  For some $n$ in $\N$, whenever $k<n$,
  suppose $p_k$ exists.  Then
  \begin{gather*}
    p_1p_2\cdots p_{n-1}+1\equiv1\pmod{p_k},\\
    p_k\ndivides p_1p_2\cdots p_{n-1}+1.
  \end{gather*}
  However, thus sum must \emph{have} a prime factor, since
  \begin{equation*}
    p_1p_2\cdots p_{n-1}+1\geq2,
  \end{equation*}
  even when $n=0$ (for then the product is $1$).
  The least prime factor is $p_n$.
  By strong induction, $p_k$ exists for all counting numbers $k$.
\end{proof}

We can say a little more,
as Hardy and Wright do \cite[p.\ 12]{MR568909}.
See \figref{fig:log-log}.
\begin{figure}
  \centering
  \psset{unit=5mm}
  \begin{pspicture}(-1,-1)(20,9)
    \psline{->}(0,0)(20,0)
    \psline{->}(0,0)(0,9)
    \psset{linewidth=1.2pt}
    \psline{-o}(0,0)(2,0)
    \psline{*-o}(2,1)(3,1)
    \psline{*-o}(3,2)(5,2)
    \psline{*-o}(5,3)(7,3)
    \psline{*-o}(7,4)(11,4)
    \psline{*-o}(11,5)(13,5)
    \psline{*-o}(13,6)(17,6)
    \psline{*-o}(17,7)(19,7)
    \psline{*-}(19,8)(20,8)
    \uput[d](2,0){$2$}
    \uput[d](3,0){$3$}
    \uput[d](5,0){$5$}
    \uput[d](7,0){$7$}
    \uput[d](11,0){$11$}
    \uput[d](13,0){$13$}
    \uput[d](17,0){$17$}
    \uput[d](19,0){$19$}
    %\uput[l](0,1){$1$}
    \uput[l](0,2){$2$}
    %\uput[l](0,3){$3$}
    \uput[l](0,4){$4$}
    %\uput[l](0,5){$5$}
    \uput[l](0,6){$6$}
    %\uput[l](0,7){$7$}
    \uput[l](0,8){$8$}
    \psplot2{20}{x log 2 log div log 2 log div}
    \psdots(2,0)(4,1)(16,2)
  \end{pspicture}
  \caption{$y=\uppi(x)$ and $y=\log_2\log_2x$}\label{fig:log-log}
  
\end{figure}

\begin{theorem}\label{thm:log-log}
  For real numbers $x$ exceeding $1$,
  \begin{equation}\label{eqn:log-log}
\uppi(x)\geq\log_2\log_2 x.
  \end{equation}
\end{theorem}

\begin{proof}
  Since
  \begin{equation*}
    \log_2\log_2 x\leq0
    \iff\log_2x\leq1
    \iff x\leq2,
  \end{equation*}
  the claim is true when $x\leq 2$.
  If $x>2$, then for some $k$ in $\N$,
  \begin{equation*}
    2^{2^k}\geq x>2^{2^{k-1}}.
  \end{equation*}
  From the two inequalities respectively, we have
  \begin{align*}
    k&\geq\log_2\log_2x,&\uppi(x)&\geq\uppi(2^{2^{k-1}}).
  \end{align*}
  To prove \eqref{eqn:log-log} now, it is enough to show
  \begin{equation*}
    \uppi(2^{2^{k-1}})\geq k.
  \end{equation*}
  For \emph{this,} it is enough to show
  \begin{equation}\label{eqn:22}
    2^{2^{k-1}}\geq p_k.
  \end{equation}
  This follows by strong induction from the proof of Theorem \ref{thm:Euclid}.
  Suppose, for some $n$ in $\N$, that \eqref{eqn:22} is true whenever $k<n$.
Then
  \begin{multline*}
    p_n
    \leq p_1p_2\cdots p_{n-1}+1\\
    \leq 2^{2^0}2^{2^1}\cdots 2^{2^{n-2}}+1
    =2^{2^0+2^1+\dots+2^{n-2}}+1\\
    =2^{2^{n-1}-1}+1
    \leq 2\cdot 2^{2^{n-1}-1}
    =2^{2^{n-1}},
  \end{multline*}
  so \eqref{eqn:22} holds when $k=n$.
\end{proof}

We aim to prove
the \textbf{Prime Number Theorem} or \textbf{PNT}
(Theorem \ref{thm:PNT}, page \pageref{thm:PNT}),
established in 1896 by Hadamard
and de la Vall\'ee-Poussin independently,
namely
\begin{equation}\label{eqn:PNT-preview}
  \lim_{x\to\infty}\frac{\uppi(x)\log x}x=1,
\end{equation}
where $\log$ is the natural logarithm, $\log_{\me}$.
We can rewrite \eqref{eqn:PNT-preview} as either of
\begin{align*}
  \uppi(x)\log x&\sim x,&
  \uppi(x)&\sim\frac x{\log x}.
\end{align*}
We may say then that $\uppi(x)$
and $x/\log x$ are \textbf{asymptotic} to one another \cite[p.\ 8]{MR568909}.
For example, when we define
\begin{equation}\label{eqn:Li-def}
\Li(x)=\int_2^x\frac{\dee t}{\log t},
\end{equation}
we obtain
\begin{equation}\label{eqn:Li}
\Li(x)\sim\frac x{\log x}
\end{equation}
by L'H\^opital's Rule.
First we compute
  \begin{equation*}
    \frac{\Li(x)-x/\log x}{x/\log x}
    =\frac{\log x\cdot\Li(x)-x}x.
  \end{equation*}
  If the latter is $f/g$, then,
  since $g$ grows without bound, we compute
  \begin{equation*}
    \frac{f'}{g'}=\frac{(1/x)\Li(x)+\log x/\log x-1}1=\frac{\Li(x)}x,
  \end{equation*}
  and if \emph{this} is $f/g$, then $f'/g'$ is $1/\log x$,
  which tends to $0$ as $x$ grows without bound.

A weaker form of the PNT is
\textbf{Chebyshev's Theorem}
(Theorem \ref{thm:C}, page \pageref{thm:C}),
established around 1850,
that the functions
\begin{align*}
  &\frac{\uppi(x)\log x}x,&&\frac x{\uppi(x)\log x}
\end{align*}
are bounded above on some interval $[a,\infty)$;
  we write this also as
\begin{equation*}
\uppi(x)\asymp\frac x{\log x},
\end{equation*}
using the notation of Hardy and Wright \cite[p.\ 7]{MR568909},
in whose terminology
$\uppi(x)$ and $x/\log x$ are
\textbf{of the same order of magnitude.}
For example
\begin{equation*}
  2+\sin x\asymp 1.
\end{equation*}

Our first big result will be \textbf{Bertrand's Postulate}
(Theorem \ref{thm:B}, page \pageref{thm:B}),
that for every counting number $n$,
\begin{equation}\label{eqn:2n-n}
  \uppi(2n)-\uppi(n)>0.
\end{equation}
In the proof, we shall use that there is a sequence
  \begin{equation}\label{eqn:631}
    2,\ 3,\ 5,\ 7,\ 13,\ 23,\ 43,\ 83,\ 163,\ 317,\ 631
  \end{equation}
of primes,
where each successive term is the greatest prime
that is less than twice the previous term.
Because of this, any $n$ for which \eqref{eqn:2n-n} fails
must be at least $631$.



\chapter{Tuesday}

As from Theorem \ref{thm:Euclid} we derived Theorem \ref{thm:log-log},
so from Bertrand's Postulate,
which is an improvement on Theorem \ref{thm:Euclid},
we can derive an improvement of Theorem \ref{thm:log-log},
namely
\begin{equation*}
  \uppi(x)\geq\log_2x-1,
\end{equation*}
and therefore, by an exercise, for large-enough $x$,
\begin{equation*}
  \uppi(x)\geq\log x.
\end{equation*}
To prove Bertrand's Postulate itself,
we define
\begin{equation*}%\label{eqn:theta}
  \upvartheta(x)=\sum_{p\leq x}\log p.
\end{equation*}
Then for example
\begin{multline*}
  \upvartheta(10)=\log2+\log3+\log5+\log7\\
  =\log(2\cdot3\cdot5\cdot7)
  =\log(210).
\end{multline*}

We shall often make use of the \textbf{binomial coefficients,}
defined by
  \begin{equation}\label{eqn:binom-coeff}
    \binom nk=\frac{n!}{(n-k)!\;k!},
  \end{equation}
where $0\leq k\leq n$.

\begin{theorem}[Binomial Theorem]\label{thm:binom}
  For all natural numbers $n$,
  \begin{equation}\label{eqn:binom}
    (x+y)^n=\sum_{k=0}^n\binom nkx^{n-k}y^k.
  \end{equation}
\end{theorem}

\begin{proof}
By direct computation from \eqref{eqn:binom-coeff},
  \begin{align*}
    \binom m0&=1,&\binom mm&=1,
  \end{align*}
  and
  \begin{equation*}
    1\leq k\leq m\implies\binom mk+\binom m{k-1}=\binom{m+1}k.
  \end{equation*}
  Then \eqref{eqn:binom} is true when $n=0$,
  and if it is true when $n=m$, then
  \begin{multline*}
    (x+y)^{m+1}=(x+y)\sum_{k=0}^m\binom mkx^{m-k}y^k\\
    =\sum_{k=0}^m\binom mkx^{m+1-k}y^k
    +\sum_{k=0}^m\binom mkx^{m-k}y^{k+1}\\
    =x^{m+1}+\sum_{k=1}^m\binom mkx^{m+1-k}y^k
    +\sum_{k=0}^{m-1}\binom mkx^{m-k}y^{k+1}+y^{m+1}\\
    =x^{m+1}+\sum_{k=1}^m\binom mkx^{m+1-k}y^k
    +\sum_{k=1}^m\binom m{k-1}x^{m+1-k}y^k+y^{m+1}\\
    =x^{m+1}+\sum_{k=1}^m\binom{m+1}kx^{m+1-k}y^k+y^{m+1}
    =(x+y)^{m+1},
  \end{multline*}
  so \eqref{eqn:binom} is true when $n=m+1$.
\end{proof}

\begin{corollary}
Each binomial coefficient is a natural number.
\end{corollary}

We shall often use the following bound \cite[Thm 441, p.\ 341]{MR568909}.

\begin{theorem}\label{thm:2xlog2}
  For all positive real numbers $x$,
\begin{equation}\label{eqn:lem}
\upvartheta(x)<2x\log 2.
\end{equation}
\end{theorem}

\begin{proof}
Since
\begin{equation*}%\label{eqn:theta[x]}
  \upvartheta(x)=\upvartheta\bigl([x]\bigr),
\end{equation*}
where
\begin{equation*}
  [x]=\max\{n\in\Z\colon n\leq x\},
\end{equation*}
it is enough to prove the claim when $x$ is a counting number.
We shall use strong induction,
but need some preliminary work.
Primes enter the argument through a standard exercise,
  \begin{equation}\label{eqn:p-div}
    0<k<p\implies p\biggm|\binom pk.
  \end{equation}
  The proof uses Euclid's Lemma \cite[Proposition \textsc{vii}.30]{MR1932864},
  that a prime measuring a product measures one of the factors;
  symbolically,
  \begin{equation*}
    p\divides ab\And p\ndivides a\implies p\divides b.
  \end{equation*}
  Thus, in particular, since
  \begin{equation*}
    p\biggm|\binom pk\cdot k!\cdot(p-k)!,
  \end{equation*}
  but
  \begin{equation*}
    0<k<p\implies p\ndivides k!\cdot(p-k)!,
  \end{equation*}
we can conclude \eqref{eqn:p-div}.
  In the same way,
  \begin{equation*}
    n-k\leq k<p\leq n\implies p\biggm|\binom nk,
  \end{equation*}
  and therefore
  \begin{equation*}
    n-k\leq k\implies\prod_{k<p\leq n}p\biggm|\binom nk
    \implies\prod_{k<p\leq n}p\leq\binom nk.
  \end{equation*}
  Taking natural logarithms preserves the last inequality, and
  \begin{equation*}
    \log\prod_{k<p\leq n}p
    =\sum_{k<p\leq n}\log p
    =\upvartheta(n)-\upvartheta(k),
  \end{equation*}
  so
  \begin{equation}\label{eqn:theta-nk}
    n-k\leq k\implies\upvartheta(n)-\upvartheta(k)\leq\log\binom nk.
  \end{equation}
  We can now proceed.
  We assume \eqref{eqn:lem} holds when $x$ is an integer less than $n$.
  We have to consider four cases of $n$.
  \begin{asparaenum}
  \item  
    In case $n=1$, we have
    \begin{equation*}
      \upvartheta(n)=\upvartheta(1)=0=2n\log2.
    \end{equation*}
    \item
    In case $n=2$, we compute
    \begin{equation*}
      \upvartheta(n)=\upvartheta(2)=\log2<4\log2=2n\log2.
    \end{equation*}
    \item
    In case $n=2m$, where $m>1$, then,
    $2m$ being composite,
    \begin{equation*}
      \upvartheta(n)
      =\upvartheta(2m)
      =\upvartheta(2m-1)
      <2(2m-1)\log2
      <2n\log2.
    \end{equation*}
    \item
    We suppose finally $n=2m+1$, where again $m>1$.
    As a special case of \eqref{eqn:theta-nk},
    \begin{equation}\label{eqn:2m+1}
      \upvartheta(n)=  \upvartheta(2m+1)
      \leq\log\binom{2m+1}{m+1}+\upvartheta(m+1).
    \end{equation}
    We have also
    \begin{equation*}
      \binom{2m+1}{m+1}=\binom{2m+1}{m}, 
    \end{equation*}
    and these are distinct terms in the expansion of $(1+1)^{2m+1}$,
    by Theorem \eqref{thm:binom}; so
    \begin{align*}
      2\binom{2m+1}{m+1}&\leq2^{2m+1},&
      \binom{2m+1}{m+1}&\leq2^{2m}.
    \end{align*}
    Plugging this, and the strong inductive hypothesis
    \begin{equation*}
      \upvartheta(m+1)<2(m+1)\log2,
    \end{equation*}
    into \eqref{eqn:2m+1}, we obtain
    \begin{equation*}
      \upvartheta(n)
      \leq2(2m+1)\log2=\log2n\log2.\qedhere
    \end{equation*}
  \end{asparaenum}

\end{proof}

We need one more lemma for Bertrand's Postulate.

\begin{theorem}\label{thm:Legendre}
For all positive integers $n$,
\begin{equation}\label{eqn:Legendre}
\log(n!)=\sum_{p\leq n}\log p\cdot\sum_{j=1}^{\infty}\Bigl[\frac n{p^j}\Bigr].
\end{equation}
\end{theorem}

\begin{proof}
  A proof will just express what one sees in an example:
  \begin{multline*}
 10!
 =1\cdot2\cdot3\cdot2^2\cdot5
 \cdot(2\cdot3)\cdot7\cdot2^3\cdot3^2\cdot(2\cdot5)\\
 =2^{5+2+1}\cdot3^{3+1}\cdot5^2\cdot7\\
 =2^{[10/2]+[10/4]+[10/8]}\cdot3^{[10/3]+[10/9]}\cdot5^{[10/5]}\cdot7^{[10/7]}\\
 =2^{\sum_{j=1}^{\infty}[10/2^j]}
 +3^{\sum_{j=1}^{\infty}[10/3^j]}
 +5^{\sum_{j=1}^{\infty}[10/5^j]}
 +7^{\sum_{j=1}^{\infty}[10/5^j]},
  \end{multline*}
  while $\{2,3,5,7\}=\{p\colon p\leq10\}$.
\end{proof}

One may observe
$10!=2^{2^3}\cdot3^{2^2}\cdot5^{2^1}\cdot7^{2^0}$,
but the sequence of exponents is entirely coincidental.

The sum in \eqref{eqn:Legendre}
has a term $\log p\cdot[n/p^j]$ precisely for those powers
$p^j$ that are no greater than $n$.
Thus we might write
\begin{equation*}
  \log(n!)=\sum_{p^j\leq n}\log p\cdot\Bigl[\frac n{p^j}\Bigr]
  =\sum_{k\leq n}\Lambda(k)\cdot\Bigl[\frac nk\Bigr],
\end{equation*}
where $\Lambda$ is the \textbf{von Mangoldt function,} given by
\begin{equation*}
\Lambda(n)=
    \begin{cases}
      \log p,&\text{ if $n=p^j$ for some positive $j$};\\
     0,&\text{ otherwise.}
    \end{cases}
\end{equation*}
We shall use this function in
\eqref{eqn:psi} on page \pageref{eqn:psi}.
Meanwhile, here is a puzzle; what is
  $\sum_{d\divides n}\Lambda(d)$?
For example,
\begin{multline*}
  \sum_{d\divides12}\Lambda(d)
  =\Lambda(1)+\Lambda(2)+\Lambda(3)+\Lambda(4)+\Lambda(6)+\Lambda(12)\\
  =0+\log2+\log3+\log2+0+0\\
  =\log(2\cdot3\cdot2)=\log(12).
\end{multline*}
This is not an accident: always
\begin{equation*}
  \sum_{d\divides n}\Lambda(d)=\log n.
\end{equation*}
We can understand this as a form of the Fundamental Theorem of Arithmetic.

\chapter{Wednesday}

\begin{theorem}[Bertrand's Postulate]\label{thm:B}%
\index{Bertrand's Postulate}
For every positive integer $n$ there is a prime $p$ such that
\begin{equation}\label{eqn:n<p<=2n}
n<p\leq 2n.
\end{equation}
\end{theorem}

\begin{proof}
  No prime factor of $\binom{2n}n$ exceeds $2n$.
  Thus it is enough to show that
  $\binom{2n}n$ has a prime factor exceeding $n$.
There are exponents $n(p)$ such that
\begin{equation*}
\binom{2n}n=\prod_{p\leq2n}p^{n(p)}.
\end{equation*}
Thus
\begin{gather}\label{eqn:n(p)=1}
  n(p)\geq1\iff p\biggm|\binom{2n}n,\\\label{eqn:2nn}
\log\binom{2n}n=\sum_{p\leq2n}\log p\cdot n(p).
\end{gather}
Since also, by \eqref{eqn:binom-coeff},
\begin{equation*}
  \log\binom{2n}n=\log\bigl((2n)!\bigr)-2\log(n!),
\end{equation*}
we have,
by Theorem \ref{thm:Legendre},
\begin{equation}\label{eqn:n(p)}
  n(p)=\sum_{j=1}^{\infty}
  \Bigl(\Bigl[\frac{2n}{p^j}\Bigr]-2\Bigl[\frac n{p^j}\Bigr]\Bigr).
\end{equation}
Here, in each case,
\begin{equation}\label{eqn:0<<1}
0\leq  \Bigl(\Bigl[\frac{2n}{p^j}\Bigr]-2\Bigl[\frac n{p^j}\Bigr]\Bigr)\leq1,
\end{equation}
for,
\begin{gather*}
  [x]=m\iff m\leq x<m+1\iff
  2m\leq2x<2m+2,\\
  2m\leq2x<2m+1
  \implies[2x]=2m,\\
    2m+1\leq2x<2m+2
  \implies[2x]=2m+1.
\end{gather*}
Moreover,
\begin{equation}\label{eqn:k>2n}
  k>2n\implies
  \left[\frac{2n}k\right]-2\left[\frac nk\right]=0,
\end{equation}
while
\begin{equation}\label{eqn:p^j}
  p^j>2n\iff j\log p>\log(2n).
\end{equation}
Plugging \eqref{eqn:0<<1}, \eqref{eqn:k>2n},
and \eqref{eqn:p^j} into \eqref{eqn:n(p)} gives
\begin{equation}\label{eqn:n(p)<}
  n(p)\leq\sum_{j\leq\log(2n)/\log p}1\leq\frac{\log(2n)}{\log p}.
\end{equation}
Therefore
\begin{equation}\label{eqn:sqrt(2n)}
  2\leq n(p)\implies2\log p\leq\log(2n)\implies p\leq\sqrt{2n}.
\end{equation}
From \eqref{eqn:2nn} and \eqref{eqn:n(p)=1},
\begin{multline}\label{eqn:1-2}
  \log\binom{2n}n
=\sum_{n(p)\geq1}\log p\cdot n(p)\\
=\sum_{n(p)=1}\log p+\sum_{n(p)\geq2}\log p\cdot n(p).
\end{multline}
We bound the two terms.  Again by \eqref{eqn:n(p)=1},
\begin{equation*}
  \sum_{n(p)=1}\log p\leq\sum_{p\divides\binom{2n}n}\log p,
\end{equation*}
while by \eqref{eqn:n(p)<} and \eqref{eqn:sqrt(2n)},
\begin{equation*}
  \sum_{n(p)\geq2}\log p\cdot n(p)
\leq\sum_{n(p)\geq2}\log(2n)
\leq\log(2n)\sqrt{2n}.
\end{equation*}
Thus \eqref{eqn:1-2} yields
\begin{equation}\label{eqn:log-binom}
\log\binom{2n}n
\leq\sum_{p\divides\binom{2n}n}\log p+\log(2n)\sqrt{2n}.
\end{equation}
Thus we have an upper bound on $\log\binom{2n}n$.
We introduce a lower bound by noting that,
since
\begin{equation*}
2^{2n}=\sum_{j=0}^{2n}\binom{2n}j=2+\sum_{j=1}^{2n-1}\binom{2n}j,
\end{equation*}
where there are $2n$ terms,
the greatest being $\binom{2n}n$,
\begin{gather}\notag
  2^{2n}\leq2n\binom{2n}n,\\\label{eqn:2nlog2}
  2n\log 2-\log(2n)\leq\log\binom{2n}n.
\end{gather}
Combining \eqref{eqn:log-binom} and \eqref{eqn:2nlog2} yields
\begin{equation}\label{eqn:both}
  2n\log 2
  \leq\sum_{p\divides\binom{2n}n}\log p+\log(2n)(1+\sqrt{2n}).
\end{equation}
The left-hand side dominates the second term on the right,
that is,
\begin{equation*}
  \lim_{x\to\infty}\frac{\log(2n)(1+\sqrt{2n})}{2n\log 2}=0,
\end{equation*}
since generally
\begin{equation*}
  \lim_{x\to\infty}\frac{\log x}{x^s}=0
\end{equation*}
when $s>0$, by L'H\^opital's Rule.
We may write this theorem as
\begin{equation}\label{eqn:log-prec}
  s>0\implies\log x\prec x^s.
\end{equation}
We shall show that $\binom{2n}n$ must have prime factors exceeding $n$,
to compensate.
By Theorem \ref{thm:2xlog2},
\begin{equation}\label{eqn:bigm}
  \sum_{p\bigm|\binom{2n}n\And p\leq n}\log p
  \leq\sum_{p\leq n}\log p=\upvartheta(n)\leq2n\log 2.
\end{equation}
Since this is just the left-hand side of \eqref{eqn:both},
there is no problem so far.
However,
\begin{multline*}
  \frac{2n}3<p\leq n
  \implies 2p\leq 2n<3p\\
  \implies\Bigl[\frac{2n}p\Bigr]
  -2\Bigl[\frac np\Bigr]
  =2-2\cdot1=0,
\end{multline*}
and also
  \begin{multline*}
    \frac{2n}3<p\And n\geq5
    \implies p^2>\frac{4n^2}9=\frac{2n}9\cdot2n>2n\\
    \implies\Bigl[\frac{2n}{p^2}\Bigr]=0,
  \end{multline*}
and therefore
  \begin{equation*}
    \frac{2n}3<p\leq n\And n\geq5
    \implies n(p)=0.
  \end{equation*}
Thus, assuming $n\geq5$, in the manner of \eqref{eqn:bigm} we have
\begin{equation*}
    \sum_{p\bigm|\binom{2n}n\And p\leq n}\log p
    \leq\sum_{p\leq2n/3}\log p=\upvartheta\left(\frac{2n}3\right)
    \leq\frac{4n}3\log 2.
\end{equation*}
Combining with \eqref{eqn:both} gives
\begin{equation}\label{eqn:geq}
  \sum_{p\bigm|\binom{2n}n\And n<p}\log p\geq
  \frac{2n}3\log2-\bigl(1+\sqrt{2n}\bigr)\log(2n).
\end{equation}
We already know that the right-hand side is positive when $n$ is large enough.
It is enough to show $631$ is large enough,
because of the sequence \eqref{eqn:631}.
Since $631>512=2^9$, let us assume now
\begin{align*}
  n&>2^9,&2n&>2^{10}=1024,&\sqrt{2n}&>2^5=32.
\end{align*}
Multiplying the right-hand side of \eqref{eqn:geq}
by what will turn out to be a convenient factor,
we compute
\begin{multline*}
  \frac3{\sqrt{2n}\log\sqrt{2n}\log2}
  \left(\frac{2n}3\log2-\bigl(1+\sqrt{2n}\bigr)\log(2n)\right)\\
    =\frac{\sqrt{2n}}{\log\sqrt{2n}}
    -\frac{2\cdot3}{\log2}\left(\frac1{\sqrt{2n}}+1\right),
\end{multline*}
while
\begin{multline*}
    \frac{2\cdot3}{\log2}\left(\frac1{32}+1\right)
    =\frac{2\cdot3\cdot33}{2^5\log2}
    \leq\frac{2\cdot100\cdot2^5}{2^{10}\log2}\\
    \leq\frac{2\cdot100\cdot2^5}{1000\log2}
    =\frac{2^5}{5\log2}
    =\frac{2^5}{\log(2^5)}.
\end{multline*}
Now the right-hand side of \eqref{eqn:geq} is positive,
because $x/\log x$ is an increasing function of $x$ on $[\me,\infty)$,
  since its derivative is $(\log x-1)/(\log x)^2$.
\end{proof}

\chapter{Thursday}


The \textbf{Riemann zeta function}
is given by
\begin{equation}\label{eqn:zeta}
\upzeta(s)=\sum_{n\in\N}\frac1{n^s},
\end{equation}
where (in Riemann's own notation)
\begin{equation*}
  s=\sigma+\mi t
\end{equation*}
and
\begin{equation*}
  \sigma>1.
\end{equation*}
The convergence of the sum is absolute,
by the Integral Test,
since
\begin{equation*}
  \abs{n^s}
  =n^{\sigma}\abs{n^{\mi t}}
  =n^{\sigma}\abs{\me^{\mi t\log n}}=n^{\sigma},
\end{equation*}
and
\begin{equation}\label{eqn:II}
  \int_1^{\infty}\frac{\dee x}{x^{\sigma}}
  =\frac1{1-\sigma}\cdot\frac1{x^{\sigma-1}}\Bigm|^{\infty}_1=\frac1{\sigma-1}.
\end{equation}

\begin{theorem}\label{thm:I}
  When $\sigma>1$, then
\begin{equation}\label{eqn:zeta-prod}
\upzeta(s)=\prod_p\frac1{1-p^{-s}}.
\end{equation}
\end{theorem}

\begin{proof}
  By definition,
  \begin{equation*}
    \upzeta(s)
    =\frac1{1^s}+\frac1{2^s}+\frac1{3^s}+\frac1{2^s\cdot2^s}+\frac1{5^s}
    +\frac1{2^s\cdot3^s}+\dotsb
  \end{equation*}
  while, by the rule
  \begin{equation}\label{eqn:geo}
\frac1{1-r}=\sum_{k=0}^{\infty}r^k
  \end{equation}
  for geometric series,
  \begin{multline*}
    \prod_p\frac1{1-p^{-s}}
    =\left(1+\frac1{2^s}+\frac1{2^{2s}}+\dotsb\right)\\
    \cdot\left(1+\frac1{3^s}+\frac1{3^{2s}}+\dotsb\right)
    \cdot\left(1+\frac1{5^s}+\frac1{5^{2s}}+\dotsb\right)\dotsm
  \end{multline*}
  By the Fundamental Theorem of Arithmetic,
  the two sides of \eqref{eqn:zeta-prod} match up.
  (A proper proof would use the absolute convergence
  of the sum expansion of $\zeta(s)$.)
\end{proof}

In complex analysis, a \textbf{holomorphic function}
is a differentiable function, according to the rule from real analysis,
with complex numbers used for real numbers.
We shall say more later.  Meanwhile:

\begin{theorem}\label{thm:II}
  The function
%  $\upzeta$ has a pole of order $1$ at $1$, but the function
  \begin{equation*}
    %s\mapsto
    \upzeta(s)-\frac1{s-1}
  \end{equation*}
extends holomorphically to $\sigma>0$.
%(and thus the residue of $\upzeta$ at $1$ is $1$).
\end{theorem}

\begin{proof}
  When $\sigma>1$, we have, by \eqref{eqn:II},
  \begin{equation*}
    \upzeta(s)-\frac1{s-1}
    =\sum_{n=1}^{\infty}\frac1{n^s}-\int_1^{\infty}\frac{\dee x}{x^s}
    =\sum_{n=1}^{\infty}\int_n^{n+1}\left(\frac1{n^s}-\frac1{x^s}\right)\dee x,
  \end{equation*}
  and the last series converges absolutely when $\sigma>0$,
%  (and thus can be used to define $\upzeta(s)-(s-1)\inv$ then),
  since
  \begin{equation*}
    \frac1{n^s}-\frac1{x^s}=s\int_n^x\frac{\dee u}{u^{s+1}},
  \end{equation*}
  and this, on $[n,n+1]$, is bounded absolutely by
    $\abs s/n^{\sigma+1}$.
\end{proof}

With more complex analysis we shall show
\begin{equation*}
  x\sim\upvartheta(x).
\end{equation*}
Meanwhile,
we prove Chebyshev's Theorem
(as stated
\cite[Thm 7, p.\ 9]{MR568909}
and proved \cite[\S\S22.1--4, p.\ 340--6]{MR568909}
by Hardy and Wright),
and from this derive the corollary
\begin{equation*}
  \upvartheta(x)\sim\uppi(x)\log x.
\end{equation*}
Landau also proves the theorem
\cite[Thm 112, pp.\ 88--91]{MR0092794}.

\begin{theorem}[Chebyshev]\label{thm:C}
For some positive $A$ and $B$,
  for large $x$,
  \begin{equation*}
    Ax\leq\uppi(x)\log x\leq Bx;
  \end{equation*}
that is,
\begin{equation*}
\uppi(x)\asymp\frac x{\log x}.
\end{equation*}
\end{theorem}

\begin{proof}[Proof for the first inequality.]
  Since
\begin{equation}\label{eqn:theta>comp}
\upvartheta(x)=\sum_{p\leq x}\log p\leq\sum_{p\leq x}\log x=\uppi(x)\log x,
\end{equation}
it is enough to bound $\upvartheta(x)$ below by a positive multiple of $x$.
To do so, we define
\begin{equation*}
  \uppsi(x)=\sum_{m=1}^{\infty}\upvartheta(x^{1/m}).  
\end{equation*}
Since
\begin{gather*}
  \upvartheta(y)>0\iff y\geq2,\\
  x^{1/m}\geq2\iff\frac1m\log x\geq\log2\iff m\leq\frac{\log x}{\log 2},
\end{gather*}
we have
\begin{equation*}
  \uppsi(x)
  =\sum_{m=1}^{[\log x/\log 2]}\upvartheta(x^{1/m})
  =\upvartheta(x)
  +\sum_{m=2}^{[\log x/\log 2]}\upvartheta(x^{1/m}).
\end{equation*}
Also
\begin{equation*}
  m\geq2\implies\upvartheta(x^{1/m})
  \leq\upvartheta(\surd x)
  \leq\surd x\log\surd x
  \leq\surd x\log x,
\end{equation*}
so that
\begin{equation*}
\sum_{m=2}^{[\log x/\log 2]}\upvartheta(x^{1/m})
\leq\surd x\log x\cdot\frac{\log x}{\log2}\prec x
\end{equation*}
by \eqref{eqn:log-prec}.
Thus
\begin{equation*}
    \uppsi(x)-\upvartheta(x)\prec x.
\end{equation*}
It is now enough to bound $\uppsi(x)$ below by a positive multiple of $x$;
for if $Ax\leq\uppsi(x)$,
then for $x$ large enough,
\begin{align*}
\uppsi(x)-\upvartheta(x)&\leq\frac12Ax,&
\frac12 Ax\leq  \upvartheta(x).
\end{align*}
Towards bounding $\uppsi(x)$, we observe
\begin{multline*}
  \uppsi(x)
  =\sum_{m=1}^{\infty}\sum_{p\leq x^{1/m}}\log p\\
  =\sum_{m=1}^{\infty}\sum_{p^m\leq x}\log p
  =\sum_{p\leq x}\log p\cdot\left[\frac{\log x}{\log p}\right].
\end{multline*}
From our proof of Bertrand's Postulate (Theorem \ref{thm:B}),
specifically \eqref{eqn:2nn} and \eqref{eqn:n(p)<},
\begin{equation*}
  \log\binom{2n}n
  =\sum_{p\leq2n}\log p\cdot n(p)
  \leq\sum_{p\leq2n}\log p\cdot\left[\frac{\log(2n)}{\log p}\right].
\end{equation*}
Thus
\begin{equation*}
\log\binom{2n}n\leq\uppsi(2n).
\end{equation*}
Moreover,
\begin{align*}
  2^n&=\prod_{j=1}^n2\leq\prod_{j=1}^n\frac{n+j}j=\binom{2n}n,&
  n\log2&\leq\log\binom{2n}n.
\end{align*}
Suppose finally $n=[x/2]$, that is,
\begin{equation*}
  n\leq\frac x2<n+1.
\end{equation*}
If also $x\geq6$, so that $x/6\geq1$, then
\begin{align*}
  \frac x3=\frac x2-\frac x6&<n,&2n&\leq x,
\end{align*}
so that
\begin{equation*}
\frac{\log2}3\cdot x\leq n\log2\leq\uppsi(2n)\leq\uppsi(x).\qedhere
\end{equation*}
\end{proof}

\chapter{Friday}

Letting $s=\sigma+\mi t$ in $\C$,
we have
\begin{compactitem}
  \item
    defined $\upzeta(s)=\sum_{n=1}^{\infty}1/n^2$ when $\sigma>1$;
  \item
    shown $\upzeta(s)=\prod_p1/(1-p^{-s})$;
  \item
    proved that some \emph{holomorphic} function on $\sigma>0$
    agrees with $\zeta(s)-1/(s-1)$ on $\sigma>1$;
  \item
    proved that, for some positive $A$, for large real $x$,
    $Ax\leq\upvartheta(x)\leq\uppi(x)\log x$.
\end{compactitem}
In our remaining time,
we are going to show that:
\begin{compactitem}
\item
  for some $B$, for large $x$, $\uppi(x)\log x\leq Bx$;
\item
  $\uppi(x)\log x\sim\upvartheta(x)$;
\item
  $\upzeta(s)\neq0$ when $\sigma\geq1$;
\item
  some holomorphic function on $\sigma\geq1$
  agrees with $\Phi(s)-1/(s-1)$ on $\sigma>1$,
  where $\Phi(s)=\sum_p\log p/p^s$;
\item
    Theorem \ref{thm:anal}:
  when $f$ is bounded on $[0,\infty)$
    and integrable on every bounded interval,
    and a holomorphic function $g(s)$ on $\sigma\geq0$
    agrees with $\int_0^{\infty}f(x)\me^{-sx}\dee x$ on $\sigma>0$,
    then $g(0)=\int_0^{\infty}f(x)\dee x$.
  \item
    $\int_1^{\infty}(\upvartheta(x)-x)\dee x/x^2$ converges.
  \item
    $\upvartheta(x)\sim x$.
\end{compactitem}

  \begin{proof}[Proof for the second inequality.]
  We bound $\uppi(x)\log x$ above by a multiple of $x$.
  From Theorem \ref{thm:2xlog2},
  we have such an upper bound, namely $2x\log2$, on $\upvartheta(x)$.
  Moreover,
  \begin{multline}\label{eqn:theta>}
    \upvartheta(x)
    =\sum_{p\leq x}\log p
	\geq\sum_{x\geq p>\surd x}\log\surd p
	\geq\sum_{x\geq p>\surd x}\log\surd x\\
	=\bigl(\uppi(x)-\uppi(\surd x)\bigr)\log\surd x.
  \end{multline}
  Since
  \begin{align*}
    \uppi(\surd x)\leq\surd x&=\frac x{\surd x}
    \leq\frac x{\log x},&
    \log\surd x&=\frac12\log x,
  \end{align*}
  we obtain
  \begin{gather}\label{eqn:theta>'}
    	\upvartheta(x)
        \geq\left(\uppi(x)-\frac x{\log x}\right)\frac{\log x}2,\\\notag
        %\label{eqn:2theta}
        2\upvartheta(x)+x\geq\uppi(x)\log x,
  \end{gather}
and this is enough.
\end{proof}

We can now obtain the following as a corollary.

\begin{theorem}\label{thm:theta-sim}
  \begin{equation}\label{eqn:theta-sim}
    \upvartheta(x)\sim\uppi(x)\log x.
  \end{equation}
  \end{theorem}

\begin{proof}
  As a variant of \eqref{eqn:theta>} and \eqref{eqn:theta>'},
  if $0<\epsilon<1$, then
  \begin{gather*}
      \upvartheta(x)\geq\sum_{x^{1-\epsilon}<p\leq x}\log(x^{1-\epsilon})
      \geq(\uppi(x)-x^{1-\epsilon})\log x\cdot(1-\epsilon),\\
      \upvartheta(x)+
      x^{1-\epsilon}\log x\cdot(1-\epsilon)
      \geq
      \uppi(x)\log x\cdot(1-\epsilon),\\      
      \frac{\upvartheta(x)}{\uppi(x)\log x}
      +\frac x{\uppi(x)\log x}\cdot\frac{\log x}{x^{\epsilon}}\cdot(1-\epsilon)
      \geq1-\epsilon.
  \end{gather*}
  We can make the second term on the left as small as desired,
since $x/\uppi(x)\log x$ is bounded above by Theorem \ref{thm:C},
while $\log x\prec x^{\epsilon}$ by \eqref{eqn:log-prec}.
Thus when $x$ is large enough we have
    \begin{equation*}
      \frac{\upvartheta(x)}{\uppi(x)\log x}
       \geq1-2\epsilon.
    \end{equation*}
    For all small $\epsilon$, for large $x$, this is true.
    Since the left side is bounded above by $1$ by \eqref{eqn:theta>comp},
    we conclude
    \begin{equation*}
      \lim_{x\to\infty}\frac{\upvartheta(x)}{\uppi(x)\log x}=1.\qedhere
    \end{equation*}
\end{proof}

  We turn to holomorphic functions.
  A subset $\Omega$ of $\C$ is \textbf{open}
  if, for every element $a$ of $\Omega$,
  for some positive $\epsilon$,
  \begin{equation*}
    \{z\in\C\colon\abs{z-a}<\epsilon\}\included\Omega.
  \end{equation*}
  If $f\colon\Omega\to\C$ and $g\colon\Omega\to\C$ and,
  for every $a$ in $\Omega$,
  \begin{equation}\label{eqn:holom}
    \lim_{z\to a}\frac{f(z)-f(a)}{z-a}=g(a),
  \end{equation}
  then $g$ is the \textbf{complex derivative}---denoted by $f'$---of $f$,
  and $f$ itself is \textbf{holomorphic.}

  For example, complex conjugation $z\mapsto\conj z$
  is \emph{not} holomorphic, since
  \begin{equation*}
      \frac{\conj z-\conj a}{z-a}=\frac{\conj{z-a}}{z-a}
  =\frac{\conj{z-a}^{\,2}}{\abs{z-a}^2},
\end{equation*}
  and this is on the unit circle and can be anywhere on that circle.

  When we consider $\C$ as the real vector space $\R^2$,
  then complex conjugation is a linear transformation of this space,
  and then it is is own derivative at each point.
  Why then conjugation is not holomorphic
  is that it is not a linear transformation of $\C$ as a complex vector space.
  
In detail, we can rewrite \eqref{eqn:holom} as
\begin{equation*}
  \lim_{z\to a}\frac{f(z)-f(a)-f'(a)(z-a)}{z-a}=0.
\end{equation*}
Suppose merely
\begin{equation*}
  \lim_{z\to a}\frac{f(z)-f(a)-T(z-a)}{z-a}=0,
\end{equation*}
where $T$ is an $\R$-linear function, that is,
\begin{align*}
  T(z+w)&=T(z)+T(w),&T(uz)&=uT(z),
\end{align*}
where $u\in\R$.
Then $T$ is the \textbf{real derivative} of $f$ at $a$.
$T$ is $\C$-linear if and only if it is multiplication by a complex number,
which in this case would be $f'(a)$,
and $f$ would be holomorphic.

In any case, the partial derivatives of $f$ at $a$ are as follows,
where $h$ is a real number.
\begin{align*}
    \partial_xf(a)
    &=\lim_{h\to0}\frac{f(a+h)-f(a)}h,\\
    \partial_yf(a)
    &=\lim_{h\to0}\frac{f(a+\mi h)-f(a)}{h}
    =-\mi\lim_{h\to0}\frac{f(a+\mi h)-f(a)}{\mi h}.
\end{align*}
  If $f$ is holomorphic,
  we obtain the \textbf{Cauchy--Riemann Equation,}
  \begin{equation}\label{eqn:CR}
    \partial_xf(a)
    =-\mi\partial_yf(a).
  \end{equation}

\chapter{Saturday}

We know $\uppi(x)\log x\sim\upvartheta(x)$,
and $\upzeta(s)-1/(s-1)$ is defined holomorphically on $\sigma>0$,
where $s=\sigma+\mi t$.
It remains to prove the following.
\begin{compactenum}
\item
  When $\sigma\geq1$, then $\upzeta(s)\neq0$,
  and $\Phi(s)-1/(s-1)$ is holomorphic,
  where
  \begin{equation}\label{eqn:Phi}
    \Phi(s)=\sum_p\frac{\log p}{p^s}.
  \end{equation}
\item
  Theorem \ref{thm:anal}:
  When $f$ is bounded on $[0,\infty)$
    and integrable on every bounded interval,
    and a holomorphic function $g(s)$ on $\sigma\geq0$
    agrees with $\int_0^{\infty}f(x)\me^{-sx}\dee x$ on $\sigma>0$,
    then $g(0)=\int_0^{\infty}f(x)\dee x$;
  \item
    $\int_1^{\infty}(\upvartheta(x)-x)\dee x/x^2$ converges.
  \item
    If $\int_1^{\infty}(f(x)-x)\dee x/x^2$ converges,
    and $f$ is increasing, then $f(x)\sim x$.
\end{compactenum}
The last theorem is just calculus:


\begin{theorem}\label{thm:VI}
  If $f$ is an increasing function such that the integral
  \begin{equation*}
    \int_1^{\infty}\frac{f(t)-t}{t^2}\dee t
  \end{equation*}
  converges, then
\begin{equation*}
  f(x)\sim x.
\end{equation*}
\end{theorem}

\begin{proof}
  Let $f$ be an increasing function such that $f(x)\nsim x$.
  There are two ways this can happen.
  \begin{asparaenum}
    \item
    Suppose first for some $\lambda$, $\lambda>1$ and,
    for arbitrarily large $x$,
    \begin{equation*}
      f(x)\geq\lambda x.
    \end{equation*}
    For such $x$, since $f$ is increasing,
    \begin{equation*}
      \int_x^{\lambda x}\frac{f(t)-t}{t^2}\dee t
      \geq\int_x^{\lambda x}\frac{\lambda x-t}{t^2}\dee t=I
    \end{equation*}
    for some $I$.  Letting $t=xu$, so that $\dee t=x\dee u$, we have
    \begin{equation*}
      I
      =\int_1^{\lambda}\frac{\lambda x -ux}{u^2x^2}x\dee u
      =\int_1^{\lambda}\frac{\lambda -u}{u^2}\dee u>0.
    \end{equation*}
    However, if $\int_1^{\infty}g$ converges,
    then for large $x$,
    $\abs{\int_x^{\infty}g}<I/2$
    and
        $\abs{\int_{\lambda x}^{\infty}g}<I/2$,
    so
        $\abs{\int_x^{\lambda x}g}<I$.
  \item
    In the other case, for some $\lambda$, $0<\lambda<1$ and
    for arbitrarily large $x$,
    \begin{equation*}
      f(x)\leq\lambda x.
    \end{equation*}
    The argument is similar.\qedhere
  \end{asparaenum}
\end{proof}


\begin{theorem}\label{thm:IV}
The function
\begin{equation*}
  %s\mapsto
  \Phi(s)-\frac1{s-1},
\end{equation*}
where $\Phi$ is as in \eqref{eqn:Phi},
extends holomorphically to $\sigma\geq1$,
and $\upzeta$ is non-zero here.
\end{theorem}

\begin{proof}
  From \eqref{eqn:zeta-prod},
  namely $\upzeta(p)=\prod_p(1-p^{-s})\inv$,
  we know that $\upzeta$ is nonzero on $\sigma>1$.
  From
  \begin{equation*}
    \log\upzeta(s)=-\sum_p\log(1-p^{-s})=-\sum_p\log(1-\me^{-s\log p}),
  \end{equation*}
  taking the derivative,
  we compute
  \begin{equation*}
    -\frac{\upzeta'(s)}{\upzeta(s)}
    =\sum_p\frac{\log p\cdot p^{-s}}{1-p^{-s}}
    =\sum_p\frac{\log p}{p^s-1}.
  \end{equation*}
  Since
  \begin{equation*}
    \frac1{x-1}=\frac1x+\frac1{x(x-1)},
  \end{equation*}
  we have now
  \begin{multline}\label{eqn:zeta-Phi}
    -\frac{\upzeta'(s)}{\upzeta(s)}
    =\sum_p\left(\frac{\log p}{p^s}+\frac{\log p}{p^s(p^s-1)}\right)\\
    =\Phi(s)+\sum_p\frac{\log p}{p^s(p^s-1)}.
  \end{multline}
  The last series converges absolutely when $\sigma>1/2$,
  since for large $p$,
  \begin{equation*}
    \frac1{p^{2s}-p^s}<\frac2{p^{2s}}.
  \end{equation*}
  It remains to show $\upzeta(s)\neq0$ when $\sigma=1$.
  Then our claim will follow from complex analysis.
  Specifically, if $f$ is holomorphic,
  then, by Theorem \ref{thm:holo-ana} on page \pageref{thm:holo-ana},
  $f$ is \textbf{analytic,}\label{analytic}
  which means that, for every point $a$ of its domain,
  for some coefficients $a_n$,
  for $z$ near $a$,
  \begin{equation*}
    f(z)=a_0+a_1(z-a)+a_2(z-a)^2+\dotsb
    =\sum_{n=0}^{\infty}a_n(z-a)^n.
  \end{equation*}
  \begin{compactitem}
    \item
  If $a_0=\dots=a_{k-1}=0$,
  but $a_k\neq0$, then $f$ has a \textbf{zero of order $k$ at $a$.}
  \item
    If $a_0\neq0$, and $k>0$,
    then $f(z)/(z-a)^k$ has a \textbf{pole of order $k$ at $a$.}
  \end{compactitem}
  Suppose now
  \begin{equation*}
    g(z)=\sum_{n=k}^{\infty}b_n(z-a)^n=b_k(z-a)^k+\dotsb,
  \end{equation*}
  where $k$ may be negative.
  The \textbf{residue} of $g$ at $a$ is $b_{-1}$.
  Also
  \begin{gather*}
    g'(z)=kb_k(z-a)^{k-1}+\dotsb,\\
    \frac{g'(z)}{g(z)}=k(z-a)^{-1}+\dotsb.
  \end{gather*}
  If $k\neq0$,
  then $g'/g$ has a pole of order $1$ at $a$,
  and the residue $k$ of $g'/g$ at $a$ is the order of the zero at $a$,
  if there is one; otherwise $-k$ is the order of the pole at $a$.

  By Theorem \ref{thm:II}, since $1/(s-1)$ has a pole of order $1$ at $1$,
  so does $\upzeta(s)$.
  Therefore $\upzeta'/\upzeta$ has a pole of order $1$, and residue $1$, at $1$.
  By \eqref{eqn:zeta-Phi}, so has $\Phi$.
  Thus it remains to show $\upzeta(s)\neq0$ when $\sigma=1$.
  
  Suppose if possible $\upzeta$ has a zero of order $\mu$ at $1+\mi a$.
  Then $\mu$ is the residue of $\upzeta'/\upzeta$ at $1+\mi a$, so
  \begin{multline}\label{eqn:mu}
      \mu
    =\lim_{z\to1+\mi a}\frac{(z-1-\mi a)\upzeta'(z)}{\upzeta(z)}\\
=    \lim_{z\to0}
    \frac{z\upzeta'(1+\mi a+z)}{\upzeta(1+\mi a+z)}
    =-\lim_{z\to0}z\Phi(1+\mi a+z).
  \end{multline}
  Likewise
  \begin{equation}\label{eqn:Phi-1}
1=\lim_{z\to0}z\Phi(z),
  \end{equation}
    since $\Phi$ has a pole of order $1$, and residue $1$, at $1$.

    Either $\upzeta$ has a zero of some order $\nu$ at $1+2\mi a$,
    or else we let $\nu=0$.
  For small positive $\epsilon$, we compute
  \begin{multline}\label{eqn:Phi-pos}
    \sum_{j=-2}^2\binom4{2+j}\Phi(1+j\mi a+\epsilon)
    =\sum_{j=-2}^2\binom4{2+j}\sum_p\frac{\log p}{p^{1+\epsilon+j\mi a}}\\
    =\sum_p\frac{\log p}{p^{1+\epsilon}}\sum_{j=-2}^2\binom4{2+j}\frac1{p^{j\mi a}}
    =\sum_p\frac{\log p}{p^{1+\epsilon}}
    \left(\frac1{p^{\mi a/2}}+\frac1{p^{-\mi a/2}}\right)^4\\
    =\sum_p\frac{\log p}{p^{1+\epsilon}}
    \left(2\Re\Bigl(\frac1{p^{\mi a/2}}\Bigr)\right)^4
    \geq0.
  \end{multline}
  Here $\Re(z)=(z+\conj z)/2$, the real part of $z$.
  Since
  \begin{equation*}
    \conj{\Phi(s)}=\Phi(\conj s),
  \end{equation*}
  so that
  \begin{equation*}
    2\Re(\Phi(s))=\Phi(s)+\Phi(\conj s),
  \end{equation*}
  we have,
  \begin{multline*}
    \sum_{j=-2}^2\binom4{2+j}\Phi(1+j\mi a+\epsilon)\\
    =    2\Re(\Phi(1+2\mi a+\epsilon))
    +8\Re(\Phi(1+\mi a+\epsilon))\\
    +6\Re(\Phi(1+\epsilon)).
  \end{multline*}
  In the limit at $\epsilon$,
  the product of the sum here with $\epsilon$ is $-2\nu-8\mu+6$,
  by \eqref{eqn:mu},
  and the similar computation for $\nu$, and \eqref{eqn:Phi-1}.
  By \eqref{eqn:Phi-pos}, we have
  \begin{equation*}
    -2\nu-8\mu+6\geq0,
  \end{equation*}
  so $\mu$ cannot be positive.
\end{proof}

\appendix

\chapter{Analytic Functions}

From the definition on page \pageref{analytic},
analytic functions are holomorphic.
We shall prove the converse.

We are considering a holomorphic function $f$
on an open subset $\Omega$ of $\C$.
Supposing $\gamma\colon[a,b]\to\Omega$,
and making the analysis
\begin{equation}\label{eqn:gamma}
\gamma=\gamma_0+\mi\gamma_1,
\end{equation}
where $\gamma_e\colon[a,b]\to\R$,
we define
\begin{equation}\label{eqn:int-gamma}
\int_a^b\gamma=\int_a^b\gamma_0+\mi\int_a^b\gamma_1,
\end{equation}
provided the integrals on the right exist.
Suppose further that $\gamma$ is one-to-one and
\textbf{continuously differentiable,}
which means that each $\gamma_e$ has a continuous derivative and
\begin{equation*}
  \gamma'=\gamma_0{}'+\mi\gamma_1{}'.
\end{equation*}
Then $\gamma$ has the \textbf{initial point} $\gamma(a)$ 
and the \textbf{terminal point} $\gamma(b)$,
and $\gamma$ itself is an
\textbf{arc} or \textbf{path} or \textbf{line.}
We define the \textbf{line integral} of
$f$ along $\gamma$
using the substitution
\begin{align*}
  z&=\gamma(t),&\dee z&=\gamma'(t)\dee t,
\end{align*}
obtaining
\begin{equation*}
\int_{\gamma}f(z)\dee z=\int_a^bf(\gamma(t))\gamma'(t)\dee t,
\end{equation*}
or simply
\begin{equation}\label{eqn:int-f}
\int_{\gamma}f=\int_a^b(f\circ\gamma)\gamma'.
\end{equation}
  We say $\int_{\gamma}f$ is \textbf{path independent}
  if it depends only on $f$, $\gamma(a)$, and $\gamma(b)$.

\begin{theorem}\label{thm:path-ind}
  The line integral of a continuous derivative of a holomorphic function
  is path independent.
\end{theorem}

\begin{proof}
  If $f=F'$, then by the Chain Rule,
  \begin{equation*}
    (F\circ\gamma)'=(F'\circ\gamma)\gamma'=(f\circ\gamma)\gamma',
  \end{equation*}
  and so by \eqref{eqn:int-f} and the Fundamental Theorem of Calculus,
  \begin{equation*}
    \int_{\gamma}f=\int_a^b(F\circ\gamma)'=F(\gamma(b))-F(\gamma(a)).\qedhere
  \end{equation*}
\end{proof}

An arc whose initial and terminal points are the same
is a \textbf{closed curve.}
The line integrals of a function are path independent
if and only if the integrals around closed curves are path independent.
The latter case means those integrals are zero.

For example,
if $n\neq0$ and $f(z)=(z-a)^n/n$,
then $f$ is holomorphic on its domain,
which is $\C$ if $n>0$,
and $\{z\in\C\colon z\neq a\}$ if $n<0$.
Also
\begin{equation*}%\label{eqn:Dz(z-a)}
  f'(z)=(z-a)^{n-1},
\end{equation*}
so that $(z-a)^{n-1}$
is the derivative of a holomorphic function of $z$,
unless $n=0$.
Therefore,
letting $\oint$ denote an integral along a counterclockwise closed curve
in the domain of the integrand,
we have
\begin{equation*}
n\neq0\implies\oint(z-a)^{n-1}\dee z=0.
\end{equation*}
The case when $n=0$ is different, as follows.

\begin{theorem}\label{thm:2ip}
  If $\gamma$ describes a counterclockwise loop around $a$, then
  \begin{equation*}
    \int_{\gamma}\frac{\dee z}{z-a}=2\mi\uppi.
  \end{equation*}
\end{theorem}

\begin{proof}
  We may assume $a=0$.
  If $\delta$ is $t\mapsto\me^{\mi t}$ on $[0,2\uppi]$,
  we compute
  \begin{equation*}
    \int_{\delta}\frac{\dee z}z
    =\int_0^{2\uppi}\frac{\mi\me^{\mi t}\dee t}{e^{\mi t}}
    =\mi\int_0^{2\uppi}\dee t=2\mi\uppi.
  \end{equation*}
  The general case follows from Theorem \ref{thm:path-ind},
  since we can analyze $\delta-\gamma$ as a sum of closed curves,
  each surrounding a region where $1/z$ is
  the derivative of a holomorphic function
  (which we ambiguously call $\log z$).
  \end{proof}

In the following,
\eqref{eqn:CIF} is \textbf{Cauchy's Integral Formula.}

\begin{theorem}\label{thm:CIF}
  If $f$ is holomorphic
  on an open neighborhood of $a$,
  and $\gamma$ describes a counterclockwise loop,
  within that neighborhood,
  around $a$,
  then
  \begin{equation}\label{eqn:CIF}
    f(a)=\frac1{2\mi\uppi}\int_{\gamma}\frac{f(z)}{z-a}\dee z.
  \end{equation}
\end{theorem}

\begin{proof}
  Again we may assume $a=0$.  By Theorem \ref{thm:2ip},
  \begin{equation}\label{eqn:f(0)}
    f(0)=\frac1{2\mi\uppi}\int_{\gamma}\frac{f(0)}z\dee z.
  \end{equation}
  As in the proof of Theorem \ref{thm:2ip},
  we may adjust $\gamma$,
  now shrinking it to a circle of radius $\delta$ around $0$.
  Given a positive $\epsilon$,
  we may let $\delta$ be small enough that
  \begin{equation*}
    \abs{f(z)-f(0)}<\epsilon
  \end{equation*}
  on $\gamma$.
Using \eqref{eqn:f(0)}, we compute
  \begin{multline*}
    \abs{\frac1{2\mi\uppi}\int_{\gamma}\frac{f(z)}z\dee z-f(0)}
    =\abs{\frac1{2\mi\uppi}\int_{\gamma}\frac{f(z)-f(0)}z\dee z}\\
    =\frac1{2\uppi}
    \abs{\int_0^1\frac{f(\delta\me^{2\mi\uppi t})-f(0)}{\delta\me^{2\mi\uppi t}}
    2\mi\uppi\delta\me^{2\mi\uppi t}\dee t}\\
    \leq\int_0^1\abs{f(\delta\me^{2\mi\uppi t})-f(0)}\dee t
    <\epsilon.
  \end{multline*}
  This being so for all positive $\epsilon$,
  then claim follows.
\end{proof}

\begin{theorem}\label{thm:holo-ana}
  Holomorphic functions are analytic.
\end{theorem}

\begin{proof}
  Let $\gamma$ describe a circle
  in the domain of a holomorphic function $f$.
  We may assume the center of the circle is $0$.
  Let $w$ be a point inside the circle.
  By Theorem \ref{thm:CIF},
  % Cauchy's Integral Formula \eqref{eqn:CIF},
  and then the rule \eqref{eqn:geo} for geometric series,
  \begin{multline*}
    2\mi\uppi f(w)
    =\int_{\gamma}\frac{f(z)}{z-w}\dee z
    =\int_{\gamma}\frac{f(z)}{z(1-w/z)}\dee z\\
    =\int_{\gamma}\frac{f(z)}z\sum_{n\in\upomega}\left(\frac wz\right)^n\dee z
    =\int_{\gamma}\sum_{n\in\upomega}\frac{f(z)w^n}{z^{n+1}}\dee z.
  \end{multline*}
  Since $f(z)$ is bounded on $\gamma$
  (this being compact),
  the convergence of the series is absolute,
  so we can interchange the integration and summation:
  \begin{equation*}%\label{eqn:holo-ana}
    f(w)
    =\sum_{n\in\upomega}\frac1{2\mi\uppi}
    \left(\int_{\gamma}\frac{f(z)\dee z}{z^{n+1}}\right)w^n.\qedhere
  \end{equation*}
\end{proof}

\chapter{The Prime Number Theorem}\label{ch:PNT}

We shall prove the Prime Number Theorem
as Theorem \ref{thm:PNT} below.
This will use our earlier results,
along with Theorem \ref{thm:V},
which will be a consequence of the following ``analytic theorem.''

\begin{theorem}[Newman \protect{\cite{MR602825}}]%
  \label{thm:anal}\nocite{MR1476753}
  Any function $f$
  that is bounded and locally integrable on $[0,\infty)$
    is globally integrable,
    provided the function $g$ given on $\sigma>0$ by
    \begin{equation*}
      g(s)=\int_0^{\infty}f(t)\me^{-st}\dee t
    \end{equation*}
    extends holomorphically to $\sigma\geq0$.
    In this case, moreover,
    \begin{equation*}
      g(0)=\int_0^{\infty}f(t)\dee t.
    \end{equation*}
\end{theorem}

\begin{proof}
  Defining
  \begin{equation*}
    g_x(z)=\int_0^xf(t)\me^{-zt}\dee t,
  \end{equation*}
  we want to prove
  \begin{equation}\label{eqn:anal}
    g(0)=\lim_{x\to\infty}g_x(0).
  \end{equation}
  Given large positive $R$,
  we can find positive $\delta$ so that $g$ is holomorphic on the region
  $-\delta\leq\sigma\And\abs s\leq R$
  shown in Figure \ref{fig:anal}.
  \begin{figure}
    \centering
    \psset{unit=12mm}
    \begin{pspicture}(-2,-2.5)(2,2.5)
      %\psgrid
      \psarc(0,0)2{-120}{120}
      \psline(! -1 3 sqrt)(! -1 3 sqrt neg)
      \psarc[linestyle=dotted](0,0)2{120}{240}
      \psline{->}(-2.5,0)(2.5,0)
      \psline{->}(0,-2.5)(0,2.5)
      \uput[ur](0,2){$\mi R$}
      \uput[ur](2,0){$R$}
      \uput[dr](0,-2){$-\mi R$}
      \uput[ul](-1,0){$-\delta$}
    \end{pspicture}
    \caption{A contour for integration}
    \label{fig:anal}
  \end{figure}
  Let $\gamma$ be a counterclockwise path around this region.
  By Cauchy's Integral Formula,
  \begin{equation}\label{eqn:CZ}
    g(0)-g_x(0)
    =\frac1{2\mi\uppi}\int_{\gamma}\bigl(g(z)-g_x(z)\bigr)\frac{\dee z}z.
  \end{equation}
  Now let
  \begin{equation*}
    h_x(s)=\me^{sx}\left(1+\frac{s^2}{R^2}\right),
  \end{equation*}
  so $h_x$ is holomorphic on $\C$.
  The innovation of Newman
  is to multiply $g(z)-g_x(z)$ by $h_x(z)$, so that, since $h_x(0)=1$,
  \eqref{eqn:CZ} becomes
  \begin{equation*}%\label{eqn:CZ}
    g(0)-g_x(0)
    =\frac1{2\mi\uppi}\int_{\gamma}\bigl(g(z)-g_x(z)\bigr)\frac{h_x(z)}z\dee z.
  \end{equation*}
  We shall bound the integral.
We have
  \begin{equation*}
    \abs{\frac{h_x(s)}s}
    =\frac{\me^{\sigma x}}R\abs{\frac Rs+\frac sR},
  \end{equation*}
  and so
  \begin{equation}\label{eqn:h-est}
    \abs s
    =R\implies\abs{\frac{h_x(s)}s}
    \leq\frac{2\me^{\sigma x}\abs{\sigma}}{R^2}.
  \end{equation}
  Since $f$ is assumed to be bounded, we may let
  \begin{equation*}
    B=\sup_{0\leq t}\abs{f(t)},
  \end{equation*}
  so that
  \begin{multline}\label{eqn:Re(z)>0}
    \sigma>0\implies\abs{g(s)-g_x(s)}
    =\abs{\int_x^{\infty}f(t)\me^{-st}\dee t}\\
    \leq B\int_x^{\infty}\me^{-\sigma t}\dee t
  =\frac B{\me^{\sigma x}\sigma}.
  \end{multline}
Combining the two estimates \eqref{eqn:h-est} and \eqref{eqn:Re(z)>0},
letting $\gamma_+$ be the restriction of $\gamma$
so that the range is in $\sigma>0$,
and thus the length of $\gamma_+$ is $\uppi R$,
we have
  \begin{multline}\label{eqn:gamma+}
    \abs{\int_{\gamma_+}\bigl(g(z)-g_x(z)\bigr)\frac{h_x(z)}z\dee z}\\
    \leq\uppi R
    \cdot\frac B{\me^{\sigma x}\sigma}
    \cdot\frac{2\me^{\sigma x}\sigma}{R^2}
    % =\uppi R\cdot\frac2{R^2}\cdot B
    =\frac{2\uppi B}R.
  \end{multline}
%(In what would seem to be a misprint, Zagier has $B/R$ here.)
Letting $\gamma_-$ be the other part of $\gamma$, we have
\begin{multline}\label{eqn:gamma-}
  \abs{\int_{\gamma_-}\bigl(g(z)-g_x(z)\bigr)\frac{h_x(z)}z\dee z}\\
  \leq\abs{\int_{\gamma_-}g(z)\frac{h_x(z)}z\dee z}
  +\abs{\int_{\gamma_-}g_x(z)\frac{h_x(z)}z\dee z}.
\end{multline}
For the last integral, since $g_x$ is entire,
we can replace $\gamma_-$ with $\gamma_-{}'$
having the same endpoints,
other points having negative real part and absolute value $R$.
Since, as in \eqref{eqn:Re(z)>0},
  \begin{multline*}
    \sigma<0\implies\abs{g_x(s)}
    =\abs{\int_0^xf(t)\me^{-st}\dee t}\\
    \leq B\int_{-\infty}^x\me^{-\sigma t}\dee t
  =\frac B{\me^{\sigma x}\abs{\sigma}},
  \end{multline*}
  combining with \eqref{eqn:h-est} gives,
  as in \eqref{eqn:gamma+},
  \begin{multline*}
    \abs{\int_{\gamma_-}g_x(z)\frac{h_x(z)}z\dee z}
    =\abs{\int_{\gamma_-{}'}g_x(z)\frac{h_x(z)}z\dee z}\\
    \leq\uppi R
    \cdot\frac B{\me^{\sigma x}\abs{\sigma}}
    \cdot\frac{2\me^{\sigma x}\abs{\sigma}}{R^2}
    =\frac{2\uppi B}R.
  \end{multline*}
%  (this is the value that Zagier gives).
  Thus we have a bound of $4\uppi B/R$ on everything so far,
  and we can make this bound as small as we like,
  by letting $R$ grow large.
  One integral remains to consider from \eqref{eqn:gamma-}.
  We have
  \begin{equation*}%\label{eqn:gamma-}
    \int_{\gamma_-}g(z)\frac{h_x(z)}z\dee z
    =\int_{\gamma_-}\me^{zx}g(z)\left(1+\frac{z^2}{R^2}\right)\frac{\dee z}z.
  \end{equation*}
  Here $x$ occurs only in the factor $\me^{zx}$.
  For some large $N$,
  we analyze $\gamma_-$ into components $\gamma_N$
  and $\gamma_N'$,
  according to whether the real part of a point
  is greater than (that is, to the right of) $-\delta/N$
  or not.
  First,
  \begin{equation*}
    \abs{\int_{\gamma_N}\me^{zx}g(z)\left(1+\frac{z^2}{R^2}\right)\frac{\dee z}z}
    \leq\abs{\int_{\gamma_N}g(z)\left(1+\frac{z^2}{R^2}\right)\frac{\dee z}z}.
  \end{equation*}
  We can make this bound, which is independent of $x$,
  as small as we like,
  by making $N$ large enough.
  Moreover,
  \begin{multline*}
    \abs{\int_{\gamma_N'}
      \me^{zx}g(z)\left(1+\frac{z^2}{R^2}\right)\frac{\dee z}z}\\
\leq\me^{-\delta x/N}    \abs{\int_{\gamma_N'}
      g(z)\left(1+\frac{z^2}{R^2}\right)\frac{\dee z}z},
  \end{multline*}
  and we can make \emph{this} as small as we like,
  given $N$,
  by making $x$ large enough.
  Thus for all large $R$, for all positive $\epsilon$,
  for sufficiently large $x$,
  \begin{equation*}
    \abs{g(0)-g_x(0)}\leq\frac{4\uppi B}R+\epsilon.
  \end{equation*}
  This implies \eqref{eqn:anal}.
\end{proof}

We immediately apply Theorem \ref{thm:anal}.

\begin{theorem}\label{thm:V}
  The integral
\begin{equation*}
  \int_1^{\infty}\frac{\upvartheta(x)-x}{x^2}\dee x
\end{equation*}
converges.
\end{theorem}

\begin{proof}
  As in the proof of Theorem \ref{thm:log-log},
  we consider the primes as forming the increasing sequence
  $(p_n\colon n\in\upomega)$.  Now
  \begin{align*}
    \log p_0&=\upvartheta(p_0),&
    \log p_{n+1}&=\upvartheta(p_{n+1})-\upvartheta(p_n),
  \end{align*}
so that, when $\sigma>1$,
  \begin{multline*}
    \Phi(s)
    =\sum_{n\in\upomega}\frac{\log p_n}{p_n{}^s}
    =\frac{\upvartheta(p_0)}{p_0{}^s}+
    \sum_{n\in\upomega}\frac{-\upvartheta(p_n)+\upvartheta(p_{n+1})}{p_{n+1}{}^s}\\
    =\sum_{n\in\upomega}\upvartheta(p_n)\left(\frac1{p_n{}^s}
    -\frac1{p_{n+1}{}^s}\right)
    =\sum_{n\in\upomega}\upvartheta(p_n)\int_{p_n}^{p_{n+1}}\frac{s\dee x}{x^{s+1}}\\
    =s\sum_{n\in\upomega}\int_{p_n}^{p_{n+1}}\frac{\upvartheta(x)}{x^{s+1}}\dee x
    =s\int_1^{\infty}\frac{\upvartheta(x)}{x^{s+1}}\dee x,
  \end{multline*}
    and therefore
  \begin{equation*}
    \frac{\Phi(s+1)}{s+1}-\frac1s
    =    \int_1^{\infty}\frac{\upvartheta(x)}{x^{s+2}}\dee x
    -\int_1^{\infty}\frac{\dee x}{x^{s+1}}
    =\int_1^{\infty}\frac{\upvartheta(x)-x}{x^{s+2}}\dee x.
  \end{equation*}
  By Theorem \ref{thm:IV},
  the left-hand side extends holomorphically to $\sigma\geq0$.
  We want to show that the equation still holds when $s=0$.
  To apply Theorem \ref{thm:anal},
  we use the substitution
  \begin{align*}%\label{eqn:u-sub}
    x&=\me^t,&\dee x&=\me^t\dee t,
  \end{align*}
  obtaining
  \begin{equation*}
    \int_1^{\infty}\frac{\upvartheta(x)-x}{x^{s+2}}\dee x
=\int_0^{\infty}\me^{-st}
    \left(\frac{\upvartheta(\me^t)}{\me^t}-1\right)\dee t.    
  \end{equation*}
  Since $\upvartheta(\me^t)/\me^t$ is bounded by Theorem \ref{thm:2xlog2},
  we are done.
  \begin{comment}
    \begin{equation*}
      \Phi(s)
      =s\int_0^{\infty}\me^{-st}\upvartheta(\me^t)\dee t,
    \end{equation*}
    so that
    \begin{multline*}
      \frac{\Phi(s+1)}{s+1}-\frac1s
      =\int_0^{\infty}\me^{-(s+1)t}\upvartheta(\me^t)\dee t
      -\int_0^{\infty}\me^{-st}\dee t\\
      =\int_0^{\infty}\me^{-st}
      \left(\frac{\upvartheta(\me^t)}{\me^t}-1\right)\dee t.
    \end{multline*}
    By Theorem \ref{thm:IV},
    the left-hand side extends holomorphically to $\sigma\geq0$.
    By Theorem \ref{thm:anal},
    the equation still holds when $s=0$.
    We can now compute, using \eqref{eqn:u-sub} again,
    \begin{equation*}
      \int_0^{\infty}\left(\frac{\upvartheta(\me^t)}{\me^t}-1\right)\dee t
      =\int_1^{\infty}\frac{\upvartheta(x)-x}{x^2}\dee x.\qedhere
    \end{equation*}
  \end{comment}
\end{proof}

\begin{theorem}[The Prime Number Theorem]\label{thm:PNT}
  \begin{equation}\label{eqn:PNT}
    \uppi(x)\sim\frac x{\log x}.
  \end{equation}
  \end{theorem}

\begin{proof}
  By Theorems \ref{thm:V}, \ref{thm:VI}, and \ref{thm:theta-sim},
  \begin{equation*}
    x\sim\upvartheta(x)\sim\uppi(x)\log x.\qedhere
  \end{equation*}
\end{proof}

%\bibliographystyle{plain}
%\bibliography{../../../references}
\def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$}
  \def\rasp{\leavevmode\raise.45ex\hbox{$\rhook$}} \def\cprime{$'$}
  \def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$}
\begin{thebibliography}{1}

\bibitem{MR1932864}
Euclid.
\newblock {\em Euclid's {E}lements}.
\newblock Green Lion Press, Santa Fe, NM, 2002.
\newblock All thirteen books complete in one volume. The Thomas L. Heath
  translation, edited by Dana Densmore.

\bibitem{MR568909}
G.~H. Hardy and E.~M. Wright.
\newblock {\em An Introduction to the Theory of Numbers}.
\newblock Clarendon Press, Oxford, fifth edition, 1979.
\newblock First edition 1938. Reprinted 1990.

\bibitem{MR0092794}
Edmund Landau.
\newblock {\em Elementary Number Theory}.
\newblock Chelsea Publishing, New York, 1958.
\newblock Originally part of \emph{Vorlesungen {\"u}ber Zahlentheorie}
  (Leipzig, 1927). Translated by J. E. Goodman.

\bibitem{MR602825}
D.~J. Newman.
\newblock Simple analytic proof of the prime number theorem.
\newblock {\em Amer. Math. Monthly}, 87(9):693--696, 1980.

\bibitem{MR1476753}
D.~Zagier.
\newblock Newman's short proof of the prime number theorem.
\newblock {\em Amer. Math. Monthly}, 104(8):705--708, 1997.

\end{thebibliography}

\end{document}
