# Rado’s criterion over squares and higher powers

Sam Chow  Department of Mathematics
University of York
Heslington
York YO10 5DD
United Kingdom<EMAIL_ADDRESS>,  Sofia Lindqvist  Mathematical
Institute
University of Oxford
UK<EMAIL_ADDRESS>and  Sean Prendiville  School of Mathematics
University of Manchester
UK<EMAIL_ADDRESS>
###### Abstract.

We establish partition regularity of the generalised Pythagorean equation in
five or more variables. Furthermore, we show how Rado’s characterisation of a
partition regular equation remains valid over the set of positive $k$th
powers, provided the equation has at least $(1+o(1))k\log k$ variables. We
thus completely describe which diagonal forms are partition regular and which
are not, given sufficiently many variables. In addition, we prove a
supersaturated version of Rado’s theorem for a linear equation restricted
either to squares minus one or to logarithmically-smooth numbers.

###### Key words and phrases:

Arithmetic combinatorics, arithmetic Ramsey theory, Weyl sums, smooth numbers,
restriction theory

###### 2010 Mathematics Subject Classification:

11B30, 11D72, 11L15

###### Contents

  1. 1 Introduction
  2. 2 Methods
  3. 3 Open problems
  4. I The generalised Pythagorean equation
    1. 4 Induction on colours
    2. 5 A pseudorandom Furstenberg–Sárközy theorem
    3. 6 The $W$-trick for squares: a simplified treatment
    4. 7 Multidimensional homogeneous Furstenberg–Sárközy
    5. 8 Varnavides averaging for supersaturation
  5. II Rado’s criterion over squares and higher powers
    1. 9 The smooth homogeneous Bergelson–Leibman theorem
    2. 10 A supersaturated generalisation of both Roth and Sárközy’s theorems
    3. 11 Pseudorandom Roth–Sárközy
    4. 12 The $W$-trick for smooth powers and a non-linear Roth–Sárközy theorem
    5. 13 Deducing partition regularity
  6. III Supersmooths and shifted squares
    1. 14 Modelling a pseudorandom partition with a colouring
    2. 15 A pseudorandom Rado theorem
    3. 16 Supersaturation for shifted squares
    4. 17 Supersaturation for logarithmically-smooth numbers
  7. IV Appendices
    1. A Results on smooth numbers
    2. B The unrestricted count and mean values estimates
    3. C A generalised von Neumann lemma
    4. D Pointwise exponential sum estimates
    5. E Restriction estimates
    6. F Lefmann’s criterion

###  1\. Introduction

Schur’s theorem [Sch1916] is a foundational result in Ramsey theory, asserting
that in any finite colouring of the positive integers there exists a
monochromatic solution to the equation $x+y=z$ (a solution in which each
variable receives the same colour). A notorious question of Erdős and Graham
asks if the same is true for the Pythagorean equation $x^{2}+y^{2}=z^{2}$,
offering $250 for an answer [Grah07, Grah08]. The computer-aided verification
[HKM16] of the two colour case of this problem is reported to be the largest
mathematical proof in existence, consuming 200 terabytes [Lam16]. We provide
an affirmative answer to the analogue of the Erdős–Graham question for
generalised Pythagorean equations in five or more variables.

######  Theorem 1.1 (Schur-type theorem in the squares).

In any finite colouring of the positive integers there exists a monochromatic
solution to the equation

$x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}=x_{5}^{2}.$ (1.1)

This is a consequence of a more general phenomenon. Given enough variables, we
completely describe which diagonal forms have the above property and which do
not.

######  Definition 1.2 (Partition regular).

Given a polynomial $P\in\mathbb{Z}[x_{1},\dots,x_{s}]$ and a set $S$ call the
equation $P(x)=0$ _partition regular over $S$_ if, in any finite colouring of
$S$, there exists a solution $x\in S^{s}$ whose coordinates all receive the
same colour. We say that the equation is _non-trivially partition regular_ if
every finite colouring of $S$ has a monochromatic solution in which each
variable is distinct.

Rado [Rad33] established an elegant algebraic characterisation of partition
regular homogeneous linear equations.

######  Rado’s criterion for one equation.

Let $c_{1},\dots,c_{s}\in\mathbb{Z}\setminus\left\\{0\right\\}$, where
$s\geqslant 3$. Then the equation $\sum_{i=1}^{s}c_{i}x_{i}=0$ is (non-
trivially) partition regular over the positive integers if and only if there
exists a non-empty set $I\subset[s]$ such that $\sum_{i\in I}c_{i}=0$.

A number of authors [Ber96, Ber16, Grah08, DNB18] have sought algebraic
characterisations of partition regularity within families of non-linear
Diophantine equations. The example of the Fermat equation shows that one
cannot hope for something as simple as Rado’s criterion for diagonal forms.
Nevertheless, provided that the number of variables $s$ is sufficiently large
in terms of the degree $k$, we establish that the same criterion characterises
partition regularity for equations in $k$th powers.

######  Theorem 1.3 (Rado over $k$th powers).

There exists $s_{0}(k)\in{\mathbb{N}}$ such that for $s\geqslant s_{0}(k)$ and
$c_{1},\dots,c_{s}\in\mathbb{Z}\setminus\left\\{0\right\\}$ the following
holds. The equation

$\sum_{i=1}^{s}c_{i}x_{i}^{k}=0$ (1.2)

is (non-trivially) partition regular over the positive integers if and only if
there exists a non-empty set $I\subset[s]$ such that $\sum_{i\in I}c_{i}=0$.
Moreover, we may take $s_{0}(2)=5$, $s_{0}(3)=8$ and

$s_{0}(k)=k\left(\log k+\log\log k+2+O(\log\log k/\log k)\right).$ (1.3)

Notice that Rado’s criterion for a linear equation shows that the condition
$\sum_{i\in I}c_{i}=0$ is necessary for (1.2) to be partition regular. The
content of Theorem 1.3 is that this condition is also sufficient.

For higher-degree equations one cannot avoid the assumption of some lower
bound on the number of variables, as the example of the Fermat equation
demonstrates. Given current knowledge on the solubility of diagonal
Diophantine equations [Woo92], the bound (1.3) is at the cutting edge of
present technology. Indeed, it is unlikely that one could improve this
condition without making an analogous breakthrough in Waring’s problem, since
partition regularity implies the existence of a non-trivial integer solution
to the equation (1.2).

We remark that one could use the methods of this paper to establish the weaker
but explicit bound

$s_{0}(k)\leqslant k^{2}+1.$

This follows by utilising the work of Bourgain–Demeter–Guth [BDG16] on
Vinogradov’s mean value theorem, eschewing smooth numbers, as in [Cho17].

We are also able to establish the sufficiency of Rado’s criterion for other
sparse arithmetic sets of interest, such as logarithmically-smooth numbers and
shifted squares. For these sets we avoid certain local issues which must be
surmounted for perfect powers, and thereby prove stronger quantitative
variants of partition regularity, analogous to work of Frankl, Graham and Rödl
[FGR88] counting monochromatic solutions to a linear equation.

######  Theorem 1.4 (Supersaturation111The term ‘supersaturation’, from
extremal combinatorics, describes when we wish to “determine the minimum
number of copies of a particular substructure in a combinatorial object of
prescribed size” [NSS18]. For us, the substructure is defined by a Diophantine
equation. in squares minus one).

Let $c_{1},\dots,c_{s}\in\mathbb{Z}\setminus\left\\{0\right\\}$ with
$s\geqslant 5$ and suppose that $\sum_{i\in I}c_{i}=0$ for some non-empty $I$.
Define the set of shifted squares by

$S:=\left\\{x^{2}-1:x\in\mathbb{Z}\right\\}.$

For any $r\in\mathbb{N}$ there exist $c_{0}>0$ and $N_{0}\in\mathbb{N}$ such
that for any $N\geqslant N_{0}$ if we have an $r$-colouring of $S$ then

$\\#\Bigl{\\{}x\in(S\cap[N])^{s}:\sum_{i}c_{i}x_{i}=0\text{ and x is
monochromatic}\Bigr{\\}}\\\ \geqslant c_{0}|S\cap[N]|^{s}N^{-1}.$ (1.4)

######  Remark 1.5.

For the set of squares minus one, the upper bound

$\\#\Bigl{\\{}x\in(S\cap[N])^{s}:\sum_{i}c_{i}x_{i}=0\Bigr{\\}}\ll|S\cap[N]|^{s}N^{-1}$

follows from an application of the Hardy–Littlewood circle method [Vau97].
Hence, the number of monochromatic solutions is within a constant (depending
only on the number of colours) of the maximum possible.

We prove Theorem 1.4 in Part III together with an analogous result for
logarithmically-smooth numbers.

######  Definition 1.6 ($R$-smooth numbers).

A number is _$R$ -smooth_ if all of its prime factors are at most $R$. Denote
the set of $R$-smooths in $[N]$ by

$S(N;R):=\left\\{x\in[N]:p\mid x\implies p\leqslant R\right\\}.$

When $R$ is logarithmic in $N$, of the form $R=\log^{K}N$, then

$|S(N;\log^{K}N)|\sim N^{1-K^{-1}+o(1)}\qquad(N\to\infty),$

so logarithmically-smooth numbers constitute a polynomially sparse arithmetic
set [Gran08].

A recent breakthrough of Harper [Har16] gives a count of the number of
solutions to an additive equation in logarithmically-smooth numbers. We are
able to extend this count to finite colourings as follows.

######  Theorem 1.7 (Supersaturation in the smooths).

Let $c_{1},\dots,c_{s}\in\mathbb{Z}\setminus\left\\{0\right\\}$, and suppose
that $\sum_{i\in I}c_{i}=0$ for some non-empty $I$. Then for any
$r\in\mathbb{N}$ there exist $c_{0}>0$ and $C,N_{0}\in\mathbb{N}$ such that if
$N\geqslant N_{0}$, $R\geqslant\log^{C}N$ and $S(N;R)$ is $r$-coloured then

$\\#\Bigl{\\{}x\in S(N;R)^{s}:\sum_{i}c_{i}x_{i}=0\text{ and x is
monochromatic}\Bigr{\\}}\\\ \geqslant c_{0}|S(N;R)|^{s}N^{-1}.$ (1.5)

As for shifted squares, we emphasise that the corresponding upper bound in
(1.5) follows (when $s\geqslant 3$) from the methods of Harper [Har16].

####  1.1. Non-triviality

It may be that (1.2) possesses a wealth of monochromatic solutions for
‘trivial’ reasons. For instance, if $c_{1}+\dots+c_{s}=0$ then taking
$x_{1}=\dots=x_{s}$ yields many uninteresting solutions. We have delineated
between partition regularity and non-trivial partition regularity to ensure
that Rado’s criterion still has content in such a situation. However, since
Rado’s criterion is necessary for ‘trivial’ partition regularity, the two
notions are in fact equivalent.

####  1.2. Previous work

To the knowledge of the authors, work on non-linear partition regularity
begins with papers of Furstenberg and Sárközy [Fur77, Sár78], independently
resolving a conjecture of Lovász—a line of investigation which culminates in
the polynomial Szemerédi theorem of Bergelson–Leibman [BL96], proved using
ergodic methods. Such methods have also established colouring results for
which no density analogue exists, such as partition regularity of the equation
$x-y=z^{2}$ [Ber96, p.53]. Interestingly, the story is more complicated for
the superficially similar equation $x+y=z^{2}$ studied in [KS06, CGS12, GL16,
Pac18].

A recent breakthrough of Moreira [Mor17] resolves a longstanding conjecture of
Hindman [Hin79], proving partition regularity of the equation $x+y^{2}=yz$.
More intuitively: in any finite colouring of the positive integers there
exists a monochromatic configuration of the form $\left\\{a,a+b,ab\right\\}$.
This result is a consequence of a general theorem which also yields partition
regularity of equations of the form
$x_{0}=c_{1}x_{1}^{2}+\dots+c_{s}x_{s}^{2}$, subject to the condition that
$c_{1}+\dots+c_{s}=0$.

Notice that all of the above results involve an equation with at least one
linear term. There are fewer results in the literature concerning genuinely
non-linear equations such as (1.2). Certain diagonal quadrics are dealt with
in Lefmann [Lef91, Fact 2.8], using Rado’s theorem to locate a long
monochromatic progression whose common difference possesses a (well-chosen)
multiple of the same colour. This results in the following sufficient
condition for partition regularity.

######  Lefmann’s criterion.

Let $c_{1},\dots,c_{s}\in\mathbb{Z}\setminus\left\\{0\right\\}$, and suppose
that $\sum_{i\in I}c_{i}=0$ with $I\neq\emptyset$. Moreover, suppose that the
auxiliary system

$\begin{split}\Bigl{(}\sum_{i\notin I}c_{i}\Bigr{)}x_{0}^{2}+\sum_{i\in
I}c_{i}x_{i}^{2}&=0,\\\ \sum_{i\in I}c_{i}x_{i}&=0\end{split}$ (1.6)

possesses a rational solution with $x_{0}\neq 0$. Then the equation

$c_{1}x_{1}^{2}+\dots+c_{s}x_{s}^{2}=0$ (1.7)

is partition regular.

This result reduces the combinatorial problem of establishing partition
regularity of (1.7) to a task in number theory: find a rational point of a
certain form on a variety determined by a diagonal quadric and linear
equation. In Appendix F we derive general algebraic criteria guaranteeing such
a rational point using the Hardy–Littlewood circle method.

######  Theorem 1.8 (Lefmann + Hardy–Littlewood circle method).

Let $c_{1},\dots,c_{s}\in\mathbb{Z}\setminus\left\\{0\right\\}$, and suppose
that $\sum_{i\in I}c_{i}=0$ with $I\neq\emptyset$. Suppose in addition that
$|I|\geqslant 6$ and at least two $c_{i}$ are positive and at least two are
negative. Then

$c_{1}x_{1}^{2}+\dots+c_{s}x_{s}^{2}=0$ (1.8)

is partition regular.

This result does not encompass all equations amenable to Lefmann’s criterion:
fewer variables may suffice, for instance

$x^{2}+9y^{2}=2z^{2}+8w^{2}\qquad\text{or}\qquad 4x^{2}+y^{2}=2z^{2}+2w^{2}.$

We emphasise that Lefmann’s criterion cannot hope to be a necessary condition
for partition regularity, as there are partition regular equations for which
the auxiliary Lefmann system (1.6) has no rational point of the required form.
Such equations include the generalised Pythagorean equation (1.1), as well as
the ‘convex’ equation

$x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}=4x_{5}^{2}$ (1.9)

addressed in [BP17].

In the same article, Lefmann [Lef91, Theorem 2.6] established Rado’s criterion
for reciprocals.

######  Theorem 1.9 (Lefmann).

Let $c_{1},\ldots,c_{s}\in{\mathbb{Z}}\setminus\\{0\\}$. Then

$\sum_{i=1}^{s}c_{i}x_{i}^{-1}=0$

is partition regular over ${\mathbb{N}}$ if and only if $\sum_{i\in I}c_{i}=0$
for some non-empty $I\subset[s]$.

This demonstrates the partition regularity of

$\frac{1}{x}+\frac{1}{y}=\frac{1}{z},$

answering a question of Erdős and Graham.

If one is prepared to relax the definition of partition regularity, so that
certain variables are not constrained to receive the same colour as the
remainder, then specific homogeneous equations of arbitrary degree are dealt
with in Frantzikinakis–Host [FH14]. For instance, one consequence of their
methods is that in any finite colouring of the positive integers there exist
distinct $x,y$ of the same colour, along with $\lambda$ (possibly of a
different colour) such that

$9x^{2}+16y^{2}=\lambda^{2}.$ (1.10)

However for these techniques to succeed, not only must one variable of (1.10)
be free to take on any colour, but it is also necessary for the solution set
to possess a well-factorable parametrisation, allowing for the theory of
multiplicative functions to come into play.

When the coefficients of (1.2) sum to zero, partition regularity follows
easily, since any element of the diagonal constitutes a monochromatic
solution. However, there are results in the literature which also guarantee
_non-trivial_ partition regularity in this situation, provided that
$s\geqslant k^{2}+1$. This was first established for quadrics in [BP17] and
for general $k$ in [Cho17]. In fact in [Cho17] it is established that, under
these assumptions, dense subsets of the _primes_ contain many solutions to
(1.2). Density results were obtained for non-diagonal quadratic forms in at
least 9 variables by Zhao [Zha17], subject to the condition that the
corresponding matrix has columns which sum to zero.

We believe that when the solution set of a given equation contains the
diagonal it is more robust with respect to certain local issues—indeed one
expects dense sets (such as congruence classes) to contain solutions under
this assumption. As a consequence, the local issues for such equations are
easier to handle using elementary devices, such as passing to a well-chosen
subprogression. The novelty in our methods is that for general equations,
instead of tackling the somewhat thorny local problem head on, we show how we
may assume our colouring possesses a certain homogeneous structure, and this
structure allows the same devices available in the dense regime to come into
play.

We remark that it appears to be a challenging problem to decrease $s_{0}(k)$
substantially below $k^{2}+1$ for the density analogue of Theorem 1.3. In
order to show that $s_{0}(k)=(1+o(1))k\log k$ is admissible in our partition
result we make heavy use of the fact that a colouring of the positive integers
induces a colouring of the smooth positive integers, and we obtain a
monochromatic solution to our equation in the smooths. Sets of positive
density, however, may not contain any smooth numbers. We are therefore in the
curious situation where we can prove that relatively dense sets of smooth
numbers possess solutions to certain diagonal equations, but cannot say the
same for dense sets of integers.

It is interesting to compare our results with partition regularity results
over the primes. Here congruence obstructions mean that one cannot hope to
establish a Rado-type criterion. For example, a parity obstruction prohibits
Schur’s equation from being partition regular over the primes. The situation
is markedly different if one considers modifications of the primes with no
local obstructions, such as the set of primes minus one. Partition regularity
of the Schur equation over this set was established by Li–Pan [LP12], then
generalised to the full Rado criterion for systems of linear equations by Lê
[Lê12]. This latter result utilised the full strength of Green and Tao’s
asymptotic for linear equations in primes [GT10a], together with a
characterisation of so called ‘large’ sets due to Deuber [Deu73]. Neither of
these tools are available, or reasonable to expect, for $k$th powers.

The argument of Li–Pan for Schur’s theorem in primes minus one is a direct
application of the Fourier-analytic transference principle pioneered by Green
[Gre05], elucidated by the same author in the context of partition regularity
in a comment222https://goo.gl/Yjookp on MathOverflow. This approach cannot
hope to succeed for perfect powers, at least when the coefficients of the
equation do not sum to zero, since one can no longer pass to the same (affine)
subprogression in all of the variables. The introduction of homogeneous sets
(Definition 2.2) allows us to circumvent these difficulties. However, for
squares minus one, or smooth numbers, one need only pass to projective
subprogressions when enacting the transference principle. The methods of Part
III therefore use a direct form of the transference principle analogous to
Li–Pan. We include the argument to illustrate the subtleties which must be
overcome for perfect powers.

####  1.3. Notation

We adopt the convention that $\varepsilon$ denotes an arbitrarily small
positive real number, so its value may differ between instances. We shall use
Vinogradov and Bachmann–Landau notation: for functions $f$ and positive-valued
functions $g$, write $f\ll g$ or $f=O(g)$ if there exists a constant $C$ such
that $|f(x)|\leqslant Cg(x)$ for all $x$. At times we opt for a more explicit
approach, using $C$ to denote a large absolute constant (whose value may
change from line to line), and $c$ to denote a small positive absolute
constant. The notation $f\asymp g$ is the same as $f\ll g\ll f$. For
$Y\geqslant 1$, let $[Y]=\\{1,2,\ldots,\lfloor Y\rfloor\\}$. We write
$\mathbb{T}$ for the torus $\mathbb{R}/\mathbb{Z}$. For $x\in\mathbb{R}$ and
$q\in\mathbb{N}$, put $e(x)=e^{2\pi ix}$ and $e_{q}(x)=e^{2\pi ix/q}$. If $S$
is a set, we denote the cardinality of $S$ by $|S|$ or $\\#S$.

Throughout we use counting measure on $\mathbb{Z}^{d}$ and Haar probability
measure on the dual $\mathbb{T}^{d}:=\mathbb{R}^{d}/\mathbb{Z}^{d}$. So if
$f,g:\mathbb{Z}^{d}\to\mathbb{C}$ have finite support then

$\left\|f\right\|_{p}:=\begin{cases}\left(\sum_{x}|f(x)|^{p}\right)^{1/p}&\text{if
}p<\infty\\\ \mathrm{max}_{x}|f(x)|&\text{if }p=\infty.\end{cases}$

Define the Fourier transform of $f$ by

$\hat{f}(\alpha):=\sum_{x}f(x)e(\alpha\cdot x).$

We endow $\mathbb{T}^{d}$ with the metric
$({\alpha},{\beta})\mapsto\left\|\alpha-\beta\right\|$, where

$\left\|\alpha\right\|:=\sum_{i=1}^{d}\min_{n\in\mathbb{Z}}|\alpha_{i}-n|.$

#### Funding

SC was supported by EPSRC Programme Grant EP/J018260/1. SL is supported by Ben
Green’s Simons Investigator Grant, number 376201. A portion of this project
was completed whilst the authors were in residence in Berkeley, California
during the Spring 2017 semester: SC and SL at the Mathematical Sciences
Research Institute, and SP at the Simons Institute for the Theory of
Computing. During this time SC was supported by the National Science
Foundation under Grant No. DMS-1440140.

#### Acknowledgements

The authors have benefited greatly from Trevor Wooley’s knowledge of discrete
restriction theory over smooth numbers. Thanks to Ben Barber for enquiring
about Rado’s criterion over squares during a seminar at the University of
Bristol, and for recording this question on
MathOverflow333https://goo.gl/Yjookp. Thanks to Xuancheng Shao for the idea of
colouring smooth numbers. We are indebted to Jonathan Chapman for corrections,
clarifications and numerous useful comments on an earlier version of this
manuscript.

###  2\. Methods

All of the essential ideas required for Theorem 1.3 are contained in the proof
of the following finitary analogue of Theorem 1.1, whose deduction is the
focus of this section.

######  Theorem 2.1 (Finitary Schur-type theorem in the squares).

For any $r\in\mathbb{N}$ there exists $N_{0}=N_{0}(r)$ such that for any
$N\geqslant N_{0}$ the following is true. Given an $r$-colouring of $[N]$
there exists a monochromatic solution to the equation
$x_{1}^{2}-x_{2}^{2}=x_{3}^{2}+x_{4}^{2}+x_{5}^{2}.$

Inspired by work of Cwalina–Schoen [CS17] and Green–Sanders [GS16], we derive
Theorem 2.1 in §4 by an induction on the number of colours, in combination
with a density result concerning what we have termed _homogeneous sets_.

######  Definition 2.2 (Homogeneous set).

Call a set $B$ of positive integers _$M$ -homogeneous_ if for any
$q\in\mathbb{N}$ we have

$\begin{split}B\cap q\cdot[M]\neq\emptyset.\end{split}$ (2.1)

Given a set $S\subset\mathbb{N}$, we say that $B$ is $M$-_homogeneous in $S$_
if (2.1) holds for all homogeneous progressions $q\cdot[M]$ contained in $S$.
Notice that the latter does not require that $B\subset S$.

Chapman [Cha18] has observed that this is a quantitative variant of what it
means to be _multiplicatively syndetic_ (see Bergelson–Glasscock [BG16]), and
that such sets appear to have a number of interesting properties in regard to
the partition regularity of homogeneous systems of polynomial equations.

We leave it as an exercise for the reader to verify that if $B$ is an
$M$-homogeneous set then $|B\cap[N]|\gg_{M}N$ for $N$ sufficiently large in
terms of $M$, so homogeneous sets are dense (see Lemma 4.2). In fact they are
dense on all sufficiently long homogeneous arithmetic progressions.

We demonstrate the utility of this definition by giving a proof of Schur’s
theorem. The argument is prototypical for that employed in the proof of
Theorem 2.1.

###### Proof of Schur’s theorem.

We induct on the number of colours $r$ to show that there exists
$N_{r}\in{\mathbb{N}}$ such that however $[N_{r}]$ is $r$-coloured there exist
$x_{1},x_{2},x_{3}\in[N_{r}]$ all of the same colour with $x_{1}+x_{2}=x_{3}$.

The base case of 1-colourings follows on taking $N_{1}=2$, so we may assume
that $r\geqslant 2$. Let $N$ be a large positive integer, whose size
(depending on $r$) is to be determined, and fix an $r$-colouring

$[N]=C_{1}\cup\dots\cup C_{r}.$

Set $M:=N_{r-1}$ and consider two possibilities.

The inhomogeneous case: Some colour class $C_{i}$ is not $M$-homogeneous in
$[N]$. From the definition of homogeneity it follows that there exists a
positive integer $q$ such that $q\cdot[M]\subset[N]$ and $q\cdot[M]\cap
C_{i}=\emptyset$. On setting $C_{j}^{\prime}:=\left\\{x\in[M]:qx\in
C_{j}\right\\}$ we induce an $(r-1)$-colouring

$[M]=\bigcup_{j\neq i}C_{j}^{\prime}.$

Since $M=N_{r-1}$ it follows from our induction hypothesis that there exist
$x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime}\in C_{j}^{\prime}$ such that
$x_{1}^{\prime}+x_{2}^{\prime}=x_{3}^{\prime}$. Schur’s theorem follows in
this case on setting $x_{t}:=qx_{t}^{\prime}$ for $t=1,2,3$.

The homogeneous case: All colour classes are $M$-homogeneous in $[N]$. In this
case it turns out that every colour class contains a solution to the Schur
equation, provided that $N$ is sufficiently large in terms of $r$. To prove
this we invoke the following.

######  Claim.

For any $\delta>0$ and $M\in\mathbb{N}$ there exists $N_{0}=N_{0}(\delta,M)$
such that for any $N\geqslant N_{0}$ if $A\subset[N]$ has $|A|\geqslant\delta
N$ and $B\subset[N]$ is $M$-homogeneous in $[N]$ then there exist
$x,x^{\prime}\in A$ and $y\in B$ such that $x-x^{\prime}=y$.

The claim settles the homogeneous case of Schur’s theorem on taking $A=B$ to
be any colour class, since $M$-homogeneous sets have density at least
$M^{-2}+o(1)$ in $[N]$ (see Lemma 4.2; one could have alternatively taken the
largest colour class).

To prove the claim we invoke Szemerédi’s theorem!444The claim itself is not
deep, for instance it is readily obtained from [CRS07, Theorem 4]. Our proof
is designed to set the stage for the general setting of Part II, when we will
invoke the multidimensional polynomial Szemerédi theorem of Bergelson and
Leibman [BL96]. This yields $N_{0}=N_{0}(\delta,M)$ such that for any
$N\geqslant N_{0}$ if $A\subset[N]$ with $|A|\geqslant\delta N$ then $A$
contains an arithmetic progression of length $M+1$, so that there exist $x$
and $q>0$ for which

$x,\quad x+q,\quad x+2q,\quad\dots,\quad x+Mq\quad\in A.$

Notice that $q\cdot[M]\subset[N]$, so $M$-homogeneity of $B$ implies that
there exists $y\in q\cdot[M]\cap B$. Taking $x^{\prime}=x+y$ establishes the
claim and completes our proof of Schur’s theorem. ∎

It may seem excessive to employ a density result in the proof of a colouring
result, since (typically) density results lie deeper and require more work to
prove.555One can give an alternative argument for Schur’s theorem based on
these ideas, replacing Szemerédi’s theorem with van der Waerden’s. However,
this approach does not seem to generalise to the non-linear situation. We have
described this approach to motivate our proof of Theorem 1.1, which uses an
analogous non-linear density result. We also believe the proof offers an
alternative reason for _why_ Schur’s theorem is true: there is always a long
homogeneous arithmetic progression on which one of the colour classes is
multiplicatively syndetic. This exemplifies a well-used philosophy in Ramsey
theory that underlying every partition result there is some notion of
largeness.

To prove partition regularity of the generalised Pythagorean equation we
induct on the number of colours as in our proof of Schur’s theorem. The
inhomogeneous case follows with minimal change to the argument. In the
remaining case we may assume that all colour classes are homogeneous. In this
situation we are able to show that every colour class contains many solutions
to our non-linear equation by employing the following density result.

######  Theorem 2.3 (Non-linear homogeneous Sárközy).

For any $\delta>0$ and $M\in\mathbb{N}$ there exist $N_{0}$ and $c_{0}>0$ such
that for any $N\geqslant N_{0}$ the following holds. Let $A\subset[N]$ have
density at least $\delta$ in $[N]$, and let $B$ be an $M$-homogeneous subset
of the positive integers. Then

$\begin{split}\\#\left\\{({\mathbf{x}},{\mathbf{y}})\in A^{2}\times
B^{3}:x_{1}^{2}-x_{2}^{2}=y_{1}^{2}+y_{2}^{2}+y_{3}^{2}\right\\}\geqslant
c_{0}N^{3}.\end{split}$

Using Green’s Fourier-analytic transference principle [Gre05], as elucidated
for squares in [BP17, Pre17a], the deduction of Theorem 2.3 is reduced (in
§§5–6) to a linear analogue in which the squares have been removed from the
dense variables. This can be thought of as a generalisation of the
Furstenberg–Sárközy theorem [Fur77, Sár78], extended to homogeneous sets.

######  Theorem 2.4 (Supersaturated homogeneous Sárközy).

For any $\delta>0$ and $M\in\mathbb{N}$ there exist $N_{0},c_{0}>0$ such that
for any $N\geqslant N_{0}$ the following holds. Let $A\subset[N]$ have density
at least $\delta$ in $[N]$ and let $B$ be an $M$-homogeneous subset of the
positive integers. Then there are at least $c_{0}N^{\frac{5}{2}}$ tuples
$(x,y)\in A^{2}\times B^{3}$ satisfying the equation

$\begin{split}x_{1}-x_{2}=y_{1}^{2}+y_{2}^{2}+y_{3}^{2}.\end{split}$ (2.2)

Our ability to remove the squares from the dense variables is intrinsically
linked to the fact that the coefficients corresponding to these variables sum
to zero. One consequence of this is that we may restrict all of the dense
variables to lie in the same congruence class, without destroying solutions to
the equation in the process.

Theorem 2.4 is ultimately derived (in §8) from the following result, which is
both more general and at the same time slightly weaker than Theorem 2.4. It is
weaker in that it yields only one solution to (2.2), yet it applies to the
more general context of multidimensional sets of integers. The increase in
dimension allows us to deduce a supersaturation result for (2.2) by
bootstrapping the existence of a single solution to the existence of many
solutions, using an averaging argument first implemented by Varnavides
[Var59].

######  Theorem 2.5 (Multidimensional homogeneous Sárközy).

For any $\delta>0$ and $d,M\in\mathbb{N}$ there exists $N_{0}$ such that for
any $N\geqslant N_{0}$ the following holds. If $A\subset[N]^{d}$ is at least
$\delta$-dense in $[N]^{d}$ and $B_{1},\dots,B_{d}$ are $M$-homogeneous sets
of positive integers, then there exist $x,x^{\prime}\in A$ and $y_{1}\in
B_{1},\dots,y_{d}\in B_{d}$ such that

$x-x^{\prime}=(y_{1}^{2},\dots,y_{d}^{2}).$ (2.3)

In §7 this theorem is proved using the Fourier-analytic density increment
strategy pioneered by Roth [Rot53], a proof which yields quantitative bounds
on $N_{0}$. One can deduce the qualitative statement in a few lines from the
multidimensional polynomial Szemerédi theorem of Bergelson and Leibman [BL96],
see Corollary 9.1. The general Rado criterion of Theorem 1.3 requires a more
complicated density result for which Fourier analysis does not appear
sufficient and which therefore necessitates the invocation of this deep
result.

###  3\. Open problems

####  3.1. The supersaturation result

Frankl, Graham and Rödl [FGR88] establish that for any $r$-colouring of $[N]$,
a linear equation $\sum_{i=1}^{s}c_{i}x_{i}=0$ satisfying Rado’s criterion has
$\gg_{r}N^{s-1}$ monochromatic solutions. Our methods do not yield the
analogous supersaturation result for equation (1.2). We instead find that if
$N$ is sufficiently large in terms of $M$ then $[N]$ contains a homogeneous
arithmetic progression of length $M$ which possesses at least $\gg_{r}M^{s-k}$
monochromatic solutions to (1.2). This deficiency is an artefact of our method
where, to avoid tackling certain local issues, we iteratively pass to a well-
chosen homogeneous subprogression.

It may be possible to establish a supersaturation result if one is prepared to
replace the homogeneous arithmetic progressions appearing in this paper with
quadratic Bohr sets. Informally, let us call a set _quadratic Bohr
homogeneous_ if it has large intersection with all quadratic Bohr sets
(centred at zero). Then our methods reduce to showing that if $A$ is a dense
subset of a quadratic Bohr set and if $B$ is quadratic Bohr homogeneous, then
there are many solutions to the equation

$x_{1}^{2}-x_{2}^{2}=y_{1}^{2}+y_{2}^{2}+y_{3}^{2}$

with $x_{i}\in A$ and $y_{i}\in B$. A promising strategy for obtaining such a
result proceeds by decomposing $1_{A}$ according to a variant of the
arithmetic regularity lemma developed by Green and Tao [GT10b]. It is in fact
this strategy which informs the simpler approach developed in this paper.

####  3.2. Quantitative bounds

Define the _Rado number_ (see [GRS90, p.103]) of the equation (1.2) to be the
smallest positive integer $R_{\mathbf{c},k}(r)$ such that any $r$-colouring of
the interval $\left\\{1,2,\dots,R_{\mathbf{c},k}(r)\right\\}$ results in at
least one monochromatic tuple $(x_{1},\dots,x_{s})$ satisfying (1.2) with all
$x_{i}$ distinct. For linear equations, this quantity has been extensively
studied by Cwalina and Schoen [CS17], with near optimal bounds extracted for
certain choices of coefficients. In [BP17] it is shown that when $k=2$,
$c_{1}+\dots+c_{s}=0$ and $s\geqslant 5$ then there exists a constant
$C_{\mathbf{c}}$ such that

$R_{\mathbf{c},2}(r)\leqslant\exp\exp\exp(C_{\mathbf{c}}r).$ (3.1)

It is feasible that the methods of this paper lead to quantitative bounds for
the Rado number of the equation (1.2) provided that there exist coefficients
with $c_{i}=-c_{j}$. In this situation, all of the results we employ in our
argument can be proved using Fourier-analytic methods, where the quantitative
machinery is well-developed. However, these bounds are sure to be of worse
quality than (3.1) due to our induction on the number of colours, a feature of
the argument not present in [BP17].

If there are no coefficients satisfying $c_{i}=-c_{j}$, then any hope of
extracting quantitative bounds on $R_{\mathbf{c},k}(r)$ is diminished, since
the methods of this paper invoke the multidimensional (polynomial) Szemerédi
theorem, a result for which there are no quantitative bounds presently known.
It would be interesting if one could avoid calling on such a deep result.

####  3.3. Systems of equations

Rado [Rad33] characterised when _systems_ of linear equations are partition
regular. This criterion says that a system $Ax=0$ is partition regular if and
only if the integer matrix $A$ satisfies the so-called _columns condition_
(see [GRS90, p.73]). We conjecture that the columns condition is sufficient
for systems of equations in $k$th powers, provided that the number of
variables is sufficiently large in terms of the degree and the number of
equations, and that the matrix of coefficients is sufficiently generic. For
instance, in analogy with results of Cook [Coo71] we posit the following.

######  Conjecture 3.1.

Let $a_{1},\ldots,a_{s},b_{1},\ldots,b_{s}\in{\mathbb{Z}}\setminus\\{0\\}$.
Then the system of equations

$\displaystyle a_{1}x_{1}^{2}+\dots+a_{s}x_{s}^{2}$ $\displaystyle=0$
$\displaystyle b_{1}x_{1}^{2}+\dots+b_{s}x_{s}^{2}$ $\displaystyle=0$

is non-trivially partition regular, provided that

  * (i)

$s\geqslant 9$;

  * (ii)

the matrix $A:=\begin{pmatrix}a_{1}&\dots&a_{s}\\\
b_{1}&\dots&b_{s}\end{pmatrix}$ satisfies the columns condition;

  * (iii)

for any real numbers $\lambda,\mu$ that are not both zero, the vector
$(\lambda,\mu)A$ has at least five non-zero entries, not all of which have the
same sign.

Condition (ii) is certainly necessary for partition regularity, by Rado’s
criterion. Weakening conditions (i) and (iii) would presumably require
improvements in circle method technology.

####  3.4. Roth with logarithmically-smooth common difference

Using the arguments of §9 one can prove the following (see Remark 9.3).

######  Theorem 3.2.

If $A\subset[N]$ lacks a three-term arithmetic progression with $R$-smooth
common difference, where $10\leqslant R\leqslant N$, then

$|A|\ll N\frac{(\log\log R)^{4}}{\log R}.$ (3.2)

When $R=\log^{K}N$ for some fixed absolute constant $K$, the set of $R$-smooth
numbers in $[N]$ has cardinality $N^{1-K^{-1}+o(1)}$. Common differences
arising from such a set are therefore polynomially sparse, and Theorem 3.2
results in a density bound of the form $(\log\log N)^{-1+o(1)}$.

The argument for Theorem 3.2 really only uses the fact that the $R$-smooths
contain the interval $[R]$, and that $A$ must be dense on a translate of this
set, so we are in fact locating a ‘short’ arithmetic progression. Since smooth
arithmetic progressions are much more abundant than short arithmetic
progressions, it would be interesting if one could obtain a better density
bound by exploiting this.

The only other bound known for Roth’s theorem with common difference arising
from a polynomially sparse arithmetic set can be found in [Pre17b], which
deals with perfect $k$th powers. This also results in a double logarithmic
bound, of the form $(\log\log N)^{-c_{k}}$ for some small $c_{k}>0$. Breaking
the double logarithmic barrier for the smooth Roth problem may be a tractable
intermediate step towards improving bounds in the polynomial Roth theorem.

##  Part I The generalised Pythagorean equation

In this part we establish partition regularity of the 5-variable Pythagorean
equation $x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}=x_{5}^{2}$. The proof
contains all of the essential ideas required for Theorem 1.3 but is more
transparent, avoiding notational complexities and the need for smooth number
technology. Unlike the general case, we show that all requisite steps can be
established using Fourier analysis, avoiding recourse to deeper results
involving higher-order uniformity and the multidimensional Szemerédi theorem.
This may be of use to those interested in quantitative bounds and
supersaturation.

Throughout this part we assume familiarity with the high-level schematic
outlined in §2.

###  4\. Induction on colours

We first derive Theorem 2.1 from Theorem 2.3 by induction on the number of
colours. We deduce Theorem 2.3 from Theorem 2.4 in §§5–6, and prove Theorem
2.4 in §§7–8.

####  4.1. The inductive base: one colour

######  Definition 4.1 ($T$ counting operator).

Given functions $f_{1},\dots,f_{s}:\mathbb{Z}\to\mathbb{C}$ with finite
support, define the counting operator

$\displaystyle
T(f_{1},\dots,f_{5}):=\sum_{x_{1}^{2}-x_{2}^{2}=x_{3}^{2}+x_{4}^{2}+x_{5}^{2}}f_{1}(x_{1})f_{2}(x_{2})f_{3}(x_{3})f_{4}(x_{4})f_{5}(x_{5}).$

We write $T(f)$ for $T(f,f,\dots,f)$.

By Theorem B.1, there exist $N_{1}\in\mathbb{N}$ and $c_{1}>0$ such that for
$N\geqslant N_{1}$ we have

$T(1_{[N]})\geqslant c_{1}N^{3}.$

Since the latter quantity is positive, Theorem 2.1 follows for 1-colourings
(the base case of our induction).

####  4.2. The inductive step

Let $[N]=C_{1}\cup\dots\cup C_{r}$ be an $r$-colouring. We split our proof
into two cases depending on the homogeneity of the $C_{i}$.

#####  4.2.1. The inhomogeneous case

Let $M:=N_{0}(r-1)$ be the quantity whose existence is guaranteed by our
inductive hypothesis. We first suppose that some $C_{i}$ is not
$M$-homogeneous in $[N]$ (see Definition 2.2). Consequently there exists
$q\in\mathbb{N}$ such that

$\begin{split}q\cdot[M]\subset[N]\quad\text{and}\quad C_{i}\cap
q\cdot[M]=\emptyset.\end{split}$ (4.1)

For $j\neq i$ let us define

$C_{j}^{\prime}:=\left\\{x\in[M]:qx\in C_{j}\right\\}.$

Then it follows from (4.1) that $\bigcup_{j\neq i}C_{j}^{\prime}=[M]$. By the
induction hypothesis, there exist $y_{k}\in C_{j}^{\prime}$ for some $j\neq i$
such that $y_{1}^{2}-y_{2}^{2}=y_{3}^{2}+y_{4}^{2}+y_{5}^{2}$. Setting
$x_{k}:=qy_{k}$ we obtain elements of $C_{j}$ which solve the generalised
Pythagorean equation.

#####  4.2.2. The homogeneous case

In this case every colour class is $M$-homogeneous in $[N]$. We claim that
Theorem 2.3 then implies that each $C_{i}$ contains a solution to the
generalised Pythagorean equation. First we observe that each colour class is
dense.

######  Lemma 4.2 (Homogeneous sets are dense).

If $B\subset[N]$ is $M$-homogeneous in $[N]$ then

$|B|\geqslant\frac{1}{M}\left\lfloor\frac{N}{M}\right\rfloor.$

###### Proof.

We proceed by a variant of Varnavides averaging [Var59]. For each $q\leqslant
N/M$ the definition of homogeneity gives

$B\cap q\cdot[M]\neq\emptyset.$

Summing over $q$ then yields

$\sum_{q\leqslant N/M}|B\cap q\cdot[M]|\geqslant\left\lfloor
N/M\right\rfloor.$

Interchanging the order of summation, we see that

$\displaystyle\sum_{x\in
B}\\#\left\\{(q,m)\in[N/M]\times[M]:x=qm\right\\}\geqslant\left\lfloor
N/M\right\rfloor.$

The result follows on noting that

$\\#\left\\{(q,m)\in[N/M]\times[M]:x=qm\right\\}\leqslant M.$

∎

Setting $A=B=C_{i}$ in Theorem 2.3 we deduce that if $N\geqslant N_{0}(M)$
then

$T(1_{C_{r}})\geqslant c_{0}(M)N^{s-k}.$

Since the latter quantity is positive the induction step follows, completing
the proof of Theorem 2.1. Note that a quantity dependent on $M=N_{0}(r-1)$ is
ultimately dependent only on $r$.

###  5\. A pseudorandom Furstenberg–Sárközy theorem

In §4 we reduced partition regularity of the generalised Pythagorean equation
(1.1) to Theorem 2.3. In §6 we deduce the latter result from Theorem 2.4. To
prepare the ground for this deduction, we first modify Theorem 2.4 to
accommodate sets which are relatively dense in a suitably pseudorandom set.
The goal is to find the weakest possible pseudorandomness conditions required
for such a result to hold. Our primary quantity of interest is the following.

######  Definition 5.1 ($T_{1}$ counting operator).

Given functions $f_{1},f_{2}:\mathbb{Z}\to\mathbb{C}$ with finite support and
$B\subset\mathbb{Z}$, define

$\displaystyle
T_{1}(f_{1},f_{2};B):=\sum_{\begin{subarray}{c}x_{1}-x_{2}=y_{1}^{2}+y_{2}^{2}+y_{3}^{2}\end{subarray}}f_{1}(x_{1})f_{2}(x_{2})1_{B}(y_{1})1_{B}(y_{2})1_{B}(y_{3}).$

We write $T_{1}(f;B)$ for $T_{1}(f,f;B)$ and $T_{1}(A;B)$ for
$T_{1}(1_{A};B)$.

We begin by showing how Theorem 2.4 implies a result in which the indicator
function $1_{A}$ can be replaced by a function $f:[N]\to[0,1]$ with
sufficiently large average.

######  Lemma 5.2 (Functional Sárközy).

For any $\delta>0$ and $M\in\mathbb{N}$ there exists $N_{0}\in\mathbb{N}$ and
$c_{0}>0$ such that for any $N\geqslant N_{0}$ the following holds. Let
$f:[N]\to[0,1]$ with $\left\|f\right\|_{1}\geqslant\delta N$ and let $B$ be an
$M$-homogeneous subset of the positive integers. Then

$\begin{split}T_{1}(f;B)\geqslant c_{0}N^{\frac{5}{2}}.\end{split}$

###### Proof.

Let $A=\\{x\in[N]:f(x)\geqslant{\delta}/2\\}$. As
$\|f\|_{1}\geqslant{\delta}N$ and $f\leqslant 1$, we have
$|A|\geqslant{\delta}N/2$. Since $f\geqslant{\delta}1_{A}/2$, we deduce that

$T_{1}(f;B)\geqslant({\delta}/2)^{2}T_{1}(A;B),$

and an application of Theorem 2.4 completes the proof. ∎

Our next step is to weaken the assumptions of Theorem 2.4 even further,
replacing bounded functions with unbounded functions which are sufficiently
pseudorandom. The pseudorandomness we enforce posits the existence of a
‘random-like’ majorising function $\nu$, whose properties are given in the
following two definitions.

######  Definition 5.3 (Fourier decay).

We say that $\nu:[N]\to[0,\infty)$ has _Fourier decay of level $\theta$_ (with
respect to $1_{[N]}$) if

$\bigg{\|}\frac{\hat{\nu}}{\left\|\nu\right\|_{1}}-\frac{\hat{1}_{[N]}}{\left\|1_{[N]}\right\|_{1}}\biggr{\|}_{\infty}\leqslant\theta.$

######  Definition 5.4 ($p$-restriction).

We say that $\nu:[N]\to[0,\infty)$ satisfies a _$p$ -restriction estimate with
constant $K$_ if

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

######  Theorem 5.5 (Pseudorandom Sárközy).

For any $\delta>0$ and $K,M\in\mathbb{N}$ there exist $N_{0},c_{0},\theta>0$
such that for any $N\geqslant N_{0}$ the following holds. Let $B$ be an
$M$-homogeneous set of positive integers. Let $\nu:[N]\to[0,\infty)$ satisfy a
$4.995$-restriction estimate with constant $K$, and have Fourier decay of
level $\theta$. Then for any $f:[N]\to[0,\infty)$ with $f\leqslant\nu$ and
$\left\|f\right\|_{1}\geqslant\delta\left\|\nu\right\|_{1}$ we have

$\begin{split}T_{1}(f;B)\geqslant
c_{0}\left\|\nu\right\|^{2}_{1}N^{\frac{1}{2}}.\end{split}$

###### Proof.

Since $\nu$ has Fourier decay of level $\theta$, we may apply the dense model
lemma recorded in [Pre17a, Theorem 5.1], rescaling as appropriate, to conclude
the existence of $g:{\mathbb{Z}}\to{\mathbb{C}}$ satisfying $0\leqslant
g\leqslant 1_{[N]}$ and

$\bigg{\|}\frac{\hat{f}}{\left\|\nu\right\|_{1}}-\frac{\hat{g}}{N}\biggr{\|}_{\infty}\ll\log(\theta^{-1})^{-3/2}.$
(5.1)

Provided that $\theta\leqslant\exp(-C\delta^{-1})$ with $C$ a large positive
constant, we can compare Fourier coefficients at 0 to deduce that
$\left\|g\right\|_{1}\gg\delta N$. Applying Lemma 5.2 then gives

$T_{1}(g;B)\gg_{\delta,M}N^{\frac{5}{2}}.$ (5.2)

Let $h$ denote the indicator function of the set $\\{x^{2}:x\in
B\cap[\sqrt{N}]\\}$. Then for functions $h_{1},h_{2}:[N]\to\mathbb{C}$ we have

$T_{1}(h_{1},h_{2};B)=\sum_{x_{1}-x_{2}=x_{3}+x_{4}+x_{5}}h_{1}(x_{1})h_{2}(x_{2})h(x_{3})h(x_{4})h(x_{5}).$
(5.3)

The function $h$ is majorised by the indicator function of the set

$\\{x^{2}:x\in[\sqrt{N}]\\}$

which, by Lemma B.3, satisfies a $4.995$-restriction estimate with constant
$O(1)$.

The function $g$ is majorised by $1_{[N]}$, which satisfies a
4.995-restriction estimate with constant $O(1)$. Employing the generalised von
Neumann lemma (Lemma C.3), together with (5.1) and (5.3), we deduce that

$\left|\left\|\nu\right\|_{1}^{-2}T_{1}(f;B)-N^{-2}T_{1}(g;B)\right|\ll
KN^{1/2}\log(\theta^{-1})^{-3/400}.$

Combining this with (5.2) and choosing
$\theta\leqslant{\theta}_{0}({\delta},M,K)$ completes the proof. ∎

###  6\. The $W$-trick for squares: a simplified treatment

In this section we deduce our non-linear density result (Theorem 2.3) from its
pseudorandom analogue (Theorem 5.5). The heart of the matter is massaging the
set of squares to appear suitably pseudorandom. This is accomplished using a
version of the $W$-trick for squares, simplified from that developed in
Browning–Prendiville [BP17].

It is useful to have a non-linear version of the operator $T_{1}$ introduced
in §5.

######  Definition 6.1 ($T_{2}$ counting operator).

Given functions $f_{1},f_{2}:\mathbb{Z}\to\mathbb{C}$ with finite support and
$B\subset\mathbb{Z}$, define

$\displaystyle
T_{2}(f_{1},f_{2};B):=\sum_{\begin{subarray}{c}x_{1}^{2}-x_{2}^{2}=y_{1}^{2}+y_{2}^{2}+y_{3}^{2}\end{subarray}}f_{1}(x_{1})f_{2}(x_{2})1_{B}(y_{1})1_{B}(y_{2})1_{B}(y_{3}).$

We write $T_{2}(f;B)$ for $T_{2}(f,f;B)$ and $T_{2}(A;B)$ for
$T_{2}(1_{A};B)$.

Assuming the notation and premises of Theorem 2.3, our objective is to obtain
a lower bound for $T_{2}(A;B)$ by relating it to an estimate for $T_{1}(f;B)$,
where $f$ is a function bounded above by a pseudorandom majorant $\nu$, as in
Theorem 5.5.

Let

$W=2\prod_{p\leqslant w}p^{2},$ (6.1)

where $w=w(\delta,M)$ is a constant to be determined, and the product is over
primes. By Lemma A.4, applied with $S=[N]$, there exists a $w$-smooth positive
integer $\zeta\ll_{\delta,w}1$, and $\xi\in[W]$ with $(\xi,W)=1$, such that

$|\\{x\in\mathbb{Z}:\zeta(\xi+Wx)\in
A\\}|\geqslant\tfrac{1}{2}\delta|\\{x\in\mathbb{Z}:\zeta(\xi+Wx)\in[N]\\}|.$

Set

$A_{1}:=\\{\tfrac{1}{2}Wx^{2}+\xi x:\zeta(\xi+Wx)\in
A\\}\setminus\left\\{0\right\\}$

and, noting that $(2W)^{1/2}$ is a positive integer, set

$B_{1}:=\bigl{\\{}y\in{\mathbb{N}}:\zeta(2W)^{1/2}y\in B\bigr{\\}}.$

One may check that $B_{1}$ is $M$-homogeneous, and that there exists an
absolute constant $C$ such that if $N\geqslant C(\delta\zeta W)^{-1}$ then

$|A_{1}|\geqslant\frac{\delta N}{8\zeta W}.$ (6.2)

By the binomial theorem

$T_{2}(A;B)\geqslant T_{1}(A_{1};B_{1}).$ (6.3)

We note that although the squares are not equidistributed in arithmetic
progressions with small modulus, the same cannot be said of the set

$\left\\{\tfrac{1}{2}Wx^{2}+\xi x:x\in\mathbb{N}\right\\}.$ (6.4)

This is the reason for our passage from $A$ to $A_{1}$; the latter is a subset
of the more pseudorandom set (6.4). Unfortunately, the (truncated) Fourier
transform of (6.4) still does not behave sufficiently like that of an
interval: they decay differently around the zero frequency, reflecting the
growing gaps between consecutive elements of (6.4). To compensate for this, we
must work with a weighted indicator function of $A_{1}$ that counteracts this
increasing sparsity.

We first observe that $A_{1}$ is contained in the interval $[X]$, where

$X:=\frac{1}{2W}\cdot\left(\frac{N}{\zeta}\right)^{2}.$

Define a weight function $\nu:[X]\to[0,\infty)$ by

$\nu(n)=\begin{cases}Wx+\xi,&\text{if }n=\tfrac{1}{2}Wx^{2}+\xi x\text{ for
some }x\in[N/\zeta]\\\ 0,&\text{otherwise.}\end{cases}$ (6.5)

Since the results we are about to invoke are independent of the normalisation
of $\nu$, we note that we could replace the weight $Wx+\xi$ in the above
definition by $x$, or even by $\sqrt{n}$. We have chosen to incorporate the
more complicated weight in order to make calculations a little cleaner. The
weight $\nu(\cdot)$ has average value 1, since

$\sum_{n\in[X]}\nu(n)=\sum_{x\leqslant\frac{N}{\zeta
W}}Wx+O(N/\zeta)=X+O\left(W^{1/2}X^{1/2}\right).$ (6.6)

######  Lemma 6.2 (Density transfer).

For $N$ large in terms of $w$ and ${\delta}$ we have

$\sum_{n\in
A_{1}}\nu(n)\geqslant\tfrac{\delta^{2}}{256}\left\|\nu\right\|_{1}.$

###### Proof.

For $N$ sufficiently large in terms of $\delta$ and $w$ the estimate (6.2)
holds so, with $Z>0$ a parameter, we have

$\sum_{\begin{subarray}{c}\frac{1}{2}Wx^{2}+\xi x\in A_{1}\\\
x>Z\end{subarray}}1\geqslant|A_{1}|-Z\geqslant\tfrac{{\delta}N}{8\zeta W}-Z.$

Therefore

$\sum_{n\in A_{1}}\nu(n)\geqslant\sum_{\frac{1}{2}Wx^{2}+\xi x\in
A_{1}}Wx\geqslant WZ\left(\tfrac{\delta N}{8\zeta W}-Z\right)=\tfrac{\delta
ZN}{8\zeta}-WZ^{2}.$

Choosing $Z=\tfrac{\delta N}{16\zeta W}$ gives

$\sum_{n\in
A_{1}}\nu(n)\geqslant\tfrac{\delta^{2}N^{2}}{256\zeta^{2}W}=\tfrac{\delta^{2}}{128}X.$

An application of (6.6) completes the proof. ∎

The following two ingredients are established in Appendices D and E.

######  Lemma 6.3 (Fourier decay).

We have

$\|\hat{\nu}-\hat{1}_{[X]}\|_{\infty}\ll Xw^{-1/2}.$

######  Lemma 6.4 (Restriction estimate).

For any real number $p>4$ we have

$\begin{split}\sup_{|\phi|\leqslant\nu}\int_{\mathbb{T}}\left|\hat{\phi}(\alpha)\right|^{p}\mathrm{d}\alpha\ll_{p}X^{p-1}.\end{split}$

###### Proof of Theorem 2.3.

Let $K$ denote the absolute constant implicit in Lemma 6.4 when $p=4.995$. Let
$N_{0}$ and $\theta$ denote the parameters occurring in Theorem 5.5 with
respect to a density of $\delta^{2}/256$, restriction constant $K$ and
homogeneity of level $M$. Employing Lemma 6.3, we may choose $w=w({\delta},M)$
sufficiently large to ensure that $\nu$ has Fourier decay of level $\theta$
with respect to $1_{[X]}$. Setting $f=\nu 1_{A_{1}}$ in Theorem 5.5 yields

$T_{1}(\nu 1_{A_{1}};B_{1})\gg_{{\delta},M}X^{\frac{5}{2}}.$

Hence by (6.3) we obtain

$T_{2}(A;B)\geqslant\|\nu\|_{\infty}^{-2}T_{1}(\nu
1_{A_{1}};B_{1})\gg_{{\delta},M}\|\nu\|_{\infty}^{-2}X^{\frac{5}{2}}.$

This inequality completes the proof of Theorem 2.3 on noting that
$X\gg_{\delta,M}N^{2}$ and $\left\|\nu\right\|_{\infty}\ll N$. ∎

###  7\. Multidimensional homogeneous Furstenberg–Sárközy

It remains to establish Theorem 2.4. In §8 we derive this supersaturated
counting result from a multidimensional ‘existence’ result, Theorem 2.5, whose
proof is the aim of this section. One can prove Theorem 2.5 succinctly using
the multidimensional polynomial Szemerédi theorem of Bergelson–Leibman [BL96],
see Corollary 9.1 for such an argument. One may regard such an approach as
overkill, and of little utility if one is interested in quantitative bounds.
In this section we opt for a more circuitous approach which demonstrates how
Fourier analysis suffices for Theorem 2.5. More precisely, we adapt the
Fourier-analytic density increment strategy originating with Roth [Rot53] and
Sárközy [Sár78], and show how it may accommodate the presence of homogeneous
sets. The structure of our argument is based on Green [Gre02].

######  Lemma 7.1 (Density increment lemma).

Let $B_{i}$ be $M$-homogeneous sets of positive integers, and let
$A\subset[N]^{d}$ have size at least $\delta N^{d}$. Suppose that $A\times A$
lacks $(x,x^{\prime})$ satisfying

$x-x^{\prime}=(y_{1}^{2},\dots,y_{d}^{2})$ (7.1)

with $(y_{1},\dots,y_{d})\in B_{1}\times\dots\times B_{d}$. Then either

$N\leqslant C_{d}(\delta^{-1}M^{d})^{C},$ (7.2)

or there exist

  1. (i)

$M$-homogeneous sets $B_{i}^{\prime}\subset\mathbb{N}$;

  2. (ii)

a positive integer $N_{1}\geqslant N^{c}$, where $c>0$ is an absolute
constant;

  3. (iii)

a multidimensional set $A_{1}\subset[N_{1}]^{d}$ such that

    1. (ia)

$A_{1}\times A_{1}$ lacks tuples satisfying (7.1) with $(y_{1},\dots,y_{d})\in
B_{1}^{\prime}\times\dots\times B_{d}^{\prime}$;

    2. (ib)

$|A_{1}|\geqslant(\delta+c_{d}(\delta M^{-d})^{6})N_{1}^{d}$.

###### Proof of Theorem 2.5 given Lemma 7.1.

Let us assume that $A\subset[N]^{d}$ has size at least $\delta N^{d}$ and
lacks solutions to (7.1) with $y_{i}\in B_{i}$, where the $B_{i}$ are
$M$-homogeneous sets. Setting $A_{0}:=A$, we iteratively apply Lemma 7.1 to
obtain a sequence of sets $A_{0},A_{1},A_{2},\dots$, each contained in an
ambient grid $[N_{n}]^{d}$ with

$N_{n}\geqslant N^{c^{n}},\qquad|A_{n}|\geqslant\left(\delta+nc_{d}(\delta
M^{-d})^{6}\right)N_{n}^{d}.$

If this iteration continues until $n$ is sufficiently large in terms of
$d,\delta,M$, we obtain a density exceeding 1, which would be impossible.
Hence for some $n\ll_{d,\delta,M}1$ the inequality (7.2) is satisfied with
$N_{n}$ in place of $N$ therein. Therefore

$N\leqslant
N_{n}^{C^{n}}\leqslant\left(C_{d}(\delta^{-1}M^{d})^{C}\right)^{C^{n}}\ll_{d,\delta,M}1.$

∎

We henceforth proceed with the proof of Lemma 7.1. Put

$B:=B_{1}\times\dots\times B_{d},$

let $A\subset[N]^{d}$ with $|A|=\delta N^{d}$, and suppose $A\times A$ lacks
tuples $(x,x^{\prime})$ satisfying (7.1) with $(y_{1},\dots,y_{d})\in B$.

For $f,g:[N]^{d}\to\mathbb{C}$, define the counting operator

$T_{B}(f,g):=\sum_{x-x^{\prime}=(y_{1}^{2},\dots,y_{d}^{2})}f(x)g(x^{\prime})1_{B}(y_{1},\dots,y_{d}).$

Write $T_{B}(f)$ for $T_{B}(f,f)$. With this notation, our assumption is that

$T_{B}(1_{A})=0.$

Let $f=1_{A}-\delta 1_{[N]^{d}}$ denote the _balanced function_ of $A$ in
$[N]^{d}$. Then by bilinearity

$\begin{split}T_{B}(1_{A})=T_{B}(1_{A},f)+T_{B}(f,\delta
1_{[N]^{d}})+\delta^{2}T_{B}(1_{[N]^{d}}).\end{split}$

Hence there exists $g:[N]\to[0,1]$ with
$\left\|g\right\|_{2}\leqslant\sqrt{\delta N}$ and such that

$|T_{B}(g,f)|\geqslant\tfrac{1}{2}\delta^{2}T_{B}(1_{[N]^{d}})\quad\text{or}\quad|T_{B}(f,g)|\geqslant\tfrac{1}{2}\delta^{2}T_{B}(1_{[N]^{d}}).$
(7.3)

Since the balanced function $f$ has average value $0$, one can regard (7.3) as
exhibiting the fact that $f$ displays some form of non-uniformity. In order to
demonstrate this formally we require the following lemmas.

######  Lemma 7.2 (Homogeneous counting lemma).

Let $B=B_{1}\times\dotsm\times B_{d}$ be a product of $M$-homogeneous sets.
Then for $N\geqslant 64M^{2}$ we have

$T_{B}(1_{[N]^{d}})\geqslant\left(\frac{N^{\frac{3}{2}}}{8M^{2}}\right)^{d}.$

###### Proof.

It suffices to prove the result for $d=1$, since

$T_{B}(1_{[N]^{d}})=\prod_{i=1}^{d}T_{B_{i}}(1_{[N]}).$

If $y\in\left[\sqrt{N/2}\right]$ then $y^{2}\in[N/2]$, so for $y$ in this
interval we have

$\begin{split}\sum_{x-x^{\prime}=y^{2}}1_{[N]}(x)1_{[N]}(x^{\prime})=\\#\left\\{y^{2}+x:1\leqslant
x\leqslant N-y^{2}\right\\}\geqslant\frac{N}{2}.\end{split}$

Summing over $y$ lying in the intersection of this interval with a homogeneous
set $B$, we apply Lemma 4.2 to deduce that

$\begin{split}T_{B}(1_{[N]})&\geqslant\sum_{y\in
B\cap[\sqrt{N/2}]}\sum_{x-x^{\prime}=y^{2}}1_{[N]}(x)1_{[N]}(x^{\prime})\\\
&\geqslant\frac{1}{M}\bigg{\lfloor}\frac{\lfloor\sqrt{N/2}\rfloor}{M}\bigg{\rfloor}\frac{N}{2}.\end{split}$

The result follows provided that $N$ is sufficiently large. ∎

######  Lemma 7.3 (Generalised von Neumann theorem).

Let $f_{1},f_{2}:[N]^{d}\to[-1,1]$. Then for $i=1,2$ we have

$|T_{B}(f_{1},f_{2})|\ll_{d}N^{3d/2}\left(\frac{\big{\|}\hat{f_{i}}\big{\|}_{L^{\infty}(\mathbb{T}^{d})}}{N^{d}}\right)^{1/3}.$

###### Proof.

We prove the result for $i=1$, the other case being similar. For
${\alpha}=({\alpha}_{1},\ldots,{\alpha}_{d})\in{\mathbb{T}}^{d}$, define

$S_{B}(\alpha):=\sum_{y\in
B\cap[\sqrt{N}]^{d}}e(\alpha_{1}y_{1}^{2}+\dots+\alpha_{d}y_{d}^{2}).$

By orthogonality and Hölder’s inequality, we have

$\begin{split}|T_{B}(f_{1},f_{2})|&=\left|\int_{\mathbb{T}^{d}}S_{B}(\alpha)\hat{f}_{1}(-\alpha)\hat{f}_{2}(\alpha)\mathrm{d}\alpha\right|\\\
&\leqslant\left\|S_{B}\right\|_{L^{6}(\mathbb{T}^{d})}\big{\|}\hat{f}_{1}\big{\|}^{1/3}_{L^{\infty}(\mathbb{T}^{d})}\big{\|}\hat{f}_{1}\big{\|}_{L^{2}(\mathbb{T}^{d})}^{2/3}\big{\|}\hat{f}_{2}\big{\|}_{L^{2}(\mathbb{T}^{d})}.\end{split}$

The result now follows on incorporating Parseval’s identity

$\big{\|}\hat{f}_{i}\big{\|}_{L^{2}(\mathbb{T}^{d})}=\big{\|}f_{i}\big{\|}_{L^{2}(\mathbb{Z}^{d})}\leqslant
N^{d/2}$

together with the estimate

$\int_{\mathbb{T}^{d}}|S_{B}(\alpha)|^{6}\mathrm{d}\alpha\ll_{d}N^{2d}.$

The latter mean value estimate follows from orthogonality and Theorem B.1. ∎

When taken in conjunction with (7.3), Lemmas 7.2 and 7.3 imply that for
$N\geqslant 64M^{2}$ there exists $\alpha\in\mathbb{T}^{d}$ for which

$\begin{split}\bigl{|}\hat{f}(\alpha)\bigr{|}\gg_{d}\left(\delta
M^{-d}\right)^{6}N^{d}.\end{split}$ (7.4)

######  Lemma 7.4 (Fragmentation into level sets).

If $\alpha\in\mathbb{T}^{d}$, $Q\geqslant 1$ and $P\in{\mathbb{N}}$ then there
exist positive integers $q_{i}\leqslant Q$ and a partition of $\mathbb{Z}^{d}$
into sets $R$ of the form

$\prod_{i=1}^{d}\left(a_{i}+q^{2}_{i}\cdot(-P,P]\right)$ (7.5)

such that for any $g:\mathbb{Z}^{d}\to[-1,1]$ with finite $L^{1}$ norm we have
the estimate

$\begin{split}\left|\hat{g}(\alpha)\right|\leqslant\sum_{R}\Bigl{|}\sum_{x\in
R}g(x)\Bigr{|}+O_{d}\left(\left\|g\right\|_{1}PQ^{-1/3}\right).\end{split}$
(7.6)

###### Proof.

By a weak form of a result of Heilbronn [Hei48], there are
$q_{1},\dots,q_{d}\leqslant Q$ such that

$\begin{split}\left\|\alpha_{i}q_{i}^{2}\right\|\ll Q^{-1/3}\qquad(1\leqslant
i\leqslant d).\end{split}$ (7.7)

We partition $\mathbb{Z}^{d}$ into congruence classes of the form

$\prod_{i}\left(a_{i}+q_{i}^{2}\cdot\mathbb{Z}\right),$

then partition each copy of $\mathbb{Z}$ appearing in this product into a
union of intervals of the form $2nP+(-P,P]$ with $n\in\mathbb{Z}$. This yields
a partition of $\mathbb{Z}^{d}$ into sets $R$ of the form (7.5).

If $x,x^{\prime}$ lie in the same $R$ then
$x-x^{\prime}=(q_{1}^{2}y_{1},\dots,q_{d}^{2}y_{d})$ for some
$y\in(-P,P]^{d}$, and so

$|e(\alpha\cdot x)-e(\alpha\cdot
x^{\prime})|\ll\sum_{i=1}^{d}P\left\|q_{i}^{2}\alpha_{i}\right\|\ll_{d}PQ^{-1/3}.$

It then follows from the triangle inequality that

$\begin{split}\left|\hat{g}(\alpha)\right|&\leqslant\sum_{R}\biggl{|}\sum_{x\in
R}g(x)e(\alpha\cdot x)\biggr{|}\\\ &=\sum_{R}\biggl{|}\sum_{x\in
R}g(x)\biggr{|}+O_{d}\Bigl{(}\sum_{R}\sum_{x\in
R}|g(x)|PQ^{-1/3}\Bigr{)}.\end{split}$

∎

Let us take $P:=\left\lfloor N^{1/9}\right\rfloor$ and $Q:=N^{3/8}$. Then,
provided that (7.2) fails to hold, we have

$PQ^{-1/3}\leqslant c_{d}(\delta M^{-d})^{6},\qquad PQ^{2}N^{-1}\leqslant
c_{d}(\delta M^{-d})^{6}.$ (7.8)

With these bounds in hand, we claim that we may apply Lemma 7.4 to (7.4) and
conclude that there exists a set $R$ contained in $[N]^{d}$ and of the form
(7.5) for which

$\sum_{x\in R}f(x)\gg_{d}(\delta M^{-d})^{6}|R|.$ (7.9)

Let us presently set about showing this.

The first bound in (7.8), together with (7.6), implies that

$\sum_{R}\biggl{|}\sum_{x\in R}f(x)\biggr{|}\gg_{d}(\delta M^{-d})^{6}N^{d}.$

By definition, the balanced function has average value $\sum_{x}f(x)=0$, so
adding this quantity to either side of the inequality gives

$\sum_{R}\max\Bigl{\\{}0,\sum_{x\in R}f(x)\Bigr{\\}}\gg_{d}(\delta
M^{-d})^{6}N^{d}.$

Inspection of the proof of Lemma 7.4 reveals that the number of $R$ which
intersect $[N]^{d}$ is at most

$\left(\frac{N}{2P}+Q^{2}\right)^{d}.$ (7.10)

Similarly, the number of $R$ contained in $[N]^{d}$ is at least

$\left(\frac{N}{2P}-Q^{2}\right)^{d}.$

Therefore

$\sum_{R\subset[N]^{d}}\max\Bigl{\\{}0,\sum_{x\in
R}f(x)\Bigr{\\}}\geqslant\left(c_{d}(\delta
M^{-d})^{6}-C_{d}Q^{2}PN^{-1}\right)N^{d}.$

The second inequality in (7.8) now implies that

$\sum_{R\subset[N]^{d}}\max\Bigl{\\{}0,\sum_{x\in
R}f(x)\Bigr{\\}}\gg_{d}(\delta M^{-d})^{6}N^{d}.$

By (7.8) and (7.10), the number of $R$ contained in $[N]^{d}$ is
$O_{d}((N/P)^{d})$. An application of the pigeonhole principle finally
confirms (7.9).

The estimate (7.9) completes our proof of Lemma 7.1, for if $R$ takes the form
(7.5) with $P=\left\lfloor N^{1/9}\right\rfloor$ then we may take $N_{1}:=2P$,
$B_{i}^{\prime}:=\left\\{y\in\mathbb{N}:q_{i}y\in B_{i}\right\\}$ and

$A_{1}:=\left\\{x\in[N_{1}]^{d}:(a_{1},\dots,a_{d})+\left(q_{1}^{2}(x_{1}-P),\dots,q_{d}^{2}(x_{d}-P)\right)\in
A\right\\}.$

###  8\. Varnavides averaging for supersaturation

We complete the proof of Theorem 2.1 by deducing the counting result, Theorem
2.4, from the multidimensional existence result, Theorem 2.5. The deduction
proceeds by collecting a single configuration from many subprogressions, then
establishing that these configurations don’t coincide too often. This random
sampling argument originates with Varnavides [Var59].

######  Proposition 8.1 (Varnavides argument).

For any $\delta>0$ and $d,M\in\mathbb{N}$ there exists $N_{0}\in\mathbb{N}$
and $c_{0}>0$ such that for any $N\geqslant N_{0}$ the following holds. If
$A\subset[N]^{d}$ is at least $\delta$-dense in $[N]^{d}$ and
$B_{1},\dots,B_{d}$ are $M$-homogeneous sets of natural numbers, then there
are at least $c_{0}N^{\frac{3d}{2}}$ tuples $(x,x^{\prime},y)\in A^{2}\times
B_{1}\times\dots\times B_{d}$ satisfying (2.3).

###### Proof.

For $q,n\in\mathbb{Z}^{d}$ write $q^{\otimes 2}\otimes n$ for the tuple
$(q_{1}^{2}n_{1},\dots,q_{d}^{2}n_{d})$ and write $q^{\otimes
2}\otimes[N]^{d}$ for the set

$\left\\{q^{\otimes 2}\otimes n:n\in[N]^{d}\right\\}.$

Let $N_{0}=N_{0}(\delta/2^{1+d},d,M)$ be the quantity given by Theorem 2.5.
Suppose that $N\geqslant N_{0}$ and write
$Q:=\left\lfloor\sqrt{N/N_{0}}\right\rfloor$. Averaging, we have

$\begin{split}\sum_{z\in\mathbb{Z}^{d}}\sum_{q\in[Q]^{d}}|A\cap\left(z+q^{\otimes
2}\otimes[N_{0}]^{d}\right)|\geqslant\delta(NQN_{0})^{d}.\end{split}$

By the definition of $Q$, there are at most $(2N)^{d}$ choices for $z$ for
which there exists $q\in[Q]^{d}$ such that

$|A\cap\left(z+q^{\otimes 2}\otimes[N_{0}]^{d}\right)|\neq 0.$

Hence there are at least $\tfrac{1}{2}\delta(NQ)^{d}$ choices for
$(z,q)\in\mathbb{Z}^{d}\times\mathbb{N}^{d}$ for which

$\begin{split}|A\cap\left(z+q^{\otimes 2}\otimes[N_{0}]^{d}\right)|\geqslant
2^{-1-d}\delta N_{0}^{d}.\end{split}$ (8.1)

Call each such choice of $(z,q)$ a _good_ tuple. Define

$A_{z,q}:=\left\\{y\in[N_{0}]^{d}:z+q^{\otimes 2}\otimes y\in A\right\\}.$

If $(z,q)$ is good then $|A_{z,q}|\geqslant 2^{-1-d}\delta N_{0}^{d}$.
Applying Theorem 2.5 we see that there exist $x,x^{\prime}\in A_{z,q}$
satisfying (2.3) with the $y_{i}$ restricted to the $M$-homogeneous sets

$\left\\{y_{i}:q_{i}y_{i}\in B_{i}\right\\}.$

Translating and dilating, we deduce that each set $A\cap\left(z+q^{\otimes
2}\otimes[N_{0}]^{d}\right))$ satisfying (8.1) contains a solution to (2.3)
with $y_{i}\in B_{i}$.

For fixed $(x,y)\in\mathbb{Z}^{d}\times\mathbb{N}^{d}$ define $R(x,y)$ to be
the quantity

$\\#\left\\{(z,q)\in\mathbb{Z}^{d}\times[Q]^{d}:\left\\{x,\ x+y^{\otimes
2}\right\\}\subset\left(z+q^{\otimes 2}\otimes[N_{0}]^{d}\right)\right\\}.$

######  Claim.

$R(x,y)\leqslant N_{0}^{2d}.$

To see this, observe that if $\left\\{x,\ x+y^{\otimes 2}\right\\}\subset
z+q^{\otimes 2}\otimes[N_{0}]^{d}$ then for each $i$ there exists
$m_{i}\in[N_{0}]$ such that $y_{i}^{2}=q_{i}^{2}m_{i}.$ As there are at most
$N_{0}$ choices for $m_{i}$ for fixed $y_{i}$, there are at most $N_{0}^{d}$
choices for $q$. Once one has fixed this choice of $q$ we have

$z\in x-q^{\otimes 2}\otimes[N_{0}]^{d},$

so there are at most $N_{0}^{d}$ choices of $z$ for fixed $x$. This
establishes the claim.

Invoking the claim gives

$N_{0}^{2d}\\#\left\\{(x,y)\in\mathbb{Z}^{d}\times B_{1}\times\dotsm\times
B_{d}:\left\\{x,\ x+y^{\otimes 2}\right\\}\subset A\right\\}\\\
\geqslant\sum_{\begin{subarray}{c}x\in\mathbb{Z}^{n},y\in B_{1}\times\dotsm
B_{d}\\\ x,\ x+y^{\otimes 2}\in A\end{subarray}}R(x,y).$

Next we interchange the order of summation to find that

$\displaystyle\sum_{\begin{subarray}{c}x\in\mathbb{Z}^{d},y\in
B_{1}\times\dotsm B_{d}\\\ x,\ x+y^{\otimes 2}\in A\end{subarray}}$
$\displaystyle R(x,y)$
$\displaystyle\geqslant\sum_{z\in\mathbb{Z}^{d}}\sum_{q\in[Q]^{d}}\\#\left\\{(x,y):\left\\{x,\
x+y^{\otimes 2}\right\\}\subset A\cap\left(z+q^{\otimes
2}\otimes[N_{0}]^{d}\right)\right\\}$
$\displaystyle\geqslant\\#\left\\{(z,q)\in\mathbb{Z}^{d}\times[Q]^{d}:(z,q)\text{
is good}\right\\}$ $\displaystyle\geqslant\tfrac{1}{2}\delta(NQ)^{d}.$

It follows that

$\\#\left\\{(x,y)\in\mathbb{Z}^{d}\times B_{1}\times\dotsm\times
B_{d}:\left\\{x,\ x+y^{\otimes 2}\right\\}\subset A\right\\}\\\
\geqslant\tfrac{1}{2}\delta
N_{0}^{-2d}N^{d}\left\lfloor\sqrt{N/N_{0}}\right\rfloor^{d}.$

The result follows since $N_{0}\ll_{\delta,d,M}1$. ∎

###### Proof that Proposition 8.1 implies Theorem 2.4.

We prove a more general result for sums of $d$ squares. First note that, by
translation, Proposition 8.1 remains valid for dense subsets of $[-N,N]^{d}$.
Given $A\subset[N]$ of density at least $\delta$, define

$A^{\prime}:=\left\\{x\in[-N,N]^{d}:x_{1}+\dots+x_{d}\in A\right\\}$

For every element $n$ of $[-N,N]$ there are at least $N$ pairs
$(n_{1},n_{2})\in[-N,N]^{2}$ such that $n=n_{1}+n_{2}$. An induction then
shows that for each $n\in[-N,N]$ we have

$\\#\left\\{(n_{1},\dots,n_{d})\in[-N,N]^{d}:n=n_{1}+\dots+n_{d}\right\\}\geqslant
N^{d-1}.$

Consequently

$|A^{\prime}|\geqslant\delta N^{d}\gg_{d}\delta|[-N,N]^{d}|.$

Applying Proposition 8.1 with $B_{i}:=B$ for all $i$, we deduce that there are
at least $c_{0}N^{3d/2}$ tuples $(x,y)\in A^{\prime}\times B^{d}$ such that
$x+(y_{1}^{2},\dots,y_{d}^{2})\in A^{\prime}$. For each such tuple the sum
$x=x_{1}+\dots+x_{d}$ is an element of the one-dimensional set $A$, as is
$x+y_{1}^{2}+\dots+y_{d}^{2}$. As each element of $A$ has at most
$(2N+1)^{d-1}$ representations of the form $x_{1}+\dots+x_{d}$, it follows
that the number of solutions to

$x-x^{\prime}=y_{1}^{2}+\dots+y_{d}^{2}$

is at least

$c_{0}N^{\frac{3d}{2}-(d-1)}=c_{0}N^{1+\frac{d}{2}},$

as required. ∎

##  Part II Rado’s criterion over squares and higher powers

In this part we prove Theorem 1.3. Let $\eta=\eta_{k}>0$ be a fixed constant,
where $\eta_{2}=1$, and $\eta_{k}$ is sufficiently small when $k\geqslant 3$.
In other words, we will work with smooth numbers when $k\geqslant 3$, but not
when $k=2$. This choice will improve our mean value estimate in the former
situation, and our minor arc estimate in the latter.

###  9\. The smooth homogeneous Bergelson–Leibman theorem

We begin our investigation of Rado’s criterion in $k$th powers by generalising
Theorem 2.4, which asserts that dense multidimensional sets contain
configurations of the form

$(x_{1},\dots,x_{d}),\quad(x_{1}+y_{1}^{2},\dots,x_{d}+y_{d}^{2})$

with the $y_{i}$ lying in a homogeneous set. We require a version of this
result which concerns affine configurations determined by $k$th powers,
similar in flavour to the following special case of the multidimensional
polynomial Szemerédi theorem of Bergelson–Leibman [BL96].

######  Bergelson–Leibman.

Let $k\in\mathbb{N}$, $\delta>0$ and let $F\subset\mathbb{Z}^{d}$ be a finite
set. There exists $N_{0}=N_{0}(k,\delta,F)$ such that for any $N\geqslant
N_{0}$, if $A\subset[N]^{d}$ has size $|A|\geqslant\delta N^{d}$ then there
exists $x\in\mathbb{Z}^{d}$ and $y\in\mathbb{N}$ such that

$x+y^{k}\cdot F\subset A.$

We require a version of this result in which the $k$th power comes from a
homogeneous set. Fortunately, this strengthening can be deduced from the
original. It is convenient to set up the following notation.

######  Notation.

Given $q,y,k\in\mathbb{N}^{d}$ define

$q\otimes y:=(q_{1}y_{1},\dots,q_{d}y_{d}),\qquad y^{\otimes
k}:=(y_{1}^{k_{1}},\dots,y_{d}^{k_{d}}).$

For $F\subset\mathbb{Z}^{d}$, write $q\otimes F$ for the set

$\left\\{q\otimes y:y\in F\right\\}.$

Here is our version of the Bergelson–Leibman theorem with common difference
arising from a homogeneous set.

######  Corollary 9.1 (Homogeneous Bergelson–Leibman).

Let $k\in\mathbb{N}^{d}$, $M\in\mathbb{N}$, $\delta>0$ and let
$F\subset\mathbb{Z}^{d}$ be a finite set. There exists $N_{0}$ such that for
any $N\geqslant N_{0}$, if $A\subset[N]^{d}$ has size $|A|\geqslant\delta
N^{d}$ and $B_{1},\dots,B_{d}\subset\mathbb{N}$ are $M$-homogeneous, then
there exists $x\in\mathbb{Z}^{d}$ and $y_{1}\in B_{1},\dots,y_{d}\in B_{d}$
such that

$x+y^{\otimes k}\otimes F\subset A.$ (9.1)

###### Proof.

Let $K:=\prod_{i}k_{i}$ and consider the finite set

$F^{\prime}:=[M^{K}]^{d}\otimes F.$

By the Bergelson–Leibman theorem, provided that $N\gg_{M,K,F,\delta}1$, there
exist $x\in\mathbb{Z}^{d}$ and $t\in\mathbb{N}$ such that

$x+t^{K}\cdot F^{\prime}\subset A.$

The result follows if the progression $t^{K}\cdot[M^{K}]$ contains an element
of the form $y_{i}^{k_{i}}$ for some $y_{i}\in B_{i}$.

Let $z_{i}:=t^{K/k_{i}}$. Then

$\left\\{z_{i}^{k_{i}},(2z_{i})^{k_{i}},\dots,(Mz_{i})^{k_{i}}\right\\}=t^{K}\cdot\left\\{1^{k_{i}},2^{k_{i}},\dots,M^{k_{i}}\right\\}\subset
t^{K}\cdot[M^{K}].$

Since each $B_{i}$ is $M$-homogeneous, it intersects the set $z_{i}\cdot[M]$.
∎

Next we require a counting analogue of this result. In fact, we need to count
the number of configurations arising from a smooth common difference. Before
stating the theorem, we remind the reader of what it means for a set to be
$M$-homogeneous in the $N^{\eta}$-smooths (see Definitions 1.6 and 2.2).

######  Theorem 9.2 (Varnavides averaging).

Let $k_{1},\dots,k_{d},M\in\mathbb{N}$, $\eta,\delta\in(0,1]$, and let
$F\subset\mathbb{Z}^{d}$ be a finite set. There exist $N_{0}\in\mathbb{N}$ and
$c_{0}>0$ such that for any $N\geqslant N_{0}$, if $A\subset[N]^{d}$ has
$|A|\geqslant\delta N^{d}$ and $B\subset\mathbb{N}$ is $M$-homogeneous in the
$N^{\eta}$-smooths, then the number of tuples $(x,y)\in\mathbb{Z}^{d}\times
B^{d}$ for which (9.1) holds is at least

$c_{0}N^{d+\frac{1}{k_{1}}+\dots+\frac{1}{k_{d}}}.$

###### Proof.

Increasing the size of $F$ if necessary, we may assume that $F$ contains two
elements which differ in the $i$th coordinate for each $i\in[d]$. Let $N_{0}$
be the quantity given by Corollary 9.1 with respect to the density
$\delta/2^{d+1}$. Suppose that

$N\geqslant N_{0}^{1/\eta},$ (9.2)

and define the following sets of smooths:

$S_{i}:=S\bigl{(}\bigl{\lfloor}\sqrt[k_{i}]{N/N_{0}}\bigr{\rfloor};N^{\eta}\bigr{)}.$

Interchanging the order of summation, we have

$\begin{split}\sum_{z\in\mathbb{Z}^{d}}\sum_{q_{1}\in
S_{1}}\dots\sum_{q_{d}\in S_{d}}|A\cap\left(z+q^{\otimes
k}\otimes[N_{0}]^{d}\right)|\geqslant\delta|S_{1}|\dotsm|S_{d}|(NN_{0})^{d}.\end{split}$

Notice that there are at most $(2N)^{d}$ choices for $z$ for which there
exists $q\in S_{1}\times\dots\times S_{d}$ such that

$|A\cap\left(z+q^{\otimes k}\otimes[N_{0}]^{d}\right)|\neq 0.$

Hence there are at least $\tfrac{1}{2}\delta N^{d}|S_{1}|\dotsm|S_{d}|$
choices for $(z,q)\in\mathbb{Z}^{d}\times\prod_{i}S_{i}$ for which

$\begin{split}|A\cap\left(z+q^{\otimes k}\otimes[N_{0}]^{d}\right)|\geqslant
2^{-d-1}\delta N_{0}^{d}.\end{split}$ (9.3)

Call such a choice of $(z,q)$ a _good_ tuple.
Claim 1. For each good tuple $(z,q)$ the set $A\cap\left(z+q^{\otimes
k}\otimes[N_{0}]^{d}\right)$ contains a configuration of the form
$x+y^{\otimes k}\otimes F$ for some $x\in{\mathbb{Z}}^{d}$ and some $y\in
B^{d}$.

To see this, define

$A_{z,q}:=\left\\{x\in[N_{0}]^{d}:z+q^{\otimes k}\otimes x\in A\right\\}.$

Then $|A_{z,q}|\geqslant 2^{-d-1}\delta N_{0}^{d}$. Let

$B_{i}=\left\\{y_{i}\in[N_{0}]:q_{i}y_{i}\in B\right\\}\cup(N_{0},\infty).$

Using the fact that $B$ is $N^{\eta}$-smoothly $M$-homogeneous, together with
(9.2), one can check that each $B_{i}$ is $M$-homogeneous (not just smoothly
homogeneous). Invoking Corollary 9.1, we see that there exist
$x\in\mathbb{Z}^{d}$ and $y\in B_{1}\times\dots\times B_{d}$ such that

$x+y^{\otimes k}\otimes F\subset A_{z,q}.$

Translating and dilating, we deduce that $A\cap\left(z+q^{\otimes
k}\otimes[N_{0}]^{d}\right)$ contains a configuration of the form
$x^{\prime}+(q\otimes y)^{\otimes k}\otimes F$. By definition of the $B_{i}$
and the fact that $F$ is non-constant in each coordinate, we see that
$y\in[N_{0}]^{d}$ and thus each coordinate of $q\otimes y$ lies in $B$. This
establishes Claim 1.

For fixed $(x,y)\in\mathbb{Z}^{d}\times\mathbb{N}^{d}$ let $G(x,y)$ denote the
number of tuples $(z,q)\in\mathbb{Z}^{d}\times\mathbb{N}^{d}$ satisfying

$x+y^{\otimes k}\otimes F\subset z+q^{\otimes k}\otimes[N_{0}]^{d}.$ (9.4)

Define

$\mathcal{A}:=\left\\{(x,y)\in\mathbb{Z}^{d}\times B^{d}:x+y^{\otimes
k}\otimes F\subset A\right\\}.$ (9.5)

Then interchanging the order of summation shows that the sum
$\sum_{(x,y)\in\mathcal{A}}G(x,y)$ is at least

$\displaystyle\sum_{z\in\mathbb{Z}^{d}}\sum_{q_{1}\in
S_{1}}\dots\sum_{q_{d}\in S_{d}}\Bigl{|}\left\\{(x,y)\in\mathbb{Z}^{d}\times
B^{d}:x+y^{\otimes k}\otimes F\subset A\cap\left(z+q^{\otimes
k}\otimes[N_{0}]^{d}\right)\right\\}\Bigr{|}$
$\displaystyle\geqslant\Bigl{|}\Bigl{\\{}(z,q)\in\mathbb{Z}^{d}\times\prod_{i}S_{i}:(z,q)\text{
is good}\Bigr{\\}}\Bigr{|}\geqslant\tfrac{1}{2}\delta
N^{d}|S_{1}|\dotsm|S_{d}|.$

Applying Lemma A.2 (for $N$ sufficiently large) we deduce that

$\sum_{(x,y)\in\mathcal{A}}G(x,y)\gg_{k,\delta,\eta,N_{0}}\
N^{d+\frac{1}{k_{1}}+\dots+\frac{1}{k_{d}}}.$

Since the theorem asserts a lower bound on the size of $\mathcal{A}$, the
result is proved provided we have the following upper bound on $G(x,y)$.
Claim 2. Suppose that $F$ contains two elements which differ in the $i$th
coordinate for each $i\in[d]$. Then $G(x,y)\leqslant N_{0}^{2d}$.

To see this, first note that if $x+y^{\otimes k}\otimes F\subset z+q^{\otimes
k}\otimes[N_{0}]^{d}$ then, since $F$ contains two elements differing in their
$i$th coordinate, there exist integers $f_{i}<f_{i}^{\prime}$ such that

$x_{i}+y_{i}^{k_{i}}f_{i},\ x_{i}+y_{i}^{k_{i}}f_{i}^{\prime}\in
z_{i}+q_{i}^{k_{i}}\cdot[N_{0}].$

Subtracting these elements, we deduce that there exists $n_{i}\in[N_{0}]$ for
which

$q_{i}^{k_{i}}=\frac{y_{i}^{k_{i}}(f_{i}^{\prime}-f_{i})}{n_{i}}.$

As there are at most $N_{0}$ choices for $n_{i}$, and $y_{i}$ is fixed, there
are at most $N_{0}^{d}$ choices for $q$. Once one has fixed this choice of
$q$, for any $f\in F$ we have

$z\in x+y^{\otimes k}\otimes f-q^{\otimes k}\otimes[N_{0}]^{d},$

so there are at most $N_{0}^{d}$ choices for $z$. In summary $G(x,y)\leqslant
N_{0}^{2d}$, which establishes Claim 2. ∎

######  Remark 9.3 (Roth’s theorem with logarithmically-smooth common
difference).

The above argument remains valid for much stronger levels of smoothness. For
instance, one can use it to establish that if $A\subset[N]$ lacks a three-term
progression with common difference equal to an $R$-smooth number then

$|A|\ll\frac{r_{3}(R)}{R}N.$ (9.6)

Here $r_{3}(N)$ denotes the size of a largest subset of $[N]$ lacking a non-
trivial three-term arithmetic progression.

###  10\. A supersaturated generalisation of both Roth and Sárközy’s theorems

In this section we deduce a one-dimensional counting result analogous to
Theorem 2.4 by projecting down the multidimensional Theorem 9.2. Again we
remind the reader of what it means to be $M$-homogeneous in
$S(N^{1/k};N^{\eta})$ (see Definition 2.2).

######  Theorem 10.1 (Supersaturated smooth homogeneous Roth–Sárközy).

Let
$\lambda_{1},\dots,\lambda_{s},\mu_{1},\dots,\mu_{t}\in\mathbb{Z}\setminus\left\\{0\right\\}$
with $\lambda_{1}+\dots+\lambda_{s}=0$. For any $\eta,\delta>0$ and
$M\in\mathbb{N}$ there exists $N_{0}\in\mathbb{N}$ and $c_{0}>0$ such that for
any $N\geqslant N_{0}$ the following holds. If $A$ is at least $\delta$-dense
in $[N]$ and $B$ is $M$-homogeneous in $S(N^{1/k};N^{\eta})$, then there are
at least $c_{0}N^{s+\frac{t}{k}-1}$ tuples $(x,y)\in A^{s}\times B^{t}$
solving the equation

$\lambda_{1}x_{1}+\dots+\lambda_{s}x_{s}=\mu_{1}y_{1}^{k}+\dots+\mu_{t}y_{t}^{k}.$
(10.1)

Notice that Theorem 10.1 is a common generalisation of both the
Furstenberg–Sárközy theorem (take $s=2$ and $t=1$) and Roth’s theorem (take
$\lambda=(1,-2,1)$ and $t=0$).

###### Proof.

Given $A\subset[N]$ of density at least $\delta$, let us define

$\tilde{A}:=\Bigl{\\{}x\in[N]^{s+t-2}:\sum_{i}x_{i}\in A\Bigr{\\}}$

A stars and bars argument shows that for $n\in[N]$ we have

$\\#\left\\{(n_{1},\dots,n_{d})\in[N]^{d}:n=n_{1}+\dots+n_{d}\right\\}=\binom{n-1}{d-1}.$

Since there are at most $\tfrac{1}{2}|A|$ elements $x$ of $A$ satisfying the
inequality $x\leqslant\tfrac{1}{2}|A|$, it follows that for $N\geqslant
C_{s,t}\delta^{-1}$ we have

$|\tilde{A}|=\sum_{n\in A}\binom{n-1}{s+t-3}\gg_{s,t}\delta^{s+t-2}N^{s+t-2}.$
(10.2)

In the statement of Theorem 10.1, at least one of the coefficients
$\lambda_{i}$ must be positive. Relabelling indices, we may assume that
$\lambda_{s}>0$. For a technical reason, it will be useful in a later part of
the argument if we can ensure that

$\tilde{A}-\tilde{A}\subset\left[-\tfrac{N}{\lambda_{s}},\tfrac{N}{\lambda_{s}}\right]^{s+t-2}.$
(10.3)

This follows on partitioning the hypercube $[N]^{s+t-2}$ into subhypercubes of
sufficiently small side length and applying the pigeonhole principle to ensure
that $\tilde{A}$ has large density on one such part (worsening the density
(10.2) by a factor of $O_{s,t,\lambda_{s}}(1)$ in the process).

Define $F\subset\mathbb{Z}^{s+t-2}$ to be the set consisting of the zero
vector together with the rows of the following matrix

$\begin{pmatrix}-\lambda_{s}&\ &\ &\ &\ &\ &\ \\\ \ &-\lambda_{s}&\ &\ &\ &\
&\ \\\ \ &\ &\ddots&\ &\ &\ &\ \\\ \ &\ &\ &-\lambda_{s}&\ &\ &\ \\\
\lambda_{1}&\lambda_{2}&\dots&\lambda_{s-2}&\lambda_{s}^{k-1}\mu_{1}&\dots&\lambda_{s}^{k-1}\mu_{t}\end{pmatrix}.$
(10.4)

Consider the set

$\tilde{B}:=\left\\{y\in\mathbb{N}:\lambda_{s}y\in
B\right\\}\cup(N^{1/k}\lambda_{s}^{-1},\infty).$

Provided that $N^{\eta}\geqslant\max\left\\{\lambda_{s},M\right\\}$ (as we may
assume), we see that $\tilde{B}$ is $M$-homogeneous in the $N^{\eta}$-smooths.
Applying Theorem 9.2, we find that there are at least
$c_{0}N^{s+t-2+s-2+\frac{t}{k}}$ tuples
$(x,y,z)\in\mathbb{Z}^{s+t-2}\times\tilde{B}^{s-2}\times\tilde{B}^{t}$ such
that $\tilde{A}$ contains the configuration

$x+(y_{1},\dots,y_{s-2},z_{1}^{k},\dots,z_{t}^{k})\otimes F.$

By (10.3) and (10.4) we have $\lambda_{s}^{k}\mu_{i}z_{i}^{k}\in[-N,N]$, hence
by definition of $\tilde{B}$ we deduce that $\lambda_{s}z_{i}\in B$.
Projecting down to one dimension and taking into account the multiplicities of
representations, we obtain $\gg N^{s+\frac{t}{k}-1}$ tuples
$(x,y,z)\in\mathbb{Z}\times\mathbb{N}^{s-2}\times\mathbb{N}^{t}$ with
$\lambda_{s}z_{i}\in B$ and such that $A$ contains the configuration

$\begin{split}x,\quad x-\lambda_{s}y_{1},\quad\dots,\quad
x-\lambda_{s}y_{s-2},\quad
x+\sum_{i=1}^{s-2}\lambda_{i}y_{i}+\lambda_{s}^{k-1}\sum_{j=1}^{t}\mu_{j}z_{j}^{k}.\end{split}$

Let us set $x_{i}:=x-\lambda_{s}y_{i}$ for $i=1,\dots,s-2$, along with
$x_{s-1}=x$ and

$x_{s}:=x+\sum_{i=1}^{s-2}\lambda_{i}y_{i}+\lambda_{s}^{k-1}\sum_{j=1}^{t}\mu_{j}z_{j}^{k}.$

One can then check that the tuple
$(x_{1},\dots,x_{s},\lambda_{s}z_{1},\dots,\lambda_{s}z_{t})$ is an element of
$A^{s}\times B^{t}$ satisfying (10.1). By construction there are $\gg
N^{s+\frac{t}{k}-1}$ such tuples. ∎

###  11\. Pseudorandom Roth–Sárközy

In this section we develop a pseudorandom variant of Theorem 10.1. As in Part
I, we begin by relaxing Theorem 10.1 to encompass general bounded functions.
In order to count solutions to our equation weighted by general functions, we
use the following notation.

######  Definition 11.1 ($T_{\ell}$ counting operator).

Fix
$\lambda_{1},\dots,\lambda_{s},\mu_{1},\dots,\mu_{t}\in\mathbb{Z}\setminus\left\\{0\right\\}$
with $\lambda_{1}+\dots+\lambda_{s}=0$. Given functions
$f_{1},\dots,f_{s}:\mathbb{Z}\to\mathbb{C}$ and $B\subset\mathbb{Z}$, write
(when defined)

$\displaystyle
T_{\ell}(f_{1},\dots,f_{s};B):=\sum_{\begin{subarray}{c}\lambda_{1}x_{1}^{\ell}+\dots+\lambda_{s}x_{s}^{\ell}=\\\
\mu_{1}y_{1}^{k}+\dots+\mu_{t}y_{t}^{k}\end{subarray}}f_{1}(x_{1})\dotsm
f_{s}(x_{s})1_{B}(y_{1})\dotsm 1_{B}(y_{t}).$

We write $T_{\ell}(f;B)$ for $T_{\ell}(f,f,\dots,f;B)$ and $T_{\ell}(A;B)$ for
$T_{\ell}(1_{A};B)$.

######  Remark 11.2 (Dependence on constants).

In the sequel we regard the coefficients $\lambda_{i}$ and $\mu_{j}$ as fixed,
and suppress their dependence in any implied constants. Similarly for the
degree $k$ and the number of variables $s+t$. We also fix $\eta=\eta_{k}$
globally: recall that this is 1 if $k=2$, and a small positive constant if
$k\geqslant 3$. We opt to keep any dependence on the following explicit: the
level of homogeneity $M$, and the density $\delta$.

######  Lemma 11.3 (Functional Roth–Sárközy).

For any $\delta>0$ and $M\in\mathbb{N}$ there exist $N_{0}\in\mathbb{N}$ and
$c_{0}>0$ such that for any $N\geqslant N_{0}$ the following holds. Let
$f:[N]\to[0,1]$ with $\left\|f\right\|_{1}\geqslant\delta N$, and let $B$ be
$M$-homogeneous in $S(N^{1/k};N^{\eta})$. Then

$\begin{split}T_{1}(f;B)\geqslant c_{0}N^{s+\frac{t}{k}-1}.\end{split}$

###### Proof.

Let $A=\\{x\in[N]:f(x)\geqslant{\delta}/2\\}$. As
$\|f\|_{1}\geqslant{\delta}N$, we must necessarily have
$|A|\geqslant{\delta}N/2$. Since $f\geqslant{\delta}1_{A}/2$, we deduce that

$T_{1}(f;B)\geqslant({\delta}/2)^{s}T_{1}(A;B),$

and an application of Theorem 10.1 completes the proof. ∎

Our next step is to weaken the assumptions of Theorem 10.1 even further,
replacing bounded functions with unbounded functions which are sufficiently
pseudorandom, in that they possess a majorant with good Fourier decay
(Definition 5.3) and $p$-restriction (Definition 5.4).

######  Theorem 11.4 (Pseudorandom Roth–Sárközy).

There exists $s_{0}(k)$ such that for $s+t\geqslant s_{0}(k)$, $\delta>0$ and
$K,M\in\mathbb{N}$ there exist $N_{0}\in\mathbb{N}$ and $c_{0},\theta>0$ such
that for $N\geqslant N_{0}$ the following holds.

  * •

Let $\nu:[N]\to[0,\infty)$ satisfy a $(s+t-10^{-8})$-restriction estimate with
constant $K$, and have Fourier decay of level $\theta$;

  * •

let $B$ be $M$-homogeneous in $S(N^{1/k};N^{\eta})$;

  * •

let $f:[N]\to[0,\infty)$ with $f\leqslant\nu$ and
$\left\|f\right\|_{1}\geqslant\delta\left\|\nu\right\|_{1}$.

Then

$\begin{split}T_{1}(f;B)\geqslant
c_{0}\left\|\nu\right\|_{1}^{s}N^{\frac{t}{k}-1}.\end{split}$ (11.1)

Moreover, we may take $s_{0}(2)=5$, $s_{0}(3)=8$, and $s_{0}(k)$ satisfying
(1.3).

###### Proof.

By replacing $B$ with $B\cap S(N^{1/k};N^{\eta})$, we may freely suppose that
$B\subset S(N^{1/k};N^{\eta})$. Deploying the dense model lemma [Pre17a,
Theorem 5.1], there exists $g:{\mathbb{Z}}\to{\mathbb{C}}$ satisfying
$0\leqslant g\leqslant 1_{[N]}$ and

$\bigg{\|}\frac{\hat{f}}{\left\|\nu\right\|_{1}}-\frac{\hat{g}}{N}\biggr{\|}_{\infty}\ll\log(\theta^{-1})^{-3/2}.$
(11.2)

Provided that $\theta\leqslant\exp(-C\delta^{-1})$ with $C$ a large positive
constant, we can compare Fourier coefficients at 0 to deduce that
$\left\|g\right\|_{1}\gg\delta N$. Lemma 11.3 then gives

$T_{1}(g;B)\gg_{\delta,M}N^{s+\frac{t}{k}-1}.$ (11.3)

Let $h$ denote the indicator function of the set $\\{x^{k}:x\in B\\}$. Then
for functions $h_{1},\dots,h_{s}:[N]\to[0,\infty)$ we have

$T_{1}(h_{1},\dots,h_{s};B)=\sum_{\lambda\cdot x=\mu\cdot y}h_{1}(x_{1})\dotsm
h_{s}(x_{s})h(y_{1})\dotsm h(y_{t}).$ (11.4)

The function $h$ is majorised by the indicator function of the set

$\\{x^{k}:x\in S(N^{1/k};N^{\eta})\\}$

which, by Lemma B.3, satisfies an $(s+t-10^{-8})$-restriction estimate with
constant $O_{\eta}(1)$.

Observe that $g$ is majorised by $1_{[N]}$, which also satisfies an
$(s+t-10^{-8})$-restriction estimate with constant $O(1)$. The generalised von
Neumann theorem (Lemma C.3), together with (11.2) and (11.4), yields

$\displaystyle\Biggl{|}\frac{T_{1}(f;B)}{\|\nu\|_{1}^{s}}-\frac{T_{1}(g;B)}{N^{s}}\Biggr{|}$
$\displaystyle\ll\frac{K|S(N^{1/k};N^{\eta})|^{t}}{N}\log({\theta}^{-1})^{1.5\times
10^{-8}}$ $\displaystyle\leqslant
KN^{\frac{t}{k}-1}\log({\theta}^{-1})^{1.5\times 10^{-8}}.$

Pairing this with (11.3), and choosing
$\theta\leqslant{\theta}_{0}({\delta},M,K)$, completes the proof.

∎

###  12\. The $W$-trick for smooth powers and a non-linear Roth–Sárközy
theorem

Our objective in this section is to use Theorem 11.4 to deduce the following
non-linear density result. Recall that $\eta=\eta_{k}$ is 1 if $k=2$, and a
small positive constant if $k\geqslant 3$.

######  Theorem 12.1 (Non-linear Roth–Sárközy).

There exists $s_{0}(k)$ such that the following holds. Let
$\lambda_{1},\dots,\lambda_{s},\mu_{1},\dots,\mu_{t}\in\mathbb{Z}\setminus\left\\{0\right\\}$
with $s+t\geqslant s_{0}(k)$ and $\lambda_{1}+\dots+\lambda_{s}=0$. For any
$\delta>0$ and $M\in\mathbb{N}$ there exist $N_{0}\in\mathbb{N}$ and $c_{0}>0$
such that for any $N\geqslant N_{0}$ the following holds. Let $A$ have density
at least $\delta$ in $S(N;N^{\eta})$ and let $B$ be $M$-homogeneous in
$S(N;N^{\eta})$. Then

$\begin{split}\\#\Bigl{\\{}(x,y)\in A^{s}\times
B^{t}:\sum_{i=1}^{s}\lambda_{i}x_{i}^{k}=\sum_{j=1}^{t}\mu_{j}y_{j}^{k}\Bigr{\\}}\geqslant
c_{0}N^{s+t-k}.\end{split}$

Moreover, we may take $s_{0}(2)=5$, $s_{0}(3)=8$, and $s_{0}(k)$ satisfying
(1.3).

This deduction proceeds by developing a $W$-trick for smooth $k$th powers,
analogous to that developed for prime powers in [Cho17]. Let

$W=k^{k-1}\prod_{p\leqslant w}p^{k},$ (12.1)

where $w=w(\eta,\delta,M)$ is a constant to be determined, and the product is
over primes. We apply Lemma A.4 with $S=S(N;N^{\eta})$, using Lemma A.2 in the
process. This allows us to conclude that there exists a $w$-smooth positive
integer $\zeta\ll_{\eta,\delta,w}1$ and $\xi\in[W]$ with $(\xi,W)=1$ such that

$\\#\\{x\in\mathbb{Z}:\zeta(\xi+Wx)\in
A\\}\geqslant\tfrac{1}{2}\delta\\#\\{x\in\mathbb{Z}:\zeta(\xi+Wx)\in
S(N;N^{\eta})\\}.$ (12.2)

Define

$P:=\frac{N}{\zeta},\qquad X:=\frac{P^{k}}{kW}$ (12.3)

and set

$A_{1}:=\left\\{\tfrac{(Wx+\xi)^{k}-\xi^{k}}{kW}:\zeta(Wx+\xi)\in A\text{ and
}Wx+\xi\in S(P;P^{\eta})\right\\}\setminus\left\\{0\right\\}.$ (12.4)

Then $A_{1}\subset[X]$. Combining (12.2) and Lemma A.5, we have the lower
bound

$|A_{1}|\geqslant\tfrac{\delta}{2}\\#\left\\{x\in
S(P;P^{\eta}):x\equiv\xi\bmod W\right\\}-O_{\eta,\delta,w}\left(N(\log
N)^{-1}\right).$ (12.5)

Noting that $(kW)^{1/k}$ is a positive integer, let

$B_{1}:=\bigl{\\{}y\in{\mathbb{N}}:\zeta(kW)^{1/k}y\in B\bigr{\\}}.$ (12.6)

Provided that $N\geqslant\max\left\\{k,w,\zeta\right\\}^{1/\eta}$, one may
check that $B_{1}$ is $M$-homogeneous in $S(X^{1/k};X^{\eta})$. Recalling that
$\sum_{i=1}^{s}\lambda_{i}=0$, we have

$T_{k}(A;B)\geqslant T_{1}(A_{1};B_{1}).$ (12.7)

Define $\nu:[X]\to[0,\infty)$ by

$\nu(n)=\begin{cases}x^{k-1},&\text{if }n=\frac{x^{k}-\xi^{k}}{kW}\text{ for
some }x\in S(P;P^{\eta})\text{ with }x\equiv\xi\bmod W\\\
0,&\text{otherwise.}\end{cases}$ (12.8)

First we check our $L^{1}$ normalisation. Let $\rho(\cdot)$ denote the
Dickman–de Bruijn $\rho$-function (see [Gran08]).

######  Lemma 12.2.

We have

$\sum_{n}\nu(n)=\rho(1/\eta)X+O_{\eta,w}(P^{k}/\log P).$ (12.9)

###### Proof.

Throughout the following argument, all implied constants in our asymptotic
notation are permitted to depend on $k,\eta,w$. Bear in mind that
$\eta\leqslant\eta_{k}$ is small.

From the definition

$\sum_{n}\nu(n)=\sum_{\begin{subarray}{c}x\in S(P;P^{\eta})\\\
x\equiv\xi{\,\,\mathrm{mod}\,\,W}\end{subarray}}x^{k-1}+O(1).$

We obtain from the start of the proof of [Vau89, Lemma 5.4] the fact that if
$m\leqslant P$ then

$\sum_{\begin{subarray}{c}x\in S(m;P^{\eta})\\\
x\equiv\xi{\,\,\mathrm{mod}\,\,W}\end{subarray}}1=\frac{1}{W}\sum_{x\in
S(m;P^{\eta})}1+O\Bigl{(}\frac{P}{\log P}\Bigr{)}.$ (12.10)

Now partial summation and Lemma A.2 yield

$\displaystyle\sum_{n}\nu(n)$
$\displaystyle=W^{-1}P^{k}\rho\left(1/\eta\right)-\int_{P^{1/2}}^{P}\frac{k-1}{W}t^{k-1}\rho\Bigl{(}\frac{\log
t}{\eta\log P}\Bigr{)}{\mathrm{d}}t$
$\displaystyle\qquad+O\Bigl{(}\frac{P^{k}}{\log P}\Bigr{)}$

so, by the mean value theorem and the boundedness of $\rho^{\prime}$, it
remains to show that

$\int_{P^{1/2}}^{P}kt^{k-1}\rho\Bigl{(}\frac{\log t}{\eta\log
P}\Bigr{)}{\mathrm{d}}t=P^{k}\rho\left(1/\eta\right)+O\Bigl{(}\frac{P^{k}}{\log
P}\Bigr{)}.$

Integration by parts gives

$\displaystyle\int_{P^{1/2}}^{P}kt^{k-1}\rho\Bigl{(}\frac{\log t}{\eta\log
P}\Bigr{)}{\mathrm{d}}t$
$\displaystyle=P^{k}\rho\left(1/\eta\right)-P^{k/2}\rho(1/(2\eta))$
$\displaystyle\qquad-\int_{P^{1/2}}^{P}\frac{t^{k-1}}{\eta\log
P}\rho^{\prime}\Bigl{(}\frac{\log t}{\eta\log P}\Bigr{)}{\mathrm{d}}t,$

and the estimate now follows from the boundedness of $\rho,\rho^{\prime}$. ∎

######  Lemma 12.3 (Density transfer).

For $N$ large in terms of $k$, $\eta$, $w$ and ${\delta}$ we have

$\sum_{n\in A_{1}}\nu(n)\gg_{\eta,k}\delta^{k}\sum_{n}\nu(n).$ (12.11)

###### Proof.

We employ (12.5) in conjunction with (12.10) to conclude that

$\displaystyle\\#\Bigl{\\{}x\in S(P;P^{\eta}):x\equiv\xi\bmod
W,\quad\frac{x^{k}-\xi^{k}}{kW}\in A_{1},\quad x>Z\Bigr{\\}}$
$\displaystyle\geqslant|A_{1}|-ZW^{-1}-1$
$\displaystyle\geqslant\tfrac{\delta}{2}\\#\left\\{x\in
S(P;P^{\eta}):x\equiv\xi\bmod W\right\\}-ZW^{-1}-O_{\eta,\delta,w}\left(N(\log
N)^{-1}\right)$
$\displaystyle\geqslant\tfrac{\delta}{2W}|S(P;P^{\eta})|-ZW^{-1}-O_{\eta,\delta,w}\left(N(\log
N)^{-1}\right).$

Choosing

$Z=\frac{\delta}{4}|S(P;P^{\eta})|$

furnishes

$\displaystyle\sum_{n\in A_{1}}\nu(n)$
$\displaystyle\geqslant\tfrac{(\delta/4)^{k}}{W}|S(P;P^{\eta})|^{k}-O_{\eta,\delta,w}\left(N^{k}(\log
N)^{-1}\right).$

Using Lemma A.2 and recalling (12.3) we obtain

$\displaystyle\sum_{n\in A_{1}}\nu(n)$ $\displaystyle\geqslant
W^{-1}({\delta}P\rho(1/\eta)/4)^{k}-O_{\eta,\delta,w}\left(N^{k}(\log
N)^{-1}\right)$
$\displaystyle\geqslant(k(\rho(1/\eta)/4)^{k})\cdot\delta^{k}X-O_{\eta,\delta,w}\left(N^{k}(\log
N)^{-1}\right).$

Taking $N$ sufficiently large, an application of (12.9) completes the proof.∎

The following two ingredients are established in Appendices D and E.

######  Lemma 12.4 (Fourier decay).

We have

$\left\|\frac{\hat{\nu}}{\left\|\nu\right\|_{1}}-\frac{\hat{1}_{[X]}}{X}\right\|_{\infty}\ll_{\eta}w^{-1/k}.$
(12.12)

######  Lemma 12.5 (Restriction estimate).

There exists $s_{0}(k)$ such if $s\geqslant s_{0}(k)$ then

$\begin{split}\sup_{|\phi|\leqslant\nu}\int_{\mathbb{T}}\left|\hat{\phi}(\alpha)\right|^{s-10^{-8}}\mathrm{d}\alpha\ll_{\eta,k}\left\|\nu\right\|_{1}^{s-10^{-8}}X^{-1}.\end{split}$

Moreover, we may take $s_{0}(2)=5$, $s_{0}(3)=8$ and $s_{0}(k)$ satisfying
(1.3).

###### Proof of Theorem 12.1.

We employ Theorem 11.4 with majorant $\nu$ given by (12.8), homogeneous set
$B_{1}\subset S(X^{1/k};X^{\eta})$ given by (12.6), and function $f=\nu
1_{A_{1}}$ (recall (12.4)). It is first necessary to check that these choices
satisfy the hypotheses of Theorem 11.4.

By Lemma 12.5, the function $\nu$ satisfies a $(s+t-10^{-8})$-restriction
estimate with constant $K=O_{\eta,k}(1)$. Let $c_{\eta,k}$ denote the implied
constant in (12.11) and set $\tilde{\delta}:=c_{\eta,k}\delta^{k}$. Theorem
11.4 guarantees the existence of a positive constant

$\theta=\theta(\eta,\tilde{\delta},M,K)$ (12.13)

such that provided $\nu$ has Fourier decay of level $\theta$ and
$\left\|f\right\|_{1}\geqslant\tilde{\delta}\left\|\nu\right\|_{1}$ we may
conclude that (11.1) holds. Taking

$w=C_{\eta}\theta^{k}$

guarantees sufficient Fourier decay, by Lemma 12.4. We note that this choice
of $w$ satisfies $w\ll_{\eta,\delta,M}1$, as can be checked by unravelling the
dependencies in (12.13). We obtain
$\left\|f\right\|_{1}\geqslant\tilde{\delta}\left\|\nu\right\|_{1}$ via Lemma
12.3. This requires us to take $N$ sufficiently large in terms of $k,\eta,w$
and $\delta$. By our choice of $w$, this is ensured if $N$ is sufficiently
large in terms of $\eta,\delta$ and $M$ (as we may assume).

Applying Theorem 11.4 and (12.9) yields

$T_{1}(\nu
1_{A_{1}};B_{1})\gg_{\eta,\delta,M}\|\nu\|_{1}^{s}X^{\frac{t}{k}-1}\gg_{\eta,\delta,M}X^{s+\frac{t}{k}-1}.$

By (12.7) and the bound $\|\nu\|_{\infty}\ll_{\eta,{\delta},M}N^{k-1}$, we
finally have

$T_{k}(A;B)\geqslant T_{1}(A_{1};B_{1})\geqslant\|\nu\|_{\infty}^{-s}T_{1}(\nu
1_{A_{1}};B_{1})\gg_{\eta,{\delta},M}N^{s+t-k}.$

∎

###  13\. Deducing partition regularity

In this final section of this part of the paper we prove a finitary version of
Theorem 1.3.

######  Theorem 13.1 (Smooth finitary colouring result).

Define $s_{0}(k)$ as in Theorem 1.3, and let $s\geqslant s_{0}(k)$. Let
$c_{1},\dots,c_{s}\in\mathbb{Z}\setminus\left\\{0\right\\}$ and suppose that
$\sum_{i\in I}c_{i}=0$ for some non-empty $I$. Then, for any $r\in\mathbb{N}$,
there exists $N_{0}\in\mathbb{N}$ such that the following holds: for any
$N\geqslant N_{0}$, if we have a finite colouring of the $N^{\eta}$-smooth
numbers in $[N]$

$S(N;N^{\eta})=C_{1}\cup\dots\cup C_{r},$

then there exists a colour $i\in[r]$ and distinct $x_{1},\dots,x_{s}\in C_{i}$
solving (1.2).

####  13.1. The inductive base: one colour

As in §4, given functions $f_{1},\dots,f_{s}:\mathbb{Z}\to\mathbb{C}$ with
finite support, define the counting operator

$\displaystyle
T(f_{1},\dots,f_{s}):=\sum_{c_{1}x_{1}^{k}+\dots+c_{s}x_{s}^{k}=0}f_{1}(x_{1})f_{2}(x_{2})\dotsm
f_{s}(x_{s})$

and write $T(f)$ for $T(f,f,\dots,f)$.

It follows from Theorem B.1 that there exist $\eta=\eta(k)>0$,
$N_{1}=N_{1}(\eta,k,\mathbf{c})\in\mathbb{N}$ and
$c_{1}=c_{1}(\eta,k,\mathbf{c})>0$ such that for $N\geqslant N_{1}$ and we
have

$T(1_{S(N;N^{\eta})})\geqslant c_{1}N^{s-k}.$

By Lemma B.4, the number of trivial solutions in $S(N;N^{\eta})$ is
$o(N^{s-k})$, so there must be at least one non-trivial solution
$(x_{1},\ldots,x_{s})\in S(N;N^{\eta})^{s}$ to (1.2) for $N$ sufficiently
large in terms of $\eta$, $k$, $s$ and $\mathbf{c}$. The base case follows.

####  13.2. The inductive step

Let $S(N;N^{\eta})=C_{1}\cup\dots\cup C_{r}$. Re-labelling indices, we may
assume that $C_{r}$ is the largest colour class, so that

$|C_{r}|\geqslant|S(N;N^{\eta})|/r.$ (13.1)

We split our proof into two cases depending on the properties of $C_{r}$.

#####  13.2.1. The inhomogeneous case

Let $M:=N_{0}(r-1)$ be the quantity whose existence is guaranteed by our
inductive hypothesis. We may assume that $N\geqslant M^{1/\eta}$, so every
element of $[M]$ is $N^{\eta}$-smooth. First let us suppose that $C_{r}$ is
not $M$-homogeneous in $S(N;N^{\eta})$. Consequently there exists $q\in
S(N/M;N^{\eta})$ such that

$\begin{split}C_{r}\cap q\cdot[M]=\emptyset.\end{split}$ (13.2)

For $i=1,\dots,r-1$ let us define

$C_{i}^{\prime}:=\left\\{x\in S(M;M^{\eta}):qx\in C_{i}\right\\}.$

Then it follows from (13.2) that $C_{1}^{\prime}\cup\dots\cup
C_{r-1}^{\prime}=S(M;M^{\eta})$. By the induction hypothesis, there exist
distinct elements of some $C^{\prime}_{i}$ which solve (1.2). Since this
equation is homogeneous, we obtain a non-trivial solution in $C_{i}$ by
multiplying the equation through by $q^{k}$.

#####  13.2.2. The homogeneous case

We now assume that $C_{r}$ is $M$-homogeneous in $S(N;N^{\eta})$. We apply
Theorem 12.1, taking $A=B=C_{r}$. By (13.1) the density of $A$ in
$S(N;N^{\eta})$ is at least $\tfrac{1}{r}$. Theorem 12.1 then implies that,
provided $N\geqslant N_{0}(\eta,1/r,M)$ we have

$T(1_{C_{r}})\geqslant c_{0}(\eta,1/r,M)N^{s-k}.$

By Lemma B.4, the number of solutions in $S(N;N^{\eta})$ with two or more
coordinates equal is $o(N^{s-k})$, hence taking $N$ sufficiently large yields
at least one non-trivial solution in $C_{r}$. We note that a quantity
dependent on the tuple $(\eta,1/r,M)$ is ultimately dependent only on $\eta$
and $r$, by the definition of $M$. The induction step thereby follows,
completing the proof of Theorem 13.1.

##  Part III Supersmooths and shifted squares

In this part we establish Rado’s criterion for a linear equation in
logarithmically-smooth numbers (Theorem 1.7). Furthermore, we show how a
direct application of the transference principle yields a supersaturated
version of this result, and analogously for a linear equation in the set of
squares minus one (Theorem 1.4). Both of these results are established without
recourse to properties of homogeneous sets. This reflects the fact that
supersmooths and shifted squares possess subsets which can be projectively
transformed to obtain equidistribution in congruence classes to small moduli,
ruling out possible local obstructions to partition regularity—obstructions
which must be surmounted when working with perfect squares and higher powers.
This phenomenon manifests itself when massaging the perfect powers to obtain
equidistribution; this can be done, but requires an _affine_ transformation,
as opposed to a projective one. Unfortunately, a typical equation satisfying
Rado’s criterion is only projectively invariant, so the methods of this part
do not succeed in establishing partition regularity for equations in perfect
powers.

###  14\. Modelling a pseudorandom partition with a colouring

As described above, the proofs of Theorems 1.4 and 1.7 proceed by first
passing to a subset of the sparse arithmetic set of interest (supersmooths or
shifted squares). We then projectively transform this subset to obtain a set
which is well distributed in arithmetic progressions to small moduli. We can
then define a weight $\nu:[N]\to\infty$ supported on our equidistributed set
which has nice pseudorandomness properties.

Given a finite colouring of our original arithmetic set, the above procedure
induces a finite partition of our pseudorandom weight function into non-
negative functions $f_{i}$, so that

$\nu=\sum_{i}f_{i}.$

Deducing supersaturation then amounts to showing that the count of solutions
to our equation weighted by some $f_{i}$ is within a constant factor of the
maximum possible.

The main tool in deriving this lower bound is to model the $f_{i}$ with
functions $g_{i}$ whose sum dominates the indicator function of the interval
$1_{[N]}$. It is a short step to show that, in essence, we may assume that the
$g_{i}$ correspond to indicator functions of a colouring of $[N]$. For such
colourings there is already a supersaturation result in the literature due to
Frankl, Graham and Rödl [FGR88, Theorem 1]. Employing this theorem and then
(quantitatively) retracing our steps yields Theorems 1.4 and 1.7.

In this section we establish the modelling part of the above procedure: non-
negative functions $f_{i}$ with pseudorandom sum $\sum_{i}f_{i}$ have
approximants $g_{i}$ whose sum dominates the constant function $1_{[N]}$. This
‘transference principle’666This is also referred to as a ‘dense model’ or
‘bounded approximation’ lemma in the literature. for colourings is based on
Green’s transference principle for dense sets [Gre05], as exposited in
[Pre17a]. We recall the concepts of Fourier decay and $p$-restriction given in
Definitions 5.3 and 5.4.

######  Proposition 14.1 (Modelling lemma).

Suppose that $\nu:[N]\to[0,\infty)$ satisfies a $p$-restriction estimate with
constant $K$, and has Fourier decay of level $1/M$ with $M\geqslant
M_{0}(p,K)$ . Then for any $f_{i}:[N]\to[0,\infty)$ with
$f_{1}+\dots+f_{r}=\nu$ there exists $g_{i}:[N]\to[0,\infty)$ such that
$g_{1}+\dots+g_{r}=(1+\tfrac{1}{\sqrt{M}})1_{[N]}$ and

$\bigg{\|}\frac{\hat{f}_{i}}{\left\|\nu\right\|_{1}}-\frac{\hat{g}_{i}}{N}\biggr{\|}_{\infty}\ll_{r,p,K}(\log
M)^{-\frac{1}{p+2}}\qquad(1\leqslant i\leqslant r).$

Let ${\kappa},\varepsilon>0$ be parameters, to be determined later. In proving
this result we utilise the large spectrum of $f_{i}$, which we take as

$S_{i}:=\left\\{\alpha\in\mathbb{T}:|\hat{f}_{i}(\alpha)|\geqslant{\kappa}\left\|\nu\right\|_{1}\right\\}.$
(14.1)

Define the Bohr set with frequencies $S:=S_{1}\cup\dots\cup S_{r-1}$ and width
$\varepsilon\leqslant 1/2$ by

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

Next define

$g_{i}:=\frac{Nf_{i}*1_{B}*1_{B}}{\left\|\nu\right\|_{1}|B|^{2}}\qquad(1\leqslant
i\leqslant r-1),$

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

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

We first estimate
$\big{|}\frac{\hat{f}_{i}}{\left\|\nu\right\|_{1}}-\frac{\hat{g}_{i}}{N}\big{|}$
with $i=1,\dots,r-1$. The key identity is

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

If $\alpha\in\mathbb{T}\setminus S$ then by the definition (14.1) of the large
spectrum we have

$\biggl{|}\frac{\hat{f}_{i}(\alpha)}{\left\|\nu\right\|_{1}}-\frac{\hat{g}_{i}(\alpha)}{N}\biggr{|}=\biggl{|}\frac{\hat{f}_{i}(\alpha)}{\left\|\nu\right\|_{1}}\biggr{|}\left|1-\tfrac{\hat{1}_{B}(\alpha)^{2}}{|B|^{2}}\right|\leqslant
2{\kappa}.$

If $\alpha\in S$, then for each $n\in B$ we have $e(\alpha
n)=1+O(\varepsilon).$ Hence

$\hat{1}_{B}(\alpha)=|B|+O(\varepsilon|B|),$

and consequently

$\biggl{|}\frac{\hat{f}_{i}(\alpha)}{\left\|\nu\right\|_{1}}-\frac{\hat{g}_{i}(\alpha)}{N}\biggr{|}=\biggl{|}\frac{\hat{f}_{i}(\alpha)}{\left\|\nu\right\|_{1}}\biggr{|}\left|1+\tfrac{\hat{1}_{B}(\alpha)}{|B|}\right|\left|1-\tfrac{\hat{1}_{B}(\alpha)}{|B|}\right|\ll\varepsilon.$

Combining both cases gives

$\bigg{\|}\frac{\hat{f}_{i}}{\left\|\nu\right\|_{1}}-\frac{\hat{g}_{i}}{N}\biggr{\|}_{\infty}\ll\varepsilon+{\kappa}.$

From this it is apparent we should choose ${\kappa}=\varepsilon$, which we do.

We will show that, for any $n$, the sum $\sum_{i\leqslant r-1}g_{i}(n)$ is
almost bounded above by 1. By positivity and orthogonality, we have

$\displaystyle\sum_{i=1}^{r-1}g_{i}(n)$
$\displaystyle=N\left\|\nu\right\|_{1}^{-1}|B|^{-2}\sum_{x+y+z=n}\sum_{i=1}^{r-1}f_{i}(x)1_{B}(y)1_{B}(z)$
$\displaystyle\leqslant
N\left\|\nu\right\|_{1}^{-1}|B|^{-2}\sum_{x+y+z=n}\nu(x)1_{B}(y)1_{B}(z)$
$\displaystyle=N\left\|\nu\right\|_{1}^{-1}|B|^{-2}\int_{\mathbb{T}}\hat{\nu}(\alpha)\hat{1}_{B}(\alpha)^{2}e(-\alpha
n)\mathrm{d}\alpha.$

Inserting our Fourier decay assumption, and using Parseval, yields

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

Following the proof of [Pre17a, Lemmas A.1 and A.2], the restriction estimate
yields a constant $C=C(p,K)>1$ such that
$|B|\geqslant\exp(-C\varepsilon^{-p-2})N.$ Taking $\varepsilon=(2C/\log
M)^{\frac{1}{p+2}}$ with $M$ large, we deduce that

$\sum_{i=1}^{r-1}g_{i}(n)\leqslant 1+1/\sqrt{M},$ (14.2)

and that

$\bigg{\|}\frac{\hat{f}_{i}}{\left\|\nu\right\|_{1}}-\frac{\hat{g}_{i}}{N}\biggr{\|}_{\infty}\ll\varepsilon\ll_{p,K}\left(\log
M\right)^{-\frac{1}{p+2}}\qquad(1\leqslant i\leqslant r-1).$

Having found suitable bounded approximants $g_{i}$ for $i=1,\dots,r-1$, we
define

$g_{r}:=\left(1+\tfrac{1}{\sqrt{M}}\right)1_{[N]}-(g_{1}+\dots+g_{r-1}).$

This is non-negative, by (14.2). Finally, we calculate how well $g_{r}$
approximates $f_{r}=\nu-(f_{1}+\dots+f_{r-1})$. The triangle inequality gives

$\begin{split}\bigg{\|}\frac{\hat{f}_{r}}{\left\|\nu\right\|_{1}}-\frac{\hat{g}_{r}}{N}\biggr{\|}_{\infty}&\leqslant\frac{1}{\sqrt{M}}+\bigg{\|}\frac{\hat{\nu}}{\left\|\nu\right\|_{1}}-\frac{\hat{1}_{[N]}}{N}\biggr{\|}_{\infty}+\sum_{i=1}^{r-1}\bigg{\|}\frac{\hat{f}_{i}}{\left\|\nu\right\|_{1}}-\frac{\hat{g}_{i}}{N}\biggr{\|}_{\infty}\\\
&\ll_{r,p,K}1/(\log M)^{\frac{1}{p+2}}.\end{split}$

###  15\. A pseudorandom Rado theorem

Frankl, Graham and Rödl [FGR88, Theorem 1] proved that if
$c_{1},\dots,c_{s}\in\mathbb{Z}\setminus\left\\{0\right\\}$ are such that
$\sum_{i\in I}c_{i}=0$ for some non-empty $I\subset[s]$, then for any $r$
there exists $c_{0}=c_{0}(r,\mathbf{c})>0$ such that in any $r$-colouring of
$[N]$ there are at least $c_{0}N^{s-1}$ monochromatic solutions $\mathbf{x}$
to the equation

$\begin{split}c_{1}x_{1}+\dots+c_{s}x_{s}=0.\end{split}$

The purpose of this section is to generalise this result from colourings to
partitions of pseudorandom functions.

######  Proposition 15.1 (Pseudorandom FGR).

Let $c_{1},\dots,c_{s}\in\mathbb{Z}\setminus\left\\{0\right\\}$ with
$\sum_{i\in I}c_{i}=0$ for some non-empty $I\subset[s]$. For any
$r,K\in\mathbb{N}$ there exist $N_{0},M\in\mathbb{N}$ and $c_{0}>0$ such that
for $N\geqslant N_{0}$ the following holds. Let $\nu:[N]\to[0,\infty)$ satisfy
a $(s-0.005)$-restriction estimate with constant $K$, and have Fourier decay
of level $1/M$. Then for any partition $\nu=\sum_{i\leqslant r}f_{i}$ with
$f_{i}$ non-negative we have

$\begin{split}\sum_{i=1}^{r}\sum_{\mathbf{c}\cdot\mathbf{x}=0}f_{i}(x_{1})\dotsm
f_{i}(x_{s})\geqslant c_{0}\left\|\nu\right\|_{1}^{s}N^{-1}.\end{split}$
(15.1)

We begin the proof of this theorem by generalising [FGR88] from colourings to
bounded weights.

######  Lemma 15.2 (Functional FGR).

Let $c_{1},\dots,c_{s}\in\mathbb{Z}\setminus\left\\{0\right\\}$ with
$\sum_{i\in I}c_{i}=0$ for some non-empty $I\subset[s]$. For any $r$ there
exists $N_{0}\in\mathbb{N}$ and $c_{0}>0$ such that for $N\geqslant N_{0}$ and
$g_{1},\dots,g_{r}:[N]\to[0,\infty)$ with $\sum_{i}g_{i}\geqslant 1_{[N]}$ we
have

$\begin{split}\sum_{i=1}^{r}\sum_{\mathbf{c}\cdot\mathbf{x}=0}g_{i}(x_{1})\dotsm
g_{i}(x_{s})\geqslant c_{0}N^{s-1}.\end{split}$

###### Proof.

By the pigeonhole principle, for each $x\in[N]$ there exists $i\in[r]$ such
that $g_{i}(x)\geqslant 1/r$. Let $i$ be minimal with this property, and
assign $x$ the colour $i$. By the result of Frankl, Graham and Rödl, for some
such choice of $i$ there are at least $c^{\prime}_{0}N^{s-1}$ tuples
$\mathbf{x}$ where each coordinate receives the colour $i$ and such that
$\mathbf{c}\cdot\mathbf{x}=0$. It follows that

$\begin{split}\sum_{\mathbf{c}\cdot\mathbf{x}=0}g_{i}(x_{1})\dotsm
g_{i}(x_{s})\geqslant r^{-s}c^{\prime}_{0}N^{s-1}.\end{split}$

∎

With this in hand, we proceed to prove Proposition 15.1. Since $\nu$ satisfies
a $(s-0.005)$-restriction estimate with constant $K$, and has Fourier decay of
level $1/M$, we may apply the modelling lemma (Proposition 14.1, provided
$M\geqslant M_{0}(s,K)$ as we may assume) to conclude the existence of
$g_{i}:[N]\to[0,\infty)$ with $\sum_{i}g_{i}=(1+\tfrac{1}{\sqrt{M}})1_{[N]}$
and

$\bigg{\|}\frac{\hat{f}_{i}}{\left\|\nu\right\|_{1}}-\frac{\hat{g}_{i}}{N}\biggr{\|}_{\infty}\ll_{r,s,K}(\log
M)^{-\frac{1}{p+2}}\qquad(1\leqslant i\leqslant r),$

where $p=s-0.005$. This also implies that

$\bigg{\|}\frac{\hat{f}_{i}}{\left\|\nu\right\|_{1}}-\frac{\hat{g}_{i}}{(1+M^{-1/2})N}\biggr{\|}_{\infty}\ll_{r,s,K}(\log
M)^{-\frac{1}{p+2}}\qquad(1\leqslant i\leqslant r).$

Applying Lemma 15.2 (provided that $N\geqslant N_{0}(r,\mathbf{c})$, as we may
assume) furnishes a colour class $i$ for which

$\sum_{\mathbf{c}\cdot\mathbf{x}=0}g_{i}(x_{1})\dotsm
g_{i}(x_{s})\gg_{r,{\mathbf{c}}}N^{s-1}.$

Our assumption that $\sum_{i\in I}c_{i}=0$ ensures that
$s\geqslant|I|\geqslant 2$. We may in fact assume that $s\geqslant 3$, for if
$s=|I|=2$ then Proposition 15.1 is trivial. Hence $(1+M^{-1/2})1_{[N]}$
satisfies a $(s-0.005)$-restriction estimate with constant 1, and majorises
each $g_{i}$. Employing the generalised von Neumann lemma (Lemma C.3), with
$i$ as in the previous paragraph, we deduce that

$\frac{N}{\left\|\nu\right\|_{1}^{s}}\sum_{\mathbf{c}\cdot\mathbf{x}=0}f_{i}(x_{1})\dotsm
f_{i}(x_{s})\geqslant
c_{0}(r,{\mathbf{c}})-O_{r,{\mathbf{c}},K}\left(\left(\log
M\right)^{-\frac{1}{400s}}\right).$

Assuming that $M\geqslant M_{0}(r,{\mathbf{c}},K)$ completes the proof of
Proposition 15.1.

###  16\. Supersaturation for shifted squares

In this section we relate a colouring of the shifted squares to a partition of
a pseudorandom majorant $\nu$ satisfying the hypotheses of Proposition 15.1,
and thereby prove Theorem 1.4. As in §6, we accomplish this through the
$W$-trick for squares.

Define $W$ by (6.1), where $w=w(\mathbf{c},r)$ is a constant to be determined.
Let

$S^{\prime}:=\left\\{\tfrac{1}{2}Wx^{2}+x:x\in{\mathbb{N}},(Wx+1)^{2}\leqslant
N\right\\},$

so that $S^{\prime}\subset[N^{\prime}]$, where $N^{\prime}:=N/(2W)$. If $c$ is
an $r$-colouring of the squares minus one, we induce an $r$-colouring of
$S^{\prime}$ via

$c^{\prime}(\tfrac{1}{2}Wx^{2}+x):=c\left((Wx+1)^{2}-1\right).$

Let $S_{1}^{\prime},\dots,S_{r}^{\prime}$ denote the induced colour classes.
From the definition of $S^{\prime}$ and the homogeneity of the equation, we
see that the left-hand side of (1.4) is at least as large as

$\sum_{i=1}^{r}\sum_{\mathbf{c}\cdot\mathbf{x}=0}1_{S_{i}^{\prime}}(x_{1})\dotsm
1_{S_{i}^{\prime}}(x_{s}).$ (16.1)

As in (6.5), define a weight function $\nu:[N^{\prime}]\to[0,\infty)$
supported on $S^{\prime}$ by

$\nu(n)=\begin{cases}Wx+1,&\text{if }n=\tfrac{1}{2}Wx^{2}+x\in
S^{\prime}\text{ for some }x\in\mathbb{N}\\\ 0,&\text{otherwise.}\end{cases}$
(16.2)

We reassure the reader that neither the constant term 1 nor the factor $W$
appearing above are necessary, but their presence is consistent with (6.5) and
(12.8). A calculation similar to (6.6) gives

$\left\|\nu\right\|_{1}\gg\left\|\nu\right\|_{\infty}|S^{\prime}|\gg_{w}\left\|\nu\right\|_{\infty}|S\cap[N]|,$

where $S$ is the set of shifted squares as defined in the theorem.

We recall that $W$ ultimately depends only on $w=w(\mathbf{c},r)$. Therefore,
to show that (16.1) is of order $|S\cap[N]|^{s}N^{-1}$, and hence to prove
Theorem 1.4, it suffices to establish that for $f_{i}=\nu 1_{S_{i}^{\prime}}$
we have

$\sum_{i=1}^{r}\sum_{\mathbf{c}\cdot\mathbf{x}=0}f_{i}(x_{1})\dotsm
f_{i}(x_{s})\gg_{r,{\mathbf{c}}}\left\|\nu\right\|_{1}^{s}(N^{\prime})^{-1}.$
(16.3)

Appendices D and E yield the following.

######  Lemma 16.1 (Fourier decay).

We have

$\bigg{\|}\frac{\hat{\nu}}{\left\|\nu\right\|_{1}}-\frac{\hat{1}_{[N^{\prime}]}}{N^{\prime}}\biggr{\|}_{\infty}\ll
w^{-1/2}.$

######  Lemma 16.2 (Restriction estimate).

We have

$\begin{split}\sup_{|\phi|\leqslant\nu}\int_{\mathbb{T}}\left|\hat{\phi}(\alpha)\right|^{4.995}\mathrm{d}\alpha\ll\left\|\nu\right\|_{1}^{4.995}(N^{\prime})^{-1}.\end{split}$

Let $K$ denote the absolute constant occurring in Lemma 16.2, and let
$N_{0},M$ denote the parameters occurring in Proposition 15.1. By Lemma 16.1,
provided that we take $w=w(r,\mathbf{c})$ sufficiently large, we may apply
Proposition 15.1 with $f_{i}=\nu 1_{S_{i}^{\prime}}$ to conclude that (16.3)
holds. This completes the proof of Theorem 1.4.

###  17\. Supersaturation for logarithmically-smooth numbers

The proof of Theorem 1.7 follows in analogy with the argument of the prior
section. The situation is somewhat simpler in this context, as there is no
need to massage the set of smooths to exhibit sufficient pseudorandomness.

Define the indicator function $\nu:[N]\to[0,\infty)$ of the $R$-smooth numbers
in $[N]$ by

$\nu(x):=\begin{cases}1&\text{if }p\mid x\implies p\leqslant R\\\
0&\text{otherwise.}\end{cases}$

The relevant pseudorandomness properties follow from work of Harper [Har16].

######  Lemma 17.1 ([Har16, Theorem 2]).

There exists an absolute constant $C>0$ such that for $R\geqslant\log^{C}N$ we
have

$\begin{split}\sup_{|\phi|\leqslant\nu}\int_{\mathbb{T}}\left|\hat{\phi}(\alpha)\right|^{2.995}\mathrm{d}\alpha\ll\left\|\nu\right\|_{1}^{2.995}N^{-1}.\end{split}$

######  Lemma 17.2 ([Har16, §5]).

We have the Fourier decay estimate

$\bigg{\|}\frac{\hat{\nu}}{\left\|\nu\right\|_{1}}-\frac{\hat{1}_{[N]}}{N}\biggr{\|}_{\infty}\ll\frac{\log\log
N}{\log R}.$

###### Proof of Theorem 1.7.

We are assuming that $\sum_{i\in I}c_{i}=0$ for some $I\neq\emptyset$, and
this forces $s\geqslant 2$. If $s=2$ then we are counting monochromatic
solutions to $x_{1}-x_{2}=0$, for which we have the lower bound
$|S(N;R)|\geqslant|S(N;R)|^{2}N^{-1}$.

Let us therefore assume that $s\geqslant 3$. Provided that
$R\geqslant\log^{C}N$ we have that $\nu$ satisfies a $p=2.995$ restriction
estimate with constant $K=O(1)$. Applying Proposition 15.1 with these
parameters, there exist $N_{0},M,c_{0}>0$ such that (1.5) holds, provided that
$\nu$ has Fourier decay of level $M^{-1}$. This can be guaranteed on employing
Lemma 17.2 and ensuring that

$R\geqslant\log^{C}N,$

where $C=C(r,{\mathbf{c}})$ is sufficiently large. ∎

##  Part IV Appendices

###  Appendix A Results on smooth numbers

######  Definition A.1 ($R$-smooth numbers).

We say that a positive integer is _$R$ -smooth_ if all of its prime divisors
are at most $R$. We denote the set of such numbers in the interval $[N]$ by

$S(N;R):=\left\\{n\in[N]:p\mid n\implies p\leqslant R\right\\}.$

The following estimate was proved by de Bruijn; see [Gran08, Eq. (1.8)]. Here
$\rho:[0,\infty)\to(0,1]$ denotes the Dickman–de Bruijn $\rho$-function. Note
that $\rho$ is decreasing and has bounded derivative.

######  Lemma A.2.

We have

$|S(N;N^{\eta})|=\rho(1/\eta)N+O_{\eta}\left(N/\log N\right).$

In particular, there exists $N_{0}=N_{0}(\eta)$ such that for $N\geqslant
N_{0}$ we have

$|S(N;N^{\eta})|\gg_{\eta}N.$

######  Lemma A.3.

There are at most $10^{w}NM^{-1/2}$ elements of $[N]$ divisible by a
$w$-smooth number greater than $M$.

###### Proof.

It follows from Rankin’s trick that the number of integers in $[N]$ divisible
by a $w$-smooth number exceeding $M$ is at most

$\displaystyle\sum_{\begin{subarray}{c}m>M\\\ \text{$m$ is
$w$-smooth}\end{subarray}}\frac{N}{m}$
$\displaystyle\leqslant\sum_{\begin{subarray}{c}\text{$m$ is
$w$-smooth}\end{subarray}}\frac{N}{m}\left(\frac{m}{M}\right)^{1/2}=NM^{-1/2}\prod_{p\leqslant
w}\left(1+\frac{1}{p^{1/2}-1}\right).$

The result follows on noting that $1+\frac{1}{p^{1/2}-1}\leqslant 10$. ∎

Notice that if $W$ is a $w$-smooth positive integer divisible by the primorial
$\prod_{p\leqslant w}p$, then every positive integer can be written in the
form $\zeta(\xi+Wy)$ for a unique choice of a $w$-smooth positive integer
$\zeta$ and a unique $\xi\in[W]$ with $(\xi,W)=1$.

######  Lemma A.4.

Let $W$ be a $w$-smooth positive integer divisible by the primorial
$\prod_{p\leqslant w}p$. For any sets $A\subset S\subset[N]$ with
$|A|\geqslant\delta|S|$ and $|S|\geqslant\eta N$, there exist a $w$-smooth
number $\zeta\ll_{{\delta},\eta,w}1,$ and $\xi\in[W]$ with $(\xi,W)=1$, such
that

$\\#\left\\{x\in\mathbb{Z}:\zeta(\xi+Wx)\in
A\right\\}\geqslant\tfrac{1}{2}\delta\\#\left\\{x\in\mathbb{Z}:\zeta(\xi+Wx)\in
S\right\\}.$

###### Proof.

For $\zeta,\xi\in{\mathbb{N}}$ and $T\subseteq\mathbb{Z}$, write

$T_{\zeta,\xi,W}:=\left\\{x\in T:x=\zeta(\xi+Wy)\text{ for some
}y\in\mathbb{Z}\right\\}.$

Let $M=4({\delta}\eta)^{-2}10^{2w}$, so that
$N10^{w}M^{-1/2}=\frac{{\delta}}{2}\eta N\leqslant\frac{{\delta}}{2}|S|$. By
the remarks preceding this lemma, together with Lemma A.3, we have

$\displaystyle{\delta}|S|\leqslant|A|$
$\displaystyle\leqslant\sum_{\begin{subarray}{c}\zeta\leqslant M\\\
\zeta\text{ is $w$-smooth}\end{subarray}}\sum_{\begin{subarray}{c}\xi\in[W]\\\
\ (\xi,W)=1\end{subarray}}|A_{\zeta,\xi,W}|+N10^{w}M^{-1/2}$
$\displaystyle\leqslant\sum_{\begin{subarray}{c}\zeta\leqslant M\\\
\zeta\text{ is $w$-smooth}\end{subarray}}\sum_{\begin{subarray}{c}\xi\in[W]\\\
\ (\xi,W)=1\end{subarray}}|A_{\zeta,\xi,W}|+\frac{{\delta}}{2}|S|.$

Therefore

$\delta\sum_{\begin{subarray}{c}\zeta\leqslant M\\\ \zeta\text{ is
$w$-smooth}\end{subarray}}\sum_{\begin{subarray}{c}\xi\in[W]\\\ \
(\xi,W)=1\end{subarray}}|S_{\zeta,\xi,W}|\leqslant{\delta}|S|\leqslant
2\sum_{\begin{subarray}{c}\zeta\leqslant M\\\ \zeta\text{ is
$w$-smooth}\end{subarray}}\sum_{\begin{subarray}{c}\xi\in[W]\\\ \
(\xi,W)=1\end{subarray}}|A_{\zeta,\xi,W}|,$

and the pigeonhole principle completes the proof. ∎

######  Lemma A.5.

For any $K\geqslant 1$ we have

$S(N;KN^{\eta})-S(N;N^{\eta})\ll_{K,\eta}\frac{N}{\log N}.$

###### Proof.

By Lemma A.2, we have

$\frac{S(N;KN^{\eta})-S(N;N^{\eta})}{N}=\rho\Bigl{(}\frac{\log N}{\eta\log
N+\log K}\Bigr{)}-\rho(1/\eta)+O(1/\log N).$

The estimate now follows from the mean value theorem, since $\rho^{\prime}$ is
bounded and

$\frac{\log N}{\eta\log N+\log K}-\frac{1}{\eta}\ll\frac{1}{\log N}.$

∎

###  Appendix B The unrestricted count and mean values estimates

Recall that $\eta$ is 1 if $k=2$ and a small positive constant if $k\geqslant
3$. The following is a consequence of the current state of knowledge in
Waring’s problem.

######  Theorem B.1.

Let $c_{1},\dots,c_{s}\in\mathbb{Z}\setminus\left\\{0\right\\}$ with
$\sum_{i\in I}c_{i}=0$ for some non-empty subset $I$ of $[s]$. Then, for
$k\geqslant 2$, there exists $s_{0}(k)\in{\mathbb{N}}$ such that if
$s\geqslant s_{0}(k)$ and $N\geqslant N_{0}$ then

$\\#\Bigl{\\{}{\mathbf{x}}\in
S(N;N^{\eta})^{s}:\sum_{i=1}^{s}c_{i}x_{i}^{k}=0\Bigr{\\}}\asymp_{{\mathbf{c}},\eta,k}N^{s-k}.$

Moreover, one can take $s_{0}(2)=5$, $s_{0}(3)=8$, and $s_{0}(k)$ satisfying
(1.3).

The $k=2$ case was known to Hardy and Littlewood. In an influential paper,
Kloosterman [Klo27] opens with a discussion of this, then adapts the
Hardy–Littlewood method to address the quaternary problem. Details of a proof
may be found in [Dav2005, Ch. 8].

As we cannot find the precise statement that we require for $k\geqslant 3$ in
the literature, we outline a proof below. The conclusion largely follows from
the earlier techniques of Vaughan and of Wooley [Vau89, VW91, Woo92], but we
find it convenient to also draw material from other sources. Indeed, the
aforementioned articles on Waring’s problem involve a combination of smooth
and full-range variables, so for our lower bound the results cannot be
imported directly. Theorem B.1 is an indefinite version of a special case of
[DS16, Theorem 2.4]; the latter is more profound, as it tackles a more
challenging smoothness regime. One approach would be simply to imitate the
proof of that theorem, until needing to treat the local factors—this is
approximately what we do below.

###### Proof.

Let $k\geqslant 3$, and let $\eta=\eta_{k}$ be a small positive constant. By
orthogonality, our count is

$\int_{0}^{1}g_{1}({\alpha})\cdots g_{s}({\alpha}){\mathrm{d}}{\alpha},$

where

$g({\alpha})=\sum_{x\in S(N;N^{\eta})}e({\alpha}x^{k}),\qquad
g_{i}({\alpha})=g(c_{i}{\alpha})\quad(1\leqslant i\leqslant s).$

Let $A\geqslant A_{0}(k)$, and put $Q=(\log N)^{A}$. Now perform a
Hardy–Littlewood dissection [Vau97]: define major arcs

${\mathfrak{M}}=\bigcup_{\begin{subarray}{c}0\leqslant a<q\leqslant Q\\\
(a,q)=1\end{subarray}}{\mathfrak{M}}(q,a),\qquad{\mathfrak{M}}(q,a)=\\{{\alpha}\in[0,1]:|q{\alpha}-a|\leqslant
QN^{-k}\\}$

and minor arcs ${\mathfrak{m}}=[0,1]\setminus{\mathfrak{M}}$. It follows from
[DS16, Lemma 8.6], by slightly adjusting the parameters therein to allow for
constant multiples, that

$\int_{\mathfrak{m}}|g_{i}({\alpha})|^{s}{\mathrm{d}}{\alpha}=c_{i}^{-1}\int_{c_{i}{\mathfrak{m}}}|g({\beta})|^{s}{\mathrm{d}}{\beta}\ll
N^{s-k}Q^{-c},$

for some $c=c(k)>0$. Therefore

$\int_{0}^{1}g_{1}({\alpha})\cdots
g_{s}({\alpha}){\mathrm{d}}{\alpha}=\int_{\mathfrak{M}}g_{1}({\alpha})\cdots
g_{s}({\alpha}){\mathrm{d}}{\alpha}+o(N^{s-k}).$

First we prune our major arcs down to a lower height. Set $Q_{1}=\sqrt{\log
N}$. Let

${\mathfrak{N}}=\bigcup_{\begin{subarray}{c}0\leqslant a<q\leqslant Q_{1}\\\
(a,q)=1\end{subarray}}{\mathfrak{N}}(q,a),\qquad{\mathfrak{N}}(q,a)=\\{{\alpha}\in[0,1]:|q{\alpha}-a|\leqslant
Q_{1}N^{-k}\\},$

and put ${\mathfrak{n}}=[0,1]\setminus{\mathfrak{N}}$. Let
${\alpha}\in{\mathfrak{M}}(q,a)$ with $0\leqslant a<q\leqslant Q$ and
$(a,q)=1$ and, by Dirichlet’s approximation theorem [Vau97, Lemma 2.1], choose
relatively prime $r\in{\mathbb{N}}$ and $b\in{\mathbb{Z}}$ such that
$r\leqslant 2Q$ and $|rc_{s}{\alpha}-b|\leqslant(2Q)^{-1}$. The triangle
inequality gives

$\Bigl{|}\frac{a}{q}-\frac{b}{rc_{s}}\Bigr{|}\leqslant\frac{Q}{qN^{k}}+\frac{1}{2rc_{s}Q}<\frac{1}{qrc_{s}},$

so $\frac{a}{q}=\frac{b}{rc_{s}}$. As $(a,q)=1$ and $(rc_{s},b)\ll 1$, we have
$q\asymp r$, $|rc_{s}{\alpha}-b|\asymp|q{\alpha}-a|$, and it now follows from
[VW91, Lemma 8.5] that

$g_{s}({\alpha})\ll_{\varepsilon}q^{\varepsilon}N(q+N^{k}|q{\alpha}-a|)^{-1/k}+N\exp(-c\sqrt{\log
N})(1+N^{k}|{\alpha}-a/q|),$

where $c=c(A,\eta)$ is a small positive constant. In particular, if
${\alpha}\in{\mathfrak{M}}\setminus{\mathfrak{N}}$ then

$g_{s}({\alpha})\ll NQ_{1}^{\varepsilon-1/k}.$

Furthermore, the sharp mean value estimate [DS16, Theorem 2.3] implies

$\int_{0}^{1}|g_{i}({\alpha})|^{s-0.1}{\mathrm{d}}{\alpha}\ll
N^{s-0.1-k}\qquad(1\leqslant i\leqslant s).$ (B.1)

Using Hölder’s inequality, we now obtain

$\int_{{\mathfrak{M}}\setminus{\mathfrak{N}}}|g_{1}({\alpha})\cdots
g_{s}({\alpha})|{\mathrm{d}}{\alpha}=o(N^{s-k}),$

and so

$\int_{0}^{1}g_{1}({\alpha})\cdots
g_{s}({\alpha}){\mathrm{d}}{\alpha}=\int_{\mathfrak{N}}g_{1}({\alpha})\cdots
g_{s}({\alpha}){\mathrm{d}}{\alpha}+o(N^{s-k}).$ (B.2)

For $q\in{\mathbb{N}}$, $a\in{\mathbb{Z}}$ and ${\beta}\in{\mathbb{R}}$,
define

$S(q,a)=\sum_{x\leqslant q}e_{q}(ax^{k}),\qquad w({\beta})=\sum_{N^{\eta
k}<m\leqslant N^{k}}\frac{1}{k}m^{\frac{1}{k}-1}\rho\Bigl{(}\frac{\log m}{\eta
k\log N}\Bigr{)}e({\beta}m)$

and

$W({\alpha},q,a)=q^{-1}S(q,a)w({\alpha}-a/q),$

where as before $\rho$ denotes the Dickman–de Bruijn $\rho$-function. Next, we
apply [Vau89, Lemma 5.4] to $c_{i}{\alpha}$, for $1\leqslant i\leqslant s$ and
${\alpha}\in{\mathfrak{N}}(q,a)\subset{\mathfrak{N}}$, where $0\leqslant
a<q\leqslant Q_{1}$ and $|q{\alpha}-a|\leqslant Q_{1}N^{-k}$. With
$c^{\prime}_{i}=c_{i}/(c_{i},q)$ and $q_{i}=q/(c_{i},q)$, this gives

$g_{i}({\alpha})=W(c_{i}{\alpha},q_{i},c^{\prime}_{i}a)+O((\log N)^{-1/2}),$

and furthermore

$W(c_{i}{\alpha},q,c_{i}a)=W(c_{i}{\alpha},q_{i},c_{i}^{\prime}a)\ll
q^{-1/k}\min(N,|{\alpha}-a/q|^{-1/k}).$ (B.3)

By (B.1) and (B.2), together with Hölder, we now have

$\displaystyle\int_{0}^{1}g_{1}({\alpha})\cdots
g_{s}({\alpha}){\mathrm{d}}{\alpha}$
$\displaystyle\quad=\sum_{q\leqslant\sqrt{\log
N}}q^{-s}\sum_{\begin{subarray}{c}a\leqslant q\\\
(a,q)=1\end{subarray}}\int_{|{\beta}|\leqslant\frac{\sqrt{\log
N}}{qN^{k}}}\Bigl{(}\prod_{i\leqslant
s}S(q,c_{i}a)w(c_{i}{\beta})\Bigr{)}{\mathrm{d}}{\beta}+o(N^{s-k}).$

The bound (B.3) enables us to extend the integral to $[-1/2,1/2]^{s}$ and then
the outer sum to infinity with $o(N^{s-k})$ error, as is usual for a major arc
analysis [Dav2005, Vau97]. We thus obtain

$\int_{0}^{1}g_{1}({\alpha})\cdots
g_{s}({\alpha}){\mathrm{d}}{\alpha}={\mathfrak{S}}J+o(N^{s-k}),$

where

${\mathfrak{S}}=\sum_{q=1}^{\infty}\sum_{\begin{subarray}{c}a\leqslant q\\\
(a,q)=1\end{subarray}}q^{-s}S(q,c_{1}a)\cdots S(q,c_{s}a)$

and

$J=\int_{[-1/2,1/2]^{s}}w(c_{1}{\beta})\cdots
w(c_{s}{\beta}){\mathrm{d}}{\beta}.$

As discussed in [Dav2005, Ch. 8], the singular series is a product of $p$-adic
densities,

${\mathfrak{S}}=\prod_{p}\chi_{p},$

and is strictly positive if and only if $\chi_{p}>0$ for all $p$. The
positivity of the $p$-adic densities $\chi_{p}$ follows from the assumption
that $\sum_{i\in I}c_{i}=0$ for some non-empty $I\subseteq[s]$: one takes a
non-trivial solution in $\\{0,1\\}^{s}$, and this is a non-singular $p$-adic
zero.

Our final task is to show that $J\asymp N^{s-k}$. By orthogonality

$J=k^{-s}\sum_{\begin{subarray}{c}{\mathbf{m}}\in(N^{\eta k},N^{k}]^{s}\\\
{\mathbf{c}}\cdot{\mathbf{m}}=0\end{subarray}}\prod_{i\leqslant
s}m_{i}^{\frac{1}{k}-1}\rho\Bigl{(}\frac{\log m_{i}}{\eta k\log N}\Bigr{)}.$

With $c>0$ small, we have the crude lower bound

$J\gg N^{s(1-k)}\sum_{\begin{subarray}{c}{\mathbf{m}}\in(cN^{k},N^{k}]^{s}\\\
{\mathbf{c}}\cdot{\mathbf{m}}=0\end{subarray}}1\gg
N^{s(1-k)}(N^{k})^{s-1}=N^{s-k},$

since the $c_{i}$ are not all of the same sign. We also have the complementary
upper bound

$J\ll N^{s(1-k)}\sum_{\begin{subarray}{c}{\mathbf{m}}\in[1,N^{k}]^{s}\\\
{\mathbf{c}}\cdot{\mathbf{m}}=0\end{subarray}}1\ll N^{s-k}.$

∎

######  Remark B.2.

By working harder, we could have obtained a main term ${\lambda}N^{s-k}$, for
some positive constant ${\lambda}={\lambda}({\mathbf{c}})$, similarly to
Drappeau—Shao [DS16].

We also need the following bounded restriction inequalities.

######  Lemma B.3.

Let

$f:[N]\to\\{z\in{\mathbb{C}}:|z|\leqslant 1\\}.$

If $p>4$ then

$\int_{\mathbb{T}}\Bigl{|}\sum_{x\in
S(N;N^{\eta})}f(x)e({\alpha}x^{2})\Bigr{|}^{p}{\mathrm{d}}{\alpha}\ll_{p}N^{p-2}.$

For $k\geqslant 3$, there exists $s_{0}(k)$ such that if $s\geqslant s_{0}(k)$
then

$\int_{\mathbb{T}}\Bigl{|}\sum_{x\in
S(N;N^{\eta})}f(x)e({\alpha}x^{k})\Bigr{|}^{s-10^{-8}}{\mathrm{d}}{\alpha}\ll
N^{s-10^{-8}-k}.$

Moreover, one may take $s_{0}(3)=8$, and $s_{0}(k)$ satisfying (1.3).

###### Proof.

The quadratic statement is a direct consequence of [Bou89, Eq. (4.1)].
Assuming for the time being that $k\geqslant 4$, write $2t$ for the smallest
even integer greater than or equal to the integer $s_{0}(k)$ appearing in
Theorem B.1. Note that modifying $s_{0}(k)$ by adding a constant does not
affect the veracity of (1.3), and so we will prove the statement for
$s\geqslant s_{0}(k)+2$ in this case.

By orthogonality, the triangle inequality and Theorem B.1, we have

$\displaystyle\int_{\mathbb{T}}\Bigl{|}\sum_{x\in
S(N;N^{\eta})}f(x)e({\alpha}x^{k})\Bigr{|}^{2t}{\mathrm{d}}{\alpha}$
$\displaystyle\qquad\leqslant\\#\Bigl{\\{}({\mathbf{x}},{\mathbf{y}})\in
S(N;N^{\eta})^{t}\times S(N;N^{\eta})^{t}:\sum_{i\leqslant
t}x_{i}^{k}=\sum_{i\leqslant t}y_{i}^{k}\Bigr{\\}}\ll_{t,\eta}N^{2t-k}.$

The trivial estimate $\Bigl{|}\sum_{x\in
S(N;N^{\eta})}f(x)e({\alpha}x^{k})\Bigr{|}\leqslant N$ completes the proof
when $k\geqslant 4$.

For $k=3$ we require a more elaborate argument to prove that the precise value
of $s_{0}(3)=8$ is admissible. In particular, our approach relies on a
‘subconvex’ mean value estimate of Wooley [Woo95]. Define
$\phi:{\mathbb{Z}}\to{\mathbb{C}}$ by $\phi(n)=f(x)$ if $n=x^{3}$ for some
$x\in S(N;N^{\eta})$, and zero otherwise. Our objective is to show that

$\int_{\mathbb{T}}|\hat{\phi}({\alpha})|^{8-10^{-8}}{\mathrm{d}}{\alpha}\ll
N^{5-10^{-8}}.$

In the present appendix, we let ${\delta}$ denote a parameter in the range

$0<{\delta}<1,$

and consider the large spectra

$\mathcal{R}_{\delta}=\\{{\alpha}\in{\mathbb{T}}:|\hat{\phi}({\alpha})|>{\delta}N\\}.$

By the dyadic pigeonholing argument in [BP17, §6], it suffices to prove that

$\mathrm{meas}(\mathcal{R}_{\delta})\ll\frac{1}{{\delta}^{8-10^{-7}}N^{3}}.$

By orthogonality, Wooley’s estimate [Woo95, Theorem 1.2] implies that

$\int_{\mathbb{T}}|\hat{\phi}({\alpha})|^{6}{\mathrm{d}}{\alpha}\ll
N^{3.25-10^{-4}}.$

Thus, we may assume without loss of generality that

$N^{10^{-5}-\frac{1}{8}}<{\delta}<1.$ (B.4)

Indeed, if ${\delta}\leqslant N^{10^{-5}-\frac{1}{8}}$ then

$\mathrm{meas}(\mathcal{R}_{\delta})\leqslant({\delta}N)^{-6}\int_{\mathcal{R}_{\delta}}|\hat{\phi}({\alpha})|^{6}{\mathrm{d}}{\alpha}\ll({\delta}N)^{-6}N^{3.25-10^{-4}}\leqslant\frac{1}{{\delta}^{8-10^{-7}}N^{3}}.$

Let ${\theta}_{1},{\theta}_{2},\ldots,{\theta}_{R}$ be $N^{-3}$-separated
points in $\mathcal{R}_{\delta}$. As $8-10^{-7}\geqslant 6.3$ it suffices to
show that

$R\ll{\delta}^{-6.3}.$ (B.5)

Let $\mu(n)=1$ if $n=x^{3}$ for some $x\in[N]$, and zero otherwise. For some
$a_{n}\in{\mathbb{C}}$ with $|a_{n}|\leqslant 1$, we then have
$\phi(n)=a_{n}\mu(n)$; this ‘throws away’ smoothness. With ${\gamma}=3.1$, the
calculation in [BP17, §6] yields