Differential Ring (2): Arithmetic Function Ring

Arithmetic Function as Differential Ring

Definition. We call the element of ${\mathrm{Hom}}_{\mathrm{Set}}({\mathbb{N}}^{+},\mathbb{C})$$\mathrm{Hom}_{\mathrm{Set}}(\mathbb N^+,\mathbb C)$ arithmetic function. We will use the notation $\mathfrak{A}$$\mathfrak A$.

Example. Euler function $\phi (n)=|(\mathbb{Z}/n\mathbb{Z}{)}^{\ast }|$$\varphi(n)=|(\mathbb Z/n\mathbb Z)^*|$, p-adic valuation $v_p(n)$$v_p(n)$...

Definition. Dirichlet convolution.

For $f,g\in \mathfrak{A}$$f,g\in\mathfrak A$, their Dirichlet convolution is defined as follows.

$$\begin{array}{}\text{(1)}& f\ast g(n)=\sum _{d_1{d}_2=n}f(d_1)g(d_2)\end{array}$$

Proposition. $(\mathfrak{A},+,\ast )$$(\mathfrak A,+,*)$ form a commutative ring.

Proof.

It is not hard to see that $(\mathfrak{A},+)$$(\mathfrak A,+)$ form an abelian group. Now we check the rest axiom.

Obviously, It is closed under $\ast$$*$, and $f\ast g=g\ast f$$f*g=g*f$.

For the associative law,

$$\begin{array}{}\text{(2)}& (f\ast g)\ast h(n)=\sum _{d_1{d}_2=n}(f\ast g)(d_1)h(d_2)=\sum _{d_1{d}_2=n}\sum _{d_3{d}_4=d_1}f(d_3)g(d_4)h(d_2)=\sum _{ijk=n}f(i)g(j)h(k)\end{array}$$

Similarly,

$$\begin{array}{}\text{(3)}& f\ast (g\ast h)=\sum _{ijk=n}f(i)g(j)h(k)\end{array}$$

Hence

$$\begin{array}{}\text{(4)}& (f\ast g)\ast h=f\ast (g\ast h)\end{array}$$

For the distributive law.

$$\begin{array}{}\text{(5)}& f\ast (g+h):=\sum _{d_1{d}_2=n}f(d_1)(g+h)(d_2)=\sum _{d_1{d}_2=n}f(d_1)(g(d_2)+h(d_2))=\sum _{d_1{d}_2=n}f(d_1)g(d_2)+\sum _{d_1{d}_2=n}f(d_1)h(d_2)=:f\ast g+f\ast h\end{array}$$

The unit of $\mathfrak{A}$$\frak A$ is $\begin{array}{c}\epsilon (n):=\{\begin{array}{l}1,n=1\\ 0,n\ge 2\end{array}\end{array}$$\varepsilon(n):=\begin{cases} 1,n=1\\0,n\ge 2 \end{cases}$ , $(f\ast \epsilon )(n)=f(n)$$(f*\varepsilon)(n)=f(n)$. For the constant function $1$$1$, we have $\begin{array}{c}(f\ast 1)(n)=\sum _{d|n}f(d)\end{array}$$(f*1)(n)=\sum_{d|n} f(d)\\$.

Hence $(\mathfrak{A},+,\ast )$$(\mathfrak A,+,*)$ is a commutative ring. $◻$$\square$

Definition. If $\partial \in \mathfrak{A}$$\partial\in\mathfrak A$ satisfies $\partial (mn)=\partial (m)+\partial (n)$$\partial(mn)=\partial(m)+\partial(n)$, then $\partial$$\partial$ is additive.

Example. $v_p(n),\log (n)$$v_p(n),\log(n)$...

Another example is from the last blog, Remember $\begin{array}{c}{d}_{\mathbb{Z}}(n)=n\sum _{i=1}^n\frac{v_{p_i}}{p_i}\end{array}$$d_{\mathbb Z}(n)=n\sum_{i=1}^n \frac{v_{p_i}}{p_i}\\$?

Proposition. $\begin{array}{c}D(n):=\frac{d_{\mathbb{z}}(n)}{n}\end{array}$$D(n):=\frac{d_{\mathbb z}(n)}{n}\\$ is additive.

Proof .

We already now that $d_{\mathbb{Z}}(mn)=d_{\mathbb{Z}}(m)n+m{d}_{\mathbb{Z}}(n)$$d_{\mathbb Z}(mn)=d_{\mathbb Z}(m)n+md_{\mathbb Z}(n)$. Hnece $\begin{array}{c}D(mn)=\frac{d_{\mathbb{Z}}(m)}{m}+\frac{d_{\mathbb{Z}}(n)}{n}\end{array}$$D(mn)=\frac{d_{\mathbb Z}(m)}{m}+\frac{d_{\mathbb Z}(n)}{n}\\$. $◻$$\square$

Proposition. $\partial \in \mathrm{Der}(\mathfrak{A})$$\partial\in\mathrm{Der}(\mathfrak A)$.

Remark.The derivation is defined by $\partial :\mathfrak{A}\to \mathfrak{A},\partial (f):=\partial \cdot f$$\partial:\mathfrak A\to\mathfrak{A},\partial(f):=\partial\cdot f$. i.e. $\partial \cdot (f+g)=\partial \cdot f+\partial \cdot g,\partial (f\ast g)=\partial \cdot f\ast g+f\ast \partial \cdot g$$\partial\cdot(f+g)=\partial\cdot f+\partial\cdot g,\partial(f*g)=\partial\cdot f*g+f*\partial\cdot g$.

Proof.

$\begin{array}{c}[\partial \cdot (f\ast g)](n)=\partial (n)\cdot (f\ast g)(n)=[\partial (d_1)+\partial (d_2)]\sum _{d_1{d}_2=n}f(d_1)g(d_2)=\sum _{d_1{d}_2=n}\partial (d_1)f(d_1)g(d_2)+\sum _{d_1{d}_2=n}\partial (d_2)f(d_1)g(d_2)\end{array}$$[\partial\cdot (f*g)](n)=\partial(n)\cdot (f*g)(n)=[\partial(d_1)+\partial(d_2)]\sum_{d_1d_2=n}f(d_1)g(d_2)=\sum_{d_1d_2=n}\partial(d_1) f(d_1)g(d_2)+\sum_{d_1d_2=n}\partial(d_2) f(d_1)g(d_2)\\$

i.e. $\partial \cdot f\ast g(n)+f\ast \partial \cdot g(n)$$\partial\cdot f*g(n)+f*\partial\cdot g(n)$. $\partial \ast (f+g)=\partial \ast f+\partial \ast g$$\partial*(f+g)=\partial*f+\partial*g$ follows from distributive law directly. $◻$$\square$

I will not repeat the differential ring properties again for $(\mathfrak{A},\partial )$$(\mathfrak{A},\partial)$. See my blog DR (1) .

Let us consider some interesting things. As we know, the kernel of derivative form a ring.

What is the kernel of $v_p?$$v_p?$ What is the solution of the ODE $v_{p}f=0?$$v_{p}f=0?$

We know that the solution is nontrivial, since $v_p$$v_{p}$ is a zero divisor in $\mathfrak{A}.$$\mathfrak{A}.$ $v_p(n)=0⟺n\notin p{\mathbb{N}}^{+}.$$v_p(n)=0\iff n\notin p\mathbb N^+.$

Hence the solution of $v_{p}f=0$$v_pf=0$ is $\mathrm{Ker}(v_p)=\{f\in \mathfrak{A}|\mathrm{\forall }x\in p{\mathbb{N}}^{+},f(x)=0\}$$\mathrm{Ker}(v_p)=\{f\in\mathfrak{A}|\forall x\in p\mathbb N^+,f(x)=0\}$.

Some special arithmetic function

As we can see, $f\ast 1=\sum _{d|n}f(d)$$f*1=\sum_{d|n} f(d)$ appear at lots of place. If I know $f\ast 1$$f*1$, how could I know $f?$$f?$

Well, we need the inverse of $1$$1$, i.e. The mobius function $\begin{array}{c}\mu =\{\begin{array}{l}\mu (1)=1\\ \mu (n)=(-1{)}^r,n=p_1...p_r\\ \mu (n)=0,\text{if }n\text{ is not square free}.\end{array}\end{array}$$\mu=\begin{cases}\mu(1)=1\\\mu(n)=(-1)^r,n=p_1...p_r\\\mu(n)=0,\text{if } n \text{ is not square free}.\end{cases}$

We need to prove that $\mu \ast 1=\epsilon$$\mu*1=\varepsilon$.

Proof. Obviously $(\mu \cdot 1)(1)=\epsilon (1)$$(\mu\cdot 1)(1)=\varepsilon(1)$. Let $n=p_1^{e_1}...p_s^{e_s}$$n=p_1^{e_1}...p_s^{e_s}$

$\begin{array}{c}(\mu \ast 1)(n)=\sum _{d|n}\mu (d)=\mu (1)+\mu (p_i)+\sum _{i,j}\mu (p_i{p}_j)+\sum _{i,j,k}\mu (p_i{p}_j{p}_k)+...+\mu (p_1...p_s)=\sum _{r=0}^s(-1{)}^r(\genfrac{}{}{0ex}{}{s}{r})=(1-1{)}^s=0◻\end{array}$$(\mu*1)(n)=\sum_{d|n}\mu(d)=\mu(1)+\mu(p_i)+\sum_{i,j}\mu(p_ip_j)+\sum_{i,j,k}\mu(p_i p_jp_k)+...+\mu(p_1...p_s)=\sum_{r=0}^s(-1)^r\binom{s}{r}=(1-1)^s=0\quad\square\\$

Corollary. Mobius inversion. Let $\begin{array}{c}g=f\ast 1,f=g\ast \mu \end{array}$$g=f*1,f=g*\mu\\$.

Definition. Euler function $\phi (n)=|(\mathbb{Z}/n\mathbb{Z}{)}^{\ast }|$$\varphi(n)=|(\mathbb Z/n\mathbb Z)^*|$. ($\phi (1)=1$$\varphi(1)=1$)

It is not hard to see that $\phi (p^e)=p^e-p^{e-1}.$$\varphi(p^e)=p^e-p^{e-1}.$ Since in $(\mathbb{Z}/p^e\mathbb{Z}{)}^{\ast }=\mathbb{Z}/p^e\mathbb{Z}-\{p,2p,3p,...,p^{e-1}p\}$$(\mathbb Z/p^e\mathbb Z)^*=\mathbb Z/p^e\mathbb Z- \{p,2p,3p,...,p^{e-1}p\}$.

Proposition. If $gcd(m,n)=1$$\gcd(m,n)=1$, then $\phi (mn)=\phi (m)\phi (n).$$\varphi(mn)=\varphi(m)\varphi(n).$

It follows from Chinese Remainder Theorem directly. According to CRT, $\mathbb{Z}/mn\mathbb{Z}\cong \mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}.$$\mathbb Z/mn\mathbb Z\cong\mathbb Z/m\mathbb Z\times\mathbb Z/ n\mathbb Z.$

Hence $(\mathbb{Z}/mn\mathbb{Z}{)}^{\ast }\cong (\mathbb{Z}/m\mathbb{Z}{)}^{\ast }\times (\mathbb{Z}/n\mathbb{Z}{)}^{\ast }$$(\mathbb Z/mn\mathbb Z)^*\cong(\mathbb Z/m\mathbb Z)^*\times(\mathbb Z/n\mathbb Z)^*$. $|(\mathbb{Z}/mn\mathbb{Z}{)}^{\ast }|=|(\mathbb{Z}/m\mathbb{Z}{)}^{\ast }\times (\mathbb{Z}/n\mathbb{Z}{)}^{\ast }|=|(\mathbb{Z}/m\mathbb{Z}{)}^{\ast }|\times |(\mathbb{Z}/n\mathbb{Z}{)}^{\ast }|$$|(\mathbb Z/mn\mathbb Z)^*|=|(\mathbb Z/m\mathbb Z)^*\times(\mathbb Z/n\mathbb Z)^*|=|(\mathbb Z/m\mathbb Z)^*|\times|(\mathbb Z/n\mathbb Z)^*|$ $◻$$\square$

Proposition. $\phi \ast 1={\mathrm{id}}_{{\mathbb{N}}^{+}}$$\varphi*1=\mathrm{id}_{\mathbb N^{+}}$. i.e. $\begin{array}{c}\sum _{d|n}\phi (d)=n\end{array}$$\sum_{d|n}\varphi(d)=n\\$

Proof.

$\phi \ast 1=\sum _{d|n}\phi (d)$$\varphi*1=\sum_{d|n}\varphi(d)$. For each $d|n$$d|n$, $(a,n)=d⟺(a/d,n/d)=1$$(a,n)=d\iff(a/d,n/d)=1$.

Let $A_d:=\{0\le a\le n|gcd(a,n)=d\}$$A_d:=\{0\le a\le n|\gcd(a,n)=d\}$, then $|A_d|=|\{0\le a_1\le n/d,(a_1,n/d)=1\}|=\phi (n/d)$$|A_d|=|\{0\le a_1\le n/d, (a_1,n/d)=1\}|=\varphi(n/d)$.

Each $A_d$$A_d$ is fiber of $gcd(-,n)\equiv f:\mathbb{Z}/m\mathbb{Z}\to n\downarrow$$\gcd(-,n)\equiv f:\mathbb Z/m\mathbb Z\to n\downarrow$. i.e. $A_d=f^{-1}(d)$$A_d=f^{-1}(d)$. Here $n\downarrow$$n\downarrow$ is the set of divisor of $n$$n$.

Hence $A_d$$A_d$ form a partition of $\mathbb{Z}/m\mathbb{Z}$$\mathbb Z/m\mathbb Z$.

$$\begin{array}{}\text{(6)}& \sum _{d|n}|A_d|=m=\sum _{d|n}\phi (n/d)=\sum _{d|n}\phi (d)=\phi \ast 1(n)={\mathrm{id}}_{{\mathbb{N}}^{+}}(n)◻\end{array}$$

Corollary. $\phi =\mu \ast {\mathrm{id}}_{\mathbb{N}}$$\varphi=\mu*\mathrm{id_{\mathbb N}}$.

i.e. $\begin{array}{c}\phi (n)=\sum _{d_1{d}_2=n}\mu (d_1)d_2=n-\sum _i\frac{n}{p_i}+\sum _{i,j}\frac{n}{p_1{p}_2}+...=n(1-\frac{1}{p_1})...(1-\frac{1}{p_s})\end{array}$$\varphi(n)=\sum_{d_1d_2=n}\mu(d_1)d_2=n-\sum_{i} \frac{n}{p_i}+\sum_{i,j}\frac{n}{p_1p_2}+...=n\left(1-\frac{1}{p_1}\right)...\left(1-\frac{1}{p_s}\right)\\$.

Futher Properties

Definition multiplicative function and completely multiplicative function

Let $f\ne 0$$f\ne 0$.

If $gcd(m,n)=1⟹f(mn)=f(m)f(n)$$\gcd(m,n)=1\implies f(mn)=f(m)f(n)$, then $f$$f$ is multiplicative function.

If $\mathrm{\forall }m,n\in {\mathbb{N}}^{+},f(mn)=f(m)f(n)$$\forall m,n\in\mathbb N^+,f(mn)=f(m)f(n)$, then $f$$f$ is completely multiplicative function.

Example. $1$$1$.

Proposition. $f$$f$ is multiplicative function $⟹$$\implies$ $f(1)=1$$f(1)=1$.

Proof. $f(n\cdot 1)=f(n)\cdot f(1)◻$$f(n\cdot 1)=f(n)\cdot f(1)\quad\square$

Proposition. The set of multiplicative function/completely multiplicative function is closed under convolution.

Proof.

$$\begin{array}{}\text{(7)}& f\ast g(m)\cdot f\ast g(n)=\sum _{d_1|m}f(d_1)g(m/d_1)\cdot \sum _{d_2|n}f(d_2)g(n/d_2)=\sum _{d_1|m,d_2|n}f(d_1{d}_2)g(mn/d_1{d}_2)=f\ast g(mn)◻\end{array}$$

Proposition $f(1)\ne 0⟺f$$f(1)\ne 0\iff f$ is invertible, and the inverse is unique.

If $f$$f$ is invertible, $f\ast g(1)=\epsilon (1)=f(1)g(1)=1$$f*g(1)=\varepsilon(1)=f(1)g(1)=1$

If $f(1)\ne 0,f\ast g(n)=\sum _{d_1{d}_2=n}f(d_1)g(d_2)=0,f(1)g(n)=-\sum _{1<d_1,d_2<n,d_1{d}_2=n}f(d_1)g(d_2)$$f(1)\ne 0,f*g(n)=\sum_{d_1d_2=n} f(d_1)g(d_2)=0,f(1)g(n)=-\sum_{1<d_1,d_2< n,d_1d_2=n}f(d_1)g(d_2)$

$$\begin{array}{}\text{(8)}& g(n)=\frac{-\sum _{1<d_1,d_2<n,d_1{d}_2=n}f(d_1)g(d_2)}{f(1)}◻\end{array}$$

Corollary. Multiplicative function is invertible.

Proposition. Let $f$$f$ be a multiplicative function, then the inverse of $f$$f$ is multiplicative function as well.

Proof.

Obviously $g(1\cdot 1)=g(1)\cdot g(1)$$g(1\cdot 1)=g(1)\cdot g(1)$.

Let $(a,b)=1$$(a,b)=1$

$$\begin{array}{}\text{(9)}& (f\ast g)(ab)=\sum _{D|ab}f(D)g(ab/D)=\sum _{d|a,\delta |b}f(d\delta )g(ab/d\delta )=\epsilon (ab)\end{array}$$

$$\begin{array}{}\text{(10)}& (f\ast g)(a)\cdot (f\ast g)(b)=\sum _{d|a}f(d)g(a/d)\cdot \sum _{\delta |b}f(\delta )\cdot g(b/\delta )=\sum _{d|a,\delta |b}f(d\delta )g(a/d)g(b/\delta )=\epsilon (ab)\end{array}$$

Define the function $G(ab/d\delta )=g(a/d)g(b/\delta )$$G(ab/d\delta)=g(a/d)g(b/\delta)$. Then $f\ast G=f\ast g$$f*G=f*g$. By the uniqueness of inverse, $G=g$$G=g$.

Hence $g(a/d)g(b/\delta )=g(ab/d\delta )$$g(a/d)g(b/\delta)=g(ab/d\delta)$. Let $d=\delta =1$$d=\delta=1$, $g(a)g(b)=g(ab)◻$$g(a)g(b)=g(ab)\quad\square$

Corollary. $f=g\ast 1$$f=g*1$ is multiplicative function iff $g$$g$ is multiplicative function.

Since $1$$1$ is multiplicative, hence $\mu$$\mu$ is multiplicative as well.

Corollary. The multiplicative functions form a abelian group.

Corollary. $(\mathfrak{A},+,\ast )$$(\mathfrak A,+,*)$ is a local ring. Hence we can view $\mathfrak{A}$$\mathfrak A$ as stalk at the maximal ideal.