Return to Question

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.

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.

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^{5/3} \log \log x)$, or $O(x^{1/2+\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.

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.

[1] Dress, F., Fonction sommatoire de la fonction de Moebius 1. Majorations experimentales. Experimental Mathematics, Vol. 2 (1993), no. 2, pp 89-98.

[2] Deleglise, M., and J. Rivat, Computing the summation of the Moebius function, Experimental Mathematics, Vol. 5 (1996), no. 4.

[3] Lagarias, J. C., Odlyzko, A. M., Computing π(x): an analytic method. J. Algorithms 8 (1987), no. 2, 173–191.

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