The Green–Tao theorem

The obstacle is density zero, so the theorem cannot follow from Szemerédi's theorem applied to $\mathcal{P}$ directly. Green and Tao's insight was that Szemerédi-type density arguments still work for a set of relative density inside a larger, sufficiently pseudorandom set — even if that set is itself sparse in $\mathbb{Z}$ — as long as the ambient set behaves randomly enough for counting arguments to carry over.

Step 1 (the obstruction). The von Mangoldt function $\Lambda(n)$ (equal to $\log p$ when $n=p^j$ and 0 otherwise) is the natural weight for detecting primes, with average size $\mathbb{E}[\Lambda] \approx 1$. But $\Lambda$ itself is not bounded, and $\mathcal{P}$ has density 0, so no classical density theorem applies to it directly.

Step 2 (a pseudorandom majorant). Using ideas from Goldston–Yıldırım-type sieve weights, Green and Tao construct a measure $\nu(n) \ge 0$ with $\mathbb{E}[\nu] \approx 1$ that dominates the primes, $\Lambda(n) \le K\nu(n)$ for a constant $K$, and that is pseudorandom: it satisfies precise linear-forms and correlation conditions modeled on what a genuinely random set of the same density would satisfy.

Step 3 (relative Szemerédi theorem). Green and Tao prove that any function $0 \le f \le \nu$ with positive relative density, $\mathbb{E}[f] \ge \delta$, still contains the expected density of $k$-term progressions, provided $\nu$ is pseudorandom. The proof decomposes $f$ into a bounded, structured part plus a part that is small in the Gowers uniformity norms relative to $\nu$; the uniform part contributes negligibly to the progression count by a generalized von Neumann theorem, so the structured part alone must already account for the expected progressions — exactly as in the classical hypergraph-regularity proof of Szemerédi's theorem, but relativized to $\nu$.

Step 4 (putting it together). Verifying that the Goldston–Yıldırım-type $\nu$ really is pseudorandom (checking the linear-forms and correlation conditions using standard prime-counting estimates) lets Step 3 apply to $f = \Lambda / K$, which has positive relative density since $\mathbb{E}[\Lambda] \approx 1$. This yields a positive relative density of $k$-term progressions weighted by $\Lambda$, and hence — after removing the negligible contribution from prime powers — an honest $k$-term progression of primes, for every $k$.

This special case predates Green–Tao by 65 years and was settled by van der Corput in 1939 using the Hardy–Littlewood circle method directly on the primes, with no need for the transference machinery required for general $k$. It shows why $k=3$ was long tractable by classical analytic number theory while longer progressions were completely open until 2004.

Step 1 (weighted count via exponential sums). Write $S(\theta) = \sum_{n \le N} \Lambda(n) e(\theta n)$. The weighted count of 3-term progressions $p_1 + p_3 = 2p_2$ with all terms $\le N$ equals $\int_0^1 S(\theta)^2 S(-2\theta) \, d\theta$ by orthogonality of the exponential.

Step 2 (major arcs). Near rationals $\theta \approx a/q$ with $q$ small, $S(\theta)$ is well approximated using the prime number theorem in arithmetic progressions; summing these contributions gives the Hardy–Littlewood main term $\mathfrak{S}(N) \, N^2 / \log^3 N$, where the singular series $\mathfrak{S}(N)$ is a positive constant depending only on local (mod $q$) densities of primes.

Step 3 (minor arcs). Away from rationals with small denominator, Vinogradov's estimates bound $S(\theta)$ by $O(N (\log N)^{-A})$ for any fixed $A$, using cancellation in the sum over primes; integrating this bound over the minor arcs shows their total contribution is $o(N^2/\log^3 N)$ — negligible next to the major-arc main term.

Step 4 (conclusion). Since the major-arc main term $\mathfrak{S}(N)\,N^2/\log^3 N$ dominates the negligible minor-arc error, the weighted count of 3-term progressions grows like $N^2/\log^3 N \to \infty$, so there are infinitely many (and asymptotically many) 3-term arithmetic progressions of primes — a full 65 years before the general case was settled.