A Sketchy Overview of Green-Tao

These are the notes of my last lecture in the 18.099 discrete analysis seminar. It is a very high-level overview of the Green-Tao theorem. It is a subset of this paper.

1. Synopsis

This post as in overview of the proof of:

Theorem 1 (Green-Tao)

The prime numbers contain arbitrarily long arithmetic progressions.

Here, Szemerédi’s theorem isn’t strong enough, because the primes have density approaching zero. Instead, one can instead try to prove the following “relativity” result.

Theorem (Relative Szemerédi)

Let ${S}$ be a sparse “pseudorandom” set of integers. Then subsets of ${A}$ with positive density in ${S}$ have arbitrarily long arithmetic progressions.

In order to do this, we have to accomplish the following.

Make precise the notion of “pseudorandom”.
Prove the Relative Szemerédi theorem, and then
Exhibit a “pseudorandom” set ${S}$ which subsumes the prime numbers.

This post will use the graph-theoretic approach to Szemerédi as in the exposition of David Conlon, Jacob Fox, and Yufei Zhao. In order to motivate the notion of pseudorandom, we return to the graph-theoretic approach of Roth’s theorem, i.e. the case ${k=3}$ of Szemerédi’s theorem.

2. Defining the linear forms condition

2.1. Review of Roth theorem

Roth’s theorem can be phrased in two ways. The first is the “set-theoretic” formulation:

Theorem 2 (Roth, set version)

If ${A \subseteq \mathbb Z/N}$ is 3-AP-free, then ${|A| = o(N)}$ .

The second is a “weighted” version

Theorem 3 (Roth, weighted version)

Fix ${\delta > 0}$ . Let ${f : \mathbb Z/N \rightarrow [0,1]}$ with ${\mathbf E f \ge \delta}$ . Then

$\displaystyle \Lambda_3(f,f,f) \ge \Omega_\delta(1).$

We sketch the idea of a graph-theoretic proof of the first theorem. We construct a tripartite graph ${G_A}$ on vertices ${X \sqcup Y \sqcup Z}$ , where ${X = Y = Z = \mathbb Z/N}$ . Then one creates the edges

${(x,y)}$ if ${2x+ y \in A}$ ,
${(x,z)}$ if ${x-z \in A}$ , and
${(y,z)}$ if ${-y-2z \in A}$ .

This construction is selected so that arithmetic progressions in ${A}$ correspond to triangles in the graph ${G_A}$ . As a result, if ${A}$ has no 3-AP’s (except trivial ones, where ${x+y+z=0}$ ), the graph ${G_A}$ has exactly one triangle for every edge. Then, we can use the theorem of Ruzsa-Szemerédi, which states that this graph ${G_A}$ has ${o(n^2)}$ edges.

2.2. The measure ${\nu}$

Now for the generalized version, we start with the second version of Roth’s theorem. Instead of a set ${S}$ , we consider a function

$\displaystyle \nu : \mathbb Z/N \rightarrow \mathbb R_{\ge 0}$

which we call a majorizing measure. Since we are now dealing with ${A}$ of low density, we normalize ${\nu}$ so that

$\displaystyle \mathbf E[\nu] = 1 + o(1).$

Our goal is to now show a result of the form:

Theorem (Relative Roth, informally, weighted version)

If ${0 \le f \le \nu}$ , ${\mathbf E f \ge \delta}$ , and ${\nu}$ satisfies a “pseudorandom” condition, then ${\Lambda_3(f,f,f) \ge \Omega_{\delta}(1)}$ .

The prototypical example of course is that if ${A \subset S \subset \mathbb Z_N}$ , then we let ${\nu(x) = \frac{N}{|S|} 1_S(x)}$ .

2.3. Pseudorandomness for ${k=3}$

So, how can we put the pseudorandom condition? Initially, consider ${G_S}$ the tripartite graph defined earlier, and let ${p = |S| / N}$ ; since ${S}$ is sparse we expect ${p}$ small. The main idea that turns out to be correct is: The number of embeddings of ${K_{2,2,2}}$ in ${S}$ is “as expected”, namely ${(1+o(1)) p^{12} N^6}$ . Here ${K_{2,2,2}}$ is actually the ${2}$ -blow-up of a triangle. This condition thus gives us control over the distribution of triangles in the sparse graph ${G_S}$ : knowing that we have approximately the correct count for ${K_{2,2,2}}$ is enough to control distribution of triangles.

For technical reasons, in fact we want this to be true not only for ${K_{2,2,2}}$ but all of its subgraphs ${H}$ .

Now, let’s move on to the weighted version. Let’s consider a tripartite graph ${G}$ , which we can think of as a collection of three functions

$\displaystyle \begin{aligned} \mu_{-z} &: X \times Y \rightarrow \mathbb R \\ \mu_{-y} &: X \times Z \rightarrow \mathbb R \\ \mu_{-x} &: Y \times Z \rightarrow \mathbb R. \end{aligned}$

We think of ${\mu}$ as normalized so that ${\mathbf E[\mu_{-x}] = \mathbf E[\mu_{-y}] = \mathbf E[\mu_{-z}] = 1}$ . Then we can define

Definition 4

A weighted tripartite graph ${\mu = (\mu_{-x}, \mu_{-y}, \mu_{-z})}$ satisfies the ${3}$ -linear forms condition if

$\displaystyle \begin{aligned} \mathbf E_{x^0,x^1,y^0,y^1,z^0,z^1} &\Big[ \mu_{-x}(y^0,z^0) \mu_{-x}(y^0,z^1) \mu_{-x}(y^1,z^0) \mu_{-x}(y^1,z^1) \\ & \mu_{-y}(x^0,z^0) \mu_{-y}(x^0,z^1) \mu_{-y}(x^1,z^0) \mu_{-y}(x^1,z^1) \\ & \mu_{-z}(x^0,y^0) \mu_{-z}(x^0,y^1) \mu_{-z}(x^1,y^0) \mu_{-z}(x^1,y^1) \Big] \\ &= 1 + o(1) \end{aligned}$

and similarly if any of the twelve factors are deleted.

Then the pseudorandomness condition is according to the graph we defined above:

Definition 5

A function ${\nu : \mathbb Z / N \rightarrow \mathbb Z}$ is satisfies the ${3}$ -linear forms condition if ${\mathbf E[\nu] = 1 + o(1)}$ , and the tripartite graph ${\mu = (\mu_{-x}, \mu_{-y}, \mu_{-z})}$ defined by

$\displaystyle \begin{aligned} \mu_{-z} &= \nu(2x+y) \\ \mu_{-y} &= \nu(x-z) \\ \mu_{-x} &= \nu(-y-2z) \end{aligned}$

satisfies the ${3}$ -linear forms condition.

Finally, the relative version of Roth’s theorem which we seek is:

Theorem 6 (Relative Roth)

Suppose ${\nu : \mathbb Z/N \rightarrow \mathbb R_{\ge 0}}$ satisfies the ${3}$ -linear forms condition. Then for any ${f : \mathbb Z/N \rightarrow \mathbb R_{\ge 0}}$ bounded above by ${\nu}$ and satisfying ${\mathbf E[f] \ge \delta > 0}$ , we have

$\displaystyle \Lambda_3(f,f,f) \ge \Omega_{\delta}(1).$

2.4. Relative Szemerédi

We of course have:

Theorem 7 (Szemerédi)

Suppose ${k \ge 3}$ , and ${f : \mathbb Z/n \rightarrow [0,1]}$ with ${\mathbf E[f] \ge \delta}$ . Then

$\displaystyle \Lambda_k(f, \dots, f) \ge \Omega_{\delta}(1).$

For ${k > 3}$ , rather than considering weighted tripartite graphs, we consider a ${(k-1)}$ -uniform ${k}$ -partite hypergraph. For example, given ${\nu}$ with ${\mathbf E[\nu] = 1 + o(1)}$ and ${k=4}$ , we use the construction

$\displaystyle \begin{aligned} \mu_{-z}(w,x,y) &= \nu(3w+2x+y) \\ \mu_{-y}(w,x,z) &= \nu(2w+x-z) \\ \mu_{-x}(w,y,z) &= \nu(w-y-2z) \\ \mu_{-w}(x,y,z) &= \nu(-x-2y-3z). \end{aligned}$

Thus 4-AP’s correspond to the simplex ${K_4^{(3)}}$ (i.e. a tetrahedron). We then consider the two-blow-up of the simplex, and require the same uniformity on subgraphs of ${H}$ .

Here is the compiled version:

Definition 8

A ${(k-1)}$ -uniform ${k}$ -partite weighted hypergraph ${\mu = (\mu_{-i})_{i=1}^k}$ satisfies the ${k}$ -linear forms condition if

$\displaystyle \mathbf E_{x_1^0, x_1^1, \dots, x_k^0, x_k^1} \left[ \prod_{j=1}^k \prod_{\omega \in \{0,1\}^{[k] \setminus \{j\}}} \mu_{-j}\left( x_1^{\omega_1}, \dots, x_{j-1}^{\omega_{j-1}}, x_{j+1}^{\omega_{j+1}}, \dots, x_k^{\omega_k} \right)^{n_{j,\omega}} \right] = 1 + o(1)$

for all exponents ${n_{j,w} \in \{0,1\}}$ .

Definition 9

A function ${\nu : \mathbb Z/N \rightarrow \mathbb R_{\ge 0}}$ satisfies the ${k}$ -linear forms condition if ${\mathbf E[\nu] = 1 + o(1)}$ , and

$\displaystyle \mathbf E_{x_1^0, x_1^1, \dots, x_k^0, x_k^1} \left[ \prod_{j=1}^k \prod_{\omega \in \{0,1\}^{[k] \setminus \{j\}}} \nu\left( \sum_{i=1}^k (j-i)x_i^{(\omega_i)} \right)^{n_{j,\omega}} \right] = 1 + o(1)$

for all exponents ${n_{j,w} \in \{0,1\}}$ . This is just the previous condition with the natural ${\mu}$ induced by ${\nu}$ .

The natural generalization of relative Szemerédi is then:

Theorem 10 (Relative Szemerédi)

Suppose ${k \ge 3}$ , and ${\nu : \mathbb Z/n \rightarrow \mathbb R_{\ge 0}}$ satisfies the ${k}$ -linear forms condition. Let ${f : \mathbb Z/N to \mathbb R_{\ge 0}}$ with ${\mathbf E[f] \ge \delta}$ , ${f \le \nu}$ . Then

$\displaystyle \Lambda_k(f, \dots, f) \ge \Omega_{\delta}(1).$

3. Outline of proof of Relative Szemerédi

The proof of Relative Szeremédi uses two key facts. First, one replaces ${f}$ with a bounded ${\widetilde f}$ which is near it:

Theorem 11 (Dense model)

Let ${\varepsilon > 0}$ . There exists ${\varepsilon' > 0}$ such that if:

${\nu : \mathbb Z/N \rightarrow \mathbb R_{\ge 0}}$ satisfies ${\left\lVert \nu-1 \right\rVert^{\square}_r \le \varepsilon'}$ , and
${f : \mathbb Z/N \rightarrow \mathbb R_{\ge 0}}$ , ${f \le \nu}$

then there exists a function ${\widetilde f : \mathbb Z/N \rightarrow [0,1]}$ such that ${\left\lVert f - \widetilde f \right\rVert^{\square}_r \le \varepsilon}$ .

Here we have a new norm, called the cut norm, defined by

$\displaystyle \left\lVert f \right\rVert^{\square}_r = \sup_{A_i \subseteq (\mathbb Z/N)^{r-1}} \left\lvert \mathbf E_{x_1, \dots, x_r} f(x_1 + \dots + x_r) 1_{A_1}(x_{-1}) \dots 1_{A_r}(x_{-r}) \right\rvert.$

This is actually an extension of the cut norm defined on a ${r}$ -uniform ${r}$ -partite hypergraph (not ${(r-1)}$ -uniform like before!): if ${g : X_1 \times \dots \times X_r \rightarrow \mathbb R}$ is such a graph, we let

$\displaystyle \left\lVert g \right\rVert^{\square}_{r,r} = \sup_{A_i \subseteq X_{-i}} \left\lvert g(x_1, \dots, x_r) 1_{A_1}(x_{-1}) \dots 1_{A_r}(x_{-r}) \right\rvert.$

Taking ${g(x_1, \dots, x_r) = f(x_1 + \dots + x_r)}$ , ${X_1 = \dots = X_r = \mathbb Z/N}$ gives the analogy.

For the second theorem, we define the norm

$\displaystyle \left\lVert g \right\rVert^{\square}_{k-1,k} = \max_{i=1,\dots,k} \left( \left\lVert g_{-i} \right\rVert^{\square}_{k-1, k-1} \right).$

Theorem 12 (Relative simplex counting lemma)

Let ${\mu}$ , ${g}$ , ${\widetilde g}$ be weighted ${(k-1)}$ -uniform ${k}$ -partite weighted hypergraphs on ${X_1 \cup \dots \cup X_k}$ . Assume that ${\mu}$ satisfies the ${k}$ -linear forms condition, and ${0 \le g_{-i} \le \mu_{-i}}$ for all ${i}$ , ${0 \le \widetilde g \le 1}$ . If ${\left\lVert g-\widetilde g \right\rVert^{\square}_{k-1,k} = o(1)}$ then

$\displaystyle \mathbf E_{x_1, \dots, x_k} \left[ g(x_{-1}) \dots g(x_{-k}) - \widetilde g(x_{-1}) \dots \widetilde g(x_{-k}) \right] = o(1).$

One then combines these two results to prove Szemerédi, as follows. Start with ${f}$ and ${\nu}$ in the theorem. The ${k}$ -linear forms condition turns out to imply ${\left\lVert \nu-1 \right\rVert^{\square}_{k-1} = o(1)}$ . So we can find a nearby ${\widetilde f}$ by the dense model theorem. Then, we induce ${\nu}$ , ${g}$ , ${\widetilde g}$ from ${\mu}$ , ${f}$ , ${\widetilde f}$ respectively. The counting lemma then reduce the bounding of ${\Lambda_k(f, \dots, f)}$ to the bounding of ${\Lambda_k(\widetilde f, \dots, \widetilde f)}$ , which is ${\Omega_\delta(1)}$ by the usual Szemerédi theorem.

4. Arithmetic progressions in primes

We now sketch how to obtain Green-Tao from Relative Szemerédi. As expected, we need to us the von Mangoldt function ${\Lambda}$ .

Unfortunately, ${\Lambda}$ is biased (e.g. “all decent primes are odd”). To get around this, we let ${w = w(N)}$ tend to infinity slowly with ${N}$ , and define

$\displaystyle W = \prod_{p \le w} p.$

In the ${W}$ -trick we consider only primes ${1 \pmod W}$ . The modified von Mangoldt function then is defined by

$\displaystyle \widetilde \Lambda(n) = \begin{cases} \frac{\varphi(W)}{W} \log (Wn+1) & Wn+1 \text{ prime} \\ 0 & \text{else}. \end{cases}$

In accordance with Dirichlet, we have ${\sum_{n \le N} \widetilde \Lambda(n) = N + o(N)}$ .

So, we need to show now that

Proposition 13

Fix ${k \ge 3}$ . We can find ${\delta = \delta(k) > 0}$ such that for ${N \gg 1}$ prime, we can find ${\nu : \mathbb Z/N \rightarrow \mathbb R_{\ge 0}}$ which satisfies the ${k}$ -linear forms condition as well as

$\displaystyle \nu(n) \ge \delta \widetilde \Lambda(n)$

for ${N/2 \le n < N}$ .

In that case, we can let

$\displaystyle f(n) = \begin{cases} \delta \widetilde\Lambda(n) & N/2 \le n < N \\ 0 & \text{else}. \end{cases}$

Then ${0 \le f \le \nu}$ . The presence of ${N/2 \le n < N}$ allows us to avoid “wrap-around issues” that arise from using ${\mathbb Z/N}$ instead of ${\mathbb Z}$ . Relative Szemerédi then yields the result.

For completeness, we state the construction. Let ${\chi : \mathbb R \rightarrow [0,1]}$ be supported on ${[-1,1]}$ with ${\chi(0) = 1}$ , and define a normalizing constant ${c_\chi = \int_0^\infty \left\lvert \chi'(x) \right\rvert^2 \; dx}$ . Inspired by ${\Lambda(n) = \sum_{d \mid n} \mu(d) \log(n/d)}$ , we define a truncated ${\Lambda}$ by

$\displaystyle \Lambda_{\chi, R}(n) = \log R \sum_{d \mid n} \mu(d) \chi\left( \frac{\log d}{\log R} \right).$

Let ${k \ge 3}$ , ${R = N^{k^{-1} 2^{-k-3}}}$ . Now, we define ${\nu}$ by

$\displaystyle \nu(n) = \begin{cases} \dfrac{\varphi(W)}{W} \dfrac{\Lambda_{\chi,R}(Wn+1)^2}{c_\chi \log R} & N/2 \le n < N \\ 0 & \text{else}. \end{cases}$