Dirichlet 积
最后更新于：2023年2月24日 下午
潘承洞先生的《数论基础》(现代数学基础丛书 34) 以现代数学的眼光看数论函数，使得分析问题更加简洁本质，而这些都要归功于 Dirichlet 积的引入。
常见数论函数
为了更好的介绍 Dirichlet 积，先引入一些记号，数论函数是指定义于全体正整数集上的函数。
\(u(n) \equiv 1\)
\(e(n) = n\)
\(I(n) = \left\{\begin{array}{ll} 1, & n=1, \\ 0, & n>1. \end{array} \right.\)
\(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} \]
\(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} \]
\(n\) 的不同素因子的个数 \(\omega(n)\)
\[ \begin{array}{ll} \omega(1)=0 & \\ \omega(n) = s, & n=p_1^{a_1} \cdots p_s^{a_s} \end{array} \]
\(n\) 的正除数的幂和函数 \(\sigma_{\lambda}(n) = \sum_{d|n} d^{\lambda}\)
所有不超过 \(n\) 且和 \(n\) 互素的正整数的个数 \(\psi(n)\) \[ \psi(n) = \sum_{ \begin{array}{c} 1 \leq d \leq n \\ (d,n)=1 \end{array} } 1 \]
\(\psi(n)\) 称之为 Euler 函数。
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. \]
Mangoldt 函数 \(\Lambda(n)\)
\[ \Lambda(n) = \left\{\begin{array}{ll} \log p, & n= p^k, k \geq 1\\ 0, & else. \end{array} \right. \]
Liouville 函数 \(\lambda(n) = (-1)^{\Omega(n)}\)
Euler 函数的推广(自创) \(\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 积满足交换律和结合律即
- 交换律： \(f \star g = g \star f\)
- 结合律： \((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 变换的例子
- \(I(n)\) 是 \(\mu(n)\) 的 Möbius 变换
- \(d(n)\) 是 \(u(n)\) 的 Möbius 变换
- \(e(n)\) 是 \(\psi(n)\) 的 Möbius 变换
- \(\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)\) 有如下性质
- \(f(1)=1\)
- \(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}\)
- \(f(n)\) 为完全可乘的充要条件是对任意的 \(p\) 和 \(k \geq 1\) 恒有 \[ f(p^k) = f ^k (p) \]
- \(f((m,n)[m,n])=f(m)f(n)\)
- \(f\)的逆元必然存在
- \(f\)的 Möbius 变换也可逆
上述定理的证明是显然的，结论是重要的。
定理七 Dirchlet 积 保持可乘性
- 若 \(f\) 可乘, \(g\) 可乘, 则 \(h=f \star g\) 可乘;
- 若 \(g\) 可乘, \(h=f \star g\) 可乘，则 \(f\) 可乘.
Proof:
若 \(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) \]
反证，若 \(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 变换，则
\(f\) 可乘 \(\Longleftrightarrow\) \(F\) 可乘
\(f\) 可乘，则 \[ F(n) = \sum_{d|n} f(d) = \prod_{p^a || n} (1+ f(p)+\cdots f(p^a)) \]
\(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 级数。
应用
\(d(n)\) 的一个公式
按照公式，我们有 \(d(n) = \sum_{i \mid n} 1\)。其实这个公式可以推广为
\[ d(n_1 \cdots n_m) = \sum_{i_1 \mid n_1} \cdots \sum_{i_m \mid n_m} 1, \; \gcd(i_s,i_t)=1,1 \leq s < t \leq m \] Proof： 数学归纳法证明：\(m=1\) 时结论显然。 设结论对 \(m-1\) 成立。 \[ \begin{aligned} d(n_1 \cdots n_m) &= \sum_{i \mid n_1 \cdots n_m} 1 = \sum_{d \mid n_m} \sum_{i \mid n_1 \cdots n_m , \gcd(i,n_m)=d} 1 \\ &= \sum_{d \mid n_m} \sum_{\frac{i}{d} \mid n_1 \cdots n_{m-1} , \gcd(\frac{i}{d},\frac{n_m}{d})=1} 1 \\ &= \sum_{d \mid n_m} \sum_{i \mid n_1 \cdots n_{m-1} , \gcd(i,d)=1} 1 \end{aligned} \] 由数学归纳法知，原结论成立。
上面公式的一个应用
\[ \sum_{i_1 = 1} ^{n_1} \cdots \sum_{i_m = 1} ^{n_m} d(n_1 \cdots n_m) = \sum_{\gcd(i_s,i_t)=1,1 \leq s < t \leq m } \lfloor \frac{n_1}{i_1} \rfloor \cdots \lfloor \frac{n_m}{i_m} \rfloor \]
一道例题：codeforce 235
求解: \[ \sum_{i=1}^a \sum_{j=1}^b \sum_{k=1}^c d(ijk) \] 如果令 \(f(n) = \sum_{i=1} ^n d(i),g(n)=\sum_{i \mid n} \mu(i) f(\lfloor \frac{c}{i} \rfloor)\) 那么 \[ \sum_{i=1}^a \sum_{j=1}^b \sum_{k=1}^c d(ijk) = \sum_{t} \mu(t) \lfloor \frac{a}{it} \rfloor \lfloor \frac{b}{it} \rfloor g(ijt^2) \]