The Möbius Inversion Formula

前面在介紹 Euler's $\phi$-function 時, 我們曾提及不容易找到 arithmetic function f 將 $\phi$-function 表成 $\phi$(n) = $\sum_{d\vert n,d>0}^{}$f (d ) 這樣的形式. 事實上 Möbius inversion formula 可以幫助我們找到這樣的 f.

Theorem 2.5.1 (Möbius Inversion Formula)   假設 F, f 皆為 arithmetic function, $\mu$ 為 möbius $\mu$-function. 則對任意 n $\in$ $\mathbb {N}$, F, f 滿足

F(n) = $$\sum_{d\vert n,d>0}^{}$$f (d ),

若且唯若對任意 n $\in$ $\mathbb {N}$, F, f 滿足

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

証 明. 令 l : $\mathbb {N}$$\to$$\mathbb {N}$ 是一個 arithmetic function 滿足對任意 n $\in$ $\mathbb {N}$, l(n) = 1. 依 convolution 的定義我們要證明 F = f*l 若且唯若 f = F*$\mu$.

若 F = f*l, 則 F*$\mu$ = (f*l)*$\mu$. 利用 Proposition 2.4.2(3) 知 F*$\mu$ = f*(l*$\mu$). 然而對任意 n $\in$ $\mathbb {N}$, l*$\mu$(n) = $\mu$*l(n) = $\sum_{d\vert n,d>0}^{}$$\mu$(d ), 由 Example 2.1.6 知 l*$\mu$ = $\mu$*l = $\delta$, 其中 $\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}$$

換言之, 我們有 F*$\mu$ = f*(l*$\mu$) = f*$\delta$. 因而利用 Proposition 2.4.2(1) 得證 F*$\mu$ = f.

反之, 若 f = F*$\mu$, 則 f*l = (F*$\mu$)*l = F*($\mu$*l). 故再利用 $\mu$*l = $\delta$ 得知 f*l = F*$\delta$ = F. $\qedsymbol$

注意 Möbius inversion formula 需要對任意 n $\in$ $\mathbb {N}$ 對才能使用. 也就是說你不能看到

F(6) = f (1) + f (2) + f (3) + f (6)

就下結論說

f (6) = F(1)$$\mu$$(6) + F(2)$$\mu$$(3) + F(3)$$\mu$$(2) + F(6)$$\mu$$(1) = F(1) - F(2) - F(3) + F(6).

需要檢驗所有 n $\in$ $\mathbb {N}$ 都對才可下此結論 (至少在此例中還要多檢查 F(1) = f (1) , F(2) = f (1) + f (2) 以及 F(3) = f (1) + f (3)).

Example 2.5.2   現在我們來看看如何利用 Möbius inversion formula, 找到 f 使得 $\phi$(n) = $\sum_{d\vert n,d>0}^{}$f (d ). 由 Möbius inversion formula 知此時 f = $\mu$*$\phi$. 由於 $\mu$ 和 $\phi$ 皆為 multiplicative, 由 Theorem 2.4.3 知 f 亦為 multiplicative. 因此我們先觀察對任意質數 p 以及 t $\in$ $\mathbb {N}$, f (p^t) 之值. 然而

f (p^t) = $$\sum_{d\vert p^t,d>0}^{}$$$$\mu$$(d )$$\phi$$($${\frac{p^t}{d}}$$) = $$\mu$$(1)$$\phi$$(p^t) + $$\mu$$(p)$$\phi$$(p^{t - 1}) = $$\phi$$(p^t) - $$\phi$$(p^{t - 1}).

因此知 f (p) = p - 1 - 1 = p - 2 且當 t$\ge$2 時 f (p^t) = p^t - p^{t - 1} - (p^{t - 1} - p^{t - 2}) = p^{t - 2}(p - 1)². 因此若 n = p₁^{n₁ ...} p_r^n_r, 其中 p_i 為相異質數, 可以得 f (n) = f (p₁^n₁) ^... f (p_r^n_r). 但是接下來很難將 f 寫成很好的形式 (注意要區分有某個 n_i = 1 的情形). 事實上若沒有 Möbius inversion formula, 我們也很難證出這個 f 確實滿足 $\mu$(n) = $\sum_{d\vert n,d>0}^{}$f (d ). 所以當初在證明 $\phi$ 是 multiplicative 時, 我們並沒有利用 Theorem 2.1.5 證得.

事實上利用 Example 2.5.2 的方法我們可以證出任何的 arithmetic function F 皆可找到唯一的 arithmetic function f 使得對任意 n $\in$ $\mathbb {N}$, 皆有 F(n) = $\sum_{d\vert n,d>0}^{}$f (d ). 當我們找到的 f 是 multiplicative 時, Theorem 2.1.5 告訴我們 F 也是 multiplicative. 反之, 以下 Corollary 告訴我們若已知 F 是 multiplicative, 則找出的 f 一定也是 multiplicative.

Corollary 2.5.3   假設 F, f 皆為 arithmetic function. 若對任意 n $\in$ $\mathbb {N}$, 皆有

F(n) = $$\sum_{d\vert n,d>0}^{}$$f (d )

且已知 F 是一個 multiplicative arithmetic function, 則 f 亦為一個 multiplicative arithmetic function.

証 明. 由 Theorem 2.5.1 知 f = $\mu$*F, 故由 $\mu$ 是 multiplicative 以及 F 是 multiplicative 的假設, 利用 Theorem 2.4.3 知 f = $\mu$*F 亦為 multiplicative. $\qedsymbol$

Example 2.5.4   前面幾節中我們曾利用 multiplicative arithmetic function 得到一些有趣的等式, 接下來的例子我們將利用 Möbius inversion formula 得到更多等式.

1. 令 v(n) 表示 n 的正因數個數. 已知對任意 n $\in$ $\mathbb {N}$, 皆有
   v(n) = $$\sum_{d\vert n,d>0}^{}$$1 = $$\sum_{d\vert n,d>0}^{}$$l(d ),
   其中對所有 n $\in$ $\mathbb {N}$, l(n) = 1, 故利用 Möbius inversion formula 知對任意 n $\in$ $\mathbb {N}$,
   1 = l(n) = $$\sum_{d\vert n,d>0}^{}$$$$\mu$$(d )v($${\frac{n}{d}}$$) = $$\sum_{d\vert n,d>0}^{}$$v(d )$$\mu$$($${\frac{n}{d}}$$).

2. 令 $\sigma$(n) 表示 n 的所有正因數之和. 已知對任意 n $\in$ $\mathbb {N}$ 皆有
   $$\sigma$$(n) = $$\sum_{d\vert n,d>0}^{}$$d = $$\sum_{d\vert n,d>0}^{}$$$$\mathcal {I}$$(d ),
   其中對所有 n $\in$ $\mathbb {N}$, $\mathcal {I}$(n) = n, 故利用 Möbius inversion formula 知對任意 n $\in$ $\mathbb {N}$,
   n = $$\mathcal {I}$$(n) = $$\sum_{d\vert n,d>0}^{}$$$$\mu$$(d )$$\sigma$$($${\frac{n}{d}}$$) = $$\sum_{d\vert n,d>0}^{}$$$$\sigma$$(d )$$\mu$$($${\frac{n}{d}}$$).

3. 由 Corollary 2.3.6 知對任意 n $\in$ $\mathbb {N}$ 皆有
   n = $$\mathcal {I}$$(n) = $$\sum_{d\vert n,d>0}^{}$$$$\phi$$(d ),
   故利用 Möbius inversion formula 知對任意 n $\in$ $\mathbb {N}$, 皆有
   $$\phi$$(n) = $$\sum_{d\vert n,d>0}^{}$$$$\mu$$(d )$$\mathcal {I}$$($${\frac{n}{d}}$$) = $$\sum_{d\vert n,d>0}^{}$$$$\mu$$(d )$${\frac{n}{d}}$$.

Example 2.5.4(3) 的等式在前一節 Example 2.4.4 中我們曾用 multiplicative 的性質得到. 事實上 Example 2.5.4 中的等式都可以用 multiplicative 的性質得到. 不過要注意的是 Möbius inversion formula 並不侷限於 multiplicative 的情形, 它對 一般的 arithmetic function 皆適用.