# Strong bounds for skew corner-free sets

Michael Jaber Department of Computer Science, UT Austin. Email:
<EMAIL_ADDRESS>Supported by NSF Grant CCF-2312573 and a Simons
Investigator Award (#409864, David Zuckerman). Shachar Lovett Department of
Computer Science and Engineering, UC San Diego. Email<EMAIL_ADDRESS>Supported by NSF DMS award 1953928, NSF CCF award 2006443, and a Simons
investigator award. The research was done while on sabbatical at the Weizmann
Institute of Science, partially funded by the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation programme,
grant agreement No. 949083. Anthony Ostuni Department of Computer Science and
Engineering, UC San Diego. Email<EMAIL_ADDRESS>Supported by NSF DMS award
1953928.

###### Abstract

Motivated by applications to matrix multiplication algorithms, Pratt asked
(ITCS’24) how large a subset of $[n]\times[n]$ could be without containing a
skew-corner: three points $(x,y),(x,y+h),(x+h,y^{\prime})$ with $h\neq 0$. We
prove any skew corner-free set has size at most
$\exp(-\Omega(\log^{1/12}n))\cdot n^{2}$, nearly matching the best known lower
bound of $\exp(-O(\sqrt{\log n}))\cdot n^{2}$ by Beker (arXiv’24). Our
techniques generalize those of Kelley and Meka’s recent breakthrough on three-
term arithmetic progression (FOCS’23), answering a question of Beker
(arXiv’24). We note that a similar bound was obtained concurrently and
independently by Milićević (arXiv’24).

##  1 Introduction

In an attempt to rule out certain groups as candidates for achieving an
optimal matrix multiplication algorithm using the framework of [10, 9], Pratt
[18] introduced skew corners: triples of points $(x,y),(x,y+h)$, and
$(x+h,y^{\prime})$ for arbitrary $x,y,y^{\prime},$ and $h$. Note that the more
traditional form of corners can be recovered by insisting $y=y^{\prime}$. We
call a skew corner trivial if $h=0$ and nontrivial otherwise, and we call a
set skew corner-free if it does not contain any nontrivial skew corners.
Pratt’s matrix multiplication results are conditional, holding if the largest
skew corner-free subset of $[n]\times[n]$ has size $O(n^{1+\varepsilon})$ for
all $\varepsilon>0$, as well as weaker results for the upper bound
$O(n^{4/3-\varepsilon})$ for any fixed $\varepsilon>0$ [18].

Very recently, these two conjectures were refuted. Pohoata and Zakharov [19]
constructed a skew corner-free set of size $\Omega(n^{5/4})$, which was
improved shortly after to $\exp(-O(\sqrt{\log n}))\cdot n^{2}$ by Beker [3]
using a Behrend-type construction (see [2]). In the same paper, Beker also
improved the best known upper bounds to $O((\log n)^{-c})\cdot n^{2}$ for an
absolute constant $c>0$, and went on to ask if one could use the techniques of
the recent breakthrough on three-term arithmetic progressions (3APs) [13] (see
also [8, 7]) to obtain a bound of $\exp(-\Omega(\log^{c}n))\cdot n^{2}$ for
some constant $c>0$. We resolve this question affirmatively.

######  Theorem 1.1.

Any skew corner-free subset of $[n]\times[n]$ has size at most
$\exp\left\\{-\Omega\left(\log^{1/12}n\right)\right\\}\cdot n^{2}$.

In fact, we can prove such a result for any skew corner-free subset of
$G\times G$, where $G$ is an arbitrary finite Abelian group. It is likely that
the constant $1/12$ can be somewhat improved using ideas similar to [7].
However, the overall technique’s limitations appear to prevent improvements
significant enough to approach Beker’s lower bound [3], so we instead
prioritize a streamlined presentation.

As is somewhat standard, we first exhibit our argument in the simpler finite
field setting. Here, we can obtain slightly stronger bounds.

######  Theorem 1.2.

Let $q$ be a prime power. Any skew corner-free subset of
$\mathbb{F}_{q}^{n}\times\mathbb{F}_{q}^{n}$ has size at most
$q^{2n-\Omega(n^{1/9})}$.

A version of Theorem 1.2 with the superior bound $O(q^{(2-c)n})$ (for a
constant $c>0$ depending on $q$) is known via the polynomial method [19].
However, this technique does not appear to generalize to the integer case,
whereas our analytic approach is able to do so relatively painlessly.

We largely view this work as a step toward better understanding the
traditional corners problem of how large a subset of $[n]\times[n]$ one can
have without three points $(x,y),(x,y+h),(x+h,y)$. This problem is much older
and better studied than the skew variant, yet the best upper bound of
$O(n^{2}/(\log\log n)^{0.0137\cdots})$ [21] remains far from the lower bound
of $\exp(-O(\sqrt{\log n}))\cdot n^{2}$ [2] (see also [14, 11, 12]).

There has been optimism (see, e.g., [15] and [17, Section 1.2]) that the
techniques recently used to dramatically improve the best known upper bounds
on 3AP-free sets [13] could also be applied in the (traditional) corners
setting. Our work provides evidence that this is a potentially fruitful
direction. In fact, we are able to either black-box or closely follow the
proofs of many lemmas from the excellent exposition of Bloom and Sisask [8] of
Kelley and Meka’s work, raising the following question about the relationship
between these problems.

######  Question 1.3.

Suppose the largest 3AP-free subset of $[n]$ has size $\delta n$. Does the
largest skew corner-free subset of $[n]\times[n]$ have size
$\text{poly}(\delta)\cdot n^{2}$? More generally, is it possible to directly
convert bounds from one setting to another?

##### Concurrent work.

A similar result to Theorem 1.1 was obtained concurrently and independently by
Milićević [16]. His techniques are also based on the ideas of [13], although
the specifics diverge slightly from our own.

##  2 Background

Let $G$ be a finite Abelian group throughout (although we will only truly be
concerned with vector spaces over a finite field $\mathbb{F}_{q}^{n}$ or the
integers modulo a positive integer $\mathbb{Z}/N\mathbb{Z}$).

##### Asymptotics.

We use standard asymptotic notation of $O(\cdot)$ and $\Omega(\cdot)$ to
suppress fixed constants that do not depend on any parameters. Occasionally,
we will use subscripts to hide a dependence on particular parameters (e.g.,
$O_{\varepsilon}(\cdot)$).

##### Distributions.

A distribution $\nu$ over $G$ is a non-negative function $\nu\colon
G\to\mathbb{R}_{\geq 0}$ with $\operatorname{\mathbb{E}}[\nu]=1$. For $f\colon
G\to\mathbb{R}_{\geq 0}$ define $\nu(f)=\operatorname{\mathbb{E}}_{x\in
G}\nu(x)f(x)$ to be the average of $f$ under $\nu$. We also define $\nu_{f}$
to be $f$ normalized to have expectation $1$ under $\nu$; that is,
$\nu_{f}(x)=\nu(x)f(x)/\nu(f)$. We use $\mu$ to denote the uniform
distribution on $G$, so $\mu\equiv 1$. Given a set $A\subseteq G$, we identify
$A$ with its indicator function $1_{A}$ and define accordingly
$\nu(A)=\nu(1_{A})$ and $\nu_{A}=\nu_{1_{A}}$.

##### Functions.

For functions $f,g\colon G\to\mathbb{R}$, we define inner products and norms
with the normalized counting measure on $G$, namely

$\langle f,g\rangle=\mathop{\mathbb{E}}_{x\in
G}f(x)g(x)\quad\text{and}\quad\|f\|_{p}=\left(\mathop{\mathbb{E}}_{x\in
G}|f(x)|^{p}\right)^{1/p}\text{ for }1\leq p<\infty,$

as well as $\|f\|_{\infty}=\max_{x\in G}|f(x)|$. Additionally, we define the
convolution and the difference convolution as

$(f\ast g)(x)=\mathop{\mathbb{E}}_{y\in
G}f(y)g(x-y)\quad\text{and}\quad(f\circ g)(x)=\mathop{\mathbb{E}}_{y\in
G}f(y)g(x+y),$

and the $p$-fold convolution as $f^{(p)}=f\ast f^{(p-1)}$, where $f^{(1)}=f$.
Note the useful adjoint property $\langle f,g\ast h\rangle=\langle h\circ
f,g\rangle.$ We will also want to work with other measures on $G$. For a
measure $\nu$ on $G$, we write

$\langle f,g\rangle_{\nu}=\mathop{\operatorname{\mathbb{E}}}_{x\in
G}\nu(x)f(x)g(x)\quad\text{and}\quad\|f\|_{p(\nu)}=\left(\mathop{\operatorname{\mathbb{E}}}_{x\in
G}\nu(x)|f(x)|^{p}\right)^{1/p}\text{ for }1\leq p<\infty.$

Occasionally the notation $f^{g}(x)=f(x-g)$ for some $g\in G$ will be useful.

Let $\widehat{G}=\\{\text{homomorphisms }\gamma:G\to\mathbb{C}^{\times}\\}$ be
the dual group of $G$. The Fourier transform of $f$ is
$\widehat{f}\colon\widehat{G}\to\mathbb{C}$, where

$\widehat{f}(\gamma)=\mathop{\operatorname{\mathbb{E}}}_{x\in
G}f(x)\gamma(-x).$

If $\widehat{f}(\gamma)\geq 0$ for all $\gamma\in\widehat{G}$, we say $f$ is
spectrally non-negative, denoted $\widehat{f}\geq 0$. Note the basic facts
that $\widehat{f\ast g}=\widehat{f}\cdot\widehat{g}$, $\widehat{f\circ
f}=|\widehat{f}|^{2}$, and $\widehat{f^{p}}=\widehat{f}^{(p)}$. In particular,
$f\circ f$ is spectrally non-negative.

###  2.1 Skew corners

Sequences of evenly spaced integers, known as arithmetic progressions, are
central objects of study in additive combinatorics. In an attempt to
understand similar structure in higher dimensions, Ajtai and Szemerédi [1]
considered the following objects.

######  Definition 2.1 (Corners).

A _corner_ in $G\times G$ is a triple of the form $(x,y),(x,y+h),(x+h,y)$ for
arbitrary $x,y,h\in G$. A corner is _nontrivial_ if $h\neq 0$.

By relaxing the structure to allow the third point to lie anywhere on the
vertical line $x+h$, one obtains skew corners, a generalization recently
raised by Pratt [18].

######  Definition 2.2 (Skew corners).

A _skew corner_ in $G\times G$ is a triple of the form
$(x,y),(x,y+h),(x+h,y^{\prime})$ for arbitrary $x,y,y^{\prime},h\in G$. A skew
corner is _nontrivial_ if $h\neq 0$. Additionally, a set is _skew corner-free_
is it does not contain nontrivial skew corners.

One immediate, yet useful, observation is that shifting a set will not change
the number of skew corners it contains.

######  Observation 2.3.

The number of skew corners in a set $A$ is invariant to both horizontal
shifting ($A\rightarrow\\{(x+a,y):(x,y)\in A\\}$) and vertical shifting
($A\rightarrow\\{(x,y+b(x)):(x,y)\in A\\}$).

The following lemma allows us to count skew corners in an analytic way.

######  Lemma 2.4.

Let $A\subseteq G\times G$ and $A_{x}=\\{y:(x,y)\in A\\}$. Additionally, let
$D\colon G\to\mathbb{R}_{\geq 0}$ be given by $D(x)=|A_{x}|$. Then, the number
of skew corners in $A$ is counted by

$|G|^{2}\sum_{x\in G}\langle 1_{A_{x}}\circ 1_{A_{x}+x},D\rangle.$

###### Proof.

Recall a skew corner in $A$ is a triple of the form

$(x,y),(x,y+h),(x+h,y^{\prime})$

for arbitrary $x,y,y^{\prime},h\in G$. The number of skew corners is given by

$\displaystyle\sum_{x,y,y^{\prime},h\in
G}1_{A}(x,y)1_{A}(x,y+h)1_{A}(x+h,y^{\prime})$
$\displaystyle=\sum_{x,y,y^{\prime},h}1_{A_{x}}(y)1_{A_{x}}(y+h)1_{A_{x+h}}(y^{\prime})$
$\displaystyle=\sum_{x,y,h}1_{A_{x}}(y)1_{A_{x}+x}(x+y+h)D(x+h)$
$\displaystyle=|G|\sum_{x,h}(1_{A_{x}}\circ 1_{A_{x}+x})(x+h)D(x+h)$
$\displaystyle=|G|^{2}\sum_{x}\langle 1_{A_{x}}\circ 1_{A_{x}+x},D\rangle.$ ∎

Occasionally, the following normalized form will be more useful.

######  Lemma 2.5.

Let $A\subseteq G\times G$, $A_{x}=\\{y:(x,y)\in A\\}$, and
$\eta\in\mathbb{R}_{\geq 0}$. Additionally, let $f=\sum_{x\in G}1_{A_{x}}\circ
1_{A_{x}+x}$ and $D\colon G\to\mathbb{R}_{\geq 0}$ be given by $D(x)=|A_{x}|$.
If $\langle\mu_{f},\mu_{D}\rangle\geq\eta$, then the number of skew corners in
$A$ is at least

$\eta\cdot\frac{|A|^{3}}{|G|^{2}}.$

###### Proof.

Unraveling the definition of $\langle\mu_{f},\mu_{D}\rangle$, we have

$\displaystyle\eta\leq\left\langle\frac{1}{\operatorname{\mathbb{E}}[f]}\sum_{x\in
G}1_{A_{x}}\circ
1_{A_{x}+x},\frac{D}{\operatorname{\mathbb{E}}[D]}\right\rangle$
$\displaystyle=\frac{1}{\operatorname{\mathbb{E}}[f]}\cdot\frac{1}{\operatorname{\mathbb{E}}[D]}\sum_{x\in
G}\left\langle 1_{A_{x}}\circ 1_{A_{x}+x},D\right\rangle$
$\displaystyle=\frac{|G|^{2}}{\sum|A_{x}|^{2}}\cdot\frac{|G|}{\sum|A_{x}|}\sum_{x\in
G}\left\langle 1_{A_{x}}\circ 1_{A_{x}+x},D\right\rangle$
$\displaystyle\leq\frac{|G|^{3}}{|A|^{2}}\cdot\frac{|G|}{|A|}\sum_{x\in
G}\left\langle 1_{A_{x}}\circ 1_{A_{x}+x},D\right\rangle$ (Cauchy-Schwarz)
$\displaystyle=\frac{|G|^{2}}{|A|^{3}}\times\text{(number of skew corners in
$A$)}.$ (Lemma 2.4) ∎

###  2.2 Bohr sets

To prove Theorem 1.2, we will take advantage of the abundance of subspaces in
$\mathbb{F}_{q}^{n}$. As this no longer holds once we move to more general
Abelian groups, we will turn to the machinery of Bohr sets, introduced by
Bourgain [5], to prove Theorem 1.1. We will only require the very basics, but
one may entirely skip over this topic if they are solely interested in a high-
level understanding of our results; all the main ideas are present in the
simpler finite field case (Section 3).

######  Definition 2.6 (Bohr sets).

For a nonempty $\Gamma\subseteq\widehat{G}$ and $\phi\in[0,2]$, we define the
Bohr set

$B=\mathrm{Bohr}(\Gamma,\phi)=\\{x\in G:|1-\gamma(x)|\leq\phi\text{ for all
}\gamma\in\Gamma\\},$

where $\Gamma$ is the frequency set, $\phi$ is the width (or radius), and
$|\Gamma|$ is the rank $\mathrm{rk}(B)$.

Note that a Bohr set $B$ does not uniquely define its frequency set or width.
Thus, we always implicitly view $B$ as the tuple
$(\Gamma,\phi,\mathrm{Bohr}(\Gamma,\phi))$. However, the notation
$B^{\prime}\subseteq B$ only refers to containment of the actual set itself
and does not depend on the frequency set or width. To handle situations where
we are concerned with these parameters, we follow [22] in defining sub-Bohr
sets.

######  Definition 2.7.

Let $B=\mathrm{Bohr}(\Gamma,\phi)$,
$B^{\prime}=\mathrm{Bohr}(\Gamma^{\prime},\phi^{\prime})$ be Bohr sets. We say
that $B^{\prime}$ is a _sub-Bohr set_ of $B$, denoted $B^{\prime}\leq B$, if
$\Gamma^{\prime}\supseteq\Gamma$ and $\phi^{\prime}\leq\phi$.

######  Observation 2.8.

Let $B^{\prime}\leq B$ for Bohr sets $B,B^{\prime}$. Then,
$B^{\prime}\subseteq B$.

A common operation performed on Bohr sets is dilation. If
$B=\mathrm{Bohr}(\Gamma,\phi)$ is a Bohr set and $\rho>0$, then the
corresponding dilate of $B$ is $B_{\rho}=\mathrm{Bohr}(\Gamma,\rho\phi)$. The
following observation about sub-Bohr set dilates will be useful in later
arguments.

######  Observation 2.9.

Let $B^{\prime}\leq B$ for Bohr sets $B,B^{\prime}$. Then,
$B^{\prime}_{\rho}\leq B_{\rho}$ for all $\rho>0$. In particular,
$B^{\prime}_{\rho}\subseteq B_{\rho}$.

If small dilations do not substantially change the size of a Bohr set $B$, we
call $B$ regular. Regular Bohr sets will be particularly useful for our
purposes, as informally, one can view a regular Bohr set of rank $r$
analogously to a subspace of co-dimension $r$.

######  Definition 2.10 (Regular Bohr sets).

A Bohr set $B$ of rank $r$ is _regular_ if for all $0\leq\kappa\leq 1/100r$,
we have

$|B_{1+\kappa}|\leq(1+100\kappa
r)|B|\quad\text{and}\quad|B_{1-\kappa}|\geq(1-100\kappa r)|B|.$

We record some useful lemmas, most of which are listed in the appendix of [8].
See [23, Section 4.4] or [4, Chapter 6] for proofs of the first two standard
results, as well as a more thorough treatment of Bohr set machinery.

######  Lemma 2.11.

For any Bohr set $B$, there exists $\rho\in[\frac{1}{2},1]$ such that
$B_{\rho}$ is regular.

######  Lemma 2.12.

If $\rho\in(0,1)$ and $B$ is a Bohr set of rank $r$, then
$|B_{\rho}|\geq(\rho/4)^{r}|B|$.

######  Lemma 2.13 ([6, Lemma 4.6]).

There is a constant $c>0$ such that the following holds. If $B$ is a regular
Bohr set of rank $r$ and $\nu$ is a probability measure supported on
$B_{\rho}$, with $\rho\leq c/r$, then

$\mu_{B}\leq 2\mu_{B_{1+\rho}}\ast\nu.$

######  Lemma 2.14 ([6, Lemma 4.5]).

If $B$ is a regular Bohr set of rank $r$ and $\nu$ is a probability measure
supported on $B_{\rho}$, with $\rho\in(0,1)$, then

$\|\mu_{B}\ast\nu-\mu_{B}\|_{1}\leq O(\rho r).$

We will make use of the following corollary.

######  Corollary 2.15.

If $B$ is a regular Bohr set of rank $r$ and $\nu$ is a probability measure
supported on $B_{\rho}$, with $\rho\in(0,1)$, and $f\colon G\to\mathbb{R}$,
then

$|\langle f\ast\nu,\mu_{B}\rangle-\langle f,\mu_{B}\rangle|\leq
O\left(\|f\|_{\infty}\cdot\rho r\right).$

###### Proof.

We have $\langle f\ast\nu,\mu_{B}\rangle=\langle
f,\mu_{B}\circ\nu\rangle=\langle f,\mu_{B}\rangle+\langle
f,\mu_{B}\circ\nu-\mu_{B}\rangle.$ Since Bohr sets are symmetric, we can
replace $\nu(x)$ with $\nu(-x)$ and maintain that $\nu$ is supported on
$B_{\rho}$. It suffices to bound

$\displaystyle|\langle
f,\mu_{B}\ast\nu-\mu_{B}\rangle|\leq\|f\|_{\infty}\|\mu_{B}\ast\nu-\mu_{B}\|_{1}\leq
O(\|f\|_{\infty}\cdot\rho r),$

which follows by Lemma 2.14 and the triangle inequality. ∎

###  2.3 Spread sets

A key definition underpinning Kelley and Meka’s breakthrough result on 3APs
[13] is a pseudorandomness notion they call spreadness. A subset of
$\mathbb{F}_{q}^{n}$ is spread if it has no significant density increment by
restricting to a large affine subspace.

######  Definition 2.16 ($(r,\lambda)$-spread).

Let $r\geq 1$ and $\lambda>1$. A set $A\subseteq\mathbb{F}_{q}^{n}$ is
_$(r,\lambda)$ -spread_ if for every subspace $V\subseteq\mathbb{F}_{q}^{n}$
of co-dimension at most $r$ and shift $x\in\mathbb{F}_{q}^{n}$, we have

$\frac{|(A-x)\cap V|}{|V|}\leq\lambda\cdot\frac{|A|}{|\mathbb{F}_{q}^{n}|}.$

In light of Lemma 2.4, we will need the following generalization of spreadness
that applies to multiple sets. It should intuitively be clear that the
definition we choose needs to be invariant to shifts, since the number of skew
corners in a set has this property (2.3).

######  Definition 2.17 ($(r,\lambda)$-simultaneously spread).

Let $r\geq 1$ and $\lambda>1$. A collection $\\{A_{i}\\}_{i\in S}$ of subsets
of $\mathbb{F}_{q}^{n}$ is _$(r,\lambda)$ -simultaneously spread_ if for every
subspace $V\subseteq\mathbb{F}_{q}^{n}$ of co-dimension at most $r$ and shifts
$\\{x_{i}\\}_{i\in S}$ in $\mathbb{F}_{q}^{n}$, we have

$\sum_{i\in S}\left(\frac{|(A_{i}-x_{i})\cap
V|}{|V|}\right)^{2}\leq\lambda\cdot\sum_{i\in
S}\left(\frac{|A_{i}|}{|\mathbb{F}_{q}^{n}|}\right)^{2}.$

When our ambient space is a vector space $W\subseteq\mathbb{F}_{q}^{n}$, we
will say the collection is $(r,\lambda)$-simultaneously spread _in $W$_ if it
is $(r,\lambda)$-simultaneously spread after being mapped according to an
isomorphism from $W$ to $\mathbb{F}_{q}^{\dim W}$.

Additionally, we require a version with Bohr sets replacing subspaces for
general Abelian groups. For technical reasons, it will simplify later analysis
to measure density with respect to a particular Bohr set rather than the
ambient space (as in Definition 2.17).

######  Definition 2.18 ($(r,\delta,\lambda)$-simultaneously spread).

Let $r\geq 1$, $\delta\in(0,1)$, and $\lambda>1$. A collection
$\\{A_{i}\\}_{i\in S}$ of subsets of a regular Bohr set $B\subseteq G$ is
_$(r,\delta,\lambda)$ -simultaneously spread in $B$_ if for every regular Bohr
set $B^{\prime}\leq B$ of rank at most $\mathrm{rk}(B)+r$ and measure
$\mu(B^{\prime})\geq\delta\mu(B)$, and shifts $\\{x_{i}\\}_{i\in S}$ in $G$,
we have

$\sum_{i\in S}\left(\frac{|(A_{i}-x_{i})\cap
B^{\prime}|}{|B^{\prime}|}\right)^{2}\leq\lambda\cdot\sum_{i\in
S}\left(\frac{|A_{i}|}{|B|}\right)^{2}.$

It was useful in [13] to use $\|\mu_{A}\ast\mu_{V}\|_{\infty}\leq\lambda$ as
an equivalent form of Definition 2.16. We will later need to exploit a similar
relationship with an alternative definition of simultaneous spreadness. (The
proof of this connection explains why the summands in Definition 2.17 and
Definition 2.18 are squared.)

######  Lemma 2.19.

Let $r\geq 1$, $\lambda>1$, $\\{A_{i}\\}_{i\in S}$ be an
$(r,\lambda)$-simultaneously spread collection of subsets of
$\mathbb{F}_{q}^{n}$, and $\alpha=\sum_{i\in
S}(|A_{i}|/|\mathbb{F}_{q}^{n}|)^{2}$. Then for every subspace
$V\subseteq\mathbb{F}_{q}^{n}$ of co-dimension at most $r$, we have

$\left\|\left(\frac{1}{\alpha}\sum_{i\in S}1_{A_{i}}\circ
1_{A_{i}}\right)\ast\mu_{V}\right\|_{\infty}\leq\sqrt{\lambda}.$

###### Proof.

Let $x\in\mathbb{F}_{q}^{n}$ be an element maximizing the input to the
$L^{\infty}$-norm. Then by Cauchy-Schwarz,

$\left\|\left(\sum_{i\in S}1_{A_{i}}\circ
1_{A_{i}}\right)\ast\mu_{V}\right\|_{\infty}=\sum_{i\in S}\langle
1_{A_{i}}\circ 1_{A_{i}},\mu_{V+x}\rangle\leq\sum_{i\in
S}\|1_{A_{i}}\|_{1}\|1_{A_{i}}\ast\mu_{V}\|_{\infty}\leq\alpha^{1/2}\left(\sum_{i\in
S}\|1_{A_{i}}\ast\mu_{V}\|_{\infty}^{2}\right)^{1/2}.$

Now let $x_{i}$ be a shift which maximizes $|(A_{i}-x_{i})\cap V|$ for each
$i\in S$. By our spreadness assumption, we have

$\sum_{i\in S}\|1_{A_{i}}\ast\mu_{V}\|_{\infty}^{2}=\sum_{i\in
S}\left(\frac{|(A_{i}-x_{i})\cap V|}{|V|}\right)^{2}\leq\lambda\cdot\sum_{i\in
S}\left(\frac{|A_{i}|}{|\mathbb{F}_{q}^{n}|}\right)^{2}=\lambda\alpha.$

Substituting the second equation into the first yields the result. ∎

We also need an analogous lemma for Bohr sets. While similar, we present the
proof here to illustrate why there is an additional $\mu(B)^{-1}$ factor.

######  Lemma 2.20.

Let $r\geq 1$, $\varepsilon\in(0,1)$, $\lambda>1$, $\\{A_{i}\\}_{i\in S}$ be
an $(r,\delta,\lambda)$-simultaneously spread collection of subsets of a
regular Bohr set $B\subseteq G$, and $\alpha=\sum_{i\in S}(|A_{i}|/|G|)^{2}$.
Then for every regular Bohr set $B^{\prime}\leq B$ of rank at most
$\mathrm{rk}(B)+r$ and measure $\mu(B^{\prime})\geq\delta\mu(B)$, we have

$\left\|\left(\frac{1}{\alpha}\sum_{i\in S}1_{A_{i}}\circ
1_{A_{i}}\right)\ast\mu_{B^{\prime}}\right\|_{\infty}\leq\sqrt{\lambda}\cdot\mu(B)^{-1}.$

###### Proof.

Let $x\in G$ be an element maximizing the input to the $L^{\infty}$-norm. Then
by Cauchy-Schwarz,

$\left\|\left(\sum_{i\in S}1_{A_{i}}\circ
1_{A_{i}}\right)\ast\mu_{B^{\prime}}\right\|_{\infty}=\sum_{i\in S}\langle
1_{A_{i}}\circ 1_{A_{i}},\mu_{B^{\prime}+x}\rangle\leq\sum_{i\in
S}\|1_{A_{i}}\|_{1}\|1_{A_{i}}\ast\mu_{B^{\prime}}\|_{\infty}\leq\alpha^{1/2}\left(\sum_{i\in
S}\|1_{A_{i}}\ast\mu_{B^{\prime}}\|_{\infty}^{2}\right)^{1/2}.$

Now let $x_{i}$ be a shift which maximizes $|(A_{i}-x_{i})\cap B^{\prime}|$.
By our spreadness assumption, we have

$\sum_{i\in S}\|1_{A_{i}}\ast\mu_{B^{\prime}}\|_{\infty}^{2}=\sum_{i\in
S}\left(\frac{|(A_{i}-x_{i})\cap
B^{\prime}|}{|B^{\prime}|}\right)^{2}\leq\lambda\cdot\sum_{i\in
S}\left(\frac{|A_{i}|}{|B|}\right)^{2}=\lambda\alpha\cdot\mu(B)^{-2}.$

Substituting the second equation into the first yields the result. ∎

##  3 The finite field case

In this section, we prove Theorem 1.2, restated below for convenience. Note
that Pohoata and Zakharov [19] used the polynomial method to obtain the
stronger bound $O(q^{(2-c)n})$ (for a constant $c>0$ depending on $q$).
However, their techniques do not seem to generalize to the integer case. See
1.2

The analogous result for 3APs in [13] is proved by repeatedly restricting the
set of interest to a large, denser subspace until no such subspaces exist
(i.e., the set is spread). Then, they show spread sets have approximately the
same number of 3APs as a random set, and since there cannot be too many
trivial 3APs, the original set size cannot be too large.

This intuition guides our approach, although the situation is more complicated
for skew corners. It is helpful to think about the converse of the above
discussion. For a set $A$ of large density, if $A$ contains no 3APs, then $A$
must exhibit a density increment on a reasonably large subspace. In the skew
corners case, we start with a large subset $A$ of
$\mathbb{F}_{q}^{n}\times\mathbb{F}_{q}^{n}$, and denote by $\\{A_{g}\\}$ its
columns. We are asking if there are many solutions of the form $x-y+g\in D$
for $x,y\in A_{g}$, where $D$ can be thought of as the set of columns of
decent density. By Kelley and Meka’s result, if each of the sets $A_{g}$ was
spread, then we would have many solutions and thus many skew corners. So, we
know that if there are no skew corners, then most of the $A_{g}$ are not
spread, and most of the $A_{g}$ exhibit a density increment on some large
subspace $V_{g}$. The issue is, however, that a priori these subspaces $V_{g}$
might be completely uncorrelated.

One might hope that if the sum of $1_{A_{g}}\circ 1_{A_{g}+g}$ is far from
uniform, then the individual deviations of the $1_{A_{g}}\circ 1_{A_{g}+g}$
are cooperating, and so there should be a density increment which is
compatible with the $A_{g}$ on average. Indeed, this ends up being what
happens, and we show that there is a common subspace $V$ which “explains” the
lack of uniformity for the sum of convolutions. Namely, for most $A_{g}$,
there is some affine shift $V+x_{g}$ which admits a density increment on
$A_{g}$. For technical reasons, we will measure progress in terms of the sum
of the squared densities $(|A_{g}\cap(V+x_{g})|/|V|)^{2}$.

It is tempting to ignore the collection of $A_{g}$, and simply proceed with a
single $A_{h}$ of highest density. The Kelley-Meka techniques allow one to
restrict $A_{h}$ to an affine subspace $V$ on which the convolution
$1_{A_{h}}\circ 1_{A_{h}+h}$ is close to uniform. The issue, however, is that
this approach does not ensure that $D$ has large density on $V$. There may in
fact be no nonempty columns indexed by elements from $V$, and so this naive
approach does not work as is. For this reason, our density increment process
needs access to many of the $A_{g}$ at once, so that we can restrict the set
of “rows” in which the $A_{g}$ are contained, as well as the set of “columns”
by which the $A_{g}$ are indexed while maintaining density guarantees.

The main steps then are to argue that (1) a collection of sets
$\\{A_{g}\\}_{g\in G}$ can be restricted in such a way that it no longer
admits a collective density increment on a subspace and (2) if a collection of
$\\{A_{g}\\}_{g\in G}$ contains enough points but fails to have skew corners,
then there must be some subspace on which the $A_{g}$ collectively obtain a
density increment.

###  3.1 Obtaining simultaneous spreadness

A useful property of spreadness is that it is easy to obtain via an iterative
density increment argument. The generalization to simultaneous spreadness
preserves this property with only slightly more work.

######  Lemma 3.1.

Let $\varepsilon\in(0,1),r\geq 1,$ and $\\{A_{g}\\}_{g\in\mathbb{F}_{q}^{n}}$
be a collection of subsets of $\mathbb{F}_{q}^{n}$ with $\sum|A_{g}|^{2}\geq
2^{-d}|\mathbb{F}_{q}^{n}|^{3}$. Then there exists a subspace
$V\subseteq\mathbb{F}_{q}^{n}$ of co-dimension at most $O(rd/\varepsilon)$ and
shifts $\\{x_{g}\\}_{g\in\mathbb{F}_{q}^{n}}$, $w\in\mathbb{F}_{q}^{n}$ such
that

  1. 1.

The collection $\\{(A_{g}-x_{g})\cap V\\}_{g\in V+w}$ is
$(r,1+\varepsilon)$-simultaneously spread in $V$, and

  2. 2.

$\sum_{g\in V+w}|(A_{g}-x_{g})\cap V|^{2}\geq 2^{-d}|V|^{3}$.

###### Proof.

If $\\{A_{g}\\}_{g\in\mathbb{F}_{q}^{n}}$ is not
$(r,1+\varepsilon)$-simultaneously spread, then there exists a subspace
$V\subseteq\mathbb{F}_{q}^{n}$ of co-dimension at most $r$ and shifts
$\\{x_{g}\\}_{g\in\mathbb{F}_{q}^{n}}$ in $\mathbb{F}_{q}^{n}$ such that

$\sum_{g\in\mathbb{F}_{q}^{n}}\left(\frac{|(A_{g}-x_{g})\cap
V|}{|V|}\right)^{2}>(1+\varepsilon)\sum_{g\in\mathbb{F}_{q}^{n}}\left(\frac{|A_{g}|}{|\mathbb{F}_{q}^{n}|}\right)^{2}.$

By averaging, there must exist an affine subspace $V+w$ with

$\sum_{g\in V+w}\left(\frac{|(A_{g}-x_{g})\cap
V|}{|V|}\right)^{2}>(1+\varepsilon)\frac{|V|}{|\mathbb{F}_{q}^{n}|}\sum_{g\in\mathbb{F}_{q}^{n}}\left(\frac{|A_{g}|}{|\mathbb{F}_{q}^{n}|}\right)^{2}.$
(1)

Construct a new collection $A^{\prime}_{g}=(A_{g+w}-x_{g+w})\cap V$ for $g\in
V$. If $\\{A^{\prime}_{g}\\}_{g\in V}$ is not
$(r,1+\varepsilon)$-simultaneously spread in $V$, we repeat this process with
$\\{A^{\prime}_{g}\\}_{g\in V}$ as the collection and
$V\cong\mathbb{F}_{q}^{\dim(V)}$ as the ambient vector space, noting that
Equation 1 and our initial density assumption imply

$\sum_{g\in V}|A^{\prime}_{g}|^{2}>(1+\varepsilon)\cdot 2^{-d}|V|^{3}.$

After $i$ iterations, the density will be at least $(1+\varepsilon)^{i}\cdot
2^{-d}$. Since it cannot exceed 1, we must obtain the desired collection in
$O(d/\varepsilon)$ iterations. ∎

###  3.2 Using simultaneous spreadness

Now that we have a simultaneously spread collection, it remains to show the
corresponding set must have roughly as many skew corners as a random set of
the same density. This section will focus on proving the following theorem.

######  Theorem 3.2.

Let $\varepsilon\in(0,1)$. For a collection
$\\{A_{g}\\}_{g\in\mathbb{F}_{q}^{n}}$ of subsets of $\mathbb{F}_{q}^{n}$ with
$\sum_{g\in\mathbb{F}_{q}^{n}}|A_{g}|\geq 2^{-{d}}|\mathbb{F}_{q}^{n}|^{2}$,
let $F=\sum_{g\in\mathbb{F}_{q}^{n}}1_{A_{g}}\circ 1_{A_{g}+g}$,
$F^{\prime}=\sum_{g\in\mathbb{F}_{q}^{n}}1_{A_{g}}\circ 1_{A_{g}}$, and
$D\colon\mathbb{F}_{q}^{n}\to\mathbb{R}_{\geq 0}$ be given by $D(x)=|A_{x}|$.
Then either

  1. 1.

$|\langle\mu_{F},\mu_{D}\rangle-1|\leq\varepsilon$, or

  2. 2.

There exists a subspace $V$ of co-dimension $O_{\varepsilon}(d^{8})$ such that
$\|\mu_{F^{\prime}}\ast\mu_{V}\|_{\infty}\geq 1+\frac{1}{32}\varepsilon$.

The proof of Theorem 1.2 follows from Theorem 3.2. Namely, if our collection
of sets $\\{A_{g}\\}_{g\in G}$ admits no collective density increment, and it
is sufficiently dense, then it must contain roughly as many skew corners as a
random set.

###### Proof of Theorem 1.2 from Theorem 3.2.

Let $A\subseteq\mathbb{F}_{q}^{n}\times\mathbb{F}_{q}^{n}$ be skew corner-free
with $|A|=2^{-d}|\mathbb{F}_{q}^{n}|^{2}$, and define the collection
$\\{A_{g}\\}_{g\in\mathbb{F}_{q}^{n}}$ by $A_{g}=\\{y:(g,y)\in A\\}$. By
Cauchy-Schwarz, we have $\sum|A_{g}|^{2}\geq 2^{-2d}|\mathbb{F}_{q}^{n}|^{3}$,
so applying Lemma 3.1 with $\\{A_{g}\\}_{g\in\mathbb{F}_{q}^{n}}$,
$\varepsilon\coloneqq 1/128$, $d\coloneqq 2d$, and $r>0$ to be determined
later yields a collection of sets $\\{(A_{g+w}-x_{g+w})\cap V\\}_{g\in V}$,
where $V\subseteq\mathbb{F}_{q}^{n}$ is a co-dimension $O(dr)$ subspace and
$\\{x_{g}\\}_{g\in\mathbb{F}_{q}^{n}},w\in\mathbb{F}_{q}^{n}$ are shifts. For
brevity, define $A^{\prime}_{g}\coloneqq(A_{g+w}-x_{g+w})\cap V$ and
$A^{\prime}\coloneqq\\{(g,y):g\in V,y\in A^{\prime}_{g}\\}\subseteq V\times
V$. Note that by 2.3, $A$ has at least as many skew corners as $A^{\prime}$,
$|A^{\prime}|\geq 2^{-2d}|V|^{2}$, and $\\{A^{\prime}_{g}\\}_{g\in V}$ is
$(r,1+1/128)$-simultaneously spread in $V$.

Apply Theorem 3.2 with $\varepsilon\coloneqq 1/2$ to the new collection, and
set $r=O(d^{8})$ to be larger than the co-dimension bound in the second
conclusion. If $|\langle\mu_{F},\mu_{D}\rangle-1|\leq 1/2$, Lemma 2.5 implies
$A^{\prime}$ contains at least

$\frac{1}{2}\cdot\frac{|A^{\prime}|^{3}}{|V|^{2}}\geq 2^{-6d-1}|V|^{4}\geq
2^{-\Omega(d^{9})}|\mathbb{F}_{q}^{n}|^{4}$

skew corners. Since there are at most $|\mathbb{F}_{q}^{n}|^{3}$ trivial skew
corners in $A^{\prime}$, we are done after rearrangement. Otherwise, there
exists a subspace $V$ of co-dimension $\ell=O(d^{8})$, with $\ell<r$, such
that $\|\mu_{F^{\prime}}\ast\mu_{V}\|_{\infty}\geq 1+1/64$. By Lemma 2.19,
this contradicts the fact that $\\{A^{\prime}_{g}\\}_{g\in V}$ is
$(r,1+1/128)$-simultaneously spread. ∎

The proof of Theorem 3.2 follows from five major steps, which we briefly
sketch. Throughout, let $F=\sum_{g}1_{A_{g}}\circ 1_{A_{g}+g}$,
$F^{\prime}=\sum_{g}1_{A_{g}}\circ 1_{A_{g}}$, and $D(x)=|A_{x}|$.

  1. 1.

Non-uniformity (Section 3.2.1) – If there are few skew corners (i.e.,
$|\langle\mu_{F},\mu_{D}\rangle-1|>\varepsilon$), then Hölder’s inequality
implies that $\|\mu_{F}-1\|_{p}\geq\varepsilon/2$ for $p=O(d)$.

  2. 2.

Unbalancing (Section 3.2.2) – We then show it suffices to consider the
spectrally non-negative $F^{\prime}$, which we use to prove
$\|\mu_{F^{\prime}}\|_{p^{\prime}}\geq 1+\varepsilon/4$ for some
$p^{\prime}=O_{\varepsilon}(p)$.

  3. 3.

Dependent random choice (Section 3.2.3) – From here, we rely on a known
application of dependent random choice to find two relatively dense sets
$M_{1},M_{2}$ whose difference convolution correlates well with elements of
noticeable upward deviation from $F^{\prime}$’s mean. That is,
$\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq 1-\varepsilon/32$, where
$S=\\{x:\mu_{F^{\prime}}(x)>1+\varepsilon/8\\}$.

  4. 4.

Almost periodicity (Section 3.2.4) – Next, we use an almost periodicity result
of [22] to show there exists a subspace $V$ of co-dimension
$O_{\varepsilon}(d^{8})$ such that
$\langle\mu_{V}\ast\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq
1-\varepsilon/16$.

  5. 5.

Combining steps (Section 3.2.5) – Putting these results together yields the
second conclusion of Theorem 3.2.

These are essentially the same steps given in [8], which is an excellent
exposition and simplification of [13]. Moreover, we are able to either black-
box or closely follow the proofs of many of their results, highlighting the
relationship between arithmetic progressions and skew corners.

####  3.2.1 Non-uniformity

The following lemma will allow us to argue that if there are very few skew
corners, then $\|\mu_{F}-1\|_{p}\geq\varepsilon/2$.

######  Lemma 3.3.

Let $\varepsilon>0$ and $f\colon G\to\mathbb{R}$. If $\\{A_{g}\\}_{g\in G}$ is
a collection of subsets of $G$ where $\sum_{g\in G}|A_{g}|\geq 2^{-d}|G|^{2}$,
and $D\colon G\to\mathbb{R}_{\geq 0}$ is given by $D(x)=|A_{x}|$, then either

  1. 1.

$|\langle\mu_{f},\mu_{D}\rangle-1|\leq\varepsilon$ or

  2. 2.

$\|\mu_{f}-1\|_{p}\geq\varepsilon/2$ for an integer $p=O(d)$.

###### Proof.

If (1) fails, then by Hölder’s inequality, we have for any $p\geq 1$ that

$\varepsilon<\left|\langle\mu_{f}-1,\mu_{D}\rangle\right|\leq\|\mu_{f}-1\|_{p}\|\mu_{D}\|_{1+\frac{1}{p-1}}\leq\|\mu_{f}-1\|_{p}\|\mu_{D}\|_{\infty}^{1/p}\|\mu_{D}\|_{1}^{1-1/p}=\|\mu_{f}-1\|_{p}\|\mu_{D}\|_{\infty}^{1/p}.$

Note that $\|\mu_{D}\|_{\infty}\leq 2^{d}$, since $D(x)\leq|G|$ and
$\mathbb{E}[D]\geq 2^{-d}|G|$. Setting $p=\lceil{d}\rceil$ yields (2). ∎

####  3.2.2 Unbalancing

The next lemma will allow us to consider the function
$F^{\prime}=\sum_{g}1_{A_{g}}\circ 1_{A_{g}}$ rather than
$F=\sum_{g}1_{A_{g}}\circ 1_{A_{g}+g}$.

######  Lemma 3.4.

Let $p\geq 1$ be an integer and $\\{f_{g}\\}_{g\in S}$ a collection of real-
valued functions on $G$ indexed by some set $S\subseteq G$, we have

$\left\|\sum_{g\in S}f_{g}\circ f_{g}\right\|_{p}\geq\left\|\sum_{g\in
S}f_{g}\circ f_{g}^{g}\right\|_{p}$

where $f_{g}^{g}$ denotes the function $f_{g}^{g}(x)=f_{g}(x-g)$.

###### Proof.

We have

$\left\|\sum_{g\in S}f_{g}\circ
f_{g}^{g}\right\|_{p}^{p}=\sum_{\alpha_{1}+\dots+\alpha_{p}=0}\prod_{i=1}^{p}\left(\sum_{g\in
S}|\widehat{f}_{g}(\alpha_{i})|^{2}\cdot\chi_{\alpha_{i}}(g)\right)\leq\sum_{\alpha_{1}+\dots+\alpha_{p}=0}\prod_{i=1}^{p}\left(\sum_{g\in
S}|\widehat{f}_{g}(\alpha_{i})|^{2}\right)=\left\|\sum_{g\in S}f_{g}\circ
f_{g}\right\|_{p}^{p}.$

∎

The merit of working with $F^{\prime}$ is that it is spectrally non-negative,
so all its odd moments are non-negative. Kelley and Meka [13] show that if a
random variable $X$ admits non-negative odd moments as well as deviations from
uniform in the $k$-norm, then $X+1$ must also admit strong deviations upwards
from uniform. The utility of this lemma comes when $X$ is set to the mean zero
part of a function $f$, namely $f_{0}\coloneqq
f-\operatorname{\mathbb{E}}[f]$. If $\operatorname{\mathbb{E}}[f_{0}^{k}]\geq
0$ for odd $k$, then deviations from uniform in $f_{0}$ imply upwards
deviations from uniform in $f$. In particular, when $f=1_{A}\circ 1_{A}$ is a
convolution, or the sum of convolutions, we will be able to extract
information about $A$ from $f$’s upwards deviations.

######  Lemma 3.5 ([L]emma 7).

bloom2023kelley] Let $\varepsilon\in(0,1)$ and $\nu\colon G\to\mathbb{R}_{\geq
0}$ be some probability measure such that $\widehat{\nu}\geq 0$. Let $f\colon
G\to\mathbb{R}$ be such that $\widehat{f}\geq 0$. If
$\|f\|_{p(\nu)}\geq\varepsilon$ for some $p\geq 1$, then
$\|f+1\|_{p^{\prime}(\nu)}\geq 1+\varepsilon/2$ for some integer
$p^{\prime}=O_{\varepsilon}(p)$.

Note that we will only apply Lemma 3.5 when $\varepsilon$ is a constant, so
the exact dependence on $\varepsilon$ is inconsequential. Combining the
previous two lemmas, we obtain the following corollary.

######  Corollary 3.6.

Let $\varepsilon\in(0,1)$, $F=\sum_{g\in G}1_{A_{g}}\circ 1_{A_{g}+g}$,
$F^{\prime}=\sum_{g\in G}1_{A_{g}}\circ 1_{A_{g}}$, where $\\{A_{g}\\}_{g\in
G}$ is a collection of subsets of $G$. If $\|\mu_{F}-1\|_{p}\geq\varepsilon$
for some integer $p\geq 1$, then $\|\mu_{F^{\prime}}\|_{p^{\prime}}\geq
1+\varepsilon/2$ for some integer $p^{\prime}=O_{\varepsilon}(p)$.

###### Proof.

Let $\alpha_{g}=|A_{g}|/|G|$ and $\alpha=\sum_{g\in G}\alpha_{g}^{2}$, so that
$\frac{1}{\alpha}F=\mu_{F}$ and $\frac{1}{\alpha}F^{\prime}=\mu_{F^{\prime}}$.
Setting $f_{g}=1_{A_{g}}-\alpha_{g}$, we have

$\sum_{g\in G}f_{g}\circ f_{g}=\sum_{g\in
G}\left(1_{A_{g}}-\alpha_{g}\right)\circ\left(1_{A_{g}}-\alpha_{g}\right)=\sum_{g\in
G}1_{A_{g}}\circ 1_{A_{g}}-\alpha_{g}^{2}=F^{\prime}-\alpha.$

Similarly, we have

$\sum_{g\in G}f_{g}\circ f^{g}_{g}=\sum_{g\in
G}\left(1_{A_{g}}-\alpha_{g}\right)\circ\left(1_{A_{g}}^{g}-\alpha_{g}\right)=\sum_{g\in
G}1_{A_{g}}\circ 1_{A_{g}+g}-\alpha_{g}^{2}=F-\alpha.$

If we apply Lemma 3.4 with $S\coloneqq G$, this gives
$\|\mu_{F^{\prime}}-1\|_{p}\geq\varepsilon$. Since $\mu_{F^{\prime}}-1$ is
spectrally non-negative, we can apply Lemma 3.5 to obtain
$\|\mu_{F^{\prime}}\|_{p^{\prime}}\geq 1+\varepsilon/2$ for some integer
$p^{\prime}=O_{\varepsilon}(p)$. ∎

####  3.2.3 Dependent random choice

At this point, we can assume we are working with a sum of difference
convolutions $F^{\prime}=\sum_{g\in G}1_{A_{g}}\circ 1_{A_{g}}$ which admits
upwards deviations from uniform in an appropriate $p$-norm. We will want to
extract information about the collection $\\{A_{g}\\}_{g\in G}$ itself from
$F^{\prime}$. It will be useful for us to find a “robust witness” to upward
deviations from the mean. One can view a robust witness as being a convolution
which correlates well with the set of points on which $F^{\prime}$ has a large
deviation upwards. We will need the following lemma by Bloom and Sisask [8]
using dependent random choice (originally dubbed sifting by Kelley and Meka
[13]).

######  Lemma 3.7 ([8, Lemma 8]).

Let $\varepsilon,\delta\in(0,1)$ and $p\geq 1$ be an integer. Let
$B_{1},B_{2}\subseteq G$, and let $\nu=\mu_{B_{1}}\circ\mu_{B_{2}}$. For any
finite set $A\subseteq G$, if

$S=\\{x\in
G:(\mu_{A}\circ\mu_{A})(x)>(1-\varepsilon)\|\mu_{A}\circ\mu_{A}\|_{p(\nu)}\\},$

then there are $M_{1}\subseteq B_{1}$ and $M_{2}\subseteq B_{2}$ such that

$\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq
1-\delta\quad\text{and}\quad\min\left(\mu_{B_{1}}(M_{1}),\mu_{B_{2}}(M_{2})\right)\geq\left(\operatorname{\mathbb{E}}[1_{A}]\cdot\|\mu_{A}\circ\mu_{A}\|_{p(\nu)}\right)^{2p+O_{\varepsilon,\delta}(1)}.$

As with the previous lemma (Lemma 3.5), we will only apply Lemma 3.7 for
constant $\varepsilon$ and $\delta$, so we will not be concerned with the
precise dependency on these variables.

In the 3AP setting, this lemma is enough to obtain a robust witness to $A*A$
being far from uniform. Since we are working with a collection of sets
$\\{A_{g}\\}_{g\in G}$, we will encode our collection into a large set
$A\subseteq G\times G$ while preserving the relevant properties and apply
sifting there. Despite the lemma being stated for a single set, we are able to
appropriately encode our collection to apply it. First, we prove sifting for
an arbitrary Abelian group $G$, then we apply it specifically to the case of
$\mathbb{F}_{q}^{n}$. Later, we will apply this result to
$G=\mathbb{Z}/N\mathbb{Z}$ as well.

######  Lemma 3.8.

Let $\varepsilon,\delta\in(0,1)$ and $p\geq 1$ be an integer. Additionally,
let $B_{1},B_{2}\subseteq G$, $\nu=\mu_{B_{1}}\circ\mu_{B_{2}}$, and
$f=\sum_{g\in C}1_{A_{g}}\circ 1_{A_{g}}$, where $\\{A_{g}\\}_{g\in C}$ is a
collection of subsets of $G$ indexed by $C$ with $\sum_{g\in C}|A_{g}|\geq
2^{-{d}}|G||C|$. If

$S=\\{x\in G:\mu_{f}(x)>(1-\varepsilon)\|\mu_{f}\|_{p(\nu)}\\},$

then there are $M_{1}\subseteq B_{1}$ and $M_{2}\subseteq B_{2}$ such that

$\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq
1-\delta\quad\text{and}\quad\min(\mu_{B_{1}}(M_{1}),\mu_{B_{2}}(M_{2}))\geq\left(2^{-d}\|\mu_{f}\|_{p(\nu)}\right)^{O_{\varepsilon,\delta}(p)}.$

###### Proof.

Let $H=G\times G,L=\\{0\\}\times G$, $B_{1}^{\prime}=\\{0\\}\times B_{1}$ and
$B_{2}^{\prime}=\\{0\\}\times B_{2}$. Additionally, let
$\pi=\mu_{B_{1}^{\prime}}\circ\mu_{B_{2}^{\prime}}$, and note that $\pi$ is
supported on $L$. We embed our collection into a single set $A=\\{(g,y)\mid
g\in C,y\in A_{g}\\}$ in $H$, and define

$S=\\{x\in
L:(\mu_{A}\circ\mu_{A})(x)>(1-\varepsilon)\|\mu_{A}\circ\mu_{A}\|_{p(\pi)}\\}.$

We note that it suffices to define $S$ for $x\in L$ (as opposed to $H$), since
$L$ contains the support of $\pi$. Applying Lemma 3.7, we obtain
$M_{1}\subseteq B^{\prime}_{1}$ and $M_{2}\subseteq B^{\prime}_{2}$, such that

$\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle_{H}\geq
1-\delta\quad\text{and}\quad\min\left(\mu_{B^{\prime}_{1}}(M_{1}),\mu_{B^{\prime}_{2}}(M_{2})\right)\geq\left(\operatorname{\mathbb{E}}[1_{A}]\cdot\|\mu_{A}\circ\mu_{A}\|_{p(\pi)}\right)^{O_{\varepsilon,\delta}(p)}.$

Observe that for $x=(0,y)\in L$, we have

$(1_{A}\circ 1_{A})(x)=\mathop{\operatorname{\mathbb{E}}}_{z\in
H}1_{A}(z)1_{A}(x+z)=\frac{1}{|G|^{2}}\sum_{g\in C}\sum_{z\in
G}1_{A_{g}}(z)1_{A_{g}}(y+z)=\frac{1}{|G|}\sum_{g\in C}(1_{A_{g}}\circ
1_{A_{g}})(y)=\frac{1}{|G|}f(y).$

In particular, $(\mu_{A}\circ\mu_{A})(x)=\zeta\cdot\mu_{f}(y)$, where

$\zeta=\frac{\operatorname{\mathbb{E}}_{G}[f]}{\operatorname{\mathbb{E}}_{H}[1_{A}]^{2}\cdot|G|}=\frac{|G|\cdot\sum_{g\in
C}|A_{g}|^{2}}{|\sum_{g\in C}A_{g}|^{2}}\geq\frac{|G|}{|C|},$ (2)

with the final inequality by Cauchy-Schwarz. Similarly, we have

$\pi(x)=(\mu_{B_{1}^{\prime}}\circ\mu_{B_{2}^{\prime}})(x)=\frac{|H|^{2}}{|B_{1}^{\prime}||B_{2}^{\prime}|}\cdot(1_{B_{1}^{\prime}}\circ
1_{B_{2}^{\prime}})(x)=\frac{|G|^{4}}{|B_{1}||B_{2}|}\cdot\frac{1}{|G|}(1_{B_{1}}\circ
1_{B_{2}})(y)=|G|(\mu_{B_{1}}\circ\mu_{B_{2}})(y)=|G|\nu(y).$

Recalling that $L$ contains the support of $\pi$, we can rewrite $S$ as
$\left\\{(0,y)\in L:\mu_{f}(y)>(1-\varepsilon)\|\mu_{f}\|_{p(\nu)}\right\\}$.

We would like to verify the inner product over $G$ satisfies the conclusion of
the theorem. Let $\alpha_{1}=|M_{1}|/|H|$ and $\alpha_{2}=|M_{2}|/|H|$.
Unraveling the definition of
$\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle$, we have

$\displaystyle\operatorname{\mathbb{E}}_{x\in
H}(\mu_{M_{1}}\circ\mu_{M_{2}})(x)1_{S}(x)$
$\displaystyle=\frac{1}{|H|}\sum_{x\in H}\left(\frac{1}{|H|}\sum_{y\in
H}\mu_{M_{1}}(y)\mu_{M_{2}}(x+y)\right)1_{S}(x)$
$\displaystyle=\frac{1}{|G|^{2}}\sum_{x\in H}\left(\frac{1}{|G|^{2}}\sum_{y\in
H}\frac{1_{M_{1}}(y)}{\alpha_{1}}\cdot\frac{1_{M_{2}}(x+y)}{\alpha_{2}}\right)1_{S}(x)$
$\displaystyle=\frac{1}{|G|^{2}}\sum_{x\in L}\left(\sum_{y\in
L}\frac{1_{M_{1}}(y)}{\alpha_{1}|G|}\cdot\frac{1_{M_{2}}(x+y)}{\alpha_{2}|G|}\right)1_{S}(x)$
(since $M_{1},M_{2}\subseteq L$) $\displaystyle=\frac{1}{|G|}\sum_{x\in
L}\left(\frac{1}{|G|}\sum_{y\in
L}\frac{1_{M_{1}}(y)}{\operatorname{\mathbb{E}}_{L}[M_{1}]}\cdot\frac{1_{M_{2}}(x+y)}{\operatorname{\mathbb{E}}_{L}[M_{2}]}\right)1_{S}(x).$

Since $L\cong G$, we can interpret $M_{1},M_{2},$ and $S$ as subsets of $G$ to
obtain $\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle_{G}\geq 1-\delta$.
Similarly, we can interpret $M_{1}\subseteq B_{1}$ and $M_{2}\subseteq B_{2}$.
We conclude by using Equation 2 to deduce

$\min\left(\mu_{B_{1}}(M_{1}),\mu_{B_{2}}(M_{2})\right)\geq\left(\operatorname{\mathbb{E}}_{H}[1_{A}]\cdot\zeta\cdot\|\mu_{f}\|_{p(\nu)}\right)^{O_{\varepsilon,\delta}(p)}\geq\left(2^{-d}\|\mu_{f}\|_{p(\nu)}\right)^{O_{\varepsilon,\delta}(p)}.$

For the case where $G=\mathbb{F}_{q}^{n}$, we will not need the same level of
generality.

######  Corollary 3.9.

Let $\varepsilon\in(0,1)$ and $p\geq 1$ be an integer. Additionally, let
$f=\sum_{g\in\mathbb{F}_{q}^{n}}1_{A_{g}}\circ 1_{A_{g}}$ where
$\\{A_{g}\\}_{g\in\mathbb{F}_{q}^{n}}$ is a collection of subsets of
$\mathbb{F}_{q}^{n}$ with $\sum_{g\in\mathbb{F}_{q}^{n}}|A_{g}|\geq
2^{-{d}}|\mathbb{F}_{q}^{n}|^{2}$. If $\|\mu_{f}\|_{p}\geq 1+\varepsilon$ and
$S=\\{x:\mu_{f}(x)>1+\varepsilon/2\\}$, then there are
$M_{1},M_{2}\subseteq\mathbb{F}_{q}^{n}$ both of density at least
$2^{-O_{\varepsilon}(dp)}$ such that

$\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq 1-\frac{\varepsilon}{8}.$

###### Proof.

Apply Lemma 3.8 with $C,B_{1},B_{2}\coloneqq\mathbb{F}_{q}^{n}$,
$\varepsilon\coloneqq\varepsilon/4$, and $\delta\coloneqq\varepsilon/8$. ∎

####  3.2.4 Almost periodicity

At this point, we have obtained a robust witness to the non-uniformity of
$F^{\prime}$. Namely, we have two dense sets $M_{1},M_{2}$ whose convolution
$M_{1}\ast M_{2}$ correlates well with the points where $F^{\prime}$ has
upwards deviations. We will want to convert our robust witness into a subspace
$V$ on which our collection $\\{A_{g}\\}_{g\in\mathbb{F}_{q}^{n}}$ admits a
collective density increment. Kelley and Meka [13] originally used a result of
Sanders [20]; we will follow [8] in using the following theorem to find a
large subspace $V$ which correlates well with the upwards deviations of
$F^{\prime}$ via the robust witness we found in the previous step.

######  Theorem 3.10 ([22, Theorem 3.2]).

Let $\varepsilon\in(0,1)$. If $M_{1},M_{2},S\subseteq\mathbb{F}_{q}^{n}$ are
such that $M_{1}$ and $M_{2}$ both have density at least $2^{-d}$, then there
is a subspace $V$ of co-dimension $O_{\varepsilon}(d^{4})$ such that

$|\langle\mu_{V}\ast\mu_{M_{1}}\ast\mu_{M_{2}},1_{S}\rangle-\langle\mu_{M_{1}}\ast\mu_{M_{2}},1_{S}\rangle|\leq\varepsilon.$

######  Corollary 3.11.

Let $\varepsilon\in(0,1)$, and let $M_{1},M_{2},S\subseteq\mathbb{F}_{q}^{n}$
be such that $M_{1}$ and $M_{2}$ both have density at least $2^{-d}$. If

$\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq 1-\frac{\varepsilon}{2},$

then there is a subspace $V$ of co-dimension $O_{\varepsilon}(d^{4})$ such
that

$\langle\mu_{V}\ast\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq
1-\varepsilon.$

###### Proof.

Apply Theorem 3.10 with $\varepsilon\coloneqq\varepsilon/2,M_{1}\coloneqq
M_{1},M_{2}\coloneqq-M_{2}$, and $S\coloneqq S$. ∎

####  3.2.5 Combining steps

All that remains to prove Theorem 3.2 (restated below) is to combine the prior
steps. See 3.2

###### Proof.

If (1) does not hold, we apply Lemma 3.3 to arrive at
$\|\mu_{F}-1\|_{p}\geq\varepsilon/2$ for integer $p=O(d)$. Corollary 3.6
implies $\|\mu_{F^{\prime}}\|_{p^{\prime}}\geq 1+\varepsilon/4$ for some
integer $p^{\prime}=O_{\varepsilon}(p)$. Let
$S=\\{x\in\mathbb{F}_{q}^{n}:\mu_{F^{\prime}}(x)>1+\varepsilon/8\\}$. We apply
Corollary 3.9 to obtain $M_{1},M_{2}\subseteq\mathbb{F}_{q}^{n}$ both of
density at least $2^{-O_{\varepsilon}(d^{2})}$ such that

$\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq
1-\frac{\varepsilon}{32}.$

We then apply Corollary 3.11 with $\varepsilon\coloneqq\varepsilon/16$ and
$d\coloneqq O_{\varepsilon}(d^{2})$ to find a subspace $V$ with co-dimension
at most $O_{\varepsilon}(d^{8})$ such that

$\langle\mu_{V}\ast\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq
1-\frac{\varepsilon}{16}.$

By the definition of $S$, we have

$1+\frac{\varepsilon}{32}\leq\left(1+\frac{\varepsilon}{8}\right)\left(1-\frac{\varepsilon}{16}\right)\leq\langle\mu_{V}\ast\mu_{M_{1}}\circ\mu_{M_{2}},\mu_{F^{\prime}}\rangle\leq\|\mu_{F^{\prime}}\ast\mu_{V}\|_{\infty}\|\mu_{M_{1}}\circ\mu_{M_{2}}\|_{1}=\|\mu_{F^{\prime}}\ast\mu_{V}\|_{\infty}.$

##  4 The integer case

In this section, we prove the following theorem.

######  Theorem 4.1.

Let $G$ be a finite Abelian group. Any skew corner-free subset of $G\times G$
has size at most

$\exp\left\\{-\Omega\left(\log^{1/12}|G|\right)\right\\}\cdot|G|^{2}.$

Note that Theorem 4.1 immediately implies Theorem 1.1 (restated below), since
embedding $A\subseteq[n]\times[n]$ in
$\mathbb{Z}/N\mathbb{Z}\times\mathbb{Z}/N\mathbb{Z}$ for $N=2n$ does not
change the number of skew corners or (asymptotic) density,

See 1.1

All the main ideas of Theorem 4.1’s proof are the same as those in Section 3,
although some additional technicalities arise from replacing subspaces with
regular Bohr sets. (It may be helpful to revisit Section 2.2.) For the
remainder of the discussion, we will assume we are working with
$G=\mathbb{Z}/N\mathbb{Z}$, but everything we are doing works over any finite
Abelian group.

We will aim to replicate what we did in the finite field case when working
with $\mathbb{Z}/N\mathbb{Z}$. The main issue is that there are potentially no
nontrivial subgroups to work with over $\mathbb{Z}/N\mathbb{Z}$. This ends up
not being so much of an issue, since we can replace subgroups with regular
Bohr sets, which approximate subgroups in many important ways. And, not unlike
the case over $\mathbb{F}_{q}^{n}$, we will be able to argue that if a
collection $\\{A_{g}\\}_{g\in G}$ contains very few skew corners, then there
must be some collective density increment on a Bohr set $B$.

In the finite field case, when we found a subspace $V$ with a collective
density increment, we could restrict our attention to $V$ since
$V\cong\mathbb{F}_{q}^{\dim(V)}$. Here, we will not have this luxury, since
Bohr sets are not necessarily subgroups! We will have to maintain our ambient
group as $\mathbb{Z}/N\mathbb{Z}$, all while restricting our sets
$\\{A_{g}\\}_{g\in G}$ to smaller and smaller Bohr sets. Thus, we will work
with functions defined over $\mathbb{Z}/N\mathbb{Z}$. The supports of these
functions, however, will only be contained in some Bohr set $R$. So, when
taking norms and inner products, we will want to zoom in on the action by
taking everything with respect to a certain measure $\nu$. For the most part,
$\nu$ will be some convolution of dilates of $R$, which we will be able to
control since Bohr sets behave well under convolutions. Dealing with these
technicalities surrounding Bohr sets and nonuniform measures forms the major
differences between working over $\mathbb{F}_{q}^{n}$ and
$\mathbb{Z}/N\mathbb{Z}$, but the overall proof structures are conceptually
the same.

###  4.1 Obtaining simultaneous spreadness

As in the finite field case, we will want to perform a density increment
argument on the rows and columns of $A\subseteq G\times G$ until we obtain a
collection $\\{A_{g}\\}_{g\in C}$ of subsets of $R$ for regular Bohr sets
$R,C\subseteq G$ which is simultaneously spread. For technical reasons, we
will want $C$ to be a translate of a dilate of $R$. This will end up being
necessary when we prove Lemma 4.4 and Lemma 4.5.

Another difference between the Abelian group case and the finite field case
comes from our definition of simultaneous spreadness. In particular, if our
sets $\\{A_{g}\\}_{g\in C}$ are each contained in $R$, then the Bohr set $B$
on which we find a density increment must be a sub-Bohr set of $R$, which to
recall we notate by $B\leq R$. The reader will notice in the proof of Lemma
4.2 that this becomes necessary when trying to obtain $B_{\rho}\subseteq
R_{\rho}$ from $B\leq R$ for some $\rho\in(0,1)$. If we try to start with an
assumption of the form $B\subseteq R$, it is not true in general that
$B_{\rho}\subseteq R_{\rho}$.

Overall, the proof idea is conceptually the same as Lemma 3.1 in the finite
field case. The main differences come from ensuring that the index $C$ is a
translate of an appropriate dilate of $R$.

######  Lemma 4.2.

Let $\varepsilon,\delta\in(0,1),r\geq 1,d\geq 0$, and $\\{A_{g}\\}_{g\in G}$
be a collection of subsets of $G$ with $\sum_{g\in G}|A_{g}|^{2}\geq
2^{-d}|G|^{3}$. Then there exists a regular Bohr set $R\subseteq G$ of rank
$\mathrm{rk}(R)\leq O(dr/\varepsilon)$ and density
$\mu(R)\geq\delta^{O(d/\varepsilon)}$, a shift of a regular Bohr set
$C=R_{\rho}+w$ where
$\rho=\left(\varepsilon^{2}/rd2^{d}\right)^{O(d/\varepsilon)}$ and $w\in G$,
and shifts $\\{x_{g}\\}_{g\in C}$ with $x_{g}\in G$ such that

  1. 1.

The collection $\\{\left(A_{g}-x_{g}\right)\cap R\\}_{g\in C}$ is
$(r,\delta,1+\varepsilon)$-simultaneously spread in $R$, and

  2. 2.

$\sum_{g\in C}|\left(A_{g}-x_{g}\right)\cap R|^{2}\geq 2^{-d}|R|^{2}|C|$.

###### Proof.

We proceed by a similar density increment argument as in the finite field case
(Lemma 3.1), where regular Bohr sets replace the role of vector spaces.

Let $B$ be a regular Bohr set and $\\{A_{g}\\}_{g\in B_{\sigma}+w}$ be a
collection of subsets of $B$ indexed by $B_{\sigma}+w$, where initially $B=G$
and $\sigma=1$. We will assume $w=0$ for simplicity; the proof is essentially
the same for nonzero shifts. If $\\{A_{g}\\}_{g\in B_{\sigma}}$ is not
$(r,\delta,1+\varepsilon)$-simultaneously spread in $B$, then by definition,
there exists a regular Bohr set $B^{\prime}\leq B$ with rank
$\mathrm{rk}(B^{\prime})\leq\mathrm{rk}(B)+r$ and density
$\mu(B^{\prime})\geq\delta\mu(B)$, and shifts $\\{x_{g}\\}_{g\in B_{\sigma}}$
in $G$, such that for $A^{\prime}_{g}\coloneqq(A_{g}-x_{g})\cap B^{\prime}$ we
have

$\sum_{g\in
B_{\sigma}}\left(\frac{|A^{\prime}_{g}|}{|B^{\prime}|}\right)^{2}\geq(1+\varepsilon)\sum_{g\in
B_{\sigma}}\left(\frac{|A_{g}|}{|B|}\right)^{2}.$ (3)

From here, the proof proceeds by filtering the index set of our collection to
be some translate of a dilate of $B^{\prime}$. In other words, we will
restrict our index set to some translate of $B^{\prime}_{\sigma^{\prime}}$
where $\sigma^{\prime}$ will be chosen later. Consider the function
$f(g)\coloneqq(|A^{\prime}_{g}|/|B^{\prime}|)^{2}$. Then,

$\frac{1}{|B_{\sigma}|}\sum_{g\in
B_{\sigma}}\left(\frac{|A^{\prime}_{g}|}{|B^{\prime}|}\right)^{2}=\langle\mu_{B_{\sigma}},f\rangle\quad\text{
and }\quad\frac{1}{|B_{\sigma}||B^{\prime}_{\sigma^{\prime}}|}\sum_{g\in
B_{\sigma}}\sum_{h\in
B^{\prime}_{\sigma^{\prime}}}\left(\frac{|A^{\prime}_{g+h}|}{|B^{\prime}|}\right)^{2}=\langle\mu_{B_{\sigma}}\ast\mu_{B^{\prime}_{\sigma^{\prime}}},f\rangle.$

Note that $\langle\mu_{B_{\sigma}},f\rangle\geq 2^{-d}$, since the density of
our collection has only increased from the initial assumption that $\sum_{g\in
G}|A_{g}|^{2}\geq 2^{-d}|G|^{3}$.

We want to apply Corollary 2.15 to $B_{\sigma}$ and
$B^{\prime}_{\sigma^{\prime}}$. Set $\sigma^{\prime}=c\sigma\tau$ where we
will choose $\tau$ later, and $c\in[1/2,1]$ according to Lemma 2.11 so that
$B^{\prime}_{\sigma^{\prime}}$ is regular. Since $B^{\prime}\leq B$, 2.9
implies the inclusion $B^{\prime}_{\sigma^{\prime}}\subseteq
B_{\sigma\tau}=(B_{\sigma})_{\tau}$. Applying Corollary 2.15 gives

$\displaystyle\langle\mu_{B_{\sigma}}\ast\mu_{B^{\prime}_{\sigma^{\prime}}},f\rangle$
$\displaystyle\geq\langle\mu_{B_{\sigma}},f\rangle-|\langle\mu_{B_{\sigma}}\ast\mu_{B^{\prime}_{\sigma^{\prime}}}-\mu_{B_{\sigma}},f\rangle|$
$\displaystyle\geq\langle\mu_{B_{\sigma}},f\rangle-O(\tau\cdot\mathrm{rk}(B_{\sigma}))$
(since $\|f\|_{\infty}\leq 1$)
$\displaystyle\geq(1-\varepsilon/4)\langle\mu_{B_{\sigma}},f\rangle$

for $\tau\leq c^{\prime}\varepsilon/2^{d}\mathrm{rk}(B_{\sigma})$ with
constant $c^{\prime}>0$ chosen sufficiently small. By our setting of $\tau$,
we have

$\frac{1}{|B_{\sigma}||B^{\prime}_{\sigma^{\prime}}|}\sum_{g\in
B_{\sigma}}\sum_{h\in
B^{\prime}_{\sigma^{\prime}}}\left(\frac{|A^{\prime}_{g+h}|}{|B^{\prime}|}\right)^{2}\geq(1-\varepsilon/4)\frac{1}{|B_{\sigma}|}\sum_{g\in
B_{\sigma}}\left(\frac{|A^{\prime}_{g}|}{|B^{\prime}|}\right)^{2}.$ (4)

By combining Equation 3 with Equation 4 and averaging, there is some choice of
$g\in B_{\sigma}$ so that

$\frac{1}{|B^{\prime}_{\sigma^{\prime}}|}\sum_{h\in
B^{\prime}_{\sigma^{\prime}}}\left(\frac{|A^{\prime}_{g+h}|}{|B^{\prime}|}\right)^{2}\geq(1-\varepsilon/4)(1+\varepsilon)\frac{1}{|B_{\sigma}|}\sum_{g\in
B_{\sigma}}\left(\frac{|A_{g}|}{|B|}\right)^{2}\geq(1+\varepsilon/2)\frac{1}{|B_{\sigma}|}\sum_{g\in
B_{\sigma}}\left(\frac{|A_{g}|}{|B|}\right)^{2}.$

If our new collection $\\{A^{\prime}_{h}\\}_{h\in
B^{\prime}_{\sigma^{\prime}}+g}$ is not
$(r,\delta,1+\varepsilon)$-simultaneously spread in $B^{\prime}$, we can
iterate this procedure. After $i$ iterations, we obtain Bohr sets
$B^{(i)},C^{(i)}$ and a collection $\\{A_{g}^{(i)}\\}_{g\in C^{(i)}}$ such
that:

  1. 1.

$B^{(i)}$ is a regular sub-Bohr set of $B^{(i-1)}$ of rank at most $i\cdot r$
and density at least $\delta^{i}$.

  2. 2.

Each $C^{(i)}$ is a translate of $B^{(i)}_{\sigma_{i}}$ for
$\sigma_{i}\geq(\tau/2)^{i}$.

  3. 3.

Each $A_{g}^{(i)}$ equals $(A_{g}^{(i-1)}-x_{g}^{(i)})\cap B^{(i)}$ for some
shift $x_{g}^{(i)}$.

  4. 4.

We have

$\frac{1}{|B^{(i)}_{\sigma_{i}}|}\sum_{g\in
C^{(i)}}\left(\frac{|A_{g}^{(i)}|}{|B^{(i)}|}\right)^{2}\geq(1+\varepsilon/2)^{i}\frac{1}{|G|}\sum_{g\in
G}\left(\frac{|A_{g}|}{|G|}\right)^{2}.$

The process must end within $O(d/\varepsilon)$ iterations, since the density
on the right-hand side of (4) cannot exceed 1. This implies that
$\mathrm{rk}(B^{(i)})\leq O(rd/\varepsilon)$ for all $i$, so we can obtain the
claimed bound on the final $\sigma_{i}$ by ultimately choosing
$\tau=c^{\prime\prime}\varepsilon^{2}/(rd2^{d})$ for some constant
$c^{\prime\prime}>0$. ∎

###  4.2 Using simultaneous spreadness

Assuming we have a simultaneously spread collection, it remains to show the
corresponding set must have roughly as many skew corners as a random set of
the same density. This can be viewed as a “structure vs. pseudo-randomness”
result, where we say that either a set $A\times A\subseteq G$ has roughly as
many skew-corners as a random set of the same density, or $A$ admits a type of
density increment on a structured set.

######  Theorem 4.3.

There exists an absolute constant $c>0$ such that the following holds. Let
$\varepsilon\in(0,1)$ and $R\subseteq G$ be a regular Bohr set of rank $r$.
Furthermore, let $\\{A_{g}\\}_{g\in C}$ be a collection of subsets of $R$
indexed by a regular Bohr set $C=R_{\sigma}$ with $\sigma\leq
c\varepsilon/r2^{d}$, where $\sum_{g\in C}|A_{g}|\geq 2^{-d}|R||C|$. Moreover,
let $F=\sum_{g\in C}1_{A_{g}}\circ 1_{A_{g}+g}$ and $F^{\prime}=\sum_{g\in
C}1_{A_{g}}\circ 1_{A_{g}}$, and let $D(x)=|A_{x}|$ when $x\in C$ and 0
otherwise. Then either

  1. 1.

$|\langle\mu_{F},\mu_{D}\rangle-\mu(R)^{-1}|\leq\varepsilon\mu(R)^{-1}$, or

  2. 2.

There exists a sub-Bohr set $B\leq R$ with
$\mathrm{rk}(B)\leq\mathrm{rk}(R)+O_{\varepsilon}(d^{8})$ and
$\mu(B)\geq\delta\mu(R)$ such that

$\|\mu_{F^{\prime}}\ast\mu_{B}\|_{\infty}\geq(1+\varepsilon/80)\mu(R)^{-1},$

where $\delta=\exp\left(-O_{\varepsilon}(r\log(1/\sigma)+rd^{2}+rd\log
r+d^{10})\right)$.

A quick aside on normalization: say for a moment that the $\\{A_{g}\\}_{g\in
C}$ are random subsets of $R$, and imagine we were in the perfectly structured
situation that $R+R=R$. Then, we would expect $\mu_{F}$ to be a very uniform
function supported on $R+C$. Since $C$ is a sufficiently narrow dilate of $R$,
by regularity we can think of the distribution $R+C$ as being “close” to the
uniform distribution on $R$. Thus, we are left with $\mu_{F}$ which is roughly
uniform on $R$, and zero everywhere else. Since $\mu_{F}$ has mean 1 on all of
$G$, we can really think of $\mu_{F}$ as being a uniform function taking
values close to $\mu(R)^{-1}$ on $R$, and zero everywhere else. Making these
structured statements into approximate ones will follow from Bohr set
machinery.

For our application (Theorem 4.1), we will instantiate $\sigma$ to be the
value given by Lemma 4.2, which is smaller than the bound in the hypothesis of
Theorem 4.3. This does not affect our final bound.

###### Proof of Theorem 4.1 from Theorem 4.3.

Let $A\subseteq G\times G$ be skew corner-free with $|A|=2^{-d}|G|^{2}$, and
define the collection $\\{A_{g}\\}_{g\in G}$ by $A_{x}=\\{y:(x,y)\in A\\}$. By
Cauchy-Schwarz, we have $\sum|A_{g}|^{2}\geq 2^{-2d}|G|^{3}$, so applying
Lemma 4.2 with $\\{A_{g}\\}_{g\in G}$, $\varepsilon\coloneqq 1/80$,
$\delta\coloneqq\exp(-cd^{11})$, $d\coloneqq 2d$, and $r\coloneqq
c^{\prime}d^{8}$ for constants $c,c^{\prime}>0$ to be determined later yields
a collection of sets $\\{\left(A_{g}-x_{g}\right)\cap R\\}_{g\in C+w}$, where
$R\subseteq G$ is a regular Bohr set of rank at most $O(d^{9})$ and density
$\mu(R)\geq 2^{-O(d^{12})}$, $C=R_{\rho}$ for $\rho=2^{-O(d^{2})}$ is a
regular Bohr set, and $\\{x_{g}\\}_{g\in C+w},w\in G$ are shifts. Observe that
$\mu(C)\geq 2^{-O(d^{12})}$ by Lemma 2.12.

For brevity, define $A^{\prime}_{g}\coloneqq(A_{g+w}-x_{g+w})\cap R$ for $g\in
C$ and $A^{\prime}\coloneqq\\{(g,y):g\in C,y\in A^{\prime}_{g}\\}\subseteq
C\times R$. Note that by 2.3, $A$ has at least as many skew corners as
$A^{\prime}$, $|A^{\prime}|\geq 2^{-2d}|R||C|$, and
$\\{A^{\prime}_{g}\\}_{g\in C}$ is $(r,\delta,1+\varepsilon)$-simultaneously
spread in $R$.

Apply Theorem 4.3 with $\varepsilon\coloneqq 1/2$ to the new collection, and
set $c^{\prime}$ large enough for $r$ to exceed the rank bound in the second
conclusion. If
$|\langle\mu_{F},\mu_{D}\rangle-\mu(R)^{-1}|\leq\tfrac{1}{2}\mu(R)^{-1}$,
Lemma 2.5 implies $A^{\prime}$ contains at least

$\frac{\mu(R)^{-1}}{2}\cdot\frac{|A^{\prime}|^{3}}{|G|^{2}}\geq
2^{-6d-1}\mu(R)^{2}\mu(C)^{3}|G|^{4}\geq 2^{-O(d^{12})}|G|^{4}$

skew corners. Since there are at most $|G|^{3}$ trivial skew corners in
$A^{\prime}$, we are done after rearrangement. Otherwise, there exists a sub-
Bohr set $B\leq R$ with $\mathrm{rk}(B)\leq\mathrm{rk}(R)+r$ and
$\mu(B)\geq\delta^{\prime}\mu(R)$ such that

$\|\mu_{F^{\prime}}\ast\mu_{B}\|_{\infty}\geq\left(1+\frac{1}{160}\right)\mu(R)^{-1},$

where $\delta^{\prime}=\exp\left(-O(d^{11})\right)$. By Lemma 2.20, this
contradicts the fact that $\\{A^{\prime}_{g}\\}_{g\in C}$ is
$(r,\delta,1+1/80)$-simultaneously spread in $R$, assuming $c$ is large enough
to ensure $\delta<\delta^{\prime}$. ∎

####  4.2.1 Non-uniformity

The following lemma shows that if no corners are present, then we obtain some
non-uniformity on our collection of sets in appropriate $k$-norm. Here, it
will be critical that $C$ is contained in a sufficiently narrow dilate of $R$
so that we can apply Lemma 2.14. This combined with an application of Hölder’s
inequality constitutes most of the proof.

######  Lemma 4.4.

There exists an absolute constant $c>0$ such that the following holds. Let
$\varepsilon>0$ and $\\{A_{g}\\}_{g\in C}$ be a collection of subsets of a
regular Bohr set $R$ of rank $r$, indexed by a regular Bohr set $C=R_{\sigma}$
with $\sigma\leq c\varepsilon/r2^{d}$, where $\sum_{g\in C}|A_{g}|\geq
2^{-d}|R||C|$. Define $\alpha_{g}=|A_{g}|/|G|$ and $\alpha=\sum_{g\in
C}\alpha_{g}^{2}$. Additionally, let $D(x)=|A_{x}|$ when $x\in C$ and 0
otherwise, and let $f=\sum_{g\in C}1_{A_{g}}\circ 1_{A_{g}+g}$. Then either

  1. 1.

$|\langle\mu_{f},\mu_{D}\rangle-\mu(R)^{-1}|\leq\varepsilon\mu(R)^{-1}$ or

  2. 2.

There is some even integer $p=O(d)$ such that

$\left\|\frac{1}{\alpha}\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}+g}-\alpha_{g}\mu_{R+g}\right)\right\|_{p(\mu_{C})}\geq\frac{\varepsilon}{2}\mu(R)^{-1}.$

###### Proof.

Our proof follows closely [8, Proposition 20]. Assume the first conclusion
does not hold, and note that

$\displaystyle\left\langle\frac{1}{\alpha}\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}+g}-\alpha_{g}\mu_{R+g}\right),\mu_{D}\right\rangle$
$\displaystyle=\left(\frac{1}{\alpha}\sum_{g\in C}\left\langle 1_{A_{g}}\circ
1_{A_{g}+g},\mu_{D}\right\rangle-\mu(R)^{-1}\right)$ (5)
$\displaystyle-\left(\frac{1}{\alpha}\sum_{g\in C}\alpha_{g}\langle
1_{A_{g}}\circ\mu_{R+g},\mu_{D}\rangle-\mu(R)^{-1}\right)$ (6)
$\displaystyle-\left(\frac{1}{\alpha}\sum_{g\in
C}\alpha_{g}\langle\mu_{R}\circ 1_{A_{g}+g},\mu_{D}\rangle-\mu(R)^{-1}\right)$
(7) $\displaystyle+\left(\frac{1}{\alpha}\sum_{g\in
C}\alpha_{g}^{2}\langle\mu_{R}\circ\mu_{R+g},\mu_{D}\rangle-\mu(R)^{-1}\right).$
(8)

We will bound the last three terms in magnitude, then apply Hölder’s
inequality to the first term (5) to obtain the second conclusion. Consider the
second term (6); we have

$\displaystyle\frac{1}{\alpha}\sum_{g\in C}\alpha_{g}\langle
1_{A_{g}}\circ\mu_{R+g},\mu_{D}\rangle-\mu(R)^{-1}$
$\displaystyle=\frac{1}{\alpha}\sum_{g\in C}\alpha_{g}\langle
1_{A_{g}},\mu_{R+g}\ast\mu_{-D}\rangle-\mu(R)^{-1}$
$\displaystyle=\frac{1}{\alpha}\sum_{g\in C}\alpha_{g}\langle
1_{A_{g}},\mu_{R}\ast\mu_{-D}^{g}\rangle-\mu(R)^{-1}$
$\displaystyle=\left(\frac{1}{\alpha}\sum_{g\in C}\alpha_{g}\langle
1_{A_{g}},\mu_{R}\rangle\right)+\left(\frac{1}{\alpha}\sum_{g\in
C}\alpha_{g}\langle
1_{A_{g}},\mu_{R}\ast\mu_{-D}^{g}-\mu_{R}\rangle\right)-\mu(R)^{-1}.$ (9)

First, since $A_{g}\subseteq R$, we know that $\langle
1_{A_{g}},\mu_{R}\rangle$ = $\alpha_{g}\mu(R)^{-1}$. Summing over $g\in C$
gives

$\frac{1}{\alpha}\sum_{g\in C}\alpha_{g}\langle
1_{A_{g}},\mu_{R}\rangle=\frac{1}{\alpha}\sum_{g\in
C}\alpha^{2}_{g}\cdot\mu(R)^{-1}=\mu(R)^{-1},$

so the first and third terms of (9) cancel out. We next bound the second term
of (9). Since $\mu_{D}$ is supported on $C=R_{\sigma}$ and $C$ is symmetric,
we have $\mu_{-D}$ is supported on $C$ as well. As $g\in C$, we can infer that
$\mu_{-D}^{g}$ is supported on $C+C\subseteq R_{2\sigma}$. The last point to
note is that $\frac{1}{\alpha}\left(\sum_{g\in C}\alpha_{g}\right)\leq
2^{d}\mu(R)^{-1}$ by Cauchy-Schwarz. We will now use the assumption that
$\sigma\leq c\varepsilon/2^{d}\mathrm{rk}(R)$ for a small enough constant
$c>0$. By Corollary 2.15, we know

$\displaystyle\left|\frac{1}{\alpha}\sum_{g\in C}\alpha_{g}\langle
1_{A_{g}},\mu_{R}\ast\mu_{-D}^{g}-\mu_{R}\rangle\right|$
$\displaystyle\leq\frac{1}{16\alpha}\sum_{g\in C}\alpha_{g}\varepsilon
2^{-d}\leq\frac{\varepsilon}{16}\mu(R)^{-1}.$

Similar reasoning bounds the third (7) and fourth (8) terms by the same
quantity. Finally, let $f_{0}=\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}+g}-\alpha_{g}\mu_{R+g}\right)$.
Combining the above bounds gives

$\left|\langle\mu_{f},\mu_{D}\rangle-\mu(R)^{-1}-\langle\mu_{f_{0}},\mu_{D}\rangle\right|\leq\frac{\varepsilon}{4}\mu(R)^{-1}.$

For simplicity, define $D^{\prime}(x)=D(x)/|R|$, so that
$\|D^{\prime}\|_{\infty}\leq 1$. Note that $\mu_{D}=\mu_{D^{\prime}}$. If the
first conclusion fails, and using the fact that $D^{\prime}$ is supported on
$C$, we have

$\frac{3}{4}\varepsilon\mu(R)^{-1}\leq|\langle\mu_{f_{0}},\mu_{D}\rangle|=|\langle\mu_{f_{0}},\mu_{D^{\prime}}\rangle|=\operatorname{\mathbb{E}}_{C}[D^{\prime}]^{-1}\cdot|\langle\mu_{f_{0}},D^{\prime}\rangle_{\mu_{C}}|.$

An application of Hölder’s inequality, for any $p\geq 1$, gives

$\left|\langle\mu_{f_{0}},D^{\prime}\rangle_{\mu_{C}}\right|\leq\|\mu_{f_{0}}\|_{p(\mu_{C})}\cdot\|D^{\prime}\|_{\left(\frac{p}{p-1}\right)(\mu_{C})}\leq\|\mu_{f_{0}}\|_{p(\mu_{C})}\cdot\|D^{\prime}\|_{\infty}\cdot\|D^{\prime}\|_{1(\mu_{C})}^{1-1/p}.$

We have
$\|D^{\prime}\|_{1(\mu_{C})}=\operatorname{\mathbb{E}}_{C}[D^{\prime}]^{-1}\geq
2^{-d}$. Combining the above inequalities gives

$2^{d/p}\|\mu_{f_{0}}\|_{p(\mu_{C})}\geq\left|\langle\mu_{f_{0}},\mu_{D^{\prime}}\rangle\right|\geq\frac{3}{4}\varepsilon\mu(R)^{-1}.$

Choosing $p$ an even integer so that $2^{d/p}\geq 3/2$ gives the result. ∎

####  4.2.2 Unbalancing

At this point, we have a non-uniformity assumption on the function

$F_{0}=\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}+g}-\alpha_{g}\mu_{R+g}\right),$

and we would like to switch to working with the function
$F^{\prime}=\sum_{g\in C}1_{A_{g}}\circ 1_{A_{g}}$. The reason for this is
mostly technical; $F^{\prime}$ has non-negative Fourier coefficients, while
$F_{0}$ in general may not. There are minor complications that arise when
working with nonuniform measures, which accounts for the main differences
between the following lemma and the corresponding one in the finite field
case.

The goal of this section is to prove the following:

######  Lemma 4.5.

There exist absolute constants $c>0$ such that the following holds. Let
$\varepsilon\in(0,1)$ and $p\geq 2$ an even integer. Furthermore, let
$\\{A_{g}\\}_{g\in C}$ be a collection of subsets of a regular Bohr set $R$ of
rank $r$ indexed by a regular Bohr set $C=R_{\sigma}$ for $\sigma\leq
c\varepsilon/r2^{d}$. Moreover, let $C^{\prime},C^{\prime\prime}\subseteq
C_{\tau}$ both be regular Bohr sets for any $\tau\leq cr^{-1}$, and define
$\alpha_{g}=|A_{g}|/|G|$ and $\alpha=\sum_{g\in C}\alpha_{g}^{2}$. Then

$\left\|\frac{1}{\alpha}\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}+g}-\alpha_{g}\mu_{R+g}\right)\right\|_{p(\mu_{C})}\geq\varepsilon\mu(R)^{-1}$

implies that

$\left\|\frac{1}{\alpha}\sum_{g\in C}1_{A_{g}}\circ
1_{A_{g}}\right\|_{p^{\prime}(\mu_{C^{\prime}}\ast\mu_{C^{\prime\prime}-x})}\geq\left(1+\frac{\varepsilon}{8}\right)\mu(R)^{-1}$

for some shift $x\in G$ and integer $p^{\prime}=O_{\varepsilon}(p)$.

To prove Lemma 4.5, we would like to remove the “shifts” in $F_{0}$ while
maintaining the non-uniformity assumption. As a first step, we would like to
switch to working with the function

$F^{\prime}_{0}=\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right),$

which enjoys the property of being spectrally non-negative. For technical
reasons, we will want to start working with a nonuniform measure which is also
spectrally non-negative, so that we can eventually apply Lemma 3.5. The
following lemma accomplishes both of these goals with little loss in
parameters.

######  Lemma 4.6.

There exists an absolute constant $c>0$ such that the following holds. Let
$p\geq 2$ be an even integer and $\\{f_{g}\\}_{g\in S}$ be a collection of
real-valued functions on $G$ indexed by some set $S\subseteq G$. Additionally,
let $B\subseteq G$ and $B^{\prime},B^{\prime\prime}\subseteq B_{\tau}$ all be
regular Bohr sets for $\tau\leq c\cdot\mathrm{rk}(B)^{-1}$. Then

$\left\|\sum_{g\in S}f_{g}\circ
f_{g}\right\|_{p(\mu_{B^{\prime}}\circ\mu_{B^{\prime}}\ast\mu_{B^{\prime\prime}}\circ\mu_{B^{\prime\prime}})}\geq\frac{1}{2}\left\|\sum_{g\in
S}f_{g}\circ f_{g}^{g}\right\|_{p(\mu_{B})}$

where $f^{g}$ denotes the function $f^{g}(x)=f(x-g)$.

###### Proof.

For simplicity, we will define

$F_{1}\coloneqq\sum_{g\in S}f_{g}\circ f_{g}^{g}\quad\text{and}\quad
F_{2}\coloneqq\sum_{g\in S}f_{g}\circ f_{g}.$

It follows by linearity that for $\gamma\in\widehat{G}$, we have

$\widehat{F_{1}}(\gamma)=\sum_{g\in
S}|\widehat{f_{g}}(\gamma)|^{2}\gamma(g)\quad\text{and}\quad\widehat{F_{2}}(\gamma)=\sum_{g\in
S}|\widehat{f_{g}}(\gamma)|^{2},$

and by the triangle inequality, we have
$|\widehat{F_{1}}(\gamma)|\leq|\widehat{F_{2}}(\gamma)|$.

From here, the proof is almost identical to [8, Proposition 19]. Let
$\nu=\mu_{B^{\prime}}\circ\mu_{B^{\prime}}\ast\mu_{B^{\prime\prime}}\circ\mu_{B^{\prime\prime}}$,
and observe that $\nu$ is supported on $B_{\rho}$ for $\rho=4\tau$.
Additionally, note that $\nu$ is spectrally non-negative, since
$\widehat{\nu}(\gamma)=\widehat{\mu_{B^{\prime}}}(\gamma)^{2}\widehat{\mu_{B^{\prime\prime}}}(\gamma)^{2}$.
Apply Lemma 2.13 to obtain

$\displaystyle\mu_{B}$ $\displaystyle\leq 2\mu_{B_{1+\rho}}\ast\nu.$

Expanding, we have

$\displaystyle\|F_{1}\|_{p(\mu_{B})}^{p}$
$\displaystyle=\operatorname{\mathbb{E}}_{x\in G}\mu_{B}(x)F_{1}(x)^{p}$
$\displaystyle\leq 2\operatorname{\mathbb{E}}_{x\in
G}\left(\mu_{B_{1+\rho}}\ast\nu\right)(x)F_{1}(x)^{p}$
$\displaystyle=2\operatorname{\mathbb{E}}_{t\in
B_{1+\rho}}\operatorname{\mathbb{E}}_{x\in G}\nu(x-t)F_{1}(x)^{p}.$

Recall that $\widehat{f^{p}}=\widehat{f}^{(p)}$, where $\widehat{f}^{(p)}$ is
the $p$-fold convolution of $\widehat{f}$. By averaging, there exists some
$t\in B_{1+\tau}$ such that

$\displaystyle\|F_{1}\|_{p(\mu_{B})}^{p}$ $\displaystyle\leq
2\operatorname{\mathbb{E}}_{x\in G}\nu(x-t)F_{1}(x)^{p}$
$\displaystyle=2\sum_{\gamma\in\widehat{G}}\widehat{\nu}(\gamma)\gamma(-t)\left(\widehat{F_{1}}\right)^{(p)}(\gamma)$
$\displaystyle\leq
2\sum_{\gamma\in\widehat{G}}\widehat{\nu}(\gamma)\left(|\widehat{F_{1}}|\right)^{(p)}(\gamma)$
$\displaystyle\leq
2\sum_{\gamma\in\widehat{G}}\widehat{\nu}(\gamma)\left(|\widehat{F_{2}}|\right)^{(p)}(\gamma)$
$\displaystyle=2\|F_{2}\|_{p(\nu)}^{p}.$ ∎

From here we can instantiate the previous lemma to obtain the following
corollary.

######  Corollary 4.7.

There exists an absolute constant $c>0$ such that the following holds. Let
$\varepsilon\in(0,1)$ and $p\geq 2$ an even integer. Furthermore, let
$\\{A_{g}\\}_{g\in C}$ be a collection of subsets of $R\subseteq G$ indexed by
a regular Bohr set $C$. Define $\alpha_{g}=|A_{g}|/|G|$ and $\alpha=\sum_{g\in
C}\alpha_{g}^{2}$. Moreover, let $C^{\prime},C^{\prime\prime}\subseteq
C_{\tau}$ be regular Bohr sets for some $\tau\leq c\cdot\mathrm{rk}(C)^{-1}$,
and let
$\nu=\mu_{C^{\prime}}\circ\mu_{C^{\prime}}\ast\mu_{C^{\prime\prime}}\circ\mu_{C^{\prime\prime}}$.
Then

$\left\|\frac{1}{\alpha}\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}+g}-\alpha_{g}\mu_{R+g}\right)\right\|_{p(\mu_{C})}\geq\varepsilon\mu(R)^{-1}$

implies that

$\left\|\frac{1}{\alpha}\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\right\|_{p(\nu)}\geq\frac{1}{2}\varepsilon\mu(R)^{-1}.$

###### Proof.

Apply Lemma 4.6 with $B\coloneqq C$, $S\coloneqq C$, $B^{\prime}\coloneqq
C^{\prime}$, $B^{\prime\prime}\coloneqq C^{\prime\prime}$, and $f_{g}\coloneqq
1_{A_{g}}-\alpha_{g}\mu_{R}$. We have

$\sum_{g\in C}f_{g}\circ f_{g}=\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)$

and

$\sum_{g\in C}f_{g}\circ f^{g}_{g}=\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}}^{g}-\alpha_{g}\mu_{R}^{g}\right)=\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}+g}-\alpha_{g}\mu_{R+g}\right).$

The following lemma lets us move from a non-uniformity assumption on a
function $F^{\prime}_{0}$ whose mean is zero to an assumption on $F^{\prime}$.
This will be critical when we want to apply “sifting” later (see Section
4.2.3). The lemma applies Lemma 3.5 after making some estimates using Bohr
sets and Lemma 2.14.

######  Lemma 4.8.

There exists an absolute constant $c>0$ such that the following holds. Let
$\varepsilon\in(0,1)$ and $p\geq 2$ be an integer. Additionally, let
$\\{A_{g}\\}_{g\in C}$ be a collection of subsets of a regular Bohr set $R$ of
rank $r$ indexed by a regular Bohr set $C$ with $\sum_{g\in C}|A_{g}|\geq
2^{-d}|R||C|$. Define $\alpha_{g}=|A_{g}|/|G|$ and $\alpha=\sum_{g\in
C}\alpha_{g}^{2}$, and let $\nu\colon G\to\mathbb{R}_{\geq 0}$ be a
probability measure supported on $R_{\sigma}$ for $\sigma\leq
c\varepsilon/r2^{d}$ such that $\widehat{\nu}\geq 0$. If

$\left\|\frac{1}{\alpha}\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\right\|_{p(\nu)}\geq\varepsilon\mu(R)^{-1},$

then there is an integer $p^{\prime}=O_{\varepsilon}(p)$ such that

$\left\|\frac{1}{\alpha}\sum_{g\in C}1_{A_{g}}\circ
1_{A_{g}}\right\|_{p^{\prime}(\nu)}\geq\left(1+\varepsilon/4\right)\mu(R)^{-1}.$

###### Proof.

The proof follows [8, Proposition 18]. We write

$f=\frac{1}{\alpha}\sum_{g\in
C}\alpha_{g}(1_{A_{g}}\circ\mu_{R})+\alpha_{g}(\mu_{R}\circ
1_{A_{g}})-\alpha_{g}^{2}(\mu_{R}\circ\mu_{R}).$

For any $p^{\prime}\geq 1$,

$\displaystyle\left\|\frac{1}{\alpha}\sum_{g\in C}1_{A_{g}}\circ
1_{A_{g}}\right\|_{p^{\prime}(\nu)}$
$\displaystyle=\left\|\frac{1}{\alpha}\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)+\mu(R)^{-1}+f-\mu(R)^{-1}\right\|_{p^{\prime}(\nu)}$
$\displaystyle\geq\left\|\frac{1}{\alpha}\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)+\mu(R)^{-1}\right\|_{p^{\prime}(\nu)}-\left\|f-\mu(R)^{-1}\right\|_{p^{\prime}(\nu)}.$

First, we use spectral positivity and Lemma 3.5 to obtain that for
$p^{\prime}=O_{\varepsilon}(p)$ it holds

$\left\|\frac{1}{\alpha}\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)+\mu(R)^{-1}\right\|_{p^{\prime}(\nu)}\geq\left(1+\frac{\varepsilon}{2}\right)\mu(R)^{-1}.$

Next, we use Corollary 2.15 to bound the error term. For
$x\in\text{supp}(\nu)$, we have

$\displaystyle\frac{1}{\alpha}\sum_{g\in
C}\alpha_{g}|(1_{A_{g}}\circ\mu_{R})(x)-(1_{A_{g}}\circ\mu_{R})(0)|$
$\displaystyle=\frac{1}{\alpha}\sum_{g\in C}\alpha_{g}\left|\langle
1_{A_{g}},\mu_{R-x}-\mu_{R}\rangle\right|$
$\displaystyle=\frac{1}{\alpha}\sum_{g\in C}\alpha_{g}\left|\langle
1_{A_{g}},\mu_{R}\ast 1_{-x}-\mu_{R}\rangle\right|$
$\displaystyle\leq\frac{1}{\alpha}\sum_{g\in C}\alpha_{g}\cdot\sigma\text{
}\mathrm{rk}(R)$ $\displaystyle=\frac{\varepsilon}{4}\mu(R)^{-1},$

where the implicit constant in $\sigma$ is set sufficiently small. Similar
reasoning gives the same bounds for the other terms in $f$. We have

$\|f-\mu(R)^{-1}\|_{p^{\prime}(\nu)}\leq\|f-\mu(R)^{-1}\|_{L^{\infty}\left(\text{supp}(\nu)\right)}\leq\frac{1}{4}\mu(R)^{-1}.$

This concludes the proof. ∎

Putting everything together, we can now prove the main result of this section
(restated below). The choice of measure
$\mu_{C^{\prime}}\ast\mu_{C^{\prime\prime}-x}$ in the conclusion may seem a
bit mysterious, but it will be necessary when we apply (in Corollary 4.9) that
the measure we are working with is a convolution of two sets.

See 4.5

###### Proof.

We first apply Corollary 4.7 to infer that

$\left\|\frac{1}{\alpha}\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\right\|_{p(\nu)}\geq\frac{\varepsilon}{2}\mu(R)^{-1}.$

Then Lemma 4.8 implies that

$\left\|\frac{1}{\alpha}\sum_{g\in C}1_{A_{g}}\circ
1_{A_{g}}\right\|_{p^{\prime}(\nu)}\geq(1+\varepsilon/8)\mu(R)^{-1}$

for some integer $p^{\prime}=O_{\varepsilon}(p)$ and
$\nu=\mu_{C^{\prime}}\circ\mu_{C^{\prime}}\ast\mu_{C^{\prime\prime}}\circ\mu_{C^{\prime\prime}}$.
By averaging, for some choice of $x\in C^{\prime}+C^{\prime\prime}$, we must
have

$\left\|\frac{1}{\alpha}\sum_{g\in C}1_{A_{g}}\circ
1_{A_{g}}\right\|_{p^{\prime}(\mu_{C^{\prime}}\ast\mu_{C^{\prime\prime}-x})}\geq(1+\varepsilon/8)\mu(R)^{-1}.$

####  4.2.3 Dependent random choice

Here, we perform the analogous step to what Kelley and Meka call “sifting,”
relying on Lemma 3.8.

######  Corollary 4.9.

Let $\varepsilon\in(0,1)$ and $p\geq 1$ be an integer. Furthermore, let
$\\{A_{g}\\}_{g\in C}$ be a collection of subsets of a set $R\subseteq G$
indexed by a set $C\subseteq G$. Assume $\sum_{g\in C}|A_{g}|=2^{-d}|R||C|$.
Moreover, let $B,B^{\prime}\subseteq G$ and $f=\sum_{g\in C}1_{A_{g}}\circ
1_{A_{g}}$. If

$\left\|\mu_{f}\right\|_{p(\mu_{B}\ast\mu_{B^{\prime}})}\geq(1+\varepsilon)\mu(R)^{-1}$

and

$S=\left\\{x\in
G:\mu_{f}(x)>(1-\varepsilon/2)\|\mu_{f}\|_{p(\mu_{B}\ast\mu_{B^{\prime}})}\right\\},$

then there exists $M_{1}\subseteq B$, $M_{2}\subseteq B^{\prime}$ such that

$\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq
1-\frac{\varepsilon}{4}\quad\text{and}\quad\min\left(\mu_{B}(M_{1}),\mu_{B^{\prime}}(M_{2})\right)\geq
2^{-O_{\varepsilon}(dp)}.$

###### Proof.

Apply Lemma 3.8 to $R$ and $C$ with $B_{1}\coloneqq B$,
$B_{2}\coloneqq-B^{\prime}$, $d\coloneqq d-\log(\mu(R))$,
$\varepsilon\coloneqq\varepsilon/2$, and $\delta\coloneqq\varepsilon/4$. ∎

####  4.2.4 Almost periodicity

Corollary 4.9 allowed us to turn a non-uniformity assumption on $F^{\prime}$
into dense sets $M_{1},M_{2}$ which are robust witnesses to upwards deviations
in $F^{\prime}$. The following result allows us to obtain a density increment
on some translate of a sufficiently large Bohr set.

######  Theorem 4.10 ([22, Theorem 5.4], see also [8, Theorem 17]).

Let $\varepsilon>0$ and $B,B^{\prime}\subseteq G$ be regular Bohr sets of rank
$r$. Suppose that $M_{1}\subseteq B$ with $\mu_{B}(M_{1})=2^{-d_{1}}$ and
$M_{2}\subseteq B^{\prime}$ with $\mu_{B^{\prime}}(M_{2})=2^{-d_{2}}$. Let $S$
be any set with $|S|\leq 2|B|$. Then there is a regular Bohr set
$B^{\prime\prime}\leq B^{\prime}$ of rank at most

$\mathrm{rk}(B^{\prime\prime})\leq r+O_{\varepsilon}(d_{1}^{3}d_{2})$

and density

$\mu(B^{\prime\prime})\geq\exp\left(-O_{\varepsilon}((d_{1}^{3}d_{2}+r)(d_{1}+d_{2}+\log
r))\right)\mu(B^{\prime})$

such that

$|\langle\mu_{B^{\prime\prime}}\ast\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle-\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle|\leq\varepsilon.$

Note that the Bohr set $B^{\prime\prime}$ is a sub-Bohr set of $B^{\prime}$ in
the conclusion of the above theorem. We will apply Theorem 4.10 to obtain the
corollary below. The choice of dilates for $C^{\prime},C^{\prime\prime}$ in
the hypothesis are simply to ensure that $|C^{\prime}+C^{\prime\prime}|\leq
2|C^{\prime}|$ via regularity.

######  Corollary 4.11.

Let $\varepsilon\in(0,1)$ and $p\geq 1$ an integer. Furthermore, let
$\\{A_{g}\\}_{g\in C}$ be a collection of subsets of a Bohr set $R$ of rank
$r$ indexed by a regular Bohr set $C$, and assume $\sum_{g\in
C}|A_{g}|=2^{-d}|R||C|$. Let $C^{\prime}$ be a rank $r$ regular Bohr set, and
let $C^{\prime\prime}=C^{\prime}_{\sigma}$ where $\sigma=O(r^{-1})$ is chosen
to ensure $C^{\prime\prime}$ is regular. Moreover, let $M_{1}\subseteq
C^{\prime}$ and $M_{2}\subseteq C^{\prime\prime}-x$ for some shift $x\in G$
with density guarantees
$\mu_{C^{\prime}}(M_{1}),\mu_{C^{\prime\prime}-x}(M_{2})\geq
2^{-O_{\varepsilon}(dp)}$. Let $S\subseteq G$ be any set. If

$\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq 1-\varepsilon/2,$

then there exists a regular Bohr set $B\leq C^{\prime\prime}$ such that

$\langle\mu_{B}\ast\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq 1-\varepsilon$

where

$\mathrm{rk}(B)\leq
r+O_{\varepsilon}\left(d^{4}p^{4}\right)\quad\text{and}\quad\mu(B)\geq\exp\left(-O_{\varepsilon}(rp\left(d+\log
r\right)+d^{5}p^{5})\right)\mu(C^{\prime\prime}).$

###### Proof.

Since $\mu_{M_{1}}\circ\mu_{M_{2}}$ is supported on
$C^{\prime}+C^{\prime\prime}-x$, we can assume $S$ is supported on the same
set. We can also shift $M_{2}$, $S$ by $x$ so that $M_{2}\subseteq
C^{\prime\prime}$ without changing any assumptions or conclusions. Thus, in
order to apply Theorem 4.10, it suffices to check that
$|C^{\prime}+C^{\prime\prime}|\leq 2|C^{\prime}|$. By regularity and our
choice of $\sigma$, we have

$|C^{\prime}+C^{\prime\prime}|=|C^{\prime}+C^{\prime}_{\sigma}|\leq(1+O(\sigma\cdot
r))|C^{\prime}|\leq 2|C^{\prime}|.$

The proof concludes by applying Theorem 4.10 with $B\coloneqq C^{\prime}$,
$B^{\prime}\coloneqq C^{\prime\prime}$ and $M_{1},M_{2},S$ as given. ∎

####  4.2.5 Combining steps

All that remains to prove Theorem 4.3 (restated below) is to combine the prior
steps. See 4.3

###### Proof.

If we are not in the first condition, then Lemma 4.4 implies there is some
integer $p=O(d)$ such that

$\left\|\frac{1}{\alpha}\sum_{g\in
C}\left(1_{A_{g}}-\alpha_{g}\mu_{R}\right)\circ\left(1_{A_{g}+g}-\alpha_{g}\mu_{R+g}\right)\right\|_{p(\mu_{C})}\geq\frac{1}{2}\varepsilon\mu(R)^{-1}.$

We then apply Lemma 4.5 to infer that

$\left\|\frac{1}{\alpha}\sum_{g\in C}1_{A_{g}}\circ
1_{A_{g}}\right\|_{p^{\prime}(\mu_{C^{\prime}}\ast\mu_{C^{\prime\prime}-x})}\geq\left(1+\frac{\varepsilon}{16}\right)\mu(R)^{-1},$

for some shift $x\in G$, where $C^{\prime}\subseteq C_{\tau_{1}}$ and
$C^{\prime\prime}\subseteq C^{\prime}_{\tau_{2}}$ are regular Bohr sets for
some $\tau_{1},\tau_{2}=O(r^{-1})$ chosen so that
$C^{\prime},C^{\prime\prime}$ are regular. In particular, the choice of
dilates is so that we can later use Corollary 4.11. Let

$S=\left\\{x\in G:\sum_{g\in C}1_{A_{g}}\circ
1_{A_{g}}(x)>(1-\varepsilon/32)\left\|\sum_{g\in C}1_{A_{g}}\circ
1_{A_{g}}\right\|_{p^{\prime}(\mu_{C^{\prime}}\ast\mu_{C^{\prime\prime}-x})}\right\\}.$

Via Corollary 4.9, we obtain $M_{1}\subseteq C^{\prime}$, $M_{2}\subseteq
C^{\prime\prime}$ such that

$\langle\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq 1-\varepsilon/128,$

where $M_{1}$ and $M_{2}$ satisfy the density constraints

$\min\left(\mu_{B}(M_{1}),\mu_{B^{\prime}}(M_{2})\right)\geq
2^{-O_{\varepsilon}(dp)}.$

We then apply Corollary 4.11 to produce a regular Bohr set $B\leq
C^{\prime\prime}$ such that

$\langle\mu_{B}\ast\mu_{M_{1}}\circ\mu_{M_{2}},1_{S}\rangle\geq
1-\varepsilon/64,$

where

$\mathrm{rk}(B)=r+O_{\varepsilon}(d^{8})\quad\text{and}\quad\mu(B)\geq\exp\left(-O_{\varepsilon}(rd^{2}+rd\log
r+d^{10})\right)\mu(C^{\prime\prime}).$

Since $C=R_{\sigma}$, $C^{\prime}=R_{\sigma\tau_{1}}$, and
$C^{\prime\prime}\subseteq R_{\sigma\tau_{1}\tau_{2}}$, Lemma 2.12 implies

$\mu(C^{\prime\prime})\geq\left(\frac{\sigma\tau_{1}\tau_{2}}{4}\right)^{r}\mu(R)\geq\exp\left(-O(r\log(1/\sigma)+r\log
r)\right)\mu(R).$

Combining the above inequalities gives

$\mu(B)\geq\text{exp}\left(-O_{\epsilon}(r\log(1/\sigma)+rd^{2}+rd\log
r+d^{10})\right).$

The last step is to note that

$\displaystyle(1+\varepsilon/80)\mu(R)^{-1}$
$\displaystyle\leq(1-\varepsilon/64)\left(1-\varepsilon/32\right)(1+\varepsilon/16)\mu(R)^{-1}$
$\displaystyle\leq\langle\mu_{B}\ast\mu_{M_{1}}\circ\mu_{M_{2}},\mu_{F^{\prime}}\rangle$
$\displaystyle\leq\|\mu_{F^{\prime}}\ast\mu_{B}\|_{\infty}\|\mu_{M_{1}}\circ\mu_{M_{2}}\|_{1}$
$\displaystyle=\|\mu_{F^{\prime}}\ast\mu_{B}\|_{\infty}.$ ∎

##  5 Acknowledgements

MJ and AO thank Lior Lovett for his constant encouragement.

## References

  * AS [74] Miklós Ajtai and Endre Szemerédi, _Sets of lattice points that form no squares_ , Stud. Sci. Math. Hungar 9 (1974), no. 1975, 9–11.
  * Beh [46] Felix A Behrend, _On sets of integers which contain no three terms in arithmetical progression_ , Proceedings of the National Academy of Sciences 32 (1946), no. 12, 331–332.
  * Bek [24] Adrian Beker, _Improved bounds for skew corner-free sets_ , arXiv preprint arXiv:2402.19169 (2024).
  * Blo [21] Thomas F Bloom, _Additive combinatorics_ , 2021, Course notes available at http://thomasbloom.org/teaching/AC2021.pdf.
  * Bou [99] Jean Bourgain, _On triples in arithmetic progression_ , Geometric And Functional Analysis 9 (1999), no. 5, 968–984.
  * BS [20] Thomas F Bloom and Olof Sisask, _Breaking the logarithmic barrier in Roth’s theorem on arithmetic progressions_ , arXiv preprint arXiv:2007.03528 (2020).
  * [7] , _An improvement to the Kelley–Meka bounds on three-term arithmetic progressions_ , arXiv preprint arXiv:2309.02353 (2023).
  * [8] , _The Kelley–Meka bounds for sets free of three-term arithmetic progressions_ , Essential Number Theory 2 (2023), no. 1, 15–44.
  * CKSU [05] Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Christopher Umans, _Group-theoretic algorithms for matrix multiplication_ , 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), IEEE, 2005, pp. 379–388.
  * CU [03] Henry Cohn and Christopher Umans, _A group-theoretic approach to fast matrix multiplication_ , 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., IEEE, 2003, pp. 438–449.
  * Gre [21] Ben Green, _Lower bounds for corner-free sets_ , arXiv preprint arXiv:2102.11702 (2021).
  * Hun [22] Zach Hunter, _Corner-free sets via the torus_ , arXiv preprint arXiv:2209.10012 (2022).
  * KM [23] Zander Kelley and Raghu Meka, _Strong bounds for 3-progressions_ , 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, pp. 933–973.
  * LS [21] Nati Linial and Adi Shraibman, _Larger corner-free sets from better NOF Exactly- $n$ protocols_, arXiv preprint arXiv:2102.00421 (2021).
  * Mek [23] Raghu Meka, _Strong bounds for 3-progressions_ , 2023, Talk as part the Breakthroughs lecture series at the Simons Institute for the Theory of Computing. [Accessed: 2024 03 16] https://www.youtube.com/watch?v=WN7rJPWy6z8.
  * Mil [24] Luka Milićević, _Good bounds for sets lacking skew corners_ , arXiv preprint arXiv:2404.07180 (2024).
  * Pel [23] Sarah Peluse, _Finite field models in arithmetic combinatorics–twenty years on_ , arXiv preprint arXiv:2312.08100 (2023).
  * Pra [24] Kevin Pratt, _On Generalized Corners and Matrix Multiplication_ , 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) (Dagstuhl, Germany) (Venkatesan Guruswami, ed.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 287, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, pp. 89:1–89:17.
  * PZ [24] Cosmin Pohoata and Dmitrii Zakharov, _On skew corner-free sets_ , arXiv preprint arXiv:2401.17507 (2024).
  * San [12] Tom Sanders, _On the Bogolyubov–Ruzsa lemma_ , Analysis & PDE 5 (2012), no. 3, 627–655.
  * Shk [06] Ilya D Shkredov, _On a generalization of Szemerédi’s theorem_ , Proceedings of the London Mathematical Society 93 (2006), no. 3, 723–760.
  * SS [16] Tomasz Schoen and Olof Sisask, _Roth’s theorem for four variables and additive structures in sums of sparse sets_ , Forum of Mathematics, Sigma, vol. 4, Cambridge University Press, 2016, p. e5.
  * TV [06] Terence Tao and Van H Vu, _Additive combinatorics_ , vol. 105, Cambridge University Press, 2006.