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 be a sparse “pseudorandom” set of integers. Then subsets of with positive density in 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 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 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 is 3-AP-free, then .

The second is a “weighted” version

**Theorem 3** **(Roth, weighted version)**

Fix . Let with . Then

We sketch the idea of a graph-theoretic proof of the first theorem. We construct a tripartite graph on vertices , where . Then one creates the edges

- if ,
- if , and
- if .

This construction is selected so that arithmetic progressions in correspond to triangles in the graph . As a result, if has no 3-AP’s (except trivial ones, where ), the graph has exactly one triangle for every edge. Then, we can use the theorem of Ruzsa-Szemerédi, which states that this graph has edges.

### 2.2. The measure

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

which we call a majorizing measure. Since we are now dealing with of low density, we normalize so that

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

**Theorem** **(Relative Roth, informally, weighted version)
**

If , , and satisfies a “pseudorandom” condition, then .

The prototypical example of course is that if , then we let .

### 2.3. Pseudorandomness for

So, how can we put the pseudorandom condition? Initially, consider the tripartite graph defined earlier, and let ; since is sparse we expect small. The main idea that turns out to be correct is: The number of embeddings of in is “as expected”, namely . Here is actually the -blow-up of a triangle. This condition thus gives us control over the distribution of triangles in the sparse graph : knowing that we have approximately the correct count for is enough to control distribution of triangles.

For technical reasons, in fact we want this to be true not only for but all of its subgraphs .

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

We think of as normalized so that . Then we can define

**Definition 4**

A weighted tripartite graph satisfies the **-linear forms condition** if

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 is satisfies the **-linear forms condition** if , and the tripartite graph defined by

satisfies the -linear forms condition.

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

**Theorem 6** **(Relative Roth)**

Suppose satisfies the -linear forms condition. Then for any bounded above by and satisfying , we have

### 2.4. Relative Szemerédi

We of course have:

**Theorem 7** **(Szemerédi)**

Suppose , and with . Then

For , rather than considering weighted tripartite graphs, we consider a -uniform -partite hypergraph. For example, given with and , we use the construction

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

Here is the compiled version:

**Definition 8**

A -uniform -partite weighted hypergraph satisfies the **-linear forms condition** if

for all exponents .

**Definition 9**

A function satisfies the **-linear forms condition** if , and

for all exponents . This is just the previous condition with the natural induced by .

The natural generalization of relative Szemerédi is then:

**Theorem 10** **(Relative Szemerédi)**

Suppose , and satisfies the -linear forms condition. Let with , . Then

## 3. Outline of proof of Relative Szemerédi

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

**Theorem 11** **(Dense model)**

Let . There exists such that if:

- satisfies , and
- ,

then there exists a function such that .

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

This is actually an extension of the cut norm defined on a -uniform -partite hypergraph (*not* -uniform like before!): if is such a graph, we let

Taking , gives the analogy.

For the second theorem, we define the norm

**Theorem 12** **(Relative simplex counting lemma)**

Let , , be weighted -uniform -partite weighted hypergraphs on . Assume that satisfies the -linear forms condition, and for all , . If then

One then combines these two results to prove Szemerédi, as follows. Start with and in the theorem. The -linear forms condition turns out to imply . So we can find a nearby by the dense model theorem. Then, we induce , , from , , respectively. The counting lemma then reduce the bounding of to the bounding of , which is 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 .

Unfortunately, is biased (e.g. “all decent primes are odd”). To get around this, we let tend to infinity slowly with , and define

In the **-trick** we consider only primes . The modified von Mangoldt function then is defined by

In accordance with Dirichlet, we have .

So, we need to show now that

**Proposition 13**

Fix . We can find such that for prime, we can find which satisfies the -linear forms condition as well as

for .

In that case, we can let

Then . The presence of allows us to avoid “wrap-around issues” that arise from using instead of . Relative Szemerédi then yields the result.

For completeness, we state the construction. Let be supported on with , and define a normalizing constant . Inspired by , we define a truncated by

Let , . Now, we define by

This turns out to work, provided grows sufficiently slowly in .