• Dr.
    • Lola Thompson
    • Utrecht University - The Netherlands
    • Number Theory

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.


Lola Thompson is an associate professor (universitair hoofddocent) in the Mathematical Institute at Utrecht University. She also teaches at University College Utrecht, an American-style liberal arts college in the Netherlands. Originally from the United States, she earned bachelor’s degrees in mathematics and economics from the University of Chicago. She went on to receive a master’s degree and a PhD in mathematics from Dartmouth College. She completed her doctoral studies under the direction of Carl Pomerance. Following her PhD, dr. Thompson was an NSF VIGRE postdoc at the University of Georgia, and then she spent seven years on the mathematics faculty at Oberlin College, earning tenure in 2019. She has held visiting research positions at the Max Planck Institute for Mathematics, the Mathematical Sciences Research Institute, and the Hausdorff Institute for Mathematics. dr. Thompson's research is primarily in analytic number theory. Along with Harald Helfgott, she was awarded the 2022 Selfridge Prize in algorithmic number theory. She is currently on the editorial boards of Indagationes Mathematicae and MAA Focus.