Sunday, August 2, 2026

Möbius inversion formula

For the most general form, consider a finite poset $P$ and functions $$f,g:P\to\mathbb{C}$$ s.t. for every $x\in P$ $$g(x)=\sum_{y\le x}f(y).$$ If we try to recover $f$ from $g$ via $$f(x)=\sum_{y\le x}g(y)\mu(y,x),$$ what is required of $\mu$? 

From the perspective of the contribution of $f(y)$ to $g(z)$ and then to $f(x)$, we need $$\sum_{\{z:y\le z\le x\}}\mu(z,x)=\delta(y,x)$$ and $$\mu(y,x)=\begin{cases}1&y=x\\ -\sum_{\{z:y<z\le x\}}\mu(z,x)&y<x\\0&\text{otherwise}\end{cases}.$$


This looks different from textbooks!

From the perspective of the contribution of $g(y)$ to $f(z)$ and then to $g(x)$, we need $$\sum_{\{z:y\le z\le x\}}\mu(y,z)=\delta(y,x)$$ and $$\mu(y,x)=\begin{cases}1&y=x\\ -\sum_{\{z:y\le z< x\}}\mu(y,z)&y<x\\0&\text{otherwise}\end{cases}.$$


So, these two recurrences give the same function $\mu$.

No comments: