19
$\begingroup$

Say you want to check that $|\sum_{n\leq x} \mu(n)|\leq \sqrt{x}$ for all $x\leq X$. (I am actually interested in checking that $\sum_{n\leq x} \mu(n)/n|\leq c/\sqrt{x}$, where $c$ is a constant, and in finding the best $c$ such that this is true in a given range, such as $3\leq x\leq X$, say; all of these problems are evidently related.)

The natural algorithm (the same you can find in section 4 of [1], say) has running time $O(X \log \log X)$ and takes space $O(\sqrt{X})$ (where we think of integers as taking constant space). I've coded it with some optimizations (for $\sum_{n\leq x} \mu(n)/n$, using interval arithmetic) and should have a result for $x=10^{14}$ in about a fortnight; $x=10^{12}$ takes an afternoon. (When I first coded this, less carefully and on worse hardware, it took a week.)

Is it possible to do things in either less time or less space? Space is important here in practice - ideally you would want to keep everything in cache, and it is rare to have more than 4MB per processor core - that is, enough for $1.6\cdot 10^7$ values of $\mu$, or $5\cdot 10^5$ large integers.

Notice that I am asking for a check for all $x\leq X$, and not just for a single $x=X$.


Further remarks: I am aware that there are algorithms for computing a single value of $\sum_{n\leq x} \mu(n)$ in time $O(x^{2/3} \log \log x)$ [2], or even (in what looks like a more sophisticated but less practical way that may have never been coded) in time $O(x^{1/2+\epsilon})$ ([3]; see also Mertens' function in time $O(\sqrt x)$). Once can of course use such an algorithm to compute the sum for values of $x$ that are about $c\sqrt{x}$ apart, and then use what I've called the "natural" algorithm to deal with intervals in which such a computation shows that the statement to be verified could be violated. This results in a running time of $O(x^{7/6} \log \log x)$, or $O(x^{1+\epsilon})$, and while memory usage could be decreased by applying the "natural" algorithm on intervals of length smaller than $\sqrt{x}$, this would result in a longer running time.

The same is true, of course, of the "natural" algorithm itself: one could store a list of primes $p\leq \sqrt{x}$ in the main memory in $\sqrt{x}$ bits, and compute $\mu(m)$ in blocks of size $M$ at a time; this would require working in memory $O(M)$ (to be stored in the cache) for the most part, but the running time would be $O(x^{3/2}/M)$. Or is there a way around this? Can one, say, select the primes $p\leq \sqrt{x}$ that might divide integers in an interval of length $M \lll \sqrt{x}$, and do so in time less than $\sqrt{x}$ or $\sqrt{x}/\log x$? Or is there any other way to take space substantially less than $O(\sqrt{x})$ while still having essentially linear running time? Or a way to have better than linear running time?

PS. I could also ask about parallelising this, but I would not like to risk making the discussion too hardware-specific here.

[1] François Dress, MR 1259423 Fonction sommatoire de la fonction de Möbius. I. Majorations expérimentales, Experiment. Math. 2 (1993), no. 2, 89--98.

[2] Marc Deléglise and Joël Rivat, MR 1437219 Computing the summation of the Möbius function, Experiment. Math. 5 (1996), no. 4, 291--295.

[3] J. C. Lagarias, and A. M. Odlyzko, MR 0890871 Computing $\pi(x)$: an analytic method, J. Algorithms 8 (1987), no. 2, 173--191.

$\endgroup$
  • $\begingroup$ Do you mean $\sqrt{x}$ or $\sqrt{X}$? If the latter, there is a simple sieving process that computes the sum on the fly, and you can save extremal values for later processing and check that the inequality is satisfied. You can even sift just the squarefree values for processing. The memory storage is $O(\log X)$ bits for each prime at most $\sqrt{X}$. The runtime should be not much longer than $O(X\log\log X)$. Gerhard "Sometimes Has Xtreme Case Sensitivity" Paseman, 2016.04.25. $\endgroup$ – Gerhard Paseman Apr 25 '16 at 22:48
  • $\begingroup$ It may be that I am talking about the "natural algorithm" already, which is a variant of the one at mathoverflow.net/a/50691 for determining distinct prime factors of integers up to X in a serial fashion. However I still wonder what parameter you are talking about for space usage. Gerhard "Space Usage: The Final Frontier" Paseman, 2016.04.25. $\endgroup$ – Gerhard Paseman Apr 25 '16 at 23:22
  • $\begingroup$ the simplest algorithm for checking $M(x)$ not for every $x \le X$ but for every $x = \lfloor X/n\rfloor$ is by using $\sum_{n=1}^x M(x/n) = 1$, and computing $M(k)$ for every different $k \in \{ \lfloor X/n \rfloor \}$, it takes $\mathcal{O}(X)$ additions and $\mathcal{O}(\sqrt{X}\log X)$ in space $\endgroup$ – reuns Apr 25 '16 at 23:27
  • $\begingroup$ Gerhard: that's exactly what I mean by "the natural algorithm". $\endgroup$ – H A Helfgott Apr 26 '16 at 0:34
  • $\begingroup$ And yes, the running time is as you said and I said. I'm looking for something better. $\endgroup$ – H A Helfgott Apr 26 '16 at 0:36

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.