Associative algebra used in combinatorics, a branch of mathematics
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
- a, b] = {x : a ≤ x ≤ b}
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
![{\displaystyle (f*g)(a,b)=\sum _{a~\leq ~x~\leq ~b}f(a,x)g(x,b).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1b9917c96a66355f7e127cddd53d26528659724)
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 n-element set S. We enumerate S as s1, …, sn, and in such a way that the enumeration is compatible with the order ≤ on S, that is, si ≤ sj implies i ≤ j, which is always possible.
Then, functions f as above, from intervals to scalars, can be thought of as
matrices Aij, where Aij = f(si, sj) whenever i ≤ j, and Aij = 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]
Special elements
The multiplicative identity element of the incidence algebra is the
delta function, defined by
![{\displaystyle \delta (a,b)={\begin{cases}1&{\text{if }}a=b,\\0&{\text{if }}a\neq b.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/283791c652e70afc2f6a0a85e79069520ad9f370)
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:
![{\displaystyle \mu (x,y)={\begin{cases}{}\qquad 1&{\text{if }}x=y\\[6pt]\displaystyle -\!\!\!\!\sum _{z\,:\,x\,\leq \,z\,<\,y}\mu (x,z)&{\text{for }}x<y\\{}\qquad 0&{\text{otherwise }}.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80e285bc91e06a1b64be51c1a4340d98a929f1d5)
Multiplying by μ is analogous to
differentiation, and is called
Möbius inversion.
The square of the zeta function gives the number of elements in an interval:
![{\displaystyle \zeta ^{2}(x,y)=\sum _{z\in [x,y]}\zeta (x,z)\,\zeta (z,y)=\sum _{z\in [x,y]}1=\#[x,y].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6048bdedc7d543740e1d6e86cd45bce385dce359)
Examples
- Positive integers ordered by divisibility
- The convolution associated to the incidence algebra for intervals [1, n] becomes the
Dirichlet convolution, hence the Möbius function is μ(a, b) = μ(b/a), where the second "μ" is the classical
Möbius function introduced into number theory in the 19th century.
- Finite subsets of some set E, ordered by inclusion
- The Möbius function is
![{\displaystyle \mu (S,T)=(-1)^{\left|T\smallsetminus S\right|}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2373d588fd24b33896bc9f2dbdef8ddf76de895d)
- whenever S and T are finite
subsets of E with S ⊆ T, and Möbius inversion is called the
principle of inclusion-exclusion.
- Geometrically, this is a
hypercube:
![{\displaystyle 2^{E}=\{0,1\}^{E}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8ffe5cb5e770a71f15ac9d1ac6b03d89cc1f908)
- Natural numbers with their usual order
- The Möbius function is
![{\displaystyle \mu (x,y)={\begin{cases}1&{\text{if }}y=x,\\-1&{\text{if }}y=x+1,\\0&{\text{if }}y>x+1,\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53c9c61f0a7451bce39435cada490f7b246814e5)
and Möbius inversion is called the (backwards)
difference operator.
- Geometrically, this corresponds to the discrete
number line.
- The convolution of functions in the incidence algebra corresponds to multiplication of
formal power series: see the discussion of reduced incidence algebras below. The Möbius function corresponds to the sequence (1, −1, 0, 0, 0, ... ) of coefficients of the formal power series 1 − t, and the zeta function corresponds to the sequence of coefficients (1, 1, 1, 1, ...) of the formal power series
, which is inverse. The delta function in this incidence algebra similarly corresponds to the formal power series 1.
- Finite sub-multisets of some multiset E, ordered by inclusion
- The above three examples can be unified and generalized by considering a
multiset E, and finite sub-multisets S and T of E. The Möbius function is
![{\displaystyle \mu (S,T)={\begin{cases}0&{\text{if }}T\smallsetminus S{\text{ is a proper multiset (has repeated elements)}}\\(-1)^{\left|T\smallsetminus S\right|}&{\text{if }}T\smallsetminus S{\text{ is a set (has no repeated elements)}}.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b318bdcf9e6f84a69fad220a7be4e9cec55e14bc)
- This generalizes the positive
integers ordered by
divisibility by a positive integer corresponding to its multiset of
prime
factors with multiplicity, e.g., 12 corresponds to the multiset
![{\displaystyle \{2,2,3\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a085d727129288e862c32619a87f8fc77141213)
- This generalizes the
natural numbers with their usual order by a natural number corresponding to a multiset of one underlying element and cardinality equal to that number, e.g., 3 corresponds to the multiset
![{\displaystyle \{1,1,1\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a781bb7986548a4229435aa0f00b7a18150ccdb)
- Subgroups of a finite
p-group G, ordered by inclusion
- The Möbius function is
![{\displaystyle \mu _{G}(H_{1},H_{2})=(-1)^{k}p^{\binom {k}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b027f9106e57aa3006847f5151cecd444c508899)
if
is a
normal subgroup of
and
and it is 0 otherwise. This is a theorem of Weisner (1935).
- Partitions of a set
- Partially order the set of all
partitions of a finite set by saying σ ≤ τ if σ is a finer partition than τ. In particular, let τ have t blocks which respectively split into s1, ..., st finer blocks of σ, which has a total of s = s1 + ⋅⋅⋅ + st blocks. Then the Möbius function is:
![{\displaystyle \mu (\sigma ,\tau )=(-1)^{s-t}(s_{1}{-}1)!\dots (s_{t}{-}1)!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6a02d8ed5fc0d4dacfcc6128719e48b63421659)
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.
[2]
Natural numbers and ordinary generating functions
For the poset
the reduced incidence algebra consists of functions
invariant under translation,
for all
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
. This notation makes clear the isomorphism between the reduced incidence algebra and the ring of formal power series
over the scalars R, also known as the ring of ordinary
generating functions. We may write the zeta function as
the reciprocal of the Möbius function
Subset poset and exponential generating functions
For the Boolean poset of finite subsets
ordered by inclusion
, the reduced incidence algebra consists of invariant functions
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\smallsetminus S|=n\\0&{\text{otherwise,}}\end{array}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68672d011e53b99c9070de6979a4471e3da89d7c)
where the sum is over all chains
![{\displaystyle S=T_{0}\subset T_{1}\subset \cdots \subset T_{n}=T,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90df485c1649e6865e6e22e3677debb917520258)
and the only non-zero terms occur for saturated chains with
![{\displaystyle |T_{i}\smallsetminus T_{i-1}|=1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e31001bbd78fdd30e204f1feba51301c07818ea5)
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!}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b9866378d0ba41ed51b7be282e03310feeb5cd7)
and we may write any invariant function as
![{\displaystyle \textstyle f=\sum _{n\geq 0}f(\emptyset ,[n]){\frac {t^{n}}{n!}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/872c9dbaebf260e05ba9707b26addc6e53c44151)
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),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b2b634cdce5cc2a9b462eaae7e45ff193425fb4)
with Möbius function:
![{\displaystyle \mu ={\frac {1}{\zeta }}=\exp(-t)=\sum _{n\geq 0}(-1)^{n}{\frac {t^{n}}{n!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a36ea0f4b957fdbec91a93543b15ae33539bdbbb)
Indeed, this computation with formal power series proves that
![{\displaystyle \mu (S,T)=(-1)^{|T\smallsetminus S|}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13cddda0281bac09ce103c70055c557548a80b31)
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 by
The reduced incidence algebra consists of functions
that are invariant under multiplication:
for all
(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
defined by
if b/a = n and 0 otherwise; then any invariant function can be written
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),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e3083d8e13b7dcbca3302e17ff57397d6e03652)
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
to
so that f corresponds to
The incidence algebra zeta function ζD(a,b) = 1 corresponds to the classical
Riemann zeta function
having reciprocal
where
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
is the square of the zeta function,
a special case of the above result that
gives the number of elements in the interval [x,y]; equivalenty,
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
, with the order given by coordinatewise comparison:
, where
is the kth prime, corresponds to its sequence of exponents
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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/942033a8743dec1bbdc13c3169710eb26195de89)
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
so that
where the right side is a Cartesian product. Applying the isomorphism which sends t in the kth factor to
, we obtain the usual Euler product.
See also
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:
- Rota, Gian-Carlo (1964), "On the Foundations of Combinatorial Theory I: Theory of Möbius Functions", Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 2 (4): 340–368,
doi:
10.1007/BF00531932,
S2CID
121334025
-
N. Jacobson, Basic Algebra. I, W. H. Freeman and Co., 1974. See section 8.6 for a treatment of Mobius functions on posets
Further reading