# 积性函数

# 定义

  • 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]}

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

其中 a,bNa,b\in \mathbb{N^*}

等价写法:

(fg)(n)=dnf(d)g(nd)(f*g)(n)=\sum_{d|n}f\left(d\right)g\left(\frac{n}{d}\right)

亦可简记为 fgf*g

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

  • 交换律

显然,简记 fg=gff*g=g*f

  • 结合律
(fgh)(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(gh)](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}

证毕。

简记 fgh=f(gh)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)=(fh+gh)(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=fh+gh(f+g)*h=f*h+g*h。由交换律可得 f(g+h)=fg+fhf*(g+h)=f*g+f*h

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

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

μ(n)={1n=1,(1)kaN,a1,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}

其中 kknn 的质因数个数。

# 性质

一些常用的性质

  • 积性函数:μ(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)=dnμ(d) \begin{aligned} (\mu*\operatorname{I})(n)&=\sum_{d|n}\mu(d) \end{aligned}

n=1n=1 时,显然。

n>1n>1 时,设 dnd|nmmnn 的质因数个数。

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

那么对 (μ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)=(11)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)=dnf(d)f(n)=dnμ(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=fIf=μFF=f*\operatorname{I}\Leftrightarrow f=\mu*F

又因为

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

F=fIf=μFF=f*\operatorname{I}\Leftrightarrow f=\mu*F 成立,莫比乌斯反演得证。

# 应用

先鸽着。


# References

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