📂整数論

メビウスの反転公式の導出

公式 ¹

$f$ と $g$ は算術関数で、$\mu$ はメビウス関数だ。 $$ f(n) = \sum_{d \mid n} g(d) \iff g(n) = \sum_{d \mid n} f(d) \mu \left( {{ n } \over { d }} \right) $$

説明

メビウス関数は、初めに見た時に不自然な関数と思われがちだけど、実際には算術関数全体を貫く核心公式に現れる。任意の算術関数 $g$ の級数は、単位関数 $u$ と畳み込み $\ast$ を使って $g*u$ のように表せるけど、ちょうど $u$ の逆関数が $\mu$、すなわち $I = \mu \ast\ u$ だからだ。 戦略：$u$ は単位関数で、$I$ はアイデンティティだ。畳み込みと算術関数の級数関係を利用すれば簡単に導出できる。

導出

$(\Rightarrow)$

$$ f(n) = \sum_{d \mid n} g(d) = \sum_{d \mid n} g(d) u \left( {{ n } \over { d }} \right) $$ を畳み込み積として表せば、$f = g \ast\ u$ だ。

メビウス級数： $$ I(n) = \sum_{d \mid n } \mu (d) = \sum_{d \mid n } \mu (d) u \left( {{ n } \over { d }} \right) $$

同じく、メビウス級数を畳み込み積として表せば、$I = \mu \ast\ u$ なので $$ \begin{align*} f \ast\ \mu =& (g \ast\ u) \ast\ \mu \\ =& g \ast\ ( u \ast\ \mu ) \\ =& g \ast\ I \\ =& g \end{align*} $$

---

$(\Leftarrow)$

$$\begin{align*} & f \ast\ \mu = g \\ \implies& f \ast\ \mu \ast\ u = g \ast\ u \\ \implies& f \ast\ I = g \ast\ u \\ \implies& f = g \ast\ u \\ \implies& f(n) = \sum_{d \mid n} g(d) u \left( {{ n } \over { d }} \right) = \sum_{d \mid n} g(d) \end{align*} $$

■