Dirichlet 卷积

(f∗g)(n)=∑k∣nf(k)g(nk)=∑kℓ=nf(k)g(ℓ).(f \ast g)(n) = \sum_{k\mid n}f(k)g\left(\dfrac{n}{k}\right) = \sum_{k\ell=n}f(k)g(\ell).

常见卷积

单位函数 ε\varepsilon 和莫比乌斯函数 μ\mu

ε(n)=[n=1]\varepsilon(n) = [n=1]

莫比乌斯反演就是用了这个进行变形f=1∗g  ⟺  g=μ∗ff = 1 * g \iff g = \mu * ff∗μ=(1∗g)∗μ=(1∗μ)∗g=ε∗g=gf * \mu = (1 * g) * \mu = (1 * \mu) * g = \varepsilon * g = g

除数个数函数 τ\tau 与常数函数 11

τ=1∗1⟺τ(n)=∑d∣n1\tau = 1 * 1 \quad\Longleftrightarrow\quad \tau(n) = \sum_{d\mid n} 1

τ(n)\tau (n) 表示 nn 的正因子个数。

除数和函数 σ\sigma 与恒等函数 id\mathrm{id}、常数函数 11

σ=id∗1⟺σ(n)=∑d∣nd\sigma = \mathrm{id} * 1 \quad\Longleftrightarrow\quad \sigma(n) = \sum_{d\mid n} d

欧拉函数 φ\varphi 与恒等函数 id\mathrm{id}、莫比乌斯函数 μ\mu

φ=id∗μ⟺φ(n)=∑d∣nd⋅μ ⁣(nd)\varphi = \mathrm{id} * \mu \quad\Longleftrightarrow\quad \varphi(n) = \sum_{d\mid n} d \cdot \mu\!\left(\frac{n}{d}\right)
推导φ∗1=idφ∗1∗μ=id∗μ\varphi * 1 =id\\ \varphi * 1 * \mu =id * \mu\\

左边：

φ∗(1∗μ)=φ∗ε=φ\varphi * (1 * \mu) = \varphi * \varepsilon = \varphi

所以

φ=id∗μ\varphi = \mathrm{id} * \mu

除数和函数 σ\sigma 与莫比乌斯函数 μ\mu

σ∗μ=id\sigma * \mu =\mathrm{id}

可以硬拆证明，也可以那上面的推（需要用到下面的结合律）：

σ=id∗1ε=μ∗1\sigma = \mathrm{id} * 1 \\ \varepsilon = \mu * 1

左右乘起来：

σ∗μ=id∗εσ∗μ=id\sigma*\mu=\mathrm{id}*\varepsilon\\ \sigma * \mu =\mathrm{id}

运算律

交换律：f∗g=g∗ff\ast g=g\ast f。

结合律：(f∗g)∗h=f∗(g∗h)(f\ast g)\ast h=f\ast(g\ast h)。

分配律：(f+g)∗h=f∗h+g∗h(f+g)\ast h = f\ast h + g\ast h。

单位元：f∗ε=ε∗f=ff\ast\varepsilon = \varepsilon \ast f = f，其中 ε(n)=[n=1]\varepsilon(n) = [n=1]。

逆元：当且仅当 f(1)≠0f(1)\neq 0 时，存在 gg 使得 f∗g=εf\ast g=\varepsilon，且 gg 称为 ff 的 Dirichlet 逆元，可以记作 f−1f^{-1}。

∑kℓ=nf(k)g(ℓ)=ε(n)f(1)g(n)+∑kℓ=nk≠1f(k)g(ℓ)=ε(n)g(n)=ε(n)−∑kℓ=n, k≠1f(k)g(ℓ)f(1)\sum_{k\ell = n} f(k) g(\ell) = \varepsilon(n)\\ f(1) g(n) + \sum_{\substack{k\ell = n \\ k \neq 1}} f(k) g(\ell) = \varepsilon(n)\\ g(n) = \frac{\varepsilon(n) - \sum_{k\ell = n,\, k \neq 1} f(k) g(\ell)}{f(1)}

定理

设 f,gf,g 是积性函数，那么，f∗gf\ast g 也是积性函数。而且，逆元 f−1f^{-1} 一定存在，它也是积性函数。

证明

先证明 f∗gf\ast g 也是积性函数。

设 m,nm,n 互质，则：

(f∗g)(mn)=∑d∣mnf(d)g(mn/d)=∑d1∣m∑d2∣nf(d1d2)g(m/d1⋅n/d2).(f*g)(mn)=\sum_{d\mid mn}f(d)g(mn/d)=\sum_{d_1\mid m}\sum_{d_2\mid n}f(d_1d_2)g(m/d_1\cdot n/d_2).

由于 d1,d2d_1,d_2 互质且 m/d1,n/d2m/d_1,n/d_2 互质，利用 f,gf,g 的积性得：

=∑d1∣mf(d1)g(m/d1)∑d2∣nf(d2)g(n/d2)=(f∗g)(m)(f∗g)(n).=\sum_{d_1\mid m}f(d_1)g(m/d_1)\sum_{d_2\mid n}f(d_2)g(n/d_2)=(f*g)(m)(f*g)(n).

关于逆元的我还不会证。

完全积性函数也有更特殊的性质，没看懂。

Dirichlet 生成函数