Does the Mobius Inversion Theorem hold when sum function is over multiples instead of divisors

466 Views Asked by At

Does the Mobius Inversion Theorem hold when the sum function is over multiples instead of divisors.

Formally, are the following two expressions equivalent:

$$ f(n) = \sum_{k:n|k}h(k) * \mu\left(\frac{k}{n}\right) $$

and

$$ h(n) = \sum_{k:n|k}f(k) $$


I encountered this while solving a problem which had $h$ as:

$$ h(k) = \left\lfloor\frac{\alpha}{k}\right\rfloor \left\lfloor\frac{\beta}{k}\right\rfloor $$

where $\alpha$ and $\beta$ are constants

Specifically in that problem I had the following expression: $$ F(g) = \sum_{k:g|k}\mu\left(\frac{k}{g}\right)h(k)\tag{1} $$

Then I assumed that Mobius Inversion Theorem holds when sum function is over multiples, to get:

$$ h(g) = \sum_{k:g|k}F(k) $$

which gives me:

$$ F(g) = \left\lfloor\frac{n}{g}\right\rfloor\left\lfloor\frac{m}{g}\right\rfloor - \sum_{k:g|k, k \neq g}F(k)\tag{2} $$

I wrote this code(C++) to check whether $(1)$ and $(2)$ are equivalent, and it seems that they are.

1

There are 1 best solutions below

0
On BEST ANSWER

Let's assume that all functions considered are decaying fast enough (we will be a bit more explicit with what "fast enough" is below) that we need not worry about convergence and the validity of reordering the sums. For such functions, let's define

$$S(f) \colon n \mapsto \sum_{k : n\mid k} f(k) = \sum_{m = 1}^{\infty} f(m\cdot n)$$

and

$$M(f) \colon n \mapsto \sum_{k : n\mid k} \mu\biggl(\frac{k}{n}\biggr) f(k) = \sum_{m = 1}^{\infty} \mu(m) f(m\cdot n).$$

Then we have indeed $M(S(f)) = f = S(M(f))$. The key is, as for the usual Möbius inversion, that

$$\sum_{d \mid n} \mu(d) = \begin{cases} 1 &, n = 1 \\ 0 &, n > 1. \end{cases}$$

With that, we calculate

\begin{align} M(S(f))(n) &= \sum_{m = 1}^{\infty} S(f)(mn) \\ &= \sum_{m = 1}^{\infty} \sum_{k = 1}^{\infty} \mu(k)f(kmn) \\ &= \sum_{r = 1}^{\infty} \Biggl(\sum_{k \mid r} \mu(k)\Biggr) f(rn) \\ &= f(n) \end{align}

and similarly

\begin{align} S(M(f))(n) &= \sum_{k = 1}^{\infty} \mu(k)M(f)(kn) \\ &= \sum_{k = 1}^{\infty} \sum_{m = 1}^{\infty} \mu(k)f(kmn) \\ &= \sum_{r = 1}^{\infty} \Biggl(\sum_{k \mid r} \mu(k)\Biggr) f(rn) \\ &= f(n). \end{align}

In your example, we have $h(k) = 0$ for $k > c := \min\: \{\lvert\alpha\rvert,\, \lvert\beta\rvert\}$, and hence also $F(k) = 0$ for $k > c$, so we are effectively dealing with finite sums and no convergence problems arise. In general, the reordering is certainly legitimate if

$$\sum_{k = 1}^{\infty} \sum_{m = 1}^{\infty} \lvert \mu(k) f(kmn)\rvert = \sum_{r = 1}^{\infty} \Biggl(\sum_{k \mid r} \lvert \mu(k)\rvert\Biggr) \lvert f(rn)\rvert < +\infty$$

for every $n$, and that is the case if

$$\sum_{n = 1}^{\infty} \tau(n)\lvert f(n)\rvert < +\infty,$$

where $\tau(n)$ is the number of divisors of $n$.

We note that essentially the same computation shows that - under suitable conditions - the generalised Möbius inversion formula

$$h(x) = \sum_{m = 1}^{\infty} f\bigl(x\cdot c(m)\bigr) \iff f(x) = \sum_{m = 1}^{\infty} \mu(m) h\bigl(x \cdot c(m)\bigr)$$

holds for every non-constant completely multiplicative function $c$. The case $c(m) = \dfrac{1}{m}$ is famous.