Section23.2New Arithmetic Functions from Old

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

Briefly speaking, if you sum an arithmetic function over divisors, 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 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\) via the formula \[(f\star g)(n)=\sum_{de=n}f(d)g(e)=\sum_{d\mid n}f(d)g\left(\frac{n}{d}\right)\, .\]
Example23.2.3

For example, if \(u(n)=1\) and \(N(n)=n\), then \[(\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)\; .\]

We really knew this long ago, of course, but now we can write it concisely as \(\phi\star u=N\).

So we could restate the theorem as, \[\text{If }f=g\star u\text{, then }g=f\star \mu\; .\] Such a “product” of two functions is called the Dirichlet product of the functions; we will discuss this more later.

Subsection23.2.2Proof of Moebius Inversion

Let's expand the formula for \(g(n)\) the theorem would give, in terms of \(g\) itself. \[\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]\, .\] 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. 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, \[\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)\, .\]

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!