A bilinear Bogolyubov-Ruzsa lemma with polylogarithmic bounds

A bilinear Bogolyubov-Ruzsa lemma with polylogarithmic bounds, Discrete Analysis 2019:10, 14 pp.

The Bogolyubov-Ruzsa lemma in additive combinatorics states that if \(A\) is a subset of density \(\alpha\) of \(\mathbb{F}^n\), where \(\mathbb{F}\) is a finite field, then there exists a subspace \(V\leqslant \mathbb{F}^n\) of codimension \(c(\alpha)\) such that \(A+A-A-A \supseteq V\). Here we think of the dimension \(n\) as very large (and tending to infinity), and the density \(\alpha\) of \(A\) as constant. The Bogolyubov-Ruzsa lemma therefore implies that the iterated sumset \(A+A-A-A\) is highly structured, in the sense that it contains a very large subspace.

A straightforward Fourier argument, using the fact that \(A+A-A-A\) is the support of the iterated convolution \(1_A*1_A*1_{-A}*1_{-A}\), where \(1_A\) is the indicator function of the set \(A\), yields that \(c(\alpha)=O(\alpha^{-2})\). The (essentially) best known bound on \(c(\alpha)\), due to Sanders, is of the form \(O(\log^4(\alpha^{-1}))\).

The bound on the constant \(c(\alpha)\) matters for various reasons, one of which is that it translates almost immediately to a bound for a central result in additive combinatorics, namely the Freiman-Ruzsa theorem. This states that a subset \(A\) of \(\mathbb{F}^n\) whose sum set \(A+A\) is small, in the sense that \(|A+A|\leq K|A|\) for some constant \(K\), is efficiently contained in a subspace. An alternative formulation, which claims that a sizeable portion of \(A\) is concentrated on a small (affine) subspace, is conjectured to hold with bounds that are polynomial in the parameter \(K\). The Polynomial Freiman-Ruzsa conjecture has been shown to be equivalent to polynomial bounds in the inverse theorem for the \(U^3\) norm, which in turn is a cornerstone of what is now known as quadratic Fourier analysis and underpins all known quantitative approaches to Szemerédi’s theorem: that is, to counting arithmetic progressions of length greater than 3 in dense sets.

More recently, a bilinear version of the Bogolyubov-Ruzsa lemma has appeared independently in two different contexts. Bienvenu and Lê proved a bilinear Bogolyubov-Ruzsa lemma in order to show that in function fields the Möbius function has small correlation with (appropriately defined) quadratic phase functions. More precisely, they proved that given any \(A\subseteq \mathbb{F}^n\times \mathbb{F}^n\) of density \(\alpha\), there is a bilinear variety \(B\) of codimension \(c'(\alpha)\) such that \(\phi_{hhvvhh}(A)\supseteq B\). Here the operators \(\phi_v(A)=\{(x_1-x_2,y):(x_1,y),(x_2,y)\in A\}\) and \(\phi_h(A)=\{(x,y_1-y_2):(x,y_1),(x,y_2)\in A\}\) are the natural difference set operators on vertical and horizontal fibres, respectively, and \(\phi_{hhvvhh}(A)\) is simply the composition of six of these. A bilinear variety is a set of the form \(B=\{(x,y)\in V\times W :b_1(x,y)=...=b_{r}(x,y)=0\}\), whose codimension is defined to be the sum of the codimensions of the subspace \(V\) and \(W\) and the number \(r\) of bilinear forms involved.

Around the same time, Gowers and Milićević gave a proof of (in essence) the same statement with \(c'(\alpha)=\exp(\exp(\log^{O(1)}\alpha^{-1}))\) as part of the first quantitative proof of a \(U^4\) inverse theorem in vector spaces over finite fields. Bienvenu and Lê obtained a weaker \(c'(\alpha)=\exp(\exp(\exp(\log^{O(1)}\alpha^{-1})))\), but explicitly conjectured that a polylogarithmic bound should hold.

In this paper the authors prove such a bilinear Bogolyubov-Ruzsa lemma with a polylogarithmic bound. Specifically, a bilinear variety of codimension \(O(\log^{80}(\alpha^{-1}))\) is shown to be contained in \(\phi_{hvvhvvvhh}(A)\). This is achieved by applying the linear result in a carefully crafted sequence of steps, and is (up to the precise value of the exponent) the best one could hope to do given our current understanding of the linear case.