number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

, the Green–Tao theorem, proven by Ben Green and Terence Tao in 2004, states that the

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...

prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...

s contains arbitrarily long

arithmetic progression An arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference from any succeeding term to its preceding term remains constant throughout the sequence. The constant difference is called common difference of that ...

s. In other words, for every

natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...

k

, there exist arithmetic progressions of primes with

k

terms. The proof is an extension of

Szemerédi's theorem In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers ''A'' with positive natural density contains a ''k''- ...

. The problem can be traced back to investigations of

Lagrange Joseph-Louis Lagrange (born Giuseppe Luigi LagrangiaWaring from around 1770..

Statement

Let

\pi(N)

denote the number of primes less than or equal to

N

. If

A

is a

subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...

of the prime numbers such that :

\limsup_ \frac>0,

then for all positive

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

k

, the set

A

contains infinitely many arithmetic progressions of length

k

. In particular, the entire set of prime numbers contains arbitrarily long arithmetic progressions. In their later work on the generalized Hardy–Littlewood conjecture, Green and Tao stated and conditionally proved the asymptotic formula :

(\mathfrak_k + o(1))\frac

for the number of ''k'' tuples of primes

p_1 < p_2 < \dotsb < p_k \leq N

in arithmetic progression. Here,

\mathfrak_k

is the constant :

\mathfrak_k := \frac\left(\prod_\fracp\left(\frac\right)^\right)\!\left(\prod_\left(1 - \fracp\right)\!\left(\frac\right)^\right)\!.

The result was made unconditional by Green–Tao and Green–Tao–Ziegler.

Overview of the proof

Green and Tao's proof has three main components: #

, which asserts that subsets of the integers with positive upper density have arbitrarily long arithmetic progressions. It does not ''a priori'' apply to the primes because the primes have density zero in the integers. # A transference principle that extends Szemerédi's theorem to subsets of the integers which are pseudorandom in a suitable sense. Such a result is now called a relative Szemerédi theorem. # A pseudorandom subset of the integers containing the primes as a dense subset. To construct this set, Green and Tao used ideas from Goldston, Pintz, and Yıldırım's work on

prime gap A prime gap is the difference between two successive prime numbers. The ''n''-th prime gap, denoted ''g'n'' or ''g''(''p'n'') is the difference between the (''n'' + 1)-st and the ''n''-th prime numbers, i.e., :g_n = p_ - p_n. ...

s. Once the

pseudorandomness A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Pseudorandom number generators are often used in computer programming, as tradi ...

of the set is established, the transference principle may be applied, completing the proof. Numerous simplifications to the argument in the original paper have been found. provide a modern exposition of the proof.

Numerical work

The proof of the Green–Tao theorem does not show how to find the arithmetic progressions of primes; it merely proves they exist. There has been separate computational work to find large arithmetic progressions in the primes. The Green–Tao paper states 'At the time of writing the longest known arithmetic progression of primes is of length 23, and was found in 2004 by Markus Frind, Paul Underwood, and Paul Jobling: 56211383760397 + 44546738095860 · ''k''; ''k'' = 0, 1, . . ., 22.'. On January 18, 2007, Jarosław Wróblewski found the first known case of 24 primes in arithmetic progression: :468,395,662,504,823 + 205,619 · 223,092,870 · ''n'', for ''n'' = 0 to 23. The constant 223,092,870 here is the product of the prime numbers up to 23, more compactly written 23# in

primorial In mathematics, and more particularly in number theory, primorial, denoted by "", is a function from natural numbers to natural numbers similar to the factorial function, but rather than successively multiplying positive integers, the function ...

notation. On May 17, 2008, Wróblewski and Raanan Chermoni found the first known case of 25 primes: :6,171,054,912,832,631 + 366,384 · 23# · ''n'', for ''n'' = 0 to 24. On April 12, 2010, Benoît Perichon with software by Wróblewski and Geoff Reynolds in a distributed

PrimeGrid PrimeGrid is a volunteer computing project that searches for very large (up to world-record size) prime numbers whilst also aiming to solve long-standing mathematical conjectures. It uses the Berkeley Open Infrastructure for Network Computing ( ...

project found the first known case of 26 primes : :43,142,746,595,714,191 + 23,681,770 · 23# · ''n'', for ''n'' = 0 to 25. In September 2019 Rob Gahan and PrimeGrid found the first known case of 27 primes : :224,584,605,939,537,911 + 81,292,139 · 23# · ''n'', for ''n'' = 0 to 26.

Extensions and generalizations

Many of the extensions of Szemerédi's theorem hold for the primes as well. Independently, Tao and Ziegler and Cook, Magyar, and Titichetrakun derived a multidimensional generalization of the Green–Tao theorem. The Tao–Ziegler proof was also simplified by Fox and Zhao. In 2006, Tao and Ziegler extended the Green–Tao theorem to cover polynomial progressions. More precisely, given any

integer-valued polynomial In mathematics, an integer-valued polynomial (also known as a numerical polynomial) P(t) is a polynomial whose value P(n) is an integer for every integer ''n''. Every polynomial with integer coefficients is integer-valued, but the converse is not tr ...

P_1, \ldots, P_k

in one unknown

m

all with constant term 0, there are infinitely many integers

x, m

such that

x + P_ (m), \ldots, x + P_ (m)

are simultaneously prime. The special case when the polynomials are

m, 2m, \ldots, km

implies the previous result that there arithmetic progressions of primes of length

k

. Tao proved an analogue of the Green–Tao theorem for the Gaussian primes.

Statement

Overview of the proof

Numerical work

Extensions and generalizations

See also

References

Further reading