Möbius函数的性质$μ∗f=∏_{p∣n}​(1-f(p))$

hbghlyj

引理7.1.2.1
当 $f(n)$ 为积性函数时:$$μ∗f=\prod_{p∣n}​(1-f(p))$$

---

取$n=30$算一下
左边$\verb|Sum[MoebiusMu[d] f[d], {d, Divisors[30]}]|$
$$μ∗f=f(1)-f(2)-f(3)-f(5)+f(6)+f(10)+f(15)-f(30)$$
右边$\verb|Product[1 - f[d], {d, {2, 3, 5}}]|$
$$(1-f(2)) (1-f(3)) (1-f(5))$$
然后就会证明它了:
因为 $f(n)$ 为积性函数
$f(1)=1$
$f(6)=f(2)f(3)$
$f(10)=f(2)f(10)$
$f(15)=f(3)f(5)$
$f(30)=f(2)f(3)f(5)$

对于一般的$n$, 证明:
若$d∣n$是squarefree 则右边出现的$μ(d)$等于右边的$(-1)^{ν(d)}$ 因为$f(d)$是由$ν(d)$个$f(p)$相乘得到的.
若$d∣n$不squarefree 则左边不出现它 (因为$μ(d)=0$), 右边也不出现它, 因为每项中$f(p)$都不能重复.

hbghlyj

brilliant.org/wiki/dirichlet-convolution/
$f,g$ 为数论函数(arithmetic function), 其 Dirichlet 卷积(Dirichlet convolution) $f∗g$, 为如下的数论函数:
\[ (f * g)(n) = \sum_{d | n} f(d) g \left( \frac{n}{d} \right), \]
求和的 $d$ 遍历 $n$ 的因数.

---

数论函数集合在加法和 Dirichlet 卷积运算下形成一个环，积性函数是一个子环。单位元为 Multiplicative identity function, 定义为$$e(n) = \begin{cases} 1 &\text{if } n=1 \\ 0 &\text{if } n > 1 \end{cases}$$

---

常用数论函数的 Dirichlet 卷积
$\mathbf{1}∗\mathbf{1}=d$. 由定义立得.
$I∗\mathbf{1}=σ$. 一般地, $I_k * \mathbf{1} = \sigma_k$.

证明

\begin{aligned}
(I * \mathbf{1})(n) &= \sum_{d | n} I(d) \mathbf{1} \left( \frac{n}{d} \right) \\
&= \sum_{d | n} d \cdot 1 \\
&= \sum_{d | n} d = \sigma(n)
\end{aligned}

$\varphi * \mathbf{1} = I$. 这等价于 $\sum_{d|n} \phi(d) = n$.

证明

将$\frac1n,\frac2n,\cdots,\frac nn$约分, 都变成$\frac ad$的形式, $(a,d)$是互质的, $d|n$, $1\le a\le d$.
反过来, 对于互质的$(a,d)$ 满足 $d|n$, $1\le a\le d$, 那么 $\frac ad$ 可以写成分母为$n$的分数$\dfrac{a\cdot\frac nd}{n}$.

$μ∗\mathbf{1}=e$. 证明见 Möbius Function.

---

数论函数 $f$、$g$ 的 Dirichlet 卷积为 $e$, 即 $f∗g=e$, 则 $g$ 称为 $f$ 的 Dirichlet 逆.
任何数论函数 $f$ 使 $f(1)≠0$ 具有 Dirichlet 逆, 由下面的定理给出:
定理: $f$ 的 Dirichlet 逆 $g$ 为: $g(1)=\frac1{f(1)}$​, 对 $n>1$,
\[g(n) = \frac{-1}{f(1)} \sum_{d|n, d<n} f\left( \frac{n}{d} \right) g(d) ,\]
求和的 $d$ 遍历 $n$ 的真因数.

证明

$n=1$时,\begin{aligned}
e(1) &= (f * g)(1) \\
1 &= \sum_{d|1} f\left( \frac{1}{d} \right) g(d) \\
&= f(1) g(1) \\
g(1) &= \frac{1}{f(1)}.
\end{aligned}第一行来自 $g$ 是 $f$ 的 Dirichlet 逆的定义；第三行是因为 1 只有一个正因数 1。
对于$n>1$,\begin{aligned}
e(n) &= (f * g)(n) \\
0 &= \sum_{d|n} f \left( \frac{n}{d} \right) g(d) \\
&= f(1) g(n) + \sum_{d|n, d<n} f \left( \frac{n}{d} \right) g(d) \\
-f(1) g(n) &= \sum_{d|n, d<n} f \left( \frac{n}{d} \right) g(d) \\
g(n) &= \frac{-1}{f(1)} \sum_{d|n, d<n} f \left( \frac{n}{d} \right) g(d).
\end{aligned}第二行是因为 Dirichlet 卷积是可交换的。第四行将情况 $d=n$ 与求和中的其余情况分开。 最后一行是因为$f(1)≠0$

如上所述，$μ∗\mathbf1=e$，所以 $\mathbf{1}$ 的 Dirichlet 逆是 $μ$。这个事实被称为 Möbius inversion(莫比乌斯反演)；有关其应用的更多信息，请参见莫比乌斯函数。

---

Show that the Dirichlet inverse of $λ$ is $\abs μ$.
$λ$ 与 $|\mu|$ 都是积性函数, 故 $λ∗|μ|$ 是积性函数. $e$ 也是积性函数, 故只需证两个函数在素幂的值相等:
\begin{aligned}
\big(\lambda*|\mu|\big)\big(p^k\big) &= \sum_{d|p^k}\lambda\left(\frac{p^k}{d}\right)\big|\mu(d)\big| \\
&= \lambda\big(p^k\big)+\lambda\big(p^{k-1}\big) \\&= (-1)^k+(-1)^{k-1}\\&=0.
\end{aligned}因 $e(p^k)=0$, 两个积性函数在素幂的值相等, 从而它们相等. $_\square$