(Edit) Can someone explain where the mistake is and what is wrong with the following "proof"?:

(i) $\sum_{d\mid n}(\sigma_k(d))$ = $\sum_{d|n}(\tau(\frac{n}{d})d^k)$ (True)

(ii) Define a function $S(n)$ such that $\sum_{d\mid n}(\sigma_k(d)) = S(n) = \sum_{d|n}(\tau(\frac{n}{d})d^k)$

(iii) The möbius inversion formula as it is stated in [Apostal, Analytic Number Theory, pg 32] says: If $f(n) = \sum_{d|n}g(d)$, then $g(n) = \sum_{d|n}f(d)\mu(\frac{n}{d})$

(iv)(a) $S(n) = \sum_{d\mid n}(\sigma_k(d))$, so we have $\sigma_k(n) = \sum_{d|n}S(d)\mu(\frac{n}{d})$

(iv)(b) $S(n) = \sum_{d\mid n}(\tau(\frac{n}{d})d^k))$, so we have $\tau(\frac{n}{n})n^k = n^k = \sum_{d|n}S(d)\mu(\frac{n}{d})$

(v) Therefore $\sigma_k(n) = n^k$

If anyone can tell me which line(s) is wrong and why it's wrong, that would be incredibly helpful. Thanks.

  • $\begingroup$ What are $\sigma_k$ and $\tau$? $\endgroup$ – Aravind Aug 8 '20 at 17:22
  • $\begingroup$ $\sigma_k(n)$ is the sum of the divisors of n, each raised to the kth power, and $\tau(n)$ is the number of divisors of n. $\endgroup$ – James Aug 8 '20 at 17:24
  • $\begingroup$ How exactly did you use the MIF on the right side of your summation equation to get $n^k$? $\endgroup$ – Somos Aug 8 '20 at 17:27
  • $\begingroup$ If you let both sums equal some function dependent on n, say S(n), by taking the right hand side term outside the summation you get $\tau(\frac{n}{n})*n^k = \sum_{d|n}(\mu(\frac{n}{d})*S(d))$ $\endgroup$ – James Aug 8 '20 at 17:29
  • $\begingroup$ What do you mean with "taking the right hand side term outside the summation"? $\endgroup$ – Daniel Fischer Aug 8 '20 at 17:36

The mistake is in (iv)(b). In $$\sum_{d \mid n} \Biggl(\tau\biggl(\frac{n}{d}\biggr)d^k\Biggr) \tag{1}$$ the expression we sum over is not of the form $f(d)$, as it would need to be to apply the Möbius inversion formula (iii). The summands in $(1)$ depend on $n$ as well as on $d$, we have the form $$S(n) = \sum_{d \mid n} f(n,d)\,.$$

If we write things using the Dirichlet convolution using $u \colon n \mapsto 1$ and $\nu_k \colon n \mapsto n^k$ (thus we could write $\nu_0$ instead of $u$, but $u$ is a widely used name for that function), then the Möbius inversion formula can succinctly be stated as $$g = u \ast f \iff f = \mu \ast g\,. \tag{2}$$ The left hand side of (i) gives you $S$ in the form $u \ast \sigma_k$, precisely what $(2)$ is about, thus $\sigma_k = \mu \ast S$, or written in long form $$\sigma_k(n) = \sum_{d \mid k} \mu\biggl(\frac{n}{d}\biggr)S(d)\,,$$ by the Möbius inversion formula.

The right hand side of (i) however gives you $S$ in the form $S = \tau \ast \nu_k$, and $(2)$ says nothing about that form. A more general form of $(2)$ applies to that form however, and gives $\nu_k = \tau^{-1} \ast S$, or in long form $$n^k = \sum_{d \mid n} \tau^{-1}\biggl(\frac{n}{d}\biggr)S(d)\,,$$ where $\tau^{-1}$ is the Dirichlet inverse of $\tau$. (Since $\tau = u\ast u$ and $\mu$ is the Dirichlet inverse of $u$ we have $\tau^{-1} = \mu \ast \mu$.)

  • $\begingroup$ Ah, never even occurred to me to consider the problem might be with n, thank you so much!! $\endgroup$ – James Aug 11 '20 at 23:04

Let $f_k(n)=n^k$, then $\sigma_k=1* f_k$, thus $1*\sigma_k=1*(1*f_k)=(1*1)*f_k=\tau*f_k$. If you use Möbius inversion formula to $\sigma_k=1*f_k$, you get $f_k=\mu*\sigma_k$, not $f_k=\sigma_k$.

  • $\begingroup$ Is 1 the identity function? $\endgroup$ – James Aug 8 '20 at 17:46
  • $\begingroup$ It's the constant function $n\mapsto 1$. $\endgroup$ – Tuvasbien Aug 8 '20 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.