1 Introduction
Let
$p,n,k$
be positive integers with
$p$
a prime,
$a_{i}$
be integers where
$p\nmid a_{i}$
,
$1\leqslant i\leqslant n$
, and
$c$
be any integer. Our interest here is in obtaining small solutions to the diagonal congruence
$$\begin{eqnarray}a_{1}x_{1}^{k}+a_{2}x_{2}^{k}+\cdots +a_{n}x_{n}^{k}\equiv c\hspace{0.6em}({\rm mod}\hspace{0.2em}p).\end{eqnarray}$$
In general, the best one can hope for is a solution with all
$|x_{i}|\ll p^{1/k}$
; consider for example the congruence
$x_{1}^{k}+\cdots +x_{n}^{k}\equiv (p-1)/2~(\text{mod}\,p)$
. The best results available until now yield solutions with
$|x_{i}|\ll _{k,\unicode[STIX]{x1D700}}p^{1/k+\unicode[STIX]{x1D6FF}_{k}(n)+\unicode[STIX]{x1D700}}$
, for some positive constant
$\unicode[STIX]{x1D6FF}_{k}(n)$
satisfying
$\unicode[STIX]{x1D6FF}_{k}(n)\rightarrow 0$
as
$n\rightarrow \infty$
. Here we obtain the best possible result for arbitrary
$k$
, with a relatively small number of variables.
Theorem 1.1. For any positive integer
$k$
, positive integer
$n\geqslant \frac{3}{2}(k^{2}+k+2)$
, prime
$p$
, and integers
$c,a_{i}$
with
$p\nmid a_{i}$
,
$1\leqslant i\leqslant n$
, there exists a solution of (1.1) with
$1\leqslant {x_{i}\ll }_{k}p^{1/k}$
,
$1\leqslant i\leqslant n$
.
In fact, for
$n\geqslant \frac{3}{2}(k^{2}+k+2)$
we obtain the existence of a solution of (1.1) in any cube of the type
$$\begin{eqnarray}{\mathcal{B}}:=\{\text{}\underline{x}\in \mathbb{Z}^{n}:c_{i}+1\leqslant x_{i}\leqslant c_{i}+B,1\leqslant i\leqslant n\},\end{eqnarray}$$
$B,c_{i}\in \mathbb{Z}$
,
$1\leqslant i\leqslant n$
,
$1\leqslant B\leqslant p$
, provided that
$B\gg _{k}p^{1/k}$
and that for at least
$\frac{1}{2}(k^{2}+k+2)$
choices of
$i$
, we have
${c_{i}\ll }_{k}1$
; see Remark 8.1. The constraint
$n\geqslant \frac{3}{2}(k^{2}+k+2)$
in the theorem is certainly not best possible. In fact, it is reasonable to believe that the conclusion of the theorem holds for
$n\geqslant Ck$
, for some absolute constant
$C$
.
With fewer variables we obtain a slightly larger solution.
Theorem 1.2. For any positive real
$\unicode[STIX]{x1D700}<1$
, positive integers
$k,n$
with
$n>\frac{3}{2}k\log (3e/\unicode[STIX]{x1D700})+3$
, prime
$p$
, and integers
$c,a_{i}$
,
$1\leqslant i\leqslant n$
with
$p\nmid a_{i}$
,
$1\leqslant i\leqslant n$
, there is a solution of (1.1) with
$1\leqslant {x_{i}\ll }_{\unicode[STIX]{x1D700},k}p^{1/k+\unicode[STIX]{x1D700}}$
,
$1\leqslant i\leqslant n$
.
Another problem of interest is to minimize the number of variables required to break the
$\sqrt{p}$
threshold for the size of a solution. The square-root threshold is the natural one that arises when one tries to attack the problem by completing exponential sums over restricted intervals.
Corollary 1.1. For
$k\geqslant 2$
,
$n\geqslant 5k+3$
, and any
$c,a_{i}$
with
$p\nmid a_{i}$
,
$1\leqslant i\leqslant n$
, there exists a solution of (1.1) with
$1\leqslant {x_{i}\ll }_{k}\sqrt{p}$
,
$1\leqslant i\leqslant n$
.
2 Comparison with known results
The problem of obtaining small solutions to diagonal congruences of the type (1.1) has received much attention over the years including the work of Schmidt [Reference Schmidt11–Reference Schmidt13], Baker [Reference Baker1, Reference Baker2], Dietmann [Reference Dietmann8], Cochrane [Reference Cochrane5] and Cochrane and Zheng [Reference Cochrane and Zheng7]. Their results are summarized in the introduction to the authors’ first paper on this topic [Reference Cochrane, Ostergaard and Spencer6]. The results from [Reference Cochrane, Ostergaard and Spencer6] stated below in (2.1), (2.2), and (2.3) are the best available estimates (prior to the current work) for the problem at hand.
In [Reference Cochrane, Ostergaard and Spencer6], the authors proved that for
$k\geqslant 2$
,
$\unicode[STIX]{x1D700}>0$
, and integers
$c,a_{i}$
with
$p\nmid a_{i}$
,
$1\leqslant i\leqslant n$
, there exists a non-zero solution
$\text{}\underline{x}$
to (1.1) with
$$\begin{eqnarray}1\leqslant {x_{i}\ll }_{k,\unicode[STIX]{x1D700}}\left\{\begin{array}{@{}ll@{}}p^{k(\log k+\unicode[STIX]{x1D6FE}\log \log 2k)/n+\unicode[STIX]{x1D700}}\quad & \text{if}~n\leqslant k(k-1)(\log k+\unicode[STIX]{x1D6FE}\log \log 2k),\\ p^{1/(k-1)}\quad & \text{if}~k(k-1)(\log k+\unicode[STIX]{x1D6FE}\log \log 2k)\\ \quad & \quad <n\leqslant k(k-1)^{2},\\ p^{1/k+(k-1)/n+\unicode[STIX]{x1D700}}\quad & \text{if}~n>k(k-1)^{2},\end{array}\right.\end{eqnarray}$$
for
$1\leqslant i\leqslant n$
. Here,
$\unicode[STIX]{x1D6FE}$
is the implicit constant appearing in [Reference Wooley16, Theorem 1.1]. Theorem 1.2 improves on this result for
$n<\frac{3}{2}(k^{2}+k+2)$
and Theorem 1.1 improves on it for all larger values of
$n$
.
Also in [Reference Cochrane, Ostergaard and Spencer6], the authors established that for
$k\geqslant 2$
,
$\unicode[STIX]{x1D700}>0$
, and integers
$c,a_{i}$
with
$p\nmid a_{i}$
,
$1\leqslant i\leqslant n$
, there exists a solution
$\text{}\underline{x}$
to (1.1) in an arbitrary cube
${\mathcal{B}}$
of side length
$B$
provided that
$$\begin{eqnarray}B\gg _{k,\unicode[STIX]{x1D700}}\left\{\begin{array}{@{}ll@{}}p^{k(k-1)/n+\unicode[STIX]{x1D700}}\quad & \text{if}~n\leqslant k(k-1)^{2},\\ p^{1/k+(k-1)/n+\unicode[STIX]{x1D700}}\quad & \text{if}~n>k(k-1)^{2},\end{array}\right.\end{eqnarray}$$
and that for
$2\leqslant k\leqslant 5$
, the inequalities in (2.2) may be improved to
$$\begin{eqnarray}B\gg _{k,\unicode[STIX]{x1D700}}\left\{\begin{array}{@{}ll@{}}p^{2^{k-1}/n+\unicode[STIX]{x1D700}}\quad & \text{if}~n\leqslant 2^{k-1}(k-1),\\ p^{1/k+2^{k-1}/(nk)+\unicode[STIX]{x1D700}}\quad & \text{if}~n>2^{k-1}(k-1).\end{array}\right.\end{eqnarray}$$
For
$n\geqslant \frac{3}{2}(k^{2}+k+2)$
, Theorem 1.1 improves on (2.2) and (2.3) for cubes to which it applies.
3 A general upper bound on the number of solutions of (1.1)
The objective of the next few sections is to establish a sharp upper bound on the number of solutions to a diagonal congruence of the type (1.1), with variables restricted to a cube
${\mathcal{B}}$
of the type (1.2). In fact our proof holds identically for a general modulus
$q$
and so we state it as such. In this case, we restrict our attention to congruences of the type
$$\begin{eqnarray}\mathop{\sum }_{i=1}^{n}a_{i}x_{i}^{k}\equiv c\hspace{0.6em}({\rm mod}\hspace{0.2em}q)\end{eqnarray}$$
with the
$a_{i}$
integers relatively prime to
$q$
. Let
$N_{q}({\mathcal{B}})$
denote the number of solutions of (3.1) with
$\text{}\underline{x}\in {\mathcal{B}}$
.
Theorem 3.1. Let
$q,n,k$
be positive integers with
$n\geqslant k^{2}+k+2$
,
${\mathcal{B}}$
be any cube of edge length
$B\leqslant q$
as in (1.2),
$a_{i}$
be integers with
$(a_{i},q)=1$
,
$1\leqslant i\leqslant n$
, and
$c\in \mathbb{Z}$
. Then
$$\begin{eqnarray}N_{q}({\mathcal{B}})\ll _{k}\frac{B^{n}}{q}+B^{n-k}.\end{eqnarray}$$
An explicit value for the constant in (3.2) is given in (6.1). Aside from the determination of this constant the upper bound is best possible. Indeed, as
$c$
runs from 0 to
$q-1$
, the average number of solutions of the congruence (3.1) with
$\text{}\underline{x}\in {\mathcal{B}}$
, is
$B^{n}/q$
. On the other hand, if
$\sum _{i=1}^{n}|a_{i}|$
is fixed, and
$c$
is allowed to run from
$-B^{k}\sum _{i=1}^{n}|a_{i}|$
to
$B^{k}\sum _{i=1}^{n}|a_{i}|$
, then the average number of solutions of the equation
$\sum _{i=1}^{n}a_{i}x_{i}^{k}=c$
with
$1\leqslant x_{i}\leqslant B$
is of order
$B^{n-k}$
. Thus for a cube of the type
$1\leqslant x_{i}\leqslant B$
, one can do no better than
$B^{n}/q$
for large
$B$
(
$B>q^{1/k}$
), and no better than
$B^{n-k}$
for small
$B$
, (
$B<q^{1/k}$
).
Theorem 3.1 yields the upper bound
$N_{q}({\mathcal{B}})\ll _{k}|{\mathcal{B}}|/q$
for
$B\gg _{k}q^{1/k}$
. In comparison, for the case of prime moduli
$p$
, standard estimates for exponential sums over the algebraic set
$\sum _{i=1}^{n}a_{i}x_{i}^{k}=c$
in
$\mathbb{Z}_{p}$
, yield the asymptotic formula [Reference Cochrane5, Example 4.4.19],
$$\begin{eqnarray}N_{p}({\mathcal{B}})=\frac{B^{n}}{p}+O_{n,k}(p^{(n-1)/2}(\log p)^{n}),\end{eqnarray}$$
for any
$k,n$
, and
$p\nmid a_{1}\cdots a_{n}c$
. This estimate, when it applies, improves on the constant in the main term of (3.2) for
$B\gg _{n,k}p^{1/2+1/2n}\log p$
. However, estimates of this kind fall short of breaking the
$\sqrt{p}$
barrier for a solution of (1.1), no matter how many variables are used.
The upper bound in (3.2) can be generalized to a rectangular box with edges of different lengths as follows. For any positive integers
$k,n,q$
with
$n\geqslant \frac{1}{2}(k^{2}+k+2)$
,
$$\begin{eqnarray}{\mathcal{B}}:=\{\text{}\underline{x}\in \mathbb{Z}^{n}:c_{i}+1\leqslant x_{i}\leqslant c_{i}+B_{i},1\leqslant i\leqslant n\},\end{eqnarray}$$
$c_{i},B_{i}\in \mathbb{Z}$
,
$1\leqslant B_{i}\leqslant q$
, and
$(a_{i},q)=1$
,
$1\leqslant i\leqslant n$
,
$$\begin{eqnarray}N_{q}({\mathcal{B}})\ll _{k}\mathop{\prod }_{i=1}^{n}\biggl(\frac{B_{i}^{n}}{q}+B_{i}^{n-k}\biggr)^{1/n}.\end{eqnarray}$$
We begin the proof of the theorem with the following lemma. Let
$\mathbb{Z}_{q}$
denote the residue class ring modulo
$q$
and
$e_{q}(\cdot ):=\text{e}^{2\unicode[STIX]{x1D70B}i(\cdot )/q}$
, an additive character on
$\mathbb{Z}_{q}$
. For any subsets
$S_{1},\ldots ,S_{n}$
of
$\mathbb{Z}_{q}$
, put
$\mathscr{S}=S_{1}\times \cdots \times S_{n}$
, and define
$$\begin{eqnarray}I_{n,k}(\mathscr{S}):=\#\biggl\{(\text{}\underline{x},\text{}\underline{y})\in \mathscr{S}\times \mathscr{S}:\mathop{\sum }_{i=1}^{n}x_{i}^{k}\equiv \mathop{\sum }_{i=1}^{n}y_{i}^{k}~(\text{mod}\,q)\biggr\}.\end{eqnarray}$$
Lemma 3.1. Let
$q,n,k$
be positive integers,
$S_{1},\ldots ,S_{2n}$
be subsets of
$\mathbb{Z}_{q}$
, and
$\mathscr{T}=S_{1}\times \cdots \times S_{2n}$
. For any integers
$c,a_{i}$
,
$1\leqslant i\leqslant 2n$
, with
$(a_{i},q)=1$
,
$1\leqslant i\leqslant 2n$
, we have
$$\begin{eqnarray}\#\biggl\{\text{}\underline{x}\in \mathscr{T}:\mathop{\sum }_{i=1}^{2n}a_{i}x_{i}^{k}\equiv c~(\text{mod}\,q)\biggr\}\leqslant \mathop{\prod }_{i=1}^{2n}I_{n,k}({\mathcal{S}}_{i}^{n})^{1/2n},\end{eqnarray}$$
where
$S_{i}^{n}$
is the cartesian product of
$S_{i}$
with itself
$n$
times.
Proof. We have
$$\begin{eqnarray}\displaystyle \#\biggl\{\text{}\underline{x}\in \mathscr{T}:\mathop{\sum }_{i=1}^{2n}a_{i}x_{i}^{k}\equiv c~(\text{mod}\,q)\biggr\} & = & \displaystyle \frac{1}{q}\mathop{\sum }_{\text{}\underline{x}\in \mathscr{T}}\mathop{\sum }_{\unicode[STIX]{x1D706}=1}^{q}e_{q}\biggl(\unicode[STIX]{x1D706}\biggl(\mathop{\sum }_{i=1}^{2n}a_{i}x_{i}^{k}-c\biggr)\biggr)\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \frac{1}{q}\mathop{\sum }_{\unicode[STIX]{x1D706}=1}^{q}\biggl|e_{q}(-\unicode[STIX]{x1D706}c)\mathop{\prod }_{i=1}^{2n}\mathop{\sum }_{x_{i}\in S_{i}}e_{q}(\unicode[STIX]{x1D706}a_{i}x_{i}^{k})\biggr|\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \frac{1}{q}\biggl[\mathop{\sum }_{\unicode[STIX]{x1D706}=1}^{q}\biggl|\mathop{\sum }_{x_{1}\in S_{1}}e_{q}(\unicode[STIX]{x1D706}a_{1}x_{1}^{k})\biggr|^{2n}\biggr]^{1/2n}\nonumber\\ \displaystyle & & \displaystyle \cdots \biggl[\mathop{\sum }_{\unicode[STIX]{x1D706}=1}^{q}\biggl|\mathop{\sum }_{x_{2n}\in S_{2n}}e_{q}(\unicode[STIX]{x1D706}a_{2n}x_{2n}^{k})\biggr|^{2n}\biggr]^{1/2n},\nonumber\end{eqnarray}$$
by Hölder’s inequality. Now, for
$1\leqslant i\leqslant n$
, the sum
$$\begin{eqnarray}\mathop{\sum }_{\unicode[STIX]{x1D706}=1}^{q}\biggl|\mathop{\sum }_{x_{i}\in S_{i}}e_{q}(\unicode[STIX]{x1D706}a_{i}x_{i}^{k})\biggr|^{2n}\end{eqnarray}$$
is
$q$
times the number of solutions of the congruence
$$\begin{eqnarray}a_{i}(x_{1}^{k}+\cdots +x_{n}^{k})\equiv a_{i}(y_{1}^{k}+\cdots +y_{n}^{k})\hspace{0.6em}({\rm mod}\hspace{0.2em}q),\end{eqnarray}$$
with variables restricted to
$S_{i}$
. Since
$(a_{i},q)=1$
this is just
$qI_{n,k}(S_{i}^{n})$
. Therefore,
$$\begin{eqnarray}\displaystyle \#\biggl\{\text{}\underline{x}\in \mathscr{T}:\mathop{\sum }_{i=1}^{2n}a_{i}x_{i}^{k}\equiv c~(\text{mod}\,q)\biggr\} & {\leqslant} & \displaystyle \frac{1}{q}\mathop{\prod }_{i=1}^{2n}(qI_{n,k}(S_{i}^{n}))^{1/2n}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{i=1}^{2n}I_{n,k}(S_{i}^{n})^{1/2n}.\Box \nonumber\end{eqnarray}$$
4 Relating
$I_{n,k}({\mathcal{B}})$
to
$J_{n,k}(B)$
and
$J_{n,k}^{\ast }(B)$
In this section we obtain an estimate for
$I_{n,k}({\mathcal{B}})$
, the number of solutions of
$$\begin{eqnarray}\mathop{\sum }_{i=1}^{n}x_{i}^{k}\equiv \mathop{\sum }_{i=1}^{n}y_{i}^{k}\hspace{0.6em}({\rm mod}\hspace{0.2em}q),\end{eqnarray}$$
with
$\text{}\underline{x},\text{}\underline{y}$
in a cube of the type
$$\begin{eqnarray}{\mathcal{B}}={\mathcal{B}}(c,B):=\{\text{}\underline{x}\in \mathbb{Z}^{n}:c+1\leqslant x_{i}\leqslant c+B,1\leqslant i\leqslant n\},\end{eqnarray}$$
by first relating it to the number of solutions
$J_{n,k}(B)$
to the system of congruences
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}x_{1}+\cdots +x_{n}\ & \equiv \ & y_{1}+\cdots +y_{n}\hspace{0.6em}({\rm mod}\hspace{0.2em}q),\\ x_{1}^{2}+\cdots +x_{n}^{2}\ & \equiv \ & y_{1}^{2}+\cdots +y_{n}^{2}\hspace{0.6em}({\rm mod}\hspace{0.2em}q),\\ \ & \vdots \ & \\ x_{1}^{k}+\cdots +x_{n}^{k}\ & \equiv \ & y_{1}^{k}+\cdots +y_{n}^{k}\hspace{0.6em}({\rm mod}\hspace{0.2em}q)\end{array}\end{eqnarray}$$
with
$1\leqslant x_{i},y_{i}\leqslant B$
,
$1\leqslant i\leqslant n$
, and then relating it to the number of solutions of the corresponding system of equations (4.7).
Lemma 4.1. For any positive integers
$B,n,k,q$
with
$B\leqslant q$
, integer
$c$
, and cube
${\mathcal{B}}(c,B)$
as in (4.2) we have
$$\begin{eqnarray}I_{n,k}({\mathcal{B}})\leqslant (2n)^{k-1}B^{k(k-1)/2}J_{n,k}(B).\end{eqnarray}$$
Moreover, if for some
$j$
with
$1\leqslant j<k$
we have
$n(B^{j-1}-1)<(q-1)/2\leqslant n(B^{j}-1)$
, then
$$\begin{eqnarray}I_{n,k}({\mathcal{B}})\leqslant (2n)^{j-1}B^{j(j-1)/2}q^{k-j}J_{n,k}(B).\end{eqnarray}$$
Proof. First we observe that for any integers
$h_{i}$
,
$1\leqslant i\leqslant k-1$
, the number
$N(h_{1},\ldots ,h_{k-1})$
of integer solutions of the system
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}(x_{1}-c)+\cdots +(x_{n}-c)\ & \equiv \ & (y_{1}-c)+\cdots \\ \ & \ & +\,(y_{n}-c)+h_{1}\hspace{0.6em}({\rm mod}\hspace{0.2em}q)\\ \ & \vdots \ & \\ (x_{1}-c)^{k-1}+\cdots +(x_{n}-c)^{k-1}\ & \equiv \ & (y_{1}-c)^{k-1}+\cdots \\ \ & \ & +\,(y_{n}-c)^{k-1}+h_{k-1}\hspace{0.6em}({\rm mod}\hspace{0.2em}q)\\ x_{1}^{k}+\cdots +x_{n}^{k}\ & \equiv \ & y_{1}^{k}+\cdots +y_{n}^{k}\hspace{0.6em}({\rm mod}\hspace{0.2em}q)\end{array}\end{eqnarray}$$
with
$c+1\leqslant x_{i},y_{i}\leqslant c+B$
, is less than or equal to the number of solutions with all
$h_{i}=0$
. This follows by applying the triangle inequality to the exponential sum representation for the number of solutions of the system,
$$\begin{eqnarray}\displaystyle & & \displaystyle \frac{1}{q^{k}}\mathop{\sum }_{\unicode[STIX]{x1D706}_{1}=1}^{q}\cdots \mathop{\sum }_{\unicode[STIX]{x1D706}_{k}=1}^{q}e_{q}(-\unicode[STIX]{x1D706}_{1}h_{1}-\cdots -\unicode[STIX]{x1D706}_{k-1}h_{k-1})\mathop{\sum }_{\text{}\underline{x}\in {\mathcal{B}}}\mathop{\sum }_{\text{}\underline{y}\in {\mathcal{B}}}\nonumber\\ \displaystyle & & \displaystyle \quad e_{q}\biggl[\unicode[STIX]{x1D706}_{k}\biggl(\mathop{\sum }_{i=1}^{n}x_{i}^{k}-\mathop{\sum }_{i=1}^{n}y_{i}^{k}\biggr)+\mathop{\sum }_{j=1}^{k-1}\unicode[STIX]{x1D706}_{j}\biggl(\mathop{\sum }_{i=1}^{n}(x_{i}-c)^{j}-\mathop{\sum }_{i=1}^{n}(y_{i}-c)^{j}\biggr)\biggr].\nonumber\end{eqnarray}$$
But with all
$h_{i}=0$
the system of congruences above is equivalent to the defining system (4.3) for
$J_{n,k}(B)$
, and this system is invariant under the translation
$x_{i}\rightarrow x_{i}+c$
,
$y_{i}\rightarrow y_{i}+c$
. Thus we have
$N(h_{1},\ldots ,h_{k-1})\leqslant J_{n,k}(B)$
uniformly. Also, any solution of the diagonal congruence (4.1) with
$\text{}\underline{x},\text{}\underline{y}\in {\mathcal{B}}$
, is a solution of a system of the type (4.6) for some
$h_{i}$
satisfying
$|h_{i}|\leqslant n(B^{i}-1)$
,
$1\leqslant i\leqslant k-1$
. Thus we obtain
$$\begin{eqnarray}\displaystyle I_{n,k}({\mathcal{B}}) & = & \displaystyle \mathop{\sum }_{|h_{1}|\leqslant n(B-1)}\cdots \mathop{\sum }_{|h_{k-1}|\leqslant n(B^{k-1}-1)}N(h_{1},\ldots ,h_{k-1})\nonumber\\ \displaystyle & {\leqslant} & \displaystyle J_{n,k}(B)\mathop{\prod }_{i=1}^{k-1}(2n(B^{i}-1)+1),\nonumber\end{eqnarray}$$
yielding the inequality in (4.4).
Suppose now that for some
$j$
with
$1\leqslant j<k$
we have
$n(B^{j-1}-1)<(q-1)/2\leqslant n(B^{j}-1)$
. Then the upper bound can be improved by simply allowing
$h_{j},\ldots ,h_{k-1}$
to each run through a complete residue system modulo
$q$
. In this case, we see that there are at most
$(2n)^{j-1}B^{1+2+\cdots +(j-1)}q^{k-j}$
choices for the
$h_{i}$
, yielding the second inequality in the lemma.◻
Next we relate
$J_{n,k}(B)$
to
$J_{n,k}^{\ast }(B)$
, the number of integer solutions to the system of equations
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}x_{1}+\cdots +x_{n}\ & =\ & y_{1}+\cdots +y_{n},\\ x_{1}^{2}+\cdots +x_{n}^{2}\ & =\ & y_{1}^{2}+\cdots +y_{n}^{2},\\ \ & \vdots \ & \\ x_{1}^{k}+\cdots +x_{n}^{k}\ & =\ & y_{1}^{k}+\cdots +y_{n}^{k},\end{array}\end{eqnarray}$$
with
$1\leqslant x_{i},y_{i}\leqslant B$
,
$1\leqslant i\leqslant n$
.
Lemma 4.2. Let
$B,k,n,q$
be positive integers with
$1\leqslant B\leqslant q$
.
(i) If
$n(B^{k}-1)<q$
then
$J_{n,k}(B)=J_{n,k}^{\ast }(B)$
.(ii) If
$n(B^{k-1}-1)<(q-1)/2\leqslant n(B^{k}-1)$
then $$\begin{eqnarray}J_{n,k}(B)\leqslant (2nB^{k}/q+1)J_{n,k}^{\ast }(B).\end{eqnarray}$$
(iii) If for some
$j$
with
$1\leqslant j\leqslant k-1$
we have
$n(B^{j-1}-1)<(q-1)/2\leqslant n(B^{j}-1)$
, then $$\begin{eqnarray}J_{n,k}(B)<5(2n/q)^{k-j+1}B^{k(k+1)/2-j(j-1)/2}J_{n,k}^{\ast }(B).\end{eqnarray}$$
Proof. Any solution of (4.3) with
$1\leqslant x_{i}$
,
$y_{i}\leqslant B$
,
$1\leqslant i\leqslant n$
, satisfies a system of equations of the form
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}x_{1}+\cdots +x_{n}\ & =\ & y_{1}+\cdots +y_{n}+l_{1}q,\\ x_{1}^{2}+\cdots +x_{n}^{2}\ & =\ & y_{1}^{2}+\cdots +y_{n}^{2}+l_{2}q,\\ \ & \vdots \ & \\ x_{1}^{k}+\cdots +x_{n}^{k}\ & =\ & y_{1}^{k}+\cdots +y_{n}^{k}+l_{k}q\end{array}\end{eqnarray}$$
for some integers
$l_{i}$
with
$|l_{i}|\leqslant n/q(B^{i}-1)$
,
$1\leqslant i\leqslant k$
. For fixed
$l_{i}$
the number of solutions of (4.8) with
$1\leqslant x_{i}$
,
$y_{i}\leqslant B$
is at most
$J_{n,k}^{\ast }(B)$
, as one can see by applying the triangle inequality to the integral representation for the number of solutions.
If
$n(B^{k}-1)<q$
, then for
$1\leqslant i\leqslant k$
we have
$(n/q)(B^{i}-1)<1$
and so there is only one choice for
$l_{i}$
, namely
$l_{i}=0$
. Thus
$J_{n,k}(B)=J_{n,k}^{\ast }(B)$
, completing the proof of part (i). If for some
$j$
with
$1\leqslant j\leqslant k$
we have
$n(B^{j-1}-1)<(q-1)/2\leqslant n(B^{j}-1)$
, then for
$1\leqslant i\leqslant j-1$
, we again have
$l_{i}=0$
. Thus
$$\begin{eqnarray}J_{n,k}(B)\leqslant J_{n,k}^{\ast }(B)\mathop{\prod }_{i=j}^{k}\biggl(2\biggl\lfloor\frac{n}{q}(B^{i}-1)\biggr\rfloor+1\biggr)\leqslant J_{n,k}^{\ast }(B)\mathop{\prod }_{i=j}^{k}\biggl(2\frac{n}{q}B^{i}+1\biggr).\end{eqnarray}$$
If
$j=k$
this is the inequality in (ii). Suppose now that
$j\leqslant k-1$
. Then,
$$\begin{eqnarray}J_{n,k}(B)\leqslant J_{n,k}^{\ast }(B)B^{j+(j+1)+\cdots +k}\biggl(\frac{2n}{q}\biggr)^{k-j+1}\mathop{\prod }_{i=j}^{k}\biggl(1+\frac{q/2n}{B^{i}}\biggr).\end{eqnarray}$$
Using
$(q-1)/2\leqslant n(B^{j}-1)$
, whence
$q/2n<B^{j}$
, we see that (since
$B\geqslant 2$
),
$$\begin{eqnarray}\mathop{\prod }_{i=j}^{k}\biggl(1+\frac{q/2n}{B^{i}}\biggr)<\mathop{\prod }_{i=j}^{k}\biggl(1+\frac{1}{B^{i-j}}\biggr)\leqslant \mathop{\prod }_{i=j}^{\infty }\biggl(1+\frac{1}{2^{i-j}}\biggr)<4.77,\end{eqnarray}$$
completing the proof of part (iii). ◻
Putting together the results of Lemmas 4.1 and 4.2, we obtain a uniform upper bound for
$I_{n,k}({\mathcal{B}})$
in terms of
$J_{n,k}^{\ast }(B)$
.
Lemma 4.3. For any integer
$c$
, positive integers
$B,k,n,q$
with
$1\leqslant B\leqslant q$
, and cube
${\mathcal{B}}={\mathcal{B}}(c,B)$
as in (4.2) we have
$$\begin{eqnarray}I_{n,k}({\mathcal{B}})\leqslant 5(2n)^{k}B^{\frac{1}{2}k(k-1)}\biggl(\frac{B^{k}}{q}+\frac{1}{2n}\biggr)J_{n,k}^{\ast }(B).\end{eqnarray}$$
5 Estimation of
$J_{n,k}^{\ast }(B)$
The task of estimating
$J_{n,k}^{\ast }(B)$
has been a central problem in additive number theory since Vinogradov’s seminal work [Reference Vinogradov15] on Waring’s problem. Recall that a non-negative real number
$\unicode[STIX]{x1D6E5}_{n,k}^{\ast }$
is called an admissible exponent for the system (4.7) if
$$\begin{eqnarray}J_{n,k}^{\ast }(B)\leqslant c_{1}(n,k)B^{2n-\frac{1}{2}k(k+1)+\unicode[STIX]{x1D6E5}_{n,k}^{\ast }}\end{eqnarray}$$
for some constant
$c_{1}(n,k)$
. Wooley [Reference Wooley17, Theorems 1.1, 1.2] established that for
$k\geqslant 2$
and
$n\geqslant k(k+1)$
one can take
$\unicode[STIX]{x1D6E5}_{n,k}^{\ast }=\unicode[STIX]{x1D700}$
for any
$\unicode[STIX]{x1D700}>0$
, and that for
$k\geqslant 3$
and
$n\geqslant k^{2}+k+1$
one can take
$\unicode[STIX]{x1D6E5}_{n,k}^{\ast }=0$
. He [Reference Wooley18, Theorem 1.1] then obtained
$\unicode[STIX]{x1D6E5}_{n,k}^{\ast }=\unicode[STIX]{x1D700}$
for
$k\geqslant 3$
,
$n\geqslant k^{2}-1$
, and any
$\unicode[STIX]{x1D700}>0$
. Recently, Bourgain, Demeter, and Guth [Reference Bourgain, Demeter and Guth3] established that for
$k\geqslant 2$
, one can take
$\unicode[STIX]{x1D6E5}_{n,k}^{\ast }=\unicode[STIX]{x1D700}$
for
$n\geqslant \frac{1}{2}k(k+1)$
and
$\unicode[STIX]{x1D6E5}_{n,k}^{\ast }=0$
for
$n>\frac{1}{2}k(k+1)$
. In fact, for
$n>\frac{1}{2}k(k+1)$
, it follows from the work of [Reference Bourgain, Demeter and Guth3] that one has the asymptotic formula
$$\begin{eqnarray}J_{n,k}^{\ast }(B)\sim c(n,k)B^{2n-(1/2)k(k+1)},\end{eqnarray}$$
where
$c(n,k)$
is a constant given by
$$\begin{eqnarray}c(n,k)=\mathfrak{S}(n,k)\mathfrak{J}(n,k),\end{eqnarray}$$
with
$$\begin{eqnarray}\mathfrak{S}(n,k):=\mathop{\sum }_{q=1}^{\infty }\mathop{\sum }\nolimits_{(\unicode[STIX]{x1D706}_{1},\ldots ,\unicode[STIX]{x1D706}_{k},q)=1}\biggl|q^{-1}\mathop{\sum }_{x=1}^{q}e_{q}(\unicode[STIX]{x1D706}_{1}x+\cdots +\unicode[STIX]{x1D706}_{k}x^{k})\biggr|^{2n},\end{eqnarray}$$
and
$$\begin{eqnarray}\mathfrak{J}(n,k):=\int _{\mathbb{R}^{k}}\biggl|\int _{0}^{1}e(\unicode[STIX]{x1D6FD}_{1}x+\cdots +\unicode[STIX]{x1D6FD}_{k}x^{k})\,dx\biggr|^{2n}\,d\text{}\underline{\unicode[STIX]{x1D6FD}}.\end{eqnarray}$$
For
$B$
sufficiently large, it follows in this case that the constant in (5.1) can be taken to be
$c(n,k)+\unicode[STIX]{x1D700}$
, for any
$\unicode[STIX]{x1D700}>0$
. Using the result of [Reference Bourgain, Demeter and Guth3] we obtain from Lemma 4.3 the following upper bound on
$I_{n,k}({\mathcal{B}})$
.
Proposition 5.1. For any positive integers
$n,k$
with
$n>\frac{1}{2}k(k+1)$
and cube
${\mathcal{B}}$
as in (4.2), we have
$$\begin{eqnarray}I_{n,k}({\mathcal{B}})\leqslant 5c_{1}(n,k)(2n)^{k}\biggl(\frac{B^{2n}}{q}+\frac{1}{2n}B^{2n-k}\biggr),\end{eqnarray}$$
where
$c_{1}(n,k)$
is the constant appearing in (5.1) with
$\unicode[STIX]{x1D6E5}_{n,k}^{\ast }=0$
.
6 Proof of Theorem 3.1
Proof. We may assume that
$n=k^{2}+k+2$
, by setting
$n-(k^{2}+k+2)$
variables equal to arbitrary values in their specified intervals if
$n>k^{2}+k+2$
. Put
$m=n/2$
. For
$1\leqslant i\leqslant n$
, let
$S_{i}=\{x\in \mathbb{Z}:c_{i}+1\leqslant x\leqslant c_{i}+B\}$
, and
$S_{i}^{m}$
be the cartesian product of
$S_{i}$
with itself
$m$
times, so that
$S_{i}^{m}$
is a cube of type (4.2). By Proposition 5.1, we have
$$\begin{eqnarray}I_{m,k}(S_{i}^{m})\leqslant 5c_{1}(m,k)n^{k}\biggl(\frac{B^{n}}{q}+\frac{1}{n}B^{n-k}\biggr),\end{eqnarray}$$
for each of the cubes
$S_{i}^{m}$
, and thus the theorem follows immediately from Lemma 3.1 (with
$n$
replaced by
$m$
). We observe that the constant in the upper bound of Theorem 3.1 may be taken to be
$$\begin{eqnarray}5c_{1}((k^{2}+k+2)/2,k)(k^{2}+k+2)^{k}.\end{eqnarray}$$
◻
Remark 6.1. Cilleruelo et al [Reference Cilleruelo, Garaev, Ostafe and Shparlinski4] employed a similar strategy to our proof of Theorem 3.1 for estimating the number of solutions of a congruence
$f(x)\equiv y~(\text{mod}\,p)$
. Shparlinski and Zumalacárregui [Reference Shparlinski and Zumalacárregui14, (unpublished)] recently obtained a variation of Proposition 5.1. They also note that a non-trivial estimate of this kind is available with
$n$
slightly smaller than
$\frac{1}{2}k(k+1)$
, using
$J_{n,k}^{\ast }(B)\ll B^{\unicode[STIX]{x1D700}}(B^{2n-(1/2)k(k+1)}+B^{n})$
. However, for our purposes, this yields no benefits.
7 The value set of a diagonal form over a cube
For any cube
${\mathcal{B}}$
as in (1.2), we define
$S_{{\mathcal{B}}}$
to be the set of values the diagonal form
$\sum _{i=1}^{n}a_{i}x_{i}^{k}$
takes on modulo
$q$
as
$\text{}\underline{x}$
runs through
${\mathcal{B}}$
,
$$\begin{eqnarray}S_{{\mathcal{B}}}:=\biggl\{\mathop{\sum }_{i=1}^{n}a_{i}x_{i}^{k}\in \mathbb{Z}_{q}:\text{}\underline{x}\in {\mathcal{B}}\biggr\},\end{eqnarray}$$
and put
$$\begin{eqnarray}N_{{\mathcal{B}}}:=\#\biggl\{(\text{}\underline{x},\text{}\underline{y})\in {\mathcal{B}}\times {\mathcal{B}}:\mathop{\sum }_{i=1}^{n}a_{i}x_{i}^{k}\equiv \mathop{\sum }_{i=1}^{n}a_{i}y_{i}^{k}~(\text{mod}\,q)\biggr\}.\end{eqnarray}$$
By Theorem 3.1, we have for
$n\geqslant \frac{1}{2}(k^{2}+k+2)$
and
$(a_{i},q)=1$
,
$1\leqslant i\leqslant n$
, that
$$\begin{eqnarray}{N_{{\mathcal{B}}}\ll }_{k}\frac{B^{2n}}{q}+B^{2n-k},\end{eqnarray}$$
and thus using the elementary relationship
$|S_{{\mathcal{B}}}|\geqslant B^{2n}/N_{{\mathcal{B}}}$
, we deduce Lemma 7.1 as follows.
Lemma 7.1. For any positive integers
$k,n,B,q$
with
$n\geqslant \frac{1}{2}(k^{2}+k+2)$
, cube
${\mathcal{B}}$
as in (1.2) with
$B\gg q^{1/k}$
, and integers
$a_{i}$
with
$(a_{i},q)=1$
,
$1\leqslant i\leqslant n$
, we have
$|S_{{\mathcal{B}}}|\gg _{k}q$
.
If
$n(B^{k}-1)<q$
, so that
$J_{n,k}(B)=J_{n,k}^{\ast }(B)$
, we obtain in the same manner from (4.4) and (5.1) the following explicit estimates when
$n\geqslant \frac{1}{2}(k^{2}+k+2)$
:
$$\begin{eqnarray}N_{{\mathcal{B}}}\leqslant c_{1}(n,k)(2n)^{k-1}B^{2n-k},\end{eqnarray}$$
and
$$\begin{eqnarray}|S_{{\mathcal{B}}}|\geqslant c_{1}(n,k)^{-1}(2n)^{1-k}B^{k},\end{eqnarray}$$
with
$c_{1}(n,k)$
the constant in (5.1) with
$\unicode[STIX]{x1D6E5}_{k}^{\ast }=0$
.
8 Proof of Theorem 1.1
Before proving the theorem we need a few lemmas. For prime
$p$
and positive integer
$k$
, let
$\unicode[STIX]{x1D6E4}(k,p)$
be the minimal
$n$
such that for any integers
$a_{i}$
with
$p\nmid a_{i}$
,
$1\leqslant i\leqslant n$
, and any integer
$c$
, the congruence (1.1) is solvable.
Lemma 8.1. For any prime
$p$
and positive integer
$k$
we have
$\unicode[STIX]{x1D6E4}(k,p)\leqslant k$
.
Proof. Let
$\mathbb{Z}_{p}$
be the residue class ring modulo
$p$
. For
$1\leqslant i\leqslant n$
let
$a_{i}$
be a non-zero element of
$\mathbb{Z}_{p}$
and
$T_{i}=\{a_{i}x^{k}:x\in \mathbb{Z}_{p}\}$
. Then
$|T_{i}|\geqslant (p-1)/k+1$
and by the Cauchy–Davenport theorem
$$\begin{eqnarray}|T_{1}+T_{2}+\cdots +T_{n}|\geqslant \min \biggl\{p,n\frac{p-1}{k}+1\biggr\}.\end{eqnarray}$$
Thus, if
$n\geqslant k$
the sum set is all of
$\mathbb{Z}_{p}$
.◻
The following lemma is due to Sárközy [Reference Sárközy10].
Lemma 8.2 [Reference Sárközy10, Corollary A].
If
$A,B,C,D$
are subsets of
$\mathbb{Z}_{p}$
with
$|A||B||C||D|>p^{3}$
, then there is a solution of
$a+b=cd$
with
$a\in A$
,
$b\in B$
,
$c\in C$
,
$d\in D$
.
An immediate consequence that we will use is the following lemma.
Lemma 8.3. If
$A_{1},A_{2},A_{3}$
, and
$B_{1}$
are subsets of
$\mathbb{Z}_{p}$
with
$|A_{1}||A_{2}||A_{3}||B_{1}|>p^{3}$
, then
$A_{1}B_{1}+A_{2}+A_{3}=\mathbb{Z}_{p}$
.
Proof. For any
$x\in \mathbb{Z}_{p}$
, apply Sárközy’s Lemma with
$A=A_{2}-x$
,
$B=A_{3}$
,
$C=-A_{1}$
, and
$D=B_{1}$
.◻
Proof of Theorem 1.1.
Suppose that
$p$
is a prime,
$k,n$
are positive integers with
$n\geqslant \frac{3}{2}(k^{2}+k+2)$
, and that
$c,a_{i}$
are integers with
$p\nmid a_{i}$
,
$1\leqslant i\leqslant n$
. Our goal is to produce a solution of the diagonal congruence (1.1) with
$$\begin{eqnarray}1\leqslant x_{i}\leqslant \unicode[STIX]{x1D705}(k)p^{1/k},\end{eqnarray}$$
for some constant
$\unicode[STIX]{x1D705}(k)$
. Set
$n_{1}=(k^{2}+k+2)/2$
. By specifying variables if needed we may assume that
$n=3n_{1}$
. We claim that we may take
$\unicode[STIX]{x1D705}(k)$
to be
$$\begin{eqnarray}\unicode[STIX]{x1D705}(k):=\max \{2^{k},\lceil k/c_{2}(k)^{3}\rceil \}\end{eqnarray}$$
with
$c_{2}(k)$
the constant occurring in (8.1). If
$p\leqslant \unicode[STIX]{x1D705}(k)$
, the result is trivial. In this case the
$x_{i}$
are allowed to run through a complete residue system modulo
$p$
. Since
$\unicode[STIX]{x1D6E4}(k,p)\leqslant k$
by Lemma 8.1, it suffices to have
$n\geqslant k$
. Thus we may assume that
$p>\max \{2^{k},\lceil k/c_{2}(k)^{3}\rceil \}$
.
Let
${\mathcal{B}}$
be the cube
$1\leqslant x_{i}\leqslant B$
,
$1\leqslant i\leqslant n$
, in
$n$
variables with edge length
$B$
satisfying
$\frac{1}{2}p^{1/k}\leqslant B<p^{1/k}$
. Such an integer
$B$
exists since
$p>2^{k}$
. Divide the
$n$
variables into three disjoint sets,
$F_{1},F_{2},F_{3}$
, with
$|F_{i}|=n_{1}$
,
$1\leqslant i\leqslant 3$
. Let
${\mathcal{B}}_{i}$
be the cube corresponding to the
$i$
th set of variables, and let
$A_{1},A_{2},A_{3}$
be the value sets of the diagonal sums over each of these sets of variables. Thus, for the first set of variables,
$F_{1}=\{x_{1},\ldots ,x_{n_{1}}\}$
say,
$$\begin{eqnarray}A_{1}=\{a_{1}x_{1}^{k}+\cdots +a_{n_{1}}x_{n_{1}}^{k}~(\text{mod}\,p):1\leqslant x_{i}\leqslant B,1\leqslant i\leqslant n_{1}\},\end{eqnarray}$$
and similarly for
$A_{2}$
and
$A_{3}$
. Set
$D:=\{1^{k},2^{k},\ldots ,L^{k}\}\subseteq \mathbb{Z}_{p}$
(with
$L$
a parameter to be chosen later), a set with at least
$L/k$
distinct values modulo
$p$
assuming that
$L\leqslant p$
. Since
$B\geqslant \frac{1}{2}p^{1/k}$
we have from Lemma 7.1 that
$$\begin{eqnarray}|A_{1}|,|A_{2}|,|A_{3}|\geqslant c_{2}(k)p\end{eqnarray}$$
for some constant
$c_{2}(k)$
. Thus, if
$L\leqslant p$
and
$c_{2}(k)^{3}p^{3}L/k>p^{3}$
, we can apply Lemma 8.3 to obtain
$A_{1}D+A_{2}+A_{3}=\mathbb{Z}_{p}$
. It suffices to take
$L=\lceil k/c_{2}(k)^{3}\rceil$
, a value that is at most
$p$
by our assumption that
$p>\lceil k/c_{2}(k)^{3}\rceil$
. We have
$$\begin{eqnarray}A_{1}D=\biggl\{\mathop{\sum }_{i=1}^{n_{1}}a_{i}(yx_{i})^{k}~(\text{mod}\,p):1\leqslant y\leqslant L,1\leqslant x_{i}\leqslant B,1\leqslant i\leqslant n_{1}\biggr\}.\end{eqnarray}$$
Observing that
$1\leqslant yx_{i}\leqslant LB<Lp^{1/k}\leqslant \unicode[STIX]{x1D705}(k)p^{1/k}$
, we obtain a solution of (1.1) with the first
$n_{1}$
variables bounded by
$\unicode[STIX]{x1D705}(k)p^{1/k}$
and the remaining ones by
$p^{1/k}$
.◻
Remark 8.1. It is plain from the proof above that the cubes corresponding to the second and third sets of variables may be taken in arbitrary position since Lemma 7.1 applies to a general cube. In this way we can obtain a solution of (1.1) with
$n_{1}$
variables restricted to the interval
$[1,\unicode[STIX]{x1D705}(k)p^{1/k}]$
, and the other
$2n_{1}$
variables in arbitrary intervals of length
$B\geqslant p^{1/k}$
.
Remark 8.2. The constant
$\unicode[STIX]{x1D705}(k)$
in Theorem 1.1 may be taken to be
$$\begin{eqnarray}\unicode[STIX]{x1D705}(k)=2^{3k}kc_{1}(n_{1},k)^{3}n_{1}^{3k},\end{eqnarray}$$
for
$p\gg _{k}1$
, where
$n_{1}=\frac{1}{2}(k^{2}+k+2)$
, and
$c_{1}(n_{1},k)$
is the constant in (5.1) with
$\unicode[STIX]{x1D6E5}_{k}^{\ast }=0$
.
9 Smooth solutions
$(\text{mod}\,q)$
In order to prove Theorem 1.2, we seek smooth solutions of the diagonal congruence (1.1). Let
$k,q,n,\ell$
, and
$B$
be positive integers and
${\mathcal{A}}={\mathcal{A}}(B,B^{1/\ell })$
be the set of
$B^{1/\ell }$
-smooth numbers defined by
$$\begin{eqnarray}{\mathcal{A}}:=\{x\in [1,B]\cap \mathbb{Z}:p~\text{prime},p|x\Rightarrow p\leqslant B^{1/\ell }\}.\end{eqnarray}$$
By the work of Ramaswami [Reference Ramaswami9], we have
$$\begin{eqnarray}|{\mathcal{A}}|=|{\mathcal{A}}(B,B^{1/\ell })|=B\unicode[STIX]{x1D70C}(\ell )+\text{O}\biggl(\frac{B}{\log B}\biggr),\end{eqnarray}$$
where
$\unicode[STIX]{x1D70C}(\ell )$
is the Dickman function. Let
${\mathcal{A}}^{n}$
denote the cartesian product of
${\mathcal{A}}$
with itself
$n$
times and put
$$\begin{eqnarray}I_{n,k}^{\ast }({\mathcal{A}}^{n})=\#\biggl\{(\text{}\underline{x},\text{}\underline{y})\in {\mathcal{A}}^{n}\times {\mathcal{A}}^{n}:\mathop{\sum }_{i=1}^{n}(x_{i}^{k}-y_{i}^{k})=0\biggr\}.\end{eqnarray}$$
Following Wooley, [Reference Wooley16, §2, p. 4], we call an exponent
$\unicode[STIX]{x1D6E5}_{n,k}$
permissible when for
$\ell$
sufficiently large,
$\ell \geqslant \ell _{0}(k,n)$
, and for any
$\unicode[STIX]{x1D700}>0$
, we have
$$\begin{eqnarray}I_{n,k}^{\ast }({\mathcal{A}}^{n})\leqslant c(\unicode[STIX]{x1D700},k,\ell ,n)B^{2n-k+\unicode[STIX]{x1D700}+\unicode[STIX]{x1D6E5}_{n,k}},\end{eqnarray}$$
for some constant
$c(\unicode[STIX]{x1D700},k,\ell ,n)$
. The following lemma of Wooley provides a value for
$\unicode[STIX]{x1D6E5}_{n,k}$
.
Lemma 9.1 [Reference Wooley16, Lemma 2.1].
For
$k\geqslant 4$
,
$n\geqslant 2$
, let
$\unicode[STIX]{x1D6E5}_{n,k}$
be the unique positive solution of the equation
$\unicode[STIX]{x1D6E5}_{n,k}\text{e}^{\unicode[STIX]{x1D6E5}_{n,k}/k}=k\text{e}^{1-2n/k}$
. Then
$\unicode[STIX]{x1D6E5}_{n,k}$
is permissible. In particular, the exponent
$\unicode[STIX]{x1D6E5}_{n,k}^{\ast }=k\text{e}^{1-2n/k}$
is permissible.
For any positive integers
$k\geqslant 4$
,
$n\geqslant 2$
and positive real
$\unicode[STIX]{x1D6FF}<k$
with
$n>\frac{1}{2}k\log (ek/\unicode[STIX]{x1D6FF})$
, we obtain from the lemma the permissible exponent
$$\begin{eqnarray}\unicode[STIX]{x1D6E5}_{n,k}^{\ast }:=k\text{e}^{1-2n/k}<k\text{e}^{1-\log (ek/\unicode[STIX]{x1D6FF})}=\unicode[STIX]{x1D6FF}.\end{eqnarray}$$
For any integers
$a_{i}$
with
$(a_{i},q)=1$
,
$1\leqslant i\leqslant n$
, let
$N_{{\mathcal{A}}^{n}}$
denote the value
$$\begin{eqnarray}N_{{\mathcal{A}}^{n}}:=\#\biggl\{(\text{}\underline{x},\text{}\underline{y})\in {\mathcal{A}}^{n}\times {\mathcal{A}}^{n}:\mathop{\sum }_{i=1}^{n}a_{i}x_{i}^{k}\equiv \mathop{\sum }_{i=1}^{n}a_{i}y_{i}^{k}~(\text{mod}\,q)\biggr\}.\end{eqnarray}$$
Following the proof of Lemma 3.1, we obtain
$$\begin{eqnarray}N_{{\mathcal{A}}^{n}}\leqslant \#\biggl\{(\text{}\underline{x},\text{}\underline{y})\in {\mathcal{A}}^{n}\times {\mathcal{A}}^{n}:\mathop{\sum }_{i=1}^{n}x_{i}^{k}\equiv \mathop{\sum }_{i=1}^{n}y_{i}^{k}~(\text{mod}\,q)\biggr\}.\end{eqnarray}$$
If
$n(B^{k}-1)<q$
, so that any solution of the congruence
$\sum _{i=1}^{n}x_{i}^{k}\equiv \sum _{i=1}^{n}y_{i}^{k}~(\text{mod}\,q)$
is a solution of the corresponding equation, we then obtain
$$\begin{eqnarray}N_{{\mathcal{A}}^{n}}\leqslant I_{n,k}^{\ast }({\mathcal{A}}^{n})\leqslant c(\unicode[STIX]{x1D700},k,\ell ,n)B^{2n-k+\unicode[STIX]{x1D700}+\unicode[STIX]{x1D6E5}_{n,k}},\end{eqnarray}$$
for any permissible exponent
$\unicode[STIX]{x1D6E5}_{n,k}$
.
Letting
$S_{{\mathcal{A}}^{n}}$
, denote the value set
$$\begin{eqnarray}S_{{\mathcal{A}}^{n}}:=\biggl\{\mathop{\sum }_{i=1}^{n}a_{i}x_{i}^{k}\in \mathbb{Z}_{q}:\text{}\underline{x}\in {\mathcal{A}}^{n}\biggr\},\end{eqnarray}$$
and using
$|S_{{\mathcal{A}}^{n}}|\geqslant |{\mathcal{A}}^{n}|^{2}/N_{{\mathcal{A}}^{n}}$
, together with the lower bound
$|{\mathcal{A}}^{n}|>\frac{1}{2}\unicode[STIX]{x1D70C}(\ell )^{n}B^{n}$
available from (9.2) for
$B$
sufficiently large, we obtain the following lower bound on
$|S_{{\mathcal{A}}^{n}}|$
.
Lemma 9.2. For any positive integers
$k,\ell ,n,q,B$
and
$\unicode[STIX]{x1D700}>0$
with
$B^{k}<q/n$
, and integers
$a_{i}$
with
$(a_{i},q)=1$
,
$1\leqslant i\leqslant n$
, we have
$$\begin{eqnarray}|S_{{\mathcal{A}}^{n}}|\gg _{k,\ell ,n,\unicode[STIX]{x1D700}}B^{k-\unicode[STIX]{x1D700}-\unicode[STIX]{x1D6E5}_{n,k}},\end{eqnarray}$$
for any permissible exponent
$\unicode[STIX]{x1D6E5}_{n,k}$
.
10 Proofs of Theorem 1.2 and Corollary 1.1
Proof of Theorem 1.2.
Let
$k,n$
be positive integers with
$n>\frac{3}{2}k\log (3e/\unicode[STIX]{x1D700})+3$
,
$p$
a prime,
$a_{i}$
be integers with
$p\nmid a_{i}$
,
$1\leqslant i\leqslant n$
and
$c$
be any integer. Our goal is to obtain a solution of the diagonal congruence (1.1) with
$$\begin{eqnarray}1\leqslant {x_{i}\ll }_{\unicode[STIX]{x1D700},k}p^{1/k+\unicode[STIX]{x1D700}},\quad 1\leqslant i\leqslant n.\end{eqnarray}$$
If
$k=1$
the result is trivial. For
$k=2$
, it is already known [Reference Cochrane and Zheng7] that for
$n\geqslant 4$
(1.1) has a solution with
$1\leqslant x_{i}\ll \sqrt{p}\log p$
. For
$k=3$
the result follows from Theorem 1.1 for
$\unicode[STIX]{x1D700}\leqslant 0.18$
and from (2.3) for
$\unicode[STIX]{x1D700}\geqslant 0.18$
. Thus, we may assume that
$k\geqslant 4$
.
Set
$m=\lfloor n/3\rfloor$
and
$B=\lfloor (3p/n)^{1/k}\rfloor$
. Since
$n>k$
, we know by Lemma 8.1 that (1.1) is solvable. Thus by taking the implied constant in (10.1) sufficiently large we may assume that
$p$
is greater than any constant we may need depending only on
$\unicode[STIX]{x1D700},n$
and
$k$
. In particular, we may assume that
$3p>n$
, whence
$B\geqslant 1$
. Let
${\mathcal{A}}$
be the set of
$B^{1/\ell }$
-smooth numbers as in (9.1), with
$\ell$
sufficiently large. We divide the
$n$
variables into three sets, each with at least
$m$
variables. Assuming the first set of variables is
$x_{1},\ldots ,x_{m}$
, let
$$\begin{eqnarray}A_{1}=\biggl\{\mathop{\sum }_{i=1}^{m}a_{i}x_{i}^{k}\in \mathbb{Z}_{p}:x_{i}\in {\mathcal{A}},1\leqslant i\leqslant m\biggr\},\end{eqnarray}$$
and define
$A_{2}$
and
$A_{3}$
similarly for the second and third sets of variables.
Note that
$m>n/3-1>\frac{1}{2}k\log (3e/\unicode[STIX]{x1D700})$
, and so by (9.3) with
$\unicode[STIX]{x1D6FF}=\unicode[STIX]{x1D700}k/3$
, there exists a permissible exponent
$\unicode[STIX]{x1D6E5}_{m,k}^{\ast }<\unicode[STIX]{x1D700}k/3$
. Let
$\unicode[STIX]{x1D700}^{\prime }>0$
satisfy
$\unicode[STIX]{x1D700}^{\prime }+\unicode[STIX]{x1D6E5}_{m,k}^{\ast }=\unicode[STIX]{x1D700}k/3$
. We have
$B^{k}<3p/n\leqslant p/m$
, and so by Lemma 9.2 (with
$\unicode[STIX]{x1D700}$
taken to be
$\unicode[STIX]{x1D700}^{\prime }$
) we obtain
$$\begin{eqnarray}|A_{1}|,|A_{2}|,|A_{3}|\gg _{k}B^{k-k\unicode[STIX]{x1D700}/3}\gg _{k}p^{1-\unicode[STIX]{x1D700}/3}.\end{eqnarray}$$
Let
$D=\{1^{k},2^{k},3^{k},\ldots ,L^{k}\}\subseteq \mathbb{Z}_{p}$
, a set with at least
$L/k$
distinct values
$(\text{mod}\,p)$
, assuming that
$L\leqslant p$
. Thus, for
$L\gg _{k,n}p^{\unicode[STIX]{x1D700}}$
,
$$\begin{eqnarray}|A_{1}||A_{2}||A_{3}||D|\geqslant p^{3},\end{eqnarray}$$
and applying Lemma 8.3, we obtain a solution of (1.1) with
$$\begin{eqnarray}1\leqslant x_{i}\leqslant LB\ll _{k}p^{1/k+\unicode[STIX]{x1D700}},\end{eqnarray}$$
for
$1\leqslant i\leqslant n$
.◻
Remark 10.1. An alternate way of stating Theorem 1.2 is as follows: for any positive integers
$k,n$
, prime
$p$
,
$\unicode[STIX]{x1D70F}>3\text{e}^{1-2(n-3)/3k}$
and integers
$a_{i}$
,
$c$
with
$p\nmid a_{i}$
,
$1\leqslant i\leqslant n$
, there is a solution of (1.1) with
$1\leqslant {x_{i}\ll }_{k,\unicode[STIX]{x1D70F}}p^{1/k+\unicode[STIX]{x1D70F}}$
.
Proof of Corollary 1.1.
For convenience, we call a solution of (1.1) a small solution if
$1\leqslant {x_{i}\ll }_{k}\sqrt{p}$
,
$1\leqslant i\leqslant n$
. For
$k=2$
, Theorem 1.1 gives a small solution for
$n\geqslant 12$
. For
$k=3$
, the inequality in (2.3) gives a small solution for
$n\geqslant 9$
, while for
$k=4$
it yields a small solution for
$n\geqslant 17$
. Thus for
$k\leqslant 4$
and
$n\geqslant 5k+3$
, there is small solution. Suppose now that
$k\geqslant 5$
. Letting
$\unicode[STIX]{x1D700}=\frac{1}{2}-1/k$
in Theorem 1.2, we see that if
$n>\frac{3}{2}k\log (6ek/(k-2))+3$
then there exists a small solution. For
$k\geqslant 5$
,
$\frac{3}{2}\log (6ek/(k-2))\leqslant 4.96$
, and thus for
$n\geqslant 5k+3$
there is a small solution.◻
Remark 10.2. An alternate way of stating the corollary with a smaller constant on
$k$
is the following: for
$k\geqslant 3$
and
$n\geqslant 4.19k+6+6/(k-2)$
, there is a solution of (1.1) with
$1\leqslant {x_{i}\ll }_{k}\sqrt{p}$
.
Acknowledgement
The research of the third author was supported in part by NSA Young Investigator Grant #H98230-14-1-0164.
