Date/heure
12 mai 2022
14:30 - 15:30
Lieu
Salle Döblin
Oratrice ou orateur
Lola Thompson (Université de Utrecht)
Catégorie d'évènement Analyse et théorie des nombres
Résumé
We present a new elementary algorithm for computing $M(x) = \sum_{n \leq x} \mu(n),$ where $\mu(n)$ is the Möbius function. Our algorithm takes
\[\begin{aligned}
\mathrm{time} \ \ O_\epsilon\left(x^{\frac{3}{5}} (\log x)^{\frac{3}{5}+\epsilon} \right)
\ \ \mathrm{and}\ \ \mathrm{space} \ \ O\left(x^{\frac{3}{10}} (\log x)^{\frac{13}{10}}
\right)\end{aligned},\] which improves on existing combinatorial algorithms. While there is an analytic algorithm due to Lagarias-Odlyzko with computations based on the integrals of $\zeta(s)$ that only takes time $O(x^{1/2 + \epsilon})$, our algorithm has the advantage of being easier to implement. The new approach roughly amounts to analyzing the difference between a model that we obtain via Diophantine approximation and reality, and showing that it has a simple description in terms 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 Andrés Helfgott.