Szemerédi’s Theorem Part III – Precise definitions

This is the third in a series of six posts on Szemerédi’s theorem. In the previous post I outlined the ideas of the ergodic theoretical proof by Furstenberg. In this post I will set up the machinery and give the precise definitions that appear on that proof (namely the notions of weak mixing extension and compact extension), and then I will show how Furstenberg’s multiple recurrence theorem follows from the three key results stated in the end of the previous post. Recall that in the first post of this series we deduced Szemerédi’s theorem from the multiple recurrence theorem; thus in this post we will reduce Szemerédi’s theorem to those three key results, which will be proved in the last three posts of this series.

From now on I will assume that {(X,\mathcal B,\mu, T)} denotes a probability preserving system. Also, for a function {f:X\rightarrow{\mathbb R}} and any integer {n\in{\mathbb N}}, we denote by {T^nf} the function {f\circ T^n}. Note that if {f} is measurable with respect to any factor of {\mathcal B}, then so is {T^nf}. Moreover {T} is an isometry of any {L^p} space (for any {1\leq p\leq\infty} and any factor). In this post we will fix an extension {\mathcal A\subset\mathcal D} of factors of {\mathcal B}.

We will make extensive use of the notion of conditional expectation, also explored in a previous post in this blog. In short if {f\in L^2(\mathcal B)} and {\mathcal A\subset\mathcal B} is a {\sigma}-subalgebra, then the conditional expectation {\mathop{\mathbb E}[f\mid\mathcal A]} is the orthogonal projection of {f} in the subspace {L^2(\mathcal A)\subset L^2(\mathcal B)}. When {f} is just in {L^1({\cal B})} we can approximate it by functions in {L^2({\cal B})}.

— 1. The Hilbert module —

We need to set up some terminology before defining weak mixing and compact extensions.

Definition 1 (Conditional inner product) Let {f,g\in L^2(\mathcal D)}. We define their conditional inner product by:

\displaystyle \langle f,g\rangle_{(\mathcal D\mid\mathcal A)}:=\mathop{\mathbb E}\left[fg\mid\mathcal A\right]\in L^1(\mathcal A)

Note that if {{\cal A}=\{\emptyset,X\}} is the trivial {\sigma}-algebra, then this degenerates to the usual {L^2} inner product.

An immediate property of this inner product is that {\langle hf,g\rangle_{(\mathcal D\mid\mathcal A)}=h\langle f,g\rangle_{(\mathcal D\mid\mathcal A)}} for every {f,g\in L^2(\mathcal D)} and {h\in L^\infty({\cal A})}. Indeed

\displaystyle \langle hf,g\rangle_{(\mathcal D\mid\mathcal A)}=\mathop{\mathbb E}\left[hfg\mid\mathcal A\right]=h\mathop{\mathbb E}\left[fg\mid\mathcal A \right]=h\langle f,g\rangle_{(\mathcal D\mid\mathcal A)}

This conditional inner product gives rise to a conditional norm, and then we can define the conditional Hilbert space (or Hilbert module over {L^\infty(\mathcal A)}).

Definition 2 (Hilbert Module) We define {L^2(\mathcal D\mid\mathcal A)} to be the subspace of {L^2(\mathcal D)} consisting of those functions {f} for which the conditional norm

\displaystyle \|f\|_{(\mathcal D\mid\mathcal A)}:=\sqrt{\langle f,f\rangle_{(\mathcal D\mid\mathcal A)}}=\sqrt{\mathop{\mathbb E}\left[|f|^2\mid\mathcal A \right]}

is in {L^\infty(\mathcal A)}.

Note that the functions {f} and {\sqrt{\mathop{\mathbb E}\left[|f|^2\mid\mathcal A \right]}} have the same {L^2} norm. Thus, in particular, if {\|f\|^2_{L^2(\mathcal D\mid\mathcal A)}=0} then {f=0}.

The conditional Cauchy-Schwartz inequality assures us that for {f,g\in L^2(\mathcal D\mid\mathcal A)}, the inner product {\langle f,g\rangle_{(\mathcal D\mid\mathcal A)}}, which is a priori only in {L^1({\cal A})}, is actually in {L^\infty(\mathcal A)}.

Proposition 3 (Conditional Cauchy-Schwartz inequality) For any functions {f,g\in L^2(\mathcal D\mid\mathcal A)} we have

\displaystyle \left|\langle f,g\rangle_{(\mathcal D\mid\mathcal A)}\right|\leq\|f\|_{(\mathcal D\mid\mathcal A)}\|g\|_{(\mathcal D\mid\mathcal A)}\qquad a.e.

Proof: Most proofs of the usual Cauchy-Schwartz inequality can be relativized do this situation. Note that if {f,g\in L^2({\cal D}\mid{\cal A})} then the function {f\|g\|_{({\cal D}\mid{\cal A})}-g\|f\|_{({\cal D}\mid{\cal A})}} is also in {L^2({\cal D}\mid{\cal A})}. We now use the trivial inequality {x^2\geq0} with this function:

\displaystyle  \begin{array}{rcl} 0&\leq&\displaystyle \big\|f\|g\|_{({\cal D}\mid{\cal A})}-g\|f\|_{({\cal D}\mid{\cal A})}\big\|_{(\mathcal D\mid\mathcal A)}^2\\&=&\displaystyle \big\langle f\|g\|_{({\cal D}\mid{\cal A})}-g\|f\|_{({\cal D}\mid{\cal A})},f\|g\|_{({\cal D}\mid{\cal A})}-g\|f\|_{({\cal D}\mid{\cal A})}\big\rangle\\&=&\displaystyle 2\|f\|_{(\mathcal D\mid\mathcal A)}^2\|g\|_{(\mathcal D\mid\mathcal A)}^2-2\|f\|_{(\mathcal D\mid\mathcal A)}\|g\|_{(\mathcal D\mid\mathcal A)}\langle f,g\rangle_{({\cal D}\mid{\cal A})}\end{array}

After rearranging this gives the desired inequality. \Box

Observe that this also implies a conditional Triangular inequality

Corollary 4 (Conditional Triangular Inequality) Let {f,g\in L^2(\mathcal D\mid\mathcal A)}. Then

\displaystyle \|f+g\|_{L^2(\mathcal D\mid\mathcal A)}\leq\|f\|_{L^2(\mathcal D\mid\mathcal A)}+\|g\|_{L^2(\mathcal D\mid\mathcal A)}\qquad a.e.


\displaystyle  \begin{array}{rcl}  \displaystyle\|f+g\|_{L^2(\mathcal D\mid\mathcal A)}^2&=&\displaystyle\|f\|_{L^2(\mathcal D\mid\mathcal A)}^2+\|g\|_{L^2(\mathcal D\mid\mathcal A)}^2+2\langle f,g\rangle_{L^2(\mathcal D\mid\mathcal A)}\\&\leq&\displaystyle\left(\|f\|_{L^2(\mathcal D\mid\mathcal A)}+\|g\|_{L^2(\mathcal D\mid\mathcal A)}\right)^2 \end{array}


We define the norm on {L^2(\mathcal D\mid\mathcal A)} by making {\|f\|=\big\|\|f\|_{L^2(\mathcal D\mid\mathcal A)}\big\|_{L^\infty}}. Corollary 4 implies that this is indeed a norm. This turns {L^2(\mathcal D\mid\mathcal A)} into a complete metric space.

— 2. Weak mixing and compact extensions —

We can now define weak mixing extensions. Recall from the previous post the notation of uniform Cesàro limits.

Definition 5 (Weak mixing extension)

  • A function {f\in L^2(\mathcal D\mid\mathcal A)} is conditionally weak mixing if for each {g\in L^2(\mathcal D\mid\mathcal A)} we have

    \displaystyle UC\text{-}\lim|\langle T^nf,g\rangle_{(\mathcal D\mid\mathcal A)}|=0\qquad\text{ in }L^2(\mathcal A)

  • The extension is called weak mixing if every {f\in L^2(\mathcal D\mid\mathcal A)} such that {\mathop{\mathbb E}[f|\mathcal A]=0} is conditionally weak mixing.

Example 1 If {{\cal A}=\{\emptyset,X\}} is the trivial {\sigma}-algebra, then the extension {({\cal D}\mid{\cal A})} is weak mixing if and only if the m.p.s. {(X,{\cal D},\mu,T)} is a weakly mixing system.

It takes a little more effort to define compact extensions:

Definition 6 (Compact extension)

  • A subset {A\subset L^2(\mathcal D\mid\mathcal A)} is conditionally pre-compact if it is totally bounded with respect to the {L^2(\mathcal D\mid\mathcal A)} norm, i.e. if {\forall\epsilon>0} there are finitely many functions {f_1,...,f_r\in L^2(\mathcal D\mid\mathcal A)} such that for any {g\in A} and each {x\in X}, we have {\|f_t-g\|_{(\mathcal D\mid\mathcal A)}(x)<\epsilon} for some {t\in\{1,...,r\}}.
  • A function {f\in L^2(\mathcal D\mid\mathcal A)} is conditionally compact if the orbit {A=\{T^nf:n\in{\mathbb Z}\}} is conditionally pre-compact.
  • The extension is called compact if for each {f\in L^2(\mathcal D\mid\mathcal A)} and each {\epsilon>0} there is a subset {A\in \mathcal A} such that {\mu(A)>1-\epsilon} and {f1_A} is conditionally compact.

We stress the subtlety that, in the definition of conditionally pre-compact set, the choice of {f_i} depends on each {x\in X}.

Example 2 The first example of a compact extension is when {{\cal A}=\{\emptyset,X\}} is the trivial {\sigma}-algebra and {(X,{\cal D},\mu,T)} is (isomorphic to) a rotation on a compact group, i.e. {X} is a compact metrizable group, {{\cal D}} is the Borel {\sigma}-algebra, {\mu} is the Haar measure and {Tx=ax} for some {a\in X}.

Indeed, in this case, the conditional norm coincides with the {L^2} norm, and hence the extension is compact if and only in for each function {f\in L^2({\cal D})}, the orbit {\{T^nf:n\in{\mathbb N}\}} is pre-compact in the {L^2} norm. Since {X} is compact, for every {\epsilon>0} there exists a finite set {F\subset{\mathbb N}} such that for any power {a^n} of {a} with {n\in{\mathbb N}}, there is some {m\in F} such that {d(a^n,a^m)<\epsilon}. It is not hard to see that a similar phenomenon happens with the translations of a function {f\in C(X)}; more precisely, for every {f\in C(X)} and {\epsilon>0} there exists a finite set {F\subset{\mathbb N}} such that for any {n\in{\mathbb N}} the function {T^nf} is {\epsilon}-close to some function {T^mf} with {m\in F}. Finally, since {C(X)} is dense in {L^2({\cal D})}, we conclude that any function is almost periodic.

The next example gives a more general example of a skew-product.

Example 3 Let {X={\mathbb T}^2}, let {{\cal B}} be the Borel {\sigma}-algebra in {{\mathbb T}} and let {{\cal D}={\cal B}\otimes{\cal B}} be the Borel {\sigma}-algebra on {X}. Let {\mu} be the Haar measure on {{\cal D}}, let {\alpha\in{\mathbb T}} and define {T:X\rightarrow X} by {T(x,y)=(x+\alpha,y+x)}. Let {{\cal A}:=\{A\times{\mathbb T}:A\in{\cal B}\}} be the vertical {\sigma}-algebra. Then {{\cal A}} is a factor of {{\cal D}} and the extension {({\cal D}\mid{\cal A})} is a compact extension.

Proof: Since {T^{-1}(A\times{\mathbb T})=(T^{-1}A)\times{\mathbb T}} we deduce that {{\cal A}} is indeed a factor. To see that the extension is compact recall that {L^2({\cal B})} has the following orthonormal basis formed by characters:

\displaystyle \big\{e_{j,k}:(x,y)\mapsto e^{2\pi i(jx+ky)}:(j,k)\in{\mathbb Z}^2\big\}

I will show that, for each {(j,k)\in{\mathbb Z}^2}, the character {e_{j,k}} is conditionally compact. It follows from Fubini’s theorem that, for every {f_1,f_2\in L^2({\cal D}\mid{\cal A})} and any point {(x,y_0)\in X} we have

\displaystyle  \|f_1-f_2\|_{({\cal D}\mid{\cal A})}^2(x,y_0)=\int_{\mathbb T}\big(f_1(x,y)-f_2(x,y)\big)^2dy \ \ \ \ \ (1)

Now, fix {\epsilon>0} and let {\lambda_1,\cdots,\lambda_r\in{\mathbb C}} with each {|\lambda_t|=1} be an {\epsilon}-net of the unit circle. Let {f_t:y\mapsto\lambda_te^{2\pi iky}}. For every {(x,y_0)\in X} and {n\in{\mathbb N}}, applying (1) and a simple computation we have

\displaystyle \|T^me_{j,k}-f_t\|_{({\cal D}\mid{\cal A})}^2(x,y_0)=\int_{\mathbb T}\left(\left[e^{2\pi i\big(x(j+nk)+\alpha(jn+kn(n-1)/2)\big)}-\lambda_t\right]e^{2\pi iky}\right)^2dy

Thus, choosing the appropriate {\lambda_t} we conclude that {\|T^me_{j,k}-f_t\|_{({\cal D}\mid{\cal A})}<\epsilon} and hence every character is conditionally compact. It is easy to see that finite linear combinations of conditionally compact functions are still conditionally compact, and hence we found a dense subset of {L^2({\cal D}\mid{\cal A})} formed by compact functions. \Box

— 3. Proof of the multiple recurrence theorem —

With all the definitions in place I will recall Theorem 8 from the previous post:

Theorem 7

  • Let {{\cal A}\subset{\cal D}} be an extension between factors of {{\cal B}}. If the extension is weak mixing and {{\cal A}} is a Sz factor, then also {{\cal D}} is a Sz factor.
  • Let {{\cal A}\subset{\cal D}} be an extension between factors of {{\cal B}}. If the extension is compact and {{\cal A}} is a Sz factor, then also {{\cal D}} is a Sz factor.
  • Let {{\cal A}} be a factors of {{\cal B}}. If the extension {{\cal A}\subset{\cal B}} is not weak mixing, then there exists a non-trivial extension {{\cal D}} of {{\cal A}} which is compact.

In this section I will deduce Furstenberg’s multiple recurrence (Theorem 2 of the previous post) from Theorem 7. In the previous post we saw how the multiple recurrence theorem implies Szemerédi’s theorem; thus we will have reduced Szemerédi’s theorem to Theorem 7. The final three posts of this series will be dedicated to prove this theorem, one point per post.

First we need a technical lemma (alternatively one could use some version of Doob Martingale convergence Theorem).

Lemma 8 Let {(X,\mathcal B,\mu)} be a probability space, let {\{\mathcal B_\alpha\}} be {\sigma}-subalgebras of {\mathcal B} totally ordered by inclusion and let {\mathcal A=\sigma\left(\bigcup B_\alpha\right)} be the {\sigma}-algebra generated by all {\mathcal B_\alpha}. Let {f\in L^\infty(\mathcal A)} and {\epsilon>0}. Then there is some {\mathcal B_\alpha} such that {\|f-\mathop{\mathbb E}[f\mid\mathcal B_\alpha]\|_{L^2}<\epsilon}.

Proof: Let {H\subset L^2(\mathcal B)} be the closure of the union of the {L^2(\mathcal B_\alpha)}, precisely {H=\overline{\bigcup L^2(\mathcal B_\alpha)}}, where we view {L^2(\mathcal B_\alpha)} as a subspace of {L^2(\mathcal B)}. I claim that if {f,g\in H\cap L^\infty(\mathcal B)}, then also {fg\in H}.

To see this assume without loss of generality that {\|f\|_{L^\infty}=\|g\|_{L^\infty}=1}, let {\epsilon>0} and choose {f_\alpha,g_\alpha\in L^2(\mathcal B_\alpha)} be such that both {\|f-f_\alpha\|<\epsilon} and {\|g-g_\alpha\|<\epsilon}. Note that multiplying {g_\alpha} with the characteristic function of the set {\{|g_\alpha|<2\}} (which is in {\mathcal B_\alpha}) gives a function in {L^2(\mathcal B_\alpha)} closer to {g} than {g_\alpha}, thus we can assume that {\|g_\alpha\|_{L^\infty}<2}. We now have

\displaystyle \|fg-f_\alpha g_\alpha\|_{L^2}=\|f(g-g_\alpha)+ g_\alpha(f-f_\alpha)\|_{L^2}\leq\|f(g-g_\alpha)\|_{L^2}+\|g_\alpha(f-f_\alpha)\|_{L^2}

and also

\displaystyle \|f(g-g_\alpha)\|_{L^2}^2=\int_X|f|^2|g-g_\alpha|^2d\mu\leq\int_X|g-g_\alpha|^2d\mu=\|g-g_\alpha\|_{L^2}^2<\epsilon^2


\displaystyle \|g_\alpha(f-f_\alpha)\|_{L^2}^2=\int_X|g_\alpha|^2|f-f_\alpha|^2d\mu\leq4\int_X|f-f_\alpha|^2d\mu=4\|f-f_\alpha\|_{L^2}^2<4\epsilon^2

Putting the last three equations together we get that {\|fg-f_\alpha g_\alpha\|_{L^2}<5\epsilon^2}, since {\epsilon>0} was arbitrary, this proves the claim.

Now let {\mathcal D} be the family of all sets {D\in\mathcal B} such that {1_D\in H}. I claim that {\mathcal D} is a {\sigma}-algebra. Let {D\in \mathcal D}, then {1-1_D\in H} and so {X\setminus D\in \mathcal D}. Now let {\{D_i\}_{i\in{\mathbb N}}} be any sequence of sets in {\mathcal D}. Let {f_i=\prod_{j\leq i} 1_{D_j}}, note that {f_i} is the characteristic function of the intersection {\bigcap_{j\leq i}D_j}. By the previous claim, {f_i\in H}, and {\lim f_i} is the characteristic function of the intersection {\bigcap_{i\in{\mathbb N}} D_i}. Since {H} is closed, we get that the intersection of all {D_i} is still in {\mathcal D} and hence {\mathcal D} is indeed a {\sigma}-algebra as claimed.

Moreover, since any set in any {\mathcal B_\alpha} has its characteristic function in {H} we conclude that {\mathcal B_\alpha\subset\mathcal D}, so also {\mathcal A\subset\mathcal D}. Finally since {H} is a closed subspace we actually get that {L^2(\mathcal A)\subset H}. \Box

We are now ready to prove Furstenberg’s multiple recurrence (Theorem 2 of the previous post), conditional on Theorem 7.


Let {\Omega} be the set of all Sz factors of the system {(X,{\cal B},\mu,T)}, I want to show that {{\cal B}\in\Omega}. We can order {\Omega} partially by inclusion, and we will apply Zorn’s lemma to find a maximal element in {\Omega}. Let {\{{\cal B}_\alpha\}} be a totally ordered family of {\Omega}. I claim that the {\sigma}-algebra {{\cal A}} generated by {\bigcup_\alpha {\cal B}_\alpha} is also Sz.

Let {f\in L^\infty(\mathcal A)} be such that {f\geq0} and {\int_Xfd\mu>0}. We need to show that, for each {k\in{\mathbb N}},

\displaystyle  UC\text{-}\liminf\int_Xf(x)f(T^nx)\cdots f(T^{kn}x)d\mu(x)>0 \ \ \ \ \ (2)

There must exist some {c>0} such that the set {E=\{x\in X:f(x)>c\}} has positive measure, otherwise {\int_Xfd\mu} would be {0}. Since

\displaystyle \int_Xf(x)f(T^nx)\cdots f(T^{kn}x)d\mu(x)\geq c^{k+1}\int_X1_E(x)1_E(T^nx)\cdots 1_E(T^{kn}x)d\mu(x),

it suffices to assume that {f} itself is the characteristic function of some set, say {f=1_E}.

Fix {k\in{\mathbb N}} and apply Lemma 8 to find a Sz factor {\mathcal B_\alpha} such that

\displaystyle \big\|1_E-\mathop{\mathbb E}[1_E\mid\mathcal B_\alpha]\big\|_{L^2}<\frac{\sqrt{\mu(E)}}{2(k+1)}

Call {g=\mathop{\mathbb E}[1_E\mid\mathcal B_\alpha]} and {h=1_E-g}. I claim now that {g(x)>1-1/2(k+1)} in a set of positive measure.

Indeed, if that were not true, we would have {h(x)>1/2(k+1)} for all {x\in E}, and hence

\displaystyle \frac{\mu(E)}{4(k+1)^2}>\|h\|_{L^2}^2=\int_X|h|^2d\mu\geq\int_E|h|^2d\mu>\frac{\mu(E)}{4(k+1)^2}

which is a contradiction. Thus the set {H:=\{x\in X:g(x)>1-1/2(k+1)\}} has positive measure. Also {H\in{\cal B}_\alpha}, which is a Sz factor, so

\displaystyle c:=UC\text{-}\liminf\int_X1_H(x)1_H(T^nx)\cdots 1_H(T^{kn}x)d\mu(x)>0

and hence, the set {D:=\{n\in{\mathbb N}:\mu(H\cap T^{-n}H\cap\cdots\cap T^{-kn}H)>c/2\}} is syndetic. For any {n\in D} denote {H_n:=H\cap T^{-n}H\cap\cdots\cap T^{-kn}H}. If {x\in H_n} then {T^{ni}x\in H} for all {i=0,1,\dots,k}, and hence

\displaystyle \mathop{\mathbb E}[T^{ni}1_E\mid{\cal B}_\alpha](x)=\mathop{\mathbb E}[1_E\mid{\cal B}_\alpha](T^{ni}x)=g(T^{ni}x)>1-\frac1{2(k+1)}

Since each of the functions {T^{in}1_E} only takes values in {\{0,1\}} we have

\displaystyle \prod_{i=0}^kT^{ni}1_E\geq1-\sum_{i=0}^k(1-T^{in}1_E)

and taking conditional expectations we get, for {x\in H_n},

\displaystyle \mathop{\mathbb E}\left[\prod_{i=0}^kT^{ni}1_E\mid{\cal B}_\alpha\right](x)>1-\sum_{i=0}^k\big(1-\mathop{\mathbb E}[T^{in}1_E\mid{\cal B}_\alpha](x)\big)>1-\frac{k+1}{2(k+1)}=\frac12

Finally integrating we obtain

\displaystyle \int_X\prod_{i=0}^kT^{ni}1_Ed\mu=\int_X\mathop{\mathbb E}\left[\prod_{i=0}^kT^{ni}1_E\mid{\cal B}_\alpha\right]d\mu>\frac{\mu(H_n)}2>\frac c4

Since this happens for every {n\in D} which is a syndetic set, say with gaps bounded by {d}, we conclude that

\displaystyle UC\text{-}\liminf\mu(E\cap T^{-n}E\cap\dots\cap T^{-in}E)>\frac c{4d}>0

This means that the factor {{\cal A}} is indeed a Sz factor.

We are now in conditions to apply Zorn’s lemma to find a maximal Sz factor {{\cal D}}. Assume, for the sake of a contradiction, that {{\cal D}\neq{\cal B}}. If the extension {{\cal D}\subset{\cal B}} is weak mixing, then, by the first point of Theorem 7 also {{\cal B}} is Sz. Otherwise, by the third point of Theorem 7, there exists an intermediate factor {{\cal D}'} such that the extension {{\cal D}\subset{\cal D}'} is compact. But then, by the second point of Theorem 7, {{\cal D}'} would also be Sz, contradicting the maximality of {{\cal D}}. \Box

We have proved Szemeredi’s Theorem, assuming only Theorem 7.

This entry was posted in Combinatorics, Ergodic Theory, Ramsey Theory and tagged , , , . Bookmark the permalink.

3 Responses to Szemerédi’s Theorem Part III – Precise definitions

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

  2. Pingback: Szemerédi’s Theorem Part V – Compact extensions | I Can't Believe It's Not Random!

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

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