AN INFORMATION THEORETIC PROOF OF SZEMERÉDI’S REGULARITY LEMMA

TERENCE TAO

Abstract. Szemerédi’s regularity lemma (Theorem 2.6 below) is a basic tool in graph theory, and was first introduced to prove Szemerédi’s theorem on arithmetic progressions [6], [5]. This theorem also has an alternate proof by Furstenberg [1] based on what seems to be completely different methods, using sigma algebras, conditional expectation, and ergodic theory techniques. However, as we hope to demonstrate in these notes, the two techniques are not as totally distinct as it first appears, and one can use the language of sigma algebras and conditional expectation (and more precisely, the language of information theory) to give a proof of the regularity lemma, which is very much in the spirit of Furstenberg’s proof of Szemerédi’s theorem. This blended approach, combining the ergodic theory ideas of Furstenberg with the quantitative arguments of Szemerédi, is one of the key ingredients in the recent proof in [4] that the primes contain arbitrarily long arithmetic progressions. Actually, we give two proofs, an “energy increment” proof and an “entropy increment” proof.

1. Information theoretic notation

1.1. Probability and expectation. If f : V → R is any function defined on a finite non-empty set V, we define the expectation

E(f) := \frac{1}{|V |} ∑_{v∈V} f(v).

More generally, for any non-empty subset A of V we define

E(f(v)|v ∈ A) := \frac{1}{|A|} ∑_{v∈A} f(v)

and

P(A) := E(1_{A}) = |A|/|V |

where 1_{A} is of course the indicator function of A. In particular we can define the real Hilbert space L^{2}(V) to be the space of all functions f : V → R endowed with the inner product

⟨f, g⟩_{L^{2}(V)} := E(fg).

1.2. σ-algebras and conditional expectation. Define a σ-algebra on V to be any collection B of subsets of V which contain the empty set ∅ and the whole set V, and are closed under unions, intersections, and complementation. As V is a finite set, we will not need to distinguish between countable and uncountable unions or intersections. We define the atoms of a σ-algebra to be the minimal non-empty elements of B (with respect to set inclusion); it is clear that the atoms in B form a partition of V, and B consists precisely of arbitrary unions of its atoms (including the empty union ∅). A function f ∈ L^{2}(V) is said to be measurable with respect to a σ-algebra B if all the level sets of f lie in B, or equivalently if f is constant on each of the atoms of B. We define L^{2}(B) ⊆ L^{2}(V) to be the subspace of L^{2}(V) consisting of B-measurable functions, equipped with the same L^{2} norm and inner product. We can then define the conditional expectation operator f ↦ E(f|B) to be the orthogonal projection of L^{2}(V) to L^{2}(B). An equivalent definition of conditional expectation is

E(f|B)(x) := E(f(y)|y ∈ B(x))

for all x ∈ V, where B(x) is the unique atom in B which contains x. It is clear that conditional expectation is a linear self-adjoint orthogonal projection on L^{2}(B), preserves non-negativity, and also preserves constant functions.

If B′, B are two σ-algebras of V such that B′ ⊂ B then we say that B′ is a subalgebra of B, or equivalently that B′ is coarser than B (or B is finer than B′). Observe that if B′ is coarser than B then L^{2}(B′) is a subspace of L^{2}(B) and hence E(E(f|B)|B′) = E(f|B′).

If B, B′ are two σ-algebras on V, we use B ∨ B′ to denote the σ-algebra generated by B and B′ (i.e. the σ-algebra whose atoms are the intersections of atoms in B with atoms in B′).

If B is a σ-algebra on V, we define the entropy H(B) of B to be the quantity

H(B) := E(log \frac{1}{|B(x)|}|x ∈ V) = − ∑_{A an atom in B} P(A) log P(A).  (1)

From Jensen’s inequality we see that if B has n atoms, then^{1}

H(B) ≤ log n,  (2)

in particular the entropy is always non-negative. Another application of Jensen’s inequality yields the subadditivity property

H(B ∨ B′) ≤ H(B) + H(B′)  (3)

Also if B is finer than B′ then H(B) ≥ H(B′).

1.3. Cartesian products. Now we work on the Cartesian product V × V′ of two finite non-empty sets.

1In fact, we could run the arguments here using log n as the definition of entropy instead of H(B). However the notion given here is more robust (addition or removal of very small atoms will significantly alter the entropy, although they can allow log n to fluctuate quite a bit), and is more natural in information theory, especially with regards to such concepts as conditional entropy. See the second half of this paper.

If B and B′ are two sigma algebras on V and V′ respectively, we also define the sigma-algebra B ⊗ B′ on V × V′, whose atoms are the Cartesian products of atoms in B with atoms in B′. We observe the tensor property

H(B ⊗ B′) = H(B) + H(B′).  (4)

If K ∈ L^{2}(V × V′), we can define the weak operator norm ∥K∥_{w−op} to be the quantity

∥K∥_{w−op} := sup\{\frac{|⟨K, 1_{A} ⊗ 1_{A′}⟩_{L^{2}(V ×V′)}|}{P(A)^{1/2}P(A′)^{1/2}} : A ⊂ V; A′ ⊂ V′; A, A′ ≠ ∅\}. (5)

2. The regularity lemma

We can now give a probabilistic proof of the Szemerédi regularity lemma. We begin with an observation that any bounded function with large operator norm must correlate with a pair of σ-algebras of low entropy.

Lemma 2.1 (Non-randomness implies structure). Let V, V′ be finite non-empty sets, and let K ∈ L^{2}(V × V′) obey the bounds

|K(v, v′)| ≤ 1 for all (v, v′) ∈ V × V′

and

∥K∥_{w−op} ≥ δ

for some δ > 0. Then there exists σ-algebras B_{0} on V and B′_{0} on V′ such that

H(B_{0} ⊗ B′_{0}) ≤ 2 log 2  (6)

and

∥E(K|B_{0} ⊗ B′_{0})∥_{L^{2}(V ×V′)} ≥ δ.

Proof By the definition of weak operator norm, we can find non-empty sets A ⊂ V and A′ ⊂ V′ such that

|⟨K, 1_{A} ⊗ 1_{A′}⟩_{L^{2}(V ×V′)}| ≥ δP(A)^{1/2}P(A′)^{1/2}.  (7)

Thus if we define B_{0} := {∅, V, A, V \A} and B′_{0} := {∅, V, A′, V \A′} to be the σalgebras generated by A and A′ respectively, then (6) follows from (2), (4). On the other hand, since K is pointwise bounded by 1, we have

|⟨K, 1_{A} ⊗ 1_{A′}⟩_{L^{2}(V ×V′)}| ≤ ⟨1, 1_{A} ⊗ 1_{A′}⟩_{L^{2}(V ×V′)} = P(A)P(A′)

and hence (by (7))

P(A)P(A′) ≥ δ^{2}.

On the other hand, from (7) again we see that

E(K|B_{0} ⊗ B′_{0})(x, x′) ≥ \frac{δ}{P(A)^{1/2}P(A′)^{1/2}} for all (x, x′) ∈ A × A′

and hence

∥E(K|B_{0} ⊗ B′_{0})∥_{L^{2}(V ×V′)} ≥ \frac{δ}{P(A)^{1/2}P(A′)^{1/2}} P(A × A′)^{1/2} = δ

as desired.

Remark. In this lemma, we used the weak operator norm to detect the presence of non-randomness in K. However, other choices of norm are available. For instance, one can easily modify the above claim (with slightly worse constants) to handle the strong operator norm

∥K∥_{op} := sup\{\frac{|⟨K, f ⊗ f′⟩_{L^{2}(V ×V′)}|}{∥f∥_{L^{2}(V)}∥f′∥_{L^{2}(V′)}} : f ∈ L^{2}(V); f′ ∈ L^{2}(V′); f, f′ ≢ 0\}

instead of the weak operator norm. Similarly for the next two propositions below. However this (minor) improvement is not needed for the application to the regularity lemma. In the applications to the primes [4], we use the uniformity norms of Gowers [3] instead of the weak operator norm in order to detect non-randomness.

Remark. The above result has an analogue in Furstenberg’s proof of Szemerédi’s theorem, namely that if a compact operator commuting with a shift T on a probability space (X, B_{max}, P) is not identically zero, then B_{max} contains a compact T -invariant factor B_{0}.

We now give a relative version of the above lemma which is suitable for iterating.

Corollary 2.2 (Relative non-randomness implies relative structure). Let V, V′ be finite non-empty sets, and let K ∈ L^{2}(V × V′) obey the bounds

0 ≤ K(x, x′) ≤ 1 for all (x, x′) ∈ V × V′.

Suppose that there exists σ-algebras B on V and B′ on V′ such that

∥K − E(K|B ⊗ B′)∥_{w−op} > δ

for some δ > 0. Then there exists a σ-algebra B_{∗} ⊃ B on V and B′_{∗} ⊃ B′ on V′ such that

H(B_{∗} ⊗ B′_{∗}) ≤ H(B ⊗ B′) + 2 log 2  (8)

and

∥E(K|B_{∗} ⊗ B′_{∗})∥_{L^{2}(V ×V′)}^{2} ≥ ∥E(K|B ⊗ B′)∥_{L^{2}(V ×V′)}^{2} + δ^{2}.  (9)

Proof Write K̃ := K − E(K|B ⊗ B′), then we have |K̃(v, v′)| ≤ 1 for all (v, v′) ∈ V ×V′. Applying Lemma 2.1, we can find σ-algebras B_{0} on V and B′_{0} on V′ obeying (6), and such that

∥E(K̃|B_{0} ⊗ B′_{0})∥_{L^{2}(V ×V′)} ≥ δ.

Now define B_{∗} := B ∨ B_{0} and B′_{∗} := B′ ∨ B′_{0}, then (8) follows from (6) and (3). Meanwhile, since B_{∗} ⊗ B′_{∗} is a finer σ-algebra than B_{0} ⊗ B′_{0}, we have

∥E(K̃|B_{∗} ⊗ B′_{∗})∥_{L^{2}(V ×V′)} ≥ ∥E(K̃|B_{0} ⊗ B′_{0})∥_{L^{2}(V ×V′)} ≥ δ.

On the other hand, since B_{∗} ⊗ B′_{∗} is a finer σ-algebra than B ⊗ B′, we have by definition of K̃ that

E(K̃|B_{∗} ⊗ B′_{∗}) = E(K|B_{∗} ⊗ B′_{∗}) − E(K|B ⊗ B′).

For similar reasons, E(K|B_{∗} ⊗ B′_{∗}) − E(K|B ⊗ B′) is orthogonal to E(K|B ⊗ B′). The claim (9) then follows from Pythagoras’s theorem.

Remark. Again, the above result has an analogue in Furstenberg’s proof of Szemerédi’s theorem, namely that if a (relatively) compact operator commuting with a shift T on a probability space (X, B_{max}, P) relative to some invariant factor (X, B, P) is not identically zero, then B_{max} contains a relatively compact T -invariant extension B_{∗} of B.

We now iterate the above Corollary to give the the probabilistic version of Szemerédi’s lemma. We begin with a preliminary dichotomy.

Lemma 2.3 (Randomness/Structure dichotomy). let K ∈ L^{2}(V × V′) obey the bounds

0 ≤ K(x, x′) ≤ 1 for all (x, x′) ∈ V × V′,

and let B, B′ be σ-algebras on V, V′ respectively. Let ε, δ > 0 be arbitrary. Then there exists a σ-algebra B̃ ⊇ B finer than B, and a σ-algebra B̃′ ⊇ B′ obeying the entropy bounds

H(B̃ ⊗ B̃′) ≤ H(B ⊗ B′) + (2 log 2)(\frac{ε^{4}}{δ^{2}} + 1)  (10)

such that one of the following statements must hold:

(i) (Randomness) We have

∥K − E(K|B̃ ⊗ B̃′)∥_{w−op} ≤ δ  (11)

and

∥E(K|B̃ ⊗ B̃′)∥_{L^{2}(V ×V′)}^{2} ≤ E(K|B ⊗ B′)∥_{L^{2}(V ×V′)} + ε^{4}.  (12)

(ii) (Structure) We have

∥E(K|B̃ ⊗ B̃′)∥_{L^{2}(V ×V′)}^{2} > ∥E(K|B ⊗ B′)∥_{L^{2}(V ×V′)}^{2} + ε^{4}.  (13)

Proof We perform the following algorithm to construct B̃ and B̃′.

Step 0. Initialize B̃ := B and B̃′ := B′. Observe that the estimate (12) is trivially

true at present. Step 1. If (11) holds, then we are in the “Randomness” half of the dichotomy and

can now halt the algorithm. Step 2. If instead we have ∥K − E(K|B̃ ⊗ B̃′)∥_{op} > δ, then we use Corollary 2.2 to

find a σ-algebra B̃_{∗} finer than B̃, and a σ-algebra B̃′_{∗} finer than B̃′. Then replace B̃ by B̃_{∗}, and B̃′ by B̃′_{∗}. Observe from (8) that the entropy H(B̃⊗B̃′) has increased by at most 2 ln 2 by this procedure, while from (9) we see that ∥E(K|B̃ ⊗ B̃′)∥_{L^{2}(V ×V′)}^{2} has increased by at least δ^{2}.

Step 3. If (13) holds, then we are in the “Structure” half of the dichotomy and can now halt the algorithm. Otherwise, (12) holds and we return to Step 1.

Since the quantity ∥E(K|B̃ ⊗ B̃′)∥_{L^{2}(V ×V′)}^{2} increases by at least δ^{2} at each stage, and we halt the algorithm if this quantity increases by more than ε^{4}, we see that this algorithm can only iterate for at most \frac{ε^{4}}{δ^{2}} + 1 steps to land in one of the two cases of the dichotomy. The entropy bound (10) then follows by iterating (8).

By iterating the above Lemma again, we obtain a version of Szemerédi’s regularity lemma in the probabilistic setting.

Corollary 2.4 (Szemerédi’s lemma, probabilistic version). Let V, V′ be finite nonempty sets, and let K ∈ L^{2}(V × V′) obey the bounds

0 ≤ K(x, x′) ≤ 1 for all (x, x′) ∈ V × V′.

Let 0 < ε ≤ 1. Then there exists σ-algebras B ⊂ B̃ on V and B′ ⊆ B̃′ on V′ such that

H(B ⊗ B′) ≤ H(B̃ ⊗ B̃′) ≤ C(ε)  (14)

where C(ε) is a finite quantity depending only on ε, and such that we have the estimates

∥K − E(K|B̃ ⊗ B̃′)∥_{w−op} ≤ e^{−2H(B⊗B′)/ε}  (15)

and

∥E(K|B̃ ⊗ B̃′) − E(K|B ⊗ B′)∥_{L^{2}(V ×V′)} ≤ ε^{2}.  (16)

Proof We perform the following algorithm to construct B, B′, B̃, and B̃′.

Step 0. Initialize B := {∅, V } and B′ := {∅, V′}. Note that we have H(B ⊗ B′) = 0

at present. Step 1. We apply Lemma 2.3 with δ := e^{−2H(B⊗B′)/ε}, to obtain σ-algebras B̃ ⊃ B

and B̃′ ⊃ B′ such that

H(B̃ ⊗ B̃′) ≤ C(ε, H(B ⊗ B′))  (17)

and such that we are either in the Randomness or Structure half of the dichotomy.

Step 2. If we are in the Randomness half of the dichotomy, then we have both (15)

and (16) and we now halt the algorithm. Step 3. If instead we are in the Structure half of the dichotomy, then we reset

B := B̃ and B′ := B̃′, and observe from (13) that the quantity ∥E(K|B ⊗ B′)∥_{L^{2}(V ×V′)}^{2} will increase by at least ε^{4} when one does so. We now return to Step 1.

In light of (13) and the trivial bound

∥∥E(K|B ⊗ B′)∥_{L^{2}(V ×V′)}^{2} ≤ ∥K∥_{L^{2}(V ×V′)}^{2} ≤ 1

we see that this algorithm must halt after at most \frac{1}{ε^{4}} iterations. Applying (17) once for each such iteration and starting with the trivial bound noted in Step 0, we obtain the bound (14) as claimed (with a bound which is basically an exponential tower of height 1/ε^{4}).

Remark. The above theorem is related to Furstenberg’s structure theorem, which decomposes any ergodic system into a weakly mixing extension of a tower of compact extensions. The above arguments are a blend of the ergodic arguments of Furstenberg and the more quantitative arguments of Szemerédi, and are closely related to the arguments used in Section 7 of [4], which established arbitrarily long progressions in the primes. The tower bound is unfortunately more or less sharp, see [2].

Remark. One can think of E(K|B ⊗ B′) as an “homogenized” approximant to K; the bounds (15), (16) show that this approximation is quite accurate for many purposes. This approximant is much simpler than K itself; in particular, its level sets are the union of O(C(ε)) Cartesian products. The fact that there are two error terms (15), (16), one of which is small in the relatively strong L^{2} norm (which can be thought of in the operator sense as the Hilbert-Schmidt norm), while the other is extremely small in the weak operator norm, which is substantially weaker, is a consequence of the doubly inductive nature of the argument, and seems in fact to be an essential feature of the regularity lemma (given that it must have at least tower growth in the constants [2]).

We are now ready to prove Szemerédi’s regularity lemma in its more traditional form.

Definition 2.5. A bipartite graph is a triplet (V, V′, E) where V, V′ are two finite non-empty sets, and E ⊂ V × V′. If ε > 0, we say that a bipartite graph (V, V′) is ε-regular if we have

|E ∩ (A × A′)| = \frac{|A × A′|}{|V × V′|}|E| + O(ε|V × V′|)

for all A ⊆ V and A′ ⊆ V′.

Theorem 2.6 (Szemeredi regularity lemma). Let (V, V′, E) be a bipartite graph, and let 0 < ε ≤ 1. Assume that |V |, |V′| ≥ C(ε). Then there exists a number 1 ≤ M ≤ C(ε) and decompositions

V = V_{0} ∪ V_{1} ∪ … ∪ V_{M}; V′ = V′_{0} ∪ V′_{1} ∪ … ∪ V′_{M}

such that

• (Exceptional set) |V_{0}| = O(ε|V |) and |V′_{0}| = O(ε|V′|).

• (Uniform partition) |V_{i}| = |V_{i′}| and |V′_{j}| = |V′_{j′}| for all 1 ≤ i, i′ ≤ M and

1 ≤ j, j′ ≤ M.

• (Regularity) (V_{i}, V′_{j}, E ∩ (V_{i} × V′_{j})) is ε-regular for all but O(εM^{2}) of the

pairs 1 ≤ i ≤ M, 1 ≤ j ≤ M.

Proof Let K := 1_{E}, thus K(v, v′) := 1 when there is an edge between v, v′ and K(v, v′) := 0 otherwise. We apply Corollary 2.4 to obtain σ-algebras B, B′, B̃, B̃′ obeying the properties of that lemma. We set H := H(B ⊗ B′), and define

M := ⌊e^{−H/ε}/ε⌋.  (18)

Thus by (14) we have M ≤ C(ε) as desired.

Call an atom A in B small if we have P(A) ≤ \frac{1}{εM}, and large otherwise. By (1) we have

∑_{A small} P(A) ≤ \frac{1}{log(εN)} ∑_{A} P(A) log \frac{1}{P(A)} = \frac{1}{log(εM)}H = O(ε)

and hence by (14) we see that if M is large enough depending on ε, we have

P( ⋃_{A small} A) = O(ε).

Thus we may place all the small atoms in V_{0}. For all the large atoms A, we can split the atom into disjoint sets V_{i}, each of which has cardinality ⌊|V |/(1+O(ε))M⌋, plus an error which has cardinality O(ε|A|). Adding up all these errors will give another set of probability O(ε) which can be absorbed into V_{0}. The remaining sets V_{i} each have the same cardinality ⌊|V |/(1 + O(ε))M⌋ and so there must be (1 + O(ε))M of them. We can discard O(ε)M of these to place into the exceptional set once again, and we end up with the decomposition

V = V_{0} ∪ V_{1} ∪ … ∪ V_{M}

obeying the first two of the required properties. Similarly we can decompose V′ = V′_{0} ∪ … ∪ V′_{M}.

Now we must establish regularity. From (16) we have

E((E(K|B̃ ⊗ B̃′)(v, v′) − E(K|B ⊗ B′)(v, v′))^{2}|v ∈ V, v′ ∈ V′) = O(ε^{4}).

We split this into the components V_{i} and V′_{j} (discarding the negligible errors V_{0}, V′_{0}) to obtain

E(E((E(K|B̃⊗B̃′)(v, v′)−E(K|B⊗B′)(v, v′))^{2}|v ∈ V_{i}, v′ ∈ V′_{j})|1 ≤ i, j ≤ M) = O(ε^{4}).

By Markov’s inequality, we thus have

O(E(K|B̃ ⊗ B̃′)(v, v′) − E(K|B ⊗ B′)(v, v′))^{2}|v ∈ V_{i}, v′ ∈ V′_{j}) = O(ε^{2}). (19)

for all but at most O(εM^{2}) pairs (i, j).

Fix a pair (i, j) for which (19) holds. In particular, for any A ⊂ V_{i} and A′ ⊂ V′_{j} we have by Cauchy-Schwarz

E(E(K|B̃ ⊗ B̃′)(v, v′) − E(K|B ⊗ B′)(v, v′)|v ∈ V_{i}, v′ ∈ V′_{j}) = O(ε).

On the other hand, from (15), (5) we have

∑_{v∈A} ∑_{v′∈A′} K(v, v′) − E(K|B̃ ⊗ B̃′)(v, v′) = e^{−2H/ε}|V ||V′|

which by (18) implies

E(K(v, v′) − E(K|B̃ ⊗ B̃′)(v, v′)|v ∈ V_{i}, v′ ∈ V′_{j}) = O(ε).

Adding the two, and observing that E(K|B ⊗ B′) is equal to some constant value d_{ij} on V_{i} × V′_{j} (since V_{i} is contained in an atom of B by construction, and similarly for V′_{j}) we obtain

∑_{v∈A} ∑_{v′∈A′} K(v, v′) = d_{ij}|A||A′| + O(ε|V_{i}||V′_{j}|)

for all A ⊆ V_{i} and A′ ⊆ V_{j}. Using the definition of K, we can write this as

|E ∩ (A × A′)| = d_{ij}|A||A′| + O(ε|V_{i}||V′_{j}|).

We can solve for d_{ij} by substituting A := V_{i} and A′ := V′_{j}, to obtain

|E ∩ (A × A′)| = \frac{|E ∩ (V_{i} × V′_{j})|}{|V_{i} × V′_{j}|}|A||A′| + O(ε|V_{i}||V′_{j}|)

and thus (V_{i}, V′_{j}, E ∩ (V_{i} × V_{j})) is ε-regular, and the claim follows.

Remark. It is an easy matter to modify the above argument to handle non-bipartite graphs. Also one can also impose an arbitrary lower bound on the size of M by observing that any uniform subdivision of an ε-regular graph will also give an ε′- regular graph (for some slightly worse ε′, depending on the number of subdivisions. It should also be clear that there are analogues of this lemma when the vertex set V (which was essentially given the uniform probability distribution here) is replaced by any other probability space.

3. More on entropy

We now recall some more facts on entropy. In this section it is convenient to talk about the entropy of a discrete random variable X instead of a σ-algebra B, defined by setting H(X) := H(B_{X}), where B_{X} is the σ-algebra generated by X. In other words,

H(X) := − ∑_{x∈range(X)} P(X = x) log P(X = x).  (20)

Intuitively, H(X) measures the amount of information carried by X. Thus for instance if X is a Boolean variable which equals 1 with probability τ, then we have H(X) = τ log \frac{1}{τ} + (1 − τ) log \frac{1}{1−τ} with the convention 0 log 0 := 0. In particular all Boolean variables have entropy at most log 2.

For readers unfamiliar with entropy inequalities, it may help to keep in mind the analogy between entropy of random variables and the somewhat simpler concepts of cardinality of finite sets or dimension of vector spaces, which are more special instances of valuations on submodular lattices; see Table 1. In particular, every entropy inequality or identity has a counterpart for sets or vector spaces. However we caution that the converse is not true.

We use the notation X ↦ Y to denote the statement that Y is determined by X, or more precisely that there exists a deterministic function F such that Y = F (X); this is clearly a transitive and reflexive relation. An equivalent formulation is that the σ-algebra determined by Y is coarser than the σ-algebra determined by X. Note that this notation is compatible with the notation X ↦ E for events E, in that X ↦ E if and only if X ↦ 1_{E}. We say that two random variables X and Y are equivalent, and write X ↔ Y, if X ↦ Y and Y ↦ X, or equivalently if X and Y determine the same σ-algebra; this is clearly an equivalence relation on random variables.

Random variables X, Y, Z Sets A, B, C Vector spaces U, V, W
H(X)  |A|  dim(U)
X ↔ Y  A = B  U = V
0  ∅  {0}
(X, Y)  A ∪ B  U + V
(X|Y)  A\B  (U + V)/V
H(X|Y)  |A\B|  dim((U + V)/V)
X ↦ Y  A ⊇ B  U ⊇ V
X, Y independent  A, B disjoint U, V linearly independent
I(X : Y) |A ∩ B| dim(U ∩ V)
I(X : Y |Z)  |(A ∩ B)\C| dim((U + W) ∩ (V + W)/W)

Table 1. Analogy between discrete random variables, finite sets, and finite-dimensional vector spaces. Indeed sets are a special case of vector spaces (identifying A with the vector space of real-valued functions on A), and vector spaces are a special case of random variables (identifying Ω with the ambient vector space, and U with the orthogonal projection onto U; one can work in a finite field geometry to keep everything discrete).

We say that X is deterministic if X takes only a single value, or in other words the σ-algebra generated by X is trivial. Note that all deterministic random variables are equivalent to the zero random variable 0, and we shall thus write X ↔ 0 to denote that X is deterministic.

If X and Y are random variables, we use X, Y to denote the joint random variable (X, Y). Given any event E with non-zero probability, we define the conditioning (X|E) of X to be the random variable restricted to E, which is now thought of as a new probability space with probability measure P(F |E) := P(F ∩E)/P(E). If Y is another random variable, we informally regard (X|Y) as an ensemble of conditional random variables (X|Y = y), each of which is assigned a weight P(Y = y); this informal convention shall be reflected in our choice of notation below.

If X is a discrete random variable, we define the essential range range(X) of X to denote those x for which P(X = x) > 0; this is then a finite set. We define the Shannon entropy H(X) (or entropy for short) of X to be the quantity

If Y is another discrete random variable, we define the conditional Shannon entropy H(X|Y) to be the quantity

H(X|Y) := ∑_{y∈range(Y)} P(Y = y)H(X|Y = y)
= − ∑_{y∈range(Y)} ∑_{x∈range(X)} P(Y = y)P(X = x|Y = y) log P(X = x|Y = y).

(21)

Intuitively, H(X|Y) measures the amount of additional information that X carries if one already knows the value of Y. From the identity H(X) = H(X|0) we see that the concept of entropy is a special case of that of conditional entropy. One easily verifies the Bayes identity

H(X, Y) = H(X|Y) + H(Y).  (22)

One can then define the mutual information

I(X : Y) := H(X) + H(Y) − H(X, Y) = H(X) − H(X|Y) = H(Y) − H(Y |X), (23)

which intuitively represents the amount of information that X and Y share in common. We can generalize this notion to the conditional mutual information

I(X : Y |Z) := H(X|Z) + H(Y |Z) − H(X, Y |Z)
= H(X|Z) − H(X|Y, Z)
= H(Y |Z) − H(Y |X, Z)
= H(X, Y, Z) + H(Z) − H(X, Z) − H(Y, Z).

(24)

Equivalently, we have

I(X : Y |Z) = ∑_{z∈range(Z)} I(X : Y |Z = z)P(Z = z)  (25)

where I(X : Y |Z = z) is the mutual information of (X|Z = z) and (Y |Z = z). Clearly I(X : Y) and I(X : Y |Z) are symmetric, and I(X : Y) = I(X : Y |0). Also we observe that I(X : X) = H(X) and I(X : X|Z) = H(X|Z), so the entropy and conditional entropy are special cases of the mutual and conditional mutual information respectively. From (24) we observe the telescoping identity

I(X : Y |Z) + I(X : W |Y, Z) = I(X : Y, W |Z).  (26)

We summarize the basic properties of these quantities below.

Proposition 3.1 (Shannon entropy inequalities). Let X, X′, Y, Y′, Z, Z′ be discrete random variables.

• (Non-negativity) We have

H(X), H(X|Y), I(X : Y), I(X : Y |Z) ≥ 0.  (27)

• (Equivalence) If X ↔ X′, Y ↔ Y′, Z ↔ Z′, then

H(X) = H(X′)
H(X|Y) = H(X′|Y′)
I(X : Y) = I(X′, Y′)
I(X : Y |Z) = I(X′ : Y′|Z′).

(28)

In a similar spirit, if (X, Z) ↔ (X′, Z), (Y, Z) ↔ (Y′, Z), and (X, Y, Z) ↔

(X′, Y′, Z) then
H(X|Z) = H(X′|Z); I(X : Y |Z) = I(X′ : Y′|Z).  (29)

• (Monotonicity) If X ↦ X′, Y ↦ Y′, Z ↦ Z′, then

H(X) ≥ H(X′)
H(X|Y′) ≥ H(X|Y) ≥ H(X′|Y)
I(X : Y) ≥ I(X′ : Y), I(X : Y′)
I(X : Y |Z) ≥ I(X′ : Y |Z), I(X : Y′|Z).

(30)

Thus the entropy H(X) is monotone increasing in X, the conditional entropy H(X|Y) is increasing in X and decreasing in Y, and the mutual information I(X : Y) or I(X : Y |Z) is increasing in X, Y. We caution however that I(X : Y |Z) is not necessarily decreasing^{2} in Z, however we do have the weaker version

I(X : Y |Z) ≤ I(X : Y, Z|Z′).  (31)

In a similar spirit we have

0 ≤ I(X : Y |Z) ≤ H(X|Z) ≤ H(X).  (32)

• (Subadditivity) We have

H(X, Y) ≤ H(X) + H(Y); H(X, Y |Z) ≤ H(X|Z) + H(Y |Z).  (33)

We caution however that the mutual information is not subadditive.

• (Determinism) We have

X ↔ 0 ⟺ H(X) = 0  (34)

and

X ↦ X′ ⟺ H(X′|X) = 0.  (35)

• (Independence) We have

X, Y independent ⟺ I(X : Y) = 0  (36)
X, Y independent conditionally on Z ⟺ I(X : Y |Z) = 0,  (37)

where conditional independence means that (X|Z = z) and (Y |Z = z) are independent for all z in the essential range of Z.

Proof The non-negativity H(X) ≥ 0 is clear from (20), and the non-negativity H(X|Y) ≥ 0 then follows from (21). From the convexity of x log x, (21) and Jensen’s inequality we obtain the inequality H(X|Y) ≤ H(X), which by (23) implies that I(X : Y) ≥ 0. Finally from (25) we conclude that I(X : Y |Z) ≥ 0. This establishes (27).

The equivalence (28) is clear from the definitions, and (29) then follows from (28) and (22), (24). The first two inequalities in (30) follow from the non-negativity (27) of mutual and conditional mutual information. Next, from (28), (26), (27) we see that if Y ↦ Y′

2Consider for instance let x_{1}, x_{2}, x_{3} be three independent uniform random variables in Z/2Z (i.e the result of flipping three fair coins), and set X = x_{1} + x_{2}, Y = x_{2} + x_{3}, and Z = x_{3} + x_{1}.

Then X and Y are independent unconditionally, but become dependent (indeed, they determine each other) conditioning on Z, in fact I(X : Y |0) = 0 ≱ I(X : Y |Z, 0) = log 2. This, incidentally, is one instance in which the set-theoretic analogy in Table 1 breaks down, although the vector space analogy continues to be accurate here (consider for instance the vector space (Z/2Z)^{3} = {(x_{1}, x_{2}, x_{3}) : x_{1}, x_{2}, x_{3} ∈ Z/2Z} and the spaces U := {x_{1} + x_{2} = 0}, V := {x_{2} + x_{3} = 0}, W := {x_{3} + x_{1} = 0}).

I(X : Y |Z) = I(X : Y, Y′|Z) = I(X : Y′|Z) + I(X : Y |Y′, Z) ≥ I(X : Y′|Z)

which proves the last inequality in (30); the other inequalities then follow. Similarly, if Z ↦ Z′ then by (26), (27), (28)

I(X : Y, Z|Z′) = I(X : Z|Z′) + I(X : Y |Z, Z′) ≥ I(X : Y |Z, Z′) = I(X : Y |Z)

which gives (31). The inequalities (32) follow from (27) since H(X) = H(X|Z) + I(X : Z) and H(X|Z) = I(X : Y |Z)+H(X|Y, Z), while the inequalities (33) follow from (27) and (23), (24).

The equivalence (34) is clear from (20), and (35) follows from (34) and (21). To prove (36), we return to the Jensen inequality proof of the inequality H(X|Y) ≤ H(X) and observe that equality occurs if and only if the conditioned random variables (X|Y = y) all have the same distribution, i.e. that X, Y are independent. The claim (37) then follows by conditioning on each event Z = z separately using (25).

4. Another information-theoretic regularity lemma

We now give an alternate approach to the regularity lemma, introduced in [8]. Instead of approximating a kernel K or graph G by a partition of two vertex sets V_{1}, V_{2}, we now approximate a random variable Y by some bounded entropy coarsenings of two random variables X_{1} and X_{2} (which can be unbounded entropy and also do not need to be independent).

Lemma 4.1 (Information-theoretic regularity lemma). [8] Let X_{1}, X_{2}, Y be discrete random variables such that H(Y) ≤ m for some m ≥ 0. Let F : R^{+} → R^{+} be an arbitrary function, and ε > 0. Then there exists random variables Z_{1}, Z_{2} (the “coarse approximation”) and Z′_{1}, Z′_{2} (the “fine approximation”) with the following properties.

• (Determinism) We have the determinism relations

X_{1} ↦ Z′_{1} ↦ Z_{1}; X_{2} ↦ Z′_{2} ↦ Z_{2}.  (38)

• (Coarse approximation has bounded entropy) We have

H(Z_{1}, Z_{2}) ≤ H(Z′_{1}, Z′_{2}) ≤ C(m, F, ε).  (39)

• (Coarse and fine approximations are close) We have

I(Y : Z′_{1}, Z′_{2}|Z_{1}, Z_{2}) ≤ ε.  (40)

• (Fine approximation is nearly optimal) For any random variables W_{1}, W_{2} with X_{1} ↦ W_{1} and X_{2} ↦ W_{2} we have

I(Y : W_{1}, W_{2}|Z′_{1}, Z′_{2}) ≤ \frac{H(W_{1}, W_{2})}{F (H(Z_{1}, Z_{2}))}.  (41)

Proof To construct Z_{1}, Z_{2}, Z′_{1}, Z′_{2} we perform the following “entropy incrementation” algorithm.

• Step 0. Initialize Z_{1} = Z_{2} = 0.

• Step 1. Let Z′_{1}, Z′_{2} be random variables which minimize the quantity

H(Y |Z′_{1}, Z′_{2}) + \frac{H(Z′_{1}, Z′_{2})}{F (H(Z_{1}, Z_{2}))}  (42)

subject to the constraints X_{1} ↦ Z′_{1} ↦ Z_{1} and X_{2} ↦ Z′_{2} ↦ Z_{2}. (If there are several such maximizers, we select among them arbitrarily).

• Step 2. If we have

H(Y |Z_{1}, Z_{2}) − H(Y |Z′_{1}, Z′_{2}) > ε

then we replace Z_{1}, Z_{2} with Z′_{1}, Z′_{2} respectively, and return to Step 1. Otherwise, we terminate the algorithm.

We remark that because X_{1}, X_{2} are discrete variables, the number of possibilities for the random variables Z′_{1}, Z′_{2} is finite up to equivalence. Hence a minimizer to the quantity (42) always exists. Intuitively, Z′_{1}, Z′_{2} is constructed to capture as much information about Y as is possible while remaining determined by X_{1}, X_{2}; the slight penalty term in (42) is designed to keep some control the entropy of Z′_{1}, Z′_{2} (otherwise it would be as large as that of X_{1}, X_{2}, for which we have no bounds). Observe that every time we return from Step 2 to Step 1, the quantity H(Y |Z_{1}, Z_{2}) (which measures the amount of information in Y that remains to be captured by Z_{1}, Z_{2}) decreases by at least ε. On the other hand, from (32) we see that this quantity lies between 0 and H(Y) ≤ m. Thus the above algorithm must halt after at most m/ε iterations. It is also clear that the random variables Z_{1}, Z_{2}, Z′_{1}, Z′_{2} generated by this algorithm will obey the determinism relationships (38) and (40).

Also, if W_{1}, W_{2} are any random variables determined by X_{1}, X_{2} respectively, then by comparing the minimizer Z′_{1}, Z′_{2} against the competitor (Z′_{1}, W_{1}), (Z′_{2}, W_{2}) (which obeys the required constraints), then we have (41) as desired.

Now we compare the entropies of Z_{1}, Z_{2} and Z′_{1}, Z′_{2}. Since Z̃ obeys the constraints in the minimization problem (42), we have

H(Y |Z′_{1}, Z′_{2}) + \frac{H(Z′_{1}, Z′_{2})}{F (H(Z_{1}, Z_{2}))} ≤ H(Y |Z_{1}, Z_{2}) + \frac{H(Z_{1}, Z_{2})}{F (H(Z_{1}, Z_{2}))}.

As observed earlier, the first summand on either side ranges between 0 and m. Thus we have (after some rearranging)

H(Z′_{1}, Z′_{2}) ≤ H(Z_{1}, Z_{2}) + mF (H(Z_{1}, Z_{2})).

In particular, every time we return from Step 2 to Step 1, the quantity H(Z_{1}, Z_{2}) increases by at most mF (H(Z_{1}, Z_{2})). From Step 0, the initial value of H(Z_{1}, Z_{2}) is 0. Since the number of iterations is bounded by m/ε, we see that the final value of H(Z_{1}, Z_{2}) is bounded a finite (but extremely large^{3}) quantity C(m, F, ε), defined as the value obtained after m/ε iterations of the map M ↦ M + mF (M) applied to 0.

3This is the origin of the notorious tower exponential-type growth bounds in Szemerédi’s regularity lemma, see [2] for some discussion of this issue. In the cases d > 1 we will in fact obtain d-fold iterated tower exponentials due to the inductive nature of the argument; based on

To pass from an entropy formulation to an expectation formulation, we need a way to pass from control of entropy to control of expectations. A clue to how to do this is provided by the following observation: if Y ↦ Y′ and I(X : Y |Y′) = 0, then we know from (37) that X and Y are independent conditionally on Y′. In particular, if X takes values in a vector space, this implies that E(X|Y) = E(X|Y′). In other words, whenever I(X : Y |Y′) = H(X|Y′)−H(X|Y) is zero, so is E(X|Y′)−E(X|Y). This may help motivate the following lemma, which is a perturbative version of the above observation.

Lemma 4.2 (Relation between entropy and expectation). [8] Let X, Y, Y′ be discrete random variables with Y ↦ Y′, and with X taking values in the unit interval {−1 ≤ x ≤ 1}. Then we have

E(|E(X|Y′) − E(X|Y)|) ≤ 2I(X : Y |Y′)^{1/2}.

More informally, this lemma asserts that approximate conditional independence in the entropy sense implies approximate conditional independence in an expectation sense. The bound 2I(X : Y |Y′)^{1/2} is not best possible, but any bound which decays to zero as I(X : Y |Y′) → 0 will be sufficient for our purposes.

Proof The idea will be to repeat the Jensen inequality argument used to prove the Shannon entropy inequalities, but now exploit the observation that the function −x log x is not only concave but also strictly concave. Let us first verify this in the special case Y′ ↔ 0, which is already the most important case. Let 1 ≤ x_{1}, …, x_{n} ≤ −1 be the essential range of X, and let y_{1}, …, y_{m} be the essential range of Y. For any 1 ≤ i ≤ n and 1 ≤ j ≤ m, define

p_{ij} := P(X = x_{i}|Y = y_{j}); q_{j} := P(Y = y_{j}).

Then we observe that 0 ≤ p_{ij}, q_{j} ≤ 1 and that ∑_{j=1}^{m} q_{j} = 1. If we define f : [0, 1] → R to be the function f(x) := −x log x (with the convention f(0) := 0), we thus have by (21) and Bayes’ formula that

I(X : Y) = H(X) − H(X|Y)

≥ ∑_{i=1}^{n}(f(∑_{j=1}^{m} q_{j}p_{ij}) − ∑_{j=1}^{m} q_{j}f(p_{ij})).

Now observe that f is concave, indeed we have f′′(x) = −1/x for all x ∈ (0, 1]. Thus by Taylor’s theorem with remainder, if we write \overline{p_{i}} := ∑_{j=1}^{m} q_{j}p_{ij} = P(X = x_{i}), then

f(p_{ij}) ≤ f(\overline{p_{i}}) + f′(\overline{p_{i}})(p_{ij} − \overline{p_{i}}) − \frac{1}{2}(p_{ij} − \overline{p_{i}})^{2}/p_{ij}^{∗}

the results in [2] it seems likely that such enormous - though still primitive recursive - bounds are essential for this lemma.

where p_{ij}^{∗} is a quantity between p_{ij} and \overline{p_{i}}. Inserting this into the preceding estimate and noting that ∑_{j=1}^{m} q_{j}(p_{ij} − \overline{p_{i}}) = 0, we conclude that

∑_{j=1}^{m} q_{j} ∑_{i=1}^{n}(p_{ij} − \overline{p_{i}})^{2}/p_{ij}^{∗} ≤ 2I(X : Y).

Now we compute using the boundedness of x_{i} and Cauchy-Schwarz, as well as the crude estimate p_{ij}^{∗} ≤ \overline{p_{i}} + p_{ij},

E(|E(X) − E(X|Y)|) = ∑_{j=1}^{m} q_{j}|E(X) − E(X|Y = y_{j})|

= ∑_{j=1}^{m} q_{j}| ∑_{i=1}^{n} x_{i}(\overline{p_{i}} − p_{ij})|

≤ ∑_{j=1}^{m} q_{j} ∑_{i=1}^{n} |\overline{p_{i}} − p_{ij}|

≤ (∑_{j=1}^{m} q_{j} ∑_{i=1}^{n} |\overline{p_{i}} − p_{ij}|^{2}/p_{ij}^{∗})^{1/2}(∑_{j=1}^{m} q_{j} ∑_{i=1}^{n} p_{ij}^{∗})^{1/2}

≤ [2I(X : Y) ∑_{j=1}^{m} q_{j} ∑_{j=1}^{n} \overline{p_{i}} + p_{ij}]^{1/2}

= 2I(X : Y)^{1/2}.

Now we consider the general case when Y′ is not deterministic. In that case we write

E(|E(X|Y′)−E(X|Y)|) = ∑_{y′∈range(Y′)} P(Y′ = y′)E(|E(X|Y′ = y′)−E(X|Y; Y′ = y′)|).

Applying the preceding computation, we conclude

E(|E(X|Y′) − E(X|Y)|) ≤ ∑_{y′∈range(Y′)} P(Y′ = y′)2I(X : Y |Y′ = y′)^{1/2}.

Applying Cauchy-Schwarz again we conclude

E(|E(X|Y′)−E(X|Y)|) ≤ 2\sqrt{∑_{y′∈range(Y′)} P(Y′ = y′)I(X : Y |Y′ = y′)} = 2I(X : Y |Y′)^{1/2}

as desired.

Now we can give a re-proof of Corollary 2.4 in the most important case, namely when K is the indicator of a graph; this is enough to reprove Theorem 2.6. One can also modify the above arguments to give a hypergraph regularity lemma; see [8].

Theorem 4.3 (Szemerédi’s lemma, probabilistic version). Let V_{1}, V_{2} be finite nonempty sets, and let G ⊆ V_{1} × V_{2}. Let 0 < ε ≤ 1. Then there exists σ-algebras B_{1} ⊂ B′_{1} on V_{1} and B_{2} ⊆ B′_{2} on V_{2} such that

H(B_{1} ⊗ B_{2}) ≤ H(B′_{1} ⊗ B′_{2}) ≤ C(ε)  (43)

where C(ε) is a finite quantity depending only on ε, and such that we have the estimates

∥1_{G} − E(1_{G}|B′_{1} ⊗ B′_{2})∥_{w−op} ≤ e^{−2H(B_{1}⊗B_{2})/ε}  (44)

and

∥E(1_{G}|B′_{1} ⊗ B′_{2}) − E(1_{G}|B_{1} ⊗ B_{2})∥_{L^{2}(V_{1}×V_{2})} ≤ ε^{2}.  (45)

Proof Let X_{1} be a random variable taking values in V with the uniform distribution, and let X_{2} be a random variable taking values in V′ with the uniform distribution (with X_{1}, X_{2} independent). Let Y = 1_{(X_{1},X_{2})∈G} be the indicator of the event that X_{1}, X_{2} lies in G. Since Y is a Boolean variable we see that H(Y) ≤ log 2. Applying the previous lemma (with ε replaced by ε^{8}/4, and F to be chosen later), we can then find random variables X_{1} ↦ Z′_{1} ↦ Z_{1} and X_{2} ↦ Z′_{2} ↦ Z_{2} obeying the bounds

H(Z_{1}, Z_{2}) ≤ H(Z′_{1}, Z′_{2}) ≤ C(F, ε).  (46)

and

I(Y : Z′_{1}, Z′_{2}|Z_{1}, Z_{2}) ≤ ε^{8}/4.  (47)

and

I(Y : W_{1}, W_{2}|Z′_{1}, Z′_{2}) ≤ \frac{H(W_{1}, W_{2})}{F (H(Z_{1}, Z_{2}))}.  (48)

whenever X_{1} ↦ W_{1} and X_{2} ↦ W_{2}. We then set B_{1}, B_{2}, B′_{1}, B′_{2} to be the σ-algebras determined by Z_{1}, Z_{2}, Z′_{1}, Z′_{2} respectively.

The inclusions B_{1} ⊂ B′_{1} and B_{2} ⊂ B′_{2} are clear. From (47) and Lemma 4.2 we have

E(|E(Y |Z′_{1}, Z′_{2}) − E(Y |Z_{1}, Z_{2})|) ≤ ε^{4};

since |E(Y |Z′_{1}, Z′_{2}) − E(Y |Z_{1}, Z_{2})| is bounded, we thus have

E(|E(Y |Z′_{1}, Z′_{2}) − E(Y |Z_{1}, Z_{2})|^{2}) ≤ ε^{4}

which gives (45). Now we establish (44). From the definition of weak operator norm, it suffices to show that

|E(1_{A_{1}} ⊗ 1_{A_{2}}(1_{G} − E(1_{G}|B′_{1} ⊗ B′_{2})))| ≤ e^{−2H(B_{1}⊗B_{2})/ε}P(A_{1})^{1/2}P(A_{2})^{1/2}

whenever A_{1} and A_{2} are events in V_{1}, V_{2}; writing this in terms of X_{1}, X_{2}, Y, Z_{1}, Z_{2}, Z′_{1}, Z′_{2} this becomes

|E(1_{X_{1}∈A_{1}}1_{X_{2}∈A_{2}}(Y −E(Y |Z′_{1}, Z′_{2})))| ≤ e^{−2H(B_{1}⊗B_{2})/ε}P(X_{1} ∈ A_{1})^{1/2}P(X_{2} ∈ A_{2})^{1/2}.

On the one hand, we have the crude bound

|E(1_{X_{1}∈A_{1}}1_{X_{2}∈A_{2}}(Y −E(Y |Z′_{1}, Z′_{2})))| ≤ |E(1_{X_{1}∈A_{1}}1_{X_{2}∈A_{2}})| = P(X_{1} ∈ A_{1})P(X_{2} ∈ A_{2}).

On the other hand, if we let W_{1} := 1_{X_{1}∈A_{1}} and W_{2} := 1_{X_{2}∈A_{2}} then

E(1_{X_{1}∈A_{1}}1_{X_{2}∈A_{2}}Y) = E(1_{X_{1}∈A_{1}}1_{X_{2}∈A_{2}}E(Y |Z′_{1}, W_{1}, Z′_{2}, W_{2}))

and hence

|E(1_{X_{1}∈A_{1}}1_{X_{2}∈A_{2}}(Y − E(Y |Z′_{1}, Z′_{2})))| ≤ E(|E(Y |Z′_{1}, W_{1}, Z′_{2}, W_{2}) − E(Y |Z′_{1}, Z′_{2})|).

Using Lemma 4.2 we conclude

|E(1_{X_{1}∈A_{1}}1_{X_{2}∈A_{2}}(Y − E(Y |Z′_{1}, Z′_{2})))| ≤ 2I(Y : Z′_{1}, W_{1}, Z′_{2}, W_{2}|Z′_{1}, Z′_{2})^{1/2}.

From (26) we observe that

I(Y : Z′_{1}, W_{1}, Z′_{2}, W_{2}|Z′_{1}, Z′_{2}) = I(Y : W_{1}, W_{2}|Z′_{1}, Z′_{2})

and hence by (48)

|E(1_{X_{1}∈A_{1}}1_{X_{2}∈A_{2}}(Y − E(Y |Z′_{1}, Z′_{2})))| ≤ 2\frac{H(W_{1}, W_{2})^{1/2}}{F (H(Z_{1}, Z_{2}))^{1/2}} .

Since W_{1}, W_{2} are Boolean variables, H(W_{1}, W_{2}) ≤ 2 log 2, and hence

|E(1_{X_{1}∈A_{1}}1_{X_{2}∈A_{2}}(Y − E(Y |Z′_{1}, Z′_{2})))| ≤ \frac{2\sqrt{2 log 2}}{F (H(Z_{1}, Z_{2}))^{1/2}} .

If we set F (x) := 8 log 2e^{4x/ε}, we conclude (44). Finally, (14) follows from (46).

References

[1] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204–256.

[2] T. Gowers, Lower bounds of tower type for Szemerédi’s uniformity lemma, Geom. Func. Anal. 7 (1997), 322–337.

[3] T. Gowers, A new proof of Szemerédi’s theorem, GAFA 11 (2001), 465-588.

[4] B. Green, T. Tao, The primes contain arbitrarily long proper arithmetic progressions, preprint.

[5] E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 89–104.

[6] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 299–345.

[7] E. Szemerédi, Regular partitions of graphs, in “Proc. Colloque Inter. CNRS” (J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, D. Sotteau, eds.) (1978), 399–401.

[8] T. Tao, Information theory, relative versions of the hypergraph regularity and removal lemmas, the Szemerédi-Furstenberg-Katznelson theorem, and prime constellations in number fields, preprint.

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu