数论函数的 Dirichlet 积

最近重温潘承洞老先生的《数论基础》(现代数学基础丛书 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)$.

   $$d(n)= \sum_{d|n} 1 = (a_1+1)(a_2+1) \cdots (a_n+1), \; n=p_1^{a_1} \cdots p_s^{a_s}$$

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

   $$\begin{array}{ll} \Omega(1)=0 & \\ \Omega(n) = a_1 + a_2+ \cdots a_n, & n=p_1^{a_1} \cdots p_s^{a_s} \end{array}$$

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

   $$\begin{array}{ll} \omega(1)=0 & \\ \omega(n) = s, & n=p_1^{a_1} \cdots p_s^{a_s} \end{array}$$

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

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

   $$\psi(n) = \sum_{ \begin{array}{c} 1 \leq d \leq n \\ (d,n)=1 \end{array} } 1$$

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

9. Möbius 函数 $\mu(n)$

   $$\mu(n) = \left\{\begin{array}{ll} 1, & n=1, \\ (-1)^s, & n=p_1p_2 \cdots p_s, \; p_1 < p_2< \cdots < p_s. \\ 0, & else. \end{array} \right.$$

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

    $$\Lambda(n) = \left\{\begin{array}{ll} \log p, & n= p^k, k \geq 1\\ 0, & else. \end{array} \right.$$

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

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

    $$\psi _{\lambda} (n) = \sum_{ \begin{array}{c} 1 \leq d \leq n \\ (d,n)=1 \end{array} } d^{\lambda}$$

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

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

Dirichlet 积

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

$$h(n) = \sum_{d|n} f(d)g(\frac{n}{d})$$

称为$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$.此时它的逆元为

$$f^{-1} (1) = \frac{1}{f(1)},\quad f^{-1} (n) = \frac{-1}{f(1)} \sum _{d|n,\, d<n} f(\frac{n}{d})f^{-1}(d),\; n>1$$

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

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

定理 4 Möbius 函数 $\mu(n)$ 是 $u(n)$ 的逆，即

$$\sum_{ d|n } \mu(n) = \left\{ \begin{array}{ll} 1, & n=1, \\ 0, & n>1. \end{array} \right.$$

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

$$\begin{array}{ll} \sum_{ d|n } \mu(n) & = \mu(1) + \mu(p_1) + \mu(p_2) + \cdots +\mu(p_s) + \cdots + \mu(p_1 p_2) + \cdots \\ & \quad + \mu(p_{s-1}p_s) + \cdots \mu(p_1 p_2 \cdots p_s) \\ & = 1 + {s \choose 1} (-1) + {s \choose 2} (-1)^2 + \cdots + {s \choose s} (-1)^s \\ &= (1-1)^s = 0 \end{array}$$

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

定义 5 若 $F=f \star u$ 则称 $F$ 是 $f$ 的 Möbius 变换，即

$$F(n) = \sum_{d|n} f(d)$$

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

$$F(n) = \sum_{d|n} f(d) \Longleftrightarrow f(n) = \sum_{d|n} F(d) \mu(\frac{n}{d})$$

Möbius 变换的例子

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

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

$$n = \sum _{i=1} ^n 1 = \sum _{d|n} \sum_{(n,i) = d} 1 = \sum _{d|n} \sum_{(\frac{n}{d},k)=1} 1 = \sum _{d|n} \psi(\frac{n}{d}) = \sum _{d|n} \psi(d)$$

因此

$$\psi(n) = \sum _{d|n} \mu(d) \frac{n}{d} = n \sum _{d|n} \frac{\mu(d)}{d}$$

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

$$\psi(n) = \sum_{ \begin{array}{c} 1 \leq d \leq n \\ (d,n)=1 \end{array} } 1 ＝ \sum_{1 \leq d \leq n} \sum_{l|(d,n)} \mu(l) = \sum _{l|n} \mu(l) \sum _{1 \leq d \leq n , l|d} 1 = \sum _{l|n} \mu(l) \frac{n}{l}$$

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

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

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

$$\sum _{i=1} ^n i^{\lambda} = \sum _{d|n} \sum_{(n,i) = d} i^{\lambda} = \sum _{d|n} d^{\lambda} \sum_{(\frac{n}{d},k)=1} k^{\lambda} = \sum _{d|n} d^{\lambda} \psi _{\lambda} (\frac{n}{d}) = n^{\lambda} * \psi _{\lambda}$$

可乘函数

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

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

$$f(mn) = f(m) f(n), \quad (m,n)=1$$

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

$$f(mn) = f(m) f(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$ 恒有 $$f(p^k) = f ^k (p)$$
4. $f((m,n)[m,n])=f(m)f(n)$
5. $f$的逆元必然存在
6. $f$的 Möbius 变换也可逆

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

定理七 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$

$$h(mn) = \sum _{d|mn} f(d)g(\frac{mn}{d}) = \sum _{d_1|m} f(d_1)g(\frac{m}{d_1}) \sum _{d_2|n} f(d_2)g(\frac{n}{d_2}) = h(m)h(n)$$

1. 反证，若 $f$ 不可乘，则可以推出$h$不可乘即可。若 $f$ 不可乘,则必存在 $m,n$,$(m,n)=1$ 但是

$$f(mn) \neq f(m)f(n)$$

若 $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$ 是恒有

$$f(d_1d_2) = f(d_1)f(d_2),\quad (d_1,d_2)=1$$

由 $h$ 的定义

$$\begin{array}{cl} h(mn) = \sum_{d \mid mn} f(d) g(\frac{mn}{d}) &= \sum_{d_1 \mid m} f(d_1) g(\frac{m}{d_1}) \sum_{d_2|m} f(d_2)g(\frac{n}{d_2}) - f(m)f(n) + f(mn) \\ &= h(m)h(n) - f(m)f(n) + f(mn) \neq h(m)h(n) \end{array}$$

证毕。

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

由 定理 6 和 定理 7，我们有如下推论: 若 $F$ 是 $f$ 的 Möbius 变换，则

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

2. $f$ 可乘，则

$$F(n) = \sum_{d|n} f(d) = \prod _{p^a || n} (1+ f(p)+\cdots f(p^a))$$

1. $f$ 可乘，则

$$\sum _{d|n} \mu(d) f(d) = \prod _{p | n} (1 - f(p))$$

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

$$\psi(n) = n \sum _{d|n} \frac{\mu(d)}{d} ＝ n \prod _{p|n} (1-\frac{1}{p})$$

完全可乘的逆

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

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

$$f^{-1}(n) = \mu(n)f(n)$$

推广的 Möbius 反演公式

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

$$h(n) = \sum _{d|n} f(d)g(\frac{n}{d}) \quad \Longleftrightarrow \quad f(n) = \sum _{d|n} h(d) \mu(\frac{n}{d})g(\frac{n}{d})$$

另上式中 $g=u$，上式就变成了 Möbius 反演公式。
由推广的 Möbius 反演公式，我们由

$$\sum _{i=1} ^n i^{\lambda} = n^{\lambda} \star \psi _{\lambda}$$

可知

$$\psi_{\lambda}(n) = (\sum _{i=1} ^n i^{\lambda}) \star \mu(n) n^{\lambda}$$

广义 Dirichlet 积

考虑和式

$$G(x) = \sum_{n \leq x} f(n)H(\frac{x}{n})$$

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

$$f \circ (g \circ H) = (f*g) \circ H$$

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

$$H(x) = \sum_{n \leq x} \mu(n) G(\frac{x}{n})$$

几种特殊重要情况：

• 仅在整点上取值，普通 Dirichlet 积
• $H(x) \equiv 1$，$G(x)$ 为前缀和
• $H(x) = \lfloor x \rfloor$ 向下取整，$G(x) = \sum_{n \leq x} f(n) \lfloor \frac{x}{n} \rfloor$

注意到 $\sum_{n \leq x} 1 = \lfloor x \rfloor$，所以 $\lfloor x \rfloor = e \circ 1$ （这给出了恒等于 1 与 向下取整的关系）

从而我们有直接推论

$$\sum_{n \leq x} f(n) \lfloor \frac{x}{n} \rfloor = \sum_{n \leq x} (f \star u)(n)$$

特别地，

• $\sum _{n \leq x} \mu(n) \lfloor \frac{x}{n} \rfloor = 1$
• $\sum_{n \leq x} d(n) = \sum_{n \leq x} \lfloor \frac{x}{n} \rfloor$

更一般地，若 $h = f \star g$，

$$H(x) = \sum_{n \leq x} h(n),\quad F(x) = \sum_{n \leq x} f(n),\quad G(x) = \sum_{n \leq x} g(n)$$

则

$$H(x) = \sum_{n \leq x} f(n) G(\frac{x}{n}) = \sum_{n \leq x} g(n) F(\frac{x}{n})$$

特别地，取 $g = u$，设 $F(x) = \sum_{n \leq x} f(n)$ 则

$$\sum_{n \leq x} F(\frac{x}{n}) = \sum_{n \leq x} (f * u)(n)$$

例如

• 取 $f = \phi$ 为 Euler 函数，$\sum_{n \leq x} sumPhi(\frac{x}{n}) = \frac{n(n + 1)}{2}$
• 取 $f = \mu$ 为 Möbius 函数，$\sum_{i=1} ^n sumMu(\lfloor \frac{n}{i} \rfloor) = 1$

最一般的情况是，对任意 $ab = x$ 成立

$$H(x) = \sum_{n \leq a} f(n) G(\frac{x}{n}) + \sum_{n \leq b} g(n) F(\frac{x}{n}) - F(a)F(b)$$

取 $a = 1$ 或者 $b = 1$ 就是刚刚的式子

这个公式一般是用于做估计的。

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

$$Q(x) = \frac{6}{\pi^2} x + O(\sqrt{x})$$

Proof ：显然我们有

$$\lfloor x \rfloor = \sum_{k \leq \sqrt{x}} Q(\frac{x}{k^2})$$

另一方面

$$Q(x) = \sum_{n \leq \sqrt{x}} Q(\frac{x}{n^2}) \sum_{d \mid n} \mu(d) = \sum_{d \leq \sqrt{x}} \mu(d) \sum_{ k \leq \sqrt{\frac{x}{d^2}} } Q(\frac{x}{d^2k^2})$$

所以

$$\sum_{n \leq x} |\mu(n)| = Q(x) = \sum_{d \leq \sqrt{x}} \mu(d) \lfloor \frac{x}{d^2} \rfloor$$

根据上式

$$Q(x) = x \sum_{d=1}^{\infty} \frac{\mu(d)}{d^2} +O(\sqrt{x}) = \frac{6}{\pi^2} x + O(\sqrt{x})$$

一个优美公式：$\sum _{n=1}^{\infty} \frac{\mu(n)}{n^2} = \frac{6}{\pi^2}$

Proof:

$$\sum _{n=1} ^{\infty} \frac{1}{n^2} \sum_{n=1} ^{\infty} \frac{\mu(n)}{n^2} = \sum_{n=1} ^{\infty} \frac{a_n}{n^2}$$

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

多维广义 Dirichlet 积

为了简洁不妨考虑二维，有两种形式

$$G(x, y) = \sum_{n \leq \min(x, y)} f(n) H(\frac{x}{n}, \frac{y}{n})$$

此形式可以看作向量版的广义 Dirichlet 积。

$$G(x, y) = \sum_{i \leq x} \sum_{j \leq y} f(i) g(j)H(\frac{x}{i}, \frac{y}{j})$$

这个怎么搞呢？

利用图形可说明的一个公式：

$$\sum_{i = 1}^n \sum_{j = 1, gcd(i, j) = 1}^m f \left( \min(\lfloor \frac{n}{i} \rfloor, \lfloor \frac{m}{j} \rfloor) \right) = \sum_{i = 1}^n \sum_{j = 1}^m f(\gcd(i, j)) - f(\gcd(i, j) - 1)$$

一般地怎么弄呢？

设 $F_d(n, m) = \sum_{i = 1}^n \sum_{j = 1, gcd(i, j) = d}^m f \left( \min(\lfloor \frac{n}{i} \rfloor, \lfloor \frac{m}{j} \rfloor) \right)$，则

$$\sum_{d = 1}^{\min(n, m)} F_1(\frac{n}{d}, \frac{m}{d}) = \sum_{d = 1}^{\min(n, m)} F_d(n, m) = \sum_{i = 1}^n \sum_{j = 1}^m f \left( \min(\lfloor \frac{n}{i} \rfloor, \lfloor \frac{m}{j} \rfloor) \right) = G(n, m)$$

$G(n, m)$ 可以用图形，分情况利用 floorSum 计算，但是还是很慢，这是因为 map 二维记忆化搜索不可避免的慢！一定要避免使用。但是无妨，我们可以反演，得到 $F_1(n, m) = \sum_{d = 1}^{\min(n, m)} \mu(d) G(\frac{n}{d}, \frac{m}{d})$，依然还是慢（floorSum 多了一个 log）。

那么最终问题就变成：

$$\sum_{d = 1}^{\min(n, m)} \mu(d) G(\frac{n}{d}, \frac{m}{d}) = \sum_{d = 1}^{\min(n, m)} \mu(d) \sum_{i = 1}^{\frac{n}{d}} \sum_{j = 1}^{\frac{m}{d}} f \left( \min(\lfloor \frac{n}{id} \rfloor, \lfloor \frac{m}{jd} \rfloor) \right) = \sum_{i = 1}^n \sum_{j = 1}^m f(\gcd(i, j)) - f(\gcd(i, j) - 1)$$

Dirichlet 级数

$\mathcal{D}_f(s) = \sum_{n = 1}^{\infty} f(n) n^{-s}$

注意到 $f(n)$ 为恒等时，就是 Riemann-zeta 函数

一些重要的性质：

• $\mathcal{D}_{f \star g} = \mathcal{D}_{f} \mathcal{D}_{g}$
• 若 $f$ 可乘，则 $\mathcal{D}_f(s) = \prod_{p \text{ prime}} \sum_{i = 0}^{\infty} f(p^i) p^{-es}$
• 若 $f$ 完全可乘，则 $\mathcal{D}_f(s) = \prod_{p \text{ prime}} \frac{1}{1 - \frac{f(p)}{p^s}}$

素数定理：$\lim_{x \to \infty} \frac{\pi(x)}{x / \ln x} = 1$ 的证明就用到了 Dirichlet 级数。