Bourgain's Lambda(p) selection theorem: a greedy proof with polynomial failure bounds

Abstract

We give a self-contained proof of Bourgain's finite $\Lambda (p)$ selection theorem with an explicit probability bound. For every $p>2$ and $N\ge 2$, given $N$ pairwise orthogonal functions bounded by one on a probability space, a uniformly chosen subsystem of cardinality $\lceil N^{\frac{2}{p}}\rceil$ satisfies the $\Lambda (p)$ inequality with probability at least $1-\frac{1}{N}$, with a constant depending only on $p$. The inequality holds simultaneously for all complex coefficient vectors. More generally, for every fixed $A>0$, the success probability is at least $1-\frac{1}{N^A}$ with a constant depending only on $p$ and $A$, and independent of $N$. The proof uses a greedy approximation in $L^r$, with $r>2$, whose potential decreases throughout all approximation scales. A single weighted bound on the cumulative number of updates controls a union bound over discrete update histories, and increasing the weight assigned to each history gives the prescribed failure exponent without changing the cardinality exponent.