# Difference between revisions of "Furstenberg correspondence principle"

(New page: The Furstenberg correspondence principle equates density Ramsey theorems in combinatorics with recurrence theorems in ergodic theory. In our context, the principle equates the following t...) |
(→Version 6a implies Version 1: typo corrected) |
||

Line 27: | Line 27: | ||

== Version 6a implies Version 1 == | == Version 6a implies Version 1 == | ||

− | This is the hard direction. We argue by contradiction. If Version 1 failed, then there exists <math>\delta > 0</math>, a sequence of n going off to infinity, and a sequence of line-free sets <math>A^{(n)} \subset [3]^n</math>, each of density at least <math>\delta<math>. | + | This is the hard direction. We argue by contradiction. If Version 1 failed, then there exists <math>\delta > 0</math>, a sequence of n going off to infinity, and a sequence of line-free sets <math>A^{(n)} \subset [3]^n</math>, each of density at least <math>\delta</math>. |

We let <math>m = m^{(n)}</math> be an integer growing slowly with n, and <math>r = r^{(n)}</math> be an integer growing more slowly with n. For each <math>i \geq 0</math>, let <math>B_i</math> be the ball of radius i in <math>F_3</math> (i.e. the set of all strings of length at most i formed from the generators <math>1,2,3,1^{-1},2^{-1},3^{-1}</math>). For any d, define a ''simple'' d-dimensional [[combinatorial subspace]] to be a d-dimensional combinatorial subspace whose d wildcards <math>*_1,\ldots,*_d</math> each appear in just a single position <math>a_1,\ldots,a_d \in [n]</math>; we refer to these positions as the <math>directions</math> of the simple subspace. We say that a simple (d+1)-dimensional subspace is a ''j-extension'' of a simple d-dimensional subspace for some j=1,2,3, if the latter subspace can be obtained from the former by replacing the final wildcard <math>*_{d+1}</math> with j, and then we refer to the latter subspace as the ''j-slice'' of the former. | We let <math>m = m^{(n)}</math> be an integer growing slowly with n, and <math>r = r^{(n)}</math> be an integer growing more slowly with n. For each <math>i \geq 0</math>, let <math>B_i</math> be the ball of radius i in <math>F_3</math> (i.e. the set of all strings of length at most i formed from the generators <math>1,2,3,1^{-1},2^{-1},3^{-1}</math>). For any d, define a ''simple'' d-dimensional [[combinatorial subspace]] to be a d-dimensional combinatorial subspace whose d wildcards <math>*_1,\ldots,*_d</math> each appear in just a single position <math>a_1,\ldots,a_d \in [n]</math>; we refer to these positions as the <math>directions</math> of the simple subspace. We say that a simple (d+1)-dimensional subspace is a ''j-extension'' of a simple d-dimensional subspace for some j=1,2,3, if the latter subspace can be obtained from the former by replacing the final wildcard <math>*_{d+1}</math> with j, and then we refer to the latter subspace as the ''j-slice'' of the former. |

## Revision as of 09:54, 19 February 2009

The Furstenberg correspondence principle equates density Ramsey theorems in combinatorics with recurrence theorems in ergodic theory. In our context, the principle equates the following two statements:

**DHJ(3), Version 1**. For every [math]\delta \gt 0[/math] there exists n such that every subset [math]A \subset [3]^n[/math] of density at least [math]\delta[/math] contains a combinatorial line.

**DHJ(3), Version 6**. If the free group [math]F_3[/math] on three generators 1, 2, 3, acts in a measure-preserving fashion [math](T_w: X \to X)_{w \in F_3}[/math] on a probability space X, and E is a set of positive measure in X, then there exists a combinatorial line [math]w^1,w^2,w^3[/math] such that [math]T_{w^1}^{-1}(E) \cap T_{w^2}^{-1}(E) \cap T_{w^3}^{-1}(E)[/math] has positive measure.

To prove this equivalence, it is convenient to introduce an intermediate stage:

**DHJ(3), Version 6a**. Let [math](X_n)_{n \in {\Bbb Z}}[/math] be a family of probability spaces, and for each [math]w \in F_3[/math] of length [math]|w| \in {\Bbb Z}[/math] (where the inverse generators [math]1^{-1}, 2^{-1}, 3^{-1}[/math] are considered to have length -1) and [math]n \in {\Bbb Z}[/math], let [math]T_{w, n+|w|}: X_{n+|w|} \to X_n[/math] be an invertible measure-preserving map obeying the groupoid law

- [math] T_{vw, n+|vw|} = T_{v,n+|v|} T_{w,n+|vw|}[/math] (1)

for all integers n and group elements [math]v,w \in F_3[/math]. Let [math]E_0[/math] be a set of positive measure in [math]X_0[/math], then there exists a combinatorial line [math]w^1,w^2,w^3 \in [3]^n[/math] such that [math]T_{w^1,n}^{-1}(E_0) \cap T_{w^2,n}^{-1}(E_0) \cap T_{w^3,n}^{-1}(E_0)[/math] has positive measure in [math]X_n[/math].

## Version 1 implies Version 6

This is easy. Let [math]\delta[/math] be the measure of E, and let n be as in Version 1. From the first moment method and the measure-preserving nature of T, we see that the expected density of [math] \{ w \in [3]^n: x \in T_w^{-1}(E) \}[/math] is [math]\delta[/math]. Thus for a set of positive measure, this set has density at least [math]\delta[/math] and thus contains a combinatorial line. The claim now follows from the pigeonhole principle.

## Version 6 implies Version 6a

This is also easy. Let the setup be as in Version 6a. We define the product space [math]X := \prod_{n \in {\Bbb Z}} X_n[/math], and give it the action [math]T_w: X \to X[/math] of the free group [math]F_3[/math] by the formula

- [math] T_w ( x_n )_{n \in {\Bbb Z}} := ( T_{w,n+|w|} x_{n+|w|} )_{n \in {\Bbb Z}};[/math]

the groupoid law (1) ensures that this is an action, and the measure-preserving nature of the [math]T_{w,n+|w|}[/math] ensures that this is measure-preserving. The claim now follows by applying Version 6 to the cylinder set [math]E_0 \times \prod_{n \neq 0} X_n[/math].

## Version 6a implies Version 1

This is the hard direction. We argue by contradiction. If Version 1 failed, then there exists [math]\delta \gt 0[/math], a sequence of n going off to infinity, and a sequence of line-free sets [math]A^{(n)} \subset [3]^n[/math], each of density at least [math]\delta[/math].

We let [math]m = m^{(n)}[/math] be an integer growing slowly with n, and [math]r = r^{(n)}[/math] be an integer growing more slowly with n. For each [math]i \geq 0[/math], let [math]B_i[/math] be the ball of radius i in [math]F_3[/math] (i.e. the set of all strings of length at most i formed from the generators [math]1,2,3,1^{-1},2^{-1},3^{-1}[/math]). For any d, define a *simple* d-dimensional combinatorial subspace to be a d-dimensional combinatorial subspace whose d wildcards [math]*_1,\ldots,*_d[/math] each appear in just a single position [math]a_1,\ldots,a_d \in [n][/math]; we refer to these positions as the [math]directions[/math] of the simple subspace. We say that a simple (d+1)-dimensional subspace is a *j-extension* of a simple d-dimensional subspace for some j=1,2,3, if the latter subspace can be obtained from the former by replacing the final wildcard [math]*_{d+1}[/math] with j, and then we refer to the latter subspace as the *j-slice* of the former.

We will assign a random simple [math]m+|w|[/math]-dimensional subspace [math]V_w = \phi_w( [3]^{m+|w|} ) \subset [3]^n[/math] to each word [math]w \in B_r[/math], by the following recursive procedure:

- To the identity element id, we choose [math]V_{id}[/math] uniformly at random among all m-dimensional simple combinatorial subspaces in [math][3]^n[/math], such that the digits 1, 2, 3 each appear at least r times amongst the frozen coordinates.
- Now suppose recursively that [math]V_w[/math] has been chosen for all [math]v \in B_i[/math].
- If [math]v \in B_i \backslash B_{i-1}[/math] and [math]j \in \{1,2,3\}[/math], we define [math]V_{vj^{-1}}[/math] to be the j=slice of [math]V_v[/math].
- If [math]v \in B_i \backslash B_{i-1}[/math] and [math]j \in \{1,2,3\}[/math], we draw [math]V_{vj}[/math] uniformly and independently at random from all j-extensions of [math]V_v[/math].

For each integer s, let [math]\Gamma_s := \{w \in F_3: |w| = s \}[/math], and let [math]X_s := 2^{\Gamma_{-s}}[/math] be the power set of the countable set [math]\Gamma_{-n}[/math]. We have the maps [math]T_{w,s+|w|}: X_{s+|w|} \to X_s[/math] defined by

- [math]T_{w,s+|w|}(B) := w B[/math];

these are invertible and obeys the groupoid relation (1).

We can define a random element [math]x_0^{(n)} \in X_0[/math] by the formula

- [math]x_0^{(n)} := \{ w \in B_r \cap \Gamma_{-0}: \phi_w( 1^m ) \in A^{(n)} \}.[/math]

The distribution of this random element gives a probability measure [math]\mu_0^{(n)}[/math].

Let [math]E_0 \subset X_0[/math] be the cylinder set [math]E_0 := \{ B \subset \Gamma_0: id \in B \}.[/math]

**Lemma 1** (Density): [math]\mu_0^{(n)}(E_0) = \delta + o(1)[/math] as [math]n \to \infty[/math].

**Proof**. ...

**Lemma 2** (Asymptotic stationarity): If [math]w \in \Gamma_0[/math] and E is a cylinder set in [math]X_0[/math], then [math]\mu_0^{(n)}( T_{w,0}(E) ) = \mu_0( E ) + o(1)[/math] as [math]n \to \infty[/math].

**Proof**. ...

**Lemma 3** (Line-free-ness) For any combinatorial line [math]w^1,w^2,w^3[/math], the set [math]E_0 \cap T_{w^2 (w^1)^{-1},0}(E_0) \cap T_{w^3 (w^1)^{-1},0}(E_0)[/math] has zero measure in [math]\mu_0^{(n)}[/math].

**Proof**. ...

Now let [math]\mu_0[/math] be a vague subsequential limit of the [math]\mu_0^{(n)}[/math], then by Lemma 1, [math]E_0[/math] has positive measure, and by Lemma 2 the probability measure [math]\mu_0[/math] is invariant with respect to [math]T_{w,0}[/math] whenever [math]w \in \Gamma_0[/math], We can then uniquely define a probability measure [math]\mu_s[/math] on [math]X_s[/math] by requiring that [math]T_{w,s}: X_s \to X_0[/math] map [math]\mu_s[/math] to [math]\mu_0[/math] for all [math]w \in \Gamma_s[/math]. The hypotheses of Theorem 6a are now satisfied and so there exists a combinatorial line [math]w^1,w^2,w^3 \in [3]^s[/math], the set [math]E_0 \cap T_{w^2 (w^1)^{-1},0}(E_0) \cap T_{w^3 (w^1)^{-1},0}(E_0)[/math] has positive measure with respect to [math]\mu_s[/math], but this contradicts Lemma 3 and we are done.