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 by
A 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:
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.
— 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 .
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 .
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
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 5 Let be such that . Then contains arbitrarily long arithmetic progressions.
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 —
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
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 .
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:
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