莫比乌斯反演练习

问题 1     求对所有的正整数 $n$ ,  $\sum_{d | n}\mu (d)\tau (d)$,其中 $\tau (d)$是因子个数函数.


首先给出一个有关莫比乌斯函数的定理

引理      若 $f$ 是乘性函数并且满足 $f(1) = 1$,则有

$\sum_{d | n}\mu(d) f(d) = \prod_{i = 1}^{k}(1 – f(p_i))$

其中$n$的素因子分解为$n = \prod_{i = 1}^{k}p_i^{a_i}$

引理的证明

考虑函数$h(n) = \mu(n)f(n)$.注意到等式右侧为乘积的形式,因此考虑证明$h(n)$为乘性函数.

事实上,根据乘性函数的定义,对于任意互素的整数$m, n$,我们有

$h(mn) = \mu(mn)f(mn)$

由于莫比乌斯函数$\mu(n)$为乘性函数,因此

$LHS = \mu(m)f(m)\mu(n)f(n)$

所以 $h(n)$ 为乘性函数.其和函数 $\sum_{d|n}h(n)$ 亦为乘性函数.

另一方面,对于整数 $n = p^{k}$ ,其中 $p$ 为素数,我们可以立即得到

$\sum_{d | n}(h(n)) = \mu(1)f(1) + \mu(p)f(p) + … + \mu(p^{k})f(p^{k})\\ = 1 – f(p)$

这是因为对于任意$k >= 2, \mu(p^{k}) = 0$

因此将 $n$ 质因数分解后便可立即得到等式.

 

根据引理,由于$\tau(n)$为乘性函数并且$\tau(1) = 1$

所以

$\prod_{ k = 1}^{m}(1 – \tau(p_{k})) = (-1)^{m}$

其中$n$的素因子分解为$n = \prod_{i = 1}^{m}p_i^{a_i}$


        定义 $n$次本原单位根为:对于复数 $\omega $,若 $\omega ^{n} = 1$ 且 $\omega ^{k} \neq 1,  1 \leqslant  k \leqslant  n – 1$.由于 $e^{2\pi i} = 1$,因此 $ e^{\frac{2\pi j i}{n}}, 1 \leqslant  j \leqslant  n – 1,(j,n) = 1$是本原单位根.

$n$阶分圆多项式为$\Phi _{n}(x) = \prod_{1 \leqslant j \leqslant n ,(j,n) = 1}(x – e^{j\frac{2\pi i}{n}})$.

我们有

$x^{n} – 1 = \prod_{d|n}\Phi_{d}(x)$

这是因为

$x^{n} – 1 = \prod_{1 \leqslant j \leqslant n}(x – e^{\frac{2\pi j i}{n}})\\ = \prod_{d | n}\prod_{1 \leqslant j \leqslant n,(j,n) = d}(x – e^{\frac{2\pi j i}{n}}) \\= \prod_{d|n}\prod_{1 \leqslant j \leqslant n,(\frac{j}{d},\frac{n}{d}) = 1}(x – e^{\frac{2\pi j i}{n}})\\ = \prod_{d | n}\Phi_{\frac{n}{d}}(x) \\= \prod_{d|n}\Phi_{d}(x)                                 (*)$

根据这个性质,我们还可以得到

$\Phi_{n}(x) = \prod_{d|n}(x^{d} – 1)^{\mu(\frac{n}{d})}$

这是因为

对(*)式两边取自然对数:

$ln(x^{n} – 1) = \sum_{d | n}ln(\Phi_{d}(x))$

由反演公式可得

$ln(\Phi_{d}(x) )= \sum_{d|n}\mu(\frac{n}{d})ln(x^{d} – 1)$

注意枚举因子时$\frac{n}{d}$与$d$的含义是一致的.

(待续)

此条目发表在数学, 数论分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注