NTIC Inverting Functions

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

τ (n) = \sum_{d ∣ n} 1 = \sum_{d ∣ n} u (n)

(recall Definition 19.2.9) then it implies

\sum_{d ∣ n} μ (d) τ (\frac{n}{d}) = 1 .

This is worth checking by hand or with Sage. Somehow, mysteriously, the number of divisors weighted by the $μ$ 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 ⋆ g,$ the Dirichlet product, via the formula

(f ⋆ g) (n) = \sum_{d e = n} f (d) g (e) = \sum_{d ∣ n} f (d) g (\frac{n}{d}) .

🔗

Example 23.2.4.

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

(ϕ ⋆ u) (n) = \sum_{d ∣ n} ϕ (d) u (\frac{n}{d}) = \sum_{d ∣ n} ϕ (d) = n = N (n) .

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.

\sum_{d ∣ n} μ (d) f (\frac{n}{d}) = \sum_{d ∣ n} μ (d) [\sum_{e ∣ \frac{n}{d}} g (e)] .

🔗

Each time

g (e)

appears in this sum, it has a coefficient of

μ (d) .

How often does this happen, and what is

d

anyway?

🔗

e ∣ \frac{n}{d},

then

e ∣ 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

e d ∣ n,

in which case certainly

d ∣ \frac{n}{e} .

🔗

g (e)

shows up once for each

d ∣ \frac{n}{e},

with coefficient

μ (d) .

Thus,

\sum_{d ∣ n} μ (d) f (\frac{n}{d}) = \sum_{e ∣ n} (\sum_{d ∣ \frac{n}{e}} μ (d)) g (e) .

🔗

Here comes the final step. Unless

\frac{n}{e} = 1,

we have

\sum μ (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!