Title: Summing $\mu(n)$: a better elementary algorithm
Speaker: Harald Helfgott (University of Göttingen and CRNS)
Abstract: Consider either of two related problems: determining the precise number $\pi(x)$ of prime numbers $p\leq x$, and computing the Mertens function $M(x) = \sum_{n\leq x} \mu(n)$, where $\mu$ is the Möbius function. The two best algorithms known are the following: An analytic algorithm (Lagarias-Odlyzko, 1987), with computations based on integrals of $\zeta(s)$; its running time is $O(x^{1/2+\epsilon})$. A more elementary algorithm (Meissel-Lehmer, 1959 and Lagarias-Miller-Odlyzko, 1985; refined by Deléglise-Rivat, 1996), with running time about $O(x^{2/3})$. The analytic algorithm had to wait for almost 30 years to receive its first rigorous, unconditional implementation (Platt), which concerns only the computation of $\pi(x)$. Moreover, in the range explored to date ($x\leq 10^{24}$), the elementary algorithm is faster in practice. We present a new elementary algorithm with running time about $O(x^{3/5})$ for computing $M(x) = \sum_{n\leq x} \mu(n)$. The algorithm should be adaptable to computing $\pi(x)$ and other related problems. (joint with L. Thompson)
Seminar URL: https://research.math.osu.edu/numbertheory/
