Incidence algebra

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.

Consider the case of a partial order ≤ over any n-element set S. We enumerate S as s₁, …, s_n, and in such a way that the enumeration is compatible with the order ≤ on S, that is, s_i ≤ s_j implies i ≤ j, which is always possible.

Then, functions f as above, from intervals to scalars, can be thought of as matrices A_ij, where A_ij = f(s_i, s_j) whenever i ≤ j, and A_ij = 0 otherwise. Since we arranged S 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 S 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.[1]

For the poset ${\displaystyle (\mathbb {N} ,\leq ),}$ the reduced incidence algebra consists of functions ${\displaystyle f(a,b)}$ invariant under translation, ${\displaystyle f(a+k,b+k)=f(a,b)}$ for all ${\displaystyle k\geq 0,}$ 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ⁿ(a, a+n) = 1 and tⁿ(x, y) = 0 otherwise. These form a basis for the reduced incidence algebra, and we may write any invariant function as ${\displaystyle \textstyle f=\sum _{n\geq 0}f(0,n)t^{n}}$. This notation makes clear the isomorphism between the reduced incidence algebra and the ring of formal power series ${\displaystyle R[[t]]}$ over the scalars R, also known as the ring of ordinary generating functions. We may write the zeta function as ${\displaystyle \zeta =1+t+t^{2}+\cdots ={\tfrac {1}{1-t}},}$ the reciprocal of the Möbius function ${\displaystyle \mu =1-t.}$

For the Boolean poset of finite subsets ${\displaystyle S\subset \{1,2,3,\ldots \}}$ ordered by inclusion ${\displaystyle S\subset T}$, the reduced incidence algebra consists of invariant functions ${\displaystyle f(S,T),}$ 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:

$${\displaystyle t^{n}(S,T)=\,\sum t(T_{0},T_{1})\,t(T_{1},T_{2})\dots t(T_{n-1},T_{n})=\left\{{\begin{array}{cl}n!&{\text{if}}\,\,|T{\setminus }S|=n\\0&{\text{otherwise,}}\end{array}}\right.}$$

where the sum is over all chains ${\displaystyle S=T_{0}\subset T_{1}\subset \cdots \subset T_{n}=T,}$ and the only non-zero terms occur for saturated chains with ${\displaystyle |T_{i}{\setminus }T_{i-1}|=1;}$ since these correspond to permutations of n, we get the unique non-zero value n!. Thus, the invariant delta functions are the divided powers ${\displaystyle {\tfrac {t^{n}}{n!}},}$ and we may write any invariant function as ${\displaystyle \textstyle f=\sum _{n\geq 0}f(\emptyset ,[n]){\frac {t^{n}}{n!}},}$ 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 ${\displaystyle \textstyle \zeta =\sum _{n\geq 0}{\frac {t^{n}}{n!}}=\exp(t),}$ with Möbius function:

$${\displaystyle \mu ={\frac {1}{\zeta }}=\exp(-t)=\sum _{n\geq 0}(-1)^{n}{\frac {t^{n}}{n!}}.}$$

Indeed, this computation with formal power series proves that ${\displaystyle \mu (S,T)=(-1)^{|T{\setminus }S|}.}$ 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.

Consider the poset D of positive integers ordered by divisibility, denoted by ${\displaystyle a\,|\,b.}$ The reduced incidence algebra consists of functions ${\displaystyle f(a,b)}$ that are invariant under multiplication: ${\displaystyle f(ka,kb)=f(a,b)}$ for all ${\displaystyle k\geq 1.}$ (This multiplicative equivalence of intervals is a much stronger relation than poset isomorphism; e.g., for primes 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 ${\displaystyle \delta _{n}}$ defined by ${\displaystyle \delta _{n}(a,b)=1}$ if b/a = n and 0 otherwise; then any invariant function can be written ${\displaystyle \textstyle f=\sum _{n\geq 0}f(1,n)\,\delta _{n}.}$

The product of two invariant delta functions is:

${\displaystyle (\delta _{n}\delta _{m})(a,b)=\sum _{a|c|b}\delta _{n}(a,c)\,\delta _{m}(c,b)=\delta _{nm}(a,b),}$

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 ${\displaystyle \delta _{n}}$ to ${\displaystyle n^{-s}\!,}$ so that f corresponds to ${\textstyle \sum _{n\geq 1}{\frac {f(1,n)}{n^{s}}}.}$

The incidence algebra zeta function ζ_D(a,b) = 1 corresponds to the classical Riemann zeta function ${\displaystyle \zeta (s)=\textstyle \sum _{n\geq 1}{\frac {1}{n^{s}}},}$ having reciprocal ${\textstyle {\frac {1}{\zeta (s)}}=\sum _{n\geq 1}{\frac {\mu (n)}{n^{s}}},}$ where ${\displaystyle \mu (n)=\mu _{D}(1,n)}$ 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 ${\displaystyle \sigma _{0}(n)}$ is the square of the zeta function, ${\displaystyle \sigma _{0}(n)=\zeta ^{2}\!(1,n),}$ a special case of the above result that ${\displaystyle \zeta ^{2}\!(x,y)}$ gives the number of elements in the interval [x,y]; equivalenty, ${\textstyle \zeta (s)^{2}=\sum _{n\geq 1}{\frac {\sigma _{0}(n)}{n^{s}}}.}$

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 ${\displaystyle \mathbb {N} \times \mathbb {N} \times \dots }$, with the order given by coordinatewise comparison: ${\displaystyle n=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots }$, where ${\displaystyle p_{k}}$ is the k^th prime, corresponds to its sequence of exponents ${\displaystyle (e_{1},e_{2},\dots ).}$ 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:

${\displaystyle \mu (n)=\mu _{D}(1,n)=\prod _{k\geq 1}\mu _{\mathbb {N} }(0,e_{k})\,=\,\left\{{\begin{array}{cl}(-1)^{d}&{\text{for }}n{\text{ squarefree with }}d{\text{ prime factors}}\\0&{\text{otherwise.}}\end{array}}\right.}$

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 ${\textstyle {\frac {1}{1-t}},}$ so that ${\textstyle \zeta _{D}\cong \prod _{k\geq 1}\!{\frac {1}{1-t}},}$ where the right side is a Cartesian product. Applying the isomorphism which sends t in the k^th factor to ${\displaystyle p_{k}^{-s}}$, we obtain the usual Euler product.