Möbius Inversion

Unless otherwise emphasied, all the variables in this blog will refer to natural numbers. Also $0$ is not regarded as a natural number.

1. Convolution & Corresponding Math Structure

1.0. What is Möbius Inversion

The intuition of Möbius Inversion comes from the following situation. If $F:\mathbb {N\to R}$, and function $G$ is given by

$$G(n)=\sum_{k\mid n}F(k) $$

then how to express $F$ in terms of $G$ ?

1.1. Preliminary Definitions

We define the convolution ( $*$ ) of two functions $F,G:\mathbb N\to\mathbb R$ as follows:

$$F*G(n):=\sum_{k\mid n}F(k)\cdot G({n\over k}) $$

We then define the function One ($\mathbb 1$) as follows:

$$\forall n\in \mathbb N:\mathbb 1(n):=1 $$

Then by definition, it’s rather easy to check that $\forall n\in \mathbb N, \forall F,G:\mathbb{N\to R}$,

$$\begin{aligned} F*G(n) &=\sum_{k\mid n}F({n \over k})\cdot G(k)\\ &=G*F(n) \end{aligned} $$

and that

$$\begin{aligned} \mathbb 1*F(n) &=\sum_{k\mid n}\mathbb 1(k)\cdot F({n\over k})\\ &=\sum_{k\mid n}F(k) \end{aligned} $$

So the question to express $F$ in terms of $G$ now suffices to find the “inverse” of function $\mathbb 1$ since

$$G(n)=\mathbb 1 * F(n) $$

1.2. Indentity under Convolution

Let $\delta(n)=(n ==1)$. Or in a math manner, define

$$\delta(n)=\left\{ \begin{aligned} & 1, n=1\\ & 0, else \end{aligned} \right. $$

then we can check that $\delta$ is an identity function under convolution operator. Since

$$\begin{aligned} \delta *F(n) &=\sum_{k\mid n}\delta(k)\cdot F({n\over k})\\ &=\delta(1)\cdot F(n)+\sum_{\text{some }k\ge2}\delta(k)\cdot F({n\over k})\\ &=F(n) \end{aligned} $$

If you view $\mathcal G=(F,*)$ as a group, where $F:\mathbb{N\to R}$ is a function and $*$ is convolution, then $\delta$ is the identity in this group. But note that $\mathcal G$ is not a real group, since some elements are not inversable.

So suppose we can find a Inverse with of function $\mathbb 1$ respect to $\delta$, we then can find a explicit expression of $F$ by

$$\begin{aligned} G(n)&=\mathbb 1 * F(n)\\ \mathbb 1^{-1}*G(n)&=\mathbb 1^{-1}*\mathbb 1*F(n)\\ F(n)&=\mathbb 1^{-1}*G(n) \end{aligned} $$

1.3. The Existence of Inverse

Attention is all you need (x

Observe that such inverse of fuction $F(n)$ with respect to $\delta$ exist iff. $F(1)\neq 0$.

$Pf.$ Denote $F^{-1}$ by $G$. Suppose if $F(1)\neq 0$, take $n=1$

$$F*G(1)=F(1)G(1)=\delta(1)=1 $$

then $G(1)={1\over {F(1)}}$.

Suppose $G(k)$ can be derived for $k=1,2,...n\in \mathbb N$. Then

$$\begin{aligned} F*G(n+1)&=\sum_{k\mid {(n+1)}}F(k)G({n+1\over k})\\ &=\delta(n+1)=0\\ \Rightarrow G(n+1)&=-\frac{\displaystyle\sum_{2\le k\mid(n+1)}F(k)G({n+1\over k})}{F(1)}\\ \end{aligned} $$

can be explicitly derived by mathematical induction. Also by definition it’s trivial to check that if $F(1)=0$, then the inverse of $F$ cannot exist.

Since $\mathbb 1(1)=1\ne 0$, so the inverse of $\mathbb 1$ must exist, denoted by $\mu$. What’s the explicit expression of $\mu$ ?

1.4. Möbius Function

Such $\mu$ is called Möbius Function. Actually,

$$\mu(n)=\left\{ \begin{aligned} & 1, n=1\\ & (-1)^k, \text{\textit{n} is the product of \textit{k} different primes.} \\ & 0, \text{else} \end{aligned} \right. $$

Let’s check if $\mathbb 1* \mu(n) =\delta(n)$.

if $n=1$, you can get

$$\mathbb 1*\mu (n)=\sum_{k\mid n}\mathbb 1(k)\mu({\frac n k})=1 $$

if $n\ge 2$, write $n$ in the form of different prime fators, then

$$n=\prod_{i=1}^m p_i^{\alpha_i} $$

where $p_i$ is a prime for all $i=1,2,...,m$. Then

$$\begin{aligned} \mathbb 1*\mu (n) &=\sum_{k\mid n}\mathbb 1(k)\mu(\frac n k)\\ &=\sum_{k\mid n}\mu(k)\\ &=\sum_{\substack{0\le i_j\le \alpha_j\\}}\mu(\prod_{j=1}^mp_j^{i_j})\\ &=\sum_{\substack{0\le i_j\le 1\\}}\mu(\prod_{j=1}^mp_j^{i_j})\\ &=\sum_{\substack{0\le i_j\le 1\\}}(\mu(p_1\cdot\prod_{j=2}^mp_j^{i_j}) + \mu(\prod_{j=2}^mp_j^{i_j}))\\ &=\sum_{\substack{0\le i_j\le 1\\}}(1+(-1))\mu(\prod_{j=2}^mp_j^{i_j})\\ &=0 \end{aligned} $$

So we can explicitly denote $F$ as follows

$$F(n)=\sum_{k\mid n}\mu(k)\cdot G(\frac n k) $$

where $\mu(n)$ is the Möbius Function defined above.

2. Some applications

The most famous application, I believe, is the relation between a natural number $n$ and its Euler’s function $\varphi(n)$. Usually We use the Principle of Inclusion and Exclution to calculate the explicit expression of $\varphi$, but here we can use Möbius Inversion to do so.

Firstly recall that the definition of $\varphi:\mathbb{N\to N}$ is

$$\varphi(n)=\sum_{\substack{1\le d \le n\\\text{gcd}(d,n)=1}}1 $$

Observe that

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

This formula is not so obvious, but you can check it by definition. note that

$$\begin{aligned} \text{RHS} &=\sum_{d\mid n}\varphi(d)\\ &=\sum_{d\mid n}\varphi({n\over d})\\ &=\sum_{d\mid n}|{\{k\in \mathbb N\mid 1\le k\le n \text{ and gcd}(n,k)=d\}}| \end{aligned} $$

Note that by definition

$$\begin{aligned} &\bigsqcup_{d\mid n}{\{k\in \mathbb N\mid 1\le k\le n \text{ and gcd}(n,k)=d\}}\\ =&\{1,2,\ldots,n\} \end{aligned} $$

So $\text{RHS=LHS}$.

Denote $n$ by the product of $m$ primes, then by Möbius Inversion

$$\begin{aligned} \varphi(n)&=\sum_{d\mid n}\mu(d)\cdot {n\over d}\\ &=n\sum_{\substack{i_1,\ldots,i_m\in\{0,1\}}}\mu(\prod_{k=1}^mp_{i_k}^{i_k})\cdot { (\prod_{k=1}^mp_{i_k}^{i_k}})^{-1}\\ &=n\sum_{\substack{i_1,\ldots,i_m\in\{0,1\}}}(-1)^{i_1+i_2+\ldots+i_m}\cdot { (\prod_{k=1}^mp_{i_k}^{i_k}})^{-1}\\ &=n\sum_{i_1=0}^1\sum_{i_2=0}^1\cdots\sum_{i_m=0}^1(\prod_{k=1}^{m}({-1\over p_k}))\\ &=n\prod_{k=1}^m(1-{1\over p_k}) \end{aligned} $$

3. Generalized Möbius Inversion

Consider the set $X_n=\{1,2,\ldots,n\}$ of $n$ elements, and the partially ordered set $(\mathcal P(X_n), \subset)$ of all subsets of $X_n$ partially ordered by containment. Let

$$F:\mathcal P(X_n)\to \mathbb R $$

be a real-valued function defined on $\mathcal P(X_n)$, and we use $F$ to define a new function

$$G(K)=\sum_{L\subset K}F(K)\quad K\subset X_n $$