Sea ${\displaystyle \pi (N)}$  el número de números primos menores o iguales que ${\displaystyle N}$ . Si ${\displaystyle A}$  es un subconjunto de los números primos tal que

${\displaystyle \limsup _{N\rightarrow \infty }{\dfrac {|A\cap [1,N]|}{\pi (N)}}>0}$ ,

entonces, para todos los números enteros positivos ${\displaystyle k}$ , el conjunto ${\displaystyle A}$  contiene infinitas progresiones aritméticas de longitud ${\displaystyle k}$ . En particular, todo el conjunto de números primos contiene progresiones aritméticas arbitrariamente largas.

En su trabajo posterior sobre los números primos gemelos generalizados, Green y Tao establecieron y probaron condicionalmente la fórmula asintótica

${\displaystyle ({\mathfrak {S}}_{k}+o(1)){\frac {N^{2}}{(\log N)^{k}}}}$ 

para el número de k-tuplas de números primos ${\displaystyle p_{1}<p_{2}<\dotsb <p_{k}\leq N}$  en progresión aritmética.^[2]​ Aquí, ${\displaystyle {\mathfrak {S}}_{k}}$  es la constante

${\displaystyle {\mathfrak {S}}_{k}:={\frac {1}{2(k-1)}}\left(\prod _{p\leq k}{\frac {1}{p}}\left({\frac {p}{p-1}}\right)^{\!k-1}\right)\!\left(\prod _{p>k}\left(1-{\frac {k-1}{p}}\right)\!\left({\frac {p}{p-1}}\right)^{\!k-1}\right)\!.}$ 

El resultado pasó a ser incondicional mediante las aportaciones de Green–Tao^[3]​ y de Green-Tao-Ziegler.^[4]​

La prueba de Green y Tao tiene tres componentes principales:

1. El teorema de Szemerédi, que afirma que los subconjuntos de los enteros con densidad superior positiva tienen progresiones aritméticas arbitrariamente largas. No se aplica a priori a los números primos porque los números primos tienen densidad cero en los números enteros.
2. Un principio de transferencia que extiende el teorema de Szemerédi a subconjuntos de los números enteros que son pseudoaleatorios en un sentido propio. Tal resultado ahora se llama teorema relativo de Szemerédi.
3. Un subconjunto pseudoaleatorio de los enteros que contienen los números primos como un subconjunto denso. Para construir este conjunto, Green y Tao utilizaron ideas del trabajo de Goldston, Pintz y Yıldırım sobre la diferencia entre dos números primos consecutivos.^[5]​ Una vez establecida la pseudoaleatoriedad del conjunto, se puede aplicar el principio de transferencia, completando la demostración.

Se han encontrado numerosas simplificaciones al argumento del artículo original^[1]​.Conlon, Fox y Zhao (2014) proporciona una exposición moderna de la prueba.

La demostración del teorema de Green-Tao no muestra cómo encontrar las progresiones aritméticas de números primos; simplemente prueba su existencia, independientemente de que por separado se haya realizado un trabajo computacional para encontrar grandes progresiones aritméticas en los números primos.

El artículo de Green-Tao afirma: "En el momento de escribir este artículo, la progresión aritmética de números primos más larga conocida tiene una longitud de 23 y fue encontrada en 2004 por Markus Frind, Paul Underwood y Paul Jobling: 56211383760397 + 44546738095860 · k; k= 0, 1, . . ., 22.

El 18 de enero de 2007, Jarosław Wróblewski encontró el primer caso conocido de 24 números primos en progresión aritmética:^[6]​

468.395.662.504.823 + 205.619 · 223.092.870 · n, para n= 0 a 23.

La constante 223.092.870 aquí es el producto de los números primos hasta 23, escrito de forma más compacta como 23# en notación primorial.

El 17 de mayo de 2008, Wróblewski y Raanan Chermoni encontraron el primer caso conocido de 25 números primos en progresión aritmética:

6.171.054.912.832.631 + 366.384 · 23# · n, para n= 0 a 24.

El 12 de abril de 2010, Benoît Perichon con software de Wróblewski y Geoff Reynolds en un proyecto de PrimeGrid distribuido encontró el primer caso conocido de 26 números primos en progresión aritmética (sucesión A204189 en OEIS):

43.142.746.595.714.191 + 23.681.770 · 23# · n, para n= 0 a 25.

En septiembre de 2019, Rob Gahan y PrimeGrid encontraron el primer caso conocido de 27 números primos en progresión aritmética (sucesión A327760 en OEIS):

224.584.605.939.537.911 + 81.292.139 · 23# · n, para n= 0 a 26.

Muchas de las extensiones del teorema de Szemerédi también son válidas para los números primos.

Independientemente, Tao y Ziegler^[7]​ y Cook, Magyar y Titichetrakun^[8]​^[9]​ dedujeron una generalización multidimensional del teorema de Green-Tao. Fox y Zhao también simplificaron la prueba Tao-Ziegler.^[10]​

En 2006, Tao y Ziegler ampliaron el teorema de Green-Tao para cubrir progresiones polinómicas.^[11]​^[12]​ Más precisamente, dado cualquier polinomio de valores enteros P₁, ..., P_k para una m desconocida, todos con término constante 0, hay infinitos números enteros x, m tal que x + P₁(m), ..., x + P_k (m) que son simultáneamente primos. El caso especial cuando los polinomios son m, 2m, ..., km implica el resultado anterior de que existen progresiones aritméticas de números primos de longitud k.

Tao demostró un análogo del teorema de Green-Tao para enteros gaussianos.^[13]​

• Conjetura de Erdős sobre progresiones aritméticas
• Teorema de Dirichlet sobre progresiones aritméticas
• Combinatoria aritmética

• Conlon, David; Fox, Jacob; Zhao, Yufei (2014). «The Green–Tao theorem: an exposition». EMS Surveys in Mathematical Sciences 1 (2): 249-282. MR 3285854. S2CID 119301206. arXiv:1403.2957. doi:10.4171/EMSS/6. 
• Gowers, Timothy (2010). «Decompositions, approximate structure, transference, and the Hahn–Banach theorem». London Mathematical Society 42 (4): 573-606. MR 2669681. S2CID 17216784. arXiv:0811.3103. doi:10.1112/blms/bdq018. 
• Green, Ben (2007). «Long arithmetic progressions of primes». En Duke, William; Tschinkel, Yuri, eds. Analytic number theory. Clay Mathematics Proceeding 7. Providence, RI: American Mathematical Society. pp. 149-167. ISBN 978-0-8218-4307-9. MR 2362199. 
• Host, Bernard (2006). «Progressions arithmétiques dans les nombres premiers (d'après B. Green et T. Tao)» [Arithmetical progressions in the primes (after B. Green and T. Tao)]. Astérisque (en francés) (307): 229-246. Bibcode:2006math......9795H. MR 2296420. arXiv:math/0609795. 
• Kra, Bryna (2006). «The Green–Tao theorem on arithmetic progressions in the primes: an ergodic point of view». Bulletin of the American Mathematical Society 43 (1): 3-23. MR 2188173. doi:10.1090/S0273-0979-05-01086-4. 
• Tao, Terence (2006). «Arithmetic progressions and the primes». Collectanea Mathematica. Extra: 37-88. MR 2264205. Archivado desde el original el 5 de agosto de 2015. Consultado el 5 de junio de 2015. 
• Tao, Terence (2006). «Obstructions to uniformity and arithmetic patterns in the primes». Pure and Applied Mathematics Quarterly 2 (2): 395-433. MR 2251475. S2CID 6939076. arXiv:math/0505402. doi:10.4310/PAMQ.2006.v2.n2.a2. 
• Tao, Terence (7 de enero de 2008). «AMS lecture: Structure and randomness in the prime numbers».