Jump to content

Möbius inversion formula: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
m Wrap interval notation in nowiki tags to prevent problem detection by the Wiki Syntax Project.
mNo edit summary
Line 3: Line 3:


The classic '''Möbius inversion formula''' was introduced into [[number theory]] during the 19th century by [[August Ferdinand Möbius]]. It was later generalized to other "Möbius inversion formulas"; see [[incidence algebra]]. The classic version states that if ''g''(''n'') and ''f''(''n'') are [[arithmetic function]]s satisfying
The classic '''Möbius inversion formula''' was introduced into [[number theory]] during the 19th century by [[August Ferdinand Möbius]]. It was later generalized to other "Möbius inversion formulas"; see [[incidence algebra]]. The classic version states that if ''g''(''n'') and ''f''(''n'') are [[arithmetic function]]s satisfying

: <math>g(n)=\sum_{d\mid n}f(d)\quad\mbox{for every integer }n\ge 1</math>
: <math>g(n)=\sum_{d\,\mid \,n}f(d)\quad\mbox{for every integer }n\ge 1</math>

then
then

:<math>f(n)=\sum_{d\mid n}g(d)\mu(n/d)\quad\mbox{for every integer }n\ge 1</math>
:<math>f(n)=\sum_{d\,\mid\, n}g(d)\mu(n/d)\quad\mbox{for every integer }n\ge 1</math>

where &mu; is the [[Möbius function]] and the sums extend over all positive [[divisor]]s ''d'' of ''n''.
where &mu; is the [[Möbius function]] and the sums extend over all positive [[divisor]]s ''d'' of ''n''.


Line 11: Line 15:


In the language of convolutions (see [[multiplicative function]]), the inversion formula can also be expressed as
In the language of convolutions (see [[multiplicative function]]), the inversion formula can also be expressed as

:&mu; * 1 = &epsilon;.
:&mu; * 1 = &epsilon;.

An equivalent formulation of the inversion formula more useful in [[combinatorics]] is as follows: suppose ''F''(''x'') and ''G''(''x'') are [[complex number|complex]]-valued [[function (mathematics)|function]]s defined on the [[interval (mathematics)|interval]] <nowiki>[1,&infin;)</nowiki> such that
An equivalent formulation of the inversion formula more useful in [[combinatorics]] is as follows: suppose ''F''(''x'') and ''G''(''x'') are [[complex number|complex]]-valued [[function (mathematics)|function]]s defined on the [[interval (mathematics)|interval]] <nowiki>[1,&infin;)</nowiki> such that

: <math>G(x) = \sum_{1 \le n \le x}F(x/n)\quad\mbox{ for all }x\ge 1</math>
: <math>G(x) = \sum_{1 \le n \le x}F(x/n)\quad\mbox{ for all }x\ge 1</math>

then
then

: <math>F(x) = \sum_{1 \le n \le x}\mu(n)G(x/n)\quad\mbox{ for all }x\ge 1.</math>
: <math>F(x) = \sum_{1 \le n \le x}\mu(n)G(x/n)\quad\mbox{ for all }x\ge 1.</math>


Line 21: Line 30:
The Möbius inversion treated above is the ''original'' Möbius inversion. When the [[partially ordered set]] of natural numbers ordered by divisibility one is replaced by other locally finite partially ordered sets, one has other Möbius inversion formulas; for an account of those, see [[incidence algebra]].
The Möbius inversion treated above is the ''original'' Möbius inversion. When the [[partially ordered set]] of natural numbers ordered by divisibility one is replaced by other locally finite partially ordered sets, one has other Möbius inversion formulas; for an account of those, see [[incidence algebra]].


See also: [[August Ferdinand Möbius]].
See also [[August Ferdinand Möbius]].


[[es:Fórmula de inversión de Möbius]]
[[es:Fórmula de inversión de Möbius]]

Revision as of 01:00, 16 January 2005


The classic Möbius inversion formula was introduced into number theory during the 19th century by August Ferdinand Möbius. It was later generalized to other "Möbius inversion formulas"; see incidence algebra. The classic version states that if g(n) and f(n) are arithmetic functions satisfying

then

where μ is the Möbius function and the sums extend over all positive divisors d of n.

The formula is also correct if f and g are functions from the positive integers into some abelian group.

In the language of convolutions (see multiplicative function), the inversion formula can also be expressed as

μ * 1 = ε.

An equivalent formulation of the inversion formula more useful in combinatorics is as follows: suppose F(x) and G(x) are complex-valued functions 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.

The Möbius inversion treated above is the original Möbius inversion. When the partially ordered set of natural numbers ordered by divisibility one is replaced by other locally finite partially ordered sets, one has other Möbius inversion formulas; for an account of those, see incidence algebra.

See also August Ferdinand Möbius.