The polymath blog

It’s probably time to refresh the previous thread for the “finding primes” project, and to summarise the current state of affairs.

The current goal is to find a deterministic way to locate a prime in an interval in time that breaks the “square root barrier” of (or more precisely, ).  Currently, we have two ways to reach that barrier:

1. Assuming the Riemann hypothesis, the largest prime gap in is of size .  So one can simply test consecutive numbers for primality until one gets a hit (using, say, the AKS algorithm, any number of size z can be tested for primality in time .
2. The second method is due to Odlyzko, and does not require the Riemann hypothesis.  There is a contour integration formula that allows one to write the prime counting function up to error in terms of an integral involving the Riemann zeta function over an interval of length , for any .  The latter integral can be computed to the required accuracy in time about .  With this and a binary search it is not difficult to locate an interval of width that is guaranteed to contain a prime in time .  Optimising by choosing and using a sieve (or by testing the elements for primality one by one), one can then locate that prime in time .

Currently we have one promising approach to break the square root barrier, based on the polynomial method, but while individual components of this approach fall underneath the square root barrier, we have not yet been able to get the whole thing below (or even matching) the square root.  I will sketch the approach (as far as I understand it) below; right now we are needing some shortcuts (e.g. FFT, fast matrix multiplication, that sort of thing) that can cut the run time further.

– The polynomial method –

The polynomial method begins with the following observation: in order to quickly find a prime in , it suffices to be able to quickly solve the prime decision problem: given a subinterval of , decide whether such an interval contains a prime or not.  If one can solve this problem in, say, time, then one can find a prime in this time also by binary search.

Actually, using Odlyzko’s method we can already narrow down to an interval of length with a lot of primes in it in time, so we only need to break the square root barrier for the decision problem for intervals of length or less.

The decision problem is equivalent to determining whether the prime polynomial

(1)

is non-trivial or not, where ranges over primes in the interval .

Now, the prime polynomial, as it stands, has a high complexity; the only obvious way to compute it is to enumerate all the primes from to , which could take time in the worst case.  But we can improve matters by working modulo 2; note that as the coefficients of are either 1 or 0, it suffices to decide whether is non-trivial modulo 2.

The reason we do this is the observation that if is a natural number, then the number of solutions to the diophantine equation with is odd when n is prime, and usually even when n is composite.  (There are some rare exceptions to this latter fact, when n contains square factors, but it seems likely that one can deal with these latter cases by Möbius inversion, exploiting the convergence of the sum .)  So, the prime polynomial f modulo 2 is morally equal to the variant polynomial

 (2)

So a toy problem would be to decide whether (2) was non-zero modulo 2 or not in time or better.

The reason that (2) is more appealing than (1) is that the primes have disappeared from the problem.  Instead, one is computing a sum over a fairly simple region bounded by two hyperbolae and two lines.

The point is now this: if vanishes modulo 2, then it also vanishes modulo for any low-degree polynomial g (degree or better), and more generally $\tilde f(x^n)$ vanishes modulo .  Conversely (if one is lucky), if vanishes modulo for sufficiently many , then it should be that vanishes.  So this leads to the following strategy:

• Goal 1: Find a collection of such that if vanishes modulo for all the pairs , then vanishes modulo 2.
• Goal 2: Find a way to decide whether vanishes modulo for all the required in time or better.

One way to achieve Goal 1 is to forget about , and choose the so that the least common multiple of all the (modulo 2) cannot divide .  Since is basically a polynomial of degree shifted by a monomial, one obvious way to proceed would be to pick more than polynomials g.  But then it looks unlikely that one can beat the square root barrier in Goal 2.  Similarly if one varies n as well as g.

On the other hand, we have a partial result in Goal 2: for any fixed n and g, we can compute in time below the square root barrier, e.g. in time .  For instance, setting n=1 and , we can compute in this time.  Unfortunately a single n,g is not nearly enough to solve Goal 2 yet, so we either need a further advance on Goal 1, or some very efficient way to test non-vanishing of modulo (2,g) for many pairs (n,g) at a time (e.g. by an FFT type approach).

The partial result is based on the fact that has an arithmetic circuit complexity below the square root level, i.e. it can be expressed in terms of (say) arithmetic operations.  As such, for any low-degree g (say degree ), can be computed in time (using fast multiplication for mod g arithmetic if necessary).

Let’s sketch how the circuit complexity result works.  Recall that (2) is a sum over the geometric region .  Using the geometric series formula, one can convert this sum over to a sum over what is basically the boundary of .  This boundary has points, so this shows that has an arithmetic circuit complexity of already.  But one can do better by using the Farey sequence to represent the discrete hyperbolae that bound by line segments.  The sum over each line segment is basically a quadratic sum of the form for various coefficients .  It seems that one can factorise this sum as a matrix product and use ideas from the Strassen fast multiplication algorithm to give this a slightly better circuit complexity than the crude bound of ; see these notes; there may also  be other approaches to computing this quickly (e.g. FFT).

Where we’re still stuck right now is scaling up this single case of Goal 2 to the more general case we need.  Alternatively, we need to strengthen Goal 1 by cutting down substantially the number of pairs (n,g) we need to test…