Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section23.2Inverting Functions

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

Proof

We can interpret this result briefly as follows. Suppose you sum an arithmetic function over the set of its (positive) divisors to create a new function. Then summing that function over divisors, along with \(\mu\), 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.

Subsection23.2.1Some useful notation

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

Definition23.2.2Dirichlet product

Let \(f\) and \(g\) be arithmetic functions. Then we define the new function \(f\star g\), 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)\, .\end{equation*}

Example23.2.3

For example, if \(u(n)=1\) and \(N(n)=n\), 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)\; .\end{equation*}

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\; .\end{equation*}

Subsection23.2.2Proof of Moebius inversion

Now we are ready to prove the Möbius Inversion Formula, following [C.1.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]\, .\end{equation*} Each time \(g(e)\) appears in this sum, it has a coefficient of \(\mu(d)\). How often does this happen, and what is \(d\) anyway?

If \(e\mid \frac{n}{d}\), then \(e\mid n\), 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}\), we have \(ed\mid n\), in which case certainly \(d\mid \frac{n}{e}\).

So \(g(e)\) shows up once for each \(d\mid \frac{n}{e}\), with coefficient \(\mu(d)\). 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)\, .\end{equation*}

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

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