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.