An efficient algorithm exists if Cramer's conjecture holds

2009-08-03T00:10:35Z

Louigi: changed n+ n^{1000} to n+ (log n)^{1000}.

Cramer's conjecture asserts that for sufficiently large n there is a prime between n and <math>n+C(\log n)^2</math>. This conjecture is plausible if you believe that when you pick a random integers m near n, then the events "m is prime" are roughly independent. In that case, the number of primes between n and <math>n+C(\log n)^2</math> should have a Poisson distribution with mean <math>C\log n</math> (by the prime number theorem), which means that the probability of getting no prime will be around <math>\exp(-C\log n)</math>. If we take C to be greater than 2, then the sum <math>\sum_{n=N}^\infty n\exp(-C\log n)=\sum_{n=N}^\infty n^{1-C}</math> converges to around <math>N^{2-C}</math>, so we expect there to be no values of n greater than N for which Cramer's conjecture fails.

Unfortunately, nobody knows how to prove independence of this kind (even after adjusting for obvious dependences, such as the fact that if n is a prime greater than 2, then n+1 is not prime). If they did, then the twin prime conjecture would follow easily, for instance.

If Cramer's conjecture is true, then from that and the fact that primality testing is in [[The complexity class P|P]] it follows instantly that there is a polynomial-time algorithm for finding a k-digit prime. You just search through all the integers from <math>10^{k-1}</math> to <math>10^{k-1}+Ck^2</math>, testing each one for primality in time p(k). This interval is guaranteed to contain a prime, so the algorithm terminates after at most <math>Ck^2p(k)</math> steps.

This is interesting, and shows that there is a deterministic algorithm for finding k-digit primes that probably works. The trouble is, we don't know how to prove that it works, and are basing our belief that it works on a very strong conjecture. This makes our belief less secure than it would be if we based it on a conjecture such as GRH that has rather more evidence in its favour.

Needless to say, we could increase the security of the above approach by using the weaker conjecture that there is a prime between n and <math>n+(\log n)^{1000}</math>. Unexpected phenomena do sometimes occur in the distribution of primes ''[reference needed to Maier's work here]'', so using a higher power would make the conjecture more robust. But it would still be way beyond what anyone knows how to prove.

Polymath Wiki - User contributions [en]

An efficient algorithm exists if Cramer's conjecture holds