An efficient algorithm for summing values of arithmetic functions

Arithmetic functions are a special class of functions that map from the positive integers into a subset of the complex numbers. In this talk, we will focus on a particular arithmetic function called the Moebius function. The Moebius function, mu(n), is always equal to ±1 or 0, depending on the prime factorization of the input n. One reason that the Moebius function is of interest to mathematicians is because it is connected to a famous unsolved problem in number theory called the Riemann Hypothesis. In a recent paper with Harald Helfgott, we devised a new elementary algorithm for summing mu(n) for all integers n in intervals [1,x] in time about O(x^{3/5}). Previous algorithms took time about O(x^{2/3}). Our paper gave the first improvement in the exponent of x for this type of algorithm since 1985. In this talk, we will give a friendly discussion of some of the ideas that go into the proof of our algorithm. We will also describe some of the computational aspects of the problem, demonstrating that we can break previous records for summing mu(n) using these new ideas. Much of our work can be adapted to efficiently sum values of other arithmetic functions.