Recent developments on the Green-Tao theorem

There has quite a bit of activities around the Green-Tao theorem recently. In this blog post, I want to highlight some of these developments, focusing on the following papers, which were all posted on the arXiv in the past couple of months.

Relative Szemerédi theorem

Multidimensional Szemerédi theorem in the primes


We start the story with Szemerédi’s famous result.

Szemerédi’s theorem. Every subset of integers with positive density contains arbitrarily long arithmetic progressions.

Green and Tao proved their famous theorem extending Szemerédi’s theorem to the primes.

Green-Tao theorem. The primes contain arbitrarily long arithmetic progressions. In fact, any subset of the primes with positive relative density contains arbitrarily long arithmetic progressions.

An important idea in Green and Tao’s work is the transference principle. They transfer Szemerédi’s theorem as a black box to the sparse setting, so that it can be applied to subsets of a sparse pseudorandom set of integers (in this case, some carefully designed enveloping set for the primes).

Jacob Fox, David Conlon, and myself

Jacob Fox, David Conlon, and me at the Erdős Centennial conference in Budapest, Hungary, July 2013.

In my recent paper with David Conlon and Jacob Fox, we gave a new simplified approach to proving the Green-Tao theorem. In particular, we established a new relative Szemerédi theorem, which required simpler pseudorandomness hypotheses compared to Green and Tao’s original proof. Roughly speaking, a relative Szemerédi theorem is a result of the following form.

Relative Szemerédi theorem (roughly speaking). Let S be a pseudorandom subset of integers. Then any subset of S with positive relative density contains long arithmetic progressions.

The original proof in our paper followed the hypergraph approach, and in particular used the hypergraph removal lemma, a deep combinatorial result, as a black box. Subsequently, I wrote up a short six-page note showing how to prove the same result by directly transferring Szemerédi’s theorem, without going through hypergraph removal lemma. The former approach is more powerful and more general, while the latter approach is more direct and gives better quantitative bounds.

Next we shift our attention to higher dimensions. Furstenberg and Katznelson proved, using ergodic-theoretic techniques, a multidimensional generalization of Szemerédi’s theorem.

Multidimensional Szemerédi theorem (Furstenberg and Katznelson). Any subset of Zd with positive density contains arbitrary constellations.

Here a constellation means some finite set R of lattice points, and the theorem says that the subset of Zd contains some translation of a dilation of R.

(This result always reminds me of a lovely scene in the movie A Beautiful Mind where the John Nash character traces out shapes among the stars.)

"Pick a shape" - A Beautiful Mind

Pick a shape” – A Beautiful Mind

Tao proved a beautiful extension for the Gaussian primes.

Theorem (Tao). The Gaussian primes contain arbitrary constellations.

In that paper, Tao also made the following interesting conjecture: let P denote the primes. Then any subset of P × P of positive relative density contains arbitrary constellations. This statement can be viewed as a hybrid of the Green-Tao theorem and the multidimensional Szemerédi theorem. Recently this conjecture was resolved by Tao and Ziegler, and independently by Cook, Magyar, and Titichetrakun.

Multidimensional Szemerédi theorem in the primes. Let P denote the primes. Then any subset of Pd with positive density contains arbitrary constellations.

Terry Tao has written a blog post about this new result where he describes the ideas in the proofs (so I won’t repeat too much). Tao and Ziegler proved their result via ergodic theory. Their proof is about 19 pages long, and they assume as black boxes two powerful results: (1) Furstenberg and Katznelson’s multidimensional Szemerédi theorem (more precisely their equivalent ergodic-theoretic formulation) and (2) the landmark results of Green, Tao, and Ziegler on linear equations in primes (and related work on the Mobius-nilsequences conjecture and the inverse conjecture on the Gowers norm). Both these results are deep and powerful hammers.

In contrast, Cook, Magyar, and Titichetrakun proceeded differently as they develop a sparse extension of hypergraph regularity method from scratch, without assuming previous deep results. Though their paper is much longer, at 44 pages.

In a recent paper by Jacob Fox and myself, we give a new and very short proof of the same result, assuming the same tools as the Tao-Ziegler proof. Our paper is only 4 pages long, and it uses a very simple sampling argument described in two paragraphs on the first page of our paper (all the ideas are on the first page; the rest of the paper just contains the technical details spelled out). I invite you to read the first page of our paper to learn the very short proof of the theorem.

2 thoughts on “Recent developments on the Green-Tao theorem

  1. Hi Yufei!

    It seems from these results that it’s basically possible to extend any conclusion that you want similar to the original Green-Tao theorem to higher dimensions, and to objects like positive density subsets of P^d.

    Is this pretty universally true, or can you give an example of a statement of this nature that isn’t true? Where’s the subtle line?

    • Hi Sam,

      You need to know something about the pseudorandomness of the primes with respect to the patterns you’re trying to count, in order to apply a second method bound.

      For example, Tao and Ziegler showed that dense subsets of the primes contain arbitrarily polynomial progressions, but we don’t know how to extend this result to higher dimensions, because there’s isn’t an extension of the Green-Tao-Ziegler result (on the asymptotic number of certain patterns in primes) for polynomials.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s