狄利克雷生成函数学习笔记

对于一些奇怪的数论问题有奇效。也是对数论函数的另一种视角。

基础形式

$f$ 的狄利克雷生成函数是

F(z)=\sum_{n=1}^{\infty}\dfrac{f(n)}{n^z}

容易验证它的乘积就是狄利克雷卷积

(F*G)(z)=\sum_{n=1}\dfrac{\sum_{d|n}f(d)g(\frac{n}{d})}{n^z}

狄利克雷函数初看非常的诡异，它和普通型与指数型不同，并不是一个形式幂级数。我们介绍一些典型的狄利克雷生成函数来了解它的性质。

$\left<1,0,0,...\right>$ $\varepsilon$ 函数，的狄利克雷生成函数是 1。

$\left<1,1,...\right>$ $\mathbf{1}$ 函数，它的狄利克雷生成函数是

\sum_{n=1}^{\infty}\dfrac{1}{n^z}

$\zeta$ 函数。

$\dfrac{1}{1-x}$ $e^x$ 不同，它的性质比较复杂，我们甚至不完全了解它的零点……不过这和接下来的介绍关系不大。

$\mathbf{1}$ $n$ $p^k$ $f$ 的狄利克雷生成函数有下面的形式

\prod_{p\text{ is a prime}}\sum_{k=0}^{\infty}\dfrac{f(p^k)}{p^{kz}}

$\zeta(z)=$

\prod_{p\text{ is a prime}}\sum_{k=0}^{\infty}\dfrac{1}{p^{kz}}

\prod_{p\text{ is a prime}}\dfrac{1}{1-p^{-z}}

那么它的逆就是

\prod_{p\text{ is a prime}}(1-p^{-z})

$k=0$ $1$ $k=1$ $-1$ $0$ $\mu$ 。也就是说

\mu(z)=\zeta^{-1}(z)

\sum_{n=1}^{\infty}\dfrac{n}{n^z}

显然就是

\zeta(z-1)

同理，

\mathbf{Id}_k(z)=\zeta(z-k)

显然有

\sigma_k(z)=\zeta(z)\zeta(z-k)

有

\varphi(z)=\dfrac{\zeta(z-1)}{\zeta(z)}

从中可以立刻看出欧拉函数的筛法：

\prod_{p\text{ is a prime}}\dfrac{1-p^{-z}}{1-p^{1-z}}

\prod_{p\text{ is a prime}}1+\sum_{k=1}^{\infty}\dfrac{(p-1)p^{k-1}}{p^{kz}}

$p^k$ 的贡献是

\begin{cases}1&(k=0)\\(p-1)p^{k-1}&(k\ge1)\end{cases}

$p$ 的时候按这个柿子更新贡献即可。

$\varphi*\mu$ 。

$\dfrac{\zeta(z-1)}{\zeta^2(z)}$ $p^k$ 的贡献是

\begin{cases}1&(k=0)\\p-2&(k=1)\\(p^2-2p+1)p^{k-2}&(k\ge 2)\end{cases}

显然有答案的生成函数是

\dfrac{\zeta(z-q)}{\zeta(z-p)}

$d^k$ 的贡献是

\begin{cases}1&(k=0)\\(d^q-d^p)d^{(k-1)q}&(k\ge 1)\end{cases}