# Furstenberg correspondence principle

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 [3]^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, in which the group action is replaced by a groupoid action:

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 [3]^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 [3]^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 [3]^n$, each of density at least $\delta$.

We let $m = m^{(n)}$ be an integer growing 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( [3]^{m+|w|} ) \subset [3]^n$ to each word $w \in B_m$, 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 $[3]^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$ and some $0 \leq i \lt m$.
• 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_m \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) \geq \delta + o(1)$ as $n \to \infty$.

Proof. The quantity $\mu_0^{(n)}(E_0)$ is the probability that $\phi_{id}(1^m)$ lies in $A^{(n)}$. This quantity is essentially uniformly distributed in $[3]^n$ (up to an error of total variation o(1)) and the claim follows. $\Box$

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}^{-1}(E) ) = \mu_0^{(n)}( E ) + o(1)$ as $n \to \infty$.

Proof. The cylinder set E can be defined in terms of a finite number of events $\{ B \subset \Gamma_0: w_i \in B \}$ for i=1,...,k (say). It then suffices to show that the joint distribution of $(\phi_{w_1}(1^m),\ldots,\phi_{w_k}(1^m))$ and $(\phi_{w w_1}(1^m),\ldots,\phi_{w w_k}(1^m))$ on $([3]^n)^k$ differ by o(1) in total variation. This is some tedious calculation which I will omit here. $\Box$

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. By construction, $\phi_{id}(1^m), \phi_{w^2 (w^1)^{-1}}(1^m), \phi_{w^3 (w^1)^{-1}}(1^m)$ form a combinatorial line, and thus cannot all lie in A, and the claim follows. $\Box$

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 [3]^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.