§ Dirichlet inversion
We call all functions as
arithmetic functions, since they operate on the integers.
We introduce an operator .
It is defined by:
We will show that the set of arithmetic functions forms a group
under the operator , with identity:
The reason all of this is interesting is that the inverse of the constant function
is going to be this function called as the mobius function :
The mobius function will allow us to perform mobius inversion:
That is, we originally had defined in terms of . We can
recover an expression for in terms of .
§ The algebra of multiplicative functions
We claim that the set of functions
is a commutative group, with the group operation such that:
with the identity element being . The idea
is that if , then , and for any other
number , , hence .
§ verification of being the identity
§ associativity, commutativity of
To prove associativity, it's better to write the formula as:
From this rewrite, it's clear that will unambiguously
sum over tripes such that . I leave the working-this-out
to you. This should also make the commutativity immediate. Summing over pairs
of the form is the same as summing over .
§ Existence of inverse
We can show that an inverse exists by showing that a formula for it exists; The
idea is to construct one by induction.
Clearly, for a given function , we need the inverse to be such that
Great, we have a base case; We can now compute inductively, assuming
we know the value of for all .
§ as the inverse of the function
§ Mobius inversion
Now that we know that , we can use this fact
to perform mobius inversion:
We have written in terms of . We can now write in terms of :
Notice that the sizes of sets that we are calculating, for example,
. Summing over all of
what we have, we've counted the numbers in in two ways ---
one directly, and the other by partitioning into equivalence classes:
In general, the same argument allows us to prove that:
§ Using mobius inversion on the euler totient function
§ Other arithmetical functions and their relations