# A bilinear Bogolyubov-Ruzsa lemma with polylogarithmic bounds

Kaave Hosseini Supported by NSF grant CCF-1614023. Shachar Lovett Supported by
NSF grant CCF-1614023.

###### Abstract

The Bogolyubov-Ruzsa lemma, in particular the quantitative bound obtained by
Sanders, plays a central role in obtaining effective bounds for the $U^{3}$
inverse theorem for the Gowers norms. Recently, Gowers and Milićević applied a
bilinear Bogolyubov-Ruzsa lemma as part of a proof of the $U^{4}$ inverse
theorem with effective bounds. The goal of this note is to obtain a
quantitative bound for the bilinear Bogolyubov-Ruzsa lemma which is similar to
that 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$ contains a bilinear structure of codimension
$r=\log^{O(1)}\alpha^{-1}$. This improves the result of Gowers and Milićević,
who obtained a similar statement with a weaker bound of
$r=\exp(\exp(\log^{O(1)}\alpha^{-1}))$, and by Bienvenu and Lê, who obtained
$r=\exp(\exp(\exp(\log^{O(1)}\alpha^{-1})))$.

title = A bilinear Bogolyubov-Ruzsa lemma with polylogarithmic bounds, author
= Kaave Hosseini and Shachar Lovett, plaintextauthor = Kaave Hosseini, Shachar
Lovett, keywords = Additive combinatorics, Bogolyubov-Ruzsa lemma, bilinear
set., year=2019, volume=XX, number=10, received=30 August 2018, revised=21 May
2019, published=14 June 2019, doi=10.19086/daXXX,

[classification=text]

##  1 Introduction

One of the key ingredients in the proof of the quantitative inverse theorem
for the Gowers $U^{3}$ norm over finite fields, due to Green and Tao [GT08]
and Samorodnitsky [Sam07], is an inverse theorem concerning the structure of
sumsets. The best known result in this direction is the quantitatively
improved Bogolyubov-Ruzsa lemma due to Sanders [San12a]. Before introducing
it, we fix some common notation. We assume that $\mathbb{F}=\mathbb{F}_{p}$ is
a prime field, where $p$ is a fixed constant, and suppress the exact
dependence on $p$ in the bounds. Given a subset $A\subset\mathbb{F}^{n}$ its
density is $\alpha=|A|/|\mathbb{F}|^{n}$. The sumset of $A$ is
$2A=A+A=\\{a+a^{\prime}:a,a^{\prime}\in A\\}$, and its difference set is
$A-A=\\{a-a^{\prime}:a,a^{\prime}\in A\\}$.

######  Theorem 1.1.

([San12a]) Let $A\subset\mathbb{F}^{n}$ be a subset of density $\alpha$. Then
there exists a subspace $V$ of $\mathbb{F}^{n}$ of codimension
$O(\log^{4}\alpha^{-1})$ such that $V\subset 2A-2A$ .

In fact, the link between the $U^{3}$ inverse theorem and inverse sumset
results runs deeper. It was shown in [GT10, Lov12] that a $U^{3}$ inverse
theorem with (to date conjectural) polynomial bounds is equivalent to the
polynomial Freiman-Ruzsa conjecture, one of the central open problems in
additive combinatorics. Given this, one cannot help but wonder whether there
is a more general inverse sumset phenomenon that would naturally correspond to
quantitative inverse theorems for the $U^{k}$ norms. In a recent breakthrough,
Gowers and Milićević [GM17b] showed that this is indeed the case, at least for
the $U^{4}$ norm. They used a bilinear generalization of Theorem 1.1 to obtain
a quantitative $U^{4}$ inverse theorem.

To be able to explain this result we need to introduce some notation. Let
$A\subset\mathbb{F}^{n}\times\mathbb{F}^{n}$. Define two operators, capturing
subtraction on horizontal and vertical fibers as follows:

$\displaystyle\phi_{\textup{h}}(A):=\\{(x_{1}-x_{2},y):(x_{1},y),(x_{2},y)\in
A\\},$
$\displaystyle\phi_{\textup{v}}(A):=\\{(x,y_{1}-y_{2}):(x,y_{1}),(x,y_{2})\in
A\\}.$

Given a word $w\in\\{\textup{h},\textup{v}\\}^{k}$ define
$\phi_{w}=\phi_{w_{1}}\circ\ldots\circ\phi_{w_{k}}$ to be their composition. A
_bilinear variety_ $B\subset\mathbb{F}^{n}\times\mathbb{F}^{n}$ of codimension
$r=r_{1}+r_{2}+r_{3}$ is a set defined as follows:

$B=\\{(x,y)\in V\times W:b_{1}(x,y)=\ldots=b_{r_{3}}(x,y)=0\\},$

where $V,W\subset\mathbb{F}^{n}$ are subspaces of codimension $r_{1},r_{2}$,
respectively, and
$b_{1},\ldots,b_{r_{3}}:\mathbb{F}^{n}\times\mathbb{F}^{n}\to\mathbb{F}$ are
bilinear forms.

Gowers and Milićević [GM17a] and independently Bienvenu and Lê [BL17] proved
the following, although [BL17] obtained a weaker bound of
$r=\exp(\exp(\exp(\log^{O(1)}\alpha^{-1})))$.

######  Theorem 1.2 ([GM17a, BL17]).

Let $A\subset\mathbb{F}^{n}\times\mathbb{F}^{n}$ be of density $\alpha$ and
let $w=\textup{h}\textup{h}\textup{v}\textup{v}\textup{h}\textup{h}$. Then
there exists a bilinear variety $B\subset\phi_{w}(A)$ of codimension
$r=\exp(\exp(\log^{O(1)}\alpha^{-1}))$.

To be precise, it was not Theorem 1.2 directly but a more analytic variant of
it that was used (combined with many other ideas) to prove the $U^{4}$ inverse
theorem in [GM17b]. However, we will not discuss this analytic variant here.

The purpose of this note is to improve the bound in Theorem 1.2 to
$r=\log^{O(1)}\alpha^{-1}$, as was conjectured in [BL17]. Our proof is
arguably simpler and is obtained only by invoking Theorem 1.1 a few times,
without doing any extra Fourier analysis. The motivation behind this work —
other than obtaining a bound that matches the linear case — is to employ this
result in a more algebraic framework to obtain a modular and simpler proof of
a $U^{4}$ inverse theorem. Moreover, Theorem 1.3 was recently used by Bienvenu
and Lê [BL19] to obtain upper bounds on the correlation of the Möbius function
over functions fields with quadratic phases.

One more remark before stating the result is that Theorem 1.2 generalizes
Theorem 1.1 because given a set $A\subset\mathbb{F}^{n}$, one can apply
Theorem 1.2 to the set $A^{\prime}=\mathbb{F}^{n}\times A$ and find
$\\{x\\}\times V\subset\phi_{w}(A^{\prime})$, where $x$ is arbitrary, and $V$
a subspace of codimension $3r$. This implies $V\subset 2A-2A$.

######  Theorem 1.3 (Main theorem).

Let $A\subset\mathbb{F}^{n}\times\mathbb{F}^{n}$ be of density $\alpha$ and
let
$w=\textup{h}\textup{v}\textup{v}\textup{h}\textup{v}\textup{v}\textup{v}\textup{h}\textup{h}$.
Then there exists a bilinear variety $B\subset\phi_{w}(A)$ of codimension
$r=O(\log^{80}\alpha^{-1})$.

Note that the choice of the word $w$ in Theorem 1.3 is
$w=\textup{h}\textup{v}\textup{v}\textup{h}\textup{v}\textup{v}\textup{v}\textup{h}\textup{h}$,
which is slightly longer than the word hhvvhh in Theorem 1.2. However, for
applications this usually does not matter and any constant length $w$ would do
the job. In fact, allowing $w$ to be longer is what enables us to obtain a
result with a stronger bound.

###  1.1 A robust analog of Theorem 1.3

Returning to the theorem of Sanders, there is a more powerful variant of
Theorem 1.1 which guarantees that $V$ enjoys a stronger property than just
being a subset of $2A-2A$. The stronger property is that every element $y\in
V$ can be written in many ways as $y=a_{1}+a_{2}-a_{3}-a_{4}$, with
$a_{1},a_{2},a_{3},a_{4}\in A$. This stronger property of $V$ has a number of
applications, for example to upper bounds for Roth’s theorem in four
variables. We refer the reader to [SS16], where Theorem 3.2 is obtained from
Theorem 1.1 and the aforementioned application is given.

######  Theorem 1.4 ([San12a, SS16]).

Let $A\subset\mathbb{F}^{n}$ be a subset of density $\alpha$. Then there
exists a subspace $V\subset 2A-2A$ of codimension $O(\log^{4}\alpha^{-1})$
such that the following holds. Every $y\in V$ can be expressed as
$y=a_{1}+a_{2}-a_{3}-a_{4}$ with $a_{1},a_{2},a_{3},a_{4}\in A$ in at least
$\alpha^{O(1)}|\mathbb{F}|^{3n}$ many ways.

In Section 3 we also prove a bilinear version of Theorem 1.4 by slightly
modifying the proof of Theorem 1.3. To explain it, we need just a bit more
notation.

Fix an arbitrary $(x,y)\in\mathbb{F}^{n}\times\mathbb{F}^{n}$, and note that
$(x,y)$ can be written as $(x,y)=\phi_{\textup{h}}((x+x_{1},y),(x_{1},y))$ for
any $x_{1}\in\mathbb{F}^{n}$. Moreover, for any fixed $x_{1}$, each of the
points $(x+x_{1},y),(x_{1},y)$ can be written as
$(x+x_{1},y)=\phi_{\textup{v}}((x+x_{1},y+y_{1}),(x+x_{1},y_{1}))$ and
$(x_{1},y)=\phi_{\textup{v}}((x_{1},y+y_{2}),(x_{1},y_{2}))$ for arbitrary
$y_{1},y_{2}\in\mathbb{F}^{n}$. So overall, the point $(x,y)$ can be written
using the operation $\phi_{\textup{v}\textup{h}}$ in exactly
$|\mathbb{F}^{n}|^{3}$ many ways, namely, the total number of two-dimensional
parallelograms
$(x+x_{1},y+y_{1}),(x+x_{1},y_{1}),(x_{1},y+y_{2}),(x_{1},y_{2})$, where
$(x,y)$ is fixed. More generally, for an arbitrary word
$w\in\\{\textup{h},\textup{v}\\}^{k}$, the point $(x,y)$ can be written using
the operation $\phi_{w}$ in exactly $|\mathbb{F}^{n}|^{2^{k}-1}$ many ways.

Given a set $A\subset\mathbb{F}^{n}\times\mathbb{F}^{n}$ and a word
$w\in\\{\textup{h},\textup{v}\\}^{k}$, we define $\phi_{w}^{\varepsilon}(A)$
to be the set of all elements $(x,y)\in\mathbb{F}^{n}\times\mathbb{F}^{n}$
that can be obtained in at least $\varepsilon|\mathbb{F}^{n}|^{2^{k}-1}$ many
ways by applying the operation $\phi_{w}(A)$.

The following is an extension of Theorem 1.3 similar in spirit to Theorem 1.4.

######  Theorem 1.5.

Let $A\subset\mathbb{F}^{n}\times\mathbb{F}^{n}$ be of density $\alpha$ and
let
$w=\textup{h}\textup{v}\textup{v}\textup{h}\textup{v}\textup{v}\textup{v}\textup{h}\textup{h}$
and $\varepsilon=\exp(-O(\log^{20}\alpha^{-1}))$. Then there exists a bilinear
variety $B\subset\phi^{\varepsilon}_{w}(A)$ of codimension
$r=O(\log^{80}\alpha^{-1})$.

As a final comment, we remark that if one keeps track of the dependence on the
size of the field throughout the proofs, then the bound in Theorem 1.3 and
Theorem 1.5 is $r=O(\log^{80}\alpha^{-1}\cdot\log^{O(1)}|\mathbb{F}|)$.

#### Paper organization.

We prove Theorem 1.3 in Section 2 and Theorem 1.5 in Section 3.

##  2 Proof of Theorem 1.3

We prove Theorem 1.3 in six steps, which correspond to applying the chain of
operators
$\phi_{\textup{h}}\circ\phi_{\textup{v}\textup{v}}\circ\phi_{\textup{h}}\circ\phi_{\textup{v}}\circ\phi_{\textup{v}\textup{v}}\circ\phi_{\textup{h}\textup{h}}$
to $A$. In the proof, we invoke Theorem 1.1 (or Theorem 1.4, or the Freiman-
Ruzsa theorem, which is a corollary of Theorem 1.1), four times in total, in
Steps 1, 2, 4, and 5.

We will assume that $A\subset\mathbb{F}^{m}\times\mathbb{F}^{n}$, where
initially $m=n$ but where throughout the proof we update $m,n$ independently
when we restrict $x$ or $y$ to large subspaces. It also helps readability, as
we will always have that $x$ and related sets or subspaces are in
$\mathbb{F}^{m}$, while $y$ and related sets or subspace are in
$\mathbb{F}^{n}$.

We use three variables $r_{1},r_{2},r_{3}$ that hold the total number of
linear forms on $x$, linear forms on $y$, and bilinear forms on $(x,y)$ that
are being fixed throughout the proof, respectively. Initially,
$r_{1}=r_{2}=r_{3}=0$, but their values will be updated as we go along and at
the end $r=r_{1}+r_{2}+r_{3}$ will be the codimension of the final bilinear
variety.

#### Step 1.

Decompose $A=\bigcup_{y\in\mathbb{F}^{n}}A_{y}\times\\{y\\}$ with
$A_{y}\subset\mathbb{F}^{m}$. Define $A^{1}:=\phi_{\textup{h}\textup{h}}(A)$,
so that

$A^{1}=\bigcup_{y\in\mathbb{F}^{n}}(2A_{y}-2A_{y})\times\\{y\\}.$

Let $\alpha_{y}$ denote the density of $A_{y}$. By Theorem 1.1, there exists a
linear subspace $V^{\prime}_{y}\subset 2A_{y}-2A_{y}$ of codimension
$O(\log^{4}\alpha_{y}^{-1})$. Let $S:=\\{y:\alpha_{y}\geq\alpha/2\\}$, where
by averaging $S$ has density $\geq\alpha/2$. Note that for every $y\in S$ the
codimension of each $V^{\prime}_{y}$ is $O(\log^{4}\alpha^{-1})$. We have

$B^{1}:=\bigcup_{y\in S}V^{\prime}_{y}\times\\{y\\}\subset A^{1}.$

#### Step 2.

Consider $A^{2}:=\phi_{\textup{v}\textup{v}}(B^{1})$. It satisfies

$A^{2}=\bigcup_{y_{1},y_{2},y_{3},y_{4}\in S}\left(V^{\prime}_{y_{1}}\cap
V^{\prime}_{y_{2}}\cap V^{\prime}_{y_{3}}\cap
V^{\prime}_{y_{4}}\right)\times\\{y_{1}+y_{2}-y_{3}-y_{4}\\}.$

By Theorem 1.1, there is a subspace $W^{\prime}\subset 2S-2S$ of codimension
$O(\log^{4}\alpha^{-1})$. Note that the codimension of $W^{\prime}$, as well
as the codimension of each $V^{\prime}_{y_{1}}\cap V^{\prime}_{y_{2}}\cap
V^{\prime}_{y_{3}}\cap V^{\prime}_{y_{4}}$, is at most
$O(\log^{4}\alpha^{-1})$. We thus have

$B^{2}:=\bigcup_{y\in W^{\prime}}V_{y}\times\\{y\\}\subset A^{2},$

where $V_{y}=V^{\prime}_{y_{1}}\cap V^{\prime}_{y_{2}}\cap
V^{\prime}_{y_{3}}\cap V^{\prime}_{y_{4}}$ for some
$y_{1},y_{2},y_{3},y_{4}\in S$ which satisfy $y=y_{1}+y_{2}-y_{3}-y_{4}$.

Update $r_{2}:=\text{codim}(W^{\prime})$, where we restrict $y\in W^{\prime}$.
To simplify the notation, identify
$W^{\prime}\cong\mathbb{F}^{n-\text{codim}(W^{\prime})}$ and update
$n:=n-\text{codim}(W^{\prime})$. Thus we assume from now that

$B^{2}:=\bigcup_{y\in\mathbb{F}^{n}}V_{y}\times\\{y\\},$

where each $V_{y}$ has codimension $d=O(\log^{4}\alpha^{-1})$.

#### Step 3.

Consider $A^{3}:=\phi_{\textup{v}}(B^{2})$. It satisfies

$A^{3}=\bigcup_{y,z\in\mathbb{F}^{n}}\left(V_{z}\cap
V_{y+z}\right)\times\\{y\\}.$

#### Step 4.

Consider $A^{4}:=\phi_{\textup{h}}(A^{3})$. It satisfies

$A^{4}=\bigcup_{y,z,w\in\mathbb{F}^{n}}\left(\left(V_{z}\cap
V_{y+z}\right)+\left(V_{w}\cap V_{y+w}\right)\right)\times\\{y\\}.$

Define $U_{y}:=V_{y}^{\perp}$, so that $\dim(U_{y})=d$ and

$A^{4}=\bigcup_{y,z,w\in\mathbb{F}^{n}}\left(\left(U_{z}+U_{y+z}\right)\cap\left(U_{w}+U_{y+w}\right)\right)^{\perp}\times\\{y\\}.$

We pause for a moment to introduce one more useful piece of notation. Recall
that an affine map $L:\mathbb{F}^{n}\to\mathbb{F}^{m}$ is of the form
$L(y)=My+b$ where $M\in\mathbb{F}^{m\times n},b\in\mathbb{F}^{m}$. Given a set
of affine maps
$\mathcal{L}=\\{L_{i}:\mathbb{F}^{n}\rightarrow\mathbb{F}^{m},i\in[k]\\}$ and
$y\in\mathbb{F}^{n}$, let
$\mathcal{L}(y)=\\{L_{1}(y),\dots,L_{k}(y)\\}\subset\mathbb{F}^{m}$, and let
$\overline{\mathcal{L}}$ denote the linear span of $\mathcal{L}$. Our goal in
this step is to find a small family of affine maps $\mathcal{L}$ with
$|\mathcal{L}|=O(d)$, and a fixed choice of $z,w$, so that

$\Pr_{y\in\mathbb{F}^{n}}\bigg{[}\left(U_{z}+U_{y+z}\right)\cap\left(U_{w}+U_{y+w}\right)\subset\overline{\mathcal{L}}(y)\bigg{]}\gg
1,$ (1)

as this will give us a dense set $T\subset\mathbb{F}^{n}$ so that

$\bigcup_{y\in T}\overline{\mathcal{L}}(y)^{\perp}\times\\{y\\}\subset A^{4}.$

We now explain how to get Equation 1. For every $a\in\mathbb{F}^{n}$, let
$\mathcal{L}_{a}$ be a collection of affine maps where initially
$\mathcal{L}_{a}=\\{0\\}$ for all $a$’s. We keep adding affine maps to some of
the $\mathcal{L}_{a}$s, while always maintaining $|\mathcal{L}_{a}|\leq 2^{d}$
for all $a\in\mathbb{F}^{n}$, until we satisfy

$\Pr_{y,z,w\in\mathbb{F}^{n}}\bigg{[}\left(U_{z}+U_{y+z}\right)\cap\left(U_{w}+U_{y+w}\right)\subset\overline{\mathcal{L}}_{z}(z)+\overline{\mathcal{L}}_{y+z}(y+z)+\overline{\mathcal{L}}_{w}(w)+\overline{\mathcal{L}}_{y+w}(y+w)\bigg{]}\geq\frac{1}{2}$
(2)

and then we will pick some popular affine maps
$\mathcal{L}\subset\cup_{a\in\mathbb{F}^{n}}\mathcal{L}_{a}$ with
$|\mathcal{L}|=O(d)$ that will give us Equation 1. For now, we show how to get
Equation 2. We need the following lemma.

######  Lemma 2.1.

For each $y\in\mathbb{F}^{n}$, let $U_{y}\subset\mathbb{F}^{m}$ be a subspace
of dimension $d$. Assume that

$\Pr_{y,z,w\in\mathbb{F}^{n}}\bigg{[}\left(U_{z}+U_{y+z}\right)\cap\left(U_{w}+U_{y+w}\right)\subset\overline{\mathcal{L}}_{z}(z)+\overline{\mathcal{L}}_{y+z}(y+z)+\overline{\mathcal{L}}_{w}(w)+\overline{\mathcal{L}}_{y+w}(y+w)\bigg{]}\leq\frac{1}{2}.$

Then there exists an affine function $L:\mathbb{F}^{n}\to\mathbb{F}^{m}$ such
that

$\Pr_{y\in\mathbb{F}^{n}}\left[L(y)\in
U_{y}\setminus\overline{\mathcal{L}}_{y}(y)\right]\geq\exp(-O(d^{4})).$

In the following we prove Lemma 2.1. We will use a modified version of a
_functional version_ of the Freiman-Ruzsa theorem, with the quasi-polynomial
bounds obtained by Sanders [San12a]. We first recall the standard version. For
details of how it is derived from Theorem 1.1 we refer the reader to [Gre05].
In fact, in this case the bound can be slightly improved. The reader is
referred to [San12b].

######  Theorem 2.2.

(Freiman-Ruzsa theorem; functional version). Let
$f:\mathbb{F}^{n}\rightarrow\mathbb{F}^{m}$ be a function. Suppose that

$\Pr_{y,z,z^{\prime}\in\mathbb{F}^{n}}\left[f(y+z)-f(z)=f(y+z^{\prime})-f(z^{\prime})\right]\geq\alpha.$

Then there exists an affine map $L:\mathbb{F}^{n}\rightarrow\mathbb{F}^{m}$
such that

$|\\{z\in\mathbb{F}^{n}:L(z)=f(z)\\}|\geq\exp(-O(\log^{4}(\alpha^{-1})))|\mathbb{F}^{n}|.$

Now, this result may be strengthened as follows.

######  Lemma 2.3.

Let $f:\mathbb{F}^{n}\rightarrow\mathbb{F}^{m}$ be a function and
$Z\subset\mathbb{F}^{n}$ with $|Z|\geq\alpha|\mathbb{F}^{n}|$. Suppose that

$\Pr_{y\in\mathbb{F}^{n},z,z^{\prime}\in
Z}\left[f(y+z)-f(z)=f(y+z^{\prime})-f(z^{\prime})\right]\geq\alpha.$

Then there exists an affine map $L:\mathbb{F}^{n}\rightarrow\mathbb{F}^{m}$
such that

$|\\{z\in Z:L(z)=f(z)\\}|\geq\exp(-O(\log^{4}(\alpha^{-1})))|\mathbb{F}^{n}|.$

###### Proof.

Let $\Gamma=\\{(x,f(x)):x\in\mathbb{F}^{n}\\}$ and
$\Gamma^{\prime}=\\{(x,f(x)):x\in Z\\}$. The additive energy
$E(\Gamma,\Gamma^{\prime})$ is defined as

$E(\Gamma,\Gamma^{\prime})=|\\{(a,b,c,d):a-b=c-d,a,c\in\Gamma,b,d\in\Gamma^{\prime}\\}|$

and satisfies

$E(\Gamma,\Gamma^{\prime})\geq\alpha^{O(1)}|\Gamma|^{3}.$

Using the Cauchy-Schwarz inequality for additive energy (see Corollary 2.10 in
[TV06]), we have

$E(\Gamma,\Gamma^{\prime})\leq\sqrt{E(\Gamma,\Gamma)\cdot
E(\Gamma^{\prime},\Gamma^{\prime})}.$

Using the fact that $|\Gamma^{\prime}|\geq\alpha|\Gamma|$, we get that
$E(\Gamma^{\prime},\Gamma^{\prime})\geq\alpha^{O(1)}|\Gamma|^{3}$. Let $M\geq
m$ be large enough, and define a function
$f^{\prime}:\mathbb{F}^{n}\to\mathbb{F}^{M}$ by setting $f^{\prime}(z)=f(z)$
if $z\in Z$, and otherwise $f$ takes random values in $\mathbb{F}^{M}$. Apply
Theorem 2.2 to $f^{\prime}$. The linear function $L$ thus obtained has to
necessarily agree with $f^{\prime}$ (and hence with $f$) on a subset
$Z^{\prime}\subset Z$ of the claimed density. ∎

######  Remark 2.4.

Note that using a bootstrapping argument due to Konyagin, the bound
$\exp(-O(\log^{4}(\alpha^{-1})))|\mathbb{F}^{n}|$ in Theorem 2.2 can be
improved to $\exp(-O(\log^{3+o(1)}(\alpha^{-1})))|\mathbb{F}^{n}|$ (see
Theorem 12.5 in [San12b]). Here, we have used the exponent $4$ instead of
$3+o(1)$ for aesthetic reasons. Using Lemma 2.3 with exponent $3+o(1)$ in what
follows would result in a final bound of $\log^{64+o(1)}\alpha^{-1}$ instead
of $\log^{80}\alpha^{-1}$ in Theorem 1.3 and Theorem 1.5.

Now we may return to the proof of Lemma 2.1.

###### Proof of Lemma 2.1.

Consider a choice of $y,w,z$ for which

$\left(U_{y+z}+U_{z}\right)\cap\left(U_{y+w}+U_{w}\right)\not\subset\overline{\mathcal{L}}_{y+z}(y+z)+\overline{\mathcal{L}}_{z}(z)+\overline{\mathcal{L}}_{y+w}(y+w)+\overline{\mathcal{L}}_{w}(w).$

This directly implies that there is an ordered quadruple $(a,b,c,d)$ so that
$a\in U_{y+z},b\in U_{z},c\in U_{y+w},d\in U_{w}$ with $a-b=c-d\neq 0$ and

$\left(\left[a\notin\overline{\mathcal{L}}_{y+z}(y+z)\right]\textrm{OR}\left[b\notin\overline{\mathcal{L}}_{z}(z)\right]\right)\and\left(\left[c\notin\overline{\mathcal{L}}_{y+w}(y+w)\right]\textrm{OR}\left[d\notin\overline{\mathcal{L}}_{w}(w)\right]\right).$

Consider all the possible solutions of the above formula, namely:

  * •

$\left[a\notin\overline{\mathcal{L}}_{y+z}(y+z)\right]\and\left[c\notin\overline{\mathcal{L}}_{y+w}(y+w)\right]$

  * •

$\left[b\notin\overline{\mathcal{L}}_{z}(z)\right]\and\left[c\notin\overline{\mathcal{L}}_{y+w}(y+w)\right]$

  * •

$\left[a\notin\overline{\mathcal{L}}_{y+z}(y+z)\right]\and\left[d\notin\overline{\mathcal{L}}_{w}(w)\right]$

  * •

$\left[b\notin\overline{\mathcal{L}}_{z}(z)\right]\and\left[d\notin\overline{\mathcal{L}}_{w}(w)\right]$

One of these cases occur for at least $1/4$ of the choices of $y,w,z$; assume
without loss of generality that it is the last one. The other cases are
analogous.

Next, sample a random function $f:\mathbb{F}^{n}\to\mathbb{F}^{m}$ by picking
$f(x)\in U_{x}$ uniformly and independently for each $x\in\mathbb{F}^{n}$.
Note that the quadruple $a,b,c,d$ depends on $y,w,z$, and that for each such
choice

$\Pr_{f}[f(y+z)=a,f(z)=b,f(y+w)=c,f(w)=d]\geq|\mathbb{F}|^{-4d}.$

Note that when this event happens, by construction we have
$f(y+z)-f(z)=f(y+w)-f(w)$. Combining this with the assumption of the lemma, we
get

$\Pr_{y,z,w\in\mathbb{F}^{n},f}\left[f(y+z)-f(z)=f(y+w)-f(w),f(z)\in
U_{z}\setminus\overline{\mathcal{L}_{z}}(z),f(w)\in
U_{w}\setminus\overline{\mathcal{L}_{w}}(w)\right]\geq\frac{1}{2}\cdot\frac{1}{4}\cdot|\mathbb{F}|^{-4d}.$

Fix $f$ where the above bound holds. Let $Z=\\{z:f(z)\in
U_{z}\setminus\overline{\mathcal{L}_{z}}(z)\\}$. Then, supressing the
dependence on the size of the field, we have
$|Z|\geq\exp(-O(d))|\mathbb{F}|^{n}$ and

$\Pr_{y\in\mathbb{F}^{n},z,w\in
Z}\left[f(y+z)-f(z)=f(y+w)-f(w)\right]\geq\exp(-O(d)).$

By Lemma 2.3, there exists an affine map $L:\mathbb{F}^{n}\to\mathbb{F}^{m}$
and a set $Z^{\prime}\subset Z$ with
$|Z^{\prime}|\geq\exp(-O(d^{4}))|\mathbb{F}^{n}|$ such that for all
$z^{\prime}\in Z^{\prime}$, $f(z^{\prime})=L(z^{\prime})$ and hence
$L(z^{\prime})\in
U_{z^{\prime}}\setminus\overline{\mathcal{L}_{z^{\prime}}}(z^{\prime})$. ∎

Next, we proceed as follows. As long as Equation 2 is satisfied, apply Lemma
2.1 to find an affine map $L:\mathbb{F}^{n}\to\mathbb{F}^{m}$. For every $x$
that satisfies $L(x)\in U_{x}\setminus\overline{\mathcal{L}_{x}}(x)$, add the
map $L$ to $\mathcal{L}_{x}$. This process needs to stop after
$t=\exp(O(d^{4}))$ many steps. Let
$L_{1},\ldots,L_{t}:\mathbb{F}^{n}\to\mathbb{F}^{m}$ be the affine maps
obtained in this process. Using this notation, set
$\mathcal{L}^{\prime}=\cup_{x\in\mathbb{F}^{n}}\mathcal{L}_{x}$. For every
subspace $U_{x}$, there is a set
$\mathcal{L}^{\prime}_{x}\subset\mathcal{L}^{\prime}$ of size
$|\mathcal{L}^{\prime}_{x}|\leq d$ such that

$\overline{\mathcal{L}_{x}}(x)\subset\overline{\mathcal{L}^{\prime}_{x}}(x).$

This implies that

$\Pr_{y,z,w\in\mathbb{F}^{n}}\left[\left(\left(U_{z}+U_{y+z}\right)\cap\left(U_{w}+U_{y+w}\right)\subset\overline{\mathcal{L}^{\prime}_{z}}(z)+\overline{\mathcal{L}^{\prime}_{y+z}}(y+z)+\overline{\mathcal{L}^{\prime}_{w}}(w)+\overline{\mathcal{L}^{\prime}_{y+w}}(y+w)\right)\right]\geq\frac{1}{2}.$

Consider the most popular quadruple
$\mathcal{L}^{\prime}_{1},\mathcal{L}^{\prime}_{2},\mathcal{L}^{\prime}_{3},\mathcal{L}^{\prime}_{4}\subset\mathcal{L}^{\prime}$
so that

$\Pr_{y,z,w\in\mathbb{F}^{n}}\left[\left(\left(U_{z}+U_{y+z}\right)\cap\left(U_{w}+U_{y+w}\right)\subset\overline{\mathcal{L}^{\prime}_{1}}(z)+\overline{\mathcal{L}^{\prime}_{2}}(y+z)+\overline{\mathcal{L}^{\prime}_{3}}(w)+\overline{\mathcal{L}^{\prime}_{4}}(y+w)\right)\right]\geq\frac{1}{2}\times{t\choose
d}^{-4}.$

Let
$\mathcal{L}:=\mathcal{L}^{\prime}_{1}\cup\mathcal{L}^{\prime}_{2}\cup\mathcal{L}^{\prime}_{3}\cup\mathcal{L}^{\prime}_{4}$.
Recall that $t=\exp(O(d^{4}))$ and hence ${t\choose d}=\exp(O(d^{5}))$. We
have

$\Pr_{y,z,w\in\mathbb{F}^{n}}\bigg{[}\left(U_{z}+U_{y+z}\right)\cap\left(U_{w}+U_{y+w}\right)\subset\overline{\mathcal{L}}(z)+\overline{\mathcal{L}}(y+z)+\overline{\mathcal{L}}(w)+\overline{\mathcal{L}}(y+w)\bigg{]}\geq\exp(-O(d^{5})).$

By averaging, there is some choice of $z,w$ such that,

$\Pr_{y\in\mathbb{F}^{n}}\bigg{[}\left(U_{z}+U_{y+z}\right)\cap\left(U_{w}+U_{y+w}\right)\subset\overline{\mathcal{L}}(z)+\overline{\mathcal{L}}(y+z)+\overline{\mathcal{L}}(w)+\overline{\mathcal{L}}(y+w)\bigg{]}\geq\exp(-O(d^{5})).$

Recall that each $L\in\mathcal{L}$ is an affine map and that
$|\mathcal{L}|\leq 4d$. Thus,
$\overline{\mathcal{L}}(z),\overline{\mathcal{L}}(y+z),\overline{\mathcal{L}}(w),\overline{\mathcal{L}}(y+w)\subset\overline{\mathcal{L}}(y)+Q$
where $Q\subset\mathbb{F}^{m}$ is a linear subspace of dimension $O(d)$. We
thus have

$B^{4}:=\bigcup_{y\in
T}(\overline{\mathcal{L}}(y)+Q)^{\perp}\times\\{y\\}\subset A^{4},$

where $T\subset\mathbb{F}^{n}$ has density $\exp(-O(d^{5}))$.

To simplify the presentation, we would like to assume that the maps in
$\mathcal{L}$ are linear maps instead of affine maps, that is, that they do
not have a constant term. This can be obtained by restricting $x$ to the
subspace orthogonal to $Q$ and to the constant term in the affine maps in
$\mathcal{L}$. Correspondingly, we update
$r_{1}:=r_{1}+\dim(Q)+|\mathcal{L}|=O(d)$. So from now on we may assume that
$\mathcal{L}$ is defined by $4d$ linear maps, and that

$B^{4}:=\bigcup_{y\in
T}{\overline{\mathcal{L}}(y)}^{\perp}\times\\{y\\}\subset A^{4},$

where $T\subset\mathbb{F}^{n}$ has density $\exp(-O(d^{5}))$.

#### Step 5.

Consider $A^{5}:=\phi_{\textup{v}\textup{v}}(B^{4})$ so that

$\displaystyle A^{5}$ $\displaystyle=\bigcup_{y_{1},y_{2},y_{3},y_{4}\in
T}\left({\overline{\mathcal{L}}(y_{1})}^{\perp}\cap{\overline{\mathcal{L}}(y_{2})}^{\perp}\cap{\overline{\mathcal{L}}(y_{3})}^{\perp}\cap{\overline{\mathcal{L}}(y_{4})}^{\perp}\right)\times\\{y_{1}+y_{2}-y_{3}-y_{4}\\}.$

By Theorem 1.1 there exists a subspace $W\subset 2T-2T$ of codimension
$O(d^{20})$. However, this time, the conclusion is not strong enough for us,
and we need to use Theorem 1.4 instead. The following equivalent formulation
of Theorem 1.4 will be more convenient for us: there is a subspace
$W\subset\mathbb{F}^{n}$ of codimension $O(\log^{4}{\alpha^{-1}})$ such that,
for each $y\in W$ there is a set $S_{y}\subset(\mathbb{F}^{n})^{3}$ of density
$\alpha^{O(1)}$, such that for all $(a_{1},a_{2},a_{3})\in S_{y}$,

$\quad a_{1},a_{2},a_{3},a_{1}+a_{2}-a_{3}-y\in A.$

Apply Theorem 1.4 to the set $T$ to obtain the subspace $W$ and the sets
$S_{y}$. We have

$\displaystyle B^{5}:=$ $\displaystyle\bigcup_{y\in
W}\left(\bigcup_{(y_{1},y_{2},y_{3})\in
S_{y}}\left(\overline{\mathcal{L}}(y_{1})+\overline{\mathcal{L}}(y_{2})+\overline{\mathcal{L}}(y_{3})+\overline{\mathcal{L}}(y_{1}+y_{2}-y_{3}-y)\right)^{\perp}\right)\times\\{y\\}\subset
A^{5}.$

To simplify the presentation we introduce the notation
$\overline{\mathcal{L}}(y_{1},y_{2},y_{3}):=\overline{\mathcal{L}}(y_{1})+\overline{\mathcal{L}}(y_{2})+\overline{\mathcal{L}}(y_{3})$.
Next, observe that for any $y,y^{\prime}\in\mathbb{F}^{n}$,
$\overline{\mathcal{L}}(y^{\prime})+\overline{\mathcal{L}}(y+y^{\prime})=\overline{\mathcal{L}}(y^{\prime})+\overline{\mathcal{L}}(y)$.
Thus we can simplify the expression of $B^{5}$ to

$\displaystyle B^{5}=$ $\displaystyle\bigcup_{y\in
W}\left(\bigcup_{(y_{1},y_{2},y_{3})\in
S_{y}}\left(\overline{\mathcal{L}}(y_{1},y_{2},y_{3})+\overline{\mathcal{L}}(y)\right)^{\perp}\right)\times\\{y\\},$

which can be re-written as

$\displaystyle B^{5}=$ $\displaystyle\bigcup_{y\in
W}\left(\bigcup_{(y_{1},y_{2},y_{3})\in
S_{y}}\overline{\mathcal{L}}(y_{1},y_{2},y_{3})^{\perp}\cap{\overline{\mathcal{L}}(y)}^{\perp}\right)\times\\{y\\}.$

#### Step 6.

Consider $A^{6}:=\phi_{\textup{h}}(B^{5})$. It satisfies

$\displaystyle A^{6}=\bigcup_{y\in
W}\left(\bigcup_{\begin{subarray}{c}(y_{1},y_{2},y_{3})\in S_{y}\\\
(y^{\prime}_{1},y^{\prime}_{2},y^{\prime}_{3})\in
S_{y}\end{subarray}}\overline{\mathcal{L}}(y_{1},y_{2},y_{3})^{\perp}\cap{\overline{\mathcal{L}}(y)}^{\perp}+\overline{\mathcal{L}}(y^{\prime}_{1},y^{\prime}_{2},y^{\prime}_{3})^{\perp}\cap{\overline{\mathcal{L}}(y)}^{\perp}\right)\times\\{y\\}.$

In order to complete the proof, we will find a large subspace $V$ such that
for every $y\in W$,

$V\cap{\overline{\mathcal{L}}(y)}^{\perp}\subset\bigcup_{\begin{subarray}{c}(y_{1},y_{2},y_{3})\in
S_{y}\\\ (y^{\prime}_{1},y^{\prime}_{2},y^{\prime}_{3})\in
S_{y}\end{subarray}}\overline{\mathcal{L}}(y_{1},y_{2},y_{3})^{\perp}\cap{\overline{\mathcal{L}}(y)}^{\perp}+\overline{\mathcal{L}}(y^{\prime}_{1},y^{\prime}_{2},y^{\prime}_{3})^{\perp}\cap{\overline{\mathcal{L}}(y)}^{\perp}.$

In fact, we will prove something stronger: there is a large subspace $V$ such
that for each $y\in W$, there is a choice of
$(y_{1},y_{2},y_{3}),(y^{\prime}_{1},y^{\prime}_{2},y^{\prime}_{3})\in S_{y}$
for which

$V\cap{\overline{\mathcal{L}}(y)}^{\perp}\subset\overline{\mathcal{L}}(y_{1},y_{2},y_{3})^{\perp}\cap{\overline{\mathcal{L}}(y)}^{\perp}+\overline{\mathcal{L}}(y^{\prime}_{1},y^{\prime}_{2},y^{\prime}_{3})^{\perp}\cap{\overline{\mathcal{L}}(y)}^{\perp}.$

The following lemma is key. Given a set $\mathcal{L}$ of linear maps from
$\mathbb{F}^{n}$ to $\mathbb{F}^{m}$, let $\dim(\overline{\mathcal{L}})$
denote the dimension of linear span of $\mathcal{L}$ as a vector space over
$\mathbb{F}$.

######  Lemma 2.5.

Fix $\delta>0$. Let $\mathcal{L}$ be a set of linear maps from
$\mathbb{F}^{n}$ to $\mathbb{F}^{m}$ with $\dim(\overline{\mathcal{L}})=k$.
Then there is a subspace $Z\subset\mathbb{F}^{m}$ of dimension at most
$k(2k+\log\delta^{-1}+3)$ such that the following holds. For every subset
$S\subset\mathbb{F}^{n}$ of density at least $\delta$, and arbitrary
$y\in\mathbb{F}^{n}$, at least half the pairs $s,s^{\prime}\in S$ satisfy

$(\overline{\mathcal{L}}(s)+\overline{\mathcal{L}}(y))\cap(\overline{\mathcal{L}}(s^{\prime})+\overline{\mathcal{L}}(y))\subset
Z+\overline{\mathcal{L}}(y).$

###### Proof.

The proof is by induction on $\dim(\overline{\mathcal{L}})$. Consider first
the base case of $\dim(\overline{\mathcal{L}})=1$ and suppose that
$\overline{\mathcal{L}}=\langle L\rangle$ for some map $L$. We consider two
cases based on the minimum rank of the maps in $\overline{\mathcal{L}}$. First
suppose that rank of every non-zero map in $\overline{\mathcal{L}}$ (which is
the same as rank of $L$) is bigger than $\log\delta^{-1}+5$. Fix arbitrary
$L_{1},L_{3}\in\overline{\mathcal{L}}\setminus\\{0\\}$ and
$L_{2},L_{4}\in\overline{\mathcal{L}}$ and $s,y\in\mathbb{F}^{n}$ and observe
that

$\Pr_{s^{\prime}\in
S}\left[L_{1}(s)+L_{2}(y)=L_{3}(s^{\prime})+L_{4}(y)\right]<\frac{|\mathbb{F}|^{-(\log\delta^{-1}+5)}}{\Pr_{s^{\prime}\in\mathbb{F}^{n}}\left[s^{\prime}\in
S\right]}\leq|\mathbb{F}|^{-(\log\delta^{-1}+5)}\delta^{-1}.$

By applying the union bound over all quadruples
$L_{1},\cdots,L_{4}\in\overline{\mathcal{L}}$, we obtain that

$\Pr_{s,s^{\prime}\in
S}\left[\left(\overline{\mathcal{L}}(s)+\overline{\mathcal{L}}(y)\right)\cap\left(\overline{\mathcal{L}}(s^{\prime})+\overline{\mathcal{L}}(y)\right)\neq\overline{\mathcal{L}}(y)\right]\leq|\mathbb{F}|^{4}|\mathbb{F}|^{-(\log\delta^{-1}+5)}\delta^{-1}\leq\frac{1}{2}.$

Therefore, we can safely choose $Z=\\{0\\}$ in the lemma. Now, for the second
case, suppose that $\textrm{rank}(L)\leq\log\delta^{-1}+5$. Let
$Z=\text{Im}(L)$. Then for all $s\in\mathbb{F}^{n}$,
$\overline{\mathcal{L}}(s)\subset\text{Im}(L)=Z$, and so
$(\overline{\mathcal{L}}(s)+\overline{\mathcal{L}}(y))\cap(\overline{\mathcal{L}}(s^{\prime})+\overline{\mathcal{L}}(y))\subset
Z\subset Z+\overline{\mathcal{L}}(y)$.

Now let $\dim(\overline{\mathcal{L}})=k$. First, suppose that $\forall
L\in\overline{\mathcal{L}}$, $\textrm{rank}(L)>4k+\log\delta^{-1}+1$. Then
similar to the base case, for all $y\in\mathbb{F}^{n}$,

$\Pr_{s,s^{\prime}\in
S}\left[\left(\overline{\mathcal{L}}(s)+\overline{\mathcal{L}}(y)\right)\cap\left(\overline{\mathcal{L}}(s^{\prime})+\overline{\mathcal{L}}(y)\right)\neq\overline{\mathcal{L}}(y)\right]\leq|\mathbb{F}|^{4k}|\mathbb{F}|^{-(4k+\log\delta^{-1}+1)}\delta^{-1}\leq\frac{1}{2}.$

Otherwise, suppose there is some $L\in\overline{\mathcal{L}}\setminus\\{0\\}$
with rank at most $4k+\log\delta^{-1}+1$. Let $Y$ be a subspace so that
$Y\oplus\text{Im}(L)=\mathbb{F}^{m}$. Let $\textrm{Proj}_{Y}:\mathbb{F}^{n}\to
Y$ be the projection map along $\text{Im}(L)$ with
$\textrm{Proj}_{Y}(\text{Im}(L))=0$. Consider the new family of maps

$\mathcal{L}^{\prime}=\\{\textrm{Proj}_{Y}\circ M:M\in\mathcal{L}\\}.$

Note that $\overline{\mathcal{L}^{\prime}}$ has dimension $\leq k-1$ because
$\textrm{Proj}_{Y}\circ L\equiv 0$ and so by the induction hypothesis, there
exists a subspace $Z^{\prime}$ of dimension at most
$(k-1)(2(k-1)+\log\delta^{-1}+3)$ such that, for all $y\in\mathbb{F}^{n}$, for
least half the pairs $s,s^{\prime}\in S$ it holds that

$(\overline{\mathcal{L}^{\prime}}(s)+\overline{\mathcal{L}^{\prime}}(y))\cap(\overline{\mathcal{L}^{\prime}}(s^{\prime})+\overline{\mathcal{L}^{\prime}}(y))\subset
Z^{\prime}+\overline{\mathcal{L}^{\prime}}(y).$

The above implies that

$\textrm{Proj}_{Y}((\overline{\mathcal{L}}(s)+\overline{\mathcal{L}}(y))\cap(\overline{\mathcal{L}}(s^{\prime})+\overline{\mathcal{L}}(y)))\subset
Z^{\prime}+\textrm{Proj}_{Y}(\overline{\mathcal{L}}(y))\subset
Z^{\prime}+\overline{\mathcal{L}}(y)+\text{Im}(L),$

so we can take $Z=Z^{\prime}+\text{Im}(L)$. ∎

We note that for Theorem 1.3 we only need a weaker form of Lemma 2.5, which
states that at least one pair $s,s^{\prime}\in S$ exists; however, we will
need the stronger version for Theorem 1.5.

We apply Lemma 2.5 as follows. Define a new family of linear maps
$\mathcal{L}^{*}$ from $\mathbb{F}^{3n}$ to $\mathbb{F}^{m}$ as follows. For
each $L\in\mathcal{L}$ define three linear maps $L_{i}$, $i\in\\{1,2,3\\}$ by:

$L_{i}:(\mathbb{F}^{n})^{3}\rightarrow\mathbb{F}^{m},L_{i}(y_{1},y_{2},y_{3})=L(y_{i})$

and let

$\mathcal{L}^{*}:=\\{L_{i}:L\in\mathcal{L},i\in[3]\\}.$

Apply Lemma 2.5 to the family $\mathcal{L}^{*}$ with $\delta=\exp(-O(d^{5}))$
and obtain a subspace $V\subset\mathbb{F}^{m}$ of codimension
$O(d^{2}\log(\exp(-O(d^{5})))=O(d^{7})$ so that, for every
$S_{y}\subset(\mathbb{F}^{n})^{3}$ with $y\in W$, there exist
$(y_{1},y_{2},y_{3}),(y^{\prime}_{1},y^{\prime}_{2},y^{\prime}_{3})\in S_{y}$
for which

$V\cap\overline{\mathcal{L}^{*}}((y,y,y))^{\perp}\subset(\overline{\mathcal{L}^{*}}((y_{1},y_{2},y_{3}))^{\perp}\cap\overline{\mathcal{L}^{*}}((y,y,y))^{\perp})+(\overline{\mathcal{L}^{*}}((y^{\prime}_{1},y^{\prime}_{2},y^{\prime}_{3}))^{\perp}\cap\overline{\mathcal{L}^{*}}((y,y,y))^{\perp}).$

This directly implies that

$V\cap\overline{\mathcal{L}}(y)^{\perp}\subset(\overline{\mathcal{L}}(y_{1},y_{2},y_{3})^{\perp}\cap\overline{\mathcal{L}}(y)^{\perp})+(\overline{\mathcal{L}}(y^{\prime}_{1},y^{\prime}_{2},y^{\prime}_{3})^{\perp}\cap\overline{\mathcal{L}}(y)^{\perp}).$

Define

$B^{6}:=\bigcup_{y\in
W}\left(V\cap{\overline{\mathcal{L}}(y)}^{\perp}\right)\times\\{y\\}\subset
A^{6}.$

Observe that $B^{6}$ is a bilinear variety defined by $\text{codim}(V)$ many
linear equations on $x$, $\text{codim}(W)$ linear equations on $y$ and
$|\mathcal{L}|$ bilinear equations on $(x,y)$.

To complete the proof we calculate the quantitative bounds obtained. We have
$d=O(\log^{4}\alpha^{-1})$, where $\alpha$ was the density of the original set
$A$, and

$\displaystyle r_{1}=O(d)+\text{codim}(V)=O(d^{7}),$ $\displaystyle
r_{2}=O(d)+\text{codim}(W)=O(d^{20}),$ $\displaystyle
r_{3}=|\mathcal{L}|=O(d).$

Together these give the final bound of
$r=r_{1}+r_{2}+r_{3}=O(\log^{80}\alpha^{-1})$.

##  3 Proof of Theorem 1.5

In this section we prove Theorem 1.5 by slightly modifying the proof of
Theorem 1.3. We point out the necessary modifications to the proof of Theorem
1.3.

#### Step 1.

In this step, we use Theorem 1.4 instead of Theorem 1.1 and directly obtain

$B^{1}\subset\phi^{\varepsilon_{1}}_{\textup{h}\textup{h}}(A)$ (3)

for $\varepsilon_{1}=\alpha^{O(1)}$.

#### Step 2.

Similarly in this step as well, using Theorem 1.4 instead of Theorem 1.1 gives

$B^{2}\subset\phi^{\varepsilon_{2}}_{\textup{v}\textup{v}}(B^{1})$ (4)

with $\varepsilon_{2}=\alpha^{O(1)}$. Recall that from now on we assume for
simplicity of exposition that
$B^{2}=\bigcup_{y\in\mathbb{F}^{n}}V_{y}\times\\{y\\}$.

#### Steps 3 and 4.

This step is slightly different from Steps 1 and 2. Here, we are not able to
directly produce some set $B^{4}$ that would satisfy
$B^{4}\subset\phi_{\textup{h}\textup{v}}^{\varepsilon_{4}}(B^{2})$. But what
we can do is to apply the remaining operation
$\phi_{\textup{h}\textup{v}\textup{v}\textup{h}\textup{v}}$ to $B^{2}$ and
obtain the final bilinear structure $B^{6}$ that satisfies what we want, which
is

$B^{6}\subset\phi_{\textup{h}\textup{v}\textup{v}\textup{h}\textup{v}}^{\varepsilon_{6}}(B^{2})$
(5)

for $\varepsilon_{6}=\exp(-\textrm{poly}\log\alpha^{-1})$. Combining Equations
3, 4 and 5 gives

$B^{6}\subset\phi_{\textup{h}\textup{v}\textup{v}\textup{h}\textup{v}\textup{v}\textup{v}\textup{h}\textup{h}}^{\varepsilon}(A)$

for $\varepsilon=\exp(-\textrm{poly}\log\alpha^{-1})$.

We establish Equation 5 in the rest of the proof. Recall that previously we
showed that the following holds: there is a set of affine maps $\mathcal{L}$,
with $|\mathcal{L}|=O(d)$, such that

$\Pr_{y,w,z\in\mathbb{F}^{n}}\bigg{[}\left(\overline{\mathcal{L}}(z)+\overline{\mathcal{L}}(y+z)+\overline{\mathcal{L}}(w)+\overline{\mathcal{L}}(y+w)\right)^{\perp}\subset\left(V^{\perp}_{z}\cap
V^{\perp}_{y+z}\right)+\left(V^{\perp}_{w}\cap
V^{\perp}_{y+w}\right)\bigg{]}\geq\exp(-O(d^{5}))$

and consequently

$\Pr_{y,w,z\in\mathbb{F}^{n}}\bigg{[}\left(\overline{\mathcal{L}}(y)+\overline{\mathcal{L}}(z)+\overline{\mathcal{L}}(w)\right)^{\perp}\subset\left(V^{\perp}_{z}\cap
V^{\perp}_{y+z}\right)+\left(V^{\perp}_{w}\cap
V^{\perp}_{y+w}\right)\bigg{]}\geq\exp(-O(d^{5})).$

Recall that $d=O(\log^{4}\alpha^{-1})$. Furthermore, we may assume the maps in
$\mathcal{L}$ are linear (instead of affine) after we update
$r_{1}:=r_{1}+|\mathcal{L}|=O(d)$.

In the proof of Theorem 1.3 we then fixed one popular choice of $w,z$.
However, here we cannot do this, as we need many pairs $w,z$. Let $T$ be the
set of $y$s that satisfy

$\Pr_{w,z\in\mathbb{F}^{n}}\bigg{[}\left(\overline{\mathcal{L}}(y)+\overline{\mathcal{L}}(z)+\overline{\mathcal{L}}(w)\right)^{\perp}\subset\left(V^{\perp}_{z}\cap
V^{\perp}_{y+z}\right)+\left(V^{\perp}_{w}\cap
V^{\perp}_{y+w}\right)\bigg{]}\geq\exp(-O(d^{5})),$ (6)

so $T$ has density $\exp(-O(d^{5}))$. We deduce something stronger from
Equation 6 but we need to introduce some notation first.

For $A,B\subset\mathbb{F}^{n}$ let $A-_{\eta}B$ denote the set of all elements
$c\in A-B$ that can be written in at least $\eta|\mathbb{F}^{n}|$ many ways as
$c=a-b$ for $a\in A,b\in B$. To use this notation, note that if $A,B$ are two
subspaces of codimension $k$, then $A-B=A-_{\eta}B$ for $\eta=\exp(-O(k))$.
This is because every element $c\in A-B$ can be written as $c=(a+v)-(b+v)$
where $v$ is an arbitrary element in the subspace $A\cap B$ of codimension at
most $2k$. So we can improve Equation 6 to

$\Pr_{w,z\in\mathbb{F}^{n}}\bigg{[}\left(\overline{\mathcal{L}}(y)+\overline{\mathcal{L}}(z)+\overline{\mathcal{L}}(w)\right)^{\perp}\subset\left(V^{\perp}_{z}\cap
V^{\perp}_{y+z}\right)-_{\eta}\left(V^{\perp}_{w}\cap
V^{\perp}_{y+w}\right)\bigg{]}\geq\exp(-O(d^{5})),$ (7)

for $\eta=\exp{(-O(d))}.$

#### Step 5.

Similar to before, consider the subspace $W\subset 2T-2T$ of codimension
$O(d^{20})$ that is given by Theorem 1.4. This subspace $W$ has the following
property: if we fix an arbitrary $y\in W$, sample
$y_{1},y_{2},y_{3}\in\mathbb{F}^{n}$ uniformly and independently, and set
$y_{4}=-y+y_{1}+y_{2}-y_{3}$, then with probability at least $\exp(-O(d^{5}))$
we have $y_{1},y_{2},y_{3},y_{4}\in T$. This means that if we furthermore
sample $w_{1},w_{2},w_{3},w_{4},z_{1},z_{2},z_{3},z_{4}\in\mathbb{F}^{n}$
uniformly and independently, then, with probability at least
$\exp(-O(d^{5}))$, the following four equations simultaneously hold:

$\left(\overline{\mathcal{L}}(y_{i})+\overline{\mathcal{L}}(z_{i})+\overline{\mathcal{L}}(w_{i})\right)^{\perp}\subset\left(V^{\perp}_{z_{i}}\cap
V^{\perp}_{y_{i}+z_{i}}\right)-_{\eta}\left(V^{\perp}_{w_{i}}\cap
V^{\perp}_{y_{i}+w_{i}}\right)\qquad i=1,\ldots,4.$

By computing the intersection of the left-hand side and the right-hand side
for each $i=1,\ldots,4$, we obtain that with probability at least
$\exp(-O(d^{5}))$,

$\left(\overline{\mathcal{L}}(y)+\sum_{i=1}^{3}\overline{\mathcal{L}}(y_{i})+\sum_{i=1}^{4}\overline{\mathcal{L}}(z_{i})+\sum_{i=1}^{4}\overline{\mathcal{L}}(w_{i})\right)^{\perp}\subset\bigcap_{i=1}^{4}\left(\left(V^{\perp}_{z_{i}}\cap
V^{\perp}_{y_{i}+z_{i}}\right)-_{\eta}\left(V^{\perp}_{w_{i}}\cap
V^{\perp}_{y_{i}+w_{i}}\right)\right).$ (8)

For a given
$y\in\mathbb{F}^{n},\mathbf{s}=(y_{1},y_{2},y_{3},w_{1},w_{2},w_{3},w_{4},z_{1},z_{2},z_{3},z_{4})\in(\mathbb{F}^{n})^{11}$,
let

$\mathcal{V}_{y,\mathbf{s}}=\bigcap_{i=1}^{4}\left(\left(V^{\perp}_{z_{i}}\cap
V^{\perp}_{y_{i}+z_{i}}\right)-_{\eta}\left(V^{\perp}_{w_{i}}\cap
V^{\perp}_{y_{i}+w_{i}}\right)\right),$

where we recall that $y_{4}=-y+y_{1}+y_{2}-y_{3}$. Observe that for any
$\mathbf{s}$,

$\bigcup_{y\in
W}\mathcal{V}_{y,\mathbf{s}}\times\\{y\\}\subset\phi_{\textup{v}\textup{v}\textup{h}\textup{v}}(B^{2}).$

We rewrite Equation 8 more compactly as

$\Pr_{\mathbf{s}}\left[\left(\overline{\mathcal{L}}(y)+\overline{\mathcal{L}}(\mathbf{s})\right)^{\perp}\subset\mathcal{V}_{y,\mathbf{s}}\right]\geq\exp(-O(d^{5})),$
(9)

where we use the notation
$\overline{\mathcal{L}}(\mathbf{s})=\sum_{i=1}^{3}\overline{\mathcal{L}}(y_{i})+\sum_{i=1}^{4}\overline{\mathcal{L}}(z_{i})+\sum_{i=1}^{4}\overline{\mathcal{L}}(w_{i})$.

#### Step 6.

Now we consider the ultimate result of applying the operation hvvhv to
$B^{2}$. Only the final operation h remains to be applied. After doing so, we
find a subspace $V\subset\mathbb{F}^{m}$ of codimension $O(d^{7})$ that
satisfies the following: for any $y\in W$, choose
$\mathbf{s_{1}},\mathbf{s_{2}}\in(\mathbb{F}^{n})^{11}$ uniformly and
independently at random. Then with probability $\exp(-O(d^{5}))$,

$V\cap\overline{\mathcal{L}}(y)^{\perp}\subset\mathcal{V}_{y,\mathbf{s_{1}}}-_{\eta}\mathcal{V}_{y,\mathbf{s_{2}}}.$

where we recall that $\eta=\exp(-O(d))$.

In order to determine $V$, fix $y\in W$ and let $S_{y}$ be the set of all
tuples
$\mathbf{s}=(y_{1},y_{2},y_{3},w_{1},w_{2},w_{3},w_{4},z_{1},z_{2},z_{3},z_{4})\in(\mathbb{F}^{n})^{11}$
that satisfy Equation 9. Note that the density of each $S_{y}$ is at least
$\exp(-O(d^{5}))$. To simplify the notation, denote
$\mathbf{s}=(s_{1},\ldots,s_{11})$. We invoke Lemma 2.5 in a similar way to
before. Define a family $\mathcal{L}^{*}$ of linear maps, containing linear
maps $L_{i}$ for each $L\in\mathcal{L}$ and $i=1,\ldots,11$, where

$L_{i}:(\mathbb{F}^{n})^{11}\rightarrow\mathbb{F}^{m},L_{i}(\mathbf{s})=L(s_{i}).$

Applying Lemma 2.5 to $\mathcal{L}^{*}$ and density parameter
$\delta=\exp(-O(d^{5}))$, we obtain a subspace $V\subset\mathbb{F}^{m}$ of
codimension $O(d^{7})$ such that for each $y\in W$,

$\Pr_{\mathbf{s_{1}},\mathbf{s_{2}}\in
S_{y}}\left[V\cap\overline{\mathcal{L}}(y)^{\perp}\subset(\overline{\mathcal{L}}(\mathbf{s_{1}})+\overline{\mathcal{L}}(y))^{\perp}+(\overline{\mathcal{L}}(\mathbf{s_{2}})+\overline{\mathcal{L}}(y))^{\perp}\right]\geq\frac{1}{2},$
(10)

which implies

$\Pr_{\mathbf{s_{1}},\mathbf{s_{2}}\in(\mathbb{F}^{n})^{11}}\left[V\cap\overline{\mathcal{L}}(y)^{\perp}\subset\mathcal{V}_{y,\mathbf{s_{1}}}-_{\eta}\mathcal{V}_{y,\mathbf{s_{2}}}\right]\geq\exp(-O(d^{5})).$
(11)

Define the final bilinear structure as

$B^{6}:=\bigcup_{y\in
W}\left(V\cap{\overline{\mathcal{L}}(y)}^{\perp}\right)\times\\{y\\}.$

It satisfies

$B^{6}\subset\phi_{\textup{h}\textup{v}\textup{v}\textup{h}\textup{v}}^{\varepsilon_{6}}(B^{2})$

with $\varepsilon_{6}=\exp(-O(d^{5}))$, and so overall

$B^{6}\subset\phi_{\textup{h}\textup{v}\textup{v}\textup{h}\textup{v}\textup{v}\textup{v}\textup{h}\textup{h}}^{\varepsilon}(A)$

with $\varepsilon=\exp(-O(d^{5}))$.

## References

  * [BL17] Pierre-Yves Bienvenu and Thái Hoàng Lê.  A bilinear Bogolyubov theorem.  arXiv preprint arXiv:1711.05349, 2017.
  * [BL19] Pierre-Yves Bienvenu and Thái Hoàng Lê.  Linear and quadratic uniformity of the Möbius function over $\mathbb{F}_{q}[t]$.  Mathematika, 65(3):505–529, 2019.
  * [GM17a] Timothy Gowers and Luka Milićević.  A bilinear version of Bogolyubov’s theorem.  arXiv preprint arXiv:1712.00248, 2017.
  * [GM17b] Timothy Gowers and Luka Milićević.  A quantitative inverse theorem for the $U^{4}$ norm over finite fields.  arXiv preprint arXiv:1712.00241, 2017.
  * [Gre05] Ben Green.  Notes on the polynomial Freiman-Ruzsa conjecture.  Preprint, 2005.  http://people.maths.ox.ac.uk/greenbj/papers/PFR.pdf.
  * [GT08] Ben Green and Terence Tao.  An inverse theorem for the Gowers $U^{3}$ norm.  Proc. Edinb. Math. Soc. (2), 51(1):73–153, 2008.
  * [GT10] Ben Green and Terence Tao.  An equivalence between inverse sumset theorems and inverse conjectures for the $U^{3}$ norm.  Math. Proc. Cambridge Philos. Soc., 149(1):1–19, 2010.
  * [Lov12] Shachar Lovett.  Equivalence of polynomial conjectures in additive combinatorics.  Combinatorica, 32(5):607–618, 2012.
  * [Sam07] Alex Samorodnitsky.  Low-degree tests at large distances.  In STOC’07 Proceedings of the thirty-ninth annual ACM symposium on Theory of Computing, 506–515. ACM, 2007.
  * [San12a] Tom Sanders.  On the Bogolyubov-Ruzsa lemma.  Analysis & PDE, 5(3):627–655, 2012.
  * [San12b] Tom Sanders.  The structure theory of set addition revisited.  Bull. Amer. Math. Soc., 50(1): 93–127, 2013.
  * [SS16] Tomasz Schoen and Olof Sisask.  Roth’s theorem for four variables and additive structures in sums of sparse sets.  Forum Math. Sigma 4, e5, 28 pp, 2016.
  * [TV06] Terence Tao and Van H Vu.  Additive combinatorics. Cambridge Studies in Advanced Mathematics, volume 105, Cambridge University Press, 2006.

[kaave] Kaave Hosseini
University of California, San Diego
USA
skhosseiucsdedu
http://cseweb.ucsd.edu/~skhossei/ [shachar] Shachar Lovett
University of California, San Diego
USA
slovettucsdedu
https://cseweb.ucsd.edu/~slovett/home.html