12

As far as I know, there is one way currently known to -- in principle -- compute the Mertens function $M(x) = \sum_{n\leq x} \mu(n)$ in time essentially $O\left(x^{1/2}\right)$, namely, a modification of the Lagarias-Odlyzko method.

Mertens' function in time $O(\sqrt x)$

Computing the Mertens function

The Lagarias-Odlyzko method's main variant is designed to compute $\pi(x)$ in time essentially $O(x^{1/2})$. In the last few years, it has been implemented and optimized:

https://arxiv.org/abs/1203.5712

https://arxiv.org/abs/1410.7008

http://www.ams.org/journals/mcom/2017-86-308/S0025-5718-2017-03038-6/home.html

Has the analogue for computing $M(x)$ ever been implemented? If not, why not? Are there significant ways in which this variant of Lagarias-Odlyzko would be much slower or harder to implement than the version for $\pi(x)$?

(One guess is that evaluating residues of $1/\zeta(s)$ may be hard. I know that this is a difficulty when one tries to obtain explicit forms of analytic results on $M(x)$, but I do not know whether the issue is at all relevant to Lagarias-Odlyzko and similar computational methods.)

H A Helfgott
  • 19,290
  • Not an answer, but it isn't too hard to compute the number of squarefrees, $\sum_{n\leq x} |\mu (n)|$, in time $x^{1/2 -\delta}$ for $\delta >0$. But I don't know any improvement for the Merten's function itself beyond Lagarias-Odlyzko. – Mark Lewko Apr 14 '18 at 17:28
  • Not surprising given that $\sum_{n\leq x} |\mu(n)| = \sum_{d\leq \sqrt{x}} \mu(d) \lfloor x/d^2\rfloor$; we can of course use the fact $\lfloor x/d^2\rfloor$ is constant on long intervals for $d$ close to $\sqrt{x}$. But what method precisely are you proposing? (And what is the current record? $x^{1/3}$?) – H A Helfgott Apr 15 '18 at 19:47
  • 2
    The best result I'm aware of is $x^{1/3+\epsilon}$ due to Johan Andersson on the Mathoverflow thread: https://mathoverflow.net/questions/95726/mertens-function-in-time-o-sqrt-x?noredirect=1&lq=1. – Mark Lewko Apr 15 '18 at 20:05
  • I'd say the first thing to note is that $\sum_{n=1}^N M(N/n) = 1$ and for a fixed $N$, $\lfloor \frac{N}{n} \rfloor$ takes about $2\sqrt{N}$ different values as $n$ varies – reuns Aug 28 '18 at 22:43
  • @MarkLewko: you mean time $O(x^{1/3+\epsilon})$ for computing $\sum_{n\leq N} |\mu(n)|$. – H A Helfgott Aug 29 '18 at 03:48

0 Answers0