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

Question

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?



Added (clarification):

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.

Answer 1

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.

Answer 2

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.

Answer 3

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}$)