1
$\begingroup$

I am out to prove that if $$f(n)=\prod\limits_{d|n}g(d)$$ then $$g(n)=\prod\limits_{d|n}f(d)^{\mu{n\over{d}}}$$ I have been grappling with this for a bit too long now, and would really appreciate some help. I suspect logarithms might be helpful after looking at similar problems, namely this one, however I am not to familiar with their workings.

$\endgroup$
3
  • $\begingroup$ Taking the logarithm, if $ F(n) = \sum_{d | n} G(d)$ then $\sum_{d | n} \mu(n/d) F(d) = \sum_{d | n} \mu(n/d) \sum_{k | d} G(k) = \sum_{k | n} G(k) \sum_{l | n/k} \mu(l)$ $ = \sum_{k | n} G(k) 1_{n/k = 1} =G(n)$ $\endgroup$ – reuns Oct 26 '17 at 4:11
  • $\begingroup$ You're first step is confusing me, sorry. $\endgroup$ – Gwen Di Oct 26 '17 at 4:26
  • $\begingroup$ $F(n) = \log f(n)$ $\endgroup$ – reuns Oct 26 '17 at 4:27
2
$\begingroup$

You can also avoid logarithms. If $f(n)=\prod_{a\mid n}g(a)$, then

$$ \prod_{b\mid n}f(b)^{\mu(n/b)} = \prod_{b\mid n}\prod_{a\mid b} g(a)^{\mu(n/b)}=\prod_{a\mid n}\prod_{c\mid\frac{n}{a}}g(a)^{\mu\left(\frac{n}{ac}\right)} $$and for a fixed $a$ which is a divisor of $n$, $$ \sum_{c\mid \frac{n}{a}}\mu\left(\frac{n}{ac}\right)=0 $$ unless $a=n$. It follows that the previous product is exactly $g(n)$, as expected.

$\endgroup$
3
  • $\begingroup$ This looks interesting, but I'm having trouble following it starting with the last equality on the first line after the one ending 'then'. Any additional explanation would be nice. $\endgroup$ – Circulwyrd Oct 31 '17 at 21:49
  • $\begingroup$ @GregB.Hill: that is just reindexing. We want to sum over $a\mid b\mid n$, so by setting $b=ac$ we get the shown rearrangement of the double product. $\endgroup$ – Jack D'Aurizio Oct 31 '17 at 23:41
  • $\begingroup$ @Jack.D'Aurizio That's a cool solution: I would never have thought of that. $\endgroup$ – Circulwyrd Nov 1 '17 at 14:56
1
$\begingroup$

You just need to use that $\log(xy)=\log x + \log y$ and $\log(x^y)=y \log x$. Applying $\log$ to your equations (and making the necessary assumptions for the values of $g$ so that the logarithms are defined) yields the usual Möbius inversion formula.

$\endgroup$
5
  • $\begingroup$ How would you get rid of the logs at the end? $\endgroup$ – Gwen Di Oct 26 '17 at 4:25
  • $\begingroup$ By applying the exponential function which is the inverse of the logarithmic one. $\endgroup$ – posilon Oct 26 '17 at 4:29
  • $\begingroup$ Ok, the relation is valid assuming that $g$ is always positive, but shouldn't you address the case where $g$ is not always positive? (One could make a case to ignore $f(n)=0$ which can cause $f(d)^{\mu(n/d)}$ to be undefined, but negative numbers are perfectly within reason here.) $\endgroup$ – Erick Wong Oct 26 '17 at 6:54
  • 1
    $\begingroup$ I was intentionally vague about the necessary assumptions for the values of $g$, since the OP did not specify what the codomain of $g$ was. In general $g$ could take values in $\mathbb{C}\setminus\{0\}$ and the same argument works if you consider the complex logarithm as a multivalued function, i.e. $\log(r e^{i\theta}) := \{\log r + (\theta+2 k \pi)i \mid k \in \mathbb{Z}\}$. Alternatively, if you are interested only in $g$ taking values in $\mathbb{R}\setminus\{0\}$, then you know the statement is true for $|f|$ and $|g|$. All that remains is to show that the signs agree. $\endgroup$ – posilon Oct 26 '17 at 7:31
  • $\begingroup$ I should probably mention that even more generally, the Möbius inversion formula holds for $g$ taking values in any abelian group. The cases we are discussing are just $(\mathbb{R},+)$, $(\mathbb{R}_{>0},\cdot)$, $(\mathbb{R}\setminus\{0\},\cdot)$ and $(\mathbb{C}\setminus\{0\},\cdot)$. $\endgroup$ – posilon Oct 26 '17 at 7:49
1
$\begingroup$

The Mobius inversion formula states that for sequences $\{f_n\}_{n \geq 1}$ and $\{g_n\}_{n \geq 1}$, if $f_n = \Sigma_{d|n}g_d$, then $g_n = \Sigma_{d|n}\mu(\frac{n}{d})f_d$. There is a nice proof of this in Wilf's book Generatingfunctionology, which should be available as a free PDF file.

I think what the other logarithm based answers are saying is correct, that your version can be reduced to the form above by taking logarithms, and then applying the Mobius inversion formula, and exponentiating at the end to get your RHS. That is,

Taking logarithms (to your LHS), ${\text log\ } f_n = \Sigma_{d|n}{\text log\ } g_d$. By the inversion formula referenced above, $${\text log\ }g_n = \Sigma_{d|n}\mu(\frac{n}{d}){\log\ }f_d = \Sigma_{d|n}{\text log }f_d^{\mu(\frac{n}{d})}$$ and then exponentiating, $g_n = \Pi_{d|n}f_d^{\mu(\frac{n}{d})}$.

The comments to @posilon 's answer give some additional clarification about making sure the operations are defined: I'm just giving detail on the basic steps and don't have anything to add regarding those subtleties.

$\endgroup$

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.