📂Number Theory

Arithmetic Functions' Dirichlet Convolution

Definition ¹

For two arithmetic functions $f$, $g$, the arithmetic function $h$ satisfying the following is called the Dirichlet product of $f$ and $g$. $$ h(n) = \sum_{d \mid n} f(d) g \left( {{ n } \over { d }} \right) $$ The Dirichlet product can be represented as either $h (n) = \left( f \ast g \right) (n) $ or $h = f \ast g$.

Explanation

The Dirichlet product, as can be inferred from its form, is also called a convolution. It can be guessed that merely denoting an arithmetic function as $a_{d}$, $b_{n/d}$ in this definition would be quite inconvenient.

For convolution $\ast$, the set of arithmetic functions has the following basic algebraic properties. If one is interested in analytic number theory, it is natural to think of the Abelian group $(A,*)$ obtained by applying binary operation $\ast$ to the set of arithmetic functions $A$. Unfortunately, the accurate answer is ’no’, but by providing more appropriate conditions, it can form an Abelian group.

Moreover, the convolution can be generalized such that one of the two functions being multiplied does not have to be an arithmetic function.

Basic Properties

• [1] Associative law: $$ \left( f \ast g \right) \ast k = f \ast (g \ast k) $$
• [2] Commutative law: $$ f \ast g = g \ast f $$

Proof

[1]

Let’s say $A = f \ast g$, $B := (g \ast k)$, then $$ \begin{align*} \left( f \ast g \right) \ast k =& A \ast k \\ =& \sum_{cm = n} A(m) k(c) \\ =& \sum_{cm=n} \left[ \sum_{ab=m} f(a) g(b) \right] k(c) \\ =& \sum_{abc=n} f(a) g(b) k(c) \\ =& \sum_{am=n} f(a) \left[ \sum_{bc=m} g(b) k(c) \right] \\ =& \sum_{am=n} f(a) B(m) \\ =& f \ast B \\ =& f \ast (g \ast k) \end{align*} $$

■

[2]

$$ \begin{align*} \left( f \ast g \right)(n) =& \sum_{d \mid n} f(d) g \left( {{ n } \over { d }} \right) \\ =& \sum_{ab=n} f(a) g(b) \\ =& \sum_{ab=n} g(b) f(a) \\ =& \sum_{d \mid n} g(d) f\left( {{ n } \over { d }} \right) \\ =& (g \ast f)(n) \end{align*} $$

■

Generalization

• Generalized Dirichlet product