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.