This is the second in a series of posts about Szemerédi’s theorem. In the first post I presented the first step in the proof of Szemerédi’ theorem, namely applying the correspondence principle of Furstenberg to transform the problem into one of ergodic theory. More precisely, I showed that Szemerédi’s theorem is equivalent to the following:

Theorem 1Let be a measure preserving system, let be such that and and let . Then there exists such that

It turns out that much more is given by Furstenberg’s proof. Indeed he showed that

Theorem 2Let be a measure preserving system, let be such that and and let . Then

Theorem 2 implies not only Szemerédi’s theorem, it gives some information about the common difference of the arithmetic progression:

Corollary 3Let be such that and let . Then the setis syndetic (this means that it has bounded gaps).

The proof of this corollary follows the same lines as the deduction of Szemerédi’s theorem from Theorem 1 in the previous post.

*Proof:*

Let have positive Banach upper density and let . We apply Furstenberg’s correspondence principle to find a m.p.s. and a set such that and

Apply Theorem 2 with . We can find such that

Applying (1) we deduce that

In particular, for each there exists some such that the intersection is nonempty. If is in that intersection, then and so . We concluded that for every the set has nonempty intersection with the interval . Thus has bounded gaps and hence is syndetic.

The proof of Theorem 2, which will occupy the rest of this series on Szemerédi’s theorem, is based on a structure theorem for measure preserving systems. This structure theorem was devised by Furstenberg in order to prove Theorem 2 and has been widely used since then (together with variants) to prove many other dynamical results which have direct combinatorial consequences.

In this post I will introduce some notions of ergodic theory that we will need, and then I will motivate and present the structure theorem (Theorem 8 below).

** — 1. A note about uniform Cesàro limits — **

Before jumping in to the main part of this post I want to make a remark on the averaging scheme used in this series on Szemerédi’s theorem. As mentioned above, Furstenberg’s multiple recurrence theorem (2 above) gives more that just Szemerédi’s theorem, namely we can obtain Corollary 3. However, to prove Theorem 2 we need to deal with averages along any increasing sequence of intervals (or, equivalently, take limiting averages with respect to an arbitrary F\o lner sequence on ). While it is possible to just average over the interval and still obtain Szemerédi’s theorem, I chose to use a more general averaging scheme to stress the advantage of the ergodic theoretical proof. Besides, the proof does not get any longer or harder, if we introduce the right notation:

Definition 4 (Uniform Cesàro averages)Let be a vector space (usually some function space or ) and let be a sequence taking values in . We use the notationto say that for every there exists some such that if satisfy , then .

It is not hard to show (if one knows all the involving definitions) that

is equivalent to

** — 2. Factors and extensions — **

In this section I will develop some general facts of ergodic theory that will play an important role in what follows. We identify two -subalgebras (say and ) of if the spaces and of equivalence classes of functions are equal (in the sense that for every equivalence class there exists exactly one equivalence class such that ). In other words, and are equivalent if for every there exists some such that has measure, and vice versa. Thus every time we speak of -subalgebras of we are strictly speaking referring to *equivalence classes* of -subalgebras under this equivalent relation. Observe that if the -subalgebras and are equivalent, then the m.p.s. and are isomorphic.

Definition 5 (Factor)Let be a measure preserving system. A -subalgebra of such that is measurable with respect to (in other words, such that is -invariant) is called a factor of . More precisely is a factor if and only if for all the pre-image is also in .

There are several simple examples of factors. Of course is itself a factor, and the trivial -algebra is also a factor. If is not invertible then, for each , the -algebra is a nontrivial factor.

The example that best illustrates the idea behind the notion of a factor is the following: Let and be m.p.s. and let , (this is the smallest -algebra on containing all the rectangles with and ), let and . Then is a m.p.s., called the *product* of the systems and . The -subalgebras and are factors of . Observe that the systems and are isomorphic, respectively, to and .

Another important example is the case of a *skew product*. Instead of giving a general definition I will just consider a particular case: Let be the two dimensional torus with the Borel -algebra and the Haar-Lebesgue measure. Let and . Note that the is not the product of two transformations on , so this system can not be decomposed as the product of two systems. Now let . It is not hard to see that is a factor of . Moreover, the system is isomorphic to the rotation on the torus with the Borel -algebra and the Haar-Lebesgue measure. More generally, if is a factor of , the system is “simpler” than the original system. For instance if is the trivial -algebra, then is isomorphic as a measure preserving system to the one point trivial system. The idea behind this is that in ergodic theory one only cares about measurable sets (the elements of the underlying -algebra) and hence in a smaller -algebra one has less sets to worry about.

Definition 6 (Sz factor)A factor of is called Sz if satisfies the conclusion of the Theorem 2.

For instance, the factor is trivially Sz (the only measurable functions are the constants). Theorem 2 can be rephrased as saying that itself is a Sz factor. The idea to prove Theorem 2 is to find, for each Sz factor of (and strictly contained in) , a larger Sz factor containing . Thus one can show that no maximal Sz factor can exist except itself.

Definition 7 (Extension)Let and be factors of . If , then we say that is an extension of . We say that is a non-trivial extension of if .

Our task is to prove that any proper factor which is Sz has a (non-trivial) extension which is also Sz. But how does one construct an extension of a given factor? The answer lies with almost periodic functions!

Let’s start with the trivial factor , which is Sz. An extension of is simply any factor of . Consider the collection of all almost periodic functions, i.e., all functions such that the set is precompact in . It turns out that the family forms a factor of (I presented a proof of this fact in a previous post). Moreover, because of the almost periodicity, it is not hard to show that this factor is Sz. But what if there are no almost periodic functions? Well then it turns out that the system is weak mixing, and then proving multiple recurrence for the whole system (i.e. showing that is Sz) is easy. This shows how one gets one extension of the trivial factor to be Sz. To get a Sz extension of a general factor, more technical definitions are needed. It turns out that one can still adapt the ideas of the previous paragraph with the trivial factor replaced with any factor . Thus one can construct an extension consisting of almost periodic functions relative to (the precise definitions will be given in the next post), and it is possible to leverage the special structure of this extension to prove that the Sz property *lifts* from to . Finally, if no such extension of exists, then is itself a weak mixing extension of , and again this property can be used to lift the Sz property to .

I will not define precisely either compact or weak mixing extensions until the next post. For now it suffices to know that an extension of m.p.s. can take two special forms: it can be a *compact extension* or a *weak mixing* extension (and of course there are many extensions which are neither compact nor weak mixing). The ideas of the previous paragraph can be summarized in the next theorem:

- Let be an extension between factors of . If the extension is weak mixing and is a Sz factor, then also is a Sz factor.
- Let be an extension between factors of . If the extension is compact and is a Sz factor, then also is a Sz factor.
- Let be a factors of . If the extension is not weak mixing, then there exists a non-trivial extension of which is compact.

In the next post in this series I will give all the precise definitions and I will show how Theorem 8 implies Theorem 2. Theorem 8 will be proved in the three last post of this series, one point in each post.

Pingback: Szemerédi’s Theorem Part III – Precise definitions | 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: Szemerédi’s Theorem Part V – Compact extensions | 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!