generalized Möbius function
   HOME

TheInfoList



OR:

In
order theory Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
, a field of
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an incidence algebra is an
associative algebra In mathematics, an associative algebra ''A'' is an algebraic structure with compatible operations of addition, multiplication (assumed to be associative), and a scalar multiplication by elements in some field ''K''. The addition and multiplic ...
, defined for every
locally finite partially ordered set In mathematics, a locally finite poset is a partially ordered set ''P'' such that for all ''x'', ''y'' ∈ ''P'', the interval 'x'', ''y''consists of finitely many elements. Given a locally finite poset ''P'' we can defin ...
and
commutative ring In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not sp ...
with unity. Subalgebras called reduced incidence algebras give a natural construction of various types of generating functions used in
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
and
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
.


Definition

A locally finite poset is one in which every closed interval : 'a, b''= is finite. The members of the incidence algebra are the functions ''f'' assigning to each
nonempty In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other t ...
interval 'a, b''a scalar ''f''(''a'', ''b''), which is taken from the ''
ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...
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 In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions ( and ) that produces a third function (f*g) that expresses how the shape of one is ...
defined by :(f*g)(a, b)=\sum_f(a, x)g(x, b). An incidence algebra is finite-dimensional
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
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 In category theory, a field of mathematics, a category algebra is an associative algebra, defined for any locally finite category and commutative ring with unity. Category algebras generalize the notions of group algebras and incidence algebras ...
, defined analogously;
groups A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...
and posets being special kinds of
categories Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally *Category of being *Categories (Aristotle), ''Categories'' (Aristotle) *Category (Kant) ...
.


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 In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
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 Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
.


Special elements

The multiplicative identity element of the incidence algebra is the delta function, defined by :\delta(a, b) = \begin 1 & \text a=b, \\ 0 & \text a \ne b. \end 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 Integration may refer to: Biology *Multisensory integration *Path integration * Pre-integration complex, viral genetic material used to insert a viral genome into a host genome *DNA integration, by means of site-specific recombinase technology, ...
. 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: :\mu(x,y) = \begin \qquad 1 & \text x = y\\ pt\displaystyle -\!\!\!\!\sum_ \mu(x,z) & \text x Multiplying by ''μ'' is analogous to differentiation, and is called
Möbius inversion Moebius, Möbius or Mobius may refer to: People * August Ferdinand Möbius (1790–1868), German mathematician and astronomer * Theodor Möbius (1821–1890), German philologist * Karl Möbius (1825–1908), German zoologist and ecologist * Paul ...
. The square of the zeta function counts the number of elements in an interval: \zeta^2(x,y) = \sum_ \zeta(x,z)\,\zeta(z,y) = \sum_ 1 = \# ,y


Examples

;Positive integers ordered by divisibility :The convolution associated to the incidence algebra for intervals
, ''n'' The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
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 \mu(S,T)=(-1)^ :whenever ''S'' and ''T'' are finite
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s of ''E'' with ''S'' ⊆ ''T'', and Möbius inversion is called the
principle of inclusion-exclusion A principle is a proposition or value that is a guide for behavior or evaluation. In law, it is a rule that has to be or usually is to be followed. It can be desirably followed, or it can be an inevitable consequence of something, such as the law ...
. :Geometrically, this is a
hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, ...
: 2^E = \^E. ;Natural numbers with their usual order :The Möbius function is \mu(x,y) = \begin 1& \texty=x, \\ -1 & \texty = x+1, \\ 0 & \texty>x+1, \end 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 In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial sum ...
: 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 (1 - t)^ = 1 + t + t^2 + t^3 + \cdots, 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 \mu(S,T) = \begin 0 & \text T \setminus S \text\\ (-1)^ & \text T\setminus S \text. \end :This generalizes the positive
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s ordered by divisibility by a positive integer corresponding to its multiset of
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
factors Factor, a Latin word meaning "who/which acts", may refer to: Commerce * Factor (agent), a person who acts for, notably a mercantile and colonial agent * Factor (Scotland), a person or firm managing a Scottish estate * Factors of production, suc ...
with multiplicity, e.g., 12 corresponds to the multiset \. :This generalizes the
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
s 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 \mu_G(H_1,H_2) = (-1)^ p^ if H_1 is a
normal subgroup In abstract algebra, a normal subgroup (also known as an invariant subgroup or self-conjugate subgroup) is a subgroup that is invariant under conjugation by members of the group of which it is a part. In other words, a subgroup N of the group G i ...
of H_2 and H_2/H_1 \cong (\Z/p\Z)^k and it is 0 otherwise. This is a theorem of Weisner (1935). ;Partitions of a set :Partially order the set of all
partitions Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...
of a finite set by saying σ ≤ Ï„ if σ is a finer partition than Ï„. In particular, let Ï„ have ''t'' blocks which respectively split into ''s''1, ..., ''s''''t'' finer blocks of σ, which has a total of ''s'' = ''s''1 + ··· + ''s''''t'' blocks. Then the Möbius function is: \mu(\sigma,\tau) = (-1)^(s_11)! \dots (s_t1)!


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 In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space ...
of the
simplicial complex In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their ''n''-dimensional counterparts (see illustration). Simplicial complexes should not be confused with the more abstract notion of a simplicial set ...
whose faces are chains in ''P'' \ . 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 In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
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 function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
s.Peter Doubilet, Gian-Carlo Rota and Richard Stanley: ''On the Foundations of Combinatorics (IV): The Idea of Generating Function'', Berkeley Symp. on Math. Statist. and Prob. Proc. Sixth Berkeley Symp. on Math. Statist. and Prob., Vol. 2 (Univ. of Calif. Press, 1972), 267-318
available online in open access
/ref>


Natural numbers and ordinary generating functions

For the poset (\mathbb,\leq), the reduced incidence algebra consists of functions f(a,b) invariant under translation, f(a+k,b+k) = f(a,b) for all k \ge 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'' ''n''(''a'', ''a''+''n'') = 1 and ''t'' ''n''(''x'', ''y'') = 0 otherwise. These form a
basis Basis may refer to: Finance and accounting *Adjusted basis, the net cost of an asset after adjusting for various tax-related items *Basis point, 0.01%, often used in the context of interest rates *Basis trading, a trading strategy consisting of ...
for the reduced incidence algebra, and we may write any invariant function as \textstyle f = \sum_ f(0,n)t^n. This notation makes clear the isomorphism between the reduced incidence algebra and the ring of formal power series R t over the scalars ''R,'' also known as the ring of ordinary
generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
s. We may write the zeta function as \zeta=1+t+t^2+\cdots = \tfrac1, the reciprocal of the Möbius function \mu=1-t.


Subset poset and exponential generating functions

For the Boolean poset of finite subsets S\subset\ ordered by inclusion S\subset T, the reduced incidence algebra consists of invariant functions 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: t^n(S,T) =\, \sum t(T_0,T_1)\,t(T_1,T_2) \dots t(T_,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 S = T_0\subset T_1\subset\cdots\subset T_n=T, and the only non-zero terms occur for saturated chains with , 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 \tfrac{t^n}{n!}, and we may write any invariant function as \textstyle f = \sum_{n\geq0} f(\emptyset, \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 \textstyle \zeta = \sum_{n\geq 0}\frac{t^n}{n!} = \exp(t), with Möbius function: \mu = \frac1{\zeta} = \exp(-t) = \sum_{n\geq 0} (-1)^n \frac{t^n}{n!}. Indeed, this computation with formal power series proves that \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.


Divisor poset and Dirichlet series

Consider the poset ''D'' of positive integers ordered by divisibility, denoted a\,, \,b. The reduced incidence algebra consists of functions f(a,b) invariant under multiplication, f(ka,kb) = f(a,b) for all k\ge 1. (This multiplication equivalence of intervals is a much stronger relation than poset isomorphism: for prime ''p'', the two-element intervals ,''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 \delta_n defined by \delta_n(a,b) = 1 if ''b''/''a'' = ''n'' and 0 otherwise: any invariant function can be written \textstyle f = \sum_{n\geq 0} f(1,n)\, \delta_n. The product of two invariant delta functions is: :(\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 \delta_n to n^{-s}\!, so that ''f'' corresponds to \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 The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
\zeta(s)=\textstyle \sum_{n\geq 1}\frac{1}{n^s}, having reciprocal \frac{1}{\zeta(s)} = \sum_{n\geq 1}\frac{\mu(n)}{n^s}, where \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 \sigma_0(n) is the square of the zeta function, \sigma_0(n) = \zeta^2\!(1,n), a special case of the above result that \zeta^2\!(x,y) counts the number of elements in the interval 'x'',''y'' equivalenty, \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 \N\times\N \times \dots, with the order given by coordinatewise comparison: n = p_1^{e_1}p_2^{e_2}\dots, where p_k is the ''k''th prime, corresponds to its sequence of exponents (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: :\mu(n) = \mu_D(1,n) = \prod_{k\geq 1}\mu_{\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 \frac{1}{1-t}, so that \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 p_k^{-s}, we obtain the usual Euler product.


See also

*
Graph algebra In mathematics, especially in the fields of universal algebra and graph theory, a graph algebra is a way of giving a directed graph an algebraic structure. It was introduced by McNulty and Shallon, and has seen many uses in the field of universa ...
*
Incidence coalgebra In mathematics, coalgebras or cogebras are structures that are dual (in the category-theoretic sense of reversing arrows) to unital associative algebras. The axioms of unital associative algebras can be formulated in terms of commutative diagrams. ...
*
Path algebra In graph theory, a quiver is a directed graph where loops and multiple arrows between two vertices are allowed, i.e. a multidigraph. They are commonly used in representation theory: a representation  of a quiver assigns a vector space  ...


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: * * 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

* {{DEFAULTSORT:Incidence Algebra Algebraic combinatorics Order theory