Lola Thompson Université d'Utrecht, Pays-Bas

Summing μ(n): a faster elementary algorithm

We present a new elementary algorithm for computing M(x) = Σ_{n ≤ x} μ(n), where μ(n) is the Möbius function.
Our algorithm takes time O_ε(x^3/5 (log x)^{3/5 + ε}) and space O(x^3/10 (log x)^13/10) which improves on existing
combinatorial algorithms. While there is an analytic algorithm due to Lagarias-Odlyzko with computations
based on the integrals of ζ(s) that only takes time O(^{1/2 + ε}), 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
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 Andrés Helfgott.