Lean Bourgain Extractor

4 Energy Growth

Theorem 4.1
#

Let \(S_1, S_2, \dots , S_k \subseteq S\) be finite sets with \(|S_i| \geq \delta |S|\) for all \(i\). Then, there exists \(i\) such that \(|\{ j | |S_j \cap S_i| \geq (\delta ^2 / 2) k\} | \geq (\delta ^2 / 2) k\)

Proof

This is exactly Claim 3.3.6 in [Dvi12].

Theorem 4.2
#

Let \(A, T\) be finite sets with \(Q(A, \lambda A) \geq \frac{|A|^3}K\) for all \(\lambda \in T\). Then there exist sets \(A', T'\) with \(\frac{|A|}{16 K} \leq |A'|\) and \(\frac{|T|}{2^{17} K^4} \leq |T'|\), such that \(T' \subseteq \operatorname{\operatorname {Stab}}_{2^{110} K^{42}}(A')\).

Proof

This is exactly Theorem 3.3.5 in [Dvi12], using BSG from LeanAPAP.

[Dvi12]: Dvir, Zeev. Incidence Theorems and Their Applications , now, 2012, doi: 10.1561/0400000056.