The theorem of van der Waerden on arithmetic progressions, whose precise statement and proof can be found in a previous post of mine, states that in a finite partition of the set of positive integers, one of the pieces contains arbitrarily long arithmetic progressions. This was one of the first results in what we call now Ramsey theory. According to the principles of Ramsey theory, the partition result of van der Waerden suggests that any “large” subset of the integers should contain arbitrarily long arithmetic progressions. Erdös and Turán conjectured, in 1936, that the right notion of largeness here is having positive upper density:

Definition 1 (Upper density)Let be a subset of the positive integers. Its upper density is defined byA set has positive upper density if .

This turns out to be the right notion of largeness for this result (well, at least one good notion of largeness. A famous unsolved conjecture by Erdös claims that it suffices for to have arbitrarily long arithmetic progressions), and that fact was proved by Szemerédi in 1975:

Theorem 2 (Szemerédi)Let be such that . Then contains arbitrarily long arithmetic progressions.

Szemerédi used a complicated combinatorial argument. Two years later Furstenberg provided a different proof of this result, using ergodic theory and a correspondence principle which allows one to derive conclusions about sets of integers by studying dynamics on certain measure spaces. It should also be mentioned that a third proof of the Szemerédi’s Theorem was discovered by Gowers in 2001, generalizing Roth’s harmonic analysis proof of the existence of progressions of length in a set of positive density, to progressions of arbitrary length and having the advantage of providing concrete bounds for the finitistic version. More recently a number of different proofs appeared. A good discussion on the different proofs and similarities between them can be found on chapters 10 and 11 of the Tao and Vu’s book.

This post is the first in a sequence of posts I am writing about Szemerédi’s theorem which will include the ergodic theoretical proof of Furstenberg. In fact I will not quite follow the original paper by Furstenberg, but instead I will use an approach more closely related to the one in his paper with Katznelson and Ornstein. This first post is a general introduction with some equivalent forms of Szemerédi’s theorem, including the ergodic theoretical version. The plan for the following posts is the following: In the second post I will present a high level draft of the proof, in the third post I will set up some machinery which will be used in the last three (and more technical) posts where the proof will be finished.

Some good sources for the ergodic approach to Szemerédi’s theorem are the chapter 4.1 of this survey by Bergelson and the chapter 7 of the book of Einsiedler and Ward.

** — 1. Finitistic version — **

An equivalent statement of Szmerédi’s theorem is the following, called a “finitistic” version. We use the following convention: for a positive integer we denote the set simply by .

Theorem 3Let and . Then there exists a number such that for every and every set with , there exists a -term arithmetic progression in .

In fact it was this finitistic form that was proved in Szemerédi’s original paper. To see why Theorem 3 implies Theorem 2, note simply that if , then there exists an arbitrarily large positive integer such that (this follows directly from the definition of upper density). On the other hand it takes a small trick to get the converse.

**Proof that Theorem 2 implies Theorem 3:** Assume that Theorem 3 is false, let and be such that no exists. Thus for each there exists a set with and such that has no terms in arithmetic progression. We can now form a set by gluing the sets in the following way:

- Let .
- For let and let .
- Let

Note that , and hence, letting we have

Therefore we have

It follows from Theorem 2 that must contain a -term arithmetic progression, and this implies that some must contain a -term arithmetic progression (because arithmetic progressions are finite objects). Assume also that is the smallest such that contains an arithmetic progression. Then the progression cannot be contained in . If some part of the progression is in and the rest is in , then because of the gap of length in between these two portions of we conclude that the gap between consecutive terms of the progression is at least . However this is impossible for since . Finally we conclude that the progression must be entirely contained in , which is also impossible as this would imply that contains a -term arithmetic progression, contradicting the construction.

The finitistic version of Szemerédi’s theorem implies a slightly stronger version of Theorem 2. We will need the following definition

Definition 4 (Banach upper density)Let . The Banach upper density is defined as

For instance, the set has but . Also it is clear that for any set . Thus the following version of Szemerédi’s theorem covers more sets than the formulation of Theorem 2:

Theorem 5Let be such that . Then contains arbitrarily long arithmetic progressions.

This formulation clearly implies Theorem 2. It is also not hard to see how it follows from Theorem 3.

*Proof:* Let be such that . Let and let be given by Theorem 3. Let be such that and let be such that . Then and since we deduce that contains a -term arithmetic progression. It follows that also contains such a progression. Since was arbitrary we conclude that contains arbitrarily long arithmetic progressions.

** — 2. Szemerédi’s theorem as multiple recurrence — **

Let . To say that contains the -term arithmetic progression is the same as saying that . Thus, to say that contains arbitrarily long arithmetic progressions is equivalent to saying that

for some . If one defines the map by , then one can rewrite (1) as

Now this expression starts to look a lot like certain expressions one encounters in ergodic theory. In ergodic theory though one takes the measure of that intersection. Indeed Szemerédi’s theorem follows if one can show that for every set with and every there exists some such that

Again drawing the analogy with ergodic theory, to show that this is positive for some , we can show that the average over all is positive. Here “average” is in the following sense:

From the above discussion it should be clear that Szemerédi’s theorem follows from the claim that if , then we have (2). Although the upper density , or even the upper Banach density are quite good notions of largeness, they are not countably additive (each singleton has density, but the countable union of all of them has density ), hence it is not a measure and many of the tools of measure theory can not be applied to the space such as the Dominated Convergence Theorem. To deal with this problem, Furstenberg created a correspondence principle, which allows one to solve problems in (or indeed quite more general settings) by looking at measure spaces. We will now formulate the version of Furstenberg’s correspondence principle which we will use. Recall that a probability measure preserving system is a quadruple where is a -algebra over , is a measure defined on and is a -measurable map which preserves , in the sense that for every .

Theorem 6 (Furstenberg’s correspondence principle)Let . There exists a probability measure preserving system and a set such that and for any and ,

As it becomes clear from the proof, one can take to be a compact metric space (with the Borel -algebra) and an homeomorphism, but we will not need these facts. The proof of (a more general version of) this theorem can be found in my previous post.

Applying the correspondence principle, Szemerédi’s theorem reduces to:

Theorem 7 (Multiple recurrence theorem)Let be a probability measure preserving system. Then for all with and , and all there exists some such that:

One can easily verify that Theorems 6 and 7 together imply Theorem 2. Indeed given with positive density and , using the correspondence principle we find some probability preserving system and some subset satisfying equation (3). Then using the multiple recurrence on that system with we find such that

Next we use equation (3) to get

In particular that intersection is non-empty. Let . We have then and thus contains an arithmetic progression of the arbitrary length .

The main effort of the following posts in this sequence will be to prove Theorem 7. By the discussion above, this will be a proof of Szemerédi’s theorem. I will finish this post going in the opposite direction, and showing how one can use the combinatorial version (Theorem 2) of Szemerédi’s theorem to deduce the dynamical formulation (Theorem 7).

*Proof:* Let be a probability measure preserving system, let with and , and let . Let

Clearly . For each defined the function which measures the proportion of the points in the -th orbit of a point which are inside :

Integrating we get

By Fatou’s lemma we obtain

Let and define the set , which must have positive measure. For each , let . Since we have

We can now apply Theorem 2 to find an arithmetic progression of length inside , say for all . Now the pair takes values on the countable set . Therefore, we have a partition of into countably many pieces, depending on and . Hence one of those pieces will still have positive measure.

There is a subtle detail here, regarding measurability of the pieces. However, note that for any fixed pair , we can describe the set

Thus by choosing, for each , the smallest pair (on some ordering of ) which works for we can assure that the pieces are measurable.

Let be such that and do not depend on . Let and for some (hence all) . Then we have that

Finally note that . We conclude that

Pingback: Szemerédi’s Theorem Part II – Overview of the proof | I Can't Believe It's Not Random!

Pingback: Szemerédi’s Theorem Part III – Precise definitions | I Can't Believe It's Not Random!

Pingback: Pomerance Theorem on colinear points in certain paths in a two dimensional lattice | I Can't Believe It's Not Random!

Pingback: Szemerédi’s Theorem Part IV – Weak mixing extensions | I Can't Believe It's Not Random!

Pingback: Weighted densities with multiplicative structure | I Can't Believe It's Not Random!

Pingback: Szemerédi Theorem Part VI – Dichotomy of extensions | I Can't Believe It's Not Random!

Pingback: Structure of multicorrelation sequences with integer part polynomial iterates along primes | I Can't Believe It's Not Random!

Pingback: Multiple ergodic averages along functions from a Hardy field: convergence, recurrence and combinatorial applications | I Can't Believe It's Not Random!

I realize this post is almost 7 years old, nonetheless these notes have been very useful as I try to make sense of the details in the Furstenberg/Katznelson/Ornstein paper. Many thanks for that.

An observation of the proof of Thm. 2 implies Thm. 3: I agree that the negation of Thm. 3 yields a sequence of sets (A(n)) that do not contain k-term progressions for some k, but as far as I can tell A(n) is contained, not in [n], but in [l(n)] where (l(n)) is some subsequence of the natural numbers.

The general idea behind the proof should still go through though, since even if we cannot choose A(n) contained in [max B(m-1)], we do have one contained in [l(n)] where l(n) > max B(m-1).

You’re right that one can prove it that way. But alternatively one can use the fact that if has density for some , then by pigeonholing there is a subinterval of of length such that has density within (and, of course, still no progressions).