| Sbornik: Mathematics |
|
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers) Distribution of Korobov-Hlawka sequences A. A. Illarionov Khabarovsk Division of the Institute for Applied Mathematics, Far Eastern Branch, Russian Academy of Sciences, Khabarovsk, Russia
Bibliographic databases:
     § 1. IntroductionLet $N$ be a positive integer, and let $a_1, \dots, a_s$ be integers. For the approximate calculation of multiple integrals by means of quadrature formulae on the unit $s$-dimensional cube $[0, 1]^s$, Korobov [1] and Hlawka [2] proposed (independently) to use grids of the form
$$
\begin{equation*}
K_N(a)=\biggl\{ \biggl( \biggl\{\frac{a_1k}{N}\biggr\},\dots, \biggl\{\frac{a_sk}{N}\biggr\} \biggr)\colon k=1,\dots,N\biggr\}.
\end{equation*}
\notag
$$
This idea turned out to be fruitful. It gave rise to a whole direction at the intersection of number theory and computational mathematics (see [3]–[5]). Recall that the discrepancy $D(X)$ of a finite set $X\subset [0,1)^s$ from the uniform distribution is defined by
$$
\begin{equation*}
D(X)=\sup_{\Pi} \biggl| \frac{\# (X\cap \Pi)}{\# X}-\operatorname{meas} \Pi \biggr|,
\end{equation*}
\notag
$$
where the least upper bound is taken over all parallelepipeds $\Pi=[x_1,x_1') \times \dots \times [x_s,x_s')$ such that $0\leqslant x_j < x_j'<1$, $j=1,\dots,s$. Here and below $\# X$ denotes the cardinality of the set $X$. From the theoretic and practical points of view, it is reasonable to construct sequences with small discrepancy (see [3]–[5]). If $s=1$ and $\operatorname{\textrm{gcd}} (a_1,N)=1$, then $D(K_N(a_1))=1/N$. The study of the quantity $D(K_N(a))$ becomes much more complicated for $s\geqslant 2$. The well-known upper bound
$$
\begin{equation*}
\mathfrak D^{(s)}_N \equiv \min_{a\in \mathbb Z_N^s} D(K_N(a)) \underset{s}\ll \frac{\ln^s N}{ N}
\end{equation*}
\notag
$$
was obtained by Korobov [3] for any prime number $N$ and by Niederreiter [6] for any integer $N>1$. Larcher [7] proved that
$$
\begin{equation*}
\mathfrak D^{(2)}_N \ll \frac{\ln N}{\varphi(N)} \ln\ln N ,
\end{equation*}
\notag
$$
where $\varphi(N)$ is the Euler function. The best upper bound was obtained by Bykovskii [8]. It has the form
$$
\begin{equation*}
\mathfrak D^{(s)}_N \underset{s}\ll \frac{\ln ^{s-1} N}{N} \ln\ln N.
\end{equation*}
\notag
$$
There are reasons to suppose that
$$
\begin{equation*}
\mathfrak D^{(s)}_N \underset{s}\gg \frac{\ln ^{s-1} N}{N}.
\end{equation*}
\notag
$$
For $s=2$ this inequality follows from Schmidt’s theorem (see [9]). For $s>2$ the best lower bound follows from the results of [10]. It has the form
$$
\begin{equation*}
\mathfrak D^{(s)}_N\underset{s}\gg\frac{(\ln N)^{(s-1)/2+\eta(s)}}{N} \quad \text{for } s\geqslant 3,
\end{equation*}
\notag
$$
where $\eta(s)$ is a positive constant depending only on $s$. For any $x\in \mathbb Z^s$ we set and for every $a\in \mathbb Z^s\setminus\{0\}$ we set where the minimum is taken over all nontrivial solutions $x\in \mathbb Z^s\setminus\{0\}$ of the congruenceThe parameter $q_N(a)$ was introduced by Bakhvalov [11] and Hlawka [2]. It characterizes the ‘irregularity’ of the sequence $K_N(a)$. For example, the following bounds hold (see [5], § 5.1):
$$
\begin{equation}
\frac{1}{q_N(a)} \underset{s}\ll D(K(a,N)) \underset{s}\ll \frac{\ln^s N}{q_N(a)}.
\end{equation}
\tag{1.2}
$$
Therefore, it is reasonable to choose points $a\in \mathbb Z^s$ with large $q_N(a)$. By Minkowski’s convex body theorem $q_N(a) \leqslant N/2$ (see [5], § 5.1). We take any number $a_1\in \mathbb Z$ such that $\operatorname{\textrm{gcd}} (a_1,N)=1$. Let $a_1/N=[b_0;b_1,\dots,b_k]$ be the expansion of the rational number $a_1/N$ in a continued fraction (the $b_j$ are the partial quotients). As is well known (see [5], Theorem 5.17),
$$
\begin{equation}
q_N(a) \asymp N \Bigl( \max_{1\leqslant i\leqslant k} b_i \Bigr)^{-1} \quad\text{for } a=(a_1,1).
\end{equation}
\tag{1.3}
$$
Korobov, as well as other authors, stated repeatedly the conjecture that for some absolute constant $C$ and any positive integer $N$ there exists $a_1$, $\operatorname{\textrm{gcd}} (a_1, q)=1$, such that $b_j \leqslant C$ for all $j$. This is widely known as ‘Zaremba’s conjecture’ and has yet to be proved. If Zaremba’s conjecture is true, then, according to (1.3), However, the best known bound has the form
$$
\begin{equation*}
\max_{a\in \mathbb Z^s} q_N(a) \underset{s}\gg \frac{N}{\ln^{s-1} N} \qquad (s\geqslant 2).
\end{equation*}
\notag
$$
It was proved by Bakhvalov [11] and (independently) Hlawka [12] for any prime number $N$ and by Zaremba [13] for an arbitrary integer $N>1$. The main results of our paper are as follows. Let $\mathbb Z_N$ be the complete system and $\mathbb Z^*_N$ be the reduced system of residues modulo $N$. Theorem 1. Let $s \geqslant 3$, $N \in \mathbb N$, $\lambda \in [1,+\infty)$, $N > 1$ and $\ln \lambda \ll_s \ln\ln N$. Then Corollary 1. Let the conditions of Theorem 1 hold. Then Theorem 2. For any integer $s\geqslant 3$ there is a positive constant $C(s)$ depending only on $s$ such that, if $N\in \mathbb N$ and $\lambda\in [1,+\infty)$, where $N\geqslant 3$ and $\ln\lambda \ll_s \ln\ln N$, then The proofs of Theorems 1 and 2 use Markov’s and Chebyshev’s inequalities. Corollary 1 follows from Theorem 1 and relations (1.2). In the proof of Theorem 2, Bykovskii’s inequality for $D(K_N(a))$ (see [8], Theorem 1, or bound (5.3) below) also plays an important role. Theorem 2 and Corollary 1 imply that
$$
\begin{equation*}
\frac{\ln^{s-1} N}{N\ln\ln N} \underset{s}\ll D(K_N(a)) \underset{s}\ll \frac{\ln^{s-1} N}{N} \ln\ln N
\end{equation*}
\notag
$$
for ‘almost all’ $a\in (\mathbb Z_N^*)^s$. Remark 1. In the proofs given below the condition $s>2$ is essential. Let $s=2$. Then (1.5) follows from the results of [14]. By (1.3) and [15], Theorem 1, Remark 2. Theorem 2 was proved by this author in [16] for any prime integer $N$. The case of composite $N$ has turned out to be much more complicated. Remark 3. For $\alpha=(\alpha_1,\dots,\alpha_s) \in \mathbb R^s$ and $n\in \mathbb N$ write The rest of the paper consists of four sections. In § 2 we derive asymptotic formulae for the number of solutions of some congruences. These results are used in § 3 to investigate the distribution of solutions of congruence (1.1). The proof of Theorem 1 is presented in § 4 and the proof of Theorem 2 in § 5. § 2. Number of solutions of some congruencesThe aim of this section is to prove Corollaries 2 and 3. We use the following notation. The expression
$$
\begin{equation*}
f(x) \ll g(x) \quad (\text{or } f(x)=O(g(x))) \quad \text{for } x\in X
\end{equation*}
\notag
$$
means that there exists a positive absolute constant $C$ such that $|f(x)| \leqslant C \cdot g(x)$ for all $x\in X$. If $C$ depends on a parameter $\theta$, then we write $f(x) \ll_{\theta} g(x)$ (or $f(x)=O_\theta(g(x))$). The notation $f\asymp g$ means that $f\ll g\ll f$. For any $n\in \mathbb Z$ and $m \in \mathbb N$ we set
$$
\begin{equation*}
\delta_m(n)=\begin{cases} 1 & \text{for } n\equiv 0 \pmod m, \\ 0 & \text{for } n\not\equiv 0 \pmod m. \end{cases}
\end{equation*}
\notag
$$
Let $e(z)=e^{2\pi i z}$ for all $z\in \mathbb C$. The following formulae are well known:
$$
\begin{equation}
\sum_{n\in \mathbb Z_N} e\biggl(\frac{mn}{N}\biggr)=N \delta_N(m),
\end{equation}
\tag{2.1}
$$
$$
\begin{equation}
\sum_{n\in \mathbb Z_N^*} e\biggl(\frac{mn}{N}\biggr) =N \sum_{d\mid N} \frac{\mu(d)}{d}\delta_{N/d}(m).
\end{equation}
\tag{2.2}
$$
Here and below $\mu(d)$ denotes the Möbius function and $N\in \mathbb N$, $N\geqslant 3$. If $\Omega\subset \mathbb R^s$, then is a sum over all $x\in \mathbb Z^s\cap \Omega$ such that $x\neq 0$.We denote by $a\cdot x$ the standard inner product of the vectors $a$ and $x$. Lemma 1 (see [8], Lemma 10). Let $s\geqslant 2$, $l\in \mathbb Z$ and $P_1,\dots,P_s \in [1,N]$. Then Lemma 2. If $P\in \{1,2,\dots, N\}$, $c\in \mathbb Z$, then where Proof. We define the function by
$$
\begin{equation*}
\chi(t)=\begin{cases} 1 & \text{if } t\in [P,2P), \\ 0 & \text{if } t \not\in [P,2P). \end{cases}
\end{equation*}
\notag
$$
Using the discrete Fourier transform we obtain
$$
\begin{equation*}
\chi(t)=\sum_{-N/2 < k\leqslant N/2 } F(k) e\biggl(\frac{kt}N\biggr),
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
F(k)=\frac{1}{N} \sum_{P\leqslant n< P+N} \chi(n) e\biggl(-\frac{kn}N\biggr) =\frac{1}{N} \sum_{P\leqslant n< 2P} e\biggl(-\frac{kn}N\biggr).
\end{equation*}
\notag
$$
It can readily be seen that and
$$
\begin{equation*}
|F(k)| =\frac{1}{N}\biggl|\frac{1- e(-kP/N)}{1-e(-k/N)}\biggr| =\frac{1}{N}\biggl|\frac{\sin(\pi P k/N)}{\sin(\pi k/N)} \biggr| \leqslant\frac{1}{2|k|}, \qquad k\neq 0.
\end{equation*}
\notag
$$
Therefore,
$$
\begin{equation*}
\begin{aligned} \, \sum_{t=P}^{2P-1} \delta_N(t+c) &=\sum_{t=P}^{P+N-1}\chi(t) \delta_N(t+c) =\sum_{t=P}^{P+N-1} \sum_{-N/2 < k\leqslant N/2 } F(k) e\biggl(\frac{kt}{N}\biggr) \delta_N(t+c) \\ &=\sum_{-N/2<k\leqslant N/2} F(k)\sum_{t\in \mathbb Z_N} e\biggl(\frac{kt}{N}\biggr) \delta_N(t+c) \\ &=\sum_{-N/2 < k\leqslant N/2 } F(k) e\biggl(\frac{-ck}{N}\biggr) =\frac{P}{N}+\mathop{{\sum}'}_{-N/2 < k\leqslant N/2 } F(k) e\biggl(\frac{-kc}{N}\biggr). \end{aligned}
\end{equation*}
\notag
$$
This completes the proof of Lemma 2. For every $s\geqslant 2$, $l\in \mathbb Z$ and $P=(P_1,\dots,P_s)\in \mathbb N^s$ set
$$
\begin{equation*}
\mathcal A_N^{(s)}(P;l)=\sum_{a\in (\mathbb Z_N^*)^s} \sum_{P_1\leqslant x_1< 2 P_1}\dotsb \sum_{P_s\leqslant x_s< 2 P_s} \delta_N(a\cdot x-l).
\end{equation*}
\notag
$$
In other words, $\mathcal A_N^{(s)}(P;l)$ is the number of solutions $(a,x)\in (\mathbb Z_N^*)^s\,{\times}\, \mathbb Z^s$ of the problem
$$
\begin{equation*}
a_1x_1+\dots+a_s x_s \equiv l \pmod N, \qquad P_j\leqslant x_j< 2P_j, \quad j=1,\dots, s.
\end{equation*}
\notag
$$
Let $\tau(N)=\sum_{d\mid N} 1$ be the number of positive integer divisors of $N$. Lemma 3. Let $s\geqslant 2$, $l\in \mathbb Z$, $P=(P_1,\dots,P_s) \in \mathbb N^s$ and $P_j\leqslant N$, $j=1,\dots, s$. Then Proof. Without loss of generality assume that $P_1\,{=}\max\{P_1,\dots, P_s\}$.
Let $s=2$. It is obvious that
$$
\begin{equation*}
\mathcal A_N^{(2)}(P;l)=\sum_{a_1,a_2\in \mathbb Z_N^*} \sum_{P_1\leqslant x_1 < 2P_1}\sum_{P_2\leqslant x_2 < 2P_2} \delta_N(x_1+a_2x_2 -a_1 l).
\end{equation*}
\notag
$$
By Lemma 2
$$
\begin{equation*}
\sum_{P_1 \leqslant x_1 < 2P_1} \delta_N(x_1+a_2 x_2 -l a_1) =\frac{P_1}{N}+\mathop{{\sum}'}_{-N/2 < k\leqslant N/2 } F(k) e\biggl(\frac{k(-a_2 x_2+a_1 l)}{N}\biggr),
\end{equation*}
\notag
$$
where $|F(k)| \leqslant 1/|2k|$. Thus,
$$
\begin{equation}
\mathcal A_N^{(2)}(P;l)=\frac{\varphi^2(N)}{N} P_1P_2+S,
\end{equation}
\tag{2.4}
$$
where
$$
\begin{equation*}
S=\sum_{P_2\leqslant x_2< 2P_2} \sum_{a_1,a_2\in \mathbb Z_N^*} \mathop{{\sum}'}_{-N/2 < k\leqslant N/2 } F(k) e\biggl(\frac{-ka_2 x_2}{N}\biggr)e\biggl(\frac{k a_1 l}{N}\biggr).
\end{equation*}
\notag
$$
Summing over $a_2\in \mathbb Z_N^*$ we have (see (2.2))
$$
\begin{equation*}
S=N \sum_{P_2\leqslant x_2< 2P_2}\sum_{a_1\in \mathbb Z_N^*} \sum_{d\mid N} \frac{\mu(d)}{d} \mathop{{\sum}'}_{-N/2 < k\leqslant N/2 } F(k) \delta_{N/d}(kx_2) e\biggl(\frac{k a_1 l}{N}\biggr).
\end{equation*}
\notag
$$
Taking the inequalities $|F(k)|\leqslant |2k|^{-1}$, $|e(z)|\leqslant 1$ and $|\mu(d)|\leqslant 1$ into account we arrive at the bound
$$
\begin{equation*}
|S| \leqslant N\varphi(N) \sum_{d\mid N} \frac{1}{d}\sum_{P_2\leqslant x_2< 2P_2} \mathop{{\sum}'}_{-N/2 < k\leqslant N/2 } \frac{\delta_{N/d}(k x_2)}{2|k|}.
\end{equation*}
\notag
$$
If $r=\operatorname{\textrm{gcd}} (x_2, N/d)$, then
$$
\begin{equation*}
\mathop{{\sum}'}_{-N/2 < k\leqslant N/2 } \frac{\delta_{N/d}(k x_2)}{2|k|} \leqslant\sum_{1\leqslant k \leqslant N/2} \frac{\delta_{N/dr}(k)}{k} \leqslant\frac{dr}{N} \sum_{1\leqslant k'\leqslant dr/2} \frac{1}{k'} \ll \frac{dr}{N}\ln N.
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
\begin{aligned} \, S &\ll \varphi(N) \ln N \sum_{d\mid N} \sum_{P_2\leqslant x_2 < 2 P_2} \operatorname{\textrm{gcd}} \biggl(x_2, \frac Nd\biggr) \\ &\ll\varphi(N) \ln N \sum_{d\mid N} \sum_{r\mid (N/d)} r \sum_{P_2\leqslant x_2 < 2 P_2} \delta_r(x_2) \\ &\ll\varphi(N) \ln N \sum_{d\mid N} \sum_{r\mid (N/d)} P_2 \leqslant\varphi(N) P_2 \tau^2(N)\ln N. \end{aligned}
\end{equation*}
\notag
$$
Using the last inequality and (2.4) we conclude that
$$
\begin{equation}
\mathcal A_N^{(2)}(P;l)=\frac{\varphi^2(N)}{N} P_1P_2 +O\bigl( \varphi(N) P_2 \tau^2(N)\ln N\bigr).
\end{equation}
\tag{2.5}
$$
Now let $s\geqslant 3$. It is clear that
$$
\begin{equation*}
\mathcal A_N^{(s)}(P;l)=\sum_{a_3,\dots, a_s \in \mathbb Z_N^*} \sum_{\substack{P_j\leqslant x_j < 2 P_j\\ 3\leqslant j\leqslant s}} \mathcal A_N^{(2)}(P_1,P_2; l -a_3 x_3 -\dots-a_s x_s).
\end{equation*}
\notag
$$
Taking (2.5) into account we obtain
$$
\begin{equation*}
\mathcal A_N^{(s)}(P;l)=\biggl(\frac{\varphi^2(N)}{N} P_1P_2 +O\bigl( \varphi(N) P_2 \tau^2(N)\ln N\bigr)\biggr) \varphi^{s-2}(N) P_3\dotsb P_s.
\end{equation*}
\notag
$$
This completes the proof of Lemma 3. Corollary 2. Let $s\geqslant 2$, $l\in \mathbb Z$, $P=(P_1,\dots,P_s) \in \mathbb N^s$ and Then Corollary 2 follows from Lemma 3 and the well-known bound We take arbitrary $f,g\in \mathbb Z$, $P=(P_1,\dots,P_s)\in \mathbb N^s$ and $Q=(Q_1,\dots,Q_s)\in \mathbb N^s$. Let $\mathcal B^{(s)}_N(P,Q;f,g)$ be the number of tuples $(a,x,y) \in (\mathbb Z_N^*)^s\times \mathbb Z^s\times \mathbb Z^s$ such that
$$
\begin{equation}
a_1 x_1+\dots+a_s x_s \equiv f \pmod N, \qquad a_1 y_1+\dots+a_s y_s \equiv g \pmod N,
\end{equation}
\tag{2.7}
$$
$$
\begin{equation}
P_j\leqslant x_j < 2P_j, \quad Q_j\leqslant y_j < 2Q_j, \qquad j=1,\dots,s,
\end{equation}
\tag{2.8}
$$
$$
\begin{equation}
\text{the vectors $x$ and $y$ are linearly independent over $\mathbb R$.}
\end{equation}
\tag{2.9}
$$
Our aim is to obtain an asymptotic formula for $\mathcal B^{(s)}_N(P,Q;f,g)$. Let $\widehat{\mathcal B}^{(s)}_N(P,Q;f,g)$ be the number of tuples $(a,x,y) \in (\mathbb Z_N^*)^s\times \mathbb Z^s\times \mathbb Z^s$ satisfying (2.7), (2.8) and the additional condition
$$
\begin{equation}
x_i y_j \neq x_j y_i \quad \text{for all } 1\leqslant i < j \leqslant s.
\end{equation}
\tag{2.10}
$$
Proof. It suffices to prove that the number of tuples $(a,x,y) \in (\mathbb Z_N^*)^3\times \mathbb Z^3\times \mathbb Z^3$ satisfying (2.7)–(2.9) (for $s=3$) and the condition does not exceed
Let
$$
\begin{equation}
r_x=\frac{\operatorname{\textrm{gcd}} (x_1,x_2)}{\operatorname{\textrm{gcd}} (x_1,x_2,y_1,y_2)}\quad\text{and} \quad r_y=\frac{\operatorname{\textrm{gcd}} (y_1,y_2)}{\operatorname{\textrm{gcd}} (x_1,x_2,y_1,y_2)}.
\end{equation}
\tag{2.12}
$$
Then $\operatorname{\textrm{gcd}} (r_x,r_y)=1$. By (2.11) and (2.12), Using (2.13) and (2.7) we obtain
$$
\begin{equation}
a_3 (r_y x_3-r_x y_3) \equiv l \pmod N, \qquad P_3 \leqslant x_3 < 2P_3, \quad Q_3 \leqslant y_3 < 2Q_3,
\end{equation}
\tag{2.14}
$$
where $l=r_y f -r_x g$. Formulae (2.13) and (2.9) imply the inequality
1. We take any coprime integers $r_x,r_y\in \mathbb N$. Let $G(r_x,r_y)$ be the number of tuples $(a_3,x_3,y_3)$ for which (2.14) and (2.15) hold. We claim that
$$
\begin{equation}
G(r_x,r_y) \ll (r_y P_3+r_x Q_3) \tau(N) \min\{P_3,Q_3\}.
\end{equation}
\tag{2.16}
$$
Without loss of generality assume that $P_3\geqslant Q_3$.
The number of $a_3\in \mathbb Z_N^*$ satisfying (2.14) for fixed $x_3$ and $y_3$ does not exceed $d=\operatorname{\textrm{gcd}} (N, r_yx_3 -r_x y_3)$. Hence
$$
\begin{equation*}
G(r_x,r_y) \leqslant\sum_{d\mid N, \, d\leqslant 2 (r_yP_3+r_x Q_3)} d S(d),
\end{equation*}
\notag
$$
where $S(d)$ is the number of pairs $(x,y)\in \mathbb Z^2$ such that
$$
\begin{equation}
r_y x-r_x y \equiv 0 \pmod d, \qquad P_3 \leqslant x < 2P_3\quad\text{and} \quad Q_3 \leqslant y < 2Q_3.
\end{equation}
\tag{2.17}
$$
Using (2.17) and the condition $\operatorname{\textrm{gcd}} (r_x,r_y)=1$ we see that $y$ is a multiple of $\operatorname{\textrm{gcd}} (r_y,d)$. Since $Q_3 \leqslant y < 2Q_3$, the number of such $y$ does not exceed $2Q_3 / \mathrm{\textrm{gcd}} (r_y,d)$. If $y$ is fixed, then the number of $x$ satisfying (2.17) does not exceed $P_3 \operatorname{\textrm{gcd}} (r_y,d) d^{-1}+1$. Therefore,
$$
\begin{equation*}
S(d) \leqslant\frac{2Q_3}{\operatorname{\textrm{gcd}} (r_y,d)} \biggl(\frac{P_3}{d} \operatorname{\textrm{gcd}} (r_y,d)+1\biggr) =\frac{2P_3 Q_3}{d}+\frac{2Q_3}{\operatorname{\textrm{gcd}} (r_y,d))}.
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
\begin{aligned} \, G(r_x,r_y) &\leqslant\sum_{\substack{d\mid N \\ d\leqslant 2 (r_yP_3+r_x Q_3)}} d \biggl(\frac{2P_3 Q_3}{d}+\frac{2Q_3}{\operatorname{\textrm{gcd}} (r_y,d))}\biggr) \\ &\leqslant 2P_3 Q_3 \tau(N)+4 (r_y P_3+r_x Q_3)\tau(N) Q_3. \end{aligned}
\end{equation*}
\notag
$$
Inequality (2.16) is proved.
2. Let $L=L(a_3,x_3,y_3,r_x,r_y)$ be the number of tuples $(a_1,a_2, x_1,x_2,y_1,y_2) \in (\mathbb Z_N^*)^2\times \mathbb Z^4$ such that (2.7), (2.8), (2.11) and (2.12) hold for fixed $a_3$, $x_3$, $y_3$, $r_x$ and $r_y$. By (2.13), where $z_1,z_2\in \mathbb Z$. Using (2.7) and (2.8) we obtain
$$
\begin{equation}
r_x (a_1 z_1+a_2 z_2) \equiv f-a_3 x_3, \quad r_y (a_1 z_1+a_2 z_2) \equiv g-a_3 y_3 \pmod N
\end{equation}
\tag{2.18}
$$
and
$$
\begin{equation}
\max\biggl\{ \frac{P_j}{r_x}, \frac{Q_j}{r_y} \biggr\} \leqslant z_j < 2 \min\biggl\{ \frac{P_j}{r_x}, \frac{Q_j}{r_y} \biggr\}, \qquad j=1,2.
\end{equation}
\tag{2.19}
$$
Since $\operatorname{\textrm{gcd}} (r_x,r_y)=1$, it follows that (2.18) implies the congruence where $l_0$ is some integer depending only on $r_x$, $r_y$, $f-a_3x_3$ and $g-a_3 y_3$. Thus, $L$ does not exceed the number of tuples $(a_1,a_2,z_1,z_2)\in (\mathbb Z_N^*)^2\times \mathbb Z^2$ satisfying conditions (2.19) and (2.20). Applying Lemma 1 we obtain
$$
\begin{equation}
L \leqslant 4 \varphi(N) \min\biggl\{ \frac{P_1}{r_x}, \frac{Q_1}{r_y} \biggr\}\min\biggl\{ \frac{P_2}{r_x}, \frac{Q_2}{r_y} \biggr\} \leqslant 4\varphi(N) \frac{P_1 Q_2}{r_x r_y}.
\end{equation}
\tag{2.21}
$$
3. Let $H(r_x,r_y)$ be the number of families $(a,x,y)$ such that (2.7)–(2.9), (2.11), and (2.12) hold for fixed $r_x$ and $r_y$. Taking (2.16) and (2.21) into account we obtain
$$
\begin{equation}
\begin{aligned} \, \notag H(r_x,r_y) &\ll G(r_x,r_y)\cdot L \ll (r_y P_3+r_x Q_3) \tau(N) \min\{P_3,Q_3\} \varphi(N) \frac{P_1 Q_2}{r_x r_y} \\ &=\tau(N) \varphi(N) \min\{P_3,Q_3\} P_1 Q_2 \biggl(\frac{P_3}{r_x}+\frac{Q_3}{r_y}\biggr). \end{aligned}
\end{equation}
\tag{2.22}
$$
$$
\begin{equation*}
1\leqslant r_x < R_x=2 \min\{P_1,P_2\}\quad\text{and} \quad 1\leqslant r_y < R_y=2 \min\{Q_1,Q_2\}.
\end{equation*}
\notag
$$
It follows from these relations and (2.22) that the number of solutions of problem (2.7)–(2.9), (2.11) does not exceed
$$
\begin{equation*}
\begin{aligned} \, &\sum_{1\leqslant r_x < R_x} \sum_{1\leqslant r_y < R_y} H(r_x,r_y) \\ &\qquad\ll\tau(N) \varphi(N) \min\{P_3,Q_3\} P_1 Q_2 \sum_{1\leqslant r_x < R_x}\sum_{1\leqslant r_y<R_y} \biggl(\frac{P_3}{r_x}+\frac{Q_3}{r_y}\biggr) \\ &\qquad\ll\tau(N) \varphi(N) \min\{P_3,Q_3\} P_1 Q_2 (P_3 R_y \ln R_x+Q_3 R_x \ln R_y) \\ &\qquad\ll\tau(N) \varphi(N) \ln N \frac{P_1P_2P_3Q_1Q_2Q_3}{\min\{P_1,P_2,P_3,Q_1,Q_2,Q_3\}}. \end{aligned}
\end{equation*}
\notag
$$
This completes the proof of Lemma 4. Lemma 5. Let $f,g\in \mathbb Z$, $P,Q \in \mathbb N^3$, and $P_j,Q_j\leqslant N$, $j=1,2,3$. Then where Proof. Without loss of generality assume that $P_1 \leqslant Q_1$ and $P_2 \leqslant Q_2$.
For brevity we set $\widehat{\mathcal B}^{(3)}_N=\widehat{\mathcal B}^{(3)}_N(P,Q;f,g)$. It is clear that
$$
\begin{equation*}
\widehat{\mathcal B}^{(3)}_N =\mathop{\widetilde{\sum}}_{x_1,x_2,y_1,y_2} \sum_{\substack{P_3\leqslant x_3 < 2P_3 \\ Q_3\leqslant y_3 < 2Q_3}} \sum_{a_1,a_2,a_3\in \mathbb Z_N^*}\delta_N(a\cdot x-f)\delta_N(a\cdot y-g)+O(\xi),
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
\xi=\mathcal B^{(3)}_N(P,Q;f,g)-\widehat{\mathcal B}^{(3)}_N(P,Q;f,g),
\end{equation*}
\notag
$$
and $\mathop{\widetilde{\sum}}_{x_1,x_2,y_1,y_2} (\dots)$ is the sum over all $x_1,x_2,y_1,y_2 \in \mathbb Z$ satisfying the conditions
$$
\begin{equation*}
P_j \leqslant x_j < 2P_j, \quad Q_j \leqslant y_j < 2Q_j\quad\text{and} \quad x_1y_2 \neq x_2 y_1.
\end{equation*}
\notag
$$
Therefore,
$$
\begin{equation*}
\begin{aligned} \, &\widehat{\mathcal B}^{(3)}_N=O(\xi) +\mathop{\widetilde{\sum}}_{x_1,x_2,y_1,y_2} \sum_{\substack{P_3\leqslant x_3 < 2P_3 \\ Q_3\leqslant y_3 < 2Q_3}} \sum_{a_1,a_2,a_3\in \mathbb Z_N^*} \delta_N (a_1 x_1+a_2 x_2+x_3-f a_3) \\ &\qquad\qquad\qquad\qquad\times \delta_N (a_1 y_1+a_2 y_2+y_3-g a_3). \end{aligned}
\end{equation*}
\notag
$$
Using Lemma 2 we obtain the relation
$$
\begin{equation*}
\begin{aligned} \, &\sum_{Q_3\leqslant y_3 < 2Q_3} \delta_N (a_1 y_1+a_2 y_2+y_3-g a_3) \\ &\qquad=\frac{Q_3}{N}+\mathop{{\sum}'}_{-N/2< k\leqslant N/2} F(k) e\biggl( \frac{k(g a_3-a_1 y_1-a_2 y_2)}{N}\biggr), \end{aligned}
\end{equation*}
\notag
$$
where $|F(k)| \leqslant |2k|^{-1}$. Thus,
$$
\begin{equation}
\begin{aligned} \, \notag &\widehat{\mathcal B}^{(3)}_N=\mathop{\widetilde{\sum}}_{x_1,x_2,y_1,y_2} \sum_{P_3\leqslant x_3 < 2P_3}\sum_{a_1,a_2,a_3\in \mathbb Z_N^*} \frac{Q_3}{N}\delta_N (a_1 x_1+a_2 x_2+x_3-f a_3) \\ &\qquad\qquad+S+O(\xi). \end{aligned}
\end{equation}
\tag{2.24}
$$
Here
$$
\begin{equation*}
S =\mathop{\widetilde{\sum}}_{x_1,x_2,y_1,y_2} \sum_{P_3\leqslant x_3 < 2P_3}\sum_{a_3 \in \mathbb Z_N^*} \mathop{{\sum}'}_{-N/2<k\leqslant N/2} F(k) S_1(k),
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
S_1(k)=\sum_{a_1,a_2\in \mathbb Z_N^*} e\biggl( \frac{k(g a_3-a_1 y_1-a_2 y_2)}{N}\biggr) \delta_N (a_1 x_1+a_2 x_2+x_3-f a_3).
\end{equation*}
\notag
$$
Given $x_1$ and $x_2$, the number of pairs $(y_1,y_2)\in \mathbb Z^2$ such that $x_1 y_2 \neq x_2 y_1 $ and $Q_j \leqslant y_j < 2Q_j$, $j=1,2$, is equal to $Q_1Q_2+O(\min\{Q_1,Q_2\})$. Hence
$$
\begin{equation*}
\begin{aligned} \, &\mathop{\widetilde{\sum}}_{x_1,x_2,y_1,y_2} \sum_{P_3\leqslant x_3 < 2P_3}\sum_{a_1,a_2,a_3\in \mathbb Z_N^*} \frac{Q_3}{N}\delta_N (a_1 x_1+a_2 x_2+x_3-f a_3) \\ &\qquad=\mathcal A^{(3)}_N (P;f) \frac{Q_1Q_2Q_3}{N} \biggl( 1+O\biggl(\frac{1}{\max\{Q_1,Q_2\}}\biggr)\biggr). \end{aligned}
\end{equation*}
\notag
$$
Using the last formula, relation (2.24), and Lemmas 3 and 4 we obtain
$$
\begin{equation}
\widehat{\mathcal B}^{(3)}_N=\frac{\varphi^3(N)}{N^2} P_1P_2P_3 Q_1Q_2Q_3+S+O(\mathcal R^{(3)}_N(P,Q)).
\end{equation}
\tag{2.25}
$$
It remains to estimate the quantity $S$. By (2.1),
$$
\begin{equation*}
\delta_N (a_1 x_1+a_2 x_2+x_3-f a_3) =\frac{1}{N} \sum_{n\in \mathbb Z_N} e\biggl(\frac{a_1x_1+a_2x_2+x_3-f a_3}{N} n\biggr).
\end{equation*}
\notag
$$
Thus,
$$
\begin{equation*}
\begin{aligned} \, &S_1(k) =\frac{1}{N} \sum_{n\in \mathbb Z_N} \sum_{a_1,a_2\in \mathbb Z_N^*} e\biggl(\frac{x_3n+(g k-f n)a_3}{N}\biggr) \\ &\qquad\qquad\qquad\times e\biggl(\frac{x_1n-y_1k}{N}a_1\biggr)e\biggl(\frac{x_2n-y_2k}{N}a_2\biggr). \end{aligned}
\end{equation*}
\notag
$$
We sum with respect to $a_1$ and $a_2$ using (2.2). Then we obtain
$$
\begin{equation*}
\begin{aligned} \, S_1(k) &=N \sum_{n\in \mathbb Z_N}\sum_{d_1,d_2\mid N} \frac{\mu(d_1) \mu(d_2)}{d_1d_2} \, e\biggl(\frac{x_3n+(g k-f n)a_3}{N}\biggr) \\ &\qquad\qquad\times\delta_{N/d_1}(x_1n-y_1k)\delta_{N/d_2}(x_2n-y_2k). \end{aligned}
\end{equation*}
\notag
$$
It follows from the last formula and the definition of $S$ that
$$
\begin{equation}
S =N\sum_{d_1,d_2\mid N} \frac{\mu(d_1) \mu(d_2)}{d_1d_2} \mathop{\widetilde{\sum}}_{x_1,x_2,y_1,y_2} \sum_{P_3\leqslant x_3 < 2P_3}\sum_{a_3 \in \mathbb Z_N^*} S_2,
\end{equation}
\tag{2.26}
$$
where
$$
\begin{equation*}
\begin{aligned} \, S_2&=\mathop{{\sum}'}_{-N/2< k \leqslant N/2} \sum_{n\in \mathbb Z_N} F(k)e\biggl(\frac{x_3n+(g k- f n)a_3}{N}\biggr) \\ &\qquad\qquad\times \delta_{N/d_1}(x_1n-y_1k)\delta_{N/d_2}(x_2n-y_2k). \end{aligned}
\end{equation*}
\notag
$$
1. Let us estimate the sum $S_2$. If $\delta_{N/d_1}(x_1n-y_1k)\delta_{N/d_2}(x_2n-y_2k)=1$, then
$$
\begin{equation}
d_1x_1 n \equiv d_1 y_1 k \pmod{N}\quad\text{and} \quad d_2x_2 n \equiv d_2 y_2 k \pmod{N}.
\end{equation}
\tag{2.27}
$$
Therefore, where
$$
\begin{equation*}
D=x_1y_2-x_2y_1\quad\text{and} \quad d_0=\frac{d_1 d_2}{\operatorname{\textrm{gcd}} (d_1,d_2)}.
\end{equation*}
\notag
$$
Let $\Lambda$ be the set of pairs $(n,k)\in \mathbb Z^2$ satisfying (2.27). This is a two-dimensional integer lattice. Therefore, there exist $\alpha, \gamma \in \mathbb N$ and $\beta\in \mathbb Z$ such that $(\alpha,0)$, $(\beta,\gamma)$ is a basis of $\Lambda$ (see [18], Ch. 1), that is,
$$
\begin{equation*}
\Lambda=\{(\alpha n'+\beta k',\gamma k')\colon n',k'\in \mathbb Z\}.
\end{equation*}
\notag
$$
Let $r=\operatorname{\textrm{gcd}} (N,d_1 x_1, d_2 x_2)$. Using (2.27) and (2.28) and the conditions $(\alpha,0)\in \Lambda$ and $(\beta,\gamma)\in \Lambda$ we obtain the relations
$$
\begin{equation*}
\alpha=\frac{N}{r}\quad\text{and}\quad \gamma \text{ is a multiple of } \frac{N}{\operatorname{\textrm{gcd}} (N,d_0 D)}\,.
\end{equation*}
\notag
$$
Thus,
$$
\begin{equation*}
\begin{aligned} \, S_2 &=\mathop{{\sum}'}_{-N/(2\gamma)< k'\leqslant N/(2\gamma)}\sum_{n'=0}^{r-1} F(\gamma k') e\biggl(\frac{x_3(\alpha n'+\beta k')}{N}\biggr) e\biggl(\frac{g \gamma k' -f(\alpha n'+\beta k')}{N}a_3\biggr) \\ &=\mathop{{\sum}'}_{-N/(2\gamma)< k'\leqslant N/(2\gamma)} F(\gamma k') e\biggl(\frac{x_3\beta+(g\gamma -f\beta)a_3}{N} k'\biggr) \sum_{n'=0}^{r-1} e\biggl(\frac{x_3 -f a_3}{r}n'\biggr) \\ &=r \delta_r(x_3-f a_3)\mathop{{\sum}'}_{-N/(2\gamma)< k'\leqslant N/(2\gamma)} F(\gamma k') e\biggl(\frac{x_3\beta+(g\gamma -f\beta)a_3}{N} k'\biggr). \end{aligned}
\end{equation*}
\notag
$$
Using the bounds
$$
\begin{equation*}
|F(\gamma k')| \leqslant\frac{1}{2|\gamma k'|}, \qquad \gamma \geqslant \frac{N}{\operatorname{\textrm{gcd}} (N,d_0 D)}\quad\text{and} \quad |e(z)|\leqslant 1
\end{equation*}
\notag
$$
we obtain
$$
\begin{equation}
|S_2| \leqslant r \delta_r(x_3-f a_3) \sum_{1\leqslant k' \leqslant N/(2\gamma)} \frac{1}{\gamma k'} \ll \frac{r \delta_r(x_3-f a_3)}{N} \operatorname{\textrm{gcd}} (N,d_0 D) \ln N.
\end{equation}
\tag{2.29}
$$
2. Now let us estimate the sum $\mathop{\widetilde{\sum}}_{x_1,x_2,y_1,y_2}\sum_{x_3,a_3} S_2$. Consider the congruence $x_3 \!\equiv\! f a_3\! \pmod r$. For fixed $x_3$ the number of $a_3\in \mathbb Z_N$ such that $x_3\! \equiv\! f a_3\! \pmod r$ does not exceed $N \operatorname{\textrm{gcd}} (f,r)/r$. Moreover, $x_3$ is divisible by $\operatorname{\textrm{gcd}} (f,r)$. Hence
$$
\begin{equation*}
\sum_{P_3\leqslant x_3 < 2P_3}\sum_{a_3 \in \mathbb Z_N^*} r\delta_r(x_3-f a_3) \ll N \operatorname{\textrm{gcd}} (f,r) \sum_{\substack{P_3\leqslant x_3 < 2P_3 \\ x_3 \equiv 0 \ (\operatorname{mod}{\operatorname{\textrm{gcd}} (f,r)})}} 1 \ll NP_3.
\end{equation*}
\notag
$$
Taking (2.29) into account we have
$$
\begin{equation*}
\sum_{P_3\leqslant x_3 < 2P_3}\sum_{a_3 \in \mathbb Z_N^*} S_2 \ll P_3 \operatorname{\textrm{gcd}} (N,d_0 D) \ln N.
\end{equation*}
\notag
$$
Since $D=x_1 y_2 -x_2 y_1$ and $d_0=d_1 d_2 (\operatorname{\textrm{gcd}} (d_1,d_2))^{-1}$, $d_0\mid N$, it follows that
$$
\begin{equation}
\begin{aligned} \, \notag &\mathop{\widetilde{\sum}}_{x_1,x_2,y_1,y_2}\sum_{P_3\leqslant x_3 < 2P_3} \sum_{a_3 \in \mathbb Z_N^*} S_2 \ll P_3 d_0 \ln N \mathop{\widetilde{\sum}}_{x_1,x_2,y_1,y_2} \operatorname{\textrm{gcd}} \biggl (\frac{N}{d_0}, x_1y_2-x_2 y_1\biggr) \\ &\qquad\leqslant P_3 d_0 \ln N \sum_{q\mid (N/d_0)} q S_3(q), \end{aligned}
\end{equation}
\tag{2.30}
$$
where $S_3(q)$ is the number of tuples $(x_1,x_2,y_1,y_2)\in \mathbb Z^4$ for which
$$
\begin{equation}
\begin{gathered} \, x_1 y_2 \equiv x_2 y_1 \pmod q, \qquad x_1y_2 \neq x_2 y_1, \\ P_j\leqslant x_j < 2P_j\quad\text{and} \quad Q_j\leqslant y_j < 2Q_j, \qquad j=1,2. \end{gathered}
\end{equation}
\tag{2.31}
$$
We set Then $t\in \mathbb Z$ and $1\leqslant |t| \leqslant 4(P_1Q_2+P_2 Q_1) q^{-1}$. Recall that $Q_j\geqslant P_j$, $j= 1,2$. Given $x_1$, $x_2$ and $t$, the number of pairs $(y_1,y_2)\in \mathbb Z^2$ satisfying (2.31) and (2.32) does not exceed
$$
\begin{equation*}
O\biggl(\operatorname{\textrm{gcd}} (x_1,x_2) \min\biggl\{\frac{Q_1}{P_1}, \frac{Q_2}{P_2}\biggr\} \biggr).
\end{equation*}
\notag
$$
Thus,
$$
\begin{equation*}
\begin{aligned} \, S_3(q) &\ll \sum_{1\leqslant |t| \leqslant 4(P_1Q_2+P_2 Q_1) q^{-1}} \sum_{\substack{P_1 \leqslant x_1 < 2P_1 \\ P_2 \leqslant x_2 < 2P_2}} \operatorname{\textrm{gcd}} (x_1,x_2) \min\biggl\{\frac{Q_1}{P_1}, \frac{Q_2}{P_2}\biggr\} \\ &\ll\frac{P_1 Q_2+P_2 Q_1}{q}\min\biggl\{\frac{Q_1}{P_1}, \frac{Q_2}{P_2}\biggr\} \sum_{1\leqslant u \leqslant 2 \min\{P_1,P_2\}}\, \sum_{\substack{P_1 \leqslant x_1 < 2P_1 \\ P_2 \leqslant x_2 < 2P_2}} u\delta_u(x_1)\delta_u(x_2) \\ &\ll \frac{P_1 Q_2+P_2 Q_1}{q}\min\{Q_1 P_2,Q_2 P_1\} \sum_{1\leqslant u \leqslant 2N} \frac{1}{u} \ll \frac{P_1P_2 Q_1Q_2}{q}\ln N. \end{aligned}
\end{equation*}
\notag
$$
Taking (2.30) into account we obtain
$$
\begin{equation*}
\mathop{\widetilde{\sum}}_{x_1,x_2,y_1,y_2}\, \sum_{P_3\leqslant x_3 < 2P_3}\, \sum_{a_3 \in \mathbb Z_N^*} S_2 \ll P_1P_2P_3Q_1Q_2 d_0 \tau\biggl(\frac{N}{d_0}\biggr) \ln^2 N.
\end{equation*}
\notag
$$
3. By the last bound, the condition $d_0=d_1 d_2/ \operatorname{\textrm{gcd}} (d_1,d_2)$ and (2.26),
$$
\begin{equation*}
S \ll N\sum_{d_1,d_2 \mid N} \frac{P_1P_2P_3Q_1Q_2 d_0 \tau(N/d_0) \ln^2 N }{d_1 d_2} \leqslant N P_1P_2P_3 Q_1 Q_2 (\ln N)^2 \tau^3(N).
\end{equation*}
\notag
$$
To complete the proof it remains to use (2.25). Lemma 6. Let $s\geqslant 3$, $f,g \in \mathbb Z$, $P,Q\in \mathbb N^s$ and $P_j,Q_j \leqslant N$, $j=1,\dots,s$. Then where Proof. It can readily be seen that
$$
\begin{equation*}
0\leqslant \mathcal B^{(s)}_N(P,Q;f,g)-\sum_{a_4,\dots,a_s\in \mathbb Z_N^*} \sum_{\substack{P_j \leqslant x_j < 2P_j \\ 4\leqslant j\leqslant s}}\, \sum_{\substack{Q_j \leqslant y_j< 2Q_j \\ 4\leqslant j\leqslant s}} \widehat{\mathcal B}^{(3)}_N(\widetilde P, \widetilde Q; \widetilde f, \widetilde g) \leqslant\xi_s,
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
\begin{gathered} \, \xi_s=\mathcal B^{(s)}_N (P,Q;f,g)-\widehat{\mathcal B}^{(s)}_N (P,Q;f,g), \qquad \widetilde P=(P_1,P_2,P_3), \qquad \widetilde Q=(Q_1,Q_2,Q_3), \\ \widetilde f=f-a_4x_4-\dots-a_sx_s\quad\text{and} \quad \widetilde g=g-a_4y_4-\dots-a_sy_s. \end{gathered}
\end{equation*}
\notag
$$
Using Lemma 5 we obtain the asymptotic formula
$$
\begin{equation*}
\begin{aligned} \, \mathcal B^{(s)}_N(P,Q;f,g) &=\frac{\varphi^s(N)}{N^2} P_1\dotsb P_sQ_1\dotsb Q_s \\ &\qquad+O\bigl(\mathcal R^{(3)}_N(\widetilde P, \widetilde Q) \varphi^{s-3}(N) P_4\dotsb P_s Q_4\dotsb Q_s\bigr)+O (\xi_s) \\ &=\frac{\varphi^s(N)}{N^2} P_1\dotsb P_sQ_1\dotsb Q_s+O(\xi_s)+O(\mathcal R^{(s)}_N( P, Q)). \end{aligned}
\end{equation*}
\notag
$$
It remains to estimate $\xi_s$. We take any tuple $(a,x,y)$ satisfying (2.7)–(2.9). If $x_iy_j=x_j y_i$, then there exists $l\in\{1,\dots,s\} \setminus\{i,j\}$ such that $x_i y_l \neq x_l y_j$. Therefore,
$$
\begin{equation*}
\xi_s=\mathcal B^{(s)}_N (P,Q;f,g)-\widehat{\mathcal B}^{(s)}_N (P,Q;f,g) \leqslant\sum_{1\leqslant i < j\leqslant s} \sum_{\substack{1\leqslant l \leqslant s \\ l\neq i,j}} \mathcal C_{i,j,l},
\end{equation*}
\notag
$$
where $\mathcal C_{i,j,l}=\mathcal C_{i,j,l}(N;P,Q;f,g)$ is the number of families $(a,x,y)\in (\mathbb Z_N^*)^s \times \mathbb Z^s \times \mathbb Z^s$ for which (2.7) and (2.8) hold, $x_i y_j=x_jy_i$ and $x_i y_l \neq x_ly_i$. Clearly,
$$
\begin{equation*}
\mathcal C_{i,j,l} \leqslant \sum_{\substack{a_k \in \mathbb Z_N^*,\, P_k\leqslant x_k < 2P_k,\, Q_k\leqslant y_k < 2Q_k \\ 1\leqslant k\leqslant s,\, k\neq i,j,k}} \bigl( \mathcal B^{(3)}_N( P', Q'; f', g') -\widehat{\mathcal B}^{(3)}_N( P', Q'; f', g')\bigr),
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
\begin{gathered} \, P'=(P_i,P_j,P_l), \qquad Q'=(Q_i,Q_j,Q_l), \\ f'=f- \sum_{k\neq i,j,l} a_k x_k\quad\text{and} \quad g'=g- \sum_{k\neq i,j,l} a_k y_k. \end{gathered}
\end{equation*}
\notag
$$
It follows from Lemma 4 that
$$
\begin{equation*}
\mathcal C_{i,j,l}\ll \frac{P_1\dotsb P_sQ_1\dotsb Q_s}{\min\{P_i,P_j,P_l,Q_i,Q_j,Q_l\}} \tau(N) \varphi^{s-2}(N) \ln N \leqslant\mathcal R_N^{(s)}(P,Q).
\end{equation*}
\notag
$$
Hence $\xi_s \ll_s \mathcal R^{(s)}_N (P,Q)$.
This completes the proof of Lemma 6. Using Lemma 6 and estimate (2.6) we obtain the following result. Corollary 3. Let $s\geqslant 3$, $f,g \in \mathbb Z$, $P,Q\in \mathbb N^s$, and let Then § 3. Distribution of solutions of congruence (1.1)The aim of this section is to prove Corollaries 4 and 5. Let It follows from the well-known bound thatLet $\mathbb Z_+=\mathbb N\cup\{0\}$. For every $k=(k_1,\dots, k_s) \in \mathbb Z_+^s$ we set
$$
\begin{equation*}
\begin{gathered} \, \Pi_k=\{x\in \mathbb Z^s\colon 2^{k_j} \leqslant |x_j| < 2^{k_j+1},\ j=1,\dots,s\}, \\ |k|_1=k_1+\dots+k_s, \qquad |k|_\infty=\max_{1\leqslant j \leqslant s} k_j\quad\text{and} \quad |k|_*=\min_{1\leqslant j \leqslant s} k_j. \end{gathered}
\end{equation*}
\notag
$$
For every $R>1$ and $a\in \mathbb Z^s$ we set
$$
\begin{equation*}
\begin{aligned} \, \Upsilon_N(R)&=\{k\in \mathbb Z_+^s\colon |k|_1 \leqslant\log_2 R, \ |k|_*\geqslant h\}, \\ V(a)&=\sum_{k\in \Upsilon_N(R)} \sum_{x\in \Pi_k} \delta_N(a\cdot x), \\ \mu_s(N,R)&=\frac{1}{\varphi^s(N)} \sum_{a\in (\mathbb Z_N^*)^s} V(a) \end{aligned}
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\begin{aligned} \, \sigma_s^2(N,R)&=\frac{1}{\varphi^s(N)} \sum_{a\in (\mathbb Z_N^*)^s} (V(a)-\mu_s(N,R))^2 \\ &=\frac{1}{\varphi^s(N)} \sum_{a\in (\mathbb Z_N^*)^s} V^2(a)-\mu_s^2(N,R). \end{aligned}
\end{equation*}
\notag
$$
Lemma 7. Let $s\geqslant 2$, $R\in (1,+\infty)$, and let $\ln N \ll_s \ln R \leqslant\ln N$. Then If $s\geqslant 3$ in addition, then Proof. Clearly,
$$
\begin{equation*}
\sum_{a\in (\mathbb Z_N^*)^s}\sum_{x\in \Pi_k} \delta_N(a\cdot x)=2^s \sum_{a\in (\mathbb Z_N^*)^s} \sum_{\substack{2^{k_j}\leqslant x_j < 2^{k_j+1} \\ 1\leqslant j\leqslant s}} \delta_N(a\cdot x) =2^s \mathcal A_N^{(s)}(2^{k_1},\dots, 2^{k_s};0).
\end{equation*}
\notag
$$
Using this formula and Corollary 2 we obtain the asymptotic equality
It can readily be seen that
$$
\begin{equation}
\begin{aligned} \, \notag &\sum_{k\in \mathbb Z^s_+,\, |k|_1 \leqslant\log_2 R} 2^{|k|_1} =\sum_{0\leqslant k_0 \leqslant\log_2 R} 2^{k_0} \sum_{k_1+\dots+k_s=k_0} 1 =\sum_{0\leqslant k_0 \leqslant\log_2 R} 2^{k_0} C^{s-1}_{k_0+s} \\ &=\sum_{0\leqslant k_0 \leqslant\log_2 R} \frac{2^{k_0}}{(s-1)!} ( k_0^{s-1}+O_s (k_0^{s-2})) =\frac{2R \log_2^{s-1} R}{(s-1)!}+O_s (R \log_2^{s-2} R). \end{aligned}
\end{equation}
\tag{3.6}
$$
Here and below $C_n^k$ is a binomial coefficient. Using (3.2) we obtain
$$
\begin{equation}
\sum_{|k|_1 \leqslant\log_2 R,\, |k|_* \leqslant h} 2^{|k|_1} \underset{s}\ll h R \ln^{s-2} R \ll \frac{R \ln^{s-1} N}{\ln\ln N}.
\end{equation}
\tag{3.7}
$$
By (3.6) and (3.7),
$$
\begin{equation}
\sum_{k\in \Upsilon_N(R)} 2^{|k|_1} =\frac{2 R \log_2^{s-1} R}{(s-1)!}+O_s\biggl(\frac{R \ln^{s-1} N}{\ln\ln N}\biggr).
\end{equation}
\tag{3.8}
$$
Asymptotic formula (3.3) follows from (3.5) and (3.8).
We proceed to the proof of (3.4). Let where the set $W_s''$ consists of the pairs $(x,y)\in \mathbb Z^s\times \mathbb Z^s$ such that $x$ and $y$ are linearly dependent over $\mathbb R$. Set
$$
\begin{equation*}
S=\sum_{a\in (\mathbb Z_N^*)^s} \sum_{k,n\in \Upsilon_N(R)} \sum_{\substack{x\in \Pi_k, y\in \Pi_n\\ (x,y)\in W_s''}} \delta_N(a\cdot x)\delta_N(a\cdot y).
\end{equation*}
\notag
$$
We claim that Consider any pair $(x,y)\in W_s''$ such that $x\in \Pi_k$ and $y\in \Pi_n$, where $n,k\in \Upsilon_N(R)$. Set
$$
\begin{equation*}
\alpha=\frac{\operatorname{\textrm{gcd}} (x_1,\dots,x_s)}{\operatorname{\textrm{gcd}} (x_1,\dots,x_s,y_1,\dots,y_s)}\quad\text{and} \quad\beta=\frac{\operatorname{\textrm{gcd}} (y_1,\dots,y_s)}{\operatorname{\textrm{gcd}} (x_1,\dots,x_s,y_1,\dots,y_s)}.
\end{equation*}
\notag
$$
Then $\operatorname{\textrm{gcd}} (\alpha,\beta)=1$. Since $x$ and $y$ are linearly dependent, it follows that
$$
\begin{equation*}
\frac{x_j}{\alpha}=\frac{y_j}{\beta}=z_j, \qquad j=1,\dots, s,
\end{equation*}
\notag
$$
where $z_j\in \mathbb Z$. Without loss of generality we assume that $\alpha\geqslant \beta$. The following relations are obvious:
$$
\begin{equation*}
\frac{2^{k_j}}{\alpha} \leqslant |z_j| < \frac{2^{k_j+1}}{\alpha}, \quad j=1,\dots, s,\quad\text{and} \quad \alpha \leqslant\max_{k\in \Upsilon_N(R)} \min_{1\leqslant j\leqslant s} 2^{k_j+1} \leqslant 2R.
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
S\ll \sum_{1\leqslant\beta \leqslant\alpha \leqslant 2 R} S_1(\alpha,\beta)
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
S_1(\alpha,\beta)=\sum_{k\in \Upsilon_N(R)}\, \sum_{a\in (\mathbb Z_N^*)^s}\, \sum_{2^{k_j} \alpha^{-1} \leqslant |z_j| < 2^{k_j+1}\alpha^{-1}} \delta_N(\alpha a\cdot z)\delta_N(\beta a\cdot z).
\end{equation*}
\notag
$$
Since $\operatorname{\textrm{gcd}} (\alpha,\beta)=1$, it follows that $\delta_N(\alpha a\cdot z) \delta_N(\beta a\cdot z)=\delta_N(a\cdot z)$. Using Lemma 3, relations (2.6) and (3.6), and condition $2^{|k|_*} \geqslant 2^h=\tau^3(N)\ln^{s+2} N$ we obtain
$$
\begin{equation*}
\begin{aligned} \, S_1(\alpha,\beta) & \underset{s}\ll \sum_{k\in \Upsilon_N(R)} \mathcal A^{(s)}_N(2^{k_1}\alpha^{-1},\dots, 2^{k_s}\alpha^{-1};0) \\ &\underset{s}\ll\sum_{k \in \Upsilon_N(R)} \biggl(\frac{\varphi^s(N) 2^{|k|_1} }{ N \alpha^s} +\frac{\varphi^{s-1}(N) 2^{|k|_1} \tau^2(N) \ln N}{ 2^{|k|_*} \alpha^{s-1}} \biggr) \\ &\underset{s}\ll\frac{\varphi^s(N)}{N} \biggl(\frac{1}{\alpha^s} +\frac{1}{\alpha^{s-1} \ln N}\biggr) \sum_{k\in \Upsilon_N(R)} 2^{|k|_1} \\ &\underset{s}\ll{} \frac{\varphi^s(N)}{N} \biggl(\frac{1}{\alpha^3} +\frac{1}{\alpha^{2}\ln N}\biggr) R\log_2^{s-1} R. \end{aligned}
\end{equation*}
\notag
$$
The last bound, (3.3), and the assumption that $\ln N \asymp_s \ln R$ imply that
$$
\begin{equation*}
\begin{aligned} \, S &\underset{s}\ll \frac{\varphi^s(N)}{N} R\log_2^{s-1} R \sum_{1\leqslant\beta \leqslant\alpha \leqslant 2R} \biggl(\frac{1}{\alpha^3}+\frac{1}{\alpha^2 \ln N}\biggr) \\ &\underset{s}\ll\frac{\varphi^s(N)}{N} R\log_2^{s-1} R \underset{s}\ll \varphi^s(N) \mu_s(N,R). \end{aligned}
\end{equation*}
\notag
$$
Inequality (3.9) is proved.
It is obvious that
$$
\begin{equation*}
\sum_{a\in (\mathbb Z_N^*)^s} V^2(a) =\sum_{a\in (\mathbb Z_N^*)^s} \sum_{k\in \Upsilon_N(R)} \sum_{x\in \Pi_k} \delta_N(a\cdot x) \sum_{n\in \Upsilon_N(R)} \sum_{y\in \Pi_n} \delta_N(a\cdot y).
\end{equation*}
\notag
$$
Hence, taking (3.9) into account we obtain the asymptotic formula
$$
\begin{equation}
\frac{1}{\varphi^s(N)}\sum_{a\in (\mathbb Z_N^*)^s} V^2(a) =S_2+O_s(\mu_s(N,R)),
\end{equation}
\tag{3.10}
$$
where
$$
\begin{equation*}
S_2=\frac{1}{\varphi^s(N)}\sum_{a\in (\mathbb Z_N^*)^s}\, \sum_{k,n\in \Upsilon_N(R)}\, \sum_{\substack{x\in \Pi_k, y\in \Pi_n \\ (x,y)\in W_s'}} \delta_N(a\cdot x)\delta_N(a\cdot y).
\end{equation*}
\notag
$$
It can readily be seen that
$$
\begin{equation*}
S_2=\frac{2^{2s}}{\varphi^s(N)} \sum_{k,n\in \Upsilon_N(R)} \mathcal B^{(s)}_N (2^{k_1},\dots, 2^{k_s}, 2^{n_1},\dots, 2^{n_s};0,0).
\end{equation*}
\notag
$$
Using Corollary 3 we obtain
$$
\begin{equation*}
\begin{aligned} \, S_2 &=\frac{2^{2s}}{N^2} \sum_{k,n\in \Upsilon_N(R)} 2^{|k|_1+|n|_1} \bigl(1+O_s( \ln^{-(s-1)}N)\bigr) \\ &=\biggl(\frac{2^{s}}{N} \sum_{k\in \Upsilon_N(R)} 2^{|k|_1}\biggr)^2 \bigl(1+O_s(\ln^{-(s-1)}N)\bigr). \end{aligned}
\end{equation*}
\notag
$$
It follows from the last relation, (3.10) and (3.5) that
$$
\begin{equation*}
\begin{aligned} \, \sigma_s^2(N,R) &=\frac{1}{\varphi^s(N)}\sum_{a\in (\mathbb Z_N^*)^s} V^2(a)-\mu_s^2(N,R) \\ &=\biggl(\frac{2^{s}}{N} \sum_{k\in \Upsilon_N(R)} 2^{|k|_1}\biggr)^2 \bigl(1+O_s(\ln^{-(s-1)}N) -(1+O_s(\ln^{-(s-1)}N))^2\bigr) \\ &\qquad+O_s(\mu_s(N,R)) \\ &\underset{s}\ll \frac{1}{N^2 \ln^{s-1} N }\biggl(\sum_{k\in \Upsilon_N(R)} 2^{|k|_1}\biggr)^2+\mu_s(N,R). \end{aligned}
\end{equation*}
\notag
$$
Using (3.6), (3.3) and the conditions $\ln N \ll_s \ln R \leqslant\ln N$ yields
$$
\begin{equation*}
\sigma_s^2(N,R) \underset{s}\ll \frac{1}{N^2 \ln^{s-1} N } (R \ln^{s-1} R)^2+\mu_s(N,R) \ll \mu_s(N,R).
\end{equation*}
\notag
$$
This completes the proof of Lemma 7. Remark 4. Let $X$ be a finite subset of $(0,+\infty)$ and let The following Chebyshev inequality holds for any positive real $\lambda$: Chebyshev’s inequality and Lemma 7 imply the following result. Corollary 4. Let $s\geqslant 3$, $R\in (1,+\infty)$ and $\ln N \ll_s \ln R \leqslant\ln N$. Then, for any positive real $\xi$, We define a set
$$
\begin{equation*}
\Omega_N(R)=\Bigl\{x\in \mathbb Z^s\colon H(x) \leqslant R, \, \min_{1\leqslant j\leqslant s} |x_j| \geqslant 2\tau^3(N) \ln^{s+2} N\Bigr\}.
\end{equation*}
\notag
$$
It can readily be seen that
$$
\begin{equation}
\Omega_N(R) \subset \bigcup_{k\in \Upsilon_N(R)} \Pi_k.
\end{equation}
\tag{3.11}
$$
Set
$$
\begin{equation*}
\widehat \mu=\widehat \mu (N,R,s)=\frac{2^{s+1}}{(s-1)!} \frac{R \log_2^{s-1} R}{N}.
\end{equation*}
\notag
$$
Corollary 5. Let $s\geqslant 3$, $\eta_0 \in (1,+\infty)$, $R\in (1,+\infty)$ and $\ln N \ll_s \ln R \leqslant\ln N$. Then for any real $\eta\geqslant \eta_0$, Proof. By (3.3) there exists a positive integer $N_0$, which depends only on $s$ and $\eta_0$, such that Without loss of generality we assume that $N\geqslant N_0$.
Consider an arbitrary $a\in (\mathbb Z_N^*)^s$ such that
$$
\begin{equation*}
\sum_{x\in \Omega_N(R)} \delta_N (a\cdot x) \geqslant \eta \widehat \mu.
\end{equation*}
\notag
$$
Using (3.11) we obtain
$$
\begin{equation*}
V(a) \geqslant \sum_{x\in \Omega_N(R)} \delta_N(a\cdot x) \geqslant \eta \widehat \mu \geqslant \eta \mu_s(N,R) \biggl(\frac{1}{2}+\frac{1}{2\eta_0}\biggr) > \mu_s(N,R).
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
\begin{aligned} \, |V(a)-\mu_s(N,R)| &=V(a)-\mu_s(N,R) \geqslant \eta \widehat \mu- \widehat \mu \biggl(\frac{1}{2}+\frac{1}{2\eta_0}\biggr)^{-1} \\ &=\eta \widehat \mu \biggl(1-\frac{2\eta_0}{\eta (\eta_0+1)}\biggr) \geqslant \eta \widehat \mu \biggl(1- \frac{2}{\eta_0+1}\biggr). \end{aligned}
\end{equation*}
\notag
$$
By Corollary 4 the number of such elements $a\in (\mathbb Z_N^*)^s$ does not exceed
$$
\begin{equation*}
O_s\biggl(\varphi^s(N) \frac{R \ln^{s-1} N}{N} \biggl(\eta\widehat \mu \biggl(1- \frac{2}{\eta_0+1}\biggr) \biggr)^{-2} \biggr) =O_{s,\eta_0} \biggl(\varphi^s(N)\frac{N}{\eta^2 R \ln^{s-1} N}\biggr).
\end{equation*}
\notag
$$
This completes the proof of the corollary. § 4. Proof of Theorem 1 Proof. It follows from the proof of Theorem 2 in [8] that
$$
\begin{equation*}
\sum_{a\in (\mathbb Z_N^*)^s} \mathop{{\sum}'}_{H(x)\leqslant R} \delta_N(a\cdot x)=\sum_{t=2}^s 2^t C^t_s \varphi^{s-t}(N) E_N^{(t)}(R),
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
E_N^{(t)}(R)=\sum_{a\in (\mathbb Z_N^*)^t} \sum_{x\in \mathbb N^t,\, H(x)\leqslant R} \delta_N(a\cdot x) \underset{t}\ll \varphi^{t-1}(N) R \ln^{t-1} R.
\end{equation*}
\notag
$$
Therefore,
$$
\begin{equation}
\sum_{a\in (\mathbb Z_N^*)^s} \mathop{{\sum}'}_{H(x)\leqslant R} \delta_N(a\cdot x)=2^s E_N^{(s)}(R)+O_s (\varphi^{s-2}(N) R \ln^{s-2} R).
\end{equation}
\tag{4.2}
$$
It can readily be seen that
$$
\begin{equation}
E_N^{(s)}(R) \leqslant\sum_{k\in \mathbb Z^s_+,\, |k|_1 \leqslant\log_2 R} \mathcal A^{(s)}_N(2^{k_1},\dots, 2^{k_s};0)=S_1+S_2,
\end{equation}
\tag{4.3}
$$
where and
It follows from Corollary 2 and (3.6) that
$$
\begin{equation}
S_1 \underset{s}\ll \frac{\varphi^s(N)}{N} \sum_{|k|_1 \leqslant\log_2 R} 2^{|k|_1} \underset{s}\ll \frac{\varphi^s(N)}{N} R \log_2^{s-1} R.
\end{equation}
\tag{4.4}
$$
Using Lemma 1 and inequality (3.2) we obtain
$$
\begin{equation}
\begin{aligned} \, \notag S_2 &\leqslant 2^s \varphi^{s-1}(N) \sum_{|k|_1 \leqslant\log_2 R,\, |k|_\infty \leqslant h} 2^{|k|_1} \underset{s}\ll \varphi^{s-1}(N) R h^{s-1} \\ &\underset{s}\ll\varphi^{s-1}(N) R \biggl(\frac{\ln N}{\ln\ln N}\biggr)^{s-1} \ll \frac{\varphi^s(N)}{N} R \frac{\ln^{s-1} N}{(\ln\ln N)^{s-2}}. \end{aligned}
\end{equation}
\tag{4.5}
$$
Estimate (4.1) follows from (4.2)–(4.5).
This completes the proof of Lemma 8. Proof of Theorem 1. It is clear that
$$
\begin{equation*}
\#\{a\in (\mathbb Z_N^*)^s \colon q_N(a) \leqslant R\} \leqslant\sum_{a\in (\mathbb Z_N^*)^s} \mathop{{\sum}'}_{H(x)\leqslant R} \delta_N(a\cdot x).
\end{equation*}
\notag
$$
Using Lemma 8 for $R=N (\lambda \ln^{s-1} N)^{-1}$ we obtain
It remains to estimate the number of $a\in (\mathbb Z_N^*)^s$ such that $q_N(a) \geqslant N \lambda (\ln N)^{1-s}$. Set
$$
\begin{equation*}
R=\lambda \frac{N}{2^s\ln^{s-1} N}\quad\text{and} \quad \xi=\frac{\mu_s(N,R)}{2}.
\end{equation*}
\notag
$$
Fix an arbitrary $a\in (\mathbb Z_N^*)^s$ such that If $x\in \bigcup_{k\in \Upsilon_N(R)} \Pi_k$, then
$$
\begin{equation*}
H(x)=|x_1\dotsb x_s| \leqslant 2^{s+|k|_1} \leqslant 2^s R=\lambda\frac{N}{\ln^{s-1} N}.
\end{equation*}
\notag
$$
Therefore, $a\cdot x \not\equiv 0 \pmod N$ and $\delta_N(a\cdot x)=0$. Thus,
$$
\begin{equation*}
\biggl| \sum_{k\in \Upsilon_N(R)} \sum_{x\in \Pi_k} \delta_N(a\cdot x) -\mu_s(N,R) \biggr|=\mu_s(N,R) \geqslant \frac{\mu_s(N,R)}{2}=\xi.
\end{equation*}
\notag
$$
Using Corollary 4 and (3.3) we obtain
$$
\begin{equation*}
\begin{aligned} \, &\frac{1}{\varphi^s(N)}\cdot\# \biggl\{a\in (\mathbb Z_N^*)^s \colon q_N(a) > \lambda\frac{N}{\ln^{s-1} N}\biggr\} \\ &\qquad \underset{s}\ll \frac{R \ln^{s-1} N}{\xi^2 N} =\frac{4R \ln^{s-1} N}{\mu_s^2(N,R) N} \\ &\qquad\underset{s}\ll \frac{N R \ln^{s-1} N}{ (R \ln^{s-1} R)^2} =\frac{1}{\lambda} \biggl(\frac{\ln N}{\ln R} \biggr)^{2(s-1)} \underset{s}\ll \frac{1}{\lambda}. \end{aligned}
\end{equation*}
\notag
$$
This completes the proof of Theorem 1. Proof of Corollary 1. Using (1.2) we see that $q_N(a) \gg_s D(K_N(a))^{-1}$. Therefore, Corollary 1 follows from Theorem 1.
§ 5. Proof of Theorem 2Let $\Gamma$ be a lattice in $\mathbb R^s$, so that $\Gamma$ is a discrete additive subgroup of the group $(\mathbb R^s,+)$. A nonzero node $u\in \Gamma$ is called a relative minimum of $\Gamma$ if there exists no other nonzero node $v\in \Gamma\setminus\{0\}$ such that and at least one of these inequalities is strict. We denote the set of relative minima of the lattice $\Gamma$ by $\mathfrak M(\Gamma)$.For any $a\in (\mathbb Z_N^*)^s$ set
$$
\begin{equation*}
\Gamma_N(a)=\{x\in \mathbb Z^s\colon a\cdot x \equiv 0\ (\operatorname{mod} N)\}.
\end{equation*}
\notag
$$
It follows from Minkowski’s convex body theorem that
$$
\begin{equation}
H(u) \leqslant N \quad \text{for all } u\in \mathfrak M(\Gamma_N(a)).
\end{equation}
\tag{5.1}
$$
Theorem (see [8], Theorem 1). Let $s\geqslant 2$, $N\in \mathbb N$ and $a\in \mathbb Z^s\setminus\{0\}$. Then By (5.1) and (5.2) there exists a positive constant $C_0(s)$ depending only on $s$ such that
$$
\begin{equation}
D(K_N(a)) \leqslant C_0(s)\mathop{{\sum}'}_{H(x)\leqslant N} \frac{\delta_N(a\cdot x)}{H(x)}.
\end{equation}
\tag{5.3}
$$
For every $T\in [1,N]$ we set
$$
\begin{equation*}
\begin{aligned} \, \Theta_N(T) &=\biggl\{x\in \mathbb Z^s\setminus\{0\}\colon \frac{N}{T} \leqslant H(x)\leqslant N\biggr\}, \\ \Theta'_N(T) &=\Bigl\{x\in \Theta_N(T)\colon \min_{1\leqslant j \leqslant s} |x_j| \geqslant 2\tau^3(N) \ln^{s+2} N\Bigr\} \end{aligned}
\end{equation*}
\notag
$$
and Proof. Consider an arbitrary $t\in\{2,\dots,s\}$. By [8], Lemma 13,
$$
\begin{equation*}
\sum_{a\in (\mathbb Z_N^*)^t} \sum_{NT^{-1} \leqslant |x_1 \cdots x_t| \leqslant N} \frac{\delta_N(a\cdot x)}{H(x)} \underset{t}\ll \frac{\varphi^t (N) \ln^{t-1} N}{N} \ln T \ll \frac{\varphi^t(N) \ln^{t-1} N}{N} \ln\ln N.
\end{equation*}
\notag
$$
Therefore, the left-hand side of (5.4) does not exceed
$$
\begin{equation*}
G(N,T)+O_s \biggl(\frac{\varphi^{s-1} (N) \ln^{s-2} N}{N} \ln \ln N\biggr),
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
G(N,T)=\sum_{a\in (\mathbb Z_N^*)^s} \sum_{\substack{x\in \Theta''_N(T) \\ x_1 \dotsb x_s \neq 0}} \frac{\delta_N(a\cdot x)}{H(x)} \underset{s}\ll \sum_{a\in (\mathbb Z_N^*)^s}\, \sum_{\substack{x\in \mathbb N^s,\, NT^{-1}\leqslant H(x)\leqslant N\\ x_1 \leqslant 2^h}} \frac{\delta_N(a\cdot x)}{H(x)},
\end{equation*}
\notag
$$
and $h=\log_2 (2\tau^3(N) \ln^{s+2} N)$. It can readily be proved that
$$
\begin{equation*}
G(N,T) \underset{s}\ll \sum_{k} \sum_{\substack{2^{k_j}\leqslant x_j < 2^{k_{j+1}} \\ 1\leqslant j\leqslant s}} \sum_{a\in (\mathbb Z_N^*)^s} \frac{\delta_N(a\cdot x)}{H(x)} \leqslant \sum_{k} \frac{1}{2^{|k|_1}} \mathcal A_N^{(s)}(2^{k_1},\dots, 2^{k_s};0),
\end{equation*}
\notag
$$
where $\sum_k$ is the sum with respect to $k\in \mathbb Z^s_+$ such that $k_1 \leqslant h$, $\log_2(NT^{-1})-s \leqslant |k|_1 \leqslant\log_2 N$. Since $|k|_1 \geqslant \log_2(N T^{-1})-s$ and $T\leqslant\sqrt N$, it follows that
$$
\begin{equation*}
\max_{1\leqslant j\leqslant s} k_j \geqslant \frac{|k|_1}{s} \geqslant \frac{\log_2 N}{2s} -1\quad\!\!\text{and}\!\!\quad \max\{2^{k_1},\dots, 2^{k_s}\} \geqslant \frac{N^{1/(2s)}}{2} \underset{s}\gg \tau^3(N) \ln^{s+2} N.
\end{equation*}
\notag
$$
Using these relations and Corollary 2 we obtain
$$
\begin{equation*}
\mathcal A_N^{(s)}(2^{k_1},\dots, 2^{k_s};0) \underset{s}\ll \frac{\varphi^s(N)}{ N} 2^{|k|_1}.
\end{equation*}
\notag
$$
Thus,
$$
\begin{equation*}
\begin{aligned} \, \frac{N}{\varphi^s(N)} G(N,T) &\underset{s}\ll \sum_{k} 1 =\sum_{\log_2(NT^{-1})-s \leqslant k_0 \leqslant\log_2 N}\, \sum_{k_1+\dots+k_s=k_0,\, k_1 \leqslant h} 1 \\ &\underset{s}\ll h \log_2^{s-2} N \sum_{\log_2(NT^{-1})-s \leqslant k_0 \leqslant\log_2 N} 1 \ll h (\log_2 N)^{s-2} \log_2 T. \end{aligned}
\end{equation*}
\notag
$$
Taking (3.1) into account we conclude that
This completes the proof of Lemma 9. Remark 5. Let $X$ be a finite subset of $(0,+\infty)$, and let $\mu$ be the arithmetic mean of the numbers in $X$. For any $\eta> 0$ the following Markov inequality holds: This follows from Markov’s inequality and Lemma 9. Lemma 10. Let $s \!\geqslant\! 3$, $\gamma_0 \!\in\! (1,+\infty)$ and $T \!\in\! (1,+\infty)$, where ${\ln\ln N\!\ll_s\!\ln T \!\leqslant\!\ln N}$. Then for any $\gamma\geqslant \gamma_0$, Proof. Let
$$
\begin{equation*}
R_j = \frac{2^{j} N}{2^{[\log_2 T]}}, \qquad 0\leqslant j\leqslant [\log_2 T],
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\Theta_j=\biggl\{x\in \mathbb Z^s\colon \frac{R_j}{2} < H(x)\leqslant R_j, \ \min_{1\leqslant j\leqslant s} |x_j| \geqslant 2\tau^3(N) \ln^{s+2} N \biggr\}.
\end{equation*}
\notag
$$
Then
$$
\begin{equation*}
\Theta'_N(T) \subset \bigcup_{0\leqslant j\leqslant\log_2 T} \Theta_j.
\end{equation*}
\notag
$$
We set where $m$ is an absolute constant such that $\sum_{j\geqslant 0} (j+m)^{-2} < 1$. Then
Let $a\in (\mathbb Z_N^*)^s$ and
$$
\begin{equation*}
\sum_{x\in \Theta'_N(T)} \frac{\delta_N(a\cdot x)}{H(x)} \geqslant 3\gamma \frac{2^{s+1}}{(s-1)!}\frac{\log_2^{s-1} N}{N} \log_2T.
\end{equation*}
\notag
$$
Then there is an index $j$ satisfying the condition
$$
\begin{equation}
\sum_{x\in \Theta_j} \delta_N(a\cdot x) > \eta_j \frac{2^{s+1}}{(s-1)!} \frac{R_j \log_2^{s-1} R_j}{N},
\end{equation}
\tag{5.7}
$$
where $\eta_j=\gamma \lambda_j/2$. Indeed, otherwise
$$
\begin{equation*}
\begin{aligned} \, \sum_{x\in \Theta'_N(T)} \frac{\delta_N(a\cdot x)}{H(x)} &\leqslant\sum_{0\leqslant j \leqslant\log_2 T} \sum_{x\in \Theta_j} \frac{\delta_N(a\cdot x)}{H(x)} \\ &\leqslant\sum_{0\leqslant j \leqslant\log_2 T} \frac{2}{R_j} \cdot \eta_j \frac{2^{s+1}}{(s-1)!} \frac{R_j \log_2^{s-1} R_j}{N} \\ &\leqslant\gamma \frac{2^{s+1}}{(s-1)!} \frac{\log_2^{s-1} N}{N} \sum_{0\leqslant j \leqslant\log_2 T} \lambda_j \\ &< 3\gamma \frac{2^{s+1}}{(s-1)!} \frac{\log_2^{s-1} N}{N} \log_2 T. \end{aligned}
\end{equation*}
\notag
$$
It follows from (5.7) that the left-hand side of (5.6) does not exceed
$$
\begin{equation*}
\frac{1}{\varphi^s(N)} \sum_{0\leqslant j\leqslant\log_2 T} L_j,
\end{equation*}
\notag
$$
where $L_j$ is the number of $a\in (\mathbb Z_N^*)^s$ for which (5.7) holds.
Since $\ln T \gg_s \ln\ln N$, we can assume without loss of generality that
$$
\begin{equation*}
\frac{\log_2 T}{2((\log_2 T)^{1/3}+m)^2} \geqslant 1.
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
\text{if } j> (\log_2 T)^{1/3}, \quad\text{then } \eta_j=\gamma \geqslant \gamma_0,
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\text{if } j\leqslant (\log_2 T)^{1/3}, \quad\text{then } \eta_j=\frac{\gamma \log_2 T}{2(j+m)^2} \geqslant \frac{\gamma \log_2 T}{2((\log_2 T)^{1/3}+m)^2} \geqslant \gamma\geqslant \gamma_0.
\end{equation*}
\notag
$$
It is obvious that $\Theta_j \subset \Omega_N(R_j)$ (the set $\Omega_N(R)$ was defined in § 3). Therefore, it follows from (5.7) that
$$
\begin{equation*}
\sum_{x\in \Omega_N(R_j)} \delta_N(a\cdot x) \geqslant\sum_{x\in \Theta_j} \delta_N(a\cdot x) >\eta_j \frac{2^{s+1}}{(s-1)!} \frac{R_j \log_2^{s-1} R_j}{N}.
\end{equation*}
\notag
$$
Using Corollary 5 we obtain
$$
\begin{equation*}
\frac{L_j}{\varphi^s(N)} \underset{s,\gamma_0} \ll \frac{N}{\eta_j^2 R_j \ln^{s-1} N} =\frac{4\cdot 2^{[\log_2 T]}}{\gamma^2 \lambda_j^2 2^{j} \ln^{s-1} N}.
\end{equation*}
\notag
$$
Thus, the left-hand side of (5.6) does not exceed
$$
\begin{equation*}
\begin{aligned} \, \frac{1}{\varphi^s(N)} \sum_{0\leqslant j\leqslant\log_2 T} L_j &\underset{s,\gamma_0}\ll \frac{T}{\gamma^2 \ln^{s-1} N} \sum_{0\leqslant j \leqslant\log_2 T}\frac{1}{ \lambda_j^2 2^{j}} \\ &\leqslant \frac{T}{\gamma^2 \ln^{s-1} N} \biggl( \sum_{j\geqslant 0} \frac{(j+m)^4}{2^j \log_2^2 T} +\sum_{j> (\log_2 T)^{1/3}} \frac{1}{4\cdot 2^j} \biggr) \\ &\ll \frac{T}{\gamma^2 (\ln N)^{s-1} (\log_2 T)^2} . \end{aligned}
\end{equation*}
\notag
$$
This completes the proof of Lemma 10. Proof of Theorem 2. Set
$$
\begin{equation*}
\begin{gathered} \, T=\lambda (\ln N)^{s-1} \ln\ln N, \\ \mu_0=\frac{\ln^{s-1} N}{N} \ln\ln N\quad\text{and} \quad \widetilde \mu=3 \frac{2^{s+1}}{(s-1)!} \,\frac{\log_2^{s-1} N}{N} \log_2 T. \end{gathered}
\end{equation*}
\notag
$$
Since $\ln \lambda\ll_s \ln\ln N$, it follows that $\ln T \asymp_s \ln\ln N$. Hence $\widetilde \mu \ll_s \mu_0$, that is, there is a positive constant $C_1(s)$ depending only on $s$ such that $\widetilde \mu \leqslant C_1(s)\mu_0$. Let ${C(s)=3 C_0(s)C_1(s)}$, where $C_0(s)$ is the constant from (5.3).
If $a\in (\mathbb Z_N^*)^s$ and $D(K_N(a)) \geqslant \lambda C(s) \mu_0$, then
$$
\begin{equation*}
\mathop{{\sum}'}_{H(x) \leqslant N} \frac{\delta_N(a\cdot x)}{H(x)} \geqslant \frac{1}{C_0(s)} D(K_N(a)) \geqslant \frac{\lambda C(s) \mu_0}{ C_0(s)} =3 \lambda C_1(s)\mu_0 \geqslant 3\lambda \widetilde \mu
\end{equation*}
\notag
$$
by (5.3). Therefore, the number of points $a\,{\in}\, (\mathbb Z_N^*)^s$ such that $D(K_N(a))\,{\geqslant}\, \lambda C(s) \mu_0$ does not exceed
$$
\begin{equation*}
M=\biggl\{a\in (\mathbb Z_N^*)^s\colon \mathop{{\sum}'}_{H(x) \leqslant N} \frac{\delta_N(a\cdot x)}{H(x)} \geqslant 3\lambda \widetilde \mu\biggr\}.
\end{equation*}
\notag
$$
It can readily be seen that $M\leqslant M_1+M_2+M_3$, where
$$
\begin{equation*}
\begin{aligned} \, M_1 &=\biggl\{a\in (\mathbb Z_N^*)^s\colon q_N(a) \leqslant\frac{N}{T}\biggr\}, \\ M_2 &=\biggl\{a\in (\mathbb Z_N^*)^s\colon \sum_{x\in \Theta'_N (T)} \frac{\delta_N(a\cdot x)}{H(x)} \geqslant 2\lambda \widetilde \mu\biggr\}, \\ M_3 &=\biggl\{a\in (\mathbb Z_N^*)^s\colon \sum_{x\in \Theta''_N (T)} \frac{\delta_N(a\cdot x)}{H(x)} \geqslant \lambda \widetilde \mu\biggr\}. \end{aligned}
\end{equation*}
\notag
$$
From Theorem 1, Lemma 10 (for $\eta_0=2$) and Corollary 6 we conclude that
$$
\begin{equation*}
\begin{gathered} \, M_1 \underset{s}\ll\frac{\varphi^s(N)}{\lambda \ln\ln N}, \\ M_2 \underset{s}\ll\varphi^s(N)\frac{ T}{\lambda^2 (\ln N)^{s-1} (\ln T)^2} =\varphi^s(N)\frac{\ln\ln N}{\lambda \ln^2 T} \underset{s}\asymp \frac{\varphi^s(N)}{\lambda \ln\ln N} \end{gathered}
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
M_3 \underset{s}\ll\varphi^s(N) \frac{\ln^{s-1} N}{N \ln\ln N}\, \frac{\ln T}{\lambda \widetilde \mu} \underset{s}\ll \frac{\varphi^s(N)}{\lambda \ln\ln N}.
\end{equation*}
\notag
$$
This completes the proof of Theorem 2. 
Citation in format AMSBIB
\Bibitem{Ill22} |
|
||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|