Prime Gaps

A prime gap of length is a run of consecutive composite numbers between two successive primes. Therefore, the difference between two successive primes and bounding a prime gap of length is , where is the th prime number. Since the prime difference function

(1)

is always even (except for ), all primes gaps are also even. The notation is commonly used to denote the smallest prime corresponding to the start of a prime gap of length , i.e., such that is prime, , , ..., are all composite, and is prime (with the additional constraint that no smaller number satisfying these properties exists).

The maximal prime gap is the length of the largest prime gap that begins with a prime less than some maximum value . For , 2, ..., is given by 4, 8, 20, 36, 72, 114, 154, 220, 282, 354, 464, 540, 674, 804, 906, 1132, ... (OEIS A053303).

Arbitrarily large prime gaps exist. For example, for any , the numbers , , ..., are all composite (Havil 2003, p. 170). However, no general method more sophisticated than an exhaustive search is known for the determination of first occurrences and maximal prime gaps (Nicely 1999).

Cramér (1937) and Shanks (1964) conjectured that

(2)

Wolf conjectures a slightly different form

(3)

which agrees better with numerical evidence.

Wolf conjectures that the maximal gap between two consecutive primes less than appears approximately at

(4)

where is the prime counting function and is the twin primes constant. Setting reduces to Cramer's conjecture for large ,

(5)

It is known that there is a prime gap of length 803 following , and a prime gap of length following (Baugh and O'Hara 1992). H. Dubner (2001) discovered a prime gap of length between two 3396-digit probable primes. On Jan. 15, 2004, J. K. Andersen and H. Rosenthal found a prime gap of length between two probabilistic primes of digits each. In January-May 2004, Hans Rosenthal and Jens Kruse Andersen found a prime gap of length between two probabilistic primes with digits each (Anderson 2004).

The merit of a prime gap compares the size of a gap to the local average gap, and is given by . In 1999, the number 1693182318746371 was found, with merit . This remained the record merit until 804212830686677669 was found in 2005, with a gap of 1442 and a merit of . Andersen maintains a list of the top 20 known merits. The prime gaps of increasing merit are 2, 3, 7, 113, 1129, 1327, 19609, ... (OEIS A111870).

Young and Potler (1989) determined the first occurrences of prime gaps up to , with all first occurrences found between 1 and 673. Nicely (1999) has extended the list of maximal prime gaps. The following table gives the values of for small , omitting degenerate runs which are part of a run with greater (OEIS A005250 and A002386).

1	2	354
2	3	382
4	7	384
6	23	394
8	89	456
14	113	464
18	523	468
20	887	474
22		486
34		490
36		500
44		514
52		516
72		532
86		534
96		540
112		582
114		588
118		602
132		652
148		674
154		716
180		766
210		778
220		804
222		806
234		906
248		916
250		924
282
288
292
320
336

Define

(6)

as the infimum limit of the ratio of the th prime difference to the natural logarithm of the th prime number. If there are an infinite number of twin primes, then . This follows since it must then be true that infinitely often, say at for , 2, ..., so a necessary condition for the twin prime conjecture to hold is that

			(7)
			(8)
			(9)
			(10)

However, this condition is not sufficient, since the same proof works if 2 is replaced by any constant.

Hardy and Littlewood showed in 1926 that, subject to the truth of the generalized Riemann hypothesis, . This was subsequently improved by Rankin (again assuming the generalized Riemann hypothesis) to . In 1940, Erdős used sieve theory to show for the first time with no assumptions that . This was subsequently improved to 15/16 (Ricci), (Bombieri and Davenport 1966), and (Pil'Tai 1972), as quoted in Le Lionnais (1983, p. 26). Huxley (1973, 1977) obtained , which was improved by Maier in 1986 to , which was the best result known until 2003 (American Institute of Mathematics).

At a March 2003 meeting on elementary and analytic number theory in Oberwolfach, Germany, Goldston and Yildirim presented an attempted proof that . While the original proof turned out to be flawed (Mackenzie 2003ab), the result has now been established by a new proof (American Institute of Mathematics 2005, Cipra 2005, Devlin 2005, Goldston et al. 2005ab).