NTIC Inverting Functions

$\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 ²See also Definition 23.3.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*}$

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 [C.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?

🔗

$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{.}$

🔗

$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!