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

Exercises

• Exercise 2.1.1: Compute $\phi (20)$, $\phi (17)$ and $\phi (22)$.
• Exercise 2.1.2: Compute $\mu (4278)$. Hint: $4278=2\cdot 3\cdot 23\cdot 31$.
• Exercise 2.1.3: Compute $\mathrm{\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

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.

Proof:

1.:

$\begin{array}{cc}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{array}$,

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

2.:

$\begin{array}{cc}f*(g*h)=f*(h*g)& =\sum _{d_1|n}f(d_1)(\sum _{d_2|\frac{n}{d_1}}g\left(\frac{n}{d_1{d}_2}\right)h(d_2))\\ & =\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{array}$,

where the last equality follows from the identity function

$Id:\{(d_1,d_2):d_2|n,d_1\left|\frac{n}{d_2}\right\}\to \{(d_1,d_2):d_1|n,d_2\left|\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)$$◻$

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

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

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

Proof:

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

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

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

$g(n)=-f(1{)}^{-1}\sum _{\genfrac{}{}{0ex}{}{d|n}{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{array}{cc}f*g(n)& =f*g(n)-f(1{)}^{-1}f*g*f(n)\\ & =f*g(n)-f^{-1}\sum _{\genfrac{}{}{0ex}{}{d|n}{d<n}}f*g(d)f\left(\frac{n}{d}\right)=0\end{array}$

$◻$

Exercises

• Exercise 2.2.1:
• Exercise 2.2.2:

Multiplicative functions

Proof:

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

$f*g(kn)=\sum _{d|(kn)}f(d)g\left(\frac{kn}{d}\right)=\sum _{\genfrac{}{}{0ex}{}{d_1|k}{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 _{\genfrac{}{}{0ex}{}{d_1|k}{d_2|n}}f(d_1{d}_2)g\left(\frac{kn}{d_1{d}_2}\right)=\sum _{\genfrac{}{}{0ex}{}{d_1|k}{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$.$◻$

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$).

Proof: Let $p_1,p_2,p_3,\dots =2,3,5,\dots$ be the ordered sequence of all prime numbers. For all $m_1,\dots ,m_r,r\in \mathbb{N}$ we have

$S_{f,r,m_1,\dots ,m_r}:=\sum _{d|(p_1^{m_1}\cdots p_r^{m_r})}f(d)=\sum _{0\le k_1\le m_1}\cdots \sum _{0\le k_r\le m_r}f\left(p_1^{k_1}\right)\cdots f\left(p_r^{k_r}\right)=\prod _{l=1}^r(\sum _{k=0}^{m_l}f(p_l^k))$

due to the multiplicativity of $f$. For each $r$, we successively take $m_1\to \mathrm{\infty }$, ..., $m_r\to \mathrm{\infty }$ and then $r\to \mathrm{\infty }$. It follows from the definitions and the rule $x_n\to x\Rightarrow y{x}_n\to yx$ that the right hand side converges to

$\prod _{l=1}^{\mathrm{\infty }}(\sum _{k=0}^{\mathrm{\infty }}f(p_l^k))$.

We claim that

$\underset{r\to \mathrm{\infty }}{\lim }\underset{m_1\to \mathrm{\infty }}{\lim }\cdots \underset{m_r\to \mathrm{\infty }}{\lim }{S}_{f,r,m_1,\dots ,m_r}=\sum _{j=1}^{\mathrm{\infty }}f(j)$.

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

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

Then by the fundamental theorem of arithmetic, there exists an $R\in \mathbb{N}$ and $M_1,\dots ,M_R\in \mathbb{N}$ such that

$\mathrm{\forall }j\in \{1,\dots ,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,\dots ,L_R>M_R$ and $L_{R+1},\dots ,L_T$ arbitrary that

$\begin{array}{cc}|S_{f,T,L_1,\dots ,L_T}-\sum _{j=1}^{\mathrm{\infty }}f(j)|& \le |\sum _{\genfrac{}{}{0ex}{}{d|(p_1^{L_1}\cdots p_T^{L_T})}{d\le N}}f(d)-\sum _{j=1}^{N}f(j)|+|\sum _{\genfrac{}{}{0ex}{}{d|(p_1^{L_1}\cdots p_T^{L_T})}{d>N}}f(d)-\sum _{j=N+1}^{\mathrm{\infty }}f(j)|\\ & <0+ϵ.\end{array}$

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.$◻$

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

Proof:

Due to theorem 2.9, we have

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

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

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

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 ℂ\setminus \{0\}$. Prove that the function $f(n):=\exp (\log (s)h(n))$ is multiplicative.

Bell series

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}^{\mathrm{\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}^{\mathrm{\infty }}\delta (p^j)x^j=1$

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

$\begin{array}{cc}{\phi }_p(x)& =\sum _{j=0}^{\mathrm{\infty }}\phi (p^j)x^j\\ & =\sum _{j=0}^{\mathrm{\infty }}\phi (p^j)x^j\\ & =1+\sum _{j=1}^{\mathrm{\infty }}(p^j-p^{j-1})x^j\\ & =\frac{1+x}{1-px}\end{array}$

3. The Möbius $mu$ function:

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

4. The von Mangoldt function:

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

5. The monomials:

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

6. The number of distinct prime divisors:

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

7. The number of prime divisors including multiplicity:

$\begin{array}{cc}{\mathrm{\Omega }}_p(x)& =\sum _{j=1}^{\mathrm{\infty }}j{x}^j\\ & =\frac{1}{x}\sum _{j=0}^{\mathrm{\infty }}(x^j{)}^{\prime }\\ & =\frac{1}{x}\left(\sum _{j=0}^{\mathrm{\infty }}{x}^j\right)\\ & =\frac{1}{x}\left(\frac{1}{1-x}\right)\\ & =-\frac{1}{x}\frac{1}{(1-x{)}^2}\end{array}$

8. The Liouville function:

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

Proof:

$\begin{array}{cc}{f}_p(x)g_p(x)& =(\sum _{j=0}^{\mathrm{\infty }}f(p^j)x^j)(\sum _{j=0}^{\mathrm{\infty }}g(p^j)x^j)\\ & =\sum _{k=0}^{\mathrm{\infty }}{x}^k(\sum _{j=0}^{k}f(p^j)g(p^{k-j}))\\ & =\sum _{k=0}^{\mathrm{\infty }}{x}^k(f*g)(p^k)\end{array}$$◻$

In case of multiplicativity, we have the following theorem:

Proof: $\Rightarrow$ is pretty obvious; $\Leftarrow$: $f_p(x)=g_p(x)$ as formal power series is equivalent to saying $\mathrm{\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$.$◻$

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

Derivatives

Proof:

1. is easily checked.

2.:

$\begin{array}{cc}(f*g{)}^{\prime }(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{array}$

3.

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

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

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

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