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,

  • 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.

  • 2
    @Arturo Mag$i$din: 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?