\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}

\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}}

\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{August 20--26, 2018\\
Last edited \today}
\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}

In six days on the Prime Number Theorem,
here is what I tried to cover.
Students knew the needed real analysis,
but not the complex analysis.
I tried to give this.
The course might then be considered
as a practical introduction to that subject.
\begin{asparadesc}
\item[Monday:]
  Chapter \ref{ch:intro}
  and its Theorems \ref{thm:Euclid} and \ref{thm:log-log},
  that $\uppi(x)$ grows beyond all bounds and, more precisely,
  exceeds $\log\log x$.
  Begin Chapter \ref{ch:B} with, hurriedly,
  Theorem \ref{thm:2xlog2}, giving the important bound,
  \begin{equation*}
    \upvartheta(x)\leq 2x\log x.
  \end{equation*}
\item[Tuesday:]
  Review the proof of Theorem \ref{thm:2xlog2}.
  Prove Theorem \ref{thm:Legendre},
  giving the prime factorization of $n$-factorial.
  Start proving Theorem \ref{thm:B},
  Bertrand's Postulate,
  \begin{equation*}
    \uppi(2n)-\uppi(n)>0
  \end{equation*}
  for all $n$ in $\N$;
  but take a break at \eqref{eqn:log-binom}.
  Finish after the break.
\item[Wednesday:]
  In Chapter \ref{ch:C},
  prove Theorem \ref{thm:C}, Chebyshev's Theorem,
  \begin{equation*}
    \uppi(x)\log x\asymp x.
  \end{equation*}
  First reach \eqref{eqn:Chebyshev-1}, $\uppi(x)\log x=\bigO(x),$
  before introducing $\uppsi$.
  Take a break after reaching \eqref{eqn:psi=theta+},
  without having given \eqref{eqn:theta-log}
  or \eqref{eqn:theta(x)<=xlogx}
  or discussed strategy.
  After the break,
  a student suggests the line of argument in \eqref{eqn:A/2}.
  Finish Chapter \ref{ch:C} with time to spare.
  Skip to Chapter \ref{ch:PNT} by defining the Riemann zeta function.
  One student (of six now) knows $\upzeta(s)$
  is defined when the real part $\sigma$ of $s$
  is greater than $1$.
  State Theorem \ref{thm:I}, the product formula for $\upzeta$.
\item[Friday:]
  Prove Theorem \ref{thm:I} and then Theorem \ref{thm:theta-sim},
  that
  \begin{equation*}
    \uppi(x)\log x\sim\upvartheta(x).    
  \end{equation*}
  From Chapter \ref{ch:complex},
  define holomorphic and analytic functions,
  prove Theorem \ref{thm:CR} (the Cauchy--Riemann Equations),
  and state Theorem \ref{thm:holo-ana}
  (holomorphic functions are analytic).
  Prove Theorem \ref{thm:II},
  that $\upzeta(s)-(s-1)\inv$ extends holomorphically to $\sigma>0$.
  Summarize the steps leading to Theorem \ref{thm:PNT},
  the Prime Number Theorem.
\item[Saturday:]
  Prove Theorem \ref{thm:VI},
  that $f(x)\sim x$ when $f$ is increasing and
    $\int_1^{\infty}\bigl(f(t)-t\bigr)\dee t/t^2$ converges.
  Derive Theorem \ref{thm:V},
  that $\int_1^{\infty}(\upvartheta(x)-x)\dee x/x^2$ converges,
  from Theorem \ref{thm:anal}, Newman's ``analytic theorem.''
  With some handwaving about residues (Theorem \ref{thm:res}),
  and without proving $\upzeta(s)\neq0$ when $\sigma=1$,
  prove Theorem \ref{thm:IV},
  that $\Phi(s)-(s-1)\inv$ extends holomorphically to $\sigma\geq1$.
  End with the simplest case of Theorem \ref{thm:2ip},
  that $\int_{\gamma}\dee z/(z-a)=2\mi\uppi$.
\item[Sunday:]
  State what remains: the assertion about zeros of $\upzeta(s)$,
  and Theorem \ref{thm:anal}.
  A crash course in complex analysis (Chapter \ref{ch:complex}),
  not stating Theorems \ref{thm:g-d} and \ref{thm:est},
  but spelling out the rest,
  up to Theorems \ref{thm:CIF} (Cauchy's Integral Formula)
  and \ref{thm:holo-ana}.
  I use mostly English today,
  since the three students present at the beginning (more come later)
  are comfortable with it.
  One comments at the end how quickly we have gone.
\end{asparadesc}


\tableofcontents
\listoffigures

\chapter{Introduction}\label{ch:intro}

These notes concern the \textbf{counting numbers,}
or \emph{positive} integers;
the set of them is $\N$.
The \textbf{natural numbers} are the \emph{non-negative} integers;
the set of them is $\upomega$.
We shall have reason to consider also real and complex numbers,
composing the sets $\R$ and $\C$ respectively.
Some real analysis
is discussed later in this Introduction.
In Chapter \ref{ch:complex} is the complex analysis
needed for our ultimate goal.

That goal is to prove the Prime Number Theorem
(Theorem \ref{thm:PNT}, page \pageref{thm:PNT}).
We shall fill in the details of the proof
in Don Zagier's four-page article,
``Newman's Short Proof of the Prime Number Theorem'' \cite{MR1476753}.
Newman's own treatment is in his own four-page article,
``Simple analytic proof of the prime number theorem''
\cite{MR602825}.

Before the PNT,
we shall prove Bertrand's Postulate
and Chebyshev's Theorem,
all discussed in this Introduction.
A general reference is Hardy and Wright,
\emph{Introduction to the Theory of Numbers} \cite[p.\ 12]{MR568909}.

In the present document,
the real numbers $\me$ and $\uppi$,\label{eip}
and the complex number $\mi$,
related by the equation
\begin{equation*}
\me^{\mi\uppi}+1=0,
\end{equation*}
will be thus written, in upright, roman shape.
This in principle means that the slanted, italic letters $e$, $i$, and $\pi$
are available to serve as variables.  
We shall give $\uppi$ also another meaning as a function,
which will be the object of our study.

Used mathematically,
\emph{the italic letter $p$ will always denote a prime number.}
This is a prime number in the original sense of Euclid,
thus an element of $\N$.
We are going to use the roman or upright letter $\uppi$
not only for the ratio of the circumference of a circle to its diameter,
but also for the function of a real argument
giving the number of primes
that are no greater than the argument.
Thus
\begin{equation}\label{eqn:pi}
\uppi(x)
=\sum_{p\leq x}1
=\abs{\{p\colon p\leq x\}}.
\end{equation}

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

\begin{proof}
  The prime numbers form a list $(p_0,p_1,p_2,\dots)$, where
  \begin{equation*}
    p_0<p_1<p_2<\dotsb
  \end{equation*}
  We show that the list never terminates; that is,
  $p_n$ exists for each $n$ in $\upomega$.
  We use strong induction.
  Suppose $p_k$ exists when $k<n$.  Then
  \begin{equation*}
    \prod_{k<n}p_k+1\geq2.
  \end{equation*}
  (Note that this is true, even if $n=0$;
  the empty product has the value $1$.)
  If $j<n$, then
  \begin{equation*}
    \prod_{k<n}p_k+1\equiv1\pmod{p_j},
  \end{equation*}
  so $p_j$ is not a factor of $\prod_{k<n}p_k+1$.
  However, thus sum must \emph{have} a prime factor.
  The least such is $p_n$.
  Therefore $p_n$ does exist for all natural numbers $n$.
\end{proof}

One can say a little more,
as Hardy and Wright do \cite[p.\ 12]{MR568909}.
In the following, as always, the base of logarithms is $\me$,
unless otherwise specified.

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

\begin{proof}
  As in the proof of Theorem \ref{thm:Euclid}, and \emph{by} the theorem,
  the primes form the increasing sequence $(p_n\colon n\in\upomega)$.
  The proof also shows
  \begin{multline*}
    \bigwedge_{j<n}p_j\leq 2^{2^j}
    \implies
    p_n\leq\prod_{j<n}p_j+1
    \leq\prod_{j<n}2^{2^j}+1\\
    =2^{\sum_{j<n}2^j}+1
    =2^{2^n-1}+1
    \leq2^{2^n},
  \end{multline*}
  and so, by strong induction, for all $n$ in $\upomega$,
  \begin{align*}
    p_n&\leq2^{2^n},&n&\leq\uppi(2^{2^n}).
  \end{align*}
  If $x\geq2$, then for some $n$ in $\upomega$,
  \begin{equation*}
    2^{2^{n+1}}>x\geq2^{2^n},
  \end{equation*}
  and therefore
  \begin{multline*}
    \uppi(x)\geq\uppi(2^{2^n})\geq n
    =\log_2\log_2(2^{2^{n+1}})-1\\
    >\log_2\log_2x-1
    =\frac{\log\log x-\log\log2-\log2}{\log2}\\
    =\log\log x+\frac{(1-\log2)\log\log x-\log\log2-\log2}{\log2}.
  \end{multline*}
  Since $1>\log2$,
  we have the desired result.
\end{proof}

Specifically, \eqref{eqn:log-log} holds if
  \begin{equation*}
    \log\log x\geq\frac{\log\log2+\log2}{1-\log2}.
  \end{equation*}
  To handle lesser $x$ by hand, we may note
    \begin{equation*}
    \me^3>\left(\frac{27}{10}\right)^3
        =\frac{19683}{1000}>16=2^4,
  \end{equation*}
  so that
  \begin{equation*}
    n\geq4\implies
    \me^{\me^{n-1}}
    >\me^{2^n}
    >2^{2^n},
  \end{equation*}
  and therefore
  \begin{multline*}
\me^{\me^n}\geq x>\me^{\me^{n-1}}\And    n\geq4\\
    \implies\uppi(x)\geq\uppi(\me^{\me^{n-1}})
    \geq\uppi(2^{2^n})\geq n\geq\log\log x.
  \end{multline*}
  This proves \eqref{eqn:log-log} when $x>\me^{\me^3}$.
  Going further, we have
  \begin{equation*}
    \me^{\me^3}\geq x\geq5\implies\uppi(x)\geq3\geq\log\log x.
  \end{equation*}
  Moreover,
  \begin{equation*}
    \me^{\me^1}>\left(\frac{27}{10}\right)^2=\frac{729}{100}>5,
  \end{equation*}
  so
  \begin{equation*}
    5>x\geq2\implies\uppi(x)\geq1\geq\log\log x.
  \end{equation*}
  Finally, $\me^{\me^0}>2$, so $2>x\geq1\implies\uppi(x)=0\geq\log\log x$.


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*}
  \uppi(2n)-\uppi(n)>0.
\end{equation*}
I do not know why the result is called a postulate,
but apparently Bertrand verified it in 1845
when $n$ was less than three million.
My source here is Dickson's
\emph{History of the Theory of Numbers} \cite[p.\ 435]{Dickson-I}.
This was first published in 1919,
when some results that we shall consider were fresh or not yet known.
For details,
Dickson defers to Landau's
\emph{Handbuch [der Lehre von der] Verteilung der Primzahlen, I,} of 1919
(which I haven't got).

Given two positive-valued functions $f$ and $g$,
defined on either $\N$ or an interval $(a,\infty)$,
if the quotient $f(x)/g(x)$ is bounded above,
we shall use the standard notation
(due to Landau, I believe)
\begin{equation*}
  f=\bigO(g).
\end{equation*}
One must recognize that $\bigO(g)$ means nothing in isolation.
In case both $f=\bigO(g)$ and $g=\bigO(f)$,
we shall write
\begin{equation}\label{eqn:asymp}
f\asymp g,
\end{equation}
using the notation of Hardy and Wright \cite[p.\ 7]{MR568909}.
In this case,
\begin{compactitem}
\item
$f$ \textbf{is of the same order of magnitude as} $g$,
in the terminology of Hardy and Wright;
\item
$f$ and $g$ \textbf{go to infinity at similar rates,}
  for Mazur and Stein in
  \emph{Prime Numbers and the Riemann Hypothesis}
\cite[ch.\ 17, p.\ 56]{Mazur-Stein}.
\end{compactitem}
The latter terminology is potentially misleading,
since a constant function does not ``go to infinity,''
although, as we shall presently confirm,
\begin{equation*}
  s>1\implies\int_1^x\frac{\dee t}{t^s}\asymp 1.
\end{equation*}
Here $\int_1^x\dee t/t^s$ denotes
the function that takes this value at $x$.
For arbitrary positive $s$ different from $1$,
\begin{equation*}
  \int_1^x\frac{\dee t}{t^s}
  =\left.\frac1{(1-s)t^{s-1}}\right|_1^x
  =\frac1{1-s}\left(\frac1{x^{s-1}}-1\right).
\end{equation*}
Thus, as we shall want to know for Theorem \ref{thm:II}
on page \pageref{thm:II},
\begin{equation}\label{eqn:II}
  s>1\implies
  \lim_{x\to\infty}\int_1^x\frac{\dee t}{t^s}
  =\frac1{s-1}.
\end{equation}
Similarly,
\begin{equation*}
   0<s<1\implies\int_1^x\frac{\dee t}{t^s}\asymp x^{1-s},
\end{equation*}
because
\begin{equation}\label{eqn:1-s}
  0<s<1\implies\lim_{x\to\infty}\frac{\int_1^x\dee t/t^s}{x^{1-s}}
  =\frac1{1-s}.
\end{equation}
More difficult than Bertrand's Postulate
will be \textbf{Chebyshev's Theorem}
(Theorem \ref{thm:C}, page \pageref{thm:C}),
\begin{equation*}
\uppi(x)\asymp\frac x{\log x},
\end{equation*}
established around 1850.
In such an expression, again,
we understand the symbolism $f(x)$ as another name for $f$.
In Chebyshev's Theorem,
the base of logarithms is irrelevant.
The statement of the Theorem does not imply Bertrand's Postulate,
but the proofs will use lemmas in common.

In addition to \eqref{eqn:asymp},
we define the expression
\begin{equation*}
  f\prec g,
\end{equation*}
which means $f(x)/g(x)$ tends to $0$ as $x$ grows large.
By an easy application of L'H\^opital's Rule,
\begin{equation}\label{eqn:log-prec}
  s>0\implies\log x\prec x^s.
\end{equation}
We shall use this in proving Chebyshev's Theorem.

Under the condition not only that $f(x)/g(x)$ stays within positive bounds,
but that it has unity as a limit,
or equivalently
\begin{equation*}
  \lim_{x\to\infty}\frac{f(x)-g(x)}{g(x)}=0,
\end{equation*}
we shall write
\begin{equation*}%\label{eqn:sim}
f\sim g;
\end{equation*}
this means
\begin{compactitem}
\item
 $f$ \textbf{is asymptotic to} $g$ \cite[p.\ 8]{MR568909};
\item
  $f$ and $g$ \textbf{go to infinity at the same rate}
  \cite[ch.\ 17, p.\ 56]{Mazur-Stein}.
\end{compactitem}
For example, by \eqref{eqn:II} and \eqref{eqn:1-s},
\begin{gather*}
  s>1\implies\int_1^x\frac{\dee t}{t^s}\sim\frac1{s-1},\\
  0<s<1\implies\int_1^x\frac{\dee t}{t^s}\sim\frac{x^{1-s}}{1-s}.
\end{gather*}
These are easy results, because we can calculate the integrals.
With more work, 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.
See Figure \ref{fig:Li}.
\begin{figure}
  \centering
  \begin{pspicture}(-1.5,-0.5)(9,3)%\psgrid
    \psline{->}(0,0)(9,0)
    \psline{->}(0,0)(0,3)
    \psplot[linewidth=1.6pt]{1.4}{9}{1 x ln div}
    \psline(! 2 EXP 0)(! 2 EXP 0.5)(0,0.5)
    \psline(! 1 EXP 0)(! 1 EXP 1)(0,1)
    \psline(2,0)(! 2 dup ln 1 exch div)
    \uput[d](1,0){$1$}
    \uput[d](2,0){$2$}
    \uput[d](! 2 EXP 0){$\me^2$}
    \uput[l](0,0.5){$1/2$}
    \uput[d](! 1 EXP 0){$\vphantom2\me$}
    \uput[l](0,1){$1$}
    \uput[l](! 0 1 2 ln div){$1/\log2$}
    \psline[linestyle=dotted](! 0 1 2 ln div)(! 2 1 2 ln div)
    \psline[linestyle=dashed](1,0)(1,3)
  \end{pspicture}
  \caption{$y\log x=1$}\label{fig:Li}
  
\end{figure}
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'}=\frac1x\Li(x)=\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.

The \textbf{Prime Number Theorem}
(Theorem \ref{thm:PNT}, page \pageref{thm:PNT}) is
\begin{equation*}
\uppi(x)\sim\frac x{\log x},
\end{equation*}
established in 1896 by Hadamard
and de la Vall\'ee-Poussin independently.
The Theorem implies Bertrand's Conjecture.

The \emph{Riemann Hypothesis}
is a refinement of the Prime Number Theorem.

\chapter{Bertrand's Postulate}\label{ch:B}

Our proof of Bertrand's Postulate, Theorem~\ref{thm:B} below,
will be based on that of Hardy and Wright~\cite[\S22.3]{MR568909},
who attribute it to Paul Erd\H os~\cite{Erdos}.
Erd\H os's paper appeared in 1932, and Erd\H os was born in 1913.
An earlier proof, from 1919, is due to Srinivasa Ramanujan~\cite{Ramanujan};
this proof is very short (2 pages),
but makes use of the Gamma function
and Stirling's approximation to it.
Hardy and Wright attribute the earliest proof of Bertrand's
Postulate to Tchebyshef (Chebyshev) in 1850.

We shall make use of the auxiliary function $\upvartheta$ given by
\begin{equation}\label{eqn:theta}
  \upvartheta(x)=\sum_{p\leq x}\log p.
\end{equation}
Then $\upvartheta(x)=\log\prod_{p\leq x}p$,
so that, for example,
\begin{equation*}
  2<3<5\And\upvartheta(5)=\log(2\cdot3\cdot5).
\end{equation*}
We establish 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}
In particular, $\upvartheta(x)=\bigO(x)$.
\end{theorem}

\begin{proof}
Since
\begin{equation*}%\label{eqn:theta[x]}
  \upvartheta(x)=\upvartheta\bigl([x]\bigr),
\end{equation*}
it is enough to prove the claim when $x$ is a positive integer.
Primes will enter the argument as follows.
  If $0\leq k\leq n$, by definition
  \begin{equation}\label{eqn:binom-coeff}
    \binom nk=\frac{n!}{(n-k)!\;k!}.
  \end{equation}
  One way to prove this an integer is to use the Binomial Theorem,
  \begin{equation}\label{eqn:binom}
    (x+y)^n=\sum_{k=0}^n\binom nkx^{n-k}y^k;
  \end{equation}
  here the coefficients in the expansion of $(x+y)^n$ must be integers.
  The proof of \eqref{eqn:binom} will use the rules
  \begin{align*}
    \binom n0&=1,&\binom nn&=1,
  \end{align*}
  and
  \begin{equation*}
    0\leq k<n\implies\binom nk+\binom n{k+1}=\binom{n+1}{k+1};
  \end{equation*}
  from these, one can prove directly (by induction)
  that each $\binom nk$ is an integer.
  
  It is a standard exercise to show
  \begin{equation}\label{eqn:p-div}
    0<k<p\implies p\biggm|\binom pk
  \end{equation}
  using 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\implies\prod_{k<p\leq n}p\biggm|\binom nk.
  \end{equation*}
  Since
  \begin{equation*}
    \log\prod_{k<p\leq n}p=\upvartheta(n)-\upvartheta(k),
  \end{equation*}
  we conclude
  \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 by strong induction.
  We assume \eqref{eqn:lem} holds when $x$ is an integer less than $n$.
  The case where $n=1$ is trivial.
  In case $n=2$, we compute immediately
  \begin{equation*}
    \uptheta(n)=\uptheta(2)=\log2<4\log2=2n\log2.
  \end{equation*}
  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*}
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 \eqref{eqn: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{proof}

Erd\H os attributes the following to Legendre.

\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\in\N}\Bigl[\frac n{p^j}\Bigr].
\end{equation}
\end{theorem}

\begin{proof}
  We are counting the number of times that each $p$ is a factor of $n!$.
  Such $p$ must be no greater than $n$.
To the number of times that some fixed $p$ is a factor of $n!$,
\begin{compactitem}
\item
  each multiple $\ell p$ of $p$, where $\ell p\leq n$, contributes one;
\item
  each multiple $\ell p^2$ of $p$, where $\ell p^2\leq n$,
  contributes an additional one,
  besides the factor contributed because $(\ell p)p\leq n$;
\item
  each multiple $\ell p^3$ of $p$, where $\ell p^3\leq n$,
  contributes an additional one,
  besides the factors contributed
  because $(ell p)p\leq n$ and $(\ell p^2)p\leq n$;
\end{compactitem}
and so on.
The result is the sum over all $j$ in $\N$
of those $\ell p^j$ such that $\ell p^j\leq n$.
The number of such multiples $\ell p^j$ is $[n/p^j]$.
\end{proof}

The sum in \eqref{eqn:Legendre}
has a term $\log p\cdot[n/p^j]$ precisely for those prime-powers
(that is, powers of primes) $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].
\end{equation*}
Alternatively,
\begin{equation*}
  \log(n!)=\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^m$ for some positive $m$};\\
     0,&\text{ otherwise.}
    \end{cases}
\end{equation*}
We shall use this function in
\eqref{eqn:psi} on page \pageref{eqn:psi}.
Meanwhile, we may observe
\begin{equation*}
  \sum_{m\divides n}\Lambda(m)=\log n.
\end{equation*}
I would call this the Fundamental Theorem of Arithmetic;
however, in \emph{Multiplicative Number Theory,}
Davenport remarks
\cite[p.\ 55]{MR606931},
\begin{quote}
  Although this can be proved directly,
  the simplest way of deriving this and similar identities
  is by comparing coefficients in two Dirichlet series
  which have the same sum.
\end{quote}
We just pass on to the following.

\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}n(p)\log 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*}
  2m\leq\frac{2n}k<2m+2
  \implies\left[\frac nk\right]=m,\\
  2m\leq\frac{2n}k<2m+1
  \implies\left[\frac{2n}k\right]=2m,\\
    2m+1\leq\frac{2n}k<2m+2
  \implies\left[\frac{2n}k\right]=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{equation}\label{eqn:1-2}
  \log\binom{2n}n
=\sum_{n(p)\geq1}n(p)\log p
=\sum_{n(p)=1}\log p+\sum_{n(p)\geq2}n(p)\log p.
\end{equation}
Here, 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}n(p)\log p
\leq\sum_{n(p)\geq2}\log(2n)
\leq\sqrt{2n}\log(2n).
\end{equation*}
Thus \eqref{eqn:1-2} becomes
\begin{equation}\label{eqn:log-binom}
\log\binom{2n}n
\leq\sum_{p\divides\binom{2n}n}\log p+\sqrt{2n}\log(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
  \leq\log(2n)+\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+(1+\sqrt{2n})\log(2n).
\end{equation}
The left-hand side dominates the second term on the right,
by \eqref{eqn:log-prec}.
We shall show then 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,
since there is a sequence
  \begin{equation*}
    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.
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)\\
  \begin{aligned}
    &=\frac{\sqrt{2n}}{\log\sqrt{2n}}
    -\frac{2\cdot3}{\log2}\left(\frac1{\sqrt{2n}}+1\right)\\
    &\geq\frac{\sqrt{2n}}{\log\sqrt{2n}}
    -\frac{2\cdot3}{\log2}\left(\frac1{32}+1\right)\\
    &=\frac{\sqrt{2n}}{\log\sqrt{2n}}
    -\frac{2\cdot3\cdot33}{2^5\log2}\\    
    &\geq\frac{\sqrt{2n}}{\log\sqrt{2n}}
    -\frac{2\cdot100\cdot2^5}{2^{10}\log2}\\
    &\geq\frac{\sqrt{2n}}{\log\sqrt{2n}}
    -\frac{2^5}{5\log2}
    >0,
  \end{aligned}
\end{multline*}
since $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{Chebyshev's Theorem}\label{ch:C}

Chebyshev's Theorem is stated
\cite[Thm 7, p.\ 9]{MR568909}
and proved \cite[\S\S22.1--4, p.\ 340--6]{MR568909}
by Hardy and Wright;
we shall follow their proof,
which uses the auxiliary function $\upvartheta$,
as given by \eqref{eqn:theta}, and also $\uppsi$,
given by
\begin{equation}\label{eqn:psi}
  \uppsi(x)=\sum_{p^m\leq x}\log p=\sum_{n\leq x}\Lambda(n).
\end{equation}
Hence
$\uppsi(x)=\log\prod_{p^m\leq x}p$,
so that, for example,
\begin{equation*}
  2<3<2^2<5\And  \uppsi(x)=\log(2\cdot3\cdot2\cdot5).
\end{equation*}
Also
\begin{equation*}
  \uppsi(x)=\log\lcm([x]!).
\end{equation*}
Landau also proves the theorem
\cite[Thm 112, pp.\ 88--91]{MR0092794}.

\begin{theorem}[Chebyshev]\label{thm:C}
\begin{equation*}
\uppi(x)\asymp\frac x{\log x}.
\end{equation*}  
\end{theorem}

\begin{proof}
  We have to bound $\uppi(x)$ from both sides.
  From Theorem \ref{thm:2xlog2},
  we have an upper bound $2x\log2$ on $\upvartheta(x)$.
  We shall relate this to $\uppi(x)$.
  We observe
  \begin{equation}\label{eqn:theta>}
	\upvartheta(x)
	\geq\sum_{x\geq p>\surd x}\log\surd x
	=\bigl(\uppi(x)-\uppi(\surd x)\bigr)\log\surd x.
  \end{equation}
  Using here 
  $\log\surd x=\frac12\log x$ and
  \begin{equation*}
    \uppi(\surd x)\leq\surd x=\frac x{\surd x}
    \leq\frac x{\log x},
  \end{equation*}
  we obtain
  \begin{gather}\label{eqn:theta>'}
    	\upvartheta(x)
        \geq\left(\uppi(x)-\frac x{\log x}\right)\frac{\log x}2,\\
        \label{eqn:2theta}
        \frac{2\upvartheta(x)+x}{\log x}\geq\uppi(x),\\\label{eqn:Chebyshev-1}
        (4\log2+1)\frac x{\log x}\geq\uppi(x)
  \end{gather}
by Theorem \ref{thm:2xlog2}.
This is half of Chebyshev's Theorem.
For the other half,
we first work out a complement of \eqref{eqn:theta>},
namely
\begin{equation}\label{eqn:theta>comp}
\upvartheta(x)\leq\sum_{p\leq x}\log x=\uppi(x)\log x,
\end{equation}
so that we have, complementing \eqref{eqn:2theta},
\begin{equation}\label{eqn:theta-log}
\frac{\upvartheta(x)}{\log x}\leq\uppi(x).
\end{equation}
We want to bound $\upvartheta(x)$ below by a multiple of $x$.
We shall do this by
\begin{compactenum}[(i)]
  \item\label{item:A}
    bounding $\uppsi(x)$ in the same way, and
  \item\label{item:<x}
    showing $\uppsi(x)-\upvartheta(x)\prec x$.
\end{compactenum}
If we have \eqref{item:<x},
and \eqref{item:A} in the form $\uppsi(x)\geq Ax$,
then for $x$ large enough,
\begin{align}\label{eqn:A/2}
  \frac A2
  &\geq\frac{\uppsi(x)-\upvartheta(x)}x,
  %  \geq\frac{Ax-\upvartheta(x)}x=A-\frac{\upvartheta(x)}x,
  &
  \upvartheta(x)\geq\frac A2x.
\end{align}
To achieve \eqref{item:<x},
we shall use an upper bound on $\upvartheta(x)$:
\begin{equation}\label{eqn:theta(x)<=xlogx}
   \upvartheta(x)
  \leq x\log x.
\end{equation}
This will be useful, because
\begin{gather*}
  \uppsi(x)=\sum_m\upvartheta(x^{1/m}),\\
  2\leq x^{1/m}\iff m\leq\frac{\log x}{\log 2},
\end{gather*}
so that
\begin{equation}\label{eqn:psi=theta+}
  \uppsi(x)
  -\upvartheta(x)
  =\sum_{m=2}^{[\log x/\log 2]}\upvartheta(x^{1/m}).
\end{equation}
From \eqref{eqn:theta(x)<=xlogx},
\begin{equation*}
  2\geq m\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\frac{\surd x(\log x)^2}{\log 2}\prec x.
\end{equation*}
It remains to bound $\uppsi(x)$ below by a multiple of $x$.
To do this, we let
\begin{equation*}
  \left[\frac x2\right]=n.
\end{equation*}
If $x\geq2$, we have
\begin{equation*}
\frac x3\leq n.
\end{equation*}
In the notation of, and by, the proof of Theorem \ref{thm:B},
we have
\begin{multline*}
  \log\binom{2n}n
  =\sum_{p\leq2n}n(p)\log p
  \leq\sum_{p\leq2n}\left[\frac{\log(2n)}{\log p}\right]\log p\\
  =\uppsi(2n)\leq\uppsi(x).
\end{multline*}
Moreover,
\begin{equation*}
2^n\leq\prod_{1\leq j\leq n}\frac{n+j}j=\binom{2n}n,
\end{equation*}
which means now
\begin{equation*}
\frac{\log 2}2x\leq  n\log2\leq\log\binom{2n}n.
\end{equation*}
Thus we have the desired bound.
\end{proof}

We can now pass immediately to Theorem \ref{thm:theta-sim}.
Meanwhile, in the process of proving Chebyshev's Theorem,
we have established also
  \begin{equation}\label{eqn:theta(x)x}
    \upvartheta(x)\asymp x
  \end{equation}
  as well as
  \begin{equation*}
    \uppsi(x)\asymp x.
  \end{equation*}

\chapter{Complex Analysis}\label{ch:complex}

A standard text for complex analysis is Ahlfors's
\emph{Complex Analysis}
\cite{Ahlfors}.
But there is a lot that we shall not need.
A terse source is ``A first course in complex variables,''
Problem \textbf{4-33} of Spivak's
\emph{Calculus on Manifolds} \cite[pp.\ 105--6]{MR0209411}.

\section{Holomorphic Functions}

We can define limits and derivatives of complex-valued functions
as we do for real-valued functions.
To do so, we replace finite open intervals
with open disks.
Each of these is an open \emph{ball} of the appropriate dimension.

If $a\in\C$, and $\epsilon$ is real and positive,
the \textbf{open disk}
having center $a$ and radius $\epsilon$
is the subset
\begin{equation*}
  \{z\in\C\colon\abs{z-a}<\epsilon\}
\end{equation*}
of $\C$; we may denote this disk by
\begin{equation*}
  \ball.
\end{equation*}
A \textbf{neighborhood} of $a$ is a subset of $\C$
that includes some disk $\ball$.
A subset of $\C$
is called \textbf{open}
if it includes a neighborhood of its every point.
We shall generally let 
$\Omega$ be an open subset of $\C$,
and $f\colon\Omega\to\C$.

An element $L$ of $\C$ is the \textbf{limit} of $f$ at a point $a$ in $\Omega$,
and we write
\begin{equation*}
L=\lim_{z\to a}f(z),
\end{equation*}
provided that,
for all positive $\epsilon$ in $\R$,
for some positive $\delta$ in $\R$,
for all $z$ in $\Omega$,
\begin{equation*}
0<\abs{z-a}<\delta\implies\abs{f(z)-L}<\epsilon.
\end{equation*}
Here the value of $f(a)$ is irrelevant (and we may allow it to be undefined).
If however
\begin{equation*}
  \lim_{z\to a}f(z)=f(a),
\end{equation*}
then $f$ is \textbf{continuous} at $a$.

An element $D$ of $\C$ is the \textbf{derivative} of $f$ at $a$,
and we write
\begin{equation*}
D=f'(a),
\end{equation*}
if
\begin{equation*}%\label{eqn:=D}
\lim_{z\to a}\frac{f(z)-f(a)}{z-a}=D.
\end{equation*}
If $f$ has a derivative at every point of $\Omega$,
then $f$ is called \textbf{holomorphic.}
In place of $f'(z)$, we may write
\begin{equation*}
  \Dee_zf(z),
\end{equation*}
especially if we have not got a letter like $f$ in isolation,
but only $f(z)$,
as in \eqref{eqn:Dz(z-a)} below.%%%%%
\footnote{According to Kline in
  \emph{Mathematical Thought from Ancient to Modern Times}
  \cite[p.\ 642]{MR0472307},
  the French form of the term ``holomorphic''
  was introduced by Briot (1817--82) and Bouquet (1819--85)
to replace the term \emph{synectique,}
which had been introduced by Cauchy in 1851.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The rules of differentiation familiar from calculus---%
the constant, multiplication, division, and power rules---%
still apply to complex differentiation.
Moreover, the identity $z\mapsto z$ is holomorphic,
with derivative $1$.
Thus all rational functions are holomorphic on their domains.

The fundamental example of a function that is \emph{not} holomorphic
is \textbf{complex conjugation,} $z\mapsto\conj z$, where
\begin{equation*}
  \conj{x+\mi y}=x-\mi y.
\end{equation*}
For, the function $z\mapsto(\conj z-\conj a)/(z-a)$
has no limit at $a$, 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.

Ahlfors uses the term \emph{analytic}
for the functions that we are calling holomorphic
\cite[p.\ 24]{Ahlfors},
For Spivak, an analytic function
is a function that is holomorphic in our sense
\emph{and} has continuous derivative.
Ahlfors remarks \cite[p.\ 101]{Ahlfors},
\begin{quote}
  it is only quite recently that it became possible to prove,
  without resorting to complex integrals or similar tools,
  that the derivative of an analytic function is continuous,
  or that the higher derivatives exist.
  At present the integration-free proofs are,
  to say the least,
  much more difficult than the classical proofs.
\end{quote}
The same might be said
for analysis-free proofs of the Prime Number Theorem.

In another approach to taking derivatives,
we may consider $\C$
merely as the two-dimensional real vector-space $\R^2$,
where
\begin{align*}
  1&=
  \begin{pmatrix}
    1\\0
  \end{pmatrix},&
  \mi&=
  \begin{pmatrix}
    0\\1
  \end{pmatrix}.
\end{align*}
If there is a linear transformation $T$ of $\R^2$ such that
\begin{equation*}
  \lim_{z\to a}\frac{\abs{f(z)-f(a)-T(z-a)}}{\abs{z-a}}=0,
\end{equation*}
then let us write
\begin{equation*}
  T=\Dee f(a).
\end{equation*}
If $\Dee f(a)$ exists for all $a$ in $\Omega$,
we may say that $f$ is \textbf{differentiable.}

We can express $\Dee f$ in terms of partial derivatives.
If we define
\begin{equation*}
  f=g+\mi h,
\end{equation*}
where $g$ and $h$ are real-valued functions, then
\begin{equation}\label{eqn:Df(a)}
  Df(a)(x+\mi y)=
  \begin{pmatrix}
    \partial_xg(a)&\partial_yg(a)\\
    \partial_xh(a)&\partial_yh(a)
  \end{pmatrix}
  \begin{pmatrix}
    x\\y
  \end{pmatrix},
\end{equation}
where for example
\begin{equation*}
  \partial_yg(a)=\lim_{h\to0}\frac{g(a+\mi h)-g(a)}h,
\end{equation*}
the $h$ here being real.
Complex conjugation is differentiable,
its derivative being given by the matrix
\begin{equation*}
  \begin{pmatrix}
    1&0\\0&-1
  \end{pmatrix}.
\end{equation*}
In general, we may write
\begin{align*}
  \partial_xg(a)+\mi\partial_xh(a)&=\partial_xf(a),&
    \partial_yg(a)+\mi\partial_yh(a)&=\partial_yf(a).
\end{align*}
For $f$ to be differentiable,
it is necessary for $\partial_xf$ and $\partial_yf$ to exist,
and sufficient that they be continuous
\cite[p.\ 31]{MR0209411}.

In the following,
\eqref{eqn:CR}
are the \textbf{Cauchy--Riemann Equations.}

\begin{theorem}\label{thm:CR}
  For the function $f$ on $\Omega$ to be holomorphic,
  it is necessary and sufficient that $f$ be differentiable and
\begin{equation}\label{eqn:CR-comb}
  \mi\partial_xf=\partial_yf.
\end{equation}
\end{theorem}

\begin{proof}
If $f'(a)$ exists, this means
  \begin{equation}\label{eqn:|D|}
    \lim_{z\to a}\frac{f(z)-f(a)-f'(a)(z-a)}{z-a}=0.
  \end{equation}
  Here multiplication by $f'(a)$
  is a \emph{complex}-linear transformation of $\C$,
  and therefore a real-linear transformation of $\R^2$.
In particular,
  \begin{equation*}
    (b+\mi c)(x+\mi y)
    =bx-cy+\mi(cx+by)
    =
    \begin{pmatrix}
      b&-c\\c&b
    \end{pmatrix}
    \begin{pmatrix}
      x\\y
    \end{pmatrix}.
  \end{equation*}
  Comparison with \eqref{eqn:Df(a)}
  shows that $Df(a)$ is complex-linear at each $a$ in $\Omega$
  if and only if, on $\Omega$,
  \begin{align}\label{eqn:CR}
    \partial_xg&=\partial_yh,&
    \partial_xh&=-\partial_yg.
  \end{align}
  These equations are summarized as \eqref{eqn:CR-comb}.
\end{proof}

The theorem follows also from the observation that,
  if $f'(a)$ exists, then
  \begin{equation*}
    f'(a)=\lim_{h\to0}\frac{f(a+h)-f(a)}h=\partial_xf(a),
  \end{equation*}
  where $h$ is real, but also
  \begin{equation*}
    \mi f'(a)=\lim_{h\to0}\frac{f(a+\mi h)-f(a)}h
    =\partial_yf(a).
  \end{equation*}


\section{Analytic Functions}

If, for every $a$ in $\Omega$,
there is an infinite sequence $(c_n\colon n\in\omega)$,
and there is some positive $\epsilon$, such that
\begin{equation*}
  \abs{z-a}<\epsilon\implies f(z)=\sum_{n\in\omega}c_n(z-a)^n,
\end{equation*}
then $f$ is called \textbf{analytic.}
In this case, $f$ has all higher derivatives $f^{(n)}(a)$
at every point $a$ of $\Omega$, and moreover
\begin{equation*}
  \ball\included\Omega
  \And z\in\ball
  \implies f(z)=\sum_{n\in\omega}\frac{f^{(n)}(a)}{n!}(z-a)^n.
\end{equation*}
In particular, analytic functions are holomorphic.
We shall prove the converse as Theorem \ref{thm:holo-ana}.

Suppose now $\gamma\colon[a,b]\to\Omega$.
We may make the analysis
\begin{equation}\label{eqn:gamma}
\gamma=\gamma_0+\mi\gamma_1,
\end{equation}
where $\gamma_e\colon[a,b]\to\R$.
Now we can define
\begin{equation*}
\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 continuously differentiable
(which means that each $\gamma_e$ is continuously differentiable)
and one-to-one.
Then $\gamma$ can be said to have the \textbf{initial point} $\gamma(a)$ 
and the \textbf{terminal point} $\gamma(b)$,
and $\gamma$ itself can be called an
\textbf{arc} or \textbf{path} or \textbf{line.}
%(I am not aware that one needs to distinguish between these words).
If the range of $\gamma$ is included in the domain $\Omega$
of the holomorphic function $f$,
then by definition,
\begin{equation}\label{eqn:int-f}
\int_{\gamma}f=\int_a^b(f\circ\gamma)\gamma'.
\end{equation}
We may also write this as
\begin{equation*}
\int_{\gamma}f(z)\dee z=\int_a^bf(\gamma(t))\gamma'(t)\dee t.
\end{equation*}
This is a \textbf{line integral,} 
and it is computed by the formal substitution
\begin{align*}
  z&=\gamma(t),&\dee z&=\gamma'(t)\dee t.
\end{align*}
We may confuse a path like $\gamma$
with its range and its initial and terminal points,
by the following.

\begin{theorem}\label{thm:g-d}
  If $\delta$ is an arc
  with the same range, initial point, and terminal point as $\gamma$,
  then
  \begin{equation*}
    \int_{\gamma}f=\int_{\delta}f,
  \end{equation*}
\end{theorem}

\begin{proof}
  Suppose the domain of $\delta$ is $[c,d]$.
  By the substitution
  \begin{align*}
    \gamma(t)&=\delta(u),&
    \gamma'(t)\dee t&=\delta'(u)\dee u,
  \end{align*}
  we obtain
  \begin{equation*}
    \int_a^bf(\gamma(t))\gamma'(t)\dee t
    =\int_a^bf(\delta(u))\delta'(u)\dee u.\qedhere
  \end{equation*}
\end{proof}

We can allow arcs to be merely ``piecewise'' continuously differentiable,
that is, continuously differentiable
at all but finitely many points of their domains.

Understanding $z$ as $x+\mi y$, we may write
\begin{equation}\label{eqn:line-int-comp}
\int_{\gamma}f=\int_{\gamma}f(z)\dee z
=\int_{\gamma}\bigl(f(z)\dee x+\mi f(z)\dee y\bigr).
\end{equation}
Writing $f$ as $f_0+\mi f_1$,
we obtain
\begin{multline}\label{eqn:line-int}
	\int_{\gamma}f
%	=\int_{\gamma}f(z)\dee z
%	=\int_{\gamma}\bigl(f^0(z)+\mi f^1(z)\bigr)\cdot(\dee x+\mi\dee y)
	=\int_{\gamma}\bigl(f_0(z)\dee x-f_1(z)\dee y\bigr)\\
	{}+\mi\int_{\gamma}\bigl(f_1(z)\dee x+f_0(z)\dee y\bigr).
\end{multline}
This is just notation for now,
but it suggests an alternative approach to defining the complex integral.
That is, given two functions $g$ and $h$ from $\Omega$ to $\R$,
we can define
\begin{equation*}
\int_{\gamma}\bigl(g(z)\dee x+h(z)\dee y\bigr)
=  \int_a^b\bigl((g\circ\gamma)\gamma_0{}'
  +(h\circ\gamma)\gamma_1{}'\bigr),
\end{equation*}
when the latter exists.
Using this twice in \eqref{eqn:line-int},
we recover \eqref{eqn:int-f}.

  We also define an integral with respect to arc length:
  \begin{equation*}
    \int_{\gamma}f(z)\abs{\dee z}=\int_a^b(f\circ\gamma)\abs{\gamma'}.
  \end{equation*}

  \begin{theorem}\label{thm:est}
    \begin{equation*}
      \abs{\int_{\gamma}f}\leq\int_{\gamma}\abs{f(z)}\abs{\dee z}.
    \end{equation*}
  \end{theorem}

  \begin{proof}
    For any real $\theta$,
    \begin{equation*}
      \me^{\mi\theta}\int_{\gamma}f=\int_{\gamma}\me^{\mi\theta}f
      =\int_a^b\me^{\mi\theta}(f\circ\gamma)\gamma',
    \end{equation*}
    and so
    \begin{multline*}
      \Re\left(\me^{\mi\theta}\int_{\gamma}f\right)
      =\int_a^b\Re\left(\me^{\mi\theta}(f\circ\gamma)\gamma'\right)\\
      \leq\int_a^b\abs{f\circ\gamma}\abs{\gamma'}
      =\int_{\gamma}\abs{f(z)}\abs{\dee z}.
    \end{multline*}
    Finally, for appropriate $\theta$,
    \begin{equation*}
      \abs{\int_{\gamma}f}=\Re\left(\me^{\mi\theta}\int_{\gamma}f\right).
      \qedhere
    \end{equation*}
  \end{proof}

%\subsection{Path independence}

If $\int_{\gamma}f$ depends only on the initial and terminal points of $\gamma$,
we may say that the integral is \textbf{path independent.}

\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}

\begin{theorem}\label{thm:hol-der}
If the line integrals of a continuous function are path independent,
then the function is the derivative of a holomorphic function.
\end{theorem}

\begin{proof}
  Suppose line integrals
  of a continuous function $f$ from $\Omega$ to $\C$ are path independent. 
  Fix a point $c$ of $\Omega$.
  If, for a point $d$ of $\Omega$,
  there are arcs in $\Gamma$ with initial point $c$
  and terminal point $d$,
  let $\gamma$ be one of them.
  We can unambiguously define
  \begin{equation}\label{eqn:F(d)}
    F(d)
    =\int_{\gamma}f.
  \end{equation}
  This gives us a function $F$
  defined on the set of points to which there is a path from $c$.
  Supposing $\gamma$ has domain $[a,b]$,
  we can write \eqref{eqn:F(d)} as
  \begin{equation*}%\label{eqn:F}
    (F\circ\gamma)(b)
    =\int_a^b(f\circ\gamma)\gamma'.
  \end{equation*}
  Since $\Omega$ is open,
  it includes a neighborhood of $b$,
  and we can therefore extend $\gamma$ beyond $d$.
  In particular, for some positive $\delta$,
  on $[a,b+\delta)$ we have
  \begin{equation*}%\label{eqn:F}
    (F\circ\gamma)(x)
    =\int_a^x(f\circ\gamma)\gamma'.
  \end{equation*}    
  By the Fundamental Theorem,
  $F\circ\gamma$ is differentiable at $b$, and
  \begin{equation}\label{eqn:Fg}
    (F\circ\gamma)'(b)=f(\gamma(b))\gamma'(b)=f(d)\gamma'(b).
  \end{equation}
  Near $b$,
  we can require $\gamma$ to be either of
  \begin{align*}
    t&\mapsto d+t-b,&
    t&\mapsto d+\mi(t-b),
  \end{align*}
  yielding respectively
  \begin{align*}
    \gamma'(b)&=1,&\gamma'(b)&=\mi,\\
    (F\circ\gamma)'(b)&=\partial_xF(d),&
    (F\circ\gamma)'(b)&=\partial_yF(d).
  \end{align*}
  Then from \eqref{eqn:Fg} we obtain
  \begin{align}\label{eqn:FCR}
    \partial_xF(d)&=f(d),&
    \partial_yF(d)&=\mi f(d).
  \end{align}
  Thus $F$ satisfies the
  Cauchy--Riemann Equations,
  in the combined form \eqref{eqn:CR-comb}.
  In particular, if $F$ is differentiable,
  then it is holomorphic,
  and $F'=f$.
  Again, a sufficient condition
  for the differentiability of $F$
  (given the existence of the partial derivatives)
  is continuity of $f$.
\end{proof}

If we suppose only that the real part of line integrals of $f$
are path independent, this means by \eqref{eqn:line-int}
that the integrals
\begin{equation*}
\int_{\gamma}\bigl(f_0(z)\dee x-f_1(z)\dee y\bigr)
\end{equation*}
are path independent.
We obtain $F$ as before, but now real-valued;
and in place of \eqref{eqn:FCR},
\begin{align*}
	\partial_xF(d)&=f_0(d),&\partial_yF(d)&=-f_1(d).
\end{align*}
One then refers to the integrand $f_0(z)\dee x-f_1(z)\dee y$
as an \textbf{exact differential.}
One may refer to the integrand $f(z)\dee x+\mi f(z)\dee y$
in \eqref{eqn:line-int-comp} in the same way.


The last two theorems are summarized by Ahlfors
\cite[p.\ 107]{Ahlfors}:
\begin{quotation}
  \emph{The integral $\int_{\gamma}f\dee z$, with continuous $f$,
    depends only on the endpoints of $\gamma$
    if and only if $f$ is the derivative of an analytic function on $\Omega$.}

  Under these circumstance we shall prove later
  that $f(z)$ is itself analytic.
\end{quotation}
To this end, we prove the following.

\begin{theorem}\label{thm:rect}
  The integral of a holomorphic function
  along the boundary of a rectangle
  (whose sides are parallel to the coordinate axes) is zero.
\end{theorem}

\begin{proof}
  Say the function is $f$ and the rectangle is traced by $\gamma_0$.
  By bisecting the rectangle vertically and horizontally,
  we obtain four sub-rectangles.
  For one of them, if $\gamma_1$ traces its boundary, then
    \begin{equation*}
      \abs{\int_{\gamma_1}f}\geq\frac14\abs{\int_{\gamma_0}f}.
    \end{equation*}
    Continuing in this way,
    we get a sequence of $\gamma_k$, where
    \begin{equation*}
      \abs{\int_{\gamma_k}f}\geq\frac1{4^k}\abs{\int_{\gamma_0}f},
    \end{equation*}
    and all of the $\gamma_k$ surround a unique point $a$.
    If $n$ is large enough, then inside $\gamma_n$,
    \begin{gather*}
      \abs{\frac{f(z)-f(a)}{z-a}-f'(a)}\leq\epsilon,\\
      \abs{f(z)-f(a)-(z-a)f'(a)}\leq\epsilon\abs{z-a}.
    \end{gather*}
    Since, by Theorem \ref{thm:path-ind},
    \begin{align*}
      \int_{\gamma_n}f(a)&=0,&
      \int_{\gamma_n}(z-a)f'(a)\dee z=0,
    \end{align*}
    we have now, by Theorem \ref{thm:est},
    \begin{multline*}
      \abs{\int_{\gamma_n}f}
      =\abs{\int_{\gamma_n}\bigl(f(z)-f(a)-(z-a)f'(a)\bigr)\dee z}\\
      \leq\int_{\gamma_n}\abs{f(z)-f(a)-(z-a)f'(a)}\abs{\dee z}\\
      \leq\epsilon\int_{\gamma_n}\abs{z-a}\abs{\dee z}
      \leq\frac{\epsilon dL}{4^n},
    \end{multline*}
    where $d$ is the diagonal of the rectangle surrounded by $\gamma_0$,
    and $L$ is the perimeter of the rectangle.
    Thus
    \begin{equation*}
\abs{\int_{\gamma_0}f}\leq\epsilon dL.
    \end{equation*}
    This being true for all positive $\epsilon$, $\int_{\gamma_0}f=0$.
\end{proof}

\begin{theorem}
  Holomorphic functions on convex regions
  are derivatives of holomorphic functions.
\end{theorem}

\begin{proof}
  Let $\Omega$ be convex, $f$ holomorphic on $\Omega$, and $a\in\Omega$.
  We define $F$ on $\Omega$ so that, if $b\in\Omega$, then
  \begin{equation*}
    F(b)=\int_{\gamma}f,
  \end{equation*}
  where $\gamma$ is the path from $a$ to $b$
  that is first horizontal, then vertical.
  By Theorem \ref{thm:rect},
  $\gamma$ may also be first vertical, then horizontal.
  This shows, as in the proof of Theorem \ref{thm:hol-der},
  that $F$ is holomorphic with derivative $f$.
\end{proof}


%\subsection{Cauchy's Theorem}\label{subsect:Cauchy}

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,
$(z-a)^n$ is holomorphic on its domain,
which is $\C$ if $n\geq0$,
and $\{z\in\C\colon z\neq a\}$, if $n<0$.
Also
\begin{equation}\label{eqn:Dz(z-a)}
  \Dee_z(z-a)^n=n(z-a)^{n-1}.
\end{equation}
Therefore,
letting $\oint$ denote an integral along a counterclockwise closed curve
in the domain of $(z-a)^n$,
we have
\begin{equation*}
n\neq0\implies\oint(z-a)^{n-1}\dee z=0.
\end{equation*}

\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 around $a$
  within that neighborhood,
  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$.
  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.\qedhere
  \end{multline*}
\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 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}

\begin{comment}
  From \eqref{eqn:holo-ana} we can derive a rule for higher derivatives:
  \begin{equation*}
    f^{(n)}(a)=\frac1{2\mi\uppi n!}
    \int_{\gamma}\frac{f(z)\dee z}{(z-a)^{n+1}}.
  \end{equation*}
\end{comment}
To say that $f$ is \textbf{analytic at} $a$
means $f$ is analytic on some neighborhood of $a$.
If $n\in\N$,
and $(z-a)^nf(z)$ is analytic at $a$,
but $(z-a)^{n-1}f(z)$ is not,
then $f$ has a \textbf{pole of order} $n$ at $a$.
In this case, the \textbf{residue} of $f$ at $a$
is the coefficient of $(z-a)\inv$ in the power-series expansion of $f$;
thus the residue is
\begin{equation*}
  \frac1{2\mi\uppi}\oint f,
\end{equation*}
the integral being taken around $a$
along a curve not encompassing any other poles.
If $f'(a)$ exists for all $a$ in $\Omega$,
except for poles, then $f$ is \textbf{meromorphic.}

If $f(z)/(z-a)^n$ is analytic at $a$,
but $f(z)/(z-a)^{n-1}$ is not,
then $f$ has a \textbf{zero of order} $n$ at $a$.
Thus a zero of order $n$ of $f$ at $a$
is a pole of order $n$ of $1/f$ at $a$.


\begin{theorem}\label{thm:res}
  The order of a zero,
  or the negative of the order of a pole, of $f$ at $a$
  is the residue of $f'/f$ at $a$;
  and here, $f'/f$ has a pole of order $1$.
\end{theorem}

\begin{proof}
  From
  \begin{gather*}
    f(z)=c_n(x-a)^n+c_{n+1}(x-a)^{n+1}+\dotsb,\\
    f'(z)=nc_n(x-a)^{n-1}+(n+1)c_{n+1}(x-a)^n+\dotsb,
  \end{gather*}
  we obtain
  \begin{equation*}
    \frac{f'(z)}{f(z)}=n(x-a)\inv+\dotsb.\qedhere
  \end{equation*}
\end{proof}

  Note that, in general,
  \begin{equation*}
    \frac{f'(z)}{f(z)}=\Dee_z\log(f(z));
  \end{equation*}
we may refer to this as the \textbf{logarithmic derivative} of $f$.

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

We shall prove the Prime Number Theorem
as Theorem \ref{thm:PNT} below.
There are other formulations.
With the definition of \eqref{eqn:Li-def},
Mazur and Stein \cite[chh.\ 13 \&\ 17, pp.\ 49 \&\ 58]{Mazur-Stein}
give first
\begin{equation*}
  \uppi(x)\sim\Li(x).
\end{equation*}
This is equivalent,
by \eqref{eqn:Li},
to \eqref{eqn:PNT},
which is the formulation of Hardy and Wright \cite[Thm 6, p.\ 9]{MR568909},
who prove it over the course of 27 pages
 \cite[\S\S22.1--17, pp.\ 340--67]{MR568909}.

We shall follow and expand Don Zagier's short article
``Newman's Short Proof of the Prime Number Theorem'' \cite{MR1476753}.
The argument there is highly concentrated
and proceeds in six numbered steps,
our Theorems \ref{thm:I}, \ref{thm:II}, \ref{thm:2xlog2},
\ref{thm:IV}, \ref{thm:V}, and \ref{thm:VI} respectively.
The ultimate conclusion, Theorem \ref{thm:PNT},
needs one more proof,
namely that of our Theorem \ref{thm:theta-sim}.
Theorem \ref{thm:V} uses an ``analytic theorem,''
our Theorem \ref{thm:anal};
this is Newman's contribution,
reformulated by Zagier, who says he will both
\begin{compactenum}[1)]
\item
  reproduce
``an ingenious short proof''
  that the Riemann zeta function has no zeros with real part $1$
  (this is part of Theorem \ref{thm:IV}), and
    \item
      ``describe'' the analytic proof of the Prime Number Theorem from this,
      using ``a very simple version [found by
        D. J. Newman] of the Tauberian argument needed.''
\end{compactenum}
As they are formulated here,
we can prove Theorems \ref{thm:I}, \ref{thm:II}, \ref{thm:anal}, \ref{thm:VI},
and \ref{thm:theta-sim} in any order.
Theorem \ref{thm:IV} needs Theorems \ref{thm:I} and \ref{thm:II};
Theorem \ref{thm:V} needs Theorems \ref{thm:IV} and \ref{thm:anal};
Theorem \ref{thm:PNT} needs Theorems
\ref{thm:V}, \ref{thm:VI}, and \ref{thm:theta-sim}.
See Figure \ref{fig:dep}.
\begin{figure}
  \centering
  \pstree{\TR{Theorem \ref{thm:PNT}}}{
          \pstree{\TR{Theorem \ref{thm:V}}}{
                  \pstree{\TR{Theorem \ref{thm:IV}}}{
                         \TR{Theorem \ref{thm:I}}\TR{Theorem \ref{thm:II}}}
                  \TR{Theorem \ref{thm:anal}}}
                  \TR{Theorem \ref{thm:VI}}
                  \TR{Theorem \ref{thm:theta-sim}}}
                          
  \caption{Dependence of theorems}
  \label{fig:dep}
\end{figure}
We now proceed.

The \textbf{Riemann zeta function}
is the function $\upzeta$
given on the half-plane $\{s\in\C\colon\Re(s)>1\}$ by
\begin{equation}\label{eqn:zeta}
\upzeta(s)=\sum_{n\in\N}\frac1{n^s}.
\end{equation}
To simplify such expressions, we may use Riemann's notation,
\begin{equation*}
  s=\sigma+\mi t,
\end{equation*}
so that, in particular,
\begin{equation*}
  \Re(s)=\sigma.
\end{equation*}
Speaking elliptically,
we say that $\upzeta$ is the function
$\sum_{n\in\N}1/n^s$, where $\sigma>1$.
The convergence of the sum is absolute,
by the Integral Test,
since
\begin{equation*}
  n^s=\me^{s\log n}=\me^{\mi t\log n}\me^{\sigma\log n}=\me^{\mi t\log n}n^{\sigma},
\end{equation*}
and so
\begin{equation*}
  \abs{\frac1{n^s}}
  =\frac1{n^{\sigma}},
\end{equation*}
while $\int_1^{\infty}\dee t/t^{\sigma}$ converges when $\sigma>1$,
by \eqref{eqn:II}.

\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}
  The factors are sums of geometric series:
  \begin{equation}\label{eqn:geo}
\frac1{1-z\inv}=\sum_{k\in\upomega}\frac1{z^k}.    
  \end{equation}
  Consequently,
  if $P$ is a finite set of primes, then 
  \begin{equation*}
    \prod_{p\in P}\frac1{1-p^{-s}}
    =\sum_{f\in\upomega^P}\Biggl(\prod_{p\in P}p^{f(p)}\Biggr)^{-s},
  \end{equation*}
  where $\upomega^P$ is the set of functions from $P$ to $\upomega$.
  In the sum, $n^{-s}$ appears,
  provided $n$ is the product of primes coming only from $P$.
  Let $N_P$ be the set of such $n$.
  By the Fundamental Theorem of Arithmetic,
  a term $n^{-s}$ appears only once in the sum above.
  Thus
  \begin{equation}\label{eqn:prod-P}
    \prod_{p\in P}\frac1{1-p^{-s}}=\sum_{n\in N_P}\frac1{n^{-s}}.
  \end{equation}
  Since the sum in \eqref{eqn:zeta} converges absolutely,
  no matter how $P$ grows to encompass all primes,
  the product in \eqref{eqn:prod-P} approaches the sum in
  \eqref{eqn:zeta} as a limit.
\end{proof}

\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 the half-plane $\sigma>0$
%$\{s\in\C\colon\Re(s)>0\}$
(and thus the residue of $\upzeta$ at $1$ is $1$).
\end{theorem}

\begin{proof}
  When $\sigma>1$, we have, by \eqref{eqn:II} on page \pageref{eqn:II},
  \begin{equation*}
    \upzeta(s)-\frac1{s-1}
    =\sum_{n\in\N}\frac1{n^s}-\int_1^{\infty}\frac{\dee x}{x^s}
    =\sum_{n\in\N}\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}
  
We now introduce the function $\Phi$, given on the half-plane
$\sigma>1$ by
\begin{equation*}
  \Phi(s)=\sum_p\frac{\log p}{p^s}.
\end{equation*}

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

\begin{proof}
  We already know from \eqref{eqn:zeta-prod}
  that $\upzeta$ is nonzero on
  $\sigma>1$.
  Therefore, on this domain,
  the logarithmic derivative $\upzeta'/\upzeta$ of $\upzeta$
  is holomorphic.
  From
  \begin{equation*}
    \log\upzeta(s)=\sum_p\log\bigl((1-p^{-s})\inv\bigr),
  \end{equation*}
  using $p^{-s}=\me^{-s\log p}$,
  we compute
  \begin{multline*}
    \frac{\upzeta'(s)}{\upzeta(s)}
    =\sum_p(1-p^{-s})(-1)(1-p^{-s})^{-2}p^{-s}\log p\\
    =-\sum_p\frac{\log p}{p^s(1-p^{-s})}
    =-\sum_p\frac{\log p}{p^s-1}.
  \end{multline*}
  Since
  \begin{equation*}
    \frac1{x-1}=\frac1x+\frac1{x(x-1)},
  \end{equation*}
  we compute now
  \begin{equation*}
    -\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{equation*}
  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*}
  Thus $\Phi$ extends \emph{meromorphically} to
  $\sigma>1/2$,
  as $\upzeta'/\upzeta$ does.
  Since $\upzeta$ has a pole of order $1$ at $1$ by Theorem \ref{thm:II},
  so does $-\upzeta'/\upzeta$, and its residue is $1$,
  by Theorem \ref{thm:res}.
  Then also $\Phi$ has at $1$ a pole of order $1$ and the residue $1$.
  Thus $\Phi(s)-(s-1)\inv$ is analytic at $1$
  as well as meromorphic on $\sigma\geq1$,
  and it will have poles only at zeroes of $\upzeta$.

  By the product formula \eqref{eqn:zeta-prod},
  $\upzeta$ has no zero when $\sigma>1$.
  Suppose if possible $\upzeta$ has a zero of order $\mu$ at $1+\mi a$.
  Then
  \begin{multline*}
      -\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*}
  Also, because of the pole and the residue at $1$,
  \begin{equation*}
1=\lim_{z\to0}z\Phi(z).    
  \end{equation*}
  Now, $\upzeta$ will have a zero of \emph{some} order $\nu$,
  possibly $0$, at $1+2\mi a$.
  Since
  \begin{equation*}
    \overline{\Phi(s)}=\Phi(\overline s),
  \end{equation*}
  so that
  \begin{equation*}
    2\Re(\Phi(s))=\Phi(s)+\Phi(\overline s),
  \end{equation*}
  we have,
    when $\epsilon$ is a small positive real number,
  \begin{multline}\label{eqn:286}
    \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}
  Also,
  \begin{multline*}
    \sum_{j=-2}^2\binom4{2+j}\Phi(1+j\mi a+\epsilon)\\
    =\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*}
  \begin{comment}
    \begin{multline*}
      0
      \leq\sum_p\frac{\log p}{p^{1+\epsilon}}
      \left(2\Re\Bigl(\frac1{p^{\mi a/2}}\Bigr)\right)^4\\
      \leq\sum_p\frac{\log p}{p^{1+\epsilon}}
      \left(\frac1{p^{\mi a/2}}+\frac1{p^{-\mi a/2}}\right)^4\\
      =\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*}
  \end{comment}
  In the limit at $\epsilon$,
  the product with $\epsilon$ of the sum in \eqref{eqn:286} is $-2\nu-8\mu+6$.
  Since this is not negative, $\mu$ must be $0$.
\end{proof}

The ``analytic theorem'' is the following;
we use it solely to derive Theorem \ref{thm:V}.

\begin{theorem}\label{thm:anal}
  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 \cite{MR602825}
  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}

The following is a straightforward theorem of calculus,
needing nothing special that we have done.
However, with Theorem \ref{thm:V},
it will allow us to refine Theorem \eqref{eqn:theta(x)x},
$\upvartheta(x)\asymp x$.

\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$ in $(1,\infty)$,
    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 -u}{u^2}\dee u>0,
    \end{equation*}
so
    $\int_1^x(f(t)-t)\dee t/t^2$
    has no limit as $x$ goes to $\infty$.
        \item
          Similarly, if for $\lambda$ in $(0,1)$,
    for arbitrarily large $x$,
    \begin{equation*}
      f(x)\leq\lambda x,
    \end{equation*}
    then for such $x$,
    \begin{equation*}
            \int_{\lambda x}^x\frac{f(t)-t}{t^2}\dee t
            \leq\int_{\lambda x}^x\frac{\lambda x-t}{t^2}\dee t
            =\int_{\lambda}^1\frac{\lambda -u}{u^2}\dee u<0,
    \end{equation*}
so again
 $\int_1^x(f(t)-t)\dee t/t^2$
    has no limit as $x$ goes to $\infty$.\qedhere
  \end{asparaenum}
\end{proof}

The final ingredient is the following,
which we obtain by refining the proof
of Chebyshev's Theorem, Theorem \ref{thm:C}
(page \pageref{thm:C}).

\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/2$, we have
  \begin{gather*}
      \upvartheta(x)\geq\sum_{x^{1-\epsilon}<p\leq x}\log(x^{1-\epsilon})
          \geq(1-\epsilon)(\uppi(x)-x^{1-\epsilon})\log x,\\
      \upvartheta(x)+(1-\epsilon)x\frac{\log x}{x^{\epsilon}}
      \geq(1-\epsilon)\uppi(x)\log x,\\
      \frac{\upvartheta(x)}{\uppi(x)\log x}
      +(1-\epsilon)\frac x{\uppi(x)\log x}\cdot\frac{\log x}{x^{\epsilon}}
      \geq1-\epsilon.
    \end{gather*}
While $x/\uppi(x)\log x$ is bounded above by Theorem \ref{thm:C},
    while $\log x\prec x^{\epsilon}$ by \eqref{eqn:log-prec},
when $x$ is large enough we have
    \begin{equation*}
      \frac{\upvartheta(x)}{\uppi(x)\log x}
       \geq1-2\epsilon.
    \end{equation*}
    Thus
    \begin{equation*}
      \liminf_{x\to\infty}\frac{\upvartheta(x)}{\uppi(x)\log x}\geq1.
    \end{equation*}
    With \eqref{eqn:theta>comp}, namely
    $\upvartheta(x)\leq\uppi(x)\log x$,
    we are done.
\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}
\begin{thebibliography}{10}

\bibitem{Ahlfors}
Lars Ahlfors.
\newblock {\em Complex Analysis}.
\newblock McGraw Hill, New York, second edition, 1966.

\bibitem{MR606931}
Harold Davenport.
\newblock {\em Multiplicative number theory}, volume~74 of {\em Graduate Texts
  in Mathematics}.
\newblock Springer-Verlag, New York-Berlin, second edition, 1980.
\newblock Revised by Hugh L. Montgomery.

\bibitem{Dickson-I}
Leonard~Eugene Dickson.
\newblock {\em History of the Theory of Numbers. {V}olume {I}: {D}ivisibility
  and Primality}.
\newblock Dover, Mineola, New York, 2005.
\newblock Unabridged republication of the work originally published as
  Publication Number 256 in Washington D.C. by the Carnegie Institute of
  Washington in 1919.

\bibitem{Erdos}
P.~Erd{\H o}s.
\newblock Beweis eines {S}atzes von {T}schebyschef (in {G}erman).
\newblock {\em Acta Litt. Sci. Szeged}, 5:194--198, 1932.
\newblock Available at \url{www.renyi.hu/~p_erdos/1932-01.pdf} (as of December
  3, 2010).

\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{MR0472307}
Morris Kline.
\newblock {\em Mathematical Thought from Ancient to Modern Times}.
\newblock Oxford University Press, New York, 1972.

\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{Mazur-Stein}
Barry Mazur and William Stein.
\newblock {\em Prime Numbers and the Riemann Hypothesis}.
\newblock Cambridge University Press (to appear), September 2015.
\newblock Draft at \url{wstein.org/rh/} as of December 29, 2015.

\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{Ramanujan}
Srinivasa Ramanujan.
\newblock A proof of {B}ertrand's postulate.
\newblock {\em Journal of the Indian Mathematical Society}, XI:181--2, 1919.
\newblock Available at
  \url{www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper24/page1.htm} (as of
  December 3, 2010).

\bibitem{MR0209411}
Michael Spivak.
\newblock {\em Calculus on manifolds. {A} modern approach to classical theorems
  of advanced calculus}.
\newblock W. A. Benjamin, New York--Amsterdam, 1965.

\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}
