§ Mobius inversion on Incidence Algebras
Most of these functions are really defined on the incidence algebra of
the poset with ground field . An incidence algebra is a
set of functions which maps intervals of to the ground field . an
interval is a tuple such that
(where the comes from the partial order on ). We have a product
structure which I denote , given by:
A linear algebra way to look at this is to consider matrices over
where the rows and columns are indexed by .
The a function
can be written as the elements of the matrix.
Then this convolution-like operator is simply matrix multiplication.
We have three natural functions:
(1) The characteristic function, which is the identity for :
(2) the zeta function, which plays the role of the constant :
(3) The inverse of the zeta function, the mobius function, a tool for mobius inversion:
The mobius inversion theorem for posets states that and as
defined above are convolutional inverses. that is, .
This allows us to prove:
We have managed to find in terms of , when previously we had
in terms of .
TODO : we are usually interested in a fixed . 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:
by setting up mobius inversion on the usual partial order for the natural
numbers. For simplicity, I'll show the example on . The example
- We have the partial (well, total) order : .
- We are given a function we wish to integrate. We define an auxiliary function which evaluates on the right endpoint.
- We can now define as the sum of from to :
- This tells us that :
- We note that we need to know the values of for a fixed n, for varying x. Let us attempt to calculate and see if this can be generalized: