Möbius inversion


Theorem 1 (Moebius Inversion).

Let μ be the Moebius function, and let f and g be two functions on the positive integers. Then the following two conditions are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath:

f(n) = d|ng(d) for all n* (1)
g(n) = d|nμ(d)f(nd) for all n* (2)

Proof: Fix some n*. Assuming (1), we have

d|nμ(d)f(nd) = d|nμ(d)e|n/dg(e)
= k|nd|kμ(d)g(nk)
= k|ng(nk)d|kμ(d)
= g(n),

the last step following from the identityPlanetmathPlanetmathPlanetmathPlanetmath given in the Mobius function entry.

Conversely, assuming (2), we get

d|ng(d) = d|ne|dμ(e)f(de)
= k|nf(nk)e|kμ(ke)
= f(n)  (by the same identity)

as claimed.

Definitions: In the notation above, f is called the Möbius transform of g, and formulaMathworldPlanetmathPlanetmath (2) is called the Möbius inversionPlanetmathPlanetmath formula.

Möbius-Rota inversion

G.-C. Rota has described a generalizationPlanetmathPlanetmath of the Möbius formalism. In it, the set *, ordered by the relationMathworldPlanetmathPlanetmathPlanetmath x|y between elements x and y, is replaced by a more general ordered set, and μ is replaced by a function of two variables.

Let (S,) be a locally finitePlanetmathPlanetmath ordered set, i.e. an ordered set such that {zS|xzy} is a finite setMathworldPlanetmath for all x,yS. Let A be the set of functions α:S×S such that

α(x,x) = 1 for all xS (3)
α(x,y) 0 implies xy (4)

A becomes a monoid if we define the productPlanetmathPlanetmathPlanetmath of any two of its elements, say α and β, by

(αβ)(x,y)=tSα(x,t)β(t,y).

The sum makes sense because α(x,t)β(t,y) is nonzero for only finitely many values of t. (Clearly this definition is akin to the definition of the product of two square matrices.)

Consider the element ι of A defined simply by

ι(x,y)={1 if xy0otherwise.

The function ι, regarded as a matrix over , has an inverse matrix, say ν. That means

tSι(x,t)ν(t,y)={1if x=y,0otherwise.

Thus for any f,gA, the equations

f = ιg (5)
g = νf (6)

are equivalent.

Now let’s sketch out how the traditional Möbius inversion is a special case of Rota’s notion. Let S be the set *, ordered by the relation x|y between elements x and y. In this case, ν is essentially a function of only one variable:

PropositionPlanetmathPlanetmath 3: With the above notation, ν(x,y)=μ(y/x) for all x,y* such that x|y.

The proof is fairly straightforward, by inductionMathworldPlanetmath on the number of elements of the interval {zS|xzy}.

Now let g be a function from * to some additive groupMathworldPlanetmath, and write g¯(x,y)=g(y/x) for all pairs (x,y) such that x|y.

Example: Let E be a set, and let S be the set of all finite subsets of E, ordered by inclusion. The ordered set S is left-finite, and for any x,yS such that xy, we have ν(x,y)=(-1)|y-x|, where |z| denotes the cardinal of the finite set z.

A slightly more sophisticated example comes up in connectionMathworldPlanetmathPlanetmath with the chromatic polynomial of a graph or matroidMathworldPlanetmath.

An Additional Generalization

A final generalization of Moebius inversion occurs when the sum is taken over all integers less than some real value x rather than over the divisorsMathworldPlanetmathPlanetmath of an integer. Specifically, let f: and define F: by F(x)=nxf(xn).

Then

f(x)=nxμ(n)F(xn).
Title Möbius inversion
Canonical name MobiusInversion
Date of creation 2013-03-22 11:46:58
Last modified on 2013-03-22 11:46:58
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 25
Author mathcam (2727)
Entry type Topic
Classification msc 11A25
Synonym Moebius inversion
Related topic MoebiusFunction
Defines Mobius inversion formula
Defines Mobius transform
Defines Mobius function
Defines Mobius-Rota inversion