Intuition for Möbius function on a poset

Question

I am attempting to learn about Möbius inversion in the context of partial order theory. However, I'm hitting a bit of a mental block when it comes to understanding the Möbius function, and I'm looking for a clearer understanding of the motivation and intuition behind it.

Rota, for example, defines the function inductively as follows: $$ \mu(x,x)=1 $$ $$ \mu(x,y) = -\sum_{x\le z<y} \mu(x,z) $$ but then says "clearly $\mu$ is an inverse of $\zeta$".

Unfortunately it's far from clear to me! The definition doesn't seem to give me any intuition for what this function is, how I should expect it to behave, or even really how to do algebra with it. I've tried tabulating all the values of $\mu$ for a few small lattices, and I can verify that it is indeed an inverse of $\zeta$ in those cases, but it hasn't been very enlightening - I haven't been able to discern any meaning in the numbers it assigns.

In short, my question is, what is the Möbius function? How should I think about what it's doing, and how can I see its fundamental properties?

A note about my background: I'm working on applications in probability theory and information theory and I have zero knowledge of number theory --- so motivations and analogies from that direction won't help me, unless they can be explained starting from a novice level.

Edit: it's now clear to me that $\mu$ is indeed an inverse of $\zeta$. It helped to realise that for finite posets we can write these functions as matrices, in which case convolution is matrix multiplication and $\mu$ is the matrix inverse of $\zeta$. However, I'm still looking for a good explanation of what $\mu$ "really is", other than a convenient algebraic tool.

I suspect this question has an answer, because if my poset is a family of sets with the partial order relation being set inclusion, then $\mu$ seems to be saying something about which things you have to subtract off to avoid double-counting. (i.e. the inclusion-exclusion principle.) It's this intuition that I'd like to get a firmer handle on, particularly when it comes to general posets where the order relation is not set inclusion.

Answer 1

You can see this as being a direct analog of the inclusion-exclusion principle.

First off, the intuition about posets being a family of sets ordered by inclusion is universal — every poset is isomorphic to a poset of that form.

Then, I think what you're missing is the intuition about what $\zeta$ is. If your poset has a minimum $\bot$, then $(f \star \zeta)(\bot,y)$ is precisely the function that accumulates the value of $f(\bot,z)$ over all $z$ under $y$. $(f \star \zeta)(x,y)$ is similar, except restricted just to the things over $x$.

Then, if you know $(f \star \zeta)(x,z)$ for all $z$ below $y$, $\mu$ really is just the linear combination you need to to recombine those values to get the value of $f(x,y)$.

---

You're familiar with the inclusion-exclusion principle for complete lattices; another simple example might be useful: the poset of integers with their usual ordering.

In this poset, we can see that convolution with $\zeta$ is simply summation:

$$ (f \star \zeta)(x,y) = \sum_{i=x}^y f(x,i) $$

If $x < y$, there is an easy identity to recover the value of $f$:

$$ f(x,y) = \left(\sum_{i=x}^y f(x,i)\right) - \left(\sum_{i=x}^{y-1} f(x,i)\right) = (f \star \zeta)(x,y) - (f \star \zeta)(x,y - 1) $$

and thus the corresponding mobius function is

• $\mu(y,y) = 1$
• $\mu(y-1, y) = -1$
• $\mu(z, y) = 0$ when $z < y-1$

Answer 2

From the inductive representation of the Möbius function $\mu$ we obtain the representation \begin{align*} \mu(x,y)=1&\qquad\qquad x=y\\ \mu(x,y)+\sum_{x\leq z<y}\mu(x,z)=0&\qquad\qquad x<y \end{align*} or equivalently \begin{align*} \sum_{x\leq z\leq y}\mu(x,z)= \begin{cases} 1&\qquad x=y\\ 0&\qquad x<y \end{cases}\tag{1} \end{align*}

To become somewhat more familiar with (1) we look at the convolution $f\star g$ of two functions $f,g$ which is defined pointwise as \begin{align*} (f\star g)(x,y)=\sum_{x\leq z \leq y}f(x,z)g(z,y)\tag{2} \end{align*}

We need two more special functions. The first is the identity function $\delta$ defined as \begin{align*} \delta(x,y)= \begin{cases} 1&\qquad x=y\\ 0&\qquad x\ne y \end{cases} \end{align*}

The second one is the zeta function $\zeta$ defined as \begin{align*} \zeta(x,y)= \begin{cases} 1&\qquad x\leq y\\ 0&\qquad \text{otherwise} \end{cases} \end{align*}

The convolution of a function $f$ with the zeta-function gives \begin{align*} (f\star\zeta)(x,y)=\sum_{x\leq z\leq y}f(x,z)\zeta(z,y)=\sum_{x\leq z\leq y}f(x,z)\tag{3} \end{align*}

Considering the special case $f=\mu$ in (3) we obtain using (1) \begin{align*} (\mu\star\zeta)(x,y)&=\sum_{x\leq z\leq y}\mu(x,z)\zeta(z,y)=\sum_{x\leq z\leq y}\mu(x,z)=\delta(x,y)\\ (\zeta\star\mu)(x,y)&=\sum_{x\leq z\leq y}\zeta(x,z)\mu(z,y)=\sum_{x\leq z\leq y}\mu(z,y)=\delta(x,y)\\ \end{align*} or equivalently \begin{align*} \color{blue}{\mu\star\zeta=\delta=\zeta\star\mu} \end{align*}

Conclusion: The zeta function $\zeta$ and the Möbius function $\mu$ are inverse functions with respect to the convolution of functions. This implies whenever a function $g$ has a representation as convolution of a function $f$ with $\zeta$, we can derive the function $f$ by calculating the convolution of $g$ with $\mu$. \begin{align*} \color{blue}{f \star \zeta = g\quad\longleftrightarrow \quad f=g \star \mu} \end{align*}