# Möbius inversion

###### Theorem 1 (Moebius Inversion).

Let $\mu$ be the Moebius function, and let $f$ and $g$ be two functions on the positive integers. Then the following two conditions are equivalent:

 $\displaystyle f(n)$ $\displaystyle=$ $\displaystyle\sum_{d|n}g(d)\textrm{ for all }n\in\mathbb{N}^{*}$ (1) $\displaystyle g(n)$ $\displaystyle=$ $\displaystyle\sum_{d|n}\mu(d)f\left(\frac{n}{d}\right)\textrm{ for all }n\in% \mathbb{N}^{*}$ (2)

Proof: Fix some $n\in\mathbb{N}^{*}$. Assuming (1), we have

 $\displaystyle\sum_{d|n}\mu(d)f\left(\frac{n}{d}\right)$ $\displaystyle=$ $\displaystyle\sum_{d|n}\mu(d)\sum_{e|n/d}g(e)$ $\displaystyle=$ $\displaystyle\sum_{k|n}\sum_{d|k}\mu(d)g\left(\frac{n}{k}\right)$ $\displaystyle=$ $\displaystyle\sum_{k|n}g\left(\frac{n}{k}\right)\sum_{d|k}\mu(d)$ $\displaystyle=$ $\displaystyle g(n),$

the last step following from the identity given in the Mobius function entry.

Conversely, assuming (2), we get

 $\displaystyle\sum_{d|n}g(d)$ $\displaystyle=$ $\displaystyle\sum_{d|n}\sum_{e|d}\mu(e)f\left(\frac{d}{e}\right)$ $\displaystyle=$ $\displaystyle\sum_{k|n}f\left(\frac{n}{k}\right)\sum_{e|k}\mu\left(\frac{k}{e}\right)$ $\displaystyle=$ $\displaystyle f(n)\qquad\text{(by the same identity)}$

as claimed.

Definitions: In the notation above, $f$ is called the Möbius transform of $g$, and formula (2) is called the Möbius inversion formula.

## Möbius-Rota inversion

G.-C. Rota has described a generalization of the Möbius formalism. In it, the set $\mathbb{N}^{*}$, ordered by the relation $x|y$ between elements $x$ and $y$, is replaced by a more general ordered set, and $\mu$ is replaced by a function of two variables.

Let $(S,\leq)$ be a locally finite ordered set, i.e. an ordered set such that $\{z\in S|x\leq z\leq y\}$ is a finite set for all $x,y\in S$. Let $A$ be the set of functions $\alpha:S\times S\to\mathbb{Z}$ such that

 $\displaystyle\alpha(x,x)$ $\displaystyle=$ $\displaystyle 1\textrm{ for all }x\in S$ (3) $\displaystyle\alpha(x,y)$ $\displaystyle\neq$ $\displaystyle 0\textrm{ implies }x\leq y$ (4)

$A$ becomes a monoid if we define the product of any two of its elements, say $\alpha$ and $\beta$, by

 $(\alpha\beta)(x,y)=\sum_{t\in S}\alpha(x,t)\beta(t,y).$

The sum makes sense because $\alpha(x,t)\beta(t,y)$ is nonzero for only finitely many values of $t$. (Clearly this definition is akin to the definition of the product of two square matrices.)

Consider the element $\iota$ of $A$ defined simply by

 $\iota(x,y)=\begin{cases}1&\textrm{ if x\leq y}\\ 0&\text{otherwise.}\end{cases}$

The function $\iota$, regarded as a matrix over $\mathbb{Z}$, has an inverse matrix, say $\nu$. That means

 $\sum_{t\in S}\iota(x,t)\nu(t,y)=\begin{cases}1&\text{if x=y,}\\ 0&\text{otherwise.}\end{cases}$

Thus for any $f,g\in A$, the equations

 $\displaystyle f$ $\displaystyle=$ $\displaystyle\iota g$ (5) $\displaystyle g$ $\displaystyle=$ $\displaystyle\nu f$ (6)

are equivalent.

Now let’s sketch out how the traditional Möbius inversion is a special case of Rota’s notion. Let $S$ be the set $\mathbb{N}^{*}$, ordered by the relation $x|y$ between elements $x$ and $y$. In this case, $\nu$ is essentially a function of only one variable:

With the above notation, $\nu(x,y)=\mu(y/x)$ for all $x,y\in\mathbb{N}^{*}$ such that $x|y$.

The proof is fairly straightforward, by induction on the number of elements of the interval $\{z\in S|x\leq z\leq y\}$.

Now let $g$ be a function from $\mathbb{N}^{*}$ to some additive group, and write $\overline{g}(x,y)=g(y/x)$ for all pairs $(x,y)$ such that $x|y$.

Example: Let $E$ be a set, and let $S$ be the set of all finite subsets of $E$, ordered by inclusion. The ordered set $S$ is left-finite, and for any $x,y\in S$ such that $x\subset y$, we have $\nu(x,y)=(-1)^{|y-x|}$, where $|z|$ denotes the cardinal of the finite set $z$.

A slightly more sophisticated example comes up in connection with the chromatic polynomial of a graph or matroid.

A final generalization of Moebius inversion occurs when the sum is taken over all integers less than some real value $x$ rather than over the divisors of an integer. Specifically, let $f:\mathbb{R}\rightarrow\mathbb{C}$ and define $F:\mathbb{R}\rightarrow\mathbb{C}$ by $F(x)=\sum_{n\leq x}f(\frac{x}{n})$.
 $\displaystyle f(x)=\sum_{n\leq x}\mu(n)F\left(\frac{x}{n}\right).$