Summing \mu(n): a faster elementary algorithm

DOI10.1007/S40993-022-00408-8MaRDI QIDQ6358759arXivFDO

Authors Harald A. Helfgott, Lola Thompson

Publication date 21 January 2021

Published in arXiv

Full work available at URL https://doi.org/10.1007/S40993-022-00408-8

Mathematics Subject Classification ID

Arithmetic functions; related numbers; inversion formulas (11A25) Continued fractions and generalizations (11J70) Number-theoretic algorithms; complexity (11Y16)

arXiv classification

math.NT

Abstract: We present a new elementary algorithm that takes [ mathrm{time} O_epsilonleft(x^{frac{3}{5}} (log x)^{frac{3}{5}+epsilon} ight) mathrm{and} mathrm{space} Oleft(x^{frac{3}{10}} (log x)^{frac{13}{10}} ight)] for computing $M(x)=su{m}_{nleqx}mu(n),$ where $mu(n)$ is the M"{o}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}(logx{)}^{5/3})$ by the use of (Helfgott, 2020; arxiv.org:1712.09130), at the cost of letting time rise to the order of $x^{3/5}(logx)$.

This page was built for publication: Summing $\mu(n)$: a faster elementary algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6358759)