莫比乌斯反演入门：积性函数、Dirichlet 卷积、反演和一道例题。
积性函数和完全积性函数
定义
$f(n)$是积性函数的定义是： $$ \forall x, y \in \mathbb{N}_ +\;\gcd(x,y)=1 \implies f(xy)=f(x)f(y) $$ $f(n)$是完全积性函数的定义是： $$ \forall x, y \in \mathbb{N}_ + \; f(xy)=f(x)f(y) $$
性质
将$n$质因数分解， $$ n = \prod_i p_i^{e_i} $$ 则对于积性函数$f(n)$， $$ f(n) = \prod_i f(p_i^{e_i}) $$ 对于完全积性函数$f(n)$， $$ f(n) = \prod_i f(p_i)^{e_i} $$
常用积性函数
单位函数
$$ \varepsilon(n) = e(n) = [n=1]=\begin{cases} 1 & n=1, \\ 0 & n \ge 2.\end{cases} $$ 单位函数满足完全积性。注意到
- 当且仅当$x=y=1$，$f(xy)=f(x)f(y)=1$；
- 在其他情况下$f(xy)=f(x)f(y)=0$。
恒等函数
$$ \text{id}_k(n) = \theta_k(n) = n^k $$ 其中 $$ \text{id}_1(n) = \theta_1(n) = \text{id}(n) = n $$ 恒等函数显然是完全积性的。
常数函数
$$ 1(n) = 1 $$ 常数函数显然是完全积性的。
除数函数
$$ \sigma_k(n) = \sum_{d n} d^k $$ 其中 $$ \sigma_0(n) = d(n) = \tau(n) = \sum_{dn} 1 = \sum_{i=1}^n [in] $$ 是$n$的因数个数。 以及 $$ \sigma_1(n) = \sigma(n) = \sum_{dn} d $$ 是$n$的因数之和。 除数函数的积性证明。假如$\gcd(m,n)=1$，设$dmn$，则存在唯一数对$(d_m, d_n)$，使得$d_m d$, $d_nd$, 并且 $d_m d_n = d$。从而 $$ \sigma(mn)=\sum_{dmn}d=\sum_{d_mm,d_nn}d_m d_n = \sum_{d_mm}d_m \sum_{d_nn}d_n= \sigma(m) \sigma(n) $$ 根据除数函数的积性，可以得到其通式。设$p$是质数，则 $$ \sigma(p^e) = 1+p+p^2+\dots+p^e = \frac{p^{e+1}-1}{p-1} $$ 因此对于正整数$n = \prod_i p_i^{e_i}$， $$ \sigma(n) = \prod_i \left( \frac{p_i^{e_i+1}-1}{p_i-1} \right) $$ 另当$k=0$时，有 $$ d(p^e) = e + 1 $$ 因此 $$ d(n) = \prod_i(e^i+1) $$
欧拉函数
$$ \phi(n) = \sum_{i=1}^n [\gcd(i, n) = 1] $$ 是不超过$n$的正整数中与$n$互质的数的个数。 欧拉函数的积性证明此处略去。 注意到当$e \ge 1$, $$ \phi(p^e) = p^e - p^{e-1} = p^e(1-\frac 1 p) $$ 从而 $$ \phi(n) = \prod_i p_i^{e_i}(1-\frac 1 {p_i}) = n\prod_i(1-\frac {1}{p_i}) $$
莫比乌斯函数
$$ \mu(n) = \begin{cases} 1 & n=1,\\ (-1)^{k} & n \text{ is a product of } k \text{ distinct primes}, \\ 0 & \text{otherwise}.\end{cases} $$ 其积性容易被验证。 如此定义莫比乌斯函数的原因将在下面解释。
Dirichlet 卷积
定义两个数论函数的卷积是： $$ (f*g)(n) = \sum_{dn}f(d)g(\frac nd ) $$
性质
$$ \begin{align} f* g&=g* f \\ (f* g)* h &= f* (g* h) \\ f* (g+h) &= f* g + f* h \\ f* e &= f \\ f* f^{-1} &= e \\ \end{align} $$ 两个积性函数的卷积还是积性函数。
涉及除数函数的卷积
$$ d = 1* 1 \\ \sigma = \text{id} * 1 $$ 上面二式由定义易得。
涉及欧拉函数的卷积
$$ \phi * 1 = \text{id} $$ 略证：由积性函数的性质，等式左侧是积性函数，故只用考虑 $$ (\phi * 1)(p^e) = \sum_{dp^e} \phi(d) = 1 + (1-\frac 1 p) \sum_{i=1}^e p^i = p^e $$ 从而 $$ (\phi*1)(n) = \text{id}(n) $$
涉及莫比乌斯函数的卷积
$$ \mu * 1 = e $$ 可以从两方面理解这个式子。一方面，从$\mu$的构造出发证明它： 当$n=1$， $$ (\mu*1)(1) = 1 = e(1) $$ 当$n=p$， $$ (\mu * 1)(p) = \sum_{dp} \mu(d) = 1 + (-1) = 0 = e(p) $$ 当$n=p^k,k \ge 2$， $$ (\mu * 1)(p^k) = \sum_{dp} \mu(d) = 1 + (-1) + 0 + \dots + 0 = 0 = e(p^k) $$ 再由$(\mu * 1)$的积性即证毕。 另一方面，可以认为$\mu$的定义是$\mu * 1 = e$，即莫比乌斯函数$\mu$是常数函数$1$的在卷积意义下的逆，再由这个定义出发证明$\mu$的构造。这个思路更容易明白莫比乌斯函数的构造的原因。证明细节略。
上述卷积的推论
$$ \mu * \text{id} = \phi $$ 结合后两个卷积以及卷积的性质可得。 $$ [\gcd(m,n)=1] = \sum_{d\gcd(m,n)} \mu (d) $$ $\mu * 1 = e$两边代入$\gcd(m, n)$即得。
莫比乌斯反演
$$ f = g * 1 \implies g = f* \mu $$ 即 $$ f(n) = \sum_{dn}g(d) \implies g(n) = \sum_{dn} \mu(d) f(\frac n d) $$ 另一种形式： $$ f(n) = \sum_{nm}g(m) \implies g(n) = \sum_{mn} \mu(\frac m n) f(m) $$
例题
例1
给定$a,b,k$，求 $$ S=\sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k]. $$ 首先，$\gcd(i,j)=k$等价于$\gcd(i/k, j/k)=1$，从而对$i,j$换元，变换求和指标得 $$ S = \sum_{i=1}^{\lfloor \frac ak \rfloor} \sum_{j=1}^{\lfloor \frac bk \rfloor} [\gcd(i,j)=1] = \sum_{i=1}^{\lfloor \frac ak \rfloor} \sum_{j=1}^{\lfloor \frac bk \rfloor} e(\gcd(i,j)) $$ 使用$e=\mu * 1$代换得 $$ S = \sum_{i=1}^{\lfloor \frac ak \rfloor} \sum_{j=1}^{\lfloor \frac bk \rfloor} \sum_{d\gcd(i,j)}\mu(d) $$ 改为枚举$d$的形式： $$ S = \sum_{i=1}^{\lfloor \frac ak \rfloor} \sum_{j=1}^{\lfloor \frac bk \rfloor} \sum_{d=1}^{\min( \lfloor \frac ak \rfloor, \lfloor \frac bk \rfloor)}\mu(d)[d\gcd(i,j)] $$ 这里$d$范围的原因是 $$ d \gcd(i,j) \implies d i \implies d \le i \le \lfloor\frac ak \rfloor $$ 同理$d \le \lfloor \frac bk \rfloor$。 这样，由于$d$的范围不再受$i$和$j$的直接约束，就可以把对$d$的求和放在最外层： $$ S = \sum_{d=1}^{\min( \lfloor \frac ak \rfloor, \lfloor \frac bk \rfloor)} \mu(d) \sum_{i=1}^{\lfloor \frac ak \rfloor} \sum_{j=1}^{\lfloor \frac bk \rfloor} [d\gcd(i,j)] $$ 内两层求和相当于固定$d$，找符合条件$d\gcd(i,j)$的$i$和$j$。该条件等价于$di$且$dj$，则 $$ S = \sum_{d=1}^{\min( \lfloor \frac ak \rfloor, \lfloor \frac bk \rfloor)} \mu(d) \sum_{i=1}^{\lfloor \frac ak \rfloor} [di]\sum_{j=1}^{\lfloor \frac bk \rfloor} [dj] $$ 在$1$到$\lfloor \frac ak \rfloor$之间的$d$的倍数有 $$ \left\lfloor \frac{a}{kd} \right\rfloor $$ 个，从而答案是 $$ S = \sum_{d=1}^{\min( \lfloor \frac ak \rfloor, \lfloor \frac bk \rfloor)} \mu(d) \left\lfloor \frac{a}{kd} \right\rfloor \left\lfloor \frac{b}{kd} \right\rfloor $$ 由数论分块可解。