# The Kelley–Meka bounds for sets free of three-term arithmetic progressions

Thomas F. Bloom and Olof Sisask

###### Abstract.

We give a self-contained exposition of the recent remarkable result of Kelley
and Meka: if $A\subseteq\\{1,\ldots,N\\}$ has no non-trivial three-term
arithmetic progressions then $\lvert A\rvert\leq\exp(-c(\log N)^{1/11})N$ for
some constant $c>0$.

Although our proof is identical to that of Kelley and Meka in all of the main
ideas, we also incorporate some minor simplifications relating to Bohr sets.
This eases some of the technical difficulties tackled by Kelley and Meka and
widens the scope of their method. As a consequence, we improve the lower
bounds for finding long arithmetic progressions in $A+A+A$, where
$A\subseteq\\{1,\ldots,N\\}$.

This note gives an exposition of the following remarkable breakthrough result
of Kelley and Meka [11] on Roth’s theorem, which achieves quasi-polynomial
density bounds for the size of sets of integers without three-term arithmetic
progressions.

######  Theorem 1 (Kelley–Meka).

If $A\subseteq\\{1,\ldots,N\\}$ has size $\left\lvert A\right\rvert=\alpha N$
then $A$ contains at least111In this paper we use the convenient abbreviation
$\mathcal{L}(\alpha)$ to denote $\log(2/\alpha)$.

$\exp\left(-O(\mathcal{L}(\alpha)^{11})\right)N^{2}$

many three-term arithmetic progressions. In particular, if $A$ contains only
trivial three-term arithmetic progressions then

$\alpha\leq\exp\left(-\Omega\left((\log N)^{1/11}\right)\right).$

The best bound previously available [4] was $\alpha\leq(\log N)^{-1-c}$ for
some small constant $c>0$ (we refer to the introduction of [4] for further
history). The Kelley–Meka bound is a huge leap forward, and tantalisingly
close to the best known lower bound, due to Behrend [2], who constructed a set
in $\\{1,\ldots,N\\}$ with density $\alpha\geq\exp(-O((\log N)^{1/2}))$ that
is free of non-trivial three-term arithmetic progressions. Getting anywhere
near Behrend-style bounds for this problem has been a long-standing goal in
the area, and the argument of Kelley and Meka achieves this in a beautiful and
elegant way.

Our reasons for writing this note are

  1. (1)

to explain the Kelley–Meka approach using terminology and a perspective
perhaps more familiar to researchers in additive combinatorics, and

  2. (2)

to provide some minor technical refinements which allow for a proof of the
full Theorem 1 which involves only ‘classical’ Bohr set techniques, rather
than the ad hoc method employed in [11] (in particular we answer [11, Question
6.2] of whether such an approach is possible in the affirmative). This widens
the scope of potential applications over the integers, and allows for integer
analogues of the other main results in [11].

It must be made clear, however, that our sole contribution is at the technical
level, allowing the Bohr set machinery to run a little more smoothly; all of
the main new ideas are the same as in [11].

As is customary in this area, a simpler model case is provided by replacing
$\\{1,\ldots,N\\}$ with the vector space $\mathbb{F}_{q}^{n}$.

######  Theorem 2 (Kelley–Meka).

If $q$ is an odd prime and $A\subseteq\mathbb{F}_{q}^{n}$ has size
$\left\lvert A\right\rvert=\alpha q^{n}$ $\alpha$ then the number of three-
term arithmetic progressions in $A$ is

$\gg q^{2n-O(\mathcal{L}(\alpha)^{9})}.$

In particular, if $A\subseteq\mathbb{F}_{q}^{n}$ has no non-trivial three-term
progressions then $\alpha\ll q^{-\Omega(n^{1/9})}$.

Although the stronger bound of $\alpha\ll q^{-\Omega(n)}$ is already known for
this problem via the polynomial method (see [8]), there is no known analogue
of the polynomial method for the integer problem, unlike the methods Kelley
and Meka use to prove Theorem 2, which can be generalised using Bohr set
machinery.

We will present Kelley and Meka’s proof of Theorem 2 in full before discussing
Theorem 1, since the former is technically much simpler, while still
containing all of the important new ideas. We will then translate this using
the language of Bohr sets to prove Theorem 1. Kelley and Meka take a
different, more ad hoc route, iterating over high-dimensional progressions.
This is an ingenious alternative, that may itself have further applications,
but in this note we show that more classical existing techniques also suffice.
As a consequence, we can also establish the following integer analogue of [11,
Corollary 1.12], which finds large subspaces in $A+A+A$ for
$A\subseteq\mathbb{F}_{q}^{n}$.

######  Theorem 3.

If $A\subseteq\\{1,\ldots,N\\}$ has size $\alpha N$ then $A+A+A$ contains an
arithmetic progression of length

$\geq\exp(-O(\mathcal{L}(\alpha)^{2}))N^{\Omega(1/\mathcal{L}(\alpha)^{9})}.$

For comparison, the best bound known was $N^{\alpha^{1+o(1)}}$, originally due
to Sanders [12]. A construction due to Freiman, Halberstam, and Ruzsa [9]
shows that no exponent better than $\Omega(1/\mathcal{L}(\alpha))$ is
possible.

We shall in fact deduce both of Theorems 1 and 3 from the following general-
group analogue of [11, Lemma 1.14], whose existence confirms the speculation
of [11, Footnote 9]. For background material on Bohr sets we refer to Appendix
A, but the unfamiliar reader can for now think of a Bohr set of rank $d$ as
roughly like a $d$-dimensional box in $\mathbb{Z}^{d}$, and where $B_{\rho}$
corresponds to dilating the side length of the box by $\rho$ – these play the
same role in arbitrary groups as subspaces of codimension $d$ do in
$\mathbb{F}_{q}^{n}$. Other notation is defined in the following subsection;
note in particular that if $A$ and $X$ are sets, we write
$\mu_{X}(A)=\left\lvert A\cap X\right\rvert/\left\lvert X\right\rvert$ for the
relative density of $A$ in $X$, and as an element-wise function on a set $G$,
$\mu_{X}=1_{X}/\mu_{G}(X)$. We will discuss some technically stronger versions
of the following further on, but this version allows for quick deductions of
Theorems 1 and 3 (see the end of Section 5).

######  Theorem 4.

There is a constant $c>0$ such that the following holds. Let
$\delta,\epsilon\in(0,1)$ and let $p,k\geq 1$ be integers such that
$(k,\left\lvert G\right\rvert)=1$. For any finite abelian group $G$ and any
subset $A\subseteq G$ with density $\mu_{G}(A)=\alpha>0$ there is a regular
Bohr set $B$ with

$d=\operatorname{rk}(B)=O_{\epsilon,k}\left(\mathcal{L}(\alpha)^{5}p^{4}\right)$

and

$\mu(B)\geq\exp\left(-O_{\epsilon,\delta,k}(\mathcal{L}(\alpha)^{6}p^{4}(\mathcal{L}(\alpha)+p))\right)$

and $A^{\prime}\subseteq(A-x)\cap B$ for some $x\in G$ such that

  1. (1)

$\mu_{B}(A^{\prime})\geq(1-\epsilon)\alpha$,

  2. (2)

$\mu_{B^{\prime}}(A^{\prime})\geq(1-\epsilon)\alpha$, where
$B^{\prime}=B_{\rho}$ is a regular Bohr set with $\rho\in(\tfrac{1}{2},1)\cdot
c\delta\alpha/dk$, and

  3. (3)

$\left\lVert(\mu_{A^{\prime}}-\mu_{B})\ast(\mu_{A^{\prime}}-\mu_{B})\right\rVert_{p(\mu_{k\cdot
B^{\prime}})}\leq\epsilon\mu(B)^{-1}.$

In other words, for any dense set $A$, we can find a low-rank Bohr set $B$
such that a restriction of (a translate of) $A$ to $B$, with almost the same
relative density, has its auto-convolution extremely balanced: it is close to
its average, as measured in an $L^{p}$-sense over another large Bohr set. To
give an idea of the parameters: to deduce Theorem 1, we shall take $\epsilon$
and $\delta$ some small constants, $k=2$, and $p\asymp\mathcal{L}(\alpha)$.
(The dependence on $\epsilon,\delta,k$ is not hard to track explicitly, but is
a distraction for the present applications.)

An identical proof gives a statement with the measure $\mu_{k\cdot
B^{\prime}}$ in part (3) replaced by $\mu_{k\cdot B^{\prime}+x}$ for any $x\in
B$, or indeed $\mu_{B}$ or $\mu_{B}\ast\mu_{B}$, the latter two of which may
appear more natural. These are, however, slightly weaker, and certainly for
the application to three-term arithmetic progressions it is important that the
measure over which the $L^{p}$ norm is taken is supported on some suitably
narrowed copy of $B$.

In Section 1 we provide an informal overview of the main steps of the
argument. In Section 2 we prove what are, in our opinion, the most important
steps of the argument in sufficient generality for the results over both
$\mathbb{F}_{q}^{n}$ and $\\{1,\ldots,N\\}$. In Section 3 we make this sketch
more precise and provide full proofs for the $\mathbb{F}_{q}^{n}$ case.
Finally, in Sections 4 and 5 we show how this argument can be directly adapted
for the integers using Bohr sets. We will proceed by proving Theorem 4 first
and then deducing Theorems 1 and 3.

### Acknowledgements

The first author is supported by a Royal Society University Research
Fellowship. We would like to thank Zander Kelley and Raghu Meka for generously
sharing a copy of their preprint with us, and their encouragement in writing
this exposition. We would also like to thank Ben Green for helpful
conversations.

### Notational conventions

In statements which refer to $G$, this can be taken to be any finite abelian
group (although for the applications this will always be either
$\mathbb{F}_{q}^{n}$ or $\mathbb{Z}/N\mathbb{Z}$). We use the normalised
counting measure on $G$, so that

$\langle
f,g\rangle=\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}f(x)\overline{g(x)}\textrm{ and
}\left\lVert
f\right\rVert_{p}=\left(\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}\left\lvert
f(x)\right\rvert^{p}\right)^{1/p}\textrm{ for }1\leq p<\infty.$

For any $f,g:G\to\mathbb{R}$ we define the convolution and the difference
convolution as

$f\ast g(x)=\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y}f(y)g(x-y)\quad\textrm{and}\quad f\circ
g(x)=\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y}f(y)g(x+y).$

Note the useful adjoint property

$\langle f,g\ast h\rangle=\langle f\circ h,g\rangle.$

For some purposes it is conceptually cleaner to work relative to other
probability measures on $G$, so that if $\mu:G\to\mathbb{R}_{\geq 0}$ has
$\left\lVert\mu\right\rVert_{1}=1$ we write

$\langle
f,g\rangle_{\mu}=\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}\mu(x)f(x)\overline{g(x)}\textrm{ and
}\left\lVert
f\right\rVert_{p(\mu)}=\left(\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}\mu(x)\left\lvert
f(x)\right\rvert^{p}\right)^{1/p}\textrm{ for }1\leq p<\infty.$

We use the slight abuse of notation that if $\mu$ is a probability measure
then $\mu(A)=\left\lVert 1_{A}\right\rVert_{1(\mu)}$ is the density of $A$
relative to $\mu$. Unless specified otherwise, $\mu$ is the uniform measure on
$G$. (So that, for example, $\mu(A)=\alpha=\left\lvert
A\right\rvert/\left\lvert G\right\rvert$ is the density of $A$ within $G$.) We
write $\mu_{A}=\alpha^{-1}1_{A}$ for the normalised indicator function of $A$
(so that $\left\lVert\mu_{A}\right\rVert_{1}=1$). We will sometimes speak of
$A\subseteq B$ with relative density $\alpha=\mu_{B}(A)=\left\lvert
A\right\rvert/\left\lvert B\right\rvert$.

The Fourier transform of $f:G\to\mathbb{R}$ is
$\widehat{f}:\widehat{G}\to\mathbb{C}$ defined as

$\widehat{f}(\gamma)=\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}f(x)\gamma(-x),$

where $\widehat{G}=\\{\gamma:G\to\mathbb{C}^{\times}:\text{$\gamma$ a
homomorphism}\\}$ is the dual group of $G$. We note the following elementary
facts:

  * •

$\widehat{f\ast g}=\widehat{f}\cdot\widehat{g}$ and $\widehat{f\circ
f}=\lvert\widehat{f}\rvert^{2}$ (so in particular the Fourier transform of
$f\circ f$ is a non-negative function on $\widehat{G}$),

  * •

$\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x}f(x)^{k}=\widehat{f}\ast\cdots\ast\widehat{f}(0_{\widehat{G}})$,
where the convolution is $k$-fold, and

  * •

if $\mu$ is a probability measure then the Fourier transform of $\mu-1$ is
$\widehat{\mu}1_{\neq 0_{\widehat{G}}}$.

Note that these three facts immediately imply that the Fourier transform of
$\mu_{A}\circ\mu_{A}-1$ is non-negative, that
$\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits(\mu_{A}\circ\mu_{A}-1)^{k}\geq 0$ for any
integer $k$, and (coupled with the triangle inequality) that
$\left\lVert\mu_{A}\ast\mu_{A}-1\right\rVert_{p}\leq\left\lVert\mu_{A}\circ\mu_{A}-1\right\rVert_{p}$
when $p$ is an even integer.

Finally, we use the Vinogradov notation $X\ll Y$ to mean $X=O(Y)$, that is,
there exists some constant $C>0$ such that $X\leq CY$. The appearance of
parameters as subscript indicates that this constant depends on these
parameters in some unspecified fasion.

##  1\. Sketch of the argument

In this section we provide a sketch of the Kelley–Meka proof of the finite
field model case, Theorem 2, along with some personal commentary and context.
Kelley and Meka also include some fascinating comparisons of this approach
with earlier work and speculations about it and alternative approaches, and we
encourage the reader to study Appendices A and B of [11] and consider the
interesting questions therein (although note that we answer their Question A.4
in the affirmative below).

Let $A\subseteq\mathbb{F}_{q}^{n}$ be a set of density $\alpha$ and
$C\subseteq\mathbb{F}_{q}^{n}$ a set of density $\gamma$. (For the case of
three-term progressions we are interested in $C=2\cdot A$, in which case
$\gamma=\alpha$.) How many solutions to $a_{1}+a_{2}=c$ with $a_{1},a_{2}\in
A$ and $c\in C$ do we expect? If $A$, $C$ are random sets then we expect
$\approx\alpha^{2}\gamma q^{2n}$ many such solutions, which is to say

$\langle\mu_{A}\ast\mu_{A},\mu_{C}\rangle\approx 1.$

The Kelley–Meka approach begins with some constant discrepancy from this
expected count, say $\langle\mu_{A}\ast\mu_{A},\mu_{C}\rangle\leq 1/2$, and
produces a large density increment of $A$ on some subspace
$V\leq\mathbb{F}_{q}^{n}$ with codimension $O(\mathcal{L}(\alpha)^{O(1)})$
(that is, $\mu_{V}(A^{\prime})\geq(1+\Omega(1))\alpha$ for some translate
$A^{\prime}$ of $A$). This is done using mostly physical-based methods, rather
than the Fourier-based methods that have dominated the study of three-term
progressions thus far.

Our presentation of the Kelley–Meka strategy breaks it down into five key
steps.

1 : Hölder lifting If $\langle\mu_{A}\ast\mu_{A},\mu_{C}\rangle\leq 1/2$ then
$\left\lVert\mu_{A}\circ\mu_{A}-1\right\rVert_{p}\geq 1/4$ for some
$p\ll\mathcal{L}(\gamma)$.

This is essentially a one-line application of Hölder’s inequality:

$\tfrac{1}{2}\leq\left\lvert\langle\mu_{A}\ast\mu_{A}-1,\mu_{C}\rangle\right\rvert\leq\left\lVert\mu_{A}\ast\mu_{A}-1\right\rVert_{p}\left\lVert\mu_{C}\right\rVert_{\infty}^{1/p}\leq
2\left\lVert\mu_{A}\ast\mu_{A}-1\right\rVert_{p}$

for sufficiently large $p$, since
$\left\lVert\mu_{C}\right\rVert_{\infty}=1/\gamma$, and recalling that
$\left\lVert\mu_{A}\ast\mu_{A}-1\right\rVert_{p}\leq\left\lVert\mu_{A}\circ\mu_{A}-1\right\rVert_{p}$
when $p$ is an even integer. Although trivial, this has been little used in
previous work, compared to the Fourier deduction that $\sum_{\gamma\neq
0}\left\lvert\widehat{\mu_{A}}\right\rvert^{2}\left\lvert\widehat{\mu_{C}}\right\rvert\gg
1$.

This physical Hölder step was used (along with almost-periodicity) in [3] to
achieve density bounds of $\alpha\leq(\log N)^{-1-o(1)}$. Indeed, in a sense
the approach of [3] corresponds to carrying out Steps 1, 4, and 5 of the
present sketch. The advancement of [4] past the logarithmic density barrier
couples this with delicate structural information on the Fourier side
(following seminal ideas of Bateman and Katz [1]).

It is incredible that the following two steps, which are simple enough to
prove in only a couple of pages, perform far better quantitatively than this
elaborate Fourier-side approach.

2 : Unbalancing For any $f:G\to\mathbb{R}$ such that $\widehat{f}\geq 0$, if
$\left\lVert f\right\rVert_{p}\geq 1/4$ then $\left\lVert
f+1\right\rVert_{p^{\prime}}\geq 1+1/8$ for some $p^{\prime}\ll p$. In
particular, if $\left\lVert\mu_{A}\circ\mu_{A}-1\right\rVert_{p}\geq 1/4$ then
$\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p^{\prime}}\geq 1+1/8$.

This step is essential to the success of the Kelly-Meka argument, and rests on
the fact that the Fourier transform of $f$ is non-negative. (Note that it is
not true for an arbitrary function.) While the spectral non-negativity of
$\mu_{A}\circ\mu_{A}-1$ has played a role in some arguments before (e.g. in
the spectral boosting aspect of [4]), to our knowledge it has not before been
so cleanly expressed, and its potential had not been fully appreciated within
additive combinatorics.

At this point we digress to note that obtaining the conclusion
$\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p}\geq 1+\Omega(1)$ for some
$p\ll\mathcal{L}(\gamma)$ from the assumption that
$\langle\mu_{A}\ast\mu_{A},\mu_{C}\rangle\leq 1/2$ is already achievable via
the traditional Fourier-based method. (In particular this observation answers
[11, Question A.4] in the affirmative.) By converting the inner product to
Fourier space and applying the triangle inequality we observe that

$\sum_{\lambda\neq
0}\left\lvert\widehat{\mu_{A}}(\lambda)\right\rvert^{2}\left\lvert\widehat{\mu_{C}}(\lambda)\right\rvert\geq
1/2.$

It follows that, for some choice of signs $c_{\lambda}\in\mathbb{C}$, we have

$\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
C}\sum_{\lambda}c_{\lambda}\left\lvert\widehat{\mu_{A}}(\lambda)\right\rvert^{2}\lambda(-x)=\sum_{\lambda}\left\lvert\widehat{\mu_{A}}(\lambda)\right\rvert^{2}\left\lvert\widehat{\mu_{C}}(\lambda)\right\rvert\geq
1+1/2.$

Applying Hölder’s inequality to the left-hand side and using orthogonality of
characters yields, for any even integer $p$,

$1+1/2\leq\gamma^{-1/p}\left(\sum_{\lambda_{1},\ldots,\lambda_{p}}c_{\lambda_{1}}\cdots\overline{c_{\lambda_{p}}}\left\lvert\widehat{\mu_{A}}(\lambda_{1})\right\rvert^{2}\cdots\left\lvert\widehat{\mu_{A}}(\lambda_{p})\right\rvert^{2}1_{\lambda_{1}+\cdots-\lambda_{p}=0}\right)^{1/p}.$

We can discard the signs $c_{\lambda}$ by the triangle inequality, and then by
orthogonality the sum here is in fact equal to
$\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p}$, and we are done choosing $p$
suitably large. This sort of step has already played a major role in previous
Fourier-based approaches to Roth’s theorem, although generally with the
$\widehat{\mu_{A}}$ restricted to some ‘large spectrum’, where it then yields
information about the additive relations within this large spectrum. It is a
great insight of Kelley and Meka that this information is far more useful on
the physical side.

In this exposition we do not pursue this Fourier-based approach, to follow
more closely Kelley and Meka, and so we will end our digression here and
return to the sketch.

3 : Dependent random choice If
$\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p}\geq 1+1/8$ then there are
$A_{1},A_{2}\subseteq A$ of density at least $\alpha^{O(p)}$ such that
$\langle\mu_{A_{1}}\circ\mu_{A_{2}},1_{S}\rangle\geq 1-1/32$ where
$S=\\{x:\mu_{A}\circ\mu_{A}(x)>1+1/16\\}$.

This is, in our opinion, the most important step (although of course every
step is necessary, and in particular the previous unbalancing step is
crucial). In combination with the previous two steps, we have now converted
the original 3 variable deficiency information of
$\langle\mu_{A}\ast\mu_{A},\mu_{C}\rangle\leq 1/2$ into 4 variable abundancy
information $\langle\mu_{A_{1}}\circ\mu_{A_{2}},\mu_{A}\circ\mu_{A}\rangle\geq
1+\Omega(1)$. This is very promising, since Schoen and the second author [21]
have already shown that almost-periodicity can prove quasi-polynomial bounds
for 4 variable equations.

The proof of this step, called sifting in [11], is completely elementary, and
uses dependent random choice – one takes $A_{i}$ to be the intersection of $p$
randomly chosen translates of $A$. A simple expectation calculation combined
with the $L^{p}$ information then verifies that there must exist some choice
of translates which satisfy both the density conditions and the inner product
condition.

Arguments of this kind have appeared before in additive combinatorics, dating
back in some form to Gowers’ proof of Szemerédi’s theorem [10]. For example,
when $p=2$ this method was used by Schoen [18] to prove strong bounds for the
Balog–Szemerédi–Gowers theorem, and similar manipulations for larger $p$ have
played an extensive role in work of Schoen and Shkredov (see for example [19,
22]). A very similar statement also appears in work of Sanders [13, Lemma
1.9], itself a generalisation of an argument of Gowers [10, Lemma 11].

Despite this previous work, the true potential of this method (when coupled
with the powerful technique of almost-periodicity) in applications to the
study of three-term progressions and related problems, had been overlooked
before the breakthrough of Kelley and Meka.

4 : Almost periodicity For any sets $A_{1},A_{2},S\subseteq\mathbb{F}_{q}^{n}$
if $A_{1},A_{2}$ have density at least $\alpha$ then there is a subspace $V$
with codimension $O(\mathcal{L}(\alpha)^{4})$ such that
$\left\lvert\langle\mu_{V}\ast\mu_{A_{1}}\circ\mu_{A_{2}},1_{S}\rangle-\langle\mu_{A_{1}}\circ\mu_{A_{2}},1_{S}\rangle\right\rvert\leq
1/100.$

Almost-periodicity statements of this type have played an important role in
additive combinatorics since their introduction by Croot and the second author
[6], most notably in the work of Sanders achieving quasi-polynomial bounds for
inverse sumset theorems [16, 17]. The conventional wisdom was that, despite
their success in inverse sumset problems and for translation invariant
equations in four or more variables (see [21] and the earlier [20] for six or
more variables), they were not able to achieve significant results for three-
term arithmetic progressions. (Although the argument of [4] did make
fundamental use of almost-periodicity, most of the work in that paper was
Fourier-analytic.) Kelley and Meka have dispelled this illusion completely.

It should be noted, however, that there is no novelty in the actual form of
almost-periodicity used by Kelley and Meka – the new strength is a result of
the context in which they use it.

5 : Density increment If $\langle\mu_{A}\ast\mu_{A},\mu_{C}\rangle\leq 1/2$
then there is an affine subspace $V$ of codimension
$O(\mathcal{L}(\alpha)^{4}\mathcal{L}(\gamma)^{4})$ on which $A$ has density
at least $(1+\tfrac{1}{100})\alpha$.

This is just a trivial combination of the previous 4 steps (noting that the
density increment condition can also be phrased as
$\left\lVert\mu_{A}\ast\mu_{V}\right\rVert_{\infty}\geq 1+1/100$). This
density increment condition can now be iteratively applied to eventually
obtain a lower bound for
$\langle\mu_{A^{\prime}}\ast\mu_{A^{\prime}},\mu_{C}\rangle$ (with
$A^{\prime}$ now perhaps some subset of a translate of $A$).

For example, the deduction of Theorem 2 is routine with $C=2\cdot A$. Indeed,
a density increment such as $\alpha\mapsto(1+\Omega(1))\alpha$ can occur at
most $O(\mathcal{L}(\alpha))$ many times, after which we must halt with many
three-term arithmetic progressions found in the intersection of $A$ with some
affine subspace, the codimension of which is bounded above by
$O(\mathcal{L}(\alpha)^{9})$.

Alternatively, carrying through these steps with $C$ being the complement of
$A+A$ leads to the following.

######  Theorem 5 (Kelley–Meka).

If $A\subseteq\mathbb{F}_{q}^{n}$ has density $\alpha$ and $\gamma\in(0,1]$
then there is some affine subspace $V\leq\mathbb{F}_{q}^{n}$ of codimension
$O(\mathcal{L}(\alpha)^{5}\mathcal{L}(\gamma)^{4})$ such that

$\left\lvert(A+A)\cap V\right\rvert\geq(1-\gamma)\left\lvert V\right\rvert.$

For comparison, the best bound previously available, due to Sanders [16], had
codimension $O(\gamma^{-2}\mathcal{L}(\alpha)^{4})$. The latter is slightly
better when $\gamma$ is constant (as was the case of interest in [16]) but
much weaker when $\gamma\approx\alpha$, which is the regime of interest for
three-term arithmetic progressions.

##  2\. The key new lemmas

In this section we prove general forms of Steps 2 and 3 that will be used for
both the $\mathbb{F}_{q}^{n}$ and integer case.

###  2.1. Unbalancing of spectrally non-negative functions

The following precise form of Step 2 will suffice for all our applications.

######  Lemma 6.

Let $\epsilon\in(0,1)$ and $\nu:G\to\mathbb{R}_{\geq 0}$ be some probability
measure such that $\widehat{\nu}\geq 0$. Let $f:G\to\mathbb{R}$ be such that
$\widehat{f}\geq 0$. If $\left\lVert f\right\rVert_{p(\nu)}\geq\epsilon$ for
some $p\geq 1$ then $\left\lVert f+1\right\rVert_{p^{\prime}(\nu)}\geq
1+\tfrac{1}{2}\epsilon$ for some $p^{\prime}\ll_{\epsilon}p$.

We have left the dependence on $\epsilon$ unspecified since our applications
only use $\epsilon\gg 1$. The proof below delivers
$p^{\prime}\ll\epsilon^{-1}\log(\epsilon^{-1})p$. Kelley and Meka use a
different method (see [11, Appendix D]) which is more efficient, giving
$p^{\prime}\ll\epsilon^{-1}p$, but requires use of an external (though simple)
fact about the binomial distribution.

###### Proof.

Without loss of generality we can assume that $p\geq 5$ is an odd integer.
Since the Fourier transforms of $f$ and $\nu$ are non-negative,

$\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits\nu
f^{p}=\widehat{\nu}\ast\widehat{f}^{(p)}(0_{\widehat{G}})\geq 0.$

It follows that, since $2\max(x,0)=x+\left\lvert x\right\rvert$ for
$x\in\mathbb{R}$,

$2\langle\max(f,0),f^{p-1}\rangle_{\nu}=\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits\nu f^{p}+\langle\left\lvert
f\right\rvert,f^{p-1}\rangle_{\nu}\geq\left\lVert
f\right\rVert_{p(\nu)}^{p}\geq\epsilon^{p}.$

Therefore, if $P=\\{x:f(x)\geq 0\\}$, then $\langle
1_{P},f^{p}\rangle_{\nu}\geq\frac{1}{2}\epsilon^{p}$. Furthermore, if
$T=\\{x\in P:f(x)\geq\tfrac{3}{4}\epsilon\\}$ then $\langle 1_{P\backslash
T},f^{p}\rangle_{\nu}\leq\tfrac{1}{4}\epsilon^{p}$, and hence by the Cauchy-
Schwarz inequality,

$\nu(T)^{1/2}\left\lVert f\right\rVert_{2p(\nu)}^{p}\geq\langle
1_{T},f^{p}\rangle_{\nu}\geq\tfrac{1}{4}\epsilon^{p}.$

On the other hand, by the triangle inequality

$\left\lVert f\right\rVert_{2p(\nu)}\leq 1+\left\lVert
f+1\right\rVert_{2p(\nu)}\leq 3,$

or else we are done, with $p^{\prime}=2p$. Hence
$\nu(T)\geq(\epsilon/10)^{2p}$. It follows that, for any $p^{\prime}\geq 1$,

$\left\lVert f+1\right\rVert_{p^{\prime}(\nu)}\geq\langle 1_{T},\left\lvert
f+1\right\rvert^{p^{\prime}}\rangle_{\nu}^{1/p^{\prime}}\geq(1+\tfrac{3}{4}\epsilon)(\epsilon/10)^{2p/p^{\prime}}.$

The desired bound now follows if we choose $p^{\prime}$ a sufficiently large
multiple (depending on $\epsilon$) of $p$. ∎

###  2.2. An application of dependent random choice

We now use dependent random choice (or what Kelley and Meka call ‘sifting’) to
prove a general form of Step 3. This makes use of (a generalisation of) the
fact that

$\left\lVert 1_{A}\circ
1_{A}\right\rVert_{p}^{p}=\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s_{1},\ldots,s_{p}\in
G}\mu((A+s_{1})\cap\cdots\cap(A+s_{p}))^{2}$

to convert $L^{p}$-information about a convolution to information about the
nested intersections appearing in the right-hand side. This identity features
extensively in some works of Shkredov (see [22] for example) and
Schoen–Shkredov [20], and is already implicitly used in work of Sanders [13,
Lemma 1.9], but its strength and utility in the current context was far from
apparent before the work of Kelley and Meka. At a first reading of the
following result, the reader may wish to take $B_{1}=B_{2}=G$, in which case
$\mu=\mu_{B_{1}}\circ\mu_{B_{2}}$ is just the usual uniform measure on $G$.

######  Lemma 7.

Let $p\geq 1$ be an integer and $\epsilon,\delta>0$. Let $B_{1},B_{2}\subseteq
G$, and let $\mu=\mu_{B_{1}}\circ\mu_{B_{2}}$. For any finite set $A\subseteq
G$ with density $\alpha$, if

$S=\\{x\in
G:\mu_{A}\circ\mu_{A}(x)>(1-\epsilon)\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p(\mu)}\\},$

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

$\langle\mu_{A_{1}}\circ\mu_{A_{2}},1_{S}\rangle\geq 1-\delta$

and

$\min\left(\mu_{B_{1}}(A_{1}),\mu_{B_{2}}(A_{2})\right)\gg\left(\alpha\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p(\mu)}\right)^{p+O_{\epsilon,\delta}(1)}.$

Again, since we will apply this only in the case $\epsilon,\delta\gg 1$, we
are not concerned with the behaviour of the $O_{\epsilon,\delta}(1)$ term,
although we record here that the proof (which is identical to that in [11]) in
fact allows for $O(\epsilon^{-1}\log(\delta^{-1}))$. We furthermore note that
$A_{i}$ will take the form $B_{i}\cap(A+s_{1})\cap\cdots\cap(A+s_{p})$ for
some randomly chosen shifts $s_{j}\in G$.

We shall prove Lemma 7 after Lemma 9 below, but first we note the following
immediate special case, which is all we use when studying
$\mathbb{F}_{q}^{n}$.

######  Corollary 8.

Let $p\geq 1$ be an integer and $\epsilon>0$. If $A\subseteq G$ is such that
$\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p}\geq 1+\epsilon$ and
$S=\\{x:\mu_{A}\circ\mu_{A}(x)>1+\epsilon/2\\}$, then there are
$A_{1},A_{2}\subseteq G$, both of density

$\gg\alpha^{p+O_{\epsilon}(1)},$

such that

$\langle\mu_{A_{1}}\circ\mu_{A_{2}},1_{S}\rangle\geq 1-\epsilon/8.$

We encode the dependent random choice argument underpinning Lemma 7 as the
following general lemma.

######  Lemma 9.

Let $p\geq 2$ be an even integer. Let $B_{1},B_{2}\subseteq G$ and
$\mu=\mu_{B_{1}}\circ\mu_{B_{2}}$. For any finite set $A\subseteq G$ with
density $\alpha$ and function $f:G\to\mathbb{R}_{\geq 0}$ there exist
$A_{1}\subseteq B_{1}$ and $A_{2}\subseteq B_{2}$ such that

$\langle\mu_{A_{1}}\circ\mu_{A_{2}},f\rangle\leq
2\frac{\langle(\mu_{A}\circ\mu_{A})^{p},f\rangle_{\mu}}{\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p(\mu)}^{p}}$

and

$\min\left(\mu_{B_{1}}(A_{1}),\mu_{B_{2}}(A_{2})\right)\geq\frac{1}{4}\alpha^{2p}\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p(\mu)}^{2p}.$

###### Proof.

For $s\in G^{p}$ let $A_{1}(s)=B_{1}\cap(A+s_{1})\cap\cdots\cap(A+s_{p})$, and
similarly for $A_{2}(s)$. Note that

$\displaystyle\langle(\mu_{A}\circ\mu_{A})^{p},f\rangle_{\mu}$
$\displaystyle=\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}b_{1}\in B_{1}\\\ b_{2}\in
B_{2}\end{subarray}}\mu_{A}\circ\mu_{A}(b_{1}-b_{2})^{p}f(b_{1}-b_{2})$
$\displaystyle=\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}b_{1}\in B_{1}\\\ b_{2}\in
B_{2}\end{subarray}}\left(\alpha^{-2}\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{t\in
G}1_{A+t}(b_{1})1_{A+t}(b_{2})\right)^{p}f(b_{1}-b_{2})$
$\displaystyle=\alpha^{-2p}\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}b_{1}\in B_{1}\\\ b_{2}\in
B_{2}\end{subarray}}\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s\in
G^{p}}1_{A_{1}(s)}(b_{1})1_{A_{2}(s)}(b_{2})f(b_{1}-b_{2})$
$\displaystyle=\alpha^{-2p}\beta_{1}^{-1}\beta_{2}^{-1}\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s}\langle 1_{A_{1}(s)}\circ
1_{A_{2}(s)},f\rangle,$

where $\beta_{i}=\mu(B_{i})$. In particular, applying this with $f\equiv 1$ we
see that, if $\alpha_{i}(s)=\left\lvert A_{i}(s)\right\rvert/\left\lvert
G\right\rvert$, then

$\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p(\mu)}^{p}=\alpha^{-2p}\beta_{1}^{-1}\beta_{2}^{-1}\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s}\alpha_{1}(s)\alpha_{2}(s)$

and

$\frac{\langle(\mu_{A}\circ\mu_{A})^{p},f\rangle_{\mu}}{\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p(\mu)}^{p}}=\frac{\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s}\langle 1_{A_{1}(s)}\circ
1_{A_{2}(s)},f\rangle}{\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s}\alpha_{1}(s)\alpha_{2}(s)}=\eta,$

say. Note that, if

$M=\tfrac{1}{2}\alpha^{p}(\beta_{1}\beta_{2})^{1/2}\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p(\mu)}^{p},$

then

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s}1_{\alpha_{1}(s)\alpha_{2}(s)<M^{2}}\alpha_{1}(s)\alpha_{2}(s)$
$\displaystyle<M\left(\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s}\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
G}1_{A_{1}(s)}(x)\right)^{1/2}\left(\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s}\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}1_{A_{1}(s)}(x)\right)^{1/2}$
$\displaystyle=M\alpha^{p}(\beta_{1}\beta_{2})^{1/2}=\frac{1}{2}\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s}\alpha_{1}(s)\alpha_{2}(s)$

and so

$\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s}\langle 1_{A_{1}(s)}\circ
1_{A_{2}(s)},f\rangle=\eta\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits\alpha_{1}(s)\alpha_{2}(s)\\\
<2\eta\mathop{\mathchoice{\vbox{\hbox{\larger[4]$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{s}\alpha_{1}(s)\alpha_{2}(s)1_{\alpha_{1}(s)\alpha_{2}(s)\geq
M^{2}}.$

In particular there must exist some $s$ such that

$\langle 1_{A_{1}(s)}\circ
1_{A_{2}(s)},f\rangle<2\eta\alpha_{1}(s)\alpha_{2}(s)1_{\alpha_{1}(s)\alpha_{2}(s)\geq
M^{2}},$

and the claim follows (note that the left-hand side is trivially $\geq 0$ and
hence such an $s$ must satisfy $\alpha_{1}(s)\alpha_{2}(s)\geq M^{2}$). ∎

The deduction of Lemma 7 is immediate from Lemma 9 with $f=1_{G\backslash S}$.
Indeed, by nesting of $L^{p}$ norms we can assume that $p$ is sufficiently
large in terms of $\epsilon$ and $\delta$ (this is where the
$O_{\epsilon,\delta}(1)$ term arises in the exponent). It suffices then to
note that

$\langle\mu_{A_{1}}\circ\mu_{A_{2}},1_{S}\rangle=1-\langle\mu_{A_{1}}\circ\mu_{A_{2}},1_{G\backslash
S}\rangle$

and by definition of $S$ we have

$\frac{\langle(\mu_{A}\circ\mu_{A})^{p},1_{G\backslash
S}\rangle}{\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p}^{p}}\leq(1-\epsilon)^{p}$

which is $\leq\delta/2$ if $p$ is large enough.

##  3\. The finite field case

In this section we prove Theorem 2, following the sketch of Section 1. The
following straightforward lemma is a form of Step 1.

######  Lemma 10.

Let $\epsilon>0$. If $A,C\subseteq G$, where $C$ has density at least
$\gamma$, then either

  1. (1)

$\left\lvert\langle\mu_{A}\ast\mu_{A},\mu_{C}\rangle-1\right\rvert\leq\epsilon$
or

  2. (2)

$\left\lVert\mu_{A}\circ\mu_{A}-1\right\rVert_{p}\geq\epsilon/2$ for some
$p\ll\mathcal{L}(\gamma)$.

###### Proof.

If the first alternative fails, then by Hölder’s inequality, for any $p\geq 1$

$\epsilon<\left\lvert\langle\mu_{A}\ast\mu_{A}-1,\mu_{C}\rangle\right\rvert\leq\left\lVert\mu_{A}\ast\mu_{A}-1\right\rVert_{p}\gamma^{-1/p}.$

In particular if we choose $p=2\lceil K\mathcal{L}(\gamma)\rceil$ for some
large constant $K$ then we deduce that

$\left\lVert\mu_{A}\ast\mu_{A}-1\right\rVert_{p}\geq\tfrac{1}{2}\epsilon.$

It remains to note that, since $p$ is even,

$\left\lVert\mu_{A}\ast\mu_{A}-1\right\rVert_{p}^{p}=(\widehat{\mu_{A}}^{2}1_{\neq
0_{\widehat{G}}})^{(p)}(0_{\widehat{G}})\leq(\lvert\widehat{\mu_{A}}\rvert^{2}1_{\neq
0_{\widehat{G}}})^{(p)}(0_{\widehat{G}})=\left\lVert\mu_{A}\circ\mu_{A}-1\right\rVert_{p}^{p}.\qed$

Steps 2 and 3 have already been proved as Lemma 6 and Corollary 8. For Step 4
we can use the following almost-periodicity result, which is [21, Theorem
3.2], as a black box.

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

If $A_{1},A_{2},S\subseteq\mathbb{F}_{q}^{n}$ are such that $A_{1}$ and
$A_{2}$ both have density at least $\alpha$ then there is a subspace $V$ of
codimension

$\mathrm{codim}(V)\ll_{\epsilon}\mathcal{L}(\alpha)^{4}$

such that

$\left\lvert\langle\mu_{V}\ast\mu_{A_{1}}\ast\mu_{A_{2}},1_{S}\rangle-\langle\mu_{A_{1}}\ast\mu_{A_{2}},1_{S}\rangle\right\rvert\leq\epsilon.$

Importantly, note that no assumption is made on $S$, and there is no
dependency on the density of $S$. We now complete the final step by combining
everything thus far into a single density increment statement, which suffices
for Theorem 2 as discussed in Section 1.

######  Proposition 12.

Let $\epsilon\in(0,1)$. If $A,C\subseteq\mathbb{F}_{q}^{n}$, where $C$ has
density at least $\gamma$, then either

  1. (1)

$\left\lvert\langle\mu_{A}\ast\mu_{A},\mu_{C}\rangle-1\right\rvert\leq\epsilon$
or

  2. (2)

there is a subspace $V$ of codimension

$\ll_{\epsilon}\mathcal{L}(\gamma)^{4}\mathcal{L}(\alpha)^{4}$

such that $\left\lVert
1_{A}\ast\mu_{V}\right\rVert_{\infty}\geq(1+\Omega(\epsilon))\alpha$.

###### Proof.

By Lemma 10, if the first alternative fails then
$\left\lVert\mu_{A}\circ\mu_{A}-1\right\rVert_{p}\geq\epsilon/2$ for some
$p\ll\mathcal{L}(\gamma)$. By Lemma 6 (applied to $f=\mu_{A}\circ\mu_{A}-1$)
we deduce that $\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p}\geq
1+\epsilon/4$ for some $p\ll_{\epsilon}\mathcal{L}(\gamma)$. Hence, by
Corollary 8, there are $A_{1},A_{2}$, both of density

$\geq\alpha^{O_{\epsilon}(\mathcal{L}(\gamma))},$

such that $\langle\mu_{A_{1}}\circ\mu_{A_{2}},1_{S}\rangle\geq 1-\epsilon/32$,
where $S=\\{x:\mu_{A}\circ\mu_{A}(x)\geq 1+\epsilon/8\\}$ . By Theorem 11
there is a subspace $V$ of the required codimension such that

$\langle\mu_{V}\ast\mu_{A_{1}}\circ\mu_{A_{2}},1_{S}\rangle\geq
1-\tfrac{1}{16}\epsilon.$

By definition of $S$, it follows that

$\displaystyle 1+\Omega(\epsilon)$
$\displaystyle\leq(1+\epsilon/8)(1-\epsilon/16)$
$\displaystyle\leq\langle\mu_{V}\ast\mu_{A_{1}}\circ\mu_{A_{2}},\mu_{A}\circ\mu_{A}\rangle$
$\displaystyle\leq\left\lVert\mu_{V}\ast\mu_{A}\right\rVert_{\infty}\left\lVert\mu_{A}\ast\mu_{A_{2}}\circ\mu_{A_{1}}\right\rVert_{1}$
$\displaystyle=\left\lVert\mu_{V}\ast 1_{A}\right\rVert_{\infty}\alpha^{-1},$

and the proof is complete. ∎

##  4\. The integer case

A useful strategy in additive combinatorics is to first prove a result of
interest over $\mathbb{F}_{q}^{n}$, making use of the abundancy of subspaces,
and then translate this to a result over the integers, replacing various
equalities with approximate equalities and subspaces with Bohr sets.

Bohr sets of low rank are analogues of subspaces of low codimension, and have
played a central role in additive combinatorics since the work of Bourgain
[5], with much of the theory further developed by Sanders [14, 15]. We have
recalled the relevant definitions and properties in Appendix A.

In this section we will employ Steps 3, 4, and 5 of the Kelley–Meka approach,
performed relative to Bohr sets, to prove the following technical statement,
whose statement is convenient for the iterative proof. In the following
section we will show how it, together with unbalancing and the regularity of
Bohr sets, implies Theorem 4, and thence Theorems 1 and 3.

We apologise for the daunting appearance and technicality of the statements in
this and the next section; a certain overhead of notation and caveats is a sad
fact of life when working with Bohr sets. The reader should be reassured,
however, that all the essential ideas are as in the $\mathbb{F}_{q}^{n}$ case.

The approach taken here should be compared with that in [11, Section 8] –
there Kelley and Meka also follow their $\mathbb{F}_{q}^{n}$ model, but
instead use mixed analogues over multi-dimensional progressions and Bohr sets,
instead of just Bohr sets as we do here. The two objects are, in a heuristic
sense, identical, but the need to pass between them adds some complexity to
the argument of Kelley and Meka.

######  Theorem 13.

There is a constant $c>0$ such that the following holds. Let
${\epsilon,\delta\in(0,1)}$ and $p,k\geq 1$ be integers such that
$(k,\left\lvert G\right\rvert)=1$. For any $A\subseteq G$ with density
$\alpha$ there is a regular Bohr set $B$ with

$d=\operatorname{rk}(B)=O_{\epsilon}\left(\mathcal{L}(\alpha)^{5}p^{4}\right)\quad\text{and}\quad\mu(B)\geq\exp\left(-O_{\epsilon,\delta}(\mathcal{L}(\alpha)^{6}p^{4}(\mathcal{L}(\alpha)+p)\right)$

and some $A^{\prime}\subseteq(A-x)\cap B$ for some $x\in G$ such that

  1. (1)

$\mu_{B}(A^{\prime})\geq(1-\epsilon)\alpha$,

  2. (2)

$\mu_{B^{\prime}}(A^{\prime})\geq(1-\epsilon)\alpha$, where
$B^{\prime}=B_{\rho}$ is a regular Bohr set with
${\rho\in(\tfrac{1}{2},1)\cdot c\delta\alpha/d}$, and

  3. (3)

$\left\lVert\mu_{A^{\prime}}\circ\mu_{A^{\prime}}\right\rVert_{p(\mu_{k\cdot
B^{\prime\prime}}\circ\mu_{k\cdot B^{\prime\prime}}\ast\mu_{k\cdot
B^{\prime\prime\prime}}\circ\mu_{k\cdot
B^{\prime\prime\prime}})}<(1+\epsilon)\mu(B)^{-1},$

for any regular Bohr sets $B^{\prime\prime}=B^{\prime}_{\rho^{\prime}}$ and
$B^{\prime\prime\prime}=B^{\prime\prime}_{\rho^{\prime\prime}}$ satisfying
${\rho^{\prime},\rho^{\prime\prime}\in(\frac{1}{2},1)\cdot c\delta\alpha/d}$.

The proof of Theorem 13 proceeds by repeated application of the following
statement, which is suitable for iteration.

######  Proposition 14.

There is a constant $c>0$ such that the following holds. Let $\epsilon>0$ and
$p,k\geq 1$ be integers such that $(k,\left\lvert G\right\rvert)=1$. Let
$B,B^{\prime},B^{\prime\prime}\subseteq G$ be regular Bohr sets of rank $d$
such that $B^{\prime\prime}\subseteq B^{\prime}_{c/d}$ and $A\subseteq B$ with
relative density $\alpha$. If

$\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p(\mu_{k\cdot
B^{\prime}}\circ\mu_{k\cdot B^{\prime}}\ast\mu_{k\cdot
B^{\prime\prime}}\circ\mu_{k\cdot
B^{\prime\prime}})}\geq\left(1+\epsilon\right)\mu(B)^{-1}$

then there is a regular Bohr set $B^{\prime\prime\prime}\subseteq
B^{\prime\prime}$ of rank at most

$\operatorname{rk}(B^{\prime\prime\prime})\leq
d+O_{\epsilon}(\mathcal{L}(\alpha)^{4}p^{4})$

and density

$\mu(B^{\prime\prime\prime})\geq\exp(-O_{\epsilon}(d\log
d+\mathcal{L}(\alpha)^{5}p^{5}))\mu(B^{\prime\prime})$

such that

$\left\lVert\mu_{B^{\prime\prime\prime}}*\mu_{A}\right\rVert_{\infty}\geq
1+\Omega(\epsilon).$

We first explain how Theorem 13 follows by iteration. In doing so we shall
require a regularity ‘narrowing’ trick originally due to Bourgain. The
following form is [4, Lemma 12.1].

######  Lemma 15.

There is a constant $c>0$ such that the following holds. Let $B$ be a regular
Bohr set of rank $d$, suppose $A\subseteq B$ has density $\alpha$, let
$\epsilon>0$, and suppose $B^{\prime},B^{\prime\prime}\subseteq B_{\rho}$
where $\rho\leq c\alpha\epsilon/d$. Then either

  1. (1)

there is some translate $A^{\prime}$ of $A$ such that
$\mu_{B^{\prime}}(A^{\prime})\geq(1-\epsilon)\alpha$ and
$\mu_{B^{\prime\prime}}(A^{\prime})\geq(1-\epsilon)\alpha$, or

  2. (2)

$\left\lVert
1_{A}\ast\mu_{B^{\prime}}\right\rVert_{\infty}\geq(1+\epsilon/2)\alpha$, or

  3. (3)

$\left\lVert
1_{A}\ast\mu_{B^{\prime\prime}}\right\rVert_{\infty}\geq(1+\epsilon/2)\alpha$.

###### Proof of Theorem 13 assuming Proposition 14.

Let $C_{\epsilon},D_{\epsilon,\delta}\geq 1$ be parameters to be specified
later, and let $c$ be the smaller of $1/2$ and the implicit constant behind
the $\Omega(\epsilon)$-term in Proposition 14. Let $t\geq 0$ be maximal such
that there is a sequence of Bohr sets, say $B^{(0)},\ldots,B^{(t)}$, and
subsets of translates of $A$, say $A_{0},\ldots,A_{t}$, such that the
following holds:

  1. (1)

$B^{(0)}=G$ and $A_{0}=A$,

  2. (2)

each $B^{(i)}$ is a regular Bohr set of rank $d_{i}$ and

$d_{i+1}\leq d_{i}+C_{\epsilon}\mathcal{L}(\alpha)^{4}p^{4}$

and

$\mu(B^{(i+1)})\geq\exp(-D_{\epsilon,\delta}\mathcal{L}(\alpha)^{5}p^{4}(\mathcal{L}(\alpha)+p))\mu(B^{(i)}),$

and

  3. (3)

each $A_{i}$ is a subset of $B^{(i)}$ with density $\alpha_{i}$ such that
$\alpha_{i+1}\geq(1+c\epsilon)\alpha_{i}$ for $0\leq i<t$.

Observe from point (3), and the trivial fact that $\alpha_{i}\leq 1$, that
$t\ll_{\epsilon}\mathcal{L}(\alpha)$. Note that this implies
$d_{t}\ll_{\epsilon}\mathcal{L}(\alpha)^{5}p^{4}$.

We apply Lemma 15 with $2c\epsilon$ in place of $\epsilon$, and $B=B^{(t)}$,
$B^{\prime}=B_{c^{\prime}\alpha\epsilon/d_{t}}$ and
$B^{\prime\prime}=B^{\prime}_{c^{\prime\prime}\delta\alpha/d_{t}}$, where the
constants are in particular chosen to ensure that
$B^{\prime},B^{\prime\prime}$ are both regular. Provided we pick
$D_{\epsilon,\delta}$ large enough in terms of $C_{\epsilon}$, $\epsilon$, and
$\delta$, Lemma 23 and the maximality of $t$ ensure that we must be in the
first alternative of Lemma 15’s conclusion: there exists a translate $A_{t}-x$
such that $\mu_{B^{\prime}}(A_{t}-x)\geq(1-\epsilon)\alpha$ and
$\mu_{B^{\prime\prime}}(A_{t}-x)\geq(1-\epsilon)\alpha$.

We claim that $A^{\prime}=(A_{t}-x)\cap B^{\prime}$ and $B^{\prime}$ satisfy
the conclusions of Theorem 13. Indeed, the bounds on the rank and size of
$B^{\prime}$, and the density conditions on $A^{\prime}$, are clearly
satisfied.

Suppose for a contradiction that

$\left\lVert\mu_{A^{\prime}}\circ\mu_{A^{\prime}}\right\rVert_{p(\mu_{k\cdot
B^{\prime\prime}}\circ\mu_{k\cdot B^{\prime\prime}}\ast\mu_{k\cdot
B^{\prime\prime\prime}}\circ\mu_{k\cdot
B^{\prime\prime\prime}})}\geq(1+\epsilon)\mu(B^{\prime})^{-1},$

for some regular Bohr sets $B^{\prime\prime}=B^{\prime}_{\rho}$ and
$B^{\prime\prime\prime}=B^{\prime\prime}_{\rho^{\prime}}$ satisfying
$\rho,\rho^{\prime}\in(\frac{1}{2},1)\cdot c\delta\alpha/d_{t}$.

The conditions of Proposition 14 are met, and hence we deduce there is some
$\tilde{B}\subseteq B^{\prime\prime}$ of rank

$\operatorname{rk}(\tilde{B})\leq\operatorname{rk}(B)+O_{\epsilon}(\mathcal{L}(\alpha)^{4}p^{4})\text{
and }\mu(\tilde{B})\geq\exp(-O_{\epsilon}(d_{t}\log
d_{t}+\mathcal{L}(\alpha)^{5}p^{5}))\mu(B^{\prime\prime})$

and there is a translate of $A_{t}$, say $A_{t}-y$, such that
$\mu_{\tilde{B}}(A_{t}-y)\geq(1+c\epsilon)\alpha$. This a contradiction to the
maximality of $t$, provided $C_{\epsilon}$ matches the implicit constant in
the first $O_{\epsilon}$-term, since we can take $B^{(t+1)}=\tilde{B}$ and
$A_{t+1}=(A_{t}-y)\cap\tilde{B}$, noting that by Lemma 23

$\mu(B^{\prime\prime})\geq\exp(-O_{\epsilon,\delta}(d\mathcal{L}(\alpha/d_{t})))\mu(B^{(t)}),$

and certainly $\log d_{t}\ll\mathcal{L}(\alpha)+p$. ∎

Proposition 14 is a consequence of Steps 3 and 4 (dependent random choice and
almost-periodicity) of the Kelley–Meka approach. We will use the following
version of almost-periodicity, which is essentially [21, Theorem 5.4].

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

There is a constant $c>0$ such that the following holds. Let $\epsilon>0$ and
$B,B^{\prime}\subseteq G$ be regular Bohr sets of rank $d$. Suppose that
$A_{1}\subseteq B$ with density $\alpha_{1}$ and $A_{2}$ is such that there
exists $x$ with $A_{2}\subseteq B^{\prime}-x$ with density $\alpha_{2}$. Let
$S$ be any set with $\left\lvert S\right\rvert\leq 2\left\lvert
B\right\rvert$. There is a regular Bohr set $B^{\prime\prime}\subseteq
B^{\prime}$ of rank at most

$d+O_{\epsilon}(\mathcal{L}(\alpha_{1})^{3}\mathcal{L}(\alpha_{2}))$

and density

$\mu(B^{\prime\prime})\geq\exp(-O_{\epsilon}(d\log
d+\mathcal{L}(\alpha_{1}\alpha_{2})\mathcal{L}(\alpha_{1})^{3}\mathcal{L}(\alpha_{2})))\mu(B^{\prime})$

such that

$\left\lvert\langle\mu_{B^{\prime}}\ast\mu_{A_{1}}\circ\mu_{A_{2}},1_{S}\rangle-\langle\mu_{A_{1}}\circ\mu_{A_{2}},1_{S}\rangle\right\rvert\leq\epsilon.$

###### Proof.

We apply [21, Theorem 5.4] with the choices (with apologies for the
unfortunate clash in variable naming between papers)

$A\to-A_{2},M\to A_{1},L\to-S,S\to B^{\prime}_{c/d},B\to B^{\prime}_{c/d}$

and note that

$\lvert-A_{2}+B^{\prime}_{c/d}\rvert\leq\lvert
B^{\prime}+B^{\prime}_{c/d}\rvert\leq 2\left\lvert B^{\prime}\right\rvert\leq
2\alpha_{2}^{-1}\left\lvert A_{2}\right\rvert$

by regularity of $B^{\prime}$. The statement now almost follows from [21,
Theorem 5.4] after observing that (in that theorem’s language) we have $K\leq
2\alpha_{2}^{-1}$, $\sigma=1$, and $\eta\geq\alpha_{1}/2$, except that there
the statement has a constraint on the rank and the width of
$B^{\prime\prime}$, rather than the rank and the size. Nonetheless the proof
immediately delivers the conclusion as stated here (after appealing to Lemma
23). ∎

We will now use this almost-periodicity together with Lemma 7 to deduce the
iterative step.

###### Proof of Proposition 14.

By averaging there exists some $x\in k\cdot B^{\prime}+k\cdot
B^{\prime\prime}$ such that

$\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p(\mu_{k\cdot
B^{\prime}}\ast\mu_{k\cdot B^{\prime\prime}-x})}\geq(1+\epsilon)\mu(B)^{-1}.$

We now apply Lemma 7 with $B_{1}=k\cdot B^{\prime}$ and $B_{2}=k\cdot
B^{\prime\prime}-x$. This produces some $A_{1}\subseteq k\cdot B^{\prime}$ and
$A_{2}\subseteq k\cdot B^{\prime\prime}-x$ such that, with
$S=\\{x:\mu_{A}\circ\mu_{A}(x)\geq(1+\epsilon/2)\mu(B)^{-1}\\}$,

$\langle\mu_{A_{1}}\circ\mu_{A_{2}},1_{S}\rangle\geq 1-\epsilon/4$

and

$\min\left(\mu_{k\cdot B^{\prime}}(A_{1}),\mu_{k\cdot
B^{\prime\prime}-x}(A_{2})\right)\gg\alpha^{p+O_{\epsilon}(1)}.$

We now apply Theorem 16 (with $k\cdot B^{\prime}$ and $k\cdot
B^{\prime\prime}$ playing the roles of $B$ and $B^{\prime}$ respectively),
noting that we can, without loss of generality, take $S$ to be supported in
$A_{1}-A_{2}\subseteq k\cdot B^{\prime}+k\cdot B^{\prime\prime}-x$ and so by
regularity of $B^{\prime}$

$\left\lvert S\right\rvert\leq\left\lvert
B^{\prime}+B^{\prime\prime}\right\rvert\leq 2\left\lvert
B^{\prime}\right\rvert.$

This produces some $B^{\prime\prime\prime}\subseteq k\cdot B^{\prime\prime}$
of the required rank and density such that

$\langle\mu_{B^{\prime\prime\prime}}\ast\mu_{A_{1}}\circ\mu_{A_{2}},\mu_{A}\circ\mu_{A}\rangle\geq(1+\epsilon/2)(1-\epsilon/4)(1-\epsilon/8)\mu(B)^{-1}\geq(1+\Omega(\epsilon))\mu(B)^{-1}.$

The result now follows from averaging, since

$\langle\mu_{B^{\prime\prime\prime}}\ast\mu_{A_{1}}\circ\mu_{A_{2}},\mu_{A}\circ\mu_{A}\rangle\leq\left\lVert\mu_{B^{\prime\prime\prime}}\ast\mu_{A}\right\rVert_{\infty}\left\lVert\mu_{A_{2}}\circ\mu_{A_{1}}\ast\mu_{A}\right\rVert_{1}=\left\lVert\mu_{B^{\prime\prime\prime}}\ast\mu_{A}\right\rVert_{\infty}.$

∎

##  5\. Deduction of Theorems 4, 1 and 3

Finally, in this section we deduce Theorem 4 from Theorem 13 (using Step 2)
and show using Step 1) how it implies Theorems 1 and 3

The following form of unbalancing relative to Bohr sets is sufficient.

######  Proposition 17.

There is a constant $c>0$ such that the following holds. Let $\epsilon>0$ and
$p\geq 2$ be an integer. Let $B\subseteq G$ be a regular Bohr set and
$A\subseteq B$ with relative density $\alpha$. Let $\nu:G\to\mathbb{R}_{\geq
0}$ be a probability measure supported on $B_{\rho}$ where $\rho\leq
c\epsilon\alpha/\operatorname{rk}(B)$ such that $\widehat{\nu}\geq 0$. If

$\left\lVert(\mu_{A}-\mu_{B})\circ(\mu_{A}-\mu_{B})\right\rVert_{p(\nu)}\geq\epsilon\,\mu(B)^{-1}$

then there is $p^{\prime}\ll_{\epsilon}p$ such that

$\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p^{\prime}(\nu)}\geq\left(1+\tfrac{1}{4}\epsilon\right)\mu(B)^{-1},$

###### Proof.

Let us write

$g=\mu_{A}\circ\mu_{B}+\mu_{B}\circ\mu_{A}-\mu_{B}\circ\mu_{B}$

and note that for any $p^{\prime}\geq 1$

$\displaystyle\left\lVert\mu_{A}\circ\mu_{A}\right\rVert_{p^{\prime}(\nu)}$
$\displaystyle=\left\lVert(\mu_{A}-\mu_{B})\circ(\mu_{A}-\mu_{B})+\mu(B)^{-1}+g-\mu(B)^{-1}\right\rVert_{p^{\prime}(\nu)}$
$\displaystyle\geq\left\lVert(\mu_{A}-\mu_{B})\circ(\mu_{A}-\mu_{B})+\mu(B)^{-1}\right\rVert_{p^{\prime}(\nu)}-\left\lVert
g-\mu(B)^{-1}\right\rVert_{p^{\prime}(\nu)}.$

To bound the error term, note that $\mu_{A}\circ\mu_{B}(0)=\mu(B)^{-1}$ and
that by regularity (for example with Lemma 24), for
$x\in\operatorname{supp}(\nu)$,

$\displaystyle\left\lvert\mu_{A}\circ\mu_{B}(x)-\mu_{A}\circ\mu_{B}(0)\right\rvert$
$\displaystyle\leq\alpha^{-1}\mu(B)^{-1}\left\lVert\mu_{B}(\cdot+x)-\mu_{B}\right\rVert_{1}$
$\displaystyle\ll\rho\operatorname{rk}(B)\alpha^{-1}\mu(B)^{-1}$
$\displaystyle\leq\tfrac{1}{12}\epsilon\mu(B)^{-1},$

say, assuming $\rho$ is sufficiently small, and similarly for the other terms
constituting $g$. Hence

$\left\lVert g-\mu(B)^{-1}\right\rVert_{p^{\prime}(\nu)}\leq\left\lVert
g-\mu(B)^{-1}\right\rVert_{L^{\infty}(\operatorname{supp}(\nu))}\leq\tfrac{1}{4}\epsilon\,\mu(B)^{-1}.$

It therefore suffices to find some $p^{\prime}\ll_{\epsilon}p$ such that

$\left\lVert(\mu_{A}-\mu_{B})\circ(\mu_{A}-\mu_{B})+\mu(B)^{-1}\right\rVert_{p^{\prime}(\nu)}\geq(1+\tfrac{1}{2}\epsilon)\mu(B)^{-1}.$

This is immediate from Lemma 6 applied to
$f=\mu(B)(\mu_{A}-\mu_{B})\circ(\mu_{A}-\mu_{B})$. ∎

To deduce Theorem 4 from Theorem 13 we will need to pass from the measure
$\mu_{B}$ to
$\mu_{B^{\prime}}\circ\mu_{B^{\prime}}\ast\mu_{B^{\prime\prime}}\circ\mu_{B^{\prime\prime}}$.
This is a technical issue with Bohr sets that does not arise in the
$\mathbb{F}_{q}^{n}$ model case (note that these measures are identical when
$B=B^{\prime}=B^{\prime\prime}=G$).

######  Proposition 18.

There is a constant $c>0$ such that the following holds. Let $p\geq 2$ be an
even integer. Let $f:G\to\mathbb{R}$, let $B\subseteq G$ and
$B^{\prime}\subseteq B_{c/\operatorname{rk}(B)}$ and
$B^{\prime\prime}\subseteq B_{c/\operatorname{rk}(B^{\prime})}$ all be regular
Bohr sets. Then

$\left\lVert f\circ
f\right\rVert_{p(\mu_{B^{\prime}}\circ\mu_{B^{\prime}}\ast\mu_{B^{\prime\prime}}\circ\mu_{B^{\prime\prime}})}\geq\tfrac{1}{2}\left\lVert
f*f\right\rVert_{p(\mu_{B})}.$

###### Proof.

By two applications of Lemma 25 we have

$\displaystyle\mu_{B}$ $\displaystyle\leq
2\mu_{B_{1+2\rho}}*\mu_{B^{\prime}_{1/2}}\circ\mu_{B^{\prime}_{1/2}}$
$\displaystyle\leq
4\mu_{B_{1+2\rho}}*\mu_{B^{\prime}}\circ\mu_{B^{\prime}}\ast\mu_{B^{\prime\prime}}\circ\mu_{B^{\prime\prime}}.$

Hence if
$\nu=\mu_{B^{\prime}}\ast\mu_{B^{\prime}}\ast\mu_{B^{\prime\prime}}\ast\mu_{B^{\prime\prime}}$
then

$\displaystyle\left\lVert f*f\right\rVert_{p(\mu_{B})}^{p}$
$\displaystyle=\mathbb{E}_{x\in G}\,\mu_{B}(x)\,f*f(x)^{p}$ $\displaystyle\leq
4\,\mathbb{E}_{x\in G}\left(\mu_{B_{1+2\rho}}*\nu\right)(x)\,f*f(x)^{p}$
$\displaystyle=4\,\mathbb{E}_{t\in B_{1+2\rho}}\mathbb{E}_{x\in
G}\,\nu(x-t)\,f*f(x)^{p}.$

By averaging there exists some $t$ such that

$\displaystyle\left\lVert f*f\right\rVert_{p(\mu_{B})}^{p}$ $\displaystyle\leq
4\,\mathbb{E}_{x\in G}\,\nu(x-t)\,f*f(x)^{p}$
$\displaystyle=4\sum_{\gamma\in\widehat{G}}\widehat{\nu}(\gamma)\gamma(-t)(\widehat{f}^{2})^{(p)}(\gamma)$
$\displaystyle\leq
4\sum_{\gamma\in\widehat{G}}\widehat{\nu}(\gamma)(\lvert\widehat{f}\rvert^{2})^{(p)}(\gamma)$
$\displaystyle=4\left\lVert f\circ f\right\rVert_{p(\nu)}^{p},$

where we have used the fact that $\widehat{\nu}\geq 0$. The bound for
$\left\lVert f\circ f\right\rVert_{p(\mu_{B})}$ is proved in an identical
fashion. ∎

###### Proof of Theorem 4.

We may, without loss of generality, assume that $\delta$ is sufficiently small
in terms of $\epsilon$ and $k$. Let $p^{\prime}\ll_{\epsilon}p$ satisfy the
condition in Proposition 17. Let $A^{\prime}$ and $B$ be the regular Bohr sets
provided by Theorem 13 applied with $p$ replaced by $p^{\prime}$ and
$\epsilon$ replaced by $\epsilon/8$. We claim that this choice satisfies the
conclusion of Theorem 4. It suffices to prove

$\left\lVert(\mu_{A^{\prime}}-\mu_{B})\ast(\mu_{A^{\prime}}-\mu_{B})\right\rVert_{p(\mu_{k\cdot
B^{\prime}})}\leq\epsilon\mu(B)^{-1}.$

Suppose not. Let $B^{\prime\prime}=B^{\prime}_{\rho}$ and
$B^{\prime\prime\prime}=B^{\prime\prime}_{\rho^{\prime}}$ be regular Bohr sets
with $\rho=c_{1}/d$ and $\rho^{\prime}=c_{2}/d$ for some sufficiently small
constants $c_{1},c_{2}>0$. By Proposition 18 we have, if we let
$f=\mu_{A^{\prime}}-\mu_{B}$ for brevity,

$\left\lVert f\ast f\right\rVert_{p(\mu_{k\cdot B^{\prime}})}\leq 2\left\lVert
f\circ f\right\rVert_{p(\nu)}$

where $\nu=\mu_{k\cdot B^{\prime\prime}}\circ\mu_{k\cdot
B^{\prime\prime}}\ast\mu_{k\cdot B^{\prime\prime\prime}}\circ\mu_{k\cdot
B^{\prime\prime\prime}}$. In particular, $\left\lVert
f\right\rVert_{p(\nu)}>\tfrac{1}{2}\epsilon\mu(B)^{-1}$, and so by Proposition
17 (noting that $\nu$ is supported on
$k(B^{\prime\prime}+B^{\prime\prime}+B^{\prime\prime\prime}+B^{\prime\prime\prime})\subseteq
B^{\prime}_{4k\rho}\subseteq B_{c/d}$) we deduce that

$\left\lVert\mu_{A^{\prime}}\circ\mu_{A^{\prime}}\right\rVert_{p^{\prime}(\nu)}\geq(1+\epsilon/8)\mu(B)^{-1},$

which contradicts the conclusion of Theorem 13, and we are done. ∎

Finally to apply Theorem 4 to three-term progressions and finding long
arithmetic progressions in $A+A+A$ we record the following version of the
Hölder lifting Step 1.

######  Proposition 19.

There is a constant $c>0$ such that the following holds. Let $\epsilon>0$. Let
$B\subseteq G$ be a regular Bohr set and $A\subseteq B$ with relative density
$\alpha$, and let $B^{\prime}\subseteq
B_{c\epsilon\alpha/\operatorname{rk}(B)}$ be a regular Bohr set and
$C\subseteq B^{\prime}$ with relative density $\gamma$. Either

  1. (1)

$\left\lvert\langle\mu_{A}*\mu_{A},\mu_{C}\rangle-\mu(B)^{-1}\right\rvert\leq\epsilon\mu(B)^{-1}$
or

  2. (2)

there is some $p\ll\mathcal{L}(\gamma)$ such that
$\left\lVert(\mu_{A}-\mu_{B})*(\mu_{A}-\mu_{B})\right\rVert_{p(\mu_{B^{\prime}})}\geq\tfrac{1}{2}\epsilon\mu(B)^{-1}$.

###### Proof.

We first note that

$\langle\mu_{A}\ast\mu_{A},\mu_{C}\rangle=\langle(\mu_{A}-\mu_{B})\ast(\mu_{A}-\mu_{B}),\mu_{C}\rangle+2\langle\mu_{A}\ast\mu_{B},\mu_{C}\rangle-\langle\mu_{B}\ast\mu_{B},\mu_{C}\rangle.$

By the regularity of $B$ (more specifically Lemma 24) and the fact that
$C\subseteq B_{c\epsilon/\operatorname{rk}(B)}$, we have

$\left\lvert\langle\mu_{B}\ast\mu_{B},\mu_{C}\rangle-\mu(B)^{-1}\right\rvert\leq\left\lVert\mu_{B}\right\rVert_{\infty}\left\lVert\mu_{B}\ast\mu_{C}-\mu_{B}\right\rVert_{1}\leq\tfrac{1}{8}\epsilon\mu(B)^{-1}.$

Similarly, the fact that $C\subseteq B_{c\epsilon\alpha/\operatorname{rk}(B)}$
implies that

$\left\lvert\langle\mu_{A}\ast\mu_{B},\mu_{C}\rangle-\mu(B)^{-1}\right\rvert\leq\left\lVert\mu_{B}\right\rVert_{\infty}\left\lVert\mu_{B}\ast\mu_{C}-\mu_{B}\right\rVert_{1}\leq\tfrac{1}{16}\epsilon\mu(B)^{-1}.$

It follows that, with $f=(\mu_{A}-\mu_{B})\ast(\mu_{A}-\mu_{B})$, we have

$\left\lvert\langle\mu_{A}\ast\mu_{A},\mu_{C}\rangle-\mu(B)^{-1}-\langle
f,\mu_{C}\rangle\right\rvert\leq\tfrac{1}{4}\epsilon\mu(B)^{-1}.$

Therefore, if the first possibility fails, then

$\gamma^{-1}\left\lvert\langle
f,1_{C}\rangle_{\mu_{B^{\prime}}}\right\rvert=\left\lvert\langle
f,\mu_{C}\rangle\right\rvert\geq\tfrac{3}{4}\epsilon\mu(B)^{-1}.$

By Hölder’s inequality, for any $p\geq 1$,

$\left\lVert
f\right\rVert_{p(\mu_{B^{\prime}})}\gamma^{1-1/p}\geq\left\lvert\langle
f,1_{C}\rangle_{\mu_{B^{\prime}}}\right\rvert.$

We can choose some $p\ll\mathcal{L}(\gamma)$ such that $\gamma^{-1/p}\leq
3/2$, and the proof is complete. ∎

###  5.1. Three-term arithmetic progressions

###### Proof of Theorem 1.

As usual, we begin by considering $A\subseteq\\{1,\ldots,N\\}$ as a subset of
$G=\mathbb{Z}/((3N+1)\mathbb{Z}$ – the density of this set within $G$ is still
$\asymp\alpha$, and any three-term arithmetic progression in $A\subseteq G$
yields one in $A\subseteq\\{1,\ldots,N\\}$.

We apply Theorem 4 with $\epsilon=1/4$, $k=2$, and $p=\lceil
K\mathcal{L}(\alpha)\rceil$ for some large constant $K$. Let
$A^{\prime\prime}=A^{\prime}\cap B^{\prime}$. If

$\langle\mu_{A^{\prime}}\ast\mu_{A^{\prime}},\mu_{2\cdot
A^{\prime\prime}}\rangle\geq\tfrac{1}{2}\mu(B)^{-1}$

we are done, since the left-hand side is at most
$\ll\alpha{-3}\mu(B)^{-2}\mu(B^{\prime})^{-1}$ times the number of three-term
arithmetic progressions in $A$, and by Lemma 23 we have

$\mu(B)\mu(B^{\prime})\geq\exp(-O_{\epsilon}(\mathcal{L}(\alpha)^{11}).$

Otherwise, we are in the second case of Proposition 19, which contradicts the
conclusion of Theorem 4, and we are done.

∎

###  5.2. Arithmetic progressions in $A+A+A$

###### Proof of Theorem 3.

As above, we may assume that in fact $A\subseteq G=\mathbb{Z}/N\mathbb{Z}$
with density $\alpha$, for some $N$ prime, which will incur only a constant
loss. We apply Theorem 4 with $\epsilon=1/4$, $k=1$, and $p=\lceil
C\mathcal{L}(\alpha)\rceil$ for some large constant $C$. Let $B,B^{\prime}$ be
the Bohr sets produced by that conclusion.

We first argue that $\mu_{B^{\prime}}(A^{\prime}+A^{\prime})\geq 1-\alpha/4$.
Indeed, otherwise if we let $C=B^{\prime}\backslash(A^{\prime}+A^{\prime})$
then the first case of Proposition 19 is violated and the conclusion of
Theorem 4 means the second also cannot hold.

Let $B^{\prime\prime}=B^{\prime}$. We argue that $B^{\prime\prime}\subseteq
A^{\prime}+A^{\prime}+A^{\prime}$. If not, there is some $x\in
B^{\prime\prime}$ such that
$(A^{\prime}+A^{\prime})\cap(x-A^{\prime})=\emptyset$, and so

$\left\lvert(x-A^{\prime})\cap B^{\prime}\right\rvert\leq\left\lvert
B^{\prime}\backslash(A^{\prime}+A^{\prime})\right\rvert\leq\tfrac{\alpha}{4}\left\lvert
B^{\prime}\right\rvert.$

By regularity, however, the left-hand side is at least
$\mu_{B^{\prime}}(A^{\prime})-\tfrac{1}{4}\alpha\geq\tfrac{1}{2}\alpha$, which
is a contradiction.

We have found some Bohr set $B^{\prime\prime}$ of rank
$O(\mathcal{L}(\alpha)^{9})$ and density

$\mu(B^{\prime\prime})\geq\exp(-O(\mathcal{L}(\alpha)^{11})$

such that $B^{\prime\prime}\subseteq A^{\prime}+A^{\prime}+A^{\prime}$. It
remains to note that $A^{\prime}+A^{\prime}+A^{\prime}$ is contained in a
translate of $A+A+A$ and to appeal to Lemma 26 to find an arithmetic
progression in $B^{\prime\prime}$ of length

$\geq\exp(-O(\mathcal{L}(\alpha)^{2}))N^{\Omega(1/\mathcal{L}(\alpha)^{9})}.$

∎

##  Appendix A Bohr sets

In abelian groups more general than $\mathbb{F}_{q}^{n}$, a useful substitute
for genuine subgroups is the class of Bohr sets, introduced to additive
combinatorics by Bourgain [5]. Below we collect some standard facts about Bohr
sets.

######  Definition 20 (Bohr sets).

For a non-empty $\Gamma\subset\widehat{G}$ and $\nu:\Gamma\to[0,2]$ we define
the Bohr set $B=\mathrm{Bohr}_{\nu}(\Gamma)$ as

$\mathrm{Bohr}_{\nu}(\Gamma)=\left\\{x\in G:\left\lvert
1-\gamma(x)\right\rvert\leq\nu(\gamma)\right\\}.$

We call $\Gamma$ the _frequency set_ of $B$ and $\nu$ the _width_ , and define
the _rank_ of $B$ to be the size of $\Gamma$, denoted by
$\operatorname{rk}(B)$. We note here that all Bohr sets are symmetric and
contain $0$.

In fact, when we speak of a Bohr set we implicitly refer to the triple
$(\Gamma,\nu,\mathrm{Bohr}_{\nu}(\Gamma))$, since the set
$\mathrm{Bohr}_{\nu}(\Gamma)$ alone does not uniquely determine the frequency
set nor the width. When we use subset notation, such as $B^{\prime}\subset B$,
this refers only to the set inclusion (and does not, in particular, imply any
particular relation between the associated frequency sets or width functions).
Furthermore, if $B=\mathrm{Bohr}_{\nu}(\Gamma)$ and $\rho\in(0,1]$ then we
write $B_{\rho}$ for the same Bohr set with the width dilated by $\rho$, i.e.
$\mathrm{Bohr}_{\rho\nu}(\Gamma)$, which is known as a _dilate_ of $B$.

Given two width functions $\nu:\Gamma\to[0,2]$ and
$\nu^{\prime}:\Gamma^{\prime}\to[0,2]$ we extend them both to
$\Gamma\cup\Gamma^{\prime}$ by setting their value as 2 if not otherwise
defined, and define their join to be

$\nu\wedge\nu^{\prime}(\gamma)=\min(\nu(\gamma),\nu^{\prime}(\gamma)).$

Bohr sets are, in general, not even approximately group-like, and may grow
exponentially under addition. Bourgain [5] observed that certain Bohr sets are
approximately closed under addition in a weak sense which is suitable for our
applications.

######  Definition 21 (Regularity222The constant $100$ here is fairly
arbitrary. Smaller constants are permissible.).

A Bohr set $B$ of rank $d$ is regular if for all
$\left\lvert\kappa\right\rvert\leq 1/100d$ we have

$(1-100d\left\lvert\kappa\right\rvert)\left\lvert B\right\rvert\leq\left\lvert
B_{1+\kappa}\right\rvert\leq(1+100d\left\lvert\kappa\right\rvert)\left\lvert
B\right\rvert.$

We record here the useful observation, frequently used in this paper, that if
$(k,\left\lvert G\right\rvert)=1$ and $B$ is a regular Bohr set of rank $d$
then $k\cdot B$ is also a regular Bohr set of rank $d$ (and of course the same
density), simply by replacing each character in the frequency set by an
appropriate dilate.

For further introductory discussion of Bohr sets see, for example, [23,
Chapter 4], in which the following basic lemmas are established.

######  Lemma 22.

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

######  Lemma 23.

If $\rho\in(0,1)$ and $B$ is a Bohr set of rank $d$ then $\left\lvert
B_{\rho}\right\rvert\geq(\rho/4)^{d}\left\lvert B\right\rvert$.

The following lemmas indicate how regularity of Bohr sets will be exploited.
These are given and proved as, for example, [4, Lemmam 4.5] and [4, Lemma 4.7]
respectively.

######  Lemma 24.

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

$\left\lVert\mu_{B}*\mu-\mu_{B}\right\rVert_{1}\ll\rho d.$

######  Lemma 25.

There is a constant $c>0$ such that the following holds. Let $B$ be a regular
Bohr set of rank $d$ and $L\geq 1$ be any integer. If $B^{\prime}\subset
B_{\rho}$ where $\rho\leq c/Ld$ then

$\mu_{B}\leq 2\mu_{B_{1+L\rho}}\ast\mu_{B^{\prime}}^{(L)}.$

Finally, we note the following simple lemma, which is useful for finding
arithmetic progressions.

######  Lemma 26.

If $N$ is a prime and $B\subseteq\mathbb{Z}/N\mathbb{Z}$ is a Bohr set of rank
$d$ then $B$ contains an arithmetic progression of length

$\gg\left\lvert B\right\rvert^{1/d}.$

###### Proof.

Let $\rho=4(2/\left\lvert B\right\rvert)^{1/d}$, and note that by Lemma 23 we
have

$\left\lvert B_{\rho}\right\rvert\geq(\rho/4)^{d}\left\lvert B\right\rvert=2.$

In particular there exists some $x\in B_{\rho}\backslash\\{0\\}$. By the
triangle inequality it is clear that $\\{x,\ldots,\lfloor\rho^{-1}\rfloor
x\\}\subseteq B$, whence $B$ contains an arithmetic progression of length
$\gg\rho^{-1}$. ∎

## References

  * [1] M. Bateman and N. H. Katz “New bounds on cap sets” J. Amer. Math. Soc. 25 (2012), no. 2, 585–613.
  * [2] F. A. Behrend “On sets of integers which contain no three terms in arithmetical progression” Proc. Nat. Acad. Sci. U. S. A. 32 (1946): 331–332.
  * [3] T. F. Bloom and O. Sisask “Logarithmic bounds for Roth’s theorem via almost-periodicity” Discrete Anal. 2019, Paper No. 4, 20 pp.
  * [4] T. F. Bloom and O. Sisask “Breaking the logarithmic barrier in Roth’s theorem on arithmetic progressions” submitted arXiv:2007.03528.
  * [5] J. Bourgain “On triples in arithmetic progression” Geom. Funct. Anal. 9, 5 (1999), 968–984.
  * [6] E. Croot and O. Sisask “A probabilistic technique for finding almost-periods of convolutions” Geom. Funct. Anal. 20(6) (2010), 1367–1396.
  * [7] E. Croot, I. Łaba and O. Sisask “Arithmetic progressions in sumsets and $L^{p}$-almost-periodicity”, Combin. Probab. Comput. 22(3) (2013), 351–365.
  * [8] J. S. Ellenberg and D. Gijswijt. “On large subsets of $\mathbb{F}^{n}_{q}$ with no three-term arithmetic progression” Ann. of Math. (2) 185, 1 (2017): 339–343.
  * [9] G.A. Freiman, H. Halberstam, and I.Z. Ruzsa “Integer sum sets containing long arithmetic progressions” J. London Math. Soc. (2) 46 (1992), 193–201.
  * [10] W. T. Gowers “A new proof of Szemerédi’s theorem for arithmetic progressions of length four” Geom. Funct. Anal. 8(3):529–551, 1998.
  * [11] Z. Kelley and R. Meka, “Strong bounds for $3$-progressions”, arXiv:2302.05537.
  * [12] T. Sanders “Additive structures in sumsets” Math. Proc. Cambridge Philos. Soc. 144(2) (2008), 289–316.
  * [13] T. Sanders “Popular difference sets” Online J. Anal. Comb. No. 5 (2010).
  * [14] T. Sanders “On Roth’s theorem on progressions” Ann. of Math. (2) 174, 1 (2011), 619–636.
  * [15] T. Sanders “On certain other sets of integers” J. Anal. Math. 116 (2012), 53–82.
  * [16] T. Sanders “On the Bogolyubov-Ruzsa lemma” Anal. PDE 5(3) (2012), 627–655.
  * [17] T. Sanders “The structure theory of set addition revisited” Bull. Amer. Math. Soc. 50 (2013), no. 1, 93–127.
  * [18] T. Schoen “New bounds in Balog-Szemerédi-Gowers theorem” Combinatorica 35 (2015), no. 6, 695–701.
  * [19] T. Schoen and I. D. Shkredov “Higher moments of convolutions” J. Number Theory 133 (2013), no. 5, 1693–1737.
  * [20] T. Schoen and I. Shkredov, ‘Roth’s theorem in many variables’, Israel J. Math. 199(1) (2014), 287–308. arXiv:1106.1601. cf. MR3219538
  * [21] T. Schoen and O. Sisask “Roth’s theorem for four variables and additive structures in sums of sparse sets” Forum Math. Sigma 4 (2016), Paper No. e5.
  * [22] I. D. Shkredov “Some new results on higher energies” Trans. Moscow Math. Soc. 2013, 31–63.
  * [23] T. Tao and V. H. Vu “Additive Combinatorics” Cambridge University Press Cambridge, 2006