Incidence algebra

Last updated

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.

Contents

Definition

A locally finite poset is one in which every closed interval

[a, b] = {x : axb}

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.

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, sisj implies ij, 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 ij, 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

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 gives the number of elements in an interval:

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
whenever S and T are finite subsets of E with ST, and Möbius inversion is called the principle of inclusion-exclusion.
Geometrically, this is a hypercube:
Natural numbers with their usual order
The Möbius function is
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
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
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
Subgroups of a finite p-group G, ordered by inclusion
The Möbius function is
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:

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 tn(a, a+n) = 1 and tn(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:

where the sum is over all chains and the only non-zero terms occur for saturated chains with since these correspond to permutations of n, we get the unique non-zero value n!. Thus, the invariant delta functions are the divided powers and we may write any invariant function as 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 with Möbius function:

Indeed, this computation with formal power series proves that 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:

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:

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:

  1. Kolegov, N. A.; Markova, O. V. (August 2019). "Systems of Generators of Matrix Incidence Algebras over Finite Fields". Journal of Mathematical Sciences. 240 (6): 783–798. doi:10.1007/s10958-019-04396-6. ISSN   1072-3374. S2CID   198443199.
  2. Peter Doubilet, Gian-Carlo Rota and Richard Stanley: On the Foundations of Combinatorics (VI): The Idea of Generating Function, Berkeley Symposium on Math. Statist. and Prob., Proc. Sixth Berkeley Symposium on Math. Statist. and Prob., Vol. 2 (Univ. of Calif. Press, 1972), 267-318, available online in open access

Further reading

Related Research Articles

<span class="mw-page-title-main">Lorentz transformation</span> Family of linear transformations

In physics, the Lorentz transformations are a six-parameter family of linear transformations from a coordinate frame in spacetime to another frame that moves at a constant velocity relative to the former. The respective inverse transformation is then parameterized by the negative of this velocity. The transformations are named after the Dutch physicist Hendrik Lorentz.

<span class="mw-page-title-main">Measure (mathematics)</span> Generalization of mass, length, area and volume

In mathematics, the concept of a measure is a generalization and formalization of geometrical measures and other common notions, such as magnitude, mass, and probability of events. These seemingly distinct concepts have many similarities and can often be treated together in a single mathematical context. Measures are foundational in probability theory, integration theory, and can be generalized to assume negative values, as with electrical charge. Far-reaching generalizations of measure are widely used in quantum physics and physics in general.

In number theory, a multiplicative function is an arithmetic function f(n) of a positive integer n with the property that f(1) = 1 and

The Möbius function μ(n) is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated Moebius) in 1832. It is ubiquitous in elementary and analytic number theory and most often appears as part of its namesake the Möbius inversion formula. Following work of Gian-Carlo Rota in the 1960s, generalizations of the Möbius function were introduced into combinatorics, and are similarly denoted μ(x).

In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. It was introduced into number theory in 1832 by August Ferdinand Möbius.

In mathematics, fuzzy sets are sets whose elements have degrees of membership. Fuzzy sets were introduced independently by Lotfi A. Zadeh in 1965 as an extension of the classical notion of set. At the same time, Salii (1965) defined a more general kind of structure called an L-relation, which he studied in an abstract algebraic context. Fuzzy relations, which are now used throughout fuzzy mathematics and have applications in areas such as linguistics, decision-making, and clustering, are special cases of L-relations when L is the unit interval [0, 1].

In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is important in number theory. It was developed by Peter Gustav Lejeune Dirichlet.

<span class="mw-page-title-main">Symmetric difference</span> Elements in exactly one of two sets

In mathematics, the symmetric difference of two sets, also known as the disjunctive union and set sum, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets and is .

In mathematics, a Dirichlet series is any series of the form

<span class="mw-page-title-main">Mertens function</span> Summatory function of the Möbius function

In number theory, the Mertens function is defined for all positive integers n as

In mathematics, subgroup growth is a branch of group theory, dealing with quantitative questions about subgroups of a given group.

In mathematics, the Gauss–Kuzmin–Wirsing operator is the transfer operator of the Gauss map that takes a positive number to the fractional part of its reciprocal. It is named after Carl Gauss, Rodion Kuzmin, and Eduard Wirsing. It occurs in the study of continued fractions; it is also related to the Riemann zeta function.

In mathematics, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. It is an example of an important arithmetic function that is neither multiplicative nor additive.

In mathematics, holomorphic functional calculus is functional calculus with holomorphic functions. That is to say, given a holomorphic function f of a complex argument z and an operator T, the aim is to construct an operator, f(T), which naturally extends the function f from complex argument to operator argument. More precisely, the functional calculus defines a continuous algebra homomorphism from the holomorphic functions on a neighbourhood of the spectrum of T to the bounded operators.

In probability theory, a random measure is a measure-valued random element. Random measures are for example used in the theory of random processes, where they form many important point processes such as Poisson point processes and Cox processes.

In number theory, an average order of an arithmetic function is some simpler or better-understood function which takes the same values "on average".

<span class="mw-page-title-main">Voter model</span>

In the mathematical theory of probability, the voter model is an interacting particle system introduced by Richard A. Holley and Thomas M. Liggett in 1975.

In mathematics, topological recursion is a recursive definition of invariants of spectral curves. It has applications in enumerative geometry, random matrix theory, mathematical physics, string theory, knot theory.

In number theory, the prime omega functions and count the number of prime factors of a natural number Thereby counts each distinct prime factor, whereas the related function counts the total number of prime factors of honoring their multiplicity. That is, if we have a prime factorization of of the form for distinct primes , then the respective prime omega functions are given by and . These prime factor counting functions have many important number theoretic relations.

Tau functions are an important ingredient in the modern mathematical theory of integrable systems, and have numerous applications in a variety of other domains. They were originally introduced by Ryogo Hirota in his direct method approach to soliton equations, based on expressing them in an equivalent bilinear form.