zbMATH — the first resource for mathematics

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
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).

11Y35 Analytic computations
11Y16 Number-theoretic algorithms; complexity
11N05 Distribution of primes
Zbl 0817.11062
[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
[6] Klinger A., Optimizing Methods in Statistics pp 303– (1971)
[7] Lagarias J. C., J. of Algorithms 4 pp 173– (1987) · Zbl 0622.10027
[8] Lehman R. S., Math. Comp. 14 pp 311– (1960)
[9] DOI: 10.1515/crll.1832.9.105 · ERAM 009.0333cj
[10] Neubauer G., Numer. Math. 5 pp 1– (1963) · Zbl 0111.04702
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.