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

### MSC:

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

Zbl 0817.11062
Full Text:

### References:

  Aho A. V., The Design and Analysis of Computer Algorithms (1974) · Zbl 0326.68005  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  Dress F., Experimental Math. 2 pp 103– (1993)  El Marraki M., Thèse, in: ”Majorations effectives de la fonction sommatoire de la fonction de Möbius” (1991) · Zbl 0869.11075  DOI: 10.1007/BF00288933 · Zbl 0278.68030  Klinger A., Optimizing Methods in Statistics pp 303– (1971)  Lagarias J. C., J. of Algorithms 4 pp 173– (1987) · Zbl 0622.10027  Lehman R. S., Math. Comp. 14 pp 311– (1960)  DOI: 10.1515/crll.1832.9.105 · ERAM 009.0333cj  Neubauer G., Numer. Math. 5 pp 1– (1963) · Zbl 0111.04702  Odlyzko A., J. reine Angew. Math. 357 pp 138– (1985)  Pintz J., Astérisque 147 pp 325– (1987)  Rosser B., Illinois J. of Math. 6 pp 64– (1962)  Rosser B., Math, of Computation 29 pp 243– (1975)  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.