# Four variants of the Fourier-analytic transference principle

Sean Prendiville  S.M. Prendiville, Mathematical Institute, University of
Oxford, Oxford, OX2 6GG, United Kingdom<EMAIL_ADDRESS>
###### Abstract.

We survey four instances of the Fourier analytic ‘transference principle’ or
‘dense model lemma’, which allows one to approximate an unbounded function on
the integers by a bounded function with similar Fourier transform. Such a
result forms a component of a general method pioneered by Green to count
solutions to a single linear equation in a sparse subset of integers.

The author was supported by Tim Browning’s ERC grant 306457. Thanks to Tim for
many useful conversations.

###### Contents

  1. 1 Introduction
  2. 2 Green’s $L^{\infty}$-bounded approximation lemma
  3. 3 Helfgott and De Roton’s $L^{2}$-bounded approximation lemma
  4. 4 Naslund’s $L^{k}$-bounded approximation lemma
  5. 5 The Hahn–Banach approach
  6. A The large spectrum and Bohr sets
  7. B The supporting hyperplane theorem
  8. C The semi-finite minimax theorem
  9. D The Weierstrass polynomial approximation theorem

##  1\. Introduction

###  1.1. Aim

There has been much recent work on counting arithmetic configurations in a
sparse set of integers, such as the set of primes [Gre05, GT08, GT10], smooth
numbers [Har], random sets [CG, Sch], pseudorandom sets [CFZ], or dense
subsets thereof. Given such a sparse set, it is often useful to be able to
construct a dense subset of integers whose arithmetic properties resemble
those of the sparse set, the theory being much more developed in the dense
regime, with recourse to powerful results such as Szemerédi’s theorem and
affiliated techniques.

When counting solutions to a single linear equation, the arithmetic closeness
of the dense model set to our original sparse set can be measured by the level
of similarity in their Fourier transform, provided that we weight the
characteristic function of our sparse set suitably. The sparseness of our set
forces this weight function to grow asymptotically, so we are left with the
problem of approximating an unbounded function by a bounded function, with the
closeness of approximation measured by the $L^{\infty}$-norm of their Fourier
transform. The purpose of this note is to survey four variants of such a
_bounded approximation lemma_ , also called a _transference principle_ or
_dense model lemma_ in the literature: the original found in Green [Gre05], a
quantitative improvement due to Helfgott–De Roton [HDR11], a further
quantitative refinement due to Naslund [Nas15], and finally a much more
general technique due (independently) to Gowers [Gow10] and Reingold et al
[RTTV]. Our focus is on the quantitative strength of each of these results. We
give a complete account of the required background in the appendices.

The Fourier-analytic transference principle is particularly powerful when
combined with the Hardy–Littlewood circle method. Traditionally, the circle
method is performed with respect to a function defined on the integers, whose
Fourier transform is then defined on the circle group
$\mathbb{T}=\mathbb{R}/\mathbb{Z}$. In the majority of the references we
survey, the Fourier analysis is performed with respect to functions defined on
the integers modulo a large prime number. This has the expositional advantage
that both physical and phase space are discrete, and in fact isomorphic.
However, we believe this reduction is artificial, and in order to highlight
the utility of the transference principle within the traditional number-
theoretic circle method, we opt to give all proofs with respect to Fourier
analysis on the integers.

###  1.2. Motivation: a sparse version of Roth’s theorem

A theorem of Roth [Rot53, Rot54] quantifies the density required of a set of
integers to ensure that it contains a non-trivial solution to a single linear
equation

$c_{1}x_{1}+\dots+c_{s}x_{s}=0.$ (1)

Assuming the coefficients sum to zero, a variant of this theorem due to Bloom
[Blo12] states that for any $\delta>0$ there exists $c(\delta)>0$ such that if
$A$ is a subset of $[N]$ of density at least $\delta$ (i.e. $|A|\geq\delta
N$), then $A$ contains many solutions to the equation, in that

$\sum_{\mathbf{c}\cdot\mathbf{x}=0}1_{A}(x_{1})\dotsm 1_{A}(x_{s})\geq
c(\delta)N^{s-1},$ (2)

where one may take

$c(\delta)\gg_{\mathbf{c}}\exp\left(-C/\delta^{\frac{1}{s-2-\varepsilon}}\right)$
(3)

for some absolute constant $C=C(s,\varepsilon)$ and any $\varepsilon>0$.

Roth’s method for proving such a result proceeds by exploiting the
orthogonality relation

$\sum_{\mathbf{c}\cdot\mathbf{x}=0}1_{A}(x_{1})\dotsm
1_{A}(x_{s})=\int_{\mathbb{T}}\hat{1}_{A}(c_{1}\alpha)\dotsm\hat{1}_{A}(c_{s}\alpha)\mathrm{d}\alpha,$
(4)

where we define the Fourier transform of a function
$f:\mathbb{Z}\to\mathbb{C}$ of finite support by

$\hat{f}(\alpha):=\sum_{n}f(n)e(\alpha n).$ (5)

If we know the distribution of $A$ in arithmetic progressions, then the
classical circle method allows us predict the behaviour of $\hat{1}_{A}$.
Roth’s argument says that either $A$ is equidistributed in arithmetic
progressions, in which case we can calculate $\hat{1}_{A}$ and therefore (4),
or alternatively $A$ is biased towards at least one arithmetic progression.
Exploiting this bias then forms the so-called ‘density increment’ argument. We
refrain from the details here, but hope to convey to the reader the sense that
if one knows how the Fourier transform $\hat{1}_{A}$ behaves, then one can
count solutions to a linear equation in $A$.

Suppose that we wish to prove an analogue of Roth’s theorem for subsets of the
integers which are not dense in the interval $[N]$, but are dense in some
fixed sparse subset $S\subset[N]$, so that $|S|=o(N)$. For example, one may
take $S$ to be of arithmetic nature, such as the set of primes or the set of
squares, or even the set of squares of primes. Alternatively, one could take
$S$ to be a random subset of $[N]$.

Given a subset $A$ of our sparse set $S$ which is _relatively dense_ , in the
sense that $|A|\geq\delta|S|$, we wish to prove a lower bound of the form (2).
Notice that if we could construct a _dense_ subset $B\subset[N]$, with
$|B|\geq\delta^{c}N$ say, and such that we have the Fourier approximation

$\hat{1}_{A}\approx\hat{1}_{B},$ (6)

then we can employ Roth’s theorem to obtain a lower bound for the number of
solutions to (1) in $A$ as follows

$\begin{split}\sum_{\mathbf{c}\cdot\mathbf{x}=0}1_{A}(x_{1})\dotsm
1_{A}(x_{s})&=\int_{\mathbb{T}}\hat{1}_{A}(c_{1}\alpha)\dotsm\hat{1}_{A}(c_{s}\alpha)\mathrm{d}\alpha\\\
&\approx\int_{\mathbb{T}}\hat{1}_{B}(c_{1}\alpha)\dotsm\hat{1}_{B}(c_{s}\alpha)\mathrm{d}\alpha\\\
&=\sum_{\mathbf{c}\cdot\mathbf{x}=0}1_{B}(x_{1})\dotsm 1_{B}(x_{s})\\\ &\geq
c(\delta^{c})N^{s-1}.\end{split}$ (7)

Obtaining an approximation such as (6) is the strategy of the Fourier-analytic
transference principle, or dense model lemma, originating in Green [Gre05].
However, as stated, such an approximation is too much to hope for. Looking at
the Fourier transform evaluated at $\alpha=0$, we would deduce that

$|S|\geq|A|=\hat{1}_{A}(0)\approx\hat{1}_{B}(0)\geq\delta^{c}N.$ (8)

This would then imply that $S$ is itself a dense subset of the interval $[N]$.
To get around this, we weight the indicator function of $A$ in order to ensure
that we have some hope of approximating its Fourier transform by the Fourier
transform of a dense set. In order to deal with arbitrary relatively dense
subsets of $S$, it makes sense to choose this weighting independently of the
set $A$ itself.

######  Definition 1.1 (Majorant).

Given $S\subset[N]$ define a _majorant on $S$_ to be a non-negative function
$\nu:\mathbb{Z}\to[0,\infty)$ with support contained in $S$ and such that

$\sum_{n}\nu(n)=\bigl{(}1+o(1)\bigr{)}N.$ (9)

Given a majorant $\nu$ on $S$ and $A\subset S$ with relative density
$|A|\geq\delta|S|$, define

$f:=1_{A}\nu.$

Provided that we choose our majorant sensibly, we should be able to prove that

$\sum_{n}f(n)\geq\delta^{c}N$ (10)

for some $c>0$. We therefore hope to obtain a Fourier approximation of the
form

$\hat{f}\approx\hat{1}_{B},$

for some $B\subset[N]$ which is suitably dense $|B|\geq\delta^{c}N$. In fact,
we do not need our dense approximant to be the characteristic function of a
set; it suffices for the function to have bounded $L^{2}$-norm, an observation
first recorded by Helfgott and De Roton [HDR11].

######  Lemma 1.2 ($L^{2}$-boundedness suffices).

Let $c_{1}+\dots+c_{s}=0$. Then for any $\delta>0$ and any constant $C$ there
exists $c(\delta,C)>0$ such that the following holds. Suppose that
$g:\mathbb{Z}\to[0,\infty)$ is a non-negative function supported on $[N]$
which has bounded111Although this estimate for the $L^{2}$-norm appears to
grow with $N$, it is the same estimate one would obtain for a bounded function
on $[N]$. $L^{2}$-norm

$\sum_{n}g(n)^{2}\leq CN.$ (11)

Then the density assumption

$\sum_{n}g(n)\geq\delta N$ (12)

implies that

$\sum_{\mathbf{c}\cdot\mathbf{x}=0}g(x_{1})\dotsm g(x_{s})\geq
c(\delta,C)N^{s-1}.$

In fact, one may take

$c(\delta,C)=(\delta/2)^{s}c\left(\tfrac{\delta^{2}}{4C}\right),$ (13)

where $c(\delta)$ is the constant appearing in Roth’s theorem (2).

###### Proof.

Define

$B:=\left\\{x\in[N]:g(x)\geq\delta/2\right\\}.$

Then, employing the Cauchy–Schwarz inequality, we have

$\begin{split}\delta N\leq\sum_{x}g(x)&=\sum_{x\notin B}g(x)+\sum_{x\in
B}g(x)\\\ &\leq\tfrac{1}{2}\delta
N+|B|^{1/2}\left(\sum_{x}g(x)^{2}\right)^{1/2}\\\ &\leq\tfrac{1}{2}\delta
N+\left(|B|CN\right)^{1/2}.\end{split}$ (14)

Therefore

$|B|\geq\frac{\delta^{2}}{4C}N.$ (15)

Applying Bloom’s variant of Roth’s theorem, we deduce that

$\sum_{\mathbf{c}\cdot\mathbf{x}=0}1_{B}(x_{1})\dotsm 1_{B}(x_{s})\geq
c\left(\tfrac{\delta^{2}}{4C}\right)N^{s-1}.$

Hence

$\displaystyle\sum_{\mathbf{c}\cdot\mathbf{x}}g(x_{1})\dotsm
g(x_{s})\geq(\delta/2)^{s}\sum_{\mathbf{c}\cdot\mathbf{x}}1_{B}(x_{1})\dotsm
1_{B}(x_{s})\geq(\delta/2)^{s}c\left(\tfrac{\delta^{2}}{4C}\right)N^{s-1}.$

∎

Let us sketch how this result, when combined with a transference principle,
allows one to extract a quantitative bound on the relative density of a subset
$A\subset S\subset[N]$ lacking non-trivial solutions to (1). Write
$\delta:=|A|/|S|$ for the relative density of $A$ in $S$. Then provided that
one has made a sensible choice for the weighted majorant $\nu$ on $S$, one
should have

$\sum_{n}1_{A}(n)\nu(n)\geq\delta^{c}N,$

for some absolute $c>0$. Applying a transference principle to the function
$f=1_{A}\nu$, one obtains an approximant $g$ supported on $[N]$ with bounded
$L^{2}$-norm of the form (11) and such that $\hat{f}\approx\hat{g}$ uniformly
on $\mathbb{T}$. Performing an approximation similar to (7) and applying Lemma
1.2 yields

$\sum_{\mathbf{c}\cdot\mathbf{x}=0}f(x_{1})\dotsm f(x_{s})\geq
c(\delta^{c},C)N^{s-1}.$ (16)

Yet if $A$ contains only trivial solutions to (1), we have

$\sum_{\mathbf{c}\cdot\mathbf{x}=0}f(x_{1})\dotsm
f(x_{s})\leq\sum_{\begin{subarray}{c}\mathbf{c}\cdot\mathbf{x}=0\\\
\mathbf{x}\text{ trivial}\end{subarray}}\nu(x_{1})\dotsm\nu(x_{s}).$ (17)

There are various possible candidates for what should constitute a trivial
solution to (1), one such choice being that $\mathbf{x}$ belongs to one of a
finite collection of proper subspaces of the hyperplane
$\mathbf{c}\cdot\mathbf{x}=0$. Whatever choice of triviality one makes, one
would expect that the trivial solutions should be a sparse subset of the
solution space, so that

$\sum_{\begin{subarray}{c}\mathbf{c}\cdot\mathbf{x}=0\\\ \mathbf{x}\text{
trivial}\end{subarray}}1_{[N]}(x_{1})\dotsm
1_{[N]}(x_{s})\leq\frac{N^{s-1}}{\omega(N)}$

for some function $\omega(N)\to\infty$. Moreover, a sensible choice of
majorant should respect this sparseness, so that

$\sum_{\begin{subarray}{c}\mathbf{c}\cdot\mathbf{x}=0\\\ \mathbf{x}\text{
trivial}\end{subarray}}\nu(x_{1})\dotsm\nu(x_{s})\ll\frac{N^{s-1}}{\omega(N)}.$

Combining this with (16) and (17) yields

$c(\delta,C)\ll\frac{1}{\omega(N)}.$

Using the lower bounds (3) and (13) then allows us to extract an upper bound
on $\delta$ in terms of $\omega(N)^{-1}$. For instance, if $C=O(1)$ then one
has

$c(\delta,C)\gg_{\mathbf{c}}\exp(-C_{s,\varepsilon}\delta^{-\frac{2}{s-2-\varepsilon}}),$

which implies that

$\delta\ll_{\mathbf{c},\varepsilon}\left(\log\omega(N)\right)^{-\frac{s}{2}+1+\varepsilon}.$
(18)

In view of Lemma 1.2 and the discussion which precedes it, our aim in the
remainder of this note is to provide sufficient conditions a majorant $\nu$
should satisfy to ensure that if $0\leq f\leq\nu$ with $\sum_{n}f(n)\geq\delta
N$ then there exists a function $g$ which is dense (as in (12)), which has
bounded $L^{2}$-norm (as in (11)), and such that
$\|\hat{f}-\hat{g}\|_{\infty}$ is small. As previously observed in (8), non-
negative functions which are close in the $L^{\infty}$-Fourier norm are also
close in the $L^{1}$-norm, so that

$\sum_{n}g(n)=\sum_{n}f(n)+O\left(\big{\|}\hat{f}-\hat{g}\big{\|}_{\infty}\right).$

Hence the density of $f$ automatically implies the density of $g$. We may
therefore drop the requirement that our approximant $g$ is dense, as this
follows from the Fourier approximation. Our aim is therefore to answer the
following question.

######  Question.

What conditions does a majorant $\nu$ on $[N]$ need to satisfy in order to
ensure that any function $0\leq f\leq\nu$ has a non-negative approximant $g$
with bounded $L^{2}$-norm and such that the difference
$\|\hat{f}-\hat{g}\|_{\infty}$ is small?

Any result which provides conditions answering this question we call a
_bounded approximation lemma_ , since we are attempting to approximate our
undbounded function $f$ by a function $g$ which exhibits less growth, as
measured by the $L^{2}$-norm.

###  1.3. Notation

In order to be consistent with the normalisation of our Fourier transform (5),
we define the $L^{p}$-norm of a function on the integers
$f:\mathbb{Z}\to\mathbb{C}$ with respect to counting measure, so that

$\left\|f\right\|_{p}:=\left(\sum_{n}|f(n)|^{p}\right)^{1/p}.$

For functions on $\mathbb{T}$, all $L^{p}$-norms are taken with respect to the
Haar probability measure, so that for finitely supported
$f:\mathbb{Z}\to\mathbb{C}$ we have

$\big{\|}\hat{f}\big{\|}_{2}=\left\|f\right\|_{2}$

Notice that if $\nu$ is a majorant then we also have the identity

$\left\|\hat{\nu}\right\|_{\infty}=\left\|\nu\right\|_{1}.$ (19)

##  2\. Green’s $L^{\infty}$-bounded approximation lemma

In this section we give a proof of perhaps the simplest bounded approximation
lemma, originating in Green [Gre05]. Not only does this yield an approximant
with bounded $L^{2}$-norm, but also bounded $L^{\infty}$-norm, so in some
sense this approximant has the best possible boundedness properties. The price
to be paid for such good boundedness is the quality of our final Fourier
approximation $\hat{f}\approx\hat{g}$.

######  Definition 2.1 (Fourier decay).

We say that a majorant $\nu$ on $[N]$ has _Fourier decay of level $\theta$_ if

$\left\|\hat{\nu}-\hat{1}_{[N]}\right\|_{\infty}\leq\theta N.$

Notice from (19), that if a majorant has Fourier decay of level $\theta$ then

$\left\|\nu\right\|_{1}=N+O(\theta N).$

######  Definition 2.2 (Restriction at $p$).

We say that a majorant $\nu$ supported on $[N]$ satisfies a _restriction
estimate at exponent $p$_ if

$\sup_{|\phi|\leq\nu}\int_{\mathbb{T}}\left|\hat{\phi}(\alpha)\right|^{p}\mathrm{d}\alpha\ll_{p}\left\|\nu\right\|_{1}^{p}N^{-1}.$

######  Theorem 2.1 (Green [Gre05]).

Suppose that the majorant $\nu$ has Fourier decay of level $\theta$ and
satisfies a restriction estimate at exponent $p$. Then for any $0\leq
f\leq\nu$ there exists $0\leq g\ll 1_{[N]}$ such that

$\big{\|}\hat{f}-\hat{g}\big{\|}_{\infty}\ll_{p}\log(\theta^{-1})^{-\frac{1}{p+2}}N.$

As the function $g$ delivered by this theorem is genuinely bounded, we call
this an _$L^{\infty}$ -bounded approximation lemma_.

We begin the proof of Theorem 2.1 by defining the large spectrum of $f$ to be
the set

$\mathrm{Spec}(f,\eta\left\|\nu\right\|_{1}):=\left\\{\alpha\in\mathbb{T}:|\hat{f}(\alpha)|\geq\eta\left\|\nu\right\|_{1}\right\\}.$

Define the Bohr set with frequency set
$S:=\mathrm{Spec}(f,\eta\left\|\nu\right\|_{1})$ and width $\varepsilon\leq
1/2$ by

$B(S,\varepsilon):=\left\\{n\in[-\varepsilon N,\varepsilon
N]:\left\|n\alpha\right\|\leq\varepsilon\quad(\forall\alpha\in S)\right\\}.$

Write $\sigma$ for the normalised characteristic function of
$B:=B(S,\varepsilon)$, so that

$\sigma:=|B|^{-1}1_{B}.$

Then we define

$g:=f*\sigma*\sigma,$ (20)

where, for finitely supported $f_{i}$, we set

$f_{1}*f_{2}(n):=\sum_{m_{1}+m_{2}=n}f_{1}(m_{1})f_{2}(m_{2}).$

We first estimate $|\hat{f}-\hat{g}|$. The key identity is

$\widehat{f_{1}*f_{2}}=\hat{f}_{1}\hat{f}_{2}.$

If $\alpha\notin\mathrm{Spec}(f,\eta N)$ then we have

$|\hat{f}(\alpha)-\hat{g}(\alpha)|=|\hat{f}(\alpha)||1-\hat{\sigma}(\alpha)^{2}|\leq
2\eta\left\|\nu\right\|_{1}\ll\eta N.$

If $\alpha\in\mathrm{Spec}(f,\eta N)$, then for each $n\in B$ we have
$e(\alpha n)=1+O(\varepsilon).$ Hence $\hat{\sigma}(\alpha)=1+O(\varepsilon),$
and consequently

$|\hat{f}(\alpha)-\hat{g}(\alpha)|=|\hat{f}(\alpha)||1+\hat{\sigma}(\alpha)||1-\hat{\sigma}(\alpha)|\ll\left\|\nu\right\|_{1}\varepsilon\ll\varepsilon
N.$

Combining both cases gives

$\big{\|}\hat{f}-\hat{g}\big{\|}_{\infty}\ll(\varepsilon+\eta)N.$ (21)

It remains to show that $g$ is bounded. By positivity and orthogonality, we
have

$\displaystyle g(n)=\sum_{x+y+z=n}f(x)\sigma(y)\sigma(z)$
$\displaystyle\leq\sum_{x+y+z=n}\nu(x)\sigma(y)\sigma(z)$
$\displaystyle=\int_{\mathbb{T}}\hat{\nu}(\alpha)\hat{\sigma}(\alpha)^{2}e(-\alpha
n)\mathrm{d}\alpha.$

It therefore suffices to show that

$\int_{\mathbb{T}}\hat{\nu}(\alpha)\hat{1}_{B}(\alpha)^{2}e(-\alpha
n)\mathrm{d}\alpha\ll|B|^{2}.$ (22)

Inserting our Fourier decay assumption and using Parseval, we have

$\displaystyle\int_{\mathbb{T}}\hat{\nu}(\alpha)\hat{1}_{B}(\alpha)^{2}e(-\alpha
n)\mathrm{d}\alpha$
$\displaystyle\leq\int_{\mathbb{T}}\hat{1}_{[N]}(\alpha)\hat{1}_{B}(\alpha)^{2}e(-\alpha
n)\mathrm{d}\alpha+\theta
N\int_{\mathbb{T}}|\hat{1}_{B}(\alpha)|^{2}\mathrm{d}\alpha$
$\displaystyle=\sum_{x+y+z=n}1_{[N]}(x)1_{B}(y)1_{B}(z)+\theta N|B|$
$\displaystyle\leq|B|^{2}+\theta N|B|.$

We therefore obtain (22) provided that

$\theta N\ll|B|.$ (23)

By Lemma A.2 we have $|B|\geq\varepsilon^{O_{p}(\eta^{-p-1})}N,$ so (23)
follows provided that $\theta\leq\varepsilon^{C_{p}\eta^{-1-p}}.$ In view of
(21), let us take $\varepsilon=\eta$ with
$\theta=\varepsilon^{C_{p}\eta^{-1-p}}.$ Then

$\log(\theta^{-1})\leq
C_{p}\log(\varepsilon^{-1})\varepsilon^{-1-p}\ll_{p}\varepsilon^{-2-p}.$

This implies that

$\big{\|}\hat{f}-\hat{g}\big{\|}_{\infty}\ll\varepsilon
N\ll_{p}\left(\log(\theta^{-1})\right)^{-\frac{1}{2+p}}N,$

which completes the proof of Theorem 2.1.

##  3\. Helfgott and De Roton’s $L^{2}$-bounded approximation lemma

For quantitative applications, a drawback of Green’s bounded approximation
lemma is the dependence of the final Fourier bound
$\|\hat{f}-\hat{g}\|_{\infty}$ on the level of Fourier decay $\theta$
exhibited by the majorant $\nu$. Typically our majorant satisfies a Fourier
decay assumption of the form

$\|\hat{\nu}-\hat{1}_{[N]}\|_{\infty}\ll N(\log N)^{-c}.$

This results in a final Fourier bound of the form

$\|\hat{f}-\hat{g}\|_{\infty}\ll N(\log\log N)^{-\frac{1}{p+2}}.$ (24)

Notice that this loses a logarithm over our assumed Fourier bound, even when
$f=\nu$, where we may take $g=1_{[N]}$.

In the process of improving Green’s bound [Gre05] for Roth’s theorem in the
primes, Helfgott and De Roton [HDR11] developed a new variant of the bounded
approximation lemma which removes this logarithmic loss from the final Fourier
bound. There is a price to be paid for this improvement. The first is that the
approximant may no longer be an $L^{\infty}$-bounded function, but instead has
the weaker property of being bounded in the $L^{2}$-norm. However, as Helfgott
and De Roton observed in Lemma 1.2, this is not really an impediment. A more
serious price must be paid in making a stronger assumption on their majorant
$\nu$ than Fourier decay.

######  Definition 3.1 (Two-point correlation estimate).

Let us say that a majorant satisfies a _two point correlation estimate_ if for
any non-zero $m$ we have

$\sum_{n}\nu(n)\nu(n+m)\ll N.$ (25)

######  Definition 3.2 ($L^{2}$-boundedness of level $\theta$).

We say that a majorant $\nu$ on $[N]$ has _$L^{2}$ -boundedness of level
$\theta$_ if

$\sum_{n}\nu(n)^{2}\leq\theta N^{2}.$ (26)

Notice that if a majorant satisfies the $L^{\infty}$-bound $\nu\leq\theta N$,
then the $L^{1}$-assumption (9) gives $L^{2}$-boundedness of level $\theta$.

######  Theorem 3.1 (Helfgott and De Roton [HDR11]).

Suppose that the majorant $\nu$ satisfies a restriction estimate at exponent
$p$, a two-point correlation estimate and has $L^{2}$-boundedness of level
$\theta$. Then for any $0\leq f\leq\nu$ there exists $g\geq 0$ such that
$\sum_{n}g(n)^{2}\ll N$ and

$\big{\|}\hat{f}-\hat{g}\big{\|}_{\infty}\ll_{p}\log(\theta^{-1})^{-\frac{1}{p+2}}N.$

In applications the $\theta$ parameter resulting from the level of
$L^{2}$-boundedness (29) is of the form $N^{-c}$ for some absolute constant
$c>0$. In practice, this is much smaller than the Fourier decay parameter
$\theta$ that one might hope to obtain for $\nu$, which is usually of the form
$(\log N)^{-c}$. This results in a final Fourier approximation of the form

$\|\hat{f}-\hat{g}\|_{\infty}\ll N(\log N)^{-\frac{1}{p+2}},$

which saves a logarithm over the estimate given in (24).

The proof of Theorem 3.1 is similar to that given in §2. Adopting the notation
of §2, we define $g$ as in (20), albeit with one less convolution

$g:=f*\sigma.$

The same argument given in §2 gives the Fourier bound

$\|\hat{f}-\hat{g}\|_{\infty}\ll(\varepsilon+\eta)N,$

so we take $\varepsilon=\eta$ to yield
$\|\hat{f}-\hat{g}\|_{\infty}\ll\varepsilon N$.

Now our treatment departs from that given previously as we are aiming to prove
the $L^{2}$-bound $\sum_{n}g(n)^{2}\ll N$, which is equivalent to

$\sum_{n_{1}-n_{2}=m_{1}-m_{2}}f(n_{1})f(n_{2})1_{B}(m_{1})1_{B}(m_{2})\ll
N|B|^{2}.$

Utilising $f\leq\nu$, this equals

$\sum_{m}\left(\sum_{m_{1}-m_{2}=m}1_{B}(m_{1})1_{B}(m_{2})\right)\left(\sum_{n}\nu(n)\nu(n+m)\right).$

Incorporating our assumptions (25) and (29), this is at most

$\theta N^{2}|B|+O(N|B|^{2}).$

We have therefore obtained $L^{2}$-boundedness provided that $\theta N\ll|B|$.
Recalling Lemma A.2, it suffices to have

$\theta\leq\varepsilon^{O_{p}(\varepsilon^{-p-1})},$

or equivalently

$C_{p}\log(\theta^{-1})^{-\frac{1}{p+2}}\leq\varepsilon.$

Taking the smallest permissible value of $\varepsilon$ then yields Theorem
3.1.

##  4\. Naslund’s $L^{k}$-bounded approximation lemma

As is apparent in the deduction of the density bound (18), if one is
interested in quantitative bounds for sets lacking solutions to (1), then the
quantitative dependence in (13) is important. Ideally, one would hope not to
lose too much by passing from the constant $c(\delta)$ available for the
characteristic function of a dense set, to the constant $c(\delta,C)$
available for a function with bounded $L^{2}$-norm. In a perfect world, this
loss would take the form, say

$c(\delta,C)=c\bigl{(}\tfrac{\delta}{100C}\bigr{)},$

whereas the proof of Lemma 1.2 yields

$c(\delta,C)=(\delta/2)^{s}c\bigl{(}\tfrac{\delta^{2}}{4C}\bigr{)}.$

The occurrence of the factor $\delta^{s}$ in (13) seems unavoidable.
Fortunately, this factor is not too costly, since it is much larger than the
lower bound (3) for $c(\delta)$. A more significant loss is the appearance of
$\delta^{2}$ within the function $c\bigl{(}\tfrac{\delta^{2}}{4C}\bigr{)}$,
which ultimately stems from the lower bound (15).

As observed by Naslund [Nas15], one may replace the use of Cauchy–Schwarz in
(14) by Hölder’s inequality in order to replace the occurrence of $\delta^{2}$
by, essentially, $\delta^{1+\varepsilon}$. This improvement ultimately stems
from aiming for an $L^{k}$-bounded approximant for some large $k$ (depending
on $\varepsilon$), rather than the weaker $L^{2}$-approximant of Helfgott and
De Roton. Since the $L^{k}$-norm of a finitely supported function tends to the
$L^{\infty}$-norm with $k$, one may think of $L^{k}$-boundedness as a half-way
house between the weak notion of $L^{2}$-boundedness and the strong
$L^{\infty}$-notion.

######  Lemma 4.1 ($L^{k}$-boundedness suffices).

Let $c_{1}+\dots+c_{s}=0$. Then for any $\delta>0$, any constant $C$ and any
$k\geq 2$ there exists $c(\delta,C,k)>0$ such that the following holds.
Suppose that $g:\mathbb{Z}\to[0,\infty)$ is a non-negative function supported
on $[N]$ which has bounded $L^{k}$-norm

$\sum_{n}g(n)^{k}\leq CN.$

Then the density assumption $\sum_{n}g(n)\geq\delta N$ implies that

$\sum_{\mathbf{c}\cdot\mathbf{x}=0}g(x_{1})\dotsm g(x_{s})\geq
c(\delta,C,k)N^{s-1},$

Moreover, one may take

$c(\delta,C,k)=(\delta/2)^{s}c\left(\left(\tfrac{\delta}{2C}\right)^{1+\frac{1}{k-1}}\right),$
(27)

where $c(\delta)$ is the constant appearing in Roth’s theorem (2).

###### Proof.

We proceed as in Helfgott and De Roton’s argument for Lemma 1.2, albeit using
Hölder’s inequality to give the upper bound

$\sum_{x\in
B}g(x)\leq|B|^{1-\frac{1}{k}}\left(\sum_{x}g(x)^{k}\right)^{\frac{1}{k}}.$

This results in the lower bound

$|B|\geq\left(\frac{\delta}{2C}\right)^{1+\frac{1}{k-1}}N,$

from which (27) follows. ∎

The price to paid for obtaining an approximant with the stronger notion of
$L^{k}$-boundedness is that one’s majorant must now satisfy a more stringent
correlation condition.

######  Definition 4.2 ($k$-point correlation estimates).

Let us say that a majorant satisfies the _$k$ -point correlation estimates_ if
for any distinct $m_{1},\dots,m_{l}$ with $l\leq k$ we have

$\sum_{n}\nu(n+m_{1})\dotsm\nu(n+m_{l})\ll N.$ (28)

######  Definition 4.3 ($L^{\infty}$-boundedness of level $\theta$).

We say that a majorant $\nu$ on $[N]$ has _$L^{\infty}$ -boundedness of level
$\theta$_ if for all $n$ we have

$\nu(n)\leq\theta N.$ (29)

By assumption a majorant satisfies $\sum_{n}\nu(n)=(1+o(1))N$, so that the
level of $L^{\infty}$-boundedness is at worst $O(1)$, and unless $\nu$ is
concentrated on a bounded set, will be $o(1)$ in applications.

######  Theorem 4.1 (Naslund [Nas15]).

Suppose that $\nu$ is a majorant on $[N]$ satisfying a restriction estimate at
exponent $p$, with $L^{\infty}$-boundedness of level $\theta$ and satisfying
the $k$-point correlation estimates with

$k\leq\tfrac{1}{2}\sqrt{\log(\theta^{-1})}.$ (30)

Then for any $0\leq f\leq\nu$ there exists $g\geq 0$ such that
$\sum_{n}g(n)^{k}\ll N$ and

$\big{\|}\hat{f}-\hat{g}\big{\|}_{\infty}\ll_{p}\log(\theta^{-1})^{-\frac{1}{p+2}}N.$

In order to employ this result in conjunction with Lemma 4.1, one might hope,
in view of (27), to take $k=\left\lceil 1+\varepsilon^{-1}\right\rceil$. As
mentioned previously, in applications we expect to be able to obtain
$L^{\infty}$-boundedness of level $N^{-c}$. Hence (30) certainly follows if
$N\geq\exp(C\varepsilon^{-2})$. Provided that one can prove the
$(1+\varepsilon^{-1})$-point correlation estimates, one may then deduce a
lower bound in (27) of the form

$c(\delta,C)\gg_{\varepsilon}(\delta/2)^{s}c\left(\left(\tfrac{\delta}{2C}\right)^{1+\varepsilon}\right).$

###### Proof.

The construction is the same as in the proof of Theorem 3.1. Just as in that
proof we take $\eta=\varepsilon$ to obtain an approximant $g\geq 0$ with
$\|\hat{f}-\hat{g}\|_{\infty}\ll\varepsilon N$. Our task then reduces to
determining a permissible value of $\varepsilon$ which allows one to show that

$\sum_{n}\left(\sum_{m}\nu(n-m)1_{B}(m)\right)^{k}\ll N|B|^{k}.$

Expanding out the $k$th power and noting that $B=-B$, this is equivalent to
the estimate

$\sum_{m_{1},\dots,m_{k}\in B}\ \sum_{n}\nu(n+m_{1})\dotsm\nu(n+m_{k})\ll
N|B|^{k}.$ (31)

Fix a choice of $(m_{1},\dots,m_{k})\in B^{k}$ and let
$(m_{1}^{\prime},\dots,m_{l}^{\prime})$ denote the distinct values occurring
in this choice, written in the order in which they appear in the tuple, and
with respective multiplicities $k_{1},\dots,k_{l}$. Then by the level of
$L^{\infty}$-boundedness and the $k$-point correlation estimate, we have

$\displaystyle\sum_{n}\nu(n+m_{1})\dotsm\nu(n+m_{k})$
$\displaystyle=\sum_{n}\nu(n+m_{1}^{\prime})^{k_{1}}\dotsm\nu(n+m_{l}^{\prime})^{k_{l}}$
$\displaystyle\leq(\theta
N)^{k-l}\sum_{n}\nu(n+m_{1}^{\prime})\dotsm\nu(n+m_{l}^{\prime})$
$\displaystyle\ll(\theta N)^{k-l}N.$

By choosing one of the symbols ‘$=$’ or ‘$\neq$’ for each pair of indices
$1\leq i<j\leq k$, we see that for each choice of tuple
$(m_{1}^{\prime},\dots,m_{l}^{\prime})\in B^{l}$ with distinct entries, there
are at most $2^{\binom{k}{2}}$ choices of $(m_{1},\dots,m_{k})\in B^{k}$
giving rise to $(m_{1}^{\prime},\dots,m_{l}^{\prime})$. It follows that

$\displaystyle\sum_{m_{1},\dots,m_{k}\in B}\
\sum_{n}\nu(n+m_{1})\dotsm\nu(n+m_{k})$
$\displaystyle\ll\sum_{l=1}^{k}2^{\binom{k}{2}}|B|^{l}(\theta N)^{k-l}N$
$\displaystyle\leq|B|^{k}N\max_{1\leq l\leq
k}\left(\frac{k2^{\binom{k}{2}}\theta N}{|B|}\right)^{l}$

The required bound (31) then follows on ensuring that $|B|\geq
k2^{\binom{k}{2}}\theta N$, which from Lemma A.2, follows if

$\varepsilon^{O_{p}(\varepsilon^{-p-1})}\geq k2^{\binom{k}{2}}\theta.$

This in turn follows if

$\log(\theta^{-1})\geq\log k+\binom{k}{2}\log 2+C_{p}\varepsilon^{-p-2}.$

By (30) and the inequality $\log k+\binom{k}{2}\log 2\leq k^{2}$, it suffices
to take

$\varepsilon=\left(\frac{2C_{p}}{\log(\theta^{-1})}\right)^{\frac{1}{p+2}}.$

∎

##  5\. The Hahn–Banach approach

The fact that a majorant satisfies a restriction estimate at some exponent $p$
is essential in applications of the transference principle to the circle
method, see for instance [GT06, Har, BP]. In general, if a function $f$ is
efficiently bounded by a majorant $\nu$, one can count solutions to a linear
equation in $s$ variables weighted by $f$ provided that one can obtain a
restriction estimate for $\nu$ for some $p<s$.

The limited use of the restriction esimate in the proof of theorems 2.1, 3.1
and 4.1 suggests that it may not be necessary for a majorant $\nu$ to satisfy
such an estimate in order for $f\leq\nu$ to have a bounded approximation. This
was first shown by Gowers [Gow10] and, independently, by Reingold et al
[RTTV]. It turns out that removing the quantitative dependence of the final
Fourier approximation on the restriction parameter gives a marginally stronger
bound. Their method extends to give a bounded approximation lemma for norms
other that the $L^{\infty}$-Fourier norm, giving an alternative derivation of
the transference principle found in [GT08, TZ08], and which is essential for
applications to systems of linear equations such as [GT10, Mat12]. In this
section we give an exposition of their argument limited to the simpler
Fourier-analytic context.

In common with Green’s transference principle, the approximation theorem
assumes some level of Fourier decay. Although quantitativley weaker than the
assumption of a correlation condition, this is in some sense a more useful
assumption for applications, such as [BP], where the correlation estimates
(25) and (28) do not necessarily hold.

######  Theorem 5.1 ([Gow10, RTTV]).

Suppose that the majorant $\nu$ has Fourier decay of level $\theta$. Then for
any $0\leq f\leq\nu$ there exists a bounded function $0\leq g\leq 1_{[N]}$
such that

$\big{\|}\hat{f}-\hat{g}\big{\|}_{\infty}\ll\log(1/\theta)^{-3/2}N.$

Both [Gow10] and [RTTV] follow similar lines in proving this result, employing
either the supporting hyperplane theorem or the minimax theorem to give the
existence of $g$, rather than the explicit construction of §§2–4. Both of
these subsidiary results are closely related to the finite dimensional
Hahn–Banach theorem. We give a complete account of the necessary background in
the appendices.

We identify the set of functions $f:\mathbb{Z}\to\mathbb{C}$ whose support is
contained in $[N]$ with the finite dimensional space $\mathbb{C}^{N}$. Then
the functional

$\left\|f\right\|:=\big{\|}\hat{f}\big{\|}_{\infty}$

forms a norm on this space. Recall that we define the dual norm by

$\left\|\phi\right\|^{*}:=\sup_{\left\|f\right\|\leq 1}\left|\left\langle
f,\phi\right\rangle\right|,$

where

$\left\langle f,\phi\right\rangle:=\sum_{n=1}^{N}f(n)\overline{\phi(n)}.$

One can check that this is itself a norm on $\mathbb{C}^{N}$, and it follows
directly from the definition that for any $f,\phi\in\mathbb{C}^{N}$ we have
the inequality

$\left|\left\langle
f,\phi\right\rangle\right|\leq\left\|f\right\|\left\|\phi\right\|^{*}.$ (32)

######  Lemma 5.1 (Properties of the dual of
$\big{\|}\hat{f}\big{\|}_{\infty}$).

  1. (i)

(Algebra property)

$\left\|\phi_{1}\phi_{2}\right\|^{*}\leq\left\|\phi_{1}\right\|^{*}\left\|\phi_{2}\right\|^{*}.$
(33)

  2. (ii)

($L^{\infty}$–compatibility)

$\left\|\phi\right\|_{\infty}\leq\left\|\phi\right\|^{*}.$

  3. (iii)

(Real compatibility)

$\left\|\mathrm{Re}\,\phi\right\|^{*}\leq\left\|\phi\right\|^{*}.$

  4. (iv)

(Duality) For any $f\in\mathbb{C}^{N}$ there exists $\phi\in\mathbb{C}^{N}$
with $\left\|\phi\right\|^{*}=1$ such that

$\left\|f\right\|=\mathrm{Re}\left\langle f,\phi\right\rangle.$

###### Proof.

Let $f\in\mathbb{C}^{N}$ with $\left\|f\right\|\leq 1$. Then by (32) we have

$\displaystyle\left|\left\langle
f,\phi_{1}\phi_{2}\right\rangle\right|=\left|\left\langle
f\overline{\phi}_{1},\phi_{2}\right\rangle\right|\leq\big{\|}f\overline{\phi}_{1}\big{\|}\big{\|}\phi_{2}\big{\|}^{*}.$

For $\alpha\in\mathbb{T}$ write $e_{\alpha}(n):=e(\alpha n)$. Then

$\displaystyle\bigl{|}\widehat{f\overline{\phi}_{1}}(\alpha)\bigr{|}$
$\displaystyle=\left|\left\langle fe_{\alpha},\phi_{1}\right\rangle\right|$
$\displaystyle\leq\left\|fe_{\alpha}\right\|\left\|\phi_{1}\right\|^{*}.$

By a change of variables we have
$\left\|fe_{\alpha}\right\|=\left\|f\right\|\leq 1$. Thus
$\left\|f\overline{\phi}_{1}\right\|\leq\left\|\phi_{1}\right\|^{*}$, which
establishes (i).

To prove (ii) it suffices, by homogeneity, to show that the ball
$B^{*}:=\left\\{\phi\in\mathbb{C}^{N}:\left\|\phi\right\|^{*}\leq 1\right\\}$
is contained in the ball
$B_{\infty}:=\left\\{\phi\in\mathbb{C}^{N}:\left\|\phi\right\|_{\infty}\leq
1\right\\}.$ By equivalence of norms on finite dimensional spaces, $B^{*}$ is
a bounded subset of $\mathbb{C}^{N}$. Suppose that $\phi$ is an element of
$B^{*}\setminus B_{\infty}$, so that $|\phi(n)|>1$ for some $n\in[N]$. By the
algebra property (33), $\phi^{k}\in B^{*}$ for all $k\in\mathbb{N}$. Yet
$|\phi^{k}(n)|\to\infty$ as $k\to\infty$, contradicting boundedness.

For (iii), we first note that $\left\|\cdot\right\|$ is invariant under
complex conjugation, since

$\displaystyle\left\|\overline{f}\right\|=\sup_{\alpha}\left|\sum_{n}\overline{f(n)}e(\alpha
n)\right|=\sup_{\alpha}\left|\sum_{n}f(n)e(-\alpha
n)\right|=\left\|f\right\|.$

It follows that

$\left\|\overline{\phi}\right\|^{*}=\sup_{\left\|f\right\|\leq
1}\left|\left\langle
f,\overline{\phi}\right\rangle\right|=\sup_{\left\|f\right\|\leq
1}\left|\left\langle\overline{f},\phi\right\rangle\right|=\sup_{\left\|g\right\|\leq
1}\left|\left\langle g,\phi\right\rangle\right|=\left\|\phi\right\|^{*}.$

Hence by the triangle inequality and homogeneity

$\left\|\mathrm{Re}\,\phi\right\|^{*}=\left\|\frac{\phi+\overline{\phi}}{2}\right\|^{*}\leq\frac{\left\|\phi\right\|^{*}+\left\|\phi\right\|^{*}}{2}=\left\|\phi\right\|^{*}.$

To prove (iv) it suffices to prove that for $f\neq 0$ there exists $\phi\neq
0$ such that $\mathrm{Re}\left\langle
f,\phi\right\rangle\geq\left\|f\right\|\left\|\phi\right\|^{*}$, as the
reverse inequality follows from (32), and (iv) then follows by homogeneity.
Consider the convex set
$C=\left\\{g:\left\|g\right\|\leq\left\|f\right\|\right\\}$. Since
$f\notin\mathrm{int}\,(C)$, the complex supporting hyperplane theorem
(Corollary B.8) gives the existence of $\phi\neq 0$ such that for any
$\left\|g\right\|\leq\left\|f\right\|$ we have

$\mathrm{Re}{\left\langle f,\phi\right\rangle}\geq\mathrm{Re}{\left\langle
g,\phi\right\rangle}.$

For each $g$ with $\left\|g\right\|\leq\left\|f\right\|$ there exists
$|\theta|=1$ such that

$|\left\langle g,\phi\right\rangle|=\theta\left\langle
g,\phi\right\rangle=\left\langle\theta
g,\phi\right\rangle=\mathrm{Re}{\left\langle\theta g,\phi\right\rangle}.$

Notice that $\left\|\theta g\right\|\leq\left\|f\right\|$ also, therefore

$\mathrm{Re}{\left\langle
f,\phi\right\rangle}\geq\mathrm{Re}{\left\langle\theta
g,\phi\right\rangle}=|\left\langle g,\phi\right\rangle|.$

Hence by homogeneity

$\mathrm{Re}\left\langle
f,\phi\right\rangle\geq\sup_{\left\|g\right\|\leq\left\|f\right\|}|\left\langle
g,\phi\right\rangle|=\left\|f\right\|\sup_{\left\|g\right\|\leq
1}|\left\langle g,\phi\right\rangle|=\left\|f\right\|\left\|\phi\right\|^{*}.$

∎

###### Proof of Theorem 5.1.

We prove the contrapositive, supposing there exists $0\leq f\leq\nu$ such that
for any $0\leq g\leq 1_{[N]}$ we have

$\big{\|}f-{g}\big{\|}>\varepsilon N.$

Our aim is to deduce that
$\left\|\nu-1_{[N]}\right\|>\exp\left(-C\varepsilon^{-2/3}\right)N$. If
$\left\|\nu-1_{[N]}\right\|>N$ we are done, so we may assume that
$\left\|\nu-1_{[N]}\right\|\leq N$. In particular, it is useful to note for
later that

$\left\|\nu\right\|_{1}=\left\|\hat{\nu}\right\|_{\infty}\leq\left\|\hat{1}_{[N]}\right\|_{\infty}+\left\|\hat{\nu}-\hat{1}_{[N]}\right\|_{\infty}\leq
2N.$ (34)

By Lemma 5.1 (iv), for each $0\leq g\leq 1_{[N]}$ there exists $\phi_{g}$ with
$\left\|\phi_{g}\right\|^{*}=1$ such that

$\mathrm{Re}\left\langle f-g,\phi_{g}\right\rangle>\varepsilon N.$ (35)

Consider the subsets of $\mathbb{C}^{N}$ given by

$A:=\left\\{g-f:0\leq g\leq 1_{[N]}\right\\}\quad\text{and}\quad
B:=\left\\{\phi:\left\|\phi\right\|^{*}\leq 1\right\\}.$

One can check that both $A$ and $B$ are convex, compact and non-empty.
Moreover, $A$ is the convex hull of the finite set
$\left\\{1_{S}-f:S\subset[N]\right\\}$. Applying the minimax theorem
(Corollary C.2), there exists $0\leq{g_{0}}\leq 1_{[N]}$ and
$\left\|{\phi_{0}}\right\|^{*}\leq 1$ such that for any $0\leq g\leq 1_{[N]}$
and $\left\|\phi\right\|^{*}\leq 1$ we have

$\mathrm{Re}\left\langle{g_{0}}-f,\phi\right\rangle\geq\mathrm{Re}\left\langle
g-f,{\phi_{0}}\right\rangle.$

In particular, using (35) we see that for any $0\leq g\leq 1_{[N]}$ we have

$\mathrm{Re}\left\langle
f-g,{\phi_{0}}\right\rangle\geq\mathrm{Re}\left\langle
f-{g_{0}},\phi_{{g_{0}}}\right\rangle>\varepsilon N.$

Set $\psi:=\mathrm{Re}\,{\phi_{0}}$ and write $\psi_{+}$ for the positive part
of $\psi$. Taking $g:=1_{\psi\geq 0}$, non-negativity gives that

$\left\langle\nu,\psi_{+}\right\rangle\geq\left\langle
f,\psi_{+}\right\rangle\geq\left\langle
f,\psi\right\rangle=\mathrm{Re}\left\langle
f,{\phi_{0}}\right\rangle>\mathrm{Re}\left\langle
g,{\phi_{0}}\right\rangle+\varepsilon N=\left\langle
1_{[N]},\psi_{+}\right\rangle+\varepsilon N.$

Therefore

$\left\langle\nu-1_{[N]},\psi_{+}\right\rangle>\varepsilon N.$

By $L^{\infty}$–compatibility (Lemma 5.1 (ii)) we have

$\left\|\psi\right\|_{\infty}\leq\left\|\phi_{0}\right\|_{\infty}\leq\left\|\phi_{0}\right\|^{*}\leq
1.$

Hence by the Weierstrass polynomial approximation theorem (Lemma D) there
exists a polynomial $P$ of degree at most $C\varepsilon^{-2/3}$ and height at
most $\exp(C\varepsilon^{-2/3})$ such that

$\left\|P\circ\psi-\psi_{+}\right\|_{\infty}\leq\tfrac{1}{4}\varepsilon$

Using this and the observation (34), we see that

$\displaystyle\left\langle\nu-1_{[N]},P\circ\psi\right\rangle$
$\displaystyle=\left\langle\nu-1_{[N]},\psi_{+}\right\rangle+\left\langle\nu-1_{[N]},P\circ\psi-\psi_{+}\right\rangle$
$\displaystyle\geq\varepsilon
N-\left\|\nu-1_{[N]}\right\|_{1}\left\|P\circ\psi-\psi_{+}\right\|_{\infty}$
$\displaystyle\geq\tfrac{1}{2}\varepsilon N.$

By (32) it follows that

$\left\|\nu-1_{[N]}\right\|\left\|P\circ\psi\right\|^{*}\geq\tfrac{1}{2}\varepsilon
N.$ (36)

By real compatibility (Lemma 5.1 (iii)), we have
$\left\|\psi\right\|^{*}\leq\left\|\phi_{0}\right\|^{*}\leq 1.$ Hence by the
algebra property (Lemma 5.1 (i)) and the triangle inequality, we deduce that

$\left\|P\circ\psi\right\|^{*}\ll\exp(C\varepsilon^{-2/3}).$

Combining this with (36) finally yields the required bound. ∎

##  Appendix A The large spectrum and Bohr sets

As in §2 we define the $(\eta\left\|\nu\right\|_{1})$-large spectrum of $f$ to
be the set

$\mathrm{Spec}(f,\eta\left\|\nu\right\|_{1}):=\left\\{\alpha\in\mathbb{T}:|\hat{f}(\alpha)|\geq\eta\left\|\nu\right\|_{1}\right\\}.$

Notice that this set is empty unless $\eta\leq 1$, which we assume throughout
what follows.

######  Lemma A.1.

Suppose that $\nu$ is a majorant on $[N]$ satisfying a restriction estimate at
exponent $p$. Then for any $0\leq f\leq\nu$ we have

$\mathrm{meas}\bigl{(}\mathrm{Spec}(f,\eta\left\|\nu\right\|_{1})\bigr{)}\ll_{p}\eta^{-p}N^{-1}.$

###### Proof.

We have

$\displaystyle\mathrm{meas}\left(\mathrm{Spec}(f,\eta N)\right)$
$\displaystyle\leq(\eta\left\|\nu\right\|_{1})^{-p}\int_{\mathrm{Spec}(f,\eta
N)}|f(\alpha)|^{p}\mathrm{d}\alpha$
$\displaystyle\leq(\eta\left\|\nu\right\|_{1})^{-p}\int_{\mathbb{T}}|f(\alpha)|^{p}\mathrm{d}\alpha.$

By the restriction estimate we have

$\int_{\mathbb{T}}|f(\alpha)|^{p}\mathrm{d}\alpha\ll_{p}\left\|\nu\right\|_{1}^{p}N^{-1}.$

∎

Define the Bohr set with frequency set $S\subset\mathbb{T}$ and width
$\varepsilon\leq 1/2$ by

$B(S,\varepsilon):=\left\\{n\in[-\varepsilon N,\varepsilon
N]:\left\|n\alpha\right\|\leq\varepsilon\quad(\forall\alpha\in S)\right\\}.$

######  Lemma A.2.

Suppose that $\nu$ is a majorant on $[N]$ satisfying a restriction estimate at
exponent $p$. Then for $0\leq f\leq\nu$ and
$S=\mathrm{Spec}(f,\eta\left\|\nu\right\|_{1})$ we have

$|B(S,\varepsilon)|\geq\varepsilon^{O_{p}(\eta^{-p-1})}N.$

###### Proof.

Set

$M:=\left\lceil 4\pi N\eta^{-1}\right\rceil$

and partition $\mathbb{T}$ into $M$ half-open intervals of length $M^{-1}$.
Let $I_{1},\dots,I_{r}$ denote those intervals which intersect
$S=\mathrm{Spec}(f,\eta N)$. We claim that

$\bigcup_{i=1}^{r}I_{i}\subset\mathrm{Spec}(f,\tfrac{1}{2}\eta\left\|\nu\right\|_{1}).$

To see this, let us fix a choice of $\alpha_{i}\in I_{i}\cap S$ for each $i$.
If $\alpha\in I_{i}$ then $\left\|\alpha-\alpha_{i}\right\|\leq\eta/(4\pi N)$
so that

$\displaystyle|\hat{f}(\alpha)|$
$\displaystyle\geq|\hat{f}(\alpha_{i})|-|\hat{f}(\alpha)-\hat{f}(\alpha_{i})|$
$\displaystyle\geq\eta\left\|\nu\right\|_{1}-\left\|f\right\|_{1}N2\pi\left\|\alpha-\alpha_{i}\right\|$
$\displaystyle\geq\tfrac{1}{2}\eta\left\|\nu\right\|_{1}.$

By Lemma A.1 we therefore have

$r\eta/N\ll\mathrm{meas}\bigl{(}\bigcup_{i=1}^{r}I_{i}\bigr{)}\ll_{p}\eta^{-p}/N,$

so that

$r\ll_{p}\eta^{-1-p}.$

One can check that

$B(\left\\{\alpha_{1},\dots,\alpha_{r}\right\\},\varepsilon/2)\subset
B(S,\varepsilon).$

Therefore

$|B(S,\varepsilon)|\geq|B(\left\\{\alpha_{1},\dots,\alpha_{r}\right\\},\varepsilon/2)|.$

Set $T:=\left\lceil 2/\varepsilon\right\rceil$ and partition $\mathbb{T}^{r}$
into $T^{r}$ half-open cubes of side-length $T^{-1}$. By the pigeon-hole
principle, some such cube $C$ contains the point
$n(\alpha_{1},\dots,\alpha_{r})$ for at least $\frac{1}{2}\varepsilon NT^{-r}$
values of $n\in[0,\frac{1}{2}\varepsilon N]$. Then
$C-C\subset[-T^{-1},T^{-1}]^{r}$ contains at least $\frac{1}{2}\varepsilon
NT^{-r}$ values of $n\in[-\frac{1}{2}\varepsilon N,\frac{1}{2}\varepsilon N]$.
In conclusion, we have shown that

$|B(\left\\{\alpha_{1},\dots,\alpha_{r}\right\\},\varepsilon/2)|\geq\tfrac{1}{2}\varepsilon
N\left\lceil 2/\varepsilon\right\rceil^{-r}\geq\left\lceil
2/\varepsilon\right\rceil^{-(r+1)}N.$

The lemma now follows. ∎

##  Appendix B The supporting hyperplane theorem

In this appendix we give an account of the supporting hyperplane theorem,
employed in §5, and also needed in the proof of the minimax theorem given in
Appendix C. The result is itself a weak version of the finite dimensional
Hahn–Banach theorem and is standard. However, we have not found a satisfactory
reference for the version of the result we require.

######  Definition B.1 (Affine independence).

We say $x_{0},x_{1},\dots,x_{k}\in\mathbb{R}^{n}$ are _affinely dependent_ if
there exist $\lambda_{i}\in\mathbb{R}$ not all zero such that

$\sum_{i=1}^{k}\lambda_{i}x_{i}=0\quad\text{and}\quad\sum_{i=1}^{k}\lambda_{i}=0.$

Equivalently, the differences $x_{1}-x_{0},\dots,x_{k}-x_{0}$ are linearly
dependent.

######  Lemma B.2.

If $x_{0},x_{1},\dots,x_{n}\in\mathbb{R}^{n}$ are affinely independent, then
the simplex

$\left\\{\sum_{i=0}^{n}\lambda_{i}x_{i}:\lambda_{i}>0,\
\sum_{i=0}^{n}\lambda_{i}=1\right\\}$ (37)

is a non-empty open set.

###### Proof.

The set

$\Delta:=\left\\{\mu\in\mathbb{R}^{n}:\mu_{i}>0,\
\sum_{i=1}^{n}\mu_{i}<1\right\\}$

is the finite intersection of $n+1$ open sets each containing
$(1/2,\dots,1/2)$, so is itself a non-empty open set.

The simplex (37) is equal to

$\left\\{\sum_{i=1}^{n}\mu_{i}(x_{i}-x_{0}):\mu_{i}>0,\
\sum_{i=1}^{n}\mu_{i}<1\right\\},$

which is the image of $\Delta$ under a map with continuous inverse. Hence (37)
is open and non-empty. ∎

Given $x\in\mathbb{R}^{n}$, write

$\left|x\right|_{\infty}:=\max_{i}|x_{i}|\quad\text{and}\quad
B^{\infty}_{\varepsilon}(x):=\left\\{y\in\mathbb{R}^{n}:\left|x-y\right|_{\infty}<\varepsilon\right\\}.$

######  Lemma B.3.

For $x_{0},x_{1},\dots,x_{n}\in\mathbb{R}^{n}$ affinely independent, there
exists $\varepsilon>0$ such that for any $y\in
B^{\infty}_{\varepsilon}(x_{n})$ the vectors $x_{0},\dots,x_{n-1},y$ are also
affinely independent.

###### Proof.

Let $T$ denote the invertible linear map
$\lambda\mapsto\sum_{i}\lambda_{i}(x_{i}-x_{0})$. Then there exists
$C=C(x_{i})>0$ such that for any $v\in\mathbb{R}^{n}$ we have

$\left|T^{-1}v\right|_{\infty}\leq C\left|v\right|_{\infty}.$

Suppose that $x_{0},\dots,x_{n-1},x_{n}+v$ are affinely dependent. Then there
exist $\lambda_{i}$ with $\lambda_{n}=1$ such that

$\sum_{i=1}^{n}\lambda_{i}(x_{i}-x_{0})=-v.$

Therefore $|T^{-1}v|_{\infty}\geq 1$, which in turn implies that
$|v|_{\infty}\geq C^{-1}$. The lemma now follows on taking
$\varepsilon=C^{-1}$. ∎

Given a subset $C$ of a topological space, write $\overline{C}$ for its
closure and $\mathrm{int}\,(C)$ for its interior.

######  Lemma B.4.

Let $C\subset\mathbb{R}^{n}$ be a convex set. Then
$\mathrm{int}\,(C)=\emptyset$ if and only if
$\mathrm{int}\,(\overline{C})=\emptyset$.

###### Proof.

It suffices to prove the contrapositive of the ‘only if’ direction. Let
$x\in\mathrm{int}\,(\overline{C})$, so that there exists $\varepsilon>0$ such
that

$B_{\varepsilon}^{\infty}(x)\subset\overline{C}.$

Taking $x_{0}=x$ and $x_{i}=x+(\varepsilon/2)e_{i}$, one sees that the set
$B_{\varepsilon}^{\infty}(x)$ contains $n+1$ affinely independent points.

By Lemma B.3 there exists $\delta>0$ such that
$B_{\delta}^{\infty}(x_{n})\subset B_{\varepsilon}^{\infty}(x)$ and for any
$y\in B_{\delta}(x_{n})$ the vectors $x_{0},x_{1},\dots,x_{n-1},y$ are
affinely independent. Since $x_{n}\in\overline{C}$, there exists
$x_{n}^{\prime}\in B_{\delta}(x_{n})\cap C$, so that
$x_{0},x_{1},\dots,x_{n-1},x_{n}^{\prime}$ are affinely independent elements
of $B_{\varepsilon}^{\infty}(x)$.

Repeating the above argument with $x_{i}$ in place of $x_{n}$, we see that we
can find affinely independent
$x_{0}^{\prime},x_{1}^{\prime},\dots,x_{n}^{\prime}\in\subset
B_{\varepsilon}^{\infty}(x)\cap C$. It then follows from convexity and Lemma
B.2 that the set

$\left\\{\sum_{i=0}^{n}\lambda_{i}x_{i}^{\prime}:\lambda_{i}>0,\
\sum_{i=0}^{n}\lambda_{i}=1\right\\}$

is a non-empty open subset of $C$.

∎

######  Lemma B.5.

Let $C$ be a convex subset of $\mathbb{R}^{n}$ with $x\in\mathrm{int}\,(C)$
and $y\in\overline{C}$. Then $\mathrm{int}\,(C)$ contains the line segment

$[x,y):=\left\\{(1-\lambda)x+\lambda y:\lambda\in[0,1)\right\\}.$

###### Proof.

Since $x\in\mathrm{int}\,(C)$ there exists an open set $U\subset C$ with $x\in
U$. Let $z\in(x,y)$, so that there exists $\lambda\in(0,1)$ with

$z=(1-\lambda)x+\lambda y.$

Taking $\mu=\lambda^{-1}$ we have

$y=\mu z+(1-\mu)x,$

so that $y$ is an element of the open set

$V:=\bigcup_{\mu>1}\left(\mu z+(1-\mu)\cdot U\right).$

Since $y\in\overline{C}$, there exists $y_{1}\in V\cap C$. Hence there exists
$\mu_{1}>1$ and $u_{1}\in U$ such that

$y_{1}=\mu_{1}z+(1-\mu_{1})u_{1}.$

Taking $\lambda_{1}=\frac{1}{\mu_{1}}$, we have

$z=\lambda_{1}y_{1}+(1-\lambda_{1})u_{1},$

so that $z$ is an element of the open set

$W:=\bigcup_{0\leq\lambda<1}\left(\lambda y_{1}+(1-\lambda)\cdot U\right).$

By convexity $W\subset C$, hence $z\in\mathrm{int}\,(C)$. ∎

######  Lemma B.6.

If $C\subset\mathbb{R}^{n}$ is convex then

$\mathrm{int}\,(C)=\mathrm{int}\,(\overline{C}).$

###### Proof.

By Lemma B.4 we may assume that $\mathrm{int}\,(C)$ is non-empty. It suffices
to show that if $B_{\varepsilon}(x)\subset\overline{C}$ for some
$\varepsilon>0$ then $x\in\mathrm{int}\,(C)$. Let $x_{0}\in\mathrm{int}\,(C)$.
Choosing $\delta>0$ sufficiently small, one can ensure that

$y:=x+\delta(x-x_{0})\in B_{\varepsilon}(x)\subset\overline{C}.$

Hence by the previous lemma $[x_{0},y)\subset\mathrm{int}\,(C)$. Taking
$\lambda=\frac{1}{1+\delta}$ we see that

$x=(1-\lambda)x_{0}+\lambda y\in(x_{0},y)\subset\mathrm{int}\,{C}.$

∎

In order to distinguish between the complex inner product on $\mathbb{C}^{n}$
and the real inner product on $\mathbb{R}^{2n}$, we write $\left\langle
x,y\right\rangle$ for the former and $x\cdot y$ for the latter.

######  Lemma B.7 (Supporting hyperplane theorem).

Let $C$ be a convex subset of $\mathbb{R}^{n}$ and $x\notin\mathrm{int}\,{C}$.
Then there exists a non-zero vector
$\phi\in\mathbb{R}^{n}\setminus\left\\{0\right\\}$ such that for all
$y\in\overline{C}$ we have

$y\cdot\phi\leq x\cdot\phi.$

###### Proof.

Let us first prove the result under the assumption that $x\notin\overline{C}$.
The result is trivial if $C=\emptyset$, so we may assume that
$C\neq\emptyset$. Using absolute values to denote the $L^{2}$-norm on
$\mathbb{R}^{n}$, it follows that there exists $y_{0}\in\overline{C}$ such
that

$|y_{0}-x|=\inf_{y\in\overline{C}}|y-x|.$

Heuristically, we expect that for any $y\in\overline{C}$, the angle formed in
the plane between $x-y_{0}$ and $y-y_{0}$ should be obtuse. If this angle were
acute, then there should exist a point $y_{1}$ on the line segment between $y$
and $y_{0}$ such that $x$ is closer to $y_{1}$ than $y_{0}$ (draw a picture).
Since $\overline{C}$ is convex we have $y_{1}\in\overline{C}$ and we have
contradicted our choice of $y_{0}$.

More rigourously, we show that for any $y\in\overline{C}$ we have

$\left(x-y_{0}\right)\cdot\left(y-y_{0}\right)\leq 0.$ (38)

Suppose this is not the case. Then we claim that there exists $t\in(0,1]$ such
that

$|(1-t)y_{0}+ty-x|<|y_{0}-x|,$

and hence obtain our desired contradiction. Write
$(1-t)y_{0}+ty-x=y_{0}-x+t(y-y_{0})$, then square, expand out and divide
through by $t$ to deduce that this is equivalent to the existence of
$t\in(0,1]$ such that

$t|y-y_{0}|^{2}<2\left(x-y_{0}\right)\cdot\left(y-y_{0}\right).$

Since we are assuming that (38) does not hold, we may take

$t:=\min\left\\{1,\frac{\left(x-y_{0}\right)\cdot\left(y-y_{0}\right)}{|y-y_{0}|^{2}}\right\\}.$

Assuming that $x\notin\overline{C}$, we may take $\phi:=x-y_{0}\neq 0$ to
deduce that for any $y\in\overline{C}$ we have

$y\cdot\phi\leq{y_{0}\cdot\phi}\leq{x\cdot\phi},$

the latter inequality following from the fact that
$(x\cdot\phi)-\left(y_{0}\cdot\phi\right)=\left(\phi\cdot\phi\right)\geq 0$.

It remains to prove the result when
$x\in\overline{C}\setminus\mathrm{int}\,(C)$. Since $C$ is convex, it follows
from Lemma B.6 that $x\notin\mathrm{int}\,(\overline{C})$, so that for any
$m\in\mathbb{N}$ there exists $x_{m}\notin\overline{C}$ such that

$|x-x_{m}|\leq 1/m.$

By our previous argument, there exists $\phi_{m}\neq 0$ such that for any
$y\in\overline{C}$ we have

$y\cdot\phi_{m}\leq{x_{m}\cdot\phi_{m}}.$ (39)

Normalising so that $|\phi_{m}|=1$, we have a sequence in a compact set, so
there exists a convergent subsequence $\phi_{k(m)}\to\phi$ with $|\phi|=1$.
Taking limits in (39) then gives the desired inequality. ∎

######  Corollary B.8 (Complex supporting hyperplane theorem).

Let $C$ be a convex subset of $\mathbb{C}^{n}$ and $x\notin\mathrm{int}\,(C)$.
Then there exists $\phi\in\mathbb{C}^{n}\setminus\left\\{0\right\\}$ such that
for all $y\in\overline{C}$ we have

$\mathrm{Re}\left\langle y,\phi\right\rangle\leq\mathrm{Re}\left\langle
x,\phi\right\rangle.$

###### Proof.

This follows from the observation that for
$x,y\in\mathbb{C}^{n}\cong\mathbb{R}^{2n}$ we have

$\mathrm{Re}\left\langle x,y\right\rangle=x\cdot y.$

∎

##  Appendix C The semi-finite minimax theorem

We have not been able to find a reference for the variant of the minimax
theorem employed in §5.

######  Proposition C.1 (Semi-finite minimax).

Let $A$ and $B$ be non-empty compact convex subsets of $\mathbb{R}^{n}$ at
least one of which is equal to the convex hull of finitely many points. Then
there exist ${a_{0}}\in A$ and ${b_{0}}\in B$ such that for any $a\in A$ and
any $b\in B$ we have

$a\cdot{b_{0}}\leq{a_{0}}\cdot b.$

###### Proof.

We may assume that $A$ is the convex hull of finitely many points, otherwise
we re-label, taking $A^{\prime}:=-B$ and $B^{\prime}:=A$ to obtain $b_{0}\in
B$ and $a_{0}\in A$ such that for any $b\in B$ and $a\in A$ we have

$-b\cdot{a_{0}}\leq-{b_{0}}\cdot a,$

which yields the claimed result.

Define

$L:=\sup_{a\in A}\inf_{b\in B}(a\cdot b)\quad\text{and}\quad U:=\inf_{b\in
B}\sup_{a\in A}(a\cdot b).$

In order to prove the proposition, it suffices to establish that

  1. (i)

There exists ${a_{0}}\in A$ and ${b_{0}}\in B$ such that

$L=\inf_{b\in B}({a_{0}}\cdot b)\quad\text{and}\quad U=\sup_{a\in
A}(a\cdot{b_{0}}).$

  2. (ii)

$U\leq L$.

We begin by showing that

$-\infty<L\leq U<\infty.$ (40)

For any $a_{1}\in A$ and $b_{1}\in B$ we have

$\inf_{b\in B}(a_{1}\cdot b)\leq a_{1}\cdot b_{1}\leq\sup_{a\in A}(a\cdot
b_{1}).$

Since $a_{1}$ and $b_{1}$ are arbitrary, it follows that $L\leq U$. Since $B$
is non-empty, there exists $b_{1}\in B$. Thus

$U\leq\sup_{a\in A}(a\cdot{b_{1}})$

By compactness, there exists $a_{1}\in A$ such that

$\sup_{a\in A}(a\cdot b_{1})=a_{1}\cdot b_{1}<\infty.$

We conclude that $U<\infty.$ Similarly, compactness of $B$ and non-emptiness
of $A$ yields $L>-\infty$. This establishes (40).

Since $U$ is finite, for any $k\in\mathbb{N}$ there exists $b_{k}\in B$ such
that

$U\leq\sup_{a\in A}(a\cdot b_{k})\leq U+\frac{1}{k}.$

By compactness of $B$, there exists a convergent subsequence $b_{k_{m}}\to
b\in B$. Continuity of the map $(a,b)\mapsto a\cdot b$ then ensures that for
any $a\in A$ we have

$a\cdot b=\lim_{m\to\infty}a\cdot b_{k_{m}}\leq U.$

Thus $\sup_{a\in A}(a\cdot b)\leq U$, which by definition of $U$ implies that
$\sup_{a\in A}(a\cdot b)=U$. A similar argument holds for $L$. This proves
(i).

Finally, we show that for any $\alpha\in\mathbb{R}$ we either have
$L\geq\alpha$ or $U\leq\alpha$. Combining this with the fact that $L\leq U$,
it follows that $L=U$ (if not, any $\alpha\in(L,U)$ leads to a contradiction).

Since $A$ is the convex hull of finitely many points, there exist
$a_{1},\dots,a_{k}\in A$ such that

$A=\left\\{\sum_{i=1}^{k}\lambda_{i}a_{i}:\lambda_{i}\geq 0\text{ and
}\sum_{i}\lambda_{i}=1\right\\}.$

Given $b\in B$ let us write

$v_{b}:=\Bigl{(}(a_{1}\cdot b)-\alpha,\dots,(a_{k}\cdot
b)-\alpha\Bigr{)}\in\mathbb{R}^{k}.$

Define $C$ to be the convex hull of the set

$\left\\{v_{b}:b\in B\right\\}\cup\left\\{e_{1},\dots,e_{k}\right\\}.$

Let us first suppose that $0\in C$. Then there exist $b_{1},\dots,b_{m}\in B$,
$\lambda_{1},\dots,\lambda_{m},\mu_{1},\dots,\mu_{k}\geq 0$ such that
$1=\sum_{i}\lambda_{i}+\sum_{j}\mu_{j}$ and

$0=\sum_{i}\lambda_{i}v_{b_{i}}+(\mu_{1},\dots,\mu_{k}).$ (41)

It follows that for each $j=1,\dots,k$ we have

$\sum_{i=1}^{m}\lambda_{i}\bigl{(}(a_{j}\cdot b_{i})-\alpha\bigr{)}\leq 0.$
(42)

By (41) we cannot have all $\lambda_{i}$ equal to zero. We may therefore re-
normalise, to conclude that there exist $\lambda_{i}\geq 0$ with
$\sum_{i}\lambda_{i}=1$ satisfying (42). We deduce that for each $j=1,\dots,k$
we have

$a_{j}\cdot\sum_{i=1}^{m}\lambda_{i}b_{i}\leq\alpha.$

Convexity then shows that for $b=\sum_{i}\lambda_{i}b_{i}\in B$ and for any
$a\in A=\mathrm{ConvexHull}(a_{1},\dots,a_{k})$ we have $a\cdot b\leq\alpha$.
Hence $U\leq\alpha$.

Next suppose that $0\notin C$. By the supporting hyperplane theorem (Lemma
B.7, and the remark which follows it), there exists
$\phi\in\mathbb{R}^{k}\setminus\left\\{0\right\\}$ such that for all
$b_{1},\dots,b_{m}\in B$ and
$\lambda_{1},\dots,\lambda_{m},\mu_{1},\dots,\mu_{k}\geq 0$ with
$\sum_{i}\lambda_{i}+\sum_{j}\mu_{j}=1$ we have

$\left(\sum_{i}\lambda_{i}v_{b_{i}}+\sum_{j}\mu_{j}e_{j}\right)\cdot\phi\geq
0.$

In particular, we have

$\phi_{j}=e_{j}\cdot\phi\geq 0\qquad(j=1,\dots,k),$

and for each $b\in B$ we have

$v_{b}\cdot\phi\geq 0.$

Since $\phi\neq 0$ we may re-normalise to conclude that there exists
$\phi_{j}\geq 0$ with $\sum_{j}\phi_{j}=1$ such that for any $b\in B$ we have

$\Bigl{(}\sum_{j=1}^{k}\phi_{j}a_{j}\Bigr{)}\cdot b\geq\alpha.$

Convexity of $A$ then gives the existence of $a=\sum_{j}\phi_{j}a_{j}\in A$
such that for all $b\in B$ we have $a\cdot b\geq\alpha$, so that
$L\geq\alpha$. ∎

Recall that in order to distinguish between the complex inner product on
$\mathbb{C}^{n}$ and the real inner product on $\mathbb{R}^{2n}$, we write
$\left\langle x,y\right\rangle$ for the former and $x\cdot y$ for the latter.

######  Corollary C.2 (Complex minimax).

Let $A$ and $B$ be non-empty compact convex subsets of $\mathbb{C}^{n}$ at
least one of which is equal to the convex hull of finitely many points. Then
there exist $a_{0}\in A$ and ${b_{0}}\in B$ such that for any $a\in A$ and any
$b\in B$ we have

$\mathrm{Re}\left\langle
a,{b_{0}}\right\rangle\leq\mathrm{Re}\left\langle{a_{0}},b\right\rangle.$

##  Appendix D The Weierstrass polynomial approximation theorem

Given a real number $x$ write

$x_{+}:=\max\left\\{x,0\right\\}=\tfrac{1}{2}(x+|x|).$

######  Lemma D.1 (Weierstrass polynomial approximation).

There exists an absolute constant $C>0$ such that for any
$\varepsilon\in(0,1)$ there exists a polynomial $P$ of degree at most
$C\varepsilon^{-2/3}$ and height at most $\exp(C\varepsilon^{-2/3})$ such that

$\sup_{|x|\leq 1}|P(x)-x_{+}|\leq\varepsilon.$

###### Proof.

By the Taylor series theorem, for any $t\in[0,1)$ we have

$(1-t)^{1/2}=-\sum_{n=0}^{N}c_{n}t^{n}+O\left(c_{N+1}\right),$ (43)

where

$c_{n}=\frac{(2n)!}{(2n-1)2^{2n}(n!)^{2}}$

Using Stirling’s formula, one can check that there exists a constant $C$ such
that

$c_{n}\sim Cn^{-3/2}\quad\text{as $n\to\infty$}.$

In particular, by absolute convergence and continuity, the approximation (43)
is valid for $t\in[0,1]$.

For any $x\in[-1,1]$ we see that

$|x|=\bigl{(}1-(1-x^{2})\bigr{)}^{1/2}=\sum_{m=0}^{N}(-1)^{m}\left(\sum_{n=m}^{N}c_{n}\binom{n}{m}\right)x^{2m}+O(N^{-3/2}).$

Using the crude bound

$\Bigl{|}\sum_{n=m}^{N}c_{n}\binom{n}{m}\Bigr{|}\leq 2^{N},$

we deduce that for any $N\in\mathbb{N}$ there exists a real polynomial $P_{N}$
of degree at most $2N$ and height at most $C\exp(N)$ such that

$\sup_{x\in[-1,1]}|P_{N}(x)-|x||\ll N^{-3/2}.$

The result now follows on taking $P(x):=\tfrac{1}{2}(P_{N}(x)+x)$ and ensuring
that $N\geq C/\varepsilon^{2/3}$ for some absolute constant $C$. ∎

## References

  * [Blo12] T. F. Bloom, _Translation invariant equations and the method of Sanders_ , Bull. Lond. Math. Soc. 44 (2012), no. 5, 1050–1067.
  * [BP] T. D. Browning and S. M. Prendiville, _A transference approach to a Roth-type theorem in the squares_ , preprint.
  * [CG] D. Conlon and W. T. Gowers, _Combinatorial theorems relative to a sparse random set_ , preprint available at arXiv:1011.4310.
  * [CFZ] D. Conlon, J. Fox and Y. Zhao, _A relative Szemerédi theorem_ , GAFA 25 (2015), 733–762.
  * [Gow10] W. T. Gowers, _Decompositions, approximate structure, transference, and the Hahn-Banach theorem_ , Bull. Lond. Math. Soc. 42 (2010), no. 4, 573–606.
  * [Gre05] B. J. Green, _Roth’s theorem in the primes_ , Annals of Math. 161 (2005), 1609–1636.
  * [GT06] B. J. Green and T. Tao , _Restriction theory of the Selberg sieve, with applications_ , Journal de théorie des nombres de Bordeaux 18 (2006), 147–182.
  * [GT08] by same author, _The primes contain arbitrarily long arithmetic progressions_ , Annals of Math. 167 (2008), 481–547.
  * [GT10] by same author, _Linear equations in primes_ , Annals of Math. 171 (2010), 1753–1850.
  * [Har] A. J. Harper, _Minor arcs, mean values, and restriction theory for exponential sums over smooth numbers_ , preprint available at arXiv:1408.1662.
  * [HDR11] H. A. Helfgott and A. De Roton, _Improving Roth’s theorem in the primes_ , IMRN (2011), no. 4, 767–783.
  * [Mat12] L. Matthiesen, _Correlations of the divisor function_ , Proc. London Math. Soc. 104 (2012), 827– 858\.
  * [Nas15] E. Naslund, _On improving Roth’s theorem in the primes_ , Mathematika 61 (2015), 49–62.
  * [RTTV] O. Reingold, L. Trevisan, M. Tulsiani, and S. Vadhan, _New proofs of the Green–Tao–Ziegler dense model theorem: an exposition_ , preprint available at arXiv:0806.0381.
  * [Rot53] K. F. Roth, _On certain sets of integers_ , J. London Math. Soc. 28 (1953), 104–109.
  * [Rot54] by same author, _On certain sets of integers. II_ , J. London Math. Soc. 29 (1954), 20–26.
  * [Sch] M. Schacht, _Extremal results for random discrete structures_ , preprint.
  * [TZ08] T. Tao and T. Ziegler, _The primes contain arbitrarily long polynomial progressions_ , Acta Math. 201 (2008), no. 2, 213–305.