# Energy bounds for modular roots and their applications

Bryce Kerr  Max Planck Institute for Mathematics, Bonn, Germany
<EMAIL_ADDRESS>,  Ilya D. Shkredov  I.D.S.: Steklov Mathematical
Institute of Russian Academy of Sciences, ul. Gubkina 8, Moscow, Russia,
119991; Institute for Information Transmission Problems of Russian Academy of
Sciences, Bolshoy Karetny Per. 19, Moscow, Russia, 127994; Moscow Institute of
Physics and Technology, Institutskii per. 9, Dolgoprudnii, Russia, 141701
<EMAIL_ADDRESS>,  Igor E. Shparlinski  I.E.S.: School of Mathematics
and Statistics, University of New South Wales. Sydney, NSW 2052, Australia
<EMAIL_ADDRESS>and  Alexandru Zaharescu  A.Z.: Department of
Mathematics, University of Illinois at Urbana-Champaign 1409 West Green
Street, Urbana, IL 61801, USA and Simon Stoilow Institute of Mathematics of
the Romanian Academy, P.O. Box 1-764, RO-014700 Bucharest, Romania
<EMAIL_ADDRESS>
###### Abstract.

We generalise and improve some recent bounds for additive energies of modular
roots. Our arguments use a variety of techniques, including those from
additive combinatorics, algebraic number theory and the geometry of numbers.
We give applications of these results to new bounds on correlations between
Salié sums and to a new equidistribution estimate for the set of modular roots
of primes.

###### Key words and phrases:

modular roots, additive energy

###### 2010 Mathematics Subject Classification:

Primary 11L07; Secondary 1B30, 11F37, 11N69

###### Contents

  1. 1 Introduction
    1. 1.1 Background
    2. 1.2 Notation
    3. 1.3 New results
  2. 2 Applications
  3. 3 Proof of Theorem 1.1
    1. 3.1 Lattices
    2. 3.2 Reduction to counting points in lattices
    3. 3.3 Concluding the proof
  4. 4 Proof of Theorem 1.2
    1. 4.1 Lattices
    2. 4.2 Concluding the proof
  5. 5 Proof of Theorem 1.3
    1. 5.1 Product polynomials
    2. 5.2 The zero set of $F_{k}(X_{1},X_{2},X_{3},X_{4})$
    3. 5.3 Concluding the proof
  6. 6 Proof of Theorem 1.4
    1. 6.1 Preliminary discussion
    2. 6.2 Gowers norms
    3. 6.3 Concluding the proof
      1. 6.3.1 Case $k=3$
      2. 6.3.2 Case $k=4$
      3. 6.3.3 Case $k\geqslant 5$
  7. 7 Proof of Theorem 2.2
  8. 8 Proof of Theorem 2.3
    1. 8.1 Preliminaries
    2. 8.2 Small $N_{1}$
    3. 8.3 Medium $N_{1}$
    4. 8.4 Large $N_{1}$
    5. 8.5 Very large $N_{1}$
    6. 8.6 Optimiziation

##  1\. Introduction

###  1.1. Background

For a prime $q$ we use $\mathbb{F}_{q}$ to denote the finite field of $q$
elements. Given a set ${\mathcal{N}}\subseteq\mathbb{F}_{q}$ and an integer
$k\geqslant 1$, let $T_{\nu,k}({\mathcal{N}};q)$ be the number of solutions to
the equation (in $\mathbb{F}_{q})$,

$b_{1}+\ldots+b_{\nu}=b_{\nu+1}+\ldots+b_{2\nu},\qquad
b_{i}^{k}\in{\mathcal{N}},\ i=1,\ldots,2\nu.$

For $\nu=2$ we also denote

$T_{\nu,k}({\mathcal{N}};q)=E_{k}({\mathcal{N}};q).$

When $k=1$, this is the well-known in additive combinatorics quantity called
the additive energy of ${\mathcal{N}}$. More generally,
$E_{k}({\mathcal{N}};q)$ is the additive energy of the set of $k$-th roots of
elements of ${\mathcal{N}}$ (of those which are $k$-th power residues).

In the special case ${\mathcal{N}}=\\{1,\ldots,N\\}$ for an integer
$1\leqslant N<q$, we also write

$T_{\nu,k}\left(j{\mathcal{N}};q\right)=\mathsf{T}_{\nu,k}(N;j,q),\qquad
E_{k}\left(j{\mathcal{N}};q\right)=\mathsf{E}_{k}(N;j,q),$

where the set $j{\mathcal{N}}=\\{j,\ldots,jN\\}$ is embedded in
$\mathbb{F}_{q}$ in a natural way.

The quantity $\mathsf{E}_{2}(N;j,q).$ has been introduced and estimated in
[10]. In particular, for any $j\in\mathbb{F}_{q}^{*}$, by [10, Lemmas 6.4 and
6.6] we have

(1.1)
$\mathsf{E}_{2}(N;j,q)\leqslant\min\left\\{N^{4}/q+N^{5/2},\,N^{7/2}/q^{1/2}+N^{7/3}\right\\}q^{o(1)},$

which has been used in [10, Theorem 1.7] to estimate certain bilinear sums and
thus improve some results of [11] on correlations between Salié sums, which is
important for applications to moments of $L$-functions attached to some
modular forms. Furthermore, bounds of such bilinear sums have applications to
the distribution of modular square roots of primes, see [10, 21] for details.

This line of research has been continued in [20] where it is shown that for
almost all primes $q$, for all $N<q$ and $j\in\mathbb{F}_{q}^{*}$ one has an
essentially optimal bound

(1.2) $\mathsf{E}_{2}(N;j,q)\leqslant\left(N^{4}/q+N^{2}\right)q^{o(1)}.$

As an application of the bound (1.2), it has been show in [20] that on average
over $q$ one can significantly improve the error term in the asymptotic
formula for twisted second moments of $L$-functions of half integral weight
modular forms.

Furthermore, it is shown in [20] that methods of additive combinatorics can be
used to estimate $E_{2}({\mathcal{N}};q)$ for sets ${\mathcal{N}}$ with small
doubling. Namely, for an arbitrary set ${\mathcal{N}}$ (of any algebraic
domain equipped with addition), as usual, we denote

${\mathcal{N}}+{\mathcal{N}}=\\{n_{1}+n_{2}:\leavevmode\nobreak\
n_{1},n_{2}\in{\mathcal{N}}\\}.$

Then it is shown in [20], in particular, that if
${\mathcal{N}}\subseteq\mathbb{Z}_{q}$ is a set of cardinality $N$ such that
$\\#\left({\mathcal{N}}+{\mathcal{N}}\right)\leqslant LN$ for some real $L$,
then

(1.3) $E_{2}({\mathcal{N}};q)\leqslant
q^{o(1)}\left(\frac{L^{4}N^{4}}{q}+L^{2}N^{11/4}\right)\,.$

Here we extend and improve these results in several directions and obtain
upper bounds on $T_{\nu,k}({\mathcal{N}};q)$ and $\mathsf{T}_{\nu,k}(N;j,q)$
for other choices of $(\nu,k)$ besides $(\nu,k)=(2,2)$ along with improving
the bound of [10, Lemma 6.6] for $T_{2,2}(N;j,q)$.

Our estimate for $T_{2,2}(N;j,q)$ gives some improvement on exponential sums
bounds from [10]. Obtaining nontrivial bounds on $\mathsf{T}_{\nu,k}(N;j,q)$
with $\nu>2$ have a potential to to obtain further improvements and extend the
region in which there are non-trivial bounds of bilinear sums from [10, 20].
In turn this can lead to further advances in their applications.

One such application is to bilinear sums with some multidimensional Salié sum
which by a result of Duke [9] can be reduced to one dimensional sums over
$k$-th roots (generalising the case of $k=2$, see [15][Lemma 12.4] or
[18][Lemma 4.4]). This result of Duke [9] combined with our present results
and also the approach of [11, 10, 20], may have a potential to lead to new
asymptotic formulas for moments of $L$-functions with Fourier coefficients of
automorphic forms over ${\mathrm{GL}}(k)$ with $k\geqslant 3$.

###  1.2. Notation

Throughout the paper, the notation $U=O(V)$, $U\ll V$ and $V\gg U$ are
equivalent to $|U|\leqslant cV$ for some positive constant $c$, which
throughout the paper may depend on the integer $k$.

For any quantity $V>1$ we write $U=V^{o(1)}$ (as $V\to\infty$) to indicate a
function of $V$ which satisfies $|U|\leqslant V^{\varepsilon}$ for any
$\varepsilon>0$, provided $V$ is large enough.

For complex weights $\bm{\beta}=\\{\beta_{n}\\}_{n\in{\mathcal{N}}}$,
supported on a finite set ${\mathcal{N}}$, we define the norms

$\|\bm{\beta}\|_{\infty}=\max_{n\in{\mathcal{N}}}|\beta_{n}|\qquad\mbox{and}\qquad\|\bm{\beta}\|_{\sigma}=\left(\sum_{n\in{\mathcal{N}}}|\alpha_{n}|^{\sigma}\right)^{1/\sigma},$

where $\sigma>1$, and similarly for other weights.

For a real $A>0$, we write $a\sim A$ to indicate that $a$ is in the dyadic
interval $A/2\leqslant a<A$.

We use $\\#{\mathcal{A}}$ for the cardinality of a finite set ${\mathcal{A}}$.

Given two functions $f,g$ on some algebraic domain ${\mathcal{D}}$ equipped
with addition, we define the convolution

$(f\circ g)(d)=\sum_{x\in{\mathcal{D}}}f(x)g(d-x).$

We can then recursively define longer convolutions $(f_{1}\circ\ldots\circ
f_{s})(d)$.

If $f$ is the indicator function of a set ${\mathcal{A}}$ then we write

$(f\circ f)(d)=\left({\mathcal{A}}\circ{\mathcal{A}}\right)(d).$

In fact, we often use ${\mathcal{A}}(a)$ for the indicator function of a set
${\mathcal{A}}$, that is, ${\mathcal{A}}(a)=1$ if $a\in{\mathcal{A}}$ and
${\mathcal{A}}(a)=0$ otherwise.

Note that $\left({\mathcal{A}}\circ{\mathcal{A}}\right)(d)$ counts the number
of the solutions to the equation $d=a_{1}-a_{2}$, where $a_{1}$, $a_{2}$ run
over ${\mathcal{A}}$, that is

(1.4)
$\left({\mathcal{A}}\circ{\mathcal{A}}\right)(d)=\\#\\{(a_{1},a_{2})\in{\mathcal{A}}^{2}:\leavevmode\nobreak\
d=a_{1}-a_{2}\\}.$

As usual, we also write

${\mathcal{A}}+{\mathcal{A}}=\\{a_{1}+a_{2}:\leavevmode\nobreak\
a_{1},a_{2}\in{\mathcal{A}}\\}.$

Finally, we follow the convention that in summation symbols $\sum_{a\leqslant
A}$ the sum is over positive integers $a\leqslant A$.

###  1.3. New results

We start with a new bound on $\mathsf{T}_{2,2}(N;j,q)=\mathsf{E}_{2}(N;j,q)$
which improves (1.1).

######  Theorem 1.1.

Let $q$ be prime. For any $j\in\mathbb{F}_{q}^{*}$ and integer $N\leqslant q$
we have

$\mathsf{T}_{2,2}(N;j,q)\ll\left(\frac{N^{3/2}}{q^{1/2}}+1\right)N^{2+o(1)}.$

Note it is easy to show the following trivial inequality

$\mathsf{T}_{4,2}(N;j,q)\leqslant N^{4}\mathsf{T}_{2,2}(N;j,q),$

which combined with Theorem 1.1 implies that

(1.5)
$\mathsf{T}_{4,2}(N;j,q)\leqslant\left(\frac{N^{3/2}}{q^{1/2}}+1\right)N^{6+o(1)}.$

We now obtain a stronger bound for short intervals.

######  Theorem 1.2.

Let $q$ be prime. For any $j\in\mathbb{F}_{q}^{*}$ and integer $N\leqslant q$
we have

$\mathsf{T}_{4,2}(N;j,q)\leqslant\left(\frac{N^{5/8}}{q^{1/8}}+\frac{N^{8}}{q^{1/2}}\right)N^{6+o(1)}+N^{5+o(1)}.$

We see that Theorem 1.2 is sharper than (1.5) provided $N\leqslant q^{1/16}$.
The proofs of Theorem 1.1 and Theorem 1.2 are based on the geometry of numbers
and in particular on some properties of lattices.

Next we generalise (1.2) to higher order roots. In fact, as in [20] the
methods allow us to also treat the natural extension of
$\mathsf{E}_{k}(N;j,q)$ to composite moduli $q$, for which we consider
equations in the residue ring $\mathbb{Z}_{q}$ modulo $q$, and estimate
$\mathsf{E}_{k}(N;j,q)$ for almost all positive integers $q$. We however
restrict ourselves to the case of prime moduli $q$.

######  Theorem 1.3.

For a fixed $k\geqslant 3$ and any positive integers $Q\geqslant N\geqslant
1$, we have

$\frac{\log Q}{Q}\sum_{\begin{subarray}{c}q\sim Q\\\ q\leavevmode\nobreak\
\text{prime}\end{subarray}}\max_{j\in\mathbb{F}_{q}^{*}}\mathsf{E}_{k}(N;j,q)\ll
N^{2}+N^{4}Q^{-1+o(1)}.$

To establish Theorem 1.3 we use some arguments related to norms of algebraic
integers.

We now extend the bound (1.3) to other values of $k$ as follows.

######  Theorem 1.4.

Let ${\mathcal{N}}\subseteq\mathbb{F}_{q}$ be a set of cardinality
$\\#{\mathcal{N}}=N\leqslant q^{2/3}$ such that
$\\#\left({\mathcal{N}}+{\mathcal{N}}\right)\leqslant LN$ for some real $L$.
Then for $k\geqslant 3$ we have

$E_{k}({\mathcal{N}};q)\leqslant L^{\vartheta_{k}}N^{3-\rho_{k}}q^{o(1)}\,,$

where

$\rho_{k}=1/(7\cdot
2^{k-1}-9)\quad\text{and}\quad\vartheta_{k}=\begin{cases}2^{k+2}\rho_{k},&\text{
for $k=3$ and $k\geqslant 5$};\\\ 48/47,&\text{ for $k=4$}.\end{cases}$

We remark that the exponent of $L$ in Theorem 1.4 is $\vartheta_{3}=32/19$ and

$\vartheta_{k}=\frac{2^{k+2}}{7\cdot 2^{k-1}-9}\leqslant\frac{128}{103}$

for $k\geqslant 5$. For $k=4$ the exponent of $L$ is better than generic
because of some additional saving in our application of the Plünnecke
inequality, see [24, Corollary 6.29].

The proof is based on some ideas of Gowers [12, 13], in particular on the
notion of the Gowers norm. Finally, we remark that it is easy to see that,
actually, our method works for any polynomial not only for monomials. Also, it
is possible, in principle, to insert the general weight $\bm{\beta}$ but the
induction procedure requires complex calculations to estimate this more
general quantity

$E_{k}({\mathcal{N}};\bm{\beta},q)=\sum_{\begin{subarray}{c}u,v,x,y\in\mathbb{F}_{q}\\\
u^{k},v^{k},x^{k},y^{k}\in{\mathcal{N}}\\\
u+v=x+y\end{subarray}}\beta_{u}\beta_{v}\beta_{x}\beta_{y}.$

Nevertheless, we record a simple consequence of Theorem 1.4 with weights
$\bm{\beta}$, which follows from the pigeonhole principle.

######  Corollary 1.5.

Let ${\mathcal{N}}\subseteq\mathbb{F}_{q}$ be a set of cardinality
$\\#{\mathcal{N}}=N$ such that
$\\#\left({\mathcal{N}}+{\mathcal{N}}\right)\leqslant LN$ for some real $L$.
Then for any weights $\bm{\beta}$ supported on ${\mathcal{N}}$, and with
$\|\bm{\beta}\|_{\infty}\leqslant 1$ Then

$E_{k}({\mathcal{N}};\bm{\beta},q)\leqslant
L^{\vartheta_{k}}\|\bm{\beta}\|^{2-2\rho_{k}}_{1}\|\bm{\beta}\|^{2+2\rho_{k}}_{2}q^{o(1)}\,,$

where $\vartheta_{k}$ and $\rho_{k}$ are as in Theorem 1.4.

We also remark that Theorem 1.4 can be reformulated as a statement that for
any set ${\mathcal{A}}\subseteq\mathbb{F}_{q}$ either the additive energy
$\\#\\{a_{1}+a_{2}=a_{3}+a_{4}:\leavevmode\nobreak\
a_{1},a_{2},a_{3},a_{4}\in{\mathcal{A}}\\}$ of ${\mathcal{A}}$ is small or
${\mathcal{A}}^{k}$ has large doubling set
${\mathcal{A}}^{k}+{\mathcal{A}}^{k}=\\{a_{1}^{k}+a_{2}^{k}:\leavevmode\nobreak\
a_{1},a_{2}\in{\mathcal{A}}\\}$.

##  2\. Applications

Given weights $\bm{\alpha},\bm{\beta}$ we define bilinear forms over modular
square roots as in [10, Equation (1.6)]

(2.1) $W_{a,q}(\bm{\alpha},\bm{\beta};h,M,N)=\sum_{m\sim M}\sum_{n\sim
N}\alpha_{m}\beta_{n}\sum_{\begin{subarray}{c}x\in\mathbb{F}_{q}\\\
x^{2}=amn\end{subarray}}{\mathbf{\,e}}_{q}(hx).$

Using Theorem 1.1 we obtain a new estimate for
$W_{a,q}(\bm{\alpha},\bm{\beta};h,M,N)$ which improves on [10, Theorem 1.7].
Assuming

$\|\bm{\alpha}\|_{\infty},\|\bm{\beta}\|_{\infty}\leqslant 1,$

it follows from the proof of [10, Theorem 1.7] that

$|W_{a,q}(\bm{\alpha},\bm{\beta};h,M,N)|^{8}\leqslant
q^{1+o(1)}(NM)^{4}\mathsf{T}_{2,2}(N;b,q)\mathsf{T}_{2,2}(M;1,q),$

for some $b$ with $\gcd(b,q)=1$.

Applying Theorem 1.1, we obtain the following bound.

######  Corollary 2.1.

For any positive integers $M,N\leqslant q/2$ and any weights $\bm{\alpha}$ and
$\bm{\beta}$ satisfying

$\|\bm{\alpha}\|_{\infty},\|\bm{\beta}\|_{\infty}\leqslant 1,$

we have

$|W_{a,q}(\bm{\alpha},\bm{\beta};h,M,N)|\leqslant
q^{1/8+o(1)}(NM)^{3/4}\left(\frac{N^{3/16}}{q^{1/16}}+1\right)\left(\frac{M^{3/16}}{q^{1/16}}+1\right).$

If the sequence $\bm{\beta}$ corresponds to values of a smooth function
$\varphi$ whose derivatives and support $\operatorname{supp}\varphi$ satisfy

(2.2)
$\varphi^{(j)}(x)\ll\frac{1}{x^{j}}\qquad\mbox{and}\qquad\operatorname{supp}\varphi\subseteq[N,2N],$

then we write

(2.3) $V_{a,q}(\bm{\alpha},\varphi;h,M,N)=\sum_{m\sim
M}\sum_{n\in\mathbb{Z}}\alpha_{m}\varphi(n)\sum_{\begin{subarray}{c}x\in\mathbb{F}_{q}\\\
x^{2}=amn\end{subarray}}e_{q}(hx).$

We now give a new bound for $V_{a,q}(\bm{\alpha};h,M,N)$. This does not rely
on energy estimates although may be of independent interest. It is also used
in a combination with Corollary 2.1 to derive Theorem 2.3 below.

######  Theorem 2.2.

For any positive integers $M,N$ satisfying $MN\ll q$ and $M<N$, any weight
$\bm{\alpha}$ satisfying

$\|\bm{\alpha}\|_{\infty}\leqslant 1,$

and a function $\varphi$ satisfying (2.2), we have

$|V_{a,q}(\bm{\alpha},\varphi;h,M,N)|\leqslant
q^{1/2-1/4r+o(1)}N^{1/2r}M^{1-1/2r}\left(1+\frac{(MN)^{1/2}}{q^{1/2-1/4r}}\right).$

Corollary 2.1 may be used to improve various results from [10, Sections
1.3-1.4]. We present once such improvement to the distribution of modular
roots of primes. Recall that the discrepancy $D(N)$ of a sequence in
$\xi_{1},\ldots,\xi_{N}\in[0,1)$ is defined as

$D_{N}=\sup_{0\leqslant\alpha<\beta\leqslant 1}\left|\\#\\{1\leqslant
n\leqslant N:\leavevmode\nobreak\
\xi_{n}\in[\alpha,\beta)\\}-(\beta-\alpha)N\right|.$

For a positive integer $P$ we denote the discrepancy of the sequence
(multiset) of points

$\\{x/q:\leavevmode\nobreak\ x^{2}\equiv p\bmod q\ \text{for some prime}\
p\leqslant P\\}$

by $\Gamma_{q}(P)$. Combining the Erdös-Turán inequality with the Heath-Brown
identity reduces estimating $\Gamma_{q}(P)$ to sums of the form (2.1) and
(2.3). Combining, Corollary 2.1 with Theorem 2.2, we obtain an improvement on
[10, Theorem 1.10].

######  Theorem 2.3.

For any $P\leqslant q^{10/11}$ we have

$\Gamma_{q}(P)\leqslant\left(P^{15/16}+q^{1/8}P^{3/4}+q^{1/16}P^{69/80}+q^{13/88}P^{3/4}\right)q^{o(1)}.$

Note that Theorem 2.3 is nontrivial provided $P\geqslant q^{13/22}$ and
improves on the range $P\geqslant q^{13/20}$ from [10, Theorem 1.10].

##  3\. Proof of Theorem 1.1

###  3.1. Lattices

We use $\mathrm{Vol}(B)$ to denote the volume of a body
$B\subseteq\mathbb{R}^{d}$. For a lattice $\Gamma\subseteq\mathbb{R}^{d}$ we
recall that the quotient space $\mathbb{R}^{d}/\Gamma$ (called the fundamental
domain) is compact and so $\mathrm{Vol}(\mathbb{R}^{d}/\Gamma)$ is correctly
defined, see also [24, Sections 3.1 and 3.5] for basic definitions and
properties of lattices. In particular, we define the successive minima
$\lambda_{j}$, $j=1,\ldots,d$, of $B$ with respect to $\Gamma$ as

$\lambda_{j}=\inf\\{\lambda>0:\leavevmode\nobreak\ \lambda B\text{ contains
$j$ linearly independent elements of }\Gamma\\},$

where $\lambda B$ is the homothetic image of $B$ with the coefficient
$\lambda$.

The following is Minkowski’s second theorem, for a proof see [24, Theorem
3.30].

######  Lemma 3.1.

Suppose $\Gamma\subseteq\mathbb{R}^{d}$ is a lattice of rank $d$,
$B\subseteq\mathbb{R}^{d}$ a symmetric convex body and let
$\lambda_{1},\ldots,\lambda_{d}$ denote the successive minima of $\Gamma$ with
respect to $B$. Then we have

$\frac{1}{\lambda_{1}\ldots\lambda_{d}}\leqslant\frac{d!}{2^{d}}\frac{\mathrm{Vol}(B)}{\mathrm{Vol}(\mathbb{R}^{d}/\Gamma)}.$

For a proof of the following, see [3, Proposition 2.1].

######  Lemma 3.2.

Suppose $\Gamma\subseteq\mathbb{R}^{d}$ is a lattice,
$B\subseteq\mathbb{R}^{d}$ a symmetric convex body and let
$\lambda_{1},\ldots,\lambda_{d}$ denote the successive minima of $\Gamma$ with
respect to $B$. Then we have

$\\#\left(\Gamma\cap
B\right)\leqslant\prod_{j=1}^{d}\left(\frac{2j}{\lambda_{j}}+1\right).$

###  3.2. Reduction to counting points in lattices

Let ${\mathcal{A}}$ denote the set

${\mathcal{A}}=\\{x\in\mathbb{F}_{q}^{*}:\leavevmode\nobreak\
jx^{2}\in\\{1,\ldots,N\\}\\},$

so that

(3.1)
$\mathsf{T}_{2,2}(N;j,q)=\sum_{d\in\mathbb{F}_{q}}({\mathcal{A}}\circ{\mathcal{A}})(d)^{2}.$

where $({\mathcal{A}}\circ{\mathcal{A}})(d)$ is defined by (1.4).

If $a_{1},a_{2}\in{\mathcal{A}}$ satisfy

$a_{1}-a_{2}=d,$

then elementary algebraic manipulations imply

$(a_{1}^{2}-a_{2}^{2}-d^{2})^{2}=4d^{2}a_{2}^{2}.$

We have

$ja_{1}^{2}-ja_{2}^{2},ja_{2}^{2}\in\\{-N,\ldots,N\\}.$

Since for any $\lambda,\mu\in\mathbb{F}_{q}$ the number of solutions to

$ja_{1}^{2}-ja_{2}^{2}=\lambda,\quad ja_{2}^{2}=\mu,\qquad
a_{1},a_{2}\in{\mathcal{A}},$

is $O(1),$ we derive from (3.1)

$\mathsf{T}_{2,2}(N;j,q)\ll\sum_{d\in\mathbb{F}_{q}}J_{0}(d)^{2},$

where

$J_{0}(d)=\\#\\{|m|,|n|\leqslant N:\leavevmode\nobreak\ (n-jd^{2})^{2}\equiv
4jd^{2}m\bmod{q}\\}.$

If $n,m$ satisfy

$(n-jd^{2})^{2}\equiv 4jd^{2}m\bmod{q},$

then

$n^{2}+j^{2}d^{4}\equiv 2jd^{2}(2m+n)\bmod{q}.$

This implies

(3.2) $\mathsf{T}_{2,2}(N;j,q)\ll\sum_{d\in\mathbb{F}_{q}}J(d)^{2},$

where

(3.3) $J(d)=\\#\\{|m|,|n|\leqslant 6N:\leavevmode\nobreak\
n^{2}+j^{2}d^{4}\equiv jd^{2}m\bmod{q}\\}.$

Let ${\mathcal{L}}(d)$ denote the lattice

${\mathcal{L}}(d)=\\{(x,y)\in\mathbb{Z}^{2}:\leavevmode\nobreak\ x\equiv
jd^{2}y\bmod{q}\\},$

$B$ the convex body

$B=\\{(x,y)\in\mathbb{R}^{2}:\leavevmode\nobreak\ |x|\leqslant 72N^{2},\
|y|\leqslant 12N\\},$

and let $\lambda_{1}(d),\lambda_{2}(d)$ denote the first and second successive
minima of ${\mathcal{L}}(d)$ with respect to $B$.

We now partition summation in (3.2) according to the size of $\lambda_{1}(d)$
and $\lambda_{2}(d)$ to get

(3.4) $\mathsf{T}_{2,2}(N;j,q)\ll S_{0}+S_{1}+S_{2},$

where

$S_{0}=\sum_{\begin{subarray}{c}d\in\mathbb{F}_{q}\\\
\lambda_{1}(d)>1\end{subarray}}J(d)^{2},\qquad
S_{1}=\sum_{\begin{subarray}{c}d\in\mathbb{F}_{q}\\\ \lambda_{1}(d)\leqslant
1\\\ \lambda_{2}(d)>1\end{subarray}}J(d)^{2},\qquad
S_{2}=\sum_{\begin{subarray}{c}d\in\mathbb{F}_{q}\\\
\lambda_{1}(d),\lambda_{2}(d)\leqslant 1\end{subarray}}J(d)^{2}.$

###  3.3. Concluding the proof

Consider first $S_{0}$. If $\lambda_{1}(d)>1$ then

$J(d)\leqslant 1,$

which follows from the fact that for any distinct points $(n_{0},m_{0})$,
$(n_{1}.m_{1})$ satisfying the conditions in (3.3) we have

$(n_{0}^{2}-n_{1}^{2},m_{0}-m_{1})\in{\mathcal{L}}(d)\cap B.$

This implies that $J(d)^{2}=J(d)$ and we derive

(3.5) $S_{0}=\sum_{\begin{subarray}{c}d\in\mathbb{F}_{q}\\\
\lambda_{1}(d)>1\end{subarray}}J(d)\ll N^{2}.$

Consider next $S_{1}$. Suppose $d$ satisfies $\lambda_{1}(d)\leqslant 1$ and
$\lambda_{2}(d)>1$. There exists $n_{d},m_{d}$ satisfying the conditions given
in (3.3) such that

$J(d)\leqslant\\#\left\\{|m|,|n|\leqslant 6N:\leavevmode\nobreak\
(n^{2}-n_{d}^{2},m-m_{d})\in{\mathcal{L}}(d)\cap B\right\\}.$

Since $\lambda_{2}(d)>1$, there exists a unique point
$(a_{d},b_{d})\in{\mathcal{L}}(d)\cap B$ satisfying

$\gcd(a_{d},b_{d})=1,\quad|a_{d}|\leqslant 72N^{2},\quad|b_{d}|\leqslant 12N,$

such that

$J(d)\leqslant\\#\left\\{|m|,|n|\leqslant 6N:\leavevmode\nobreak\
\frac{n^{2}-n_{d}^{2}}{m-m_{d}}=\frac{a_{d}}{b_{d}}\right\\}.$

This implies

(3.6)
$\begin{split}S_{1}&\leqslant\sum_{d\in\mathbb{F}_{q}}\left(\\#\left\\{|m|,|n|\leqslant
6N:\leavevmode\nobreak\
\frac{n^{2}-n^{2}_{d}}{m-m_{d}}=\frac{a_{d}}{b_{d}}\right\\}\right)^{2}\\\
&\leqslant\sum_{\begin{subarray}{c}|a|\leqslant 72N^{2},\,|b|\leqslant 12N\\\
\gcd(a,b)=1\end{subarray}}K(a,b)^{2},\end{split}$

where

$K(a,b)=\\#\left\\{|m|,|n|\leqslant 6N:\leavevmode\nobreak\
\frac{n^{2}-n_{a,b}^{2}}{m-m_{a,b}}=\frac{a}{b}\right\\},$

for some choice of integers $m_{a,b},n_{a,b}$ satisfying
$|m_{a,b}|,|n_{a,b}|\leqslant 6N$. Fix some $a,b$ as in the sum in (3.6) and
consider $K(a,b)$. If $n,m$ satisfy

$\frac{n^{2}-n_{a,b}^{2}}{m-m_{a,b}}=\frac{a}{b},\qquad|m|,|n|\leqslant 6N,$

then, since $\gcd(a,b)=1$, we have

(3.7) $n^{2}-n_{a,b}^{2}\equiv 0\bmod{|a|},$

and

(3.8) $m-m_{a,b}\equiv 0\bmod{|b|}.$

Furthermore, if one out of $m$ or $n$ is fixed then the the other number is
defined in no more than two ways.

Write (3.7) as

$(n-n_{a,b})(n+n_{a,b})\equiv 0\bmod{|a|}.$

Then we see that there are two integers $a_{1},a_{2}$ satisfying

$a_{1}a_{2}=a,\qquad|a_{1}|,|a_{2}|\leqslant 12N,$

such that

$n\equiv n_{a,b}\bmod{|a_{1}|},\quad n\equiv-n_{a,b}\bmod{|a_{2}|}.$

Hence for each fixed pair $(a_{1},a_{2})$ there are at most

$\frac{N}{\mathrm{lcm}[a_{1},a_{2}]}+1\ll\frac{N}{|a|}\gcd(a_{1},a_{2}).$

possibilities for $n$. Hence

$K(a,b)\ll\sum_{a_{1}a_{2}=a}\frac{N}{\text{lcm}(a_{1},a_{2})}\ll\frac{N}{|a|}\sum_{a_{1}a_{2}=a}\gcd(a_{1},a_{2}).$

By the Cauchy-Schwarz inequality and a well-known bound on the divisor
function, see [15, Equation (1.81)], we now derive

(3.9) $K(a,b)^{2}\ll
N^{2+o(1)}\sum_{a_{1}a_{2}=a}\frac{\gcd(a_{1},a_{2})^{2}}{|a|^{2}}.$

Similarly, using (3.8) we obtain

(3.10) $K(a,b)\ll\frac{N}{|b|}.$

Combining (3.9) and (3.10) and substituting into (3.6), we see that

$\displaystyle S_{1}$ $\displaystyle\leqslant N^{2+o(1)}\sum_{|a|\leqslant
72N^{2},\,|b|\leqslant 12N}\sum_{\begin{subarray}{c}a_{1}a_{2}=a\\\
|a_{1}|,|a_{2}|\leqslant
12N\end{subarray}}\min\left\\{\frac{1}{b^{2}},\frac{\gcd(a_{1},a_{2})^{2}}{a^{2}}\right\\}$
$\displaystyle\leqslant N^{2+o(1)}\sum_{a_{1},a_{2},b\leqslant
12N}\min\left\\{\frac{1}{b^{2}},\frac{\gcd(a_{1},a_{2})^{2}}{a^{2}_{1}a^{2}_{2}}\right\\}$
$\displaystyle\leqslant N^{2+o(1)}\sum_{e\leqslant 12N}\sum_{b\leqslant
12N}\sum_{\begin{subarray}{c}a_{1},a_{2}\leqslant 12N\\\
\gcd(a_{1},a_{2})=e\end{subarray}}\min\left\\{\frac{1}{b^{2}},\frac{e^{2}}{a^{2}_{1}a^{2}_{2}}\right\\}$
$\displaystyle\leqslant N^{2+o(1)}\sum_{e\leqslant 12N}\sum_{b\leqslant
12N}\sum_{a_{1},a_{2}\leqslant
12N/e}\min\left\\{\frac{1}{b^{2}},\frac{1}{a^{2}_{1}a^{2}_{2}e^{2}}\right\\}$

Using the bound on the divisor function again we obtain

(3.11) $\begin{split}S_{1}&\leqslant N^{2+o(1)}\sum_{b\leqslant
12N}\sum_{a\leqslant
12^{4}N^{2}}\min\left\\{\frac{1}{b^{2}},\frac{1}{a^{2}}\right\\}\\\ &\leqslant
N^{2+o(1)}\left(\sum_{b\leqslant 12N}\sum_{\begin{subarray}{c}a\leqslant
b\end{subarray}}\frac{1}{b^{2}}+\sum_{a\leqslant
12^{4}N^{2}}\sum_{\begin{subarray}{c}b\leqslant
a\end{subarray}}\frac{1}{a^{2}}\right)\leqslant N^{2+o(1)}.\end{split}$

Finally consider $S_{2}$. If $d$ satisfies $\lambda_{2}(d)\leqslant 1$ then by
Lemma 3.1 and Lemma 3.2

(3.12) $\\#\left({\mathcal{L}}(d)\cap B\right)\ll\frac{N^{3}}{q}.$

For each $|n|\leqslant 6N$ there exists at most one value of $m$ satisfying
(3.3) and for any two pairs $(n_{1},m_{1}),(n_{2},m_{2})$ satisfying (3.3) we
have

$n_{1}^{2}-n_{2}^{2}\equiv 2jd^{2}(m_{1}-m_{2})\bmod q.$

This implies

$J(d)^{2}\ll\\#\\{|n_{1}|,|n_{2}|,|m|\leqslant 6N,\ n_{1}\neq\pm
n_{2}:\leavevmode\nobreak\ n_{1}^{2}-n_{2}^{2}\equiv 2jd^{2}m\bmod{q}\\}.$

Since for any integer $r\neq 0$ the bound on the divisor function implies

$\\#\\{|n_{1}|,|n_{2}|\leqslant 8N:\leavevmode\nobreak\
n_{1}^{2}-n_{2}^{2}=r\\}\leqslant N^{o(1)},$

we obtain

$J(d)^{2}\leqslant\\#\left({\mathcal{L}}(d)\cap B\right)N^{o(1)}.$

By (3.12)

$J(d)\ll\frac{N^{3/2+o(1)}}{q^{1/2}},$

which implies

(3.13) $\begin{split}S_{2}=\sum_{\begin{subarray}{c}d\in\mathbb{F}_{q}\\\
\lambda_{1}(d),\lambda_{2}(d)\leqslant
1\end{subarray}}J(d)^{2}\ll\frac{N^{3/2}}{q^{1/2}}\sum_{\begin{subarray}{c}d\in\mathbb{F}_{q}\\\
\lambda_{1}(d),\lambda_{2}(d)\leqslant
1\end{subarray}}J(d)\ll\frac{N^{7/2+o(1)}}{q^{1/2}}.\end{split}$

Combining (3.5), (3.11) and (3.13) with (3.4), we derive the desired bound on
$\mathsf{T}_{2,2}(N;j,q)$.

##  4\. Proof of Theorem 1.2

###  4.1. Lattices

For a lattice $\Gamma$ and a convex body $B$ we define the dual lattice
$\Gamma^{*}$ and dual body $B^{*}$ by

$\Gamma^{*}=\\{x\in\mathbb{R}^{d}:\leavevmode\nobreak\ \langle
x,y\rangle\in\mathbb{Z}\quad\text{for all}\quad y\in\Gamma\\},$

and

$B^{*}=\\{x\in\mathbb{R}^{d}:\leavevmode\nobreak\ \langle x,y\rangle\leqslant
1\quad\text{for all}\quad y\in B\\},$

respectively.

The following is known as a transference theorem and is due to Mahler [16]
which we present in a form given by Cassels [7, Chapter VIII, Theorem VI].

######  Lemma 4.1.

Let $\Gamma\subseteq\mathbb{R}^{d}$ be a lattice, $B\subseteq\mathbb{R}^{d}$ a
symmetric convex body and let $\Gamma^{*}$ and $B^{*}$ denote the dual lattice
and dual body. Let $\lambda_{1},\ldots,\lambda_{d}$ denote the successive
minima of $\Gamma$ with respect to $B$ and
$\lambda_{1}^{*},\ldots,\lambda_{d}^{*}$ the successive minima of $\Gamma^{*}$
with respect to $B^{*}$. For each $1\leqslant j\leqslant d$ we have

$\lambda_{j}\lambda^{*}_{d-j+1}\leqslant d!.$

We apply Lemma 4.1 to lattices of a specific type whose dual may be easily
calculated. For a proof of the following, see [5, Lemma 15].

######  Lemma 4.2.

Let $a_{1},\ldots,a_{d}$ and $q\geqslant 1$ be integers satisfying
$\gcd(a_{i},q)=1$ and let ${\mathcal{L}}$ denote the lattice

${\mathcal{L}}=\\{(n_{1},\ldots,n_{d})\in\mathbb{Z}^{d}:\leavevmode\nobreak\
a_{1}n_{1}+\ldots+a_{d}n_{d}\equiv 0\bmod{q}\\}.$

Then we have

$\displaystyle{\mathcal{L}}^{*}=\biggl{\\{}\left(\frac{m_{1}}{q},\ldots,\frac{m_{d}}{q}\right)$
$\displaystyle\in\mathbb{Z}^{d}/q:$ $\displaystyle\leavevmode\nobreak\
\exists\ \lambda\in\mathbb{Z}\ \ \text{such that}\ \ a_{j}\lambda\equiv
m_{j}\bmod{q}\biggr{\\}}.$

Our next result should be compared with the case $\nu=3$ of [6, Lemma 17]. It
is possible to give a more direct variant of [6, Lemma 17] to estimate higher
order energies of modular square roots (see the proof of Corollary 4.4 below)
although this seems to put tighter restrictions on the size of the parameter
$N$.

######  Lemma 4.3.

Let $q$ be prime, $a,b,c\not\equiv 0\bmod{q}$ and $L,M,N$ integers. Let
${\mathcal{L}}$ denote the lattice

${\mathcal{L}}=\\{(\ell,m,n)\in\mathbb{Z}^{3}:\leavevmode\nobreak\
a\ell+bm+cn\equiv 0\bmod{q}\\},$

and let $B$ be the convex body

$B=\\{(x,y,z)\in\mathbb{R}^{3}:\leavevmode\nobreak\ |x|\leqslant N,\ \
|y|\leqslant M,\ \ |z|\leqslant L\\}.$

Let

$K=\\#\left({\mathcal{L}}\cap B\right),$

and $\lambda_{1},\lambda_{2}$ denote the first and second successive minima of
${\mathcal{L}}$ with respect to $B$. Then at least one of the following holds:

  * (i)

$K<\max\left\\{\frac{640LMN}{q},\,1\right\\}.$

  * (ii)

$\lambda_{1}\leqslant 1$ and $\lambda_{2}>1$.

  * (iii)

There exists some $\lambda\not\equiv 0\bmod{q}$ and $\ell,m,n\in\mathbb{Z}$
satisfying

$|\ell|\leqslant\frac{4320MN}{K},\quad|m|\leqslant\frac{4320LN}{K},\quad|n|\leqslant\frac{4320LM}{K}$

and

$a\lambda\equiv\ell\bmod{q},\quad b\lambda\equiv m\bmod{q},\quad
c\lambda\equiv n\bmod{q}.$

###### Proof.

Assume that (i) fails. Thus we have

(4.1) $K\geqslant\max\left\\{\frac{640LMN}{q},\,1\right\\}.$

Then $K\geqslant 1$. Hence, if
$\lambda_{1}\leqslant\lambda_{2}\leqslant\lambda_{3}$ denote the successive
minima of ${\mathcal{L}}$ with respect to $B$, then $\lambda_{1}\leqslant 1$.
We first show (4.1) implies

$\lambda_{3}>1.$

Indeed, otherwise by Lemma 3.2

(4.2)
$K\leqslant\left(\frac{2}{\lambda_{1}}+1\right)\left(\frac{4}{\lambda_{2}}+1\right)\left(\frac{6}{\lambda_{3}}+1\right)\leqslant\frac{3}{\lambda_{1}}\frac{5}{\lambda_{2}}\frac{7}{\lambda_{3}}=\frac{105}{\lambda_{1}\lambda_{2}\lambda_{3}}.$

Since

$\mathrm{Vol}(\mathbb{R}^{3}/{\mathcal{L}})=q\qquad\mbox{and}\qquad\mathrm{Vol}(B)=8LMN,$

we see from Lemma 3.1 that

(4.3)
$\frac{1}{\lambda_{1}\lambda_{2}\lambda_{3}}\leqslant\frac{3!}{8}\frac{8LMM}{q}=\frac{6LMN}{q},$

which together with (4.2) contradicts (4.1).

Hence we have either

(4.4) $\lambda_{1}\leqslant 1,\qquad\lambda_{2},\lambda_{3}>1,$

or

(4.5) $\lambda_{1},\lambda_{2}\leqslant 1,\qquad\lambda_{3}>1.$

Clearly (4.4) is the same as (ii).

Next suppose that we have (4.5). By Lemma 3.2, a similar calculation as
before, together with (4.3) gives,

(4.6) $K\leqslant
6\frac{15}{\lambda_{1}\lambda_{2}}=\frac{90\lambda_{3}}{\lambda_{1}\lambda_{2}\lambda_{3}}.$

Applying Lemma 3.1 and using

$\mathrm{Vol}(B)=8NML,\quad\mathrm{Vol}(\mathbb{R}^{3}/{\mathcal{L}})=q,$

we derive from (4.6) that

$K\leqslant\frac{90\cdot
3!\,\mathrm{Vol}(B)\lambda_{3}}{2^{3}\,\mathrm{Vol}(\mathbb{R}^{3}/{\mathcal{L}})}=\frac{720NML\lambda_{3}}{q}.$

Let $\lambda_{1}^{*}$ denote the first successive minima of the dual lattice
${\mathcal{L}}^{*}$ with respect to the dual body $B^{*}$. By Lemma 4.1

$\lambda_{3}\leqslant\frac{6}{\lambda_{1}^{*}}.$

The above estimates combined with (4.6) implies

$\lambda_{1}^{*}\leqslant\frac{4320NML}{qK}.$

Hence, by the definition of $\lambda_{1}^{*}$

(4.7) ${\mathcal{L}}^{*}\cap\frac{4320NML}{qK}B^{*}\neq\\{(0,0,0)\\}.$

Its remains to recall that by Lemma 4.2

$\displaystyle{\mathcal{L}}^{*}$
$\displaystyle=\biggl{\\{}\left(\frac{\ell}{q},\frac{m}{q},\frac{n}{q}\right)\in\mathbb{Z}^{3}/q:\leavevmode\nobreak\
\exists\ \lambda\in\mathbb{Z}\text{ such that }$
$\displaystyle\qquad\qquad\qquad a\lambda\equiv\ell\bmod{q},\ b\lambda\equiv
m\bmod{q},\ c\lambda\equiv n\bmod{q}\biggr{\\}},$

and also it is obvious that

$B^{*}=\\{(x,y,z)\in\mathbb{R}^{3}:\leavevmode\nobreak\
L|x|+M|y|+N|z|\leqslant 1\\}.$

By (4.7), this implies there exists some $\lambda\not\equiv 0\bmod{q}$ and
$\ell,m,n$ satisfying (iii), which completes the proof. ∎

######  Corollary 4.4.

Let $\varepsilon>0$ be a fixed real number. For $j\in\mathbb{F}_{q}^{*}$ and
integer $N\ll p,$ let ${\mathcal{A}},{\mathcal{D}}\subseteq\mathbb{F}_{q}$
denote the sets

${\mathcal{A}}=\\{x\in\mathbb{F}_{q}^{*}:\leavevmode\nobreak\
jx^{2}\in[1,N]\\}.$

and

${\mathcal{D}}=\\{d\in\mathbb{F}_{q}^{*}:\leavevmode\nobreak\
({\mathcal{A}}\circ{\mathcal{A}})(d)\geqslant\Delta\\}.$

Let $K$ be sufficiently large and suppose $K$ and $\Delta$ satisfy

(4.8)
$K\geqslant\left(\frac{N^{6}}{\Delta^{10}q^{1/2}}+\frac{N^{15/2}}{\Delta^{12}q^{1/2}}+\frac{N^{10}}{\Delta^{16}q^{1/2}}\right)N^{\varepsilon}$

and

(4.9)
$\Delta\geqslant\left(\frac{N^{3/2}}{q^{1/2}}+\frac{N^{5/8}}{q^{1/8}}\right)N^{\varepsilon}.$

Let ${\mathcal{F}}\subseteq\mathbb{F}_{q}^{*}$ denote the set of $f$
satisfying

(4.10) $({\mathcal{D}}\circ{\mathcal{D}})(f)\geqslant K.$

Then either

(4.11) $K\ll 1,$

or

$K\\#{\mathcal{F}}\ll\frac{N^{3+o(1)}}{\Delta^{4}}.$

###### Proof.

From (4.10)

(4.12) $K\leqslant\\#\\{(d_{1},d_{2})\in{\mathcal{D}}:\leavevmode\nobreak\
d_{1}-d_{2}=f\\}.$

If $d_{1},d_{2}\in{\mathcal{D}}$ satisfy $d_{1}-d_{2}=f$, then

$d_{1}^{2}-d_{2}^{2}-f^{2}=(d_{1}-d_{2})^{2}+2d_{1}d_{2}-2d_{2}^{2}-f^{2}=2d_{2}(d_{1}-d_{2})=2d_{2}f$

and some algebraic manipulations show

$(2jd_{1}^{2}-2jd_{2}^{2}-2jf^{2})^{2}=8jf^{2}(2jd_{2}^{2}).$

Since $0\not\in{\mathcal{D}}$, for each $d\in{\mathcal{D}}$, by (4.9) and [10,
Lemma 6.4] there exists $m_{d},n_{d}$ satisfying

(4.13) $\begin{split}&2jd^{2}\equiv
m_{d}^{-1}n_{d}\bmod{q},\qquad|n_{d}|\ll\frac{N^{2}}{\Delta^{2}},\\\
&|m_{d}|\ll\frac{N}{\Delta^{2}},\qquad\gcd(m_{d},n_{d})=1.\end{split}$

Let $I(f)$ count the number of solutions to the congruence

(4.14)
$\left(n_{d_{1}}m_{d_{1}}^{-1}-n_{d_{2}}m_{d_{2}}^{-1}-2jf^{2}\right)^{2}\equiv
8jf^{2}n_{d_{2}}m_{d_{2}}^{-1}\bmod{q},$

with $d_{1},d_{2}\in{\mathcal{D}}$. The above and (4.12) imply

(4.15) $K\leqslant I(f).$

Rearranging (4.14) we obtain

$\left(m_{d_{2}}n_{d_{1}}-m_{d_{1}}n_{d_{2}}-2jf^{2}m_{d_{1}}m_{d_{2}}\right)^{2}\equiv
8jf^{2}m_{d_{1}}^{2}m_{d_{2}}n_{d_{2}}\bmod{q}.$

This implies that $I(f)$ is bounded by the number of solutions to

(4.16)
$\begin{split}(n_{d_{1}}m_{d_{2}}-n_{d_{2}}m_{d_{1}})^{2}&-4jf^{2}m_{d_{1}}m_{d_{2}}(n_{d_{1}}m_{d_{2}}+n_{d_{2}}m_{d_{1}})\\\
&\qquad\qquad+4j^{2}f^{4}(m_{d_{1}}m_{d_{2}})^{2}\equiv 0\bmod{q},\end{split}$

with $d_{1},d_{2}\in{\mathcal{D}}$. Let ${\mathcal{L}}$ denote the lattice

${\mathcal{L}}=\\{(m,n,\ell)\in\mathbb{Z}^{3}:\leavevmode\nobreak\
m+njf^{2}+\ell j^{2}f^{4}\equiv 0\bmod{q}\\},$

and $B$ the convex body

$B=\left\\{(x,y,z)\in\mathbb{R}^{3}:\leavevmode\nobreak\
|x|\leqslant\frac{CN^{6}}{\Delta^{8}},\
|y|\leqslant\frac{CN^{5}}{\Delta^{8}},\
|z|\leqslant\frac{CN^{4}}{\Delta^{8}}\right\\}.$

for a suitable absolute constant $C$. By (4.13) and (4.16)

(4.17)
$\begin{split}\bigl{(}(n_{d_{1}}m_{d_{2}}-n_{d_{2}}m_{d_{1}})^{2},-4m_{d_{1}}m_{d_{2}}(n_{d_{1}}m_{d_{2}}+n_{d_{2}}m_{d_{1}}),&\\\
4(m_{d_{1}}m_{d_{2}})^{2}\bigr{)}&\in{\mathcal{L}}\cap B.\end{split}$

Let $\lambda_{1},\lambda_{2}$ denote the first and second successive minima of
${\mathcal{L}}$ with respect to $B$. Assuming that $K\geqslant 1$ we have
$\lambda_{1}\leqslant 1$.

Suppose that

$\lambda_{1}\leqslant 1,\quad\lambda_{2}>1.$

Then there exists some $(a_{0},b_{0},c_{0})\in{\mathcal{L}}\cap B$ such that
for any $d_{1},d_{2}\in{\mathcal{D}}$ satisfying (4.17) we have

$\displaystyle\left((n_{d_{1}}m_{d_{2}}-n_{d_{2}}m_{d_{1}})^{2},-4m_{d_{1}}m_{d_{2}}(n_{d_{1}}m_{d_{2}}+n_{d_{2}}m_{d_{1}}),(m_{d_{1}}m_{d_{2}})^{2}\right)$
$\displaystyle=m(a_{0},b_{0},$ $\displaystyle c_{0}),$

for some $m\in\mathbb{Z}$. Note from (4.13) for each
$d_{1},d_{2}\in{\mathcal{D}}$ we have $m_{d_{1}}m_{d_{2}}\neq 0$ and hence
$c_{0}\neq 0$. This implies

$\displaystyle\left(\frac{n_{d_{1}}}{m_{d_{1}}}-\frac{n_{d_{2}}}{m_{d_{2}}}\right)^{2}=\frac{a_{0}}{c_{0}},$
$\displaystyle\frac{n_{d_{1}}}{m_{d_{1}}}+\frac{n_{d_{2}}}{m_{d_{2}}}=\frac{b_{0}}{c_{0}}.$

Hence

$\displaystyle
K\leqslant\\#\biggl{\\{}(d_{1},d_{2})\in{\mathcal{D}}\times{\mathcal{D}}:\leavevmode\nobreak\
\frac{n_{d_{1}}}{m_{d_{1}}}-\frac{n_{d_{2}}}{m_{d_{2}}}$
$\displaystyle=\pm\left(\frac{a_{0}}{c_{0}}\right)^{1/2},$
$\displaystyle\frac{n_{d_{1}}}{m_{d_{1}}}+\frac{n_{d_{2}}}{m_{d_{2}}}=\frac{b_{0}}{c_{0}}\biggr{\\}}\leqslant
4,$

since once $n_{d_{1}}/m_{d_{1}}$ is fixed, due to the coprimality condition in
(4.13), $d^{2}_{1}$ is uniquely defined, and similarly for $d^{2}_{2}$. This
implies (4.11).

Suppose next that

(4.18) $\lambda_{1}\leqslant 1,\quad\lambda_{2}\leqslant 1.$

Let $J(\ell,m,n)$ count the number of solutions to

$m_{1}m_{2}=\ell,\quad n_{1}m_{2}+n_{2}m_{1}=m,\quad n_{1}m_{2}-n_{2}m_{1}=n,$

with

(4.19)
$|m_{1}|,|m_{2}|\ll\frac{N}{\Delta^{2}},\quad|n_{1}|,|n_{2}|\ll\frac{N^{2}}{\Delta^{2}},\quad\quad
m_{1}m_{2}n_{1}n_{2}\neq 0,$

so that

(4.20) $I(f)\ll\sum_{\begin{subarray}{c}|m|,|n|\leqslant CN^{3}/\Delta^{4}\\\
|\ell|\leqslant CN^{2}/\Delta^{4}\\\ 4j^{2}f^{4}\ell^{2}-4jf^{2}\ell
m+n^{2}\equiv 0\bmod{q}\end{subarray}}J(\ell,m,n),$

for some absolute constant $C$. We next show that

(4.21) $J(\ell,m,n)=N^{o(1)}.$

Estimates for the divisor function imply the number of solutions to

$m_{1}m_{2}=\ell,\quad\text{$m_{1},m_{2}$ satisfying\leavevmode\nobreak\
\eqref{eq:n12m12}},$

is at most $N^{o(1)}$. For each such $m_{1},m_{2}$ there exists at most one
solution to the system

$n_{1}m_{2}-n_{2}m_{1}=n,\quad
n_{1}m_{2}+n_{2}m_{1}=m,\quad\text{$n_{1},n_{2}$
satisfying\leavevmode\nobreak\ \eqref{eq:n12m12}},$

which establishes (4.21). By (4.15) and (4.20)

$\displaystyle K\leqslant\\#\\{(\ell,m,n)\in\mathbb{Z}^{3}$
$\displaystyle:\leavevmode\nobreak\ |\ell|\leqslant CN^{2}/\Delta^{4},\
|m|,|n|\leqslant CN^{3}/\Delta^{4},\ $ $\displaystyle\quad n^{2}-4jf^{2}\ell
m+4j^{2}f^{4}\ell^{2}\equiv 0\bmod{q}\\}N^{o(1)},$

and hence

(4.22) $\begin{split}K\leqslant\\#\Bigl{\\{}(\ell,m,n)\in\mathbb{Z}^{3}&:\\\
|\ell|\leqslant 2CN^{2}/\Delta^{4},&\ |m|\leqslant 4C^{2}N^{5}/\Delta^{8},\
|n|\leqslant CN^{3}/\Delta^{4},\\\ &n^{2}+jf^{2}m+j^{2}f^{4}\ell^{2}\equiv
0\bmod{q}\Bigr{\\}}N^{o(1)}.\end{split}$

By (4.9), for each $\ell,n\in\mathbb{Z}$, there exists at most one value of
$|m|\ll N^{5}/\Delta^{8}$ satisfying

$n^{2}+jf^{2}m+j^{2}f^{4}\ell^{2}\equiv 0\bmod{q}.$

For any $(\ell_{1},m_{1},n_{1})$ and $(\ell_{2},m_{2},n_{2})$ satisfying the
conditions of (4.22), there exists some $|m|\ll N^{5}/\Delta^{8}$ such that

(4.23)
$n_{1}^{2}+n_{2}^{2}-2jf^{2}m+j^{2}f^{4}(\ell^{2}_{1}+\ell_{2}^{2})\equiv
0\bmod{q}.$

Define the lattice

${\mathcal{L}}=\\{(n,m,\ell)\in\mathbb{Z}^{3}:\leavevmode\nobreak\
n+jf^{2}m+j^{2}f^{4}\ell\equiv 0\bmod{q}\\},$

and the convex body

$\displaystyle B=\\{(n,m,\ell)\in\mathbb{R}^{3}:\leavevmode\nobreak\ |n|$
$\displaystyle\leqslant C_{0}N^{6}/\Delta^{4},$ $\displaystyle|m|\leqslant
C_{0}N^{5}/\Delta^{8},\ |\ell|\leqslant C_{0}N^{4}/\Delta^{8}\\},$

for a suitable constant $C_{0}$. Since for any integer $r$

$\\#\\{n_{1},n_{2}\in\mathbb{Z}:\leavevmode\nobreak\
n_{1}^{2}+n_{2}^{2}=r\\}\leqslant r^{o(1)},$

we see that (4.23) implies

$K^{2}\leqslant\\#\left({\mathcal{L}}\cap B\right)N^{o(1)}.$

By (4.8), (4.18) and Lemma 4.3, there exists $(\ell,m,n)\neq(0,0,0)$
satisfying

(4.24)
$|\ell|\leqslant\frac{N^{11+o(1)}}{\Delta^{16}K^{2}},\qquad|m|\leqslant\frac{N^{10+o(1)}}{\Delta^{16}K^{2}},\qquad|n|\leqslant\frac{N^{9+o(1)}}{\Delta^{16}K^{2}},$

and

(4.25) $jf^{2}n\equiv m\bmod{q},\quad j^{2}f^{4}n\equiv\ell\bmod{q}.$

Note we may assume

(4.26) $\gcd(\ell,m,n)=1.$

Recall (4.16)

(4.27)
$\begin{split}I(f)\leqslant\\#\\{(d_{1},d_{2})&\in{\mathcal{D}}^{2}:\leavevmode\nobreak\
(n_{d_{1}}m_{d_{2}}-n_{d_{2}}m_{d_{1}})^{2}\\\
&-4jf^{2}m_{d_{1}}m_{d_{2}}(n_{d_{1}}m_{d_{2}}+n_{d_{2}}m_{d_{1}})\\\
&\qquad\qquad+4j^{2}f^{4}(m_{d_{1}}m_{d_{2}})^{2}\equiv
0\bmod{q}\\}.\end{split}$

If $d_{1},d_{2}$ satisfy the conditions in (4.27), then by (4.25)

$\displaystyle
n(n_{d_{1}}m_{d_{2}}-n_{d_{2}}m_{d_{1}})^{2}-4mm_{d_{1}}m_{d_{2}}(n_{d_{1}}m_{d_{2}}+n_{d_{2}}m_{d_{1}})$
$\displaystyle\quad\qquad\qquad\qquad\qquad\qquad\qquad+4\ell(m_{d_{1}}m_{d_{2}})^{2}\equiv
0\bmod{q},$

and hence from (4.8), assuming that $N$ is large enough, we derive

(4.28)
$\begin{split}n(n_{d_{1}}m_{d_{2}}-n_{d_{2}}m_{d_{1}})^{2}-4mm_{d_{1}}m_{d_{2}}(n_{d_{1}}&m_{d_{2}}+n_{d_{2}}m_{d_{1}})\\\
&+4\ell(m_{d_{1}}m_{d_{2}})^{2}=0.\end{split}$

Similarly by (4.24) and (4.25) we have $m^{2}\equiv n\ell\bmod{q}$ and again
(4.8) ensures that

$m^{2}=n\ell.$

Therefore (4.28) implies the following equation

$\left(\frac{n_{d_{1}}}{m_{d_{1}}}-\frac{n_{d_{2}}}{m_{d_{2}}}\right)^{2}-4\left(\frac{n_{d_{1}}}{m_{d_{1}}}+\frac{n_{d_{2}}}{m_{d_{2}}}\right)\left(\frac{m}{n}\right)+4\left(\frac{m}{n}\right)^{2}=0.$

We see that

(4.29)
$\frac{m}{n}=\frac{1}{2}\left(\frac{n_{d_{1}}}{m_{d_{1}}}+\frac{n_{d_{2}}}{m_{d_{2}}}\right)\pm\frac{\sqrt{n_{d_{1}}m_{d_{1}}n_{d_{2}}m_{d_{2}}}}{m_{d_{1}}m_{d_{2}}}.$

Hence from (4.13) and (4.27), there exists some constant $C$ such that

$\displaystyle I(f)$
$\displaystyle\leqslant\\#\biggl{\\{}\left(m_{d_{1}},m_{d_{2}},n_{d_{1}},n_{d_{2}}\right)\in\mathbb{Z}^{4}:$
$\displaystyle\qquad\qquad|m_{d_{1}}|,|m_{d_{2}}|\leqslant\frac{CN}{\Delta^{2}},\
|n_{d_{1}}|,|n_{d_{2}}|\leqslant\frac{CN^{2}}{\Delta^{2}},$
$\displaystyle\qquad\qquad\qquad\qquad
m_{d_{1}}m_{d_{2}}n_{d_{1}}n_{d_{2}}\neq 0,\ \text{and\leavevmode\nobreak\
\eqref{eq:nm123123123} holds}\biggr{\\}}.$

Summing the above over $f\in{\mathcal{F}}$, using (4.15) and noting that for
each $\ell,m,n$ satisfying (4.26) there exists $O(1)$ values of $f$ satisfying
(4.25), we see that $K\\#{\mathcal{F}}$ is bounded by the number of solutions
to the equation (4.29) with integer variables satisfying

$|m_{d_{1}}|,|m_{d_{2}}|\leqslant\frac{CN}{\Delta^{2}},\qquad|n_{d_{1}}|,|n_{d_{2}}|\leqslant\frac{CN^{2}}{\Delta^{2}},\qquad
n_{d_{1}}n_{d_{2}}m_{d_{1}}m_{d_{2}}\neq 0.$

We see from (4.29) that $n_{d_{1}}m_{d_{1}}n_{d_{2}}m_{d_{2}}=r^{2}$ for some
$r\in\mathbb{Z}$ and hence a bound on the divisor function, see [15, Equation
(1.81)], implies

$K\\#{\mathcal{F}}\leqslant N^{o(1)}\\#\left\\{\ell\leqslant
C^{4}\frac{N^{6}}{\Delta^{8}}:\leavevmode\nobreak\ \ell=r^{2}\ \text{for some
$r\in\mathbb{Z}$}\right\\}\leqslant\frac{N^{3+o(1)}}{\Delta^{4}},$

which completes the proof. ∎

###  4.2. Concluding the proof

Let notation be as in Corollary 4.4, so that

$T_{4,2}(N;j,q)=\sum_{x\in\mathbb{F}_{q}}({\mathcal{A}}\circ{\mathcal{A}}\circ{\mathcal{A}}\circ{\mathcal{A}})(x)^{2}.$

By (1.5) we may assume that

(4.30) $N\leqslant q^{1/3},$

Applying the dyadic pigeonhole principle, there exist
$\Delta_{1},\Delta_{2}\geqslant 1$ and
${\mathcal{D}}_{1},{\mathcal{D}}_{2}\subseteq\mathbb{F}_{q}$ given by

${\mathcal{D}}_{j}=\\{x\in\mathbb{F}_{q}:\leavevmode\nobreak\
\Delta_{j}\leqslant({\mathcal{A}}\circ{\mathcal{A}})(x)<2\Delta_{j}\\},\qquad
j=1,2,$

such that

$T_{4,2}(N;j,q)\leqslant
N^{o(1)}(\Delta_{1}\Delta_{2})^{2}E({\mathcal{D}}_{1},{\mathcal{D}}_{2}),$

where

$E({\mathcal{D}}_{1},{\mathcal{D}}_{2})=\sum_{x\in\mathbb{F}_{q}}({\mathcal{D}}_{1}\circ{\mathcal{D}}_{2})(x)^{2}.$

By the Cauchy-Schwarz inequality

$E({\mathcal{D}}_{1},{\mathcal{D}}_{2})\leqslant
E({\mathcal{D}}_{1})^{1/2}E({\mathcal{D}}_{2})^{1/2},$

and hence there exists some $\Delta$ and ${\mathcal{D}}$ given by

${\mathcal{D}}=\\{x\in\mathbb{F}_{q}:\leavevmode\nobreak\
\Delta\leqslant({\mathcal{A}}\circ{\mathcal{A}})(x)<2\Delta\\},$

such that

(4.31) $T_{4,2}(N;j,q)\leqslant N^{o(1)}\Delta^{4}E({\mathcal{D}}).$

It is also obvious from (3.1) that

(4.32) $\Delta^{2}\left(\\#{\mathcal{D}}\right)\leqslant T_{2,2}(N;j,q),$

and

(4.33) $\\#{\mathcal{D}}\leqslant\Delta\\#{\mathcal{D}}\ll N^{2}.$

Isolating the diagonal contribution in $E({\mathcal{D}})$, we write

$E({\mathcal{D}})=(\\#{\mathcal{D}})^{2}+\sum_{f\in\mathbb{F}_{q}^{*}}({\mathcal{D}}\circ{\mathcal{D}})(f)^{2}.$

We may assume

(4.34) $E({\mathcal{D}})\leqslant
2\sum_{f\in\mathbb{F}_{q}^{*}}({\mathcal{D}}\circ{\mathcal{D}})(f)^{2},$

since otherwise we have $E({\mathcal{D}})\leqslant 2(\\#{\mathcal{D}})^{2}$
and it follows from the bounds (4.31) and (4.32) that

$T_{4,2}(N;j,q)\leqslant\Delta^{4}(\\#{\mathcal{D}})^{2}N^{o(1)}\leqslant\mathsf{T}_{2,2}(N;j,q)^{2}N^{o(1)}.$

Now, recalling the condition (4.30) and using Theorem 1.1, we derive

$T_{4,2}(N;j,q)\leqslant N^{4+o(1)}.$

By (4.34) and the dyadic pigeonhole principle there exists some $K$ and a set
${\mathcal{F}}\subseteq\mathbb{F}_{q}^{*}$ given by

${\mathcal{F}}=\\{f\in\mathbb{F}_{q}^{*}:\leavevmode\nobreak\
K\leqslant({\mathcal{D}}\circ{\mathcal{D}})(f)<2K\\},$

such that

(4.35) $E({\mathcal{D}})\leqslant K^{2}\\#{\mathcal{F}}N^{o(1)}.$

Combining with (4.31) and (4.35) gives

(4.36) $T_{4,2}(N;j,q)\leqslant\Delta^{4}K^{2}\\#{\mathcal{F}}N^{o(1)}.$

We apply Corollary 4.4 to estimate the right hand side of (4.36).

We now fix some $\varepsilon>0$ and suppose first that one of (4.8) or (4.9)
does not hold. In particular, assume

(4.37)
$K<\left(\frac{N^{6}}{\Delta^{10}q^{1/2}}+\frac{N^{15/2}}{\Delta^{12}q^{1/2}}+\frac{N^{10}}{\Delta^{16}q^{1/2}}\right)N^{\varepsilon}$

or

(4.38)
$\Delta<\left(\frac{N^{3/2}}{q^{1/2}}+\frac{N^{5/8}}{q^{1/8}}\right)N^{\varepsilon}.$

If (4.37) holds, then using the trivial bounds

$K\\#{\mathcal{F}}\leqslant(\\#{\mathcal{D}})^{2}\qquad\mbox{and}\qquad\Delta\\#{\mathcal{D}}\ll
N^{2}\,,$

we derive from (4.36)

(4.39)
$\begin{split}T_{4,2}(N;j,q)&\leqslant\Delta^{4}(\\#{\mathcal{D}})^{2}KN^{o(1)}\leqslant\Delta^{2}KN^{4+o(1)}\\\
&\leqslant\left(\frac{N^{6}}{\Delta^{8}q^{1/2}}+\frac{N^{15/2}}{\Delta^{10}q^{1/2}}+\frac{N^{10}}{\Delta^{14}q^{1/2}}\right)N^{4+\varepsilon+o(1)}\\\
&\leqslant\left(\frac{N^{6}}{q^{1/2}}+\frac{N^{15/2}}{q^{1/2}}+\frac{N^{10}}{q^{1/2}}\right)N^{4+\varepsilon+o(1)}\\\
&\leqslant\frac{N^{10}}{q^{1/2}}N^{4+\varepsilon+o(1)}=\frac{N^{8}}{q^{1/2}}N^{6+\varepsilon+o(1)}.\end{split}$

If (4.38) holds, then from (4.36)

(4.40) $\begin{split}T_{4,2}(N;j,q)&\leqslant
N^{o(1)}\Delta^{4}(\\#{\mathcal{D}})^{3}\leqslant N^{6+o(1)}\Delta\\\
&\leqslant\left(\frac{N^{3/2}}{q^{1/2}}+\frac{N^{5/8}}{q^{1/8}}\right)N^{6+o(1)}.\end{split}$

Hence if one of the conditions (4.8) or (4.9) does not hold then combining
(4.39) and (4.40) we obtain

(4.41)
$T_{4,2}(N;j,q)\leqslant\left(\frac{N^{5/8}}{q^{1/8}}+\frac{N^{8}}{q^{1/2}}\right)N^{6+\varepsilon+o(1)}.$

Suppose next that (4.37) and (4.38) both fail and thus both (4.8) and (4.9)
hold. By Corollary 4.4 we have either

(4.42) $K\ll 1,$

or

(4.43) $K\\#{\mathcal{F}}\leqslant\frac{N^{3+o(1)}}{\Delta^{4}}.$

If (4.42) holds then from (4.36) and the trivial bound
$K\\#{\mathcal{F}}\leqslant(\\#{\mathcal{D}})^{2}$, we derive

$T_{4,2}(N;j,q)\leqslant\Delta^{4}K^{2}\\#{\mathcal{F}}N^{o(1)}\leqslant\Delta^{4}K\\#{\mathcal{F}}N^{o(1)}\leqslant\Delta^{4}(\\#{\mathcal{D}})^{2}N^{o(1)}.$

Now the bound (4.32) and Theorem 1.1 (under the condition (4.30)), yield

$T_{4,2}(N;j,q)\leqslant T_{2,2}(N;j,q)^{2}N^{o(1)}\leqslant N^{4+o(1)}.$

If (4.43) holds then using (4.33)

(4.44) $T_{4,2}(N;j,q)\leqslant N^{3+o(1)}K\leqslant
N^{3+o(1)}\\#{\mathcal{D}}\leqslant N^{5+o(1)}.$

Combining (4.41) and (4.44), since $\varepsilon>0$ is arbitrary, we complete
the proof.

##  5\. Proof of Theorem 1.3

###  5.1. Product polynomials

In the proof of [20, Lemma 5.1], a certain polynomial in four variables with
integer coefficients played a key role. More precisely, it has been found in
[20] that the polynomial

$\displaystyle F(U,V,X,Y)$ $\displaystyle=64UVXY$
$\displaystyle\qquad-\left(4UV+4XY-\left(X+Y-U-V\right)^{2}\right)^{2}\,,$

has the following property. Letting $U=u^{2}$, $V=v^{2}$, $X=x^{2}$, and
$Y=y^{2}$, one has that $F(u^{2},v^{2},x^{2},y^{2})=0$ for any $u,v,x,y$ for
which $u+v=x+y$ (over any commutative ring). We now proceed to discuss this
property in a more general context.

Denote ${\mathcal{U}}_{k}=\\{\omega\in\mathbb{C}:\leavevmode\nobreak\
\omega^{k}=1\\}$ and consider the polynomial

$G_{k}(X_{1},X_{2},X_{3},X_{4})=\prod_{\omega_{1},\omega_{2},\omega_{3}\in{\mathcal{U}}_{k}}(\omega_{1}X_{1}+\omega_{2}X_{2}-\omega_{3}X_{3}-X_{4})$

defined over the cyclotomic field $K_{k}=\mathbb{Q}\left(\exp(2\pi
i/k)\right)$. Since the Galois group ${\mathrm{Gal}}(K_{k}/\mathbb{Q})$ of $K$
is cyclic and any automorphism $\sigma$ of $K_{k}$ over $\mathbb{Q}$ is a
multiplication by some $\omega\in{\mathcal{U}}_{k}$, we see that

$\displaystyle\sigma$
$\displaystyle\left(G_{k}(X_{1},X_{2},X_{3},X_{4})\right)$
$\displaystyle=\prod_{\omega_{1},\omega_{2},\omega_{3}\in{\mathcal{U}}_{k}}\left(\sigma\left(\omega_{1}\right)X_{1}+\sigma\left(\omega_{2}\right)X_{2}-\sigma\left(\omega_{3}\right)X_{3}-\sigma\left(1\right)X_{4}\right)$
$\displaystyle=\prod_{\omega_{1},\omega_{2},\omega_{3}\in{\mathcal{U}}_{k}}\left(\omega\omega_{1}X_{1}+\omega\omega_{2}X_{2}-\omega\omega_{3}X_{3}-\omega
X_{4}\right)$
$\displaystyle=\omega^{k^{3}}\prod_{\omega_{1},\omega_{2},\omega_{3}\in{\mathcal{U}}_{k}}\left(\omega_{1}X_{1}+\omega_{2}X_{2}-\omega_{3}X_{3}-X_{4}\right)$
$\displaystyle=G_{k}(X_{1},X_{2},X_{3},X_{4}).$

Hence $G_{k}$ has rational coefficients. Since obviously these coefficients
are algebraic integers, we see that
$G_{k}\left(X_{1},X_{2},X_{3},X_{4}\right)\in\mathbb{Z}[X_{1},X_{2},X_{3},X_{4}]$.

We also see that

$\displaystyle\prod_{\omega_{1},\omega_{2},\omega_{3}\in{\mathcal{U}}_{k}}$
$\displaystyle\left(\omega_{1}X_{1}+\omega_{2}X_{2}-\omega_{3}X_{3}-X_{4}\right)$
$\displaystyle=\prod_{\omega_{1},\omega_{2},\omega_{3}\in{\mathcal{U}}_{k}}\left(\omega_{1}X_{1}+\omega_{1}\omega_{2}X_{2}-\omega_{1}\omega_{3}X_{3}-X_{4}\right)$
$\displaystyle=\prod_{\omega_{2},\omega_{3}\in{\mathcal{U}}_{k}}\prod_{\omega_{1}\in{\mathcal{U}}_{k}}\left(\omega_{1}\left(X_{1}+\omega_{2}X_{2}-\omega_{3}X_{3}\right)-X_{4}\right)$
$\displaystyle=(-1)^{k}\prod_{\omega_{2},\omega_{3}\in{\mathcal{U}}_{k}}\left(\left(X_{1}+\omega_{2}X_{2}-\omega_{3}X_{3}\right)^{k}-X_{4}^{k}\right)$

Therefore $G_{k}(X_{1},X_{2},X_{3},X_{4})$ is a polynomial in $X_{4}^{k}$.
Similarly,

$\displaystyle\prod_{\omega_{1},\omega_{2},\omega_{3}\in{\mathcal{U}}_{k}}$
$\displaystyle\left(\omega_{1}X_{1}+\omega_{2}X_{2}-\omega_{3}X_{3}-X_{4}\right)$
$\displaystyle=\prod_{\omega_{2},\omega_{3}\in{\mathcal{U}}_{k}}\prod_{\omega_{1}\in{\mathcal{U}}_{k}}\left(X_{1}+\omega_{1}^{-1}\left(\omega_{2}X_{2}-\omega_{3}X_{3}-X_{4}\right)\right)$
$\displaystyle=\prod_{\omega_{2},\omega_{3}\in{\mathcal{U}}_{k}}\left(X_{1}^{k}+\left(\omega_{3}X_{3}+X_{4}-\omega_{2}X_{2}\right)^{k}\right)$

Thus, it is also a polynomial in $X_{1}^{k}$ and of course also in $X_{2}^{k}$
and $X_{3}^{k}$. Hence we can write

$G_{k}(X_{1},X_{2},X_{3},X_{4})=F_{k}\left(X_{1}^{k},X_{2}^{k},X_{3}^{k},X_{4}^{k}\right)$

for some polynomial
$F_{k}\left(X_{1},X_{2},X_{3},X_{4}\right)\in\mathbb{Z}[X_{1},X_{2},X_{3},X_{4}]$.

######  Remark 5.1.

It is clear that this construction can be extended in several directions, in
particular to polynomials $F_{\nu,k}\in\mathbb{Z}[X_{1},\ldots,X_{2\nu}]$ such
that

$F_{\nu,k}\left(x_{1}^{k},\ldots,x_{2\nu}^{k}\right)=0$

whenever $x_{1}+\ldots+x_{\nu}=x_{\nu+1}+\ldots+x_{2\nu}$.

###  5.2. The zero set of $F_{k}(X_{1},X_{2},X_{3},X_{4})$

We now need the following bound on the number of integer zeros of $F_{k}$ in a
box. Denote by $T_{k}(N)$ the number of solution to the equation

$\displaystyle\\#\\{(n_{1},n_{2},n_{3},n_{4})\in\mathbb{Z}^{4}:\leavevmode\nobreak\
1$ $\displaystyle\leqslant n_{1},n_{2},n_{3},n_{4}\leqslant N,$
$\displaystyle\qquad F_{k}(n_{1},n_{2},n_{3},n_{4})=0\\}\ll N^{2}.$

######  Lemma 5.2.

Fix an integer $k\geqslant 3$. For any positive integer $N$, we have
$T_{k}(N)\ll N^{2}$.

###### Proof.

Take a solution $(n_{1},n_{2},n_{3},n_{4})$ to
$F_{k}(n_{1},n_{2},n_{3},n_{4})=0$ satisfying $1\leqslant
n_{1},n_{2},n_{3},n_{4}\leqslant N$. Denote by $t_{1},t_{2},t_{3},t_{4}$ the
positive real numbers that are roots of order $d$ of $n_{1},n_{2},n_{3},n_{4}$
respectively.

Therefore there exist roots of unity
$\omega_{1},\omega_{2},\omega_{3}\in\mathcal{U}_{d}$ such that

(5.1) $\omega_{1}t_{1}+\omega_{2}t_{2}-\omega_{3}t_{3}-t_{4}=0.$

We now distinguish two cases.

Case 1. At least one of the roots of unity $\omega_{1}$, $\omega_{2}$,
$\omega_{3}$ is not real. Complex conjugation then provides a second linear
equation,

(5.2)
$\bar{\omega}_{1}t_{1}+\bar{\omega}_{2}t_{2}-\bar{\omega}_{3}t_{3}-t_{4}=0.$

which is different from (5.1). Then using (5.1) and (5.2) to eliminate $t_{4}$
one obtains a nontrivial linear equation in $t_{1},t_{2}$ and $t_{3}$ which
obviously has at most $O(N^{2})$ solutions, after which $t_{4}$ is uniquely
defined.

Thus the total number of solutions in Case 1 is $O(N^{2})$.

Case 2. All three of $\omega_{1},\omega_{2},\omega_{3}$ are real, that is,
$\omega_{1},\omega_{2},\omega_{3}\in\\{-1,1\\}$, and the equation (5.1)
reduces to

(5.3) $t_{1}\pm t_{2}\pm t_{3}\pm t_{4}=0.$

We observe that Case 2 also covers the $2N^{2}+O(N)$ diagonal solutions.

To treat the non-diagonal solutions, one can now apply results of Besicovitch
[2], Mordell [17], Siegel [22], or the more recent results of Carr and
O’Sullivan [8]. For instance, [8, Theorem 1.1] shows that a set of real $k$-th
roots of integers that are pairwise linearly independent over the rationals
must also be linearly independent. Applying this to the set
$t_{1},t_{2},t_{3},t_{4}$, which by (5.3) is not linearly independent over
$\mathbb{Q}$, it follows that two of them, for example, $t_{1}$ and $t_{2}$,
are linearly dependent over $\mathbb{Q}$. We derive that there are positive
integers $a_{1},a_{2},b$ such that

$t_{1}^{k}=n_{1}=ba_{1}^{k}\qquad\mbox{and}\qquad t_{2}^{k}=n_{2}=ba_{2}^{k}.$

where $b$ is not divisible by a $k$-th power of a prime. That is, $a_{1}^{k}$
is the largest $k$-th power that divides $n_{1}$, and $a_{2}^{k}$ is the
largest $k$-th power that divides $n_{2}$.

Then letting $t_{5}$ denote the positive $k$-th root of $b$, the equation
(5.3) becomes

(5.4) $(a_{1}\pm a_{2})t_{5}\pm t_{3}\pm t_{4}=0.$

Without loss of generality, we can assume that $a_{1}\geqslant a_{2}$. Hence
for any fixed $1\leqslant a_{2}\leqslant a_{1}\leqslant N^{1/k}$ there are at
most $N/a_{1}^{k}$ possible values for $b$ and thus for $t_{5}$. After
$a_{1}$, $a_{2}$ and $t_{5}$ are fixed, there are obviously at most $N$ pairs
$(t_{3},t_{4})$ satisfying (5.4). Hence the total contribution from such
solutions is

$\sum_{1\leqslant a_{2}\leqslant a_{1}\leqslant
N^{1/k}}N^{2}/a_{1}^{k}\leqslant\sum_{1\leqslant a_{1}\leqslant
N^{1/k}}N^{2}/a_{1}^{k-1}\ll N^{2}$

which concludes the proof. ∎

We remark that the case of $k=2$ can also be included in Lemma 5.2 however
this case is already fully covered by the results of [20].

###  5.3. Concluding the proof

Clearly the congruence

$u+v\equiv x+y\bmod q,\qquad ju^{k},jv^{k},jx^{k},jy^{k}\in[1,N]$

implies that

$F_{k}(u^{k},v^{k},x^{k},y^{k})\equiv 0\bmod q$

for the above polynomial $F_{k}$. Since $F_{k}$ is homogenous this implies
that

$F_{k}(ju^{k},jv^{k},jx^{k},jy^{k})\equiv 0\bmod q.$

Since for a prime $q\sim Q$, $a\in\mathbb{F}_{q}$ and
$j\in\mathbb{F}_{q}^{*}$, there are at most $k$ solutions to the congruence
$jz^{k}\equiv a\bmod q$ in variable $z\in\mathbb{F}_{q}$, and thus at most
$2k$ solution in variable $z\in[1,N]$ (since $N\leqslant Q\leqslant 2q$) we
have

$\sum_{\begin{subarray}{c}q\sim Q\\\ q\leavevmode\nobreak\
\text{prime}\end{subarray}}\max_{j\in\mathbb{F}_{q}^{*}}\mathsf{E}_{k}(N;j,q)\leqslant
16k^{4}\sum_{\begin{subarray}{c}q\sim Q\\\ q\leavevmode\nobreak\
\text{prime}\end{subarray}}\,\mathop{\sum\ldots\sum}_{\begin{subarray}{c}U,V,X,Y\in[1,N]\\\
F_{k}(U,V,X,Y)\equiv 0\bmod q\end{subarray}}1.$

Changing the order of summation and separating the sum over the variables
$U,V,X,Y$ into two parts depending on whether $F(U,V,X,Y)=0$ or not, we derive

$\displaystyle\sum_{\begin{subarray}{c}q\sim Q\\\ q\leavevmode\nobreak\
\text{prime}\end{subarray}}$
$\displaystyle\max_{j\in\mathbb{F}_{q}^{*}}\mathsf{E}_{k}(N;j,q)\ll\mathop{\sum\ldots\sum}_{U,V,X,Y\in[1,N]}\,\sum_{\begin{subarray}{c}q\sim
Q\\\ q\leavevmode\nobreak\ \text{prime}\\\ q\mid
F_{k}(U,V,X,Y)\end{subarray}}1$ $\displaystyle\ll\frac{Q}{\log
Q}\mathop{\sum\ldots\sum}_{\begin{subarray}{c}U,V,X,Y\in[1,N]\\\
F_{k}(U,V,X,Y)=0\end{subarray}}1+\mathop{\sum\ldots\sum}_{\begin{subarray}{c}U,V,X,Y\in[1,N]\\\
F_{k}(U,V,X,Y)\neq 0\end{subarray}}\sum_{\begin{subarray}{c}q\sim Q\\\
q\leavevmode\nobreak\ \text{prime}\\\ q\mid F_{k}(U,V,X,Y)\end{subarray}}1.$

Recall that $F_{k}$ is a polynomial with constant coefficients of degree
$k^{3}$. Hence $F_{k}(U,V,X,Y)\ll N^{k^{3}}$, and thus trivially has at most
$O\left(\log N\right)$ prime divisors. Hence, we derive

$\sum_{\begin{subarray}{c}q\sim Q\\\ q\leavevmode\nobreak\
\text{prime}\end{subarray}}\max_{j\in\mathbb{F}_{q}^{*}}\mathsf{E}_{k}(N;j,q)\ll\frac{Q}{\log
Q}T_{k}(N)+N^{4+o(1)},$

and applying Lemma 5.2 we conclude the proof.

######  Remark 5.3.

Furthermore it is easy to see that there is a constant $C>0$ such that if
$N\leqslant q^{1/k^{3}}$ then $F_{k}(n_{1},n_{2},n_{3},n_{4})\equiv 0\bmod q$
with $1\leqslant n_{1},n_{2},n_{3},n_{4}\leqslant N$ implies
$F_{k}(n_{1},n_{2},n_{3},n_{4})=0$. Hence in this range of $N$, using Lemma
5.2, we obtain $\mathsf{E}_{k}(N;j,q)\ll N^{2}$ for every $q$.

##  6\. Proof of Theorem 1.4

###  6.1. Preliminary discussion

We need some facts about the Gowers norms, introduced in the celebrated work
of Gowers [12, 13] on the first quantitative bound for the famous Szemerédi
Theorem [23] about sets avoiding arithmetic progressions of length four and
longer. As an important step in the proof, Gowers [12, 13] observes that there
are very random sets having an unexpected number of arithmetic progressions of
length $l\geqslant 4$. An example is, basically, the set

(6.1) ${\mathcal{A}}^{(k)}=\left\\{x\in\mathbb{Z}_{N}:\leavevmode\nobreak\
x^{k}\in\\{1,\ldots,c_{k}N\\}\right\\}\,,$

where $c_{k}>0$ is an appropriate constant, depending on $k\geqslant 2$ only
(see the beginning of [13, Section 4] and also [14]). Then the set
${\mathcal{A}}^{(k)}$ has an enormous number of arithmetic progressions of
length $k+2$ but the expected number of shorter progressions. In Theorem 1.4
we consider the sets ${\mathcal{N}}^{1/k}$, where ${\mathcal{N}}$ is a set
with small doubling. Clearly, such sets generalise the construction (6.1).
Below we show that these sets are random in the sense, that they all have
small additive energy. Actually, we obtain a stronger property that Gowers
norms of its characteristic functions are small and thus this has even more
parallels to the Gowers construction (6.1). On the other hand, sets
${\mathcal{N}}^{1/k}$ preserve all essential combinatorial properties of the
sets ${\mathcal{A}}^{(k)}$. For example, for $k=2$ and any $s\neq 0$ we have
for an arbitrary $x\in{\mathcal{N}}^{1/2}\cap({\mathcal{N}}^{1/2}+s)$ that
$x\in({\mathcal{N}}-{\mathcal{N}}-s^{2})/2s$ and hence all intersections
${\mathcal{N}}^{1/2}\cap({\mathcal{N}}^{1/2}+s)$ are additively rich sets
exactly as in construction (6.1) (we literally use such facts in the proof of
Theorem 1.4 below).

###  6.2. Gowers norms

Now we are ready to give general definitions. Suppose that $G$ is an abelian
group with the group operation $+$ and ${\mathcal{A}}\subseteq G$ is a finite
set. Having a sequence of elements $s_{1},\ldots,s_{l}\in G$ we define the set

${\mathcal{A}}_{s_{1},\ldots,s_{l}}={\mathcal{A}}\cap({\mathcal{A}}-s_{1})\cap\ldots\cap({\mathcal{A}}-s_{l}).$

Let $\|{\mathcal{A}}\|_{\mathcal{U}^{k}}$ be the Gowers non-normalised $k$th-
norm [13] of the characteristic function of ${\mathcal{A}}$ (in additive
form). We have, see, for example, [19]:

$\|{\mathcal{A}}\|_{\mathcal{U}^{k}}=\sum_{x_{0},x_{1},\ldots,x_{k}\in
G}\,\prod_{\varepsilon\in\\{0,1\\}^{k}}{\mathcal{A}}\left(x_{0}+\sum_{j=1}^{k}\varepsilon_{j}x_{j}\right)\,,$

where $\varepsilon=(\varepsilon_{1},\ldots,\varepsilon_{k})$ (we also recall
that we use ${\mathcal{A}}(a)$ for the indicator function of ${\mathcal{A}}$).
In particular,

$\|{\mathcal{A}}\|_{\mathcal{U}^{2}}=\sum_{x_{0},x_{1},x_{2}\in
G}{\mathcal{A}}(x_{0}){\mathcal{A}}(x_{0}+x_{1}){\mathcal{A}}(x_{0}+x_{2}){\mathcal{A}}(x_{0}+x_{1}+x_{2})=E({\mathcal{A}})$

is the additive energy of ${\mathcal{A}}$, that is

$E({\mathcal{A}})=\\#\\{(a_{1},a_{2},a_{3},a_{4})\in{\mathcal{A}}^{4}:\leavevmode\nobreak\
a_{1}+a_{2}=a_{3}+a_{4}\\},$

and

$\|{\mathcal{A}}\|_{\mathcal{U}^{3}}=\sum_{s\in{\mathcal{A}}-{\mathcal{A}}}E({\mathcal{A}}_{s})\,.$

Moreover, the induction property for Gowers norms holds, see [13]

$\|{\mathcal{A}}\|_{\mathcal{U}^{k+1}}=\sum_{s\in{\mathcal{A}}-{\mathcal{A}}}\|{\mathcal{A}}_{s}\|_{\mathcal{U}^{k}}$

and

(6.2) $\|{\mathcal{A}}\|_{\mathcal{U}^{k}}=\sum_{s_{1},\ldots,s_{k}\in
G}\\#{\mathcal{A}}_{\pi(s_{1},\ldots,s_{k})}\,,$

where $\pi(s_{1},\ldots,s_{k})$ is a vector with $2^{k}$ components, namely,

$\pi(s_{1},\ldots,s_{k})=\left(\sum_{j=1}^{k}s_{j}\varepsilon_{j}\right)_{\left(\varepsilon_{1},\ldots,\varepsilon_{k}\right)\in\\{0,1\\}^{k}}\,.$

Notice also

(6.3) $\|{\mathcal{A}}\|_{\mathcal{U}^{k+1}}=\sum_{s_{1},\ldots,s_{k}\in
G}\left(\\#{\mathcal{A}}_{\pi(s_{1},\ldots,s_{k})}\right)^{2}\,.$

It is proved in [13] that $k$th–norms of the characteristic function of any
set are connected to each other. It is shown in [19] that the connection for
the non-normalised norms does not depend on size of the group $G$. Here we
formulate a particular case of [19, Proposition 35], which relates
$\|{\mathcal{A}}\|_{\mathcal{U}^{k}}$ and
$\|{\mathcal{A}}\|_{\mathcal{U}^{2}}$.

######  Lemma 6.1.

Let ${\mathcal{A}}$ be a finite subset of an abelian group $G$ with the group
operation $+$. Then for any integer $k\geqslant 1$, we have

$\|{\mathcal{A}}\|_{\mathcal{U}^{k+1}}\geqslant\frac{\|{\mathcal{A}}\|^{(3k-2)/(k-1)}_{\mathcal{U}^{k}}}{\|{\mathcal{A}}\|^{2k/(k-1)}_{\mathcal{U}^{k-1}}}\,.$

Next we have to relate $\|{\mathcal{A}}\|_{\mathcal{U}^{k}}$ and
$E({\mathcal{A}})$, see [19, Remark 36].

######  Lemma 6.2.

Let ${\mathcal{A}}$ be a finite subset of an abelian group $G$ with the group
operation $+$. Then for any integer $k\geqslant 1$, we have

$\|{\mathcal{A}}\|_{\mathcal{U}^{k}}\geqslant
E({\mathcal{A}})^{2^{k}-k-1}\left(\\#{\mathcal{A}}\right)^{-(3\cdot
2^{k}-4k-4)}\,.$

###  6.3. Concluding the proof

Let ${\mathcal{A}}={\mathcal{N}}^{1/k}$.

####  6.3.1. Case $k=3$

Let us start with the case $k=3$. Below we can assume that the quantity $L$ is
sufficiently small because otherwise the result is trivial.

For any $s\neq 0$ consider the set
${\mathcal{A}}_{s}={\mathcal{A}}\cap({\mathcal{A}}-s)$ and let
$x\in{\mathcal{A}}_{s}$. Then $x^{3},(x+s)^{3}\in{\mathcal{N}}$ and hence

$3s(x+s/2)^{2}-3s^{3}/4=3sx^{2}+3s^{2}x+s^{3}\in{\mathcal{N}}-{\mathcal{N}}\,.$

Put ${\mathcal{B}}_{s}={\mathcal{A}}_{s}+s/2$, so
$\\#{\mathcal{B}}_{s}=\\#{\mathcal{A}}_{s}$. Furthermore, let
${\mathcal{C}}_{s}=\\{x^{2}:\leavevmode\nobreak\ x\in{\mathcal{B}}_{s}\\}$.
Clearly, by the Plünnecke inequality, see [24, Corollary 6.29],

$\\#({\mathcal{C}}_{s}+{\mathcal{C}}_{s})\leqslant\\#(2{\mathcal{N}}-2{\mathcal{N}})\leqslant
L^{4}N=L_{s}\\#{\mathcal{A}}_{s}\,,$

where

$L_{s}=\frac{L^{4}N}{\\#{\mathcal{A}}_{s}}.$

Then, after that applying estimate (1.3) with our restriction $N\leqslant
q^{2/3}$, we obtain

(6.4) $\begin{split}E({\mathcal{A}}_{s})&=E({\mathcal{B}}_{s})\ll
E_{2}({\mathcal{C}}_{s};q)\\\
&\leqslant\left(L^{4}_{s}\left(\\#{\mathcal{A}}_{s}\right)^{4}/q+L^{2}_{s}\left(\\#{\mathcal{A}}_{s}\right)^{11/4}\right)q^{o(1)}\,.\end{split}$

We now assume that

(6.5) $\\#{\mathcal{A}}_{s}\geqslant N^{4/5}L^{32/5}.$

We also observe that we can always assume that $L\leqslant N^{1/32}$ as
otherwise the result is trivial. Further to show that that the second term in
(6.4) dominates the first one, we need to check that

(6.6) $L^{4}_{s}\left(\\#{\mathcal{A}}_{s}\right)^{4}/q\leqslant
L^{2}_{s}\left(\\#{\mathcal{A}}_{s}\right)^{11/4}$

or $L^{2}_{s}\left(\\#{\mathcal{A}}_{s}\right)^{5/4}\leqslant q$, which in
turn is equivalent to $\left(\\#{\mathcal{A}}_{s}\right)^{3}\geqslant
L^{32}N^{8}q^{-4}$. Since for $L\leqslant N^{1/32}$ and $N\leqslant q^{2/3}$
we have

$N^{12/5}L^{96/5}\geqslant L^{32}N^{8}q^{-4}$

we see that under the assumption (6.5) we have (6.6) and hence the bound (6.4)
becomes

(6.7) $E({\mathcal{A}}_{s})\leqslant
L^{2}_{s}\left(\\#{\mathcal{A}}_{s}\right)^{11/4}q^{o(1)}\leqslant
L^{8}N^{2}\left(\\#{\mathcal{A}}_{s}\right)^{3/4}q^{o(1)}\,.$

By the definition of the sets ${\mathcal{A}}_{s}$, we have

(6.8)
$\sum_{s\in{\mathcal{A}}-{\mathcal{A}}}\\#{\mathcal{A}}_{s}=\left(\\#{\mathcal{A}}\right)^{2}\,.$

Furthermore, using the definition of $\mathcal{U}_{3}$–norm we write

(6.9)
$\|{\mathcal{A}}\|_{\mathcal{U}^{3}}=\sum_{s\in{\mathcal{A}}-{\mathcal{A}}}E({\mathcal{A}}_{s})=\sum_{s:\,\\#{\mathcal{A}}_{s}\leqslant
T}E({\mathcal{A}}_{s})+\sum_{s:\,\\#{\mathcal{A}}_{s}>T}E({\mathcal{A}}_{s}).$

First we observe that

$\displaystyle\sum_{s:\,\\#{\mathcal{A}}_{s}\leqslant T}E({\mathcal{A}}_{s})$
$\displaystyle=\\#\\{(a_{1},a_{2},a_{3},a_{4},s)\in{\mathcal{A}}^{4}\times\left({\mathcal{A}}-{\mathcal{A}}\right):$
$\displaystyle\qquad\qquad\qquad a_{1}+a_{2}=a_{3}+a_{4},\
\\#{\mathcal{A}}_{s}\leqslant T,$ $\displaystyle\qquad\qquad\qquad\qquad\qquad
a_{i}-s\in{\mathcal{A}},\ i=1,\ldots,4\\}\,.$

Thus for each of $E({\mathcal{A}})$ choices
$(a_{1},a_{2},a_{3},a_{4},s)\in{\mathcal{A}}^{4}$, $a_{1}+a_{2}=a_{3}+a_{4}$
there are at most $T$ possibilities for $s$ with
$\\#{\mathcal{A}}_{s}\leqslant T$ and we derive

(6.10) $\sum_{s:\,\\#{\mathcal{A}}_{s}\leqslant
T}E({\mathcal{A}}_{s})\leqslant TE({\mathcal{A}})\,.$

We now choose

(6.11) $T=27E({\mathcal{A}})^{-4/5}L^{32/5}N^{16/5}$

and note that the trivial upper bound
$E({\mathcal{A}})\leqslant(\\#{\mathcal{A}})^{3}\leqslant 27N^{3}$ implies
that $T\geqslant N^{4/5}L^{32/5}$. Hence for any $s$ with
$\\#{\mathcal{A}}_{s}>T$ the condition (6.5) is satisfied and so the bound
(6.7) holds.

Hence, by identity (6.8), we obtain

(6.12)
$\begin{split}\sum_{s:\,\\#{\mathcal{A}}_{s}>T}E({\mathcal{A}}_{s})&\leqslant
L^{8}N^{2}q^{o(1)}\sum_{s:\,\\#{\mathcal{A}}_{s}>T}\left(\\#{\mathcal{A}}_{s}\right)^{3/4}\\\
&\leqslant
L^{8}N^{2}T^{-1/4}q^{o(1)}\sum_{s:\,\\#{\mathcal{A}}_{s}>T}\\#{\mathcal{A}}_{s}\\\
&\leqslant L^{8}N^{2}\cdot
N^{2}T^{-1/4}q^{o(1)}=L^{8}N^{4}T^{-1/4}q^{o(1)}\,.\end{split}$

The value of $T$ in (6.11) is chosen to balance the bounds (6.10) and (6.12)
and thus from (6.9) we derive

$\|{\mathcal{A}}\|_{\mathcal{U}^{3}}\leqslant
E({\mathcal{A}})^{1/5}L^{32/5}N^{16/5}q^{o(1)}\,.$

Finally, applying Lemma 6.2, we obtain

$E({\mathcal{A}})\leqslant
N^{2}\|{\mathcal{A}}\|^{1/4}_{\mathcal{U}^{3}}\leqslant
L^{8/5}N^{14/5}E({\mathcal{A}})^{1/20}q^{o(1)}\,,$

and whence

$E({\mathcal{A}})\leqslant L^{32/19}N^{56/19}q^{o(1)}\,,$

which gives the desired result for $k=3$.

####  6.3.2. Case $k=4$

Next we consider the case $k=4$. Let

${\mathcal{A}}_{s,t}={\mathcal{A}}\cap({\mathcal{A}}-s)\cap({\mathcal{A}}-t)\cap({\mathcal{A}}-s-t)$

and let $x\in{\mathcal{A}}_{s,t}$. Then
$x^{4},(x+s)^{4},(x+t)^{4},(x+t+s)^{4}\in{\mathcal{N}}$ and hence
${\mathcal{N}}-{\mathcal{N}}$ contains

$3ux^{3}+6u^{2}x^{2}+3u^{3}x+u^{4},\qquad u\in\\{s,t,s+t\\}.$

Subtracting the expressions with $s$ and $t$ from the expression with $s+t$,
we see that $3{\mathcal{N}}-3{\mathcal{N}}$ contains
$12stx^{2}+9(t^{2}s+ts^{2})x+(t+s)^{4}-s^{4}-t^{4}$ and we can apply a version
of previous arguments. In particular, since by the Plünnecke inequality, see
[24, Corollary 6.29],

$\\#(3{\mathcal{N}}-3{\mathcal{N}})\leqslant L^{6}N$

the role of $L_{s}$ is now played by

$L_{s,t}=\frac{L^{6}N}{\\#{\mathcal{A}}_{s,t}}.$

We also set

$T=(E({\mathcal{A}})N^{2}L^{12}\|{\mathcal{A}}\|_{\mathcal{U}^{3}}^{-1})^{4/5}$

and note that we have the trivial bound
$\|{\mathcal{A}}\|_{\mathcal{U}^{3}}\leqslant NE({\mathcal{A}})$. We also have

$T\geqslant N^{4/5}L^{48/5}.$

We now verify that $T^{3}\geqslant L^{48}N^{8}q^{-4}$ or

$N^{12/5}L^{144/5}\geqslant L^{48}N^{8}q^{-4}$

which is equivalent to $N^{28}L^{96}\leqslant q^{20}$. Since we can clearly
assume that $L\leqslant N^{1/48}$ as otherwise the result is trivial, the last
inequality hold under our assumption $N\leqslant q^{2/3}$.

Hence, similar to the case $k=3$ after simple calculations, one verifies that
for $\\#{\mathcal{A}}_{s,t}>T$, we have
$L_{s,t}^{2}\left(\\#{\mathcal{A}}_{s,t}\right)^{5/4}\leqslant q$ which in
turn is equivalent to

$\left(\\#{\mathcal{A}}_{s,t}\right)^{3}\geqslant T^{3}\geqslant
L^{48}N^{8}q^{-4}.$

Hence, by (1.3) we have

$\displaystyle E({\mathcal{A}}_{s,t})$
$\displaystyle\leqslant\left(L^{4}_{s,t}\left(\\#{\mathcal{A}}_{s,t}\right)^{4}/q+L^{2}_{s,t}\left(\\#{\mathcal{A}}_{s,t}\right)^{11/4}\right)q^{o(1)}$
$\displaystyle\leqslant
q^{o(1)}L^{12}N^{2}\left(\\#{\mathcal{A}}_{s,t}\right)^{3/4}.$

Using (6.2) and (6.3) and the arguments as above, we get

(6.13)
$\begin{split}\|{\mathcal{A}}\|_{\mathcal{U}^{4}}&=\sum_{s,t}E({\mathcal{A}}_{s,t})\\\
&\leqslant
T\|{\mathcal{A}}\|_{\mathcal{U}^{3}}+L^{12}N^{2}q^{o(1)}\sum_{(s,t):\,\\#{\mathcal{A}}_{s,t}>T}\\#({\mathcal{A}}_{s,t})^{3/4}\\\
&\leqslant
T\|{\mathcal{A}}\|_{\mathcal{U}^{3}}+L^{12}N^{2}E({\mathcal{A}})T^{-1/4}q^{o(1)}\\\
&\leqslant
L^{48}N^{8/5}E^{4/5}({\mathcal{A}})\|{\mathcal{A}}\|^{1/5}_{\mathcal{U}^{3}}q^{o(1)}\,\end{split}$

since again we have chosen $T$ to optimise the above bound.

On the other hand, applying Lemma 6.1 and then Lemma 6.2, we derive

(6.14)
$\|{\mathcal{A}}\|_{\mathcal{U}^{4}}\geqslant\frac{\|{\mathcal{A}}\|^{7/2}_{\mathcal{U}^{3}}}{\|{\mathcal{A}}\|_{\mathcal{U}^{2}}^{3}}=\frac{\|{\mathcal{A}}\|^{7/2}_{\mathcal{U}^{3}}}{E^{3}({\mathcal{A}})}\geqslant\|{\mathcal{A}}\|^{1/5}_{\mathcal{U}^{3}}\cdot\frac{E^{51/5}({\mathcal{A}})}{N^{132/5}}.$

Comparing (6.13) and (6.14)

$E({\mathcal{A}})\leqslant L^{48/47}N^{3-1/47}q^{o(1)}\,,$

which gives the desired result for $k=4$.

####  6.3.3. Case $k\geqslant 5$

Finally, consider the general case, which we treat with a version of Weyl
differencing. Now

${\mathcal{A}}_{\mathbf{s}}={\mathcal{A}}_{s_{1},\ldots,s_{k-2}}={\mathcal{A}}_{\pi(s_{1},\ldots,s_{k-2})}$

and let $x\in{\mathcal{A}}_{s_{1},\ldots,s_{k-2}}$. Indeed, we start with
${\mathcal{A}}_{s_{1}}$ and reduce the main term in
$x^{k},(x+s_{1})^{k}\in{\mathcal{N}}$ deriving that
$p_{k-1}(x)\in{\mathcal{N}}-{\mathcal{N}}$, where $\deg p_{k-1}=k-1$. After
that consider
$({\mathcal{A}}_{s_{1}})_{s_{2}}={\mathcal{A}}_{\pi(s_{1},s_{2})}$ and reduce
degree of the polynomial by one, and so on. We also note that by the Plünnecke
inequality, see [24, Corollary 6.29],

$\\#\left(2^{k-1}{\mathcal{N}}-2^{k-1}{\mathcal{N}}\right)\leqslant
L^{2^{k}}N$

the role of $L_{s}$ or $L_{s,t}$ is now played by

$L_{\mathbf{s}}=\frac{L^{2^{k}}N}{\\#{\mathcal{A}}_{\mathbf{s}}}.$

We now set

$T=\left(N^{2}L^{12}\|{\mathcal{A}}\|_{\mathcal{U}^{k-2}}\|{\mathcal{A}}\|_{\mathcal{U}^{k-1}}^{-1}\right)^{4/5}.$

Using the same arguments as above, after somewhat tedious calculations to
verify all necessary conditions such as

(6.15)
$N^{8}L^{2^{k+2}}q^{-4}\leqslant\left(\\#{\mathcal{A}}_{s_{1},\ldots,s_{k-2}}\right)^{3}$

to obtain

$E({\mathcal{A}}_{s_{1},\ldots,s_{k-2}})\leqslant
L^{2^{k}}N^{2}\left(\\#{\mathcal{A}}_{s_{1},\ldots,s_{k-2}}\right)^{3/4}q^{o(1)}.$

In particular to check (6.15) we note that for the above choice of $T$ we have

$T\geqslant N^{4/5}L^{2^{k+2}/5},$

and then derive

$N^{8}L^{2^{k+2}}q^{-4}\leqslant N^{12/5}L^{3\cdot 2^{k+2}/5}\leqslant T^{3}$

which is true because $N\leqslant q^{2/3}$ and $L\leqslant N^{1/2^{k+2}}$
(which we can assume as otherwise the bound is trivial).

Using the formula (6.2) and (6.3) we obtain

$\displaystyle\|{\mathcal{A}}\|_{\mathcal{U}^{k}}$ $\displaystyle\leqslant
T\|{\mathcal{A}}\|_{\mathcal{U}^{k-1}}+L^{2^{k}}N^{2}q^{o(1)}\sum_{\mathbf{s}:\,\\#{\mathcal{A}}_{\mathbf{s}}>T}\\#({\mathcal{A}}_{\mathbf{s}})^{3/4}$
$\displaystyle\leqslant
T\|{\mathcal{A}}\|_{\mathcal{U}^{k-1}}+L^{2^{k}}N^{2}\|{\mathcal{A}}\|_{\mathcal{U}^{k-2}}T^{-1/4}q^{o(1)}$
$\displaystyle\leqslant L^{2^{k}\cdot
4/5}N^{8/5}\|{\mathcal{A}}\|^{4/5}_{\mathcal{U}^{k-2}}\|{\mathcal{A}}\|^{1/5}_{\mathcal{U}^{k-1}}q^{o(1)}$

and hence by induction and Lemma 6.2

$E({\mathcal{A}})^{7\cdot 2^{k-1}-9}\leqslant L^{2^{k+2}}N^{21\cdot
2^{k-1}-28}q^{o(1)}.$

In other words,

$E({\mathcal{A}})\leqslant L^{2^{k+2}/(7\cdot 2^{k-1}-9)}N^{3-1/(7\cdot
2^{k-1}-9)}q^{o(1)}\,,$

which completes the proof.

##  7\. Proof of Theorem 2.2

Define

(7.1) $f_{m}(n)=\sum_{\begin{subarray}{c}x\in\mathbb{F}_{q}\\\
x^{2}=amn\end{subarray}}e_{q}(hx),$

so that

$V_{a,q}(\bm{\alpha},\varphi;h,M,N)=\sum_{m\sim
M}\alpha_{m}\sum_{n\in\mathbb{Z}}\varphi(n)f_{m}(n).$

Recall that $\varphi$ satisfies (2.2).

Applying Poisson summation to the sum over $n$ gives

(7.2) $V_{a,q}(\bm{\alpha},\varphi;h,M,N)\sim\frac{N}{q^{1/2}}\sum_{m\sim
M}\alpha_{m}\sum_{n\in\mathbb{Z}}\widehat{\varphi}\left(-\frac{n}{q}\right)\widehat{f}_{m}(n),$

where

$\widehat{f}_{m}(n)=\frac{1}{q^{1/2}}\sum_{\lambda\in\mathbb{F}_{q}}f_{m}(\lambda)e_{q}(\lambda
n).$

Using (7.1) and interchanging summation

$\displaystyle\widehat{f}_{m}(n)$
$\displaystyle=\frac{1}{q^{1/2}}\sum_{x\in\mathbb{F}_{q}}\sum_{\begin{subarray}{c}\lambda\in\mathbb{F}_{q}\\\
x^{2}=am\lambda\end{subarray}}e_{q}(hx)e_{q}(\lambda n)$
$\displaystyle=\frac{1}{q^{1/2}}\sum_{x\in\mathbb{F}_{q}}e_{q}(hx)e_{q}(\overline{am}nx^{2}+hx),$

where $\overline{am}$ denotes multiplicative inverse modulo $q$. Summation
over $x$ is a quadratic Gauss sum which has evaluation, see [4, Theorem 1.52]

$\widehat{f}_{m}(n)=\varepsilon_{q}\chi(amn)e_{q}(-am\overline{4n}h^{2}),$

for some $|\varepsilon_{q}|=1$, where $\chi$ is the quadratic character mod
$q$. Therefore, there exists some $(c,q)=1$ depending on $a,h$ such that

$\widehat{f}_{m}(n)=\varepsilon_{q}\chi(amn)e_{q}(cm\overline{n}).$

Substituting into (7.2) and applying the triangle inequality

$\left|V_{a,q}(\bm{\alpha},\varphi;h,M,N)\right|\ll\frac{1}{q^{1/2}}\sum_{m\sim
M}\left|\sum_{n\in\mathbb{Z}}\widehat{\varphi}\left(-\frac{n}{q}\right)\chi(n)e_{q}(cm\overline{n})\right|.$

Define

(7.3) $U=\frac{q}{MN},$

so by assumption on $M,N$ we have $U\gg 1$. For fixed $m\sim M$ apply shifts
$n\rightarrow n+um$ to the inner summation over $n$. Averaging this over
$1\leqslant u\leqslant U$ gives

$\displaystyle V_{a,q}(\bm{\alpha},\varphi;h,M,N)$
$\displaystyle\qquad\ll\frac{1}{q^{1/2}N}\sum_{m\sim M}\sum_{n\in\mathbb{Z}}$
$\displaystyle\qquad\qquad\qquad\quad\left|\sum_{1\leqslant u\leqslant
U}\widehat{\varphi}\left(-\frac{n+mu}{q}\right)\chi(n+mu)e_{q}(cm(\overline{n+mu}))\right|.$

Let $\varepsilon>0$ be small. Note by (2.2) and partial integration, for any
$m\sim M$, $1\leqslant u\leqslant U$ and constant $C>0$ we have

$\widehat{\varphi}\left(-\frac{n+mu}{q}\right)\ll\frac{1}{n^{C}},\quad\text{provided}\quad
n\geqslant\frac{q^{1+\varepsilon}}{N}.$

Therefore

$\displaystyle V_{a,q}(\bm{\alpha},\varphi;h,M,N)$
$\displaystyle\qquad\ll\frac{1}{q^{1/2}N}\sum_{m\sim M}\sum_{|n|\leqslant
q^{1+\varepsilon}/N}$
$\displaystyle\qquad\qquad\qquad\quad\left|\sum_{1\leqslant u\leqslant
U}\widehat{\varphi}\left(-\frac{n+mu}{q}\right)\chi(n+mu)e_{q}(cm(\overline{n+mu}))\right|.$

Applying partial summation to $u$ and using

$\frac{\partial\varphi\left(-\frac{n+mu}{q}\right)}{\partial
u}\ll\frac{N}{|u|},$

we obtain

$\displaystyle V_{a,q}(\bm{\alpha},\varphi;h,M,N)$
$\displaystyle\ll\frac{N^{1+o(1)}}{q^{1/2}U}\sum_{m\sim M}$
$\displaystyle\qquad\quad\sum_{\begin{subarray}{c}|n|\leqslant
q^{1+\varepsilon}/N\end{subarray}}\left|\sum_{1\leqslant u\leqslant
U_{0}}\chi(n\overline{m}+u)e_{q}(c\overline{(n\overline{m}+u)})\right|,$

for some $U_{0}\leqslant U$. Let $I(\lambda)$ count the number of solutions to

$\lambda\equiv nm^{-1}\bmod{q},\quad|n|\leqslant\frac{q^{1+o(1)}}{N},\quad
m\sim M,$

so that

(7.4) $\begin{split}&V_{a,q}(\bm{\alpha},\varphi;h,M,N)\\\
&\qquad\quad\leqslant\frac{N^{1+o(1)}}{q^{1/2}U}\sum_{\lambda\in\mathbb{F}_{q}}I(\lambda)\left|\sum_{1\leqslant
u\leqslant
U_{0}}\chi(\lambda+u)e_{q}(c\overline{(\lambda+u)})\right|.\end{split}$

Note

(7.5) $\sum_{\lambda\in\mathbb{F}_{q}}I(\lambda)\ll\frac{qM}{N},$

and

$\displaystyle\sum_{\lambda\in\mathbb{F}_{q}}I(\lambda)^{2}=\\#\\{(m_{1},m_{2},n_{1},n_{2})$
$\displaystyle\in\mathbb{Z}^{4}:\leavevmode\nobreak\ n_{1}m_{2}\equiv
n_{2}m_{2}\bmod{q},$
$\displaystyle|n_{1}|,|n_{2}|\leqslant\frac{q^{1+\varepsilon}}{N},\
m_{1},m_{2}\sim M\\}.$

It is known (see, for example, [1]) that

$\sum_{\lambda\in\mathbb{F}_{q}}I(\lambda)^{2}\leqslant
q^{2\varepsilon+o(1)}\left(\frac{1}{q}\left(\frac{qM}{N}\right)^{2}+\frac{qM}{N}+M^{2}\right),$

and by assumptions on $M,N$ the above simplifies to

(7.6)
$\sum_{\lambda\in\mathbb{F}_{q}}I(\lambda)^{2}\ll\frac{q^{1+2\varepsilon}M}{N}.$

Applying the Hölder inequality to summation in (7.4) gives

$\displaystyle V_{a,q}(\bm{\alpha},\varphi;h,M,N)^{2r}$
$\displaystyle\ll\frac{N^{2r+o(1)}}{q^{r}U^{2r}}\left(\sum_{\lambda\in\mathbb{F}_{q}}I(\lambda)\right)^{2r-2}\left(\sum_{\lambda\in\mathbb{F}_{q}}I(\lambda)^{2}\right)$
$\displaystyle\qquad\qquad\times\sum_{\lambda\in\mathbb{F}_{q}}\left|\sum_{1\leqslant
u\leqslant U_{0}}\chi(\lambda+u)e_{q}(c\overline{(\lambda+u)})\right|^{2r}.$

Using (7.5) and (7.6)

$\displaystyle V_{a,q}(\bm{\alpha},\varphi;h,M,N)^{2r}$
$\displaystyle\quad\quad\leqslant
q^{r-1+4r\varepsilon+o(1)}NM^{2r-1}\frac{1}{U^{2r}}\sum_{\lambda\in\mathbb{F}_{q}}\left|\sum_{1\leqslant
u\leqslant U_{0}}\chi(\lambda+u)e_{q}(c\overline{(\lambda+u)})\right|^{2r}.$

Expanding the $2r$-th power, interchanging summation, isolating the diagonal
contribution and using the Weil bound gives

$\sum_{\lambda\in\mathbb{F}_{q}}\left|\sum_{1\leqslant u\leqslant
U_{0}}\chi(\lambda+u)e_{q}(c\overline{(\lambda+u)})\right|^{2r}\ll
q^{1/2}U^{2r}+qU^{2r}.$

Using in the above and recalling (7.3), we get

$\displaystyle V_{a,q}(\bm{\alpha},\varphi;h,M,N)^{2r}$ $\displaystyle\ll
q^{r-1+4r\varepsilon+o(1)}NM^{2r-1}\left(q^{1/2}+\frac{q}{U^{r}}\right)$
$\displaystyle\ll
q^{r-1/2+4r\varepsilon+o(1)}NM^{2r-1}\left(1+\frac{(MN)^{r}}{q^{r-1/2}}\right),$

from which the result follows after taking $\varepsilon$ sufficiently small.

##  8\. Proof of Theorem 2.3

###  8.1. Preliminaries

Our argument follows the proof of [10, Theorem 1.10], the only difference
being our use of Corollary 2.1 and Theorem 2.2. We refer the reader to [10,
Section 7] for more complete details.

Let $\widetilde{S}_{q}(h,P)$ denote the sum

$\widetilde{S}_{q}(h,P)=\sum_{k=1}^{P}\Lambda(k)\sum_{\begin{subarray}{c}x\in\mathbb{F}_{q}\\\
x^{2}=k\end{subarray}}{\mathbf{\,e}}_{q}(hx).$

By partial summation, it is sufficient to show

$\widetilde{S}_{q}(h,P)\ll
q^{o(1)}(P^{15/16}+q^{1/8}P^{3/4}+q^{1/16}P^{69/80}+q^{13/88}P^{3/4}).$

Let $J\geqslant 1$ be an integer. Using the Heath-Brown identity and a smooth
partition of unity as in [10, Section 1.7], there exists some

$\mathbf{V}=(M_{1},\ldots,M_{J},N_{1},\ldots,N_{J})\in[1/2,2P]^{2J}$

$2J$-tuple of parameters satisfying

$N_{1}\geqslant\ldots\geqslant N_{J},\quad M_{1},\ldots,M_{J}\leqslant
P^{1/J},\quad P\ll Q\ll P,$

(implied constants are allowed to depend on $J$),

(8.1) $Q=\prod_{i=1}^{J}M_{i}\prod_{j=1}^{J}N_{j},$

and

  * •

the arithmetic functions $m_{i}\mapsto\gamma_{i}(m_{i})$ are bounded and
supported in $[M_{i}/2,2M_{i}]$;

  * •

the smooth functions $x_{i}\mapsto V_{i}(x)$ have support in $[1/2,2]$ and
satisfy

$V^{(j)}(x)\ll q^{j\varepsilon}$

for all integers $j\geqslant 0$, where the implied constant may depend on $j$
and $\varepsilon$.

such that defining

$\displaystyle\Sigma(\mathbf{V})=\sum_{m_{1},\ldots,m_{J}=1}^{\infty}$
$\displaystyle\gamma_{1}(m_{1})\cdots\gamma_{J}(m_{J})\sum_{n_{1},\ldots,n_{J}=1}^{\infty}$
$\displaystyle V_{1}\left(\frac{n_{1}}{N_{1}}\right)\cdots
V_{J}\left(\frac{n_{J}}{N_{J}}\right)\sum_{\begin{subarray}{c}x\in\mathbb{F}_{q}\\\
x^{2}=m_{1}\cdots m_{J}n_{1}\cdots n_{J}\end{subarray}}\mathbf{e}_{q}(hx),$

we have

$\widetilde{S}_{q}(h,P)\ll P^{o(1)}\Sigma(\mathbf{V}).$

We proceed on a case by case basis depending on the size of $N_{1}$. We first
note a general estimate for the multilinear sums. Let
${\mathcal{I}},{\mathcal{J}}\subseteq\\{1,\ldots,J\\}$ and write

$M=\prod_{i\in{\mathcal{I}}}M_{i}\prod_{j\in{\mathcal{J}}}N_{j},\quad N=Q/M.$

Grouping variables in $\Sigma(\mathbf{V})$ according to
${\mathcal{I}},{\mathcal{J}}$, there exists $\alpha,\beta$ satisfying

$\|\alpha\|_{\infty},\|\beta\|_{\infty}=Q^{o(1)},$

such that

$\Sigma(\mathbf{V})=\sum_{\begin{subarray}{c}m\leqslant 2^{J}M\\\ n\leqslant
2^{J}N\end{subarray}}\alpha(m)\beta(n)\sum_{\begin{subarray}{c}x\in\mathbb{F}_{q}\\\
x^{2}=mn\end{subarray}}e_{q}(hx).$

By Corollary 2.1

(8.2) $\begin{split}&\Sigma(\mathbf{V})\\\ &\quad\leqslant
q^{1/8+o(1)}P^{3/4}\left(\frac{P^{3/16}}{q^{1/16}M^{3/16}}+1\right)\left(\frac{M^{3/16}}{q^{1/16}}+1\right)\\\
&\quad\leqslant
q^{o(1)}\left(P^{15/16}+\frac{q^{1/16}P^{15/16}}{M^{3/16}}+q^{1/16}P^{3/4}M^{3/16}+q^{1/8}P^{3/4}\right).\end{split}$

We proceed on a case by case basis depending on the size of $N_{1}$. Let
$P^{1/2}\geqslant H\geqslant P^{\varepsilon}$ be some paramters and take

$J=\left\lceil\log P/\log H\right\rceil.$

###  8.2. Small $N_{1}$

Suppose first $N_{1}\leqslant H$ then arguing as in [10, Equation (7.13)] we
can choose two arbitrary sets
${\mathcal{I}},{\mathcal{J}}\subseteq\\{1,\ldots,J\\}$ such that for

$M=\prod_{i\in{\mathcal{I}}}M_{i}\prod_{j\in{\mathcal{J}}}N_{j}\qquad\mbox{and}\qquad
N=Q/M,$

where $Q$ is given by (8.1) and we have

(8.3) $P^{1/2}\ll M\ll H^{1/2}P^{1/2}.$

Hence by (LABEL:eq:Swigma4)

(8.4) $\Sigma(\mathbf{V})\leqslant
q^{o(1)}\left(P^{15/16}+q^{1/16}P^{27/32}H^{3/32}+q^{1/8}P^{3/4}\right).$

###  8.3. Medium $N_{1}$

Let $L$ be a parameter satisfying $H\leqslant L$ and suppose next that

$H\leqslant N_{1}\leqslant L.$

We may also suppose

$H\leqslant N_{2}\leqslant N_{1}\leqslant L,$

as otherwise we may argue before to obtain the bound (8.4). In this case we
define $M,N$ as

$N=\prod_{i=1}^{J}\prod_{j=3}^{J}N_{j}\quad\text{and}\quad M=N_{1}N_{2},$

so that

$H^{2}\leqslant M\leqslant L^{2}.$

By (LABEL:eq:Swigma4)

(8.5) $\begin{split}\Sigma(\mathbf{V})\leqslant
q^{o(1)}\biggl{(}P^{15/16}&+\frac{q^{1/16}P^{15/16}}{H^{3/8}}\\\
&\quad+q^{1/16}P^{3/4}L^{3/8}+q^{1/8}P^{3/4}\biggr{)}.\end{split}$

###  8.4. Large $N_{1}$

Let $R$ be a paramter to be chosen later and satisfying $R\geqslant P^{1/2}$.
Suppose next that

$L^{2}\leqslant N_{1}\leqslant R.$

Taking $M=N_{1}$ as above, we derive from (LABEL:eq:Swigma4)

(8.6) $\begin{split}\Sigma(\mathbf{V})\leqslant
q^{o(1)}\biggl{(}P^{15/16}&+\frac{q^{1/16}P^{15/16}}{L^{3/8}}\\\
&\quad+q^{1/16}P^{3/4}R^{3/16}+q^{1/8}P^{3/4}\biggr{)}.\end{split}$

###  8.5. Very large $N_{1}$

Finally consider when $N_{1}\geqslant R$. Applying Theorem 2.2 with $r=2$, and
using the assumptions $P\leqslant q^{3/4}$ and $R\geqslant P^{1/2}$ we obtain

(8.7) $\Sigma(\mathbf{V})\leqslant q^{3/8+o(1)}\frac{P^{3/4}}{R^{1/2}}.$

###  8.6. Optimiziation

Combining all previous bounds (8.4), (8.5), (8.6) and (8.7) results in

$\displaystyle\widetilde{S}_{q}(h,P)$ $\displaystyle\leqslant
q^{o(1)}(P^{15/16}+q^{1/8}P^{3/4})$
$\displaystyle\qquad\qquad+q^{o(1)}\left(q^{1/16}P^{27/32}H^{3/32}+\frac{q^{1/16}P^{15/16}}{H^{3/8}}\right)$
$\displaystyle\qquad\qquad\qquad+q^{o(1)}\left(q^{1/16}P^{3/4}L^{3/8}+\frac{q^{1/16}P^{15/16}}{L^{3/8}}\right)$
$\displaystyle\qquad\qquad\qquad\qquad+q^{o(1)}\left(q^{1/16}P^{3/4}R^{3/16}+q^{3/8+o(1)}\frac{P^{3/4}}{R^{1/2}}\right).$

Taking parameters

$H=P^{1/5},\quad L=P^{1/4},\quad R=q^{5/11},$

gives

$\widetilde{S}_{q}(h,P)\leqslant
q^{o(1)}(P^{15/16}+q^{1/8}P^{3/4}+q^{1/16}P^{69/80}+q^{13/88}P^{3/4}),$

which completes the proof.

## Acknowledgement

The authors would like to thank Alexander Dunn for some useful discussions and
in particular for pointing out the paper of Duke [9] regarding
multidimensional Sailé sums.

During the preparation of this work, B.K. was supported by the Academy of
Finland Grant 319180 and is currently supported by the Max Planck Institute
for Mathematics, I.D.S. by the Ministry of Education and Science of the
Russian Federation in the framework of MegaGrant 075-15-2019-1926 and I.E.S.
by the Australian Research Council Grant DP170100786.

## References

  * [1] A. Ayyad, T. Cochrane and Z. Zheng, ‘The congruence $x_{1}x_{2}\equiv x_{3}x_{4}\pmod{p}$, the equation $x_{1}x_{2}=x_{3}x_{4}$ and mean values of character sums’, J. Number Theory, 59 (1996), 398–413.
  * [2] A. S. Besicovitch, ‘On the linear independence of fractional powers of integers’, J. London Math. Soc., 15 (1940), 3–6.
  * [3] U. Betke, M. Henk and J. M. Wills, ‘Successive-minima-type inequalities’, Discr. Comput. Geom., 9 (1993), 165–175.
  * [4] B. C. Berndt, R. J. Evans and K. S. Williams, Gauss and Jacobi Sums, John Wiley, New York, 1998.
  * [5] M. Bordignon and B. Kerr, ‘An explicit Pólya-Vinogradov inequality via partial Gaussian sums’, Trans. Amer. Math. Soc., 373 (2020), 6503–6527.
  * [6] J. Bourgain, M. Z. Garaev, S. V. Konyagin and I. E. Shparlinski, ‘On congruences with products of variables from short intervals and applications’, Proc. Steklov Math. Inst., 280 (2013), 67–96.
  * [7] J. W. S. Cassels An Introduction to the geometry of numbers, Springer, Berlin, 1971.
  * [8] R. Carr and C. O’Sullivan, ‘On the linear independence of roots’, Int. J. Number Theory, 5 (2009), 161–171.
  * [9] W. Duke, ‘On multiple Salié sums’, Proc. Amer. Math. Soc., 114 (1992), 623–625.
  * [10] A. Dunn, B. Kerr, I. E. Shparlinski and A. Zaharescu, ‘Bilinear forms in Weyl sums for modular square roots and applications’, Adv. Math. 375 (2020), Art.107369.
  * [11] A. Dunn and A. Zaharescu, ‘The twisted second moment of modular half integral weight $L$-functions’, Preprint, 2019 (available from http://arxiv.org/abs/1903.03416).
  * [12] W. T. Gowers, ‘A new proof of Szemerédi’s theorem for arithmetic progressions of length four’, Geom. Funct. Anal., 8 (1998), 529–551.
  * [13] W. T. Gowers, ‘A new proof of Szemerédi’s theorem’, Geom. Funct. Anal., 11 (2001), 465–588.
  * [14] W. T. Gowers, ‘A uniform set with fewer than expected arithmetic progressions of length 4’, Preprint, 2020 (available from http://arxiv.org/abs/2004.07598).
  * [15] H. Iwaniec and E. Kowalski, Analytic number theory, Amer. Math. Soc., Providence, RI, 2004.
  * [16] K. Mahler, Ein Übertragungsprinzip für konvexe Körper, Math. Časopis, 68 (1939), 93–102.
  * [17] J. L. Mordell, ‘On the linear independence of algebraic numbers’, Pacific J. Math., 3 (1953), 625–630.
  * [18] P. Sarnak, Some applications of modular forms, Cambridge Tracts in Math., vol. 99, Cambridge Univ. Press, Cambridge, 1990.
  * [19] I. D. Shkredov, ‘Energies and structure of additive sets’, Electronic J. Combin., 21 (2014), #P3.44, 1–53.
  * [20] I. D. Shkredov, I. E. Shparlinski and A. Zaharescu, ‘Bilinear forms with modular square roots and averages of twisted second moments of half integral weight $L$-functions’, Preprint, 2019.
  * [21] I. D. Shkredov, I. E. Shparlinski and A. Zaharescu, ‘On the distribution of modular square roots of primes’, Preprint, 2020 (available from http://arxiv.org/abs/2009.03460).
  * [22] C. L. Siegel, ‘Algebraische Abhängigkeit von Wurzeln’, Acta Arith., 21 (1972) 59–64.
  * [23] E. Szemerédi, ‘On sets of integers containing no four elements in arithmetic progression’, Acta Math. Acad. Sci. Hungar., 20 (1969), 89–104.
  * [24] T. Tao and V. Vu, Additive Combinatorics, Cambridge, Stud. Adv. Math. 105, Cambridge Univ. Press, Cambridge, 2006.