Ben Green, and I have just uploaded to the arXiv a short (six-page) paper “Yet another proof of Szemeredi’s theorem“, submitted to the 70th birthday conference proceedings for Endre Szemerédi. In this paper we put in print a folklore observation, namely that the inverse conjecture for the Gowers norm, together with the density increment argument, easily implies Szemerédi’s famous theorem on arithmetic progressions. This is unsurprising, given that Gowers’ proof of Szemerédi’s theorem proceeds through a weaker version of the inverse conjecture and a density increment argument, and also given that it is possible to derive Szemerédi’s theorem from knowledge of the characteristic factor for multiple recurrence (the ergodic theory analogue of the inverse conjecture, first established by Host and Kra), as was done by Bergelson, Leibman, and Lesigne (and also implicitly in the earlier paper of Bergelson, Host, and Kra); but to our knowledge the exact derivation of Szemerédi’s theorem from the inverse conjecture was not in the literature. Ordinarily this type of folklore might be considered too trifling (and too well known among experts in the field) to publish; but we felt that the venue of the Szemerédi birthday conference provided a natural venue for this particular observation.
The key point is that one can show (by an elementary argument relying primarily an induction on dimension argument and the Weyl recurrence theorem, i.e. that given any real 
![{[N] = \{1,\ldots,N\}}](http://s0.wp.com/latex.php?latex=%7B%5BN%5D+%3D+%5C%7B1%2C%5Cldots%2CN%5C%7D%7D&bg=ffffff&fg=000000&s=0 "{[N] = \{1,\ldots,N\}}")
Technically, one might call this the shortest proof of Szemerédi’s theorem in the literature (and would be something like the sixteenth such genuinely distinct proof, by our count), but that would be cheating quite a bit, primarily due to the fact that it assumes the inverse conjecture for the Gowers norm, our current proof of which is checking in at about 100 pages…
7 comments
Comments feed for this article
14 February, 2010 at 1:17 am
Gil Kalai
Dear Terry, What kind of bounds follow from this proof?
14 February, 2010 at 10:36 am
Terence Tao
It depends on the bounds one gets from the inverse conjecture for the Gowers norms.
For length 3 progressions, one has polynomial bounds in the U^2 inverse theorem from Fourier analysis, which eventually gives the usual Roth-type result that
with this argument. For length 4 progressions, we have exponential bounds in the U^3 inverse theorem in its standard formulation, which moves the double log to a triple log; but it was observed by Gowers and Wolf that the proof of the U^3 inverse theorem gives a more complicated variant of this theorem which in some sense continues to have polynomial bounds, and which lets one recover log log type bounds for 
. For longer progressions, the inverse theorem bounds are terrible (tower exponential or worse; we haven’t tried to quantify this) and so at best one would get 
type denominators, and probably worse. (But if one assumes polynomial bounds on the inverse conjecture in all dimensions, one should get back to log log type bounds, I think.)
There is another trick of Heath-Brown and Szemeredi which, in principle, removes another log, but even in the AP4 case this is a bit tricky to implement. Ben and I were able to do it in the finite field model, and could get half-way in the integer case (getting the somewhat strange bound
but are still working on finishing off the integer case.
14 February, 2010 at 9:09 am
Tamar Ziegler
Hi Terry,
In the ergodic world the derivation of Szemeredi’s theorem via nilsequences was done in a paper of Bergelson, Leibman and Lesigne (here is the arxiv link ). They prove a Szemeredi type theorem for “intersective polynomials” – arithmetic progressions are a special case. Actually, their theorem is a nice example of a theorem for which one must use nilsequences.
14 February, 2010 at 10:48 am
Terence Tao
Thanks Tammy! Yes, you are right, strictly speaking knowing the characteristic factor is not quite enough in itself, one still has to check recurrence on that factor using some nilmanifold equidistribution theory. In the case of linear recurrence, though, this would follow fairly quickly from Leibman’s version of Ratner’s theorem on nilmanifolds and the Hall-Petresco group machinery (I suppose this is already implicit in your thesis, for instance). I’ll modify the text accordingly.
One curious thing is that a step which is almost trivial in the infinitary world – the Furstenberg-Katznelson observation that recurrence is preserved by inverse limits – becomes remarkably difficult to replicate in the finitary world; in particular, in the finitary world one is always bedeviled by little errors that are small in L^2 norm, but not so small that they can’t be neglected immediately. So duplicating the ergodic theory proof of Szemeredi’s theorem in the finitary world turns out to be non-trivial. But using a density increment argument seems to be easier (even though it does not have an obvious ergodic theory counterpart).
15 February, 2010 at 2:39 am
Harrison
“…and would be something like the sixteenth such genuinely distinct proof, by our count.”
I don’t know how tongue-in-cheek that statement is meant to be, but now I’m wondering how many “genuinely distinct proofs” there are. Obviously this depends on how fine your definition of “genuinely distinct” is, but the ones I can think of are (relatively broadly speaking):
1. Szemeredi’s original proof
2. Furstenberg’s ergodic proof
3. Furstenberg-Katznelson’s ergodic proof of DHJ
4. Gowers’ Fourier-analytic/weak inverse conjecture proof
5(*). Hypergraph regularity proof(s)
6. The Polymath proof
7. Austin’s Polymath-Furstenberg-Katznelson “hybrid” proof
8. Your new proof via the Gowers inverse conjecture
and 9. The Bergelson-Leibman-Lesigne “ergodic inverse conjecture” proof, which I only just now learned about from this blog post.
I’m aware there are a couple of different proofs of hypergraph regularity, which is why it’s marked (*), but this is all I can think of. (Admittedly, I’m not an expert and don’t actually understand anything beyond maybe Szemeredi’s k=4 proof, but I like to think I’m a fairly informed amateur at least.) Are there other “genuinely different” methods apart from the ones listed?
15 February, 2010 at 8:07 am
Terence Tao
That’s getting close to an exhaustive list. Furstenberg-Katznelson’s ergodic proof of the multidimensional Szemeredi theorem is a little different from Furstenberg’s original proof (in particular, it makes explicit use of the multidimensional van der Waerden theorem, whereas Furstenberg’s original argument did not use van der Waerden explicitly (instead relying on a kind of colour focusing argument as a substitute).
Tim Austin has a separate proof of multidimensional Szemeredi at http://arxiv.org/abs/0808.2267 which is closely related to 7 but not the same.
I have a proof which finitises Furstenberg’s proof but also combines it with some aspects of Gowers’ proof.
The ergodic inverse conjecture has two separate proofs, one by Host-Kra and one by Ziegler. There is a paper of Bergelson-Host-Kra which also implicitly establishes Szemeredi’s theorem using the ergodic inverse conjecture, and which may have served as the inspiration for the subsequent paper of Bergelson-Leibman-Lesigne.
The hypergraph removal lemma (which implies Szemeredi) also has a number of proofs: Gowers, Nagle-Rodl-Schacht-Skokan, Ishigami, myself (finitarily), myself (infinitarily), Rodl-Schacht (infinitarily, via a more general property testing result), and myself and Austin (giving an alternate proof and generalisation of Rodl-Schacht). Of course they are all fairly closely related to each other.
25 March, 2010 at 11:44 pm
Theorem 22: Szemeredi’s theorem « Theorem of the week
[...] But still the story goes on. A few years later, several people (such as Nagle-Rödl-Schacht and Gowers) found another approach, using a “hypergraph regularity lemma”. And one can also deduce the theorem from the density Hales-Jewett theorem, and so on… Tao has a list of approaches on his blog. [...]