Odlyzko's method

From Polymath1Wiki
Jump to: navigation, search

Odlyzko [O1993] has a method for computing [math]\pi(x)[/math] in time/space [math]x^{1/2+o(1)}[/math]; combining this with a binary search, one can locate a k-digit prime in time/space [math](10^k)^{1/2+o(1)}[/math].

First observe that it suffices to compute [math]\pi(x)[/math] to accuracy 1/2, since it is an integer. Next, it suffices to count the slight variant sum [math]\sum_{n \leq x} \frac{\Lambda(n)}{\log n}[/math] up to this accuracy, since the error term is a sum over prime powers and this can be computed in [math]x^{1/2+o(1)}[/math] time/space (using e.g. the sieve of Eratosthenes to find all the primes up to [math]x^{1/2}[/math]).

In fact, it suffices to compute the sum

[math]\sum_{n} c(n) \frac{\Lambda(n)}{\log n}[/math] (1)

where c is a computable function which equals 1 for [math]n \lt x - x^{1/2}[/math], vanishes for [math]n\gtx[/math], and is smooth in between. This is because the error can be computed in [math]x^{1/2+o(1)}[/math] time/space via another sieve of Erathosthenes. [Actually, by using Odlyzko's method recursively, one can reduce this portion of the cost to [math]x^{1/4+o(1)}[/math].]

The expression (1) can be rewritten using the zeta function as

[math] \frac{1}{2\pi i} \int_{2-i\infty}^{2+i\infty} F(s) \log \zeta(s)\ ds[/math]

where

[math] c(u) = \frac{1}{2\pi i } \int_{2-i\infty}^{2+i\infty} F(s) u^{-s}\ du[/math].

It turns out that F is rapidly decreasing when [math]Im(s) \gg x^{1/2}[/math], so to get within accuracy 1/2, one only needs to evaluate the integral for [math]s = O(x^{1/2+o(1)})[/math]. By quadrature, this reduces to evaluating [math]\zeta(s)[/math] (and its first few derivatives) to accuracy about [math]O(x^{-1/2+o(1)})[/math] for about [math]x^{1/2+o(1)}[/math] values of s in this range, but this can be done in many ways (e.g. by the Euler-Maclaurin formulae).