Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-142 | 17th August 2018 01:41

A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds


Authors: Kaave Hosseini, Shachar Lovett
Publication: 17th August 2018 05:30
Downloads: 82


The Bogolyubov-Ruzsa lemma, in particular the quantitative bounds obtained by Sanders, plays a central role
in obtaining effective bounds for the inverse $U^3$ theorem for the Gowers norms. Recently, Gowers and Mili\'cevi\'c
applied a bilinear Bogolyubov-Ruzsa lemma as part of a proof of the inverse $U^4$ theorem
with effective bounds.
The goal of this note is to obtain quantitative bounds for the bilinear Bogolyubov-Ruzsa lemma which are similar to
those obtained by Sanders for the Bogolyubov-Ruzsa lemma.

We show that if a set $A \subset \mathbb{F}^n \times \mathbb{F}^n$
has density $\alpha$, then after a constant number of horizontal and vertical sums, the set $A$ would contain a bilinear
structure of co-dimension $r=\log^{O(1)} \alpha^{-1}$. This improves
the results of Gowers and Mili\'cevi\'c which obtained similar results with a weaker bound of
$r=\exp(\exp(\log^{O(1)} \alpha^{-1}))$ and by Bienvenu and L\^e which obtained $r=\exp(\exp(\exp(\log^{O(1)} \alpha^{-1})))$.

ISSN 1433-8092 | Imprint