Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Computations of the Mertens function and improved bounds on the Mertens conjecture


Author: Greg Hurst
Journal: Math. Comp. 87 (2018), 1013-1028
MSC (2010): Primary 11A25, 11M26, 11Y35, 11Y55, 11Y70
DOI: https://doi.org/10.1090/mcom/3275
Published electronically: November 1, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The Mertens function is defined as $ M(x) = \sum _{n \leq x} \mu (n)$, where $ \mu (n)$ is the Möbius function. The Mertens conjecture states $ \vert M(x)/\sqrt {x}\vert < 1$ for $ x > 1$, which was proven false in 1985 by showing $ \liminf M(x)/\sqrt {x} < -1.009$ and $ \limsup M(x)/\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 \leq 10^{16}$, recording all extrema, all zeros, and $ 10^8$ values sampled at a regular interval. Finally, an algorithm to compute $ M(x)$ in $ O(x^{2/3+\varepsilon })$ time was used on all powers of two up to $ 2^{73}$.


References [Enhancements On Off] (What's this?)

  • [1] E. Kuznetsov, Computing the Mertens function on a GPU (arXiv:1108.0135v1 [math.NT], 31 Jul 2011)
  • [2] Marc Deléglise and Joël Rivat, Computing the summation of the Möbius function, Experiment. Math. 5 (1996), no. 4, 291-295. MR 1437219
  • [3] T. Kotnik and J. van de Lune, Further systematic computations on the summatory function of the Möbius function Report MAS-R0313, CWI Amsterdam (November 2003)
  • [4] D. G. Best and T. S. Trudgian, Linear relations of zeroes of the zeta-function, Math. Comp. 84 (2015), no. 294, 2047-2058. MR 3335903, https://doi.org/10.1090/S0025-5718-2014-02916-5
  • [5] A. M. Odlyzko and H. J. J. te Riele, Disproof of the Mertens conjecture, J. Reine Angew. Math. 357 (1985), 138-160. MR 783538, https://doi.org/10.1515/crll.1985.357.138
  • [6] E. C. Titchmarsh, The Theory of the Riemann Zeta-Function, Oxford, at the Clarendon Press, 1951. MR 0046485
  • [7] A. E. Ingham, On two conjectures in the theory of numbers, Amer. J. Math. 64 (1942), 313-319. MR 0006202, https://doi.org/10.2307/2371685
  • [8] T. Granlund and P. Montgomery, Division by Invariant Integers using Multiplication Proceedings of SIGPLAN `94 Conference on Programming Language Design and Implementation.
  • [9] Richard Sladkey, A Successive Approximation Algorithm for Computing the Divisor Summatory Function (arXiv:1206.3369 [math.NT], Jun 2012) 13-16
  • [10] The FPLLL development team, fplll, a lattice reduction library (available at https://github.com/fplll/fplll) (January 2016)
  • [11] Ivan Morel, Damien Stehlé, and Gilles Villard, H-LLL: using Householder inside LLL, ISSAC 2009--Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2009, pp. 271-278. MR 2742770, https://doi.org/10.1145/1576702.1576740
  • [12] Emil Grosswald, Oscillation theorems of arithmetical functions, Trans. Amer. Math. Soc. 126 (1967), 1-28. MR 0202685, https://doi.org/10.2307/1994409
  • [13] Nathan Ng, The distribution of the summatory function of the Möbius function, Proc. London Math. Soc. (3) 89 (2004), no. 2, 361-389. MR 2078705, https://doi.org/10.1112/S0024611504014741
  • [14] Tadej Kotnik and Jan van de Lune, On the order of the Mertens function, Experiment. Math. 13 (2004), no. 4, 473-481. MR 2118272
  • [15] Manuel Benito and Juan L. Varona, Recursive formulas related to the summation of the Möbius function, Open Math. J. 1 (2008), 25-34. MR 2461512, https://doi.org/10.2174/1874117700801010025
  • [16] J. C. Lagarias and A. M. Odlyzko, Computing $ \pi(x)$: an analytic method, J. Algorithms 8 (1987), no. 2, 173-191. MR 890871, https://doi.org/10.1016/0196-6774(87)90037-X
  • [17] David J. Platt, Computing $ \pi(x)$ analytically, Math. Comp. 84 (2015), no. 293, 1521-1535. MR 3315519, https://doi.org/10.1090/S0025-5718-2014-02884-6

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11A25, 11M26, 11Y35, 11Y55, 11Y70

Retrieve articles in all journals with MSC (2010): 11A25, 11M26, 11Y35, 11Y55, 11Y70


Additional Information

Greg Hurst
Affiliation: Wolfram Research Inc., 100 Trade Center Drive, Champaign, Illinois 61820
Email: ghurst@wolfram.com

DOI: https://doi.org/10.1090/mcom/3275
Keywords: The Mertens function, the Mertens conjecture
Received by editor(s): October 28, 2016
Received by editor(s) in revised form: March 4, 2017
Published electronically: November 1, 2017
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society