Odlyzko's method

From Polymath1Wiki

Jump to: navigation, search

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

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

In fact, it suffices to compute the sum

\sum_{n} c(n) \frac{\Lambda(n)}{\log n} (1)

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

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

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

where

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

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

Personal tools