# Abstract regularity lemma

Suppose we have a finite probability space $X = (X, \mu)$ such that every point in X occurs with positive probability. Given a $\sigma$-algebra (i.e. finite partition) ${\mathcal B}$ of this space, and a function $f: X \to {\Bbb R}$, define the conditional expectation ${\Bbb E}(f|{\mathcal B})$ to be the function from X to ${\Bbb R}$ whose value at any point x is the average of f on the cell of ${\mathcal B}$ 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 $2^M$ cells. If one partition ${\mathcal B}$ is coarser than another ${\mathcal B}'$, we write ${\mathcal B} \leq {\mathcal B}'$. Given two partitions ${\mathcal B}, {\mathcal B}'$, let ${\mathcal B} \vee {\mathcal B}'$ denote the common refinement.

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

1. (Coarse partition is low complexity) ${\mathcal A}_i^{coarse} \leq {\mathcal B}_i^M$, and ${\mathcal A}_i^{coarse}$ has complexity M.
2. (Fine partition is medium complexity) ${\mathcal A}_i^{fine} \leq {\mathcal B}_i^{M'}$, and ${\mathcal A}_i^{fine}$ has complexity M'.
3. (Coarse and fine approximations are close) $\| {\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$.
4. (Fine approximation is extremely high quality) For any $E_j \in {\mathcal B}_j^{M'+1}$, $E_k \in {\mathcal B}_k^{M'+1}$, we have $| {\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)$.

Proof: Run the following algorithm:

1. Initialise m=1, and set ${\mathcal A}_i^m$ to be trivial for i=0,1,2.
2. Find the {i,j,k}={0,1,2} and $E^m_j \in {\mathcal B}_j^{m+1}$, E^m_k \in {\mathcal B}_k^{m+1}[/itex] that maximises the quantity $| {\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} |$. Define $E_i^m$ to be the empty set.
3. For each i=0,1,2, define ${\mathcal A}_i^{m+1}$ to be the partition generated by ${\mathcal A}_i^m$ and $E_i^m$.

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

$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$.

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 $M = O_{F,\varepsilon}(1)$ such that

$E_{M + F(M)^2 + 1} \leq E_M + \varepsilon^2$.

By the pigeonhole principle, one can then find $M \leq M' \leq M+F(M)^2$ such that

$E_{M'+1} \leq E_{M'} + 1/F(M)^2$.

If we then set ${\mathcal A}_i^{coarse} := {\mathcal A}_i^M$ and ${\mathcal A}_i^{fine} := {\mathcal A}_i^{M'}$ 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]). $\Box$