Proof. Consider $p_N={\prod }_p^N\left(1+\frac{1}{p}+\frac{1}{p^2}+\cdots +\frac{1}{p^N}\right)$, for $N\in \mathbb{N}=\{1,2,3,\dots \}$. We have:

$$\begin{array}{llll}\hfill p_N& \ge \sum _{n=1}^N\frac{1}{n}& \hfill & \\ \hfill & \ge \sum _{n=1}^{N-1}{\int }_n^{n+1}\frac{dt}{t}& \hfill & \\ \hfill & ={\int }_1^{N-1}\frac{dt}{t}& \hfill & \\ \hfill & =\log (N-1)& \hfill & \end{array}$$

On the other hand, using $1+x\le e^x$, so

$$\begin{array}{llll}\hfill p_N& \le \prod _{p\le N}\exp \left(\frac{1}{p}+\frac{1}{p^2}+\cdots +\frac{1}{p^N}\right)& \hfill & \\ \hfill & =\exp \left(\sum _{p\le N}\left(\frac{1}{p}+\frac{1}{p^2}+\cdots +\frac{1}{p^N}\right)\right)& \hfill & \\ \hfill & \le \exp \left(\sum _{p\le N}\left(\frac{1}{p}+\frac{1}{p^2-p}\right)\right)& \hfill & \\ \hfill & \le \exp \left(C+\sum _{p\le N}\frac{1}{p}\right)& \hfill & \end{array}$$

Comparing these two bounds gives

Then letting $N\to \infty$ gives the desired result. □

Proof. Consider

$$\begin{array}{llll}\hfill S_N& =\left(\genfrac{}{}{0ex}{}{2N}{N}\right)& \hfill & \\ \hfill & =\frac{(2N)!}{{(N!)}^2}& \hfill & \end{array}$$

for $N\in \mathbb{N}$. We have

$$S_N\le \sum _{j=0}^{2N}\left(\genfrac{}{}{0ex}{}{2N}{j}\right)={(1+1)}^{2N}=4^N.$$

On the other hand,

$$S_N=\prod _{p\le 2N}{p}^{{\alpha }^p(N)}$$

where ${\alpha }_p(N)$ is the largest $j$ such that $p^j|\left(\genfrac{}{}{0ex}{}{2N}{N}\right)$. We have ${\alpha }_p(N)=1$ for $p\in (N,2N]$. So

Take $N=\lceil \frac{x}{2}\rceil$, for $x\ge 2$. Hence

Then

So for $x\ge 2$ and a suitable large enough constant $c^{\prime }$, we have

Hence

for any $𝜀$, as long as $x\ge x(𝜀)$.

Take $𝜀=1$. Choose $c>0$ large enough. □

Proof. Follows from the definition in a straightforward way. Example:

• (iii) $|f(x)|\le c_1|h(x)|$, $|g(x)|\le c_2|u(x)|$. Then $|f(x)g(x)|\le c_1{c}_2|h(x)u(x)|$, so $f(x)g(x)=O(h(x)u(x))$. □

Proof. It suffices to prove the $y=0$ case, since then

$$\sum _{y<n\le x}{a}_{n}f(n)=\sum _{0<n\le x}{a}_{n}f(n)-\sum _{0<n\le y}{a}_{n}f(n).$$

Suppose $y=0$. By the fundamental theorem of calculus,

$$f(n)=f(x)-{\int }_n^x{f}^{\prime }(t)dt={\int }_0^x{f}^{\prime }(t){𝟙}_{[n,x]}(t)dt.$$

Summing over $n\le x$, we get

$$\begin{array}{llll}\hfill \sum _{n\le x}{a}_{n}f(n)& =A(x)f(x)-{\int }_0^x{f}^{\prime }(t)\left(\sum _{n\le x}{𝟙}_{[n,x]}(t)a_n\right)dt& \hfill & \\ \hfill & =A(x)f(x)-{\int }_0^x{f}^{\prime }(t)A(t)dt\square & \hfill & \end{array}$$

Proof. Apply Partial Summation with $a_n=1$, $f(t)=\frac{1}{t}$, $y=\frac{1}{2}$. Clearly $A(t)=\lfloor t\rfloor$. Then,

$$\begin{array}{llll}\hfill \sum _{n\le x}\frac{1}{n}& =\frac{\lfloor x\rfloor }{x}+{\int }_1^x\frac{\lfloor t\rfloor }{t^2}dt& \hfill & \\ \hfill & =\frac{x+O(1)}{x}+{\int }_1^x\frac{t-\{t\}}{t^2}dt& \hfill & \\ \hfill & =1+O\left(\frac{1}{x}\right)+\log x-{\int }_1^x\frac{\{t\}}{t^2}dt& \hfill & \\ \hfill & =1+\log x-{\int }_1^{\infty }\frac{\{t\}}{t^2}dt+O\left(\frac{1}{x}\right)& \hfill & \end{array}$$

The last equality is true since ${\int }_x^{\infty }\frac{\{t\}}{t^2}dt\le {\int }_x^{\infty }\frac{1}{t^2}dt=\frac{1}{x}$.

Let $\gamma =1-{\int }_1^{\infty }\frac{\{t\}}{t^2}dt$. Then we have the asymptotic equation as desired.

Taking $x\to \infty$ in the formula, we see that $\gamma$ is equal to the formula for Euler’s constant, as desired. □

Proof. Apply Lemma 1.3 with $a_n={𝟙}_{\mathbb{P}}(n)$ (where $\mathbb{P}$ is the set of primes), $f(t)=\frac{1}{t}$, and $y=1$.

We get $A(t)=\pi (t)$, and then

$$\begin{array}{llll}\hfill \sum _{p\le x}\frac{1}{p}& =\frac{\pi (x)}{x}+{\int }_1^x\frac{\pi (t)}{t^2}dt& \hfill & \\ \hfill & ={\int }_1^x\frac{\pi (t)}{t^2}dt+O(1)\square & \hfill & \end{array}$$

Proof. Since arithmetic functions with $+$ form an abelian group, it suffices to show:

• (i) $(f\ast g)\ast h=f\ast (g\ast h)$
• (ii) $f\ast g=g\ast f$
• (iii) $f\ast I=f$
• (iv) $f\ast (g+h)=f\ast g+f\ast h$

Proofs:

• (i) Follows from $(f\ast g)(n)={\sum }_{n=ab}f(a)g(b)$.
• (ii) Follows from $(f\ast g)(n)={\sum }_{n=ab}f(a)g(b)$.
• (iii) Take

  $$I(n)=\{\begin{array}{cc}1\hfill & n=1\hfill \\ 0\hfill & n\ne 0\hfill \end{array}.$$

  Then one can check that $f\ast I=f$.

• (iv) From definition. □

Proof. Need $g$ such that $f\ast g=I$.

$$(f\ast g)(1)=f(1)g(1)=1⟹g(1)=\frac{1}{f(1)}.$$

Assume $g(m)$ defined for $m<n$. We will defined $g(n)$.

$$\begin{array}{llll}\hfill (f\ast g)(n)& =g(n)f(1)+\sum _{\begin{array}{c}d|n\\ d\ne 1\end{array}}f(d)g\left(\frac{n}{d}\right)& \hfill & \\ \hfill ⟹g(n)& =-\frac{1}{f(1)}\sum _{\begin{array}{c}d|n\\ d\ne 1\end{array}}f(d)g\underset{<n}{\underbrace{\left(\frac{n}{d}\right)}}\square & \hfill & \end{array}$$

Proof. For the first part, suffices to show closedness. Let $f,g:\mathbb{N}\to ℂ$ be multiplicative, and $m,n$ coprime.

If $mn=ab$, we can write $a=a_1{a}_2$, $b=b_1{b}_2$ where $a_1=(a,m)$, $a_2=(a,n)$, $b_1=(b,m)$ and $b_2=(b,n)$. Therefore we have:

$$\begin{array}{llllll}\hfill (f\ast g)(mn)& =\sum _{mn=ab}f(a)g(b)& \hfill & & \hfill & \\ \hfill & =\sum _{\begin{array}{c}m=a_1{b}_1\\ n=a_2{b}_2\end{array}}f(a_1{a}_2)g(b_1{b}_2)& \hfill & \text{(above observation)}& \hfill & & \hfill & \\ \hfill & =\sum _{\begin{array}{c}m=a_1{b}_1\\ n=a_2{b}_2\end{array}}f(a_1)f(a_2)g(b_1)g(b_2)& \hfill & \text{(by multiplicativity)}& \hfill & & \hfill & \\ \hfill & =(f\ast g)(m)(f\ast g)(n)& \hfill & & \hfill & \end{array}$$

(also need to check that inverses are multiplicative).

Now, remains to show that for completely multiplicative $f$, $f\ast \mu f=I$.

Note that $f\ast \mu f$ is multiplicative by the first part. So enough to show $(f\ast \mu f)(p^k)=I(p^k)$ for prime powers $p^k$. Calculate:

$$\begin{array}{llll}\hfill f\ast \mu f(p)& =f(p)+\mu f(p)& \hfill & \\ \hfill & =f(p)-f(p)& \hfill & \\ \hfill & =0& \hfill & \\ \hfill & =I(p)& \hfill & \end{array}$$

and for $k\ge 2$:

$$\begin{array}{llll}\hfill f\ast \mu f(p^k)& =f(p^k)+\mu f(p)f(p^{k-1})& \hfill & \\ \hfill & =f(p^k)-f(p)f(p^{k-1})& \hfill & \\ \hfill & =f{(p)}^k-f(p)f{(p)}^{k-1}& \hfill & \\ \hfill & =0& \hfill & \\ \hfill & =I(p^k)\square & \hfill & \end{array}$$

Proof. Let $𝜀>0$ (fixed), $n\in \mathbb{N}$ and $\mathrm{Re}(s)>1+2𝜀$.

Then

$$\begin{array}{llll}\hfill \sum _{n=N}^{\infty }|f(n)n^{-s}|& =\sum _{n=N}^{\infty }|f(n)|n^{-\mathrm{Re}(s)}& \hfill & \\ \hfill & \ll \sum _{n=N}^{\infty }{n}^{𝜀-\mathrm{Re}(s)}& \hfill & \\ \hfill & \le \sum _{n=N}^{\infty }{n}^{-1-𝜀}& \hfill & \\ \hfill & \le N^{-1-𝜀}+\sum _{n=N+1}^{\infty }{\int }_{n-1}^n{t}^{-1-𝜀}dt& \hfill & \\ \hfill & \le N^{-1-𝜀}+{\int }_N^{\infty }{t}^{-1-𝜀}dt& \hfill & \\ \hfill & \ll N^{-𝜀}& \hfill & \end{array}$$

Hence we have absolute convergence for $\mathrm{Re}(s)>1+2𝜀$. Also, $D_f(s)$ is a uniform limit of the functions ${\sum }_{n=1}^{N}f(n)n^{-s}$. From complex analysis, a uniform limit of analytic functions is analytic. Hence $D_f(s)$ is analytic for $\mathrm{Re}(s)>1+2𝜀$.

Now let $𝜀\to 0$. □

Proof. Let $N\in \mathbb{N}$, $\mathrm{Re}(s)=\sigma >1$. Let

$$D_f(s,N)=\prod _{p\le N}\left(1+\frac{f(p)}{p^s}+\frac{f(p^2)}{p^{2s}}+\cdots \right).$$

Note that the series defining the factors are absolutely convergent, since

$$\sum _{k=1}^{\infty }\frac{|f(p^k)|}{|p^{ks}|}\ll \sum _{k=1}^{\infty }\frac{1}{p^{ks}}<\infty$$

(geometric series).

Therefore, multiplying out,

$$D_f(s,N)=\sum _{n=1}^{\infty }a(n,N)f(n)n^{-s}$$

where

$$a(n,N)=\#\{\text{ways to write }n\text{ as a product of prime powers, where the primes are }\le N\}.$$

The fundamental theorem of arithmetic tells us that $a(n,N)\in \{0,1\}$ and $a(n,N)=1$ for $n\le N$.

Now,

$$\begin{array}{llll}\hfill |D_f(S)-D_f(s,N)|& \le \sum _{n=N+1}^{\infty }|f(n)||n^{-s}|& \hfill & \\ \hfill & \ll \sum _{n=N+1}^{\infty }{n}^{-\sigma }& \hfill & \\ \hfill & \stackrel{N\to \infty }{\to }0& \hfill & \end{array}$$

(since ${\sum }_{n=1}^{\infty }{n}^{-\sigma }<\infty$). Hence $D_f(s)=\underset{N\to \infty }{\lim }{D}_f(s,N)$.

Finally, for $f$ completely multiplicative, use geometric formula:

$$\sum _{k=1}^{\infty }\frac{f{(p)}^k}{p^{ks}}=\frac{1}{1-\frac{f(p)}{p^s}}.\square$$

Proof. We know $D_f(s)$ and $D_g(s)$ are absolutely convergent, so can expand out the product.

$$\begin{array}{lllllll}\hfill D_f(s)D_g(s)& =\sum _{a,b=1}^{\infty }f(a)g(b){(ab)}^{-s}& \hfill =\sum _{n=1}^{\infty }\sum _{n=ab}f(a)g(b)n^{-s}& & \hfill & & \hfill \\ \hfill & =\sum _{n=1}^{\infty }(f\ast g)(n)n^{-s}& \hfill & & \hfill & \\ \hfill & =D_{f\ast g}(s)\square & \hfill & & \hfill & \end{array}$$

Proof. ${\sum }_{n\le x}(f\ast g)(n)={\sum }_{dm\le x}f(d)g(m)$. Split this sum into parts with $d\le y$ and $d>y$ to get the conclusion. □

Proof. We use the Dirichlet hyperbola method, with $y=x^{\frac{1}{2}}$. Note that $\tau =1\ast 1$. Then,

$$\begin{array}{llll}\hfill \sum _{n\le x}\tau (n)& =\sum _{d\le x^{\frac{1}{2}}}\sum _{m\le \frac{x}{d}}1+\sum _{m\le x^{\frac{1}{2}}}\sum _{x^{\frac{1}{2}}<d\le \frac{x}{m}}1& \hfill & \\ \hfill & =\sum _{x\le x^{\frac{1}{2}}}\left(\frac{x}{d}+O(1)\right)+\sum _{m\le x^{\frac{1}{2}}}\left(\frac{x}{m}-x^{\frac{1}{2}}+O(1)\right)& \hfill & \\ \hfill & =x\sum _{d\le x^{\frac{1}{2}}}\frac{1}{d}+x\sum _{m\le x^{\frac{1}{2}}}\frac{1}{m}-\sum _{m\le x^{\frac{1}{2}}}{x}^{\frac{1}{2}}+O(x^{\frac{1}{2}})& \hfill & \end{array}$$

Recall from Lecture 2 that

Taking $y=x^{\frac{1}{2}}$, the previous expression becomes

$$2\times \left(\frac{1}{2}\log x+\gamma +O\left(\frac{1}{x^{\frac{1}{2}}}\right)\right)-x+O(x^{\frac{1}{2}})=x\log x+(2\gamma -1)x+O(x^{\frac{1}{2}}).\square$$