Dirichlet Convolution

Definition

$$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{xy=n}f(x)g(y)$$

Example

  • $\sigma_0=1*1$
  • $\sigma_1=I*1$
  • $I=\varphi*1$
  • $\epsilon(n)=\mu*1$

Property

  • 交换律:$f*g=g*f$
  • 结合律:$(f*g)h=f(g*h)$
  • 分配律:$f*(g+h)=f*g+f*h$
  • 单位元:$f*\epsilon=\epsilon * f=1$

Dirichlet Inversion

Proposition

对于任意数论函数,若 $f(1)\neq0$,则一定存在一个数论函数 $f^{-1}$,使得 $f*f^{-1}=\epsilon$,称 $f^{-1}$ 为 $f$ 的狄利克雷卷积的逆。

Proof.

$$f(n)=\begin{cases} \dfrac{1}{g(n)} & n=1\ -\dfrac{\sum_{k|n,k\neq n}f(k)g(\frac{n}{k})}{g(1)} & n\geq 2\end{cases}$$

Dirichlet Generating Function

Definition

定义数论函数 $f$ 的狄利克雷生成函数为

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

Proposition

狄利克雷生成函数的卷积即为狄利克雷卷积。