最近重温潘承洞老先生的《数论基础》(现代数学基础丛书 34),确实是经典中的经典。以现代的眼光看数论函数,使得分析问题更加简洁本质,而这些都要归功于 Dirichlet 积的引入。

常见数论函数

为了更好的介绍 Dirichlet 积,先引入一些记号,数论函数是指定义于全体正整数集上的函数。

  1. $u(n) \equiv 1$

  2. $e(n) = n$

  3. $I(n) = \left\{\begin{array}{ll} 1, & n=1, \\ 0, & n>1. \end{array} \right.$

  4. $n$ 的所有正除数的个数 $d(n)$.

  5. $n$ 的全部素因子的个数(按重数计)$\Omega(n)$

  6. $n$ 的不同素因子的个数 $\omega(n)$

  7. $n$ 的正除数的幂和函数 $\sigma_{\lambda}(n) = \sum_{d|n} d^{\lambda}$

  8. 所有不超过 $n$ 且和 $n$ 互素的正整数的个数 $\psi(n)$

    $\psi(n)$ 称之为 Euler 函数。

  9. Mobius 函数 $\mu(n)$

  10. Mangoldt 函数 $\Lambda(n)$

  11. Liouville 函数 $\lambda(n) = (-1)^{\Omega(n)}$

  12. Euler 函数的推广(自创 dna0.49) $\psi _{\lambda}(n)$

    当 $\lambda = 0$ 时即为 Euler 函数。

  13. $M(n)=\sum_{i=1}^n \mu(i)$,则我们有 $\sum_{i=1} ^n M(\lfloor \frac{n}{i} \rfloor) = 1$

  14. $N(n)=\sum_{i=1}^n \psi(i)$,我们有

上面 $M(n), N(n)$ 的计算公式见下面 广义 Dirichlet 积 以及 这篇博文

用下面的 Dirichlet 积的概念,大家就会对上面常见的数论函数有更深刻的认识。

Dirichlet 积

设$f(n)$,$g(n)$是两个数论函数,则

称为$f(n)$和$g(n)$的 Dirichlet 积,记作$h=f \star g$.

定理 1 Dirichlet 积满足交换律和结合律即

  1. 交换律: $f \star g = g \star f$
  2. 结合律: $(f\star g) \star h = f \star (g \star h)$

定理 2 Dirichlet 积的幺元存在为 $I(n)$

  • 定理 1定理 2 知。数论函数全体关于 Dirichlet 积构成了一个含幺交换半群(Commutative Monoid)
  • 由抽象代数的基本知识知道 Monoid 中的元如果存在逆元必然唯一,证明也是显然的
  • 现在的问题就是这个 Monoid 那些元有逆元( Dirichlet 逆,以下简称逆)。或者说一个数论函数可逆的充要条件是什么。

实际上,我们有如下结论

定理 3 数论函数 $f$ 可逆的充要条件是 $f(1) \neq 0$.此时它的逆元为

证明是显然的,验算即知。

至此从抽象的层次已经对数论函数的 Dirichlet 积有了一个清晰的认识,下面用这套语言考虑我们的常见函数

定理 4 Mobius 函数 $\mu(n)$ 是 $u(n)$ 的逆,即

Proof : $n=1$ 时显然,不妨设 $n = p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s} > 0$ 则由 $\mu(n)$ 的定义

由此可见,原来看上去复杂的不知所以然的 Mobius 函数本质上是恒为 1 的函数的 Dirichlet 逆元。

定义 5 若 $F=f \star u$ 则称 $F$ 是 $f$ 的 Mobius 变换,即

显然此时我们有 $f=F * \mu$, 称 $f$ 是 $F$ 的 Mobius 反变换。
实际上,这就是我们常说的 Mobius 反演公式。

Mobius 变换的例子

  1. $I(n)$ 是 $\mu(n)$ 的 Mobius 变换
  2. $d(n)$ 是 $u(n)$ 的 Mobius 变换
  3. $e(n)$ 是 $\psi(n)$ 的 Mobius 变换
  4. $\log n$ 是 $\Lambda(n)$ 的 Mobius 变换

前两个由定义显然,后面两个证明如下。

因此

另外我们还有一个证明方式

上述两种证明都是两种常用处理数论函数的技术手段。

至于 $\log n$ 是 $\Lambda(n)$ 的 Mobius 变换的证明只需验算即知。

用上面所说的技术,我们来考虑一下推广的 Euler 函数 $\psi _{\lambda}$

可乘函数

寻找不变量一直是数学关心的问题,变化中的不变量,可以大大简化运算,并且反过来刻画了变化。具体说,寻找 Dirichlet 积不变量一方面对于那些不变量,可以简化它们操作,另一方面,由于 Dirichlet 积保持这些性质也就刻画了 Dirichlet 本身。其中这样的一个不变量就是可乘函数。

设 $f(n)$ 是定义在全体自然数上不恒为 0 的数论函数,若它满足条件

则称之为可乘函数。若对任意正整数 $m,n$ 恒有

则称之为完全可乘函数。

可乘函数例子: $\mu(n)$, $d(n)$.
完全可乘函数例子: $n^{\lambda}$, $I(n)$.

显然(完全)可乘函数的的积,倒数(如果有意义的话)都是(完全)可乘函数。

定理 6 可乘函数 $f(n)$ 有如下性质

  1. $f(1)=1$
  2. $f(n)=f(p_1^{a_1}) f(p_2)^{a_2} \cdots f(p_s)^{a_s}, \quad n = p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s}$
  3. $f(n)$ 为完全可乘的充要条件是对任意的 $p$ 和 $k \geq 1$ 恒有
  4. $f((m,n)[m,n])=f(m)f(n)$
  5. $f$的逆元必然存在
  6. $f$的 Mobius 变换也可逆

上述定理的证明是显然的,结论是重要的。

定理七 Dirchlet 积 保持可乘性

  1. 若 $f$ 可乘, $g$ 可乘, 则 $h=f \star g$ 可乘;
  2. 若 $g$ 可乘, $h=f \star g$ 可乘,则 $f$ 可乘.

Proof:

  1. 若 $f$ 可乘, $g$ 可乘, 则对任意满足 $(m,n)=1$ 的正整数 $m,n$,对于 $mn$ 的每一个正因子 $d$ 可以分解为 $d=d_1 d_2$ 的形式, 其中 $(d_1,d_2)=1, d_1|m, d_2|n$
  1. 反证,若 $f$ 不可乘,则可以推出$h$不可乘即可。若 $f$ 不可乘,则必存在 $m,n$,$(m,n)=1$ 但是

若 $mn=1$ , 则 $f(1) \neq f(1) f(1)$ 知 $f(1) \neq 1$. 因此 $h(1)=f(1)g(1)=f(1) \neq 1$ 矛盾于 $h$ 可乘。
我们选取满足上述性质的最小正整数 $mn$,即当 $d_1d_2<mn$ 是恒有

由 $h$ 的定义

证毕。

Dirichlet 积一般不保持完全可乘性。

定理 6定理 7,我们有如下推论: 若 $F$ 是 $f$ 的 Mobius 变换,则

  1. $f$ 可乘 $\Longleftrightarrow$ $F$ 可乘

  2. $f$ 可乘,则

  1. $f$ 可乘,则

上面 1 是定理 7.1 的直接推论,2 可由定理 6.2 的直接推论,3 是 2 的直接推论。由 3 我们可以得到著名的欧拉公式:

完全可乘的逆

由于可乘函数满足 $f(1)=1$ 因此可乘函数的逆相对而言更加简单,并且它的逆也是可乘函数。但是计算逆的过程仍然很复杂,但是完全可乘函数的逆却特别简单。

定理 8 设 $f$ 可乘,则 $f$ 完全可乘的充要条件是

推广的 Mobius 反演公式

设 $g$ 完全可乘, $h= f \star g$ ,则 $f= h \star \mu g$,即

另上式中 $g=u$,上式就变成了 Mobius 反演公式。
由推广的 Mobius 反演公式,我们由

可知

广义 Dirichlet 积

考虑和式

其中 $f(n)$ 是数论函数,$H(x)$ 是 $(0,\infty)$上的函数。
我们记 $G = f o H$。特别的若$H(x)$在所有非整数点取值为$0$,则此时就是通常的 Dirichlet 积。
我们有以下性质:

若 $G = f o H$ 则 $H = f^{-1} o G$。
特别的,若 $G(x) = \sum_{n \leq x} H(\frac{x}{n})$, 则我们有

一个技巧相当强大的公式 $Q(x)=\sum_{n \leq x} |\mu(n)|$,显然表示不超过 $x$ 的无平方因子的正整数个数,则

Proof :显然我们有

另一方面

所以

根据上式

三个优美公式

最后我用三个我很喜欢的公式结束这篇博文。

  1. $\sum_{n \leq x} d(n) = \sum_{n \leq x} \lfloor \frac{x}{n} \rfloor$
  1. $\sum _{n \leq x} \mu(n) \lfloor \frac{x}{n} \rfloor = 1$
  1. $\sum _{n=1} ^{\infty} \frac{\mu(n)}{n^2} = \frac{6}{\pi^2} $

Proof:

其中 $a_n = \sum _{d|n} \mu(d) = I(n)$,又由 $\sum _{n=1} ^{\infty} \frac{1}{n^2} = \frac{\pi^2}{6}$ 结论显然。