Möbius inversion formula?

257 Views Asked by At

If i have two arithmetic functions F and G such as: $$ F(n)= \sum_{d | n} G(d,n)$$ where $G$ depends on the divisors of $n$ and $n$. And where $n \leq m$ where $m$ is a fixed positive integer. Can I use the Möbius inversion formula for $n \leq m$ ? I think yes we can. But i would like to know if we can applied Möbius inversion formula because it's a simple consequence of the Möbius inversion formula (where $n \in \mathbb{N}^*$) or a consequence of the generalization explained here: https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula#Generalizations (That is named also Rota inversion formula)

Thanks for your answers.

1

There are 1 best solutions below

1
On BEST ANSWER

Generally, things work in this way. For every $d \mid n$, you should define $f(d, n), g(d, n) $. Then $$(*) \ \ f(m, n) =\sum_{m \mid d \mid n} g(d, n) $$ Holds for every $m \mid n$ iff $$g(m, n) =\sum_{m \mid d \mid n} \mu(d/m) f(d, n) $$ Holds for every $m \mid n$. This is just a matter of arranging terms in a proper way: it is a combinatorial fact.

If you want to invert the equation, you should: 1. Extend your $f$ to $\bar{f} $, such that $\bar{f}(1,n)=f(n) $; 2. Verify that for all $m \mid n$ the equation $(*) $ holds.

Remark. Normally, you have both $f, g$ one-variable functions. The two steps I told you are made in this way:

  1. Set $\bar{f}(m, n) =f(n/m), \bar{g} (m, n) =g(n/m) $.
  2. If the equation $(*) $ is satisfied just for $m=1$, then $$ \bar{f}(m, n) =f(n/m) =\sum_{d\mid n/m} g(n/md) =\sum _ {m \mid d' \mid n} g(n/d') = \sum _{ m \mid d' \mid n} \bar{g} (d', n) $$ It holds for every $m$.