Prime Arithmetic Progression

An arithmetic progression of primes is a set of primes of the form  for fixed  and  and consecutive , i.e., . For example, 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089 is a 10-term arithmetic progression of primes 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 infinitely long prime arithmetic progressions as a special case. Important additional theoretical progress was subsequently made by van der Corput (1939), who proved than 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.

However, despite all this labor, proof of the general result for arbitrarily long sequences of primes has remained an open conjecture (Guy 1994, p. 15). Thanks to new work by Ben Green and Terence Tao, the conjecture seems to finally have been settled in the positive. In a recently published in preprint, Green and Tao (2004) use an important result known as Szemerédi's theorem in combination with recent work by Goldston and Yildirim, a clever "transference principle," and 48 pages of dense and technical mathematics, to apparently establish the fundamental theorem that the prime numbers do contain arithmetic progressions of length  for all  (Weisstein 2004). The proof, however, is nonconstructive.

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 . Then

(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 values up to  are rigorous, while the remainder are lower bounds which assume the validity of the k-tuple conjecture and are simply given by . 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).

The following table summarizes the largest known arithmetic progressions of  primes for small , where

(2)

	primes for , 1, ...,	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

(3)

for , 1, ..., 5 (Lander and Parkin 1967, Dubner and Nelson 1997).

The largest known case 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

(4)

for , 1, ..., 9 (OEIS A033290), discovered by Harvey Dubner, Tony Forbes, Manfred Toplic, et al. on March 2, 1998. According to Dubner et al., 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 January 15, 1998 by the same investigators,

(5)

for , 1, ..., 8 (two sequences of nine are now known), the progression of eight consecutive primes given by

(6)

for , 1, ..., 7, discovered by Harvey Dubner, Tony Forbes, et al. on November 7, 1997 (several are now known), and the progression of seven given by

(7)

for , 1, ..., 6, discovered by H. Dubner and H. K. Nelson on Aug. 29, 1995 (Peterson 1995, Dubner and Nelson 1997).

REFERENCES:

Abel, U. and Siebert, H. "Sequences with Large Numbers of Prime Values." Amer. Math. Monthly 100, 167-169, 1993.

Andersen, J. K. "The Largest Known CPAP's." https://hjem.get2net.dk/jka/math/cpap.htm.

Andersen, J. K. "Primes in Arithmetic Progression Records." https://hjem.get2net.dk/jka/math/aprecords.htm.

Andersen, J. K. "CC7 and AP9 Records." Post to primeform user forum. Apr. 6, 2006. https://groups.yahoo.com/group/primeform/message/7265/.

Caldwell, C. K. "Cunningham Chain." https://primes.utm.edu/glossary/page.php?sort=CunninghamChain.

Caldwell, C. K. "The Top Twenty: Arithmetic Progressions of Primes." https://primes.utm.edu/top20/page.php?id=14.

Caldwell, C. K. "The Top Twenty: Consecutive Primes in Arithmetic Progression." https://primes.utm.edu/top20/page.php?id=13.

Courant, R. and Robbins, H. "Primes in Arithmetical Progressions." §1.2b in Supplement to Ch. 1 in What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 26-27, 1996.

Davenport, H. "Primes in Arithmetic Progression" and "Primes in Arithmetic Progression: The General Modulus." Chs. 1 and 4 in Multiplicative Number Theory, 2nd ed. New York: Springer-Verlag, pp. 1-11 and 27-34, 1980.

Davis, K. "New AP6 Record." primeform@yahoogroups.com mailing list. Apr. 28, 2006. https://groups.yahoo.com/group/primeform/message/7361.

Dubner, H. "Prime Triplets in Arithmetic Progression Starting with 3." J. Recr. Math. 20, 211-213, 1988.

Dubner, H. and Nelson, H. "Seven Consecutive Primes in Arithmetic Progression." Math. Comput. 66, 1743-1749, 1997.

Forman, R. "Sequences with Many Primes." Amer. Math. Monthly 99, 548-557, 1992.

Frind, M. "22 primes in arithmetic progression." 19 Apr 2003. https://listserv.nodak.edu/scripts/wa.exe?A2=ind0304&L=nmbrthry&P=2770.

Frind, M. "First AP23 Discovered." 24 Jul 2004. https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0407&L=nmbrthry&F=&S=&P=2520.

Frind, M. "23 Primes in Arithmetic Progression." https://primes.plentyoffish.com/.

Gardner, M. "Primes in Arithmetic Progression." 1988 Mathematical Sciences Calendar. Raleigh, NC: Rome Press, 1987.

Golubev, V. A. "Faktorisation der Zahlen der Form ." Anz. Österreich. Akad. Wiss. Math.-Naturwiss. Kl. 184-191, 1969.

Green, B. and Tao, T. "The Primes Contain Arbitrarily Long Arithmetic Progressions." Preprint. 8 Apr 2004. https://arxiv.org/abs/math.NT/0404188.

Guy, R. K. "Arithmetic Progressions of Primes" and "Consecutive Primes in A.P." §A5 and A6 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 15-17 and 18, 1994.

Hardy, G. H. and Littlewood, J. E. "Some Problems of 'Partitio Numerorum.' III. On the Expression of a Number as a Sum of Primes." Acta Math. 44, 1-70, 1923.

Heath-Brown, D. R. "Three Primes and an Almost Prime in Arithmetic Progression." J. London Math. Soc. 23, 396-414, 1981.

Lander, L. J. and Parkin, T. R. "Consecutive Primes in Arithmetic Progression." Math. Comput. 21, 489, 1967.

Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, pp. 154-155, 1979.

Nelson, H. L. "There Is a Better Sequence." J. Recr. Math. 8, 39-43, 1975.

Oakes, M. "New AP6 Record." Post to primeform user forum. Mar. 31, 2006. https://groups.yahoo.com/group/primeform/message/7164/.

Peterson, I. "Progressing to a Set of Consecutive Primes." Sci. News 148, 167, Sep. 9, 1995.

Pritchard, P. A.; Moran, A.; and Thyssen, A. "Twenty-Two Primes in Arithmetic Progression." Math. Comput. 64, 1337-1339, 1995.

Ramaré, O. and Rumely, R. "Primes in Arithmetic Progressions." Math. Comput. 65, 397-425, 1996.

Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, p. 224, 1989.

Shanks, D. "Primes in Some Arithmetic Progressions and a General Divisibility Theorem." §104 in Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 104-109, 1993.

Sloane, N. J. A. Sequences A033188, A033189, and A033290 in "The On-Line Encyclopedia of Integer Sequences."

UTS School of Mathematical Sciences. "Primes in Arithmetic Progression." https://www.maths.uts.edu.au/numericon/prime2.html.

van der Corput, J. G. "Über Summen von Primzahlen und Primzahlquadraten." Math. Ann. 116, 1-50, 1939.

Weintraub, S. "Consecutive Primes in Arithmetic Progression." J. Recr. Math. 25, 169-171, 1993.

Weisstein, E. E. "Arbitrarily Long Progressions of Primes." MathWorld headline news, April 12, 2004. https://mathworld.wolfram.com/news/2004-04-12/primeprogressions/.

Zimmermann, P. https://www.loria.fr/~zimmerma/records/8primes.announce.