乗法的関数とメビウスの反転公式

ここでは、$n$ は正の整数のことを表すとします．また、$d$ で $n$ の約数、$p$ で任意の素数を表すことにします．オイラー関数 $\varphi(n)$ は $n$ と互いに素な正の整数の個数として定義されます．つまり、

$\varphi(n)=\#\{k\in{\Bbb N}|\gcd(k,n)=1\}$

です．そうすると、$n$までの数を正しく見てやることで

$$n=\sum_{d|n}\varphi(d)$$ 

が成り立ちます．この和は、$n$を割り切る正の整数 $d$ 全体をわたって足すということを意味します．このオイラー関数は

$$\varphi(n)=n\sum_{p|n}(1-\frac{1}{p})$$

と書き表すことができますので、（数論的な）乗法的関数です．数論的な乗法的関数 $A$ とは、互いに素な $n,m$ があったときに

$$A(nm)=A(n)A(m)$$
が成りたつことをいいます．乗法的関数 $f(n)$ があったときに、基本的かつ重要な性質は、

$$g(n)=\sum_{d|n}f(d)$$

と新しく関数 $g(n)$ を定義しても $g(n)$ が乗法的関数であることです．

これは、互いに素な数の積 $nm$ の中の任意の約数は、$n,m$のそれぞれの約数をいくつか取ってかけて一意的に得られているから当然です．

また、恒等関数 $\text{id}(n)=n$ や定数関数 $1(n)=1$ も明らかに乗法的関数となります．

メビウス関数 $\mu(n)$ は、

$$\mu(n)=\begin{cases}0&n\text{に平方因子が存在する．}\\(-1)^k&n=p_1\cdots p_k\text{ここで、$p_1,\cdots,p_k$ は相異なる素数}\\1&n=1\end{cases}$$

と定義しますと、実はメビウス関数は数論的乗法関数になっています．証明は略します．

このとき、$\sum_{d|n}\mu(d)$ の値は

$$\Delta(n)=\begin{cases}1&n=1\\0&n\neq 1\end{cases}$$

となります．$n=1$ のときは明らかに成り立ち、$n\neq 1$ のときは、素べきの場合をやれば十分ですが、$\sum_{d|p^a}\mu(d)=1+\mu(p)=0$ より、上が成り立ちます．

このとき、有名なメビウスの反転公式を紹介します．

定理（メビウスの反転公式）

$f(n)$を乗法的関数とする．このとき、以下が成り立つ．

$$g(n)=\sum_{d|n}f(n)\Leftrightarrow f(n)=\sum_{d|n}\mu(\frac{n}{d})g(d)$$

この右の右辺を $\mu\ast g(n)=\sum_{d|n}\mu(\frac{n}{d})g(d)$ と書くことにします．
この積 $\ast$ を畳みこみと呼ぶこともあります．つまり、全ての約数に関する和によって得られる関数は
$$(1\ast f)(n)$$
とかくことができます．乗法的関数全体は積 $\ast$ に関して全ての関数のなかで部分可換群をなします．そのとき、$\text{id}$ や $1$ は単位元ではなく、関数 $\Delta$ が単位元となります．

$\Rightarrow$ を証明すると、

$\sum_{d|n}\mu(\frac{n}{d})f(d)=\sum_{d|n}\mu(\frac{n}{d})\sum_{c|d}f(c)$

$f(c)$ ごとにまとめておけば、

$\sum_{c|n}f(c)\sum_{d|\frac{n}{c}}\mu(\frac{n}{d})=\sum_{c|n}f(c)\sum_{\frac{d}{c}|\frac{n}{c}}\mu(\frac{n}{d})$

$$\sum_{\frac{d}{c}|\frac{n}{c}}\mu(\frac{n}{d})=\sum_{b|\frac{n}{c}}\mu(b)=\begin{cases}1&n=c\\0&n\neq c\end{cases}$$

より、$\sum_{d|n}\mu(\frac{n}{d})f(d)=f(n)$ がなりたちます．

逆は略します．

ここでは、乗法的関数の変換 $f(n)\rightarrow g(n)$ をメビウス変換(Möbius transform)、その逆 $f(n)\leftarrow g(n)$ を逆メビウス変換(inverse Möbius transform)ということにします．つまり、メビウス変換は $g=1\ast f$ であり、逆メビウス変換は $f=\mu\ast g$ です．なので、$1\ast \mu=\mu\ast 1=\Delta$ が成り立ちます．

メビウス変換は複素平面上の一次分数変換にも用いますので注意が必要なのですが、状況として用語が被ることはないと思いますのでこのまま続けます．

例えば、先ほどのオイラー関数を $f(n)=\varphi(n)$ とすると、メビウス変換は
$$1\ast \varphi(n)=\text{id}(n)$$
となります．また、恒等変換に対しては、
$$1\ast\text{id}(n)=\sigma(n)=\sum_{d|n}d$$
となります．$\sigma$ は約数の総和の関数です．

定数関数に対しては
$$1\ast 1(n)=d(n)$$
となります．$d(n)$ は約数の個数の関数です．

$d(n)$ は $n=p_1^{n_1}\cdots p_{r}^{n_r}$ と素因数分解しておけば、
$$d(n)=\prod_{i=1}^r(n_i+1)$$
と表すことができますので、乗法的関数であることも確かめられます．

また、フォン-マンゴルト関数 $\Lambda(n)$ を
$$\Lambda(n)=\begin{cases}\log p& n=p^m\\0&n\neq p^m\end{cases}$$
として定義しておきます．$p^m$ は何らかの素数べきのことです．$\Lambda(n)$ は乗法的ではありませんが、
この関数をメビウス変換をすると完全加法的である対数関数 $\log(n)$ になっています．つまり、
$$\log(n)=1\ast\Lambda(n)=\sum_{d|n}\Lambda(d)$$
が成り立ちます．これは$d$ として $n$ に含まれる各素因数のべきについて和をとればいいわけですからすぐわかりますね．