### Möbius Inversion for Categories

#### Posted by Tom Leinster

Every small category $A$ has a classifying space $B A$. It’s a topological space, and it can be constructed as the geometric realization of the nerve of $A$.

The homotopy type of $B A$ depends on every aspect of $A$: its
underlying directed graph, its composition, and its identities. But
the *Euler characteristic* of $B A$ does not: it only depends on
the underlying graph. What’s going on?

Last week I gave a talk about this at a conference in Louvain-la-Neuve, Belgium. I’ll also be doing a shorter version at the major annual category theory meeting in Vancouver. So, I’d be grateful for any comments, suggestions or thoughts. The slides are here.

(If the title slides mystify you, what you need to know is that the conference marked the appointment of Ross Street to a visiting *chaire*.)

As you’ll have surmised from the title, my answer was all about Möbius inversion. Let me explain…

In 1832, August Ferdinand Möbius introduced the number-theoretic Möbius inversion that crops up in elementary (and not so elementary) number theory. In modern language, we might say that the original Möbius inversion takes place in the poset of positive integers, ordered by divisibility.

In the mid-20th century, Möbius inversion was generalized to arbitrary posets. Several people came up with this idea, but it’s usually associated with the name of Gian-Carlo Rota, who demonstrated its importance in enumerative combinatorics.

(I tell a small lie: instead of ‘arbitrary posets’, I should say ‘arbitrary posets satisfying a
suitable finiteness condition’. I told a similar lie when speaking of
the Euler characteristic of $B A$, since it won’t *have* a
well-defined Euler characteristic unless $A$ satisfies some finiteness
condition.)

The stage was then set for generalizing from posets to (suitably finite) categories. This was done in two distinct ways.

First, there’s what I refer to in the slides as **fine Möbius
inversion**. You can find the definition there.
Here I just want to mention a couple of its features. For a
category $A$ to have fine Möbius inversion means that there’s a
**fine Möbius function**, that is, a function

$\mu: arr(A) \to k$

satisfying certain equations.
Here $arr(A)$ is the set of arrows of $A$ and $k$ is a commutative
ring over which we’ve chosen to work. Whether a category has
fine Möbius inversion *does* depend on its composition and
identities, as does the fine Möbius function (if it exists).

Second, there’s what I call **coarse Möbius inversion**. For a
category $A$ to have coarse Möbius inversion means that there’s a
**coarse Möbius function**, that is, a function

$\mu: ob(A) \times ob(A) \to k$

satisfying certain equations. Here $ob(A)$ is the set of objects of
$A$. Whether a category has coarse Möbius inversion does
*not* depend on its composition and identities, and nor does the
coarse Möbius function (if it exists).

All of this is described in more detail in the slides. References are on the final page.

What has this got to do with Euler characteristic? Well, it’s a theorem that if $A$ has coarse Möbius inversion (and is suitably finite) then

$\chi(B A) = \sum_{a, b} \mu(a, b).$

This result appeared in my first paper on Euler characteristic of categories. Since the right-hand side is independent of the composition and identities in $A$, so is the left-hand side.

(I should add that it’s also easy to show directly that $\chi(B A)$ is independent of composition and identities, at least under the usual finiteness assumptions. None of the proofs here are in any way difficult; it’s just a matter of trying to arrange things for maximum insight.)

But also, coarse and fine Möbius inversion are related as follows. If a category has fine Möbius inversion then it also has coarse Möbius inversion. Moreover, the coarse Möbius function is determined by the fine one:

$\mu(a, b) = \sum_{f\colon a \to b} \mu(f).$

So for a category with fine Möbius inversion, we also have

$\chi(B A) = \sum_{f \in arr(A)} \mu(f).$

The right-hand side appears to depend on the composition and identities in $A$, but, being equal to the left-hand side, does not.

## Re: Möbius Inversion for Categories

What a coincidence! Yesterday I happened to be thinking about Möbius inversion in the context of entropy! It turns out that mutual information can be generalized to interaction information, and this latter concept arises from a Möbius inversion on a poset. Since mutual information is of central importance in many applications of information theory, this might be an interesting example of Möbius inversion.

So let $R$ be a finite set of random variables. The relevant poset is the power set $2^R$. Any subset of variables $S\subseteq R$ has a joint entropy $H(S)$, which is the ordinary entropy of the joint distributions of the variables in $S$. For any $T\subseteq S\subseteq R$, we define the conditional entropy

$H(S|T) = H(S) - H(T)$

and then $H(\cdot|\cdot)$ is an element of the incidence algebra of the poset $2^R$. If we now consider $H\ast \mu$ and take the first argument to be the empty set, we recover precisely the formula for interaction information:

$(H\ast \mu)(\emptyset, V)=\sum_{T\subseteq V}(-1)^{|V\setminus T|}H(T)$

Now on to the question: given any commutative diagram in $\Fin\Prob$ (in terms of a functor $C\rightarrow\Fin\Prob$ from some finite category $C$), is there a way to talk about the

entropy associated to the diagram?The mutual information $H(X)+H(Y)-H(XY)$ should be a special case of such a construction where the diagram consists of the two morphisms $(X,Y)\rightarrow X$ and $(X,Y)\rightarrow Y$. Here, $(X,Y)$ is the joint distribution of the random variables $X$ and $Y$, and I don’t distinguish between distributions of random variables and probability spaces.

Okay, as John just said there are many possible routes for continuing on the entropy business, so this is just yet another question wanting to be pursued…

Your talk and Wikipedia call the constant function the

zeta function. Is there a particular reason for this term?