5
$\begingroup$

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.

  • 0
    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.2011-07-29

4 Answers 4

3

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

And by the Möbius inversion formula,

$k(n)=\sum_{d\mid n}\mu(d)\omega(\frac{n}{d})$

As required

8

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.

  • 0
    Of course... I'm obviously too tired to keep going with this today! I'll read it tomorrow again. Thanks :)2011-07-29
7

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.

  • 0
    would the downvoter care to comment?2013-12-20
4

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

  • 0
    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.2011-07-29