1 Introduction
1.1 Motivation
The problem of distribution of elements of sets involving products and sums of intervals and arbitrary sets in finite fields has been a subject of extensive investigation (see, for example [Reference Bag and Shparlinski1–Reference Garaev and Shparlinski6, Reference Shparlinski9]). We continue studying this problem and consider some questions related to binary and ternary congruences modulo a sufficiently large prime number p, which involve products and inverses of elements from short intervals or arbitrary sets.
Let
$\mathbb {F}_p$
denote the finite field of residue classes modulo p. Throughout the paper, we always assume that
$\mathbb {F}_p$
is represented by the set
$\{0, 1, \ldots , p-1\}$
and we freely alternate between equations in
$\mathbb {F}_p$
and congruences modulo p. We also use
$\varepsilon>0$
to be an arbitrarily small real number.
Let
${\mathcal M}$
be an arbitrary subset of
$\mathbb {F}_p^*:=\mathbb {F}_p\setminus \{0\}$
with
$M=\#{\mathcal M}$
elements, let
${\mathcal X}\subseteq \mathbb {F}_p^*$
be an arbitrary interval of length H and let s be a fixed positive integer. It is known from [Reference Garaev and Shparlinski6] that if
$$ \begin{align*} H> p^{17/35+\varepsilon}, \quad M > p^{17/35+\varepsilon}. \end{align*} $$
then the number
$T_6(\lambda )$
of solutions of the congruence
$$ \begin{align*} \frac{m_1}{x_1^s}+ \frac{m_2}{x_2^s}+ \frac{m_3}{x_3^s}+\frac{m_4}{x_4^s}+ \frac{m_5}{x_5^s}+\frac{m_6}{x_6^s} \equiv \lambda\bmod p \quad\text{with } m_i\in {\mathcal M}, \, x_i \in {\mathcal X}, \, i =1, \ldots, 6, \end{align*} $$
satisfies
$$ \begin{align*} T_6(\lambda)=\frac{H^6 M^6}{p}(1+O(p^{-\delta})), \end{align*} $$
where
$\delta> 0$
depends only on s and
$\varepsilon $
. In [Reference Garaev and Shparlinski6, Section 1.2], an open question has been posed to obtain an asymptotic formula for the five-term analogue of
$T_6(\lambda )$
with
$H= M = o(p^{1/2})$
.
1.2 Main results
The first result of our present paper deals with the solubility problem of the corresponding congruence with three summands, assuming that the set
${\mathcal X}$
starts from the origin. Although our result does not provide an asymptotic formula, we can still prove the existence of solutions.
In what follows, we use
${\mathcal H}$
to denote the set of the first H positive integers: that is,
$$ \begin{align*} {\mathcal H}=\{1,2,\ldots, H\}. \end{align*} $$
We also recall that
${\mathcal M}$
is an arbitrary subset of
$\mathbb {F}_p^*$
with
$M=\#{\mathcal M}$
elements.
Theorem 1.1. Let
$M= \lfloor p^{14/29}\rfloor $
and
$H=\lfloor p^{14/29+\varepsilon }\rfloor $
. Then any integer
$\lambda $
can be represented in the form
$$ \begin{align*} \frac{m_1}{x_1^s}+\frac{m_2}{x_2^s}+\frac{m_3}{x_3^s}\equiv \lambda \bmod p \quad m_i\in {\mathcal M}, \, x_i\in{\mathcal H}, \, i=1,2,3. \end{align*} $$
We note that the problem of obtaining an asymptotic formula for the number of representations of
$\lambda $
in the form given by Theorem 1.1 is still an open problem.
We now consider the problem of solubility of the corresponding congruence with two summands, with M and H of the critical size
$p^{1/2+o(1)}$
. The case
$s\geqslant 2$
turns out to be very hard and currently we cannot say much about it. Here, we restrict ourselves to the case
$s=1$
.
If
${\mathcal M}$
is a set of M consecutive integers, then the question is reduced to the problem of the ratio of two intervals. This problem was considered in [Reference Garaev3–Reference Garaev and Karatsuba5]. In this case, it is known from the proof of [Reference Garaev and Karatsuba5, Theorem 1.7] and [Reference Garaev and Garcia4, Lemma 5] that if
$M>cp^{1/2}, H>cp^{1/2}$
, then, for some suitable positive constant c, any integer
$\lambda $
can be represented in the form
$$ \begin{align*} \frac{m_1}{x_1}+\frac{m_2}{x_2}\equiv \lambda \bmod p, \end{align*} $$
with
$m_1, m_2\in {\mathcal M}$
and
$x_1, x_2\in {\mathcal H}$
. However, the method of the aforementioned works does not apply for arbitrary sets
${\mathcal M}$
.
Our next result deals with a binary congruence for arbitrary sets
${\mathcal M}\subseteq \mathbb {F}_p^*$
for almost all prime moduli p. As usual, we denote the number of primes not exceeding X by
$\pi (X)$
.
Theorem 1.2. Let
$0<\varepsilon <0.1$
and let
$X \geqslant 2$
. The following holds for all but
$\pi (X)/X^{0.01\varepsilon }$
primes
$p\leqslant X$
. Let
$M= \lfloor {p^{1/2}}\rfloor $
and
$H=\lfloor { p^{1/2}(\log p)^{6+\varepsilon }}\rfloor $
. Then any integer
$\lambda $
can be represented in the form
$$ \begin{align*} \frac{m_1}{x_1}+\frac{m_2}{x_2}\equiv \lambda \bmod p,\quad m_i\in {\mathcal M}, \, x_i\in{\mathcal H}, \, i=1,2. \end{align*} $$
We now consider the binary problem with ratios of two intervals. First, we observe that if
$N<p^{1/2}$
, then all irreducible fractions
$$ \begin{align*} \frac{m}{x},\quad 1\leqslant m, x \leqslant N, \end{align*} $$
are distinct modulo p. Furthermore, the number of such fractions is asymptotically equal to
$6N^2/\pi ^2$
. (For the best known error term, see [Reference Walfisz10, Ch. V, Section 5, Equation (12)].) Hence, if
$N=\lfloor cp^{1/2}\rfloor $
, where
$c>\pi /\sqrt {12}$
, then
$$ \begin{align*} \#\bigg \{\frac{m}{x}\bmod p:~ 1\leqslant m, \ x \leqslant N\bigg \}>p/2 \end{align*} $$
and, by the pigeonhole principle, we get the representability of any integer
$\lambda $
in the form
$$ \begin{align*} \frac{m_1}{x_1}+\frac{m_2}{x_2}\equiv \lambda \bmod p, \end{align*} $$
with
$$ \begin{align*} 1\leqslant m_1,m_2,x_1,x_2\leqslant \Big\lfloor\sqrt{(\pi^2/12 +\varepsilon)p}\Big\rfloor. \end{align*} $$
Note that, generally speaking, the sizes of the intervals cannot be taken as
$o(p^{1/2})$
. Indeed, it is easy to see that the congruence
$$ \begin{align*} \frac{m_1}{x_1}+\frac{m_2}{x_2}\equiv -1\bmod p \end{align*} $$
has no solutions in positive integers
$m_1, m_2, x_1,x_2$
below
$\sqrt {p/3}$
. Moreover, the congruence
$$ \begin{align*} \frac{m_1}{x_1}+\frac{m_2}{x_2}\equiv 0\bmod p \end{align*} $$
has no solutions in positive integers
$m_1, m_2, x_1,x_2$
below
$\sqrt {p/2}$
.
We now consider the case of two arbitrary intervals. More precisely, let
${\mathcal I}$
and
${\mathcal J}$
be subsets of
$\mathbb {F}_p^*$
consisting of N consecutive integers. Then, it follows from [Reference Garaev and Garcia4, Reference Garaev and Karatsuba5] that the representability holds when
$N>cp^{1/2}$
for some suitable constant c.
Therefore, it is interesting to find the best possible constant c in the problem of binary congruences with a ratio of intervals. Here, following the argument of [Reference Garaev and Garcia4, Reference Garaev and Karatsuba5], we show that, for arbitrary intervals
${\mathcal I}$
and
${\mathcal J}$
of length
$\lfloor cp^{1/2}\rfloor $
, one can take
$c=\sqrt {8}$
.
Theorem 1.3. Let
${\mathcal I}$
and
${\mathcal J}$
be subsets of
$\mathbb {F}_p^*$
comprising
$\lfloor \sqrt {8p}\rfloor $
consecutive integers modulo p. Then any integer
$\lambda $
can be represented in the form
$$ \begin{align*} \frac{m_1}{x_1}+\frac{m_2}{x_2}\equiv \lambda \bmod p,\quad\text{with } m_1, m_2\in {\mathcal I}, \, x_1, x_2\in{\mathcal J}. \end{align*} $$
1.3 Notation and conventions
We recall that
$U = O(V)$
,
$U \ll V$
and
$V \gg U$
are all equivalent to the statement that
$|U| \leqslant c V$
holds with some constant
$c> 0$
.
Any implied constants in symbols O,
$\ll $
and
$\gg $
may occasionally, where obvious, depend on the integer parameters
$\ell $
and
$s,$
the real parameter
$\varepsilon>0$
and the fixed constant c, and are absolute otherwise.
Given two quantities U and
$V>0$
, we write
$U= o(V)$
and
$U = V^{o(1)}$
to mean that
$|U| \leqslant \psi (V)V$
and
$|U| \leqslant V^{\psi (V)}$
, respectively, for some function
$\psi $
such that
$\psi (V) \to 0$
as
$V \to \infty $
.
We also use
$U\lesssim V$
to mean that
$|U|< V p^{o(1)}$
.
Given a set
${\mathcal X}$
, we use
$|{\mathcal X}|$
to denote its cardinality.
For a positive integer N, as usual,
$\pi (N)$
denotes the number of primes
$p \leqslant N$
, while, for a real z and a prime p, we use the notation
${\mathbf {\,e}}_p(z) = \exp (2\pi i z/p)$
.
2 Auxiliary lemmas
We recall that s is a fixed positive integer constant,
${\mathcal M}\subseteq \mathbb {F}_p^*$
with
$M=|{\mathcal M}|<p^{1/2}$
and
${\mathcal H} =\{1,2,\ldots , H\}\bmod p$
.
Lemma 2.1. Assume that
$$ \begin{align*} M=|{\mathcal M}| < p^{1/2}, \quad H = |{\mathcal H}|<p^{1/2}. \end{align*} $$
Then, for the cardinality of the set
$$ \begin{align*} {\mathcal M}\cdot{\mathcal H}^{-s} =\{m h^{-s} \bmod p: m\in{\mathcal M},\ h\in{\mathcal H}\}, \end{align*} $$
we have the bound
$$ \begin{align*} |{\mathcal M}\cdot{\mathcal H}^{-s}| \gg \min \{M H/\!\log p, \, H^2/\!\log^2p\}. \end{align*} $$
Proof. Let J be the number of solutions of the congruence
$$ \begin{align*} m_1q_1^{-s}\equiv m_2q_2^{-s}\bmod p, \quad m_1, m_2\in{\mathcal M},\quad q_1,q_2\in {\mathcal R}, \end{align*} $$
where
${\mathcal R}$
is the set of primes from
${\mathcal H}$
. We have
$$ \begin{align} R=|{\mathcal R}|\gg \frac{H}{\log p}. \end{align} $$
We claim that,
$$ \begin{align*} J\leqslant s(M^2 + MR). \end{align*} $$
If
$m_1=m_2$
, then
$q_1^s\equiv q_2^s\bmod p$
and we have at most
$sM R$
possibilities in this case.
Let
$m_1\not =m_2$
be fixed. Denoting
$\lambda \equiv m_1m_2^{-1} \not \equiv 1 \pmod p$
, we have
$$ \begin{align} (q_1q_2^{-1})^s\equiv \lambda\bmod p. \end{align} $$
Clearly,
$ q_1 \ne q_2$
for each solution to (2.2). It follows that, for any fixed
$\lambda $
, there are at most s different values for
$q_1q_2^{-1}$
modulo p. But, for each such value of
$q_1 q_2^{-1}$
, the primes
$q_1$
and
$q_2$
are defined uniquely. Indeed, if there are two such pairs of primes
$q_1 \ne q_2$
and
$r_1 \ne r_2$
, then
$$ \begin{align*} q_1 r_2\equiv q_2 r_1\bmod p. \end{align*} $$
Since both sides are positive integers less than p, this congruence becomes an equality
$q_1 r_2 = q_2 r_1$
, which implies that
$q_1=r_1$
and
$q_2=r_2$
. Therefore, when
$m_1\not =m_2$
, and thus
$\lambda \ne 1$
, the congruence (2.2) has at most s solutions
$(q_1,q_2)$
, which leads to the term
$sM^2$
in the bound on J.
Now we use the standard relationship between the number of solutions and the cardinalities, which follows from the Cauchy-Schwarz inequality: that is,
$$ \begin{align*} \sum_{m \in {\mathcal M}} \sum_{q \in {\mathcal R}} 1 = \sum_{\lambda\in {\mathcal M}\cdot{\mathcal R}^{-s}} \mathop{\quad \sum \ \sum}_{\substack{m \in {\mathcal M}, \ q \in {\mathcal R}\\ mq^{-s}\equiv \lambda \bmod p}} 1 \leqslant \sqrt {|{\mathcal M}\cdot{\mathcal R}^{-s}| J}, \end{align*} $$
where
${\mathcal R}^{-s} = \{q^{-s}:~q \in {\mathcal R}\}$
. We now derive that
$$ \begin{align*} |{\mathcal M}\cdot{\mathcal H}^{-s}|\geqslant |{\mathcal M}\cdot{\mathcal R}^{-s}|\geqslant \frac{s M^2R^2}{s(M^2+MR)}\gg \min\{R^2, MR\}, \end{align*} $$
which, together with (2.1), concludes the proof.
We also need the following result given by [Reference Garaev and Shparlinski6, Theorem 1.2].
Lemma 2.2. Let s be a fixed positive integer and let integers K and H be such that
$$ \begin{align*} 0<K+1<K+H<p. \end{align*} $$
Then, for any fixed positive integer
$\ell $
, the following bound holds:
$$ \begin{align*} \sum_{m\in{\mathcal M}}\bigg|\kern-2pt\sum_{K+1\leqslant x\leqslant K+H}{\mathbf{\,e}}_p(amx^{-s})\bigg|\lesssim HM\bigg(\frac{p}{MH^{2\ell/(\ell+1)}}+\frac{1}{M}\bigg)^{1/(2\ell)}. \end{align*} $$
Finally, we recall the following statement from [Reference Garaev3, Theorem 3]; we refer the reader to [Reference Iwaniec and Kowalski7, Ch. 3] or [Reference Montgomery and Vaughan8, Section 4.2] for the background on characters.
Lemma 2.3. Let c be a positive constant and let
$$ \begin{align*} Q= (\log X)^c, \quad \Delta> 0, \quad \Delta \to 0 \quad \text{as } X\to +\infty. \end{align*} $$
Then, for all but
$$ \begin{align*} O(X^{2c^{-1}-4(\log\Delta)(\log Q)^{-1}}e^{-{\log X}/{100c\log\log X}}) \end{align*} $$
positive integers
$k \leqslant X$
, the inequality
$$ \begin{align*} \bigg|\kern-4pt\sum_{\substack{q\leqslant Q\\q~\text{prime}}}\chi(q)\bigg|\leqslant \pi(Q)\Delta \end{align*} $$
holds for any primitive multiplicative character
$\chi $
modulo k.
We note that, for a prime modulus
$k=p$
, all nontrivial characters are primitive.
3 Proof of the theorems
Proof of Theorem 1.1.
Let
$$ \begin{align*} {\mathcal D}= {\mathcal M}\cdot{\mathcal H}^{-s}. \end{align*} $$
By Lemma 2.1,
$$ \begin{align*} |{\mathcal D}|\gg \min \{M H/\!\log p, \, H^2/\!\log^2p\} = MH/\!\log p. \end{align*} $$
It suffices to prove the solubility of the congruence
$$ \begin{align} d_1+d_2 + \frac{m}{x^s}\equiv \lambda \bmod p, \end{align} $$
with
$$ \begin{align*} d_1, d_2\in {\mathcal D},\quad m\in {\mathcal M}, \quad x\in{\mathcal H}. \end{align*} $$
Using the orthogonality of exponential functions and expressing the number T of solutions of (3.1) via exponential sums, we see that
$$ \begin{align*} T =\sum_{d_1\in{\mathcal D}}\sum_{d_2\in {\mathcal D}}\sum_{m\in{\mathcal M}}\sum_{x \in{\mathcal H}}\frac{1}{p}\sum_{a=0}^{p-1} {\mathbf{\,e}}_p(a(d_1+d_2+mx^{-s}-\lambda)). \end{align*} $$
Next, changing the order of summation and separating the term corresponding to
$a=0$
, we obtain
$$ \begin{align} T =\frac{1}{p}\sum_{a=0}^{p-1}\sum_{d_1\in{\mathcal D}}\sum_{d_2\in {\mathcal D}}\sum_{m\in{\mathcal M}}\sum_{x\in{\mathcal H}}{\mathbf{\,e}}_p(a(d_1+d_2+mx^{-s}-\lambda)) =\frac{|D|^2HM}{p} +O(E), \end{align} $$
where
$$ \begin{align*} E& = \frac{1}{p}\bigg|\kern-2pt\sum_{a=1}^{p-1}\sum_{d_1\in{\mathcal D}}\sum_{d_2\in {\mathcal D}}\sum_{m\in{\mathcal M}}\sum_{x\in{\mathcal H}}{\mathbf{\,e}}_p(a(d_1+d_2+mx^{-s}-\lambda))\bigg| \\ & \leqslant \frac{1}{p} \sum_{a=1}^{p-1}\bigg|\kern-2pt\sum_{d\in{\mathcal D}}{\mathbf{\,e}}_p(ad)\bigg|^2\bigg|\kern-2pt\sum_{m\in{\mathcal M}}\sum_{x\in{\mathcal H}}{\mathbf{\,e}}_p(amx^{-s})\bigg|. \end{align*} $$
From Lemma 2.2 with
$\ell =3$
,
$$ \begin{align*} \bigg|\kern-2pt\sum_{m\in{\mathcal M}}\sum_{x\in{\mathcal H}}{\mathbf{\,e}}_p(amx^{-s})\bigg|\lesssim HM \bigg(\frac{p}{MH^{3/2}}+\frac{1}{M}\bigg)^{1/6}. \end{align*} $$
Observing that
$$ \begin{align*} \frac{p}{MH^{3/2}}+\frac{1}{M}\ll \frac{p}{MH^{3/2} } \quad\text{and}\quad \sum_{a=0}^{p-1}\bigg|\kern-2pt\sum_{d\in{\mathcal D}}{\mathbf{\,e}}_p(ad)\bigg|^2 = p |D|, \end{align*} $$
we get
$$ \begin{align*} E&\lesssim HM\frac{p^{1/6}}{p M^{1/6}H^{1/4}}\sum_{a=0}^{p-1}\bigg|\kern-2pt\sum_{d\in{\mathcal D}}{\mathbf{\,e}}_p(ad)\bigg|^2 \\ & = HM\frac{p^{1/6}}{ M^{1/6}H^{1/4}} |D|=\frac{|D|^2HM}{p}\times\Delta, \end{align*} $$
where
$$ \begin{align*} \Delta =\frac{p^{7/6}}{|D|M^{1/6}H^{1/4}}<p^{-0.1\varepsilon}. \end{align*} $$
Inserting this into (3.2), yields
$$ \begin{align*} T=(1+ o(1))\frac{|D|^2HM}{p}, \end{align*} $$
and the result follows.
Proof of Theorem 1.2.
In Lemma 2.3, we take
$$ \begin{align*} c=6+\varepsilon,\quad Q=(\log X)^{6+\varepsilon},\quad \Delta=(\log X)^{-1-0.1\varepsilon}. \end{align*} $$
Then we have at most
$O(X^{1-0.6\varepsilon /(6+\varepsilon )})$
exceptional positive integers
$k\leqslant X$
. Hence, for
$\pi (X)(1+O(X^{-0.05\varepsilon }))$
primes p with
$X^{1/2}< p\leqslant X$
, the inequality
$$ \begin{align} \bigg|\kern-2pt\sum_{q\leqslant Q}\chi(q)\bigg|\leqslant \pi(Q)(\log X)^{-1-0.1\varepsilon} \end{align} $$
holds for any nonprincipal character
$\chi $
modulo p.
Let
$$ \begin{align*} {\mathcal D} = \{m/h:~m\in {\mathcal M},\ h\in \{1, \ldots, \lfloor{0.01p^{1/2}}\rfloor\}\}. \end{align*} $$
Note that if
$X^{1/2}<p\leqslant X$
,
$h\leqslant [0.01p^{1/2}]$
and
$q\leqslant (\log X)^{6+\varepsilon }$
, then
$hq\leqslant p^{1/2}(\log p)^{6+\varepsilon }$
.
We now prove that if (3.3) holds for some
$p\ \mathrm{with}\ X^{1/2}<p\leqslant X$
, then the cardinality of the set
$$ \begin{align*} {\mathcal G} =\{d/q\bmod p :~d\in {\mathcal D}, \ q\leqslant (\log X)^{6+\varepsilon}\} \end{align*} $$
satisfies
$$ \begin{align} |{\mathcal G}| = (1+o(1))p. \end{align} $$
This implies that
$$ \begin{align*} {\mathcal G}+{\mathcal G} =\mathbb{F}_p, \end{align*} $$
which, together with
${\mathcal G}\subseteq {\mathcal M}/{\mathcal H}\bmod p$
, yields the desired result.
By Lemma 2.1,
$$ \begin{align} |{\mathcal D}|\gg \frac{p}{\log^2 p}. \end{align} $$
Let
${\mathcal G}^{c}=\mathbb {F}_p^*\setminus {\mathcal G}$
. Thus, (3.4) is equivalent to
$|{\mathcal G}^{c}|=o(p)$
.
By the definition of
${\mathcal G}$
, there is no solution to the congruence
$$ \begin{align*} d\equiv q y \bmod p,\quad d\in{\mathcal D}, \, q\leqslant Q,\, y\in {\mathcal G}^c. \end{align*} $$
Hence, using the orthogonality of multiplicative characters and expressing the number of solutions (which is zero) via sums of characters
$\chi $
modulo p,
$$ \begin{align*} 0= \sum_{d\in{\mathcal D}}\sum_{q\leqslant Q}\sum_{y\in {\mathcal G}^c} \frac{1}{p-1}\sum_{\chi \bmod p} \chi(d^{-1}qy). \end{align*} $$
Changing the order of summation and separating the term that corresponds to the principal character
$\chi =\chi _0$
, we derive
$$ \begin{align*} \pi(Q)\cdot |{\mathcal D}|\cdot |{\mathcal G}^c|\leqslant \sum_{\chi\not=\chi_0}\bigg|\kern-2pt\sum_{q\leqslant Q}\chi(q)\bigg|\bigg|\kern-2pt\sum_{y\in {\mathcal G}^c}\chi(y)\bigg|\bigg|\kern-2pt\sum_{d\in {\mathcal D}}\chi(d^{-1})\bigg|. \end{align*} $$
Using (2.3) to estimate the sum over
$q\leqslant Q$
, and then following the standard procedure with an application of the Cauchy–Schwarz inequality, yields
$$ \begin{align} \pi(Q)\cdot |{\mathcal D}|\cdot |{\mathcal G}^c|\leqslant \pi(Q)(\log X)^{-1-0.1\varepsilon}T_1^{1/2}T_2^{1/2}, \end{align} $$
where
$$ \begin{align*} T_1=\sum_{\chi \bmod p} \bigg|\kern-2pt\sum_{y\in {\mathcal G}^c}\chi(y)\bigg|^2=(p-1)|{\mathcal G}^c| \end{align*} $$
and
$$ \begin{align*} T_2= \sum_{\chi \bmod p} \bigg|\kern-2pt\sum_{d\in {\mathcal D}}\chi(d^{-1})\bigg|^2=(p-1)|{\mathcal D}|. \end{align*} $$
Therefore, from (3.6),
$$ \begin{align*} |{\mathcal D}||{\mathcal G}^c|\leqslant (p-1)(\log X)^{-1-0.1\varepsilon}|{\mathcal D}|^{1/2}|{\mathcal G}^c|^{1/2}. \end{align*} $$
Thus,
$$ \begin{align*} |{\mathcal G}^c|\leqslant \frac{p^2}{|{\mathcal D}|(\log X)^{2+0.2\varepsilon}}. \end{align*} $$
This, together with (3.5), implies that
$$ \begin{align*} |{\mathcal G}^c|\ll \frac{p}{(\log X)^{0.2\varepsilon}}=o(p), \end{align*} $$
and thus establishes (3.4) and finishes the proof of Theorem 1.2.
Remark 3.1. It is well known that, under the generalised Riemann hypothesis (GRH) a version of Lemma 2.3 holds for all moduli (see [Reference Montgomery and Vaughan8, Equation (13.21)]). Thus, under the GRH, we have a version of Theorem 1.2 that holds for all sufficiently large p.
Proof of Theorem 1.3.
Let
$$ \begin{align*} {\mathcal I}=\{L+1,\ldots, L+\lfloor\sqrt{8p}\rfloor\} \quad \text{and}\quad {\mathcal J}=\{K+1,\ldots, K+\lfloor\sqrt{8p}\rfloor\}. \end{align*} $$
Denote
$$ \begin{align*} {\mathcal W}= \{m/x\bmod p: m\in{\mathcal I},\ x\in{\mathcal J}\}, \end{align*} $$
and let
${\mathcal W}^c=\mathbb {F}_p\setminus {\mathcal W}$
. It suffices to prove that
$|{\mathcal W}^c|<p/2$
. Indeed, in this case,
$|{\mathcal W}|>p/2$
and the claim then follows from the pigeonhole principle.
Let
$N =\lfloor \sqrt {2p}\rfloor $
and note that
$2N\leqslant \lfloor \sqrt {8p}\rfloor $
. Clearly, for
$t\in {\mathcal W}^c$
, there is no solution to the congruence
$$ \begin{align*} m_1+m_2\equiv (x_1+x_2)t\bmod p, \end{align*} $$
with positive integers
$m_1,m_2,x_1,x_2$
satisfying
$$ \begin{align*} m_1\in [L+1, L+N], \quad x_1\in [K+1, K+N],\quad m_2\leqslant N,\quad x_2\leqslant N. \end{align*} $$
As in the proof of Theorem 1.1, we write the number of solutions of this congruence (which is zero) in terms of exponential sums and see that
$$ \begin{align*} 0=\frac{1}{p}\sum_{a=0}^{p-1}\sum_{m_1=L+1}^{L+N} \sum_{m_2=1}^N\sum_{x_1=K+1}^{K+N} \sum_{x_2=1}^N\sum_{t\in{\mathcal W}^c} {\mathbf{\,e}}_p(a(m_1+m_2 -(x_1+x_2)t)). \end{align*} $$
Separating the term corresponding to
$a=0$
and following the standard procedure, we derive
$$ \begin{align} N^4|{\mathcal W}^c|\leqslant \sum_{a=1}^{p-1}S_1(a)S_2(a)\bigg(\sum_{t\in {\mathcal W}^c}T_1(at)T_2(at)\bigg), \end{align} $$
where
$$ \begin{align*} S_1(a)=\bigg|\kern-2pt\sum_{m_1=L+1}^{L+N} {\mathbf{\,e}}_p(am_1)\bigg|, \quad S_2=\bigg|\kern-2pt\sum_{m_2=1}^Ne_p(am_2\bigg| \end{align*} $$
and
$$ \begin{align*} T_1(at)=\bigg|\kern-2pt\sum_{x_1=K+1}^{K+N} {\mathbf{\,e}}_p(-atx_1)\bigg|,\quad T_2(at)=\bigg|\kern-2pt\sum_{x_2=1}^N{\mathbf{\,e}}_p(-atx_2)\bigg|. \end{align*} $$
Now, we observe that
$$ \begin{align*} \sum_{t\in {\mathcal W}^c}T_1(at)T_2(at)\leqslant \sum_{t=0}^{p-1}T_1(at)T_2(at)=\sum_{t=0}^{p-1}T_1(t)T_2(t). \end{align*} $$
Therefore, applying the Cauchy–Schwarz inequality, we obtain
$$ \begin{align*} \sum_{t\in {\mathcal W}^c}T_1(at)T_2(at) \leqslant \bigg(\sum_{t=0}^{p-1}T_1^2(t)\bigg)^{1/2}\bigg(\sum_{t=0}^{p-1}T_2^2(t)\bigg)^{1/2}=pN. \end{align*} $$
Analogously,
$$ \begin{align*} \sum_{a=1}^{p-1}S_1(a)S_2(a)= \sum_{a=0}^{p-1}S_1(a)S_2(a) - N^2\leqslant pN-N^2. \end{align*} $$
Inserting these estimates into (3.7), we derive
$$ \begin{align*} |{\mathcal W}^c|\leqslant \frac{(p-N)p}{N^2}=\frac{p}{2}\cdot\frac{2p-2N}{N^2}. \end{align*} $$
Since
$N^2+2N = (N+1)^2- 1> 2p -1$
and
$N^2+2N\not = 2p$
, we see that
$$ \begin{align*} N^2>2p-2N, \end{align*} $$
which implies that
$|{\mathcal W}^c|<p/2$
.
