Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-142 | 17th August 2018 01:41

A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds

RSS-Feed




TR18-142
Authors: Kaave Hosseini, Shachar Lovett
Publication: 17th August 2018 05:30
Downloads: 1072
Keywords: 


Abstract:

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