7
$\begingroup$

In my notes: $$\sum_{d|n} \mu(d)\sigma(d) = (-1)^{k} \prod_{i=1}^{k} p_i$$

where $\mu(d)$ is the Möbius function and $\sigma(d)$ is the sum of all positive divisors of $d$.

And I have no idea how they got the expression on the right hand side. Could anyone help me explain how this works?

Thanks,

  • 1
    Hints: 1. When are the only possible $d$ with nonzero $\mu(d)$? 2. For such $d$, how does $\sigma(d)$ look like? In particular, is it multiplicative? 3. Look at the sum on the left again after answering 1 and 2. Can you factorize it?2011-03-01
  • 1
    **The** book? And I assume $k$ is the number of distinct prime divisors of $n$?2011-03-01
  • 1
    Arturo Magidin: I really don't know what is k. I rather change to my notes since I don't have any book for this class.2011-03-01
  • 1
    @Arturo, $k$ is the number of distinct prime divisors of $n$.2011-03-01
  • 0
    Note that this is a special case of the result from this question: http://math.stackexchange.com/questions/82379/how-to-prove-sum-d-mid-n-mudfd-prod-i-1r-1-fp-i2011-12-03

3 Answers 3

6

Caveat: This may not be the most direct way of doing it.

Write $n=p_1^{a_1}\cdots p_k^{a_k}$ with $p_i$ pairwise distinct primes. Since the Moebius function is zero at any non-square-free integer, the only divisors that matter are those which are products of some pairwise distinct $p_i$.

Since $$\sigma(p_{i_1}\cdots p_{i_r}) = \prod_{j=1}^r \sigma(p_{i_j}) = \prod_{j=1}^{r}(1+p_{i_j}),$$ then the sum on the left hand side is the sum of these products, with a minus sign if the number of factors is odd, and a plus sign if the number of factors is even.

Let $x_i = 1 + p_i$. Let $S_r(x_1,\ldots,x_k)$ is the $r$th elementary symmetric polynomial on $x_1,\ldots,x_r$; that is, \begin{align*} S_0(x_1,\ldots,x_k) &= 1,\\ S_1(x_1,\ldots,x_k) &= x_1+\cdots + x_k,\\ S_2(x_1,\ldots,x_k) &= x_1x_2 + \cdots + x_1x_k + x_2x_3+\cdots + x_{k-1}x_k,\\ &\vdots\\ S_k(x_1,\ldots,x_k) &= x_1\cdots x_k. \end{align*}

Therefore: $$\sum_{d|n}\mu(d)\sigma(d) = \sum_{r=0}^k (-1)^rS_r(x_1,\ldots,x_k).$$

Now consider the polynomial $(t-x_1)\cdots(t-x_k)$. The coefficient of $t^i$ is precisely $(-1)^{k-i}S_{k-i}(x_1,\ldots,x_k)$. Thus, the sum on the right hand side is this polynomial evaluated at $t=1$. Therefore, $$\sum_{d|n}\mu(d)\sigma(d) = \sum_{r=0}^k(-1)^rS_r(x_1,\ldots,x_k) = (1-x_1)\cdots(1-x_k) = \prod_{i=1}^k(1-x_i).$$ But $1-x_i = 1-(1+p_i) = -p_i$. Therefore, $$\sum_{d|n}\mu(d)\sigma(d) = \prod_{i=1}^k(-p_i) = (-1)^k\prod_{i=1}^kp_i,$$ as claimed.

  • 0
    @Arturo Magidin: Many thanks for your very clear explanation. You made me feel less dumb now :P! By the way, I realized you think super fast, probably 10 times faster than mine. I can't believe in about 2 minutes, you could write that much. Amazing!2011-03-01
  • 0
    @Chan: What do you mean, "about 2 minutes"? Where do you get that from? Certainly, took me longer than that to write it out! And my answer was posted well over half an hour after you posted the question (though I did not see it immediately after you did).2011-03-01
  • 0
    @Chan: Also: keep in mind, this may not be the best way of doing it; it just happens to be the way that it occurred to me to do it just now.2011-03-01
  • 0
    @Arturo Magidin: really? I thought it was much faster than that. Although 2 minutes would be an exaggeration, I don't think it took half an hour though.2011-03-01
  • 0
    @Chan: As I write this, your question says that it was posted "49 mins ago", and my answer reads "answered 16 mins ago". By my count, 49-16 is more than 30. (-:2011-03-01
  • 2
    @Arturo Magidin: Ok, fair enough. Probably because I stayed in front of my computer for too long, and did not realized time passed.2011-03-01
5

This looks more like a special case of Möbius Inversion Formula. You need to choose an appropriate $f$ and $g$.

Note that $n = p_1^{\alpha_1} p_2^{\alpha_2} \ldots p_k^{\alpha_k}$ and $n = p_1 p_2 \ldots p_k$ should give the same answer. (Essentially you are removing the $\mu(d) = 0$ terms on the left side).

Hence, we could just deal with $n = p_1 p_2 \ldots p_k$.

Now let $f(n) = n$ and $g(n) = \displaystyle \sum_{d|n} f(d)$.

$g(n)$ is nothing but the sum of divisors of $n$ i.e. $g(n) = \sigma(n)$.

Note that $\mu(d) = (-1)^k \mu \left( \frac{n}{d} \right)$ when $n = p_1 p_2 \ldots p_k$.

By Möbius Inversion Formula, $$n = \sum_{d|n} \mu(d) g\left( \frac{n}{d} \right) = (-1)^k \sum_{d|n} \mu\left( \frac{n}{d} \right) g \left( \frac{n}{d} \right) = (-1)^k \sum_{d|n} \mu\left( d \right) g \left( d \right)$$

Hence, $$\sum_{d|n} \mu\left( d \right) \sigma \left( d \right) = (-1)^k p_1 p_2 \ldots p_k$$

  • 0
    I was pretty sure Moebius inversion could be used, but the circuitous method I came up with ocurred to me before I could figure out what $g$ to use... Thanks!2011-03-01
4

Hint: the Möbius function is only non-zero on squarefree numbers (see here), and it is either $+1$ or $-1$ depending on the number of factors. Then consider: What do the squarefree divisors of $n=p_1^{a_1}\cdots p_r^{a_r}$ look like? What does $\sigma$ (the sum of divisors) of a squarefree number look like?