Abstract regularity lemma

Suppose we have a finite probability space [math]\displaystyle{ X = (X, \mu) }[/math] such that every point in X occurs with positive probability. Given a [math]\displaystyle{ \sigma }[/math]-algebra (i.e. finite partition) [math]\displaystyle{ {\mathcal B} }[/math] of this space, and a function [math]\displaystyle{ f: X \to {\Bbb R} }[/math], define the conditional expectation [math]\displaystyle{ {\Bbb E}(f|{\mathcal B}) }[/math] to be the function from X to [math]\displaystyle{ {\Bbb R} }[/math] whose value at any point x is the average of f on the cell of [math]\displaystyle{ {\mathcal B} }[/math] that contains x.

We say that a finite partition of X has complexity M if it is generated by M or fewer sets, which implies that it has at most [math]\displaystyle{ 2^M }[/math] cells. If one partition [math]\displaystyle{ {\mathcal B} }[/math] is coarser than another [math]\displaystyle{ {\mathcal B}' }[/math], we write [math]\displaystyle{ {\mathcal B} \leq {\mathcal B}' }[/math]. Given two partitions [math]\displaystyle{ {\mathcal B}, {\mathcal B}' }[/math], let [math]\displaystyle{ {\mathcal B} \vee {\mathcal B}' }[/math] denote the common refinement.

Abstract regularity lemma Let X be a finite probability space, and for each i=0,1,2, let [math]\displaystyle{ {\mathcal B}_i^0 \subset {\mathcal B}_i^1 \subset \ldots }[/math] be an increasing sequence of partitions, and let [math]\displaystyle{ f_i: X \to [0,1] }[/math] be a function. Let [math]\displaystyle{ \varepsilon \gt 0 }[/math], and let [math]\displaystyle{ F: {\Bbb R}^+ \to {\Bbb R}^+ }[/math] be a function. Then there exists integers [math]\displaystyle{ M \leq M' \leq O_{\varepsilon,F}(1) }[/math], and partitions [math]\displaystyle{ {\mathcal A}_i^{coarse} \leq {\mathcal A}_i^{fine} }[/math] for i=0,1,2 with the following properties for all {i,j,k}={0,1,2}:

1. (Coarse partition is low complexity) [math]\displaystyle{ {\mathcal A}_i^{coarse} \leq {\mathcal B}_i^M }[/math], and [math]\displaystyle{ {\mathcal A}_i^{coarse} }[/math] has complexity M.
2. (Fine partition is medium complexity) [math]\displaystyle{ {\mathcal A}_i^{fine} \leq {\mathcal B}_i^{M'} }[/math], and [math]\displaystyle{ {\mathcal A}_i^{fine} }[/math] has complexity M'.
3. (Coarse and fine approximations are close) [math]\displaystyle{ \| {\Bbb E}(f_i | {\mathcal A}_j^{fine} \vee {\mathcal A}_k^{fine} ) - {\Bbb E}(f_i | {\mathcal A}_j^{coarse} \vee {\mathcal A}_k^{coarse} ) \|_{L^2(X)} \leq \varepsilon }[/math].
4. (Fine approximation is extremely high quality) For any [math]\displaystyle{ E_j \in {\mathcal B}_j^{M'+1} }[/math], [math]\displaystyle{ E_k \in {\mathcal B}_k^{M'+1} }[/math], we have [math]\displaystyle{ | {\Bbb E} (f_i - {\Bbb E}(f_i| {\mathcal A}_j^{fine} \vee {\mathcal A}_k^{fine} )) 1_{E_j} 1_{E_k} | \leq 1/F(M) }[/math].

Proof: Run the following algorithm:

1. Initialise m=1, and set [math]\displaystyle{ {\mathcal A}_i^m }[/math] to be trivial for i=0,1,2.
2. Find the {i,j,k}={0,1,2} and [math]\displaystyle{ E^m_j \in {\mathcal B}_j^{m+1} }[/math], E^m_k \in {\mathcal B}_k^{m+1}</math> that maximises the quantity [math]\displaystyle{ | {\Bbb E} (f_i - {\Bbb E}(f_i| {\mathcal A}_j^m \vee {\mathcal A}_k^m )) 1_{E_j^m} 1_{E_k^m} | }[/math]. Define [math]\displaystyle{ E_i^m }[/math] to be the empty set.
3. For each i=0,1,2, define [math]\displaystyle{ {\mathcal A}_i^{m+1} }[/math] to be the partition generated by [math]\displaystyle{ {\mathcal A}_i^m }[/math] and [math]\displaystyle{ E_i^m }[/math].
4. Increment m to m+1, and return to Step 2.

This gives increasing sequences of partitions [math]\displaystyle{ {\mathcal A}_i^m }[/math] for i=0,1,2 and [math]\displaystyle{ m=1,2,\ldots }[/math]. Define the energy

[math]\displaystyle{ E_m := \sum_{\{i,j,k\}=\{0,1,2\}} \| {\Bbb E}(f_i | {\mathcal A}_j^m \wedge {\mathcal A}_k^m ) \|_{L^2(X)}^2 }[/math].

This energy lies between 0 and 3!, and by Pythagoras' theorem, it is non-decreasing in m. Thus by the finite convergence principle, we can find [math]\displaystyle{ M = O_{F,\varepsilon}(1) }[/math] such that

[math]\displaystyle{ E_{M + F(M)^2 + 1} \leq E_M + \varepsilon^2 }[/math].

By the pigeonhole principle, one can then find [math]\displaystyle{ M \leq M' \leq M+F(M)^2 }[/math] such that

[math]\displaystyle{ E_{M'+1} \leq E_{M'} + 1/F(M)^2 }[/math].

If we then set [math]\displaystyle{ {\mathcal A}_i^{coarse} := {\mathcal A}_i^M }[/math] and [math]\displaystyle{ {\mathcal A}_i^{fine} := {\mathcal A}_i^{M'} }[/math] for i=0,1,2, the claims are then verified by a number of applications of Pythagoras and Cauchy-Schwarz (the computations are essentially the same as those in my [regularity lemma paper]). [math]\displaystyle{ \Box }[/math]