4.3: Mobius inversion

Lemma 4.12

Define \(\epsilon (n) \equiv \sum_{d|n} \mu (d)\). Then \(\epsilon (1) = 1\) and for all \(n > 1, \epsilon (n) = 0\).

Proof

Lemma 4.8 says that \(\mu\) is multiplicative. Therefore, by Proposition 4.3, \(\epsilon\) is also multiplicative. It follows that \(\epsilon (\pi_{i=1}^{r} p_{i}^{l_{i}})\) can be calculated

by evaluating a product of terms like \(\epsilon (p^{l})\) where \(p\) is prime. For example, when \(p\) is prime, we have

\[\epsilon (p) = \mu (1)+ \mu (p) = 1+(-1) = 0 \nonumber\] and

\[\epsilon (p^2) = \mu (1)+ \mu (p)+ \mu (p^2) = 1-1+0 = 0 \nonumber\]

Thus one sees that \(\epsilon (p^l)\) is zero unless \(l = 0\).

Lemma 4.13

For \(n \in \mathbb{N}\), define

\[S_{n} \equiv \{ (a, b) \in \mathbb{N} | \exists d > 0 \mbox{ such that } d | n \mbox{ and } ab = d \} \nonumber\]

\[T_{n} \equiv \{ (a, b) \in \mathbb{N}^{2} | b | n \mbox{ and } a | \frac{n}{b} \} \nonumber\]

Then \(S_{n} = T_{n}\).

Proof

Suppose \((a, b)\) is in \(S_{n}\). Then \(ab | n\) and so

\[ab = \left. \begin{array} {ab = d}\\ {d|n} \end{array} \right \} \Rightarrow b|n \mbox{ and } a | \frac{n}{d} \nonumber\]

And so \((a, b)\) is in \(T_{n}\). Vice versa, if \((a, b)\) is in \(T_{n}\), then by setting \(d \equiv ab\),

we get

\[\left. \begin{array} {b | n}\\ {a|\frac{n}{b}} \end{array} \right \} \Rightarrow d|n \mbox{ and } ab = d \nonumber\]

And so \((a, b)\) is in \(S_{n}\)

Theorem 4.14: Mobius Inversion

Let \(F : \mathbb{N} \rightarrow \mathbb{C}\) be any number theoretic function. Then the equation

\[F(n) = \sum_{d|n} f(d) \nonumber\]

if and only if \(f : \mathbb{N} \rightarrow \mathbb{C}\) satisfies

\[f(d) = \sum_{a|d} \mu (a) F\left(\frac{d}{a}\right) = \sum_{\{(a,b) | ab = d\}} \mu (a) F(b) \nonumber\]

Proof

\(\Leftarrow\): We show that substituting \(f\) gives \(F\). Define H as

\[H(n) \equiv \sum_{d|n} f(d) = \sum_{d|n} \sum_{a|d} \mu (a) F(\frac{d}{a}) \nonumber\]

Then we need to prove that \(H(n) = F(n)\). This proceeds in three steps. For the first step we write \(ab = d\), so that now

\[H(n) \equiv \sum f(d) = \sum_{d|n} \sum_{ab = d} \mu (a) F(b) \nonumber\]

For the second step we apply Lemma 4.13 to the set over which the summation takes place. This gives:

\[H(n) = \sum_{b|n} \sum_{a|(\frac{n}{b})} \mu (a) F(b) = \sum_{b|n} \left(\sum_{a| \frac{n}{b}} \mu (a)\right) F(b) \nonumber\]

Finally, Lemma 4.12 implies that the term in parentheses equals \(G \left(\frac{n}{b}\right)\). It equals \(0\), except when \(b = n\) when it equals \(1\). The result follows.

Uniqueness: Suppose there are two solutions \(f\) and \(g\). We have:

\[F(n) = \sum_{d|n} f(d) = \sum_{d|n} g(d) \nonumber\]

We show by induction on \(n\) that \(f(n) = g(n)\).

Clearly \(F(1) = f(1) = g(1)\). Now suppose that for \(i \in \{1,\cdots k\}\), we have \(f(i) = g(i)\). Then

\[F(k+1) = (\sum_{d|(k+1), d \le k} f(d)) + f(k+1) = (\sum_{d|(k+1), d \le k} g(d)) + g(k+1) \nonumber\]

So that the desired equality for \(k+1\) follows from the induction hypothesis.