The polymath project “Finding primes” has now officially launched at the polymath blog as Polymath4, with the opening of a fresh research thread to discuss the following problem:

Problem 1. Find a deterministic algorithm which, when given an integer k, is guaranteed to locate a prime of at least k digits, in time polynomial in k.

From the preliminary research thread, we’ve discovered some good reasons why this problem is difficult (unless one assumes some powerful conjectures in number theory or complexity theory), so we have also identified some simpler toy problems:

Problem 2. Find a deterministic algorithm which, when given an integer k, is guaranteed to locate an adjacent pair n, n+1 of square-free numbers of at least k digits, in time polynomial in k.

(Note that finding one large square-free number is easy – just multiply a lot of small primes together.  Adjacent large square-free numbers exist in abundance, but it is not obvious how to actually find one deterministically and quickly.)

Problem 3. Assume access to a factoring oracle.  Find an algorithm which, when given an integer k, is guaranteed to find a prime of at least  k digits (or an integer divisible by a prime of at least k digits) in time \exp(o(k)).

The current record time is O(10^k)^{0.535} unconditionally, or about O( (10^k)^{1/2} ) on the Riemann hypothesis.

In the new research thread, a number of possible strategies are discussed, and will hopefully be explored soon.  In addition to this thread, there is also the wiki page for the project, and a discussion thread aimed at more casual participants.  Everyone is welcome to contribute to any of these three components of the project, as always.

About these ads