2
$\begingroup$

$f(n)$ is a multiplicative function, meaning $f(m\cdot n)=f(m)\cdot f(n)$.

I want to evaluate the sum: $$(1)\qquad\sum_{k=1}^{n}f(m\cdot k)$$ over a fixed $m$. Because $f$ is multiplicative, I can rewrite the sum as: $$(2)\qquad\sum_{k=1}^{n}f(m)\cdot f(k)$$ And because $m$ is fixed, I thought this sum is equal to: $$(3)\qquad f(m)\cdot \sum_{k=1}^{n} f(k)$$ But it's not, as simple paper & pencil check shows. I can easily evaluate the sum $\sum_{k=1}^{n} f(k)$, so I tried to rewrite $(2)$ in terms of it.

For example, suppose $f(n)$ is Euler's totient function, $\varphi(n)$, known as the amount of numbers $<n$ that are comprime to $n$. Suppose $m=4$ and I want to evaluate the sum up to $k=3$, that is $\sum_{k=1}^{3}\varphi(4\cdot k)$. The true sum would be written as $(1)$ & $(2)$ respectively as: $$\varphi(4)+\varphi(8)+\varphi(12) = \varphi(4)\cdot \varphi(1)+\varphi(4)\cdot \varphi(2)+\varphi(4)\cdot \varphi(3) = 10$$

In my wrong approach, the sum would be:

$$\varphi(m)\cdot \sum_{k=1}^{n} \varphi(k)=\varphi(4)\cdot \biggl(\varphi(1)+\varphi(2)+\varphi(3)\biggl)= 2\cdot \space (1+1+2)=8$$ which is different than the original sum. I've noticed this is also true if $f(n)$ is the sum of divisors function too $\sigma_1(n)$, and other multiplicative functions as well.

My question is how can I rewrite $(2)$ in terms of $\sum_{k=1}^{n} f(k)$ or perhaps in another way too, and why is my approach wrong?

Thanks.

$\endgroup$
  • 1
    $\begingroup$ Can you please elaborate on: "But it's not, as simple paper & pencil check shows" Which function $f$ (or which $m$) did you choose? $\endgroup$ – Viktor Glombik Apr 29 at 12:58
  • 1
    $\begingroup$ Is it possible, Matan, that you are comfusing "multiplicative functions" and "completely multiplicative functions"? $\endgroup$ – Gerry Myerson Apr 29 at 13:11
  • $\begingroup$ I think the functions I am talking about are not completely multiplicative, but rather merely multiplicative. @GerryMyerson $\endgroup$ – Matan Apr 29 at 13:16
  • 2
    $\begingroup$ In that case, you don't always have $f(mn)=f(m)f(n)$ – you're only guaranteed that when $\gcd(m,n)=1$. $\endgroup$ – Gerry Myerson Apr 29 at 13:18
  • 2
    $\begingroup$ (3) and (2) are equivalent, providing $f$ is completely multiplicative (which precisely means $f(mn)=f(m)f(n)$ for all $m,n$). The totient function is multiplicative, but not completely multiplicative. $\endgroup$ – Gerry Myerson Apr 29 at 13:25
1
$\begingroup$

The reason you get 8 is a failure of mind: $$2\cdot(1+2+2)=2\cdot 5=10\neq8$$

but $\varphi(2)=1$ , so this sum is completely invalidated.

if not completely multiplicative, as has been talked about, this isn't always going to hold up though. In fact it fails any time $n\geq (p\mid m)$

$\endgroup$
  • $\begingroup$ Thanks, I correct it. But if $f(n)$ is only multiplicative and not completely multiplicative, then how can I perform the summation? What "phrase" would I need to add/subtract from $(3)$ to make it correct? $\endgroup$ – Matan Apr 29 at 14:31
  • $\begingroup$ I don't even think one case easily make a sum you could subtract. $\endgroup$ – Roddy MacPhee Apr 29 at 14:59
1
$\begingroup$

Let $f$ be multiplicative, but not completely multiplicative, and consider $\sum_{k=2}^2f(2k)$ This is, of course, $f(4)$, and you are asking for a way to modify $(f(2))^2$ to get $f(4)$, or to write $f(4)$ in terms of $f(2)$. This is clearly impossible, since no matter what $f(2)$ is, $f(4)$ could be anything. Multiplicativity is not enough to get an answer to the question you are asking.

$\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.