Incidence algebra

In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set
and commutative ring with unity. Subalgebras called reduced incidence algebras give a natural construction of various types of generating functions used in combinatorics and number theory.
Definition.
A locally finite poset is one in which every closed interval
is finite.
The members of the incidence algebra are the functions "f" assigning to each nonempty interval ["a, b"] a scalar "f"("a", "b"), which is taken from the "ring of scalars", a commutative ring with unity. On this underlying set one defines addition and scalar multiplication pointwise, and "multiplication" in the incidence algebra is a convolution defined by
An incidence algebra is finite-dimensional if and only if the underlying poset is finite.
Related concepts.
An incidence algebra is analogous to a group algebra; indeed, both the group algebra and the incidence algebra are special cases of a category algebra, defined analogously; groups and posets being special kinds of categories.
Upper-Triangular Matrices.
Consider the case of a partial order ≤ over any -element set . We enumerate as , and in such a way that the enumeration is compatible with the order ≤ on , that is, implies , which is always possible.
Then, functions as above, from intervals to scalars, can be thought of as matrices , where whenever , and otherwise"." Since we arranged in a way consistent with the usual order on the indices of the matrices, they will appear as upper-triangular matrices with a prescribed zero-pattern determined by the incomparable elements in under ≤.
The incidence algebra of ≤ is then isomorphic to the algebra of upper-triangular matrices with this prescribed zero-pattern and arbitrary (including possibly zero) scalar entries everywhere else, with the operations being ordinary matrix addition, scaling and multiplication.
Special elements.
The multiplicative identity element of the incidence algebra is the delta function, defined by
The zeta function of an incidence algebra is the constant function "ζ"("a", "b") = 1 for every nonempty interval ["a, b"]. Multiplying by "ζ" is analogous to integration.
One can show that ζ is invertible in the incidence algebra (with respect to the convolution defined above). (Generally, a member "h" of the incidence algebra is invertible if and only if "h"("x", "x") is invertible for every "x".) The multiplicative inverse of the zeta function is the Möbius function "μ"("a, b"); every value of "μ"("a, b") is an integral multiple of 1 in the base ring.
The Möbius function can also be defined inductively by the following relation:
Multiplying by "μ" is analogous to differentiation, and is called Möbius inversion.
The square of the zeta function counts the number of elements in an interval:
formula_4
Euler characteristic.
A poset is "bounded" if it has smallest and largest elements, which we call 0 and 1 respectively (not to be confused with the 0 and 1 of the ring of scalars). The Euler characteristic of a bounded finite poset is "μ"(0,1). The reason for this terminology is the following: If "P" has a 0 and 1, then "μ"(0,1) is the reduced Euler characteristic of the simplicial complex whose faces are chains in "P" \ {0, 1}. This can be shown using Philip Hall's theorem, relating the value of "μ"(0,1) to the number of chains of length i.
Reduced incidence algebras.
The reduced incidence algebra consists of functions which assign the same value to any two intervals which are equivalent in an appropriate sense, usually meaning isomorphic as posets. This is a subalgebra of the incidence algebra, and it clearly contains the incidence algebra's identity element and zeta function. Any element of the reduced incidence algebra that is invertible in the larger incidence algebra has its inverse in the reduced incidence algebra. Thus the Möbius function is also in the reduced incidence algebra.
Reduced incidence algebras were introduced by Doubillet, Rota, and Stanley to give a natural construction of various rings of generating functions.
Natural numbers and ordinary generating functions.
For the poset formula_17 the reduced incidence algebra consists of functions formula_18 invariant under translation, formula_19 for all formula_20 so as to have the same value on isomorphic intervals [a+k, b+k] and [a,b]. Let "t" denote the function with "t"(a, a+1) = 1 and "t"(a,b) = 0 otherwise, a kind of invariant delta function on isomorphism classes of intervals. Its powers in the incidence algebra are the other invariant delta functions "t"n(a, a+n) = 1 and "t"n(x,y) = 0 otherwise. These form a basis for the reduced incidence algebra, and we may write any invariant function as formula_21. This notation makes clear the isomorphism between the reduced incidence algebra and the ring of formal power series formula_22 over the scalars "R," also known as the ring of ordinary generating functions. We may write the zeta function as formula_23 the reciprocal of the Möbius function formula_24
Subset poset and exponential generating functions.
For the Boolean poset of finite subsets formula_25 ordered by inclusion formula_26, the reduced incidence algebra consists of invariant functions formula_27 defined to have the same value on isomorphic intervals [S,T] and [S',T'] with |T\S| = |T'\S'|. Again, let "t" denote the invariant delta function with "t"(S,T) = 1 for |T\S| = 1 and "t"(S,T) = 0 otherwise. Its powers are:formula_28 where the sum is over all chains formula_29 and the only non-zero terms occur for saturated chains with formula_30 since these correspond to permutations of n, we get the unique non-zero value n!. Thus, the invariant delta functions are the divided powers formula_31 and we may write any invariant function as formula_32 where [n] = {1, . . . , n}. This gives a natural isomorphism between the reduced incidence algebra and the ring of exponential generating functions. The zeta function is formula_33 with Möbius function: formula_34 Indeed, this computation with formal power series proves that formula_35 Many combinatorial counting sequences involving subsets or labeled objects can be interpreted in terms of the reduced incidence algebra, and computed using exponential generating functions.
Divisor poset and Dirichlet series.
Consider the poset "D" of positive integers ordered by divisibility, denoted formula_36 The reduced incidence algebra consists of functions formula_18 invariant under multiplication, formula_38 for all formula_39 (This multiplication equivalence of intervals is a much stronger relation than poset isomorphism: for prime p, the two-element intervals [1,p] are all inequivalent.) For an invariant function, "f"(a,b) depends only on b/a, so a natural basis consists of invariant delta functions formula_40 defined by formula_41 if b/a = n and 0 otherwise: any invariant function can be written formula_42
The product of two invariant delta functions is:
since the only non-zero term comes from c = na and b = mc = nma. Thus, we get an isomorphism from the reduced incidence algebra to the ring of formal Dirichlet series by sending formula_40 to formula_45 so that "f" corresponds to formula_46
The incidence algebra zeta function ζ"D"(a,b) = 1 corresponds to the classical Riemann zeta function formula_47 having reciprocal formula_48 where formula_49 is the classical Möbius function of number theory. Many other arithmetic functions arise naturally within the reduced incidence algebra, and equivalently in terms of Dirichlet series. For example, the divisor function formula_50 is the square of the zeta function, formula_51 a special case of the above result that formula_52 counts the number of elements in the interval [x,y]; equivalenty, formula_53
The product structure of the divisor poset facilitates the computation of its Möbius function. Unique factorization into primes implies "D" is isomorphic to an infinite Cartesian product formula_54, with the order given by coordinatewise comparison: formula_55, where formula_56 is the "k"th prime, corresponds to its sequence of exponents formula_57 Now the Möbius function of "D" is the product of the Möbius functions for the factor posets, computed above, giving the classical formula: 
The product structure also explains the classical Euler product for the zeta function. The zeta function of "D" corresponds to a Cartesian product of zeta functions of the factors, computed above as formula_59 so that formula_60 where the right side is a Cartesian product. Applying the isomorphism which sends "t" in the "k"th factor to formula_61, we obtain the usual Euler product.
Literature.
Incidence algebras of locally finite posets were treated in a number of papers of Gian-Carlo Rota beginning in 1964, and by many later combinatorialists. Rota's 1964 paper was: