Summatory function of the Möbius function. I: Experimental upper bounds. (Fonction sommatoire de la fonction de Möbius. I: Majorations expérimentales.) (French) Zbl 0817.11061

Dress, François

Exp. Math. 2, No. 2, 89-98 (1993).

Let \(\mu (n)\) be the Möbius function and \(M(x)= \sum_{n\leq x} \mu(n)\) (\(\mu(1) =1\), \(\mu(n) =0\) if \(n\) has a square divisor \(>1\), and \(\mu(n) =1\) or \(\mu(n) =-1\) if \(n\) is the product of an even or an odd number of different primes, respectively). The main interest in \(M(x)\) stems from its connection with the Riemann hypothesis: its truth follows from the boundedness of the function \(| M(x)|/ \sqrt{x}\). However, although it has long been thought that \(| M(x)|/ \sqrt{x}< 1\) for \(x>1\), it is generally believed now (but still unproved) that \(| M(x)|/ \sqrt{x}\) tends to infinity with \(x\).
This paper presents the results of systematic numerical computations of \(M(x)\) for all \(x\leq 10^{12}\), thus extending previous computations of Cohen and Dress for \(x\) up to \(7.76\times 10^ 9\). As a result, the upper estimate \(| M(x)| \leq 0.570591 \sqrt {x}\), valid for \(x\in [33, 10^{12}]\), is obtained. Moreover, a table is given of all the (eight) subintervals of \([33, 10^{12}]\) where \(| M(x)| >0.5 \sqrt {x}\). Two algorithms are used for these computations: one for computing \(M(x)\) for an isolated value of \(x\), and a second one for computing \(M(x)\) for many consecutive values of \(x\). For the first algorithm it is proved that the time complexity is \(O (x^{3/4} \log^{1/2} x)\) and the required memory is \(O (x^{1/2})\). For the second algorithm, the time complexity is \(O( x^{1/2}\log \log x)\) if one wants to find extremal values of \(| M(x)|/ \sqrt {x}\) for about \(x^{1/2}\) consecutive values near \(x\).
Remarks. Recently, W. M. Lioen and J. van de Lune (unpublished manuscript. Dec. 1994) have extended the computations of Dress to the bound \(1.7889 \times 10^{13}\), by using vectorized sieving; no new extrema of \(| M(x) |/ \sqrt {x}\) were encountered.
For Part II see the following review (Zbl 0817.11062).

Reviewer: H.J.J.te Riele (Amsterdam)

MSC:

11Y35	Analytic computations
11Y16	Number-theoretic algorithms; complexity
11N05	Distribution of primes

Keywords:

summatory function; Möbius function; numerical computations; algorithms

Citations:

Zbl 0817.11062

References:

[1]	Aho A. V., The Design and Analysis of Computer Algorithms (1974) · Zbl 0326.68005
[2]	Cohen, H. and Dress, F. 1979.”Calcul numérique de Mx)”11–13. [Cohen et Dress 1979], Rapport, de I’ATP A12311 Informatique 1975 du CNRS
[3]	Dress F., Experimental Math. 2 pp 103– (1993)
[4]	El Marraki M., Thèse, in: ”Majorations effectives de la fonction sommatoire de la fonction de Möbius” (1991) · Zbl 0869.11075
[5]	DOI: 10.1007/BF00288933 · Zbl 0278.68030 · doi:10.1007/BF00288933
[6]	Klinger A., Optimizing Methods in Statistics pp 303– (1971) · doi:10.1016/B978-0-12-604550-5.50019-5
[7]	Lagarias J. C., J. of Algorithms 4 pp 173– (1987) · Zbl 0622.10027 · doi:10.1016/0196-6774(87)90037-X
[8]	Lehman R. S., Math. Comp. 14 pp 311– (1960)
[9]	DOI: 10.1515/crll.1832.9.105 · ERAM 009.0333cj · doi:10.1515/crll.1832.9.105
[10]	Neubauer G., Numer. Math. 5 pp 1– (1963) · Zbl 0111.04702 · doi:10.1007/BF01385874
[11]	Odlyzko A., J. reine Angew. Math. 357 pp 138– (1985)
[12]	Pintz J., Astérisque 147 pp 325– (1987)
[13]	Rosser B., Illinois J. of Math. 6 pp 64– (1962)
[14]	Rosser B., Math, of Computation 29 pp 243– (1975)
[15]	Schoenfeld L., Acta Arithmetica 15 pp 221– (1969)