# $\sum\limits_{d \mid n} \mu(d) \omega(n/d)=0$ for composite numbers. How?

I need some help with the last(?) step in a proof and I'm not sure how I should proceed... $\mu(n)$ is the Möbius function and $\omega(n)$ is the number of distinct prime factors. We see that for $n$ prime, $$\sum_{d \mid n}\mu(d)\omega(n/d )=\mu(1)\omega(n)+\mu(n)\omega(1)=1.$$ But for $n$ composite I'm at a loss. My idea is to somehow show that if $n=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$, then the terms in the following sum will cancel each other, like this: $$\sum_{d \mid n}\mu(d)\omega(n/d )=\omega(n)-\sum\omega\left(\frac{n}{p_i}\right)+\sum\omega\left(\frac{n}{p_ip_j}\right)+\ldots+\sum\omega\left(\frac{n}{p_1p_2\ldots p_k}\right)(-1)^{k},$$ where we just skip the divisors with exponent $a_i>1$ since $\mu$ would cancel them. Is there a way to achieve this? Or is this nonsense?

For $n=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$, $$\sum_{d \mid n}\mu(d)\omega \left( \frac{n}{d} \right)=\omega(n)+\underbrace{\mu(p_1) \omega(n/p_1)+ \ldots+\mu(p_k) \omega(n/p_k)}_{-\sum\omega\left(\frac{n}{p_i}\right)}+ \ldots + \mu(p_1 \ldots p_k) \omega\left(\frac{n}{p_1\ldots p_k}\right)$$ where $\mu(p_i)=-1$ and $\mu(p_1 \ldots p_k)=(-1)^{k}$. So we don't sum terms with square factors since they would be 0 in any case.

-
Your cancellation method gives, via the Binomial theorem and its derivative, $$\sum_{i=0}^k (k-i)(-1)^i {k \choose i} = k(1+(-1))^k - k(-1)(1+(-1))^{k-1}.$$ This formally evaluates to $1$ if $\omega(n)=k=1$ and $0$ if $k>1$. I'm not sure how you did the cancellation in the first place though... –  anon Jul 29 '11 at 9:44
@anon: Thanks! I added a clarification to the post. Could you explain how to get from my cancellation to your formula? I was trying to do something like it, but I didn't know how to do it. –  Carolus Jul 29 '11 at 10:53
I've updated my post. The reasoning process required was longer than I originally anticipated (for your direction) but my idea still applies at the end. –  anon Jul 29 '11 at 13:05

Let $P_i(k)$, $i=1,2,...\binom{\omega(n)}{k}$, be an enumeration of the products of $k$ of the prime factors of $n$, and $\nu(n)$ be the number of prime factors of $n$ with exponent $1$. Then $\binom{\nu(n)}{j}$ is the number of ways to choose $j$ primes with exponent $1$, and $\binom{\omega(n)-\nu(n)}{k-j}$ is the number of ways to choose $k-j$ primes with exponent greater than $1$. The primes with exponent $1$ in $n$ appearing in $P_i(k)$ decreases $\omega(\frac{n}{P_i(k)})$ to $\omega(n)-j$. Thus, \begin{align} \sum_{i=1}^{\binom{\omega(n)}{k}}\omega(\frac{n}{P_i(k)}) &=\sum_{j=0}^k \binom{\nu(n)}{j}\binom{\omega(n)\!-\!\nu(n)}{k\!-\!j}(\omega(n)\!-\!j)\\ &=\binom{\omega(n)}{k}\omega(n)-\sum_{j=0}^k \;j\binom{\nu(n)}{j}\binom{\omega(n)\!-\!\nu(n)}{k\!-\!j}\\ &=\binom{\omega(n)}{k}\omega(n)-\sum_{j=1}^k \;\nu(n)\binom{\nu(n)\!-\!1}{j\!-\!1}\binom{\omega(n)\!-\!\nu(n)}{k\!-\!j}\\ &=\binom{\omega(n)}{k}\omega(n)-\binom{\omega(n)\!-\!1}{k\!-\!1}\nu(n) \end{align} Because $\sum_k \binom{\omega(n)}{k}\;(-1)^k = 1$ when $\omega(n)=0$ and $0$ otherwise, we get that your alternating sum is $0$ when $\omega(n)=0$ and $\nu(n)$ when $\omega(n)=1$ and $0$ when $\omega(n)>1$.

$\omega(n)=0$ only when $n=1$. $\omega(n)=1$ and $\nu(n)=1$ only when $n$ is prime. When $n$ is composite, either $\omega(n)>1$ or $\nu(n)=0$. This should handle all cases.

-
Sorry for asking a stupid question, but what is $k$ in the first sum? –  Carolus Jul 30 '11 at 10:41
And btw, $C(n,k)$, is that the same as $\binom{n}{k}$? –  Carolus Jul 30 '11 at 10:41
@Carolus: $k$ is the number of distinct prime factors of $n$ whose product is $P_i(k)$. If $n = 2^3*3*5^2*7$, then $P_i(2)$ ranges over $2*3$, $2*5$, $2*7$, $3*5$, $3*7$, and $5*7$. Thus, $\mu(P_i(k))=(-1)^k$. –  robjohn Jul 31 '11 at 2:59
@Carolus: yes, $C(n,k)=\binom{n}{k}$. –  robjohn Jul 31 '11 at 3:01
would the downvoter care to comment? –  robjohn Dec 20 '13 at 23:49

Updated with heavy clarifications / elaborations.

Let $f(n) = \sum_{d|n} \mu(d) \omega(n/d)$. Then, by Möbius inversion, we have $\omega(n) = \sum_{d|n} f(d)$. Let $g(m)$ be the arithmetic function which evaluates to $1$ for prime $m$ and $0$ for composite $m$. Then we can write the difference function $h(n) = \sum_{d|n} [f(d)-g(d)]=0$, and use Möbius inversion again in the reverse direction to get $f(n)-g(n)=\sum_{d|n} \mu(d) h(n/d) = 0$, which proves the original hypothesis.

(Originally I believed some form of induction was best suited to finish off this proof, but discovered that that wasn't going to work while second inversion would.)

In order to go from your post-cancellation sum to the desired conclusion, we will split $n$'s prime factorization into two components, a "$\mu$" part and a "$\mu$-free" part, as $n=ab$, where $a=q_1\cdots q_k$ and $b= p_1^{e_1}\cdots p_l^{e_l}$ with exponents $e_i\ge 2$. Also write $b'=p_1\cdots p_l$. For divisors $d|n$, we write $d=d_1d_2$, where $d_1|a$ and $d_2|b$. Then $\mu(d)\ne 0$ if and only if $d_2|b'$, so we can write the sum as

$$\sum_{d_1|a}\, \sum_{d_2|b'} \mu(d_1d_2) \omega\left(\frac{ab}{d_1d_2}\right) = \left(\sum_{d_1|a} \mu(d_1)[l +\omega(a/d_1)]\right)\left( \sum_{d_2|b'} \mu(d_2)\right)$$

(Note that $\omega(b/d_2)=l$ regardless of $d_2$ because of the exponents in $b$'s prime factorization, and we use separations $\omega(xy) = \omega(x)+\omega(y)$, $\mu(xy)=\mu(x)\mu(y)$ when $\gcd(x,y)=1$.) The righthand factor above is $0$ except when $b'=1$, i.e. when $n=a$. In that case we can further reduce the sum to

$$\sum_{d_1|a} \mu(d_1)\omega(a/d_1).$$

Now my original reasoning kicks in, by letting $Q$ be the set of prime factors of $a$, and then following the explicit deduction in user10676 answer.

-
I'm trying to understand this... I understand the first part, up to induction... I don't get the test -part. –  Carolus Jul 29 '11 at 11:01
You write: "Let $g(m)$ be the arithmetic function which evaluates to 1 for prime $m$ and 0 for composite $m$" - But this is the very definition of $f(n)$ which we are trying to prove, isn't it? –  Carolus Jul 29 '11 at 13:22
@Carolus: Precisely. Since $\sum_{d|n} g(d)=\omega(n)$ just like with $f(d)$, we can write $\sum f-g = 0$ and then use Mobius inversion to get $f-g=0$ which proves they are one in the same. –  anon Jul 29 '11 at 13:29
Of course... I'm obviously too tired to keep going with this today! I'll read it tomorrow again. Thanks :) –  Carolus Jul 29 '11 at 13:45

Here is a way to complete what you have started, as suggested by Anon.

Let $P$ be the set of primes factors of $n$. Then one have $$\sum_{d|n} \mu(d) \omega(n/d) = \sum_{I \subset P} (-1)^{|I|} (|P|-|I|)$$ Then split the sum according to the cardinal of $I$: $$\sum_{d|n} \mu(d) \omega(n/d) = \sum_{k =0}^{|P|} \binom{|P|}{k} (-1)^{k} (|P|-k)$$ Conclude with the facts that $$\sum_{k=0}^{|P|} \binom{|P|}{k} (-1)^{k} = \begin{cases} 0, & \text{if } |P| \geq 1 \\ 1, & \text{if } |P|=0 \end{cases}$$ and $$\sum_{k=0}^{|P|} \binom{|P|}{k} k (-1)^{k} = \begin{cases} 0, & \text{if } |P| \geq 2 \\ -1, & \text{if } |P|=1 \\ 0, & \text{if } |P|=0. \end{cases}$$ (For the last one, notice that $k\binom{N}{k} = N\binom{N-1}{k-1}$)

-
This reasoning only works when the exponents in $n$'s prime factorization are all $1$. In my answer I reduce the problem down to just such a case and then outsource to your explication, so please keep it here. Thanks. –  anon Jul 29 '11 at 13:04
Define $k(n)$ to be $1$ if $n$ is prime and $0$ if n is composite, then
$$\sum_{d\mid n}k(d)=\sum_{p\mid n}k(p)=\sum_{p\mid n}1=\omega(n)$$
$$k(n)=\sum_{d\mid n}\mu(d)\omega(\frac{n}{d})$$