Skip to main content

Section 23.2 Inverting Functions

The main point of the Moebius function is the following famous theorem.

We can interpret this result briefly as follows. Suppose you sum an arithmetic function over the set of the (positive) divisors of \(n\) to create a new function of \(n\text{.}\) Then summing that function over divisors, along with \(\mu\text{,}\) gives you back the original function.

The reason we care about this is that we are able to use the \(\mu\) function to get new, useful, arithmetic functions via this theorem. In particular, we can “invert” all of our usual arithmetic functions, and this will lead to some very powerful applications.

Example 23.2.2.

If we apply this theorem to

\begin{equation*} \tau(n)=\sum_{d\mid n}1=\sum_{d\mid n}u(n) \end{equation*}

(recall Definition 19.2.9) then it implies

\begin{equation*} \sum_{d\mid n}\mu(d)\tau\left(\frac{n}{d}\right)=1\text{.} \end{equation*}

This is worth checking by hand or with Sage. Somehow, mysteriously, the number of divisors weighted by the \(\mu\) function nearly balances out.

Subsection 23.2.1 Some useful notation

In order to better understand what this theorem is saying, let's introduce some notation.

Definition 23.2.3. Dirichlet product.

Let \(f\) and \(g\) be arithmetic functions. Then we define the new function \(f\star g\text{,}\) the Dirichlet product, via the formula

\begin{equation*} (f\star g)(n)=\sum_{de=n}f(d)g(e)=\sum_{d\mid n}f(d)g\left(\frac{n}{d}\right)\text{.} \end{equation*}
Example 23.2.4.

For example, if we recall \(u(n)=1\) and \(N(n)=n\) from Definition 19.2.9 1 , then

\begin{equation*} (\phi\star u)(n)=\sum_{d\mid n}\phi(d)u\left(\frac{n}{d}\right)=\sum_{d\mid n}\phi(d)=n=N(n)\text{.} \end{equation*}
See also Definition 23.3.1.

We saw this originally in Fact 9.5.4, but now we can write it concisely as \(\phi\star u=N\) and see it is part of a bigger context. (See also Fact 23.3.2.)

This notation, like all the best notation, practically demands that we restate the inversion theorem in a very insightful way:

\begin{equation*} \text{If }f=g\star u\text{, then }g=f\star \mu\text{.} \end{equation*}

Subsection 23.2.2 Proof of Moebius inversion

Now we are ready to prove the Möbius Inversion Formula, following the standard proof, as for example in [E.2.1].

Let's expand the formula for \(g(n)\) the theorem would give, in terms of \(g\) itself.

\begin{equation*} \sum_{d\mid n}\mu(d)f\left(\frac{n}{d}\right)=\sum_{d\mid n}\mu(d)\left[\sum_{e\mid \frac{n}{d}}g(e)\right]\text{.} \end{equation*}

Each time \(g(e)\) appears in this sum, it has a coefficient of \(\mu(d)\text{.}\) How often does this happen, and what is \(d\) anyway?

If \(e\mid \frac{n}{d}\text{,}\) then \(e\mid n\text{,}\) which means \(\frac{n}{e}\) is an integer. However, this integer must have at least a factor of \(d\) “left” in it (after division by \(e\)). Why? Since \(e\) divides \(\frac{n}{d}\text{,}\) we have \(ed\mid n\text{,}\) in which case certainly \(d\mid \frac{n}{e}\text{.}\)

So \(g(e)\) shows up once for each \(d\mid \frac{n}{e}\text{,}\) with coefficient \(\mu(d)\text{.}\) Thus,

\begin{equation*} \sum_{d\mid n}\mu(d)f\left(\frac{n}{d}\right)=\sum_{e\mid n}\left(\sum_{d\mid \frac{n}{e}}\mu(d)\right)g(e)\text{.} \end{equation*}

Here comes the final step. Unless \(\frac{n}{e}=1\text{,}\) we have \(\sum \mu(d)=0\text{.}\) So the only subsum in this double sum that sticks around is the term for \(\frac{n}{e}=1\text{,}\) or when \(e=n\text{.}\)

Thus the whole sum collapses to \(g(n)\text{,}\) as desired!