Analytic Number Theory/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