Summing μ(n) : a faster elementary algorithm

Abstract

Abstract We present a new elementary algorithm that takes $ \textrm{time} \ \ O_\epsilon \left( x^{\frac{3}{5}} (\log x)^{\frac{8}{5}+\epsilon } \right) \ \ \textrm{and} \ \textrm{space} \ \ O\left( x^{\frac{3}{10}} (\log x)^{\frac{13}{10}} \right) $ time O ϵ x 3 5 ( log x ) 8 5 + ϵ and space O x 3 10 ( log x ) 13 10 (measured bitwise) for computing $M(x) = \sum _{n \le x} \mu (n),$ M ( x ) = ∑ n ≤ x μ ( n ) , where $\mu (n)$ μ ( n ) is the Möbius function. This is the first improvement in the exponent of x for an elementary algorithm since 1985. We also show that it is possible to reduce space consumption to $O(x^{1/5} (\log x)^{5/3})$ O ( x 1 / 5 ( log x ) 5 / 3 ) by the use of (Helfgott in: Math Comput 89:333–350, 2020), at the cost of letting time rise to the order of $x^{3/5} (\log x)^2 \log \log x$ x 3 / 5 ( log x ) 2 log log x .