u\|_{2}\leqslant\sqrt{m}$. Applying Fourier inversion to the cutoff
$w^{\otimes m}$ we then obtain

$\displaystyle w^{\otimes m}(\Psi u)$
$\displaystyle=1_{\|u\|_{\infty}\leqslant\sqrt{m}}w^{\otimes m}(\Psi u)$
$\displaystyle=\prod_{j=1}^{m}\int_{\mathbf{R}^{m}}\hat{w}(\gamma_{j})1_{[-\sqrt{m},\sqrt{m}]}(u_{j})e(\gamma_{j}(\Psi
u)_{j})d\gamma_{j}.$

This, (15.16) and the triangle inequality imply that

$|T_{a,b,c}(\xi)|\leqslant\|\hat{w}\|_{1}^{m}\prod_{j=1}^{m}\sup_{\alpha^{\prime}_{j}}\big{|}\int^{\sqrt{m}}_{-\sqrt{m}}e(\frac{1}{2}\xi\lambda_{j}u_{j}^{2}+\alpha^{\prime}_{j}u_{j})du_{j}\big{|}.$
(15.17)

Now we use the fact that

$\int^{Y_{2}}_{Y_{1}}e(x^{2})dx=O(1),$ (15.18)

uniformly in $Y_{1},Y_{2}$. To see this, divide into positive and negative
ranges, and make the substitution $x^{2}=w$; it then suffices to show that
$\int^{Y}_{0}e(w)w^{-1/2}dw=O(1)$, uniformly in $Y$. Bounding the portion of
the integral on $[0,1]$ trivially, it is sufficient to show that
$\int^{Y}_{1}e(w)w^{-1/2}dw=O(1)$, uniformly in $Y\geqslant 1$. This can be
done by integration by parts, since $e(w)w^{-1/2}$ is bounded uniformly and
moreover

$|\int^{Y}_{1}e(w)w^{-3/2}dw|<\int^{\infty}_{1}w^{-3/2}dw=O(1).$

Completing the square and making a substitution in (15.18), we have

$\int^{\sqrt{m}}_{-\sqrt{m}}e(\frac{1}{2}\xi\lambda_{j}u_{j}^{2}+\alpha^{\prime}_{j}u_{j})du_{j}\ll|\xi\lambda_{j}|^{-1/2},$

with the implied constant absolute. Substituting into (15.17), it follows that

$\displaystyle T_{a,b,c}(\xi)\leqslant O(1)^{m}\|\hat{w}\|_{1}^{m}$
$\displaystyle\prod_{j=1}^{m}|\xi\lambda_{j}|^{-1/2}\leqslant
O(1)^{m}\|\hat{w}\|_{1}^{m}|\xi|^{-m/2}L^{B}$ $\displaystyle\leqslant
O(1)^{m}\|\hat{w}\|_{1}^{m}L^{-m/16}L^{B}\leqslant L^{-2B},$

where this last line of inequalities follows from the assumption that
$|\xi|\geqslant L^{1/8}$, (15.15), $m=C_{1}B$ (with $C_{1}\geqslant 50$) and
the assumptions that $\|\hat{w}\|_{1}\leqslant L^{1/C_{1}}$ and $L>m^{m}$.∎

_Remark._ Note how important it was in this proof that we had a smooth cutoff
$w^{\otimes m}$ to $1_{[0,1]^{m}}$; dealing with a rough cutoff under the
orthogonal transformation $\Psi$ is problematic. For a very similar use of
this device, see Heath-Brown and Pierce [13, Section 3].

We turn now to the proofs of Lemmas 15.4 and 15.5. We first begin with some
initial arguments common to the proof of both lemmas.

First, we remove the weight $w^{\otimes m}$ by Fourier expansion. By the
inversion formula we have, for $\xi\neq 0$,

$S_{a,b,c}(\xi)=\int_{\gamma\in\mathbf{R}^{m}}(\prod_{j=1}^{m}\hat{w}(\gamma_{i}))S^{\prime}_{a,b+\frac{\gamma}{\xi},c}(\xi)d\gamma,$

where

$S^{\prime}_{a,b,c}(\xi)=\int_{\mathbf{R}^{m}}e(\xi
q_{a,b,c}(t))d\mu_{\operatorname{disc}}(t)$

is the unsmoothed exponential sum. Therefore for any $\xi$

$\max_{b,c}|S_{a,b,c}(\xi)|\leqslant\|\hat{w}\|_{1}^{m}\max_{b,c}|S^{\prime}_{a,b,c}(\xi)|.$
(15.19)

Note that the maxima here are over _all_ $b,c$; in these lemmas we are not
assuming any bounds on their size. They will, in any case, shortly disappear
from view.

Fix some $\xi$ in the relevant range $L^{1/8}\leqslant|\xi|\leqslant L^{2B}$.
The initial steps follow the standard proof of Weyl’s inequality for quadratic
exponential sums. Squaring and making a substitution, we have

$|S^{\prime}_{a,b,c}(\xi)|^{2}\leqslant(L_{1}\dots
L_{m})^{-2}\sum_{h_{i}\in[-L_{i},L_{i}]}\sum_{x\in
B_{h}}e(\xi(q_{a,b,c}(\frac{\mathbf{x}+\mathbf{h}}{\mathbf{L}})-q_{a,b,c}(\frac{\mathbf{x}}{\mathbf{L}}))),$
(15.20)

where, for $h\in\mathbf{Z}^{m}$,
$B_{h}:=\prod_{i=1}^{m}[L_{i}]\cap(\prod_{i=1}^{m}[L_{i}]-h)$. Here, and in
what follows, we use the shorthands

$\frac{\mathbf{x}}{\mathbf{L}}=(\frac{x_{1}}{L_{1}},\dots,\frac{x_{m}}{L_{m}}),\quad\frac{\mathbf{x}+\mathbf{h}}{\mathbf{L}}=(\frac{x_{1}+h_{1}}{L_{1}},\dots,\frac{x_{m}+h_{m}}{L_{m}})$

(and similar); note this is just notation and we are not dividing vectors,
thus we still write $x=(x_{1},\dots,x_{m})$, $h=(h_{1},\dots,h_{m})$ without
bold font. We have

$q_{a,b,c}(\frac{\mathbf{x}+\mathbf{h}}{\mathbf{L}})-q_{a,b,c}(\frac{\mathbf{x}}{\mathbf{L}})=(\frac{\mathbf{x}}{\mathbf{L}})^{T}(a+a^{T})\frac{\mathbf{h}}{\mathbf{L}}+q_{a,b,0}(\frac{\mathbf{h}}{\mathbf{L}}),$

where here and in what follows we abuse notation slightly and identify
$a=(a_{ij})_{1\leqslant i\leqslant j\leqslant m}$ with an upper-triangular
matrix in the obvious way.

Equation (15.20) then implies that

$|S^{\prime}_{a,b,c}(\xi)|^{2}\leqslant(L_{1}\cdots
L_{m})^{-2}\sum_{h_{i}\in[-L_{i},L_{i}]}\big{|}\sum_{x\in
B_{h}}e(\xi(\frac{\mathbf{x}}{\mathbf{L}})^{T}(a+a^{T})\frac{\mathbf{h}}{\mathbf{L}})\big{|}.$
(15.21)

Note that $b,c$ no longer appear here, so if
$\max_{b,c}|S_{a,b,c}(\xi)|\geqslant L^{-7B}$ then (using also (15.19) and the
assumption $\|\hat{w}\|^{m}_{1}\leqslant L^{B}$) we have

$\sum_{h_{i}\in[-L_{i},L_{i}]}\big{|}\sum_{x\in
B_{h}}e(\xi(\frac{\mathbf{x}}{\mathbf{L}})^{T}(a+a^{T})\frac{\mathbf{h}}{\mathbf{L}})\big{|}\geqslant(L_{1}\cdots
L_{m})^{2}L^{-16B}.$

Since the inner sum is trivially bounded by $L_{1}\cdots L_{m}$, this means
that there is a set $H\subset\prod_{i=1}^{m}[-L_{i},L_{i}]^{m}$,
$|H|\geqslant\frac{1}{2}(L_{1}\cdots L_{m})L^{-16B}\geqslant(L_{1}\cdots
L_{m})L^{-17B}$, such that

$\displaystyle\big{|}\sum_{x\in
B_{h}}e(\xi(\frac{\mathbf{x}}{\mathbf{L}})^{T}(a+a^{T})\frac{\mathbf{h}}{\mathbf{L}})\big{|}$
$\displaystyle\geqslant 2^{-m-1}(L_{1}\cdots L_{m})L^{-16B}$
$\displaystyle\geqslant(L_{1}\cdots L_{m})L^{-17B}$ (15.22)

for $h\in H$.

$\big{|}\sum_{x\in
B_{h}}e(\xi(\frac{\mathbf{x}}{\mathbf{L}})^{T}(a+a^{T})\frac{\mathbf{h}}{\mathbf{L}})\big{|}\geqslant(L_{1}\cdots
L_{m})L^{-17B}$ (15.23)

for $h\in H$. For $t\in\mathbf{R}^{m}$, write

$\ell_{i,a}(t):=((a+a^{T})t)_{i},\quad\mbox{$i=1,\dots,m$}.$

Thus (15.23) becomes

$\big{|}\sum_{x\in
B_{h}}e(\xi\sum_{i=1}^{m}\frac{x_{i}}{L_{i}}\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}}))\big{|}\geqslant(L_{1}\cdots
L_{m})L^{-17B}$

for $h\in H$. Noting that, for each $h$, $B_{h}$ is a sub-box of
$\prod_{i=1}^{m}[L_{i}]$, we may evaluate the sum as a geometric series and
conclude that for $h\in H$ we have

$\prod_{i=1}^{m}\min(L_{i},\|\frac{\xi}{L_{i}}\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})\|_{\mathbf{T}}^{-1})\geqslant(L_{1}\cdots
L_{m})L^{-17B}.$ (15.24)

It follows that for each $h\in H$ there is a set
$I(h)\subseteq\\{1,\dots,m\\}$, $|I(h)|\geqslant m/2$, such that

$\|\frac{\xi}{L_{i}}\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})\|_{\mathbf{T}}\leqslant
L^{-1+34B/m}\leqslant\frac{1}{2}L^{-15/16}$

for all $i\in I(h)$ (recalling that $B=C_{1}m$, and if $C_{1}$ is big enough).
Pigeonholing in $h$, we may find a set $I\subseteq\\{1,\dots,m\\}$,
$|I|\geqslant m/2$, and a set $H^{\prime}$,

$|H^{\prime}|\geqslant 2^{-m}|H|\geqslant(L_{1}\cdots L_{m})L^{-18B},$ (15.25)

such that

$\|\frac{\xi}{L_{i}}\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})\|_{\mathbf{T}}\leqslant\frac{1}{2}L^{-15/16}\;\mbox{for
$h\in H^{\prime}$ and $i\in I$}.$

Hence, since the $\ell_{i,a}$ are linear, we have

$\|\frac{\xi}{L_{i}}\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})\|_{\mathbf{T}}\leqslant
L^{-15/16}\;\mbox{for $h\in H^{\prime}-H^{\prime}$ and $i\in I$}.$ (15.26)

This fact will be the key to the proofs of both Lemma 15.4 and 15.5, but the
subsequent treatment of those two lemmas differs.

###### Proof of Lemma 15.4.

We handle the ranges $L^{1/8}<|\xi|<L^{3/4}$ and
$L^{3/4}\leqslant|\xi|<L^{5/4}$ separately, starting with the latter, which is
slightly harder.

Suppose then that $L^{3/4}<|\xi|<L^{5/4}$ and that $\det(a+a^{T})\geqslant
L^{-2B}$, as in the statement of the lemma. Note that if $h\in
H^{\prime}-H^{\prime}$, $i\in I$ and

$|\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})|<L^{-1/3}$ (15.27)

then

$\frac{|\xi|}{L_{i}}|\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})|<\frac{L^{5/4-1/3}}{L_{i}}<\frac{1}{2}$

and so

$\|\frac{\xi}{L_{i}}\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})\|_{\mathbf{T}}=\frac{|\xi|}{L_{i}}|\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})|.$

Therefore, if (15.26), (15.27) hold then (using $L_{i}\in[L,L^{1+1/48}]$),

$|\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})|\leqslant
L^{-15/16}\frac{L_{i}}{|\xi|}<L^{-15/16}\frac{L^{1+1/48}}{L^{3/4}}=L^{-2/3}.$

Thus we have shown that if (15.26) holds then

$\mbox{for $h\in H^{\prime}-H^{\prime}$, $i\in I$ we do not
have}\;L^{-2/3}<|\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})|<L^{-1/3}.$ (15.28)

To analyse (15.28) we need the following lemma.

######  Lemma 15.6.

Let $S\subset[-2mQ,2mQ]\subset\mathbf{R}$ be a set, and suppose that $S-S$
contains no element in $[2L^{-2/3},\frac{1}{2}L^{-1/3}]$. Then
$\mu_{\mathbf{R}}(S)\ll mQL^{-1/3}$.

###### Proof.

Cover $[-2mQ,2mQ]$ with $O(QmL^{1/3})$ disjoint intervals of length
$\frac{1}{2}L^{-1/3}$. The intersection of $S$ with any such interval has
measure at most $2L^{-2/3}$ (it is either empty, or if it contains some $x$
then it only contains points in an interval of diameter $\leqslant 2L^{-2/3}$
about $x$). ∎

Returning to the analysis of (15.28), consider the set $X\subset[-1,1]^{m}$
defined by

$X:=\\{\frac{\mathbf{h}}{\mathbf{L}}:h\in
H^{\prime}\\}+\prod_{i=1}^{m}[0,\frac{1}{L_{i}}].$

Thus, by (15.25),

$\mu_{\mathbf{R}^{m}}(X)=(L_{1}\cdots L_{m})^{-1}|H^{\prime}|\geqslant
L^{-18B}.$ (15.29)

Also, if $x,x^{\prime}\in X$ then for some $h,h^{\prime}\in H^{\prime}$

$\ell_{i,a}(x-x^{\prime})=\ell_{i,a}(\frac{\mathbf{h}-\mathbf{h}^{\prime}}{\mathbf{L}})+O(\frac{mQ}{L}).$

Thus, by (15.28) (and the assumption that $mQ<L^{\frac{1}{4}}$) we see that
for $i\in I$, $\ell_{i,a}(X-X)=\ell_{i,a}(X)-\ell_{i,a}(X)$ contains no
element in the interval $[2L^{-2/3},\frac{1}{2}L^{-1/3}]$. By Lemma 15.6 (and
noting that $\ell_{i,a}(X)\subset[-2mQ,2mQ]$),

$\mu_{\mathbf{R}}(\ell_{i,a}(X))=O(mQL^{-1/3})\leqslant L^{-1/12}.$

Thus, the image of $X$ under the linear map
$\psi:\mathbf{R}^{m}\rightarrow\mathbf{R}^{m}$ defined by

$\psi(x_{1},\dots,x_{m}):=(\ell_{1,a}(x),\dots,\ell_{m,a}(x))$

has measure at most $(2mQ)^{m}L^{-|I|/12}\leqslant L^{-m/48}$ (here we have
used the fact that $\ell_{j,a}(x)$ takes values in $[-2Qm,2Qm]$ for all $j$,
even if $j\notin I$). But $\det\psi=\det(a+a^{T})\geqslant L^{-2B}$, and so

$\mu_{\mathbf{R}^{m}}(X)\ll(\det\psi)^{-1}L^{-m/48}\ll L^{2B-m/48}.$

Recalling that $m=C_{1}B$, this contradicts (15.29) if $C_{1}$ is big enough.
This completes the proof of Lemma 15.4 in the range
$L^{3/4}\leqslant|\xi|<L^{5/4}$.

Now consider the remaining range $L^{1/8}<|\xi|<L^{3/4}$. Once again, we refer
to (15.26), which tells us that

$\|\frac{\xi}{L_{i}}\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})\|_{\mathbf{T}}\leqslant
L^{-15/16}\;\mbox{for $h\in H^{\prime}-H^{\prime}$ and $i\in I$}.$ (15.30)

Now

$|\frac{\xi}{L_{i}}\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})|\leqslant\frac{L^{3/4}}{L_{i}}\cdot
2Qm<\frac{1}{2}.$

Therefore (15.30) implies that

$|\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})|\ll
L^{-15/16}\frac{L_{i}}{|\xi|}\leqslant
L^{-15/16}\frac{L^{1+1/48}}{L^{1/8}}=L^{-1/24}.$

That is,

$\mbox{for $h\in H^{\prime}-H^{\prime}$, $i\in I$ we
have}\;|\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})|\leqslant L^{-1/24}.$
(15.31)

This should be compared with (15.28), but the subsequent analysis is easier
and does not require Lemma 15.6 since we immediately have

$\mu_{\mathbf{R}}(\ell_{i,a}(X))\leqslant 2L^{-1/24}.$

One may now obtain a contradiction essentially as before, with minor numerical
modifications. ∎

###### Proof of Lemma 15.5.

Suppose that $|\xi|\geqslant L^{5/4}$, as in the statement of the lemma.
Recall the key statement (15.26) established above, that is to say

$\|\frac{\xi}{L_{i}}\ell_{i,a}(\frac{\mathbf{h}}{\mathbf{L}})\|_{\mathbf{T}}\ll
L^{-15/16}\;\mbox{for $h\in H^{\prime}-H^{\prime}$ and $i\in I$}.$ (15.32)

Recall also (see (15.25)) that $|H^{\prime}|\geqslant(L_{1}\cdots
L_{m})L^{-18B}$. By an application of the pigeonhole principle (dividing
$\prod_{i=1}^{m}[-L_{i},L_{i}]$ into cubes of sidelength $10L^{18B/m}\leqslant
L^{19B/m}$) there is some $h^{*}\in H^{\prime}-H^{\prime}$ with
$0<|h^{*}|\leqslant L^{19B/m}$. Then (15.32) implies that

$\|\frac{\xi}{L_{i}}\ell_{i,a}(\frac{\mathbf{h}^{*}}{\mathbf{L}})\|_{\mathbf{T}}\leqslant
2L^{-15/16}\;\mbox{for $i\in I$}.$ (15.33)

Let us summarise the situation so far: under the assumption that
$\sup_{b,c}|S_{a,b,c}(\xi)|\geqslant L^{-7B}$ and the analysis leading to
(15.26), we have shown that (15.33) holds for some $I\subset\\{1,\dots,m\\}$
with $|I|\geqslant m/2$, and for some $h^{*}\in\mathbf{Z}^{m}$, $0<|h^{*}|\ll
L^{19B/m}$. Thus, denoting by $E_{I,h^{*}}(a)$ be the event that (15.33)
holds, we have the inclusion of events

$\\{a:\sup_{b,c}|S_{a,b,c}(\xi)|\geqslant
L^{-7B}\\}\subset\bigcup_{\begin{subarray}{c}I\subseteq[m]\\\ |I|\geqslant
m/2\end{subarray}}\bigcup_{0<|h^{*}|\leqslant L^{19B/m}}E_{I,h^{*}}(a).$
(15.34)

We will now bound $\mathbb{P}_{a}(E_{I,h^{*}}(a))$ for $I,h^{*}$ fixed, before
applying the union bound to (15.34). Pick some index $j\in[m]$ such that
$h^{*}_{j}\neq 0$. We are now going to condition on all except some fairly
small subset of the random entries $a_{ij}$. Let $I_{-}:=\\{i\in I:i<j\\}$ and
$I_{+}:=\\{i\in I:i>j\\}$.

If $|I_{-}|\geqslant m/6$ then we condition on all except the $a_{ij}$, $i\in
I_{-}$. With all the other variables fixed, the conditions (15.33) for $i\in
I_{-}$ become

$\|\frac{\xi}{L_{i}L_{j}}a_{ij}h^{*}_{j}+c_{i}\|_{\mathbf{T}}\leqslant
2L^{-15/16},$ (15.35)

where the $c_{i}$ depend on the fixed variables but not on the random
variables $(a_{ij})_{i\in I_{-}}$. ($c_{i}$ will depend on the entries
$(a+a^{T})_{ik}$, $k\neq j$, that is to say on $a_{ik}$ for $k>i$ and on
$a_{ki}$ for $k<i$; none of these variables are one of the $a_{i_{-},j}$,
$i_{-}\in I_{-}$.)

If $|I_{+}|\geqslant m/6$ then we proceed in very similar fashion, but now we
condition on all except the $a_{ji}$, $i\in I_{+}$. With all the other
variables fixed, the conditions (15.33) for $i\in I_{+}$ become

$\|\frac{\xi}{L_{i}L_{j}}a_{ji}h^{*}_{j}+c_{i}\|_{\mathbf{T}}\leqslant
2L^{-15/16},$ (15.36)

with the $c_{i}$ as before; note that none of the variables in $c_{i}$ depends
on any $a_{ji_{+}}$ with $i_{+}\in I_{+}$.) The treatment of the two cases
$|I_{-}|\geqslant m/6$ and $|I_{+}|\geqslant m/6$ is now essentially
identical, so we detail only the former.

Consider a single value of $i\in I_{-}$ and a fixed $c_{i}$. As $a_{ij}$
ranges uniformly in $[-Q,Q]$, $\frac{\xi}{L_{i}L_{j}}a_{ij}h^{*}_{j}+c_{i}$
ranges uniformly over a subinterval of $\mathbf{R}$ of length at least
$|\xi||h^{*}_{j}|/L_{i}L_{j}\geqslant L^{-3/4-1/24}$ (here we use the
hypothesis that $|\xi|\geqslant L^{5/4}$, as well as the assumption that
$L_{i},L_{j}\leqslant L^{1+1/48}$). Thus the probability (in $a$) that (15.36)
holds is bounded above by $O(L^{-15/16+3/4+1/24})<L^{-1/8}$.

As $i$ ranges over $I_{-}$, these events are independent. Therefore we see,
averaging over all choices of the fixed variables, that

$\mathbb{P}_{a}E_{I,h^{*}}(a)\leqslant\mathbb{P}_{a}\big{(}\|\frac{\xi}{L_{i}L_{j}}a_{ij}h^{*}_{j}+c_{i}\|_{\mathbf{T}}\leqslant
2L^{-15/16}\;\mbox{for $i\in I_{-}$}\big{)}\leqslant L^{-|I_{-}|/8}.$

Since $|I_{-}|\geqslant m/6$, this is at most $L^{-m/48}$. The same bound
holds in the case that $|I_{+}|\geqslant m/6$.

Finally, applying the union bound to (15.34), noting that the number of events
in the union is $\leqslant 4^{m}L^{19B}$ we see that indeed

$\mathbb{P}_{a}(\sup_{b,c}|S_{a,b,c}(\xi)|\geqslant L^{-7B})\leqslant
4^{m}L^{19B-m/48}\leqslant L^{-2B},$

assuming that $C_{1}$ is sufficiently large. ∎

This concludes the proof of all the lemmas, and hence the proof of Proposition
15.1.

###  16\. An amplification argument

In this section, we finally prove our key proposition about the density of
values taken by random quadratic forms, Proposition 9.3.

######  Proposition 9.3.

Let $B\geqslant 1$ be an exponent and let $Q\geqslant 1$ be a parameter.
Suppose that $s\geqslant C_{1}B^{2}$ is an integer. Let
$L\geqslant(QB)^{C_{2}B}$. Let $L_{1},\dots,L_{s}$ be lengths with
$L_{i}\in[L,L^{1+1/48}]$. Choose an $\frac{1}{2}s(s+1)$-tuple
$a=(a_{ij})_{1\leqslant i\leqslant j\leqslant s}$ of coefficients by choosing
the $a_{ij}$ independently and uniformly at random from $[-Q,Q]$, except for
the diagonal terms $a_{ii}$ which are selected uniformly from $[32,Q]$. For
$b=(b_{1},\dots,b_{m})$ and $c\in\mathbf{R}$ and write
$q_{a,b.c}:\mathbf{R}^{s}\rightarrow\mathbf{R}$ for the quadratic form defined
by $q_{a,b,c}(t):=\sum_{i\leqslant j}a_{ij}t_{i}t_{j}+\sum_{i}b_{i}t_{i}+c$.
Let $\Sigma=\Sigma(a)$ be the event that the set

$\\{q_{a,b,c}(\frac{x_{1}}{L_{1}},\dots,\frac{x_{s}}{L_{s}}):0\leqslant
x_{i}<L_{i}\\}$

is $L^{-B}$-dense in $[\frac{1}{2},\frac{3}{2}]$ for all $b,c$ satisfying
$|b_{i}|\leqslant Q$, $|c|\leqslant\frac{1}{4}$ and $b_{i}^{2}-4a_{ii}c<0$ for
all $i$. Then $\mathbb{P}_{a}(\Sigma(a))=1-O(L^{-Bs/16})$.

We follow the strategy outlined in Section 9. First, we establish the
following, a kind of preliminary version of the result with a smaller number
$m=O(B)$ of variables, but with a much weaker exceptional probability of
$O(L^{-B})$.

######  Proposition 16.1.

Let $B\geqslant 1$, and let $Q\geqslant 1$ be a parameter. Let $m=C_{1}B$. Let
$L_{1},\dots,L_{m}$ be lengths with $L_{i}\in[L,L^{1+1/48}]$, where
$L\geqslant(QB)^{C_{2}B}$. Fix diagonal terms $a_{ii}$ with $32\leqslant
a_{11},\dots,a_{mm}\leqslant Q$, and select $a_{ij}$, $1\leqslant i<j\leqslant
m$, uniformly and independently at random from $[-Q,Q]$. Let $a$ be the
(random) upper triangular matrix thus formed. For $b=(b_{1},\dots,b_{m})$ and
$c\in\mathbf{R}$ write $q_{a,b,c}(t):=t^{T}at+b^{T}t+c$. Let $\Sigma$ be the
event that the set

$\\{q_{a,b,c}(\frac{x_{1}}{L_{1}},\dots,\frac{x_{m}}{L_{m}}):0\leqslant
x_{i}<L_{i}\\}$ (16.1)

is $L^{-B}$-dense in $[\frac{1}{2},\frac{3}{2}]$ for all $b,c$ satisfying
$|b_{i}|\leqslant Q$, $|c|\leqslant\frac{1}{4}$ and $b_{i}^{2}-4a_{ii}c<0$.
Then $\mathbb{P}_{a}(\Sigma(a))\geqslant 1-L^{-B}$.

###### Proof.

We apply Proposition 15.1. Let $\chi$ be a minorant to the interval $I$ of
length $L^{-B}$ about the origin constructed in Lemma B.3, as in the statement
of Proposition 15.1. Set $\eta:=(Qm)^{-2}$ and let $w$ be a smooth bump
function as constructed in Lemma B.1, thus $w$ is supported on $[0,1]$, with
$w=1$ on $[\eta,1-\eta]$, and with
$\|w^{\prime}\|_{\infty},\|\hat{w}\|_{1}=O(\eta^{-1})\leqslant L^{1/C_{1}}$,
by the condition on $L$ in the statement of the proposition. This means that
the conditions involving $w$ in Proposition 15.1 are satisfied.

Suppose that $a$ satisfies the conclusion (15.1) of Proposition 15.1 (which
happens with probability $\geqslant 1-L^{-B}$).

Let $u\in[\frac{1}{2},\frac{3}{2}]$. We wish to show that the set (16.1) meets
$u+I$. If it does not then, in the notation of Proposition 15.1,

$\int w^{\otimes m}(t)\chi(q_{a,b,c-u}(t))d\mu_{\operatorname{disc}}(t)=0.$

By the conclusion of Proposition 15.1 it follows that

$\int w^{\otimes m}(t)\chi(q_{a,b,c-u}(t))d\mu(t)\leqslant L^{-B-1/4}.$ (16.2)

By contrast we claim that the LHS of (16.2) is in fact $\gg\eta^{m}L^{-B}$. To
prove the claim, let $\eta_{2},\dots,\eta_{m}\in[\eta,2\eta]$ be arbitrary and
consider the function

$F(t)=F_{\eta_{2},\dots,\eta_{m}}(t):=q_{a,b,c-u}(t,\eta_{2},\dots,\eta_{m}).$

Note that

$\displaystyle F(\eta)=q_{a,b,c-u}(\eta,\eta_{2},\dots,\eta_{m})$
$\displaystyle=q_{a,b,c-u}(0)+O(Qm\eta)$ $\displaystyle=c-u+O(Qm\eta)<0$

(by the choice of $\eta$, and also since
$c\leqslant\frac{1}{4}<\frac{1}{2}\leqslant u$) whilst for all $t$

$\displaystyle F(t)$ $\displaystyle=q_{a,b,c-u}(t,\eta_{2},\dots,\eta_{m})$
$\displaystyle=q_{a,b,c}(t,0,0,\dots)-u-O(mQ\eta)$ $\displaystyle\geqslant
a_{11}(t+\frac{b_{1}}{2a_{11}})^{2}-u-O(mQ\eta).$

In this last step we used that $b_{1}^{2}-4a_{11}c<0$. Since

$\max_{1/4\leqslant t\leqslant
3/4}a_{11}(t+\frac{b_{1}}{2a_{11}})^{2}\geqslant\frac{1}{16}a_{11}\geqslant 2$

and $u\leqslant\frac{3}{2}$ it follows that

$\max_{1/4\leqslant t\leqslant 3/4}F(t)\geqslant 2-u-O(mQ\eta)>0.$

Thus, we may apply the intermediate value theorem to see that there is some
$x=x(\eta_{2},\dots,\eta_{m})\in[\eta,\frac{3}{4}]\subset[\eta,1-\eta]$ such
that $F(x)=0$, that is to say

$q_{a,b,c}(x(\eta_{2},\dots,\eta_{m}),\eta_{2},\dots,\eta_{m})=u.$

Thus if $t$ lies in the set

$S:=[\eta,1-\eta]^{m}\cap\bigcup_{\eta\leqslant\eta_{2},\dots,\eta_{m}\leqslant
2\eta}(x(\eta_{2},\dots,\eta_{m})+[-\eta L^{-B},\eta
L^{-B}],\eta_{2},\dots,\eta_{m})$

then $|q_{a,b,c}(t)-u|\leqslant\frac{1}{2}L^{-B}$. We have
$\mu(S)\gg\eta^{m}L^{-B}$.

Now if $t\in S$ then (by construction of $\chi$ as in Lemma B.3) we have
$\chi(q_{a,b,c-u}(t))=1$. Also, since $S\subset[\eta,1-\eta]^{m}$, we have
$w^{\otimes}(t)=1$. It follows that

$\int w^{\otimes
m}(t)\chi(q_{a,b,c-u}(t))d\mu(t)\geqslant\mu(S)\gg\eta^{m}L^{-B},$

contradicting (16.2) in view of the assumption that $L>(QB)^{C_{2}B}$. ∎

Proposition 9.3 is deduced from the preliminary version, Proposition 16.1, by
a kind of amplification argument. It is driven by the following combinatorial
lemma.

######  Lemma 16.2.

Let $m$ be a positive integer, and suppose that $s\geqslant 16m^{2}$. Then
there are sets $I_{1},\dots,I_{k}\subset[s]$, $k\geqslant s/16$, with
$|I_{\ell}|=m$ and such that the sets of pairs $\\{(i,j):i<j,i,j\in
I_{\ell}\\}$ are disjoint as $\ell$ ranges over $\ell=1,\dots,k$.

###### Proof.

Let $p$, $m\leqslant p<2m$, be a prime. Consider the projective plane of order
$p^{2}+p+1$ over $\mathbf{F}_{p}$. This contains $p^{2}+p+1$ lines, each with
$p+1>m$ elements. Identifying $[p^{2}+p+1]\subset\mathbf{N}$ with the
projective plane in some arbitrary way, we may take
$I_{1},\dots,I_{p^{2}+p+1}\subset[p^{2}+p+1]$ to be subsets of these lines,
each of size $m$. For these sets $I_{\ell}$, the required disjointness
statement is simply the fact that two points in projective space determine a
unique line. Provided that $t(p^{2}+p+1)\leqslant s$, we may embed $t$
disjoint copies of this construction inside $[s]$, and thereby take
$k=t(p^{2}+p+1)$. Using the crude bound $p^{2}+p+1\leqslant 2p^{2}<8m^{2}$ and
$\lfloor s/8m^{2}\rfloor\geqslant s/16m^{2}$, the result follows. ∎

_Remark._ Erdős and Rényi [8] attribute the use of projective planes in this
context to Thoralf Skolem. One may equivalently think of this lemma as a
result about embedding cliques $K_{m}$ into the complete graph $K_{s}$ in an
edge-disjoint fashion, and the lemma states that in the regime $s\sim Cm^{2}$
this may be done quite efficiently, so as to use up a positive proportion of
the edges. Similar constructions would allow one to do the same for, say,
$s\sim Cm^{3}$, but it seems to me to be unclear111Added in proof: Stefan
Glock has drawn my attention to the paper [15], which clarifies this issue.
what the situation is when (for instance) $s\sim m^{5/2}$, or even when
$s=m^{2}/10$. Most of the extensive literature on questions of this type
considers the case $m$ fixed and $s\rightarrow\infty$.

###### Proof of Proposition 9.3.

Condition on the choice of diagonal terms $a_{ii}$; it suffices to prove the
required bound, uniformly in each fixed choice of these terms. Let
$I_{1},\dots,I_{k}\subset[s]$ be as in Lemma 16.2 above, and let
$\Sigma(\ell)$ be the event that the set

$\\{q_{a,b}(\frac{x_{1}}{L_{1}},\dots,\frac{x_{s}}{L_{s}})):0\leqslant
x_{i}<L_{i},x_{j}=0\;\mbox{for $j\notin I_{\ell}$}\\}$ (16.3)

is $L^{-B}$-dense in $[\frac{1}{2},\frac{3}{2}]$ for all $b$ with
$|b_{i}|\leqslant Q$, $|c|\leqslant\frac{1}{4}$ and $b_{i}^{2}-4a_{ii}c<0$ for
all $i$. Since the set (16.3) is contained in the set (16.1), we have the
containment $\Sigma(\ell)\subset\Sigma$.

Note moreover that the event $\Sigma(\ell)$ only depends on the variables
$(a_{ij})_{i<j}$ with $i,j\in I(\ell)$. By construction, these sets of
variables are disjoint as $\ell$ varies and therefore the events
$\Sigma(\ell)$, $\ell=1,\dots,k$, are independent.

By Proposition 16.1, $\mathbb{P}(\neg\Sigma(\ell))\leqslant L^{-B}$. It
follows that

$\mathbb{P}(\neg\Sigma)\leqslant\mathbb{P}\big{(}\bigwedge_{\ell=1}^{k}\neg\Sigma(\ell)\big{)}\leqslant
L^{-Bk}\leqslant L^{-Bs/16}.$

Averaging over the choices of $a_{11},\dots,a_{ss}$ (that is, undoing the
conditioning on diagonal terms), this at last concludes the proof of
Proposition 9.3. ∎

We have now proven all three of the ingredients stated in Section 9, and hence
by the arguments of that section Proposition 5.4 is true. This completes the
proof that there are (with high probability) no progressions of length
$N^{1/r}$ in the red points of our colouring, and hence finishes the proof of
Theorem 2.1.

## Appendix

###  Appendix A Lattice and geometry of numbers estimates

In this appendix we use the convention (also used in the main paper) that if
$x\in\mathbf{Z}^{D}$ then $|x|$ means $\|x\|_{\infty}$.The following lemma is
probably standard, but we do not know a reference.

######  Lemma A.1.

Suppose that $\Lambda,\Lambda^{\prime}$ are two $m$-dimensional lattices and
that $\Lambda^{\prime}\leqslant\Lambda$. Let $(e_{i})_{i=1}^{m}$ be an
integral basis for $\Lambda$. Then there is an integral basis
$(e^{\prime}_{i})_{i=1}^{m}$ for $\Lambda^{\prime}$ such that the following is
true: if $x\in\Lambda^{\prime}$ and $x=\sum x_{i}e_{i}=\sum
x^{\prime}_{i}e^{\prime}_{i}$, then $\max_{i}|x^{\prime}_{i}|\leqslant
2^{m}\max_{i}|x_{i}|$.

###### Proof.

By the existence of Hermitian normal form, $\Lambda^{\prime}$ has a basis
$(e^{\prime}_{i})_{i=1}^{m}$ in which

$e^{\prime}_{i}=d_{i}e_{i}+\sum_{j>i}b_{i,j}e_{j},$

with $d_{1},\dots,d_{m}\geqslant 1$ integers and $0\leqslant b_{i,j}<d_{j}$.
It follows that

$x_{i}=x^{\prime}_{i}d_{i}+\sum_{j<i}b_{j,i}x^{\prime}_{j}.$

Suppose that $|x_{i}|\leqslant M$ for all $i$. Then an easy induction confirms
that $|x^{\prime}_{i}|\leqslant 2^{i-1}M$, and the result follows. (For
example,

$|x^{\prime}_{2}|=\big{|}\frac{x_{2}}{d_{2}}-\frac{b_{1,2}x^{\prime}_{1}}{d_{2}}\big{|}\leqslant|x_{2}|+2^{0}M\leqslant
2^{1}M.)$

∎

######  Lemma A.2.

Let $Q\geqslant 1$ be a parameter. Let $V\leqslant\mathbf{Q}^{D}$ be a vector
subspace, spanned over $\mathbf{Q}$ by linearly independent vectors
$v_{1},\dots,v_{m}\in\mathbf{Z}^{D}$ with $|v_{i}|\leqslant Q$ for all $i$.
Then there is an integral basis $w_{1},\dots,w_{m}$ for $V\cap\mathbf{Z}^{D}$
such that every element $x\in V\cap\mathbf{Z}^{D}$ with $|x|\leqslant Q$ is a
(unique) $\mathbf{Z}$-linear combination $x=\sum_{i=1}^{m}n_{i}w_{i}$ with
$|n_{i}|\leqslant m!(2Q)^{m}$.

###### Proof.

Write $\Lambda^{\prime}:=V\cap\mathbf{Z}^{D}$. Consider the $m$-by-$D$ matrix
whose $(i,j)$-entry is the $j$th coordinate $v^{(i)}_{j}$. This has full rank
$m$, and so it has a nonsingular $m$-by-$m$ minor. Relabelling, we may suppose
that this is $(v^{(i)}_{j})_{1\leqslant i,j\leqslant m}$. Suppose now that
$x=\sum_{i=1}^{m}\lambda_{i}v^{(i)}\in V\cap\mathbf{Z}^{D}$, where the
$\lambda_{i}$ lie in $\mathbf{Q}$. Then the $\lambda_{i}$ may be recovered by
applying the inverse of $(v^{(i)}_{j})_{1\leqslant i,j\leqslant m}$ to
$(x_{1},\dots,x_{m})$. By the formula for the inverse in terms of the
adjugate, this inverse has entries in the set
$\\{\frac{a}{q}:a\in\mathbf{Z},|a|\leqslant(m-1)!Q^{m-1}\\}$ where
$q=\det((v^{(i)}_{j}))_{1\leqslant i,j\leqslant m}$, and so $q\lambda_{i}$ is
an integer of size at most $m!Q^{m}$.

Take $e_{i}:=\frac{1}{q}v^{(i)}$, and let $\Lambda$ be the lattice generated
by the $e_{i}$. We have shown that $\Lambda^{\prime}\leqslant\Lambda$, and
moreover that if $x\in\Lambda^{\prime}$ and $|x|\leqslant Q$ then
$x=\sum_{i}x_{i}e_{i}$ with $|x_{i}|\leqslant m!Q^{m}$. Applying Lemma A.1,
the result follows. ∎

######  Lemma A.3.

Let $Q\geqslant 1$. Let $n$ be sufficiently large and let
$V\leqslant\mathbf{R}^{n}$ be a subspace of dimension $m$. Then, uniformly in
$V$, $\\#\\{x\in\mathbf{Z}^{n}:|x|\leqslant Q,x\in V\\}\leqslant
20^{n}m^{n/2}Q^{m}$.

###### Proof.

Let $S:=\\{x\in\mathbf{Z}^{n}:|x|\leqslant Q,x\in V\\}$. Pick an orthonormal
basis $v_{1},\dots,v_{n}$ for $\mathbf{R}^{n}$ with $v_{1},\dots,v_{m}$ being
a basis for $V$. For each $x\in\mathbf{R}^{n}$, consider the rotated box

$R(x):=\\{x+\sum_{i=1}^{m}c_{i}v_{i}+Q\sum_{i=m+1}^{n}c_{i}v_{i}:x\in
S,|c_{i}|<\frac{1}{2}m^{-1/2}\;\mbox{for all $i$}\\}.$

We claim that for distinct $x,x^{\prime}\in S$, $R(x)$ and $R(x^{\prime})$ are
disjoint. Indeed if not we would have (since $x,x^{\prime}\in V$)
$x+\sum_{i=1}^{m}c_{i}v_{i}=x^{\prime}+\sum_{i=1}^{m}c^{\prime}_{i}v_{i}$ and
hence by orthogonality
$\|x-x^{\prime}\|_{2}^{2}=\sum_{i=1}^{m}|c_{i}-c^{\prime}_{i}|^{2}<1$, which
is a contradiction since $x-x^{\prime}\in\mathbf{Z}^{D}$.

Now the volume of $R(x)$ is $m^{-n/2}Q^{n-m}$, and if $y\in R(x)$ then

$\|y\|_{2}\leqslant\|x\|_{2}+\|\sum_{i=1}^{m}c_{i}v_{i}+Q\sum_{i=m+1}^{n}c_{i}v_{i}\|_{2}\leqslant
2n^{1/2}Q.$

Using a crude upper bound of $(100/n)^{n/2}$ for the volume of the unit ball
in $\mathbf{R}^{n}$, the volume of this set is at most $20^{n}Q^{n}$. The
result follows. ∎

###  Appendix B Smooth bump functions

In this appendix we give constructions of the various cutoff functions used in
the main body of the paper. We begin with cutoffs with compact support in
physical space. These are all variants of the classical Fejér kernel
construction, sometimes with an extra convolution to create more smoothing.

######  Lemma B.1.

Let $\eta>0$. Then there is a continuously differentiable function
$w:\mathbf{R}\rightarrow[0,\infty)$ with the following properties.

  1. (1)

$w$ is supported on $[0,1]$, $w=1$ on $[\eta,1-\eta]$, and $0\leqslant
w\leqslant 1$ everywhere;

  2. (2)

$\|w^{\prime}\|_{\infty}\ll\eta^{-1}$;

  3. (3)

$\|\hat{w}\|_{1}\ll\eta^{-1}$.

###### Proof.

This is a standard kind of “tent” function. Take

$w:=\frac{4}{\eta^{2}}1_{[\eta/2,1-\eta/2]}\ast 1_{[-\eta/4,\eta/4]}\ast
1_{[-\eta/4,\eta/4]}.$

It is straightforward to see that this has the relevant support properties
(1). For (2), on the intervals where $w$ is not constant it is of the form
$\psi(\frac{x+a}{2\eta})$, where $\psi$ is the triple convolution
$1_{[-1/2,1/2]}\ast 1_{[-1/2,1/2]}\ast 1_{[-1/2,1/2]}$. It is well-known that
such a triple convolution is continuously differentiable; one mode of argument
is via the Fourier transform, noting that $|\hat{\psi}(\xi)|\ll|\xi|^{-3}$, so
one gets a convergent integral by differentiating
$\psi(x)=\int\hat{\psi}(\xi)e(\xi\cdot x)d\xi$ under the integral.
Alternatively, one can work entirely in physical space.

(3) By performing the integrals explicitly,

$\hat{w}(\xi)=\frac{4}{\eta^{2}}\hat{1}_{[\eta/2,1-\eta/2]}(\xi)\hat{1}_{[-\eta/4,\eta/4]}(\xi)^{2}\ll\eta^{-2}\min(\eta,|\xi|^{-1})^{2}.$

Now consider the contributions from $|\xi|\leqslant\eta^{-1}$ and
$|\xi|\geqslant\eta^{-1}$ separately. ∎

######  Lemma B.2.

Let $X\geqslant 1$. There is a function $w:\mathbf{Z}\rightarrow[0,\infty)$
such that

  1. (1)

$w$ is supported on $[-X/5,X/5]$;

  2. (2)

$\hat{w}:\mathbf{T}\rightarrow\mathbf{C}$ is real and non-negative;

  3. (3)

$\sum_{n}w(n)\geqslant X$;

  4. (4)

$|\hat{w}(\beta)|\leqslant 2^{5}X^{-1}\|\beta\|_{\mathbf{T}}^{-2}$ for all
$\beta\in\mathbf{T}$.

###### Proof.

This is a standard Fejér kernel construction. Take

$w:=\frac{25}{X}1_{[-X/10,X/10]}\ast 1_{[-X/10,X/10]}(n).$

Then $w$ is immediately seen to satisfy (1), (2) and (3). For (4), we evaluate
the Fourier transform explicitly as

$\hat{w}(\beta)=\frac{25}{X}|\sum_{|n|\leqslant X/10}e(-\beta n)|^{2}.$

The sum here is a geometric progression; summing it, we obtain

$|\sum_{|n|\leqslant X/10}e(-\beta n)|\leqslant\frac{2}{|1-e(\beta
n)|}=\frac{1}{|\sin\pi\beta|}\leqslant\|\beta\|_{\mathbf{T}}^{-1}.$

The result follows. ∎

######  Lemma B.3.

Let $\delta\in(0,1)$. Then there is
$\chi:=\chi_{\delta}:\mathbf{R}\rightarrow[0,\infty)$ satisfying the following
properties, where the implied constants are absolute and do not depend on
$\delta$.

  1. (1)

$\chi(x)\geqslant 1$ for $|x|\leqslant\delta/2$;

  2. (2)

$\chi(x)=0$ for $|x|>\delta$;

  3. (3)

$\int\chi\ll\delta$;

  4. (4)

$\|\hat{\chi}\|_{1}\ll 1$;

  5. (5)

$\int_{|\xi|>\delta^{-2}}|\hat{\chi}(\xi)|\ll\delta^{2}$.

###### Proof.

It suffices to construct a function $\psi:\mathbf{R}\rightarrow[0,\infty)$
satisfying

  1. (1)

$\psi(x)\geqslant 1$ for $|x|\leqslant 1/2$;

  2. (2)

$\psi(x)=0$ for $|x|>1$;

  3. (3)

$\int\psi\ll 1$;

  4. (4)

$\|\hat{\psi}\|_{1}\ll 1$;

  5. (5)

$\int_{|\xi|>X}|\hat{\psi}(\xi)|\ll X^{-2}$ for $X\geqslant 1$.

Then one may take $\chi_{\delta}:=\psi(\delta^{-1}x)$, and the five properties
of $\chi$ in the lemma follow from the five properties of $\psi$ just stated
using $\hat{\chi}_{\delta}(\xi)=\delta\hat{\psi}(\xi\delta)$, and taking
$X=\delta^{-1}$. A function with these properties is

$\psi(x):=16\cdot 1_{[-3/4,3/4]}\ast 1_{[-1/8,1/8]}\ast 1_{[-1/8,1/8]}.$

Properties (1), (2), (3) are easily checked. For (4) and (5), one may compute
the Fourier transform explicitly and thereby obtain the bound
$\hat{\psi}(\xi)\ll\min(1,|\xi|^{-3})$, from which (4) and (5) both follow
straight away. ∎

Now we turn to some cutoff functions with compact support in frequency space.

######  Lemma B.4.

There is a function $\psi:\mathbf{R}\rightarrow\mathbf{R}$ satisfying the
following:

  1. (1)

$\psi\geqslant 0$ everywhere, and $\psi(x)\geqslant 1$ for $|x|\leqslant 1$

  2. (2)

$\hat{\psi}(y)=0$ for $|y|\geqslant 1$;

  3. (3)

$\int\psi\leqslant 5$.

###### Proof.

Take $\psi(x):=\frac{\sin^{2}x}{x^{2}\sin^{2}1}$. Then (1) is immediate. For
(2) and (3), observe the Fourier transform
$\int^{\infty}_{-\infty}\frac{\sin^{2}x}{x^{2}}e(-\xi
x)dx=\pi(1-\pi|\xi|)_{+}$, and then finally use $\pi<5\sin^{2}1$. ∎

######  Lemma B.5.

There is a smooth cutoff $\chi:\mathbf{T}^{D}\rightarrow[0,\infty)$ satisfying

  1. (1)

$\chi(x)\geqslant 1$ for $\|x\|_{\mathbf{T}^{D}}\leqslant X^{-1/D}$;

  2. (2)

$\int\chi\leqslant 5^{D}X^{-1}$;

  3. (3)

$\hat{\chi}(\xi)=0$ for $|\xi|\geqslant X^{1/D}$;

###### Proof.

It suffices to prove the following $1$-dimensional result: given
$\varepsilon>0$, there is
$\phi=\phi_{\varepsilon}:\mathbf{T}\rightarrow[0,\infty)$ such that

  1. (1)

$\phi(x)\geqslant 1$ for $\|x\|_{\mathbf{T}}\leqslant\varepsilon$;

  2. (2)

$\int\phi\leqslant 5\varepsilon$;

  3. (3)

$\hat{\phi}(\xi)=0$ for $|\xi|\geqslant 1/\varepsilon$, $\xi\in\mathbf{Z}$.

Indeed, one may then take $\varepsilon=X^{-1/D}$ and
$\chi(x_{1},\dots,x_{D})=\prod_{i=1}^{D}\phi(x_{i})$ to satisfy the desiderata
of the lemma.

It remains to construct $\phi$. With a slight abuse of notation, we construct
$\phi$ as a $1$-periodic real function rather than a function on $\mathbf{T}$
(they are, of course, basically the same thing). To do this, take the function
$\psi$ constructed in Lemma B.4, and set.

$\phi(x):=\sum_{n\in\mathbf{Z}}\psi(\varepsilon^{-1}(x+n)).$

Then $\phi$ is a smooth function on $\mathbf{T}$ taking non-negative values,
and it satisfies (1) above (just by taking the term $n=0$ in the sum). By
unfolding the sum we have

$\int_{\mathbf{T}}\phi(x)=\int_{t\in\mathbf{R}}\psi(\varepsilon^{-1}t)dt\leqslant
5\varepsilon,$

by change of variables and Lemma B.4 (3). Turning to the Fourier transform, if
$\xi\in\mathbf{Z}$ then

$\displaystyle\hat{\phi}(\xi)$
$\displaystyle=\int^{1}_{0}\sum_{n\in\mathbf{Z}}\psi(\varepsilon^{-1}(x+n))e(-\xi
x)$
$\displaystyle=\int^{1}_{0}\sum_{n\in\mathbf{Z}}\psi(\varepsilon^{-1}(x+n))e(-\xi(x+n))$
$\displaystyle=\int_{\mathbf{R}}\psi(\varepsilon^{-1}t)e(-\xi
t)dt=\varepsilon\hat{\psi}(\xi\varepsilon).$

By Lemma B.4 (2), this vanishes when $|\xi|\geqslant 1/\varepsilon$.

∎

Finally, for use in Section 8 we construct a minorant function with compactly
supported, nonnegative Fourier transform. For the construction we use a trick
shown to me in a different context by Joni Teräväinen.

######  Lemma B.6.

Let $D$ be sufficiently large and suppose that $\rho\leqslant D^{-4}$. There
is a function $\chi:\mathbf{T}^{D}\rightarrow\mathbf{R}$ such that

  1. (1)

$\chi(x)\leqslant 0$ unless $x\in\pi(B_{\rho/10}(0))$, where
$B_{\varepsilon}(0)\subset\mathbf{R}^{D}$ is the Euclidean ball of radius
$\varepsilon$ and $\pi:\mathbf{R}^{D}\rightarrow\mathbf{T}^{D}$ is the natural
projection;

  2. (2)

$\hat{\chi}(\xi)\geqslant 0$ for all $\xi\in\mathbf{Z}^{D}$;

  3. (3)

$\hat{\chi}$ is supported on $|\xi|\leqslant\rho^{-3}$;

  4. (4)

$\int\chi=1$.

  5. (5)

$\int|\chi|\leqslant 3$.

###### Proof.

Rather than working with Euclidean balls and the $\ell^{2}$-norm, it is easier
to work with the distance $\|\cdot\|_{\mathbf{T}^{D}}$ directly. Note that
$D^{1/2}\|\pi(t)\|_{\mathbf{T}^{D}}\geqslant\|t\|_{2}$, so it suffices to
replace (1) by the stronger condition (1’) that $\chi(x)\leqslant 0$ outside
of the box $\|x\|_{\mathbf{T}^{D}}\leqslant\rho^{7/6}<D^{-1/2}\rho/10$.

Let $k=\lfloor\rho^{-3}\rfloor$. Consider

$\displaystyle\psi(x)$
$\displaystyle:=(2D+\sum_{i=1}^{D}(e(x_{i})+e(-x_{i})))^{k}-4^{k}(D-\rho^{7/3})^{k}$
$\displaystyle=4^{k}(\cos^{2}(\pi x_{1})+\dots+\cos^{2}(\pi
x_{D}))^{k}-4^{k}(D-\rho^{7/3})^{k}.$

Since $\cos^{2}(\pi t)\leqslant 1-t^{2}$ for $|t|\leqslant\frac{1}{2}$, if
$\|x\|_{\mathbf{T}^{D}}>\rho^{7/6}$ then we have

$0\leqslant\cos^{2}(\pi x_{1})+\cdots+\cos^{2}(\pi x_{D})\leqslant
D-\rho^{7/3}$ (B.1)

and so $\psi(x)\leqslant 0$. It is clear by expanding out the definition that
$\hat{\psi}(\xi)$ is supported on $|\xi|\leqslant k$ (in fact on
$\|\xi\|_{1}\leqslant k$), and also that $\hat{\psi}(\xi)\geqslant 0$ except
possibly at $\xi=0$.

To get a lower bound for $\int\psi$, we use the inequality $\cos^{2}\pi
t\geqslant 1-\pi^{2}t^{2}$, which is valid for $|t|\leqslant\frac{1}{2}$, to
conclude that if $\|x_{i}\|_{\mathbf{T}}\leqslant 1/4\sqrt{k}$ for all $i$
then

$(\cos^{2}(\pi x_{1})+\dots+\cos^{2}(\pi x_{D}))^{k}\geqslant
D^{k}(1-\frac{1}{k})^{k}\geqslant\frac{1}{3}D^{k}.$

Therefore

$\int_{\mathbf{T}^{D}}(\cos^{2}(\pi x_{1})+\dots+\cos^{2}(\pi
x_{D}))^{k}\geqslant\frac{1}{3}(2k^{-1/2})^{D}D^{k}>2k^{-D}D^{k}.$ (B.2)

By contrast, using $k=\lfloor\rho^{-3}\rfloor$, $\rho\leqslant D^{-4}$ and the
fact that $D$ is large, we see that

$(D-\rho^{7/3})^{k}\leqslant D^{k}e^{-\rho^{7/3}k/D}<k^{-D}D^{k}.$ (B.3)

Therefore, comparing with (B.2), we see that $\int\psi>k^{-D}(4D)^{k}$.

Now define $\chi:=(\int\psi)^{-1}\psi$. Then, from what has been said above,
(1’), (2), (3) and (4) all hold.

It remains to establish (5). For this write $\psi=\psi_{+}-\psi_{-}$ in
positive and negative parts, and note that $\psi_{-}\leqslant
4^{k}(D-\rho^{7/3})^{k}$ pointwise. By (B.3) it follows that
$\int\psi_{-}<k^{-D}(4D)^{k}<\int\psi$. Since $|\psi|=\psi+2\psi_{-}$, it
follows that $\int|\psi|\leqslant 3\int\psi$, and (5) follows immediately.

∎

### References

  * [1] T. Ahmed, O. Kullmann and H. Snevily, _On the van der Waerden numbers $w(2;3,t)$,_ Discrete Appl. Math. 174 (2014), 27–51.
  * [2] G. W. Anderson, A. Guionnet and O. Zeitouni, _An introduction to random matrices_ , Cambridge Studies in Advanced Mathematics 118. Cambridge University Press, Cambridge, 2010. xiv+492 pp.
  * [3] 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.
  * [4] T. Bloom and O. Sisask, _Breaking the logarithmic barrier in Roth’s theorem on arithmetic progressions,_ preprint (July 2020), https://arxiv.org/abs/2007.03528.
  * [5] T. Brown, B. M. Landman and A. Robertson, _Bounds on some van der Waerden numbers_ , J. Combinatorial Theory, Series A 115 (2008), 1304–1309.
  * [6] R. Delannay and G. Le Caër, _Distribution of the determinant of a random real-symmetric matrix from the Gaussian orthogonal ensemble_ , Phys. Rev. E (3) 62 (2000), 1526–1536.
  * [7] M. Elkin, _An improved construction of progression-free sets_ , Israel. J. Math. 184, 93–128 (2011).
  * [8] P. Erdős and A. Rényi, _On some combinatorial problems_ , Publ. Math. Debrecen 4 (1956), 398–405.
  * [9] J. Fox and C. Pohoata, _Sets without $k$-term progressions can have many shorter progressions_, Random Structures and Algorithms 58 (2021), no. 3, 383–389.
  * [10] R. Graham, _On the growth of a van der Waerden-like function_ , INTEGERS: Electronic journal of combinatorial number theory 6 (2006), $\\#$ A 29
  * [11] B. J. Green and J. Wolf, _A note on Elkin’s improvement of Behrend’s construction_ , in _Additive Number Theory_ , 141–144, Springer, New York 2010.
  * [12] B. J. Green, _100 open problems_ , manuscript, available on request.
  * [13] D. R. Heath-Brown and L. Pierce, _Simultaneous integer values of pairs of quadratic forms,_ J. Reine Angew. Math. 727 (2017), 85–143.
  * [14] Z. Hunter, _Improved lower bounds for van der Waerden numbers_ , to appear, Combinatorica.
  * [15] N. Kuzjurin, _On the difference between asymptotically good packings and coverings_ , European Journal of Combinatorics 16 (1995), no. 1, 35–40.
  * [16] Y. Li and J. Shu, _A lower bound for off-diagonal van der Waerden numbers_ , Advances in Applied Mathematics 44 (2010), 243–247.
  * [17] A. M. Ostrowski, _Sur l’approximation du déterminant de Fredholm par les déterminants des systémes d’equations linéaires_ , Ark. Math. Stockholm Ser. A, 26 (1938), pp. 1–15, reprinted in A. M. Ostrowski, Alexander Ostrowski: Collected Mathematical Papers, Vol. 1 (Determinants, Linear Algebra, Algebraic Equations), Birkhäuser, 1983, pp 60–74.
  * [18] R. Salem and D. Spencer, _On sets of integers which contain no three terms in arithmetical progression_ , Proc. Nat. Acad. Sci. U.S.A. 28 (1942), 561–563.
  * [19] T. Schoen, _A subexponential bound for van der Waerden numbers $W(3,k)$_, Electronic J. Combinatorics 28 (2021), no. 2, P2.34.