MathWorld Headline News

Arbitrarily Long Progressions of Primes

By Eric W. Weisstein

April 12, 2004--Prime numbers (i.e., positive integers such as 2, 3, 5, 7, 11, 13, ... that cannot be written as a product of smaller positive integers) have long fascinated mathematicians and non-mathematicians alike. Prime numbers also play an important role in many areas of mathematics, including number theory and cryptography. As a result, they are much studied, and much is known about their properties.

For example, the Greek mathematician and geometer Euclid (ca. 325 - ca. 270 BC) produced a beautiful proof (now known as Euclid's second theorem) that there are an infinite number of primes. However, more than two millennia elapsed before Hadamard and de la Vallée Poussin in 1896 independently proved the so-called prime number theorem, a fundamental result that gives a formula for the asymptotic number of primes that are less than some given number.

While much is known about the prime numbers, there is also much that still remains unknown. For example, it is not known whether there are an infinite number of so-called twin primes, which are prime pairs of the form (p, p + 2). Another question that has remained unanswered is whether there exist arithmetic progressions of primes of any given length.

In mathematics, an arithmetic progression is a set of numbers that are equally spaced. So, for example, 1, 5, 9, 13, 17 is an arithmetic sequence of numbers with difference 4. Similarly, a prime arithmetic progression is an arithmetic progression of numbers that are all prime. For example, 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089 is a 10-term arithmetic progression of primes with difference 210. The largest known number of primes in arithmetic progression is 22, as achieved by the sequences 11,410,337,850,553 + 4,609,098,694,200k (Pritchard et al. 1993) and 376,859,931,192,959 + 18,549,279,769,020k (Frind 2003) for k =0, 1, ..., 21.

As early as 1770, Lagrange and Waring investigated how large the common difference of an arithmetic progression of n primes must be. In 1923, Hardy and Littlewood made a very general conjecture known as the k-tuple conjecture about the distribution of so-called prime constellations, which includes the hypothesis that there exist prime arithmetic progressions of any length k as a special case. Important additional theoretical progress was subsequently made by van der Corput (1939) and Heath-Brown (1981).

Despite all this labor, the general result for progressions of primes of arbitrary length k remained an open conjecture (Guy 1994, p. 15). Now, 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 (which states that every sequence of integers with positive density contains arbitrarily long arithmetic sequences) 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 k for all k.

It should be noted that the work of Green and Tao is a nonconstructive proof, which means that while it appears to establish the existence of prime arithmetic progressions of any given length k, it cannot actually produce a single concrete example. The final chapter on this problem therefore remains unwritten, although it seems certain that explicitly constructing prime progressions of a given length is harder than the already difficult task of theoretically proving their existence.