March 8, 2019, 3:30pm, Wean 8220

Harald Helfgott, University of Gottingen

Summing $\mu(n)$: a better elementary algorithm

Harald Helfgott, University of Gottingen

Summing $\mu(n)$: a better elementary algorithm

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\"obius 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\'eglise-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.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.