Möbius inversion formula
Encyclopedia
In mathematics
, the classic Möbius inversion formula was introduced into number theory
during the 19th century by August Ferdinand Möbius
.
Other Möbius inversion formulas are obtained when different local finite partially ordered set
s replace the classic case of the natural numbers ordered by divisibility; for an account of those, see incidence algebra
.
s satisfying
then
where μ is the Möbius function
and the sums extend over all positive divisor
s d of n. In effect, the original f(n) can be determined given g(n) by using the inversion formula. The two sequences are said to be Möbius transforms of each other.
The formula is also correct if f and g are functions from the positive integers into some abelian group
(viewed as a Z-module
).
In the language of Dirichlet convolution
s , the first formula may be written as
where * denotes the Dirichlet convolution, and 1 is the constant function
. The second formula is then written as
Many specific examples are given in the article on multiplicative function
s.
For example, if one starts with Euler's totient function
, and repeatedly applies the transformation process, one obtains:
If the starting function is the Möbius function itself, the list of functions is:
Both of these lists of functions extend infinitely in both directions. The Möbius inversion formula enables these lists to be traversed backwards. The generated sequences can perhaps be more easily understood by considering the corresponding Dirichlet series: each repeated application of the transform corresponds to multiplication by the Riemann zeta function.
is as follows: suppose F(x) and G(x) are complex
-valued function
s defined on the interval
[1,∞) such that
then
Here the sums extend over all positive integers n which are less than or equal to x.
This in turn is a special case of a more general form. If
is an arithmetic function
possessing a Dirichlet inverse
, then if one defines
then
The previous formula arises in the special case of the constant function
, whose Dirichlet inverse is 
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the classic Möbius inversion formula was introduced into number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
during the 19th century by August Ferdinand Möbius
August Ferdinand Möbius
August Ferdinand Möbius was a German mathematician and theoretical astronomer.He is best known for his discovery of the Möbius strip, a non-orientable two-dimensional surface with only one side when embedded in three-dimensional Euclidean space. It was independently discovered by Johann Benedict...
.
Other Möbius inversion formulas are obtained when different local finite partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
s replace the classic case of the natural numbers ordered by divisibility; for an account of those, see incidence algebra
Incidence algebra
In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for any locally finite partially ordered setand commutative ring with unity.-Definition:...
.
Statement of the formula
The classic version states that if g(n) and f(n) are arithmetic functionArithmetic function
In number theory, an arithmetic function is a real or complex valued function ƒ defined on the set of natural numbers In number theory, an arithmetic (or arithmetical) function is a real or complex valued function ƒ(n) defined on the set of natural numbers In number theory, an arithmetic (or...
s satisfying
then
where μ is the Möbius function
Möbius function
The classical Möbius function μ is an important multiplicative function in number theory and combinatorics. The German mathematician August Ferdinand Möbius introduced it in 1832...
and the sums extend over all positive divisor
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
s d of n. In effect, the original f(n) can be determined given g(n) by using the inversion formula. The two sequences are said to be Möbius transforms of each other.
The formula is also correct if f and g are functions from the positive integers into some abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
(viewed as a Z-module
Module (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
).
In the language of Dirichlet convolution
Dirichlet convolution
In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is important in number theory. It was developed by Johann Peter Gustav Lejeune Dirichlet, a German mathematician.-Definition:...
s , the first formula may be written as
where * denotes the Dirichlet convolution, and 1 is the constant function
Constant function
In mathematics, a constant function is a function whose values do not vary and thus are constant. For example the function f = 4 is constant since f maps any value to 4...
. The second formula is then written asMany specific examples are given in the article on multiplicative function
Multiplicative function
In number theory, a multiplicative function is an arithmetic function f of the positive integer n with the property that f = 1 and whenevera and b are coprime, then...
s.
Repeated transformations
Given an arithmetic function, one can generate a bi-infinite sequence of other arithmetic functions by repeatedly applying the first summation.For example, if one starts with Euler's totient function
Euler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...
, and repeatedly applies the transformation process, one obtains:
the totient function
where 
is the identity functionIdentity functionIn mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...
, the divisor functionDivisor functionIn mathematics, and specifically in number theory, a divisor function is an arithmetical function related to the divisors of an integer. When referred to as the divisor function, it counts the number of divisors of an integer. It appears in a number of remarkable identities, including relationships...
If the starting function is the Möbius function itself, the list of functions is:
, the Möbius function
where 
is the unit function
, the constant functionConstant functionIn mathematics, a constant function is a function whose values do not vary and thus are constant. For example the function f = 4 is constant since f maps any value to 4...
, where 
is the number of divisors of n, (see divisor functionDivisor functionIn mathematics, and specifically in number theory, a divisor function is an arithmetical function related to the divisors of an integer. When referred to as the divisor function, it counts the number of divisors of an integer. It appears in a number of remarkable identities, including relationships...
).
Both of these lists of functions extend infinitely in both directions. The Möbius inversion formula enables these lists to be traversed backwards. The generated sequences can perhaps be more easily understood by considering the corresponding Dirichlet series: each repeated application of the transform corresponds to multiplication by the Riemann zeta function.
Generalizations
An equivalent formulation of the inversion formula more useful in combinatoricsCombinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
is as follows: suppose F(x) and G(x) are complex
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
-valued function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
s defined on the interval
Interval (mathematics)
In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...
then
Here the sums extend over all positive integers n which are less than or equal to x.
This in turn is a special case of a more general form. If
is an arithmetic functionArithmetic function
In number theory, an arithmetic function is a real or complex valued function ƒ defined on the set of natural numbers In number theory, an arithmetic (or arithmetical) function is a real or complex valued function ƒ(n) defined on the set of natural numbers In number theory, an arithmetic (or...
possessing a Dirichlet inverse
, then if one definesthen
The previous formula arises in the special case of the constant function
, whose Dirichlet inverse is .