# Slightly confused about Möbius' inversion theorem

Alright, I understand the proof of the theorem and everything, but I don't have much intuition about the definition. I think the theorem would work using any function $\psi : \mathbb{N} \rightarrow \mathbb{N}$ such that $\psi(1) = 1$ and $\displaystyle\sum_{d | n} \psi(d) = 0$ whenever $n > 1$. So is there some specific reason as to why $\mu$ is defined the way it is?

As another question, I am using the book "A classical introduction to modern number theory" by Ireland & Rosen and on chapter 2 there is the exercise 21 which I just cannot make sense of. It reads:

"Define $f(n) = p$ if $n$ is a power of p and zero otherwise. Prove that $\sum_{d | n} \mu(n/d) \log d = f(n)$. [Hint: First calculate $\sum_{d | n} f(d)$ and then apply the Möbius inversion formula]"

It doesn't make sense to me, because which is this $p$ that the question references? Is it some fixed constant? I guess this would make sense if $\sum_{d | n} f(d) = \log n$ because then the formula would work out, but why would that be true? Well I guess if we consider that $n = p^{\epsilon}$ then the sum would give $\epsilon \log p = \log p^{\epsilon} = \log n$ (if we consider 1 as not a power of $p$), but that's just not a safe assumption, is it? I'm rambling here, any ideas?

-
As a hint to your second question, to find the sum $\sum_{d \mid n} f(d)$, start by writing $n = p_1^{\alpha_1} \dots p_k^{\alpha_k}$. –  JavaMan Jan 11 '12 at 23:09

The reason $\mu$ is defined the way it is is that this gives the only function $\psi$ with the properties you required. This is trivial to prove by induction.

As for your exercise, I think you must have not transcribed it correctly. Certainly $p$ is assumed to be a prime number, but from what you write it seems that $f(p^m)=\log p$ for $m>0$ and $f(1)=0$, since that is what the formula you are required to prove gives. Also $f(n)=0$ for non prime-powers, and one can check that $\sum_{d|n} f(d) = \log n$ for all $n>0$ by using the prime factorization of $n$ (if $p$ has multiplicity $m$ in $n$ then there are $m$ positive powers of $p$ that divide $n$), so your argument basically works.

-
How exactly do I prove it by induction? I tried checking that $\psi(n) = \mu(n)$ implies $\psi(n + 1) = \mu(n + 1)$ but I have no idea how to relate $\psi(n)$ with $\psi(n + 1)$. –  Pedro Jan 11 '12 at 23:59
You have to use strong induction: to prove that $\psi(n)=\mu(n)$, use that $\psi(i)=\mu(i)$ for all $i<n$, in particular for all strict divisors of $n$. Now writing $\sum_{d|n}\psi(d) = 0 = \sum_{d|n}\mu(d)$ for $n>1$, check that all terms except $d=n$ cancel out, leaving $\psi(n)=\mu(n)$. –  Marc van Leeuwen Jan 12 '12 at 5:34

Euler showed that the Dirichlet series of a multiplicative function $f$ can be written as a product (now called an Euler product):

$$L(s, f) := \sum_{n \geq 1} \frac{f(n)}{n^s} = \prod_p \left(1 + f(p)p^{-s}+ f(p^2) p^{-2s} + \dots \right).$$

In particular the $\zeta$-function corresponds to $f(n) \equiv 1$ and yields:

$$\zeta(s) = L(s,1) = \sum_{n \geq 1} n^{-s} = \prod_{p} \left((p^{-s})^0 + (p^{-s})^1 + (p^{-s})^2 + \dots \right) = \prod_{p} \left(1 - p^{-s} \right)^{-1}.$$

This implies that

$$\frac{1}{\zeta(s)} = \prod_{p} \left( 1 - p^{-s}\right) = \sum_{n \geq 1} \frac{\mu(n)}{n^s}$$

for some multiplicative function $\mu$ such that $\mu(p) = -1$ and $\mu(p^k) =0$ for any prime $p$ when $k \geq 2$. This yields the standard definition of the Möbius function and is possibly how the function was discovered. This should at least provide an intuitive understanding of the function $\mu$.

-
Cool math, but downvoted because I don't think it's a helpful level for the OP. PS: I strongly doubt that the Euler product for $1/\zeta(s)$ was considered before the definition of the arithmetic function $\mu$ was known. –  Greg Martin Jan 12 '12 at 0:01
@GregMartin: Thanks for the input. Out of curiosity, why do you doubt the Euler product for $1 / \zeta(s)$ was not the first consideration for $\mu$? Do you have historical reasons for this? My assumption that this is probably how $\mu$ was discovered is only based on the fact that the Euler product seems to be the most natural place where $\mu$ appears. Any historical evidence to the contrary would be interesting to me, however. –  JavaMan Jan 12 '12 at 2:03
$\mu$ encodes the entire inclusion-exclusion argument that goes back to the sieve of Eratosthenes, for example. –  Greg Martin Jan 12 '12 at 18:22

We had nearly the same subject last week : 'Deriving the formula for the Möbius function?'.

You should find there some proofs that your definition defines uniquely the 'Möbius function'.

Concerning $p$ it is conventional in number theory to name '$p$' a prime number. The point for $f(n)$ was to test if $n$ was (or not) a power of a prime number.

-