定义

狄利克雷卷积 是定义在数论函数间的一种二元运算，可以定义为：

\[(f * g)(n) = \sum\limits_{xy = n} f(x) g(y) \]

\[(f * g)(n) = \sum\limits_{d \mid n} f(d) g(\frac{n}{d}) \]

性质

积性函数

性质 \(1\)

若 \(f, g\) 均为积性函数，则 \(f * g\) 也是积性函数。

显然 \((f * g)(1) = f(1)g(1) = 1\)

设 \(n \perp m\)，则

\[\begin{aligned} (f * g)(n)(f * g)(m) &= \sum\limits_{d1 \mid n} f(d1)g(\frac{n}{d1}) \sum\limits_{d2 \mid m} f(d2)g(\frac{m}{d2}) \\ &= \sum\limits_{d1 \mid n, d2 \mid m} f(d1)g(\frac{n}{d1})f(d2)g(\frac{m}{d2}) \\ &= \sum\limits_{d1 \mid n, d2 \mid m} f(d1d2)g(\frac{nm}{d1d2}) \end{aligned} \]

注意到 \(n \perp m\)，则 \(nm\) 的每个因数都能且仅能被表示为 \(n\) 的某一因数乘以 \(m\) 的某一因数，即上式可表示为

\[(f * g)(n)(f * g)(m) = \sum\limits_{d \mid nm} f(d)g(\frac{nm}{d}) \]

故 \(f * g\) 也是积性函数。

性质 \(2\)

若 \(g, f * g\) 均为积性函数，则 \(f\) 也是积性函数。

反证法。

假设 \(f\) 不是积性函数，则一定存在一组 \(n, m\) 使得 \(f(n)f(m) \neq f(nm)\)。不妨尝试构造出一组使得 \(nm\) 最小的 \(n, m\)

若 \(nm = 1\)，则 \(n = m = 1\)。有 \(f(1)f(1) \neq f(1)\)，知 \(f(1) \neq 1\)。又因为 \(g\) 是积性函数，得 \(g(1) = 1\)。此时 \((f * g)(1) = f(1)g(1) \neq 1\)，矛盾。

若 \(nm > 1\)，由 \(nm\) 最小知 \(\forall \gcd(a, b) = 1, ab < nm\)，有 \(f(a)f(b) = f(ab)\)

\[\begin{aligned} (f * g)(nm) &= \sum\limits_{ab \mid nm} f(ab) g(\frac{nm}{ab}) \\ &= \sum\limits_{a \mid n, b \mid m} f(ab) g(\frac{nm}{ab}) \\ &= \sum\limits_{a \mid n, b \mid m, ab < nm} f(ab) g(\frac{nm}{ab}) + f(nm)g(1) \\ &= \sum\limits_{a \mid n, b \mid m, ab < nm} f(a) g(\frac{n}{a}) f(b) g(\frac{m}{b}) + f(nm)g(1) \\ &= \sum\limits_{a \mid n} f(a) g(\frac{n}{a}) \sum\limits_{b \mid m} f(b) g(\frac{m}{b}) - f(n)f(m) + f(nm)g(1) \\ &= (f * g)(n)(f * g)(m) - f(n)(m) + f(nm)g(1) \end{aligned} \]

因为 \(f(n)f(m) \neq f(nm)\)，所以 \((f * g)(nm) \neq (f * g)(n)(f * g)(m)\)，与 \(f * g\) 是积性函数矛盾。

综上所述，\(f\) 是积性函数。

数论函数间的关系

首先证明：

\[\begin{aligned} (f * \textbf{1})(n) &= \sum\limits_{d \mid n} f(d) \textbf{1}(\frac{n}{d}) \\ &= \sum\limits_{d \mid n} f(d) \end{aligned} \]

幂函数和除数函数

\[\begin{aligned} (\operatorname{Id_k} * \textbf{1})(n) &= \sum\limits_{d \mid n} \operatorname{Id_k}(n) \\ &= \sum\limits_{d \mid n} d^k \\ &= \sigma_k(n) \end{aligned} \]

即 \(\operatorname{Id_k} * \textbf{1} = \sigma_k\)

欧拉函数和恒等函数

显然 \(\sum\limits_{d \mid n} \varphi(d) = n = \operatorname{Id}(n)\)

又有 \(\sum\limits_{d \mid n} \varphi(d) = (\varphi * \textbf{1})\)

所以有结论：\(\varphi * \textbf{1} = \operatorname{Id}\)

莫比乌斯函数和单位函数

令 \(n = \prod\limits_{i = 1}^k p_i^{q_i}\)，其中 \(p_i\) 均为两两不同的质数。

\[\begin{aligned} (\mu * \textbf{1})(n) &= \sum\limits_{d \mid n} \mu(d) \\ &= \sum\limits_{i = 0}^k {k \choose i} (-1)^i \\ &= \sum\limits_{i = 0}^k {k \choose i} 1^{k - i} (-1)^i \\ &= [1 + (-1)]^k \end{aligned} \]

显然

\[[1 + (-1)]^k = \begin{cases} 1 \quad k = 0 \\ 0 \quad k > 0 \end{cases} \]

所以

\[\begin{aligned} (\mu * \textbf{1})(n) &= [1 + (-1)]^k \\ &= [k = 0] \\ &= [n = 1] \\ &= \epsilon(n) \end{aligned} \]

即 \(\mu * \textbf{1} = \epsilon\)

莫比乌斯函数与欧拉函数

由上可知 \(\varphi * \textbf{1} = \operatorname{Id}, \mu * \textbf{1} = \epsilon\)

\[\operatorname{Id} = \varphi * \textbf{1} \\ \operatorname{Id} * \mu = \varphi * (\textbf{1} * \mu) \\ \operatorname{Id} * \mu = \varphi * \epsilon \]

所以 \(\mu * \operatorname{Id} = \varphi\)

常数函数与因数个数函数

\[\begin{aligned} (\textbf{1} * \textbf{1})(n) &= \sum\limits_{d \mid n} \textbf{1}(d) \textbf{1}(\frac{n}{d}) \\ &= \sum\limits_{d \mid n} 1 \\ &= \textbf{d}(n) \end{aligned} \]

即 \((\textbf{1} * \textbf{1})(n) = \textbf{d}(n)\)