Analytic Number Theory/Printable version

Analytic Number Theory

The current, editable version of this book is available in Wikibooks, the open-content textbooks collection, at
https://en.wikibooks.org/wiki/Analytic_Number_Theory

Permission is granted to copy, distribute, and/or modify this document under the terms of the Creative Commons Attribution-ShareAlike 3.0 License.

Useful summation formulas

Analytic number theory is so abysmally complex that we need a basic toolkit of summation formulas first in order to prove some of the most basic theorems of the theory.

Abel's summation formula

Theorem 1.1 (Abel's summation formula, also called Abel's identity):

Let $(a_{n})_{n\in \mathbb {N} }$ be a sequence and let $f:\mathbb {R} \to \mathbb {R}$ be a differentiable function such that $f'$ is Riemann integrable. If we define

$A(x):=\sum _{1\leq n\leq x}a_{n}$,

then we have

$\sum _{1\leq n\leq x}a_{n}f(n)=A(x)f(x)-\int _{1}^{x}A(y)f'(y)dy$.

Note: We need the Riemann integrability to be able to apply the fundamental theorem of calculus.

Proof 1:

We prove the theorem by induction on $\lfloor x\rfloor$.

1. $\lfloor x\rfloor =1$:

First, we have in this case

$\sum _{1\leq n\leq x}a_{n}f(n)=a_{1}f(1)$.

Then, we have

$A(x)f(x)=a_{1}f(x)=a_{1}f(1)-a_{1}(f(1)-f(x))=a_{1}f(1)+\int _{1}^{x}A(y)f'(y)dy$

by the fundamental theorem of calculus.

2. Induction step:

Define $N:=\lfloor x\rfloor$. We have

${\begin{aligned}\sum _{1\leq n\leq x}a_{n}f(n)&=\sum _{1\leq n\leq x-1}a_{n}f(n)+a_{N}f(N)\\&=A(x-1)f(x-1)-\int _{1}^{x-1}A(y)f'(y)dy+a_{N}f(N)\end{aligned}}$

by the induction hypothesis. Further,

${\begin{aligned}-\int _{1}^{x-1}A(y)f'(y)dy&=-\int _{1}^{x}A(y)f'(y)dy+\int _{x-1}^{x}A(y)f'(y)dy\\&=-\int _{1}^{x}A(y)f'(y)dy+\int _{x-1}^{N}A(y)f'(y)dy+\int _{N}^{x}A(y)f'(y)dy\\&=-\int _{1}^{x}A(y)f'(y)dy+A(N-1)\int _{x-1}^{N}f'(y)dy+A(N)\int _{N}^{x}f'(y)dy\\&=-\int _{1}^{x}A(y)f'(y)dy+A(N-1)(f(N)-f(x-1))+A(N)(f(x)-f(N))\end{aligned}}$.

Putting things together, we obtain

$\sum _{1\leq n\leq x}a_{n}f(n)=A(x-1)f(x-1)-\int _{1}^{x}A(y)f'(y)dy+A(N-1)(f(N)-f(x-1))+A(N)(f(x)-f(N))+a_{N}f(N)$

and thus the desired formula.

The method of proof we applied here was using induction and then trying to express the terms from the induction hypothesis in terms of the terms from the desired formula.$\Box$

Proof 2:

We prove the theorem by direct manipulation of the term on the left.

Define $k:=\lfloor x\rfloor$.

${\begin{aligned}\sum _{1\leq n\leq x}a_{n}f(n)&=\sum _{1\leq n\leq x}(A(n)-A(n-1))f(n)\\&=\sum _{1\leq n\leq x}A(n)f(n)-\sum _{0\leq n\leq x-1}A(n)f(n+1)=\sum _{1\leq n\leq x}A(n)f(n)-\sum _{1\leq n\leq x-1}A(n)f(n+1)\\&=\sum _{1\leq n\leq x-1}A(n)(f(n)-f(n+1))+A(k)f(k)\\&=\sum _{1\leq n\leq x-1}A(n)\left(-\int _{n}^{n+1}f'(t)dt\right)+A(x)f(x)-\int _{k}^{x}A(t)f'(t)dt\end{aligned}}$$\Box$

Proof 3:

We prove the formula by the means of the Riemann-Stieltjes integral. Indeed, by integration by parts, we have

${\begin{aligned}\sum _{1\leq n\leq x}a_{n}f(n)=\int _{0}^{x}f(t)dA(t)&=A(x)f(x)-\int _{0}^{x}A(t)df(t)\\&=A(x)f(x)-\int _{1}^{x}A(t)f'(t)dt\end{aligned}}$.$\Box$

Corollary 1.2:

$\sum _{y<n\leq x}a_{n}f(n)=A(x)f(x)-A(y)f(y)-\int _{y}^{x}A(t)f'(t)dt$.

Proof 1:

We deduce the formula from integration by parts for the Riemann-Stieltjes integral.

${\begin{aligned}\sum _{y<n\leq x}a_{n}f(n)=\int _{y}^{x}f(t)dA(t)&=f(x)A(x)-f(y)A(y)-\int _{y}^{x}A(t)df(t)\\&=f(x)A(x)-f(y)A(y)-\int _{y}^{x}A(t)f'(t)dt\end{aligned}}$$\Box$

Proof 2:

We directly manipulate the LHS (left hand side).

Define $k:=\lfloor x\rfloor$ and $m:=\lfloor y\rfloor$.

${\begin{aligned}\sum _{y<n\leq x}a_{n}f(n)&=\sum _{y<n\leq x}(A(n)-A(n-1))f(n)\\&=\sum _{y<n\leq x}A(n)f(n)-\sum _{y-1<n\leq x-1}A(n)f(n+1)\\&=\sum _{y<n\leq x-1}A(n)(f(n)-f(n+1))-A(m)f(m)+A(k)f(k)\\&=\sum _{y<n\leq x-1}A(n)-\left(\int _{n}^{n+1}f'(t)dt\right)-A(y)f(y)+A(x)f(x)-\int _{y}^{m}A(t)f'(t)dt-\int _{k}^{x}A(t)f'(t)dt\end{aligned}}$$\Box$

Two further proofs are given in exercises 1.1.1 and 1.1.5.

We note that induction and direct manipulation are quicker proofs for theorem 1.1, while corollary 1.2 is quicker proven from theorem 1.1 or Riemann-Stieltjes integration.

Exercises

• Exercise 1.1.1: Prove corollary 1.2 from theorem 1.1. Hint: $\sum _{y<n\leq x}a_{n}f(n)=\sum _{1\leq n\leq x}a_{n}f(n)-\sum _{1<n\leq y}a_{n}f(n)$.
• Exercise 1.1.2: Compute $\sum _{n=1}^{N}n^{3}$. Hint: Use $a_{n}=n$, $f(x)=x^{2}$, apply Abelian summation and split the resulting integral into pieces where $A(t)$ is constant. Then apply a similar process.
• Exercise 1.1.3: Prove that the limit $\lim _{n\to \infty }\left(-\log(n)+\sum _{k=1}^{n}{\frac {1}{k}}\right)$ exists. This limit is called the Euler–Mascheroni constant. Hint: Use $a_{n}=1$ and $f(x)={\frac {1}{x}}$.
• Exercise 1.1.4: Prove theorem 1.1 from corollary 1.2.
• Exercise 1.1.5: Prove corollary 1.2 using induction on $\lfloor x\rfloor$.

Euler's summation formula

Definition 1.3:

For $x\in \mathbb {R}$, we define

$\{x\}:=x-\lfloor x\rfloor$.

Theorem 1.4 (Euler's summation formula):

Let $f:\mathbb {R} \to \mathbb {R}$ be a differentiable function, such that $f'$ is Riemann integrable. Then

$\sum _{y<n\leq x}f(n)=\{x\}f(x)-\{y\}f(y)+\int _{y}^{x}f(t)dt+\int _{y}^{x}\{t\}f'(t)dt$.

Proof:

We prove the theorem from Corollary 1.2, setting $a_{n}=1$ and using integration by parts (integration by parts is proven using the fundamental theorem of calculus).

Indeed,

${\begin{aligned}\sum _{y<n\leq x}f(n)&=\lfloor x\rfloor f(x)-\lfloor y\rfloor f(y)-\int _{y}^{x}\lfloor t\rfloor f'(t)dt\\&=\lfloor x\rfloor f(x)-\lfloor y\rfloor f(y)-\int _{y}^{x}tf'(t)dt+\int _{y}^{x}\{t\}f'(t)dt\\&=\{x\}f(x)-\{y\}f(y)+\int _{y}^{x}f(t)dt+\int _{y}^{x}\{t\}f'(t)dt\end{aligned}}$,

where in the last line we used integration by parts on the integral $\int _{y}^{x}tf'(t)dt$.$\Box$

Corollary 1.5:

Exercises

1. Prove corollary 1.5.

Euler–Maclaurin formula

Theorem 1.6 (Euler–Maclaurin formula):

Define the functions $\rho (x):={\frac {1}{2}}-x$ and $\sigma (x):=\int _{0}^{x}\rho (y)dy$. Then for any twice continuously differentiable function $f$ such that $f''$ is Riemann integrable, we have

$\sum _{y<n\leq x}f(n)=\int _{x}^{y}f(t)dt+\rho (y)f(y)-\rho (x)f(x)+\sigma (x)f'(x)-\sigma (y)f'(y)+\int _{x}^{y}\sigma (t)f''(t)dt$.

Proof 1:

We prove the theorem by direct computation.

${\begin{aligned}\end{aligned}}$

Proof 2:

We prove the theorem from Euler's summation formula.

The Chebychev ψ and ϑ functions

Proposition (the Chebychev ψ function may be written as the sum of Chebyshev ϑ functions):

We have the identity

$\psi (x)=\sum _{m=1}^{\log _{2}(x)}\vartheta (x^{1/m})$.

Proposition (estimate of the distance between the Chebychev ψ and ϑ functions):

Whenever $x\geq 3,594,641$, we have

$\psi (x)-\vartheta (x)={\sqrt {x}}+O\left({\frac {\sqrt {x}}{\ln(x)^{2}}}\right)$.

Note: The current proof gives an inferior error term. A subsequent version will redeem this issue. (Given the Riemann hypothesis, the error term can be made even smaller.)

Proof: We know that the formula

$\psi (x)=\sum _{m=1}^{\log _{2}(x)}\vartheta (x^{1/m})$

holds. Hence,

$\psi (x)-\vartheta (x)=\sum _{m=2}^{\log _{2}(x)}\vartheta (x^{1/m})$.

By a result obtained by Pierre Dusart (based upon the computational verification of the Riemann hypothesis for small moduli), we have

$\left|\theta (x)-x\right|\leq {\frac {0.2}{\ln(x)^{2}}}x$

whenever $x\geq 3,594,641$. If $x$ is in that range, we hence conclude

$\psi (x)-\vartheta (x)=\sum _{m=2}^{\log _{2}(x)}\vartheta (x^{1/m})\leq \left(1+{\frac {0.2}{\ln(x)^{2}}}\right)\sum _{m=2}^{\log _{2}(x)}x^{1/m}$.

By Euler's summation formula, we have

$\sum _{m=2}^{\log _{2}(x)}x^{1/m}=\int _{2}^{\log _{2}(x)}x^{1/t}dt+\int _{2}^{\log _{2}(x)}\{t\}\left({\frac {d}{dt}}x^{1/t}\right)dt+\{\log _{2}(x)\}x^{1/\log _{2}(x)}-\{2\}x^{1/2}$.

Certainly $\{2\}=0$ and $\{\log _{2}(x)\}\leq 1$. Moreover, $x^{1/\log _{2}(x)}=2$. Now derivation shows that

$-\exp \left({\frac {\ln(x)}{t}}\right){\frac {t^{2}}{\ln(x)}}$

is an anti-derivative of the function

$x^{1/t}-{\frac {2t}{\ln(x)}}x^{1/t}$

of $t$. By the fundamental theorem of calculus, it follows that

$\int _{a}^{b}\left(1-{\frac {2t}{\ln(x)}}\right)x^{1/t}dt=\left[-\exp \left({\frac {\ln(x)}{t}}\right){\frac {t^{2}}{\ln(x)}}\right]_{t=a}^{t=b}$

for real numbers $a,b\in \mathbb {R}$ such that $a<b$. This integral is not precisely the one we want to estimate. Hence, some analytical trickery will be necessary in order to obtain the estimate we want.

We start by noting that if only the bracketed term in the integral were absent, we would have the estimate we desire. In order to proceed, we replace $x$ by the more general expression $xy$ (where $y\geq 1$), and obtain

$\int _{a}^{b}\left(1-{\frac {2t}{\ln(xy)}}\right)x^{1/t}y^{1/t}dt=\left[-\exp \left({\frac {\ln(xy)}{t}}\right){\frac {t^{2}}{\ln(xy)}}\right]_{t=a}^{t=b}$.

The integrand is non-negative so long as

$t\leq {\frac {\ln(xy)}{2}}$.

Moreover, if $t_{0}$ is strictly within that range, we obtain

$\int _{2}^{t_{0}}x^{1/t}y^{1/t}dt\leq \left(1-{\frac {2t_{0}}{\ln(xy)}}\right)^{-1}\int _{2}^{t_{0}}\left(1-{\frac {2t}{\ln(xy)}}\right)x^{1/t}y^{1/t}dt=\left[-\exp \left({\frac {\ln(xy)}{t}}\right){\frac {t^{2}}{\ln(xy)}}\right]_{t=2}^{t=t_{0}}$.

We now introduce a constant $K\in (2,t_{0})$ and obtain the integrals

$\int _{2}^{K}x^{1/t}y^{1/t}dt$ and $\int _{K}^{t_{0}}x^{1/t}y^{1/t}dt$.

The first integral majorises the integral

$y^{1/K}\int _{2}^{K}x^{1/t}dt$,

whereas the second integral majorises the integral

$\int _{K}^{t_{0}}x^{1/t}dt$.

We obtain that

$\int _{2}^{t_{0}}x^{1/t}dt\leq {\frac {1}{y^{1/K}}}\int _{2}^{K}x^{1/t}y_{1}^{1/t}dt+\int _{K}^{t_{0}}x^{1/t}y_{2}^{1/t}dt$.

Now we would like to set $t_{0}=\log _{2}(x)$. To do so, we must ensure that $y$ is sufficiently large so that $K$ resp. $t_{0}$ is strictly within the admissible interval.

The two summands on the left are now estimated using our computation above, where $t_{0}$ is replaced by $K$ for the first computation: Indeed,

$\int _{2}^{K}x^{1/t}y_{1}^{1/t}dt\leq \left(1-{\frac {2K}{\ln(xy_{1})}}\right)^{-1}\left[-\exp \left({\frac {\ln(xy_{1})}{t}}\right){\frac {t^{2}}{\ln(xy_{1})}}\right]_{t=2}^{t=K}$

and

$\int _{K}^{t_{0}}x^{1/t}y_{2}^{1/t}dt\leq \left(1-{\frac {2t_{0}}{\ln(xy_{2})}}\right)^{-1}\left[-\exp \left({\frac {\ln(xy_{2})}{t}}\right){\frac {t^{2}}{\ln(xy_{2})}}\right]_{t=K}^{t=t_{0}}$.

Putting the estimates together and setting $t_{0}=\log _{2}(x)$, we obtain

$\int _{2}^{\log _{2}(x)}x^{1/t}dt\leq {\frac {1}{y_{1}^{1/K}}}\left(1-{\frac {2K}{\ln(xy_{1})}}\right)^{-1}\left[-\exp \left({\frac {\ln(xy_{1})}{t}}\right){\frac {t^{2}}{\ln(xy_{1})}}\right]_{t=2}^{t=K}+\left(1-{\frac {2t_{0}}{\ln(xy_{2})}}\right)^{-1}\left[-\exp \left({\frac {\ln(xy_{2})}{t}}\right){\frac {t^{2}}{\ln(xy_{2})}}\right]_{t=K}^{t=\log _{2}(x)}$

whenever

$K\leq {\frac {\ln(xy_{1})}{2}}$ and $\log _{2}(x)\leq {\frac {\ln(xy_{2})}{2}}$.

We now choose the ansatz

$1-{\frac {2K}{\ln(xy_{1})}}=C$ and $1-{\frac {2t_{0}}{\ln(xy_{2})}}=D$

for constants $C$ and $D$. These equations are readily seen to imply

$y_{1}={\frac {1}{x}}\exp \left({\frac {2K}{1-C}}\right)$ and $y_{2}={\frac {1}{x}}\exp \left({\frac {2\log _{2}(x)}{1-D}}\right)$.

Note though that $y_{1}\geq 1$ and $y_{2}\geq 1$ is needed. The first condition yields

$K\geq {\frac {1-C}{2}}\ln(x)$.

The equations for $y_{1}$ and $y_{2}$ may be inserted into the above constraints on $K$ and $\log _{2}(x)$; this yields

$K\leq {\frac {2K}{1-C}}$ and $\log _{2}(x)\leq {\frac {2\log _{2}(x)}{1-D}}$, that is, $C\geq {\frac {1}{2}}$ and $D\geq {\frac {1}{2}}$.

If all these conditions are true, the ansatz immediately yields

$\int _{2}^{\log _{2}(x)}x^{1/t}dt\leq {\frac {C^{-1}}{y_{1}^{1/K}}}\left[-\exp \left({\frac {\ln(xy_{1})}{t}}\right){\frac {t^{2}}{\ln(xy_{1})}}\right]_{t=2}^{t=K}+D^{-1}\left[-\exp \left({\frac {\ln(xy_{2})}{t}}\right){\frac {t^{2}}{\ln(xy_{2})}}\right]_{t=K}^{t=\log _{2}(x)}$.

We now amend our ansatz by further postulating

$K=\left({\frac {1-C}{2}}+\alpha \right)\ln(x)$.

This yields

$y_{1}={\frac {1}{x}}\exp \left({\frac {(1-C+2\alpha )\ln(x)}{1-C}}\right)$

and

${\frac {C^{-1}}{y_{1}^{1/K}}}\left[-\exp \left({\frac {\ln(xy_{1})}{t}}\right){\frac {t^{2}}{\ln(xy_{1})}}\right]_{t=2}^{t=K}={\frac {C^{-1}}{y_{1}^{1/K}}}\left[-\exp \left({\frac {\frac {(1-C+2\alpha )\ln(x)}{1-C}}{t}}\right){\frac {t^{2}}{\ln(xy_{1})}}\right]_{t=2}^{t=K}$.

From this we deduce that in order to obtain an asymptotically sharp error term, we need to set $\alpha =0$. But doing so yields the desired result. $\Box$

Arithmetic functions

In this chapter, we shall set up the basic theory of arithmetic functions. This theory will be seen in action in later chapters, but in particular in chapter 9.

Definitions

Definition 2.1:

An arithmetical function is a function $f:\mathbb {N} \to \mathbb {C}$.

Definition 2.2 (important arithmetical functions):

1. The Kronecker delta: $\delta (n):={\begin{cases}1&n=1\\0&n\neq 1\end{cases}}$
2. Euler's totient function: $\varphi (n):=\left|\{1\leq k\leq n|\gcd(k,n)=1\}\right|$
3. Möbius' $\mu$-function: $\mu (n):={\begin{cases}0&{\text{ there exists }}m\in \mathbb {N} {\text{ such that }}m^{2}|n\\(-1)^{r}&n{\text{ is product of }}r{\text{ pairwise different prime numbers}}\\1&n=1\end{cases}}$
4. The von Mangoldt function: $\Lambda (n):={\begin{cases}\log(p)&\exists p{\text{ prime}},k\in \mathbb {N} :n=p^{k}\\0&{\text{otherwise}}\end{cases}}$
5. The monomials: $I_{k}(n):=n^{k}$
6. The number of distinct prime divisors: $\omega (n):=r,n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$, $k_{1},\ldots ,k_{r}\in \mathbb {N}$
7. The sum of prime factors with multiplicity: $\Omega (n):=k_{1}+\cdots +k_{r},n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$, $k_{1},\ldots ,k_{r}\in \mathbb {N}$
8. The Liouville function: $\lambda (n):=(-1)^{\Omega (n)}$

Exercises

• Exercise 2.1.1: Compute $\varphi (20)$, $\varphi (17)$ and $\varphi (22)$.
• Exercise 2.1.2: Compute $\mu (4278)$. Hint: $4278=2\cdot 3\cdot 23\cdot 31$.
• Exercise 2.1.3: Compute $\Lambda (49)$ up to three decimal places. Hint: Use a Taylor expansion.
• Exercise 2.1.4: Prove that for each $n\in \mathbb {N}$ and $k_{1},k_{2},k_{3},k_{4}\in \mathbb {N}$ $\mu (n+4k_{1})\mu (n+4k_{2}+1)\mu (n+4k_{3}+2)\mu (n+4k_{4}+3)=0$.

The convolution and the ring of arithmetic functions

Definition 2.3:

Let $f,g:\mathbb {N} \to \mathbb {C}$ be arithmetical functions. Then the convolution of $f$ and $g$ is defined to be the function

$f*g(n):=\sum _{d|n}f(d)g\left({\frac {n}{d}}\right)$.

In the following theorem, we show that the arithmetical functions form an Abelian monoid, where the monoid operation is given by the convolution. Further, since the sum of two arithmetic functions is again an arithmetic function, the arithmetic functions form a commutative ring. In fact, as we shall also see, they form an integral domain.

Theorem 2.4 (Abelian monoid properties of the arithmetical functions):

1. The convolution is commutative, i. e. $f*g=g*f$.
2. The convolution is associative, i. e. $f*(g*h)=(f*g)*h$.
3. The function $\delta$ from definition 2.2 is an identity for the convolution, i. e. $\delta *f=f$.

Proof:

1.:

${\begin{aligned}f*g(n)&=\sum _{d|n}f(d)g\left({\frac {n}{d}}\right)=\sum _{d|n}f(\psi (d))g\left(\psi \left({\frac {n}{d}}\right)\right)\\&=\sum _{d|n}f\left({\frac {n}{d}}\right)g(d)=g*f(n)\end{aligned}}$,

where $\psi (d):={\frac {n}{d}}$ is a bijection from the set of divisors of $n$ to itself.

2.:

${\begin{aligned}f*(g*h)=f*(h*g)&=\sum _{d_{1}|n}f(d_{1})\left(\sum _{d_{2}|{\frac {n}{d_{1}}}}g\left({\frac {n}{d_{1}d_{2}}}\right)h(d_{2})\right)\\&=\sum _{d_{1}|n}\sum _{d_{2}|{\frac {n}{d_{1}}}}f(d_{1})g\left({\frac {n}{d_{1}d_{2}}}\right)h(d_{2})\\&=\sum _{d_{2}|n}\sum _{d_{1}|{\frac {n}{d_{2}}}}f(d_{1})g\left({\frac {n}{d_{1}d_{2}}}\right)h(d_{2})\end{aligned}}$,

where the last equality follows from the identity function

$Id:\left\{(d_{1},d_{2}):d_{2}|n,d_{1}{\big |}{\frac {n}{d_{2}}}\right\}\to \left\{(d_{1},d_{2}):d_{1}|n,d_{2}{\big |}{\frac {n}{d_{1}}}\right\}$

being a bijection. But

$\sum _{d_{2}|n}\sum _{d_{1}|{\frac {n}{d_{2}}}}f(d_{1})g\left({\frac {n}{d_{1}d_{2}}}\right)h(d_{2})=(f*g)*h$

and hence associativity.

3.:

$\delta *f(n)=\sum _{d|n}\delta (d)f\left({\frac {n}{d}}\right)=f(n)$$\Box$

Theorem 2.5:

The ring of arithmetic functions is an integral domain.

Proof: Let $f,g\neq 0$ be arithmetic functions, and let $n,k\in \mathbb {N}$ be minimal such that $f(n)\neq 0$, $g(k)\neq 0$. Then

$f*g(nk)=\sum _{d|nk}f(d)g\left({\frac {nk}{d}}\right)=f(n)g(k)$.$\Box$

We shall now determine the units of the ring of arithmetic functions.

Theorem 2.6:

Let $f$ be an arithmetic function. Then $f$ is invertible (with respect to convolution) if and only if $f(1)\neq 0$.

Proof:

Assume first $f(1)=0$. Then for any arithmetic function $g$, $f*g(1)=0\neq 1=\delta (1)$.

Assume now $f(1)\neq 0$. Then $g$, given by the recursive formula

$g(1)=f(1)^{-1}$,

$g(n)=-f(1)^{-1}\sum _{d|n \atop d<n}g(d)f\left({\frac {n}{d}}\right)=g(n)-f(1)^{-1}g*f(n)$, $n>1$

is an inverse (and thus the inverse) of $f$, since $f*g(1)=f(1)g(1)=1$ and for $n>1$ inductively

${\begin{aligned}f*g(n)&=f*g(n)-f(1)^{-1}f*g*f(n)\\&=f*g(n)-f^{-1}\sum _{d|n \atop d<n}f*g(d)f\left({\frac {n}{d}}\right)=0\end{aligned}}$

$\Box$

Exercises

• Exercise 2.2.1:
• Exercise 2.2.2:

Multiplicative functions

Definition 2.7:

An arithmetical function $f:\mathbb {N} \to \mathbb {C}$ is called multiplicative iff it satisfies

1. $\forall n,k\in \mathbb {N} :\gcd(n,k)=1\Rightarrow f(nk)=f(n)f(k)$, and
2. $f(1)=1$.

Theorem 2.8:

Let $f,g$ be multiplicative arithmetical functions. Then $f*g$ is multiplicative.

Proof:

Let $\gcd(k,n)=1$. Then

$f*g(kn)=\sum _{d|(kn)}f(d)g\left({\frac {kn}{d}}\right)=\sum _{d_{1}|k \atop d_{2}|n}f(d_{1}d_{2})g\left({\frac {kn}{d_{1}d_{2}}}\right)$,

since the function $\theta (d):=(\gcd(d,n),\gcd(d,k))$ is a bijection from the divisors of $nk$ to the Cartesian product of the divisors of $n$ and the divisors of $k$; this is because multiplication is the inverse:

$\gcd(d,n)\gcd(d,k)=d$, $(\gcd(d_{1}d_{2},n),\gcd(d_{1}d_{2},k))=(d_{1},d_{2})$.

To rigorously prove this actually is an exercise in itself. But due to the multiplicativity of $f$ and $g$,

$\sum _{d_{1}|k \atop d_{2}|n}f(d_{1}d_{2})g\left({\frac {kn}{d_{1}d_{2}}}\right)=\sum _{d_{1}|k \atop d_{2}|n}f(d_{1})g\left({\frac {k}{d_{1}}}\right)f(d_{2})g\left({\frac {n}{d_{2}}}\right)=f*g(k)\cdot f*g(n)$.

Furthermore, $f*g(1)=f(1)g(1)=1$.$\Box$

Since $\delta$ is multiplicative, we conclude that the multiplicative functions form an Abelian submonoid of the arithmetic functions with convolution. Unfortunately, we do not have a subring since the sum of two multiplicative functions is never multiplicative (look at $n=1$).

Theorem 2.9:

Let $f$ be a multiplicative function such that $\sum _{j=1}^{\infty }f(j)$ converges absolutely. Then

$\sum _{j=1}^{\infty }f(j)=\prod _{p{\text{ prime}}}\left(\sum _{k=0}^{\infty }f(p^{k})\right)$.

Proof: Let $p_{1},p_{2},p_{3},\ldots =2,3,5,\ldots$ be the ordered sequence of all prime numbers. For all $m_{1},\ldots ,m_{r},r\in \mathbb {N}$ we have

$S_{f,r,m_{1},\ldots ,m_{r}}:=\sum _{d|\left(p_{1}^{m_{1}}\cdots p_{r}^{m_{r}}\right)}f(d)=\sum _{0\leq k_{1}\leq m_{1}}\cdots \sum _{0\leq k_{r}\leq m_{r}}f\left(p_{1}^{k_{1}}\right)\cdots f\left(p_{r}^{k_{r}}\right)=\prod _{l=1}^{r}\left(\sum _{k=0}^{m_{l}}f(p_{l}^{k})\right)$

due to the multiplicativity of $f$. For each $r$, we successively take $m_{1}\to \infty$, ..., $m_{r}\to \infty$ and then $r\to \infty$. It follows from the definitions and the rule $x_{n}\to x\Rightarrow yx_{n}\to yx$ that the right hand side converges to

$\prod _{l=1}^{\infty }\left(\sum _{k=0}^{\infty }f(p_{l}^{k})\right)$.

We claim that

$\lim _{r\to \infty }\lim _{m_{1}\to \infty }\cdots \lim _{m_{r}\to \infty }S_{f,r,m_{1},\ldots ,m_{r}}=\sum _{j=1}^{\infty }f(j)$.

Indeed, choose $N\in \mathbb {N}$ such that

$\sum _{j=N+1}^{\infty }|f(j)|<\epsilon$.

Then by the fundamental theorem of arithmetic, there exists an $R\in \mathbb {N}$ and $M_{1},\ldots ,M_{R}\in \mathbb {N}$ such that

$\forall j\in \{1,\ldots ,N\}:j|p_{1}^{M_{1}}\cdots p_{R}^{M_{R}}$.

Then we have by the triangle inequality for $T>R$, $L_{1}>M_{1},\ldots ,L_{R}>M_{R}$ and $L_{R+1},\ldots ,L_{T}$ arbitrary that

${\begin{aligned}\left|S_{f,T,L_{1},\ldots ,L_{T}}-\sum _{j=1}^{\infty }f(j)\right|&\leq \left|\sum _{d|\left(p_{1}^{L_{1}}\cdots p_{T}^{L_{T}}\right) \atop d\leq N}f(d)-\sum _{j=1}^{N}f(j)\right|+\left|\sum _{d|\left(p_{1}^{L_{1}}\cdots p_{T}^{L_{T}}\right) \atop d>N}f(d)-\sum _{j=N+1}^{\infty }f(j)\right|\\&<0+\epsilon .\end{aligned}}$

From this easily follows the claim.

It is left to show that the product on the left is independent of the order of multiplication. But this is clear since if the sequence $(p_{n})_{n\in \mathbb {N} }$ is enumerated differently, the argument works in just the same way and the left hand side remains the same.$\Box$

Definition 2.10:

An arithmetical function $f:\mathbb {N} \to \mathbb {C}$ is called strongly multiplicative iff it satisfies

1. $\forall n,k\in \mathbb {N} :f(nk)=f(n)f(k)$, and
2. $f(1)=1$.

Equivalently, a strongly multiplicative function is a monoid homomorphism $\mathbb {N} \to \mathbb {C} ^{\times }$.

Theorem 2.11:

Let $f$ be a strongly multiplicative function such that $\sum _{j=1}^{\infty }f(j)$ converges absolutely. Then

$\sum _{j=1}^{\infty }f(j)=\prod _{p{\text{ prime}}}{\frac {1}{1-f(p)}}$.

Proof:

Due to theorem 2.9, we have

$\sum _{n=1}^{\infty }f(n)=\prod _{p{\text{ prime}}}\left(\sum _{k=0}^{\infty }f(p^{k})\right)$.

Due to strong multiplicativity and the geometric series, the latter expression equals

$\prod _{p{\text{ prime}}}{\frac {1}{1-f(p)}}$.$\Box$

Exercises

• Exercise 2.3.1: Let $h$ be an arithmetic function such that for all $m,n\in \mathbb {N}$ $h(nm)=h(n)+h(m)$, and let $s\in \mathbb {C} \setminus \{0\}$. Prove that the function $f(n):=\exp(\log(s)h(n))$ is multiplicative.

Bell series

Definition 2.12:

Let $f$ be an arithmetic function. Then for a prime $p$ the Bell series modulo $p$ is the formal power series

$f_{p}(x):=\sum _{j=0}^{\infty }f(p^{j})x^{j}$.

Examples 2.13:

We shall here compute the Bell series for some important arithmetic functions.

We note that in general for a completely multiplicative function $f$, we have

$f_{p}(x)=\sum _{j=0}^{\infty }f(p)^{j}x^{j}={\frac {1}{1-f(p)x}}$.

In particular, in this case the Bell series defines a function.

1. The Kronecker delta:

$\delta _{p}(x)=\sum _{j=0}^{\infty }\delta (p^{j})x^{j}=1$

2. Euler' totient function (we use lemma 9.?):

${\begin{aligned}\varphi _{p}(x)&=\sum _{j=0}^{\infty }\varphi (p^{j})x^{j}\\&=\sum _{j=0}^{\infty }\varphi (p^{j})x^{j}\\&=1+\sum _{j=1}^{\infty }(p^{j}-p^{j-1})x^{j}\\&={\frac {1+x}{1-px}}\end{aligned}}$

3. The Möbius $mu$ function:

$\mu _{p}(x)=\sum _{j=0}^{\infty }\mu (p^{j})x^{j}=1-x$

4. The von Mangoldt function:

$\Lambda _{p}(x)=\sum _{j=0}^{\infty }\Lambda (p^{j})x^{j}=\sum _{j=0}^{\infty }\log(p)x^{j}$

5. The monomials:

$(I_{k})_{p}=\sum _{j=0}^{\infty }p^{kj}xj={\frac {1}{1-p^{k}x}}$

6. The number of distinct prime divisors:

$\omega _{p}(x)=\sum _{j=1}^{\infty }x^{j}={\frac {1}{1-x}}-1$

7. The number of prime divisors including multiplicity:

${\begin{aligned}\Omega _{p}(x)&=\sum _{j=1}^{\infty }jx^{j}\\&={\frac {1}{x}}\sum _{j=0}^{\infty }(x^{j})'\\&={\frac {1}{x}}\left(\sum _{j=0}^{\infty }x^{j}\right)'\\&={\frac {1}{x}}\left({\frac {1}{1-x}}\right)'\\&=-{\frac {1}{x}}{\frac {1}{(1-x)^{2}}}\end{aligned}}$

8. The Liouville function:

$\lambda _{p}(x)=\sum _{j=0}^{\infty }(-1)^{j}x^{j}={\frac {1}{1+x}}$

Theorem 2.14 (compatibility of Bell series and convolution):

Let $f,g$ arithmetic functions, and $p$ be a prime. Then

$f_{p}\cdot g_{p}=(f*g)_{p}$.

Proof:

${\begin{aligned}f_{p}(x)g_{p}(x)&=\left(\sum _{j=0}^{\infty }f(p^{j})x^{j}\right)\left(\sum _{j=0}^{\infty }g(p^{j})x^{j}\right)\\&=\sum _{k=0}^{\infty }x^{k}\left(\sum _{j=0}^{k}f(p^{j})g(p^{k-j})\right)\\&=\sum _{k=0}^{\infty }x^{k}(f*g)(p^{k})\end{aligned}}$$\Box$

In case of multiplicativity, we have the following theorem:

Theorem 2.15 (Uniqueness theorem):

Let $f,g$ be multiplicative functions. Then

$f=g\Leftrightarrow f_{p}=g_{p}$.

Proof: $\Rightarrow$ is pretty obvious; $\Leftarrow$: $f_{p}(x)=g_{p}(x)$ as formal power series is equivalent to saying $\forall k\in \mathbb {N} :f(p^{k})=g(p^{k})$. If now $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$, then

$f(n)=f(p_{1}^{k_{1}}\cdots p_{r}^{k_{r}})=f(p_{1}^{k_{1}})\cdots f(p_{r}^{k_{r}})=g(p_{1}^{k_{1}})\cdots g(p_{r}^{k_{r}})=g(n)$

due to the multiplicativity of $f$ and $g$.$\Box$

In chapter 9, we will use Bell series to obtain equations for number-theoretic functions.

Derivatives

Definition 2.16:

Let $f$ be an arithmetic function. Then the derivative of $f$ is defined to be the function

$f'(n):=f(n)\log(n)$.

Theorem 2.17 (rules for the derivative):

Let $f,g$ arithmetic functions. We have the following rules:

1. $(f+g)'=f'+g'$
2. $(f*g)'=f'*g+f*g'$
3. $(f^{-1})'=-f'\cdot (f*f)^{-1}$ if $f$ invertible, i.e.$f(1)\neq 0$

Note that $f^{-1}$ is not the inverse function of $f$ (this wouldn't make much sense anyway since $f$ arithmetic can not be surjective, since $\mathbb {C}$ is uncountable), but rather the convolution inverse.

Proof:

1. is easily checked.

2.:

${\begin{aligned}(f*g)'(n)&=(f*g)(n)\log(n)\\&=\sum _{d|n}f(d)g(n/d)(\log(d)+\log(n/d))\\&=\sum _{d|n}f(d)g(n/d)\log(d)+\sum _{d|n}f(d)g(n/d)\log(n/d)\end{aligned}}$

3.

We have $\delta '=0$ and $(f*f^{-1})=\delta$. Hence, by 2.

$0=(f*f^{-1})'=f'*f^{-1}+f*(f^{-1})'$.

Convolving with $f^{-1}$ and using $f^{-1}*f^{-1}=(f*f)^{-1}$ yields the desired formula.$\Box$

Note that a chain rule wouldn't make much sense, since $f$ arithmetic may map anywhere but to $\mathbb {N}$ and thus $g\circ f$ doesn't make a lot of sense in general.

Further reading

• terrytao.wordpress.com: Derived multiplicative functions

Characters and Dirichlet characters

Definitions, basic properties

Definition 4.1

Let $G$ be a finite group. A character of G is a function $f:G\to \mathbb {C}$ such that

1. $\forall \sigma ,\tau \in G:f(\sigma \tau )=f(\sigma )f(\tau )$ and
2. $\exists \rho \in G:f(\rho )\neq 0$.

Lemma 4.2:

Let $G$ be a finite group and let $f:G\to \mathbb {C}$ be a character. Then

$\forall \sigma \in G:|f(\sigma )|=1$.

In particular, $\forall \sigma \in G:f(\sigma )\neq 0$.

Proof:

Since $G$ is finite, each $\sigma \in G$ has finite order $n:=\mathrm {ord} (\sigma )$. Furthermore, let $\rho \in G$ such that $f(\rho )\neq 0$; then $f(\rho )=f(\sigma )f(\sigma ^{-1}\rho )$ and thus $f(\sigma )\neq 0$. Hence, we are allowed to cancel and

$|f(\sigma )|=|f(\sigma ^{n+1})|=|f(\sigma )|^{n+1}\Rightarrow |f(\sigma )|=1$.$\Box$

Lemma 4.3:

Let $G$ be a finite group and let $f,g:G\to \mathbb {C}$ be characters. Then the function $h:G\to \mathbb {C} ,h(\tau ):=f(\tau )\cdot g(\tau )$ is also a character.

Proof:

$h(\sigma \tau )=f(\sigma \tau )g(\sigma \tau )=f(\sigma )g(\sigma )f(\tau )g(\tau )=h(\sigma )h(\tau )\neq 0$,

since $\mathbb {C}$ is a field and thus free of zero divisors.$\Box$

Lemma 4.4:

Let $G$ be a finite group and let $f:G\to \mathbb {C}$ be a character. Then the function $g:G\to \mathbb {C} ,g(\tau ):={\frac {1}{f(\tau )}}$ is also a character.

Proof: Trivial, since $\forall \tau \in G:f(\tau )\neq 0$ as shown by the previous lemma.$\Box$

The previous three lemmas (or only the first, together with a few lemmas from elementary group theory) justify the following definition.

Definition 4.5

Let $G$ be a finite group. Then the group

$\{f:G\to \mathbb {C} |f{\text{ is a character }}\}=\mathrm {Hom} (G,\mathbb {C} ^{\times })$

is called the character group of $G$.

Required algebra

We need the following result from group theory:

Lemma 4.6

Let $G$ be a finite Abelian group, let $H\leq G$ be a subgroup of order $n\in \mathbb {N}$, and let $\tau \in G\setminus H$ such that $k\in \mathbb {N}$ is the smallest number such that $\tau ^{k}\in H$. Then the group

$N:=\{\tau ^{n}\sigma |\sigma \in H\}$

is a subgroup of $G$ containing $H$ of order $k\cdot n$.

Proof:

Since $G$ is the disjoint union of the cosets of $H$, $N$ is the disjoint union $\bigcup _{j=0}^{n-1}\tau ^{j}H$, as $\rho H=H\Leftrightarrow \rho \in H$ and $\tau ^{l}H=\tau ^{m}H\Leftrightarrow \tau ^{l-m}\in H\Leftrightarrow k|(l-m)$. Hence, the cardinality of $N$ equals $k\cdot n$.

Furthermore, if $\tau ^{l}\sigma ,\tau ^{m}\rho \in N$, then $\tau ^{l}\sigma (\tau ^{m}\rho )^{-1}=\tau ^{l-m}\sigma \rho ^{-1}\in N$, and hence $N$ is a subgroup.$\Box$

Dirichlet series

For the remainder of this book, we shall use Riemann's convention of denoting complex numbers:

$s=\sigma +it$

Definition

Definition 5.1:

Let $f$ be an arithmetic function. Then the Dirichlet series associated to $f$ is the series

$\sum _{n=1}^{\infty }{\frac {f(n)}{n^{s}}}$,

where $s$ ranges over the complex numbers.

Convergence considerations

Theorem 5.2 (abscissa of absolute convergence):

Let $f$ be an arithmetic function such that the series of absolute values associated to the Dirichlet series associated to $f$

$\sum _{n=1}^{\infty }\left|{\frac {f(n)}{n^{s}}}\right|$

neither diverges at all $s\in \mathbb {C}$ nor converges for all $s\in \mathbb {C}$. Then there exists $\sigma _{a}\in \mathbb {R}$, called the abscissa of absolute convergence, such that the Dirichlet series associated to $f$ converges absolutely for all $\sigma +it$, $\sigma >\sigma _{a}$ and it's associated series of absolute values diverges for all $\sigma +it$, $\sigma <\sigma _{a}$.

Proof:

Denote by $S$ the set of all real numbers $\sigma$ such that

$\sum _{n=1}^{\infty }\left|{\frac {f(n)}{n^{s}}}\right|$

diverges. Due to the assumption, this set is neither empty nor equal to $\mathbb {C}$. Further, if $\sigma _{0}+it_{0}\notin S$, then for all $\sigma >\sigma _{0}$ and all $t$ $\sigma +it\notin S$, since

$\left|{\frac {f(n)}{n^{s_{0}}}}\right|={\frac {|f(n)|}{n^{\sigma _{0}}}}\geq {\frac {|f(n)|}{n^{\sigma }}}=\left|{\frac {f(n)}{n^{s}}}\right|$

and due to the comparison test. It follows that $S$ has a supremum. Let $\sigma _{a}$ be that supremum. By definition, for $\sigma >\sigma _{a}$ we have convergence, and if we had convergence for $\sigma <\sigma _{a}$ we would have found a lower upper bound due to the above argument, contradicting the definition of $\sigma _{a}$.$\Box$

Theorem 5.3 (abscissa of conditional convergence):

Formulas

Theorem 8.4 (Euler product):

Let $f$ be a strongly multiplicative function, and let $s\in \mathbb {C}$ such that the corresponding Dirichlet series converges absolutely. Then for that series we have the formula

$\sum _{n=1}^{\infty }{\frac {f(n)}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-{\frac {f(p)}{p^{s}}}}}$.

Proof:

This follows directly from theorem 2.11 and the fact that $f$ strongly multiplicative $\Rightarrow$ ${\frac {f(n)}{n^{s}}}$ strongly multiplicative.$\Box$

Formulas for number-theoretic functions

Formulas for the Möbius μ function

Lemma 2.9:

$\sum _{d|n}\mu (d){\frac {n}{d}}=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)$.

Proof:

For $\kappa \in \mathbb {Z} ^{r}$ a multiindex, $\alpha \in \{0,1\}^{r}$ and $Q\in \mathbb {C} ^{r}$ a vector define

$Q^{\alpha }:=\prod _{j=1}^{r}q_{j}^{\alpha _{j}}$,

$Q^{\kappa }:=(q_{1}^{k_{1}},\ldots ,q_{r}^{k_{r}})$.

Let $n=(P^{\kappa })^{1}=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$. Then

${\begin{aligned}\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)&=\sum _{\alpha \in \{0,1\}^{r}}(P^{\kappa })^{\alpha }(P^{\kappa -1})^{1-\alpha }(-1)^{|}{1-\alpha |}\\&=\sum _{d|n}\mu (d){\frac {n}{d}}\end{aligned}}$.$\Box$

Lemma 2.10:

$\varphi =\mu *I_{1}$.

Proof 1:

We prove the lemma from lemma 2.14.

We have by lemma 2.14

${\begin{aligned}\varphi (n)&=\sum _{k=1}^{n}\delta (\gcd(k,n))\\&=\sum _{k=1}^{n}\sum _{d|\gcd(k,n)}\mu (d)\\&=\sum _{d|n}\sum _{k=1}^{n}[d|k]\mu (d)\\&=\sum _{d|n}\sum _{j=1}^{n/d}\mu (d)\end{aligned}}$$\Box$

Proof 2:

We prove the lemma from the product formula for Euler's totient function and lemma 2.9. Indeed, for $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$

$\varphi (n)=\prod _{j=1}^{r}(p_{j}^{k_{j}}-p_{j}^{k_{j}-1})=\mu *I_{1}$.$\Box$

Lemma 2.14:

$E*\mu =\delta$.

Proof 1:

We use the Möbius inversion formula.

Indeed, $E(n)=\sum _{d|n}\delta (d)=1$, and hence $\delta =\mu *E$.$\Box$

Proof 2:

We use multiplicativity.

Indeed, for a prime $p$, $k\in \mathbb {N}$ we have

$E*\mu (p^{k})=\sum _{j=0}^{k}\mu (p^{j})=\mu (1)+\mu (p)=0$,

and thus due to the multiplicativity of $\mu$ and $E$ $E*\mu (n)=0$ if $n$ contains at least one prime factor. Since further $E*\mu (1)=1$ the claim follows.$\Box$

Proof 3:

We prove the lemma by direct computation. Indeed, if $1\neq n=P^{\kappa }$, then

${\begin{aligned}E*\mu (n)&=\sum _{d|n}\mu (d)\\&=\sum _{\alpha \in \{0,1\}^{r}}\mu (P^{\alpha })\\&=\sum _{\beta \in \{0,1\}^{r-1}}\left(\mu (P^{(0,\beta )})+\mu (P^{(1,\beta )})\right)=0\end{aligned}}$.$\Box$

Proof 4:

We prove the lemma from the Binomial theorem and combinatorics.

Let $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$. From combinatorics we note that for $m\leq r$, there exist ${\binom {m}{r}}$ distinct ways to pick a subset $I\subseteq \{1,\ldots ,r\}$ such that $|I|=m$. Define $\alpha _{I}=(\alpha _{1},\ldots ,\alpha _{r})\in \{0,1\}^{r}$ where $\alpha _{j}=1\Leftrightarrow j\in I$. Then, by the Binomial theorem

${\begin{aligned}E*\mu (n)&=\sum _{d|n}\mu (d)\\&=\sum _{I\subseteq \{1,\ldots ,r\}}\mu (P^{\alpha _{I}})\\&=\sum _{I\subseteq \{1,\ldots ,r\}}(-1)^{|I|}\\&=\sum _{j=0}^{r}{\binom {j}{r}}(-1)^{j}1^{j}=(1-1)^{r}=0\end{aligned}}$.$\Box$

Formulas for Euler's totient function

Lemma 2.11 (Gauß 1801):

$\forall n\in \mathbb {N} :n=\sum _{d|n}\varphi (d)$.

Proof 1:

We use the Möbius inversion formula, proven below without using this lemma, and lemma 2.10.

We have $\sum _{d|n}\varphi (d)=S_{\varphi }(n)$ and hence $\varphi =\mu *S_{\varphi }$ by the Möbius inversion formula. On the other hand,

$\varphi (n)=\mu *I_{1}(n)$

by lemma 2.10.

Hence, we obtain $\mu *S_{\varphi }=\mu *I_{1}$, and by cancellation of $\mu$ (the arithmetic functions form an integral domain) we get the lemma.$\Box$

Proof 2:

We use the converse of the Möbius inversion formula, proven below without using this lemma, and lemma 2.10.

Since $\varphi (n)=\mu *I_{1}(n)$ by lemma 2.10, we obtain from the converse of the Möbius inversion formula that $I_{1}(n)=S_{\varphi }(n)$.$\Box$

Proof 3:

We prove the lemma by double counting.

We first note that there are $n$ many fractions of the form ${\frac {m}{n}}$, $1\leq m\leq n$.

We now prove that there are also $\sum _{d|n}\varphi (d)$ many fractions of this form. Indeed, each fraction ${\frac {m}{n}}$, $1\leq m\leq n$ can be reduced to ${\frac {b}{d}}$, where $\gcd(b,d)=1$. $d$ is a divisor of $n$, since it is obtained by dividing $n$. Furthermore, for each divisor $d$ of $n$ there exist precisely $\varphi (d)$ many such fractions by definition of $\varphi$.$\Box$

Proof 4:

We prove the lemma by the means of set theory.

Define $S_{n,d}:=\{1\leq l\leq n|\gcd(d,l)=1\}$. Then $S_{n,d}=\{dk|1\leq k\leq n/d,\gcd(k,n)=1\}=dS_{n/d,1}$. Since $|S_{n/d,1}|=\varphi (n/d)$ and $\{1,\ldots ,n\}$ is the disjoint union of the sets $S_{n,d},d|n$, we thus have

$n=\sum _{d|n}|S_{n,d}|=\sum _{d|n}d\varphi \left({\frac {n}{d}}\right)$.$\Box$

The next theorem comprises one of the most important examples for a multiplicative function.

Theorem 2.12 (Euler 1761):

Euler's totient function is multiplicative.

Proof 1:

We prove the theorem using double counting (due to Kronecker).

By definition of $\varphi$, there are $\varphi (m)\varphi (n)$ sums of the form

${\frac {k}{m}}+{\frac {l}{n}},1\leq k\leq m,1\leq l\leq n$,

where both summands are reduced. We claim that there is a bijection

$\left\{{\frac {k}{m}}+{\frac {l}{n}}{\big |}1\leq k\leq m,1\leq l\leq n,{\frac {k}{m}},{\frac {l}{n}}{\text{ reduced}}\right\}\to \left\{{\frac {r}{mn}}{\big |}1\leq r\leq {\frac {r}{mn}}{\text{ reduced}}\right\}$.

From this would follow $\varphi (m)\varphi (n)=\varphi (mn)$.

We claim that such a bijection is given by ${\frac {k}{m}}+{\frac {l}{n}}\mapsto {\frac {nk+ml\mod mn}{nm}}$.

Well-definedness: Let ${\frac {k}{m}}$, ${\frac {l}{n}}$ be reduced. Then

${\frac {k}{m}}+{\frac {l}{n}}={\frac {kn+lm\mod mn}{nm}}$

is also reduced, for if $p|(nm)$, then without loss of generality $p|n$, and from $p|(kn+lm-cnm)$ follows $p|l$ or $p|m$. In both cases we obtain a contradiction, either to $\gcd(m,n)=1$ or to ${\frac {l}{n}}$ is reduced.

Surjectivity: Let ${\frac {r}{mn}}$ be reduced. Using the Euclidean algorithm, we find $a,b\in \mathbb {N}$ such that $an+bm=1$. Then $ran+rbm=r$. Define $k=ra\mod m$, $l=rb\mod n$. Then

$kn+lm=(ra+tm)n+(rb+sn)m\equiv r\mod mn$.

Injectivity: Let $kn+lm\equiv k'n+l'm\mod mn$. We show $k=k'$; the proof for $l=l'$ is the same.

Indeed, from $kn+lm\equiv k'n+l'm\mod mn$ follows $kn\equiv k'n\mod m$, and since $\gcd(m,n)=1$, $n$ is invertible modulo $m$, which is why we may multiply this inverse on the right to obtain $k\equiv k'\mod m$. Since $1\leq k,k'\leq m$, the claim follows.$\Box$

Proof 2:

We prove the theorem from the Chinese remainder theorem.

Let $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$. From the Chinese remainder theorem, we obtain a ring isomorphism

$\mathbb {Z} /n\to \mathbb {Z} /p_{1}^{k_{1}}\times \cdots \times \mathbb {Z} /p_{r}^{k_{r}}$,

which induces a group isomorphism

$(\mathbb {Z} /n)^{\times }\to \left(\mathbb {Z} /p_{1}^{k_{1}}\right)^{\times }\times \cdots \times \left(\mathbb {Z} /p_{r}^{k_{r}}\right)^{\times }$.

Hence, $\left|(\mathbb {Z} /n)^{*}\right|=\prod _{j=1}^{r}\left|\left(\mathbb {Z} /p_{j}^{k_{j}}\right)^{*}\right|$, and from $\forall m\in \mathbb {N} :\varphi (m)=\left|(\mathbb {Z} /m)^{*}\right|$ follows the claim.$\Box$

Proof 3: We prove the theorem from lemma 2.11 and induction (due to Hensel).

Let $m,n\in \mathbb {N}$ such that $\gcd(m,n)=1$. By lemma 2.11, we have $m=\sum _{e|m}\varphi (e)$ and $n=\sum _{d|m}\varphi (d)$ and hence

$mn=\varphi (m)\varphi (n)+\varphi (m)\sum _{d|n,d<n}\varphi (d)+\varphi (n)\sum _{e|m,e<m}\varphi (e)+\sum _{d|n,e|m \atop d<n,e<m}\varphi (d)\varphi (e)$.

Furthermore, by lemma 2.11 and the bijection from the proof of theorem 2.8,

$mn=\sum _{f|mn}\varphi (f)=\sum _{e|m,d|n}\varphi (ed)$.

By induction on $ed,en,md<mn$ we thus have

$mn=\varphi (mn)+\varphi (m)\sum _{d|n}\varphi (d)+\varphi (n)\sum _{e|m}\varphi (e)+\sum _{e|m,d|n \atop e<m,d<n}\varphi (e)\varphi (d)$.$\Box$

Proof 4: We prove the theorem from lemma 2.11 and the Möbius inversion formula.

Indeed, from lemma 2.10 and the Möbius inversion formula, we obtain

$\varphi =\mu *I_{1}$,

which is why $\varphi$ is multiplicative as the convolution of two multiplicative functions.$\Box$

Proof 5: We prove the theorem from Euler's product formula.

Indeed, if $m=P^{\kappa }$ and $n=Q^{\iota }$ and $\gcd(m,n)=1$, then $P\cap Q=\emptyset$ and hence

$\prod _{p|n}(p^{\kappa _{p}}-p^{\kappa _{p}-1})\prod _{q|n}(q^{\iota }-q^{\iota _{q}-1})=\varphi (mn)$.$\Box$

Theorem 2.15 (Möbius inversion formula):

Let $f$ be an arithmetical function and define

$S_{f}(n):=\sum _{d|n}f(d)=f*E(n)$.

Then

$f=\mu *S_{f}=\sum _{d|n}\mu (d)S_{f}\left({\frac {n}{d}}\right)$.

Proof:

By lemma 2.14 and associativity of convolution,

$\mu *S_{f}=\mu *f*E=\mu *E*f=\delta *f=f$.$\Box$

Theorem 2.16 (Product formula for Euler's totient function):

Let $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$, where $p_{1},\ldots ,p_{r}$ are pairwise different prime numbers and $k_{1},\ldots ,k_{r}\in \mathbb {N}$ (recall that every number has such a decomposition by the fundamental theorem of arithmetic. Then

$\varphi (n)=n\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)$.

Proof 1:

We prove the theorem from lemma 2.10 and the fact that $\varphi$ is multiplicative.

Indeed, let $p$ be a prime number and let $k\in \mathbb {N}$. Then $\varphi (p^{k})=p^{k}-p^{k-1}$, since

$\varphi (p^{k})=(\mu *I_{1})(p^{k})=\sum _{j=0}^{k}\mu (p^{j})p^{k-j}$

by lemma 2.10. Therefore,

$\varphi (n)=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)=n\prod _{j=1}^{r}$,

where the latter equation follows from

${\begin{aligned}n\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)&=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)\\&=\prod _{j=1}^{r}p_{j}^{k_{j}}\left(1-{\frac {1}{p_{j}}}\right)\\&=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)\end{aligned}}$.$\Box$

Proof 2:

We prove the identity by the means of probability theory.

Let $n\in \mathbb {N}$, $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$. Choose $\Omega =\{1,\ldots ,n\}$, ${\mathcal {F}}=2^{\Omega }$, $P(A):={\frac {|A|}{n}}$. For $j\in \{1,\ldots ,r\}$ define the event $E_{p_{j}}:=\{1\leq k\leq n|p_{j}|n\}$. Then we have

$P\left({\overline {E_{p_{1}}}}\cap \cdots \cap {\overline {E_{p_{r}}}}\right)={\frac {\varphi (n)}{n}}$.

On the other hand, for each $J=\{j_{1},\ldots ,j_{l}\}\subseteq \{1,\ldots ,r\}$, we have

${\begin{aligned}P\left(E_{p_{j_{1}}}\cap \cdots \cap E_{p_{j_{1}}}\right)&=P\left(\left\{1\leq k\leq n{\big |}\prod _{j\in J}p_{j}|k\right\}\right)\\&={\frac {1}{\prod _{j\in J}p_{j}}}=\prod _{j\in J}P\left(E_{p_{j}}\right)\end{aligned}}$.

Thus, it follows that $E_{p_{1}},\ldots ,E_{p_{r}}$ are independent. But since events are independent if and only if their complements are, we obtain

${\frac {\varphi (n)}{n}}=P\left({\overline {E_{p_{1}}}}\cap \cdots \cap {\overline {E_{p_{r}}}}\right)=P\left({\overline {E_{p_{1}}}})\right)\cdots P\left({\overline {E_{p_{r}}}}\right)=\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)$.$\Box$

Proof 3:

We prove the identity from the Möbius inversion formula and lemmas 2.9 and 2.10.

But by the Möbius inversion formula and since by lemma 2.10 $S_{\varphi }=I_{1}$,

$\sum _{d|n}\mu (d){\frac {n}{d}}=\mu *S_{\varphi }(n)=\varphi (n)$.$\Box$

Proof 4:

We prove the identity from the inclusion–exclusion principle.

Indeed, by one of de Morgan's rules and the inclusion–exclusion principle we have for sets $A_{1},\ldots ,A_{r}\subseteq S$

${\begin{aligned}\left|\bigcap _{j=1}^{r}A_{j}\right|&=\left|S\setminus \bigcup _{j=1}^{r}\left(S\setminus A_{j}\right)\right|\\&=|S|-\left|\bigcup _{j=1}^{r}\left(S\setminus A_{j}\right)\right|\\&=|S|+\sum _{\emptyset \neq J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|\\&=\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|\end{aligned}}$,

where we use the convention that the empty intersection equals the universal set $S$. Let now $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$, and define $S=\{m|1\leq m\leq n\}$ and $A_{j}:=\{l\in S|p_{j}\not |l\}$ for $1\leq j\leq r$. Since

$\varphi (n)=\left|\bigcap _{j=1}^{r}A_{j}\right|$,

we then have

$\varphi (n)=\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|$.

But for each $J\subseteq \{1,\ldots ,r\}$, we have

${\begin{aligned}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|&=\left\{1\leq l\leq n{\big |}\forall j\in J:p_{j}|l\right\}\\&=\left\{1\leq l\leq n{\big |}\left(\prod _{j\in J}p_{j}\right)|l\right\}={\frac {n}{\prod _{j\in J}p_{j}}}\end{aligned}}$.

It follows

$\varphi (n)=n\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}{\frac {1}{\prod _{j\in J}p_{j}}}$,

and since

$\prod {m=1}^{r}\left(1-{\frac {1}{p_{m}}}\right)=\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}{\frac {1}{\prod _{j\in J}p_{j}}}$,

the theorem is proven.$\Box$

Formulas for the von Mangoldt function

Theorem 8.? (The Selberg identity):

Partial fraction decomposition

Existence theorem

Theorem 2.1 (Existence theorem of the partial fraction decomposition):

Let $f,g$ be polynomials over a unique factorisation domain, and let $g=\prod _{j=1}^{n}p_{j}^{k_{j}}$, where the $p_{j}$ are irreducible. Then we may write

${\frac {f(x)}{g(x)}}=q(x)+\sum _{j=1}^{n}\sum _{l=1}^{k_{j}}{\frac {a_{l,j}(x)}{p_{j}(x)^{l}}}$,

where $a_{l,j}$ are polynomials of degree strictly less than $p_{j}$ and $q$ is a polynomial. The term on the right hand side is called the partial fraction decomposition of ${\frac {f}{g}}$.

Proof:

We proceed by induction on $n$. For $n=1$, the statement is true since by division with remainder, we may write

$f(x)=q_{1}(x)p_{1}(x)+r(x)$

with $\deg(r)<\deg(p_{1})$ to obtain

${\frac {f(x)}{g(x)}}={\frac {q_{1}(x)}{p_{1}(x)^{k_{1}-1}}}+{\frac {r(x)}{g(x)}}$,

and we have reduced the degree of the denominator by one (the latter summand already satisfies the required condition). By repetition of this process, we eventually obtain a denominator of one and thus a polynomial.

Let now the hypothesis be true for $n\in \mathbb {N}$, and assume that $g=\prod _{j=1}^{n+1}p_{j}^{k_{j}}$. Write $G=\prod _{j=1}^{n}p_{j}^{k_{j}}$ and $H=p_{n+1}^{k_{n+1}}$. By irreducibility, $\gcd(G,H)=1$. Hence, we find polynomials $S,T$ such that $1=SG+TH$. Then

${\frac {f}{g}}={\frac {f(SG+TH)}{g}}={\frac {fSG}{g}}+{\frac {fTH}{g}}$.

Each of the summands of the last term can by the induction hypothesis be written in the desired form.$\Box$

Technique

No matter how complicated our fraction of polynomials ${\frac {f}{g}}$ may be, we can give the partial fraction decomposition in finite time, using easy techniques. The method, which for the sake of simplicity differs from the one given in the above constructive existence proof, goes as follows:

1. Split the polynomial $g$ into irreducible factors.
2. Using division with remainder of $f$ by $g$, reduce to the case $\deg(f)<\deg(g)$ (the resulting polynomial $q$ is allowed in the formula of theorem 2.1).
3. Solve the equation given in theorem 2.1 for the $a_{l,j}$ (this is equivalent to solving a system of linear equations; namely multiply by $g$ and then equate coefficients).

Theorem 2.2:

The algorithm given above always terminates and gives the partial fraction decomposition of ${\frac {f}{g}}$.

Proof: Due to theorem 2.1, in step three we do obtain a system of linear equations which is solvable. Hence follow termination and correctness.$\Box$

Tools from complex analysis

Infinite products

Lemma 5.1 (Convergence of real products):

Let $(a_{n})_{n\in \mathbb {N} }$ be such that

$\sum _{n=1}^{\infty }|a_{n}|$

converges absolutely. Then if $\forall n\in \mathbb {N} :|b_{n}|\leq |a_{n}|$,

$\prod _{n=1}^{\infty }(1+b_{n})$

converges.

Proof: Without loss of generality, we assume $|b_{n}|<{\frac {1}{2}}$ for all $n\in \mathbb {N}$.

Denote

$p_{n}:=\prod _{j=1}^{n}(1+b_{n})$.

Then we have

$q_{n}:=\log(p_{n})=\sum _{j=1}^{n}\log(1+b_{j})$.

We now apply the Taylor formula of first degree with Lagrange remainder to $\log(1+x)$ at $1$ to obtain for $|x|<{\frac {1}{2}}$

$\log(1+x)={\frac {1}{2}}x-{\frac {1}{2(1+\xi )^{2}}}x^{2}$, $\xi \in \left({\frac {1}{2}},{\frac {3}{2}}\right)$.

Hence, we have for $|x|<{\frac {1}{2}}$

$|\log(1+x)|\leq \left|{\frac {1}{2}}x-{\frac {1}{2(1+\xi )^{2}}}x^{2}\right|\leq |x|$, $\xi \in \left({\frac {1}{2}},{\frac {3}{2}}\right)$.

Hence, $|\log(1+b_{j})|\leq |b_{j}|$ and thus we obtain the (even absolute) convergence of the $q_{n}$; thus, by the continuity of the exponential, also the $p_{n}$ converge.$\Box$

Theorem 5.2 (Comparison test for complex products):

Assume that $(a_{n})_{n\in \mathbb {N} }$ is a non-negative real sequence such that

$\prod _{j=1}^{\infty }(1+a_{j})$

converges. Assume further that $(s_{n})_{n\in \mathbb {N} }$ is a sequence of complex numbers such that $\forall n\in \mathbb {N} :|s_{n}|\leq a_{n}$. Then also

$\prod _{n=1}^{\infty }(1+s_{n})$

converges. Furthermore, for all $n\in \mathbb {N}$

$\left|\prod _{j=1}^{\infty }(1+s_{j})-\prod _{j=1}^{n}(1+s_{j})\right|\leq \left|\prod _{j=1}^{\infty }(1+a_{j})-\prod _{j=1}^{n}(1+a_{j})\right|$.

Proof:

We define

$p_{n}:=\prod _{j=1}^{n}(1+s_{j})$, $q_{n}:=\prod _{j=1}^{n}(1+a_{j})$. We note that

$|p_{n}|\leq \prod _{j=1}^{n}(1+|s_{j}|)\leq q_{n}$.

Without loss of generality we may assume that all the products are nonzero; else we have immediate convergence (to zero).

We now prove that $(p_{n})_{n\in \mathbb {N} }$ is a Cauchy sequence. Indeed, we have

$|p_{n+k}-p_{n}|=|p_{n}|\left|{\frac {p_{n+k}}{p_{n}}}-1\right|$

and furthermore

${\begin{aligned}\left|{\frac {p_{n+k}}{p_{n}}}-1\right|&=\left|s_{n+1}+\cdots +s_{n+k}+s_{n+1}s_{n+2}+\cdots +s_{n+1}\cdots s_{n+k}\right|\\&\leq |s_{n+1}|+\cdots +|s_{n+k}|+|s_{n+1}s_{n+2}|+\cdots +|s_{n+1}\cdots s_{n+k}|\\&\leq a_{n+1}+\cdots +a_{n+k}+a_{n+1}a_{n+2}+\cdots +a_{n+1}\cdots a_{n+k}\\&={\frac {q_{n+k}}{q_{n}}}-1=\left|{\frac {q_{n+k}}{q_{n}}}-1\right|\end{aligned}}$

and therefore

$|p_{n+k}-p_{n}|=|p_{n}|\left|{\frac {p_{n+k}}{p_{n}}}-1\right|\leq |q_{n}|\left|{\frac {q_{n+k}}{q_{n}}}-1\right|=|q_{n+k}-q_{n}|$.

Since $q_{n}\to q$, it is a Cauchy sequence, and thus, by the above inequality, so is $(p_{n})_{n\in \mathbb {N} }$. The last claim of the theorem follows by taking $k\to \infty$ in the above inequality.$\Box$

Theorem 5.3 (Sum test for complex products):

Let $(a_{n})_{n\in \mathbb {N} }$ be a real sequence such that

$\sum _{n=1}^{\infty }|a_{n}|$

converges absolutely. Then if $\forall n\in \mathbb {N} :|s_{n}|\leq |a_{n}|$,

$\prod _{n=1}^{\infty }(1+s_{n})$

converges, where $(s_{n})_{n\in \mathbb {N} }$ is a complex sequence. Furthermore, for all $n\in \mathbb {N}$

$\left|\prod _{j=1}^{\infty }(1+s_{j})-\prod _{j=1}^{n}(1+s_{j})\right|\leq \left|\prod _{j=1}^{\infty }(1+|a_{j}|)-\prod _{j=1}^{n}(1+|a_{j}|)\right|$.

Proof 1:

We prove the theorem using lemma 5.1 and the comparison test.

Indeed, by lemma 5.1 the product

$\prod _{j=1}^{\infty }(1+|a_{j}|)$

converges. Hence by theorem 5.2, we obtain convergence and the desired inequality.$\Box$

Proof 2 (without the inequality):

We prove the theorem except the inequality at the end from lemma 5.1 and by using the Taylor formula on $\arcsin$.

We define $p_{n}:=\prod _{j=1}^{n}(1+s_{j})$. Then since every complex number satisfies $z=|z|e^{i\arg(z)}$, we need to prove the convergence of the sequences $(|p_{n}|)_{n\in \mathbb {N} }$ and $(\arg(p_{n}))_{n\in \mathbb {N} }$.

For the first sequence, we note that the convergence of $(|p_{n}|)_{n\in \mathbb {N} }$ is equivalent to the convergence of $(|p_{n}|^{2})_{n\in \mathbb {N} }$. Now for each $k\in \mathbb {N}$

$|1+$

Theorem 5.4 (Holomorphic products):

Let $(f_{n})_{n\in \mathbb {N} }$ be a sequence of holomorphic functions in a domain $D$ such that for each $z\in D$ we can find a compact $K\ni z$ and a sequence $(a_{n}^{K})_{n\in \mathbb {N} }$ such that $\forall n\in \mathbb {N} :\forall w\in K:|f_{n}(z)|\leq |a_{n}^{K}|$ and

$\sum _{n=1}^{\infty }|a_{n}^{K}|$

converges absolutely. Then

$g(z):=\prod _{n=1}^{\infty }\left(1+f_{n}(z)\right)$

defines a holomorphic function.

Proof:

First, we note that $g(z)$ is well-defined for each $z$ due to theorem 5.2. In order to prove that the product is holomorphic, we use the fact from complex analysis that if a sequence of functions converging locally uniformly to another function has infinitely many holomorphic members, then the limit is holomorphic as well. Indeed, we note by the inequality in theorem 5.3, that we are given uniform convergence. Hence, the theorem follows.$\Box$

The Weierstraß factorisation

The following lemma is of great importance, since we can deduce three important theorems from it:

1. The existence of holomorphic functions with prescribed zeroes
2. The Weierstraß factorisation theorem (a way to write any holomorphic function made up from linear factors and the exponential)
3. The Mittag-Leffler theorem (named after Gösta Mittag-Leffler (one guy))

Lemma 5.5:

Let $(a_{n})_{n\in \mathbb {N} }$ be a sequence of complex numbers such that

$0<|a_{1}|\leq |a_{2}|\leq \cdots$

and

$\lim _{n\to \infty }|a_{n}|=\infty$.

Then the function

$\prod _{n=1}^{\infty }\left(1-{\frac {s}{a_{n}}}\right)e^{\sum _{k=1}^{n-1}(-1)^{k+1}{\frac {s^{k}}{ka_{n}^{k}}}}$

has exactly the zeroes $\{a_{n}|n\in \mathbb {N} \}$ in the correct multiplicity.

Proof:

Define for each $n\in \mathbb {N}$

$u_{n}(s):=\left(1-{\frac {s}{a_{n}}}\right)e^{\sum _{k=1}^{n-1}(-1)^{k+1}{\frac {s^{k}}{ka_{n}^{k}}}}$.

Our plan is to prove that $\prod _{n=1}^{\infty }u_{n}(s)$ converges uniformly in every subcircle of the circle of radius $|a_{N}|$ for every $N\in \mathbb {N}$. Since the function $z\mapsto \log(1+z)$ is holomorphic in a unit ball around zero, it is equal to its Taylor series there, i.e.

$\log(1+z)=\sum _{k=1}^{\infty }{\frac {z^{k}}{k}}$.

Hence, for $|s|<|a_{n}|$

$\log \left(u_{n}(s)\right)=\sum _{k=n}^{\infty }(-1)^{k+1}{\frac {s^{k}}{ka_{n}^{k}}}$.

Let now $N\in \mathbb {N}$ be given and $n\geq N$ be arbitrary. Then we have for $|s|<(1-\epsilon )|a_{N}|$, $\epsilon >0$ arbitrary

${\begin{aligned}\left|\log \left(u_{n}(s)\right)\right|&=\left|\sum _{k=n}^{\infty }(-1)^{k+1}{\frac {s^{k}}{ka_{n}^{k}}}\right|\\&\leq \sum _{k=n}^{\infty }\left|{\frac {s^{k}}{ka_{n}^{k}}}\right|\\&\leq \sum _{k=n}^{\infty }(1-\epsilon )^{k}&=(1-\epsilon )^{n}{\frac {1}{\epsilon }}\end{aligned}}$.

Now summing over $n\geq N$, we obtain

$\left|\sum _{n=N}^{\infty }\log \left(u_{n}(s)\right)\right|\leq \sum _{n=N}^{\infty }(1-\epsilon )^{n}{\frac {1}{\epsilon }}<\infty$

for all $|s|<(1-\epsilon )|a_{N}|$. Hence, we have uniform convergence in that circle; thus the sum of the logarithms is holomorphic, and so is the original product if we plug everything into the exponential function (note that we do have $\exp(\log(z))=z$ even if $z$ is an arbitrary complex number).$\Box$

Note that our method of proof was similar to how we proved lemma 5.1. In spite of this, it is not possible to prove the above lemma directly from theorem 5.4 since the corresponding series does not converge if the $a_{n}$ are chosen increasing too slowly.

Theorem 5.6 (Holomorphic functions with given zeroes):

Let $(s_{n})_{n\in \mathbb {N} }$ be a sequence of complex numbers which does not have an accumulation point. Then the function

$s\mapsto s^{m}\prod _{n=1}^{\infty }\left(1-{\frac {s}{a_{n}}}\right)e^{\sum _{k=1}^{n-1}(-1)^{k+1}{\frac {s^{k}}{ka_{n}^{k}}}}$

has zeroes $\{s_{n}|n\in \mathbb {N} \}$ with the right multiplicity, where the sequence $(a_{n})_{n\in \mathbb {N} }$ are the nonzero elements of the sequence $(s_{n})_{n\in \mathbb {N} }$ ordered ascendingly with respect to their absolute value and $m\in \mathbb {N}$ is the number of zeroes within the sequence $(s_{n})_{n\in \mathbb {N} }$.

Proof:

We order $(s_{n})_{n\in \mathbb {N} }$ increasingly according to the modulus $|s_{n}|$ and the standard greater or equal order on the real numbers. We go on to observe that then $|s_{n}|\to \infty$, since if it were to remain bounded, there would be an accumulation point according to the Heine–Borel theorem. Also, the sequence is zero only finitely many often (otherwise zero would be an accumulation point). After eliminating the zeroes from the sequence $(s_{n})_{n\in \mathbb {N} }$ we call the remaining sequence $(a_{n})_{n\in \mathbb {N} }$. Let $m\in \mathbb {N}$ the number of zeroes in $(s_{n})_{n\in \mathbb {N} }$. Then due to lemma 5.5, the function

$s^{m}\prod _{n=1}^{\infty }\left(1-{\frac {s}{a_{n}}}\right)e^{\sum _{k=1}^{n-1}(-1)^{k+1}{\frac {s^{k}}{ka_{n}^{k}}}}$

has the required properties.$\Box$

Theorem 5.7 (Weierstraß factorisation theorem):

Let $f:\mathbb {C} \to \mathbb {C}$ be holomorphic and not the constant zero function with zeroes $\{s_{n}|n\in \mathbb {N} \}$, let $(a_{n})_{n\in \mathbb {N} }$ are the nonzero elements of the sequence $(s_{n})_{n\in \mathbb {N} }$ ordered ascendingly with respect to their absolute value, and if $f(0)=0$, let $m$ be the order of the zero $0$ of $f$. Then there exists a holomorphic function $H:\mathbb {C} \to \mathbb {C}$ such that

$\forall z\in \mathbb {C} :f(z)=z^{m}e^{H(z)}\prod _{n=1}^{\infty }\left(1-{\frac {z}{a_{n}}}\right)e^{\sum _{k=1}^{n-1}(-1)^{k+1}{\frac {z^{k}}{ka_{n}^{k}}}}$.

Proof:

First, we note that $(s_{n})_{n\in \mathbb {N} }$ does not have an accumulation point, since otherwise $f$ would be the constant zero function by the identity theorem from complex analysis. From theorem 5.6, we obtain that the function $g(s):=s^{m}\prod _{n=1}^{\infty }\left(1-{\frac {s}{a_{n}}}\right)e^{\sum _{k=1}^{n-1}(-1)^{k+1}{\frac {s^{k}}{ka_{n}^{k}}}}$ has exactly the zeroes $\{s_{n}|n\in \mathbb {N} \}$ with the right multiplicity, where the sequence $(a_{n})_{n\in \mathbb {N} }$ are the nonzero elements of the sequence $(s_{n})_{n\in \mathbb {N} }$ ordered ascendingly with respect to their absolute value and $m\in \mathbb {N}$ is the number of zeroes within the sequence $(s_{n})_{n\in \mathbb {N} }$. We have that $f/g$ has no zeroes and is bounded and hence holomorphic due to Riemann's theorem on resolvable singularities. For, if $f/g$ were unbounded, it would have a singularity at a zero $z_{0}$ of $g$. This singularity can not be essential since dividing $g$ by finitely many linear factors would eliminate that singularity. Hence we have a pole, and this would be resolvable by multiplying linear factors to $f/g$. But then $g/f$ has a zero of the order of that pole, which is not possible since we may eliminate all the zeroes of $g/f$ by writing $f=(z-z_{0})^{l}h$, $h$ holomorphic and nonzero at $z_{0}$, where $l$ is the order of the zero of $f$ at $z_{0}$.

Hence, $f/g$ has a holomorphic logarithm on $\mathbb {C}$, which we shall denote by $H$. This satisfies

$z^{m}e^{H(z)}\prod _{n=1}^{\infty }\left(1-{\frac {z}{a_{n}}}\right)e^{\sum _{k=1}^{n-1}(-1)^{k+1}{\frac {z^{k}}{ka_{n}^{k}}}}=f(z)$.$\Box$

Corollary 5.8 (Mittag-Leffler's theorem):

Let $(s_{n})_{n\in \mathbb {N} }$ be a sequence of complex numbers which does not have an accumulation point. Then there exists a meromorphic function $f:\mathbb {C} \setminus \{s_{n}|n\in \mathbb {N} \}\to \mathbb {C}$ which has exactly the poles $\{s_{n}|n\in \mathbb {N} \}$, where the pole $z_{0}\in \{s_{n}|n\in \mathbb {N} \}$ has order $l:=|\{n\in \mathbb {N} |s_{n}=z_{0}\}|$.

Proof:

From theorem 5.7 we obtain a function $g$ with zeroes $\{s_{n}|n\in \mathbb {N} \}$ in the right multiplicity. Set $f=1/g$.$\Box$

The Hadamard factorisation

In this subsection, we strive to factor certain holomorphic functions in a way that makes them even easier to deal with than the Weierstraß factorisation. This is the Hadamard factorisation. It only works for functions satisfying a certain growth estimate, but in fact, many important functions occurring in analytic number theory do satisfy this estimate, and thus that factorisation will give us ways to prove certain theorems about those functions.

In order to prove that we may carry out a Hadamard factorisation, we need some estimates for holomorphic functions as well as some preparatory lemmata.

Estimates for holomorphic functions

Theorem 5.9:

Let $f:\mathbb {C} \to \mathbb {C}$ be a holomorphic function such that $f(0)\neq 0$, and let $(s_{n})_{n\in \mathbb {N} }$ be the sequence of zeroes of that function ordered ascendingly by absolute value. Let $R>r>0$. If we denote the number of zeroes of $f$ inside $B_{r}(0)$ by $N(r)$, then

$\left({\frac {R}{r}}\right)^{N(r)}\leq {\frac {M(r)}{|f(0)|}}$.

Proof:

Set $m:=N(r)$ and define the function $g:\mathbb {C} \to \mathbb {C}$ by

$g(s):={\begin{cases}f(s)\prod _{j=1}^{m}{\frac {R^{2}-s{\overline {s_{j}}}}{R(s-s_{j})}}&s\notin \{s_{1},\ldots ,s_{m}\}\\\lim _{t\to s}f(s)\prod _{j=1}^{m}{\frac {R^{2}-t{\overline {s_{j}}}}{R(t-s_{j})}}&{\text{otherwise}}\end{cases}}$,

where the latter limit exists by developing $f$ into a power series at $s$ and observing that the constant coefficient vanishes. By Riemann's theorem on removable singularities, $g$ is holomorphic. We now have

$|g(0)|=|f(0)|\prod _{j=1}^{m}{\frac {R}{|s_{j}|}}$,

and if further $|s|=R$, then ${\frac {|s|}{R}}=1$ and hence we may multiply that number without change to anything to obtain for $j\in \{1,\ldots ,m\}$

${\begin{aligned}\left|{\frac {R^{2}-s{\overline {s_{j}}}}{R(s-s_{j})}}\right|=1&\Leftrightarrow {\frac {|s|}{R}}\left|{\frac {R^{2}-s{\overline {s_{j}}}}{R(s-s_{j})}}\right|=1\\&\Leftrightarrow \left|{\frac {R^{2}s-s^{2}{\overline {s_{j}}}}{R^{2}s-R^{2}s_{j}}}\right|=1\\&\Leftrightarrow \left|{\frac {R^{2}-s{\overline {s_{j}}}}{R^{2}-R^{2}{\frac {s_{j}}{s}}}}\right|=1\end{aligned}}$.

Now writing $s=\sigma +it$ and $s_{j}=\sigma _{j}+it_{j}$, we obtain on the one hand

$s{\overline {s_{j}}}=\sigma \sigma _{j}+tt_{j}+i(t\sigma _{j}-\sigma t_{j})$

and on the other hand

$R^{2}{\frac {s}{s_{j}}}=R^{2}{\frac {\sigma _{j}\sigma +t_{j}t+i(t_{j}\sigma -\sigma _{j}t)}{\sigma ^{2}+t^{2}}}$.

Hence,

${\overline {s{\overline {s_{j}}}}}=R^{2}{\frac {s}{s_{j}}}$,

which is why both $s{\overline {s_{j}}}$ and $R^{2}{\frac {s}{s_{j}}}$ have the same distance to $R^{2}$, since $R^{2}$ lies on the real axis.

Hence, due to the maximum principle, we have

$|f(0)|\prod _{j=1}^{m}{\frac {R}{|s_{j}|}}=|g(0)|\leq \max _{|s|=R}|g(s)|=\max _{|s|=R}|f(s)|$.$\Box$

Theorem 5.10:

Let $s_{0}\in \mathbb {C}$, let $f:\mathbb {C} \to \mathbb {C}$ be holomorphic within $B_{R}(s_{0})$ and define $M:=\max _{|s|=R}\Re f(s)$. Then

$\forall n\in \mathbb {N} :{\frac {|f^{(n)}(s_{0})|}{n!}}\leq {\frac {2}{R^{n}}}(M-\Re f(s_{0}))$.

Proof:

First, we consider the case $s_{0}=0$ and $f(0)=0$. We may write $f$ in its power series form

$f(s)=\sum _{j=1}^{\infty }a_{j}s^{j},s\in B_{R}(0)$,

where $a_{j}={\frac {f^{(j)}(0)}{j!}}$. If we write $\partial B_{R}(0)\ni s=Re^{i\varphi }$ and $a_{j}=|a_{j}|e^{\varphi _{j}}$, we obtain by Euler's formula

$\Re \left(a_{j}s\right)=|a_{j}|R^{j}\cos(j\varphi +\varphi _{j})$

and thus

$\Re f(s)=\sum _{j=1}^{\infty }|a_{j}|R^{j}\cos(j\varphi +\varphi _{j})$.

Since the latter sum is majorised by the sum

$\sum _{j=1}^{\infty }|a_{j}|R^{j}$,

it converges absolutely and uniformly in $\varphi$. Hence, by exchanging the order of integration and summation, we obtain

$\int _{0}^{2\pi }\Re f(Re^{i\varphi })d\varphi =0$

due to

$\int _{0}^{2\pi }\cos(j\varphi +\varphi _{j})d\varphi =\left[{\frac {1}{j}}\sin \left(j\varphi +\varphi _{j}\right)\right]_{\varphi =0}^{\varphi =2\pi }=0$

and further for all $n\in \mathbb {N}$

$\int _{0}^{2\pi }\Re f(Re^{i\varphi })\cos(n\varphi +\varphi _{n})d\varphi =\pi |a_{n}|R^{n}$

due to

$\int _{0}^{2\pi }\cos(j\varphi +\varphi _{j})\cos(n\varphi +\varphi _{n})d\varphi =\pi \delta _{j,n}$,

as can be seen using integration by parts twice and $1=\sin ^{2}+\cos ^{2}$. By monotonicity of the integral, we now have

$\pi |a_{n}|R^{n}\leq \int _{0}^{2\pi }\Re f(Re^{i\varphi })(1+\cos(n\varphi +\varphi _{n}))d\varphi \leq 2\pi M$.

This proves the theorem in the case $s_{0}=0=f(0)$. For the general case, we define

$g(s):=f(s+s_{0})-f(s_{0})$.

Then $s_{0}=0=g(0)$, hence by the case we already proved

$\left|{\frac {f^{n}(s_{0})}{n!}}\right|=\left|{\frac {g^{n}(0)}{n!}}\right|\leq {\frac {2}{R^{n}}}\max _{|s|=R}\Re g(s)={\frac {2}{R^{n}}}(M-\Re f(s_{0}))$.$\Box$

Theorem 5.11:

Further preparations

Definition 5.12 (exponent of convergence):

Let $(s_{n})_{n\in \mathbb {N} }$ be a sequence of complex numbers not containing zero such that

$\sum _{n=1}^{\infty }{\frac {1}{|s_{n}|^{\beta }}}$

converges for a $\beta >0$. Then

$\sigma :=\inf \left\{\beta >0{\big |}\sum _{n=1}^{\infty }{\frac {1}{|s_{n}|^{\beta }}}<\infty \right\}$

is called the exponent of convergence of the sequence $(s_{n})_{n\in \mathbb {N} }$.

Definition 5.13 (holomorphic functions of finite order):

Let $f:\mathbb {C} \to \mathbb {C}$ be holomorphic, and define for $r\geq 0$

$M(r):=\max _{|s|=r}|f(s)|$.

If there exists $\alpha >0$ such that

$\forall r>r_{0}:M(r)<e^{r^{\alpha }}$

for a suitable $r_{0}>0$, then $f$ is said to be of finite order. In this case,

$\rho :=\inf \left\{\alpha >0{\big |}\exists r_{0}>0:\forall r>r_{0}:M(r)<e^{r^{\alpha }}\right\}$

is called the order of $f$.

Lemma 5.14: