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.
This post as in overview of the proof of:
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.
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:
The second is a “weighted” version
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:
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
Then the pseudorandomness condition is according to the graph we defined above:
Finally, the relative version of Roth’s theorem which we seek is:
2.4. Relative Szemerédi
We of course have:
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:
The natural generalization of relative Szemerédi is 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:
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
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
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 .