Austin's proof II

This is a variant of Austin's proof that eschews Ramsey theory (except for pigeonhole principle) and/or density incrementation.

DHJ(3) If [math]\displaystyle{ \delta \gt 0 }[/math] and n is sufficiently large depending on [math]\displaystyle{ \delta }[/math], then any subset A of [math]\displaystyle{ [3]^n }[/math] of density at least [math]\displaystyle{ \delta }[/math] contains a combinatorial line.

Step 0: selection of parameters

We can assume that [math]\displaystyle{ \delta }[/math] is smaller than some small absolute constant.

We will need a number [math]\displaystyle{ \varepsilon \gt 0 }[/math] that is sufficiently small depending on [math]\displaystyle{ \delta }[/math]. This parameter measures the amount of regularity we will extract from the abstract regularity lemma.

We need a function [math]\displaystyle{ F: {\Bbb R}^+ \to {\Bbb R}^+ }[/math] that is sufficiently rapidly growing depending on [math]\displaystyle{ \varepsilon,\delta }[/math]. This measures the quality of the fine approximation from the abstract regularity lemma.

We need a number L which is sufficiently large depending on [math]\displaystyle{ \varepsilon,\delta,F }[/math]. This measures the number of scales between the partitions in the abstract regularity lemma.

We need a number J which is sufficiently large depending on [math]\displaystyle{ \varepsilon,\delta,F, L }[/math]. This measures the total number of scales in play.

We need a number [math]\displaystyle{ \kappa \gt 0 }[/math] which is sufficiently small depending on [math]\displaystyle{ \varepsilon, \delta, F, L, J }[/math]. This measures the separation between adjacent scales.

We assume n is sufficiently large depending on [math]\displaystyle{ \varepsilon, \delta, F, L, J, \kappa }[/math].

We introduce the scales [math]\displaystyle{ n = n_0 \gt n_1 \gt \ldots \gt n_J }[/math] by setting [math]\displaystyle{ n_j := \lfloor \kappa^j n \rfloor }[/math]. Note that [math]\displaystyle{ n_j }[/math] are all larger than 1.

Step 1: Setting up the probability space and basic partitions

We set up a probability space X by creating the following random variables:

1. First, select a string x at random from [math]\displaystyle{ [3]^n }[/math] using equal-slices measure. (NB: one could also use uniform measure here, but this is inferior as one then has to make each [math]\displaystyle{ n_{j+1} }[/math] something like [math]\displaystyle{ \kappa n_j^{1/2} }[/math] rather than [math]\displaystyle{ \kappa n_j }[/math].)
2. Set [math]\displaystyle{ A_0 := [n] }[/math], and then for [math]\displaystyle{ j=1,2,3,\ldots,J }[/math] in turn, set [math]\displaystyle{ A_j }[/math] to be a random subset of [math]\displaystyle{ A_{j-1} }[/math] of cardinality [math]\displaystyle{ n_j }[/math], chosen uniformly at random for any fixed choice of [math]\displaystyle{ x,A_0,\ldots,A_{j-1} }[/math].

Let X be the probability space generated by the random variables [math]\displaystyle{ x, A_0,\ldots,A_J }[/math]. This is a finite probability space, with every point occurring with positive probability (we can of course throw out all configurations that occur with zero probability).

Next, for [math]\displaystyle{ 0 \leq j \leq J }[/math] and [math]\displaystyle{ i=0,1,2 }[/math], we form the following [math]\displaystyle{ \sigma }[/math]-algebras (partitions):

1. [math]\displaystyle{ {\mathcal B}^j_{012} }[/math] is the space of all events that depend on the sets [math]\displaystyle{ A_0,\ldots,A_j }[/math], and on the string x.
2. [math]\displaystyle{ {\mathcal B}^j_{\emptyset} }[/math] is the space of all events that depend on the sets [math]\displaystyle{ A_0,\ldots,A_j }[/math], and on the values of the string x outside of [math]\displaystyle{ A_j }[/math].
3. [math]\displaystyle{ {\mathcal B}^j_i }[/math] is the space of all events that depend on the sets [math]\displaystyle{ A_0,\ldots,A_j }[/math], on the values of the string x outside of [math]\displaystyle{ A_j }[/math], and on the i-set of x inside [math]\displaystyle{ A_j }[/math] (i.e. the set of positions inside [math]\displaystyle{ A_j }[/math] where x takes the value i).

We observe the inclusions

[math]\displaystyle{ {\mathcal B}^j_\emptyset \leq {\mathcal B}^j_i \leq {\mathcal B}^j_{012} }[/math]

for i=0,1,2, and

[math]\displaystyle{ {\mathcal B}^j_S \leq {\mathcal B}^{j+1}_S }[/math]

for [math]\displaystyle{ S=\emptyset,0,1,2,012 }[/math].

Step 2. Regularisation

We apply the abstract regularity lemma with the functions [math]\displaystyle{ f_0=f_1=f_2:=1_A }[/math], the parameters [math]\displaystyle{ \varepsilon, F }[/math], and the [math]\displaystyle{ \sigma }[/math]-algebras [math]\displaystyle{ {\mathcal B}^{mL}_i }[/math] for [math]\displaystyle{ m=0,1,2,\ldots }[/math]. This gives us positive integers [math]\displaystyle{ M \leq M' \leq O_{F,\varepsilon}(1) }[/math] and factors [math]\displaystyle{ {\mathcal A}_i^{coarse} \leq {\mathcal A}_i^{fine} }[/math] for i=0,1,2 with the following properties for {i,j,k}={0,1,2}:

1. (Coarse partition is low complexity) [math]\displaystyle{ {\mathcal A}_i^{coarse} \leq {\mathcal B}_i^{ML} }[/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'L} }[/math], and [math]\displaystyle{ {\mathcal A}_i^{fine} }[/math] has complexity M'.
3. (Coarse and fine approximations are close) [math]\displaystyle{ \| {\Bbb E}(1_A | {\mathcal A}_j^{fine} \vee {\mathcal A}_k^{fine} ) - {\Bbb E}(1_A | {\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'L+L} }[/math], E_k \in {\mathcal B}_k^{M'L+L}</math>, we have [math]\displaystyle{ | {\Bbb E} (1_A - {\Bbb E}(1_A| {\mathcal A}_j^{fine} \vee {\mathcal A}_k^{fine} )) 1_{E_j} 1_{E_k} | \leq 1/F(M) }[/math].

For each {i,j,k}={0,1,2} we decompose

[math]\displaystyle{ 1_A = f_{i,U^\perp} + f_{i,err} + f_{i,U} }[/math]

where

[math]\displaystyle{ f_{i,U^\perp} = {\Bbb E}(1_A | {\mathcal A}_j^{coarse} \vee {\mathcal A}_k^{coarse} ) }[/math]

[math]\displaystyle{ f_{i,err} = {\Bbb E}(1_A | {\mathcal A}_j^{fine} \vee {\mathcal A}_k^{fine} ) - {\Bbb E}(1_A | {\mathcal A}_j^{coarse} \vee {\mathcal A}_k^{coarse} ) }[/math]

[math]\displaystyle{ f_{i,U} = 1_A - {\Bbb E}(1_A | {\mathcal A}_j^{fine} \vee {\mathcal A}_k^{fine} ) }[/math].

We record some salient features of these functions:

1. (Structure) [math]\displaystyle{ f_{i,U^\perp} }[/math] has density [math]\displaystyle{ \delta }[/math], takes values between 0 and 1, and is constant on intersections between cells of [math]\displaystyle{ {\mathcal A}_j^{coarse} }[/math] and cells of [math]\displaystyle{ {\mathcal A}_k^{coarse} }[/math] (there are at most [math]\displaystyle{ M^2 }[/math] such intersections in all).
2. (Smallness) [math]\displaystyle{ f_{i,err} }[/math] has an [math]\displaystyle{ L^2 }[/math] norm of at most [math]\displaystyle{ \varepsilon }[/math].
3. (Uniformity) [math]\displaystyle{ |{\Bbb E} f_{i,U} 1_{E_j} 1_{E_k}| \leq 1/F(M) }[/math] whenever [math]\displaystyle{ E_j \in {\mathcal B}_j^{ML+L} }[/math] and [math]\displaystyle{ E_j \in {\mathcal B}_k^{ML+L} }[/math].

We also observe

1. (Large intersection) We have [math]\displaystyle{ {\Bbb E} \prod_{i=0,1,2} f_{i,U^\perp} \gg \delta^4 }[/math].

Indeed, as [math]\displaystyle{ f_{i,U^\perp} }[/math] is a conditional expectation of [math]\displaystyle{ 1_A }[/math], we see that A has measure at most [math]\displaystyle{ \delta/10 }[/math] on the set [math]\displaystyle{ \{ f_{i,U^\perp} \leq \delta/10 \} }[/math]. From the union bound, we conclude that on at least half of A, [math]\displaystyle{ f_{i,U^\perp} \geq \delta/10 }[/math] for all i=0,1,2, and the claim follows.

Step 3. Secondary regularisation

This is a step which is needed in the DHJ setting but not in the triangle-removal setting, due to the multiplicity of scales.

For [math]\displaystyle{ 0 \leq l \leq L }[/math], define the energy

[math]\displaystyle{ E_l := \sum_{\{i,j,k\}=\{0,1,2\}} ??? }[/math]

???. Thus, by the pigeonhole principle we can find [math]\displaystyle{ 0 \leq l \lt L }[/math] such that

[math]\displaystyle{ E_{l+1}-E_l \ll_{F,\varepsilon} 1/L }[/math].

This implies that

???