§ Mobius inversion on Incidence Algebras

Most of these functions are really defined on the incidence algebra of the poset $P$ with ground field $K$. An incidence algebra $I(P)$ is a set of functions which maps intervals of $P$ to the ground field $K$. an interval is a tuple $(x, y) \in P \times P$ such that $x \leq P$ (where the $\leq$ comes from the partial order on $P$). We have a product structure which I denote $\star$, given by:

$$(\alpha \star \beta)([x, z]) = \sum_{x \leq y \leq z} \alpha(x, y) \beta(y, z)$$

A linear algebra way to look at this is to consider $|P| x |P|$ matrices over $K$ where the rows and columns are indexed by $P$. The a function $\alpha: P \times P \rightarrow K$ can be written as the elements of the $P \times P$ matrix. Then this convolution-like operator $\star$ is simply matrix multiplication. We have three natural functions: (1) The characteristic function, which is the identity for $\star$:

$$\delta([x, z]) \equiv 1 \texttt{ if } x = z \texttt{; } 0 \texttt{ otherwise }$$

(2) the zeta function, which plays the role of the constant $1$:

$$\zeta([x, z]) \equiv 1 \texttt{ if } x \leq z \texttt{; } 0 \texttt{ otherwise }$$

(3) The inverse of the zeta function, the mobius function, a tool for mobius inversion:

$$\begin{aligned} &\mu([x, z]) = 1 \\ &\mu([x, z]) = - \sum_{x \leq y < z} \mu([x, y]) \\ \end{aligned}$$

The mobius inversion theorem for posets states that $\zeta$ and $\mu$ as defined above are convolutional inverses. that is, $\zeta \star \mu = \delta$. This allows us to prove:

$$\begin{aligned} &g([x, z]) = \sum_{x \leq y \leq z} f([x, y]) \\ &g([x, z]) = \sum_{x \leq y \leq z} f([x, y]) \cdot 1 \\ &g([x, z]) = \sum_{x \leq y \leq z} f([x, y]) \cdot \zeta(y, z) \\ &g = f \star \zeta \\ &g \star \mu = f \star \zeta \star \mu \\ &g \star \mu = f \star \delta \\ &g \star \mu = f \end{aligned}$$

We have managed to find $f$ in terms of $g$, when previously we had $g$ in terms of $f$. TODO : we are usually interested in a fixed $[x, z]$. What happens if we make this implicit? We may get nice notation for all of this!

§ Sums as mobius inversion

We can derive the formula we had for integrals, that:

$$F(i) = \sum_{0 \leq i \leq n} f(i) \iff f(k) = F(k) - F(k-1)$$

by setting up mobius inversion on the usual partial order for the natural numbers. For simplicity, I'll show the example on $[0, 1, 2, 3, 4]$. The example immediately generalizes.

• We have the partial (well, total) order $P$: $0 < 1 < 2 < 3 < 4$.
• We are given a function $f(\cdot)$ we wish to integrate. We define an auxiliary function $fi([x, y]) = f(y)$ which evaluates $f$ on the right endpoint.
• We can now define $F([x, z])$ as the sum of $f$ from $x$ to $z$:

$$\begin{aligned} &F([x, z]) \equiv \sum_{x \leq y \leq z} f(y) \\ &= \sum_{x \leq y \leq z} fi([x, y]) \\ &= \sum_{x \leq y \leq z} fi([x, y]) \cdot \zeta(y, z) \\ &= fi \star \zeta \end{aligned}$$

• This tells us that $f(n) = fi([0, n]) = (F \star \mu)([0, n])$:

$$\begin{aligned} &f(n) = fi([0, n]) \equiv (F \star mu)[0, n] \\ &= \sum_{0 \leq x \leq n} F([0, x]) \mu([x, n]) \end{aligned}$$

• We note that we need to know the values of $\mu([x, n])$ for a fixed n, for varying x. Let us attempt to calculate $\mu([0, 4]), \mu([1, 4]), \mu([2, 4]), \mu([3, 4]), \mu([4, 4])$and see if this can be generalized:

$$\begin{aligned} & \mu([4, 4]) = 1 \text{ By definition} \\ & \mu([3, 4]) = - \left (\sum_{3 \leq x < 4} \right) \text{ By definition } \\ \end{aligned}$$