|
The Möbius function is denoted μ(n), and defined as follows:
Definition
μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
μ(n) = 0 if n is not square-free.
Square-free means not divisible by any square larger than 1. The
prime factors of square-free numbers are distinct.
Sum for all d|n of μ(d) is 0, when n>1
Proof by multiplicative induction: Consider only the square-free
divisors of n, because μ(d)=0 when d has a square factor. It is true
when n is prime, because μ(p)=-1, and u(1)=1; their sum is zero.
Suppose Sn=0 for n=m. We will show that Sn=0 for
n=mp, where p is an arbitrary prime.
If p|m then the square-free divisors of mp are the same as the square-free
divisors of m, so Smp = Sm = 0.
If p m
then the set of square-free divisors of mp consists of all the square-free
divisors of m together with each divisor multiplied by p. So,
Remembering that GCD(m,p)=1, it follows from d|m that GCD(d,p)=1, and
therefore μ(pd) = −μ(d). So the sum, above, is adding up a
whole bunch of zeros, so Smp=0.
Möbius Inversion Formula
If F(n) is an arithmetical function of n, and if
then
and vice-versa.
Remarks
Before I begin the proof, I would like to make a few remarks about nested
sums involving factors of n. Understanding this will be key to
understanding the proof that follows.
Consider all the possibilities for x and y, where x and y are selected
according to the following method:
x is chosen to be a factor of n. For example, if n=12, x will be one
of {1,2,3,4,6,12}.
Then, after x is chosen, y is chosen to be a factor of "whatever is
left over", namely n/x. To take the example of n=12,
If x is 1, then y is one of the factors of 12/1, namely {1,2,3,4,6,12}
If x is 2, then y is one of the factors of 12/2, namely {1,2,3,6}
If x is 3, then y is one of the factors of 12/3, namely {1,2,4}
If x is 4, then y is one of the factors of 12/4, namely {1,3}
If x is 6, then y is one of the factors of 12/6, namely {1,2}
If x is 12, then y is one of the factors of 12/12, namely {1}.
Once all the choosing is done, we will have examined every possibility for
x and y where x, y, and xy are all factors of n. If we had chosen y
first, and then picked x so that it divides "whatever is left over",
we would have ended up with the same set of possibilities. So a nested
sum that runs through these possibilities of x and y can be rearranged any way
we like, as long as the resulting sum runs through the same set of values in
some order.
That's the key to understanding the proof that follows.
Proof:
Using the identity expressing G(n) as the sum of F(d) where d runs
through the divisors of n,
Σ
d|n
|
μ(n/d) G(d) =
|
Σ
d|n
|
μ(n/d)
|
Σ
e|d
|
F(e)
|
|
Notice that the nested sum on the RHS runs through all the possibilities
of μ(x) F(y) where x, y, and xy are factors of n. Running
through the same possibilities in a different order,
Σ
d|n
|
μ(n/d) G(d) =
|
Σ
e|n
|
F(n/e)
|
Σ
d|e
|
μ(d)
|
|
And since the sum for all d|n of μ(d) is 0 when n>1, the second sum
is 1 only when e=1, so the RHS simplifies to F(n).
Conversely, using the second identity, expressing F(n) as the sum of μ(n/d) G(d)
where d runs through the divisors of n,
Σ
d|n
|
F(d) =
|
Σ
d|n
|
Σ
e|d
|
μ(d/e) G(e)
|
Rearranging the order the terms μ(x) F(y), (where x, y, and xy are
factors of n), are summed,
Σ
d|n
|
F(d) =
|
Σ
e|n
|
G(n/e)
|
Σ
d|e
|
μ(d)
|
And, again, since the sum for all d|n of μ(d) is 0 when n>1, the
RHS simplifies to G(n).
Application of the Möbius Inversion Formula
We have observed (and proved) already that the Sum of Totients of Divisors of n is n.
So if we let F be the totient function, and apply the Möbius Inversion
Formula,
We see that G(n) is the identity function; that is, G(n)=n in this case.
If we apply the identity again, this time letting F be the identity function,
We see that G(n) is σ(n), the sum of divisors of n, denoted by the
greek letter "sigma".
Starting from the Möbius function itself, and applying the Möbius
inversion, we get the following new functions:
U(n) =
|
Σ
d|n
|
μ(d)
|
— the "unit"
function that is 1 when n=1, and 0 otherwise
|
1(n) =
|
Σ
d|n
|
U(d)
|
— the "constant"
function that is always 1
|
τ(n) =
|
Σ
d|n
|
1(d)
|
— the "tau"
function, the number divisors of n
|
The Möbius Inversion Formula can be used in either direction any number of
times, forming a bi-infinite sequence of functions.
Internet references
Wikipedia: Mobius
inversion formula
Planet Math: Mobius
Inversion Formula
Related
pages in this website
φ(n), the number of coprimes to n: Totient
function
τ(n), the number of divisors of n: Divisors, Tau function
|
