Lola Thompson

Summing mu(n): an even faster elementary algorithm

We present a new elementary algorithm for computing M(x), the sum of mu(n) for n up to x (where mu(n) is the Moebius function). Our algorithm takes roughly O(x^{3/5}) time and O(x^{3/10}) space, which improves on existing combinatorial algorithms. While there is an analytic algorithm due to Lagarias-Odlyzko with computations based on the 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.