📂Number Theory

Mobius Inversion Formula Derivation

Formulas ¹

$f$ and $g$ are arithmetic functions and $\mu$ is the Möbius function. $$ f(n) = \sum_{d \mid n} g(d) \iff g(n) = \sum_{d \mid n} f(d) \mu \left( {{ n } \over { d }} \right) $$

Explanation

The Möbius function might seem unnatural at first glance, but it actually appears in the core formulas that permeate all arithmetic functions. An arbitrary arithmetic function $g$’s series can be expressed using the unit function $u$ and convolution $\ast$ as $g*u$, precisely because the inverse of $u$ is $\mu$, in other words, $I = \mu \ast\ u$. Strategy: $u$ is the unit function and $I$ is the identity. The series relationship of arithmetic functions with convolution can be easily derived.

Derivation

$(\Rightarrow)$

$$ f(n) = \sum_{d \mid n} g(d) = \sum_{d \mid n} g(d) u \left( {{ n } \over { d }} \right) $$ can be expressed as a convolution product, which is $f = g \ast\ u$.

Möbius series: $$ I(n) = \sum_{d \mid n } \mu (d) = \sum_{d \mid n } \mu (d) u \left( {{ n } \over { d }} \right) $$

Likewise, the Möbius series expressed as a convolution product is $I = \mu \ast\ u$ therefore $$ \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*} $$

■