Convolution

我們可以利用 convolution 定義出新的 multiplicative arithmetic function, 另外 convolution 也提供了一個較簡明的方法來證明下一節要探討的 Möbius inversion formula. 雖然本節及下一節的內容在本講義中以後不會用到, 但希望利用此介紹讓大家知道有時適當定義一些運算對解決問題有很大的幫助.

Definition 2.4.1   給定兩 arithmetic functions f, g 我們記其 convolution 為 f*g, 其定義為對任意 n $\in$ $\mathbb {N}$,

f*g(n) = $$\sum_{d\vert n,d>0}^{}$$f (d )g(n/d ).

依照 convolution 的定義, 要求 f*g(n) 之值, 首先找出 n 的所有正因數, 然後對於每一個 n 的正因數 d, 我們求 f (d )g(n/d ) 之值, 再將這些值加起來. 若 d 是 n 的正因數, 令 e = n/d, 我們自然有 de = n. 反之, 若 d, e 是正整數滿足 de = n, 則我們自然有 d| n. 因此我們也可以用如下的表示法表示 f*g. 即,

f*g(n) = $$\sum_{{\begin{smallmatrix}{de=n}\\ {d,e\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d )g(e).

這樣的表示法雖然看來像兩個變數, 但實質上若給定 d, 則 e 自然確定. 我們選用這個表示法是因為底下要推導 convolution 的性質時用這種表法較簡明.

由於 f 和 g 是 arithmetic function, 所以 f*g 在任意正整數皆有取值, 因此 f*g 仍為 arithmetic function. 換言之 convolution 可以看成是一個 arithmetic function 之間的運算 (你可以將它看成是兩個 arithmetic function 之間的乘法). 接下來我們就是要探討這種運算的基本性質.

Proposition 2.4.2   設 f, g, h 皆為 arithmetic function. 令 $\delta$ : $\mathbb {N}$$\to$$\mathbb {N}$ 定義為

$$\delta$$(n) = $$\left\{\vphantom{ \begin{array}{ll} 1, & \hbox{$n=1;$} \\ 0, & \hbox{$n>1.$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} 1, & \hbox{$n=1;$} \\ 0, & \hbox{$n>1.$} \\ \end{array}$$

關於 convolution 我們有以下之性質.

1. f*$\delta$ = $\delta$*f = f.
2. f*g = g*f.
3. (f*g)*h = f*(g*h).

証 明. (1) 依定義對任意 n $\in$ $\mathbb {N}$, f*$\delta$(n) = $\sum_{d\vert n,d>0}^{}$f (d )$\delta$(n/d ). 由於當 n/d > 1 時 $\delta$(n/d )= 0. 因此在 $\sum$ 內, 只有 d = n 這一項留下, 故得 f*$\delta$(n) = f (n)$\delta$(1) = f (n). 換言之, f 和 f*$\delta$ 在任意 n $\in$ $\mathbb {N}$ 的取值皆相同. 故從函數的觀點來看, 它們是相同的函數. 同理可證 $\delta$*f = f.

(2) 由於對任意 n $\in$ $\mathbb {N}$,

f*g(n) = $$\sum_{{\begin{smallmatrix}{de=n}\\ {d,e\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d )g(e) = $$\sum_{{\begin{smallmatrix}{de=n}\\ {d,e\in\mathbb{N}}\end{smallmatrix}}}^{}$$g(e)f (d )= $$\sum_{{\begin{smallmatrix}{de=n}\\ {d,e\in\mathbb{N}}\end{smallmatrix}}}^{}$$g(d )f (e) = g*f (n).

我們得證 f*g = g*f.

(3) 依定義, 對任意 n $\in$ $\mathbb {N}$,

$$\sum_{{\begin{smallmatrix}{de=n}\\ {d,e\in\mathbb{N}}\end{smallmatrix}}}^{}$$ (f*g)*h(n) =

$$\sum_{{\begin{smallmatrix}{de=n}\\ {d,e\in\mathbb{N}}\end{smallmatrix}}}^{} \Bigl( \sum_{{\begin{smallmatrix}{rs=d}\\ {r,s\in\mathbb{N}}\end{smallmatrix}}}^{} \Bigr)$$ =

$$\sum_{{\begin{smallmatrix}{rse=n}\\ {r,s,e\in\mathbb{N}}\end{smallmatrix}}}^{}$$ =

同理我們有

f*(g*h)(n) = $$\sum_{{\begin{smallmatrix}{duv=n}\\ {d,u,v\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d )g(u)h(v).

因此得證 (f*g)*h = f*(g*h). $\qedsymbol$

Proposition 2.4.2 告訴我們, 若將 * 看成是 arithmetic function 之間的運算, 則 $\delta$ 這一個 arithmetic function 就如同乘法運算的 1 (這樣的元素, 我們稱之為 identity). 而且 * 這個運算滿足交換率以及結合率. * 這個運算其實對於 multiplicative arithmetic function 也具有封閉性. 也就是說我們有以下之性質.

Theorem 2.4.3   假設 f, g 皆為 multiplicative arithmetic function, 則 f*g 也是 multiplicative arithmetic function.

証 明. 假設 a, b $\in$ $\mathbb {N}$ 且 gcd(a, b) = 1, 我們要證明 f*g(ab) = (f*g(a))(f*g(b)). 對任意 d, e $\in$ $\mathbb {N}$ 滿足 de = ab, 我們皆有 d| ab 且 e| ab. 依 Lemma 2.1.4 知分別存在唯一的一組 d₁, d₂ 以及 e₁, e₂ 滿足 d = d₁d₂ 及 e = e₁e₂ 其中 d₁, e₁ 為 a 的正因數 且 d₂, e₂ 為 b 的正因數. 又因 gcd(a, b) = 1, 故 gcd(d₁, d₂) = 1 且 gcd(e₁, e₂) = 1. 所以由 f, g 是 multiplicative 以及定義知

f*g(ab) = $$\sum_{{\begin{smallmatrix}{de=ab}\\ {d,e\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d )g(e) = $$\sum_{{\begin{smallmatrix}{d_1d_2e_1e_2=ab}\\ {d_1\vert a,d_2\ve... ...,e_1\vert a,e_2\vert b}\\ {d_1,d_2,e_1,e_2\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d₁)f (d₂)g(e₁)g(e₂).

現對任意 d₁, d₂, e₁, e₂ $\in$ $\mathbb {N}$ 滿足 d₁d₂e₁e₂ = ab 且 d₁, e₁ 和 d₂, e₂ 分別是 a 和 b 的因數. 因為 d₁e₁| ab, 又因 gcd(a, b) = 1 且 d₁, e₁ 是 a 的因數, 知 gcd(d₁e₁, b) = 1. 因此由 Proposition 1.2.7(1) 知 d₁e₁| a. 另一方面 a| d₁e₁d₂e₂, 再由 gcd(a, b) = 1 以及 d₂, e₂ 為 b 之因數, 得 gcd(a, d₂e₂) = 1. 因此知 a| d₁e₁. 所以得證 a = d₁e₁, 同理得證 b = d₂e₂. 反之, 若 d₁, d₂, e₁, e₂ $\in$ $\mathbb {N}$ 滿足 a = d₁e₁ 且 b = d₂e₂, 則我們有 d₁d₂e₁e₂ = ab 且 d₁, e₁ 和 d₂, e₂ 分別是 a 和 b 的因數. 因此我們有

$$\sum_{{\begin{smallmatrix}{d_1d_2e_1e_2=ab}\\ {d_1\vert a,d_2\ve... ...,e_1\vert a,e_2\vert b}\\ {d_1,d_2,e_1,e_2\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d₁)f (d₂)g(e₁)g(e₂) = $$\sum_{{\begin{smallmatrix}{d_1e_1=a,d_2e_2=b}\\ {d_1,d_2,e_1,e_2\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d₁)f (d₂)g(e₁)g(e₂).

另一方面

(f*g(a))(f*g(b)) = $$\sum_{{\begin{smallmatrix}{d_1e_1=a}\\ {d_1,e_1\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d₁)g(e₁)$$\sum_{{\begin{smallmatrix}{d_2e_2=b}\\ {d_2,e_2\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d₂)g(e₂).

利用分配率知

$$\sum_{{\begin{smallmatrix}{d_1e_1=a}\\ {d_1,e_1\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d₁)g(e₁)$$\sum_{{\begin{smallmatrix}{d_2e_2=b}\\ {d_2,e_2\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d₂)g(e₂) = $$\sum_{{\begin{smallmatrix}{d_1e_1=a,d_2e_2=b}\\ {d_1,d_2,e_1,e_2\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d₁)f (d₂)g(e₁)g(e₂).

因此得證本定理. $\qedsymbol$

若令 l : $\mathbb {N}$$\to$$\mathbb {N}$ 是一個 arithmetic function 滿足對任意 n $\in$ $\mathbb {N}$, l(n) = 1, 則對任意的 arithmetic function f, 皆有當 n $\in$ $\mathbb {N}$ 時,

f*l(n) = $$\sum_{{\begin{smallmatrix}{de=n}\\ {d,e\in\mathbb{N}}\end{smallmatrix}}}^{}$$f (d )l(e) = $$\sum_{d\vert n,d>0}^{}$$f (d ).

因為 l 是一個 multiplicative arithmetic function, 從這個角度看 Theorem 2.1.5 只是 Theorem 2.4.3 的一個特殊情況.

Example 2.4.4   我們可以利用 Theorem 2.4.3 來求對任意 n $\in$ $\mathbb {N}$,

$$\sum_{d\vert n,d>0}^{}$$$$\mu$$(d )$${\frac{n}{d}}$$

之值, 其中 $\mu$ 為 Möbius $\mu$-function (參見 Example 2.1.2).

令 $\mathcal {I}$ : $\mathbb {N}$$\to$$\mathbb {N}$ 是一個 arithmetic function 滿足對任意 n $\in$ $\mathbb {N}$, $\mathcal {I}$(n) = n. 考慮 F : $\mathbb {N}$$\to$$\mathbb {N}$ 是一個 arithmetic function 滿足對任意 n $\in$ $\mathbb {N}$,

F(n) = $$\sum_{d\vert n,d>0}^{}$$$$\mu$$(d )$${\frac{n}{d}}$$ = $$\sum_{d\vert n,d>0}^{}$$$$\mu$$(d )$$\mathcal {I}$$($${\frac{n}{d}}$$).

依定義我們知 F = $\mu$*$\mathcal {I}$. 然而 $\mu$ 和 $\mathcal {I}$ 皆為 multiplicative, 故利用 Theorem 2.4.3 知 F 也是 multiplicative. 因此我們只要檢視對任意質數 p 以及 t $\in$ $\mathbb {N}$, F(p^t) 之值為何. 依定義 $\mu$(1) = 1, $\mu$(p) = - 1 且當 i > 1 時 $\mu$(pⁱ) = 0, 故得

F(p^t) = $$\mu$$(1)$$\mathcal {I}$$(p^t) + $$\mu$$(p)$$\mathcal {I}$$(p^{t - 1}) = p^t - p^{t - 1}.

注意此和 $\phi$(p^t) 的值相同 (參見 Proposition 2.3.5), 故利用 F 和 $\phi$ 皆為 multiplicative 以及 Proposition 2.1.3 知 F = $\phi$. 也就是說對任意 n $\in$ $\mathbb {N}$ 皆有

$$\sum_{d\vert n,d>0}^{}$$$$\mu$$(d )$${\frac{n}{d}}$$ = $$\phi$$(n).