Math539_Notes.tex

\documentclass[11pt]{article}
\usepackage{hyperref}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx} %\usepackage[pdftex]{graphicx}
\usepackage{xcolor}
\usepackage{setspace}
%\usepackage{tikz}


\setlength\parindent{0pt}

\newtheorem{thm}{Theorem}[subsection]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{exe}[thm]{Exercise}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{pty}[thm]{Property}
\newtheorem{remark}[thm]{Remark}
\newtheorem{obs}[thm]{Observation}
\newcommand{\The}[2]{\begin{#1}#2\end{#1}}

\newcommand{\ord}[0]{\text{ord}}

% notes
\iftrue
\newcommand{\f}[2]{\frac{#1}{#2}}
\newcommand{\re}[1]{\frac{1}{#1}}
\newcommand{\half}[0]{\frac{1}{2}}
\newcommand{\ift}[0]{It follows that}
\newcommand{\cp}[1]{\overline{#1}}
\newcommand{\Note}[0]{\noindent\textbf{Note: }}
\newcommand{\Claim}[0]{\noindent\textbf{Claim: }}
\newcommand{\Lemma}[1]{\noindent\textbf{Lemma #1}: } %
\newcommand{\Ex}[0]{\noindent\textbf{Example: }} %
\newcommand{\Special}[0]{\noindent\textbf{Special case: }} %
\newcommand{\solution}[2]{\item[]\proof[Solution to #1] #2 \qedhere}
\newcommand{\legendre}[2]{\left(\frac{#1}{#2}\right)}
\newcommand{\dent}[0]{\hspace{0.5in}}
\fi

\newcommand{\sm}[0]{\setminus}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\nl}[0]{\vspace{12pt}}
\newcommand{\rng}[2]{#1,\dots,#2}
\newcommand{\srng}[3]{#1_#2,\dots,#1_#3}
\newcommand{\st}[0]{\text{ such that }}
\newcommand{\et}[0]{\text{ and }}
\newcommand{\then}[0]{\text{ then }}
\newcommand{\forsome}[0]{\text{ for some }}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\s}[0]{\sigma}
\newcommand{\e}[0]{\varepsilon}
\newcommand{\om}[0]{\omega}
\newcommand{\Om}[0]{\Omega}
\newcommand{\la}[0]{\lambda}
\newcommand{\La}[0]{\Lambda}

% misc
\newcommand{\abs}[1]{\left\lvert#1\right\rvert} %
% lcm ???
\DeclareMathOperator{\lcm}{lcm}
% blackboard bold
\newcommand{\RR}{\mathbb{R}}
\newcommand{\FF}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
% mathcal
\newcommand{\m}[1]{\mathcal{#1}}
% vectors
\newcommand{\vvec}[1]{\textbf{#1}} %
\newcommand{\ii}[0]{\vvec{i}} %
\newcommand{\jj}[0]{\vvec{j}} %
\newcommand{\kk}[0]{\vvec{k}} %
\newcommand{\hvec}[1]{\hat{\textbf{#1}}} %
\newcommand{\cvec}[3]{ %column vector
    \ensuremath{\left(\begin{array}{c}#1\\#2\\#3\end{array}\right)}}
\newcommand{\pfrac}[2]{\frac{\partial#1}{\partial#2}} %
\newcommand{\norm}[1]{\left\lVert#1\right\rVert} %
% dotp roduct
\makeatletter
\newcommand*\dotp{\mathpalette\dotp@{.5}}
\newcommand*\dotp@[2]{\mathbin{\vcenter{\hbox{\scalebox{#2}{$\m@th#1\bullet$}}}}}
\makeatother
% divrg and curl
\newcommand{\divrg}[0]{\nabla\dotp} %
\newcommand{\curl}[0]{\nabla\times} %

\title{Math 539 Notes}
\author{Henry Xia}
%\date{15 September 2017}

\begin{document}

\maketitle

\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 01 07

\section{Introduction}

Motivating questions (some statistics):
\begin{itemize}
\item the ``probability'' that a random number has some property
\item the ``distribution'' of some given multiplicative/additive function
\end{itemize}

Idea: we can answer the question for $\set{1,...,\floor{x}}$ for some parameter $x$. Then,
take the limit $x\to\infty$ for all natural numbers.

\subsection{Notation}

Let $g(x)\ge0$.

\begin{defn}
$O(g(x))$ means some unspecified function $u(x)$ such that $\abs{u(x)}\le cg(x)$ for some
constant $c>0$.
\end{defn}

\begin{example}
Show that $e^{2x}-1=2x+O(x^2)$ for $x=[-1,1]$.
\end{example}
\proof
Observe that $f(z)=e^{2z}-1-2z$ is analytic (and entire) and has a double zero at $z=0$
(one can check that $f(z)=f'(z)=0$. Hence, $g(z)=(e^{2z}-1-2z)/z^2$ has a removable
singularity at $z=0$, whence $g$ is analytic and entire. Let
$C=\max\set{\abs{g(z)}:\abs{z}\le1}$. Then
\[
  \abs{g(z)}\le C \implies \abs{e^{2z}-1-2z} \le C\abs{z^2}
  \implies e^{2z}-1-2z = O(\abs{z}^2) .
\]
\qedhere

\begin{exe}
Show that $\sqrt{x+1}=\sqrt{x}+O(1/\sqrt{x})$ for $x\in[1,\infty)$.
\end{exe}

\begin{defn}
$f(x)\ll g(x)$ means $f(x)=O(g(x))$.
\end{defn}

\begin{exe}
Suppose that $f_1\ll g_1, f_2\ll g_2$, then $f_1+f_2\ll\max\set{g_1,g_2}$. \checkmark
\end{exe}

\begin{exe}
Let $f,g$ be continuous on $[0,\infty)$, and $f\ll g$ on $[123,\infty)$. Show that $f\ll g$
on $[0,\infty)$. \checkmark
\end{exe}

\begin{defn}
$f(x)\sim g(x)$ means $\lim\frac{f(x)}{g(x)}=1$.
\end{defn}

\begin{defn}
$f(x)=o(g(x))$ means $\lim\frac{f(x)}{g(x)}=0$.
\end{defn}

\begin{defn}
$f(x)=O_y(g(x))$ means $f,g$ depend on some parameter $y$, and the implicit constant
depends on $y$.
\end{defn}

\begin{exe}
For any $A,\epsilon>0$, show that $(\log x)^A \ll_{A,\epsilon} x^\epsilon$.
\end{exe}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 01 09

\subsection{Riemann-Stieltjes Integral}

Appendix A in the book.

\begin{defn}
Some definitions for partitions
\begin{enumerate}
\item Let $\underline{x}=\set{x_0,...,x_N}$ be a partition of $[c,d]$ if
$c=x_0<\cdots<x_N=d$.
\item The mesh size $m(\underline{x})=\max_{1\le j\le N} x_j-x_{j-1}$.
\item Sample points $\xi_j\in[x_{j-1},x_j]$.
\end{enumerate}
\end{defn}

\begin{defn}[Riemann-Stieltjes Integral]
Given two functions $f(x)$ and $g(x)$, define the Riemann-Stieltjes integral as
\[
  \int_c^df(x)~dg(x) = \lim_{m(\underline{x})\to0} \sum_{j=1}^N
  f(\xi_j)(g(x_j)-g(x_{j-1})) .
\]
\end{defn}

\begin{remark}
Setting $g(x)=x$ gives the Riemann integral.
\end{remark}

\begin{thm}
Let $f(x)$ have bounded variation and let $g(x)$ be continuous on $[c,d]$, or vice versa.
Then $\int_c^df(x)~dg(x)$ exists.
\end{thm}

\begin{remark}
If a function is piecewise monotone, then it has bounded variation.
\end{remark}

\begin{example}
Given a sequence ${a_n}_{n\in\NN}$, define the summatory function $A(x)=\sum_{n\le x}a_n$.
Then, on any $[c,d]$, $A(x)$ is bounded, piecewise continuous and piecewise monotone.
Hence, the Riemann-Stieltjes integral exists when $g$ is continuous.
\end{example}

\begin{remark}
We present 3 facts that we will use.
\begin{enumerate}
\item If $A(x)$ is the summatory function as above, and $f(x)$ is continuous, then
\[
  \int_c^d f(x) ~dA(x) = \sum_{c<n\le d} a_nf(n) .
\]
\item (Integration by parts). If the integrals exist, then
\[
  \int_c^d f(x) ~dg(x) = \left.f(x)g(x)\right|_c^d - \int_c^d g(x) ~df(x) .
\]
\item If $f(x)$ is continuously differentiable, then
\[
  \int_c^d g(x) ~df(x) = \int_c^d g(x)f'(x) ~dx .
\]
\end{enumerate}
\end{remark}

\begin{example}[Summation by parts]
Consider $\sum_{n\le y}\frac{a_n}n$. Let $f(x)=1/x$, then we can write
\begin{multline*}
\sum_{n\le y} \frac{a_n}n
= \sum_{n\le y} a_n\cdot\frac1n = \int_0^y \frac1x ~dA(x)
= \left.\frac1xA(x)\right|_0^y - \int_0^y A(x) ~d\left(\frac1x\right)
= \frac{A(y)}y - \int_0^y A(x)\frac1{x^2} ~dx .
\end{multline*}
The final manipulation that we want to get is
\begin{equation}
\sum_{n\le y} a_nf(n) = A(y)f(y) - \int_0^y A(x)f'(x) ~dx .
\label{summation by parts}
\end{equation}
\end{example}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 01 14

\section{Dirichlet Series}

A Dirichlet series is $\sum_{n=1}^\infty a_nn^{-s}$.

Facts about Dirichlet series:
\begin{itemize}
\item converge in some right half-plane $\set{s\in\CC:\Re s>R}$ for some $R$ (possibly
$R=\pm\infty$).
\item Sometimes converge conditionally. Example: $\sum_{n=1}^\infty(-1)^n/n^{1/2}$.
\item $\left(\sum_{n=1}^\infty a_nn^{-s}\right)\left(\sum_{n=1}^\infty b_nn^{-s}\right)
= \sum_{n=1}^\infty c_nn^{-s}$ where $c=\sum_{de=n}a_db_e=\sum_{d|n}a_db_{e/d}$.
(multiplicative convolution)
\end{itemize}

Some notation: for $s\in\CC$, we write $s=\sigma+it$, that is $\sigma$ is the real part of
$s$, and $t$ is the imaginary part of $s$. Note that if $x>0$, then
$\abs{x^s}=\abs{x^\sigma}\abs{x^{it}}=\abs{x^\sigma}\abs{e^{it\log{x}}}=\abs{x^\sigma}$.

\begin{thm}[thm 1.1]\label{thm:1.1}
Let $\alpha(s)=\sum_{n=1}^\infty a_nn^{-s}$ be a Dirichlet series. Suppose that
$s_0\in\CC$ is such that $\alpha(s_0)$ converges. Then $\alpha(s)$ converges uniformly in
the sector
\[
S=\set{s\in\CC:\sigma\ge\sigma_0,\abs{t-t_0}\le H\abs{\sigma-\sigma_0}}
\]
for any $H>0$.
\end{thm}

\proof
WLOG, let $s_0=0$, otherwise we can do a change of variables.

Let $A(x)=\sum_{n\le x}a_n=\alpha(0)-R(x)$. Then, for $\sigma>0$,
\begin{align*}
\sum_{M<n\le N}a_n n^s &= \int_M^N x^{-s} ~dA(x) = \int_M^N x^{-s} ~d(\alpha(0)-R(x)) \\
&= \int_M^N x^{-s} ~d\alpha(0) - \int_M^N x^{-s} ~dR(x) = -\int_M^N x^{-s} ~dR(x) \\
&= \left.-x^{-s}R(x)\right|_M^N + \int_M^N R(x) ~d(x^{-s}) \\
&= R(M)M^{-s} - R(N)N^{-s} - s\int_M^N R(x)x^{-s-1} ~dx .
\end{align*}
Note that $R(N)N^{-s}\to0$ as $N\to\infty$, and that $R(x)x^{-s-1}\ll x^{-\sigma-1}$.
Hence, letting $N\to\infty$ gives
\[
  \sum_{M<n}a_nn^{-s} = R(M)M^{-s} - s\int_M^\infty R(x)x^{-s-1} ~dx
  \to 0 \text{ as } M \to \infty .
\]

Now, choose $M$ large such that $\abs{R(x)}<\epsilon$ for all $x\ge M$. Then,
\begin{align*}
  \abs{\sum_{n>M}a_nn^{-s}}
  &\le \epsilon M^{-\sigma} + \abs{s}\int_M^\infty \epsilon x^{-\sigma-1} ~dx \\
  &= \epsilon M^{-\s} + \left.\abs{s}\epsilon x^{-\s} \frac1{-\s} \right|_M^\infty \\
  &= \epsilon M^{-\s} + \abs{s} \epsilon \frac{M^{-\s}}{\s}
  = \frac{\epsilon}{M^\s} \left(1 + \frac{\abs{s}}{\s}\right) .
\end{align*}

Since $s\in S$, we have
\[
  \abs{s} = \sqrt{\s^2+t^2} \le \sqrt{\s^2 + \abs{H\s}^2} = \s\sqrt{1+H^2} ,
\]
so $\abs{\sum_{n>M}a_nn^{-s}} \le \epsilon(1+\sqrt{1+H^2})$ as $M\to\infty$. Observe that
the latter only depends on $H$, so the convergence is uniform.
\qedhere

\begin{cor}
If $\alpha(s_0)$ converges, then $\alpha(s)$ converges for all $s$ with $\sigma>\sigma_0$.
\end{cor}

\begin{cor}
If $\alpha(s_0)$ diverges, then $\alpha(s)$ diverges for all $s$ with $\sigma<\sigma_0$.
\end{cor}

\begin{remark}
The Dirichlet series $\alpha(s)$ has an abscissa of convergence $\sigma_c$ such that
$\alpha(s)$ converges if $\sigma>\sigma_c$, and diverges if $\sigma<\sigma_c$. It is
allowed to have $\sigma_c=\pm\infty$. Furthermore, $\alpha(s)$ converges locally uniformly
right of $\sigma_c$ and each $a_nn^{-s}$ is analytic, whence $\alpha(s)$ is analytic.
(Conway; Theorem VII.2.1; p.147)
\end{remark}

\begin{remark}
Observe that $\int_1^N x^{-s} ~dA(x) = \sum_{1<n\le N}a_nn^{-s} = \sum_{n=2}^Na_nn^{-s}$.
Sometimes we write $\int_{-1}^N$ to include the 1.
\end{remark}

\begin{thm}[thm 1.3]\label{thm:1.3}
Let $\alpha(s)=\sum_{n=1}^\infty a_nn^{-s}$ have an abscissa of convergence $\s_c\ge0$.
Then for $\s>\s_c$, we have $\alpha(s)=s\int_1^\infty A(x)x^{-s-1} ~dx$.
Moreover,
\[
  \limsup_{x\to\infty} \frac{\log\abs{A(x)}}{\log x} = \s_c .
\]
\end{thm}

\proof
Observe that
\begin{align*}
  \sum_{n=1}^N a_nn^{-s} &= \int_{1^-}^N x^{-s} ~dA(x)
  = \left.x^{-s}A(x)\right|_{1^-}^N - \int_{1^-}^N A(x) ~d(x^{-s}) \\
  &= A(N)N^{-s} - \int_{1^-}^N A(x)(-sx^{-s-1} ~dx)
  = A(N)N^{-s} + s\int_1^N A(x) x^{-s-1} ~dx .
\end{align*}
Observe that in the last line, we can replace $1^-$ with $1$ because the integrand is
bounded.

Define $\phi=\limsup_{x\to\infty}\frac{\log\abs{A(x)}}{\log x}$. We compare this to $\s_c$.

Let $\s=\phi+\epsilon$ for some $\e>0$. Then $\frac{\log\abs{A(x)}}{\log x}<\phi+\frac\e2$
for large $x$, so $A(x)\ll x^{\phi+\e/2}$. Then, $A(N)N^{-s}\ll N^{\phi+\e/2}N^{-(\phi+\e)}
= N^{-\e/2}$. Hence,
\[
  \int_N^\infty A(x)x^{-\s-1} ~dx \ll \int_N^\infty x^{-\phi+\e/2}x^{-(\phi+\e+1)} ~dx
  = \int_N^\infty x^{-1-\e/2} ~dx \ll N^{-\e/2} .
\]
It follows that
\[
  \sum_{n=1}^N a_nn^{-s}
  = O(N^{-\e/2}) + s\left(\int_1^\infty A(x)x{-s-1} ~dx + O(N^{-\e/2})\right) .
\]
Let $N\to\infty$ gives $s\int_1^\infty A(x)x^{-s-1} ~dx$ converges. Hence
$\sigma_c\le\phi$.

Conversely, let $\s_0=\s_c+\e$, and let
$R_0(x)=\sum_{n>x}a_nn^{-\s_0}=\alpha(\s_0)-\sum_{n\le x}a_nn^{-\s_0}$. Observe that
\[
  A(N) = -R_0(N)N^{\s_0} + \s_0\int_0^NR_0(x)x^{\s_0-1} ~dx .
\]
Since $\alpha(0)$ converges, $R_0(x)=o(1)$ so $R_0(x)\ll1$. Then
\[
  A(N) \ll 1 \cdot N^{\s_0} + \s_0\int_0^N 1\cdot x^{\s_0-1} ~dx
  = N^{\s_0}+N^{\s_c} \ll N^{\s_0} = N^{\s_c+\e} .
\]
Hence $\frac{\log\abs{A(x)}}{\log x} \ll \frac{(\s_c+\e)\log x}{\log x} = \s_c+\e$, so
$\phi\le\s_c+\e$. Take $\e\to0$, so $\phi\le\s_c$.
\qedhere


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 01 16

\begin{defn}
The abscissa of absolute convergence is
$\s_a=\inf\set{\s\in\RR:\sum_{n=1}^\infty\abs{a_n}n^{-\s}\text{ converges}}$.
\end{defn}

\begin{example}
Let $\eta(s)=\sum_{n=1}^\infty(-1)^{n-1}n^{-s}$. Observe that $\s_c=0$ by the alternating
series test. However, we only have absolute convergence when $\s>1$, so the abscissa of
absolute convergence is $\s_a=1$.
\end{example}

\begin{remark}
When $a_n\ge0$ for all $n\in\NN$, we have $\s_c=\s_a$.
\end{remark}

\begin{thm}[thm 1.4]\label{thm:1.4}
For any Dirichlet series $\alpha(s)$, we have $\s_c\le\s_a\le\s_c+1$.
\end{thm}
\proof
The first inequality is trivial.

Let $\s=\s_c+1+\e$ where $\e>0$. We show that $\alpha(\s)$ converges absolutely. Note that
$\alpha(s)$ converges at $s=\s_c+\e/2$, that is
\[
  a_nn^{-(\s_c+\e/2)} = o(1) \implies a_nn^{-(\s_c+\e/2)} \ll 1 .
\]
Then,
\[
  \sum_{n=1}^\infty\abs{a_n}n^{-(\s_c+1+\e)}
  = \sum_{n=1}^\infty\abs{a_nn^{-(\s_c+\e/2)}}n^{-(1+\e/2)}
  \ll \sum_{n=1}^\infty n^{-(1+\e/2)} \ll 1 .
\]
It follows that $\alpha(\s)$ converges absolutely for all $\e>0$.
\qedhere

\begin{thm}[Landau's Theorem (thm 1.7)]\label{thm:1.7}
Let $\alpha(s)=\sum_{n=1}^\infty a_nn^{-s}$ with $\s_c<\infty$. If $a_n\ge0$ for each
$n\in\NN$. Then, $\alpha(s)$ has a singularity at $s=\s_c$.
\end{thm}
\proof
Suppose that there does not exist a singularity at $s=\s_c$. Then, there exists an analytic
continuation of $\alpha$ to $C=\set{s\in\CC:\abs{s-\s_c}<\delta}$.

Let $z=\s_c-\frac14\delta$ and let $w=\s_c+\frac34\delta$. Let
$D=\set{s\in\CC:\abs{s-w}<\frac54\delta}$. Observe that $D\subset C\cup\set{s\in\CC:\s>0}$,
so $\alpha$ has an analytic continuation to $D$. Let $P(s)$ be the power series of $\alpha$
centered at $w$. Observe that $z\in D$, so it suffices to show that $P(z)=\alpha(z)$,
whence we contradict the assumption that the abscissa of convergence is $\s_c$. Note that
\begin{align*}
P(z) &= \sum_{k=0}^\infty \frac{\alpha^{(k)}(w)}{k!} (z-w)^k \\
&= \sum_{k=0}^\infty \frac{1}{k!}(z-w)^k \sum_{n=1}^\infty a_n(-\log n)^k n^{-w}
~~~~~~~\text{we can differentiate termwise for }\alpha^{(k)}(w) \\
&= \sum_{k=1}^\infty \frac{1}{k!}(w-z)^k \sum_{n=1}^\infty a_n(\log n)^k n^{-w}
~~~~~~~\text{where the terms are all nonnegative} \\
&= \sum_{n=1}^\infty a_nn^{-w} \sum_{k=1}^\infty \frac{1}{k!}(w-z)^k(\log n)^k \\
&= \sum_{n=1}^\infty a_nn^{-w} e^{(w-z)\log n} = \sum_{n=1}^\infty a_nn^{-z} .
\end{align*}
It follows that $\alpha(z)$ converges left of $\s_c$, which is a contradiction.
\qedhere


% TODO @ sec 1.3 of text on multiplicative stuff
\subsection{Dirichlet convolutions}

Motivating question: are these calculations legitimate?
\begin{itemize}
\item $\zeta(s)^2 = \sum_{l,m=1}^\infty (lm)^{-s} = \sum_{n=1}^\infty d(n)n^{-s}$.
\item $\zeta(s) = \prod_{p\text{ prime}}(1+p^{-s}+p^{-2s}+\cdots) = \prod_{p\text{ prime}}
(1-p^{-s})^{-1}$ .
\end{itemize}

\begin{defn}
  Let $a=\set{a_n}$, $b=\set{b_n}$ be sequences. The Dirichlet/multiplicative convolution
  $a*b$ by $c=\set{c_n}$ where $c_n = \sum_{de=n}a_db_e = \sum_{d|n}a_db_{n/d}$.
\end{defn}

\begin{thm}[thm 1.8]\label{thm:1.8}
Let $\alpha(s)=\sum_{n=1}^\infty a_nn^{-s}$, let $\beta(s)=\sum_{n=1}^\infty b_nn^{-s}$,
and let $\gamma(s)=\sum_{n=1}^\infty c_nn^{-s}$. If $s\in\CC$ is such that $\alpha(s)$ and
$\beta(s)$ converge absolutely, and if $c=a*b$, then $\gamma(s)$ converges absolutely and
$\gamma(s)=\alpha(s)\beta(s)$.
\end{thm}

\begin{example}
Observe that $d(n)=(1*1)(n)$.
\end{example}

\begin{example}
Let $M(s)=\sum_{n=1}^\infty\mu(n)n^{-s}$, where $\mu$ is the M\"obius function which
defined as
\[
  \mu(n) = \begin{cases}
  0 &\text{if } n \text{ is not square free} \\
  1 &\text{if } n \text{ has an even number of prime divisors} \\
  -1 &\text{if } n \text{ has an odd number of prime divisors}
  \end{cases} .
\]
Equivalently, we can define $\mu$ as the function that satisfies
\[
  \sum_{d|n}\mu(d) = \begin{cases}
  1 &\text{if } n = 1 \\
  0 &\text{if } n > 1
  \end{cases} .
\]
Observe that $M(s)\zeta(s) = \sum_{n=1}^\infty(\mu*1)(n)n^{-s} = 1$ for $\s>1$, since
$(\mu*1)(n)=\sum_{d|n}\mu(d)$. It follows that $M(s)=1/\zeta(s)$.

Since the abscissa of convergence of $M$ is $\s_c=1$, we get that $\zeta(s)$ has no zeroes
when $\s>1$.
\end{example}

\begin{example}[M\"obius Inversion Formula]
Write $F(s)=\sum_{n=1}^\infty f(n)n^{-s}$ and $G(s)=\sum_{n=1}^\infty g(n)n^{-s}$. Then
\begin{align}
F(s)\zeta(s) = G(s) &\iff F(s) = \frac{G(s)}{\zeta(s)} = G(s)M(s) \notag \\
(f*1)(n) = g(n) &\iff f(n) = (g*\mu)(n) \notag \\
\sum_{d|n} f(n) = g(n) &\iff f(n) = \sum_{d|n} g(d)\mu\left(\frac{n}{d}\right) .
\label{mobius inversion formula}
\end{align}
\end{example}

\begin{example}
It is known that $\sum_{d|n}\phi(d)=n$. This gives $(\phi*1)(n)=\sum_{d|n}\phi(d)=n$. Then,
for $\s>2$, we have
\[
\left(\sum_{n=1}^\infty \phi(n)n^{-s}\right) \left(\sum_{n=1}^\infty n^{-s}\right)
= \sum_{n=1}^\infty n\cdot n^{-s} = \zeta(s-1) .
\]
This gives $\sum_{n=1}^\infty\phi(n)n^{-s}=\zeta(s-1)/\zeta(s)$.
\end{example}

\begin{exe}
Let $\sigma_1(n)=\sum_{d|n}d$. Show that
$\sum_{n=1}^\infty\sigma_1(n)n^{-s}=\zeta(s-1)\zeta(s)$.
\end{exe}

\begin{defn}
A function $f$ is multiplicative if $f(m)f(n)=f(mn)$ if $\gcd(m,n)=1$.
\end{defn}

\begin{defn}
A number $n$ is $y$-friable if $p\mid n \implies p\le y$.
\end{defn}

\begin{thm}[thm 1.9]\label{thm:1.9}
Let $f$ be a multiplicative function, and let $F(s)=\sum_{n=1}^\infty f(n)n^{-s}$. If
$\sum_{n=1}^\infty\abs{f(n)}n^{-\s}$ converges, we have the Euler product
\[
  F(s) = \prod_{p\text{ prime}} (1 + f(p)p^{-s} + f(p^2)p^{-2s} + \cdots) .
\]
\end{thm}
\proof
Let $\s>\s_a$. Then, for all $p$, we have
\[
\abs{1 + f(p)p^{-s} + f(p^2)p^{-2s} + \cdots}
\le 1 + \abs{f(p)}p^{-s} + \abs{f(p)}p^{-2s} + \cdots
\le \sum_{n=1}^\infty \abs{f(n)}n^{-s} .
\]
Since the above converges, we can rearrange the finite product
\[
\prod_{p\le y} (1 + f(p)p^{-s} + f(p^2)p^{-2s} + \cdots)
= \sum_{n~y\text{-friable}} f(n)n^{-s} .
\]
Now, we can compute
\begin{align*}
\abs{F(s) - \prod_{p\le y} (1 + f(p)p^{-s} + f(p^2)p^{-2s} + \cdots)}
&= \abs{F(s) - \sum_{n~y\text{-friable}} f(n)n^{-s}} \\
&= \abs{\sum_{n~\text{not}~y\text{-friable}} f(n)n^{-s}} \\
&\le \sum_{n>y} \abs{f(n)}n^{-s} = o(1) .
\end{align*}
The tail goes to 0, so the theorem is proved.
\qedhere

\begin{remark}
Almost the same proof shows that the Euler product converges absolutely. In particular, it
is nonzero (unless an individual factor is zero). Note that the convergence of a product is
defined as the convergence of the sum of logs.
\end{remark}

\begin{example}
Note that $\mu$ is multiplicative, so $M(s)=\prod_{p\text{ prime}}(1-p^{-s})$.
\end{example}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 01 21

\begin{pty}
If $f$ and $g$ are multiplicative, then $f*g$ is also multiplicative (If $F(s)$ and $G(s)$
have Euler products, the $F(s)G(s)$ also has an Euler product).
\end{pty}

\begin{pty}
Dirichlet convolutions are associative, that is $(f*g)*h = f*(g*h)$.
\end{pty}

\begin{defn}
Let $\om(n)$ be the number of distinct prime factors of $n$.
\end{defn}

\begin{defn}
Let $\Om(n)$ be the number of prime factors of $n$ counting with multiplicity.
\end{defn}

\begin{defn}[Liouville lambda function]
Let $\la(n)=(-1)^{\Om(n)}$. Note that $\la(n)=\mu(n)$ if and only if $n$ is squarefree.
\end{defn}

\begin{example}
Find an Euler product for $L(s)=\sum_{n=1}^\infty\la(n)n^{-s}$.

\emph{Solution}:
First, note that $\la(n)$ is totally multiplicative, that is $\la(mn)=\la(m)\la(n)$ for all
$m,n\in\NN$ (not just when $(m,n)=1$). Also, $\sum_{n=1}^\infty\abs{\la(n)n^{-s}} =
\sum_{n=1}^\infty n^{-\s}$ converges when $\s>1$. So, for $\s>1$, by theorem \ref{thm:1.9},
\begin{align*}
L(s) &= \prod_{p~\text{prime}} \left(1 + \la(p)p^{-s} + \la(p^2)p^{-2s} + \cdots \right) \\
&= \prod_{p~\text{prime}} \left(1 - p^{-s} + p^{-2s} - \cdots \right) \\
&= \prod_{p~\text{prime}} \left(1+p^{-s}\right)^{-1} .
\end{align*}
\end{example}

\begin{exe}
Show that $L(s) = \frac{\zeta(2s)}{\zeta(s)}$.
\end{exe}

\begin{remark}
If $f(n)$ is totally multiplicative, then
\begin{align*}
\sum_{n=1}^\infty f(n)n^{-s}
&= \prod_p \left(1 + f(p)p^{-s} + f(p^2)p^{-2s} + \cdots \right) \\
&= \prod_p \left(1 + f(p)p^{-s} + f(p)^2p^{-2s} + \cdots \right) \\
&= \prod_p \left(1 - f(p)p^{-s} \right) ^{-1} .
\end{align*}
\end{remark}

\begin{defn}[von Mangoldt Lambda function]
Define the von Mangoldt Lambda function as
\[
  \La(n) = \begin{cases}
    \log p &n=p^r \text{ for some prime } p \\
    0 &\text{otherwise}
  \end{cases} .
\]
\end{defn}

\begin{remark}
Recall that $\zeta(s)=\prod_p(1-p^{-s})^{-1}$ for $\s>1$, so we can take logarithms.
\[
\log \zeta(s) = \sum_p \log (1-p^{-s})^{-1}
= \sum_p \left(p^{-s} + \frac12 p^{-2s} + \frac13 p^{-3s} + \cdots \right) .
\]
This is a Dirichlet series which we can differentiate term by term, hence
\begin{align*}
\frac{\zeta'(s)}{\zeta(s)}
&= \frac{d}{ds} \sum_p\left(p^{-s}+\frac12p^{-2s}+\frac13p^{-3s}+\cdots\right) \\
&= \sum_p\left((-\log p)p^{-s} + \frac12(-2\log p)p^{-2s} + \cdots \right) \\
&= -\sum_{n=1}^\infty \La(n)n^{-s} .
\end{align*}
\end{remark}

\subsection{Meromorphic continuation of $\zeta(s)$}

\begin{example}
We prove that $\eta(s)=(1-2^{1-s})\zeta(s)$ in two different ways (for $\s>1$).
\proof[Proof 1]
For $\s>1$, $\eta(s)$ converges absolutely, so
\begin{align*}
\eta(s)
&= 1^{-s} + (2^{-s}-2\cdot 2^{-s}) + 3^{-s} + (4^{-s}-2\cdot 4^{-s}) + \cdots \\
&= (1^{-s} + 2^{-s} + 3^{-s} + \cdots) - 2(2^{-s} + 4^{-s} + \cdots) \\
&= \zeta(s) - 2\cdot 2^{-s} \zeta(s) \\
&= (1-2^{1-s})\zeta(s) .
\end{align*}
\proof[Proof 2]
Note that $(-1)^{n-1}$ is multiplicative, and its value at $p^r$ equals $-1$ if $p=2$ and
$1$ if $p\ge3$. Thus,
% TODO TODO TODO TODO
% TODO TODO TODO TODO
% TODO TODO TODO TODO
% TODO TODO TODO TODO
\end{example}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 01 23

Note that $\zeta(s)=(1-2^{1-s})^{-1}\eta(s)$, and $\eta(s)$ converges when $\s>0$. Hence,
this is a meromorphic continuation of $\zeta(s)$ to $\s>0$. Note that
$(1-2^{1-s})^{-1}\eta(s)$ has singularities when $1-2^{1-s}=0$, that is $s=1+\frac{2\pi
i}{\log2}$.

\begin{exe}
Show that $\zeta(s)$ has a simple pole at $s=1$ with residue 1.
\end{exe}

\begin{thm}[thm 1.12]\label{thm:1.12}
For $\s>0$ and $s\neq1$, we can write
\begin{equation}
\zeta(s) = \sum_{n\le x}n^{-s} + \frac{x^{1-s}}{s-1} + \frac{\{x\}}{x^s}
- s \int_x^\infty \{u\}u^{-s-1} ~du .
\label{zeta improper integral}
\end{equation}
\end{thm}
\proof
For $\s>1$, we have
\begin{align*}
\sum_{n>x}n^{-s} &= \int_x^\infty u^{-s}~d\left(\floor{u}\right) \\
&= \int_x^\infty u^{-s}~du - \int_x^\infty u^{-s}~d\left(\{u\}\right) \\
&= \left. \frac{u^{1-s}}{1-s}\right|_x^\infty
- \left(\left.\{u\}u^{-s}\right|_x^\infty - \int_x^\infty\{u\}~d(u^{-s})\right) \\
&= \frac{x^{1-s}}{s-1} + \frac{\{x\}}{x^s} - s \int_x^\infty \{u\} u^{-s-1} ~du .
\end{align*}
Let $\e>0$, then for $\s>\e$, we have
\[
\abs{\int_x^\infty \{u\}u^{-s-1} ~du}
\le \int_x^\infty 1\cdot u^{-\s-1} ~du
= \frac{x^{-\s}}{\s} .
\]
Note that this is uniform for $\s>\e$, so we have analyticity. Then, we conclude that the
equation \ref{zeta improper integral} holds for all $\s>0$ by the uniqueness of analytic
continuation.
\qedhere

\begin{remark}
We can use a similar method to show that $\zeta(s)$ is defined for all $s\in\CC\sm\set{1}$.
\end{remark}

\begin{cor}
When $x=1$, we have
\[
\zeta(s) = 1 + \frac1{s-1} - s\int_1^\infty \{u\}u^{-s-1} ~du ,
\]
so $\zeta(s)-\frac1{s-1}$ has a removable singularity at $s=1$ with value
\[
C_0 = 1 - \int_1^\infty \{u\} u^{-2} ~du .
\]
Then, by DCT, we get $\zeta(s)=\frac1{s-1}+C_0 + O(\abs{s-1})$.
\end{cor}

\begin{cor}
We can rearrange to get
\begin{align*}
\sum_{n\le x}n^{-s}
&= \zeta(s) - \frac{x^{1-s}}{s-1} - \frac{\{x\}}{x^s} + s\int_x^\infty\{u\}u^{-s-1}~du \\
&= \zeta(s) + \frac{x^{1-s}}{1-s}
+ O\left(\frac1{x^\s}+\abs{s}\int_x^\infty1\cdot u^{-\s-1}~du\right) \\
&= \zeta(s) + \frac{x^{1-s}}{1-s}
+ O\left(\frac1{x^\s}+\frac{\abs{s}}\s\frac1{x^\s}\right) .
\end{align*}
Hence, we get asymptotics for $\sum_{n\le x}n^{-\alpha}$.
\[
\sum_{n\le x}\frac1{n^\alpha} = \begin{cases}
O(x^{1-\alpha}) &\text{if }0<\alpha<1 \\
\zeta(\alpha)+O(x^{1-\alpha}) &\text{if }\alpha>1
\end{cases} .
\]
\end{cor}

\begin{cor}
Let $s=1$, then
\begin{align*}
\sum_{n\le x}\frac1n &= \int_{1^-}^x\frac1t~d\floor{t}
= \int_{1^-}^x\frac1t~dt - \int_{1^-}^x\frac1t~d\{t\} \\
&= \log x - \left.\frac{\{t\}}t\right|_{1^-}^x + \int_1^x\{t\}\frac1{t^2}~dt \\
&= \log x - \frac{\{x\}}x + 1 - \int_1^x\{t\}\frac1{t^2}~dt \\
&= \log x + 1-\int_1^\infty\{t\}t^{-2}~dt + \int_x^\infty\{t\}t^{-2}~dt - \frac{\{x\}}x \\
&= \log x + C_0 + O\left(\frac1x\right) .
\end{align*}
Note that an error of $1/x$ is the best approximation with a smooth function (because we
can't get better than the jumps).
\end{cor}

\begin{remark}
Note that $C_0$ is Euler's constant, that is
\[
C_0 = \lim_{x\to\infty}\left(\sum_{n\le x}\frac1n - \log x\right) \approx 0.577 .
\]
\end{remark}


\section{Elementary Estimates for Arithmetic Functions}

Motivating question: what is the expectation of $\frac{\phi(n)}n$?

Note that $(\phi*1)(n)=n$, so by M\"obius inversion,
\[
\phi(n) = \sum_{d|n}\mu(d)\frac{n}d
\implies
\frac{\phi(n)}n = \sum_{d|n}\frac{\mu(d)}{d} .
\]
Then, we get
\[
\sum_{n\le x}\frac{\phi(n)}n
= \sum_{n\le x}\sum_{d|n} \frac{\mu(d)}d
= \sum_{d\le x}\frac{\mu(d)}d\floor{\frac{x}d}
= \sum_{d\le x}\frac{\mu(d)}d \left(\frac{x}{d}+O(1)\right) .
\]
Hence, dividing by $x$ gives
\begin{align*}
\frac1x\sum_{n\le x}\frac{\phi(n)}n
&= \sum_{d\le x}\frac{\mu(d)}{d^2}
+ O\left(\frac1x\sum_{d\le x}\abs{\frac{\mu(d)}{d}}\right) \\
&= \sum_{d=1}^\infty\frac{\mu(d)}{d^2}
+ O\left(\sum_{d>x}\abs{\frac{\mu(d)}{d^2}} + \frac1x\sum_{d\le
x}\abs{\frac{\mu(d)}d}\right) \\
&= \frac1{\zeta(2)} + O\left(\sum_{d>x}\frac1{d^2}+\frac1x\sum_{d\le x}\frac1d\right) \\
&= \frac1{\zeta(2)} + O\left(\frac{\log x}x\right) .
\end{align*}

\begin{example}
Estimate the number of square-free numbers up to $x$. Let $Q(x)=\sum_{n\le x} \mu(n)^2$.
Note that $\mu(n)^2$ is the indicator function for square-free numbers.
\end{example}

\begin{lemma}
Define $g(d)$ as
\[
g(d) = \begin{cases}
\mu(m) &\text{if }d=m^2\text{ for some }m\in\NN \\
0 &\text{if }d\text{ is not a square}
\end{cases} .
\]
Then $\mu^2=1*g$.
\end{lemma}
\proof[Proof 1]
Let $k^2$ be the largest square divisor of $n$. Then
\begin{align*}
\mu(n)^2 &= \begin{cases}
1 &\text{if }k=1 \\
0 &\text{if }k>1
\end{cases} \\
&= \sum_{d|k}\mu(d)
= \sum_{\substack{d|n\\d=m^2}}\mu(m)
= \sum_{d|n} g(d) .
\end{align*}
\qedhere

\begin{exe}[Proof 2]
Show that $\sum_{n=1}^\infty\mu(n)^2n^{-s}=\frac{\zeta(s)}{\zeta(2s)}$ and
$\sum_{n=1}^\infty g(n)n^{-s}=\frac1{\zeta(2s)}$.
\end{exe}

\begin{exe}[Proof 3]
Show that $\mu(n)^2=\sum_{d|n}g(d)$ by M\"obius inversion, along with the fact that every
$n\in\NN$ can be uniquely written as $n=a^2b$ where $b$ is square-free.
\end{exe}

We can approximate $Q(x)$ as follows.
\begin{align*}
Q(x) &= \sum_{n\le x}\mu(n)^2
= \sum_{n\le x}\sum_{d|n}g(d)
= \sum_{d\le x}g(d)\left(\frac{x}{d}+O(1)\right)
= x\sum_{d\le x}\frac{g(d)}d + O\left(\sum_{d\le x}\abs{\frac{g(d)}d}\right) \\
&= x\sum_{m\le\sqrt x}\frac{\mu(m)}{m^2} + O\left(\sum_{m\le\sqrt{x}}\abs{\mu(m)}\right)
~~~~~\text{by the definition of }g \\
&= x\left(\frac1{\zeta(2)} + O\left(\frac1{\sqrt x}\right)\right) + O(\sqrt x) \\
&= \frac{x}{\zeta(2)} + O(\sqrt x)
\end{align*}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 01 28

\begin{defn}
The density of $A\subset\NN$ is
\[
\delta(A) = \lim_{x\to\infty} \frac1x \#\set{n\le x: n\in A} .
\]
\end{defn}

\begin{exe}
Show $\forall y\ge1$ that
\[
\#\set{n\le x:p\le y\implies p^2\nmid n}
= x\prod_{p\le y}\left(1-\frac1{p^2}\right) + O_y(1) .
\]
\end{exe}

The general method we get from the above is as follows. Let $A(x)=\sum_{n\le x} a_n$ and
$B(x)=\sum_{n\le x} b_n$. Define $c=a*b$ and $C(x)=\sum_{n\le x} c_n$. Then,
\begin{align*}
C(x) &= \sum_{n\le x} \sum_{d|n} a_d b_{n/d}
= \sum_{d\le x} \sum_{\substack{n\le x\\d|n}} a_d b_{n/d} \\
&= \sum_{d\le x} a_d \sum_{l\le x/d} b_l
= \sum_{d\le x} a_d B\left(\frac{x}{d}\right) .
\end{align*}

\begin{example}
\label{ex.hyperbola}
Let $a_n=b_n=1$ and $c_n=d(n)$. Then,
\begin{align*}
\sum_{n\le x} d(n) = C(x) &= \sum_{d\le x} a_d B\left(\frac{x}{d}\right) \\
&= \sum_{n\le x} \floor{\frac{x}{d}}
= \sum_{d\le x}\left(\frac{x}{d} + O(1)\right)
= x \sum_{d\le x} \frac1d + O(x) \\
&= x\left(\log x + C_0 + O\left(\frac1x\right)\right) + O(x)
= x\log x + O(x) .
\end{align*}
\end{example}

\begin{remark}
Note that
\[
x\log x - x = \int_1^x\log t ~dt
< \sum_{n\le x} \log n
< \int_1^{x+1}\log t ~dt
= (x+1)\log(x+1) - (x+1) .
\]
\end{remark}

\begin{exe}
For $x\ge2$, we have $\sum_{n\le x}\log x = x\log x-x+O(\log x)$.
\end{exe}

Then, $\sum_{n\le x}d(n) \sim x\log x \sim \sum_{n\le x}\log n$, so we say $d(n)$ has
average order $\log n$.

Note that example \ref{ex.hyperbola} does not give a very good error term. This is because
$B\left(\frac{x}{d}\right)$ gives a poor approximation when $x/d$ is small. Instead, we can
use Dirichlet's Hyperbola Method:
\begin{equation}
C(x) = \sum_{d\le y} a_d B\left(\frac{x}{d}\right)
+ \sum_{l\le x/y} b_l A\left(\frac{x}{l}\right)
- A(y)B\left(\frac{x}{y}\right) .
\end{equation}

Now we can improve example \ref{ex.hyperbola} as follows.
\begin{align*}
\sum_{n\le x} d(n) &= \sum_{d\le y} \floor{\frac{x}{d}}
+ \sum_{l\le x/y} \floor{\frac{x}{l}}
- \floor{y}\floor{\frac{x}{y}} \\
&= x\left(\log y+C_0+O\left(\frac1y\right)\right) + O(y)
+ x\left(\log\frac{x}{y} + C_0 + O\left(\frac{y}{x}\right)\right)
+ O\left(\frac{x}{y}\right) \\
&\hspace{36pt}- y\frac{x}{y} + O(y) + O\left(\frac{x}{y}\right) + O(1) \\
&= x\log x + (2C_0-1)x + O\left(y+\frac{x}{y}\right) \\
&= x\log x + (2C_0-1)x + O\left(\sqrt x\right) .
\end{align*}

\subsection{Prime number estimates}

We can think of the von Mangoldt Lambda function as a prime indicator function because
proper prime powers are rare, so they should not influence the main term. Let
$\Psi(x)=\sum_{n\le x}\La(n)$. Note that the Prime Number Theorem is equivalent to
\[
\Psi(x)\sim x .
\]

Recall that $\Psi(s)=-\frac{\zeta'(s)}{\zeta(s)}$. Since
$-\frac{\zeta'}{\zeta}(s)\zeta(s)=-\zeta'(s)$, we get
\[
\La*1 = \log \implies \La=\log*\mu
\implies \La(n) = \sum_{d|n}\mu(d)\log\left(\frac{n}{d}\right) .
\]

\begin{exe}
Show that $\La(n)=-\sum_{d|n}\mu(d)\log(d)$.
\end{exe}

Note that for $x\ge2$, we get
\begin{align}
\sum_{n\le x} \log n &= \sum_{n\le x} \sum_{d|n} \La(d)
= \sum_{d\le x} \La(d)\floor{\frac{x}{d}}
 \label{1840cheby1} \\
\sum_{n\le x} \log n &= x\log x - x + O(\log x) .
 \label{1840cheby2}
\end{align}
Call these two equations $[x]$. Now, replace $x$ with $x/2$ in $[x]$ and call it $[x/2]$.
Let $E(t)=\floor{t}-2\floor{t/2}$. Taking $[x]-2[x/2]$ gives
\begin{align*}
\text{LHS:}&~~~~~
(x\log x - x + O(\log x)) - 2\left(\frac{x}2\log\frac{x}2 - \frac{x}2 + O(\log x)\right)
= (\log2)x + O(\log x) \\
\text{RHS:}&~~~~~
\sum_{d\le x}\La(d)\floor{x}{d} - 2\sum_{d\le x}\La(d)\floor{\frac{x}{2d}}
= \sum_{d\le x} \La(d)E\left(\frac{x}{d}\right) .
\end{align*}
This gives the bounds
\[
\Psi(x)-\Psi\left(\frac{x}{2}\right)
= \sum_{\frac{x}{2}\le d\le x} \La(d)
\le \sum_{d\le x} \La(d)E\left(\frac{x}{d}\right)
\le \sum_{d\le x} \La(d) = \Psi(x) .
\]
Immediately we get
\begin{equation}
\Psi(x)\ge\sum_{d\le x}\La(d)E\left(\frac{x}{d}\right)
= (\log2)x + O(\log x) .
\end{equation}
With some calculation, we get
\begin{align}
\Psi(x) &= \left(\Psi(x)-\Psi\left(\frac{x}{2}\right)\right)
+ \left(\Psi\left(\frac{x}{2}\right)-\Psi\left(\frac{x}{4}\right)\right) + \cdots \notag \\
&\le \left((\log2)x+O(\log x)\right) + \left((\log2)\frac{x}{2}+O(\log x)\right) + \cdots
\notag \\
&= (2\log2)x + O\left(\log^2(x)\right)
\end{align}

Chebyshev took $[x]-[x/2]-[x/3]-[x/5]+[x/30]$ to get the bounds
\[
0.9212x + O(\log x) \le \Psi(x) \le 1.1056x + O(\log^2 x) .
\]

\begin{defn}
We write $f\asymp g$ if $f\ll g$ and $g\ll f$. We say ``$f$ is of the same order of
magnitude as $g$''.
\end{defn}

Therefore, $\Psi(x) \asymp x$.

\begin{exe}[a weak version of Bertrand's Postulate]
Note that $\sum_{x<n\le 2x}\La(n) = \Psi(2x)-\Psi(x)\gg x$. Then,
\[
\#\set{p:x<p\le 2x} \gg \frac{x}{\log x} .
\]
\end{exe}

\begin{thm}[Mertens] \label{thm:2.7}
For $x\ge2$,
\begin{enumerate}
\item $\sum_{n\le x}\frac{\La(n)}{n} = \log x + O(1)$.
\item $\sum_{p\le x}\frac{\log p}{p} = \log x + O(1)$.
\item $\sum_{p\le x}\frac1p = \log\log x + b + O\left(\frac1{\log x}\right)$.
\item $\prod_{p\le x}\left(1-\frac1p\right)^{-1} = e^c\log x + O(1)$.
\end{enumerate}
\end{thm}

\proof[Proof of (a)]
Note that equations \ref{1840cheby1} and \ref{1840cheby2} give
\begin{align*}
x\log x + O(x) &= \sum_{d\le x}\La(d)\floor{\frac{x}d}
= x\sum_{d\le x}\frac{\La(d)}d + O\left(\sum_{d\le x}\La(d)\right) \\
&= x\sum_{d\le x}\frac{\La(d)}d + O(x) .
\end{align*}
Dividing by $x$ gives the desired result.
\qedhere

\proof[Proof of (b)]
Note that
\begin{align*}
\sum_{n\le x}\frac{\La(n)}n - \sum_{p\le x} \frac{\log p}p
&= \sum_{\substack{p^r\le x\\r\ge2}} \frac{\log p}{p^r}
\le \sum_{p\le x} \log p \sum_{r=2}^\infty \frac1{p^r} \\
&= \sum_{p\le x}(\log p)\cdot\frac{1}{p(p-1)}
\ll \sum_{p=1}^\infty \frac{p^\e}{p^2} = O(1) .
\end{align*}
\qedhere

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 01 30

\proof[Proof of (d)]
Write $R(x)=\sum_{p\le x}\frac{\log p}p-\log x$, so $R(x)\ll1$ and $R(2^-)=-\log2$. Then,
\begin{align*}
\sum_{p\le x}\frac1p
&= \int_{2^-}^x \frac1{\log u} ~d\left(\sum_{p\le u}\frac{\log p}p\right) \\
&= \int_{2^-}^x \frac1{\log u} ~d(\log u) + \int_{2^-}^x\frac1{\log u} ~dR(u) \\
&= \int_{2^-}^x \frac1{u\log u} ~du + \left.\frac{R(u)}{\log u}\right|_{2^-}^x
- \int_{2^-}^x R(u) ~d\left(\frac1{\log u}\right) \\
&= \left.\log\log u\right|_{2^-}^x + \frac{R(x)}{\log x} - \frac{R(2^-)}{\log2}
+ \int_{2^-}^x R(u)\frac1{u\log^2u}~du \\
&= \log\log x-\log\log2 + 1 + O\left(\frac1{\log x}\right)
+ \int_2^\infty \frac{R(u)}{u\log^2u}
+ O\left(\int_x^\infty\frac{\abs{R(u)}}{u\log^2u}~du\right) \\
&= \log\log x + \left(1-\log\log2 + \int_2^\infty\frac{R(u)}{u\log^2u}~du\right)
+ O\left(\frac1{\log x}\right) .
\end{align*}
\qedhere

\proof[Proof of (e)]
Note that $\log(1-t)^{-1}-t\ll\abs{t}^2$ for $\abs{t}\le\frac12$ by power series. Hence
\[
S = \sum_{p>x}\log\left(1-\frac1p\right)^{-1}-\frac1p
\ll \sum_{p>x}\left(\frac1p\right)^2 \le \sum_{n>x}\frac1{n^2}
\ll \frac1x .
\]
Note that $S$ exists and
\begin{align*}
\sum_{p\le x}\log\left(1-\frac1p\right)^{-1}
&= \sum_{p\le x}\frac1p + S
+ \sum_{p>x}\left(\log\left(1-\frac1p\right)^{-1}-\frac1p\right) \\
&= \log\log x + b + O\left(\frac1{\log x}\right) + S + O\left(\frac1x\right) \\
&= \log\log x + c + O\left(\frac1{\log x}\right) .
\end{align*}
Note that $e^t=1+O\left(\abs{t}\right)$ by power series, so
\begin{align*}
\prod_{p\le x}\left(1-\frac1p\right)^{-1}
&= \exp\left(\sum_{p\le x}\log\left(1-\frac1p\right)^{-1}\right)
= \exp\left(\log\log x + c + O\left(\frac1{\log x}\right)\right) \\
&= \log x \cdot e^c \cdot e^{O\left(1/\log x\right)}
= e^c\log x\left(1 + O\left(\frac1{\log x}\right)\right) \\
&= e^c\log x + O(1) .
\end{align*}
\qedhere

\begin{remark}
Note that in theorem \ref{thm:2.7}, we have $c=C_0$ and
$b=C_0-\sum_p\sum_{k\ge2}\frac1{kp^k}$.
\end{remark}

\begin{prop}
The average order of $\omega(n)=\#\set{p:p|w}$ is $\log\log n$.
\end{prop}
\proof
We can compute
\begin{align*}
\sum_{n\le x}\omega(n) &= \sum_{n\le x}\sum_{p|n}1
= \sum_{p\le x}\sum_{\substack{n\le x\\p|n}}1
= \sum_{p\le x}\floor{\frac{x}p}
= x\sum_{p\le x}\frac1p + O\left(\sum_{p\le x}1\right) \\
&= x\log\log x + O(x) .
\end{align*}
\qedhere

\begin{exe}
Check that $\sum_{n\le x}\log\log n \sim x\log\log x$.
\end{exe}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 02 04

\begin{defn}
The variance of $f(n)$ is
\[
\lim_{x\to\infty}\sum_{n\le x}(f(n)-g(x))^2
\]
where $g(x)$ is $g(x)=\frac1x\sum_{n\le x}f(n)$.
\end{defn}

Now we compute the variance of $\omega(n)$.

\begin{lemma}
We show that
\[
\sum_{n\le x} \omega(n)^2 \le x\left(\log\log x\right)^2 + O\left(x\log\log x\right) .
\]
\end{lemma}
\proof
\begin{align*}
\sum_{n\le x}\omega(n)^2
&= \sum_{n\le x}\left(\sum_{p|n}1\right)\left(\sum_{q|n}1\right)
= \sum_{p\le x}\sum_{q\le x}\sum_{\substack{n\le x\\p|n\\q|n}}1 \\
&= \sum_{p\le x}\sum_{\substack{q\le x\\q\neq p}}\floor{\frac{x}{pq}}
+ \sum_{p\le x}\floor{\frac{p}x} \\
&\le \sum_{p\le x}\sum_{q\le x}\frac{x}{pq}+\sum_{p\le x}\frac{x}p
= x\left(\sum_{p\le x}\frac1p\right)^2 + x\sum_{p\le x}\frac1p \\
&= x\left(\log\log x+O(1)\right)^2+O\left(x\log\log x\right) .
\end{align*}
\qedhere

\begin{prop}
The variance of $\omega(n)$ is $\ll\log\log x$.
\end{prop}
\proof
\begin{align*}
\sum_{n\le x}\left(\omega(n)-\log\log x\right)^2
&= \sum_{n\le x}\omega(n)^2 - 2(\log\log x) \sum_{n\le x}\omega(n)
+ \left(\log\log x\right)^2 \sum_{n\le x}1 \\
&= \sum_{n\le x}\omega(n)^2 - 2(\log\log x)\left(x\log\log x + O(x)\right)
+ \left(x+O(1)\right)\left(\log\log x\right)^2 \\
&\le \left(x(\log\log x)^2+O(x\log\log x)\right)
- \left(x\log\log x\right)^2 + O(x\log\log x) .
\end{align*}
\qedhere

\begin{cor}
It follows that
\[
S = \#\set{n\le x:\abs{\omega(n)-\log\log x}>\left(\log\log x\right)^{\frac12+\e}}
\ll \frac{x}{\left(\log\log x\right)^{2\e}} .
\]
\end{cor}
\proof
\begin{align*}
\sum_{\substack{n\le x\\n\in S}}1
&\le \sum_{n\le x}\left(\frac{\abs{\omega(n)-\log\log x}}
{(\log\log x)^{\frac12+\e}}\right)^2 \\
&= \frac1{(\log\log x)^{1+2\e}} \sum_{n\le x}(\omega(n)-\log\log x)^2 \\
&\ll \frac{x\log\log x}{(\log\log x)^{1+2\e}} .
\end{align*}
\qedhere

\begin{exe}[Hardy-Ramanujan]
Show that
\[
\#\set{n\le x:\abs{\omega(n)-\log\log n}>(\log\log n)^{\frac12+\e}}
\ll \frac{x}{(\log\log x)^{2\e}} = o(x) .
\]
It follows that the natural density is 0.
\end{exe}

\begin{exe}
Do the above computations for $\Omega(n)$.
\end{exe}

\begin{exe}
Prove that $2^{\omega(n)}\le d(n)\le 2^{\Omega(n)}$.
\end{exe}

From Hardy-Ramanujan, for almost all $n\in\NN$,
\[
(1-\delta)\log\log n \le \omega(n) \le \Omega(n) \le (1+\delta)\log\log n ,
\]
\[
(\log n)^{(1-\delta)\log2} = 2^{(1-\delta)\log\log n}
\le d(n) \le 2^{(1+\delta)\log\log n}
= (\log n)^{(1+\delta)\log2} .
\]
So for most $n\in\NN$, we have $d(n)\approx(\log n)^{\log2}$, but the average order of
$d(n)$ is $\log n$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 02 06






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 02 13






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2020 02 15







\end{document}