A prime arithmetic progression is an arithmetic progression of primes of
the form for
,
1, ...,
, where
is a positive integer,
is a prime number, and
is a positive integer
when
. For example, 199, 409, 619, 829, 1039, 1249,
1459, 1669, 1879, 2089 is a 10-term prime arithmetic progression with difference
210.
It had long been conjectured that there exist arbitrarily long sequences of primes in arithmetic progression (Guy 1994). As
early as 1770, Lagrange and Waring investigated how large the common difference of
an arithmetic progression of primes must be. In 1923, Hardy
and Littlewood (1923) made a very general conjecture known as the k-tuple
conjecture about the distribution of prime
constellations, which includes the hypothesis that there exist arbitrarily long
finite prime arithmetic progressions as a special case. Important additional theoretical
progress was subsequently made by van der Corput (1939), who proved that there are
infinitely many triples of primes in arithmetic
progression, and Heath-Brown (1981), who proved that there are infinitely many
four-term progressions consisting of three primes
and a number that is either a prime or semiprime.
Green and Tao (2008) proved that the prime numbers contain arbitrarily long finite arithmetic progressions. The Green-Tao theorem uses Szemerédi's theorem, a transference principle, and work by Goldston and Yildirim. The proof is nonconstructive.
Green and Tao (2006) also proved that there are infinitely many three-term arithmetic progressions of Chen primes. Zhou (2009) subsequently strengthened this to arbitrarily long arithmetic progressions of Chen primes.
For , let
be an increasing arithmetic
progression of
primes with minimal difference
. If a prime
does not divide
,
then the elements of
must assume all residues modulo
, specifically, some element of
must be divisible by
.
Since
contains only primes, this element must be equal
to
.
Let the number of primes of the form less than
be denoted
.
For positive integer
and
,
|
(1)
|
where
is the logarithmic integral and
is the totient function.
Let
denote the primorial of
. Then if
,
some prime
does not divide
,
and that prime
is in
.
Thus, in order to determine if
has
,
it is only necessary to check a finite number of possible
(those with
and containing prime
) to see if they contain only primes.
If not, then
. If
,
then the elements of
cannot be made to cover all residues of any prime
. The k-tuple
conjecture then asserts that there are infinitely many arithmetic
progressions of primes with difference
.
A computation shows that the smallest possible common difference for a set of
or more primes in arithmetic
progression for
,
2, 3, ... is 0, 1, 2, 6, 6, 30, 150, 210, 210, 210, 2310, 2310, 30030, 30030, 30030,
30030, 510510, ... (OEIS A033188, Ribenboim
1989, Dubner and Nelson 1997). The displayed values are established. For larger
, once progressions with
have been excluded,
is an unconditional lower bound.
The k-tuple conjecture predicts that
this bound is attained. The smallest first terms of arithmetic
progressions of
primes with minimal differences
are 2, 2, 3, 5, 5, 7, 7, 199, 199, 199, 60858179, 147692845283, 14933623, 834172298383,
... (OEIS A033189; Wilson).
Smaller first terms are possible for nonminimal -term progressions. Examples include the 8-term progression
for
, 1, ..., 7, the 12-term progression
for
,
1, ..., 11 (Golubev 1969, Guy 1994), and the 13-term arithmetic progression
for
, 1, ..., 12 (Guy 1994).
Wróblewski (2008, pp. 1 and 10) reported finding the first known 24-term arithmetic progression of primes on Jan. 18, 2007,
|
(2)
|
for , 1, ..., 23.
The following table gives historical examples of large arithmetic progressions of prime numbers found between 2003 and 2008, where
|
(3)
|
| primes for | digits | reference | |
| 3 | 137514 | J. K. Anderson et al. (2007) | |
| 4 | 11961 | K. Davis (2008) | |
| 5 | 6913 | D. Broadhurst (2008) | |
| 6 | 1606 | K. Davis (2006) | |
| 7 | 1290 | K. Davis (2006) | |
| 8 | 1037 | P. Underwood (2003) | |
| 9 | 401 | M. Oakes (2006) |
A more complete table is maintained by Andersen.
The smallest sequence of six consecutive primes in arithmetic progression is
|
(4)
|
for , 1, ..., 5 (Lander and Parkin 1967, Dubner and Nelson
1997).
An example of three consecutive primes in arithmetic progression is for
, 1, 2, found by T. Alm, H. Rosenthal, J. K. Andersen,
and R. Ballinger in 2003.
The largest known sequence of consecutive primes in arithmetic progression (i.e., all the numbers between the first and last term in the progression, except for the members themselves, are composite) is ten, given by
|
(5)
|
for , 1, ..., 9 (OEIS A033290),
discovered by Harvey Dubner, Tony Forbes, Manfred Toplic, et al. on Mar. 2,
1998. According to Dubner et al. (2002), a trillion-fold increase in computer
speed is needed before the search for a sequence of 11 consecutive primes is practical,
so they expect the ten-primes record to stand for a long time to come.
This beats the record of nine consecutive primes set on Jan. 15, 1998 by the same investigators,
|
(6)
|
for , 1, ..., 8 (a historical example), the progression
of eight consecutive primes given by
|
(7)
|
for , 1, ..., 7, discovered by Harvey Dubner, Tony Forbes,
et al. on Nov. 7, 1997 (another historical example), and the progression
of seven given by
|
(8)
|
for , 1, ..., 6, discovered by H. Dubner and H. K. Nelson
on Aug. 29, 1995 (Peterson 1995, Dubner and Nelson 1997).