Re: Space between prime numbers

From: Paul Pollack (twonth_at_gmail.com)
Date: 03/29/05 

Date: 28 Mar 2005 16:23:14 -0800

Randy Poe wrote:

> > Obviously you can make good guesses (only examine odd numbers, etc)
> and
> > then you can test for primality.
>
> You can make guesses. Beyond oddness, I'm not sure what
> property you can choose in advance to make it more likely
> to be prime, except perhaps for choosing Mersenne numbers,
> numbers of the form 2^p - 1 where p is prime. It is known
> that infinitely many Mersenne numbers are prime, but
> infinitely many Mersenne numbers are composite, and there
> are lots of non-Mersenne primes also of course.

It is not known if there are infinitely Mersenne primes, but this is
believed to be the case and adventurous souls (Lenstra, Wagstaff and
Pomerance) have (independently) conjectured there are about
(e^gamma/log 2) log log x of them up to x.

Remarkably and frustratingly (as well as remarkably frustratingly), it
is also not known if there are infinitely many *composite* numbers of
the form 2^p-1. This would follow if it were known that there were
infinitely many primes p == 3 mod 4 for which 2p+1 was also prime. (In
this case 2p+1 == 7 mod 8 so by the supplementary laws, 2 is a square
mod (2p+1), so by Euler's criterion 2^p == 1 mod (2p+1), i.e., 2p+1
divides 2^p-1.)

> > It is said that prime numbers are irregularly spaced.
>
> First define "irregularly spaced" a little more precisely.
>
> There are various theorems about spacing. I think it
> is proven that there exist arbitrarily long sequences
> of sequential odd numbers (e.g. 3,5,7) among the primes,

Careful! In any list of three consecutive odd numbers, one of the
numbers is divisible by 3, so the list you gave is the only such list
consisting of (positive) primes. However, these congruence obstructions
are conjectured to be the only "obstacles" to such patterns.

CONJECTURE (HARDY & LITTLEWOOD). Let a_1, ..., a_k be integers and
suppose that for each prime p, there is some integer not congruent to
any of the a_i mod p. Then there are infinitely many n for which n-a_1,
..., n-a_k are simultaneously prime.

There are generalizations of this conjecture with the polynomials x-a_i
replaced by arbitrary linear polynomials (Dickson), or arbitrary
integral polynomials (Schinzel & Sierpinski), in each case subject to
similar congruence conditions. [The Dickson conjecture implies the
assertion we needed before about p==3 mod 4 and 2p+1 being
simultaneously prime infinitely often.] And each of these conjectures
has a quantitative refinement in the form of a predicted asymptotic
formula for the number of such n <= x. But even the simple from stated
above remains very much a conjecture. :-(

> and I think it's also proven that all (even) spacings no matter
> how large occur somewhere among the primes (e.g., there
> are sequential primes somewhere which are separated
> by 12345678910).

de Polignac made the stronger conjecture that every even integer is the
difference of consecutive primes in infinitely many ways. Note that de
Polignac's conjecture follows from the conjecture of H&L given above.

Both de Polignac's conjecture and the weaker statement you offered are
still only conjectures. But it *is* known that "most" even integers
are the difference between two primes -- for a certain delta > 0, there
are O(x^{1-delta}) positive even integers <= x which are not the
difference of two primes <= 2x. (Pomerane and Maier claim this follows
from the method of Montgomery & Vaughan who proved the same upper
estimate for the set of exceptions to Goldbach's conjecture.)

This deep result can be contrasted with the cute and relatively
elementary exercise of proving that for each N, there is an integer a >
0 with the property that there are more than N pairs of positive primes
(n-a,n). In fact, this is true with the primes replaced by any sequence
of positive integers whose counting function A(x) satisfies limsup
A(x)/sqrt(x) = infinity. (If A(x) = pi(x) this limsup estimate is
clear from the PNT or Chebyshev's weaker approximations to it. But in
fact it follows from the much weaker divergence of sum(1/p).)

Finally, let me mention a third consequence of the H&L conjecture
relevant to the topic of prime spacings-- there are arbitrarily long
arithmetic progressions of primes. (The hypotheses of the H&L
conjecture are satisfied with a_i = i*k! for 1<=i<=k.) It appears this
has been recently proven independently of the H&L conjecture by Ben
Green and Terence Tao. In fact, they show the same is true for any set
of primes P with positive relative upper density (i.e., with limsup
P(x)/pi(x) > 0, where P(x) is the counting function of P).

Hope this helps,
Paul