Summing $\mu(n)$: an even faster elementary algorithm
Lola Thompson (Utrecht University)
Abstract: We present a new-and-improved elementary algorithm for computing $M(x) = \sum_{n \leq x} \mu(n),$ where $\mu(n)$ is the Moebius function. Our algorithm takes time $O\left(x^{\frac{3}{5}} \log \log x \right)$ and space $O\left(x^{\frac{3}{10}} \log x \right)$, which improves on existing combinatorial algorithms. While there is an analytic algorithm due to Lagarias-Odlyzko with computations based on integrals of $\zeta(s)$ that only takes time $O(x^{1/2 + \epsilon})$, our algorithm has the advantage of being easier to implement. The new approach roughly amounts to analyzing the difference between a model that we obtain via Diophantine approximation and reality, and showing that it has a simple description in terms of congruence classes and segments. This simple description allows us to compute the difference quickly by means of a table lookup. This talk is based on joint work with Harald Andres Helfgott.
algebraic geometrynumber theory
Audience: researchers in the topic
( slides )
Series comments: To receive announcements by email, add yourself to the nt mailing list.
Organizers: | Edgar Costa*, Siyan Daniel Li-Huerta*, Bjorn Poonen*, David Roe*, Andrew Sutherland*, Robin Zhang*, Wei Zhang*, Shiva Chidambaram* |
*contact for this listing |