5
$\begingroup$

There is a very simple proof for Möbius inversion formula through convolution:

If $A$ is a UFD and $B$ is a ring, $f,g:A\rightarrow B$ two functions, then

$$(f\ast g)(n) = \sum_{k\cdot l = n}f(k)\cdot g(l)$$ makes the set of functions into a ring with identity $\delta_1$.

In this case the Möbius function, assigning 0 to every $n\in A$ which is not square free, 1 to square free elements which are the products of an even number of primes and -1 to square free products of odd number of primes, is an inverse of the constant function 1. Then the Möbius inversion formula

$$f(n) = \sum_{d|n} g(d)\Longrightarrow g(n) = \sum_{d|n}f(d)\mu\left(\frac{n}{d}\right)$$

is simply another way of writing

$$f = g\ast 1\Longrightarrow g = f\ast \mu.$$

Is there a similarly general and elegant approach to the multiplicative formula

$$f(n) = \prod_{d|n}g(d)\Longrightarrow g(n) = \prod_{d|n} f(d)^{\mu(n/d)}?$$

Thank you.

  • 0
    I think they are the exact same theorem (no new proof needed), written in multiplicative notation rather than additive.2012-10-27
  • 0
    That does not seem to be the case, since in order to define the convolution you seem to need two different operations in $B$, and while fingin the inverse of the constant function $f\equiv 1$ both neutral elements 0 and 1 play a role. I didn't manage to define the convolution of functions into a group (rather than a ring).2012-10-28

1 Answers 1

4

Of course there is: $$\tag1 \ln f=\ln g *1\Rightarrow \ln g=\ln f *\mu.$$

At least this works if we can take logarithms in $B$. Otherwise, we need to switch to a different ring:

Assume $B$ is a commutative ring with unity. Let $C$ be the set of permutations maps $\sigma \colon B^\times\to B^\times$ of the units with $\sigma(1)=1$. Then $C$ is a ring with pointwise multiplication as addition, with composition as multiplication, identity as one and $x\mapsto 1$ as zero. Moreover, we can map $\mathbb Z\to C$ via $n\mapsto(x\mapsto x^n)$ and consider $B^\times$ as a subset of $C$ via $b\mapsto(x\mapsto b x)$. Now if $f,g\colon A\to B$ are two functions with range actually in $B^\times\subseteq C$, then $f=g*1\Rightarrow g=f*\mu$ is the multiplicative inversion formula $$\tag2 f(n)=\prod_{d|n}g(d)\Rightarrow g(n)=\prod_{d|n}f(d)^{\mu(\frac nd)}.$$

What can be done if the ranges of $f,g$ are not contained in $B^\times$? Then let us hope that $B$ is at least an integral domain and replace $B$ with its quotient field.

Your specific example is with polynomials, i.e. the integral domain $\mathbb Z[X]$, so the above steps work fine. In that specific case, maybe the following is more intuitive: We can interprete polynomials as functions $\mathbb C\to \mathbb C$. Outside their roots, we can take (multivalued) logarithm, thus can apply $(1)$ pointwise and obtain the conclusion in $(2)$ pointwise for all but finitely many points $\in\mathbb C$, hence $(2)$ also as a whole.

  • 0
    I thought about this, but what is $\ln$ or $\exp$? How does one define an exponent or a logorithm of a polynomial?2012-10-27
  • 0
    To clarify: if $\Phi_n$ is the $n$-th cyclotomic polynomial, then we have $x^n-1 = \prod_{d|n}\Phi_d$ and I want to reverse this. Formal calculation with logs and exponentials is not a problem, but I don't know how to define them on a ring of polynomials. Also, the result involves $(x^d - 1)^{\mu(n/d)}$ and that means an inverse for some $d$. That is also problematic.2012-10-27
  • 1
    @Artem: I've tried to "un-handwave" that case.2012-10-27
  • 0
    Thank you. This is very interesting! I'll try and work out the details. I considered treating them as functions as well, but would the "multivaluedness" of the logarithm not cause problems there?2012-10-28
  • 0
    @Artem: Yes and no. Everything sorts out after de-logarithmizing. Thus *formally*, the approach via units in the quotient field may be more satisfactory (and general).2012-10-28
  • 0
    @Artem: Why is the set of permutations $C$ a ring? Composition of permutations is a permutation, so thats fine. But is it even closed under the addition you define?2016-07-07