The polymath blog

July 27, 2009

Proposal: deterministic way to find primes

Filed under: polymath proposals,finding primes,research — Terence Tao @ 2:24 am

Here is a proposal for a polymath project:

Problem. Find a deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k.  You may assume as many standard conjectures in number theory (e.g. the generalised Riemann hypothesis) as necessary, but avoid powerful conjectures in complexity theory (e.g. P=BPP) if possible.

The point here is that we have no explicit formulae which (even at a conjectural level) can quickly generate large prime numbers.  On the other hand, given any specific large number n, we can test it for primality in a deterministic manner in a time polynomial in the number of digits (by the AKS primality test).  This leads to a probabilistic algorithm to quickly find k-digit primes: simply select k-digit numbers at random, and test each one in turn for primality.  From the prime number theorem, one is highly likely to eventually hit on a prime after about O(k) guesses, leading to a polynomial time algorithm.  However, there appears to be no obvious way to derandomise this algorithm.

Now, given a sufficiently strong pseudo-random number generator – one which was computationally indistinguishable from a genuinely random number generator – one could derandomise this algorithm (or indeed, any algorithm) by substituting the random number generator with the pseudo-random one.  So, given sufficiently strong conjectures in complexity theory (I don’t think P=BPP is quite sufficient, but there are stronger hypotheses than this which would work), one could solve the problem.

Cramer conjectured that the largest gap between primes in [N,2N] is of size O( \log^2 N ).  Assuming this conjecture, then the claim is easy: start at, say, 10^k, and increment by 1 until one finds a prime, which will happen after O(k^2) steps.  But the only real justification for Cramer’s conjecture is that the primes behave “randomly”.  Could there be another route to solving this problem which uses a more central conjecture in number theory, such as GRH? (Note that GRH only seems to give an upper bound of O(\sqrt{N}) or so on the largest prime gap.)

My guess is that it will be very unlikely that a polymath will be able to solve this problem unconditionally, but it might be reasonable to hope that it could map out a plausible strategy which would need to rely on a number of not too unreasonable or artificial number-theoretic claims (and perhaps some mild complexity-theory claims as well).

Note: this is only a proposal for a polymath, and is not yet a fully fledged polymath project.  Thus, comments should be focused on such issues as the feasibility of the problem and its suitability for the next polymath experiment, rather than actually trying to solve the problem right now. [Update, Jul 28: It looks like this caution has become obsolete; the project is now moving forward, though it is not yet designated an official polymath project.  However, because we have not yet fully assembled all the components and participants of the project, it is premature to start flooding this thread with a huge number of ideas and comments yet.  If you have an immediate and solidly grounded thought which would be of clear interest to other participants, you are welcome to share it here; but please refrain from working too hard on the problem or filling this thread with overly speculative or diverting posts for now, until we have gotten the rest of the project in place.]

See also the discussion thread for this proposal, which will also contain some expository summaries of the comments below, as well as the wiki page for this proposal, which will summarise partial results, relevant terminology and literature, and other resources of interest.

July 26, 2009

Mock-up discussion thread

Filed under: discussion,mock-up — Terence Tao @ 8:06 pm

This is a mockup of what a discussion thread for a polymath project would look like; it would run alongside the research thread, but is focused on strategy, exposition, and discussion by casual participants, as opposed to the more cutting edge research conducted by more active participants in the research thread.

Please feel free to make suggestions in this thread as to how the format and organisation of these projects (or this blog) could be improved.

Mock-up research thread

Filed under: mock-up,research — Terence Tao @ 7:27 pm

This is a mock-up of what a research thread for a polymath project would look like.  The thread would begin with a statement of the research problem, e.g.

Problem (Boundedness of the trilinear Hilbert transform). Show that the trilinear Hilbert transform T(f,g,h) := p.v. \int_{-\infty}^\infty f(x+t) g(x+2t) h(x+3t) \frac{dt}{t} is bounded from L^{p_1}({\Bbb R}) \times \ldots \times L^{p_3}({\Bbb R}) \to L^p({\Bbb R)} for some p_1,p_2,p_3,p (e.g. p_1=p_2=p_3=4 and p_4 = 4/3).

Some discussion of the precise objective (are we aiming for an actual proof, or would we be happy with understanding why the problem is difficult?) would go here.  [Note: while the above problem is an important open problem in harmonic analysis, I am not actually proposing to solve it by polymath here; it is only being used as an example for the purposes of this mock-up.]

A brief discussion of prior results would also be appropriate here, though an extended bibliography might be better placed on the wiki.

A reminder of the polymath rules might also be placed here, together with a link to the discussion thread for issues relating to exposition, strategy, and other meta-comments.  The initiator of the project should also put some effort into laying down preliminary thoughts of the project as clearly as possible.

All threads in a polymath project would have a dedicated category; in this case, the category is mock-up.

Finally, one should put a list of moderators of the project, who would be able to respond to technical issues, such as fixing up a mangled comment.  For this mock-up project, the moderators are:

  • Terence Tao (tao@math.ucla.edu)
« Previous Page

Customized Rubric Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 225 other followers