We present a new elementary algorithm for computing the Mertens function, which improves on existing combinatorial algorithms. While there is an analytic algorithm due to Lagarias-Odlyzko with computations based on the integrals of ζ(s), our algorithm has the advantage of being easier to implement. The new approach roughly amounts to analysing 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 Andrés Helfgott.
This video is part of the Webinar in Additive Combinatorics series, and this is their YouTube channel.
