Arithmetic Functions and Dirichlet Convolution

Because $\mathbb{C}$ is a field by $\mathbb{C}=\mathbb{R}[x]\mathrm{/}(x^2+1)$ is a field, every element is uniquely $a+bi$, and every nonzero element has inverse $(a-bi)\mathrm{/}(a^2+b^2)$, the pointwise formulas for $f+g$, $0$, and $-f$ define arithmetic functions and satisfy the abelian-group laws at each positive integer. The convolution $f\ast g$ is also an arithmetic function by Dirichlet convolution of arithmetic functions.

For convolution commutativity, $(f\ast g)(n)={\sum }_{d\mid n}f(d)g(n\mathrm{/}d)={\sum }_{d\mid n}f(n\mathrm{/}d)g(d)=(g\ast f)(n)$, where the middle equality reindexes the finite divisor sum by the involution $d\mapsto n\mathrm{/}d$ using Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule.

For associativity, expand both sides and rewrite them as the same finite sum over ordered factorizations $abc=n$: $(f\ast (g\ast h))(n)={\sum }_{abc=n}f(a)g(b)h(c)=((f\ast g)\ast h)(n)$. The passage from nested divisor sums to the triple sum uses the finite Fubini and reindexing rules of Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule.

Distributivity follows by expanding a finite divisor sum termwise in $\mathbb{C}$. For the identity, only the divisor $d=n$ contributes in $(f\ast \epsilon )(n)$ and only $d=1$ contributes in $(\epsilon \ast f)(n)$, because The Dirichlet-convolution identity and the constant-one function makes $\epsilon (m)=0$ for $m>1$. Thus $(f\ast \epsilon )(n)=f(n)=(\epsilon \ast f)(n)$.

Steps 1.1, 1.2, 1.3, and 1.4 give all ring axioms, and step 1.2 also shows the multiplication is commutative.

Suppose $g$ satisfies $f\ast g=\epsilon$. Evaluating at $n=1$ gives $f(1)g(1)=\epsilon (1)=1$, so $f(1)\mathrm{\ne }0$ and $g(1)=1\mathrm{/}f(1)$.

Now assume $f(1)\mathrm{\ne }0$. Since $\mathbb{C}$ is a field by $\mathbb{C}=\mathbb{R}[x]\mathrm{/}(x^2+1)$ is a field, every element is uniquely $a+bi$, and every nonzero element has inverse $(a-bi)\mathrm{/}(a^2+b^2)$, set $g(1):=1\mathrm{/}f(1)$. Then $(f\ast g)(1)=f(1)g(1)=1=\epsilon (1)$.

Fix $n>1$ and assume inductively that $g(d)$ has already been defined for every $d<n$ so that $(f\ast g)(m)=\epsilon (m)$ for every $m<n$. Every proper positive divisor $d$ of $n$ satisfies $d<n$ by If $d\mid a$ and $a\mathrm{\ne }0$ then $d\mathrm{\ne }0$ and $\mathrm{\mid }d\mathrm{\mid }\le \mathrm{\mid }a\mathrm{\mid }$; hence the set of divisors of a nonzero integer is bounded above by $\mathrm{\mid }a\mathrm{\mid }$, so in the identity ${\sum }_{d\mid n}f(d)g(n\mathrm{/}d)=\epsilon (n)=0$ the only unknown term is $f(1)g(n)$. Solving for that term and reindexing the proper divisors by $d\leftrightarrow n\mathrm{/}d$ gives the displayed recursion, and with that choice the equality $(f\ast g)(n)=0$ holds.

Apply Strong (complete) induction to the property on natural numbers $r$ that the displayed recursion uniquely defines $g(m)$ and makes $(f\ast g)(m)=\epsilon (m)$ for every $1\le m\le r+1$. Step 1.2 gives the base case $r=0$, and step 1.3 gives the strong induction step. Therefore there is a unique arithmetic function $g$ with $f\ast g=\epsilon$ for every positive integer $n$.

By Arithmetic functions form a commutative ring under pointwise addition and Dirichlet convolution, Dirichlet convolution is commutative, so $g\ast f=f\ast g=\epsilon$. Together with step 1.1, this proves the equivalence, the recursive formula, and uniqueness.

Since $f(1)=g(1)=1$, one has $(f\ast g)(1)=f(1)g(1)=1$. Now let $m,n$ be coprime positive integers. By unique prime factorization from The fundamental theorem of arithmetic: every integer $n\ge 1$ is a product of primes, and the factorisation is unique up to order — if ${\prod }_{i<r}{p}_i={\prod }_{j<s}{q}_j$ with every $p_i$ and $q_j$ prime, then $r=s$ and $q_i=p_{\pi (i)}$ for some $\pi \in \mathrm{Sym}(r)$, every positive divisor of $mn$ is uniquely of the form $ab$ with $a\mid m$ and $b\mid n$. In particular, every such pair $a,b$ is coprime.

By An arithmetic function has a Dirichlet inverse exactly when its value at $1$ is nonzero, the inverse $h$ exists because $f(1)=1\mathrm{\ne }0$, and $h(1)=1$.

Using the divisor splitting from step 1.1 and the multiplicativity of $f$ and $g$ on coprime pairs, $(f\ast g)(mn)={\sum }_{a\mid m,b\mid n}f(ab)g(mn\mathrm{/}ab)={\sum }_{a\mid m,b\mid n}f(a)f(b)g(m\mathrm{/}a)g(n\mathrm{/}b)=({\sum }_{a\mid m}f(a)g(m\mathrm{/}a))({\sum }_{b\mid n}f(b)g(n\mathrm{/}b))=(f\ast g)(m)(f\ast g)(n)$. Thus $f\ast g$ is multiplicative.

To prove $h$ is multiplicative, fix coprime positive integers $m,n$ and argue by strong induction on $mn$. If $m=1$ or $n=1$, then step 1.2 gives $h(mn)=h(m)h(n)$ because $h(1)=1$.

Now assume $m,n>1$ and that $h(uv)=h(u)h(v)$ for every coprime pair $u,v$ with $uv<mn$. Since $(f\ast h)(m)=\epsilon (m)=0$ and $(f\ast h)(n)=\epsilon (n)=0$, one has $0=({\sum }_{a\mid m}f(m\mathrm{/}a)h(a))({\sum }_{b\mid n}f(n\mathrm{/}b)h(b))={\sum }_{a\mid m,b\mid n}f(mn\mathrm{/}ab)h(a)h(b)$, where step 1.1 and multiplicativity of $f$ identify $f(m\mathrm{/}a)f(n\mathrm{/}b)$ with $f(mn\mathrm{/}ab)$. For each pair $(a,b)\mathrm{\ne }(m,n)$, step 1.1 gives $\gcd (a,b)=1$ and $ab<mn$, so the induction hypothesis yields $h(a)h(b)=h(ab)$. Reindexing the remaining pairs by $d=ab$ via step 1.1 therefore gives $0=h(m)h(n)+{\sum }_{\begin{array}{c}d\mid mn\\ d<mn\end{array}}f(mn\mathrm{/}d)h(d)$.

The inverse recursion from An arithmetic function has a Dirichlet inverse exactly when its value at $1$ is nonzero at $mn$ gives $0=h(mn)+{\sum }_{\begin{array}{c}d\mid mn\\ d<mn\end{array}}f(mn\mathrm{/}d)h(d)$. Comparing this with step 2.3 shows $h(mn)=h(m)h(n)$. Since the induction was on an arbitrary coprime pair, Strong (complete) induction yields multiplicativity of $h$.

By For $n\ge 1$ and any injective list $p:r\to \mathbb{Z}$ of primes containing every prime divisor of $n$, one has $n={\prod }_{i<r}{p}_i^{v_{p_i}(n)}$; the exponents are determined by $n$, and $v_q(n)=0$ for every prime $q$ outside the list, the prime-power factors $p_i^{e_i}$ are pairwise coprime and their product is $n$. Repeatedly applying multiplicativity gives $f(n)=f({\prod }_{i<r}{p}_i^{e_i})={\prod }_{i<r}f(p_i^{e_i})$. For $n=1$ this is the empty product, so it reads $f(1)=1$.

For the converse, define $F(1):=1$ and, for $n>1$ with canonical factorization $n={\prod }_{i<r}{p}_i^{e_i}$, define $F(n):={\prod }_{i<r}c(p_i^{e_i})$, where $c(p^e)$ is the prescribed prime-power datum. This is well defined because For $n\ge 1$ and any injective list $p:r\to \mathbb{Z}$ of primes containing every prime divisor of $n$, one has $n={\prod }_{i<r}{p}_i^{v_{p_i}(n)}$; the exponents are determined by $n$, and $v_q(n)=0$ for every prime $q$ outside the list uniquely determines the primes and exponents.

If $\gcd (m,n)=1$, then the canonical factorization of $mn$ is exactly the disjoint union of the canonical factorizations of $m$ and $n$, again by For $n\ge 1$ and any injective list $p:r\to \mathbb{Z}$ of primes containing every prime divisor of $n$, one has $n={\prod }_{i<r}{p}_i^{v_{p_i}(n)}$; the exponents are determined by $n$, and $v_q(n)=0$ for every prime $q$ outside the list. Therefore the defining products for $F(mn)$, $F(m)$, and $F(n)$ split as $F(mn)=F(m)F(n)$, so $F$ is multiplicative.

Any multiplicative function with the prescribed prime-power values must satisfy the formula of step 1.1, so it agrees with $F$ on every positive integer. Thus the extension is unique.

By Dirichlet convolution of arithmetic functions, one has $(\mathbf{1}\ast \mathbf{1})(n)={\sum }_{d\mid n}1=\tau (n)$ from The divisor-counting function $\tau$, and also $(\mathbf{1}\ast {\mathrm{id}}_k)(n)={\sum }_{d\mid n}{d}^k={\sigma }_k(n)$ from The power functions ${\mathrm{id}}_k$ and the divisor-power-sum functions ${\sigma }_k$.

The functions $\mathbf{1}$ and ${\mathrm{id}}_k$ are completely multiplicative in the sense of Completely multiplicative arithmetic functions, so Dirichlet convolution preserves multiplicativity, and multiplicative inverses stay multiplicative makes $\tau$ and ${\sigma }_k$ multiplicative.

The positive divisors of $p^a$ are exactly $1,p,\dots ,p^a$. Therefore $\tau (p^a)={\sum }_{j=0}^{a}1=a+1$ and ${\sigma }_k(p^a)={\sum }_{j=0}^a{p}^{jk}=1+p^k+\cdots +p^{ak}$.

Write the canonical prime factorization of $n$ as $n={\prod }_{i<r}{p}_i^{e_i}$ using For $n\ge 1$ and any injective list $p:r\to \mathbb{Z}$ of primes containing every prime divisor of $n$, one has $n={\prod }_{i<r}{p}_i^{v_{p_i}(n)}$; the exponents are determined by $n$, and $v_q(n)=0$ for every prime $q$ outside the list. A positive divisor of $n$ contributes to the sum only when it is a prime power $p_i^j$, because The von Mangoldt function is zero on every other divisor. Thus ${\sum }_{d\mid n}\mathrm{\Lambda }(d)={\sum }_{i<r}{\sum }_{j=1}^{e_i}\log p_i={\sum }_{i<r}{e}_i\log p_i$.

Repeatedly applying the product law from Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm gives $\log n=\log ({\prod }_{i<r}{p}_i^{e_i})={\sum }_{i<r}\log (p_i^{e_i})={\sum }_{i<r}{e}_i\log p_i$. For $n=1$ both sums are empty, so the same formula gives $0=\log 1$.

Comparing the two expressions in steps 1.1 and 2.1 proves the divisor-sum identity, and the convolution form is exactly Dirichlet convolution of arithmetic functions with the constant-one function.

By The divisor sum of von Mangoldt is the arithmetic-function logarithm, the arithmetic function $\mathrm{\Lambda }$ satisfies $\log n={\sum }_{d\mid n}\mathrm{\Lambda }(d)$ for every positive integer $n$.

Apply Classical Möbius inversion over positive divisors to the functions $f=\mathrm{\Lambda }$ and $g=\log$. It gives $\mathrm{\Lambda }(n)={\sum }_{d\mid n}\mu (d)\log (n\mathrm{/}d)$.

The right-hand side is exactly the Dirichlet convolution formula for $\mu \ast \log$, so $\mathrm{\Lambda }=\mu \ast \log$.

By ${\sum }_{d\mid n}d{N}_q(d)=q^n$ for the counts $N_q(d)$ of monic irreducibles of degree $d$ over ${\mathbb{F}}_q$, one has ${\sum }_{d\mid n}d{N}_q(d)=q^n$. Regard $f(d):=d{N}_q(d)$ and $g(n):=q^n$ as arithmetic functions of the degree variable.

Applying Classical Möbius inversion over positive divisors to those functions gives $n{N}_q(n)={\sum }_{d\mid n}\mu (d)q^{n\mathrm{/}d}$.

Since $n\ge 1$, division by $n$ yields the claimed closed formula for $N_q(n)$.

Write $n={\prod }_{i<r}{p}_i^{e_i}$ by For $n\ge 1$ and any injective list $p:r\to \mathbb{Z}$ of primes containing every prime divisor of $n$, one has $n={\prod }_{i<r}{p}_i^{v_{p_i}(n)}$; the exponents are determined by $n$, and $v_q(n)=0$ for every prime $q$ outside the list. Every positive divisor of $n$ has the form ${\prod }_{i<r}{p}_i^{j_i}$ with $0\le j_i\le e_i$, so Dirichlet convolution of arithmetic functions and Liouville's function give $(\mathbf{1}\ast \lambda )(n)={\sum }_{d\mid n}\lambda (d)={\prod }_{i<r}({\sum }_{j=0}^{e_i}(-1{)}^j)$, where the factorization of the finite sum uses Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule.

For each $i$, the alternating sum ${\sum }_{j=0}^{e_i}(-1{)}^j$ equals $1$ when $e_i$ is even and $0$ when $e_i$ is odd. Therefore the product in step 1.1 is $1$ exactly when every exponent $e_i$ is even, and otherwise it is $0$.

By canonical factorization, every exponent $e_i$ is even exactly when $n$ is a perfect square. So step 2.1 is precisely the claimed square-indicator formula.