# 积性函数

# 定义

  • 若 f(a)f(b)=f(ab)f(a)f(b)=f(ab) 在 gcd⁡(a,b)=1\gcd(a,b)=1 时成立，则称 ff 为积性函数。
  • 若 f(a)f(b)=f(ab)f(a)f(b)=f(ab) 在任何情况下成立，则称 ff 为完全积性函数。

# 常见积性函数[1]{}^{[1]}

  • * ϵ(n)=[n=1]\epsilon(n)=[n=1]
  • * I⁡(n)=1\operatorname{I}(n)=1
  • * id⁡(n)=n\operatorname{id}(n)=n

带 * 的是完全积性函数。

# 狄利克雷卷积

# 定义[1]{}^{[1]}

(f∗g)(n)=∑ab=nf(a)g(b)(f*g)(n)=\sum_{ab=n}f\left(a\right)g(b)

其中 a,b∈N∗a,b\in \mathbb{N^*}。

等价写法：

(f∗g)(n)=∑d∣nf(d)g(nd)(f*g)(n)=\sum_{d|n}f\left(d\right)g\left(\frac{n}{d}\right)

亦可简记为 f∗gf*g。

# 运算定律[2]{}^{[2]}

  • 交换律

显然，简记 f∗g=g∗ff*g=g*f

  • 结合律
(f∗g∗h)(n)=∑ab=n[∑cd=af(c)g(d)]h(b)=∑bcd=nf(c)g(d)h(b)=∑acd=nf(a)g(c)h(d)=∑ab=nf(a)[∑cd=bg(c)h(d)]=[f∗(g∗h)](n) \begin{aligned} (f*g*h)(n)&=\sum_{ab=n}\left[\sum_{cd=a}f\left(c\right)g\left(d\right)\right]h\left(b\right)\\ &=\sum_{bcd=n}f\left(c\right)g\left(d\right)h\left(b\right)\\ &=\sum_{acd=n}f\left(a\right)g\left(c\right)h\left(d\right)\\ &=\sum_{ab=n}f\left(a\right)\left[\sum_{cd=b} g\left(c\right)h\left(d\right)\right]\\ &=[f*(g*h)](n) \end{aligned}

证毕。

简记 f∗g∗h=f∗(g∗h)f*g*h=f*(g*h)。

  • 分配率
[(f+g)∗h](n)=∑ab=n(f+g)(a)h(b)=∑ab=nf(a)h(b)+∑ab=nf(g)h(b)=(f∗h+g∗h)(n) \begin{aligned} [(f+g)*h](n)&=\sum_{ab=n}(f+g)(a)h(b)\\ &=\sum_{ab=n}f(a)h(b)+\sum_{ab=n}f(g)h(b)\\ &=(f*h+g*h)(n) \end{aligned}

证毕。

简记 (f+g)∗h=f∗h+g∗h(f+g)*h=f*h+g*h。由交换律可得 f∗(g+h)=f∗g+f∗hf*(g+h)=f*g+f*h。

# 莫比乌斯函数 (μ\mu)

# 定义[3]{}^{[3]}

μ(n)={1n=1,(−1)k∀a∈N∗,a≠1,∃a2∤n,0Otherwise. \mu(n)= \begin{cases} 1&n=1,\\ (-1)^k&\forall a\in\mathbb{N^*},a\neq 1,\exist a^2\not|n,\\ 0&\mathrm{Otherwise}. \end{cases}

其中 kk 是 nn 的质因数个数。

# 性质

一些常用的性质

  • 积性函数：μ(a)μ(b)=μ(ab)\mu(a)\mu(b)=\mu(ab)，其中 gcd⁡(a,b)=1\gcd(a,b)=1

证明

分情况讨论。

若 a,ba,b 中有一个数是 11，那么该性质显然成立。

若 a,ba,b 有一个数有平方数因子，那么 μ(a)μ(b)=μ(ab)\mu(a)\mu(b)=\mu(ab) 也显然成立。

其他情况，由于条件限定 a,ba,b 互质，那么它们的乘积的质因数个数显然是两数质因数个数之和，即 μ(ab)=(−1)k1+k2=(−1)k1(−1)k2=μ(a)μ(b)\mu(ab)=(-1)^{k_1+k_2}=(-1)^{k_1}(-1)^{k_2}=\mu(a)\mu(b)，其中 k1,k2k_1,k_2 分别是 a,ba,b 的质因数个数。

证毕。

  • [4]μ∗I⁡=ϵ{}^{[4]}\mu*\operatorname{I}=\epsilon

证明

(μ∗I⁡)(n)=∑d∣nμ(d) \begin{aligned} (\mu*\operatorname{I})(n)&=\sum_{d|n}\mu(d) \end{aligned}

当 n=1n=1 时，显然。

当 n>1n>1 时，设 d∣nd|n，mm 是 nn 的质因数个数。

由莫比乌斯函数的定义可得，当 dd 的任意一个质因数指数 >1>1 时，μ(d)=0\mu(d)=0，否则 μ(n)=(−1)k\mu(n)=(-1)^k，其中 kk 是 dd 的质因数个数。

那么对 (μ∗I⁡)(n)(\mu*\operatorname{I})(n) 有 (−1)k(-1)^k 贡献的 dd 有 (mk)\binom{m}{k} 个，即

(μ∗I⁡)(n)=∑k=0m(−1)k(mk) (\mu*\operatorname{I})(n)=\sum_{k=0}^m(-1)^k\binom{m}{k}

应用二项式定理得

(μ∗I⁡)(n)=∑k=0m(−1)k(mk)=(1−1)m=0 \begin{aligned} (\mu*\operatorname{I})(n)&=\sum_{k=0}^m(-1)^k\binom{m}{k}\\ &=(1-1)^m\\ &=0 \end{aligned}

即 (μ∗I⁡)(n)=[n=0]=ϵ(\mu*\operatorname{I})(n)=[n=0]=\epsilon，证毕。

# 莫比乌斯反演

# 定义

F(n)=∑d∣nf(d)⇔f(n)=∑d∣nμ(d)F(nd)F(n)=\sum_{d|n}f(d)\Leftrightarrow f(n)=\sum_{d|n}\mu(d)F\left(\frac{n}{d}\right)

# 证明[1]{}^{[1]}

定义中的内容可以表示为 F=f∗I⁡⇔f=μ∗FF=f*\operatorname{I}\Leftrightarrow f=\mu*F。

又因为

a\begin{aligned}a\end{aligned}

即 F=f∗I⁡⇔f=μ∗FF=f*\operatorname{I}\Leftrightarrow f=\mu*F 成立，莫比乌斯反演得证。

# 应用

先鸽着。

# References

2020 07 16 Thu 08:14:33
2020 10 17 Sat 07:00:25