Good bounds for sets lacking skew corners
Luka Milićević†

00footnotetext: † Mathematical Institute of the Serbian Academy of Sciences
and Arts
† Email<EMAIL_ADDRESS>
  * Abstract

a A skew corner is a triple of points in $\mathbb{Z}\times\mathbb{Z}$ of the
form $(x,y),(x,y+a)$ and $(x+a,y^{\prime})$. Pratt posed the following
question: how large can a set $A\subseteq[n]\times[n]$ be, provided it
contains no non-trivial skew corner (i.e. one for which $a\not=0$)? We prove
that $|A|\leq\exp(-c\log^{c}n)n^{2}$, for an absolute constant $c>0$, which,
along with a construction of Beker, essentially resolves Pratt’s question.
a Our argument is represents a two-dimensional variant of the method of Kelley
and Meka, which they used to prove Behrend-type bounds in Roth’s theorem. A
very similar result was obtained independently and simultaneously by Jaber,
Lovett and Ostuni.

## §1 Introduction

In [20], Pratt defined skew corner to be a configuration of the form
$(x,y),(x,y+a),(x+a,y^{\prime})$, with $x,y,y^{\prime},a\in\mathbb{Z}$. If
$a\not=0$, we say that the skew corner is non-trivial. In that paper, as a
part of study of certain group-theoretic approaches to the problem of
obtaining an optimal matrix multiplication algorithm originating in [7, 8],
Pratt posed the following problem: how large can a subset
$A\subseteq[n]\times[n]$ be, provided it contains no non-trivial skew corners?
Let us write $s(n)$ for this quantity. Additionally, he conjectured that in
fact $s(n)=O_{\varepsilon}(n^{1+\varepsilon})$ for every $\varepsilon>0$. In
particular, if it had held, that conjecture would have implied that the
approaches above cannot give an optimal matrix multiplication algorithm.
Notice that, if one sets $y^{\prime}=y$, then a skew corner becomes a corner
in the usual sense in the context of additive combinatorics. Finding bounds on
the size of sets that lack non-trivial corners is a well-studied problem, with
Ajtai and Szemerédi [1] obtaining first bounds of the form $o(n^{2})$. The
best known bounds in the latter problem are due to Shkredov [23], immediately
giving $s(n)\leq O(n^{2}/(\log\log n)^{\Omega(1)})$. When it comes to lower
bounds, Petrov [18] showed that $s(n)\geq\Omega(n\log n/\sqrt{\log\log n})$.
In [19], Pohoata and Zakharov showed $s(n)\geq\Omega(n^{5/4})$, thus refuting
Pratt’s conjecture. They even conjectured that $s(n)\leq O(n^{2-c})$ for an
absolute constant $c>0$. Very recently, Beker [4] disproved their conjecture
by obtaining a Behrend-type lower bound and also improved the upper bounds,
namely

$n^{2}\exp(-O(\sqrt{n}))\leq s(n)\leq O(n^{2}\log^{-\Omega(1)}n).$ (1)

Finally, Beker asked whether Behrend-shape upper bounds hold for the skew
corners-free sets. Our main result is that this is indeed the case, which
essentially answers the initial question of Pratt, at least when it comes to
the shape of the bounds.

######  Theorem 1.1.

There exists an absolute constant $c>0$ with the following property. Let
$A\subseteq[n]\times[n]$ be a skew corner-free set, i.e. a set which contains
no configuration of the form $(x,y),(x,y+a),(x+a,y^{\prime})$, with
$x,y,y^{\prime},a\in\mathbb{Z}$ and $a\not=0$. Then

$|A|\leq\exp(-c\log^{c}n)n^{2}.$

Remark. A very similar result was obtained independently and simultaneously by
Jaber, Lovett and Ostuni [13].

Our approach is closely related to the breakthrough work of Kelley and Meka
[14], where they proved Behrend-shape bounds in Roth’s theorem. However, given
that the problem considered in this paper is two-dimensional rather than one-
dimensional leads to important differences. Let us also mention that Peluse
posed the problem of improving the bounds on the corner-free sets using the
methods of Kelley and Meka (see Problem 1.18 in [17] and the surrounding
discussion). Hence, the work in this paper can be seen as progress towards
that goal.

### 1.1. Proof overview

We include a very brief summary of Kelley and Meka’s proof in this subsection
(see also an exposition by Bloom and Sisask [5]), but before we embark on that
discussion, let us explore the traditional additive-combinatorial approaches
to questions of finding arithmetic configurations.

For the following discussion, we use the usual notion of discrete
multiplicative derivative $\partial_{a}$, which, for a given function $f\colon
G\to\mathbb{C}$ gives another one defined as
$\partial_{a}f(x)=f(x+a)\overline{f(x)}$. A fundamental tool in the context of
counting arithmetic configurations are uniformity norms, introduced by Gowers
in [11, 12]. For example, if $f_{1},f_{2},f_{3}\colon G\to\mathbb{D}$ are
three functions, in the case of arithmetic progressions of length 3, the
uniformity norm $\mathsf{U}^{2}$, defined via formula
$\|f\|_{\mathsf{U}^{2}}^{4}=(\mathop{\mathbb{E}}_{a,b,x}\partial_{a}\partial_{b}f(x))^{1/4}$,
controls the corresponding counting multilinear form via inequality
$|\mathop{\mathbb{E}}_{x,a}f_{1}(x)f_{2}(x+a)f_{3}(x+2a)|\leq\|f_{3}\|_{\mathsf{U}^{2}}.$
The proof proceeds via Cauchy-Schwarz inequality (abbreviated to CS below)

$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,a}f_{1}(x)$ $\displaystyle
f_{2}(x+a)f_{3}(x+2a)\Big{|}^{4}=\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x}f_{1}(x)\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a}f_{2}(x+a)f_{3}(x+2a)\Big{)}\Big{|}^{4}$
$\displaystyle\leq$
$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x}|f_{1}(x)|^{2}\Big{|}^{2}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a}f_{2}(x+a)f_{3}(x+2a)\Big{|}^{2}\Big{|}^{2}\hskip
56.9055pt\text{(using CS)}$ $\displaystyle\leq$
$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a}f_{2}(x+a)f_{3}(x+2a)\Big{|}^{2}\Big{|}^{2}$
(2) $\displaystyle=$
$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,a,a^{\prime}}f_{2}(x+a)f_{3}(x+2a)\overline{f_{2}(x+a^{\prime})f_{3}(x+2a^{\prime})}\Big{|}^{2}\hskip
56.9055pt\text{(after expanding)}$ $\displaystyle=$
$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,a,y}\partial_{a}f_{2}(x)\partial_{2a}f_{3}(x+y)\Big{|}^{2}\hskip
56.9055pt\text{(change of variables)}$ $\displaystyle=$
$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,a}\partial_{a}f_{2}(x)\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y}\partial_{2a}f_{3}(x+y)\Big{)}\Big{|}^{2}$
$\displaystyle\leq$
$\displaystyle\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,a}|\partial_{a}f_{2}(x)|^{2}\Big{)}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,a}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y}\partial_{2a}f_{3}(x+y)\Big{|}^{2}\Big{)}\hskip
56.9055pt\text{(using CS)}$ $\displaystyle\leq$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,a}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y}\partial_{2a}f_{3}(x+y)\Big{|}^{2}$ (3)
$\displaystyle=$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,a,b}\partial_{2a,b}f_{3}(x).$

Observe that each Cauchy-Schwarz step gives rise to another application of
discrete multiplicative derivative. The derivative is applied in the direction
corresponding to the difference between corresponding points in the arguments
of the functions. More precisely, notice that in each Cauchy-Schwarz step we
eliminate a term, say $f(x)$, e.g. in (2) we eliminated term involving $f_{1}$
and in (3) we eliminated term involving $f_{2}$. Then every remaining term
$g(y)$ receives additional derivative $\partial_{y-x}$ upon expanding in the
next step.
We may carry out analogous steps in the case when we count skew corners. This
time the method above gives the following inequalities, depending on which
variables we use in outer expectation in the applications of Cauchy-Schwarz
inequality,111We are slightly more careful in the last step of the method
sketched above; that step actually gives upper bound which is the product of
norms of two functions, rather than a norm of a single function.

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,y,a,y^{\prime}}f_{1}(x,y)f_{2}(x,y+a)f_{3}(x+a,y^{\prime})\Big{|}\leq\|f_{i}\|_{\mathsf{U}(G\times
G,\\{0\\}\times G))}\|f_{3}\|_{\mathsf{U}^{2}},$

for $i\in\\{1,2\\}$, and

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,y,a,y^{\prime}}f_{1}(x,y)f_{2}(x,y+a)f_{3}(x+a,y^{\prime})\Big{|}\leq\|f_{1}\|_{\mathsf{U}(G\times
G,\\{0\\}\times G))}\|f_{2}\|_{\mathsf{U}(G\times G,\\{0\\}\times G))},$

and where $\|\cdot\|_{\mathsf{U}(H_{1},H_{2})}$ is the directional uniformity
norm222See [2, 3, 16] for the definition and discussion of directional
uniformity norms. with derivative groups $H_{1},H_{2}\leq G\times G$, i.e.

$\|f\|_{\mathsf{U}(H_{1},H_{2})}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G\times G,a_{1}\in H_{1},a_{2}\in
H_{2}}\partial_{a_{1}}\partial_{a_{2}}f(x).$

In particular, having the $\mathsf{U}^{2}$ control is sufficient when it comes
to obtaining quantitative bounds for this problem. This observation was
exploited by Beker [4] in his proof of the upper bound (1), (at least in the
finite vector space model of the problem; see Proposition 3.1 in that paper).

However, in order to achieve Behrend-type bounds, according to Kelley-Meka
method, it is crucial that we have a simultaneous control over the two norms
appearing in the final inequalities in the method above. In a nutshell, in the
Kelley-Meka method we replace the first application of Cauchy-Schwarz
inequality by Hölder’s inequality and in then their method can be viewed as
weak form of the inverse theory for the resulting norm. But, if we were to
have two applications Hölder’s inequality, then the possible inverse
conjectures would not necessarily imply the desired density increment. See
Example 8 and surrounding discussion in the paper of Shkredov [24]. So, in
some sense, our work is adaptation of Kelley-Meka method for the directional
norm ${\mathsf{U}(G\times G,\\{0\\}\times G))}$.

Furthermore, the problem of finding skew corners has an additional level of
difficulty in comparison with Roth’s theorem. Namely, in Roth’s theorem, the
only structured sets that play a role, stemming from the obstruction to
uniformity for $\mathsf{U}^{2}$ norm, are precisely (coset of) subspaces of
$G$. Thus, in that problem, we have the following simple hierarchy of
structures, $A^{\prime}\subseteq t+H\subseteq G$, where $A^{\prime}$ is the
intersection $A\cap(t+H)$, for the given set $A$, and $t+H$ is a coset of a
subspace that arises during the density increment procedure. If $A^{\prime}$
is quasirandom subset of $t+H$ in the $\mathsf{U}^{2}$ sense, this hierarchy
completely determines the count of arithmetic progressions of length 3, and
the density of $t+H$ in $G$ and the relative density of $A^{\prime}$ in $t+H$
have different effects on this count.
When it comes to finding skew corners, we need an additional kind of structure
in the hierarchy, namely sets that depend only on the first coordinate. This
time, the hierarchy is $A^{\prime}\subseteq
X\times(t+H)\subseteq(s+H)\times(t+H)\subseteq G\times G$, which has more
levels than that required in the Roth’s theorem.

Let us now return to an outline of our work and examine more closely Kelley
and Meka’s approach.
Let us write $\|\cdot\|_{\mathsf{U}^{2,r}_{\textnormal{KM}}}$ for the norm
arising in their work. Namely,

$\|f\|_{\mathsf{U}^{2,r}_{\textnormal{KM}}}=\bigg{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}a_{1},a_{2}\\\
b_{1},\dots,b_{r}\end{subarray}}\prod_{i\in[r]}f(x+a_{1}+b_{i})f(x+a_{2}+b_{i})\bigg{)}^{1/2r}.$

Note that in the case $r=2$, this quantity becomes the usual $\mathsf{U}^{2}$
uniformity norm.
Even though this paper is exclusively about a problem in cyclic groups, to
simplify the notation in this introductory discussion, in the rest of this
section (with the exception of Corollary 1.2), we consider the finite vector
space and write $G=\mathbb{F}_{p}^{n}$. Of course, in the actual work we shall
use appropriate substitutes for various notions appearing here, e.g. Bohr sets
for subgroups etc.
Let $A\subseteq G$ be a set of density $\delta$ without arithmetic progression
of length 3. Let us write $\mathsf{b}_{A}=\mathbbm{1}_{A}-\delta$ for the
balanced function of $A$. In the simplest terms, the argument of Kelley and
Meka consists of the following steps.

  * Step 1.

Starting from the assumption that $A$ has no arithmetic progressions, they
obtain
$\|\mathsf{b}_{A}\|_{\mathsf{U}^{2,r}_{\textnormal{KM}}}\geq\Omega(\delta)$
for a suitable $r$. Since these norms quantify the deviation of $A$ from a
quasirandom set, we may say that the aim of this step is to find imbalance in
$A$. (This step was called Hölder lifting in [5].)

  * Step 2.

In the second step, it is shown that the inequality
$\|\mathsf{b}_{A}\|_{\mathsf{U}^{2,r}_{\textnormal{KM}}}\geq\Omega(\delta)$
implies $\|\mathsf{b}_{A}\|_{\mathsf{U}^{2,r^{\prime}}_{\textnormal{KM}}}\geq
1+\Omega(\delta)$ for some $r^{\prime}$ which is slightly larger than $r$. So
in this step they pass from $\mathsf{b}_{A}$ to $\mathbbm{1}_{A}$. Kelley and
Meka called his step spectral positivity (and in [5] it is referred to as
unbalancing).

  * Step 3.

Starting from inequality
$\|\mathsf{b}_{A}\|_{\mathsf{U}^{2,r^{\prime}}_{\textnormal{KM}}}\geq
1+\Omega(\delta)$, using dependant random choice, in the step called sifting,
they find an additional set $A^{\prime}$, of density $\alpha^{\prime}$, such
that

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,y}\mathbbm{1}_{S}(x)\mathbbm{1}_{A^{\prime}}(x+y)\mathbbm{1}_{A^{\prime}}(y)\geq(1+\Omega(1)){\alpha^{\prime}}^{2},$

where $S$ is the set of elements $x$ where the self-convolution
$\mathbbm{1}_{A}\ast\mathbbm{1}_{A}$ is significantly larger than its mean
$\delta^{2}$.

  * Step 4.

Using almost-periodicity results stemming from the works of Croot and Sisask,
and Sanders, applied to the expression above, they obtain a subspace $V$ of
small codimension such that

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{x,y\in G,v\in
V}\mathbbm{1}_{S}(x+v)\mathbbm{1}_{A^{\prime}}(x+y)\mathbbm{1}_{A^{\prime}}(y)\geq(1+\Omega(1)){\alpha^{\prime}}^{2}.$

  * Step 5.

The final step is to obtain an efficient density increment using the
conclusions above.

In this work, however, we are looking for skew corners rather than arithmetic
progressions of length 3, giving rise to a different type of structural
hierarchy, as mentioned above. This has two important ramifications. Firstly,
throughout the proof, instead of norm
$\|\cdot\|_{\mathsf{U}^{2,r}_{\textnormal{KM}}}$, we analyse the norm called
vertical segments norm, which is defined as

$\|f\|_{\mathsf{VS}_{r}}=\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1},\dots,x_{r},y_{1},\dots,y_{r},a}\prod_{i\in[r]}f(x_{i},y_{i})f(x_{i},y_{i}+a)\Big{)}^{1/2r},$

for $f\colon G\times G\to\mathbb{R}$. Their name stems from the fact that the
points in the arguments of $f$ in the expression above belong to $r$ vertical
segments of length $a$.

This is a good place to mention another variant of such norms, called grid
norms, defined as

$\|f\|_{\mathsf{gr}_{2,r}}=\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1},x_{2}\in X,y_{1},\dots,y_{r}\in
Y}\prod_{i\in[r]}f(x_{1},y_{i})f(x_{2},y_{i})\Big{)}^{1/2r},$

for functions $f\colon X\times Y\to\mathbb{R}$, which were introduced by
Kelley, Lovett and Meka in [15]. Just like
$\|\cdot\|_{\mathsf{U}^{2,r}_{\textnormal{KM}}}$ corresponds to the usual
$\mathsf{U}^{2}$ norm, and vertical segments norm corresponds to the
directional norm $\|\cdot\|_{\mathsf{U}(G\times G,\\{0\\}\times G)}$, the grid
norms correspond to 2-dimensional box norm.

Given that we work with different norms, we need to modify the steps of Kelley
and Meka’s proof. In particular, we can no longer use the spectral positivity
step, as that argument relied on the specific form of the norm
$\|\cdot\|_{\mathsf{U}^{2,r}_{\textnormal{KM}}}$. However, in [10], where they
generalize the argument of Kelley and Meka to certain systems of linear forms,
Filmus, Hatami, Hosseini and Kelman encounter a similar difficulty, as they
consider grid norms instead of
$\|\cdot\|_{\mathsf{U}^{2,r}_{\textnormal{KM}}}$, and their argument for this
step is based on a combination a more direct use of a variant of Gowers-
Cauchy-Schwarz inequalities and an inequality of Kelley and Meka concerning
functions with non-negative odd moments (see Lemma 2.9). We overcome this
issue in a similar spirit in our paper.

Furthermore, as our structural hierarchy is $A\subseteq
X\times(t+H)\subseteq(s+H)\times(t+H)\subseteq G\times G$, we additionally
have to perform a regularization step at the beginning of the density
increment strategy, which ensures that columns of $A$ are well-behaved, as
well as the set $X$ itself. Hence, our proof consists of the following steps.

  * Step 1.

Regularization of $A$. In this step we pass to well-behaved columns of the set
$A$.

  * Step 2.

Finding imbalance in $A$. We show that a suitably defined balanced function of
$A$ is not quasirandom, i.e. that it has large vertical segments norm.

  * Step 3.

Passing from $\mathsf{b}$ to $\mathbbm{1}_{A}$. We conclude that the vertical
segments norm of $\mathbbm{1}_{A}$ is significantly higher than that of a
randomly chosen subset of $X\times(t+H)$ of the same density.

  * Step 4.

Sifting. We use a dependent random choice argument to find sets to turn the
information on the vertical segments norm of $\mathbbm{1}_{A}$ into further
counts of arithmetic configurations.

  * Step 5.

Using almost-periodicity. We use almost-periodicity results to find strong
algebraic structure. Let us remark that, even though the problem at hand is
two-dimensional, we may again use one-dimensional almost-periodicity results.

  * Step 6.

Completing the proof. The conclusions of previous steps are put together to
find a desired density increment.

Our main technical result is Proposition 3.1, which sums up a single density
increment step.

We conclude this section with an additional comment on how our results differ
from those of Filmus, Hatami, Hosseini and Kelman [10], apart from the obvious
distinction that their main arithmetic result is about one-dimensional
structures. In that work, they prove a general counting lemma for graphs
(Theorem 1.11 in their paper), which in the conclusion has a density increment
on a product of unstructured sets $S\times T$, which is unsuitable for our
purposes, as we look for structure of the form $S\times(t+H)$ for a subgroup
$H\leq G$.
On the other hand, their main result on arithmetic configurations concerns
(special instances of) affine binary systems of linear forms. These are
configurations parameterized by variables $x_{1},\dots,x_{k}$, where each
point is $\lambda_{ij_{1}}x_{j_{1}}+\lambda_{ij_{2}}x_{j_{2}}$,
$\lambda_{ij_{1}},\lambda_{ij_{2}}\not=0$ and $j_{1}\not=j_{2}$, with the
crucial requirement that pairs $\\{j_{1},j_{2}\\}$ are distinct for every $i$.
For example, arithmetic progression of length 3 can be parametrized as
$\Big{(}x-y,\frac{x-z}{2},y-z\Big{)}$, which is in the described family. We
now give a corollary of Theorem 1.1 in the 1-dimensional setting, which cannot
be realized as a binary system of linear forms.

######  Corollary 1.2.

There exists an absolute constant $c^{\prime}>0$ with the following property.
Let $B\subseteq[n]$ be a set that has no non-trivial configurations of the
form

$\Big{(}x,x+y,x+2y,x+y+a,x+2y+2a,x+a\Big{)}$

for some $x,y,a\in\mathbb{Z}$. Then

$|B|\leq\exp(-c^{\prime}\log^{c^{\prime}}n)n.$

###### Proof sketch.

Write $\beta=|B|/n$. Let $A\subseteq[n]\times[n]$ consist of all $(x,y)$ such
that $x,x+y,x+2y\in B$. By Kelley and Meka’s proof of Roth’s theorem, we see
that $A$ has density $\exp(-O(\log^{O(1)}\beta^{-1}))$ inside $[n]\times[n]$.
It follows from Theorem 1.1 that, unless $\beta$ is smaller than claimed
bound, $A$ has a non-trivial skew corner, which can be reinterpreted as the
configuration in the statement.∎

Let us briefly indicate why this configuration cannot be realized as a binary
system of linear forms. Suppose that we did have such a parametrization using
additional variables $u_{1},\dots,u_{k}$. Let us write $x(u),y(u),a(u)$ for
resulting elements $x,y,a$. Observe equalities

$x+y+a=(x+y)+(x+a)-x$

and

$x+2y+2a=2(x+y)+2(x+a)-3x.$

However, in a binary system, such equalities completely determine the two
variables $u_{i}$ which are used in the linear form on the left hand side,
implying that forms $(x+y+a)(u)$ and $(x+2y+2a)(u)$ have the same pair of
parametrizing variables.
The configuration in the corollary can be see as a union of two arithmetic
progressions of length 3, starting at the same base point $x$, with steps $a$
and $b$, with an additional point $x+a-b$. Without the last point, it is easy
to obtain such a 5-point configuration from Roth’s theorem by Cauchy-Schwarz
inequality (in fact, such a system is an affine binary systems of linear
forms). However, the introduction of the last point adds another non-trivial
arithmetic restriction and seems to make the problem more difficult.

Acknowledgements. This research was supported by the Ministry of Science,
Technological Development and Innovation of the Republic of Serbia through the
Mathematical Institute of the Serbian Academy of Sciences and Arts, and by the
Science Fund of the Republic of Serbia, Grant No. 11143, Approximate Algebraic
Structures of Higher Order: Theory, Quantitative Aspects and Applications \-
A-PLUS.

## §2 Preliminaries

In this preliminary section, we gather a few general technical results that we
will exploit later in the paper. We use the standard averaging notation
$\mathop{\mathbb{E}}_{x\in X}$, which is the shorthand for
$\frac{1}{|X|}\sum_{x\in X}$, and we also write
$\mathbb{D}=\\{z\in\mathbb{C}\colon|z|=1\\}$ for the unit disk.

### 2.1. Bohr sets

As it is well-known, due to lack of subgroups in cyclic groups
$\mathbb{Z}/N\mathbb{Z}$ we are forced to work with approximate substitutes of
subgroups. With this in mind, as it is standard in additive combinatorics, we
use the machinery of (regular) Bohr sets, introduced by Bourgain in [6]. In
the precise statements of defnitions below, we follow the work of Schoen and
Sisask [22], in which they prove Behrend-type bounds for sets lacking
solutions to 4 variable equations, as we need their variants of almost-
periodicity results.

######  Definition 2.1.

Let $\Gamma\subseteq\mathbb{Z}/N\mathbb{Z}$ be a set and let $\rho\geq 0$. The
_Bohr set_ on the _frequency set_ $\Gamma$ with _radius_ $\rho$ is given by

$\operatorname{Bohr}(\Gamma,\rho)=\\{x\in\mathbb{Z}/N\mathbb{Z}\,\colon(\forall
r\in\Gamma)\,\,|\operatorname{e}(rx/N)-1|\leq\rho\\},$

where $\operatorname{e}(t)=\exp(2\pi it)$. We refer to $|\Gamma|$ as the
_rank_ of the Bohr set.
If $B$ is a Bohr set given by $B=\operatorname{Bohr}(\Gamma,\rho)$, for a real
$\delta\geq 0$, we define its _$\delta$ -dilate_ $B_{\delta}$ as
$\operatorname{Bohr}(\Gamma,\delta\rho)$.
A Bohr set $B$ of rank $d$ is _regular_ if

$1-12d|\delta|\leq\frac{|B_{1+\delta}|}{|B|}\leq 1+12d|\delta|$

whenever $|\delta|\leq 1/12d$.

######  Lemma 2.2 (Elementary properties of Bohr sets).

Suppose that $B=B(\Gamma,\rho)$ is a Bohr set of rank $d$.

  * (i)

For any $\delta,\delta^{\prime}\geq 0$ we have
$B_{\delta}+B_{\delta^{\prime}}\subseteq B_{\delta+\delta^{\prime}}$.

  * (ii)

We have the _size estimate_ $|B|\geq(\rho/2\pi)^{d}N$.

  * (iii)

We have the _doubling estimate_ $|B_{2}|\leq 6^{d}|B|$.

  * (iv)

There exists a $\delta\in[1/2,1]$ for which $B_{\delta}$ is regular.

We need a general lemma that allows us to carry out linear changes of
variables. In contrast to the finite vector space case, we are only allowed to
modify variables by other ones that range over narrower Bohr sets. Firstly, we
prove the case when we introduce a single dummy variable.

######  Lemma 2.3 (Basic change of variables).

Let $B^{(1)},\dots,B^{(k)}$ be regular Bohr sets of rank at most $d$, and let
$S\subseteq\cap_{i\in[k]}B^{(i)}_{\rho}$. Let
$F\colon(\mathbb{Z}/N\mathbb{Z})^{k+1}\to\mathbb{D}$ be a function. Let
$\nu_{1},\dots,\nu_{k}\in\mathbb{Z}$ be given. Then

$\displaystyle\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1}\in B^{(1)},\dots,x_{k}\in B^{(k)},y\in
S}F(x_{1},\dots,x_{k},y)-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1}\in B^{(1)},\dots,x_{k}\in B^{(k)},y\in
S}F(x_{1}+\nu_{1}y,\dots,x_{k}+\nu_{k}y,y)\bigg{|}\leq 50\rho
kd\|\nu\|_{\infty}.$

In this work, we shall typically apply the lemma above to the case where

$F(x_{1},\dots,x_{k},y)=\prod_{i\in[s]}f_{i}\Big{(}\sum_{j\in[k]}\lambda_{ij}x_{j}+\lambda_{ik+1}y,\sum_{j\in[k]}\mu_{ij}x_{j}+\mu_{ik+1}y\Big{)}$

for some functions
$f_{1},\dots,f_{s}\colon\mathbb{Z}/N\mathbb{Z}\times\mathbb{Z}/N\mathbb{Z}\to\mathbb{D}$
and $\lambda_{1},\dots,\lambda_{s},\mu_{1},\dots,\mu_{s}\in\mathbb{Z}^{k+1}$.

###### Proof.

Fix arbitrary $y\in S$. For the given $y$ we prove the related inequality

$\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1}\in B^{(1)},\dots,x_{k}\in
B^{(k)}}F(x_{1},\dots,x_{k},y)-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1}\in B^{(1)},\dots,x_{k}\in
B^{(k)}}F(x_{1}+\nu_{1}y,\dots,x_{k}+\nu_{k}y,y)\bigg{|}\leq 50\rho
kd\|\nu\|_{\infty}$

and then the lemma follows from the triangle inequality. Let
$K=\|\nu\|_{\infty}$. Consider the set $X=B^{(1)}_{1-K\rho}\times\cdots\times
B^{(k)}_{1-K\rho}$. Note that $(x_{1}+\nu_{1}y,\dots,x_{k}+\nu_{k}y)\in
B^{(1)}\times\cdots\times B^{(k)}$ for all $(x_{1},\dots,x_{k})\in X$.
Therefore, for all elements $(x_{1},\dots,x_{k})\in
X\cap(\nu_{1}y,\dots,\nu_{k}y)+X$ the term $F(x_{1},\dots,x_{k},y)$ appears in
both of averages

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{x_{1}\in
B^{(1)},\dots,x_{k}\in B^{(k)}}F(x_{1},\dots,x_{k},y)\,\,\text{ and
}\,\,\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1}\in B^{(1)},\dots,x_{k}\in
B^{(k)}}F(x_{1}+\nu_{1}y,\dots,x_{k}+\nu_{k}y,y).$

Hence, writing $\tilde{B}=B^{(1)}\times\cdots\times B^{(k)}$, for which we
know that $X\pm(\nu_{1}y,\dots,\nu_{k}y)\subseteq\tilde{B}$, we see that

$\displaystyle\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1}\in B^{(1)},\dots,x_{k}\in
B^{(k)}}F(x_{1},\dots,x_{k},y)-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1}\in B^{(1)},\dots,x_{k}\in
B^{(k)}}F(x_{1}+\nu_{1}y,\dots,x_{k}+\nu_{k}y,y)\bigg{|}$ $\displaystyle\hskip
56.9055pt\leq\frac{|\tilde{B}\setminus(X\cap(\nu_{1}y,\dots,\nu_{k}y)+X)|+|(\tilde{B}+(\nu_{1}y,\dots,\nu_{k}y))\setminus(X\cap(\nu_{1}y,\dots,\nu_{k}y)+X)|}{|\tilde{B}|}$
$\displaystyle\hskip 56.9055pt\leq\frac{4|\tilde{B}\setminus
X|}{|\tilde{B}|}\leq 4\sum_{i\in[k]}\frac{|B^{(i)}\setminus
B^{(i)}_{1-K\rho}|}{|B^{(i)}|}\leq 50kKd\rho,$

where we used regularity in the last step.∎

We now deduce a general version of the change of variables lemma.

######  Lemma 2.4 (Change of variables).

Let $B^{(1)},\dots,B^{(k)}$ be regular Bohr sets of rank at most $d$, and let
$Y_{1},\dots,Y_{\ell}\subseteq\cap_{i\in[k]}B^{(i)}_{\rho}$ be sets. Let
$Z_{1},\dots,Z_{m}\subseteq\mathbb{Z}/N\mathbb{Z}$ be arbitrary sets. Let
$F\colon(\mathbb{Z}/N\mathbb{Z})^{k+\ell+m}\to\mathbb{D}$ be a function. Let
$\nu\in\mathbb{Z}^{[k]\times[\ell]}$ be given. Then

$\displaystyle\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1}\in
B^{(1)},\dots,x_{k}\in B^{(k)}\\\ y_{1}\in Y_{1},\dots,y_{\ell}\in Y_{\ell}\\\
z_{1}\in Z_{1},\dots,z_{m}\in
Z_{m}\end{subarray}}F(x_{1},\dots,x_{k},y_{1},\dots,y_{\ell},z_{1},\dots,z_{m})$
$\displaystyle\hskip
28.45274pt-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1}\in
B^{(1)},\dots,x_{k}\in B^{(k)}\\\ y_{1}\in Y_{1},\dots,y_{\ell}\in Y_{\ell}\\\
z_{1}\in Z_{1},\dots,z_{m}\in
Z_{m}\end{subarray}}F\Big{(}x_{1}+\sum_{j\in[\ell]}\nu_{1\,j}y_{j},\dots,x_{k}+\sum_{j\in[\ell]}\nu_{k\,j}y_{j},y_{1},\dots,y_{\ell},z_{1},\dots,z_{m}\Big{)}\bigg{|}\leq
50\rho k\ell d\|\nu\|_{\infty}.$

We refer to variables $y_{1},\dots,y_{\ell}$ as the _dummy variables_ as we
typically apply the lemma to approximate expressions such as

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{a,s,t\in B_{\mu},y\in
B}f(a,y+a+s)f(a,y+a+t)\approx\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a,s,t\in B_{\mu},y\in B}f(a,y+s)f(a,y+t)$

when $\mu\ll 1$. In general, we say that we apply the lemma above for the
_transformation_ $x_{i}\mapsto x_{i}+\sum_{j\in[\ell]}\nu_{i\,j}y_{j}$, for
$i\in[k]$.

###### Proof.

By triangle inequality, it suffices to prove that

$\displaystyle\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1}\in
B^{(1)},\dots,x_{k}\in B^{(k)}\\\ y_{1}\in Y_{1},\dots,y_{\ell}\in
Y_{\ell}\end{subarray}}F(x_{1},\dots,x_{k},y_{1},\dots,y_{\ell},z_{1},\dots,z_{m})$
$\displaystyle\hskip
28.45274pt-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1}\in
B^{(1)},\dots,x_{k}\in B^{(k)}\\\ y_{1}\in Y_{1},\dots,y_{\ell}\in
Y_{\ell}\end{subarray}}F\Big{(}x_{1}+\sum_{j\in[\ell]}\nu_{1\,j}y_{j},\dots,x_{k}+\sum_{j\in[\ell]}\nu_{k\,j}y_{j},y_{1},\dots,y_{\ell},z_{1},\dots,z_{m}\Big{)}\bigg{|}.$

is at most $50\rho k\ell d\|\nu\|_{\infty}$ for any fixed $z_{1}\in
Z_{1},\dots,z_{m}\in Z_{m}$. Applying triangle inequality several times, the
expression above is at most

$\displaystyle\sum_{i\in[\ell]}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1}\in
Y_{1},\dots,y_{i-1}\in Y_{i-1}\\\ y_{i+1}\in Y_{i+1},\dots,y_{\ell}\in
Y_{\ell}\end{subarray}}$
$\displaystyle\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1}\in
B^{(1)},\dots,x_{k}\in B^{(k)}\\\ y_{i}\in
Y_{i}\end{subarray}}F\Big{(}x_{1}+\sum_{j\in[i-1]}\nu_{1\,j}y_{j},\dots,x_{k}+\sum_{j\in[i-1]}\nu_{k\,j}y_{j},y_{1},\dots,y_{\ell},z_{1},\dots,z_{m}\Big{)}$
$\displaystyle\hskip
28.45274pt-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1}\in
B^{(1)},\dots,x_{k}\in B^{(k)}\\\ y_{i}\in
Y_{i}\end{subarray}}F\Big{(}x_{1}+\sum_{j\in[i]}\nu_{1\,j}y_{j},\dots,x_{k}+\sum_{j\in[i]}\nu_{k\,j}y_{j},y_{1},\dots,y_{\ell},z_{1},\dots,z_{m}\Big{)}\bigg{|}.$

The basic case of the lemma applies to give an upper bound of $50\rho
kd\|\nu\|_{\infty}$ on the term between absolute values, completing the
proof.∎

As a consequence of the change of variables lemma, we are able to average over
translates of subsets of small enough dilates of a Bohr set.

######  Corollary 2.5.

Let $B$ be a regular Bohr set of rank $d$ and let $f\colon B\to[0,1]$ be a
function such that $\mathop{\mathbb{E}}_{x\in B}f(x)\geq c$. Let
$\lambda,\varepsilon>0$ be such that $\lambda\leq\varepsilon/(200d)$. Let
$S\subseteq B_{\lambda}$ be a non-empty set. Then there exists a translate
$t+S\subseteq B$ such that

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{x\in t+S}f(x)\geq
c-\varepsilon.$

###### Proof.

By regularity of $B$, provided $\lambda\leq\varepsilon/(24d)$, we have

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{x\in
B_{1-\lambda}}f(x)\geq c-\varepsilon/2.$

Provided $\lambda\leq\varepsilon/(200d)$, Lemma 2.4 gives

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{x\in
B_{1-\lambda},y\in
S}f(x+y)\geq\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in B_{1-\lambda},y\in
S}f(x)-\varepsilon/2\geq c-\varepsilon.$

The corollary follows after averaging over $x\in B_{1-\lambda}$.∎

### 2.2. Almost-periodicity

As in the case of Kelley and Meka’s proof of Roth’s theorem, efficient almost-
periodicity for convolutions play a crucial role in our paper. Such results
originate in the work of Croot and Sisask [9], and were used by Sanders [21],
along with other ideas, to prove quasipolynomial bounds in the Bogolyubov-
Ruzsa lemma. These results were further combined by Schoen and Sisask [22] to
give an even stronger almost-periodicity results. Here we record a variant of
their result.

######  Theorem 2.6 (Almost-periodicity).

Let $\varepsilon>0$ and let $B^{(1)}$ and $B^{(2)}$ be regular Bohr sets of
rank $d$. Let $B^{(2)}$ have radius $\rho$. Suppose that $Y\subseteq B^{(1)}$
and $Z\subseteq B^{(2)}$ are sets with relative densities
$\beta=|Y|/|B^{(1)}|$ and $\gamma=|Z|/|B^{(2)}|$. Let
$D\subseteq\mathbb{Z}/N\mathbb{Z}$ be an arbitrary set such that
$|Y|\leq|D|\leq 2|B^{(1)}|$. Then there exists a further regular Bohr set
$B^{\prime}\subseteq B^{(2)}$ of rank at most $d+d^{\prime}$ and radius at
least $\rho\varepsilon\beta/(24d^{3}d^{\prime})$ where

$d^{\prime}\leq
O\Big{(}\varepsilon^{-4}\log^{3}(2\beta^{-1})\log(2\gamma^{-1})\Big{)}$

such that

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{b\in B^{\prime},y\in B^{(1)},z\in
B^{(2)}}\mathbbm{1}_{D}(z-y+b)\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B^{(1)},z\in
B^{(2)}}\mathbbm{1}_{D}(z-y)\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)\Big{|}\leq\varepsilon\beta\gamma.$

The statement is very similar to Theorem 16 of [5], the only difference is
that we use radius instead of density of Bohr sets in the conclusion.

###### Proof.

We rely on Theorem 5.4 from [22]. Set $\lambda=1/(12d)$. Using the notation of
that theorem, we set $A=-Z$, $S=B^{(2)}_{\lambda}$, $M=Y$, $L=D$ and
$B=B^{(2)}_{\lambda}$. The radius of $B$ is thus $\lambda\rho$. The relative
density of $S$ inside $B$ is 1 and $\eta=|M|/|L|=|Y|/|D|\geq\beta/2$, while
$|Y|\leq|D|$ implies $\eta\leq 1$. Also,
$K=|A+S|/|A|\leq\frac{|B^{(2)}_{1+\lambda}|}{\gamma|B^{(2)}|}\leq(1+12d\lambda)\gamma^{-1}\leq
2\gamma^{-1}$, using regularity of $B^{(2)}_{\lambda}$. Theorem 5.4 of [22]
gives the desired Bohr set $B^{\prime}$ the bound

$d^{\prime}\leq
O\Big{(}\varepsilon^{-4}\log^{3}(2\beta^{-1})\log(2\gamma^{-1})\Big{)}$

and shows in particular that

$\Big{|}\sum_{x,y,z\in\mathbb{Z}/N\mathbb{Z}}\mathbbm{1}_{A}(x)\mathbbm{1}_{M}(y)\mathbbm{1}_{L}(z)\frac{1}{|B^{\prime}|}\mathbbm{1}_{B^{\prime}}(-x-y-z)-\sum_{x,y\in\mathbb{Z}/N\mathbb{Z}}\mathbbm{1}_{A}(x)\mathbbm{1}_{M}(y)\mathbbm{1}_{L}(-x-y)\Big{|}\leq\varepsilon|A||M|.$

Returning to our notation, we obtain

$\Big{|}\frac{1}{|B^{\prime}|}\sum_{b\in
B^{\prime},y,z\in\mathbb{Z}/N\mathbb{Z}}\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)\mathbbm{1}_{D}(z-y+b)-\sum_{y,z\in\mathbb{Z}/N\mathbb{Z}}\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)\mathbbm{1}_{D}(z-y)\Big{|}\leq\varepsilon|Y||Z|.$

Since $Y\subseteq B^{(1)}$ and $Z\subseteq B^{(2)}$ we may restrict the
variables $y$ and $z$ to $B^{(1)}$ and $B^{(2)}$. By dividing by
$|B^{(1)}||B^{(2)}|$, we obtain

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{b\in B^{\prime},y\in B^{(1)},z\in
B^{(2)}}\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)\mathbbm{1}_{D}(z-y+b)-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B^{(1)},z\in
B^{(2)}}\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)\mathbbm{1}_{D}(z-y)\Big{|}\leq\varepsilon\beta\gamma.\qed$

### 2.3. Gowers-Hölder inequalities

For the purposes of quantifying quasirandomness, we need to consider a family
of multilinear forms, that we shall refer to as _vertical segments Gowers
inner product_. Let us first recall the notion of grid norms, introduced by
Kelley, Lovett and Meka in [15]. For two sets $X$ and $Y$, $k$ and $\ell$
positive even integers333The condition that $k$ and $\ell$ are even is not
essential for the definition; it plays a role in the proof of the Gowers-
Cauchy-Schwarz inequality. and a function $f\colon X\times Y\to\mathbb{R}$,
grid norm $\|f\|_{\mathsf{U}_{k,\ell}}$ by the expression

$\|f\|_{\mathsf{U}_{k,\ell}}=\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{\ell}\in
Y\end{subarray}}\prod_{i\in[k],j\in[\ell]}f(x_{i},y_{j})\Big{|}^{1/k\ell}.$

An important property of the norms $\|\cdot\|_{\mathsf{U}_{k,\ell}}$ is that
they satisfy a variant of the Gowers-Cauchy-Schwarz inequality, similarly to
the original Gowers norms.

######  Proposition 2.7 (Lemma 2.2 in [10]).

Let $f_{i\,j}\colon X\times Y\to\mathbb{R}$ be a function for each
$i\in[k],j\in[\ell]$. Then

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{\ell}\in
Y\end{subarray}}\prod_{i\in[k],j\in[\ell]}f_{i\,j}(x_{i},y_{j})\Big{|}\leq\prod_{i\in[k],j\in[\ell]}\|f_{i\,j}\|_{\mathsf{U}_{k,\ell}}.$

In this paper, we need the following special case. Let
$f_{1},\dots,f_{r},g_{1},\dots,g_{r}\colon\mathbb{Z}/N\mathbb{Z}\times\mathbb{Z}/N\mathbb{Z}\to\mathbb{R}$.
For two subsets $B$ and $B^{\prime}$ of $\mathbb{Z}/N\mathbb{Z}$ (which will
be Bohr sets later), define the _vertical segments Gowers inner product_
$\langle
f_{1},\dots,f_{r},g_{1},\dots,g_{r}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}$ as

$\langle
f_{1},\dots,f_{r},g_{1},\dots,g_{r}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
a_{1},\dots,a_{r},s,s^{\prime}\in
B^{\prime}\end{subarray}}\prod_{i\in[r]}f_{i}(a_{i},y_{i}+s)g_{i}(a_{i},y_{i}+s^{\prime}).$

We also define _vertical segments norm_
$\|f\|_{\mathsf{VS}_{r}(B,B^{\prime})}=\langle
f,\dots,f\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}^{1/2r}$, where we put $2r$
copies of $f$ as arguments. The relationship with grid norms is the following.
Let $X=B^{\prime}\times B$ and $Y=B^{\prime}$. Given a function
$f\colon\mathbb{Z}/N\mathbb{Z}\times\mathbb{Z}/N\mathbb{Z}\to\mathbb{R}$,
consider the function $F\colon X\times Y\to\mathbb{R}$, given by
$F\Big{(}(x,y),z\Big{)}=f(x,y+z)$. Then
$\|f\|_{\mathsf{VS}_{r}(B,B^{\prime})}=\|F\|_{\mathsf{U}_{r,2}}$.
Owing to this connection, we know that vertical segments Gowers inner product
satisfies a suitable Gowers-Cauchy-Schwarz inequality. However, we need
slightly more control in our proof, so we record the intermediary steps in the
proof of such inequality as a separate proposition. We refer to these
inequalities as _Gowers-Hölder inequalities_ given that one uses Hölder’s
inequality instead of Cauchy-Schwarz inequality.

######  Proposition 2.8 (Gowers-Hölder inequality for the vertical segments
Gowers inner product).

Let $B,B^{\prime}\subseteq\mathbb{Z}/N\mathbb{Z}$ be sets. Let
$f_{1},\dots,f_{r},g_{1},\dots,g_{r}\colon\mathbb{Z}/N\mathbb{Z}\times\mathbb{Z}/N\mathbb{Z}\to\mathbb{R}$
be functions. Then

  * (i)

whenever $r$ is even,

$\Big{|}\langle
f_{1},\dots,f_{r},g_{1},\dots,g_{r}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}\Big{|}^{r}\leq\prod_{i\in[r]}\langle
f_{i},f_{i},\dots,f_{i},g_{i},g_{i},\dots,g_{i}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})},$

(where in the vertical segments Gowers inner products on the right-hand-side
we have $r$ copies of $f_{i}$, followed by $r$ copies of $g_{i}$),

  * (ii)

for all $r\in\mathbb{N}$,

$\Big{|}\langle
f_{1},\dots,f_{r},g_{1},\dots,g_{r}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}\Big{|}^{2}\leq\langle
f_{1},\dots,f_{r},f_{1},\dots,f_{r}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}\langle
g_{1},\dots,g_{r},g_{1},\dots,g_{r}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}.$

###### Proof.

Inequality (i). Recall that $r$ is even. Thus

$\Big{|}\langle
f_{1},\dots,f_{r},g_{1},\dots,g_{r}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}\Big{|}=\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s,s^{\prime}\in
B^{\prime}}\prod_{i\in[r]}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in B^{\prime},y\in
B}f_{i}(a,y+s)g_{i}(a,y+s^{\prime})\Big{)}\Big{|}.$

Let $F_{i}(s,s^{\prime})=\mathop{\mathbb{E}}_{a\in B^{\prime},y\in
B}f_{i}(a,y+s)g_{i}(a,y+s^{\prime})$. By generalized Hölder’s inequality, we
get

$\Big{|}\langle
f_{1},\dots,f_{r},g_{1},\dots,g_{r}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}\Big{|}=\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s,s^{\prime}\in
B^{\prime}}F_{1}(s,s^{\prime})\dots
F_{r}(s,s^{\prime})\Big{|}\leq\prod_{i\in[r]}\|F_{i}\|_{L^{r}(B^{\prime}\times
B^{\prime})}.$

Taking $r$th power, we get

$\|F_{i}\|_{L^{r}(B^{\prime}\times
B^{\prime})}^{r}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s,s^{\prime}\in
B^{\prime}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in B^{\prime},y\in
B}f_{i}(a,y+s)g_{i}(a,y+s^{\prime})\Big{|}^{r}=\langle
f_{i},f_{i},\dots,f_{i},g_{i},g_{i},\dots,g_{i}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})},$

using the fact that $r$ is even.
Inequality (ii). This time, we use Cauchy-Schwarz inequality

$\displaystyle\Big{|}\langle
f_{1},\dots,f_{r},g_{1},\dots,g_{r}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}\Big{|}^{2}=\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
a_{1},\dots,a_{r}\in
B^{\prime}\end{subarray}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s\in
B^{\prime}}\prod_{i\in[r]}f_{i}(a_{i},y_{i}+s)\Big{)}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s\in
B^{\prime}}\prod_{i\in[r]}g_{i}(a_{i},y_{i}+s)\Big{)}\Big{|}^{2}$
$\displaystyle\hskip
56.9055pt\leq\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
a_{1},\dots,a_{r}\in
B^{\prime}\end{subarray}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s\in
B^{\prime}}\prod_{i\in[r]}f_{i}(a_{i},y_{i}+s)\Big{|}^{2}\Big{)}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
a_{1},\dots,a_{r}\in
B^{\prime}\end{subarray}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s\in
B^{\prime}}\prod_{i\in[r]}g_{i}(a_{i},y_{i}+s)\Big{|}^{2}\Big{)}$
$\displaystyle\hskip 56.9055pt=\langle
f_{1},\dots,f_{r},f_{1},\dots,f_{r}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}\langle
g_{1},\dots,g_{r},g_{1},\dots,g_{r}\rangle_{\mathsf{VS}_{r}(B,B^{\prime})}.\qed$

In the analysis of various vertical segments Gowers inner products, we shall
also make use of the following inequality due to Kelley and Meka.

######  Lemma 2.9 (Kelley and Meka [14], Appendix D, proof of Proposition
5.7).

Let $r^{\prime}\geq r$ be positive integers and let $\varepsilon>0$. Then,
provided $r^{\prime}\geq 2\varepsilon^{-1}r$, we have

$\sum_{\begin{subarray}{c}d\text{ even}\\\ r\leq d\leq
r^{\prime}\end{subarray}}\binom{r^{\prime}}{d}\varepsilon^{d}\geq(1+\varepsilon/2)^{r^{\prime}}.$

## §3 Skew corner-free sets

Recall that structural hierarchy in the problem of finding skew corners had
the form $A\subseteq
X\times(t+B)\subseteq(s+B)\times(t+B)\subseteq\mathbb{Z}/N\mathbb{Z}\times\mathbb{Z}/N\mathbb{Z}$
for a Bohr set $B$.444In the introduction, we discussed the finite vector
space case so we had subgroups instead of Bohr sets. Our argument is based on
the density increment argument, where we increase the relative density of $A$
inside $X\times B$ at each step. This comes at the cost of slightly decreasing
the relative density of $X$ inside $s+B$ and decreasing the radius of $B$ and
increasing its rank somewhat. However, these costs are small enough to allow
us to obtain the Behrend-type final bounds. The following proposition
articulates the density increment step and is the essence of the argument.

######  Proposition 3.1.

There exists an absolute constant $C\geq 1$ for which the following holds. Let
$B\subseteq\mathbb{Z}/N\mathbb{Z}$ be a regular Bohr set of rank $d$ and
radius $\rho$ and let $X\subseteq B$ be a set of relative density $\delta$.
Let $A\subseteq X\times B$ be a set of relative density $\alpha$. Suppose that

$|B_{\mu_{0}}|\geq 9\alpha^{-2}\delta^{-2}$ (4)

for $\mu_{0}=\Big{(}\frac{\alpha\delta}{2d}\Big{)}^{C\log^{2}2\delta^{-1}}$.
Suppose that $A$ contains no non-trivial skew corners. Then there exist a
further regular Bohr set $B^{\prime}\subseteq B$ and a positive quantity

$d^{\prime}\leq C\log^{C}(2\alpha^{-1})\log^{C}(2\delta^{-1})$

such that $B^{\prime}$ has rank at most $d+d^{\prime}$ and radius at least
$\rho\exp(-d^{\prime})/d^{3}$ and for some translates $x_{0}+B^{\prime}$ and
$y_{0}+B^{\prime}$ we have

$|A\cap((X\cap(x_{0}+B^{\prime}))\times(y_{0}+B^{\prime}))|\geq(1+C^{-1})\alpha|X\cap(x_{0}+B^{\prime})|\,|y_{0}+B^{\prime}|$

and

$|X\cap(x_{0}+B^{\prime})|\geq\frac{1}{C}\alpha^{C}\delta|B^{\prime}|.$

Let us conclude the main result from the proposition above.

###### Proof of Theorem 1.1.

Let $A\subseteq[N]\times[N]$ be a set of density $\alpha$ without skew
corners. We need to pass to the cyclic group setting. Without loss of
generality, $3|N$. Consider $A\cap[iN/3,(i+1)N/3)\times[jN/3,(j+1)N/3)$ for
$i,j\in\\{0,1,2\\}$. There exists a choice of such a set $A^{\prime}$ which
has relative density at least $\frac{1}{9}\alpha$ inside $[N]\times[N]$.
Viewing $A^{\prime}$ as a subset of
$\mathbb{Z}/N\mathbb{Z}\times\mathbb{Z}/N\mathbb{Z}$ instead, $A^{\prime}$
remains a skew corner-free set.

Having passed to the $\mathbb{Z}/N\mathbb{Z}\times\mathbb{Z}/N\mathbb{Z}$
setting, we are ready to perform the density increment argument. Let $C$ be
the absolute constant in Proposition 3.1. At $i$th step of the iteration, we
shall have a regular Bohr set $B^{(i)}$ of rank $d_{i}$ and radius $\rho_{i}$
and a set $X^{(i)}\subseteq B^{(i)}$ of relative density $\delta_{i}$ such
that $A^{\prime}$ has relative density $(1+C^{-1})^{i}\alpha$ inside
$(x^{(i)}+X^{(i)})\times(y^{(i)}+B^{(i)})$ for some elements
$x^{(i)},y^{(i)}\in\mathbb{Z}/N\mathbb{Z}$. The following bounds will hold at
each step:

  * •

$\delta_{i}\geq\alpha^{Ci}C^{-i}$,

  * •

$d_{i}\leq C^{C+1}(i+1)^{C+1}\log^{2C}(2C\alpha^{-1})$,

  * •

$\rho_{i}\geq\frac{\exp\big{(}-C^{C+1}(i+1)^{C+1}\log^{2C}(2C\alpha^{-1})\big{)}}{\big{(}C^{C+1}(i+1)^{C+1}\log^{2C}(2C\alpha^{-1})\big{)}^{3i}}$.

Initially, we set $X^{(0)}=B^{(0)}=\mathbb{Z}/N\mathbb{Z}$,
$d_{0}=0,\rho_{0}=1,\delta_{0}=1$. At each step of procedure we apply
Proposition 3.1, as long as the relative density of $A^{\prime}$ inside the
relevant product is at most 1 and condition (4) holds. It is easy to see that
the claimed bounds on $\delta_{i},d_{i},\rho_{i}$ hold at each step. Owing to
density of $A^{\prime}$, the procedure terminates after at most $O(\log
2\alpha^{-1})$ steps, and since $A^{\prime}$ is skew corner-free, it must be
the case that condition (4) fails. Assume that $i$th step was the final one.
Lemma 2.2 implies the bound

$(\rho_{i}\mu/2\pi)^{d_{i}}N\leq 9\alpha_{i}^{-2}\delta_{i}^{-2},$ (5)

for $\mu=(\alpha_{i}\delta_{i}/2d_{i})^{C\log^{2}(2\delta_{i}^{-1})}$. The
bounds above allow us to find a $K=O(\log^{O(1)}(2\alpha^{-1}))$ such that

$\delta_{i}^{-1}\leq\exp(-K),\,\,d_{i}\leq K,\,\,\rho_{i}^{-1}\leq\exp(-K).$

These bounds, combined with (5), give

$N\leq\exp\Big{(}(2K)^{O(1)}\Big{)}\leq\exp\Big{(}O(\log^{O(1)}(2\alpha^{-1})\Big{)}$

completing the proof.∎

The remained of the paper is devoted to the proof of Proposition 3.1. Before
we begin, let us record here some of the various parameters that will play a
role in the proof. We shall use:

  * •

constants $c_{1}=2^{-13},c_{2}=2^{-14}$ and $c_{3}=2^{-12}$,

  * •

even positive integers $r$ and $r^{\prime}$, which are roughly $\log
2\delta^{-1}$,

  * •

parameters $\lambda,\mu,\nu$, used as dilate scales of the given Bohr set $B$,
which will satisfy

$\lambda\approx\Big{(}\frac{\alpha^{4}\delta}{32}\Big{)}^{r^{2}},\,\,\mu\approx\Big{(}\frac{\alpha^{4}\delta}{32}\Big{)}^{64r}\lambda,\,\,\nu\approx\Big{(}\frac{\alpha^{4}\delta}{8}\Big{)}^{r^{\prime}}\mu.$

We shall explain their roles during the proof, but we opted to mention them in
advance to help the reader with tracking the quantitative dependencies.

###### Proof of Proposition 3.1.

Step 1. Regularization of the set $A$. We first perform a simple
regularization step in which we ensure that all columns $\\{y\in
B\colon(x,y)\in A\\}$ of $A$ have roughly the same density in $B$ and also
that $X$ has no significant density increments in further Bohr subsets of $B$.
The latter property will be used at a few places in Step 2.

Fix $c_{1}=2^{-13}$. Let us partition $X=X_{1}\cup X_{2}\cup X_{3}$ into three
sets according to sizes of the columns indexed by their elements. Namely, let
$X_{1}$ consist of those $x\in X$ such that $|\\{y\in B\colon(x,y)\in
A\\}|\geq(1+c^{2}_{1})\alpha|B|$, let $X_{2}$ consist of those $x\in X$ such
that $|\\{y\in B\colon(x,y)\in
A\\}|\in[(1-c_{1})\alpha|B|,(1+c^{2}_{1})\alpha|B|)$, and let
$X_{3}=X\setminus(X_{1}\cup X_{2})$.
If it happens that $|X_{1}|\geq c^{2}_{1}\alpha|X|$, we may consider
$A\cap(X_{1}\times B)$, which now has relative density at least
$(1+c_{1}^{2})\alpha$ inside $X_{1}\times B$, completing the proof.
Now assume the contrary. We then have

$\displaystyle\sum_{x\in X_{2}}|\\{y\in B\colon(x,y)\in A\\}|+\sum_{x\in
X_{3}}|\\{y\in B\colon(x,y)\in A\\}|$ $\displaystyle\hskip
56.9055pt\geq\alpha|X||B|-\sum_{x_{1}\in X}|\\{y\in B\colon(x,y)\in
A\\}|\geq\alpha|X||B|-c^{2}_{1}\alpha|X||B|.$

Subtract $(1-c_{1})\alpha|X_{2}\cup X_{3}||B|$ from both sides to obtain

$\displaystyle\sum_{x\in X_{2}}\Big{(}|\\{y\in B\colon(x,y)\in
A\\}|-(1-c_{1})\alpha|B|\Big{)}+\sum_{x\in X_{3}}\Big{(}|\\{y\in
B\colon(x,y)\in A\\}|-(1-c_{1})\alpha|B|\Big{)}$ $\displaystyle\hskip
56.9055pt\geq(1-c_{1}^{2})\alpha|X||B|-(1-c_{1})\alpha|X_{2}\cup X_{3}||B|$
$\displaystyle\hskip
56.9055pt\geq(1-c_{1}^{2})\alpha|X||B|-(1-c_{1})\alpha|X||B|\,\,=\,\,(c_{1}-c_{1}^{2})\alpha|X||B|.$

However, the value of $|\\{y\in B\colon(x,y)\in A\\}|-(1-c_{1})\alpha|B|$ is
at most $(c_{1}+c_{1}^{2})\alpha|B|$ when $x\in X_{2}$ and at most $0$ when
$x\in X_{3}$, from which we deduce
$(c_{1}+c_{1}^{2})\alpha|B||X_{2}|\geq(c_{1}-c_{1}^{2})\alpha|X||B|$, implying
that $|X_{2}|\geq\frac{c_{1}-c_{1}^{2}}{c_{1}+c_{1}^{2}}|X|$. In particular,
$X_{2}$ has relative density at least $\delta/2$ inside $B$.

Let $c_{2}=2^{-14}$,

$r=2\lceil\log_{2}(2\delta^{-1})\rceil+2^{30}$ (6)

(note that $r$ is an even integer) and

$\kappa=\frac{1}{2^{20}r^{2}d}\Big{(}\frac{\alpha^{4}\delta}{32}\Big{)}^{64r}.$

Next, we pass to a translate of a dilate of $B$ on which $X_{2}$ has no
density increments by a factor of $1+c_{2}$ with respect to further translates
of dilates scaled by a factor of at most $\kappa$. Set initially $t_{0}=0$ and
$\lambda_{0}=1$. Assume that at $i$th step we have translate of a dilate
$t_{i}+B_{\lambda_{i}}$ such that $B_{\lambda_{i}}$ is regular,
$\lambda_{i}\geq\kappa^{i}$ and
$|X_{2}\cap(t_{i}+B_{\lambda_{i}})|\geq(1+c_{2})^{i}|X_{2}|/|B|$. Either this
translate of a dilate satisfies the required conditions, or we may find
further translate of a dilate $t_{i+1}+B_{\lambda_{i+1}}$ such that
$B_{\lambda_{i+1}}$ is regular and

$\frac{|X_{2}\cap(t_{i+1}+B_{\lambda_{i+1}})|}{|B_{\lambda_{i+1}}|}\geq(1+c_{2})\frac{|X_{2}\cap(t_{i}+B_{\lambda_{i}})|}{|B_{\lambda_{i}}|}.$

This procedure terminates after at most $O(\log 2\delta^{-1})$ steps,
producing desired translate of a dilate $t+B_{\lambda}$. Hence,
$\lambda\geq\kappa^{O(\log 2\delta^{-1})}$ and, as we the relative density of
$X_{2}$ increases at each step, we may assume that $X_{2}\cap(t+B_{\lambda})$
has relative density $\delta^{\prime}\geq\frac{\delta}{2}$ inside
$t+B_{\lambda}$. Finally, the relative density inside any $t^{\prime}+B_{\mu}$
is at most $(1+c_{2})\delta^{\prime}$ for any $t^{\prime}$ and
$\mu\geq\kappa\lambda$, provided $B_{\mu}$ is regular.

We may shift $A$ by $(-t,0)$, allowing us to assume without loss of generality
that $t=0$. Let us now misuse the notation and write $X$ for the intersection
$X_{2}\cap B_{\lambda}$, use $\delta$ for density of $X$ relative to
$B_{\lambda}$, which does not affect the form of the final bounds. Hence, we
have $A\subseteq X\times B\subseteq B_{\lambda}\times B$.

Step 2. Finding imbalance in $A$. The goal of this step is to show that $A$ is
not quasirandom. Formally, we show that the vertical segments norm of the
(suitably defined) balanced function of $A$ is large. Namely, let us write
$\alpha_{\textnormal{vert}}(x)=\mathop{\mathbb{E}}_{y\in
B}\mathbbm{1}_{A}(x,y)$, which is the relative density of the column of $A$
with coordinate $x$ inside $B$ (and is 0 whenever $x\notin X$), and let us
define the _balanced function_ of $A$ as
$\mathsf{b}(x,y)=\mathbbm{1}_{A}(x,y)-\alpha_{\textnormal{vert}}(x)$. Let us
note obvious bounds $\|\alpha_{\textnormal{vert}}\|_{\infty}\leq 1$, since
$\alpha_{\textnormal{vert}}(x)$ is average of an indicator function, and
$\|\mathsf{b}\|_{\infty}\leq 1$, since $\mathsf{b}(x,y)=1$ or
$\mathsf{b}(x,y)=1-a$ for some $a\in[0,1]$.
Before exploiting the lack of skew corners, we first need to show some basic
bounds concerning simpler configurations. Let
$\mu\in[\kappa\lambda,2\kappa\lambda]$ be a parameter such that $B_{\mu}$ is
regular.

######  Claim 3.2.

We have

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda}\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\alpha_{\textnormal{vert}}(x+a)^{2}\leq\frac{10}{9}\alpha^{2}\delta^{2}$

and

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{A}(x+a,y+s)\alpha_{\textnormal{vert}}(x+a)\geq$
$\displaystyle\frac{8}{9}\alpha^{2}\delta^{2}$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{A}(x+a,y+a+t)\alpha_{\textnormal{vert}}(x+a)\geq$
$\displaystyle\frac{8}{9}\alpha^{2}\delta^{2}.$

###### Proof.

To obtain the first bound, observe that
$\alpha_{\textnormal{vert}}(x)\leq(1+c_{1}^{2})\alpha\mathbbm{1}_{X}(x)$ for
all $x$, so we have

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda}\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\alpha_{\textnormal{vert}}(x+a)^{2}\leq(1+c_{1}^{2})^{2}\alpha^{2}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda}\\\
a,s,t\in B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{X}(x+a).$

Furthermore, we know that $\mathop{\mathbb{E}}_{a\in
B_{\mu}}\mathbbm{1}_{X}(x+a)\leq(1+c_{2})\delta\leq\frac{101}{100}\delta$ for
all $x$, as otherwise $X$ has a significant density increment on translate of
$B_{\mu}$. On the other hand, since $\mu\leq\frac{\delta}{2^{15}d}\lambda$,
the change of variables lemma (Lemma 2.4) for transformation $x\mapsto x+s-t$
implies that

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda}\\\ s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda}\\\ s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x)\Big{|}\leq
100d\frac{\mu}{\lambda}\leq\frac{1}{100}\delta$

and we know that $\mathop{\mathbb{E}}_{\begin{subarray}{c}x\in B_{\lambda}\\\
s,t\in B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x)=\delta$. The bound follows
from these estimates.
When it comes to the second bound, the change of variables lemma (Lemma 2.4)
for transformations $y\mapsto y+s$ and for $y\mapsto y+a+t$, implies that

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{A}(x+a,y+s)\alpha_{\textnormal{vert}}(x+a)-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{A}(x+a,y)\alpha_{\textnormal{vert}}(x+a)\Big{|}\leq
50d\mu$ (7)

and

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{A}(x+a,y+a+t)\alpha_{\textnormal{vert}}(x+a)-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{A}(x+a,y)\alpha_{\textnormal{vert}}(x+a)\Big{|}\leq
100d\mu.$ (8)

On the other hand,

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{A}(x+a,y)\alpha_{\textnormal{vert}}(x+a)=$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda}\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\alpha_{\textnormal{vert}}(x+a)^{2}$
$\displaystyle\geq$
$\displaystyle(1-c_{1})^{2}\alpha^{2}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda}\\\
a,s,t\in B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{X}(x+a).$
(9)

Recalling that $X$ has no significant density increments on translates of
$B_{\mu}$, we get bounds

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{x\in
B_{\lambda}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s,t\in
B_{\mu}}\mathbbm{1}_{X}(x+s-t)\Big{|}^{2}\leq\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
B_{\lambda}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s\in
B_{\mu}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{t\in
B_{\mu}}\mathbbm{1}_{X}(x+s-t)\Big{)}\Big{|}^{2}\leq(1+c_{2})^{2}\delta^{2}$

and $\mathop{\mathbb{E}}_{a\in
B_{\mu}}\mathbbm{1}_{X}(x+a)\leq(1+c_{2})\delta$. By the change of variables
lemma (Lemma 2.4) for transformation $x\mapsto x+a$, we have

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in B_{\lambda},a\in
B_{\mu}}\mathbbm{1}_{X}(x+a)-\delta\Big{|}\leq 50d\frac{\mu}{\lambda}.$

Hence,

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
B_{\lambda}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in
B_{\mu}}\mathbbm{1}_{X}(x+a)-\delta\Big{|}^{2}=$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda}\\\
a,a^{\prime}\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+a)\mathbbm{1}_{X}(x+a^{\prime})-2\delta\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda}\\\
a,a^{\prime}\in B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+a)+\delta^{2}$
$\displaystyle\leq$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in B_{\lambda},a\in
B_{\mu}}\mathbbm{1}_{X}(x+a)\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a^{\prime}\in
B_{\mu}}\mathbbm{1}_{X}(x+a^{\prime})\Big{)}-\delta^{2}+100d\frac{\mu}{\lambda}$
$\displaystyle\leq$
$\displaystyle(1+c_{2})\delta\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in B_{\lambda},a\in
B_{\mu}}\mathbbm{1}_{X}(x+a)-\delta^{2}+100d\frac{\mu}{\lambda}$
$\displaystyle\leq$ $\displaystyle c_{2}\delta^{2}+200d\frac{\mu}{\lambda}\leq
2c_{2}\delta^{2},$

using $\mu\leq c_{2}\delta^{2}\lambda/(200d)$. By triangle and Cauchy-Schwarz
inequalities, we get

$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda}\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{X}(x+a)-\delta^{2}\Big{|}\leq\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
B_{\lambda}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s,t\in
B_{\mu}}\mathbbm{1}_{X}(x+s-t)\Big{)}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in
B_{\mu}}\mathbbm{1}_{X}(x+a)-\delta\Big{)}\Big{|}$ $\displaystyle\hskip
227.62204pt+\delta\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in B_{\lambda},s,t\in
B_{\mu}}\mathbbm{1}_{X}(x+s-t)-\delta\Big{|}$ $\displaystyle\hskip
56.9055pt\leq\sqrt{\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
B_{\lambda}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s,t\in
B_{\mu}}\mathbbm{1}_{X}(x+s-t)\Big{|}^{2}}\sqrt{\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
B_{\lambda}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in
B_{\mu}}\mathbbm{1}_{X}(x+a)-\delta\Big{|}^{2}}+100d\frac{\mu}{\lambda}\leq
3\sqrt{c_{2}}\delta^{2}.$

Returning to (9), we deduce that

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{A}(x+a,y)\alpha_{\textnormal{vert}}(x+a)\geq(1-c_{1})^{2}(1-3\sqrt{c_{2}})\alpha^{2}\delta^{2}\geq\frac{19}{20}\alpha^{2}\delta^{2}.$

Since $\mu\leq\frac{\alpha^{2}\delta^{2}}{2000d}$, the claim follows from
inequalities (7) and (8).∎

Since there are no non-trivial skew corners in $A$, using a slightly
artificial parametrization (in order to reduce the number of changes of
variables) of skew corners $(x+s-t,y^{\prime}),(x+a,y+s),(x+a,y+a+t)$, we have

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{A}(x+a,y+s)\mathbbm{1}_{A}(x+a,y+a+t)=$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in B_{\mu}\end{subarray}}\mathbbm{1}_{A}(x+a,y+s)\mathbbm{1}(a+t-s=0)$
$\displaystyle\hskip
56.9055pt\leq\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a,s,t\in
B_{\mu}}\mathbbm{1}(a+t=s)\leq\frac{1}{|B_{\mu}|}.$

Using Claim 3.2, as long as $|B_{\mu}|\geq 9\alpha^{-2}\delta^{-2}$, we get

$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathsf{b}(x+a,y+s)\mathsf{b}(x+a,y+a+t)\Big{|}$
$\displaystyle=$
$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{A}(x+a,y+s)\mathbbm{1}_{A}(x+a,y+a+t)$
$\displaystyle\hskip
56.9055pt-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\mathbbm{1}_{A}(x+a,y+s)\alpha_{\textnormal{vert}}(x+a)$
$\displaystyle\hskip
56.9055pt-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\alpha_{\textnormal{vert}}(x+a)\mathbbm{1}_{A}(x+a,y+a+t)$
$\displaystyle\hskip
56.9055pt+\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda},y\in B\\\
a,s,t\in
B_{\mu}\end{subarray}}\mathbbm{1}_{X}(x+s-t)\alpha_{\textnormal{vert}}(x+a)^{2}\Big{|}$
$\displaystyle\geq$ $\displaystyle\frac{1}{2}\alpha^{2}\delta^{2}.$

Recall that $r=2\lceil\log_{2}(2\delta^{-1})\rceil+2^{30}$, defined in (6), is
an even positive integer. Let $\chi\colon B_{\lambda}\times B_{\mu}\times
B_{\mu}\to\mathbb{R}$ be given by $\chi(x,s,t)=\mathbbm{1}_{X}(x+s-t)$.
Hölder’s inequality for norms $L^{r/(r-1)}$ and $L^{r}$ on $B_{\lambda}\times
B_{\mu}\times B_{\mu}$ gives

$\frac{1}{2}\alpha^{2}\delta^{2}\leq\Big{\|}\chi\Big{\|}_{L^{\frac{r}{r-1}}(B_{\lambda}\times
B_{\mu}\times
B_{\mu})}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x\in B_{\lambda}\\\ s,t\in
B_{\mu}\end{subarray}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B,a\in
B_{\mu}}\mathsf{b}(x+a,y+s)\mathsf{b}(x+a,y+a+t)\Big{|}^{r}\Big{)}^{1/r}.$

Log-convexity of $L^{p}$ norms implies
$\|\chi\|_{L^{\frac{r}{r-1}}}\leq\|\chi\|_{L^{1}}\Big{(}\frac{\|\chi\|_{L^{2}}}{\|\chi\|_{L^{1}}}\Big{)}^{\frac{2}{r}}$.
Furthermore, since $\mathbbm{1}_{X}$ only takes values 0 and 1, we have
$\|\chi\|_{L^{2}}=\|\chi\|_{L^{1}}^{1/2}$. Additionally, change of variables
lemma (Lemma 2.4) gives $\delta/2\leq\|\chi\|_{L^{1}}\leq 2\delta$, since
$\mu\leq\frac{\delta}{200d}\lambda$. These facts together imply
$\|\chi\|_{L^{\frac{r}{r-1}}}\leq 4\delta$, since
$r\geq\log_{2}(2\delta^{-1})$. After expanding, using the fact that $r$ is
even, we obtain

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{x\in
B_{\lambda}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
s,t,a_{1},\dots,a_{r}\in
B_{\mu}\end{subarray}}\prod_{i\in[r]}\mathsf{b}(x+a_{i},y_{i}+s)\prod_{i\in[r]}\mathsf{b}(x+a_{i},y_{i}+a_{i}+t)\Big{)}\geq\Big{(}\frac{\alpha^{2}\delta}{8}\Big{)}^{r}.$

By averaging, there is $x_{0}\in B_{\lambda}$ such that

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
s,t,a_{1},\dots,a_{r}\in
B_{\mu}\end{subarray}}\prod_{i\in[r]}\mathsf{b}(x_{0}+a_{i},y_{i}+s)\prod_{i\in[r]}\mathsf{b}(x_{0}+a_{i},y_{i}+a_{i}+t)\geq\Big{(}\frac{\alpha^{2}\delta}{8}\Big{)}^{r}.$
(10)

However, the long expression equals

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{s,t\in
B_{\mu}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B,a\in
B_{\mu}}\mathsf{b}(x_{0}+a,y+s)\mathsf{b}(x_{0}+a,y+a+t)\Big{|}^{r}$

so by averaging, there are $s_{0},t_{0}\in B_{\mu}$ such that

$\frac{\alpha^{2}\delta}{8}\leq\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B,a\in
B_{\mu}}\mathsf{b}(x_{0}+a,y+s_{0})\mathsf{b}(x_{0}+a,y+a+t_{0})\Big{|}\leq\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu}}\mathbbm{1}_{X}(x_{0}+a)$

so $|X\cap(x_{0}+B_{\mu})|\geq\frac{\alpha^{2}\delta}{8}|B_{\mu}|$. Let us
write $\delta_{\mu}=\frac{|X\cap(x_{0}+B_{\mu})|}{|B_{\mu}|}$, which is the
relative density of $X$ inside $x_{0}+B_{\mu}$. Recalling that $X$ has no
significant density increments on translates of $B_{\mu}$, we have thus
obtained

$\frac{\alpha^{2}\delta}{8}\leq\delta_{\mu}\leq(1+c_{2})\delta.$ (11)

Applying Cauchy-Schwarz inequality in (10), we get

$\displaystyle\Big{(}\frac{\alpha^{2}\delta}{8}\Big{)}^{2r}\leq$
$\displaystyle\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
a_{1},\dots,a_{r}\in
B_{\mu}\end{subarray}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s\in
B_{\mu}}\prod_{i\in[r]}\mathsf{b}(x_{0}+a_{i},y_{i}+s)\Big{)}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{t\in
B_{\mu}}\prod_{i\in[r]}\mathsf{b}(x_{0}+a_{i},y_{i}+a_{i}+t)\Big{)}\bigg{|}^{2}$
$\displaystyle\leq$
$\displaystyle\bigg{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
a_{1},\dots,a_{r}\in
B_{\mu}\end{subarray}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s\in
B_{\mu}}\prod_{i\in[r]}\mathsf{b}(x_{0}+a_{i},y_{i}+s)\Big{|}^{2}\bigg{)}$
$\displaystyle\hskip
142.26378pt\bigg{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
a_{1},\dots,a_{r}\in
B_{\mu}\end{subarray}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{t\in
B_{\mu}}\prod_{i\in[r]}\mathsf{b}(x_{0}+a_{i},y_{i}+a_{i}+t)\Big{|}^{2}\bigg{)}.$
(12)

It follows from the change of variables lemma (Lemma 2.4) for transformation
$y_{i}\mapsto y_{i}+a_{i}$, $i\in[r]$, that

$\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
a_{1},\dots,a_{r}\in
B_{\mu}\end{subarray}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{t\in
B_{\mu}}\prod_{i\in[r]}\mathsf{b}(x_{0}+a_{i},y_{i}+a_{i}+t)\Big{|}^{2}-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
a_{1},\dots,a_{r}\in
B_{\mu}\end{subarray}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{t\in
B_{\mu}}\prod_{i\in[r]}\mathsf{b}(x_{0}+a_{i},y_{i}+t)\Big{|}^{2}\bigg{|}\leq
50\mu r^{2}d.$ (13)

Combining inequalities (12) and (13), we obtain

$\Big{(}\frac{\alpha^{2}\delta}{16}\Big{)}^{r}\leq\Big{(}\frac{\alpha^{2}\delta}{8}\Big{)}^{r}-50\mu
r^{2}d\leq\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r}\in B\\\
a_{1},\dots,a_{r},s,s^{\prime}\in
B_{\mu}\end{subarray}}\prod_{i\in[r]}\mathsf{b}(x_{0}+a_{i},y_{i}+s)\mathsf{b}(x_{0}+a_{i},y_{i}+s^{\prime})=\|T_{(x_{0},0)}\mathsf{b}\|_{\mathsf{VS}_{r}(B,B_{\mu})}^{2r},$
(14)

where $T_{(x_{0},0)}\mathsf{b}$ stands for the function
$(x,y)\mapsto\mathsf{b}(x_{0}+x,y)$, (i.e. the translation operator applied to
$\mathsf{b}$), as
$\mu\leq\frac{1}{100r^{2}d}\Big{(}\frac{\alpha^{2}\delta}{8}\Big{)}^{r}$.

Step 3. Passing from $\mathsf{b}$ to $\mathbbm{1}_{A}$. In this step, we start
from the fact that
$\|T_{(x_{0},0)}\mathsf{b}\|_{\mathsf{VS}_{r}(B,B_{\mu})}\geq\Omega(\alpha\sqrt{\delta})$,
and we aim to prove
$\|T_{(x_{0},0)}\mathbbm{1}_{A}\|_{\mathsf{VS}_{r^{\prime}}(B,B_{\mu})}\geq(1+\Omega(1))\alpha\sqrt{\delta}$
where $r^{\prime}=64r$. Consider the vertical segments Gowers inner product

$\langle
f_{1},\dots,f_{r^{\prime}},g_{1},\dots,g_{r^{\prime}}\rangle_{\mathsf{VS}_{r^{\prime}}(B,B_{\mu})}$

where each $f_{i}$ and $g_{i}$ are either $(x,y)\mapsto\mathsf{b}(x_{0}+x,y)$
or $(x,y)\mapsto\alpha_{\textnormal{vert}}(x_{0}+x)$. Using Gowers-Hölder’s
inequality (Lemma 2.8 (i)), we get

$\langle
f_{1},\dots,f_{r^{\prime}},g_{1},\dots,g_{r^{\prime}}\rangle_{\mathsf{VS}_{r^{\prime}}(B,B_{\mu})}^{r^{\prime}}\leq\prod_{i\in[r^{\prime}]}\langle
f_{i},\dots,f_{i},g_{i},\dots,g_{i}\rangle_{\mathsf{VS}_{r}(B,B_{\mu})}.$ (15)

Suppose that for some $i$ we have $f_{i}$ and $g_{i}$ different, so without
loss of generality $f_{i}(x,y)=\mathsf{b}(x_{0}+x,y)$ and
$g_{i}(x,y)=\alpha_{\textnormal{vert}}(x_{0}+x)$. Then

$\langle
f_{i},\dots,f_{i},g_{i},\dots,g_{i}\rangle_{\mathsf{VS}_{r^{\prime}}(B,B_{\mu})}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s,s^{\prime}\in
B_{\mu}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in
B_{\mu}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in
B}\mathsf{b}(x_{0}+a,y+s)\Big{)}\alpha_{\textnormal{vert}}(x_{0}+a)\Big{)}^{r^{\prime}}.$

However, by regularity of $B$, for each $s\in B_{\mu}$ we have

$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B}\mathsf{b}(x_{0}+a,y+s)\Big{|}=$
$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in
B}\mathbbm{1}_{A}(x_{0}+a,y+s)-\alpha_{\textnormal{vert}}(x_{0}+a)\Big{|}$
$\displaystyle=$
$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in
B}\mathbbm{1}_{A}(x_{0}+a,y+s)-\mathbbm{1}_{A}(x_{0}+a,y)\Big{|}\leq|B\Delta
s+B|/|B|\leq 24d\mu,$

which, together with (15) and bounds
$\|\mathsf{b}\|_{\infty},\|\alpha_{\textnormal{vert}}\|_{\infty}\leq 1$,
implies that

$\langle
f_{1},\dots,f_{r^{\prime}},g_{1},\dots,g_{r^{\prime}}\rangle_{\mathsf{VS}_{r^{\prime}}(B,B_{\mu})}\leq
24d\mu.$

We now turn to the case when $f_{i}=g_{i}$ holds for all $i\in[r^{\prime}]$.
In that case, we always have

$\langle
f_{1},\dots,f_{r^{\prime}},f_{1},\dots,f_{r^{\prime}}\rangle_{\mathsf{VS}_{r^{\prime}}(B,B_{\mu})}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r^{\prime}}\in
B\\\ a_{1},\dots,a_{r^{\prime}}\in
B_{\mu}\end{subarray}}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s\in
B_{\mu}}\prod_{i\in[r^{\prime}]}f_{i}(x_{0}+a_{i},y_{i}+s)\Big{|}^{2}\geq 0.$

We need additional estimates, so let us write

$\displaystyle\Pi_{k}=\langle\underbrace{T_{(x_{0},0)}\mathsf{b},\dots,T_{(x_{0},0)}\mathsf{b}}_{k},$
$\displaystyle\underbrace{T_{(x_{0},0)}\alpha_{\textnormal{vert}},\dots,T_{(x_{0},0)}\alpha_{\textnormal{vert}}}_{r^{\prime}-k},$
$\displaystyle\hskip
28.45274pt\underbrace{T_{(x_{0},0)}\mathsf{b},\dots,T_{(x_{0},0)}\mathsf{b}}_{k},\underbrace{T_{(x_{0},0)}\alpha_{\textnormal{vert}},\dots,T_{(x_{0},0)}\alpha_{\textnormal{vert}}}_{r^{\prime}-k}\rangle_{\mathsf{VS}_{r^{\prime}}(B,B_{\mu})},$

which is the vertical segments Gowers inner product for $k$ pairs of
$T_{(x_{0},0)}\mathsf{b}$ terms and $r^{\prime}-k$ pairs of
$T_{(x_{0},0)}\alpha_{\textnormal{vert}}$ terms. We showed above that
$\Pi_{k}\geq 0$ for all $k$.

Assume that $k$ is even and that $k\geq r$. Note that

$\displaystyle\Pi_{k}=$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s,s^{\prime}\in
B_{\mu}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B,a\in
B_{\mu}}\mathsf{b}(x_{0}+a,y+s)\mathsf{b}(x_{0}+a,y+s^{\prime})\Big{)}^{k}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in
B_{\mu}}\alpha_{\textnormal{vert}}(x_{0}+a)^{2}\Big{)}^{r^{\prime}-k}$
$\displaystyle\geq$
$\displaystyle(1-c_{1})^{2r^{\prime}-2k}\alpha^{2r^{\prime}-2k}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s,s^{\prime}\in
B_{\mu}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B,a\in
B_{\mu}}\mathsf{b}(x_{0}+a,y+s)\mathsf{b}(x_{0}+a,y+s^{\prime})\Big{)}^{k}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in
B_{\mu}}\mathbbm{1}_{X}(x_{0}+a)\Big{)}^{r^{\prime}-k}$

as
$\alpha_{\textnormal{vert}}(x_{0}+a)\geq(1-c_{1})\alpha\mathbbm{1}_{X}(x_{0}+a)$
for all $a$. Recalling that $\delta_{\mu}=\mathop{\mathbb{E}}_{a\in
B_{\mu}}\mathbbm{1}_{X}(x_{0}+a)$, this further equals

$(1-c_{1})^{2r^{\prime}-2k}\alpha^{2r^{\prime}-2k}\delta_{\mu}^{r^{\prime}-k}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s,s^{\prime}\in
B_{\mu}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B,a\in
B_{\mu}}\mathsf{b}(x_{0}+a,y+s)\mathsf{b}(x_{0}+a,y+s^{\prime})\Big{)}^{k}.$

By the monotonicity of $L^{p}$ norms, this expression is at least

$(1-c_{1})^{2r^{\prime}-2k}\alpha^{2r^{\prime}-2k}\delta_{\mu}^{r^{\prime}-k}\bigg{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s,s^{\prime}\in
B_{\mu}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B,a\in
B_{\mu}}\mathsf{b}(x_{0}+a,y+s)\mathsf{b}(x_{0}+a,y+s^{\prime})\Big{)}^{r}\bigg{)}^{k/r}.$

By inequality (14), we get a further lower bound

$(1-c_{1})^{2r^{\prime}-2k}\alpha^{2r^{\prime}-2k}\delta_{\mu}^{r^{\prime}-k}\Big{(}\frac{\alpha^{2}\delta}{16}\Big{)}^{k}$

which, using (11), is at least

$(1-c_{1})^{2r^{\prime}-2k}\alpha^{2r^{\prime}-2k}\delta_{\mu}^{r^{\prime}-k}\frac{1}{(1+c_{2})^{k}}\Big{(}\frac{\alpha^{2}\delta_{\mu}}{16}\Big{)}^{k}.$

Since $(1-c_{1})^{2}/(1+c_{2})\geq 1/2$, we finally get

$\Pi_{k}\geq\Big{(}\frac{1}{32}\Big{)}^{k}(1-c_{1})^{2r^{\prime}}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}.$

Expanding out

$\|T_{(x_{0},0)}\mathbbm{1}_{A}\|^{2r^{\prime}}_{\mathsf{VS}_{r^{\prime}}(B,B_{\mu})}=\langle
T_{(x_{0},0)}\mathsf{b}_{A}+T_{(x_{0},0)}\alpha_{\textnormal{vert}},\dots,T_{(x_{0},0)}\mathsf{b}_{A}+T_{(x_{0},0)}\alpha_{\textnormal{vert}}\rangle_{\mathsf{VS}_{r^{\prime}}(B,B_{\mu})},$

which results in $4^{r^{\prime}}$ terms, and putting all the above information
on vertical segments Gowers inner products together, we obtain

$\displaystyle\|T_{(x_{0},0)}\mathbbm{1}_{A}\|^{2r^{\prime}}_{\mathsf{VS}_{r^{\prime}}(B,B_{\mu})}\geq$
$\displaystyle\sum_{k=0}^{r^{\prime}}\binom{r^{\prime}}{k}\Pi_{k}\,\,-\,\,4^{r^{\prime}}\cdot
24d\mu$ $\displaystyle\geq$ $\displaystyle\sum_{\begin{subarray}{c}k\text{
even}\\\ r\leq k\leq
r^{\prime}\end{subarray}}\binom{r^{\prime}}{k}\Pi_{k}\,\,-\,\,4^{r^{\prime}}\cdot
24d\mu$ $\displaystyle\geq$
$\displaystyle(1-c_{1})^{2r^{\prime}}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}\sum_{\begin{subarray}{c}k\text{
even}\\\ r\leq k\leq
r^{\prime}\end{subarray}}\binom{r^{\prime}}{k}32^{-k}\,\,-\,\,4^{r^{\prime}}\cdot
24d\mu$ $\displaystyle\geq$
$\displaystyle(1-c_{1})^{2r^{\prime}}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}\Big{(}1+\frac{1}{64}\Big{)}^{r^{\prime}}\,\,-\,\,4^{r^{\prime}}\cdot
24d\mu$ $\displaystyle\geq$
$\displaystyle\Big{(}1+\frac{1}{256}\Big{)}^{r^{\prime}}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}},$

where we used Lemma 2.9 in the penultimate step and inequalities $c_{1}\leq
2^{-9}$ and
$\mu\leq\frac{1}{2^{20}d}\Big{(}\frac{\alpha^{4}\delta}{32}\Big{)}^{r^{\prime}}$
in the last one.

Step 4. Sifting. Expanding out
$\|T_{(x_{0},0)}\mathbbm{1}_{A}\|^{2r^{\prime}}_{\mathsf{VS}_{r^{\prime}}(B,B_{\mu})}\geq\Big{(}1+\frac{1}{256}\Big{)}^{r^{\prime}}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}$
we obtain

$\Big{(}1+\frac{1}{256}\Big{)}^{r^{\prime}}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}\leq\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}y_{1},\dots,y_{r^{\prime}}\in
B\\\ a_{1},\dots,a_{r^{\prime}},s,s^{\prime}\in
B_{\mu}\end{subarray}}\prod_{i\in[r^{\prime}]}\mathbbm{1}_{A}(x_{0}+a_{i},y_{i}+s)\mathbbm{1}_{A}(x_{0}+a_{i},y_{i}+s^{\prime}).$

Let us rename the variables $y_{i}$ to $t_{i}$, $s$ to $y$ and $s^{\prime}$ to
$y^{\prime}$. The expression above becomes

$\Big{(}1+\frac{1}{256}\Big{)}^{r^{\prime}}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}\leq\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}t_{1},\dots,t_{r^{\prime}}\in
B\\\ a_{1},\dots,a_{r^{\prime}},y,y^{\prime}\in
B_{\mu}\end{subarray}}\prod_{i\in[r^{\prime}]}\mathbbm{1}_{A}(x_{0}+a_{i},t_{i}+y)\mathbbm{1}_{A}(x_{0}+a_{i},t_{i}+y^{\prime}).$

We may average of $y^{\prime}\in B_{\mu}$ to find some $y^{\prime}_{0}$ for
which

$\Big{(}1+\frac{1}{256}\Big{)}^{r^{\prime}}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}\leq\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}t_{1},\dots,t_{r^{\prime}}\in
B\\\ a_{1},\dots,a_{r^{\prime}},y\in
B_{\mu}\end{subarray}}\prod_{i\in[r^{\prime}]}\mathbbm{1}_{A}(x_{0}+a_{i},t_{i}+y)\mathbbm{1}_{A}(x_{0}+a_{i},y^{\prime}_{0}+t_{i}).$

Consider the set $D=\\{y\in B_{\mu}\colon\mathop{\mathbb{E}}_{a\in
B_{\mu},t\in
B}\mathbbm{1}_{A}(x_{0}+a,t+y)\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+t)\geq(1+1/512)\alpha^{2}\delta_{\mu}\\}$.
Let $c_{3}=2^{-12}$. Then

$\displaystyle\sum_{y\in
D}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},t\in
B}\mathbbm{1}_{A}(x_{0}+a,t+y)\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+t)\Big{)}^{r^{\prime}}$
$\displaystyle\hskip 113.81102pt-(1-c_{3})\sum_{y\in
B_{\mu}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},t\in
B}\mathbbm{1}_{A}(x_{0}+a,t+y)\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+t)\Big{)}^{r^{\prime}}$
$\displaystyle\geq c_{3}\sum_{y\in
B_{\mu}}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},t\in
B}\mathbbm{1}_{A}(x_{0}+a,t+y)\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+t)\Big{)}^{r^{\prime}}$
$\displaystyle\hskip 113.81102pt-\sum_{y\in B_{\mu}\setminus
D}\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},t\in
B}\mathbbm{1}_{A}(x_{0}+a,t+y)\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+t)\Big{)}^{r^{\prime}}$
$\displaystyle\geq
c_{3}\Big{(}1+\frac{1}{256}\Big{)}^{r^{\prime}}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}|B_{\mu}|-\Big{(}1+\frac{1}{512}\Big{)}^{r^{\prime}}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}|B_{\mu}|$
$\displaystyle\geq\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}|B_{\mu}|,$

since $r^{\prime}\geq 2^{10}c_{3}^{-1}$.
Upon expanding, we get

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}a_{1},\dots,a_{r^{\prime}}\in
B_{\mu}\\\ t_{1},\dots,t_{r^{\prime}}\in B,y\in
B_{\mu}\end{subarray}}\mathbbm{1}_{D}(y)\prod_{i\in[r^{\prime}]}\mathbbm{1}_{A}(x_{0}+a_{i},t_{i}+y)\mathbbm{1}_{A}(x_{0}+a_{i},y^{\prime}_{0}+t_{i})$
$\displaystyle\hskip
56.9055pt\geq(1-c_{3})\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}a_{1},\dots,a_{r^{\prime}}\in
B_{\mu}\\\ t_{1},\dots,t_{r^{\prime}}\in B,y\in
B_{\mu}\end{subarray}}\prod_{i\in[r^{\prime}]}\mathbbm{1}_{A}(x_{0}+a_{i},t_{i}+y)\mathbbm{1}_{A}(x_{0}+a_{i},y^{\prime}_{0}+t_{i})+\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}.$

Let $\nu$ be another positive parameter such that $B_{\nu}$ is regular and

$\frac{1}{2}\leq\frac{\nu}{\frac{1}{2^{40}(r^{\prime}+1)d}\Big{(}\frac{\alpha^{4}\delta}{8}\Big{)}^{r^{\prime}}\mu}\leq
1.$

Let us introduce another dummy variable $z$ that ranges over $B_{\nu}$. Apply
the change of variables lemma (Lemma 2.4) for transformation $y\mapsto y-z$,
$t_{i}\mapsto t_{i}+z$, $i\in[r^{\prime}]$, to get

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}a_{1},\dots,a_{r^{\prime}}\in
B_{\mu}\\\ t_{1},\dots,t_{r^{\prime}}\in B,y\in B_{\mu},z\in
B_{\nu}\end{subarray}}\mathbbm{1}_{D}(y-z)\prod_{i\in[r^{\prime}]}\mathbbm{1}_{A}(x_{0}+a_{i},t_{i}+y)\mathbbm{1}_{A}(x_{0}+a_{i},y^{\prime}_{0}+t_{i}+z)$
$\displaystyle\hskip
56.9055pt\geq(1-c_{3})\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}a_{1},\dots,a_{r^{\prime}}\in
B_{\mu}\\\ t_{1},\dots,t_{r^{\prime}}\in B,y\in B_{\mu},z\in
B_{\nu}\end{subarray}}\prod_{i\in[r^{\prime}]}\mathbbm{1}_{A}(x_{0}+a_{i},t_{i}+y)\mathbbm{1}_{A}(x_{0}+a_{i},y^{\prime}_{0}+t_{i}+z)$
$\displaystyle\hskip
227.62204pt+\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}-50(r^{\prime}+1)d\mu^{-1}\nu.$

Since
$\nu\leq\frac{1}{100(r^{\prime}+1)d}\Big{(}\frac{\alpha^{4}\delta}{8}\Big{)}^{r^{\prime}}\mu$,
we have $\frac{1}{2}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}\geq
50(r^{\prime}+1)d\mu^{-1}\nu$. By averaging, there exists a choice of
$a_{1},\dots,a_{r^{\prime}},t_{1},\dots,t_{r^{\prime}}$ such that

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B_{\mu},z\in
B_{\nu}}\mathbbm{1}_{D}(y-z)\prod_{i\in[r^{\prime}]}\mathbbm{1}_{A}(x_{0}+a_{i},t_{i}+y)\mathbbm{1}_{A}(x_{0}+a_{i},y^{\prime}_{0}+t_{i}+z)$
$\displaystyle\hskip
56.9055pt\geq(1-c_{3})\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B_{\mu},z\in
B_{\nu}}\prod_{i\in[r^{\prime}]}\mathbbm{1}_{A}(x_{0}+a_{i},t_{i}+y)\mathbbm{1}_{A}(x_{0}+a_{i},y^{\prime}_{0}+t_{i}+z)+\frac{1}{2}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}.$

Define $Y=\\{y\in B_{\mu}\colon(\forall
i\in[r^{\prime}])\,(x_{0}+a_{i},y+t_{i})\in A\\}$ and $Z=\\{z\in
B_{\nu}\colon(\forall
i\in[r^{\prime}])\,(x_{0}+a_{i},y^{\prime}_{0}+t_{i}+z)\in A\\}$. In terms of
$Y$ and $Z$, we obtain the inequality

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B_{\mu},z\in
B_{\nu}}\mathbbm{1}_{D}(y-z)\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)\geq(1-c_{3})\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in B_{\mu},z\in
B_{\nu}}\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)+\frac{1}{2}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}.$

Let $\beta=|Y|/|B_{\mu}|$ and $\gamma=|Z|/|B_{\nu}|$. We get

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{y\in B_{\mu},z\in
B_{\nu}}\mathbbm{1}_{D}(y-z)\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)\geq(1-c_{3})\beta\gamma$
(16)

and

$\beta,\gamma,\frac{|D|}{|B_{\mu}|}\geq\frac{1}{2}\alpha^{2r^{\prime}}\delta_{\mu}^{r^{\prime}}.$
(17)

Step 5. Using almost-periodicity. In this step, we apply Theorem 2.6. In the
notation of that theorem, we shall set $B^{(1)}=B_{\mu}$ and $B^{(2)}=B_{\nu}$
so the condition $|D|\leq 2|B^{(1)}|$ holds immediately. However, due to other
technical condition that requires $|Y|\leq|D|$, we modify $Y$ slightly. If
$|Y|\,>|D|$, choose a subset $Y^{\prime}\subseteq Y$ uniformly at random among
subsets of size $|D|$. Write $\beta^{\prime}$ for density of $Y^{\prime}$
inside $B_{\mu}$, thus $\beta^{\prime}=|D|/|B_{\mu}|$. Using linearity of
expectation, we get

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{Y^{\prime}}\bigg{(}\sum_{y\in B_{\mu},z\in
B_{\nu}}\mathbbm{1}_{D}(y-z)\mathbbm{1}_{Y^{\prime}}(y)\mathbbm{1}_{Z}(z)-(1-c_{3})\beta^{\prime}\gamma|B_{\mu}||B_{\nu}|\bigg{)}$
$\displaystyle\hskip 56.9055pt=\sum_{y\in B_{\mu},z\in
B_{\nu}}\mathbbm{1}_{D}(y-z)\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)\mathbb{P}(y\in
Y^{\prime})-(1-c_{3})\beta^{\prime}\gamma|B_{\mu}||B_{\nu}|$
$\displaystyle\hskip 56.9055pt=\frac{|Y^{\prime}|}{|Y|}\Big{(}\sum_{y\in
B_{\mu},z\in
B_{\nu}}\mathbbm{1}_{D}(y-z)\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)-(1-c_{3})\beta\gamma|B_{\mu}||B_{\nu}|\Big{)}\geq
0.$

Hence, there exists a choice of a subset $Y^{\prime}$ of size $|D|$ such that
$\mathop{\mathbb{E}}_{y\in B_{\mu},z\in
B_{\nu}}\mathbbm{1}_{D}(y-z)\mathbbm{1}_{Y^{\prime}}(y)\mathbbm{1}_{Z}(z)\geq(1-c_{3})\beta^{\prime}\gamma$.
We misuse the notation and write $Y$ for this subset and $\beta$ for its
density relative to $B_{\mu}$. Note that the lower bound on $\beta$ does not
change, as we had the same lower bound (17) on $\frac{|D|}{|B_{\mu}|}$.
Theorem 2.6 (with $\varepsilon=c_{3}$) provides us with a further regular Bohr
set $B^{\prime}\subseteq B_{\nu}$ of rank at most $d+d^{\prime}$ and radius at
least $\nu\rho c_{3}\beta/(24d^{3}d^{\prime})$, where

$d^{\prime}\leq O\Big{(}\log^{3}(2\beta^{-1})\log(2\gamma^{-1})\Big{)}$

and such that

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{y\in B_{\mu},z\in
B_{\nu},w\in
B^{\prime}}\mathbbm{1}_{D}(y-z+w)\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)\geq(1-2c_{3})\beta\gamma.$

Returning to the definition of the set $D$, we get

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}a\in B_{\mu},b\in B\\\
y\in B_{\mu},z\in B_{\nu},w\in
B^{\prime}\end{subarray}}\mathbbm{1}_{A}(x_{0}+a,y-z+w+b)\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+b)\mathbbm{1}_{Y}(y)\mathbbm{1}_{Z}(z)\geq(1+2^{-10})\alpha^{2}\beta\gamma\delta_{\mu}.$

Step 6. Completing the proof. By averaging, there are $y_{0}\in Y,z_{0}\in Z$
such that

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}a\in B_{\mu},b\in B\\\
w\in
B^{\prime}\end{subarray}}\mathbbm{1}_{A}(x_{0}+a,y_{0}-z_{0}+w+b)\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+b)\geq(1+2^{-10})\alpha^{2}\delta_{\mu}.$

Let $G$ be the set of $b\in B$ such that
$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{a\in
B_{\mu}}\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+b)\geq
2^{-11}\alpha^{2}\delta_{\mu}$. Then

$\frac{1}{|B|}\sum_{b\in
G}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},w\in
B^{\prime}}\mathbbm{1}_{A}(x_{0}+a,y_{0}-z_{0}+w+b)\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+b)\geq(1+2^{-11})\alpha^{2}\delta_{\mu}.$

Note also that

$\displaystyle\frac{1}{|B|}\sum_{b\in
G}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},w\in
B^{\prime}}\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+b)\leq$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},b\in
B}\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+b)$ $\displaystyle=$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in
B_{\mu}}\mathbbm{1}_{X}(x_{0}+a)\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{b\in
B}\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+b)\Big{)}\leq(1+c_{1})\alpha\delta_{\mu}.$

Hence, as $c_{1}\leq 2^{-13}$,

$\frac{1}{|B|}\sum_{b\in
G}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},w\in
B^{\prime}}\mathbbm{1}_{A}(x_{0}+a,y_{0}-z_{0}+w+b)\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+b)\geq(1+2^{-12})\alpha\frac{1}{|B|}\sum_{b\in
G}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},w\in
B^{\prime}}\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+b).$

By averaging, there exists $b_{0}\in G$ such that

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},w\in
B^{\prime}}\mathbbm{1}_{A}(x_{0}+a,y_{0}-z_{0}+b_{0}+w)\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+b_{0})\geq(1+2^{-12})\alpha\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in
B_{\mu}}\mathbbm{1}_{A}(x_{0}+a,y^{\prime}_{0}+b_{0}).$

Define the set $\tilde{X}=\\{a\in
x_{0}+B_{\mu}\colon(a,y^{\prime}_{0}+b_{0})\in A\\}$. Owing to definition of
$G$, its relative density $\delta^{\prime}$ inside $x_{0}+B_{\mu}$ satisfies
$\delta^{\prime}\geq 2^{-11}\alpha^{2}\delta_{\mu}\geq
2^{-14}\alpha^{4}\delta$. Using the new notation, the inequality above becomes

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},w\in
B^{\prime}}\mathbbm{1}_{A}(x_{0}+a,y_{0}-z_{0}+b_{0}+w)\mathbbm{1}_{\tilde{X}}(x_{0}+a)\geq(1+2^{-12})\alpha\delta^{\prime}.$

Write $w_{0}=y_{0}-z_{0}+b_{0}$. Let $\tilde{X}^{\prime}$ be the set of all
$x\in\tilde{X}$ such that $\mathop{\mathbb{E}}_{w\in
B^{\prime}}\mathbbm{1}_{A}(x,w_{0}+w)\geq(1+2^{-13})\alpha$. Then

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{a\in B_{\mu},w\in
B^{\prime}}\mathbbm{1}_{A}(x_{0}+a,w_{0}+w)\mathbbm{1}_{\tilde{X}^{\prime}}(x_{0}+a)\geq
2^{-13}\alpha\delta^{\prime},$

so in particular $|\tilde{X}^{\prime}|\geq
2^{-13}\alpha\delta^{\prime}|B_{\mu}|$.

It remains to ensure that translates of the same Bohr set in vertical and
horizontal directions. Recall that $B^{\prime}\subseteq B_{\nu}$. Using
$\nu\leq\frac{2^{-28}\alpha^{5}\delta}{200d}\mu$, we may apply Corollary 2.5
to find a translate $t_{0}+B^{\prime}\subseteq x_{0}+B_{\mu}$ such that
$|\tilde{X}^{\prime}\cap(t_{0}+B^{\prime})|\geq
2^{-14}\alpha\delta^{\prime}|t_{0}+B^{\prime}|$. Write
$\tilde{X}^{\prime\prime}=\tilde{X}^{\prime}\cap(t_{0}+B^{\prime})$ and let
$\tilde{\delta}$ be $|\tilde{X}^{\prime\prime}|/|t_{0}+B^{\prime}|$. Finally,
we conclude that the relative density of
$A\cap(\tilde{X}^{\prime\prime}\times(w_{0}+B^{\prime}))$ inside
$\tilde{X}^{\prime\prime}\times(w_{0}+B^{\prime})$ is precisely

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in\tilde{X}^{\prime\prime},w\in
w_{0}+B^{\prime}}\mathbbm{1}_{A}(a,w)=\frac{|B^{\prime}|}{|\tilde{X}^{\prime\prime}|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in B^{\prime},w\in
B^{\prime}}\mathbbm{1}_{A}(t_{0}+a,w_{0}+w)\mathbbm{1}_{\tilde{X}^{\prime\prime}}(t_{0}+a)\geq(1+2^{-13})\alpha.$

Hence, we have obtained the desired density increment inside
$\tilde{X}^{\prime\prime}\times(w_{0}+B^{\prime})\subseteq(t_{0}+B^{\prime})\times(w_{0}+B^{\prime})$,
as required.∎

## References

  * [1] M. Ajtai and E. Szemerédi, Sets of lattice points that form no squares, Studia Sci. Math. Hungar. 9 (1974), 9–11.
  * [2] T. Austin, _Partial difference equations over compact Abelian groups, I: modules of solutions_ , arXiv preprint (2013), `arXiv:1305.7269`.
  * [3] T. Austin, _Partial difference equations over compact Abelian groups, II: step-polynomial solutions_ , arXiv preprint (2013), `arXiv:1309.3577`.
  * [4] A. Beker, Improved bounds for skew corner-free sets, arXiv preprint (2024), `arXiv:2402.19169`.
  * [5] T.F. Bloom and O. Sisask, The Kelley–Meka bounds for sets free of three-term arithmetic progressions, arXiv preprint (2023), `arXiv:2302.07211`.
  * [6] J. Bourgain, On triples in arithmetic progression, Geom. Funct. Anal. 9 (1999), 968–984.
  * [7] H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans, Group-theoretic algorithms for matrix multiplication, Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS 2005), IEEE Computer Society, 2005, pp. 379–388.
  * [8] H. Cohn and C. Umans, A group-theoretic approach to fast matrix multiplication, Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS 2003), IEEE Computer Society, 2003, pp. 438–449.
  * [9] E. Croot and O. Sisask, A probabilistic technique for finding almost-periods of convolutions, Geom. Funct. Anal. 20 (2010), no. 6, 1367–1396.
  * [10] Y. Filmus, H. Hatami, K. Hosseini and E. Kelman, _A generalization of the Kelley-Meka theorem to binary systems of linear forms_ , arXiv preprint (2023), `arXiv:2311.12248`.
  * [11] W.T. Gowers, _A new proof of Szemerédi’s theorem_ , Geom. Funct. Anal. 8 (1998), 529–551.
  * [12] W.T. Gowers, _A new proof of Szemerédi’s theorem_ , Geom. Funct. Anal. 11 (2001), 465–588.
  * [13] M. Jaber, S. Lovett and A. Ostuni, _Strong bounds for skew corner-free sets_ , arXiv preprint (2024), `arXiv:2404.07380`.
  * [14] Z. Kelley and R. Meka, _Strong Bounds for 3-Progressions_ , in 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 933–973.
  * [15] Z. Kelley, S. Lovett and R. Meka, _Explicit separations between randomized and deterministic Number-on-Forehead communication_ , arXiv preprint (2023), `arXiv:2308.12451`.
  * [16] L. Milićević, An inverse theorem for certain directional Gowers uniformity norms, Publ. Inst. Math. (Beograd) (N.S.) 113 (2023), 1–56.
  * [17] S. Peluse, Finite field models in arithmetic combinatorics – twenty years on, arXiv preprint (2023), `arXiv:2312.08100`.
  * [18] F. Petrov, A variant of the corners problem, (2023),
`https://mathoverflow.net/questions/451580/a-variant-of-thecorners-problem/`

  * [19] C. Pohoata and D. Zakharov, On skew corner-free sets, arXiv preprint (2024), `arXiv:2401.17507`.
  * [20] K. Pratt, On generalized corners and matrix multiplication, arXiv preprint (2023), `arXiv:2309.03878`.
  * [21] T. Sanders, On the Bogolyubov-Ruzsa lemma, Anal. PDE 5 (2012), no. 3, 627–655.
  * [22] T. Schoen and O. Sisask, _Roth’s theorem for four variables and additive structures in sums of sparse sets_ , Forum Math. Sigma 4 (2016), e5, 28pp.
  * [23] I.D. Shkredov, On a generalization of Szemerédi’s theorem, Proc. Lond. Math. Soc. (3) 93 (2006), 723–760.
  * [24] I.D. Shkredov, Some new results on the higher energies I, arXiv preprint (2023), `arXiv:2303.16348`.
  * [25] T. Tao and V. Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics 105, Cambridge University Press, Cambridge, UK, 2006.