Computations of the Mertens Function and Improved Bounds on the Mertens Conjecture

The Mertens function is defined as $M(x)={\sum }_{n\le x}\mu (n)$, where $\mu (n)$ is the M"obius function. The Mertens conjecture states $\mathrm{\mid }M(x)\mathrm{/}\sqrt{x}\mathrm{\mid }<1$ for $x>1$, which was proven false in 1985 by showing $\mathrm{lim\hspace{0.17em}inf}M(x)\mathrm{/}\sqrt{x}<-1.009$ and $\mathrm{lim\hspace{0.17em}sup}M(x)\mathrm{/}\sqrt{x}>1.06$. The same techniques used were revisited here with present day hardware and algorithms, giving improved lower and upper bounds of $-1.837625$ and $1.826054$. In addition, $M(x)$ was computed for all $x\le {10}^{16}$, recording all extrema, all zeros, and ${10}^8$ values sampled at a regular interval. Lastly, an algorithm to compute $M(x)$ in $O(x^{2\mathrm{/}3+\epsilon })$ time was used on all powers of two up to $2^{73}$.