积性函数
定义
- 若 f(a)f(b)=f(ab) 在 gcd(a,b)=1 时成立,则称 f 为积性函数。
- 若 f(a)f(b)=f(ab) 在任何情况下成立,则称 f 为完全积性函数。
常见积性函数[1]
- * ϵ(n)=[n=1]
- * I(n)=1
- * id(n)=n
带 * 的是完全积性函数。
狄利克雷卷积
定义[1]
(f∗g)(n)=∑ab=nf(a)g(b)其中 a,b∈N∗。
等价写法:
(f∗g)(n)=∑d∣nf(d)g(dn)亦可简记为 f∗g。
运算定律[2]
显然,简记 f∗g=g∗f
(f∗g∗h)(n)=ab=n∑[cd=a∑f(c)g(d)]h(b)=bcd=n∑f(c)g(d)h(b)=acd=n∑f(a)g(c)h(d)=ab=n∑f(a)[cd=b∑g(c)h(d)]=[f∗(g∗h)](n)证毕。
简记 f∗g∗h=f∗(g∗h)。
[(f+g)∗h](n)=ab=n∑(f+g)(a)h(b)=ab=n∑f(a)h(b)+ab=n∑f(g)h(b)=(f∗h+g∗h)(n)证毕。
简记 (f+g)∗h=f∗h+g∗h。由交换律可得 f∗(g+h)=f∗g+f∗h。
莫比乌斯函数 (μ)
定义[3]
μ(n)=⎩⎪⎪⎨⎪⎪⎧1(−1)k0n=1,∀a∈N∗,a=1,∃a2∣n,Otherwise.其中 k 是 n 的质因数个数。
性质
一些常用的性质
- 积性函数:μ(a)μ(b)=μ(ab),其中 gcd(a,b)=1
证明
分情况讨论。
若 a,b 中有一个数是 1,那么该性质显然成立。
若 a,b 有一个数有平方数因子,那么 μ(a)μ(b)=μ(ab) 也显然成立。
其他情况,由于条件限定 a,b 互质,那么它们的乘积的质因数个数显然是两数质因数个数之和,即 μ(ab)=(−1)k1+k2=(−1)k1(−1)k2=μ(a)μ(b),其中 k1,k2 分别是 a,b 的质因数个数。
证毕。
- [4]μ∗I=ϵ
证明
(μ∗I)(n)=d∣n∑μ(d)当 n=1 时,显然。
当 n>1 时,设 d∣n,m 是 n 的质因数个数。
由莫比乌斯函数的定义可得,当 d 的任意一个质因数指数 >1 时,μ(d)=0,否则 μ(n)=(−1)k,其中 k 是 d 的质因数个数。
那么对 (μ∗I)(n) 有 (−1)k 贡献的 d 有 (km) 个,即
(μ∗I)(n)=∑k=0m(−1)k(km)应用二项式定理得
(μ∗I)(n)=k=0∑m(−1)k(km)=(1−1)m=0即 (μ∗I)(n)=[n=0]=ϵ,证毕。
莫比乌斯反演
定义
F(n)=∑d∣nf(d)⇔f(n)=∑d∣nμ(d)F(dn) 证明[1]
定义中的内容可以表示为 F=f∗I⇔f=μ∗F。
又因为
a即 F=f∗I⇔f=μ∗F 成立,莫比乌斯反演得证。
应用
先鸽着。
References