Finding Primes: A Fun Subproblem

The ongoing open mathematics project finding primes aims to find a deterministic algorithm to efficiently generate [tex]k[/tex]-digit primes. The fastest known algorithm seems to be a method of Odlyzko which generates a [tex]k[/tex]-digit prime in time [tex]O(10^{k/2})[/tex]. The people working on the project have made some observations which come tantalizingly close to breaking that barrier. The obstruction is a beautiful little problem that I thought many people might enjoy, and which may well be tractable. If you’re interested in participating in the finding primes project, it might be a good entry point. So if you’ve got a good idea to solve the problem, pitch in and help over at the Polymath blog. But please be polite: read some background first, and take a look at some of the research threads to get a feel for how things work, and what’s already known.

One small caveat: the argument that follows is not in any way mine, it’s all the work of other people! A recent comment thread on this argument starts here.

Let [tex]\pi(x)[/tex] denote the number of primes less than or equal to [tex]x[/tex]. [tex]\pi(x)[/tex] has a lot of structure, and there’s a surprising amount that can be said about it. In particular, the people working on finding primes have figured out a clever way of computing the parity of [tex]\pi(x)[/tex] in time about [tex]x^{5/11+o(1)}[/tex].

Suppose you can find two [tex]k[/tex]-digit numbers [tex]x[/tex] and [tex]y[/tex] such that the parity of [tex]\pi(x)[/tex] and [tex]\pi(y)[/tex] are different. Set [tex]z = \lfloor (x+y)/2 \rfloor[/tex], i.e., take [tex]z[/tex] to be the midpoint between [tex]x[/tex] and [tex]y[/tex]. Compute the parity of [tex]z[/tex]. It must have either a different parity to [tex]x[/tex] or a different parity to [tex]y[/tex]. Repeating this procedure [tex]O(k)[/tex] times, we can use a binary search to find adjacent [tex]k[/tex]-digit numbers [tex]p-1[/tex] and [tex]p[/tex] such that [tex]\pi(p-1)[/tex] and [tex]\pi(p)[/tex] have different parity. We conclude that [tex]p[/tex] must be prime. That takes time [tex]O(10^{5/11 k + o(1)})[/tex], and so breaks the barrier set by Odlyzko’s method.

What’s the problem with this algorithm? The problem is finding the initial [tex]k[/tex]-digit numbers [tex]x[/tex] and [tex]y[/tex] such that [tex]\pi(x)[/tex] and [tex]\pi(y)[/tex] have different parity. It would surprise me a great deal if this weren’t possible, but it’s not obvious (at least to me) how to do it quickly. Is there a fast way of doing this?