A bilinear Bogolyubov-Ruzsa lemma with polylogarithmic bounds

- Department of Computer Science, University of California, San Diego
- More about Kaave Hosseini

- Department of Computer Science, University of California, San Diego
- More about Shachar Lovett

*Discrete Analysis*, June. https://doi.org/10.19086/da.8867.

### Editorial introduction

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 α of Fn, where F is a finite field, then there exists a subspace V⩽Fn of codimension c(α) such that A+A−A−A⊇V. Here we think of the dimension n as very large (and tending to infinity), and the density α 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 1A∗1A∗1−A∗1−A, where 1A is the indicator function of the set A, yields that c(α)=O(α−2). The (essentially) best known bound on c(α), due to Sanders, is of the form O(log4(α−1)).

The bound on the constant c(α) 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 Fn whose sum set A+A is small, in the sense that |A+A|≤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 U3 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⊆Fn×Fn of density α, there is a bilinear variety B of codimension c′(α) such that ϕhhvvhh(A)⊇B. Here the operators ϕv(A)={(x1−x2,y):(x1,y),(x2,y)∈A} and ϕh(A)={(x,y1−y2):(x,y1),(x,y2)∈A} are the natural difference set operators on vertical and horizontal fibres, respectively, and ϕhhvvhh(A) is simply the composition of six of these. A *bilinear variety* is a set of the form B={(x,y)∈V×W:b1(x,y)=...=br(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′(α)=exp(exp(logO(1)α−1)) as part of the first quantitative proof of a U4 inverse theorem in vector spaces over finite fields. Bienvenu and Lê obtained a weaker c′(α)=exp(exp(exp(logO(1)α−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(log80(α−1)) is shown to be contained in ϕ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.