3
$\begingroup$

Let $f(n)$ be a multiplicative function that is not completely multiplicative, i.e $f(m)\cdot f(n)= f(m\cdot n)$ only if $gcd(m,n)=1$. Let $S(x)$ be the double sum over $f$, that is:

$$S(x)=\sum_{i=1}^x\sum_{j=1}^xf(i\cdot j)$$

It is not difficult to see that if $f(n)$ were completely multiplicative, then $S(x)$ could be simplified:

$$S(x)=\sum_{i=1}^x\sum_{j=1}^xf(i\cdot j)= \sum_{i=1}^xf(i)\sum_{j=1}^xf(j)= \biggl(\sum_{k=1}^xf(k)\biggr)^2$$

But since $f(n)$ is not completely multiplicative, this simplification is not completely true, and it fails in every combination where $gcd(i,j)\neq1$. Hence, $S(x)$ can be written this way provided we add some additional error term, let's call it $E$:

$$S(x)=\sum_{i=1}^x\sum_{j=1}^xf(i\cdot j)= \biggl(\sum_{k=1}^xf(k)\biggr)^2+E$$

$E$ is either negative or positive, I'm not sure. Obviously, $E$ is comprised of all the small errors generated by the initial sum term, when $gcd(i,j)\neq1$. I am mainly interested in the cases where $f(n)$ takes the form of:

  1. Euler totient function: $$S_{\varphi}(x)=\sum_{i=1}^x\sum_{j=1}^x\varphi(i\cdot j)$$
  2. Sum of divisors function: $$S_{\sigma_1}(x)=\sum_{i=1}^x\sum_{j=1}^x\sigma_1(i\cdot j)$$
  3. Moebius function: $$S_{\mu}(x)=\sum_{i=1}^x\sum_{j=1}^x\mu(i\cdot j)$$

My question is, what is this error term $E$ exactly? how can I calculate it? How can I properly sum all those small errors to get a correct evaluation of $S(x)$? For clarification, I am concerned with evaluating $S(x)$, but I think I must evaluate $E$ first in order to do it. I am taking this approach because I can compute $\biggl(\sum_{k=1}^xf(k)\biggr)^2$ very efficiently, and so, finding the error term $E$ will solve my question.

$\endgroup$
1
11
$\begingroup$

One underappreciated but useful fact about multiplicative functions is the following: if $f(n)$ is multiplicative, and $k$ is any positive integer such that $f(k)\ne0$, then the function $g(n) = f(nk)/f(k)$ is a multiplicative function of $n$. (You'll get the proof correct on the first try.) In particular, we can write \begin{align*} \sum_{m\le x} \sum_{n\le x} f(mn) &= \sum_{m\le x} f(m) \sum_{n\le x} \frac{f(mn)}{f(m)} \end{align*} and use whatever techniques we want for sums of multiplicative functions on the inner sum. Using the Euler totient function as an example (quickly sketching the computation here): \begin{align*} \sum_{m\le x} \sum_{n\le x} \phi(mn) &= \sum_{m\le x} \phi(m) \sum_{n\le x} \frac{\phi(mn)}{\phi(m)} \\ &= \sum_{m\le x} \phi(m) \sum_{n\le x} \sum_{\substack{d\mid n \\ (d,m)=1}} \mu(d) \frac nd \\ &= \sum_{m\le x} \phi(m) \sum_{\substack{d\le x \\ (d,m)=1}} \frac{\mu(d)}d \sum_{\substack{n\le x \\ d\mid n}} n \\ &= \sum_{m\le x} \phi(m) \sum_{\substack{d\le x \\ (d,m)=1}} \mu(d) \sum_{m\le x/d} m \\ &\sim \sum_{m\le x} \phi(m) \sum_{\substack{d\le x \\ (d,m)=1}} \mu(d) \frac12 \bigg( \frac xd \bigg)^2 \\ &\sim \frac{x^2}2 \sum_{m\le x} \phi(m) \sum_{\substack{d\in\Bbb N \\ (d,m)=1}} \frac{\mu(d)}{d^2} \\ &= \frac{x^2}2 \frac1{\zeta(2)} \sum_{m\le x} \phi(m) \prod_{p\mid m} \bigg( 1-\frac1{p^2} \bigg)^{-1} \\ &= \frac{3x^2}{\pi^2} \sum_{m\le x} m \prod_{p\mid m} \frac p{p+1} \\ &\sim \frac{3x^2}{\pi^2} \frac{x^2}2 \prod_{p} \bigg( 1-\frac1p \bigg) \bigg( 1+ \frac p{p+1} \frac1p+ \frac p{p+1} \frac1{p^2} + \cdots \bigg) \\ &\sim \frac{3x^4}{2\pi^2} \prod_{p} \bigg( 1-\frac1{p(p+1)} \bigg) \approx 0.107062 x^4 \end{align*} which is a good fit with experimental data.

$\endgroup$
8
  • $\begingroup$ Thank you very much for your answer. Different forms $f$ can take involve additional approaches for simplifying the sum, as can be shown from your $\phi$ example. Following on your excellent explanation, I am trying to extend this to the sum of divisors function, $\sigma(m\cdot n)$. Summing the divisors of different $n\leq x$ can be simplified greatly by running the sum over the divisors rather than the numbers themselves, with each divisor repeating $\lfloor \frac xd \rfloor$ times. This gives $\sum_{d=1}^x d\cdot \lfloor \frac xd \rfloor$. Can you show how this fits into your observation? $\endgroup$ – MC From Scratch May 31 '19 at 10:01
  • $\begingroup$ The reason I am interested in this, is that $\sum_{d=1}^x d\cdot \lfloor \frac xd \rfloor$ has an $O(n^{1/2+\epsilon})$ computation, using Dirichlet convolution. $\endgroup$ – MC From Scratch May 31 '19 at 10:02
  • $\begingroup$ The key starting step (very often, in my mind) is to find a way to write the multiplicative function $f(n)$ as $\sum_{d\mid n} g(d)$, then switch the order of summation to get $\sum_{n\le x} f(n) = \sum_{d\le x} g(d) \lfloor x/d\rfloor$. When $f=\sigma$ it's very easy, since $\sigma(n) = \sum_{d\mid n} g(d)$ with $g(d)=d$; that's how the formula from your comment is proved. When $f(n) = \sigma(mn)/\sigma(m)$, the corresponding formula is $f(n) = \sum_{d\mid n} g(d)$ with $g(d) = d\prod_{p^k\|m,\,p\mid d} (1-(p^k-1)/(p^{k+1}-1))$ (found by looking at prime power inputs). $\endgroup$ – Greg Martin May 31 '19 at 17:39
  • $\begingroup$ Also, the first line of the sum gives a different result from the 2nd line and forth. I tried both paper and computer calculations (which were the same, but differed between the first and second lines of the sum). For example, when $f=\sigma$, $S(5)$ results in $401$ on the first line, but $210$ on the second/third/fourth lines. Might there be a mistake? $\endgroup$ – MC From Scratch May 31 '19 at 18:26
  • $\begingroup$ Sorry, 1st/2nd/etc. lines of what? $\endgroup$ – Greg Martin May 31 '19 at 18:51

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.