Jean Bourgain was a Belgian—Fields Medal winning—mathematician who made significant contributions to various fields of mathematics, including analysis, geometry, and number theory. He was born on February 28, 1954, in Ostend, Belgium, and passed away on December 22, 2018. Bourgain was known for his deep insights and innovative techniques in solving complex mathematical problems.
I was reading Jean’s paper titled “Fourier Spectrum of Boolean Functions”. I was impressed how a 6-page paper contained such high density of mathematics. The theorem proved in this paper was later, famously, known as the Bourgain’s Junta Theorem. The goal I am chasing is proving the optimal \(k^{-\frac{1}{2}}\) instead of \(k^{-\frac{1}{2} - o(1)}\).
One of the best ways he makes his math “faster/more-efficient” is by compartmentalizing/blackbox-ing subroutines.
In this blog post, I will go through the paper and try to collect all the constants dropped by Bourgain. I also wish to understand the philosophical flow of the paper. I will also summarize the subroutines used, so that I can also use them in future.
Bourgain’s Extremely Successful Toolkit
Philosophical flow of the paper
Let \(f:\{-1,1\}^n \to \{0,1\}\) be a Boolean function. Let \(k > 0\) be an integer, and \(\gamma > 0\) a fixed constant. Assume \[ \sum\{|\hat{f}(S)|^2 \Bigg| |\hat{f}(S)| < \gamma 4^{-k^2}\} > \gamma^2 \] Then, \[ \sum_{|S| > k} |\hat{f}(S)|^2 \gtrsim k^{-\frac{1}{2} - o(1)} \]
TN: If total Fourier-mass of sets that all have very little indivdual Fourier-mass is high, then, the Fourier-mass on the tail of the Fourier spectrum is large.
Since \(\gamma\) is a constant, we can start by assuming the \(k\)-tail Fourier mass is less than \(\gamma^2/100\).
We introduce lots of parameters and then study important objects wrt those parameters. The important objects are chosen to break the problem down into recursive subproblems.
Breakdown: #1: Coordinate-level breakdown. Fixing a few coordinates, returns a Boolean function again, thus, coordinate-level breakdown is a natural idea. Objects like Influence treat coordinates as fundamental to the function, which further motivates this breakdown.
Criticism: Notice that the Boolean cube behaves quite close to the Gaussian measure (in a loose sense). In the Gaussian measure, there is no notion of “coordinate”, because there is an inherent spherical symmetry that acts. Could using tuned-spherical rotations and then proceeding with the rest of the arguments, be a good idea?
A common technique of Bourgain is to pick a breakdown dimension (coordinate breakdown, for example) and then remove a set of “exceptional” elements across that dimension. And, then proceed using some randomization/scale-based-pigeonholing/parameter-tuning based on the “non-exceptional” elements.
All while obtaining whatever results one can on the objects defined. Also reverse-engineering and creating objects according to the sort of results one needs.
Object: #1: Define \[ I_0 = \Bigg\{i \in [1, N] \Bigg| \sum_{i \in S, |S| \leq k} |\hat{f}(S)|^2 > \kappa \Bigg\} \] which is the set of all indices which have a higher than \(\kappa\) Fourier mass on sets of size \(\leq k\).
Playing with the possiblities across this chosen dimension of breakdown, one realizes \(I_0\) is the only meaningful object to work with. Very quickly, one notices \(|I_0| \leq \kappa^{-1} k\). The non-exceptional elements thus becomes \(I_0' = [N] \setminus I_0\).
Thus, studying the objects once again leads to the inequality \((4)\) pretty quickly. One needs some parameter tuning, but its not too hard. We get \[\mathcal{F}\left\{S \Bigg| S\int I_0' \neq \phi, |S| \leq k\right\}\] is higher than \(\gamma^2/2\).
Dyadic Partitioning: Track all the properties used about and around the chosen partition. Using the Ansatz of properties, could you obtain a better partition?
2 levels of randomization. Set level randomization and then further randomization within the indices in the sets.
Deconstructing the subroutines
\[ f_{x_2} - \mathbb{E}_{I(\omega)}[f_{x_2}] = \sum_{T \subset I_1, T \not\subset I(\omega)} F_{T}(x_2) w_T(\cdot) \]
Let \(f\) be a degree \(d\) Boolean function and \(p \in (1,2)\). \[ \|f\|_2 \leq (\frac{1}{\sqrt{p-1}})^{d} \|f\|_p \]