# 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^{}:

$f(n)$ | $=$ | $\sum _{d|n}}g(d)\mathit{\text{for all}}n\in {\mathbb{N}}^{*$ | (1) | ||

$g(n)$ | $=$ | $\sum _{d|n}}\mu (d)f\left({\displaystyle \frac{n}{d}}\right)\mathit{\text{for all}}n\in {\mathbb{N}}^{*$ | (2) |

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

$\sum _{d|n}}\mu (d)f\left({\displaystyle \frac{n}{d}}\right)$ | $=$ | $\sum _{d|n}}\mu (d){\displaystyle \sum _{e|n/d}}g(e)$ | ||

$=$ | $\sum _{k|n}}{\displaystyle \sum _{d|k}}\mu (d)g\left({\displaystyle \frac{n}{k}}\right)$ | |||

$=$ | $\sum _{k|n}}g\left({\displaystyle \frac{n}{k}}\right){\displaystyle \sum _{d|k}}\mu (d)$ | |||

$=$ | $g(n),$ |

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

Conversely, assuming (2), we get

$\sum _{d|n}}g(d)$ | $=$ | $\sum _{d|n}}{\displaystyle \sum _{e|d}}\mu (e)f\left({\displaystyle \frac{d}{e}}\right)$ | ||

$=$ | $\sum _{k|n}}f\left({\displaystyle \frac{n}{k}}\right){\displaystyle \sum _{e|k}}\mu \left({\displaystyle \frac{k}{e}}\right)$ | |||

$=$ | $f(n)\mathit{\hspace{1em}\hspace{1em}}\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,\le )$ be a locally finite^{} ordered set, i.e. an ordered set such that
$\{z\in S|x\le z\le 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

$\alpha (x,x)$ | $=$ | $1\text{for all}x\in S$ | (3) | ||

$\alpha (x,y)$ | $\ne $ | $0\text{implies}x\le 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{array}{cc}1\hfill & \text{if}x\le y\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$ |

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{array}{cc}1\hfill & \text{if}x=y\text{,}\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$ |

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

$f$ | $=$ | $\iota g$ | (5) | ||

$g$ | $=$ | $\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:

Proposition^{} 3: 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\le z\le 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^{}.

## An Additional Generalization

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}\to \u2102$ and define $F:\mathbb{R}\to \u2102$ by $F(x)={\sum}_{n\le x}f(\frac{x}{n})$.

Then

$f(x)={\displaystyle \sum _{n\le x}}\mu (n)F\left({\displaystyle \frac{x}{n}}\right).$ |

Title | Möbius inversion |

Canonical name | MobiusInversion |

Date of creation | 2013-03-22 11:46:58 |

Last modified on | 2013-03-22 11:46:58 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 25 |

Author | mathcam (2727) |

Entry type | Topic |

Classification | msc 11A25 |

Synonym | Moebius inversion |

Related topic | MoebiusFunction |

Defines | Mobius inversion formula |

Defines | Mobius transform |

Defines | Mobius function |

Defines | Mobius-Rota inversion |