# Difference between revisions of "Furstenberg correspondence principle"

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 $\delta \gt 0$ there exists n such that every subset $A \subset ^n$ of density at least $\delta$ contains a combinatorial line.

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

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

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

$T_{vw, n+|vw|} = T_{v,n+|v|} T_{w,n+|vw|}$ (1)

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

## Version 1 implies Version 6

This is easy. Let $\delta$ 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 $\{ w \in ^n: x \in T_w^{-1}(E) \}$ is $\delta$. Thus for a set of positive measure, this set has density at least $\delta$ 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 $X := \prod_{n \in {\Bbb Z}} X_n$, and give it the action $T_w: X \to X$ of the free group $F_3$ by the formula

$T_w ( x_n )_{n \in {\Bbb Z}} := ( T_{w,n+|w|} x_{n+|w|} )_{n \in {\Bbb Z}};$

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

## Version 6a implies Version 1

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

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

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

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

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

$T_{w,s+|w|}(B) := w B$;

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

We can define a random element $x_0^{(n)} \in X_0$ by the formula

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

The distribution of this random element gives a probability measure $\mu_0^{(n)}$.

Let $E_0 \subset X_0$ be the cylinder set $E_0 := \{ B \subset \Gamma_0: id \in B \}.$

Lemma 1 (Density): $\mu_0^{(n)}(E_0) = \delta + o(1)$ as $n \to \infty$.

Proof. ...

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

Proof. ...

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

Proof. ...

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