§ Mobius inversion on Incidence Algebras

Most of these functions are really defined on the incidence algebra of the poset PP with ground field KK. An incidence algebra I(P) I(P) is a set of functions which maps intervals of PP to the ground field KK. an interval is a tuple (x,y)P×P(x, y) \in P \times P such that xPx \leq P (where the \leq comes from the partial order on PP). We have a product structure which I denote \star, given by:
(αβ)([x,z])=xyzα(x,y)β(y,z) (\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 PxP|P| x |P| matrices over KK where the rows and columns are indexed by PP. The a function α:P×PK\alpha: P \times P \rightarrow K can be written as the elements of the P×PP \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:
δ([x,z])1 if x=z; 0 otherwise  \delta([x, z]) \equiv 1 \texttt{ if } x = z \texttt{; } 0 \texttt{ otherwise }
(2) the zeta function, which plays the role of the constant 11:
ζ([x,z])1 if xz; 0 otherwise  \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:
μ([x,z])=1μ([x,z])=xy<zμ([x,y]) \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:
g([x,z])=xyzf([x,y])g([x,z])=xyzf([x,y])1g([x,z])=xyzf([x,y])ζ(y,z)g=fζgμ=fζμgμ=fδgμ=f \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 ff in terms of gg, when previously we had gg in terms of ff. TODO: we are usually interested in a fixed [x,z][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)=0inf(i)    f(k)=F(k)F(k1) 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][0, 1, 2, 3, 4]. The example immediately generalizes.
  • We have the partial (well, total) order PP: 0<1<2<3<40 < 1 < 2 < 3 < 4.
  • We are given a function f()f(\cdot) we wish to integrate. We define anauxiliary function fi([x,y])=f(y)fi([x, y]) = f(y) which evaluates ff on the rightendpoint.
  • We can now define F([x,z])F([x, z]) as the sum of ff from xx to zz:
F([x,z])xyzf(y)=xyzfi([x,y])=xyzfi([x,y])ζ(y,z)=fiζ \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μ)([0,n])f(n) = fi([0, n]) = (F \star \mu)([0, n]):
f(n)=fi([0,n])(Fmu)[0,n]=0xnF([0,x])μ([x,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 μ([x,n])\mu([x, n]) for a fixed n,for varying x. Let us attempt to calculate μ([0,4]),μ([1,4]),μ([2,4]),μ([3,4]),μ([4,4])\mu([0, 4]), \mu([1, 4]), \mu([2, 4]), \mu([3, 4]), \mu([4, 4])and see if this can be generalized:
μ([4,4])=1 By definitionμ([3,4])=(3x<4) By definition  \begin{aligned} & \mu([4, 4]) = 1 \text{ By definition} \\ & \mu([3, 4]) = - \left (\sum_{3 \leq x < 4} \right) \text{ By definition } \\ \end{aligned}