Abstract regularity lemma

From Polymath Wiki
Jump to: navigation, search

Suppose we have a finite probability space [math]X = (X, \mu)[/math] such that every point in X occurs with positive probability. Given a [math]\sigma[/math]-algebra (i.e. finite partition) [math]{\mathcal B}[/math] of this space, and a function [math]f: X \to {\Bbb R}[/math], define the conditional expectation [math]{\Bbb E}(f|{\mathcal B})[/math] to be the function from X to [math]{\Bbb R}[/math] whose value at any point x is the average of f on the cell of [math]{\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]2^M[/math] cells. If one partition [math]{\mathcal B}[/math] is coarser than another [math]{\mathcal B}'[/math], we write [math]{\mathcal B} \leq {\mathcal B}'[/math]. Given two partitions [math]{\mathcal B}, {\mathcal B}'[/math], let [math]{\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]{\mathcal B}_i^0 \subset {\mathcal B}_i^1 \subset \ldots[/math] be an increasing sequence of partitions, and let [math]f_i: X \to [0,1][/math] be a function. Let [math]\varepsilon \gt 0[/math], and let [math]F: {\Bbb R}^+ \to {\Bbb R}^+[/math] be a function. Then there exists integers [math]M \leq M' \leq O_{\varepsilon,F}(1)[/math], and partitions [math]{\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]{\mathcal A}_i^{coarse} \leq {\mathcal B}_i^M[/math], and [math]{\mathcal A}_i^{coarse}[/math] has complexity M.
  2. (Fine partition is medium complexity) [math]{\mathcal A}_i^{fine} \leq {\mathcal B}_i^{M'}[/math], and [math]{\mathcal A}_i^{fine}[/math] has complexity M'.
  3. (Coarse and fine approximations are close) [math]\| {\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] E_j \in {\mathcal B}_j^{M'+1}[/math], [math]E_k \in {\mathcal B}_k^{M'+1}[/math], we have [math]| {\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]{\mathcal A}_i^m[/math] to be trivial for i=0,1,2.
  2. Find the {i,j,k}={0,1,2} and [math]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]| {\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]E_i^m[/math] to be the empty set.
  3. For each i=0,1,2, define [math]{\mathcal A}_i^{m+1}[/math] to be the partition generated by [math]{\mathcal A}_i^m[/math] and [math]E_i^m[/math].
  4. Increment m to m+1, and return to Step 2.

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

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

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

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

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

If we then set [math]{\mathcal A}_i^{coarse} := {\mathcal A}_i^M[/math] and [math]{\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]\Box[/math]