# New lower bounds for van der Waerden numbers

Ben Green  Mathematical Institute
Radcliffe Observatory Quarter
Woodstock Road
Oxford OX2 6GG
England<EMAIL_ADDRESS>
###### Abstract.

We show that there is a red-blue colouring of $[N]$ with no blue 3-term
arithmetic progression and no red arithmetic progression of length $e^{C(\log
N)^{3/4}(\log\log N)^{1/4}}$. Consequently, the two-colour van der Waerden
number $w(3,k)$ is bounded below by $k^{b(k)}$, where $b(k)=c\big{(}\frac{\log
k}{\log\log k}\big{)}^{1/3}$. Previously it had been speculated, supported by
data, that $w(3,k)=O(k^{2})$.

###### 2000 Mathematics Subject Classification:

Primary

The author is supported by a Simons Investigator grant and is grateful to the
Simons Foundation for their continued support.

###### Contents

  1. I Introduction
    1. 1 Statement of results and history
    2. 2 Overview and structure the paper
    3. 3 Notation and conventions
  2. II A red/blue colouring of $[N]$
    1. 4 Random ellipsoidal annuli
    2. 5 The colouring. Outline proof of the main theorem
  3. III Monochromatic progressions
    1. 6 No blue 3-term progressions
    2. 7 Diophantine conditions
    3. 8 The first step - red progressions enter balls
    4. 9 The second step – red progressions hit annuli
  4. IV Multidimensional structure and geometry of numbers
    1. 10 Preliminaries on volume
    2. 11 Non-concentration on subspaces
    3. 12 Geometry of numbers
    4. 13 Comparison of two distributions on quadratic forms
  5. V Small gaps and quadratic forms
    1. 14 Determinants of random matrices
    2. 15 An application of the circle method
    3. 16 An amplification argument
  6. A Lattice and geometry of numbers estimates
  7. B Smooth bump functions

##  Part I Introduction

###  1\. Statement of results and history

Let $k\geqslant 3$ be a positive integer. Write $w(3,k)$ (sometimes written
$w(2;3,k)$) for the smallest $N$ such that the following is true: however
$[N]=\\{1,\dots,N\\}$ is coloured blue and red, there is either a blue 3-term
arithmetic progression or a red $k$-term arithmetic progression. The
celebrated theorem of van der Waerden implies that $w(3,k)$ is finite; the
best upper bound currently known is due to Schoen [19], who proved that for
large $k$ one has $w(3,k)<e^{k^{1-c}}$ for some constant $c>0$. This also
follows from the celebrated recent work of Bloom and Sisask [4] on bounds for
Roth’s theorem.

There is some literature on lower bounds for $w(3,k)$. Brown, Landman and
Robertson [5] showed that $w(3,k)\gg k^{2-\frac{1}{\log\log k}}$, and this was
subsequently improved by Li and Shu [16] to $w(3,k)\gg(k/\log k)^{2}$, the
best bound currently in the literature. Both of these papers use probabilistic
arguments based on the Lovász Local Lemma.

Computation or estimation of $w(3,k)$ for small values of $k$ has attracted
the interest of computationally-inclined mathematicians. In [5] one finds, for
instance, that $w(3,10)=97$, whilst in Ahmed, Kullmann and Snevily [1] one
finds the lower bound $w(3,20)\geqslant 389$ (conjectured to be sharp) as well
as $w(3,30)\geqslant 903$. This data suggests a quadratic rate of growth, and
indeed Li and Shu state as an open problem to prove or disprove that
$w(3,k)\geqslant ck^{2}$, whilst in [1] it is conjectured that
$w(3,k)=O(k^{2})$. Brown, Landman and Robertson are a little more circumspect
and merely say that it is “of particular interest whether or not there is a
polynomial bound for $w(3,k)$”. I should also admit that I suggested the
plausibility of a quadratic bound myself [12, Problem 14].

The main result in this paper shows that, in fact, there is no such bound.

######  Theorem 1.1.

There is a blue-red colouring of $[N]$ with no blue 3-term progression and no
red progression of length $e^{C(\log N)^{3/4}(\log\log N)^{1/4}}$.
Consequently we have the bound $w(3,k)\geqslant k^{b(k)}$, where
$b(k)=c\big{(}\frac{\log k}{\log\log k}\big{)}^{1/3}$.

_Update, June 2022:_ Nine months after the arxiv version of this paper was
made public, Zachary Hunter [14] was able to simplify parts of the argument,
and at the same time improve the lower bound to $w(3,k)\geqslant
k^{b^{\prime}(k)}$, where $b^{\prime}(k)=c\frac{\log k}{\log\log k}$.

_Acknowledgements._ It is a pleasure to thank Jon Keating, Peter Keevash, Jens
Marklof and Mark Rudelson and the three anonymous referees for helpful
comments on various issues related to the paper.

###  2\. Overview and structure the paper

####  2.1. Discussion and overview

I first heard the question of whether or not $w(3,k)=O(k^{2})$ from Ron Graham
in around 2004. My initial reaction was that surely this must be false, for
the following reason: take a large subset of $[N]$ free of 3-term
progressions, and colour it blue. Then the complement of this set probably
does not have overly long red progressions. However, by considering the known
examples of large sets free of 3-term progressions, one swiftly becomes less
optimistic about this strategy.

_Example 1._ If we take the blue points to be the folklore example
$\\{\sum_{i}a_{i}3^{i}:a_{i}\in\\{0,1\\}\\}\cap[N]$ then the set of red points
contains a progression of _linear_ length, namely $\\{n\equiv
2(\operatorname{mod}\,3)\\}$.

_Example 2._ If we take the blue points to be the Salem-Spencer set [18] or
the Behrend set [3] then one runs into similar issues. Both sets consists of
points $a_{1}+a_{2}(2d-1)+\dots+a_{n}(2d-1)^{n}$ with all
$a_{i}\in\\{0,1,\dots,d-1\\}$, and for such sets the red set will contain
progressions such as $\\{n\equiv d(\operatorname{mod}\,2d-1)\\}$. If
$N:=d(2d-1)^{n}$, so that the set is contained in $[N]$, the length of such a
red progression is $\sim N/d$. In the Behrend case one takes $d\sim\sqrt{\log
N}$, so this is very long.

_Example 3._ One runs into an apparently different kind of obstacle (though in
fact it is closely related) when considering the variant of Behrend’s
construction due to Julia Wolf and myself [11]. (The _bound_ in [11] was
previously obtained by Elkin [7], but the method of construction in [11] was
different.) Roughly speaking, this construction proceeds as follows. Pick a
dimension $D$ and consider the torus
$\mathbf{T}^{D}=\mathbf{R}^{D}/\mathbf{Z}^{D}$. In this torus, consider a thin
annulus, the projection $\pi(A)$ of the set
$A=\\{x\in\mathbf{R}^{D}:\frac{1}{4}-N^{-4/D}\leqslant\|x\|_{2}\leqslant\frac{1}{4}\\}$
under the natural map. Pick a rotation $\theta\in\mathbf{T}^{D}$ at random,
and define the blue points to be $\\{n\in[N]:\theta n\in\pi(A)\\}$. By simple
geometry one can show that the only 3-term progressions in $A$ are those with
very small common difference $v$, $\|v\|_{2}\ll N^{-4/D}$. This property
transfers to $\pi(A)$, essentially because by choosing $\frac{1}{4}$ as the
radius of the annulus one eliminates “wraparound effects” which could have
generated new progressions under the projection $\pi$. Due to the choice of
parameters it turns out that with very high probability there are no blue
3-term progressions at all.

Let us now consider red progressions. Suppose that
$\theta=(\theta_{1},\dots,\theta_{D})$, and think of $D$ as fixed, with $N$
large. By Dirichlet’s theorem, there is some $d\leqslant\sqrt{N}$ such that
$\|\theta_{1}d\|\leqslant 1/\sqrt{N}$, where $\|\cdot\|_{\mathbf{T}}$ denotes
the distance to the nearest integer. Since $\theta$ is chosen randomly, the
sequence $(\theta n)_{n=1}^{\infty}$ will be highly equidistributed, and one
certainly expects to find an $n_{0}=O_{D}(1)$ such that $\theta
n_{0}\approx(\frac{1}{2},\dots,\frac{1}{2})$. If one then considers the
progression $P=\\{n_{0}+nd:n\leqslant\sqrt{N}/10\\}$ (say), one sees that
$P\subset[N]$, and that
$\|\theta_{1}(n_{0}+nd)-\frac{1}{2}\|_{\mathbf{T}}<\frac{1}{4}$ for all
$n\leqslant\sqrt{N}/10$. That is, all points of $P$ avoid the annulus $\pi(A)$
(and in fact the whole ball of radius $\frac{1}{4}$) since their first
coordinates are confined to a narrow interval about $\frac{1}{2}$. Therefore
$P$ is coloured entirely red.

This last example does rather better than Examples 1 and 2, and it is the
point of departure for the construction in this paper. Note that, in Example
3, the progression $P$ of length $\gg\sqrt{N}$ that we found is not likely to
be the only one. One could instead apply Dirichlet’s theorem to any of the
other coordinates $\theta_{2},\dots,\theta_{D}$. Moreover, one could also
apply it to $\theta_{1}+\theta_{2}$, noting that points $x\in\pi(A)$ satisfy
$\|x_{1}+x_{2}\|_{\mathbf{T}}\leqslant\frac{\sqrt{2}}{4}$ and so avoid a
narrow “strip”
$\|x_{1}+x_{2}-\frac{1}{2}\|_{\mathbf{T}}\leqslant\frac{1}{2}-\frac{\sqrt{2}}{4}$,
or to $\theta_{1}+\theta_{2}+\theta_{3}$, noting that points $x\in\pi(A)$
satisfy $\|x_{1}+x_{2}+x_{3}\|_{\mathbf{T}}\leqslant\frac{\sqrt{3}}{4}$ and so
avoid a narrow strip
$\|x_{1}+x_{2}+x_{3}-\frac{1}{2}\|_{\mathbf{T}}\leqslant\frac{1}{2}-\frac{\sqrt{3}}{4}$.
However, this no longer applies to
$\theta_{1}+\theta_{2}+\theta_{3}+\theta_{4}$, since the relevant strip has
zero width.

This discussion suggests the following key idea: instead of one annulus
$\pi(A)$, we could try taking several, in such a way that every strip like the
ones just discussed intersects at least one of these annuli. This then blocks
all the “obvious” ways of making red progressions of length $\sim\sqrt{N}$. Of
course, one then runs the risk of introducing blue 3-term progressions.
However, by shrinking the radii of the annuli to some $\rho\lll 1$ a suitable
construction may be achieved by picking the annuli to be random translates of
a fixed one.

At this point we have an annulus
$A=\\{x\in\mathbf{R}^{D}:\rho-N^{-4/D}\leqslant\|x\|_{2}\leqslant\rho\\}$
together with a union of translates
$S:=\bigcup_{i=1}^{M}(x_{i}+\pi(A))\subset\mathbf{T}^{D}$. Pick
$\theta\in\mathbf{T}^{D}$ at random, and colour those $n\leqslant N$ for which
$\theta n\in S$ blue. As we have stated, it is possible to show that (with a
suitable choice of $\rho$, and for random translates $x_{1},\dots,x_{M}$ with
$M$ chosen correctly) there are likely to be no blue 3-term progressions.
Moreover, the obvious examples of red progressions of length $\sim\sqrt{N}$
coming from Dirichlet’s theorem are blocked.

Now one may also apply Dirichlet’s theorem to pairs of frequencies, for
instance producing $d\leqslant N^{2/3}$ such that
$\|\theta_{1}d\|_{\mathbf{T}},\|\theta_{2}d\|_{\mathbf{T}}\leqslant N^{-1/3}$,
and thereby potentially creating red progressions of length $\sim N^{1/3}$
unless they too are blocked by the union of annuli. To obstruct these, one
needs to consider “strips” of codimension $2$, for instance given by
conditions such as $x_{1},x_{2}\approx\frac{1}{2}$. Similarly, to avoid
progressions of length $\sim N^{1/4}$ one must ensure that strips of
codimension $3$ are blocked, and so on.

Using these ideas one can produce, for arbitrarily large values of $r$, a
red–blue colouring of $[N]$ with no blue 3-term progression and no obvious way
to make a red progression of length $N^{1/r}$. Of course, this is by no means
a proof that there are no such red progressions!

Let us now discuss a further difficulty which arises when one tries to show
that there no long red progressions. Consider the most basic progression
$P=\\{1,2,\dots,X\\}$, $X=N^{1/r}$, together with the task of showing it has
at least one blue point. Suppose that $x_{1}$ (the centre of the first annulus
in $S$) is equal to $0\in\mathbf{T}^{D}$. Then, since $P$ is “centred” on $0$
it is natural to try and show that $\\{\theta,2\theta,\dots,X\theta\\}$
intersects the annulus $\pi(A)$ with centre $x_{1}=0$, or in other words to
show that there is $n\leqslant X$ such that

$(\rho-N^{-4/D})^{2}<\|n\theta_{1}\|_{\mathbf{T}}^{2}+\dots+\|n\theta_{D}\|_{\mathbf{T}}^{2}<\rho^{2}.$
(2.1)

The general flavour of this problem is to show that a certain “quadratic form”
takes at least one value in a rather small interval. However, what we have is
not a bona fide quadratic form. To make it look like one, we apply standard
geometry of numbers techniques to put a multidimensional structure on the
_Bohr set_ of $n$ such that
$\|n\theta_{1}\|_{\mathbf{T}},\dots,\|n\theta_{D}\|_{\mathbf{T}}\leqslant\frac{1}{10}$
(say). This gives, inside the set of such $n$, a multidimensional progression
$\\{\ell_{1}n_{1}+\dots+\ell_{D+1}n_{D+1}:0\leqslant\ell_{i}<L_{i}\\}$, for
certain $n_{i}$ and certain lengths $L_{i}$. The size $L_{1}\cdots L_{D+1}$ of
this progression is comparable to $X$.

In this “basis”, the task (2.1) then becomes to show that there are
$\ell_{1},\dots,\ell_{D+1}$, $0\leqslant\ell_{i}<L_{i}$, such that

$(\rho-N^{-4/D})^{2}<q(\ell_{1},\dots,\ell_{D+1})<\rho^{2},$ (2.2)

where $q$ is a certain quadratic form depending on $n_{1},\dots,n_{D+1}$ and
$\theta$. A representative case (but not the only one we need to consider)
would be $L_{1}\approx\dots\approx L_{D+1}\approx L=X^{1/(D+1)}$, with the
coefficients of $q$ having size $\sim L^{-2}$ so that $q$ is bounded in size
by $O(1)$. Note that $N^{-4/D}\approx L^{-4r}$. Thus we have a problem of
roughly the following type: given a quadratic form
$q:\mathbf{Z}^{D+1}\rightarrow\mathbf{R}$ with coefficients of size $\sim
L^{-2}$, show that on the box $[L]^{D+1}$ it takes at least one value on some
given interval of length $L^{-4r}$.

Without further information, this is unfortunately a hopeless situation
because of the possibility that, for instance, the coefficients of $q$ lie in
$\frac{1}{Q}\mathbf{Z}$, for some $Q>L^{2}$. In this case, the values taken by
$q$ are $\frac{1}{Q}$-separated and hence, for moderate values of $Q$, not
likely to lie in any particular interval of length $L^{-4r}$.

A small amount of hope is offered by the fact that $q$ is not a fixed
quadratic form – it depends on the random choice of $\theta$. However, the way
in which random $\theta$ correspond to quadratic forms is not at all easy to
analyse and moreover we also need to consider similar problems for
$2\theta,3\theta,\dots$ corresponding to potential red progressions with
common difference $d=2,3,\dots$.

Our way around this issue, and the second key idea in the paper, is to
introduce a large amount of extra randomness elsewhere, in the definition of
the annuli. Instead of the standard $\ell^{2}$-norm $\|x\|_{2}$, we consider
instead a perturbation $\|(I+E)x\|_{2}$, where $E$ is a random $D\times D$
matrix with small entries so that $I+E$ is invertible with operator norm close
to $1$. Such ellipsoidal annuli are just as good as spherical ones for the
purposes of our construction. The choice of $E$ comes with a massive
$D(D+1)/2$ degrees of freedom (not $D^{2}$, because $E$s which differ by an
orthogonal matrix give the same norm). The quadratic form $q$ then becomes a
random quadratic form $q_{E}$.

With considerable effort, the distribution of $q_{E}$, $E$ random, can be
shown to be somewhat related (for typical $\theta$) to the distribution of a
truly random quadratic form $q_{a}(\ell_{1},\dots,\ell_{D+1})=\sum_{i\leqslant
j}a_{ij}\ell_{i}\ell_{j}$, with the coefficients chosen uniformly from
$|a_{ij}|\leqslant L^{-2}$. One is then left with the task of showing that a
uniformly random quadratic form $q_{a}$ takes values in a very short interval
of length $L^{-4r}$. Moreover, this is required with a very strong bound on
the exceptional probability, suitable for taking a union bound over the $\sim
N^{1-1/r}$ possible choices of the common difference $d$.

A natural tool for studying gaps in the values of quadratic forms is the
Hardy-Littlewood circle method, and indeed it turns out that a suitable
application of the Davenport-Heilbronn variant of the method can be applied to
give what we require. The application is not direct, and additionally requires
a novel amplification argument using lines in the projective plane over a
suitable $\mathbf{F}_{p}$ to get the strong bound on the exceptional
probability that we need.

The above sketch omitted at least one significant detail, namely how to handle
“uncentred” progressions $P$ starting at points other than $0$. For these, one
must use the particular choice of the centres $x_{i}$. One can show that $P$
enters inside at least one of the balls $x_{i}+\pi(B_{\rho/10}(0))$, and
starting from here one can proceed much as centred case.

####  2.2. Structure of the paper

With that sketch of the construction complete, let us briefly describe the
structure of the paper. As the above discussion suggests, it is natural to
introduce a parameter $r$ and consider the following equivalent form of
Theorem 1.1.

######  Theorem 2.1.

Let $r$ be an integer, and suppose that $N>e^{Cr^{4}\log r}$. Then there is a
red/blue colouring of $[N]$ with no blue 3-term progression and no red
progression of length $N^{1/r}$.

Taking $r=c\big{(}\frac{\log N}{\log\log N}\big{)}^{1/4}$ for suitable $c$, we
recover Theorem 1.1. While Theorems 1.1 and 2.1 are equivalent, it is much
easier to think about Theorem 2.1 and its proof by imagining that $r$ is fixed
and that $N$ is a very large compared to $r$. We will, of course, keep track
of just how large $N$ needs to be as we go along, but this is somewhat
secondary to understanding the key concepts of the argument. For the rest of
the paper, $r$ will denote the parameter appearing in Theorem 2.1, and we will
always assume (as we clearly may) that it is sufficiently large.

In Section 3 we summarise some key notation and conventions in force for the
rest of the paper. In Section 4 we turn to the details of our construction, in
particular constructing the translates $x_{1},\dots,x_{M}$ of our annuli, and
introducing the notion of a random ellipsoidal annulus properly. In Section 5
we describe the red/blue colouring itself and divide the task of showing that
there are no blue 3-term progressions or red $N^{1/r}$-term progressions into
three parts (the blue progressions, and what we call steps 1 and 2 for the red
progressions). In Section 6 we handle the blue 3-term progressions. Section 7
is then devoted to a technical “diophantine” condition on
$\theta\in\mathbf{T}^{D}$ which will be in force for the rest of the paper. In
Section 8 we handle step 1 of the treatment of red progressions.

At this point we are only one third of the way through the paper. The
remaining discussion is devoted to the treatment of step 2 for the red
progressions, which involves the geometry of numbers and gaps in random
quadratic forms material outlined above. We devote Section 9 to a more
detailed technical overview of the argument which reduces it to three key
propositions. The proofs of these propositions are then handled in Parts IV
and V of the paper. Part IV contains, roughly speaking, the relevant geometry
of numbers arguments, whilst Part V contains the arguments pertaining to gaps
in quadratic forms. These parts may be read independently of one another and
of the rest of the paper.

####  2.3. Further comments

The discussion around the application of Dirichlet’s theorem above suggests
that there are certain “phase changes” in the problem as one goes from ruling
out red progressions of length $\sim N^{1/2}$ to ruling out progressions of
length $\sim N^{1/3}$, and so on. Indeed, this is why we formulate our main
result in the equivalent form of Theorem 2.1. I consider it quite plausible
that such phase changes are not merely an artefact of our argument but rather
of the problem as a whole, and that the apparently strong numerical evidence
for quadratic behaviour of $w(3,k)$ reflects the fact that in the regime
$k\leqslant 40$ one is only seeing the first phase in which it is more
efficient to take just one large annulus as in the construction of Julia Wolf
and myself, at the expense of having to allow strips of codimension 1 which
admit red progressions of length $\sim N^{1/2}$. It would be interesting to
see whether the ideas of this paper could be used to produce, computationally,
an example with $w(3,k)\sim k^{3}$.

I have worked quite hard to try and optimise the exponent in Theorem 1.1 and
it seems to represent the limit of the method for multiple different reasons,
as discussed in a little more detail in Section 3 below. These limitations
seem to be a mix of fundamental ones and artefacts of our analysis. I would
expect that the true value of $w(3,k)$ lies somewhere in between the bound of
Theorem 1.1 and something like $k^{c\log k}$, which is what a Behrend
construction of the blue points would give if only the complement of such a
set “behaved randomly”. Ron Graham [10] established a lower bound of this type
for a restricted version of the problem in which one only forbids red
progressions with common difference $1$.

Finally, we remark that [9] is an earlier example in which random unions of
structured objects are used to understand a problem related to arithmetic
progressions.

###  3\. Notation and conventions

####  3.1. Fourier transforms

We use the standard notation $e(t):=e^{2\pi it}$ for $t\in\mathbf{R}$.

We will take Fourier transforms of functions on
$\mathbf{R}^{k},\mathbf{Z}^{k},\mathbf{T}^{k}$ for various integer $k$. We
will use the same hat symbol for all of these, and define them as follows:

  * •

If $f:\mathbf{R}^{k}\rightarrow\mathbf{C}$,
$\hat{f}(\gamma)=\int_{\mathbf{R}^{k}}f(x)e(-\langle\gamma,x\rangle)dx$ for
$\gamma\in\mathbf{R}^{k}$;

  * •

If $f:\mathbf{Z}^{k}\rightarrow\mathbf{C}$,
$\hat{f}(\theta)=\sum_{n\in\mathbf{Z}^{k}}f(n)e(-n\cdot\theta)$ for
$\theta\in\mathbf{T}^{k}$;

  * •

If $f:\mathbf{T}^{k}\rightarrow\mathbf{C}$,
$\hat{f}(\xi)=\int_{\mathbf{T}^{k}}f(x)e(-\xi\cdot x)dx$ for
$\xi\in\mathbf{Z}^{k}$.

The notation $\langle x,y\rangle$ for $\sum_{i}x_{i}y_{i}$ in
$\mathbf{R}^{k}$, but $x\cdot y$ in $\mathbf{Z}^{k}$ and $\mathbf{T}^{k}$, is
merely cultural and is supposed to reflect the fact that our arguments in the
former space will be somewhat geometric in flavour.

We will only be using the Fourier transform on smooth, rapidly decaying
functions where convergence issues are no problem. Note in particular that the
normalisation of the Fourier transform on $\mathbf{R}^{k}$ (with the phase
multiplied by $2\pi$) is just one of the standard options, but a convenient
one in this paper. With this normalisation, Fourier inversion states that
$f(x)=\int_{\mathbf{R}^{k}}\hat{f}(\gamma)e(\langle\gamma,x\rangle)d\gamma$.

####  3.2. Convention on absolute constants

It would not be hard to write in explicit constants throughout the paper. They
would get quite large, but not ridiculously so. However, we believe it makes
the presentation neater, and the dependencies between parameters easier to
understand, if we leave the larger ones unspecified and adopt the following
convention:

  * •

$C_{1}$ is a sufficiently large absolute constant;

  * •

$C_{2}$ is an even larger absolute constant, how large it needs to be
depending on the choice of $C_{1}$;

  * •

$C_{3}$ is a still larger constant, large enough in terms of $C_{1},C_{2}$.

To clarify, no matter which $C_{1}$ we choose (provided it is sufficiently
big) there is an appropriate choice of $C_{2}$, and in fact all sufficiently
large $C_{2}$ work. No matter which $C_{2}$ we choose, all sufficiently large
$C_{3}$ work. There are many constraints on how large $C_{1}$ needs to be
throughout the paper, and it must be chosen to satisfy _all_ of them, and
similarly for $C_{2},C_{3}$.

####  3.3. Key parameters

The most important global parameters in the paper are the following:

  * •

$N$: the interval $[N]$ is the setting for Theorem 2.1.

  * •

$r$: a positive integer, always assumed to be sufficiently large. $N^{1/r}$ is
the length of red progressions we are trying to forbid.

  * •

$D$: a positive integer dimension. The torus
$\mathbf{T}^{D}=\mathbf{R}^{D}/\mathbf{Z}^{D}$ will play a key role in the
paper.

Throughout the paper, we will assume that

$\mbox{$r$ sufficiently large},\qquad D=C_{3}r^{2},\qquad N\geqslant
D^{C_{2}D^{2}}.$ (3.1)

Several lemmas and propositions do not require such strong assumptions.
However, two quite different results in the paper (Proposition 4.1, and the
application of Proposition 9.3 during the proof of Proposition 5.4 in Section
9) require a condition of the form $D\gg r^{2}$. The condition
$N>D^{C_{2}D^{2}}$ comes up in the proof of Proposition 5.4, in fact in no
fewer than three different ways in the last displayed equation of Section 9.
For these reasons, it seems as if our current mode of argument cannot possibly
yield anything stronger than Theorem 2.1.

A number of other parameters and other nomenclature feature in several
sections of the paper:

  * •

$X$: shorthand for $N^{1/r}$.

  * •

$\theta$: an element of $\mathbf{T}^{D}$, chosen uniformly at random, and
later in the paper always taken to lie in the set $\Theta$ of diophantine
elements (Section 7).

  * •

$\rho$: a small radius (of annuli in $\mathbf{T}^{D}$), from Section 5 onwards
fixed to be $D^{-4}$.

  * •

$\mathbf{e}$: a uniform random element of
$[-\frac{1}{D^{4}},\frac{1}{D^{4}}]^{D(D+1)/2}$ (used to define random
ellipsoids). Usually we will see $\sigma(\mathbf{e})$, which is a symmetric
matrix formed from $\mathbf{e}$ in an obvious way (see Section 4 for the
definition).

  * •

$d$: invariably the common difference of a progression, with $d\leqslant N/X$.

The letter $Q$ is reserved for a “complexity” parameter (bounding the allowed
size of coefficients, or of matrix entries) in various different contexts.

####  3.4. Notation

$[N]$ always denotes $\\{1,\dots,N\\}$.

If $x\in\mathbf{T}$ then we write $\|x\|_{\mathbf{T}}$ for the distance from
$x$ to the nearest integer. If $x=(x_{1},\dots,x_{D})\in\mathbf{T}^{D}$ then
we write $\|x\|_{\mathbf{T}^{D}}=\max_{i}\|x_{i}\|_{\mathbf{T}}$.

We identify the dual $\hat{\mathbf{T}}^{D}$ with $\mathbf{Z}^{D}$ via the map
$\xi\mapsto(x\mapsto e(\xi\cdot x))$, where $\xi\cdot
x=\xi_{1}x_{1}+\cdots+\xi_{D}x_{D}$. In this setting we always write
$|\xi|:=\max_{i}|\xi_{i}|$, instead of the more cumbersome $\|\xi\|_{\infty}$.

Apart from occasional instances where it denotes $3.141592\dots$, $\pi$ is the
natural projection homomorphism $\pi:\mathbf{R}^{D}\rightarrow\mathbf{T}^{D}$.
Clearly $\pi$ is not invertible, but nonetheless we abuse notation by writing
$\pi^{-1}(x)$ for the unique element $y\in(-\frac{1}{2},\frac{1}{2}]^{D}$ with
$\pi(y)=x$.

If $R$ is a $D\times D$ matrix over $\mathbf{R}$ then we write $\|R\|$ for the
$\ell^{2}$-to-$\ell^{2}$ operator norm, that is to say
$\|Rx\|_{2}\leqslant\|R\|\|x\|_{2}$, and $\|R\|$ is the smallest constant with
this property. Equivalently $\|R\|$ is the largest singular value of $R$.

##  Part II A red/blue colouring of $[N]$

###  4\. Random ellipsoidal annuli

In this section, we prepare the ground for describing our red/blue colouring
of $[N]$, which we will give in Section 5. In the next section, we describe
our basic construction by specifying the points in $[N]$ to be coloured blue.
The torus $\mathbf{T}^{D}$ (and Euclidean space $\mathbf{R}^{D}$) play a
fundamental role in our construction, where $D=C_{3}r^{2}$.

####  4.1. A well-distributed set of centres

As outlined in Section 2, an important part of our construction is the
selection (randomly) of a certain set $x_{1},\dots,x_{M}$ of points in
$\mathbf{T}^{D}$. Later, we will fix $\rho:=D^{-4}$, but the following
proposition does not make any assumption on $\rho$ beyond that $\rho<D^{-1}$.

######  Proposition 4.1.

Suppose that $D=C_{3}r^{2}$ and that $\rho<\frac{1}{D}$. There are
$x_{1},\dots,x_{M}\in\mathbf{T}^{D}$ such that the following hold:

  1. (1)

Whenever $i_{1},i_{2},i_{3}$ are not all the same,
$\|x_{i_{1}}-2x_{i_{2}}+x_{i_{3}}\|_{\mathbf{T}^{D}}\geqslant 10\rho$.

  2. (2)

Whenever $V\leqslant\mathbf{Q}^{D}$ is a subspace of dimension at most $4r$
and $x\in\mathbf{T}^{D}$, there is some $j$ such that
$\|\xi\cdot(x_{j}-x)\|_{\mathbf{T}}\leqslant\frac{1}{100}$ for all $\xi\in
V\cap\mathbf{Z}^{D}$ with $|\xi|\leqslant\rho^{-3}$.

_Remark._ With reference to the outline in Section 2, condition (2) here is
saying that any “slice” of codimension at most $4r$ contains one of the
$x_{i}$; this is what obstructs a simple construction of red progressions of
length $N^{1/r}$ using Dirichlet’s theorem. Item (1) will allow us to
guarantee that by taking a union of translates of annuli, rather than just
one, we do not introduce new blue 3-term progressions.

###### Proof.

Set $M=\lceil\rho^{-D/4}\rceil$ and pick $x_{1},\dots,x_{M}\in\mathbf{T}^{D}$
independently and uniformly at random. For any triple $(i_{1},i_{2},i_{3})$
with not all the indices the same, $x_{i_{1}}-2x_{i_{2}}+x_{i_{3}}$ is
uniformly distributed on $\mathbf{T}^{D}$. Therefore
$\mathbb{P}(\|x_{i_{1}}-2x_{i_{2}}+x_{i_{3}}\|_{\mathbf{T}^{D}}\leqslant
10\rho)\leqslant(20\rho)^{D}$. Summing over all $<M^{3}$ choices of indices
gives an upper bound of $M^{3}(20\rho)^{D}<\frac{1}{4}$ on the probability
that (1) fails (since $D$ is sufficiently large).

For (2), we may assume that $V$ is spanned (over $\mathbf{Q}$) by vectors
$\xi\in\mathbf{Z}^{D}$ with $|\xi|\leqslant\rho^{-3}$ (otherwise, pass from
$V$ to the subspace of $V$ spanned by such vectors). There are at most
$4r(3\rho^{-3})^{4rD}<\rho^{-14rD}$ such $V$ (choose the dimension $m<4r$, and
then $m$ basis elements with $\xi\in\mathbf{Z}^{D}$ and
$|\xi|\leqslant\rho^{-3}$).

Fix such a $V$. By Lemma A.2, $V\cap\mathbf{Z}^{D}$ is a free
$\mathbf{Z}$-module generated by some $\xi_{1},\dots,\xi_{m}$, $m\leqslant
4r$, and with every element $\xi\in V\cap\mathbf{Z}^{D}$ with
$|\xi|\leqslant\rho^{-3}$ being $\xi=n_{1}\xi_{1}+\cdots+n_{m}\xi_{m}$ with
$|n_{i}|\leqslant m!(2\rho^{-3})^{m}\leqslant\frac{1}{400r}\rho^{-14r}$. Thus,
to satisfy our requirement, we need only show that for any
$x\in\mathbf{T}^{D}$ there is $x_{j}$ such that

$\|\xi_{i}\cdot(x_{j}-x)\|_{\mathbf{T}}\leqslant\rho^{14r}\;\mbox{for
$i=1,\dots,m$},$ (4.1)

since then

$\|\xi\cdot(x_{j}-x)\|_{\mathbf{T}}\leqslant\rho^{14r}\sum_{i=1}^{m}|n_{i}|<\frac{1}{100}.$

Divide $\mathbf{T}^{m}$ into $\rho^{-14rm}\leqslant\rho^{-56r^{2}}$ boxes of
sidelength $\rho^{14r}$; it is enough to show that each such box $B$ contains
at least one point $(\xi_{1}\cdot x_{j},\cdots\xi_{m}\cdot x_{j})$. The
following fact will also be needed later, so we state it as a separate lemma.

######  Lemma 4.2.

Let $\xi_{1},\dots,\xi_{m}\in\mathbf{Z}^{D}$ be linearly independent. Then, as
$x$ ranges uniformly over $\mathbf{T}^{D}$, $(\xi_{1}\cdot
x,\cdots,\xi_{m}\cdot x)$ ranges uniformly over $\mathbf{T}^{m}$.

###### Proof.

Let $f(t)=e(\gamma\cdot t)$ be a nontrivial character on $\mathbf{T}^{m}$.
Then

$\int_{\mathbf{T}^{D}}f(\xi_{1}\cdot x,\dots,\xi_{m}\cdot
x)dx=\int_{\mathbf{T}^{D}}e((\gamma_{1}\xi_{1}+\cdots+\gamma_{m}\xi_{m})\cdot
x)dx=0=\int_{\mathbf{T}^{m}}f,$

since $\gamma_{1}\xi_{1}+\dots+\gamma_{m}\xi_{m}\neq 0$. Since the characters
are dense in $L^{1}(\mathbf{T}^{m})$, the result follows. ∎

Returning to the proof of Proposition 4.1, Lemma 4.2 implies that for each
fixed $j$,

$\mathbb{P}((\xi_{1}\cdot x_{j},\dots,\xi_{m}\cdot x_{j})\notin
B)=1-\rho^{14rm}.$

By independence,

$\displaystyle\mathbb{P}((\xi_{1}\cdot x_{j},\dots,\xi_{m}\cdot x_{j})\notin$
$\displaystyle\;B\;\mbox{for $j=1,\dots,M$})$
$\displaystyle=(1-\rho^{14rm})^{M}\leqslant e^{-\rho^{14rm}M}\leqslant
e^{-\rho^{-D/8}}$

Here we critically use that $D=C_{3}r^{2}$; $C_{3}\geqslant 448$ is sufficient
here, but it will need to be larger than this in later arguments. Summing over
the boxes $B$, we see that the probability of even one empty box is
$\leqslant\rho^{-56r^{2}}e^{-\rho^{-D/8}}$. This is the probability that (4.1)
does not hold, for this particular $V$. Summing over the
$\leqslant\rho^{-14Dr}$ choices for $V$, the probability that (4.1) fails to
hold for _some_ $V$ is

$\leqslant\rho^{-16Dr}e^{-\rho^{-D/8}}.$

For $D$ large, this will be $<\frac{1}{4}$ as well, uniformly in $\rho$. (To
see this, write $X=1/\rho>D$, then this function is bounded by
$X^{D^{2}}e^{-X^{D/8}}$, which is absolutely tiny on the range $X>D$.)

It follows that, with probability $>\frac{1}{2}$ in the choice of
$x_{1},\dots,x_{M}$, both (1) and (2) hold. ∎

####  4.2. Random ellipsoidal annuli

Our construction is based on annuli centred on the points $x_{1},\dots,x_{M}$
just constructed. As outlined in Section 2, so as to introduce a source of
randomness into the problem we consider, rather than just spherical annuli,
random ellipsoidal annuli.

To specify the ellipsoids, here and throughout the paper identify
$\mathbf{R}^{D(D+1)/2}$ with the space of all tuples $x=(x_{ij})_{1\leqslant
i\leqslant j\leqslant D}$. Let $\mathbf{e}$ be a random tuple uniformly
sampled from
$[-\frac{1}{D^{4}},\frac{1}{D^{4}}]^{D(D+1)/2}\subset\mathbf{R}^{D(D+1)/2}$.

To any tuple $x\in\mathbf{R}^{D(D+1)/2}$, we associate a symmetric matrix
$\sigma(x)\in\operatorname{Sym}_{D}(\mathbf{R})$ (the space of $D\times D$
symmetric matrices over $\mathbf{R}$) as follows: $(\sigma(x))_{ii}=x_{ii}$,
$(\sigma(x))_{ij}=\frac{1}{2}x_{ij}$ for $i<j$, and
$(\sigma(x))_{ij}=\frac{1}{2}x_{ji}$ for $i>j$.

The ellipsoidal annuli we consider will then be of the form
$\pi(A_{\mathbf{e}})$, where $\pi:\mathbf{R}^{D}\rightarrow\mathbf{T}^{D}$ is
the natural projection and

$A_{\mathbf{e}}:=\\{x\in\mathbf{R}^{D}:\rho-N^{-4/D}<\|(I+\sigma(\mathbf{e}))x\|_{2}<\rho\\}.$
(4.2)

It is convenient to fix, for the rest of the paper,

$\rho:=D^{-4};$ (4.3)

the choice is somewhat arbitrary and any sufficiently large power of $1/D$
would lead to essentially the same bounds in our final result. With this
choice, the parameter $M$ in Proposition 4.1 (that is, the number of points
$x_{1},\dots,x_{M}$) is $D^{D}$.

Now $\|\sigma(e)\|\leqslant D\|e\|_{\infty}\leqslant\frac{1}{2}$, where
$\|\cdot\|$ denotes the $\ell^{2}$-to-$\ell^{2}$ operator norm on matrices,
and therefore

$\frac{1}{2}\leqslant\|I+\sigma(\mathbf{e})\|\leqslant\frac{3}{2}.$ (4.4)

_Remark._ Taking $\sigma(\mathbf{e})$ to be symmetric is natural in view of
the polar decomposition of real matrices. Premultiplying $\sigma(\mathbf{e})$
by an orthogonal matrix makes no difference to
$\|(I+\sigma(\mathbf{e}))x\|_{2}$.

###  5\. The colouring. Outline proof of the main theorem

We are now in a position to describe our red/blue colouring of $[N]$. Once
again let $r,D$ be integers with $r$ sufficiently large and $D=C_{3}r^{2}$.
Set $\rho:=D^{-4}$, and let $x_{1},\dots,x_{M}\in\mathbf{T}^{D}$ be points as
constructed in Proposition 4.1, for this value of $\rho$. Pick
$\mathbf{e}\in[-\frac{1}{D^{4}},\frac{1}{D^{4}}]^{D(D+1)/2}\subset\mathbf{R}^{D(D+1)/2}$
uniformly at random, and consider the random ellipsoidal annulus

$A_{\mathbf{e}}:=\\{x\in\mathbf{R}^{D}:\rho-N^{-4/D}<\|(I+\sigma(\mathbf{e}))x\|_{2}<\rho\\}.$

Pick $\theta\in\mathbf{T}^{D}$ uniformly at random, let
$\pi:\mathbf{R}^{D}\rightarrow\mathbf{T}^{D}$ be the natural projection, and
define a red/blue colouring by

$\operatorname{Blue}_{\mathbf{e},\theta}:=\\{n\in[N]:\theta
n\in\bigcup_{j=1}^{M}(x_{j}+\pi(A_{\mathbf{e}})\\},$ (5.1)

$\operatorname{Red}_{\mathbf{e},\theta}:=[N]\setminus\operatorname{Blue}_{\mathbf{e},\theta}.$
(5.2)

Suppose henceforth that $N>D^{C_{2}D^{2}}$, this being stronger than needed
for some results but necessary in the worst case. We claim that with high
probability there is no blue progression of length $3$.

######  Proposition 5.1.

Suppose that $N>D^{C_{2}D^{2}}$. Then

$\mathbb{P}_{\theta,\mathbf{e}}\big{(}\mbox{$\operatorname{Blue}_{\theta,\mathbf{e}}$
has no 3-term progression}\big{)}\geqslant 1-O(N^{-1}).$

In dealing with the progressions in the red points, we introduce a specific
set $\Theta$ of rotations $\theta\in\mathbf{T}^{D}$ which we wish to consider.
We call $\Theta$ the set of _diophantine_ $\theta$: the terminology is not
standard, but the word diophantine is used in similar ways in other contexts.
The precise definition of $\Theta$ is given in Section 7 below. Roughly,
$\theta$ is disqualified from $\Theta$ if the orbit $\\{\theta n:n\leqslant
N\\}$ exhibits certain pathological behaviours such as being highly
concentrated near $0$, or having long subprogressions almost annihilated by a
large set of characters on $\mathbf{T}^{D}$. For our discussion in this
section, the important fact about $\Theta$ is that diophantine elements are
(highly) generic in the sense that

$\mu_{\mathbf{T}^{D}}(\Theta)\geqslant 1-O(N^{-1}).$ (5.3)

This is proven in Section 7, specifically Proposition 7.1, where the
definition of $\Theta$ is given.

Now we claim that, conditioned on the event that $\theta$ is diophantine, with
high probability there is no red progression of length $N^{1/r}$.

######  Proposition 5.2.

Suppose that $N>D^{C_{2}D^{2}}$. Then

$\mathbb{P}_{\mathbf{e}}\big{(}\mbox{$\operatorname{Red}_{\theta,\mathbf{e}}$
has no $N^{1/r}$-term progression}\;|\;\theta\in\Theta\big{)}\geqslant
1-O(N^{-1}),$

where $\Theta\subset\mathbf{T}^{D}$ denotes the set of diophantine elements.

The proof of Proposition 5.1 is relatively straightforward and is given in
Section 6. The proof of Proposition 5.2 is considerably more involved and
occupies the rest of the paper.

Let us now show how Theorem 2.1 follows essentially immediately from
Propositions 5.1 and 5.2.

###### Proof of Theorem 2.1.

(assuming Propositions 5.1 and 5.2) First observe that, with $D=C_{3}r^{2}$,
the conditions required in Propositions 5.1 and 5.2 will be satisfied if
$N>e^{Cr^{4}\log r}$ for a sufficiently large $C$. Also, in proving Theorem
2.1 we may clearly assume that $r$ is sufficiently large.

First note that by Proposition 5.2 and (5.3) we have

$\mathbb{P}_{\theta,\mathbf{e}}\big{(}\mbox{$\operatorname{Red}_{\theta,\mathbf{e}}$
has no $N^{1/r}$-term progression}\big{)}\geqslant 1-O(N^{-1}).$

This and Proposition 5.1 imply that there is some choice of
$\theta,\mathbf{e}$ (in fact, a random choice works with very high
probability) for which simultaneously
$\operatorname{Blue}_{\theta,\mathbf{e}}$ has no 3-term progression and
$\operatorname{Red}_{\theta,\mathbf{e}}$ has no $N^{1/r}$-term progression.
This completes the proof of Theorem 2.1. ∎

Let us consider the task of proving Proposition 5.2 in a little more detail.
Let

$X:=N^{1/r},$ (5.4)

a notational convention we will retain throughout the paper.

It suffices to show that if $N>D^{C_{2}D^{2}}$ and if $\theta\in\Theta$ is
diophantine then for each fixed progression $P=\\{n_{0}+dn:n\leqslant
X\\}\subset[N]$ of length $X$,

$\mathbb{P}_{\mathbf{e}}(P\cap\operatorname{Blue}_{\theta,\mathbf{e}}=\emptyset)\leqslant
N^{-3}.$ (5.5)

Indeed, there are fewer than $N^{2}$ choices of $n_{0}$ and $d$, the start
point and common difference of $P$, and so Proposition 5.2 follows from (5.5)
by the union bound.

The task, then is to show that (with very high probability) $\theta
P\subset\mathbf{T}^{D}$ intersects one of the annuli
$x_{j}+\pi(A_{\mathbf{e}})$. To achieve this, we proceed in two distinct
stages. Denoting by $P_{\operatorname{init}}=\\{n_{0}+dn:n\leqslant X/2\\}$
the first half of $P$, we show that $\theta P_{\operatorname{init}}$ at some
point enters the interior of some ball $x_{j}+\pi(B_{\rho/10}(0))$, where
$B_{\varepsilon}(0)\subset\mathbf{R}^{D}$ is the Euclidean ball of radius
$\varepsilon$, and as usual $\pi:\mathbf{R}^{D}\rightarrow\mathbf{T}^{D}$ is
projection. This we call the first step.

######  Proposition 5.3 (First step).

Suppose that $N>D^{C_{2}D^{2}}$. Let $\theta\in\Theta$ be diophantine. Let
$d\leqslant N/X$, and consider a progression
$P_{\operatorname{init}}=\\{n_{0}+dn:n\leqslant X/2\\}$. Then $\theta
P_{\operatorname{init}}$ intersects $x_{j}+\pi(B_{\rho/10}(0))$ for some
$j\in\\{1,\dots,M\\}$.

Once we have a point of $\theta P_{\operatorname{init}}$ in
$x_{j}+\pi(B_{\rho/10}(0))$ we use the remaining half of $P$ to intersect the
annulus $x_{j}+\pi(A_{\mathbf{e}})$. This we call the second step.

######  Proposition 5.4 (Second step).

Suppose that $N\geqslant D^{C_{2}D^{2}}$. Let $d\leqslant N/X$. Suppose that
$\theta\in\Theta$ is diophantine, and consider a progression
$\dot{P}=\\{dn:n\leqslant X/2\\}$. Then

$\mathbb{P}_{\mathbf{e}}(\mbox{there is $y\in\pi(B_{\rho/10}(0))$ such that
$(y+\theta\dot{P})\cap\pi(A_{\mathbf{e}})=\emptyset$})\leqslant N^{-3}.$

Together, Propositions 5.3 and 5.4 imply (5.5) and hence, as explained above,
Proposition 5.2. Indeed, Proposition 5.3 implies that there is some
$n_{0}+n_{1}d\in P_{\operatorname{init}}$ (that is, some $n_{1}\leqslant X/2$
such that $\theta(n_{0}+n_{1}d)\in x_{j}+\pi(B_{\rho/10}(0))$, for some
$j\in\\{1,\dots,M\\}$). Now apply Proposition 5.4, taking
$y=\theta(n_{0}+n_{1}d)-x_{j}$. With probability $1-O(N^{-3})$ in the choice
of $\mathbf{e}$, this provides some $n_{2}d\in\dot{P}$ (that is,
$n_{2}\leqslant X/2$) such that $y+\theta n_{2}d\in\pi(A_{\mathbf{e}})$.

If $n_{1},n_{2}$ can both be found (which happens with probability
$1-O(N^{-3})$ in the choice of $\mathbf{e}$) then

$\theta(n_{0}+(n_{1}+n_{2})d)-x_{j}\in\pi(A_{\mathbf{e}}),$

which means that $n_{0}+(n_{1}+n_{2})d$ is coloured blue. This establishes
(5.5).

The remaining tasks in the paper are therefore as follows.

  * •

Establish Proposition 5.1 (blue 3-term progressions). This is relatively
straightforward and is covered in Section 6.

  * •

Give the full definition of $\Theta$, the set of diophantine $\theta$, and
prove (5.3). This is carried out in Section 7.

  * •

Prove Proposition 5.3, the “first step” for the red progressions. This is
carried out in Section 8.

  * •

Prove Proposition 5.4, the “second step” for the red progressions.

The first three tasks, as well as an outline of the fourth, are carried out in
Part III of the paper (Sections 6, 7, 8 and 9 respectively).

The fourth task (proving Proposition 5.4) is very involved. We give a
technical outline in Section 9 which reduces it to the task of proving three
further propositions: Propositions 9.1, 9.2 and 9.3. These propositions are
established in Parts IV and V of the paper.

##  Part III Monochromatic progressions

###  6\. No blue 3-term progressions

In this section we establish Proposition 5.1. Let us recall the statement.

######  Proposition 5.1.

Suppose that $N>D^{C_{2}D^{2}}$. Then

$\mathbb{P}_{\theta,\mathbf{e}}\big{(}\mbox{$\operatorname{Blue}_{\theta,\mathbf{e}}$
has no 3-term progression}\big{)}\geqslant 1-O(N^{-1}).$

Recall that the definition of $\operatorname{Blue}_{\theta,\mathbf{e}}$ is
given in (5.1). The following lemma is a quantitative version of Behrend’s
observation that no three points on a sphere lie in arithmetic progression.
The spherical version of this was already used in [11].

######  Lemma 6.1.

Fix $e\in[-\frac{1}{D^{4}},\frac{1}{D^{4}}]^{D(D+1)/2}$. Suppose that
$u,u+v,u+2v$ all lie in $A_{e}$, where the ellipsoidal annulus $A_{e}$ is
defined as in (4.2), but with $e$ fixed. Then
$\|v\|_{2}\leqslant\frac{1}{2}N^{-2/D}$.

###### Proof.

We have the parallelogram law

$2\|y\|_{2}^{2}=\|x+2y\|_{2}^{2}+\|x\|_{2}^{2}-2\|x+y\|_{2}^{2}.$

Applying this with $x=(1+\sigma(e))u$, $y=(1+\sigma(e))v$ gives

$\|(1+\sigma(e))v\|_{2}^{2}=\|y\|_{2}^{2}\leqslant\rho^{2}-(\rho-N^{-4/D})^{2}<\frac{1}{10}N^{-4/D}.$

The result now follows from (4.4). ∎

Condition on the event that $\mathbf{e}=e$ and let $\theta\in\mathbf{T}^{D}$
be chosen uniformly at random. Suppose that $n,n+d,n+2d$ are all coloured
blue. Then for some $i,j,k\in\\{1,\dots,M\\}$ we have $\theta n\in
x_{i}+\pi(A_{e})$, $\theta(n+d)\in x_{j}+\pi(A_{e})$, $\theta(n+2d)\in
x_{k}+\pi(A_{e})$. Since $\theta(n+2d)-2\theta(n+d)+\theta n=0$ we have
$x_{i}-2x_{j}+x_{k}\in\pi(A_{e})-2\pi(A_{e})+\pi(A_{e})$, and so
$\|x_{i}-2x_{j}+x_{k}\|_{\mathbf{T}^{D}}\leqslant 4\rho$ since every
$x\in\pi(A_{e})$ has
$\|x\|_{\mathbf{T}^{D}}=\|\pi^{-1}x\|_{\infty}\leqslant\|\pi^{-1}x\|_{2}\leqslant\rho$.
By the construction of the points $x_{1},\dots,x_{M}$ (specifically,
Proposition 4.1 (1)) it follows that $i=j=k$.

We apply Lemma 6.1 with $u=\pi^{-1}(\theta n-x_{i})$, $v=\pi^{-1}(\theta d)$,
both of which lie in $B_{2\rho}(0)\subset B_{1/10}(0)$. Since $\pi(u+\lambda
v)=\theta(n+\lambda d)-x_{i}$ for $\lambda\in\\{0,1,2\\}$, we see that
$\pi(u+\lambda v)\in\pi(A_{e})$, and therefore since $u+\lambda v\in
B_{1/5}(0)$ and $A_{e}\subset B_{1/5}(0)$ we have $u+\lambda v\in A_{e}$.

It follows from Lemma 6.1 that $\|v\|_{2}\leqslant\frac{1}{2}N^{-2/D}$.
Therefore $\|\theta d\|_{\mathbf{T}^{D}}=\|\pi^{-1}(\theta
d)\|_{\infty}\leqslant\|\pi^{-1}(\theta d)\|_{2}\leqslant\frac{1}{2}N^{-2/D}$.

If $d\neq 0$ then, with $\theta\in\mathbf{T}^{D}$ chosen randomly, $\theta d$
is uniformly distributed on $\mathbf{T}^{D}$. Therefore the probability that
there is any blue 3-term progression $(n,n+d,n+2d)$ with common difference $d$
is bounded above by the probability that $\theta d$ lies in the box
$\\{x\in\mathbf{T}^{D}:\|x\|_{\mathbf{T}^{d}}\leqslant\frac{1}{2}N^{-2/D}\\}$,
a set of volume $N^{-2}$.

Therefore for any fixed $e\in[-\frac{1}{D^{4}},\frac{1}{D^{4}}]^{D(D+1)/2}$ we
have, summing over the at most $N$ possible choices for $d$, that

$\mathbb{P}_{\theta}\big{(}\mbox{$\operatorname{Blue}_{\theta,e}$ has no
3AP})\geqslant 1-O(N^{-1}),$

from which Proposition 5.1 follows immediately by removing the conditioning on
$\mathbf{e}=e$.

This completes the proof of Proposition 5.1. Note that the randomness of
$\theta$ was vital, but the ability to choose $\mathbf{e}$ randomly here was
irrelevant, since the analysis works for any fixed $\mathbf{e}=e$.

###  7\. Diophantine conditions

We turn now to the definition of $\Theta$, the set of “diophantine” rotations
$\theta\in\mathbf{T}^{D}$. Here (as usual) $X=N^{1/r}$.

######  Proposition 7.1.

Suppose that $D=C_{3}r^{2}$ and that $N\geqslant D^{D^{2}}$. Define
$\Theta\subset\mathbf{T}^{D}$ to be the set of all $\theta$ satisfying the
following two conditions:

  1. (1)

For all $n\leqslant N$,

$\dim\\{\xi\in\mathbf{Z}^{D}:|\xi|\leqslant
D^{C_{2}},\|n\xi\cdot\theta\|_{\mathbf{T}}\leqslant D^{C_{2}D}X^{-1}\\}<4r.$

  2. (2)

For all $d\leqslant N/X$,

$\\#\\{n\leqslant X:\|\theta dn\|_{\mathbf{T}^{D}}\leqslant
X^{-1/D}\\}\leqslant X^{9/10}.$

Then $\mu_{\mathbf{T}^{D}}(\Theta)\geqslant 1-O(N^{-1})$.

Before launching into the proof, let us offer some informal explanation of
conditions (1) and (2). Condition (2) is fairly self-explanatory, asserting
that orbits $\\{\theta dn:n\leqslant X\\}$ are not highly concentrated around
$0$. Note for reference that the box
$\\{x\in\mathbf{T}^{D}:\|x\|_{\mathbf{T}^{D}}\leqslant X^{-1/D}\\}$ has volume
$\sim_{D}X^{-1}$, so on average on expects just $\sim_{D}1$ points of the
orbit $\\{\theta dn:n\leqslant X\\}$ to lie in this box. Thus that (2) should
hold generically is very unsurprising (though seemingly harder to prove than
one might imagine).

Item (1) is harder to explain. With reference to the introductory discussion
in Section 2, if some condition along these lines did not hold then the orbit
$\theta n,2\theta n,3\theta n,\dots$ would be concentrated near subtori of
high codimension, and this makes it easier for such orbits to evade our union
of annuli. Thus one should expect this condition to come up in the proof of
Proposition 5.3, and we shall see in the next section that this is indeed the
case. (It also comes up later in the proof of Proposition 5.4.)

###### Proof.

We can address (1) and (2) separately and then take the intersection of the
corresponding sets of $\theta$.

(1) Suppose that $\xi_{1},\dots,\xi_{4r}$ are linearly independent over
$\mathbf{Q}$. Then, as $x$ varies uniformly over $\mathbf{T}^{D}$,
$(\xi_{1}\cdot x,\dots,\xi_{4r}\cdot x)$ is equidistributed (the proof is the
same as in Proposition 4.1). It follows that for fixed $n$,

$\mu\\{\theta:\|n\xi_{i}\cdot\theta\|_{\mathbf{T}}\leqslant
D^{C_{2}D}X^{-1}\;\mbox{for $i=1,\dots,4r$}\\}=(2D^{C_{2}D})^{4r}N^{-4}.$

By the union bound, the measure of $\theta$ for which there exists $n\leqslant
N$ such that $\|n\xi_{i}\cdot\theta\|\leqslant D^{C_{2}D}N^{-1/r}$ for
$i=1,\dots,4r$ is $\leqslant(2D^{C_{2}D})^{4r}N^{-3}$, which is comfortably
less than $N^{-2}$ with our assumptions on $r,D$ and $N$.

Now if item (1) fails then there must be some choice of
$\xi_{1},\dots,\xi_{4r}\in\mathbf{Z}^{D}$, $|\xi_{i}|\leqslant D^{C_{2}}$, for
which the preceding statement holds. The number of choices for this tuple is
at most $\big{(}(3D^{C_{2}})^{D}\big{)}^{4r}<N$. The result follows by another
application of the union bound.

(2) The proof is easier to read if we set $c:=\frac{1}{10}$ throughout (also a
similar claim with any $c>0$ would suffice for our purposes). It is enough to
show that

$\mu_{\mathbf{T}^{D}}\\{\alpha:\\#\\{n\leqslant X:\|\alpha
n\|_{\mathbf{T}^{D}}\leqslant X^{-1/D}\\}\geqslant X^{1-c}\\}\leqslant
X^{-c^{2}D/2}.$ (7.1)

Then one may take a union bound over all $\alpha=\theta d$, $d=1,\dots,N$,
noting that $NX^{-c^{2}D}<N^{-1}$ with our assumptions on $D$ and $r$ (recall
that $X=N^{1/r}$). To prove (7.1) we employ an inductive approach based on the
following claim.

_Claim._ Suppose that $\alpha^{\prime}\in\mathbf{T}^{D^{\prime}}$ and that

$\\#\\{n\leqslant X:\|\alpha^{\prime}n\|_{\mathbf{T}^{D^{\prime}}}\leqslant
X^{-(1-c)/D^{\prime}}\\}\geqslant X^{1-c}.$ (7.2)

Then there is some $\xi\in\mathbf{Z}^{D^{\prime}}$, $0<|\xi|\leqslant
2X^{3c/D^{\prime}}$, such that
$\|\xi\cdot\alpha^{\prime}\|_{\mathbf{T}}\leqslant 2X^{3c-1}$.

_Proof of Claim._ Inside the proof of the claim, we drop the dashes for
clarity (if we did not include them in the statement, it would make the
subsequent deduction of Proposition 7.1 (2) confusing). By 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-c)/D}$;

  2. (2)

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

  3. (3)

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

Then if (7.2) holds (remember, we have dropped the dashes)

$\displaystyle X^{1-c}\leqslant\sum_{n\leqslant X}\chi(\alpha n)$
$\displaystyle=\sum_{\xi}\hat{\chi}(\xi)\sum_{n\leqslant X}e(\xi\cdot\alpha
n)$ $\displaystyle\leqslant 5^{D}X^{c-1}\sum_{|\xi|\leqslant
X^{(1-c)/D}}|\sum_{n\leqslant X}e(\xi\cdot\alpha n)|$
$\displaystyle<\frac{1}{2}X^{2c-1}\sum_{|\xi|\leqslant
X^{(1-c)/D}}\min(X,\|\xi\cdot\alpha\|_{\mathbf{T}}^{-1}).$

(The factor $\frac{1}{2}$ is a minor technical convenience for later.)
Therefore

$2X^{2-3c}<\sum_{|\xi|\leqslant
X^{(1-c)/D}}\min(X,\|\xi\cdot\alpha\|_{\mathbf{T}}^{-1}).$

The contribution from those $\xi$ with
$\|\xi\cdot\alpha\|_{\mathbf{T}}\geqslant X^{3c-1}$ is bounded above by
$(3X^{(1-c)/D})^{D}X^{1-3c}<X^{2-3c}$. Writing
$\Xi\subset[-X^{1/D},X^{1/D}]^{D}$ for the set of $\xi$, $|\xi|\leqslant
X^{1/D}$, with $\|\xi\cdot\alpha\|_{\mathbf{T}}\leqslant X^{3c-1}$, it follows
that $X^{1-3c}<|\Xi|$. By the pigeonhole principle, dividing
$[-X^{1/D},X^{1/D}]^{D}$ into $X^{1-3c}$ boxes of sidelength $2X^{3c/D}$, we
see that there are distinct $\xi_{1},\xi_{2}\in\Xi$ with
$|\xi_{1}-\xi_{2}|\leqslant 2X^{3c/D}$. Taking $\xi:=\xi_{1}-\xi_{2}$
completes the proof of the claim.

Let us resume the proof of Proposition 7.1 (2). Set
$D_{0}:=\lceil(1-c)D\rceil$. We prove, by induction on $j=0,1,\dots,D-D_{0}$,
the following statement: The measure of all
$\alpha^{(j)}\in\mathbf{T}^{D_{0}+j}$ such that

$\\#\\{n\leqslant X:\|\alpha^{(j)}n\|_{\mathbf{T}^{D_{0}+j}}\leqslant
X^{-1/D}\\}\geqslant X^{1-c}$ (7.3)

is at most $X^{-cj}$. This result is trivial for $j=0$, and the case
$j=D-D_{0}$ gives the result we are trying to prove, i.e. (7.1), which implies
Proposition 7.1 (2) as explained above.

To deduce the case $j$ from $j-1$, apply the claim with $D^{\prime}=D_{0}+j$.
Since $D^{\prime}\geqslant(1-c)D$, condition (7.3) implies that

$\\#\\{n\leqslant X:\|\alpha^{(j)}n\|_{\mathbf{T}^{D^{\prime}}}\leqslant
X^{-(1-c)/D^{\prime}}\\}\geqslant X^{1-c},$

and so by the claim there is some $\xi\in\mathbf{Z}^{D^{\prime}}$,
$0<|\xi|\leqslant X^{3c/D_{0}}$ such that
$\|\xi\cdot\alpha^{(j)}\|_{\mathbf{T}}\leqslant 2X^{3c-1}$. Suppose that the
last non-zero coordinate of $\xi$ is $\xi_{D^{\prime}}=\xi_{D_{0}+j}$ (the
other possibilities can be treated similarly with very minor notational
changes). Form $\alpha^{(j-1)}\in\mathbf{T}^{D_{0}+j-1}$ by restricting
$\alpha^{(j)}$ to the first $D_{0}+j-1$ coordinates (i.e. by dropping the last
coordinate $\alpha^{(j)}_{D_{0}+j}$). Then, since
$\|\alpha^{(j-1)}n\|_{\mathbf{T}^{D_{0}+j-1}}\leqslant\|\alpha^{(j)}n\|_{\mathbf{T}^{D_{0}+j}}$,
the hypothesis (7.3) is satisfied by $\alpha^{(j-1)}$. By the inductive
hypothesis, the measure of possible $\alpha^{(j-1)}$ is at most $X^{-c(j-1)}$.
For each such $\alpha^{(j-1)}$, and for each fixed $\xi$, the final coordinate
satisfies
$\|\gamma+\xi_{D_{0}+j}\alpha^{(j)}_{D_{0}+j}\|_{\mathbf{T}}=\|\xi\cdot\alpha^{(j)}\|_{\mathbf{T}}\leqslant
2X^{3c-1}$, where $\gamma$ depends only on $\alpha^{(j-1)}$ and the first
$D_{0}+j-1$ coordinates of $\xi$. As $\alpha^{(j)}_{D_{0}+j}$ varies uniformly
over $\mathbf{T}$, so does $\xi_{D_{0}+j}\alpha^{(j)}_{D_{0}+j}$, so the
probability of this event is $\leqslant 4X^{3c-1}$.

Summing over all possible choices of $\xi$ (of which there are at most
$(3X^{3c/D_{0}})^{D}$) it follows that the total measure of $\alpha^{(j)}$
satisfying (7.3) is bounded above by

$4X^{3c-1}\cdot(3X^{3c/D_{0}})^{D}\cdot X^{-c(j-1)}<X^{-cj}.$

(The key calculation for this last step is that $3c-1+\frac{3c}{1-c}<-c$,
which is certainly true for $c=\frac{1}{10}$, and we used the assumption that
$N>D^{D^{2}}$ to comfortably absorb the $3^{D}$ term into a tiny power of
$X=N^{1/r}$.)

This completes the inductive step, and hence (7.3) is true for all $j$. As
previously remarked, the case $j=D-D_{0}\geqslant cD/2$ gives Proposition 7.1
(2). ∎

_Remark._ Whilst the $\frac{9}{10}$ in Proposition 7.1 (2) can easily be
improved a little, it cannot be improved very far by the method we have
employed here. One feels that, even with $X^{1/10}$ on the right hand side in
(2), this should be a highly likely event in $\theta$, but I do not know how
to prove anything in this direction. We state this (where, for simplicity, we
have set $D=r^{2}$) as a separate question.

######  Question 7.1.

Define $\Theta^{\prime}\subset\mathbf{T}^{r^{2}}$ to be the set of all
$\theta$ for which $\\#\\{n\leqslant N^{1/r}:\|\theta
dn\|_{\mathbf{T}^{r^{2}}}\leqslant N^{-1/r}\\}\leqslant N^{1/10r}$ for all
$d\leqslant N^{1-1/r}$. Is
$\mu_{\mathbf{T}^{r^{2}}}(\Theta^{\prime})\geqslant\frac{1}{2}$, for $N$ large
enough in terms of $r$?

We also remark that something in the direction of Proposition 7.1 (2) seems
essential for obtaining a relatively small exponent of $r$ in Theorem 2.1, but
one can still obtain _some_ fixed exponent there using only consequences of
Proposition 7.1 (1), though this would require some reorganisation of the
paper.

###  8\. The first step - red progressions enter balls

In this section we prove Proposition 5.3. Thus, let $x_{1},\dots,x_{M}$ be as
in Proposition 4.1, let $\theta\in\Theta$ be diophantine (where $\Theta$ is
defined in Proposition 7.1), and set $X:=N^{1/r}$. Recall that $\rho:=D^{-4}$,
and recall that, in the statement of Proposition 5.3, we encounter
$P_{\operatorname{init}}:=\\{n_{0}+nd:n\leqslant X/2\\}$.

###### Proof of Proposition 5.3.

Set $\alpha:=\theta d$. Set $n_{1}:=n_{0}+\lfloor\frac{X}{4}\rfloor d$, so
that $P_{\operatorname{init}}\supset\\{n_{1}+nd:|n|\leqslant X/5\\}$. Set

$\Lambda:=\\{\xi\in\mathbf{Z}^{D}:|\xi|<\rho^{-3},\|\xi\cdot\alpha\|_{\mathbf{T}}\leqslant\rho^{-2D}X^{-1}\\}.$
(8.1)

By the definition of $\Theta$ (specifically, item (1) of Proposition 7.1, and
assuming that $C_{2}\geqslant 12$) we have $\dim_{\mathbf{Q}}\Lambda<4r$. By
Proposition 4.1 there is some $j$ such that

$\|\xi\cdot(x_{j}-\theta n_{1})\|_{\mathbf{T}}\leqslant 10^{-2}$ (8.2)

for all $\xi\in\Lambda$. We claim that $\theta P_{\operatorname{init}}$
intersects the ball $x_{j}+\pi(B_{\rho/10}(0))$. To this end, take a function
$\chi:\mathbf{T}^{D}\rightarrow\mathbf{R}$ with the following properties:

  1. (1)

$\chi(x)\leqslant 0$ outside of $\pi(B_{\rho/10}(0))$;

  2. (2)

$\hat{\chi}$ is real and non-negative;

  3. (3)

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

  4. (4)

$\int\chi=1$.

  5. (5)

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

Such a function is constructed in Lemma B.6. Take also a function
$w:\mathbf{Z}\rightarrow[0,\infty)$ satisfying

  1. (a)

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

  2. (b)

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

  3. (c)

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

  4. (d)

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

For this, one can take a Fejér kernel: see Lemma B.2 for details.

Then it is enough to show that

$\sum_{n\in\mathbf{Z}}w(n)\chi(\theta(n_{1}+nd)-x_{j})>0.$ (8.3)

Indeed, if this holds then there must be some $n\in\operatorname{Supp}(w)$
(and hence $|n|\leqslant X/5$) such that $\chi(\theta(n_{1}+nd)-x_{j})>0$,
which means that $\theta(n_{1}+nd)-x_{j}\in\pi(B_{\rho/10}(0))$. Thus
$n^{\prime}:=n_{1}+nd$ lies in $P_{\operatorname{init}}$ and $\theta
n^{\prime}\in x_{j}+\pi(B_{\rho/10}(0))$, as required.

It remains to establish (8.3). By Fourier inversion on $\chi$ (recalling that
$\alpha=d\theta$), the LHS of (8.3) is

$\displaystyle\sum_{\xi\in\mathbf{Z}^{D}}\hat{\chi}(\xi)e(\xi\cdot(n_{1}\theta-$
$\displaystyle x_{j}))\sum_{n\in\mathbf{Z}}w(n)e(\xi\cdot\alpha n)$
$\displaystyle=\sum_{\xi\in\mathbf{Z}^{D}}\hat{\chi}(\xi)e(\xi\cdot(n_{1}\theta-
x_{j}))\hat{w}(-\xi\cdot\alpha)$
$\displaystyle=\sum_{\xi\in\mathbf{Z}^{D}}\hat{\chi}(\xi)\cos(2\pi\xi\cdot(n_{1}\theta-
x_{j}))\hat{w}(-\xi\cdot\alpha),$ (8.4)

where the last line follows by taking real parts, noting that the LHS of (8.3)
is real, as are $\hat{\chi}$, $\hat{w}$. Note that by (3) the sum here is
supported where $|\xi|\leqslant\rho^{-3}$. We now divide into the
contributions from the following three different classes of $\xi$: (i)
$\xi=0$; (ii) $\xi\in\Lambda$ and (iii) $|\xi|\leqslant\rho^{-3}$ but
$\xi\notin\Lambda$.

(i) The contribution from $\xi=0$ is
$\hat{\chi}(0)\hat{w}(0)=(\int\chi)(\sum_{n\in\mathbf{Z}}w(n))\geqslant X$,
using the properties of $\chi$ and $w$ listed above.

(ii) If $\xi\in\Lambda$ then by (8.2) we have $\cos(2\pi\xi\cdot(n_{1}\theta-
x_{j}))>0$. Since $\hat{\chi}$, $\hat{w}$ are both real and non-negative, the
contribution of these terms to (8.4) is non-negative.

(iii) By the triangle inequality, the contribution to (8.4) from these $\xi$
is bounded above by

$\sum_{\xi\notin\Lambda,|\xi|\leqslant\rho^{-3}}|\hat{\chi}(\xi)||\hat{w}(-\xi\cdot\alpha)|\leqslant\big{(}\sum_{|\xi|\leqslant\rho^{-3}}|\hat{\chi}(\xi)|\big{)}\sup_{\|\beta\|_{\mathbf{T}}>\rho^{-2D}X^{-1}}|\hat{w}(\beta)|,$
(8.5)

where the second step follows by the definition (8.1) of $\Lambda$. Now from
(5) above we have $|\hat{\chi}(\xi)|\leqslant\int|\chi|\leqslant 3$ for all
$\xi$, and so

$\sum_{|\xi|\leqslant\rho^{-3}}|\hat{\chi}(\xi)|\leqslant
3(3\rho^{-3})^{D}<2^{-6}\rho^{-4D}$ (8.6)

(here, of course, we have used the fact that $D$ is sufficiently large). By
property (4) of $w$, we have

$\sup_{\|\beta\|_{\mathbf{T}}>\rho^{-2D}X^{-1}}|\hat{w}(\beta)|\leqslant
2^{5}\rho^{4D}X.$ (8.7)

Combining (8.5), (8.6) and (8.7), we see that the total contribution from
$\xi$ in (iii) is at most $X/2$ in magnitude.

Summing the estimates we have obtained under (i), (ii) and (iii), it follows
from (8.4) that the LHS of (8.3) is at least $X+0-X/2=X/2$ and so is indeed
positive, which is what we aimed to prove. ∎

###  9\. The second step – red progressions hit annuli

In this section, we give the proof of Proposition 5.4, conditional upon three
substantial results which we will prove later in the paper. The proofs of
these results may be read independently of one another.

Throughout this section set $X=N^{1/r}$ (as usual) and let $d\leqslant N/X$.
Recall that $\dot{P}$ denotes the progression $\\{nd:n\leqslant X/2\\}$.
Assume through the section that $\theta\in\Theta$ is diophantine in the sense
of Proposition 7.1.

The first substantial result we need is the following proposition, in which we
put a multidimensional structure on $\mathbf{Z}$ suitable for analysing the
metric behaviour of the orbit $\theta\dot{P}=\\{\theta dn:n\leqslant
X/2\\}\subset\mathbf{T}^{D}$. Proposition 9.1 is the main result we will use
in subsequent sections.

In the statement of this result, recall that
$\pi:\mathbf{R}^{D}\rightarrow\mathbf{T}^{D}$ is the natural projection and we
write $\pi^{-1}:\mathbf{T}^{D}\rightarrow\mathbf{R}^{D}$ for the unique
partial inverse map taking values in $(-\frac{1}{2},\frac{1}{2}]^{D}$. In
particular $\|x\|_{\mathbf{T}^{D}}=\|\pi^{-1}x\|_{\infty}$. If
$w_{1},\dots,w_{s}\in\mathbf{R}^{D}$ then we define the _volume_
$\operatorname{vol}(w_{1},\dots,w_{s})$ to be $\sqrt{\det(\langle
w_{i},w_{j}\rangle)_{1\leqslant i,j\leqslant s}}$, that is to say the square
root of the determinant of the Gram matrix associated to the $w_{i}$. For more
properties of this notion, see Section 10.

######  Proposition 9.1.

Suppose that $N\geqslant D^{C_{2}D^{2}}$, let $d\leqslant N/X$, and suppose
that $\theta\in\Theta$ is diophantine. Then there are positive integers
$n_{1},\dots,n_{s}$, $s\leqslant D$, such that if we write $L_{i}:=\|\theta
dn_{i}\|_{\mathbf{T}^{D}}^{-1}$ then

  1. (1)

$\prod_{i=1}^{s}L_{i}\geqslant X^{1/80}$;

  2. (2)

$\sum_{i=1}^{s}n_{i}L_{i}\leqslant X/2$;

  3. (3)

if we set $v_{i}:=\pi^{-1}(\theta dn_{i})\in\mathbf{R}^{D}$ and
$w_{i}:=v_{i}/\|v_{i}\|_{2}$, the unit vector in the direction of $v_{i}$,
then $\operatorname{vol}(w_{1},\dots,w_{s})\geqslant D^{-C_{1}D}$;

  4. (4)

$L_{i}\leqslant X^{C_{1}/D}$ for all $i$.

Note that the $n_{i}$, the $L_{i}$ and $s$ can (and will) depend on $\theta$
and $d$. We will not indicate this dependence later in the section. Various
bounds we state will be uniform in $\theta\in\Theta$ and $d\leqslant N/X$ and
so this dependence is ultimately unimportant.

To prove this result we first develop, in Section 10, some basic properties of
volume. In Section 11 we prove a key technical result stating that the orbit
$\theta\dot{P}$ cannot be too concentrated near (the image in $\mathbf{T}^{D}$
of) the unit ball of a subspace of $\mathbf{R}^{D}$ of dimension
$(1-\varepsilon)D$: here we use the diophantine assumption on $\theta$. In
Section 12 we finally prove Proposition 9.1, first using standard geometry of
numbers techniques (Minkowski’s second theorem) and then refining the
information those give using the estimates of Sections 10 and 11.

The multidimensional structure resulting from Proposition 9.1 gives a new
“basis” relative to which we can try to understand the behaviour of the
(random) quadratic form $\|(1+\sigma(\mathbf{e}))x\|_{2}^{2}$ (which occurs in
the definition of the annuli $A_{\mathbf{e}}$) along the orbit
$\theta\dot{P}$. Unfortunately, a uniformly random $\mathbf{e}$ does not
transfer to a uniformly random quadratic form with respect to this new basis.
However, it turns out that the volume condition (3) above gives some control
of the former in terms of the latter.

The following, the second main ingredient in the proof of Proposition 5.4, is
the technical result we need. Here, we define a map
$\sigma:\mathbf{R}^{n(n+1)/2}\rightarrow\operatorname{Sym}_{n}(\mathbf{R})$ as
in Section 4: to any tuple $\mathbf{x}\in\mathbf{R}^{n(n+1)/2}$, we associate
a symmetric matrix $\sigma(\mathbf{x})\in\operatorname{Sym}_{n}(\mathbf{R})$
as follows: $(\sigma(\mathbf{x}))_{ii}=x_{ii}$,
$(\sigma(\mathbf{x}))_{ij}=\frac{1}{2}x_{ij}$ for $i<j$, and
$(\sigma(\mathbf{x}))_{ij}=\frac{1}{2}x_{ji}$ for $i>j$. We will use this for
$n=D$ and for $n=s$. Which we are talking about should be clear from context,
and the abuse of notation seems preferable to the clutter of further
subscripts.

######  Proposition 9.2.

Let $w_{1},\dots,w_{s}\in\mathbf{R}^{D}$, $s\leqslant D$, be linearly
independent unit vectors. Write
$f:\mathbf{R}^{D(D+1)/2}\rightarrow\mathbf{R}^{s(s+1)/2}$ for the map defined
by

$f(\mathbf{x})=\sigma^{-1}\big{(}(\langle(I+\sigma(\mathbf{x}))w_{i},(I+\sigma(\mathbf{x}))w_{j}\rangle)_{1\leqslant
i,j\leqslant s}\big{)}$

Then for any open set $U\subset\mathbf{R}^{s(s+1)/2}$ we have

$\mathbb{P}_{\mathbf{e}}(f(\mathbf{e})\in U)\leqslant
D^{4D^{2}}\operatorname{vol}(w_{1},\dots,w_{s})^{-D-1}\mu(U),$

where $\mu$ denotes Lebesgue measure.

This is the easiest of our three main ingredients and is a fairly standard
argument in calculus/linear algebra. It is given in Section 13.

The third and final main input to the proof of Proposition 5.4 is the
following result, which says that with overwhelming probability, random
quadratic forms have (very) small gaps in the heart of their range, subject to
a few natural conditions.

######  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_{s})$ 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}\\}$ (9.1)

is $L^{-B}$-dense in $[\frac{1}{2},\frac{3}{2}]$ (that is, intersects that
$L^{-B}$-neighbourhood of every point 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})$.

This is the most substantial of our three main ingredients. A rough outline of
the proof is as follows. First, we establish a kind of preliminary version of
the result with a smaller number $s_{0}=O(B)$ of variables, but with a much
weaker exceptional probability of $O(L^{-B})$ which is insufficient, by
itself, for our application. Indeed, we will be applying Proposition 9.3 for
each of the $N/X=N^{1-1/r}$ values of the common difference $d$ with (roughly)
$L\sim X^{1/D}$, $B\asymp r$. Since $X=N^{1/r}$, an exceptional probability of
$O(L^{-B})$ is then roughly $O(N^{-C/D})$, nowhere near good enough to apply a
union bound over the choices of $d$.

This preliminary variant uses a version of the Hardy-Littlewood circle method
(basically the Davenport-Heilbronn variant of that method) but with a random
quadratic form, which adds some features not usually seen in the method,
although in essence it makes the analysis easier. However, we need some inputs
such as a result on the probability that the determinant of a random matrix is
small (Section 14) for which we do not know references in the literature.

We then use what appears to be a novel kind of amplification trick to prove
Proposition 9.3 itself. The basic idea is to efficiently pack edge-disjoint
copies of the complete graph $K_{s_{0}}$ into $K_{s}$, which encodes a way of
applying the preliminary variant in a large number of independent instances.
To get the best exponents in our main theorems, we need to do this as
efficiently as possible, and to achieve this we use a construction based on
lines in projective space over $\mathbf{F}_{p}$, for a suitable prime $p$.

There is one further complexity, which is that edges of the complete graph
$K_{s}$ only encode _off-diagonal_ coefficients $a_{ij}$, $1\leqslant
i<j\leqslant s$. Whilst the copies of $K_{s_{0}}$ in $K_{s}$ are edge-
disjoint, they are certainly not _vertex_ -disjoint. To ensure that the
applications of the preliminary version really are independent, we need to
build in the capability of holding the diagonal entries $a_{ii}$ fixed while
only selecting the off-diagonal entries at random.

###### Proof of Proposition 5.4.

(assuming Propositions 9.1, 9.2 and 9.3) We start by invoking Proposition 9.1.
The contribution to $\prod_{i=1}^{s}L_{i}$ from those $i$ such that
$L_{i}\leqslant X^{1/160D}$ is at most $X^{1/160}$. Removing these $i$ (which
may involve reducing $s$) we may assume that $X^{1/160D}\leqslant
L_{i}\leqslant X^{C_{1}/D}$ for all $i$. Dividing into $O(\log
C_{1})<C_{1}/160$ ranges we may further assume that that there is some $L$,

$X^{1/2^{8}D}\leqslant L\leqslant X^{C_{1}/D},$ (9.2)

such that $L_{i}\in[L,L^{1+1/48}]$ for all $i$, at the expense of weakening
Proposition 9.1 (1) to

$\prod_{i=1}^{s}L_{i}\geqslant X^{1/C_{1}}.$ (9.3)

The upper bound in (9.2) then implies that

$s\geqslant D/C_{1}^{2}.$ (9.4)

Now recall that our task is to show that, with high probability in
$\mathbf{e}$, for all $y\in\pi(B_{\rho/10}(0))$ the orbit $y+\theta\dot{P}$
contains a point in $\pi(A_{\mathbf{e}})$, where

$A_{\mathbf{e}}:=\\{x\in\mathbf{R}^{D}:\rho-N^{-4/D}<\|(1+\sigma(\mathbf{e}))x\|_{2}\leqslant\rho\\}.$

Let $z:=\pi^{-1}(y)\in\mathbf{R}^{D}$, thus

$\|z\|_{2}\leqslant\rho/10.$ (9.5)

Recall that $v_{i}:=\pi^{-1}(\theta dn_{i})$. Thus, by Proposition 9.1, any
element of the form $\pi(\sum_{i}\ell_{i}v_{i})$, $\ell_{i}<L_{i}$, lies in
$\theta\dot{P}$ (since
$\pi(\sum_{i}\ell_{i}v_{i})=(\sum_{i}\ell_{i}n_{i})d\theta$). Thus it suffices
to show that with probability $1-O(N^{-3})$ in the random choice of
$\mathbf{e}$, any set of the form

$\\{z+\sum_{i}\ell_{i}v_{i}:\ell_{i}\in\mathbf{N},0\leqslant\ell_{i}<L_{i}\\},\quad\|z\|_{2}<\rho/10,$

has nontrivial intersection with $A_{\mathbf{e}}$, that is to say that there
is some choice of the $\ell_{i}$ such that

$\rho-N^{-4/D}<\|(I+\sigma(\mathbf{e}))(z+\sum_{i}\ell_{i}v_{i})\|_{2}<\rho.$
(9.6)

In other words it is enough that

$1-N^{-4/D}\leqslant
q_{a(\mathbf{e}),b(\mathbf{e}),c(\mathbf{e})}(\frac{\ell_{1}}{L_{1}},\dots,\frac{\ell_{s}}{L_{s}})\leqslant
1,$ (9.7)

where the quadratic form is given by

$q_{a(\mathbf{e}),b(\mathbf{e}),c(\mathbf{e})}(\frac{\ell_{1}}{L_{1}},\dots,\frac{\ell_{s}}{L_{s}}):=\rho^{-2}\|(I+\sigma(\mathbf{e}))(z+\sum_{i=1}^{s}\ell_{i}v_{i})\|_{2}^{2}.$
(9.8)

One computes

$c(\mathbf{e}):=\rho^{-2}\|(I+\sigma(\mathbf{e}))z\|_{2}^{2},\qquad
b_{i}(\mathbf{e}):=2\rho^{-2}\langle(I+\sigma(\mathbf{e}))z,(I+\sigma(\mathbf{e}))v_{i}\rangle
L_{i},$
$a_{ij}(\mathbf{e}):=2\rho^{-2}\langle(I+\sigma(\mathbf{e}))v_{i},(I+\sigma(\mathbf{e}))v_{j}\rangle
L_{i}L_{j},$
$a_{ii}(\mathbf{e}):=\rho^{-2}\|(I+\sigma(\mathbf{e}))v_{i}\|_{2}^{2}L_{i}^{2}.$

Set $Q:=D^{10}$. We claim that the conditions $a_{ii}(\mathbf{e})\geqslant
32$, $|a_{ij}(\mathbf{e})|$, $|b_{i}(\mathbf{e})|\leqslant Q$,
$|c(\mathbf{e})|\leqslant\frac{1}{4}$ and
$b_{i}(\mathbf{e})^{2}-4a_{ii}(\mathbf{e})c(\mathbf{e})<0$ of Proposition 9.3
are automatically satisfied.

To prove these, recall (4.4) that

$\frac{1}{2}\leqslant\|I+\sigma(\mathbf{e})\|\leqslant 2,$ (9.9)

and observe the bounds

$\frac{1}{L_{i}}=\|\theta
dn_{i}\|_{\mathbf{T}^{D}}=\|v_{i}\|_{\infty}\leqslant\|v_{i}\|_{2}\leqslant
D^{1/2}\|v_{i}\|_{\infty}=\frac{D^{1/2}}{L_{i}}.$ (9.10)

Using (9.9), (9.10) and recalling that $\rho=D^{-4}$ with $D$ large, we have
the following. First,

$a_{ii}(\mathbf{e})\geqslant\frac{1}{4}\rho^{-2}\|v_{i}\|_{2}^{2}L_{i}^{2}>32;$

Second, by Cauchy-Schwarz

$|a_{ij}(\mathbf{e})|\leqslant
2\rho^{-2}\|I+\sigma(\mathbf{e})\|^{2}\|v_{i}\|_{2}\|v_{j}\|_{2}L_{i}L_{j}\leqslant\frac{8D}{\rho^{2}}<Q;$

Third,

$|b_{i}(\mathbf{e})|\leqslant
2\rho^{-2}\|I+\sigma(\mathbf{e})\|^{2}\|z\|_{2}\|v_{i}\|_{2}L_{i}<Q;$

Fourth, since $\|z\|_{2}\leqslant\rho/10$, and by (9.9), we have

$c(\mathbf{e})\leqslant\rho^{-2}\|I+\sigma(\mathbf{e})\|^{2}\|z\|^{2}_{2}<\frac{1}{4}.$

Finally, the discriminant condition
$b_{i}(\mathbf{e})^{2}-4a_{ii}(\mathbf{e})c(\mathbf{e})<0$ is automatic from
the positive-definiteness of the quadratic form (and is also immediate using
Cauchy-Schwarz from the formulae above).

With all the relevant conditions having been verified, we are in a position to
apply Proposition 9.3 with $Q=D^{10}$, with $L$ as selected above (satisfying
(9.2)), $s\geqslant D/C_{1}^{2}$ by (9.4) and the lengths
$L_{1},\dots,L_{s}\in[L,L^{1+1/48}]$ as given above, and with
$B:=2^{15}C_{1}^{2}r$. We must first check that the application is valid by
confirming that $L\geqslant(QB)^{C_{2}B}$ and that $s\geqslant C_{1}B^{2}$.
Using the assumption that $N>D^{D^{2}}$ and recalling that $D=C_{3}r^{2}$, one
may check using (9.2) and (9.4) that this is indeed the case, if $C_{3}$ is
big enough.

Thus all of the conditions are satisfied. Now observe that with the choice of
$B$ we have made (and in view of the lower bound in (9.2), and recalling that
$X=N^{1/r}$) the fact that $B\geqslant 2^{10}r$ then implies that

$L^{-B}\leqslant N^{-4/D},$ (9.11)

the importance of the right-hand side here being that this is the width of our
ellipsoidal annuli.

Proposition 9.3 therefore tells us that indeed
$q_{a(\mathbf{e}),b(\mathbf{e}),c(\mathbf{e})}(\frac{\ell_{1}}{L_{1}},\dots,\frac{\ell_{s}}{L_{s}})$
takes values in $[1-N^{-4/D},1]$ (that is, (9.7), and hence (9.6) hold)
provided that $a(\mathbf{e}):=(a_{ij}(\mathbf{e}))_{1\leqslant i\leqslant
j\leqslant s}\in\Sigma$, where $\Sigma$ is the event appearing in Proposition
9.3. To complete the proof of Proposition 5.4, it therefore suffices to show
that

$\mathbb{P}_{\mathbf{e}}(a(\mathbf{e})\in\neg\Sigma)\ll N^{-3}.$ (9.12)

Now, using the fact that $X=N^{1/r}$ together with (9.2) and (9.4), we see
that if $a$ is chosen randomly as in Proposition 9.3 (that is, uniformly from
$[-Q,Q]^{s(s+1)/2}$ with diagonal terms $\geqslant 32$) then, from the
conclusion of Proposition 9.3, we have

$\mathbb{P}_{a}(a\in\neg\Sigma)\ll L^{-sB/16}\leqslant
N^{-\frac{2^{-8}}{D}\cdot\frac{1}{16}\cdot\frac{D}{C_{1}^{2}}\cdot
B\cdot\frac{1}{r}}=N^{-8}.$ (9.13)

Now, as $\mathbf{e}$ varies uniformly, $a(\mathbf{e})$ may not be close to a
uniformly random element of $[-Q,Q]^{s(s+1)/2}$, so (9.12) and (9.13) are not
trivially comparable. To link the two statements we invoke Proposition 9.2,
taking the $w_{i}$ to be the normalised $v_{i}$’s, as in the conclusion of
Proposition 9.1. Observe that $a(\mathbf{e})=\psi(f(\mathbf{e}))$, where $f$
is the map in Proposition 9.2 and
$\psi:\mathbf{R}^{s(s+1)/2}\rightarrow\mathbf{R}^{s(s+1)/2}$ is the diagonal
linear map

$(\psi(\mathbf{x}))_{ij}=\rho^{-2}\|v_{i}\|_{2}\|v_{j}\|_{2}L_{i}L_{j}x_{ij}.$

Recall that $\|v_{i}\|_{\infty}=L_{i}^{-1}$, so the determinant of $\psi$ is
at least $1$ (in fact, much bigger).

Therefore we have, by Proposition 9.2 and Lemma 9.1 (3),

$\displaystyle\mathbb{P}_{\mathbf{e}}(a(\mathbf{e})\in\neg\Sigma)$
$\displaystyle=\mathbb{P}_{\mathbf{e}}(f(\mathbf{e})\in\psi^{-1}(\neg\Sigma))$
$\displaystyle\leqslant
D^{4D^{2}}\operatorname{vol}(w_{1},\dots,w_{s})^{-D-1}\mu(\psi^{-1}(\neg\Sigma))$
$\displaystyle\leqslant D^{4D^{2}}\cdot
D^{C_{1}D(D+1)}\cdot\mu(\psi^{-1}(\neg\Sigma))$ $\displaystyle\leqslant
D^{4D^{2}}\cdot
D^{C_{1}D(D+1)}\cdot(2Q)^{s(s+1)/2}\cdot\mathbb{P}_{a}(a\in\neg\Sigma),$

In the last step we used the fact that the determinant of $\psi^{-1}$ is at
most $1$. Recalling (9.13), the fact that $Q=D^{10}$ and that $s\leqslant D$,
we see that this is $<N^{-3}$ provided that $N\geqslant D^{C_{2}D^{2}}$, if
$C_{2}$ is chosen sufficiently large. This concludes the proof of Proposition
5.4.

∎

##  Part IV Multidimensional structure and geometry of numbers

###  10\. Preliminaries on volume

In this section we recall some basic concepts related to volume. Given
$w_{1},\dots,w_{m}\in\mathbf{R}^{n}$ (which in our application will always be
unit vectors), define

$\operatorname{vol}(w_{1},\dots,w_{m}):=\sqrt{\det G(w_{1},\dots,w_{m})},$

where the _Gram matrix_ $G=G(w_{1},\dots,w_{m})$ has $(i,j)$-entry $\langle
w_{i},w_{j}\rangle$. Note that $\langle Gx,x\rangle=\|\sum
x_{i}w_{i}\|_{2}^{2}$, so $G$ is positive semi-definite and hence $\det
G\geqslant 0$; therefore the square root is well-defined. $G$ is nonsingular
if and only if $G$ is positive definite, if and only if the $w_{i}$ are
linearly independent.

As the notation suggests, $\operatorname{vol}(w_{1},\dots,w_{m})$ should be
interpreted as the $m$-dimensional volume of the parallelepiped spanned by
$w_{1},\dots,w_{m}$, and indeed it satisfies the intuitive properties one
would expect of such a notion. The one we will need is the following (“volume
= base times height”), and we include the proof since this is not completely
obvious and hard to find a concise reference for.

######  Lemma 10.1.

Let $w_{1},\dots,w_{m}\in\mathbf{R}^{n}$. Then

$\operatorname{vol}(w_{1},\dots,w_{m})=\operatorname{dist}(w_{m},\operatorname{Span}_{\mathbf{R}}(w_{1},\dots,w_{m-1}))\operatorname{vol}(w_{1},\dots,w_{m-1}),$

where the distance is in $\ell^{2}$.

###### Proof.

If $w_{1},\dots,w_{m-1}$ are linearly dependent then this is clear, so suppose
they are not. Let the foot of the perpendicular from $w_{m}$ to
$\operatorname{Span}_{\mathbf{R}}(w_{1},\dots,w_{m-1})$ be
$x_{1}w_{1}+\dots+x_{m-1}w_{m-1}$. Then the fact that
$v=w_{m}-x_{1}w_{1}-\dots-x_{m-1}w_{m-1}$ is orthogonal to
$w_{1},\dots,w_{m-1}$ gives us $m-1$ linear relations

$\langle w_{1},w_{i}\rangle x_{1}+\cdots+\langle w_{m-1},w_{i}\rangle
x_{m-1}=\langle w_{m},w_{i}\rangle,$ (10.1)

$i=1,\dots,m-1$. Writing $y:=\|v\|_{2}^{2}$ for the length of the
perpendicular, Pythagoras’s theorem gives

$\langle w_{1},w_{m}\rangle x_{1}+\dots+\langle w_{m-1},w_{m}\rangle
x_{m-1}+y=\langle w_{m},w_{m}\rangle.$ (10.2)

Combining (10.1) and (10.2) into an $m\times m$ system of equations in the
variables $x_{1},\dots,x_{m-1},y$, it follows from Cramer’s rule that
$y=\frac{G(w_{1},\dots,w_{m})}{G(w_{1},\dots,w_{m-1})}$, which is equivalent
to the stated result. ∎

Two immediate consequences of this are the following.

######  Corollary 10.2.

Suppose that $w_{1},\dots,w_{m}$ are unit vectors in $\mathbf{R}^{n}$. Then

$\operatorname{vol}(w_{1},\dots,w_{m})\leqslant\operatorname{vol}(w_{1},\dots,w_{m-1})\leqslant\dots\leqslant
1.$

######  Corollary 10.3.

Suppose that $w_{1},\dots,w_{m}\in\mathbf{R}^{n}$ are unit vectors, where
$m<n$. Then we may complete this list of vectors list to $w_{1},\dots,w_{n}$
with
$\operatorname{vol}(w_{1},\dots,w_{n})=\operatorname{vol}(w_{1},\dots,w_{m})$.

###### Proof.

Choose $w_{m+1},\dots,w_{n}$ to be orthogonal to one another and to
$w_{1},\dots,w_{m}$. ∎

The other consequence of Lemma 10.1 that we will require is the following
dichotomy, for which I do not know a reference.

######  Lemma 10.4.

Let $w_{1},\dots w_{m}\in\mathbf{R}^{n}$ be unit vectors, and let $k\leqslant
m$. Then, after reordering the $w_{i}$, at least one of the following
statements is true:

  1. (1)

$\operatorname{vol}(w_{1},\dots,w_{k+1})\geqslant\delta$;

  2. (2)

If $V=\operatorname{Span}(w_{1},\dots,w_{k})$ then
$\operatorname{dist}(w_{i},V)\leqslant\delta^{1/k}$ for all
$i\in\\{1,\dots,m\\}$.

###### Proof.

We perform the following algorithm for as long as possible. Start, at stage 1,
with $w_{1}$. At the $i$th stage, we will have (after reordering)
$w_{1},\dots,w_{i}$. If

$\operatorname{dist}(w_{j},\operatorname{Span}(w_{1},\dots,w_{i}))\leqslant\delta^{1/k}$

for all $j\in\\{1,\dots,m\\}$ then stop. If this happens for some $i\leqslant
k$ then we have (2). Otherwise, we may reorder $w_{i+1},\dots,w_{m}$ so that
$\operatorname{dist}(w_{i+1},\operatorname{Span}(w_{1},\dots,w_{i}))>\delta^{1/k}$.
By Lemma 10.1 (and a simple induction) we have
$\operatorname{vol}(w_{1},\dots,w_{i+1})>\delta^{i/k}$. If this continues as
far as $i=k$ then we have (1). ∎

###  11\. Non-concentration on subspaces

In this section we establish a key technical result, Lemma 11.1 below, which
says that orbits $\\{\theta dn:n\leqslant X\\}$ with $\theta$ diophantine
cannot concentrate too much near low-dimensional subspaces (or, more
accurately, the image under $\pi:\mathbf{R}^{D}\rightarrow\mathbf{T}^{D}$ of
small balls in such subspaces). Here, we use $\mathcal{N}_{\delta}(U)$ to
denote the $\delta$-neighbourhood (in the Euclidean metric) of a set
$U\subset\mathbf{R}^{D}$, and as usual $B_{\delta}(0)$ denotes the Euclidean
ball about $0\in\mathbf{R}^{D}$. Write $\theta d[X]=\\{\theta dn:n\leqslant
X\\}$ for short.

######  Lemma 11.1.

Let $r$ be sufficiently large, suppose that $D=C_{3}r^{2}$, and assume that
$N\geqslant D^{C_{2}D^{2}}$. Let $\varepsilon\in(\frac{1}{r},1)$. Let
$\theta\in\mathbf{T}^{D}$ be diophantine, let $d\leqslant N/X$, and let
$V\leqslant\mathbf{R}^{D}$ be a subspace of dimension at most
$D(1-\varepsilon)$. Then for all $d\leqslant N/X$ we have

$\\#\\{\theta d[X]\cap\pi(\mathcal{N}_{D^{-C_{1}}}(V)\cap
B_{1/10}(0))\\}\leqslant 2D^{(1-\varepsilon C_{1}/2)D}X.$ (11.1)

###### Proof.

We may assume, by adding elements if necessary, that $\dim
V=\lfloor(1-\varepsilon)D\rfloor$. Set $m:=\lceil\varepsilon D\rceil$,
$\delta:=D^{-C_{1}}$ and $S:=\mathcal{N}_{D^{-C_{1}}}(V)\cap B_{1/10}(0)$. Let
$(v_{i})_{i=1}^{D}$ be an orthonormal basis for $\mathbf{R}^{D}$ with
$V=\operatorname{Span}_{\mathbf{R}}(v_{m+1},\dots,v_{D})$. Let
$\psi:\mathbf{R}\rightarrow\mathbf{R}$ be a smooth cutoff satisfying the
following conditions:

  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$.

For the proof that such a function exists, see Lemma B.4. Now define
$\chi:\mathbf{R}^{D}\rightarrow[0,\infty)$ by

$\chi(x)=\prod_{i=1}^{D}\psi(\delta^{-1_{i\leqslant m}}\langle
x,v_{i}\rangle),$ (11.2)

where the notation means that the scale factor $\delta^{-1}$ is included only
for $i\leqslant m$ (that is, in the directions orthogonal to $V$), and is
otherwise set equal to 1. If $x\in\mathcal{N}_{\delta}(V)$ and $i\leqslant m$
then

$|\langle x,v_{i}\rangle|\leqslant\big{(}\sum_{i=1}^{m}|\langle
x,v_{i}\rangle|^{2}\big{)}^{1/2}=\operatorname{dist}(x,V)\leqslant\delta,$

and if $x\in B_{1/10}(0)$ then $|\langle x,v_{i}\rangle|<1$ for all $i$. It
follows from these observations and property (1) of $\psi$ that
$\chi(x)\geqslant 1$ for $x\in S$, and therefore

$\\#\big{(}\theta d[X]\cap\pi(S)\big{)}\leqslant\sum_{n\leqslant
X}\sum_{\lambda\in\mathbf{Z}^{D}}\chi(\theta dn+\lambda).$ (11.3)

The Poisson summation formula tells us that for any $t\in\mathbf{T}^{D}$ we
have

$\sum_{\lambda\in\mathbf{Z}^{D}}\chi(\lambda+t)=\sum_{\xi\in\mathbf{Z}^{D}}\hat{\chi}(\xi)e(\xi\cdot
t).$

Substituting into (11.3) therefore implies that

$\\#\big{(}\theta
d[X]\cap\pi(S)\big{)}\leqslant\sum_{\xi\in\mathbf{Z}^{D}}\hat{\chi}(\xi)\sum_{n\leqslant
X}e(\xi\cdot\theta dn).$ (11.4)

To proceed further, we need to understand the Fourier transform $\hat{\chi}$,
particularly at points of $\mathbf{Z}^{D}$. First, it follows from property
(3) of $\psi$ above that

$\|\hat{\chi}\|_{\infty}\leqslant\int\chi=\delta^{m}(\int\psi)^{D}\leqslant
5^{D}\delta^{m}.$ (11.5)

Next, expanding in the orthonormal basis $(v_{j})_{j=1}^{D}$ then changing
variables we have

$\displaystyle\hat{\chi}(\gamma)$
$\displaystyle=\int_{\mathbf{R}^{D}}\prod_{j=1}^{D}\psi(\delta^{-1_{j\leqslant
m}}\langle x,v_{j}\rangle)e(-\langle
x,v_{j}\rangle\langle\gamma,v_{j}\rangle)dx$
$\displaystyle=\int_{\mathbf{R}^{D}}\prod_{j=1}^{D}\psi(\delta^{-1_{j\leqslant
m}}t_{j})e(-t_{j}\langle\gamma,v_{j}\rangle)dt$
$\displaystyle=\delta^{m}\prod_{j=1}^{D}\hat{\psi}(\delta^{1_{j\leqslant
m}}\langle\gamma,v_{j}\rangle).$

Therefore from property (2) of $\psi$ we see that

$\operatorname{Supp}(\hat{\chi})\subset
B:=\\{\gamma\in\mathbf{R}^{D}:|\langle\gamma,v_{j}\rangle|\leqslant\delta^{-1_{j\leqslant
m}}\;\mbox{for all $j$}\\}.$ (11.6)

First note that this implies (rather crudely) that if $\hat{\chi}(\xi)\neq 0$
for some $\xi\in\mathbf{Z}^{D}$ then

$|\xi|^{2}<\|\xi\|_{2}^{2}=\sum_{i}|\langle\xi,v_{i}\rangle|^{2}\leqslant\frac{D}{\delta^{2}}<(\frac{D}{\delta})^{2}.$
(11.7)

Second, to analyse (11.4) we need a bound on
$\\#(\operatorname{Supp}(\hat{\chi})\cap\mathbf{Z}^{D})$. To get such a bound,
note that if $\gamma\in\operatorname{Supp}(\chi)$ and if $u\in[0,1]^{D}$ then
by (11.6) (and since $D$ is big)

$|\langle\gamma+u,v_{j}\rangle|\leqslant\delta^{-1_{j\leqslant m}}+|\langle
u,v_{j}\rangle|\leqslant\frac{D}{10}\delta^{-1_{j\leqslant m}}$

for all $j$. Therefore the disjoint union of cubes
$(\operatorname{Supp}(\hat{\chi})\cap\mathbf{Z}^{D})+[0,1)^{D}$ is contained
in the cuboid

$\\{x\in\mathbf{R}^{D}:|\langle
x,v_{j}\rangle|\leqslant\frac{D}{10}\delta^{-1_{j\leqslant m}}\;\mbox{for all
$j$}\\},$

which has volume $(D/5)^{D}\delta^{-m}$. It follows that
$\\#(\operatorname{Supp}(\chi)\cap\mathbf{Z}^{D})\leqslant(D/5)^{D}\delta^{-m}$,
and so by (11.5)

$\sum_{\xi\in\mathbf{Z}^{D}}|\hat{\chi}(\xi)|\leqslant D^{D}.$ (11.8)

Let us return to the main task of estimating the right-hand side of (11.4).
Summing the geometric series on the right of (11.4), we have

$\\#\big{(}\theta
d[X]\cap\pi(S)\big{)}\leqslant\sum_{\xi\in\mathbf{Z}^{D}}|\hat{\chi}(\xi)|\min(X,\|\xi\cdot\theta
d\|_{\mathbf{T}}^{-1}).$ (11.9)

Now by (11.8), the contribution from $\xi$ with $\|\xi\cdot\theta
d\|_{\mathbf{T}}>D^{D}\delta^{-m}X^{-1}$ is at most $\delta^{m}X\leqslant
D^{-\varepsilon C_{1}D}X$. It therefore follows from (11.5), (11.7) and (11.9)
that

$\\#\big{(}\theta d[X]\cap\pi(S)\big{)}\leqslant
5^{D}\delta^{m}X\\#\Omega+D^{-\varepsilon C_{1}D}X.$ (11.10)

where

$\Omega:=\\{\xi\in\mathbf{Z}^{D}:|\xi|<D/\delta,\|\xi\cdot\theta
d\|_{\mathbf{T}}\leqslant D^{D}\delta^{-m}X^{-1}\\}.$ (11.11)

Now since $\theta$ is diophantine, it follows from Proposition 7.1 (1) (the
definition of diophantine) that $\dim\Omega<4r$, assuming that $C_{2}\geqslant
C_{1}+1$.

It follows from Lemma A.3 that

$\\#\Omega\leqslant 20^{D}(4r)^{D/2}(D/\delta)^{4r}.$ (11.12)

To conclude the proof, we combine (11.10) and (11.12) and bound the resulting
terms crudely. Since $D=C_{3}r^{2}$ and $r$ is large, crude bounds for the
terms in (11.12) show that

$\\#\big{(}\theta d[X]\cap\pi(S)\big{)}\leqslant
D^{D}\delta^{m-4r}X+D^{-\varepsilon C_{1}D}X.$

Using the assumption that $m\geqslant 8r$, the first term is bounded above by
$D^{D}\delta^{m/2}X\leqslant D^{1-C_{1}\varepsilon D/2}X$. The proposition
follows.∎

###  12\. Geometry of numbers

Set $X:=N^{1/r}$ as usual, with $r$ sufficiently large. Let $d\leqslant N/X$;
for the rest of the section we regard $d$ as fixed and do not explicitly
indicate the dependence of various objects (lengths $L_{i},L^{\prime}_{i}$,
vectors $v_{i},w_{i}$ and so on) on $d$. Our aim in this section is to prove
Proposition 9.1, whose statement was as follows.

######  Proposition 9.1.

Suppose that $N\geqslant D^{C_{2}D^{2}}$, let $d\leqslant N/X$, and suppose
that $\theta\in\Theta$ is diophantine. Then there are positive integers
$n_{1},\dots,n_{s}$, $s\leqslant D$, such that if we write $L_{i}:=\|\theta
dn_{i}\|_{\mathbf{T}^{D}}^{-1}$ then

  1. (1)

$\prod_{i=1}^{s}L_{i}\geqslant X^{1/80}$;

  2. (2)

$\sum_{i=1}^{s}n_{i}L_{i}\leqslant X/2$;

  3. (3)

if we set $v_{i}:=\pi^{-1}(\theta dn_{i})\in\mathbf{R}^{D}$ and
$w_{i}:=v_{i}/\|v_{i}\|_{2}$, the unit vector in the direction of $v_{i}$,
then $\operatorname{vol}(w_{1},\dots,w_{s})\geqslant D^{-C_{1}D}$;

  4. (4)

$L_{i}\leqslant X^{C_{1}/D}$ for all $i$.

Just to reiterate: $s$, the $v_{i}$, the $n_{i}$ and the $L_{i}$ will all
depend on $d$, as well as on $\theta$ which should be thought of as fixed.

The proof of Proposition 9.1 is somewhat lengthy. We begin by establishing a
preliminary statement, Lemma 12.1, featuring related (but weaker) statements,
but which does not require any diophantine assumption on $\theta$. This
statement is essentially the principle, well-known in additive combinatorics,
that “Bohr sets contain large generalised progressions”. Usually in the
literature this is given for Bohr sets in $\mathbf{Z}/p\mathbf{Z}$, whereas we
require it in $\mathbf{Z}$, which requires a minor tweak to the proof and
causes the dimension of the resulting progressions to be greater by one than
in the cyclic group case.

######  Lemma 12.1.

There are positive integers $n_{1},\dots,n_{D+1}$ and also lengths
$L^{\prime}_{1},\dots,L^{\prime}_{D+1}$ such that the following hold:

  1. (1)

The elements $\sum_{i=1}^{D+1}\ell_{i}n_{i}$, $\ell_{i}\in\mathbf{Z}$,
$0\leqslant\ell_{i}<L^{\prime}_{i}$, are all distinct and at most $D^{-D}X$;

  2. (2)

$\|\theta dn_{i}\|_{\mathbf{T}^{D}}\leqslant 1/L^{\prime}_{i}$ for all $i$;

  3. (3)

$\prod_{i=1}^{D+1}L^{\prime}_{i}\geqslant D^{-3D}X$.

_Remark._ Write $\alpha:=\theta d$ throughout the proof. The $n_{i}$ appearing
in Proposition 9.1 will be a subset of the ones appearing here, but the
lengths $L_{i}$ appearing there will be modified versions of the
$L^{\prime}_{i}$. That is why we have put dashes on these lengths.

###### Proof.

In $\mathbf{R}\times\mathbf{R}^{D}$, consider the lattice

$\Lambda=\mathbf{Z}(\frac{1}{X},\alpha_{1},\dots,\alpha_{D})\oplus(\\{0\\}\times\mathbf{Z}^{D})$

and the centrally-symmetric convex body

$K:=[-D^{-D},D^{-D}]\times[-\frac{1}{2},\frac{1}{2}]^{D}.$

We have $\operatorname{vol}(K)=2D^{-D}$ and $\det(\Lambda)=\frac{1}{X}$, so
Minkowski’s second theorem tells us that the successive minima
$\lambda_{1},\dots,\lambda_{D+1}$ for $K$ with respect to $\Lambda$ satisfy

$\lambda_{1}\cdots\lambda_{D+1}\leqslant\frac{2^{D+1}\det(\Lambda)}{\operatorname{vol}(K)}=(2D)^{D}\frac{1}{X}.$
(12.1)

Consider a directional basis $\mathbf{b}_{1},\dots,\mathbf{b}_{D+1}$ for
$\Lambda$ with respect to $K$. Thus $\mathbf{b}_{i}\in\Lambda$, the
$\mathbf{b}_{i}$ are linearly independent and $\mathbf{b}_{i}\in\lambda_{i}K$
(but the $\mathbf{b}_{i}$ need not be an integral basis for $\Lambda$). Write

$\mathbf{b}_{i}=(\frac{n_{i}}{X},n_{i}\alpha-m_{i}),$

where $n_{i}\in\mathbf{Z}$ and $m_{i}\in\mathbf{Z}^{D}$. Replacing
$\mathbf{b}_{i}$ by $-\mathbf{b}_{i}$ if necessary, we may assume that
$n_{i}\geqslant 0$. We take these $n_{i}$s to be the ones in Lemma 12.1. Set

$L^{\prime}_{i}:=\frac{1}{(D+1)\lambda_{i}}.$

We now verify statements (1), (2) and (3) in the lemma. Item (3) is a
straightforward consequence of the definition of the $L^{\prime}_{i}$ and
(12.1):

$\prod_{i=1}^{D+1}L^{\prime}_{i}=(D+1)^{-D-1}\big{(}\prod_{i=1}^{D+1}\lambda_{i}\big{)}^{-1}\geqslant(D+1)^{-D-1}(2D)^{-D}X>D^{-3D}X.$

Item (2) follows from the fact that $\mathbf{b}_{i}\in\lambda_{i}K$; looking
at the last $D$ coordinates, one sees that this means that
$\|n_{i}\alpha\|_{\mathbf{T}^{D}}\leqslant\lambda_{i}/2<1/L^{\prime}_{i}$.
Finally we turn to (1). We have

$\ell_{1}\mathbf{b}_{1}+\dots+\ell_{D+1}\mathbf{b}_{D+1}=\big{(}\frac{1}{X}\sum_{i=1}^{D+1}\ell_{i}n_{i},\sum_{i=1}^{D+1}\ell_{i}(n_{i}\alpha-
m_{i})\big{)}.$ (12.2)

Since $\mathbf{b}_{i}\in\lambda_{i}K$, comparing first coordinates we see that
if $0\leqslant\ell_{i}<L^{\prime}_{i}$ then

$0\leqslant\frac{1}{X}\sum_{i=1}^{D+1}\ell_{i}n_{i}\leqslant
D^{-D}\sum_{i=1}^{D+1}\ell_{i}\lambda_{i}\leqslant D^{-D}.$

This is one part of statement (1). For the statement about distinctness,
suppose that
$\sum_{i=1}^{D+1}\ell_{i}n_{i}=\sum_{i=1}^{D+1}\ell^{\prime}_{i}n_{i}$ with
$0\leqslant\ell_{i},\ell^{\prime}_{i}<L^{\prime}_{i}$. Then
$\sum_{i=1}^{D+1}(\ell_{i}-\ell^{\prime}_{i})\mathbf{b}_{i}\in\\{0\\}\times\mathbf{Z}^{D}$
(by (12.2) and its analogue for the $\ell^{\prime}_{i}$). However,

$\|\sum_{i=1}^{D+1}(\ell_{i}-\ell^{\prime}_{i})\mathbf{b}_{i}\|_{\infty}\leqslant\sum_{i=1}^{D+1}L^{\prime}_{i}\lambda_{i}\cdot\frac{1}{2}<1.$

It follows that $\sum_{i=1}^{D+1}(\ell_{i}-\ell^{\prime}_{i})\mathbf{b}_{i}=0$
and hence, since the $\mathbf{b}_{i}$ are linearly independent, that
$\ell_{i}=\ell^{\prime}_{i}$ for all $i$. ∎

From now on we work with the $n_{i}$ generated in Lemma 12.1, and set
$L_{i}:=\|\theta dn_{i}\|^{-1}_{\mathbf{T}^{D}}$ (which agrees with the
statement of Proposition 9.1). Let us remind the reader that we are thinking
of $d$ as fixed; the $L_{i}$ of course depend on $d$. By Lemma 12.1 (2) we
have

$L^{\prime}_{i}\leqslant L_{i}.$ (12.3)

Before turning to the proof of Proposition 9.1 itself, we use Proposition 7.1
(2) (that is, the second condition in the definition of $\theta$ being
diophantine) to get some rough control on the lengths $L_{i}$. The following
lemma, though sufficient for our needs, is rather weak, asserting that it is
not possible for almost all of the product $\prod L_{i}$ to be concentrated on
a few values of $i$.

######  Lemma 12.2.

Suppose that $D=C_{3}r^{2}$ and that $N\geqslant D^{D^{2}}$. Suppose that
$I\subset[D+1]$ and that $|I|\leqslant 2^{-7}D$. Then $\prod_{i\notin
I}L_{i}\geqslant X^{1/80}$.

###### Proof.

Suppose that this is not the case for some index set $I$. Then certainly (by
(12.3)) $\prod_{i\notin I}L^{\prime}_{i}<X^{1/80}$, and so by Lemma 12.1 (3)
we have

$\prod_{i\in I}L^{\prime}_{i}\geqslant D^{-3D}X^{1-1/80}>X^{1-1/40}.$

Now look at all sums $\sum_{i\in I}\ell_{i}n_{i}$ with
$0\leqslant\ell_{i}\leqslant\frac{1}{2D}X^{-1/D}L^{\prime}_{i}$. By Lemma 12.1
(1) and (2), these sums are all distinct, and for each one

$\|\theta d\sum_{i\in I}\ell_{i}n_{i}\|_{\mathbf{T}^{D}}\leqslant\sum_{i\in
I}\ell_{i}\|\theta dn_{i}\|_{\mathbf{T}^{D}}\leqslant X^{-1/D}.$

However, Proposition 7.1 (2) tells us that

$\\#\\{n\leqslant X:\|\theta dn\|_{\mathbf{T}^{D}}\leqslant
X^{-1/D}\\}\leqslant X^{9/10}.$

It follows that

$\big{(}\frac{X^{-1/D}}{2D}\big{)}^{2^{-7}D}X^{1-1/40}\leqslant\prod_{i\in
I}(\frac{X^{-1/D}}{2D}L^{\prime}_{i})\leqslant X^{9/10},$

which is a contradiction. ∎

Now we turn to the proof of Proposition 9.1 itself.

###### Proof of Proposition 9.1.

The idea is to take the $n_{i}$ output by Lemma 12.1, but discard indices $i$
which cause items (2), (3) and (4) of Proposition 9.1 to be violated, whilst
ensuring that the lower bound (1) is maintained. When we say that (2), (3) or
(4) holds for indices in a set $I$, this has the obvious meaning (namely, for
(2) we mean that $\sum_{i\in I}n_{i}L_{i}\leqslant X/2$, and for (3) that
$\operatorname{vol}((w_{i})_{i\in I})\geqslant D^{-C_{1}D}$). Note that
properties (2), (3) and (4) are all hereditary, that is to say if they hold
for indices in $I$ then they also hold for indices in $I^{\prime}$, for any
subset $I^{\prime}\subset I$. For (2) and (4) this is obvious; for (3), it
follows from Corollary 10.2.

This, together with Lemma 12.2, allows us to treat (2), (3) and (4) of
Proposition 9.1 essentially separately. We will show, for each
$n\in\\{2,3,4\\}$, that there is a set $I_{(n)}\subset[D+1]$ of indices,

$|I^{c}_{(2)}|,|I^{c}_{(3)}|\leqslant 2^{-9}D,\;\;|I^{c}_{(4)}|\leqslant
2^{-8}D,$ (12.4)

such that item $(n)$ of Proposition 9.1 holds on $I_{(n)}$. If we then set
$I:=I_{(2)}\cap I_{(3)}\cap I_{(4)}$ then properties (2) , (3) and (4) all
hold on $I$, and by Lemma 12.2 we have the lower bound $\prod_{i\in
I}L_{i}\geqslant X^{1/80}$. Relabelling so that $I=\\{1,\dots,s\\}$,
Proposition 9.1 then follows.

The arguments for properties (2) and (3) share some common features, which we
introduce now. Consider the set

$B=\\{\sum_{i=1}^{D+1}\ell_{i}n_{i}:0\leqslant\ell_{i}\leqslant\frac{L^{\prime}_{i}}{20D^{2}}\\}.$
(12.5)

All the elements in this presentation of $B$ are distinct by Lemma 12.1 (1),
so (rather crudely)

$|B|\geqslant D^{-6D}X$ (12.6)

by Lemma 12.1 (3) and the fact that $D$ is large. Recall that
$v_{i}=\pi^{-1}(\theta dn_{i})$ (that is, the unique smallest lift under the
projection map $\pi:\mathbf{R}^{D}\rightarrow\mathbf{T}^{D}$, so in particular
$\|v_{i}\|_{\infty}=\|\theta dn_{i}\|_{\mathbf{T}^{D}}$) and that
$w_{i}=v_{i}/\|v_{i}\|_{2}$ is the associated unit vector. Therefore, since
$\pi$ is a homomorphism

$\theta d(\sum_{i=1}^{D+1}\ell_{i}n_{i})=\pi(x),$

where

$x=\sum_{i=1}^{D+1}\ell_{i}v_{i}=\sum_{i=1}^{D+1}\ell_{i}\|v_{i}\|_{2}w_{i}.$
(12.7)

By (12.3) (and the fact that $\ell_{i}<L^{\prime}_{i}/20D^{2}\leqslant
L_{i}/20D^{2}$) we have

$|\ell_{i}|\|v_{i}\|_{2}\leqslant\frac{L_{i}}{20D^{2}}\cdot
D^{1/2}\|v_{i}\|_{\infty}=\frac{L_{i}}{20D^{2}}\cdot D^{1/2}\|\alpha
n_{i}\|_{\mathbf{T}^{D}}=\frac{1}{20D^{3/2}},$ (12.8)

and so in particular

$\|x\|_{2}\leqslant(D+1)\frac{1}{20D^{3/2}}<\frac{1}{10}.$ (12.9)

Now we look at properties (2), (3) and (4) of Proposition 9.1 separately.

_Property (2)._ Set $I_{(2)}:=\\{i:L_{i}\leqslant D^{C_{1}}L^{\prime}_{i}.\\}$
Then property (2) holds on $I_{(2)}$, since

$\sum_{i\in I_{(2)}}n_{i}L_{i}\leqslant D^{C_{1}}\sum_{i\in
I_{(2)}}n_{i}L^{\prime}_{i}\leqslant D^{C_{1}-D}X<\frac{X}{2},$

by Lemma 12.1 (1). It remains to prove (12.4), that is to say that
$|I_{(2)}^{c}|\leqslant 2^{-9}D$. Suppose not, and take
$V:=\operatorname{Span}_{\mathbf{R}}((w_{i})_{i\in I_{(2)}})$. Suppose that
(12.4) fails; then $\dim V\leqslant(1-2^{-9})D$. Consider an element
$b=\sum_{i}\ell_{i}n_{i}\in B$, with $B$ defined in (12.5). As explained in
(12.9) above, we have $\theta db=\pi(x)$, with $x\in B_{1/10}(0)$. From
(12.7), since the $w_{i}$ are unit vectors we see that

$\operatorname{dist}(x,V)\leqslant\sum_{i\notin
I_{(2)}}|\ell_{i}|\|v_{i}\|_{2}.$ (12.10)

Now observe that if $i\notin I_{(2)}$ then

$\displaystyle|\ell_{i}|\|v_{i}\|_{2}\leqslant\frac{L^{\prime}_{i}\|v_{i}\|_{2}}{20D^{2}}\leqslant\frac{L^{\prime}_{i}\|v_{i}\|_{\infty}}{20D^{3/2}}$
$\displaystyle=\frac{L^{\prime}_{i}\|\theta
dn_{i}\|_{\mathbf{T}^{D}}}{20D^{3/2}}$
$\displaystyle=\frac{L^{\prime}_{i}}{20D^{3/2}L_{i}}<\frac{1}{2}D^{-1-C_{1}},$

and so from (12.10) we have $\operatorname{dist}(x,V)<D^{-C_{1}}$. We have
shown that $\theta dB\subset\pi(N_{D^{-C_{1}}}(V)\cap B_{1/10}(0))$, and so by
(12.6) and the fact that $B\subset[X]$ we have

$\\#\\{\theta d[X]\cap\pi(N_{D^{-C_{1}}}(V)\cap B_{1/10}(0))\\}\geqslant
D^{-6D}X.$ (12.11)

On the other hand, Lemma 11.1 (with $\varepsilon=2^{-9}$, since $\dim
V\leqslant(1-2^{-9})D$) tells us that

$\\#\\{\theta d[X]\cap\pi(\mathcal{N}_{D^{-C_{1}}}(V)\cap
B_{1/10}(0))\\}\leqslant 2D^{(1-2^{-10}C_{1})D}X.$ (12.12)

If $C_{1}$ is big enough, statements (12.11) and (12.12) contradict one
another, so we were wrong to assume that $|I_{(2)}^{c}|>2^{-9}D$.

_Property (3)._ Suppose that there does not exist a set $I_{(3)}\subset[D+1]$,
$|I_{(3)}|\geqslant D+1-2^{-9}D$, with $\operatorname{vol}((w_{i})_{i\in
I_{(3)}})\geqslant D^{-C_{1}D}$. Then applying Lemma 10.4, we see that there
is a subspace $V\leqslant\mathbf{R}^{D}$, $\dim V<D(1-2^{-9})$, such that

$\operatorname{dist}(w_{i},V)\leqslant D^{-C_{1}}$ (12.13)

for all $i$. We now proceed much as before. Consider an element
$b=\sum_{i}\ell_{i}n_{i}\in B$, with $B$ defined in (12.5). As explained
above, we have $\theta db=\pi(x)$, with $x\in B_{1/10}(0)$. Now, using (12.7),
(12.8) and (12.13), we see that

$\operatorname{dist}(x,V)\leqslant\sum_{i}|\ell_{i}|\|v_{i}\|_{2}\operatorname{dist}(w_{i},V)\leqslant
D^{-C_{1}}.$ (12.14)

We have shown that $\theta dB\subset\pi(N_{D^{-C_{1}}}(V)\cap B_{1/10}(0))$,
and so once again we conclude from (12.6) and the fact that $B\subset[X]$ that

$\\#\\{\theta d[X]\cap\pi(N_{D^{-C_{1}}}(V)\cap B_{1/10}(0))\\}\geqslant
D^{-6D}X.$

Once again, this contradicts Lemma 11.1 (if $C_{1}$ is large enough). Thus we
were wrong to assert that $I_{(3)}$ does not exist.

_Property (4)._ Set $J:=\\{i\in I_{(2)}:L_{i}\geqslant X^{C_{1}/D}\\}$. Since
$J\subset I_{(2)}$, we have

$\prod_{i\in J}L_{i}\leqslant
D^{C_{1}(D+1)}\prod_{i}L^{\prime}_{i}<D^{C_{1}(D+1)}X<X^{2},$

by Lemma 12.1 (1) and the assumption on $N$. If $C_{1}\geqslant 2^{11}$ then
it follows that $|J|\leqslant 2D/C_{1}<2^{-10}D$, and so if we set
$I_{(4)}:=I_{(2)}\setminus J$ then the required bound (12.4) follows.

Finally – a very minor point – we note that property (3) implies that
$w_{1},\dots,w_{s}$ are linearly independent and so $s\leqslant D$. This
completes the proof of Proposition 9.1. ∎

_Remark._ In Section 12 (which depended heavily on Sections 7 and 11) we
obtained what amounts to some weak information about the “shape” of a random
Bohr set such as

$\\{n\leqslant X:\|n\theta_{i}\|_{\mathbf{T}}\leqslant\frac{1}{4}\;\mbox{for
$i=1,\dots,D$}\\}.$

We were not interested in just the almost sure behaviour, but rather what can
be said with very small exceptional probability on the order of $X^{-r}$, say.
Many aspects of this situation remain very mysterious to me and it may be of
interest to study the problem further.

###  13\. Comparison of two distributions on quadratic forms

In this section, which essentially stands by itself, we prove Proposition 9.2.
Recall that we define a map
$\sigma:\mathbf{R}^{n(n+1)/2}\rightarrow\operatorname{Sym}_{n}(\mathbf{R})$ as
in Section 4: to any tuple $\mathbf{x}\in\mathbf{R}^{n(n+1)/2}$, we associate
a symmetric matrix $\sigma(\mathbf{x})\in\operatorname{Sym}_{n}(\mathbf{R})$
as follows: $(\sigma(\mathbf{x}))_{ii}=x_{ii}$,
$(\sigma(\mathbf{x}))_{ij}=\frac{1}{2}x_{ij}$ for $i<j$, and
$(\sigma(\mathbf{x}))_{ij}=\frac{1}{2}x_{ji}$ for $i>j$. We will use this for
$n=D$ and for $n=s$.

The inverse
$\sigma^{-1}:\operatorname{Sym}_{n}(\mathbf{R})\rightarrow\mathbf{R}^{n(n+1)/2}$
is given by $(\sigma^{-1}(M))_{ii}=M_{ii}$ and $(\sigma^{-1}(M))_{ij}=2M_{ij}$
for $i<j$. Note, in particular, that if $M$ is symmetric and if
$x\in\mathbf{R}^{n}$ then

$x^{T}Mx=\sum_{i\leqslant j}\sigma^{-1}(M)_{ij}x_{i}x_{j}.$ (13.1)

Recall that $\mathbf{e}$ is sampled uniformly from
$[-\frac{1}{D^{4}},\frac{1}{D^{4}}]^{D(D+1)/2}$.

######  Proposition 9.2.

Let $w_{1},\dots,w_{s}\in\mathbf{R}^{D}$, $s\leqslant D$, be linearly
independent unit vectors. Write
$f:\mathbf{R}^{D(D+1)/2}\rightarrow\mathbf{R}^{s(s+1)/2}$ for the map defined
by

$f(x)=\sigma^{-1}\big{(}(\langle(I+\sigma(x))w_{i},(I+\sigma(x))w_{j}\rangle)_{1\leqslant
i,j\leqslant s}\big{)}$

Then for any measurable set $U\subset\mathbf{R}^{s(s+1)/2}$ we have

$\mathbb{P}_{\mathbf{e}}(f(\mathbf{e})\in U)\leqslant
D^{4D^{2}}\operatorname{vol}(w_{1},\dots,w_{s})^{-D-1}\mu(U),$

where $\mu$ denotes Lebesgue measure.

###### Proof.

We first handle the case $s=D$ (which we will prove with the slightly stronger
constant $D^{3D^{2}}$), and then deduce the case $s<D$ from it. Suppose, for
the moment, that $s=D$.

We write $f(x)=f_{2}(f_{1}(x))$ as a composition of two maps

$f_{1}:\mathbf{R}^{D(D+1)/2}\rightarrow\mathbf{R}^{D(D+1)/2}:\quad
f_{1}(x)=\sigma^{-1}\big{(}(I+\sigma(x))^{T}(I+\sigma(x))\big{)}$

(note here that the transpose is superfluous, since $\sigma(\mathbf{x})$ is
symmetric) and

$f_{2}:\mathbf{R}^{D(D+1)/2}\rightarrow\mathbf{R}^{D(D+1)/2}:\quad
f_{2}(x)=\sigma^{-1}\big{(}W^{T}\sigma(x)W),$

where $W_{ij}=(w_{j})_{i}$ (that is, the $i$th coordinate of $w_{j}$ in the
standard basis). Checking that $f$ is indeed the composition of these two maps
amounts to checking that $(W^{T}A^{T}AW)_{ij}=\langle Aw_{i},Aw_{j}\rangle$
for any matrix $A$, which is an easy exercise.

We claim that $f_{1}$ is injective on the domain
$[-\frac{1}{D^{4}},\frac{1}{D^{4}}]^{D(D+1)/2}$. If we have
$f_{1}(x_{1})=f_{1}(x_{2})$, then
$(I+\sigma(x_{1}))^{2}=(I+\sigma(x_{2}))^{2}$. Suppose that
$I+\sigma(x_{i})=U_{i}^{-1}\Delta_{i}U_{i}$ for $i=1,2$, with the $U_{i}$
orthogonal and $\Delta_{i}$ diagonal with entries non-increasing down the
diagonal. If $v$ is a unit vector and $x$ lies in the domain then
$\|\sigma(x)v\|_{2}\leqslant D\|x\|_{\infty}\leqslant D^{-3}$, and so all
eigenvalues of $I+\sigma(x_{i})$ (that is, entries of $\Delta_{i}$) are
extremely close to $1$ and in particular positive. Therefore
$\Delta_{1}^{2},\Delta_{2}^{2}$ are also diagonal with entries non-increasing
down the diagonal. Moreover
$U_{1}^{-1}\Delta^{2}_{1}U_{1}=U_{2}^{-1}\Delta^{2}_{2}U_{2}$, so
$\Delta^{2}_{1}$ and $\Delta^{2}_{2}$ are similar matrices and therefore the
same. It follows that $\Delta_{1}=\Delta_{2}$, and also $U_{1}U_{2}^{-1}$
commutes with $\Delta_{1}^{2}$ ($=\Delta_{2}^{2}$). However, a diagonal matrix
$\Delta$ with positive entries and its square $\Delta^{2}$ have the same
centraliser (block matrices based on equal diagonal entries) and hence
$U_{1}U_{2}^{-1}$ commutes with $\Delta_{1}$ ($=\Delta_{2}$), which means that
$I+\sigma(x_{1})=U_{1}^{-1}\Delta_{1}U_{1}=U_{2}^{-1}\Delta_{1}U_{2}=U_{2}^{-1}\Delta_{2}U_{2}=I+\sigma(x_{2})$
and so $x_{1}=x_{2}$. The claim follows.

For the two maps $f_{1},f_{2}$, we additionally claim that:

  1. (1)

$f_{1}$ is differentiable on $[-\frac{1}{D^{4}},\frac{1}{D^{4}}]^{D(D+1)/2}$,
with Jacobian bounded below by $1$;

  2. (2)

$f_{2}$ is linear, with $|\det f_{2}|=|\det W|^{D+1}$.

The proposition then follows by change of variables, in fact with the more
precise constant $(2D^{4})^{D(D+1)/2}$ for the $D$-dependence, noting that
$\operatorname{vol}(w_{1},\dots,w_{D})=|\det(W^{T}W)|^{1/2}=|\det W|$.

_Proof of (1)._ This can be established by direct, co-ordinatewise,
calculation. Indeed, it is easy to check that

$(f_{1}(\mathbf{x}))_{ij}=1_{i=j}+2x_{ij}+q_{ij}(\mathbf{x}),$

where $q_{ij}(\mathbf{x})$ is a quadratic form with at most $D$ terms, each
with coefficient bounded by $1$. Thus

$\big{|}\frac{\partial(f_{1})_{ij}}{\partial x_{uv}}(\mathbf{e})-2\cdot
1_{(i,j)=(u,v)}\big{|}\leqslant 2D\|\mathbf{e}\|_{\infty}.$ (13.2)

To bound the Jacobian of $f_{1}$ below, we need a lower bound for determinants
of perturbations of the identity. Using Fredholm’s identity
$\det(I+E)=\exp(\sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{k}\mbox{tr}(E^{k}))$, one
can check that if $E$ is an $n$-by-$n$ matrix with entries bounded in absolute
value by $\varepsilon<\frac{1}{2n}$ then $\det(I+E)\geqslant
e^{-2n\varepsilon}$. (In fact, the stronger bound $1-n\varepsilon$ for
$\varepsilon\leqslant\frac{1}{n}$ was shown by Ostrowksi [17, Eq (5.5)] in
1938; for our purposes, fairly crude bounds would suffice.)

It follows from this, (13.2) and the fact that
$|\mathbf{e}\|_{\infty}\leqslant D^{-4}$ that, if $D$ is large, the Jacobian
of $f_{1}$ is indeed greater than $1$.

_Proof of (2)._ If $A$ is a $D\times D$ matrix, define
$f_{2}^{A}:\mathbf{R}^{D(D+1)/2}\rightarrow\mathbf{R}^{D(D+1)/2}$ by
$f_{2}^{A}(x)=\sigma^{-1}(A^{T}\sigma(x)A)$. It is clear that $f_{2}^{A}$ is
linear in $x$ for fixed $A$, and also that
$f_{2}^{AA^{\prime}}=f_{2}^{A^{\prime}}\circ f_{2}^{A}$ for all
$A,A^{\prime}$. Thus, to prove that $|\det(f_{2}^{A})|=|\det A|^{D+1}$ for all
$A$ (and in particular for $A=W$) it suffices, by the existence of singular
value decomposition, to prove this in the cases (i) $A$ is diagonal and (ii)
$A$ is orthogonal.

When $A$ is diagonal with diagonal entries $\lambda_{1},\dots,\lambda_{D}$
then one sees by inspection that
$(f_{2}^{A}(x))_{ij}=\lambda_{i}\lambda_{j}x_{ij}$, which renders the result
clear in this case. When $A$ is orthogonal, $f_{2}^{A}$ preserves a non-
degenerate quadratic form, namely
$\psi(x):=\|\sigma(x)\|_{\operatorname{HS}}$, where
$\|\cdot\|_{\operatorname{HS}}$ is the Hilbert-Schmidt norm. Therefore in this
case $|\det f_{2}^{A}|=1$.

This completes the proof in the case $D=s$. Now suppose that $s<D$. In this
case, we first complete $w_{1},\dots,w_{s}$ to a set $w_{1},\dots,w_{D}$ of
unit vectors with

$\operatorname{vol}(w_{1},\dots,w_{D})\geqslant\operatorname{vol}(w_{1},\dots,w_{s}).$
(13.3)

For the proof that this is possible, see Corollary 10.3.

Let $\tilde{f}:\mathbf{R}^{D(D+1)/2}\rightarrow\mathbf{R}^{D(D+1)/2}$ be

$\tilde{f}(x)=\sigma^{-1}\big{(}(\langle(I+\sigma(x))w_{i},(I+\sigma(x))w_{j}\rangle)_{1\leqslant
i,j\leqslant D}\big{)};$

then $f=\pi\circ\tilde{f}$, where
$\pi:\mathbf{R}^{D(D+1)/2}\rightarrow\mathbf{R}^{s(s+1)/2}$ is the natural
projection, i.e.

$\pi((a_{ij})_{1\leqslant i\leqslant j\leqslant D})=(a_{ij})_{1\leqslant
i\leqslant j\leqslant s}.$

The case $s=D$ just established shows that for any measurable $\tilde{U}$

$\mathbb{P}_{\mathbf{e}}(\tilde{f}(\mathbf{e})\in\tilde{U})\leqslant
D^{3D^{2}}\operatorname{vol}(w_{1},\dots,w_{D})^{-D-1}\tilde{\mu}(\tilde{U}),$
(13.4)

where $\tilde{\mu}$ is the Lebesgue measure on $\mathbf{R}^{D(D+1)/2}$.

Now suppose that $U\subset\mathbf{R}^{s(s+1)/2}$. Then, since (by (4.4))
$\|\tilde{f}(\mathbf{e})\|_{\infty}\leqslant 8$ for all
$\mathbf{e}\in[-\frac{1}{D^{4}},\frac{1}{D^{4}}]^{D(D+1)/2}$, we see using
(13.4) that

$\displaystyle\mathbb{P}_{\mathbf{e}}(f(\mathbf{e})\in U)$
$\displaystyle=\mathbb{P}_{\mathbf{e}}(\tilde{f}(\mathbf{e})\in\pi^{-1}(U))$
$\displaystyle=\mathbb{P}_{\mathbf{e}}(\tilde{f}(\mathbf{e})\in\pi^{-1}(U)\cap[-8,8]^{D(D+1)/2})$
$\displaystyle\leqslant
D^{3D^{2}}\operatorname{vol}(w_{1},\dots,w_{D})^{-D-1}\tilde{\mu}(\pi^{-1}(U)\cap[-8,8]^{D(D+1)/2})$
$\displaystyle\leqslant
D^{4D^{2}}\operatorname{vol}(w_{1},\dots,w_{D})^{-D-1}\mu(U).$

To complete the proof, apply (13.3). ∎

##  Part V Small gaps and quadratic forms

###  14\. Determinants of random matrices

In this section the main result is Lemma 14.2 below, which gives an upper
bound on the probability that certain random matrices with fixed diagonal
entries have very small determinant. The key ingredient is the following lemma
about random symmetric matrices with uniform entries, without any restriction
on the diagonal.

######  Lemma 14.1.

Let $n$ be sufficiently large and let $W$ be a random symmetric $n\times n$
matrix with entries drawn uniformly and independently from
$[-\frac{1}{n},\frac{1}{n}]$. Then $\mathbb{P}(|\det
W|\leqslant\delta)\leqslant n^{2n^{2}}\delta$.

###### Proof.

The idea is to compare $W$ with a random (symmetric) matrix $Z$ from the
Gaussian Orthogonal Ensemble (GOE) and then compute using the joint density
function for eigenvalues there, which is explicit. The density function of
$\mbox{GOE}(n)$ is $f(Z)=c_{n}e^{-\frac{1}{4}\operatorname{tr}(Z^{2})}$, where
$c_{n}=2^{-n/2}(2\pi)^{-n(n+1)/4}$ (see [2, equation 2.5.1]). If $W$ has
entries in $[-\frac{1}{n},\frac{1}{n}]$ then $\operatorname{tr}W^{2}\leqslant
1$, so $f(W)\geqslant c_{n}e^{-1/4}$. Therefore we have the comparison
estimate

$\mathbb{P}_{W}(|\det
W|\leqslant\delta)\leqslant(\frac{n}{2})^{n(n+1)/2}c_{n}^{-1}e^{1/4}\mathbb{P}_{Z}(|\det
Z|\leqslant\delta).$ (14.1)

It remains to estimate the right-hand side. For this, we use the well-known
formula (see [2, Theorem 2.5.2]) for the joint eigenvalue density of
$\mbox{GOE}(n)$, together with the fact that the determinant is the product of
the eigenvalues. This tells us that $\mathbb{P}_{Z}(|\det Z|\leqslant\delta)$
is a normalising constant times

$I:=\int_{\begin{subarray}{c}\lambda_{1}\geqslant\lambda_{2}\geqslant\dots\geqslant\lambda_{n}\\\
|\lambda_{1}\cdots\lambda_{n}|\leqslant\delta\end{subarray}}\prod_{i<j}|\lambda_{i}-\lambda_{j}|e^{-\frac{1}{4}\sum_{i=1}^{n}\lambda_{i}^{2}}d\lambda_{1}\dots
d\lambda_{n}.$

The normalising constant is (far) less than $1$ and we do not need anything
else about it. By symmetry, $I$ is equal to

$\int_{\begin{subarray}{c}|\lambda_{1}|\geqslant|\lambda_{2}|\geqslant\dots\geqslant|\lambda_{n}|\\\
|\lambda_{1}\cdots\lambda_{n}|\leqslant\delta\end{subarray}}\prod_{i<j}|\lambda_{i}-\lambda_{j}|e^{-\frac{1}{4}\sum_{i=1}^{n}\lambda_{i}^{2}}d\lambda_{1}\dots
d\lambda_{n}.$

Now with this ordering we have $|\lambda_{i}-\lambda_{j}|\leqslant
2|\lambda_{i}|$ whenever $j>i$, and so

$I\leqslant
2^{n(n-1)/2}\int_{|\lambda_{1}\cdots\lambda_{n}|\leqslant\delta}|\lambda_{1}|^{n-1}|\lambda_{2}|^{n-2}\cdots|\lambda_{n-1}|e^{-\frac{1}{4}\sum_{i=1}^{n}\lambda_{i}^{2}}d\lambda_{1}\dots
d\lambda_{n}.$ (14.2)

Now one may easily check the real-variable inequality
$|x|^{k-1}e^{-x^{2}/8}\leqslant k^{k}$ for all positive integers $k$ and all
$x\in\mathbf{R}$, which implies that $|x|^{k}e^{-x^{2}/4}\leqslant
k^{k}|x|e^{-x^{2}/8}$. Substituting into (14.2) gives

$I\leqslant
2^{n(n-1)/2}(\prod_{k=1}^{n-1}k^{k})\int_{|\lambda_{1}\cdots\lambda_{n}|\leqslant\delta}|\lambda_{1}\lambda_{2}\dots\lambda_{n-1}|e^{-\frac{1}{8}\sum_{i=1}^{n}\lambda_{i}^{2}}d\lambda_{n}\cdots
d\lambda_{1}.$

The inner integral over $\lambda_{n}$ is

$\int_{|\lambda_{n}|\leqslant\delta/|\lambda_{1}\cdots\lambda_{n-1}|}e^{-\frac{1}{8}\lambda_{n}^{2}}d\lambda_{n}\leqslant\frac{2\delta}{|\lambda_{1}\cdots\lambda_{n-1}|},$

and therefore

$I\leqslant
2^{n(n-1)/2+1}\delta(\prod_{k=1}^{n-1}k^{k})\int_{\mathbf{R}^{n-1}}e^{-\frac{1}{8}\sum_{i=1}^{n-1}\lambda_{i}^{2}}d\lambda_{n-1}\dots
d\lambda_{1}=C_{n}\delta,$

where

$C_{n}:=2^{n(n-1)/2+1}(8\pi)^{(n-1)/2}(\prod_{k=1}^{n-1}k^{k}).$

For $n$ large, a crude bound is $C_{n}\leqslant n^{n^{2}}$ and so the result
follows from this and (14.1).∎

_Remarks._ For us, the dependence on $\delta$ (which is sharp) is the
important thing. So long as we were not ridiculously profligate, the
$n$-dependence of the constant in Lemma 14.1 was of secondary importance.
However, a weaker $\delta$-dependence such as $\delta^{1/n}$ (which follows
from a Remez-type inequality, just treating $\det$ as an arbitrary degree $n$
polynomial) would lead to a weaker exponent in our main theorem.

For fixed $n$, asymptotic formulae of the form $\mathbb{P}(|\det
Z|\leqslant\delta)=(\beta_{n}+o_{\delta\rightarrow 0}(1))\delta$ can be
extracted from [6] (I thank Jon Keating for bringing this reference to my
attention). So far as I am aware nothing of this type is known for the uniform
distribution on matrix entries.

Here is the result we will actually need in the next section. It requires us
to be able to fix the diagonal entries of the symmetric matrix of interest.

######  Lemma 14.2.

Let $m$ be sufficiently large, and let $a$ be an $m\times m$ upper-triangular
matrix selected at random as follows. Fix diagonal entries $a_{ii}$ with
$1\leqslant a_{11},\dots,a_{mm}\leqslant Q$, and select the off-diagonal
entries $a_{ij}$, $i<j$, independently and uniformly at random from $[-Q,Q]$.
Then $\mathbb{P}(|\det(a+a^{T})|\leqslant\delta)\leqslant(Qm)^{5m^{2}}\delta$,
uniformly in the fixed choice of the diagonal terms $a_{ii}$.

###### Proof.

The idea is to amplify the problem so that we are considering a full set of
symmetric matrices rather than those with fixed diagonal. To this end,
consider the map

$\Psi:(1,2)^{m}\times(-Q,Q)^{m(m-1)/2}\rightarrow(1,4Q)^{m}\times(-4Q,4Q)^{m(m-1)/2}$

defined by $\Psi(D,M):=DMD$, where here $D$ is a diagonal $m\times m$ matrix
with entries in $(1,2)$ (with the space of these being identified with
$(1,2)^{m}$), $M$ is a symmetric matrix with $a_{11},\dots,a_{mm}$ on the
diagonal (with the space of these being identified with
$\mathbf{R}^{m(m-1)/2}$ by restriction to the entries above the diagonal) and
$DMD$ is a symmetric matrix with diagonal entries in the interval $(1,4Q)$
(with the space of these being identified with
$(1,4Q)^{m}\times\mathbf{R}^{m(m-1)/2}$ by restriction to the diagonal and the
entries above it). Note that $\Psi$ is a diffeomorphism onto an open set
$U=\Psi((1,2)^{m}\times(-Q,Q)^{m(m-1)/2})\subset(1,4Q)^{m}\times(-4Q,4Q)^{m(m-1)/2}$
with smooth inverse $\Psi^{-1}:U\rightarrow(1,2)^{m}\times(-Q,Q)^{m(m-1)/2}$
given by

$\Psi^{-1}(x)=\big{(}(x_{ii}/a_{ii})^{1/2}_{i=1,\dots,m},\big{(}(a_{ii}a_{jj}/x_{ii}x_{jj})^{1/2}x_{ij})_{1\leqslant
i<j\leqslant m}\big{)}.$

All of the partial derivatives of this map are bounded in modulus by $4Q^{2}$
on its domain, and therefore (crudely) the Jacobian of $\Psi^{-1}$ is bounded
by $(\frac{1}{2}m(m+1))!(4Q^{2})^{m(m+1)/2}$. Therefore (crudely, and using
the fact that $m$ is sufficiently large)

$|\mbox{Jac}(\Psi)|\geqslant\frac{1}{(\frac{1}{2}m(m+1))!(4Q^{2})^{m(m+1)/2}}\geqslant(Qm)^{-2m^{2}},$
(14.3)

uniformly on the domain.

Now set $\Omega:=\\{M\in[-Q,Q]^{m(m-1)/2}:|\det M|\leqslant\delta\\}$ (where,
recall, $[-Q,Q]^{m(m-1)/2}$ is being identified with the space of symmetric
matrices with $a_{11},\dots,a_{mm}$ on the diagonal); our task is to give an
upper bound for $\mu_{\mathbf{R}^{m(m-1)/2}}(\Omega)$. First observe that

$\mu_{\mathbf{R}^{m(m+1)/2}}((1,2)^{m}\times\Omega)=\mu_{\mathbf{R}^{m(m-1)/2}}(\Omega).$
(14.4)

To estimate the left-hand side, note that if $M\in\Omega$ and $D$ is diagonal
with entries in $(1,2)$ then $\det(\Psi(D,M))=(\det D)^{2}\det M\leqslant
4^{m}\delta$. Since, moreover,

$\Psi((1,2)^{m}\times\Omega)\subset[-4Q,4Q]^{m(m+1)/2},$

we may use Lemma 14.1 (rescaling the sample space by a factor $4Qm$) to
conclude that

$\displaystyle\mu_{\mathbf{R}^{m(m+1)/2}}(\Psi((1,2)^{m}\times\Omega))$
$\displaystyle\leqslant(4Qm)^{m(m+1)/2}m^{2m^{2}}(Qm)^{-m}\delta$
$\displaystyle<(Qm)^{3m^{2}}\delta.$

By (14.3) and change of variables, it follows that

$\mu_{\mathbf{R}^{m(m+1)/2}}((1,2)^{m}\times\Omega))<(Qm)^{5m^{2}}\delta.$
(14.5)

Comparing with (14.4) concludes the proof. ∎

###  15\. An application of the circle method

In this section we establish the key ingredient in Proposition 9.3, which is
Proposition 15.1.

For any parameter $\delta>0$, we will make use of a cutoff function
$\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}$.

For the proof that such a $\chi$ exists, see Lemma B.3.

######  Proposition 15.1.

Let $B>1$. Set $m=C_{1}B$. Suppose that $L>(Qm)^{m}$. Let
$L_{1},\dots,L_{m}\in[L,L^{1+1/48}]$ be lengths. Denote by $\mu$ the Lebesgue
measure on $\mathbf{R}^{m}$, and by $\mu_{\operatorname{disc}}$ the uniform
probability measure on the points $(x_{1}/L_{1},\dots,x_{m}/L_{m})$, with the
$x_{i}$ integers satisfying $0\leqslant x_{i}<L_{i}$.

Fix $1\leqslant a_{11},\dots,a_{mm}\leqslant Q$, and choose $a_{ij}$,
$1\leqslant i<j\leqslant s$ independently and uniformly at random from
$[-Q,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 $\chi=\chi_{L^{-B}}$ with $\chi$ as above, and let
$w:\mathbf{R}\rightarrow\mathbf{R}$ be a smooth function supported on $[0,1]$
with $\|w\|_{\infty}\leqslant 1$ and
$\|w^{\prime}\|_{\infty},\|\hat{w}\|_{1}\leqslant L^{1/C_{1}}$. Then with
probability at least $1-L^{-B}$ in the random choice of $a$ we have

$\big{|}\int w^{\otimes m}(t)\chi(q_{a,b,c}(t))d\mu(t)-\int w^{\otimes
m}(t)\chi(q_{a,b,c}(t))d\mu_{\operatorname{disc}}(t)\big{|}\leqslant
L^{-B-1/4},$ (15.1)

for all $b\in\mathbf{R}^{m}$, $c\in\mathbf{R}$ with $|b_{i}|,|c|\leqslant Q$.

_Remarks._ Here, $w^{\otimes m}(t)=w(t_{1})\cdots w(t_{m})$.

The detailed statement is somewhat complicated. What it says, roughly, is that
for almost all $a$ the distribution of the quadratic form $q_{a,b,c}(t)$ on
discrete points $t=(x_{1}/L_{1},\dots,x_{m}/L_{m})$ is closely approximated by
the distribution over all of $[0,1]^{m}$, even on the level of rather short
intervals of length $L^{-B}$. The two smoothings $\chi,w$ of course make the
statement look more exotic, but are necessary for technical reasons in the
proof.

The need to fix the diagonal terms $a_{11},\dots,a_{mm}$ and only let the off-
diagonal terms vary randomly is important for the key application of the
proposition in the next section. This also makes the argument somewhat more
complicated.

The proof is rather lengthy. The reader will lose almost nothing should they
wish to look through the proof in the case $L_{1}=\cdots=L_{m}$, $Q=1$ and
without worrying about the dependence on $w$; it is then fairly clear that the
argument can be modified, provided one makes suitable assumptions on $Q$ and
$w$, so that it works under the slightly looser hypotheses.

Let us outline the proof of the proposition. By Fourier inversion on $\chi$ we
have, for $\nu=\mu$ or $\nu=\mu_{\operatorname{disc}}$,

$\int_{\mathbf{R}^{m}}w^{\otimes
m}(t)\chi(q_{a,b,c}(t))d\nu(t)=\int_{\mathbf{R}}\hat{\chi}(\xi)\int_{\mathbf{R}^{m}}w^{\otimes
m}(t)e(\xi q_{a,b,c}(t))d\nu(t)d\xi.$

Write

$S_{a,b,c}(\xi):=\int_{\mathbf{R}^{m}}w^{\otimes m}(t)e(\xi
q_{a,b,c}(t))d\mu_{\operatorname{disc}}(t)$ (15.2)

and

$T_{a.b,c}(\xi):=\int_{\mathbf{R}^{m}}w^{\otimes m}(t)e(\xi
q_{a,b,c}(t))d\mu(t);$ (15.3)

the task is then to prove the estimate

$\int_{\mathbf{R}}\hat{\chi}(\xi)(T_{a,b,c}(\xi)-S_{a,b,c}(\xi))d\xi\ll
L^{-B-1/4}$ (15.4)

(for all $b,c$, with high probability in $a$). To prove this, we will analyse
various different ranges of $\xi$, proving the following four lemmas. In these
lemmas, we assume that the assumptions (on $L$ and $w$) from Proposition 15.1
remain in force.

######  Lemma 15.2.

For $|\xi|\leqslant L^{1/8}$, we have $|S_{a,b,c}(\xi)-T_{a,b,c}(\xi)|\ll
L^{-1/2}$, uniformly for all $a,b,c$ with $|a_{ij}|,|b_{i}|,|c|\leqslant Q$.

######  Lemma 15.3.

For $|\xi|\geqslant L^{1/8}$ we have $|T_{a,b,c}(\xi)|\ll L^{-2B}$, uniformly
in $a$ with $|a_{ij}|\leqslant Q$ and $\det(a+a^{T})\geqslant L^{-2B}$, and
for all $b,c$ with $|b_{i}|,|c|\leqslant Q$.

######  Lemma 15.4.

Suppose that $L^{1/8}<|\xi|<L^{5/4}$ and that $\det(a+a^{T})\geqslant
L^{-2B}$. Then $\max_{b,c}|S_{a,b,c}(\xi)|\leqslant L^{-2B}$.

######  Lemma 15.5.

For each fixed $\xi$, $L^{5/4}\leqslant|\xi|\leqslant L^{2B}$, we have

$\mathbb{P}_{a}(\max_{b,c}|S_{a,b,c}(\xi)|\geqslant L^{-2B})\leqslant
L^{-7B}.$

The most involved part of the argument is the proof of Lemmas 15.4 and 15.5.
Before turning to the proofs of the lemmas, let us see how they assemble to
give a proof of Proposition 15.1, via (15.4).

###### Proof of Proposition 15.1.

(assuming Lemmas 15.2 – 15.5) In this argument we write $o(1)$ to denote a
quantity tending to zero as $L\rightarrow\infty$. First, note that for each
fixed $a,b,c$ with $|a_{ij}|,|b_{i}|\leqslant Q$ the sum $S_{a,b,c}(\xi)$ is
weakly continuous in $\xi$, in the sense that
$|S_{a,b,c}(\xi)-S_{a,b,c}(\xi^{\prime})|\ll Qm^{2}|\xi-\xi^{\prime}|$. This
follows from the definition (15.2) and the fact that $|q_{a,b,c}|\ll Qm^{2}$
on $[0,1]^{m}$. If $|\xi-\xi^{\prime}|\leqslant L^{-3B}$ then, under our
assumption on $L$, this comfortably implies that

$|S_{a,b,c}(\xi)-S_{a,b,c}(\xi^{\prime})|<L^{-2B}.$ (15.5)

Let $\xi_{1},\dots,\xi_{L^{5B}}$ be a $L^{-3B}$-dense set of points in
$[L^{1/8},L^{2B}]$. Suppose that $\det(a+a^{T})\geqslant L^{-2B}$. Then by
Lemmas 15.4, 15.5 and the union bound we have

$\mathbb{P}_{a}(\max_{i}\max_{b,c}|S_{a,b,c}(\xi_{i})|\geqslant
L^{-2B})\leqslant L^{-2B}=o(L^{-B}),$

and so by (15.5)

$\mathbb{P}_{a}(\max_{L^{1/8}\leqslant|\xi|\leqslant
L^{2B}}\max_{b,c}|S_{a,b,c}(\xi)|\geqslant 2L^{-2B})=o(L^{-B}).$

That is, with probability at least $1-o(L^{-B})$ in $a$,

$|S_{a,b,c}(\xi)|\leqslant 2L^{-2B}\;\mbox{for $L^{1/8}\leqslant|\xi|\leqslant
L^{2B}$ and all $b,c$ with $|b_{i}|,|c|\leqslant Q$.}$ (15.6)

Now by Lemma 14.2, the probability that $|\det(a+a^{T})|<L^{-2B}$ is at most
$(Qm)^{5m^{2}}L^{-2B}$, which is certainly $o(L^{-B})$ with the assumption
$L>(Qm)^{m}$. Suppose from now on that $a$ has the property (15.6) and that
$\det(a+a^{T})>L^{-2B}$. We have shown that this is true with probability
$1-o(L^{-B})$.

Returning to the main task (15.4), we divide into low-, middle- and high-
frequency ranges. For the low-range frequencies $|\xi|\leqslant L^{1/8}$ we
use Lemma 15.2 and the trivial bound $|\hat{\chi}(\xi)|\leqslant L^{-B}$
(which follows from the fact that $\int\chi\ll L^{-B}$, which is property (3)
of $\chi$), obtaining

$\displaystyle\int_{|\xi|\leqslant
L^{1/8}}\hat{\chi}(\xi)(T_{a,b,c}(\xi)-S_{a,b,c}(\xi))d\xi$ $\displaystyle\ll
L^{-1/2}\int_{|\xi|\leqslant L^{1/8}}|\hat{\chi}(\xi)|$
$\displaystyle=o(L^{-B-1/4}).$ (15.7)

For the middle range frequencies $L^{1/8}<|\xi|<L^{2B}$ we have, by Lemma
15.3,

$\int_{L^{1/8}<|\xi|<L^{2B}}|\hat{\chi}(\xi)T_{a,b,c}(\xi)|d\xi\ll
L^{-2B}\int_{\mathbf{R}}|\hat{\chi}(\xi)|d\xi\ll L^{-2B},$ (15.8)

where the last inequality follows from the fact that $\|\hat{\chi}\|_{1}\ll
1$, which is item (4) of the list of properties satisfied by $\chi$. By
(15.6), we similarly have

$\int_{L^{1/8}<|\xi|<L^{2B}}|\hat{\chi}(\xi)S_{a,b,c}(\xi)|d\xi\ll
L^{-2B}\int_{\mathbf{R}}|\hat{\chi}(\xi)|d\xi\ll L^{-2B}.$ (15.9)

By the triangle inequality, (15.8) and (15.9) together give

$\int_{L^{1/8}<|\xi|<L^{2B}}\hat{\chi}(\xi)(T_{a,b,c}(\xi)-S_{a,b,c}(\xi))d\xi\ll
L^{-2B}.$ (15.10)

Finally, for the high-frequencies $|\xi|\geqslant L^{2B}$ we use the trivial
bounds $|S_{a,b,c}(\xi)|,|T_{a,b,c}(\xi)|\leqslant 1$ (both of which follow
immediately from the definitions (15.2), (15.3), remembering that $w$ is
supported on $[0,1]$ and has $\|w\|_{\infty}\leqslant 1$) and the estimate
$\int_{|\xi|\geqslant L^{2B}}|\hat{\chi}(\xi)|\ll L^{-2B}$ (item (5) on the
list of properties satisfied by $\chi$) to get

$\int_{|\xi|>L^{2B}}\hat{\chi}(\xi)(T_{a,b,c}(\xi)-S_{a,b,c}(\xi))d\xi\ll\int_{|\xi|>L^{2B}}|\hat{\chi}(\xi)|\ll
L^{-2B}.$ (15.11)

Putting (15.7), (15.10) and (15.11) together completes the proof of (15.4),
this having been shown to be true with probability $1-o(L^{-B})$ in $a$ (and
for all $b,c$ with $|b_{i}|,|c|\leqslant Q$). This completes the proof of
Proposition 15.1, subject of course to proving Lemmas 15.2, 15.3, 15.4 and
15.5. ∎

We now begin the task of proving those four lemmas.

###### Proof of Lemma 15.2.

For any function $f$ supported on $[0,1]^{m}$ we have

$\int_{\mathbf{R}^{m}}f(t)d\mu(t)=\sum_{0\leqslant
x_{i}<L_{i}}\int_{\prod_{i=1}^{m}[0,\frac{1}{L_{i}}]^{m}}f(\frac{x}{L_{i}}+t)d\mu(t).$

However for $t\in[0,\frac{1}{L_{i}}]^{m}$ the mean value theorem gives

$|f(\frac{x}{L_{i}}+t)-f(\frac{x}{L_{i}})|\leqslant\frac{m}{L}\max_{j}\|\partial_{j}f\|_{\infty},$

whilst

$\displaystyle\sum_{0\leqslant
x_{i}<L_{i}}\int_{\prod_{i=1}^{m}[0,\frac{1}{L_{i}}]^{m}}f(\frac{x}{L_{i}})d\mu(t)$
$\displaystyle=\frac{\lceil L_{1}\rceil\cdots\lceil L_{m}\rceil}{L_{1}\cdots
L_{m}}\int fd\mu_{\operatorname{disc}}$ $\displaystyle=\int
fd\mu_{\operatorname{disc}}+O(\frac{m}{L}\|f\|_{\infty}).$

Therefore

$\big{|}\int_{\mathbf{R}^{m}}f(t)d\mu(t)-\int_{\mathbf{R}^{m}}f(t)d\mu_{\operatorname{disc}}(t)\big{|}\ll\frac{m}{L}\max_{j}\|\partial_{j}f\|_{\infty}+\frac{m}{L}\|f\|_{\infty}.$
(15.12)

Taking $f(t)=w^{\otimes m}(t)e(\xi q_{a,b,c}(t))$, we see that for
$t\in[0,1]^{m}$

$\displaystyle\partial_{j}f(t)$ $\displaystyle=w^{\otimes
w}(t)\partial_{j}e(\xi q_{a,b,c}(t))+\partial_{j}(w^{\otimes m}(t))e(\xi
q_{a,b,c}(t))$ $\displaystyle\ll m|\xi|Q+\|w^{\prime}\|_{\infty}.$ (15.13)

Now $|\xi|\leqslant L^{1/8}$, and the assumptions of Proposition 15.1
guarantee that the terms $Qm,\|w^{\prime}\|_{\infty}$ are much smaller than
$L^{1/8}$. The result follows by combining (15.12), (15.13). ∎

###### Proof of Lemma 15.3..

Recall the definition (15.3) of $T_{a,b,c}$, that is to say

$T_{a,b,c}(\xi)=\int_{\mathbf{R}^{m}}w^{\otimes m}(t)e(\xi
q_{a,b,c}(t))d\mu(t),$ (15.14)

where

$q_{a,b,c}(t)=\sum_{i\leqslant
j}a_{ij}t_{i}t_{j}+\sum_{i}b_{i}t_{i}+c=\frac{1}{2}t^{T}(a+a^{T})t+b^{T}t+c.$

Let $\lambda_{1},\dots,\lambda_{m}$ be the eigenvalues of $a+a^{T}$. Thus by
assumption we have

$\lambda_{1}\cdots\lambda_{m}=\det(a+a^{T})\geqslant L^{-2B}.$ (15.15)

Let $\Psi$ be an orthogonal matrix so that $\Psi^{T}(a+a^{T})\Psi=D$, where
$D$ is the diagonal matrix with entries $\lambda_{1},\dots,\lambda_{m}$.
Making the change of variables $t=\Psi u$ in (15.14) gives

$T_{a,b,c}(\xi)=\int_{\mathbf{R}^{m}}w^{\otimes m}(\Psi
u)\prod_{j=1}^{m}e(\frac{1}{2}\xi\lambda_{j}u_{j}^{2}+\alpha_{j}u_{j}+\beta)du_{1}\cdots
du_{m}.$ (15.16)

Here, $\alpha_{1},\dots,\alpha_{m},\beta$ are real numbers depending on
$\xi,b,c,\Psi$, but their precise identity is unimportant. Note that if $\Psi
u\in[0,1]^{m}$ then $\|u\|_{\infty}\leqslant\|u\|_{2}=\|\Psi