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:
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
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:
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:
A -uniform -partite weighted hypergraph satisfies the -linear forms condition if
for all exponents .
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
Fix . We can find such that for prime, we can find which satisfies the -linear forms condition as well as
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 .