mathtools: Multiple repeating and Furstenberg final statement

The formatter threw an exception while trying to deserialize the message: Error in deserializing body of request message for operation 'Translate'. The maximum string content length quota (30720) has been exceeded while reading XML data. This quota may be increased by changing the MaxStringContentLength property on the XmlDictionaryReaderQuotas object used when creating the XML reader. Line 2, position 33745.
The formatter threw an exception while trying to deserialize the message: Error in deserializing body of request message for operation 'Translate'. The maximum string content length quota (30720) has been exceeded while reading XML data. This quota may be increased by changing the MaxStringContentLength property on the XmlDictionaryReaderQuotas object used when creating the XML reader. Line 1, position 34414.

In 1977, Furstenberg established his multiple recurrence theorem:

Theorem 1 (Furstenberg multiple recurrence) Let ${(X, {\mathcal B}, \mu, T)}$ be a measure-preserving system, thus ${(X,{\mathcal B},\mu)}$ is a probability space and ${T: X \rightarrow X}$ is a measure-preserving bijection such that ${T}$ and ${T^{-1}}$ are both measurable. Let ${E}$ be a measurable subset of ${X}$ of positive measure ${\mu(E) > 0}$ . Then for any ${k \geq 1}$ , there exists ${n > 0}$ such that $\displaystyle E \cap T^{-n} E \cap \ldots \cap T^{-(k-1)n} E \neq \emptyset.$
Equivalently, there exists ${n > 0}$ and ${x \in X}$ such that $\displaystyle x, T^n x, \ldots, T^{(k-1)n} x \in E.$

As is well known, the Furstenberg multiple recurrence theorem is equivalent to Szemerédi’s theorem, thanks to the Furstenberg correspondence principle; see for instance these lecture notes of mine.

The multiple recurrence theorem is proven, roughly speaking, by an induction on the “complexity” of the system ${(X,{\mathcal X},\mu,T)}$ . Indeed, for very simple systems, such as periodic systems (in which ${T^n}$ is the identity for some ${n>0}$ , which is for instance the case for the circle shift ${X = {\bf R}/{\bf Z}}$ , ${Tx := x+\alpha}$ with a rational shift ${\alpha}$ ), the theorem is trivial; at a slightly more advanced level, almost periodic (or compact) systems (in which ${\{ T^n f: n \in {\bf Z} \}}$ is a precompact subset of ${L^2(X)}$ for every ${f \in L^2(X)}$ , which is for instance the case for irrational circle shifts), is also quite easy. One then shows that the multiple recurrence property is preserved under various extension operations (specifically, compact extensions, weakly mixing extensions, and limits of chains of extensions), which then gives the multiple recurrence theorem as a consequence of the Furstenberg-Zimmer structure theorem for measure-preserving systems. See these lecture notes for further discussion.

From a high-level perspective, this is still one of the most conceptual proofs known of Szemerédi’s theorem. However, the individual components of the proof are still somewhat intricate. Perhaps the most difficult step is the demonstration that the multiple recurrence property is preserved under compact extensions; see for instance these lecture notes, which is devoted entirely to this step. This step requires quite a bit of measure-theoretic and/or functional analytic machinery, such as the theory of disintegrations, relatively almost periodic functions, or Hilbert modules.

However, I recently realised that there is a special case of the compact extension step – namely that of finite extensions – which avoids almost all of these technical issues while still capturing the essence of the argument (and in particular, the key idea of using van der Waerden’s theorem). As such, this may serve as a pedagogical device for motivating this step of the proof of the multiple recurrence theorem.

Let us first explain what a finite extension is. Given a measure-preserving system ${X = (X,{\mathcal X},\mu,T)}$ , a finite set ${Y}$ , and a measurable map ${\rho: X \rightarrow \hbox{Sym}(Y)}$ from ${X}$ to the permutation group of ${Y}$ , one can form the finite extension

$\displaystyle X \ltimes_\rho Y = (X \times Y, {\mathcal X} \times {\mathcal Y}, \mu \times \nu, S),$

which as a probability space is the product of ${(X,{\mathcal X},\mu)}$ with the finite probability space ${Y = (Y, {\mathcal Y},\nu)}$ (with the discrete ${\sigma}$ -algebra and uniform probability measure), and with shift map $\displaystyle S(x, y) := (Tx, \rho(x) y). \ \ \ \ \ (1)$

One easily verifies that this is indeed a measure-preserving system. We refer to ${\rho}$ as the cocycle of the system.

An example of finite extensions comes from group theory. Suppose we have a short exact sequence

$\displaystyle 0 \rightarrow K \rightarrow G \rightarrow H \rightarrow 0$

of finite groups. Let ${g}$ be a group element of ${G}$ , and let ${h}$ be its projection in ${H}$ . Then the shift map ${x \mapsto gx}$ on ${G}$ (with the discrete ${\sigma}$ -algebra and uniform probability measure) can be viewed as a finite extension of the shift map ${y \mapsto hy}$ on ${H}$ (again with the discrete ${\sigma}$ -algebra and uniform probability measure), by arbitrarily selecting a section ${\phi: H \rightarrow G}$ that inverts the projection map, identifying ${G}$ with ${H \times K}$ by identifying ${k \phi(y)}$ with ${(y,k)}$ for ${y \in H, k \in K}$ , and using the cocycle $\displaystyle \rho(y) := \phi(hy)^{-1} g \phi(y).$

Thus, for instance, the unit shift ${x \mapsto x+1}$ on ${{\bf Z}/N{\bf Z}}$ can be thought of as a finite extension of the unit shift ${x \mapsto x+1}$ on ${{\bf Z}/M{\bf Z}}$ whenever ${N}$ is a multiple of ${M}$ .

Another example comes from Riemannian geometry. If ${M}$ is a Riemannian manifold that is a finite cover of another Riemannian manifold ${N}$ (with the metric on ${M}$ being the pullback of that on ${N}$ ), then (unit time) geodesic flow on the cosphere bundle of ${M}$ is a finite extension of the corresponding flow on ${N}$ .

Here, then, is the finite extension special case of the compact extension step in the proof of the multiple recurrence theorem:

Proposition 2 (Finite extensions) Let ${X \rtimes_\rho Y}$ be a finite extension of a measure-preserving system ${X}$ . If ${X}$ obeys the conclusion of the Furstenberg multiple recurrence theorem, then so does ${X \rtimes_\rho Y}$ .

Before we prove this proposition, let us first give the combinatorial analogue.

Lemma 3 Let ${A}$ be a subset of the integers that contains arbitrarily long arithmetic progressions, and let ${A = A_1 \cup \ldots \cup A_M}$ be a colouring of ${A}$ by ${M}$ colours (or equivalently, a partition of ${A}$ into ${M}$ colour classes ${A_i}$ ). Then at least one of the ${A_i}$ contains arbitrarily long arithmetic progressions.

Proof: By the infinite pigeonhole principle, it suffices to show that for each ${k \geq 1}$ , one of the colour classes ${A_i}$ contains an arithmetic progression of length ${k}$ .

Let ${N}$ be a large integer (depending on ${k}$ and ${M}$ ) to be chosen later. Then ${A}$ contains an arithmetic progression of length ${N}$ , which may be identified with ${\{0,\ldots,N-1\}}$ . The colouring of ${A}$ then induces a colouring on ${\{0,\ldots,N-1\}}$ into ${M}$ colour classes. Applying (the finitary form of) van der Waerden’s theorem, we conclude that if ${N}$ is sufficiently large depending on ${M}$ and ${k}$ , then one of these colouring classes contains an arithmetic progression of length ${k}$ ; undoing the identification, we conclude that one of the ${A_i}$ contains an arithmetic progression of length ${k}$ , as desired. $\Box$

Of course, by specialising to the case ${A={\bf Z}}$ , we see that the above Lemma is in fact equivalent to van der Waerden’s theorem.

Now we prove Proposition 2.

Proof: Fix ${k}$ . Let ${E}$ be a positive measure subset of ${X \rtimes_\rho Y = (X \times Y, {\mathcal X} \times {\mathcal Y}, \mu \times \nu, S)}$ . By Fubini’s theorem, we have

$\displaystyle \mu \times \nu(E) = \int_X f(x)\ d\mu(x)$

where ${f(x) := \nu(E_x)}$ and ${E_x := \{ y \in Y: (x,y) \in E \}}$ is the fibre of ${E}$ at ${x}$ . Since ${\mu \times \nu(E)}$ is positive, we conclude that the set $\displaystyle F := \{ x \in X: f(x) > 0 \} = \{ x \in X: E_x \neq \empty<a href=$ set \}" alt="\displaystyle F := \{ x \in X: f(x) > 0 \} = \{ x \in X: E_x \neq \emptyset \}" src="http://s0.wp.com/latex.php?latex=%5Cdisplaystyle+F+%3A%3D+%5C%7B+x+%5Cin+X%3A+f%28x%29+%3E+0+%5C%7D+%3D+%5C%7B+x+%5Cin+X%3A+E_x+%5Cneq+%5Cemptyset+%5C%7D&bg=ffffff&fg=000000&s=0">

is a positive measure subset of ${X}$ . Note for each ${x \in F}$ , we can find an element ${g(x) \in Y}$ such that ${(x,g(x)) \in E}$ . While not strictly necessary for this argument, one can ensure if one wishes that the function ${g}$ is measurable by totally ordering ${Y}$ , and then letting ${g(x)}$ the minimal element of ${Y}$ for which ${(x,g(x)) \in E}$ .

Let ${N}$ be a large integer (which will depend on ${k}$ and the cardinality ${M}$ of ${Y}$ ) to be chosen later. Because ${X}$ obeys the multiple recurrence theorem, we can find a positive integer ${n}$ and ${x \in X}$ such that

$\displaystyle x, T^n x, T^{2n} x, \ldots, T^{(N-1) n} x \in F.$

Now consider the sequence of ${N}$ points $\displaystyle S^{-mn}( T^{mn} x, g(T^{mn} x) )$

for ${m = 0,\ldots,N-1}$ . From (1), we see that $\displaystyle S^{-mn}( T^{mn} x, g(T^{mn} x) ) = (x, c(m)) \ \ \ \ \ (2)$

for some sequence ${c(0),\ldots,c(N-1) \in Y}$ . This can be viewed as a colouring of ${\{0,\ldots,N-1\}}$ by ${M}$ colours, where ${M}$ is the cardinality of ${Y}$ . Applying van der Waerden’s theorem, we conclude (if ${N}$ is sufficiently large depending on ${k}$ and ${|Y|}$ ) that there is an arithmetic progression ${a, a+r,\ldots,a+(k-1)r}$ in ${\{0,\ldots,N-1\}}$ with ${r>0}$ such that $\displaystyle c(a) = c(a+r) = \ldots = c(a+(k-1)r) = c$

for some ${c \in Y}$ . If we then let ${y = (x,c)}$ , we see from (2) that $\displaystyle S^{an + irn} y = ( T^{(a+ir)n} x, g(T^{(a+ir)n} x) ) \in E$

for all ${i=0,\ldots,k-1}$ , and the claim follows. $\Box$

Remark 1 The precise connection between Lemma 3 and Proposition 2 arises from the following observation: with ${E, F, g}$ as in the proof of Proposition 2, and ${x \in X}$ , the set $\displaystyle A := \{ n \in {\bf Z}: T^n x \in F \}$
can be partitioned into the classes $\displaystyle A_i := \{ n \in {\bf Z}: S^n (x,i) \in E' \}$
where ${E' := \{ (x,g(x)): x \in F \} \subset E}$ is the graph of ${g}$ . The multiple recurrence property for ${X}$ ensures that ${A}$ contains arbitrarily long arithmetic progressions, and so therefore one of the ${A_i}$ must also, which gives the multiple recurrence property for ${Y}$ .

Remark 2 Compact extensions can be viewed as a generalisation of finite extensions, in which the fibres are no longer finite sets, but are themselves measure spaces obeying an additional property, which roughly speaking asserts that for many functions ${f}$ on the extension, the shifts ${T^n f}$ of ${f}$ behave in an almost periodic fashion on most fibres, so that the orbits ${T^n f}$ become totally bounded on each fibre. This total boundedness allows one to obtain an analogue of the above colouring map ${c()}$ to which van der Waerden’s theorem can be applied.

mathtools

Monday, 13 June 2011

Multiple repeating and Furstenberg final statement

No comments:

Post a Comment