Summing $\mu(n)$: an even faster elementary algorithm

Lola Thompson (Utrecht University)

08-Dec-2020, 21:30-22:30 (3 years ago)

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 )


MIT number theory seminar

Series comments: To receive announcements by email, add yourself to the nt mailing list.

Past semesters

Organizers: Edgar Costa*, Siyan Daniel Li-Huerta*, Bjorn Poonen*, David Roe*, Andrew Sutherland*, Robin Zhang*, Wei Zhang*, Shiva Chidambaram*
*contact for this listing

Export talk to