BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Lola Thompson (Utrecht University)
DTSTART:20201208T213000Z
DTEND:20201208T223000Z
DTSTAMP:20260423T130251Z
UID:MITNT/17
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/MITNT/17/">S
 umming $\\mu(n)$: an even faster elementary algorithm</a>\nby Lola Thompso
 n (Utrecht University) as part of MIT number theory seminar\n\n\nAbstract\
 nWe present a new-and-improved elementary algorithm for computing $M(x) = 
 \\sum_{n \\leq x} \\mu(n)\,$ where $\\mu(n)$ is the Moebius function. Our 
 algorithm takes time $O\\left(x^{\\frac{3}{5}} \\log \\log x \\right)$ and
   space $O\\left(x^{\\frac{3}{10}} \\log x \\right)$\, which improves on e
 xisting combinatorial algorithms. While there is an analytic algorithm due
  to Lagarias-Odlyzko with computations based\non integrals of $\\zeta(s)$ 
 that only takes time $O(x^{1/2 + \\epsilon})$\, our algorithm has the adva
 ntage of being easier to implement. The new approach roughly amounts to an
 alyzing the difference between a model that we obtain via Diophantine appr
 oximation and reality\, and showing that it has a simple description in te
 rms 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.\n
LOCATION:https://researchseminars.org/talk/MITNT/17/
END:VEVENT
END:VCALENDAR