2
$\begingroup$

Is there a quick way to compute (somewhat accurately) for large $X$, the following exponential sum, where $\Lambda$ is the von Mangoldt function? $$\int_0^1 \bigg|\sum_{n\le X} \Lambda(n)e(n\alpha)\bigg|d\alpha$$

Currently, I am trying to compute the inner exponential sum at a bunch of random points and averaging these, though this is quite limited since I don't know of any way to compute the exponential sum more quickly than in $O(X)$ time after precomputing $\Lambda(n)$ for $n\le X$ in $O(X\log\log X)$ time.

Improve this question
$\endgroup$
3
  • $\begingroup$ The main problem is to sum over all prime numbers (the rest is $O(X^{1/2})$. A fast algorithm, if ever exist, might look like the algorithm for the prime counting function. en.wikipedia.org/wiki/… This means that it cannot be much faster than, say, $O(X^{2/3})$. Even though, the idea may not be applicable, because doing "minus" will dramatically kill the accuracy. $\endgroup$
    – WhatsUp
    Commented Apr 1, 2018 at 23:49
  • $\begingroup$ How would one do the rest in $O(X^{1/2})$? $\endgroup$
    – Mayank Pandey
    Commented Apr 2, 2018 at 21:02
  • $\begingroup$ Maybe $O(X^{1/2}\log\log X)$... but not much difference. Just iterate over prime powers $p^k \leq X$ for $k = 2, 3, \cdots$. $\endgroup$
    – WhatsUp
    Commented Apr 2, 2018 at 23:02

0

Reset to default

You must log in to answer this question.