定义
对于两个数论函数 \(f, g\),存在运算 $* $,满足 \(f * g = h\)。其中 $* $ 读作“卷”。
计算式为:
\[h(x) = \sum _ {k \times \lambda = x} f(k) \times g(\lambda).
\]
一些有意思的性质
然后我们再回头看狄利克雷生成函数,就会发现一些有意思的事。
两个函数的 DGF 的积 等于 两个函数的卷积的 DGF
即:
\[\tilde{F}(x) \times \tilde{G}(x) = \sum _ {i} \sum _ {j} \dfrac{f(i) \times g(j)}{i^x j^x}.
\]
令 \(ij = k\),则有:
\[\tilde{F}(x) \times \tilde{G}(x) = \sum _ {k} \dfrac{1}{k^x} \sum _ {d \mid k} f(d) \times g(\frac{k}{d}).
\]
最右面的和式是求卷积的式子,左面的和式是 DGF 的定义式。所以,两个函数的 DGF 的积 等于 两个函数的卷积的 DGF。
交换律
\[f * g = g * f.
\]
证明:
\[f * g \iff h(x) = \sum _ {d \mid x} f(d) \times g(\frac{x}{d}) = \sum _ {d \mid x} f(\frac{x}{d}) \times g(d) \iff g * f.
\]
结合律
\[(f * g) * h = f * (g * h).
\]
证明:
设 \(s = f * g, t = h * g\),则有:
\[s(x) = \sum _ {d \mid x} f(d) \times g(\dfrac{x}{d}).
\]
\[t(x) = \sum _ {d \mid x} h(d) \times g(\dfrac{x}{d}).
\]
再设 \(u = s * h, v = f * t\),则有:
\[u(y) = \sum _ {x \mid y} s(x) \times h(\dfrac{y}{x}) = \sum _ {x \mid y} \sum _ {d \mid x} f(d) \times g(\dfrac{x}{d}) \times h(\dfrac{y}{x}) = \sum _ {d \mid y} f(d) \times t(\dfrac{y}{d}) = v(y).
\]
即:
\[u(y) = v(y).
\]
所以:
\[s * h = f * t.
\]
即:
\[(f * g) * h = f * (g * h).
\]
分配律
\[(f + g) * h = f * h + g * h.
\]
证明:
由初等函数的性质(详细情况参见高等数学)可得:
\[((f + g) * h)(x) = \sum _ {d \mid x} (f + g)(d) \times h(\dfrac{x}{d}) = \sum _ {d \mid x} (f(d) \times h(\dfrac{x}{d}) + g(d) \times h(\dfrac{x}{d})) = (f * h + g * h)(x).
\]
所以分配律成立。
两个积性函数的卷积也是积性函数
\(\\\)
证明:
设存在两个积性函数 \(f, g, h\),两个正整数 \(x, y\),并且满足 \(h = f * g, x \bot y\)。
\[h(x) = \sum _ {d \mid x} f(d) \times g(\dfrac{x}{d}).
\]
\[h(y) = \sum _ {\delta \mid y} f(\delta) \times g(\dfrac{y}{\delta}).
\]
设 \(d \in S_1, \delta \in S_2\),则一定满足 \(S_1 \cap S_2 = \{1\}\)。所以有:
\[h(x \times y) = \sum _ {\varsigma \mid (x \times y)} f(\varsigma) \times g(\dfrac{x \times y}{\varsigma}). ①
\]
显然一定有 \(\varsigma \in (S_1 \cup S_2)\),因为 \(x \bot y\),所以 \(\varsigma\) 可以取到 \(\forall d \times \forall \delta\)。
显然:
\[h(x) \times h(y) = (\sum _ {d \mid x} f(d) \times g(\dfrac{x}{d}))(\sum _ {\delta \mid y} f(\delta) \times g(\dfrac{y}{\delta})). ②
\]
拆开括号,显然有 ① = ②。
积性函数的逆元也是积性函数
卷积逆元的定义:对于数论函数 \(f, g\),若满足 \(f * g = \varepsilon\),则 \(f, g\) 互为逆元。
神秘嘉宾!!!我也不知道这玩意该怎么证。就用上面的性质感性理解吧。