Möbius Inversion for any Arithmetic Function

295 Views Asked by At

My question is whether or not it is valid, (or more importantly, is there any point in doing so?) defining a function $g(n)$ as follows, and if it is, does this mean that all arithmetic functions must have equivalent expressions to one another that involves the Mobius function?

$$\delta \left( x,y \right) =\cases{1&$x=y$\cr 0&$x\neq y$\cr}$$

$$g \left( n \right) =\sum _{k=1}^{n}f \left( k \right) \delta \left( { \frac {n}{k}}, \Bigl\lfloor {\frac {n}{k}} \Bigr\rfloor \right) $$

$$f \left( n \right) =\sum _{k=1}^{n}\mu \left( k \right) g \left( { \frac {n}{k}} \right) \delta \left( {\frac {n}{k}}, \Bigl\lfloor {\frac {n}{k}} \Bigr\rfloor \right) $$

I also don't understand how Möbius inversion applies to any abelian group, and want to know the proof for this. And the proof of Möbius inversion on wikipedia here I am also unclear about, in particular how the author moves from the 3rd to forth line, eliminating the indicator function to arrive at the arithmetic sum of the Möbius function.

1

There are 1 best solutions below

4
On BEST ANSWER

I’m surprised that no one else has answered this before me.

First, your notation $$\delta\left(\frac nk,\left\lfloor\frac nk\right\rfloor \right)$$ simply gives $1$ when $k|n$, $0$ otherwise. Therefore your notation $$\sum_{k=1}^nf(k)\delta\left(\frac nk,\left\lfloor\frac nk\right\rfloor \right)$$ is much more economically written $\sum_{d|n}f(d)$, and the third line simply restates the Möbius Inversion Formula.

I think that the Formula is best understood when translated into the language of arithmetic functions $f:\Bbb N\to\Bbb Z$, (here $\Bbb N$ is the positive integers) where as usual, addition is done pointwise but the “multiplication” is “$*$”, defined by $$(f*g)(n)=\sum_{d|n}f(d)g(n/d)\,.$$ Then, it’s necessary to show associativity of this multiplication, but this poses no problem. There is a neutral element (identity) for $*$, namely $\Bbb I(n)=\delta(1,n)$, the function that’s zero everywhere but at $n=1$. If we define $Z(n)=1$ for all $n\ge1$, then this is an arithmetic function too, and Möbius Inversion says just that if $g=Z*f$, then $f=\mu*g$. Stare at this, and it says that $Z*\mu=\Bbb I$, in other words $\mu$ and $Z$ are inverses of each other.


How now to interpret Möbius to apply to functions from $\Bbb N$ to any abelian group ($\Bbb Z$-module) $M$? Given our module $M$, we can form the set of “$M$-etic functions”, all $F:\Bbb N\to M$, call the set $M^{\Bbb N}$, on which $Z$ acts in the usual way, but also is a module over the set of arithmetic functions (which we can now call $\Bbb Z^{\Bbb N}$). The operation is by the same convolution formula, if $f\in\Bbb Z^{\Bbb N}$ and $F\in M^{\Bbb N}$, then $f*F(n)=\sum_{d|n}f(d)F(n/d)$. You have to verify that $f*(g*F)=(f*g)*F$ and $\Bbb I*F=F$ and $f*(F+G)=f*F+f*G$, and also I guess that $(f+g)*F=f*F+g*F$.

Finally, with this notation out of the way, you get from the hypothesis $G(n)=\sum_{d|n}F(d)$, rewordable as $G=Z*F$, to the conclusion $\mu*G=F$ just by multiplying both sides on the left by the inverse of $Z$, namely $\mu$.

Here’s a nice application, where $M$ is the multiplicative group of nonzero rational functions in a variable $X$, over $\Bbb Z$. Let $n>0$. Then the polynomial $X^n-1$ has for its roots all the $n$-th roots of unity, some of which are primitive $d$-th roots for $d|n$. If we call $\Phi_d$ the polynomial whose roots are the primitive $d$-th roots of unity, we get $\Phi_d(X)\in\Bbb Z[X]$; it’s the $d$-th cyclotomic polynomial. And we have $$X^n-1=\prod_{d|n}\Phi_d(X)\,,$$ and from Möbius Inversion, we get $$\Phi_n(X)=\prod_{d|n}(X^d-1)^{\mu(n/d)}\,.$$