| Izvestiya: Mathematics |
|
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper) On Romanoff's theorem A. O. Radomskii HSE University, Moscow
Bibliographic databases:
     § 1. IntroductionLet $\varphi$ denote the Euler totient function. It is clear that $1\leqslant \varphi(n)\leqslant n$ for any positive integer $n$. Therefore, if $a_1,\dots, a_{N}$ are positive integers (not necessarily distinct), $s\in \mathbb{N}$, then
$$
\begin{equation*}
\sum_{n=1}^{N} \biggl(\frac{a_{n}}{\varphi(a_{n})}\biggr)^s\geqslant N.
\end{equation*}
\notag
$$
Upper bounds for such sums are of interest. It is well-known that, for any positive integer $s$, there is a positive constant $c(s)$ depending only on $s$ such that
$$
\begin{equation*}
\sum_{n=1}^{N} \biggl(\frac{n}{\varphi (n)}\biggr)^s\leqslant c(s) N
\end{equation*}
\notag
$$
for any positive integer $N$. We prove the following result. Theorem 1.1. Let $0<\alpha <1$ be a real number. Then there is a constant $C(\alpha)>0$ depending only on $\alpha$, such that the following holds. Let $M\geqslant 1$ be a real number, let $a_1,\dots,a_{N}$ be positive integers (not necessarily distinct), $a_{n}\leqslant M$ for all $1\leqslant n \leqslant N$. We define for any positive integer $d$. Let $s$ be a positive integer. Then From the proof of Theorem 1.1 it will follow that $C(\alpha)=c/\alpha$, where $c$ is a positive absolute constant. The following result shows that Theorem 1.1 can not be improved in the following sense: the condition $p\leqslant (\ln M)^{\alpha}$ can not be replaced by $p\leqslant (\ln M)^{o(1)}$. Theorem 1.2. Let $\alpha(M)$, $M=1,2,\dots,$ be a sequence of positive real numbers such that $\alpha(M)\to 0$ as $M\to +\infty$ and $(\ln M)^{\alpha(M)}\geqslant 2$ for all $M\geqslant 3$. Then there is a constant $M_0 >0$ depending only on a sequence $\alpha(M)$ such that, for any positive integer $M\geqslant M_0$, there is a non-empty set $A\subset \{1,\dots,M\}$ such that for any prime $p\leqslant (\ln M)^{\alpha(M)}$ and Here, $c>0$ is an absolute constant. From Theorem 1.1 we obtain Theorem 1.3. Let $\varepsilon$ be a real number with $0<\varepsilon <1$. Then there is a constant $C(\varepsilon)>0$ depending only on $\varepsilon$such that the following holds. Let $x$ and $z$ be real numbers with $x\geqslant 3$ and $(\ln x)^{\varepsilon} \leqslant z \leqslant x$. Let $k$ be a positive integer, let $a_0,\dots, a_k$ be integers with $|a_i| \leqslant x$ for all $0\leqslant i \leqslant k$ and $a_k \neq 0$. By $\delta:= (a_0,\dots, a_k)$ we denote the greatest common divisor of $a_0,\dots, a_k$. Let Let $s$ be a positive integer. Then Corollary 1.1. Let $k$ be a positive integer, let be a polynomial with integer coefficients, $a_k\neq 0$. Then there is a constant $C(R)>0$ depending only on $R$ such that if $s$ is a positive integer and $x$ is a real number with $x\geqslant 1$, then Let $\mathcal{L}=\{L_1,\dots,L_k\}$ be a set of $k$ linear functions with integer coefficients For $L(n)=an+b$, $a, b\in \mathbb{Z}$, we define Modern application of the sieve methods involves the sums
$$
\begin{equation*}
\sum_{(a,b)\in \Omega} \frac{\Delta_{L}}{\varphi(\Delta_{L})}
\end{equation*}
\notag
$$
(see, for example, [1]). Here, $(a,b)$ denotes a vector and $\Omega$ is a finite set in $\mathbb{Z}^2$. The next result follows from Theorem 1.1. Theorem 1.4. Let $0<\varepsilon <1$ be a real number. Then there is a constant $C(\varepsilon)>0$ depending only on $\varepsilon$, such that the following holds. Let $x$ and $z$ be real numbers with $x\geqslant 3$ and $(\ln x)^{\varepsilon} \leqslant z \leqslant x$. Let $a, b_1,\dots, b_k$ be integers with $a\geqslant 1$, $|b_i| \leqslant x$ for all $1\leqslant i \leqslant k$. Let $\mathcal{L}=\{L_1,\dots,L_k\}$ be a set of $k$ linear functions, where $L_{i}(n)=a n+b_i,\ i=1,\dots, k$. For $L(n)=an+b$, $b\in \mathbb{Z}$, we define $\Delta_{L}=a^{k+1}\prod_{i=1}^{k}|b_i - b|$. Let $s$ be a positive integer. Then Theorem 1.4 extends one result of Maynard (Lemma 8.1 in [1]), who obtained the same result but with $s=1$ and $x^{1/10} \leqslant z \leqslant x$. Since $a/\varphi(a) \leqslant c\ln\ln (a+2)$, where $c$ is a positive absolute constant, the right-hand side of (1.2) can be replaced by
$$
\begin{equation*}
\bigl(C(\varepsilon)\ln\ln (a+2) \ln (k+1) \bigr)^ss!\, z.
\end{equation*}
\notag
$$
The same remark is also true for (1.1). We recall some facts on elliptic curves (see, for example, Ch. XXV in [2] for more details). An elliptic curve is given by an equation of the form with one additional condition on the discriminant should not vanish. For convenience, we shall generally assume that the coefficients $A$ and $B$ are integers. One of the properties that make an elliptic curve $E$ such a fascinating object is the existence of a composition law that allows us to “add” points to one another. We augment the plane with an idealized point $\mathcal{O}$. This point $\mathcal{O}$ is called the point at infinity. The law of addition extends to the point $\mathcal{O}$ as follows:
$$
\begin{equation*}
P+(-P)=\mathcal{O}\quad \text{and}\quad P+\mathcal{O}=\mathcal{O}+P=P
\end{equation*}
\notag
$$
for all points $P$ on $E$. Given a prime $p$, by $\mathbb{F}_{p}$ we denote the field of classes of residues modulo $p$. We define
$$
\begin{equation*}
E(\mathbb{F}_{p})=\{(x,y)\in {\mathbb{F}}_{p}^2\colon y^2\equiv x^3+Ax+B\ (\operatorname{mod} p)\}\cup\{\mathcal{O}\}.
\end{equation*}
\notag
$$
Repeated addition and negation allows us to “multiply” points of $E$ by an arbitrary integer $m$. This function from $E$ to itself is called the multiplication-by $m$ map:
$$
\begin{equation*}
\phi_{m}\colon E\to E,\qquad \phi_{m}(P)=mP=\operatorname{sign}(m)(P+\dots+P)
\end{equation*}
\notag
$$
(the sum contains $|m|$ terms). By convention, we also define $\phi_{0}(P)=\mathcal{O}$. The multiplication-by-$m$ map is defined by rational functions. The maps $E\to E$, as defined by rational functions and sending $\mathcal{O}$ to $\mathcal{O}$, are called endomorphisms of $E$. For the most elliptic curves (over the field of complex numbers $\mathbb{C}$) the only endomorphisms are the multiplication-by-$m$ maps. The curves that admit additional endomorphisms are said to have complex multiplication. Let $\pi(x)$ denote the number of primes not exceeding $x$. We will prove Theorem 1.5. Let $E$ be an elliptic curve given by the equation where $A$ and $B$ are integers satisfying $\Delta=4A^3+27B^2\neq 0$. Suppose that $E$ does not have complex multiplication. Let $s$ be a positive integer and $x\geqslant 2$ be a real number. Then where $C(E,s)>0$ is a constant depending only on $E$ and $s$. Let $\mathbb{P}$ denote the set of all prime numbers. In 1934, Romanoff proved the following result. Romanoff’s theorem (see [3]). Let $a\geqslant 2$ be an integer. Then there is a constant $c(a)>0$ depending only on $a$ such that for any real number $x\geqslant 3$. We will prove the following result. Theorem 1.6. Let $A=\{a_{n}\}_{n=1}^{\infty}$ be a sequence of positive integers (not necessarily distinct) and let We note that Romanoff’s theorem follows from Theorem 1.6. From Theorem 1.6 we obtain Theorem 1.7. Let $k\geqslant 2 $ be an integer, and let be a polynomial with integer coefficients, $a_k>0$. For any positive integer $n$, we put Then there are constants $c_1>0$, $c_2>0$, $x_0>0$ depending only on $R$ such that for any real number $x\geqslant x_0$. Corollary 1.2. Let $k\geqslant 2$ be an integer. For any positive integer $n$, we put Corollary 1.2 extends one result of Romanoff, who proved only inequality (1.7). Theorem 1.8. Let $E$ be an elliptic curve given by the equation $y^2=x^3+Ax+B$, where $A$ and $B$ are integers satisfying $\Delta=4A^3+27B^2\neq 0$. Suppose that $E$ does not have complex multiplication. For any positive integer $n$, we put Then there are constants $x_0>0$, $c_1>0$, $c_2(E)>0$, where $x_0$ and $c_1$ are absolute constants, $c_2(E)$ is a constant depending only on $E$, such that for any real number $x\geqslant x_0$. Theorem 1.9. Let $a$ and $b$ be integers, $a\geqslant 2$ and $b\geqslant 2$. Then there are positive constants $c_1 (a,b)$ and $c_2(a,b)$ depending only on $a$ and $b$ such that § 2. NotationIn what follows, $p$, $q$ will denote primes. In particular, the sum $\sum_{p\leqslant K}$ should be interpreted as that over all prime numbers not exceeding $K$. By $\pi(x)$ we denote the number of primes not exceeding $x$. Let $\#A$ denote the cardinality of a finite set $A$. By $\mathbb{Z}$, $\mathbb{Z}_{\geqslant 0}$, $\mathbb{N}$, $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$, we denote the sets of all integers, non-negative integers, positive integers, rational numbers, real numbers, and complex numbers, respectively. By $\mathbb{P}$ we denote the set of all prime numbers. Let $(a,b)$ be the greatest common divisor of integers $a$ and $b$, and $[a,b]$ be the least common multiple of integers $a$ and $b$. If $d$ is a divisor of $b-a$, we say that $b$ is congruent to $a$ modulo $d$ (written $b \equiv a\ (\operatorname{mod} d)$). Let $\varphi$ denote the Euler totient function, that is, $\varphi(n)=\#\{1\leqslant m \leqslant n\colon (m,n)=1\}$. We write $\nu(n)$ for the number of distinct prime divisors of $n$, and $\tau(n)$, for the number of positive divisors of $n$. Let $P^{+}(n)$ denote the greatest prime factor of $n$, and $P^{-}(n)$ denote the least prime factor of $n$ (by convention $P^{+}(1)=1$, $P^{-}(1)=+\infty$). We denote by $\mathcal{M}$ the set of square-free numbers, that is, the number $1$ and the positive integers of the form $p_1\cdots p_l$, where $p_1, \dots, p_{l}$ are distinct primes. By definition, we put The symbol ${b\mid a}$ means that $b$ divides $a$. For a fixed $a$, the sum $\sum_{b\mid a}$ and the product $\prod_{b\mid a}$ are taken over all positive divisors of $a$. If $x$ is a real number, then $[x]$ denotes its integral part, and $\lceil x\rceil$ is the smallest integer $n$ such that $n\geqslant x$. We put $\log_{a}x:=\ln x/\ln a$.For real numbers $x,$ $y$ we also use $(x,y)$ to denote the open interval, and $[x,y]$ to denote the closed interval. Also by $(a_1,\dots, a_n)$ we denote a vector. The sense of the notation will be clear from the context. § 3. Proofs Proof of Lemma 3.1. We put $\Omega = \{p\colon p\mid n\text{ and }p>y\}$. There are two cases to consider.
1) Let $\Omega=\varnothing$. Since $n>1$, we have $\nu(n)\geqslant 1$. Hence
$$
\begin{equation*}
\prod_{p\mid n\colon p>y}\biggl(1+\frac{1}{p}\biggr)= \prod_{\varnothing} = 1 \leqslant \exp\frac{\nu(n)}{y}.
\end{equation*}
\notag
$$
2) Suppose that $\Omega\neq\varnothing$. Using the inequality $1+x\leqslant e^{x}$, $x\in \mathbb{R}$, we have
$$
\begin{equation*}
\prod_{p\mid n\colon p>y}\biggl(1+\frac{1}{p}\biggr)\leqslant \exp\biggl(\sum_{p\mid n\colon p>y} \frac{1}{p}\biggr)\leqslant \exp\frac{\nu(n)}{y}.
\end{equation*}
\notag
$$
Lemma 3.1 is proved. Proof. If $n=1$, then the product equals $1$, and the required result is true. Let $n>1$. It is clear that Applying Lemma 3.1 with $y=\ln n$ and (3.1), we obtain
$$
\begin{equation*}
\prod_{p\mid n\colon p>\ln n}\biggl(1+\frac{1}{p}\biggr)\leqslant \exp\frac{\nu(n)}{\ln n} \leqslant \exp\frac1{\ln 2}< 5.
\end{equation*}
\notag
$$
Lemma 3.2 is proved. Lemma 3.3. Let $0<\alpha < 1$ be a real number. Then there is a constant $C(\alpha)>0$ depending only on $\alpha$ such that if $n$ is a positive integer, then Proof. We may assume that $n\geqslant \exp(2^{1/\alpha})$. By $\zeta (s)$ we denote the Riemann zeta function. We have
$$
\begin{equation*}
\begin{aligned} \, \frac{n}{\varphi(n)} &= \prod_{p\mid n} \biggl(1-\frac{1}{p}\biggr)^{-1}=\prod_{p\mid n} \frac{p}{p-1}= \prod_{p\mid n} \frac{p}{p-1} \frac{p}{p+1}\frac{p+1}{p} \\ &\leqslant \prod_{p\mid n} \biggl(1+\frac{1}{p}\biggr) \prod_{p}\frac{1}{1-p^{-2}} =\zeta(2)\prod_{p\mid n} \biggl(1+\frac{1}{p}\biggr)=\frac{\pi^2}{6} \prod_{p\mid n} \biggl(1+\frac{1}{p}\biggr) \\ &= \frac{\pi^2}{6} \prod_{p\mid n\colon p\leqslant (\ln n)^{\alpha}} \biggl(1+\frac{1}{p}\biggr)\prod_{p\mid n\colon (\ln n)^{\alpha} < p\leqslant \ln n} \biggl(1+\frac{1}{p}\biggr) \prod_{p\mid n\colon p> \ln n} \biggl(1+\frac{1}{p}\biggr). \end{aligned}
\end{equation*}
\notag
$$
By Lemma 3.2, the last product does not exceed $5$. It is well-known (see, for example, Ch. 1 in [4]) that
$$
\begin{equation}
B_1 \ln x \leqslant \prod_{p\leqslant x} \biggl(1+\frac{1}{p}\biggr)\leqslant B_2\ln x,\qquad x\geqslant 2,
\end{equation}
\tag{3.2}
$$
where $B_1 >0$ and $B_2>0$ are absolute constants. Hence
$$
\begin{equation*}
\begin{aligned} \, &\prod_{p\mid n\colon (\ln n)^{\alpha}< p\leqslant \ln n} \biggl(1+\frac{1}{p}\biggr) \leqslant \prod_{(\ln n)^{\alpha}< p\leqslant \ln n} \biggl(1+\frac{1}{p}\biggr) \\ &\qquad=\prod_{p\leqslant \ln n} \biggl(1+\frac{1}{p}\biggr) \biggm/ \prod_{ p\leqslant (\ln n)^{\alpha}} \biggl(1+\frac{1}{p}\biggr) \leqslant \frac{B_2 \ln\ln n}{B_1\ln(\ln n)^{\alpha}}= \frac{B_2 \ln\ln n}{B_1 \alpha \ln\ln n}=\frac{B}{\alpha}. \end{aligned}
\end{equation*}
\notag
$$
As a result,
$$
\begin{equation*}
\frac{n}{\varphi(n)}\leqslant \frac{5\pi^2B}{6\alpha} \prod_{p\mid n\colon p\leqslant (\ln n)^{\alpha}} \biggl(1+\frac{1}{p}\biggr)= C(\alpha) \prod_{p\mid n\colon p\leqslant (\ln n)^{\alpha}}\biggl(1+\frac{1}{p}\biggr).
\end{equation*}
\notag
$$
Lemma 3.3 is proved. Let us continue the proof of Theorem 1.1. We may assume that $M\,{\geqslant} \exp (2^{1/\alpha})$. We put
$$
\begin{equation*}
y=(\ln M)^{\alpha}\quad\text{and}\quad S=\sum_{n=1}^{N} \biggl(\frac{a_n}{\varphi (a_n)}\biggr)^s.
\end{equation*}
\notag
$$
Note that $y\geqslant 2$. Let $1\leqslant n \leqslant N$. By Lemma 3.3, we have
$$
\begin{equation*}
\begin{aligned} \, \frac{a_n}{\varphi (a_n)} &\leqslant C(\alpha) \prod_{p\mid a_n\colon p\leqslant (\ln a_n)^{\alpha}} \biggl(1+\frac{1}{p}\biggr) \\ &\leqslant C(\alpha) \prod_{p\mid a_n\colon p\leqslant y} \biggl(1+\frac{1}{p}\biggr)= C(\alpha)\sum_{\substack{d\mid a_n:\\d\in \mathcal{M},\,P^{+}(d)\leqslant y}} \frac{1}{d}. \end{aligned}
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
\begin{aligned} \, S&\leqslant (C(\alpha))^s\sum_{1\leqslant n \leqslant N} \biggl(\sum_{\substack{d_1\mid a_n:\\d_{1}\in \mathcal{M},\,P^{+}(d_{1})\leqslant y}}\frac{1}{d_1}\biggr)\cdots \biggl(\sum_{\substack{d_s\mid a_n:\\ d_{s}\in \mathcal{M},\,P^{+}(d_{s})\leqslant y}}\frac{1}{d_s}\biggr) \\ &=(C(\alpha))^s\sum_{1\leqslant n \leqslant N} \sum_{\substack{d_1\mid a_n,\dots,d_s\mid a_n \\d_1,\dots,d_s \in \mathcal{M}\\ P^{+}(d_1)\leqslant y,\,\dots,\,P^{+}(d_s)\leqslant y}} \frac{1}{d_1\cdots d_s} \\ &\leqslant (C(\alpha))^s\sum_{\substack{1\leqslant d_1 \leqslant M\\ P^{+}(d_1)\leqslant y\\ d_1\in \mathcal{M}}}\cdots \sum_{\substack{1\leqslant d_s \leqslant M\\ P^{+}(d_s)\leqslant y\\ d_s\in \mathcal{M}}} \frac{1}{d_1\cdots d_s} \sum_{\substack{1\leqslant n \leqslant N:\\ d_1\mid a_n,\dots,\,d_s\mid a_n}} 1 \\ &=(C(\alpha))^s\sum_{\substack{1\leqslant d_1 \leqslant M\\ P^{+}(d_1)\leqslant y\\ d_1\in \mathcal{M}}}\cdots \sum_{\substack{1\leqslant d_s \leqslant M\\ P^{+}(d_s)\leqslant y\\ d_s\in \mathcal{M}}} \frac{\omega([d_1,\dots, d_s])}{d_1\cdots d_s}. \end{aligned}
\end{equation*}
\notag
$$
Note that if $d$ and $d'$ are positive integers and $d'\mid d$, then Let $d_1,\dots, d_s$ be integers such that $1\leqslant d_i \leqslant M$, $P^{+}(d_i)\leqslant y$, $d_i\in \mathcal{M}$ for all $1\leqslant i \leqslant s$. Since we have
$$
\begin{equation*}
\omega([d_1,\dots, d_s]) \leqslant \omega\bigl(P^{+}([d_1,\dots, d_s])\bigr).
\end{equation*}
\notag
$$
Next, since we obtain
$$
\begin{equation}
\begin{aligned} \, S&\leqslant(C(\alpha))^s\sum_{\substack{1\leqslant d_1 \leqslant M\\ P^{+}(d_1)\leqslant y\\ d_1\in \mathcal{M}}}\dots \sum_{\substack{1\leqslant d_s \leqslant M\\ P^{+}(d_s)\leqslant y\\ d_s\in \mathcal{M}}} \frac{\omega(P^{+}(d_1\cdots d_s))}{d_1\cdots d_s} \notag \\ &\leqslant (C(\alpha))^s\sum_{\substack{d_{1}\in \mathcal{M}:\\P^{+}(d_1)\leqslant y}} \cdots \sum_{\substack{d_s\in \mathcal{M}\colon\\P^{+}(d_s)\leqslant y}} \frac{\omega(P^{+}(d_1\cdots d_s))}{d_1\cdots d_s}= (C(\alpha))^s S'. \end{aligned}
\end{equation}
\tag{3.3}
$$
It is easy to see that where
$$
\begin{equation*}
S_{p}=\sum_{\substack{d_{1},\dots, d_{s}\in \mathcal{M}:\\ P^{+}(d_{1})\leqslant p,\, \dots, \, P^{+}(d_{s})\leqslant p,\\ \text{and }\exists\, \tau\colon p\mid d_{\tau}}} \frac{1}{d_{1}\cdots d_{s}}.
\end{equation*}
\notag
$$
Give a prime $p$ with $p\leqslant y$ and an integer $\tau$ with $1\leqslant \tau \leqslant s$, we set
$$
\begin{equation*}
S_{p}(\tau)=\sum_{\substack{d_{1},\dots, d_{s}\in \mathcal{M}:\\ P^{+}(d_{1})\leqslant p,\,\dots,\, P^{+}(d_{s})\leqslant p,\\ \text{and } p\mid d_{\tau}}} \frac{1}{d_{1}\cdots d_{s}}.
\end{equation*}
\notag
$$
Applying (3.2), we have (here, the product is over primes $q$)
$$
\begin{equation*}
\begin{aligned} \, S_{p}(\tau) &\leqslant \frac{1}{p} \sum_{\substack{d_{1},\dots, d_{s}\in \mathcal{M}:\\ P^{+}(d_{1})\leqslant p,\, \dots,\, P^{+}(d_{s})\leqslant p}} \frac{1}{d_{1}\cdots d_{s}}= \frac{1}{p} \Biggl(\sum_{\substack{d\in \mathcal{M}:\\ P^{+}(d)\leqslant p}}\frac{1}{d}\Biggr)^s \\ &=\frac{1}{p}\biggl(\prod_{q\leqslant p}\biggl(1+\frac{1}{q}\biggr)\biggr)^s\leqslant \frac{(B_{2}\ln p)^s}{p}. \end{aligned}
\end{equation*}
\notag
$$
It is easy to see that We obtain
$$
\begin{equation*}
S_{p} \leqslant s \frac{(B_{2}\ln p)^s}{p}\leqslant \frac{(2B_{2}\ln p)^s}{p}.
\end{equation*}
\notag
$$
We may assume that $2B_{2}\geqslant 1$. Applying (3.4) and taking into account that $\omega(1)= N$ and $y=(\ln M)^{\alpha}$, we obtain
$$
\begin{equation*}
S'\leqslant (2B_{2})^s\biggl(N+\sum_{p\leqslant (\ln M)^{\alpha}} \frac{\omega(p)(\ln p)^s}{p}\biggr).
\end{equation*}
\notag
$$
By (3.3), we have
$$
\begin{equation*}
\begin{aligned} \, S &\leqslant \bigl(2B_{2}C(\alpha)\bigr)^s \biggl(N+\sum_{p\leqslant (\ln M)^{\alpha}}\frac{\omega(p)(\ln p)^s}{p}\biggr) \\ &=\bigl( \widetilde{C}(\alpha)\bigr)^s \biggl(N+\sum_{p\leqslant (\ln M)^{\alpha}}\frac{\omega(p)(\ln p)^s}{p}\biggr), \end{aligned}
\end{equation*}
\notag
$$
where $\widetilde{C}(\alpha)>0$ is a constant depending only on $\alpha$. Theorem 1.1 is proved. Proof of Theorem 1.2. The (large enough) constant $M_0>0$ depending on the sequence $\alpha(M)$ will be chosen later. For now, we assume that $M_0$ satisfy the following conditions: $M_0 \geqslant 100$ and
$$
\begin{equation*}
\alpha(M)\leqslant \frac12,\qquad (\ln M)^{\alpha(M)}\leqslant \frac{\ln M}4
\end{equation*}
\notag
$$
for any $M\geqslant M_0$. Let $M\geqslant M_0$. Setting we have $2\leqslant y \leqslant z/2.$ We define
$$
\begin{equation*}
A=\{1\leqslant n \leqslant M\colon p\mid n\text{ for any }p\in (y,z]\text{ and } p\nmid n\text{ for any } p\leqslant y\}.
\end{equation*}
\notag
$$
We define Hence
$$
\begin{equation*}
\ln Q=\sum_{y<p\leqslant z} \ln p= \theta(z) - \theta(y),\quad \text{where}\quad\theta(x)=\sum_{p\leqslant x}\ln p.
\end{equation*}
\notag
$$
Since (see, for example, Ch. 3 in [4]), there is an absolute constant $c_1>0$ such that $\theta (x) \geqslant x/2$ for all $x\,{\geqslant}\, c_1$. We may assume that $M_0 > \exp (2 c_1)$; therefore, $z=(\ln M)/2\,{\geqslant}\, c_1$ and, hence, $\theta (z)\geqslant z/2 = (\ln M)/4$. It follows from (3.5) that $ \theta(x)\leqslant b x$ for all $x\geqslant 2$, where $b>0$ is an absolute constant. Since $y\geqslant 2$, we obtain
$$
\begin{equation*}
\theta (y) \leqslant b y = b (\ln M)^{\alpha (M)}\leqslant b (\ln M)^{1/2}.
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
\ln Q\geqslant \frac{\ln M}{4} - b (\ln M)^{1/2}\geqslant 100
\end{equation*}
\notag
$$
if $M_0$ is sufficiently large. In particular, $\Omega = \{p\colon y< p \leqslant z\}\neq \varnothing$ and $Q\geqslant 100$. By (3.5), there is an absolute constant $c_2>0$ such that $\theta (x) \leqslant (3/2)x$ for all $x\geqslant c_2$. We may assume that $M_0 > \exp(2c_2)$ and, hence, $z=(\ln M)/2 \geqslant c_2$. Therefore, We obtain This shows that $Q\in A$, and hence, $A\neq\varnothing$.
Thus, $A\subset\{1,\dots, M\}$, $A\neq \varnothing$ and
$$
\begin{equation*}
\#\{n\in A\colon n\equiv 0\ (\operatorname{mod} p)\}=0
\end{equation*}
\notag
$$
for any prime $p\leqslant y=(\ln M)^{\alpha(M)}$. If $n\in A$, then $n>1$, since $Q\mid n$ and $Q\geqslant100$.
Let $n\in A$. Then
$$
\begin{equation*}
\frac{n}{\varphi (n)}=\prod_{p\mid n}\biggl(1-\frac{1}{p}\biggr)^{-1}\geqslant \prod_{y<p\leqslant z}\biggl(1-\frac{1}{p}\biggr)^{-1}= \prod_{p\leqslant z}\biggl(1-\frac{1}{p}\biggr)^{-1}\biggm/ \prod_{p\leqslant y} \biggl(1-\frac{1}{p}\biggr)^{-1}.
\end{equation*}
\notag
$$
Since
$$
\begin{equation*}
D_1 \ln x\leqslant \prod_{p \leqslant x} \biggl(1-\frac{1}{p}\biggr)^{-1}\leqslant D_2 \ln x,\qquad x\geqslant 2,
\end{equation*}
\notag
$$
where $D_1 >0$ and $D_2 >0$ are absolute constants, and $2 \leqslant y \leqslant z/2< z$, we have
$$
\begin{equation*}
\begin{aligned} \, \prod_{p\leqslant y}\biggl(1-\frac{1}{p}\biggr)^{-1} &\leqslant D_2 \ln y= D_2\alpha(M)\ln\ln M, \\ \prod_{p\leqslant z}\biggl(1-\frac{1}{p}\biggr)^{-1} &\geqslant D_1 \ln z= D_1 \ln \biggl(\frac{1}{2}\ln M\biggr)\geqslant \frac{D_1}{2}\ln\ln M. \end{aligned}
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
\frac{n}{\varphi(n)}\geqslant \frac{(D_1/2)\ln\ln M}{D_2 \alpha(M)\ln\ln M}=\frac{c}{\alpha(M)}.
\end{equation*}
\notag
$$
We obtain
$$
\begin{equation*}
\sum_{n\in A}\frac{n}{\varphi (n)}\geqslant \frac{c}{\alpha (M)} \#A,
\end{equation*}
\notag
$$
where $c>0$ is an absolute constant. Theorem 1.2 is proved. Proof of Theorem 1.3. We have
$$
\begin{equation*}
\begin{gathered} \, R(n)=a_k n^k+\dots+ a_0,\qquad a_k\neq 0,\quad \delta=(a_0,\dots,a_k), \\ |a_i|\leqslant x,\quad i=0,\dots, k,\qquad (\ln x)^{\varepsilon} \leqslant z \leqslant x,\quad x\geqslant2. \end{gathered}
\end{equation*}
\notag
$$
We put
$$
\begin{equation*}
\Omega=\{-z\leqslant n \leqslant z\colon R(n)\neq 0\}.
\end{equation*}
\notag
$$
Suppose that $\Omega \neq \varnothing$. We are going to obtain an upper bound for
$$
\begin{equation*}
S =\sum_{n\in \Omega} \biggl(\frac{|R(n)|}{\varphi (|R(n)|)}\biggr)^s.
\end{equation*}
\notag
$$
Putting we have
$$
\begin{equation*}
\begin{gathered} \, \widetilde{R}(n)=\widetilde{a}_{k}n^k+\dots+\widetilde{a}_0,\qquad (\widetilde{a}_{0},\dots, \widetilde{a}_k) = 1, \\ |\widetilde{a}_{i}|\leqslant x,\qquad i=0,\dots, k. \end{gathered}
\end{equation*}
\notag
$$
Since $\varphi (mn)\geqslant \varphi(m)\varphi(n)$ for all positive integers $m$ and $n$, we obtain
$$
\begin{equation}
S=\sum_{n\in \Omega} \biggl(\frac{\delta|\widetilde{R}(n)|} {\varphi (\delta|\widetilde{R}(n)|)}\biggr)^s\leqslant \biggl(\frac{\delta}{\varphi(\delta)}\biggr)^s\sum_{n\in \Omega} \biggl(\frac{|\widetilde{R}(n)|}{\varphi (|\widetilde{R}(n)|)}\biggr)^s= \biggl(\frac{\delta}{\varphi(\delta)}\biggr)^s \widetilde{S}.
\end{equation}
\tag{3.6}
$$
Let $n\in \Omega$. Since $|\widetilde{a}_i|\leqslant x$, $|n|\leqslant z\leqslant x$ and $x\geqslant 2$, we have We put $M= x^{3k}$. We have proved that if $n\in\Omega$ then $|\widetilde{R}(n)| \leqslant M$.
Let $c(\varepsilon)>0$ be such: i) $c(\varepsilon)\geqslant 30$; ii) $\ln x \geqslant 2^{4/\varepsilon}$ for $x\geqslant c(\varepsilon)$; iii) $\bigl(3 (\ln x)^2\bigr)^{\varepsilon/4} \leqslant (\ln x)^{\varepsilon}$ for $x\geqslant c(\varepsilon)$. Let $x \geqslant c(\varepsilon)$. There are two cases to consider. 1) Let $k\geqslant \ln x$. Let $n\in \Omega$, Then
$$
\begin{equation*}
\begin{aligned} \, 1 &\leqslant \frac{|\widetilde{R}(n)|}{\varphi(|\widetilde{R}(n)|)} \leqslant c\ln\ln(|\widetilde{R}(n)|+2)\leqslant c\ln\ln(x^{3k}+2)\leqslant c\ln\ln(x^{4k}) \\ &=c(\ln k+ \ln\ln x+ \ln 4)\leqslant c(\ln k+ 3\ln\ln x)\leqslant c(4 \ln k)=c_1 \ln k. \end{aligned}
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
\widetilde{S}=\sum_{n\in \Omega} \biggl(\frac{|\widetilde{R}(n)|} {\varphi(|\widetilde{R}(n)|)}\biggr)^s \leqslant (c_1 \ln k)^s \# \Omega.
\end{equation*}
\notag
$$
We recall that $(\ln x)^{\varepsilon} \leqslant z \leqslant x$, and, hence, $z\geqslant 1$. Since
$$
\begin{equation*}
\# \Omega = \#\{ -z\leqslant n \leqslant z\colon \widetilde{R}(n)\neq 0\}\leqslant 2z+1 \leqslant 3z,
\end{equation*}
\notag
$$
we have $\widetilde{S}\leqslant (c_2 \ln k)^s z$. Next, $S\leqslant (\delta/\varphi(\delta))^s\widetilde{S}$, and so
$$
\begin{equation*}
S=\sum_{n\in \Omega} \biggl(\frac{|R(n)|}{\varphi(|R(n)|)}\biggr)^s \leqslant \biggl(c_2\frac{\delta}{\varphi(\delta)}\ln k\biggr)^s z.
\end{equation*}
\notag
$$
2) Let $k< \ln x$. We have We take $\alpha = \varepsilon/4$. From the conditions on $c(\varepsilon)$, we obtain
$$
\begin{equation*}
\begin{gathered} \, \ln M =3 k\ln x\geqslant 3 \ln x \geqslant 2^{1/\alpha}, \\ 2\leqslant (\ln M)^{\alpha}\leqslant \bigl(3(\ln x)^2\bigr)^{\alpha}= \bigl(3(\ln x)^2\bigr)^{\varepsilon / 4}\leqslant(\ln x)^{\varepsilon}\leqslant z. \end{gathered}
\end{equation*}
\notag
$$
For any positive integer $d$, we set
$$
\begin{equation*}
\omega(d)=\#\{n\in \Omega\colon \widetilde{R}(n)\equiv 0\ (\operatorname{mod}d)\}.
\end{equation*}
\notag
$$
Let $p$ be a prime number. We have
$$
\begin{equation*}
\omega(p)\leqslant \#\{-z\leqslant n\leqslant z\colon \widetilde{R}(n)\equiv 0\ (\operatorname{mod}p)\}.
\end{equation*}
\notag
$$
Since $(\widetilde{a}_0,\dots, \widetilde{a}_k)=1$, there is a number $\widetilde{a}_i$ such that $\widetilde{a}_i\not \equiv 0\ (\operatorname{mod}p)$. Therefore, the number of solutions of the congruence
$$
\begin{equation}
\widetilde{R}(n)\equiv 0\quad (\operatorname{mod} p)
\end{equation}
\tag{3.7}
$$
is at most $k$. It is clear that the number of solutions is at most $p$. So, the number of solutions of congruence (3.7) is at most $\min (p,k)$. Let $m_1<\dots< m_t$ be all numbers from $\{1,\dots, p\}$ satisfying congruence (3.7) (in this case, $t\leqslant \min (p,k)$). Let $1 \leqslant j \leqslant t$. We have
$$
\begin{equation*}
\#\{-z\leqslant n\leqslant z\colon n\equiv m_j\ (\operatorname{mod}p)\}\leqslant \frac{2z}{p}+1.
\end{equation*}
\notag
$$
We obtain
$$
\begin{equation*}
\omega(p)\leqslant \min(p,k)\biggl(\frac{2z}{p}+1\biggr).
\end{equation*}
\notag
$$
If $p\leqslant (\ln M)^{\alpha}$, then $p\leqslant z$. Therefore, for any $p\leqslant(\ln M)^{\alpha}$. Applying Theorem 1.1, we obtain
$$
\begin{equation*}
\widetilde{S}=\sum_{n\in \Omega} \biggl(\frac{|\widetilde{R}(n)|} {\varphi(|\widetilde{R}(n)|)}\biggr)^s\leqslant (C(\alpha))^s \biggl(\#\Omega +\sum_{p\leqslant (\ln M)^{\alpha}} \frac{\omega(p) (\ln p)^s}{p}\biggr).
\end{equation*}
\notag
$$
Since $\alpha=\varepsilon /4$, we see that $C(\alpha)=C(\varepsilon)>0$ is a constant depending only on $\varepsilon$. Applying (3.8) and taking into account that $\#\Omega \leqslant 2z+1 \leqslant 3z$, we obtain
$$
\begin{equation}
\begin{aligned} \, \widetilde{S} &=\sum_{n\in \Omega} \biggl(\frac{|\widetilde{R}(n)|} {\varphi(|\widetilde{R}(n)|)}\biggr)^s \leqslant (C(\varepsilon))^s \biggl(3z +\sum_{p\leqslant (\ln M)^{\alpha}} \frac{\min(p,k) 3z (\ln p)^s}{p^2}\biggr) \notag \\ &\leqslant (C(\varepsilon))^s \biggl(3z + \! \sum_{p}\frac{\min(p,k) 3z (\ln p)^s}{p^2}\biggr)= (C(\varepsilon))^s 3z \biggl(1 +\!\sum_{p} \frac{\min(p,k) (\ln p)^s}{p^2}\biggr). \end{aligned}
\end{equation}
\tag{3.9}
$$
Proof. Putting we have
Now we induct on $s$. If $s=1$, we have $\Gamma(1,x)=e^{-x}$, and (3.10) holds. Suppose that $s\geqslant 2$ and the claim is true for $s-1$. Then (3.11) and the induction hypothesis gives us
$$
\begin{equation*}
\begin{aligned} \, \Gamma(s,x)&=x^{s-1}e^{-x}+(s-1)\Gamma(s-1,x)\leqslant x^{s-1}e^{-x} + (s-1)(s-1)!\, x^{s-2}e^{-x} \\ &=s!\, x^{s-1}e^{-x}\biggl(\frac{1}{s!}+ \frac{1-1/s}{x}\biggr)\leqslant s!\, x^{s-1}e^{-x} \biggl(1 -\frac{1}{s}+\frac{1}{s!} \biggr) \leqslant s!\, x^{s-1}e^{-x}, \end{aligned}
\end{equation*}
\notag
$$
since $x\geqslant 1$. The claim follows, proving Lemma 3.4s. Lemma 3.5. Let $k$ and $s$ be positive integers. Then where $c$ is a positive absolute constant. Proof. For any positive integer $n$ we put We set For any real number $x\geqslant 2$, we have where $c$ is a positive absolute constant. Since $A(x)=0$ for $1\leqslant x < 2$, we obtain $A(x) \leqslant c x (\ln x)^{s-1}$ for $x\geqslant 1$.
1. We first prove (3.12). We denote the sum in (3.12) by $S_1$. Suppose that $k \geqslant 2$. We put $f(x)=1/x$. By partial summation (see, for example, Theorem 2.1.1 in [5]), we have
$$
\begin{equation*}
S_{1}=\sum_{n\leqslant k} a_{n}f(n)= A(k)f(k) - \int_{1}^{k} A(x)f'(x)\, dx.
\end{equation*}
\notag
$$
Next, we have
$$
\begin{equation*}
A(k)f(k)\leqslant c (\ln k)^{s-1}\leqslant c\, \frac{\ln k}{\ln 2}(\ln k)^{s-1} \leqslant 2c (\ln k)^s
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\begin{aligned} \, -\int_{1}^{k}A(x)f'(x)\, dx &= \int_{1}^{k}\frac{A(x)}{x^{2}}\,dx\leqslant c\int_{1}^{k} \frac{(\ln x)^{s-1}}{x}\, dx \\ &=c\int_{0}^{\ln k} t^{s-1}\, dt= \frac{c}{s} (\ln k)^s\leqslant c (\ln k)^s. \end{aligned}
\end{equation*}
\notag
$$
We obtain $S_{1} \leqslant (3c) (\ln k)^s$.
Finally, if $k=1$, then $S_{1}= 0$, and the previous inequality also holds. This proves inequality (3.12). 2. Now we prove (3.13). We denote the sum in (3.13) by $S_{2}$. We put $f(x)=1/x^{2}$. Applying partial summation, we have
$$
\begin{equation*}
\sum_{n\leqslant u} a_{n}f(n) = A(u)f(u) - \int_{1}^{u}A(x)f'(x)\, dx
\end{equation*}
\notag
$$
for any real number $u\geqslant 1$. Since $A(u)f(u)\to 0$ as $u\to +\infty$, we obtain
$$
\begin{equation*}
\sum_{n=1}^{+\infty}a_{n}f(n)= - \int_{1}^{+\infty} A(x)f'(x)\, dx.
\end{equation*}
\notag
$$
We also have
$$
\begin{equation*}
\sum_{n\leqslant k}a_{n}f(n)= A(k)f(k) - \int_{1}^{k}A(x)f'(x)\, dx.
\end{equation*}
\notag
$$
Therefore,
$$
\begin{equation*}
\begin{aligned} \, S_{2}&=\sum_{n\geqslant k+1} a_{n}f(n)= - \int_{k}^{+\infty} A(x)f'(x)\, dx - A(k)f(k) \leqslant- \int_{k}^{+\infty} A(x)f'(x)\, dx \\ &= 2\int_{k}^{+\infty}\frac{A(x)}{x^{3}}\, dx\leqslant 2c\int_{k}^{+\infty} \frac{(\ln x)^{s-1}}{x^{2}}\,dx = 2 c \int_{\ln k}^{+\infty} t^{s-1}e^{-t}\, dt= 2c I_{k}. \end{aligned}
\end{equation*}
\notag
$$
By Lemma 3.4, for $k\geqslant 3$, we have
$$
\begin{equation*}
I_{k}\leqslant s!\, (\ln k)^{s-1} e^{-\ln k}=s!\, \frac{(\ln k)^{s-1}}{k}\leqslant s!\, \frac{(\ln (k+2))^{s-1}}{k}
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
I_{k} \leqslant \int_{0}^{+\infty} t^{s-1}e^{-t}\, dt= \Gamma(s)= (s-1)!\leqslant s!\, 2 \frac{(\ln (k+2))^{s-1}}{k}
\end{equation*}
\notag
$$
if $k\in \{1, 2\}$. Hence for any positive integer $k$. As a result,
$$
\begin{equation*}
S_{2} \leqslant 4c s! \, \frac{(\ln (k+2))^{s-1}}{k},
\end{equation*}
\notag
$$
proving inequality (3.13), and, therefore, Lemma 3.5. We may assume that $c\geqslant 1$, where $c$ is the constant from Lemma 3.5. Applying Lemma 3.5 and taking into account that $\ln (k+2) \leqslant 2 \ln (k+1)$, we obtain
$$
\begin{equation*}
\begin{aligned} \, \sum_{p\leqslant k}\frac{(\ln p)^s}{p} &\leqslant c \bigl(\ln k\bigr)^s \leqslant c \bigl(\ln (k+1)\bigr)^s \leqslant c^s \bigl(\ln (k+1)\bigr)^s \leqslant c^s s!\, \bigl(\ln (k+1)\bigr)^s, \\ k\sum_{p>k}\frac{(\ln p)^s}{p^2} &\leqslant c s!\, \bigl(\ln (k+2)\bigr)^{s-1}\leqslant c s!\, \bigl(\ln (k+2)\bigr)^s\leqslant c s!\, 2^s \bigl(\ln (k+1)\bigr)^s \\ &\leqslant (2c)^s s! \, \bigl(\ln (k+1)\bigr)^s. \end{aligned}
\end{equation*}
\notag
$$
Since $c^s+(2c)^s\leqslant 2 (2c)^s\leqslant (4c)^s$, we have
$$
\begin{equation*}
\sum_{p}\frac{\min(p,k) (\ln p)^s}{p^2}= \sum_{p\leqslant k}\frac{(\ln p)^s}{p}+ k\sum_{p>k}\frac{(\ln p)^s}{p^2} \leqslant (4c)^s s! \, \bigl(\ln (k+1)\bigr)^s.
\end{equation*}
\notag
$$
Next,
$$
\begin{equation*}
1\leqslant \bigl(\ln (k+2)\bigr)^s\leqslant 2^s\bigl(\ln (k+1)\bigr)^s\leqslant (2c)^ss!\, \bigl(\ln (k+1)\bigr)^s,
\end{equation*}
\notag
$$
and hence
$$
\begin{equation}
1+ \sum_{p}\frac{\min(p,k) (\ln p)^s}{p^2}\leqslant (8c)^ss!\, \bigl(\ln (k+1)\bigr)^s.
\end{equation}
\tag{3.14}
$$
By (3.9) we have
$$
\begin{equation*}
\begin{aligned} \, \widetilde{S}&\leqslant (C(\varepsilon))^s 3z (8c)^ss!\, \bigl(\ln (k+1)\bigr)^s \leqslant (24c C(\varepsilon))^s z s!\, \bigl(\ln (k+1)\bigr)^s \\ &=(C_{1}(\varepsilon))^s z s!\, \bigl(\ln (k+1)\bigr)^s, \end{aligned}
\end{equation*}
\notag
$$
where $C_{1}(\varepsilon)>0$ is a constant depending only on $\varepsilon$. From (3.6) we get
$$
\begin{equation*}
S=\sum_{n\in \Omega} \biggl(\frac{|R(n)|}{\varphi(|R(n)|)}\biggr)^s\leqslant \biggl( C_1(\varepsilon)\frac{\delta}{\varphi(\delta)} \ln (k+1)\biggr)^ss!\, z.
\end{equation*}
\notag
$$
This proves Theorem 1.3 in the case $x\geqslant c(\varepsilon)$. Since $n/\varphi(n) \leqslant c \ln\ln (n+2)$, the claim in the case $3 \leqslant x< c(\varepsilon)$ is trivial. Theorem 1.3 is proved. Proof of Corollary 1.1. We put It is clear that $x_{0}(R)$ is a positive constant depending only on $R$. Suppose that $x\geqslant x_{0}(R)$. Applying Theorem 1.3 with $\varepsilon=1/2$ and $z=x$, we obtain where $\delta=(a_{0},\dots, a_k)$ and $c_{1}(R)= C(1/2)(\delta/\varphi(\delta))\ln (k+1)$ is a positive constant depending only on $R$.
Suppose that $1\,{\leqslant}\, x\,{<}\, x_{0}(R)$. Let $\Omega\,{=}\,\{n:-x \leqslant n \leqslant x$, $ R(n) \neq 0\} \neq \varnothing$. We put
$$
\begin{equation*}
m(R)=\max_{-x_{0}(R)\leqslant n \leqslant x_{0}(R)} |R(n)|+10.
\end{equation*}
\notag
$$
It is clear that $m(R)$ is a positive constant depending only on $R$. For any integer $n$ such that $-x_{0}(R)\leqslant n \leqslant x_{0}(R)$ and $R(n)\neq 0$, we have
$$
\begin{equation*}
\frac{|R(n)|}{\varphi(|R(n)|)} \leqslant |R(n)|\leqslant m(R).
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
\begin{aligned} \, S&=\sum_{\substack{-x \leqslant n \leqslant x\\ R(n)\neq 0}} \biggl(\frac{|R(n)|}{\varphi(|R(n)|)}\biggr)^s\leqslant \sum_{\substack{-x_{0}(R) \leqslant n \leqslant x_{0}(R)\\ R(n)\neq 0}} \biggl(\frac{|R(n)|}{\varphi(|R(n)|)}\biggr)^s \\ &\leqslant (m(R))^s (2 x_{0}(R)+1)\leqslant \bigl(3x_{0}(R)m(R)\bigr)^s s!\, x= (c_{2}(R))^s s!\, x, \end{aligned}
\end{equation*}
\notag
$$
where $c_{2}(R)= 3x_{0}(R)m(R)$ is a positive constant depending only on $R$. If $\Omega = \varnothing$, then $S=0$. This proves the claim with $C(R)=\max (c_{1}(R), c_{2}(R))$. Corollary 1.1 is proved. Proof of Theorem 1.4. We assume that $x\geqslant c(\varepsilon)$, where $c(\varepsilon)$ is a positive constant depending only on $\varepsilon$; the constant (large enough) $c(\varepsilon)$ will be chosen laters.
Suppose that $\Omega:=\{-z \leqslant b\leqslant z\colon \Delta_{L}\neq 0\} \neq \varnothing$. Setting $\Delta (b):= \prod_{i=1}^{k} |b_i - b|$, we have
$$
\begin{equation*}
\frac{\Delta_{L}}{\varphi (\Delta_{L})}\leqslant \frac{a^{k+1} \Delta (b)}{\varphi(a^{k+1})\varphi (\Delta(b))}= \frac{a}{\varphi(a)}\, \frac{\Delta(b)}{\varphi(\Delta(b))}.
\end{equation*}
\notag
$$
Therefore,
$$
\begin{equation}
\sum_{b\in \Omega} \biggl(\frac{\Delta_{L}}{\varphi (\Delta_{L})}\biggr)^s \leqslant \biggl(\frac{a}{\varphi(a)}\biggr)^s \sum_{b\in \Omega} \biggl(\frac{\Delta (b)}{\varphi (\Delta (b))}\biggr)^s.
\end{equation}
\tag{3.15}
$$
To obtain an upper bound for the last sum in (3.15), we apply Theorem 1.1 with $\alpha=\varepsilon/4$.
We put
$$
\begin{equation*}
R(n)=(n-b_1)\cdots (n-b_k)=n^{k}+a_{k-1}n^{k-1}+\dots+ a_0.
\end{equation*}
\notag
$$
Given a prime $p$, we have
$$
\begin{equation*}
\omega(p)=\#\{b\in \Omega\colon \Delta(b)\equiv 0\ (\operatorname{mod}p)\} \leqslant \#\{-z \leqslant b \leqslant z\colon R(b)\equiv 0\ (\operatorname{mod}p)\}.
\end{equation*}
\notag
$$
The number of solutions of the congruence is at most $k$, and it trivially does not exceed $p$. We obtain the number of solutions of congruence (3.16) is at most $\min (p,k)$. Let $m_1<\dots < m_t$ be all numbers from $\{1,\dots, p\}$, satisfying congruence (3.16) (in this case, $t\leqslant \min (p,k)$). Let $1 \leqslant j \leqslant t$. We have
$$
\begin{equation*}
\#\{-z\leqslant b \leqslant z\colon b\equiv m_j\ (\operatorname{mod} p)\} \leqslant \frac{2z}{p}+1.
\end{equation*}
\notag
$$
Hence
$$
\begin{equation}
\omega(p) \leqslant t \biggl(\frac{2z}{p}+1\biggr)\leqslant \min (p,k) \biggl(\frac{2z}{p}+1\biggr).
\end{equation}
\tag{3.17}
$$
Let $b\in \Omega$. Since for all $1 \leqslant i \leqslant k$, we obtain $|R(b)| \leqslant (2x)^{k}=:M$.There are two cases to consider. 1) Let $k\geqslant \ln x$. We may assume that $c(\varepsilon) \geqslant 30$, and therefore, $x \geqslant 30$. We see that $(2x)^{l}+2\leqslant (3x)^{l}$ for any positive integer $l$. we also have $\ln\ln (3t)\leqslant c_0 \ln\ln t$ for any $t\geqslant 30$, where $c_0$ is a positive absolute constant. Let $b\in \Omega$. Then
$$
\begin{equation*}
\begin{aligned} \, \frac{\Delta(b)}{\varphi(\Delta(b))}&=\frac{|R(b)|}{\varphi(|R(b)|)}\leqslant c_{1}\ln\ln(|R(b)|+2)\leqslant c_{1}\ln\ln\bigl((2x)^{k}+2\bigr) \leqslant c_{1}\ln\ln\bigl((3x)^{k}\bigr) \\ &=c_1\bigl(\ln k+ \ln\ln (3x)\bigr)\leqslant c_1(\ln k+ c_0 \ln\ln x) \leqslant c_1(\ln k+ c_0 \ln k)=c_2 \ln k, \end{aligned}
\end{equation*}
\notag
$$
where $c_1$, $c_2= c_1 (1+c_0)$ are positive absolute constants. Noting that $z \geqslant (\ln x)^{\varepsilon}\geqslant 1$, we have Hence
$$
\begin{equation*}
\sum_{b\in \Omega} \biggl(\frac{\Delta(b)}{\varphi(\Delta (b))}\biggr)^s \leqslant (c_2 \ln k)^s\#\Omega \leqslant (c_2 \ln k)^s 3 z.
\end{equation*}
\notag
$$
From (3.15) we obtain
$$
\begin{equation*}
\sum_{b\in \Omega} \biggl(\frac{\Delta_{L}}{\varphi(\Delta_{L})}\biggr)^s \leqslant \biggl(c \frac{a}{\varphi (a)} \ln k \biggr)^s z,
\end{equation*}
\notag
$$
where $c$ is a positive absolute constant.
2) Let $k < \ln x$. Let $c(\varepsilon)$ be such that $\ln (2t)\geqslant 2^{4/\varepsilon}$, $(\ln (2t)\ln t)^{\varepsilon/4}\leqslant (\ln t)^{\varepsilon}$ for any $t\geqslant c(\varepsilon)$. We have
$$
\begin{equation*}
\ln M = k \ln (2x) \geqslant \ln (2x)\geqslant 2^{4/\varepsilon}, \qquad (\ln M)^{\varepsilon/4}\leqslant \bigl(\ln (2x)\ln x\bigr)^{\varepsilon/4}\leqslant (\ln x)^{\varepsilon}\leqslant z.
\end{equation*}
\notag
$$
We see that $2\leqslant (\ln M)^{\varepsilon/4}\leqslant z$, and hence, $z/p \geqslant 1$ for any prime $p \leqslant (\ln M)^{\varepsilon/4}$. From (3.17) we obtain for any prime $p \leqslant (\ln M)^{\varepsilon/4}$. Applying Theorem 1.1, we have
$$
\begin{equation*}
\begin{aligned} \, \sum_{b\in \Omega} \biggl(\frac{\Delta(b)}{\varphi(\Delta (b))}\biggr)^s&\leqslant (C(\varepsilon))^s \biggl(\#\Omega +\sum_{p\leqslant (\ln M)^{\varepsilon/4}} \frac{\omega(p)(\ln p)^s}{p}\biggr) \\ &\leqslant (C(\varepsilon))^s \biggl(3z +\sum_{p\leqslant (\ln M)^{\varepsilon/4}} \frac{3z \min (p,k) (\ln p)^s}{p^2}\biggr) \\ &\leqslant (C(\varepsilon))^s 3z \biggl(1 + \sum_{p} \frac{\min (p,k) (\ln p)^s}{p^2}\biggr). \end{aligned}
\end{equation*}
\notag
$$
By (3.14) we obtain
$$
\begin{equation*}
\sum_{b\in \Omega} \biggl(\frac{\Delta(b)}{\varphi(\Delta (b))}\biggr)^s \leqslant \biggl(C_{1}(\varepsilon) \ln (k+1)\biggr)^s s!\, z,
\end{equation*}
\notag
$$
where $C_{1}(\varepsilon) >0$ is a constant depending only on $\varepsilon$. From (3.15) we obtain
$$
\begin{equation*}
\sum_{b\in \Omega} \biggl(\frac{\Delta_{L}}{\varphi(\Delta_{L})}\biggr)^s\leqslant \biggl(C_{1}(\varepsilon) \frac{a}{\varphi (a)} \ln (k+1)\biggr)^s s!\, z.
\end{equation*}
\notag
$$
This proves Theorem 1.4 in the case $x\geqslant c(\varepsilon)$.
Let $3 \leqslant x < c(\varepsilon)$. Given $b\in \Omega$, we have
$$
\begin{equation*}
|b - b_i| \leqslant |b|+|b_i| \leqslant z + x\leqslant 2x \leqslant 2 c(\varepsilon)
\end{equation*}
\notag
$$
for all $1 \leqslant i \leqslant k$ and hence, $\Delta (b)\leqslant (2 c(\varepsilon))^{k}$. We obtain
$$
\begin{equation*}
\begin{aligned} \, \frac{\Delta (b)}{\varphi (\Delta (b))} &\leqslant c \ln\ln \bigl(\Delta (b) + 2\bigr)\leqslant c \ln\ln \bigl((2 c(\varepsilon))^{k} + 2\bigr)\leqslant c \ln\ln \bigl((3 c(\varepsilon))^{k}\bigr) \\ &= c \bigl(\ln k+ \ln\ln (3 c(\varepsilon))\bigr)\leqslant c\bigl(\ln (k+1) + 2\ln\ln (3 c(\varepsilon)) \ln (k+1)\bigr) \\ &= c_{1}(\varepsilon) \ln (k+1). \end{aligned}
\end{equation*}
\notag
$$
As a result, we have
$$
\begin{equation*}
\sum_{b\in \Omega} \biggl(\frac{\Delta (b)}{\varphi (\Delta (b))}\biggr)^s \leqslant \bigl(c_{1}(\varepsilon) \ln (k+1)\bigr)^s\#\Omega .
\end{equation*}
\notag
$$
Consequently,
$$
\begin{equation*}
\# \Omega \leqslant 2z+1\leqslant 2x+1\leqslant 2 c(\varepsilon)+1\leqslant 3 c(\varepsilon).
\end{equation*}
\notag
$$
Since $z \geqslant (\ln x)^{\varepsilon}$ and $x \geqslant 3$, we have $z\geqslant 1$, and so
$$
\begin{equation*}
\begin{aligned} \, \sum_{b\in \Omega} \biggl(\frac{\Delta (b)}{\varphi (\Delta (b))}\biggr)^s &\leqslant \bigl(c_{1}(\varepsilon) \ln (k+1)\bigr)^s 3 c(\varepsilon) z\leqslant \bigl(c_{1}(\varepsilon) 3 c(\varepsilon) \ln (k+1)\bigr)^s z \\ &= \bigl(c_{2}(\varepsilon) \ln (k+1)\bigr)^s z\leqslant \bigl(c_{2}(\varepsilon) \ln (k+1)\bigr)^s s!\, z, \end{aligned}
\end{equation*}
\notag
$$
where $c_{2}(\varepsilon) >0$ is a constant depending only on $\varepsilon$. From (3.15), we obtain
$$
\begin{equation*}
\sum_{b\in \Omega} \biggl(\frac{\Delta_{L}}{\varphi(\Delta_{L})}\biggr)^s\leqslant \biggl(c_{2}(\varepsilon) \frac{a}{\varphi (a)} \ln (k+1)\biggr)^s s!\, z.
\end{equation*}
\notag
$$
Now the claim follows with $C(\varepsilon)= \max(C_{1}(\varepsilon), c_{2}(\varepsilon))$. Theorem 1.4 is proved. Proof of Theorem 1.5. Given an integer $a$ and a prime $p$, the congruence $y^{2}\equiv a\ (\operatorname{mod} p)$ has at most $2$ solutions, and hence (the first inequality follows from the fact that at least $\mathcal{O}\in E(\mathbb{F}_{p})$). We have
$$
\begin{equation*}
\frac{\#E(\mathbb{F}_{p})}{\varphi(\#E(\mathbb{F}_{p}))}\geqslant 1
\end{equation*}
\notag
$$
for any prime $p$, and therefore, the first inequality in (1.3) is trivial.
Let us prove the second inequality in (1.3). We use the following result of David and Wu (Theorem 2.3, (i) in [6]). Suppose that an elliptic curve $E$ does not have complex multiplication. Let $a$ and $t\geqslant 1 $ be integers. Then
$$
\begin{equation*}
\#\{p\leqslant x\colon \#E(\mathbb{F}_{p})\equiv a\ (\operatorname{mod} t)\}\leqslant C(E) \biggl(\frac{\pi(x)}{\varphi (t)}+ x\exp(-b t^{-2} \sqrt{\ln x}\,)\biggr)
\end{equation*}
\notag
$$
for $\ln x \geqslant c t^{12} \ln t$. Here, $b$ and $c$ are positive absolute constants, and $C(E)>0$ is a constant depending only on $E$.
We assume that $x \geqslant c_0 (s)$, where $c_0 (s)>0$ is a constant depending only on $s$; the (sufficiently large) constant $c_0 (s)$ will be chosen later. Given a positive integer $t$, we have $t^{12}\ln t \leqslant t^{13}$. Therefore,
$$
\begin{equation}
\#\{p\leqslant x\colon \#E(\mathbb{F}_{p})\equiv a\ (\operatorname{mod} t)\}\leqslant C(E) \biggl(\frac{\pi(x)}{\varphi (t)}+ x\exp(-b t^{-2} \sqrt{\ln x}\,)\biggr)
\end{equation}
\tag{3.19}
$$
for $1 \leqslant t \leqslant (c_1 \ln x)^{1/13}$, where $c_1=1/c$ is a positive absolute constant. We see from (3.18) that $\#E(\mathbb{F}_{p})\leqslant 3p$ for any prime $p$. We put $M=3x$. Hence $\#E(\mathbb{F}_{p})\leqslant M$ for any prime $p\leqslant x$. We have
$$
\begin{equation}
2 \leqslant (\ln M)^{1/26}\leqslant (c_1 \ln x)^{1/13}
\end{equation}
\tag{3.20}
$$
for sufficiently large $c_0(s)$.
Applying Theorem 1.1 with $\alpha=1/26$, we have
$$
\begin{equation}
\sum_{p\leqslant x} \biggl(\frac{\#E(\mathbb{F}_{p})} {\varphi(\#E(\mathbb{F}_{p}))}\biggr)^s\leqslant c^s\biggl(\pi(x)+ \sum_{q \leqslant (\ln M)^{1/26}} \frac{\omega(q) (\ln q)^s}{q}\biggr),
\end{equation}
\tag{3.21}
$$
where $c$ is a positive absolute constant, and
$$
\begin{equation*}
\omega (q) = \#\{p\leqslant x\colon \#E(\mathbb{F}_{p})\equiv 0\ (\operatorname{mod} q)\}.
\end{equation*}
\notag
$$
It follows from (3.19) (with $a=0$) and (3.20) that
$$
\begin{equation*}
\omega (q) \leqslant C(E) \biggl(\frac{\pi(x)}{\varphi (q)}+ x \exp(-b q^{-2} \sqrt{\ln x}\,) \biggr)
\end{equation*}
\notag
$$
for any prime $q \leqslant (\ln M)^{1/26}$. Hence
$$
\begin{equation}
\begin{aligned} \, &\sum_{q \leqslant (\ln M)^{1/26}} \frac{\omega(q) (\ln q)^s}{q} \notag \\ &\qquad\leqslant C(E) \biggl(\pi(x)\sum_{q \leqslant (\ln M)^{1/26}} \frac{(\ln q)^s}{q\varphi (q)}+x\sum_{q \leqslant (\ln M)^{1/26}} \frac{ (\ln q)^s}{q\exp(b q^{-2} \sqrt{\ln x}\,)}\biggr). \end{aligned}
\end{equation}
\tag{3.22}
$$
Since $\varphi(n) \geqslant c n/\ln\ln (n+2)$ for any positive integer $n$, where $c$ is a positive absolute constant, we have
$$
\begin{equation}
\begin{aligned} \, \sum_{q \leqslant (\ln M)^{1/26}}\frac{(\ln q)^s}{q\varphi (q)}&\leqslant \frac{1}{c} \sum_{q \leqslant (\ln M)^{1/26}}\frac{(\ln q)^s\ln\ln(q+2)}{q^{2}} \notag \\ &\leqslant \frac{1}{c}\sum_{n=1}^{\infty}\frac{(\ln n)^s\ln\ln(n+2)}{n^{2}}= c_{1}(s), \end{aligned}
\end{equation}
\tag{3.23}
$$
where $c_{1}(s)>0$ is a constant depending only on $s$.
Recall that $M=3x$. We have $(\ln (3x))^{1/13}\leqslant 2 (\ln x)^{1/13}$ if $c_{0}(s)$ is large enough. Hence
$$
\begin{equation*}
b\frac{\sqrt{\ln x}}{q^{2}}\geqslant b\, \frac{(\ln x)^{1/2}}{(\ln (3x))^{1/13}} \geqslant \frac{b}{2}\, \frac{(\ln x)^{1/2}}{(\ln x)^{1/13}}=b_{1} (\ln x)^{11/26}
\end{equation*}
\notag
$$
for any prime $q\leqslant (\ln (3x))^{1/26}$, where $b_{1}=b/2$ is a positive absolute constant. We obtain
$$
\begin{equation*}
x\sum_{q \leqslant (\ln M)^{1/26}}\frac{ (\ln q)^s}{q\exp(b q^{-2} \sqrt{\ln x}\,)} \leqslant x\exp\bigl(-b_{1} (\ln x)^{11/26}\bigr)\sum_{q \leqslant (\ln M)^{1/26}}\frac{(\ln q)^s}{q}.
\end{equation*}
\notag
$$
Putting $k=[(\ln(3x))^{1/26}]$ and applying Lemma 3.5, we obtain
$$
\begin{equation*}
\begin{aligned} \, \sum_{q \leqslant (\ln M)^{1/26}}\frac{ (\ln q)^s}{q} &= \sum_{q \leqslant k} \frac{ (\ln q)^s}{q} \leqslant c (\ln k)^s\leqslant c \bigl(\ln \bigl((\ln(3x))^{1/26}\bigr)\bigr)^s \\ &=\frac{c}{(26)^s}\bigl(\ln\ln (3x)\bigr)^s, \end{aligned}
\end{equation*}
\notag
$$
where $c$ is a positive absolute constant. We obtain
$$
\begin{equation*}
x\sum_{q \leqslant (\ln M)^{1/26}}\frac{ (\ln q)^s}{q\exp(b q^{-2} \sqrt{\ln x}\,)}\leqslant \frac{c}{(26)^s}\, x \exp\bigl(-b_{1} (\ln x)^{11/26}\bigr)\bigl(\ln\ln (3x)\bigr)^s.
\end{equation*}
\notag
$$
We have $\pi(t) \geqslant at/\ln t$ for any real number $t\geqslant 2$, where $a$ is a positive absolute constant. Let us show that
$$
\begin{equation}
\frac{c}{(26)^s}x \exp\bigl(-b_{1} (\ln x)^{11/26}\bigr) \bigl(\ln\ln (3x)\bigr)^s \leqslant \frac{a x}{(26)^s\ln x}.
\end{equation}
\tag{3.24}
$$
The inequality (3.24) is equivalent to the inequality
$$
\begin{equation*}
c \ln x\bigl(\ln\ln (3x)\bigr)^s\leqslant a\exp\bigl(b_{1} (\ln x)^{11/26}\bigr).
\end{equation*}
\notag
$$
Taking logarithms, we obtain
$$
\begin{equation*}
\ln c + \ln\ln x + s \ln\ln\ln (3x)\leqslant \ln a+ b_{1} (\ln x)^{11/26}.
\end{equation*}
\notag
$$
This inequality holds if $c_{0}(s)$ is large enough. Inequality (3.24) is proved.
As a result, we have
$$
\begin{equation}
x\sum_{q \leqslant (\ln M)^{1/26}}\frac{(\ln q)^s}{q\exp(b q^{-2}\sqrt{\ln x}\,)} \leqslant \frac{\pi(x)}{(26)^s}.
\end{equation}
\tag{3.25}
$$
Substituting (3.23) and (3.25) into (3.22), we obtain
$$
\begin{equation}
\sum_{q \leqslant (\ln M)^{1/26}} \frac{\omega(q) (\ln q)^s}{q}\leqslant C(E) \biggl(c_{1}(s)+\frac{1}{(26)^s}\biggr)\pi(x).
\end{equation}
\tag{3.26}
$$
Substituting (3.26) into (3.21), we obtain
$$
\begin{equation*}
\sum_{p\leqslant x} \biggl(\frac{\#E(\mathbb{F}_{p})} {\varphi(\#E(\mathbb{F}_{p}))}\biggr)^s\leqslant c^s\biggl(1+ C(E) \biggl(c_{1}(s)+\frac{1}{(26)^s}\biggr) \biggr)\pi (x) = C_{1}(E,s) \pi(x),
\end{equation*}
\notag
$$
where $C_{1}(E,s)>0$ is a constant depending only on $E$ and $s$. This proves Theorem 1.5 in the case $x\geqslant c_{0}(s)$.
Suppose that $2 \leqslant x < c_{0}(s)$. For any prime $p\leqslant x$, we have
$$
\begin{equation*}
\#E(\mathbb{F}_{p}) \leqslant 3 p\leqslant 3 x\leqslant 3 c_{0}(s)=c_{2}(s).
\end{equation*}
\notag
$$
Hence, for any prime $p\leqslant x$,
$$
\begin{equation*}
\frac{\#E(\mathbb{F}_{p})}{\varphi(\#E(\mathbb{F}_{p}))}\leqslant \#E(\mathbb{F}_{p})\leqslant c_{2}(s).
\end{equation*}
\notag
$$
As a result, we have
$$
\begin{equation*}
\sum_{p\leqslant x} \biggl(\frac{\#E(\mathbb{F}_{p})} {\varphi(\#E(\mathbb{F}_{p}))}\biggr)^s\leqslant (c_{2}(s))^s \pi (x) = c_{3}(s) \pi (x),
\end{equation*}
\notag
$$
where $c_{3}(s)>0$ is a constant depending only on $s$. The required claim follows with $C(E,s)=\max (C_{1}(E,s), c_{3}(s))$. Theorem 1.5 is proved. Proof of Theorem 1.6. Our proof consists of three steps.
1. Let us fin an obtain an upper bound for Let $x\geqslant x_0$. Since $\operatorname{ord}_{A}(s)<+\infty$, for any positive integer $s$, we have $0\leqslant r(n)< +\infty$ for any positive integer $n$. Since
$$
\begin{equation*}
N_{A}(x)=\sum_{n\leqslant x}\operatorname{ord}_{A}(n),
\end{equation*}
\notag
$$
we have $N_{A}(x)<+\infty$. By the assumption of the theorem, $N_{A}(x)>0$. Hence $0< N_{A}(x)<+\infty$. Since $N_{A}(x)>0$, there is a positive integer $n\leqslant x$ such that $\operatorname{ord}_{A}(n)>0$. Hence
$$
\begin{equation*}
0<\rho_{A}(x):= \max_{n\leqslant x}\operatorname{ord}_{A}(n)<+\infty.
\end{equation*}
\notag
$$
It can be shown that
$$
\begin{equation*}
\sum_{n\leqslant x} (r(n))^{2} =\sum_{\substack{p_1, p_2\in \mathbb{P}\\ j, k\in \mathbb{N}:\\ p_1+a_j\leqslant x\\ p_2+a_k\leqslant x\\ p_1+a_j=p_2+a_k}} 1 = \sum_{\substack{\dots\\ p_1=p_2}}1+\sum_{\substack{\dots\\ p_1<p_2}}1+ \sum_{\substack{\dots\\ p_1>p_2}}1= T_1+ T_2 + T_3.
\end{equation*}
\notag
$$
It is easy to see that $T_2=T_3$. Let us estimate $T_1$. We have
$$
\begin{equation*}
T_1= \sum_{\substack{p_1\in \mathbb{P}:\\ p_1\leqslant x}}\, \sum_{\substack{j\in \mathbb{N}:\\ a_j\leqslant x-p_1 }}\, \sum_{\substack{k\in \mathbb{N}:\\ a_k=a_j}}1.
\end{equation*}
\notag
$$
Since
$$
\begin{equation*}
\sum_{\substack{k\in \mathbb{N}:\\ a_k=a_j}}1=\operatorname{ord}_{A}(a_j),
\end{equation*}
\notag
$$
we have
$$
\begin{equation*}
T_1\leqslant \sum_{\substack{p_1\in \mathbb{P}:\\ p_1\leqslant x}}\, \sum_{\substack{j\in \mathbb{N}:\\ a_j\leqslant x }} \operatorname{ord}_{A}(a_j)= \sum_{\substack{j\in \mathbb{N}:\\ a_j\leqslant x }} \operatorname{ord}_{A}(a_j) \sum_{\substack{p_1\in \mathbb{P}:\\ p_1\leqslant x}} 1= \pi(x)\sum_{\substack{j\in \mathbb{N}:\\ a_j\leqslant x }} \operatorname{ord}_{A}(a_j).
\end{equation*}
\notag
$$
Next, $a_j \leqslant x$, and hence $\operatorname{ord}_{A}(a_j)\leqslant \rho_{A}(x)$. Therefore,
$$
\begin{equation*}
\sum_{\substack{j\in \mathbb{N}:\\ a_j\leqslant x}} \operatorname{ord}_{A}(a_j)\leqslant \rho_{A}(x)\sum_{\substack{j\in \mathbb{N}:\\ a_j\leqslant x }}1= \rho_{A}(x) N_{A}(x).
\end{equation*}
\notag
$$
By Chebyshev’s theorem, $\pi(x)\leqslant b x/\ln x$, where $b>0$ is an absolute constant, and hence
$$
\begin{equation*}
T_1 \leqslant b\, \frac{x}{\ln x}\, \rho_{A}(x) N_{A}(x).
\end{equation*}
\notag
$$
Given $a \in \mathbb{N}$ we set
$$
\begin{equation*}
\pi_{2}(x, a)=\#\{p\leqslant x\colon p+a\text{ is a prime}\}.
\end{equation*}
\notag
$$
Now let us employ the following Schnirelmann’ result [7]. Let $a$ be a positive integer, and let $x\geqslant 4$ be a real number. Then
$$
\begin{equation*}
\pi_{2}(x, a)\leqslant c\,\frac{x}{(\ln x)^2}\, \frac{a}{\varphi(a)},
\end{equation*}
\notag
$$
where $c>0$ is an absolute constant. Let us estimate $T_2$. We have
$$
\begin{equation*}
\begin{aligned} \, T_2&= \sum_{\substack{p_1, p_2\in \mathbb{P}\\ j, k\in \mathbb{N}:\\ p_1+a_j\leqslant x\\ p_2+a_k\leqslant x\\ p_1+a_j=p_2+a_k\\ p_1<p_2}}1 \leqslant \sum_{\substack{j, k\in \mathbb{N}:\\ a_k < a_j\leqslant x}} \sum_{\substack{p\in \mathbb{P}:\\p\leqslant x\\ p+a_j-a_k\text{ is a prime}}}1 = \sum_{\substack{j, k\in \mathbb{N}:\\ a_k < a_j\leqslant x}}\pi_{2}(x, a_j - a_k) \\ &\leqslant c\,\frac{x}{(\ln x)^2}\sum_{\substack{j, k\in \mathbb{N}:\\ a_k < a_j\leqslant x}}\frac{a_j - a_k}{\varphi(a_j - a_k)} = c\,\frac{x}{(\ln x)^2}\sum_{\substack{k\in \mathbb{N}:\\ a_k < x}} \sum_{\substack{j\in \mathbb{N}:\\ a_k < a_j\leqslant x}} \frac{a_j - a_k}{\varphi(a_j - a_k)}. \end{aligned}
\end{equation*}
\notag
$$
We fix a positive integer $k$ with $a_k < x$. Let $j$ be a positive integer such that $a_k < a_j\leqslant x$. Then $0< a_j - a_k\leqslant x$. Applying Theorem 1.1 with $s=1$, $M=x$ and $\alpha$ from the assumption of the theorem, we obtain
$$
\begin{equation*}
\sum_{\substack{j\in \mathbb{N}:\\ a_k < a_j\leqslant x}} \frac{a_j - a_k}{\varphi(a_j - a_k)}\leqslant C(\alpha) \biggl(l+\sum_{p\leqslant (\ln x)^{\alpha}}\frac{\omega(p) \ln p}{p}\biggr),
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
l=\#\{j\in \mathbb{N}\colon a_k<a_j\leqslant x\}\leqslant \#\{j\in \mathbb{N} \colon a_j\leqslant x\}=N_{A}(x)
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\omega(p)=\#\{j\in \mathbb{N}\colon a_k<a_j\leqslant x\text{ and }a_j\equiv a_k\ (\operatorname{mod} p)\}.
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
\begin{aligned} \, &\sum_{\substack{j\in \mathbb{N}:\\ a_k < a_j\leqslant x}} \frac{a_j - a_k}{\varphi(a_j - a_k)} \\ &\quad\leqslant C(\alpha)\biggl(N_{A}(x)+\sum_{p\leqslant (\ln x)^{\alpha}} \frac{\#\{j\in \mathbb{N}\colon a_k<a_j\leqslant x\text{ and } a_j\equiv a_k\ (\operatorname{mod} p)\} \ln p}{p}\biggr). \end{aligned}
\end{equation*}
\notag
$$
As a result,
$$
\begin{equation*}
\begin{aligned} \, T_2 &\leqslant c\,\frac{x}{(\ln x)^2}\sum_{\substack{k\in \mathbb{N}:\\ a_k < x}}C(\alpha)\biggl(N_{A}(x) \\ &\qquad +\sum_{p\leqslant (\ln x)^{\alpha}}\frac{\#\{j\in \mathbb{N} \colon a_k<a_j\leqslant x\text{ and }a_j\equiv a_k\ (\operatorname{mod} p)\} \ln p}{p}\biggr) \\ &\leqslant c C(\alpha)\,\frac{x}{(\ln x)^2}(N_{A}(x))^{2}+ c C(\alpha)\,\frac{x}{(\ln x)^2} \\ &\qquad\times \sum_{\substack{k\in \mathbb{N}:\\ a_k < x}}\, \sum_{p\leqslant (\ln x)^{\alpha}}\frac{\#\{j\in \mathbb{N}\colon a_k<a_j\leqslant x\text{ and }a_j\equiv a_k\ (\operatorname{mod} p)\}\ln p}{p}. \end{aligned}
\end{equation*}
\notag
$$
By the assumption of the theorem,
$$
\begin{equation*}
\sum_{\substack{k\in \mathbb{N}:\\ a_k < x}}\, \sum_{p\leqslant (\ln x)^{\alpha}} \frac{\#\{j\in \mathbb{N}\colon a_k<a_j\leqslant x\text{ and }a_j\equiv a_k\ (\operatorname{mod} p)\} \ln p}{p}\leqslant \gamma_{2} (N_{A}(x))^{2}.
\end{equation*}
\notag
$$
Now we have
$$
\begin{equation*}
T_2\leqslant c_{0}(\gamma_2, \alpha)\,\frac{x}{(\ln x)^2}\, (N_{A}(x))^{2},
\end{equation*}
\notag
$$
where $c_{0}(\gamma_2,\alpha)>0$ is a constant depending only on $\gamma_2$ and $\alpha$.
We obtain
$$
\begin{equation*}
\begin{aligned} \, \sum_{n\leqslant x} \bigl(r(n)\bigr)^{2}&= T_1+T_2+T_3=T_1+2T_2 \\ &\leqslant b\, \frac{x}{\ln x}\, \rho_{A}(x) N_{A}(x) + 2c_{0}(\gamma_2, \alpha)\,\frac{x}{(\ln x)^2}\, (N_{A}(x))^{2} \\ &\leqslant c(\gamma_2, \alpha)\,\frac{x}{(\ln x)^2}\, N_{A}(x) \bigl(\rho_{A}(x)\ln x+ N_{A}(x)\bigr), \end{aligned}
\end{equation*}
\notag
$$
where $c(\gamma_2, \alpha)=b+2c_{0}(\gamma_2, \alpha)>0$ is a constant depending only on $\gamma_2$ and $\alpha$.
2. Let us obtain a lower bound for
$$
\begin{equation*}
\sum_{\substack{n\leqslant x:\\ r(n)\geqslant b_1 \gamma_1 (N_{A}(x)/\ln x)}} r(n),
\end{equation*}
\notag
$$
where $b_1>0$ is some absolute constant, which will be defined later.
By the assumption of the theorem $N_{A}(x/2)\geqslant \gamma_1 N_{A}(x)>0$. We also have $N_{A}(x/2)<+\infty$. Hence $0< N_{A}(x/2)<+\infty$. Since $x\geqslant x_0\geqslant 10$, we have
$$
\begin{equation*}
\pi(x/2)\geqslant b\,\frac{x/2}{\ln x/2}\geqslant\frac{b}{2}\,\frac{x}{\ln x}= b_0\, \frac{x}{\ln x},
\end{equation*}
\notag
$$
where $b_0>0$ is an absolute constant.
Next,
$$
\begin{equation*}
\sum_{n\leqslant x} r(n)\geqslant \pi\biggl(\frac{x}2\biggr) N_{A}\biggl(\frac{x}2\biggr)\geqslant b_{0}\gamma_{1}\, \frac{x}{\ln x}\, N_{A}(x),
\end{equation*}
\notag
$$
and so,
$$
\begin{equation*}
\begin{aligned} \, \sum_{\substack{n\leqslant x:\\ r(n)< (b_{0}\gamma_{1}N_{A}(x))/ (2\ln x)}} r(n) &< \frac{b_{0}\gamma_{1}}{2}\, \frac{N_{A}(x)}{\ln x} \sum_{\substack{n\leqslant x:\\ r(n)< (b_{0}\gamma_{1}N_{A}(x))/ (2\ln x)}} 1 \\ &\leqslant \frac{b_{0}\gamma_{1}}{2}\, \frac{N_{A}(x)}{\ln x} \sum_{n\leqslant x} 1 \leqslant \frac{b_{0}\gamma_{1}}{2}\, \frac{x}{\ln x}\, N_{A}(x). \end{aligned}
\end{equation*}
\notag
$$
Therefore,
$$
\begin{equation*}
\begin{aligned} \, \sum_{\substack{n\leqslant x:\\ r(n)\geqslant (b_{0}\gamma_{1}N_{A}(x))/ (2\ln x)}} r(n) &= \sum_{n\leqslant x} r(n) - \sum_{\substack{n\leqslant x:\\ r(n)< (b_{0}\gamma_{1}N_{A}(x))/ (2\ln x)}} r(n) \\ &\geqslant \frac{b_{0}\gamma_{1}}{2}\, \frac{x}{\ln x}\, N_{A}(x). \end{aligned}
\end{equation*}
\notag
$$
We set $b_1=b_{0}/2$. Then $b_1>0$ is an absolute constant, and
$$
\begin{equation*}
\sum_{\substack{n\leqslant x:\\ r(n)\geqslant b_1\gamma_1 (N_{A}(x)/\ln x)}} r(n) \geqslant b_1 \gamma_1 \,\frac{x}{\ln x}\, N_{A}(x).
\end{equation*}
\notag
$$
3. Applying the Cauchy–Schwarz inequality, we have
$$
\begin{equation*}
\begin{aligned} \, &\biggl(b_1 \gamma_1 \,\frac{x}{\ln x}\, N_{A}(x)\biggr)^2 \leqslant \Biggl(\sum_{\substack{n\leqslant x:\\ r(n)\geqslant b_1\gamma_1 (N_{A}(x)/\ln x)}} r(n)\Biggr)^{2} \\ &\leqslant \sum_{\substack{n\leqslant x:\\ r(n)\geqslant b_1\gamma_1 (N_{A}(x)/\ln x)}} 1 \, \sum_{\substack{n\leqslant x:\\ r(n)\geqslant b_1\gamma_1 (N_{A}(x)/\ln x)}} (r(n))^{2} \\ &\leqslant \sum_{\substack{n\leqslant x:\\ r(n)\geqslant b_1\gamma_1 (N_{A}(x)/\ln x)}} 1\, \sum_{n\leqslant x} (r(n))^{2} \\ &\leqslant \Biggl(\sum_{\substack{n\leqslant x:\\ r(n)\geqslant b_1\gamma_1 (N_{A}(x)/\ln x)}} 1\Biggr) c(\gamma_2, \alpha)\, \frac{x}{(\ln x)^2}\, N_{A}(x)\bigl(\rho_{A}(x)\ln x+ N_{A}(x)\bigr). \end{aligned}
\end{equation*}
\notag
$$
Therefore,
$$
\begin{equation*}
\sum_{\substack{n\leqslant x:\\ r(n)\geqslant b_1\gamma_1 (N_{A}(x)/\ln x)}} 1\geqslant \frac{(b_1 \gamma_1)^2}{c(\gamma_2, \alpha)}\,x\,\frac{N_{A}(x)}{N_{A}(x)+ \rho_{A}(x)\ln x}.
\end{equation*}
\notag
$$
We put
$$
\begin{equation*}
c_1= b_1\gamma_1,\qquad c_2= \frac{(b_1 \gamma_1)^2}{c(\gamma_2, \alpha)}.
\end{equation*}
\notag
$$
Then $c_1$ and $c_2$ are positive constants depending only on $\gamma_1$ and $\gamma_1$, $\gamma_2$, $\alpha$, respectively, and
$$
\begin{equation*}
\#\biggl\{1\leqslant n \leqslant x\colon r(n)\geqslant c_1 \frac{N_{A}(x)}{\ln x}\biggr\} \geqslant c_2 x\,\frac{N_{A}(x)}{N_{A}(x)+\rho_{A}(x)\ln x}.
\end{equation*}
\notag
$$
Theorem 1.6 is proved. Proof of Theorem 1.7. We will apply Theorem 1.6. We set
$$
\begin{equation*}
\Omega = \{n\in \mathbb{N}\colon R(n)>0\},\qquad A= \{R(n)\colon n\in \Omega\}.
\end{equation*}
\notag
$$
Given a positive integer $m$, we have In particular, $\operatorname{ord}_{A}(m) <+\infty$ for any positive integer $m$, and for any real number $t\geqslant 1$.
There is a positive integer $N_{0}$ depending only on the polynomial $R$ such that
$$
\begin{equation*}
-\frac{a_{k}}{2} t^{k} \leqslant a_{k-1}t^{k-1}+\dots+a_{0}\leqslant \frac{a_{k}}{2} t^{k}
\end{equation*}
\notag
$$
and, for any real number $t \geqslant N_{0}$,
$$
\begin{equation*}
R'(t)=k a_k t^{k-1}+ (k-1)a_{k-1}t^{k-2}+\dots + a_1> 0.
\end{equation*}
\notag
$$
Hence $(a_{k}/2) n^{k} \leqslant R(n) \leqslant 2 a_{k} n^{k}$ and $R(n)< R(n+ 1)$ for any integer $n \geqslant N_{0}$. We put
$$
\begin{equation*}
\widetilde{M}_{2}=\max_{\substack{n\in \mathbb{N}:\\ n\leqslant N_{0}}} R(n).
\end{equation*}
\notag
$$
It is clear that $\widetilde{M}_{2}$ is a positive constant depending only on $R$, and
$$
\begin{equation*}
R(n)\leqslant \widetilde{M}_{2}\leqslant \widetilde{M}_{2} n^{k}
\end{equation*}
\notag
$$
for any integer $n$ such that $n\in \Omega$ and $n\leqslant N_{0}$. Therefore,
$$
\begin{equation*}
R(n) \leqslant \max(\widetilde{M}_{2}, 2a_{k})n^{k} = M_{2} n^{k}
\end{equation*}
\notag
$$
for any $n\in \Omega$.
Setting we have
$$
\begin{equation*}
\widetilde{M}_{1} n^{k} \leqslant \widetilde{M}_{1} (N_{0})^{k}=1 \leqslant R(n)
\end{equation*}
\notag
$$
for any integer $n$ such that $n\in \Omega$ and $n \leqslant N_{0}$. Hence
$$
\begin{equation*}
R(n) \geqslant \min \biggl(\widetilde{M}_{1}, \frac{a_{k}}{2}\biggr) n^{k}= M_{1} n^{k}
\end{equation*}
\notag
$$
for any $n\in \Omega$. As a result, we have for any $n\in \Omega$, where $M_{1}$ and $M_{2}$ are positive constants depending only on $R$.
We have
$$
\begin{equation}
\Omega= \{n_1,\dots, n_{T}, N_{0}, N_{0}+1,\dots\},
\end{equation}
\tag{3.28}
$$
where $n_{1}, \dots, n_{T}$ are positive integers with $n_{1}<\dots < n_{T}< N_{0}$. We may assume that $T>0$. It is clear that $T$ is a positive constant depending only on $R$.
We assume that $x \geqslant x_{0}$, where $x_{0}$ is a positive constant depending only on $R$; the (sufficiently large) constant $x_{0}$ will be chosen later. Let $x_{0} \geqslant M_{2} (N_{0})^{k}$. Applying (3.27), we have
$$
\begin{equation*}
\begin{aligned} \, N_{A}(x)&=\#\{n\in \Omega\colon R(n)\leqslant x\}\leqslant \#\{n\in \Omega\colon M_{1} n^{k}\leqslant x\} \\ &\leqslant \#\biggl\{n\in \mathbb{N}\colon n\leqslant \biggl(\frac{x}{M_{1}}\biggr)^{1/k}\biggr\}= \biggl[\biggl(\frac{x}{M_{1}}\biggr)^{1/k}\biggr]\leqslant \biggl(\frac{x}{M_{1}}\biggr)^{1/k}. \end{aligned}
\end{equation*}
\notag
$$
Let $x_1 = M_{2} (2N_{0}+1)^{k}$. Then $x_{1}$ is a positive constant depending only on $R$. Let $t$ be a real number such that $t \geqslant x_{1}$. Applying (3.27) and (3.28), we have
$$
\begin{equation}
\begin{aligned} \, N_{A}(t)&= \#\{n\in \Omega\colon R(n)\leqslant t\}\geqslant \#\{n\in \Omega\colon M_{2}n^{k}\leqslant t\} \notag \\ &= \#\biggl\{n\in \Omega\colon n\leqslant \biggl(\frac{t}{M_{2}}\biggr)^{1/k}\biggr\}\geqslant \biggl[\biggl(\frac{t}{M_{2}}\biggr)^{1/k}\biggr] - N_{0}+1 \notag \\ &\geqslant \biggl(\frac{t}{M_{2}}\biggr)^{1/k} - N_{0}\geqslant \frac{1}{2} \biggl(\frac{t}{M_{2}}\biggr)^{1/k}. \end{aligned}
\end{equation}
\tag{3.29}
$$
Let $x_{0} \geqslant 2x_1$. Then
$$
\begin{equation}
\frac{1}{2} \biggl(\frac{x}{M_{2}}\biggr)^{1/k} \leqslant N_{A}(x) \leqslant \biggl(\frac{x}{M_{1}}\biggr)^{1/k}.
\end{equation}
\tag{3.30}
$$
In particular, $N_{A}(x)>0$. Since $x/2 \geqslant x_{1}$, from (3.29) we have
$$
\begin{equation*}
N_{A}(x/2) \,{\geqslant}\, \frac{1}{2} \biggl(\frac{x/2}{M_{2}}\biggr)^{1/k} {=}\, \frac{1}{2} \biggl(\frac{M_{1}}{2M_{2}}\biggr)^{1/k} \biggl(\frac{x}{M_{1}}\biggr)^{1/k}{\geqslant}\, \frac{1}{2} \biggl(\frac{M_{1}}{2M_{2}}\biggr)^{1/k} N_{A}(x)\,{=}\, \gamma_{1} N_{A}(x),
\end{equation*}
\notag
$$
where $\gamma_{1}$ is a positive constant depending only on $R$. This proves (1.4) and (1.5).
We may assume that $x_{0}\geqslant R(N_{0})$. Then
$$
\begin{equation*}
\rho_{A}(x) = \max_{n\leqslant x} \operatorname{ord}_{A}(n)\geqslant \operatorname{ord}_{A}\bigl(R(N_{0})\bigr) \geqslant 1.
\end{equation*}
\notag
$$
Hence Let us consider the sum
$$
\begin{equation*}
S= \sum_{\substack{j\in \Omega:\\ R(j)< x}} \, \sum_{p\leqslant \ln x} \frac{\lambda (j, p)\ln p}{p},
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
\lambda (j, p)= \#\{n\in \Omega\colon R(j)< R(n)\leqslant x\text{ and }R(n) \equiv R(j)\ (\operatorname{mod} p)\}.
\end{equation*}
\notag
$$
We fix $j$ lying in the range of summation of the sum $S$. We have
$$
\begin{equation}
\sum_{p\leqslant \ln x} \frac{\lambda (j, p)\ln p}{p}= \sum_{\substack{p\leqslant \ln x\\ p \mid a_k}} \frac{\lambda (j, p)\ln p}{p}+ \sum_{\substack{p\leqslant \ln x\\ (p,a_k)=1}} \frac{\lambda (j, p)\ln p}{p}= S_{1}+ S_{2}.
\end{equation}
\tag{3.32}
$$
Let $p$ be in the range of summation of $S_{1}$. We have $\lambda (j,p) \leqslant N_{A}(x)$, and so
$$
\begin{equation}
\begin{aligned} \, S_{1} \leqslant N_{A}(x)\sum_{\substack{p\leqslant \ln x\\ p \mid a_k}} \frac{\ln p}{p}\leqslant \biggl(\sum_{p \mid a_k} \frac{\ln p}{p} + 1\biggr)N_{A}(x)= c_{1} N_{A}(x), \end{aligned}
\end{equation}
\tag{3.33}
$$
where $c_1$ is a positive constant depending only on $R$.
By Bertrand’s postulate (see, for example, Theorem 3.1.9 in [5]), there is a positive integer $n_0$ such that, for any integer $n \geqslant n_0$, any interval between $n$ and $2 n$ contains a prime. Hence there is a prime $p$, between $n_{0}\,{+}\,a_k$ and $2(n_{0}+a_k)$. We have $p> a_k$ and hence, $(p, a_k)=1$. We also have $\ln x > 2(n_{0}+a_k)$ if $x_0$ is sufficiently large. As a result, $\{p\colon p \leqslant \ln x$, $ (p,a_k)= 1\}\neq\varnothing$. It can be assumed that (see (3.28))
$$
\begin{equation*}
x_{0}\geqslant \max \bigl(R(n_1),\dots, R(n_{T}), R(N_{0}),\dots, R(N_{0}+10)\bigr).
\end{equation*}
\notag
$$
We define Since $R(n)< R(n+1)$ for any integer $n \geqslant N_{0}$, we have
$$
\begin{equation}
\Omega(x)=\{n_{1},\dots, n_{T}, N_{0}, N_{0}+1,\dots, N_{0}+r\}.
\end{equation}
\tag{3.34}
$$
Let $p$ be in the range of summation of $S_{2}$. We define
$$
\begin{equation*}
U=\bigl\{b\in \{0,\dots, p-1\}\colon R(b)\equiv R(j) \ (\operatorname{mod}p)\bigr\}.
\end{equation*}
\notag
$$
Trivially, $\#U \leqslant p$. Since $(p,a_k)=1$, we have $\#U \leqslant k$. We obtain $\#U \leqslant \min (p,k)$. Note that if $b\in \{0,\dots, p-1\}$ is such that $b\equiv j\ (\operatorname{mod} p)$, then $b\in U$. Therefore, Given $b\in U$, we define
$$
\begin{equation*}
\Lambda (b)= \{ t\in \mathbb{Z}\colon b+pt\in \Omega(x)\}.
\end{equation*}
\notag
$$
Using (3.34), we have
$$
\begin{equation*}
\begin{aligned} \, \# \Lambda (b)&\leqslant T + \#\{t\in \mathbb{Z}\colon N_{0}\leqslant b+ pt\leqslant N_{0}+r\} \\ &= T + \biggl[\frac{N_{0}+r - b}{p}\biggr] - \biggl\lceil\frac{N_{0}-b}{p}\biggr\rceil + 1\leqslant \frac{r}{p}+ T+1. \end{aligned}
\end{equation*}
\notag
$$
Next, and (see (3.30))
$$
\begin{equation*}
N_{A}(x) \geqslant \frac{1}{2} \biggl(\frac{x}{M_{2}}\biggr)^{1/k} \geqslant \ln x
\end{equation*}
\notag
$$
if $x_0$ is large enough. Since $p\leqslant \ln x$, we obtain $p \leqslant N_{A}(x)$. Therefore,
$$
\begin{equation*}
\# \Lambda (b)\leqslant \frac{N_{A}(x)}{p}+ T+1\leqslant \frac{N_{A}(x)}{p}+ (T+1)\frac{N_{A}(x)}{p} = (T+2)\frac{N_{A}(x)}{p}= c_2 \frac{N_{A}(x)}{p},
\end{equation*}
\notag
$$
where $c_2$ is a positive constant depending only on $R$.
We have
$$
\begin{equation*}
\lambda (j,p) \leqslant \sum_{b\in U} \# \Lambda (b)\leqslant c_2 \frac{N_{A}(x)}{p} \#U\leqslant c_2 k \frac{N_{A}(x)}{p} = c_3 \frac{N_{A}(x)}{p},
\end{equation*}
\notag
$$
where $c_3$ is a positive constant depending only on $R$, and hence
$$
\begin{equation}
S_2=\sum_{\substack{p\leqslant \ln x\\ (p,a_k)=1}} \frac{\lambda (j, p)\ln p}{p}\leqslant c_3 N_{A}(x) \sum_{\substack{p\leqslant \ln x\\ (p,a_k)=1}} \frac{\ln p}{p^{2}} \leqslant c_3 N_{A}(x) \sum_{p} \frac{\ln p}{p^{2}} = c_4 N_{A}(x),
\end{equation}
\tag{3.35}
$$
where $c_{4}$ is a positive constant depending only on $R$.
Substituting (3.33) and (3.35) into (3.32), we obtain
$$
\begin{equation*}
\sum_{p\leqslant \ln x} \frac{\lambda (j, p)\ln p}{p}\leqslant (c_1 + c_4) N_{A}(x) = \gamma_{2} N_{A}(x),
\end{equation*}
\notag
$$
where $\gamma_{2}$ is a positive constant depending only on $R$. We have
$$
\begin{equation*}
\sum_{\substack{j\in \Omega:\\ R(j)< x}} \sum_{p\leqslant \ln x} \frac{\lambda (j, p)\ln p}{p}\leqslant \gamma_{2} N_{A}(x) \sum_{\substack{j\in \Omega:\\ R(j)< x}} 1 \leqslant \gamma_{2} \bigl(N_{A}(x)\bigr)^{2}.
\end{equation*}
\notag
$$
As a result, (1.6) holds with $\alpha = 1$.
By Theorem 1.6, there are positive constants $c_{1}=c_{1}(\gamma_1)$ and $c_{2}=c_{2}(\gamma_1, \gamma_2, \alpha)$ such that
$$
\begin{equation*}
\#\biggl\{1\leqslant n \leqslant x\colon \widetilde{r}(n)\geqslant c_{1}\frac{N_{A}(x)}{\ln x}\biggr\}\geqslant c_{2}x\frac{N_{A}(x)}{N_{A}(x)+\rho_{A}(x)\ln x},
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
\widetilde{r}(n) = \#\{(p,j)\in \mathbb{P}\times \Omega\colon p+ R(j)=n\}.
\end{equation*}
\notag
$$
Since $\gamma_{1}$ and $\gamma_2$ are positive constants depending only on $R$, $\alpha\,{=}\,1$, the positive constants $c_1$ and $c_2$ depend only on $R$. Applying (3.30), we obtain
$$
\begin{equation*}
\#\biggl\{1\leqslant n \leqslant x\colon \widetilde{r}(n)\geqslant c_{1}\frac{N_{A}(x)}{\ln x}\biggr\}\leqslant \#\biggl\{1\leqslant n \leqslant x\colon \widetilde{r}(n)\geqslant \frac{c_{1}}{2 (M_{2})^{1/k}} \frac{x^{1/k}}{\ln x}\biggr\}.
\end{equation*}
\notag
$$
We put
$$
\begin{equation*}
r(n) = \#\{(p,j)\in \mathbb{P}\times\mathbb{N}\colon p+ R(j)=n\}.
\end{equation*}
\notag
$$
It is clear that $\widetilde{r}(n) \leqslant r(n)$ for any positive integer $n$. Hence
$$
\begin{equation*}
\#\biggl\{1\leqslant n \leqslant x\colon \widetilde{r}(n)\geqslant \frac{c_{1}}{2 (M_{2})^{1/k}}\frac{x^{1/k}}{\ln x}\biggr\}\leqslant \#\biggl\{1\leqslant n \leqslant x\colon r(n)\geqslant \frac{c_{1}}{2 (M_{2})^{1/k}}\,\frac{x^{1/k}}{\ln x}\biggr\}.
\end{equation*}
\notag
$$
We have (see (3.31))
$$
\begin{equation*}
0< \rho_{A}(x)\ln x\leqslant k \ln x \leqslant \frac{x^{1/k}}{2 (M_{2})^{1/k}}
\end{equation*}
\notag
$$
if $x_0$ is large enough. We have $0< \rho_{A}(x)\ln x\leqslant N_{A}(x)$, and so
$$
\begin{equation*}
\frac{N_{A}(x)}{N_{A}(x)+\rho_{A}(x)\ln x}\geqslant \frac{N_{A}(x)}{N_{A}(x)+ N_{A}(x)}=\frac{1}{2}.
\end{equation*}
\notag
$$
Next,
$$
\begin{equation*}
\#\biggl\{1\leqslant n \leqslant x\colon r(n)\geqslant \frac{c_{1}}{2 (M_{2})^{1/k}}\, \frac{x^{1/k}}{\ln x}\biggr\}\geqslant \frac{c_{2}}{2} x.
\end{equation*}
\notag
$$
We see that $c_1 / (2 (M_{2})^{1/k})$ and $c_2/2$ are positive constants depending only on $R$. Now it suffices to denote $c_1 / (2 (M_{2})^{1/k})$ by $c_1$ and write $c_2$ for $c_2/2$. Theorem 1.7 is proved. Proof of Corollary 1.2. We put $R(n)=n^{k}$. By Theorem 1.7, there are positive constants $c_{1}(k)$, $c_{2}(k)$ and $x_{0}(k)$ depending only on $k$ such that
$$
\begin{equation*}
\#\biggl\{1\leqslant n \leqslant x\colon r(n)\geqslant c_{1}(k)\frac{x^{1/k}}{\ln x}\biggr\}\geqslant c_{2}(k) x
\end{equation*}
\notag
$$
for any real number $x \geqslant x_{0}(k)$, where
$$
\begin{equation*}
r(n)=\#\{(p, j)\in \mathbb{P}\times\mathbb{N}\colon p+j^{k}=n\}.
\end{equation*}
\notag
$$
We put
$$
\begin{equation*}
\max_{4 \leqslant x \leqslant x_{0}(k)}\frac{x^{1/k}}{\ln x}=\alpha (k).
\end{equation*}
\notag
$$
It is clear that $\alpha(k)$ is a positive constant depending only on $k$. Since $3=2+1=2+R(1)$ and $2\in \mathbb{P}$, we have $r(3) \geqslant 1$. Hence
$$
\begin{equation*}
\#\biggl\{1\leqslant n \leqslant x\colon r(n)\geqslant \frac{1}{\alpha (k)} \frac{x^{1/k}}{\ln x}\biggr\}\geqslant 1 \geqslant \frac{1}{x_{0}(k)} x
\end{equation*}
\notag
$$
for any real number $3 \leqslant x \leqslant x_{0}(k)$. Setting
$$
\begin{equation*}
b_{1}(k) = \min \biggl(c_{1}(k), \frac{1}{\alpha(k)}\biggr),\qquad b_{2}(k)=\min \biggl(c_{2}(k), \frac{1}{x_{0}(k)}\biggr),
\end{equation*}
\notag
$$
we see that $b_{1}(k)$ and $b_{2}(k)$ are positive constants depending only on $k$. Hence
$$
\begin{equation*}
\#\biggl\{1\leqslant n \leqslant x\colon r(n)\geqslant b_{1}(k)\frac{x^{1/k}}{\ln x}\biggr\}\geqslant b_{2}(k) x
\end{equation*}
\notag
$$
for any real number $x\geqslant 3$. It now suffices to denote $b_{1}(k)$ by $c_{1}(k)$ and write $c_{2}(k)$ for $b_{2}(k)$. Corollary 1.2 is proved. Proof of Theorem 1.8. By Hasse’s theorem [8], we have $|\#E(\mathbb{F}_{p})- (p+1)|< 2\sqrt{p}$ for any prime $p> 3$. From (3.18) we also have that $|\#E(\mathbb{F}_{p}) - (p+1)|<2\sqrt{p}$ for $p\in \{2, 3\}$. Hence for any prime $p$. Thus, for any prime $p$.
We set $A=\bigl\{ \#E(\mathbb{F}_{p})\colon p \geqslant 2\bigr\}$. We are going to apply Theorem 1.6. Suppose that $p\geqslant 5$. Let $q$ be a prime such that $q> p + 4\sqrt{p}+ 4$. Then $(\sqrt{q}-1)^{2}> (\sqrt{p}+1)^{2}$, and so from (3.36) we have $\#E(\mathbb{F}_{q})> \#E(\mathbb{F}_{p})$. Let $q$ be a prime such that $q< p - 4\sqrt{p}+ 4$. Then $(\sqrt{q}+1)^{2}< (\sqrt{p}-1)^{2}$, and now by (3.36) we have $\#E(\mathbb{F}_{q})< \#E(\mathbb{F}_{p})$. Hence
$$
\begin{equation*}
\begin{aligned} \, \operatorname{ord}_{A}\bigl(\#E(\mathbb{F}_{p})\bigr)&= \#\{q\colon \#E(\mathbb{F}_{q})=\#E(\mathbb{F}_{p})\} \\ &\leqslant \#\{q\colon p - 4\sqrt{p}+ 4 \leqslant q \leqslant p + 4\sqrt{p}+ 4\} \\ &\leqslant \#\{n\in \mathbb{N}\colon p - 4\sqrt{p}+ 4 \leqslant n \leqslant p + 4\sqrt{p}+ 4\} \\ &= [p + 4\sqrt{p}+ 4] - \lceil p - 4\sqrt{p}+ 4\rceil + 1\leqslant 8\sqrt{p}+1 < 9\sqrt{p}. \end{aligned}
\end{equation*}
\notag
$$
Suppose that $p<5$, that is, $p\in \{2,3\}$. From (3.18) we obtain $\#E(\mathbb{F}_{p})\leqslant 7$. Let $q > 14$ be a prime. Then $(\sqrt{q}-1)^{2}>7$, and from (3.36) we obtain $\#E(\mathbb{F}_{q})> \#E(\mathbb{F}_{p})$. Hence
$$
\begin{equation*}
\operatorname{ord}_{A}\bigl(\#E(\mathbb{F}_{p})\bigr)\leqslant \#\{q\colon q\leqslant 14\} = 6 < 6\sqrt{p}.
\end{equation*}
\notag
$$
We obtain
$$
\begin{equation}
\operatorname{ord}_{A}\bigl(\#E(\mathbb{F}_{p})\bigr) \leqslant 9\sqrt{p}
\end{equation}
\tag{3.37}
$$
for any prime $p$. In particular, $\operatorname{ord}_{A} (n) <+\infty$ for any positive integer $n$. We assume that $x\geqslant x_0$, where $x_0$ is a positive absolute constant; the (sufficiently large) constant $x_0$ will be chosen later. We may assume that $x_{0} \geqslant 100$. Hence $x\geqslant 100$. Let $p$ be a prime such that $\#E(\mathbb{F}_{p})\leqslant x$. It follows from (3.36) that $(\sqrt{p}-1)^{2}< x$ or, equivalently, $\sqrt{p}-1< \sqrt{x}$. Hence We put $n_0 = \#E(\mathbb{F}_2)$. From (3.18) we have $1\leqslant n_0 \leqslant 5< x$. Hence
$$
\begin{equation*}
\rho_{A}(x)=\max_{n\leqslant x}\operatorname{ord}_{A}(n) \geqslant \operatorname{ord}_{A}(n_0) \geqslant 1.
\end{equation*}
\notag
$$
Let $n_1$ be a positive integer such that $n_1 \leqslant x$ and $\rho_{A}(x)= \operatorname{ord}_{A}(n_1)$. Since $\rho_{A}(x) \geqslant 1$, we obtain $\operatorname{ord}_{A}(n_1) \geqslant 1$, and hence, there is a prime $p$ such that $\#E(\mathbb{F}_{p})=n_1$. Since $n_1\leqslant x$, we have $\#E(\mathbb{F}_{p}) \leqslant x$. From (3.38) we obtain $p\leqslant 2x$. Applying (3.37), we have
$$
\begin{equation*}
\rho_{A}(x)= \operatorname{ord}_{A}(n_1)= \operatorname{ord}_{A} \bigl(\#E(\mathbb{F}_{p})\bigr)\leqslant 9\sqrt{p} \leqslant 9\sqrt{2x}< 13 \sqrt{x}.
\end{equation*}
\notag
$$
Thus, An application of (3.38) shows that
$$
\begin{equation*}
\begin{aligned} \, N_{A}(x)&=\#\{p\colon \#E(\mathbb{F}_{p})\leqslant x\}\leqslant \#\{p\colon p\leqslant 2x\}= \pi (2x) \\ &\leqslant a\frac{2x}{\ln (2x)}\leqslant 2a \frac{x}{\ln x}= a_{2} \frac{x}{\ln x}, \end{aligned}
\end{equation*}
\notag
$$
where $a_2$ is a positive absolute constant.
Let $t\geqslant 20$ be a real number. It is easy to see that Hence if $p$ is a prime such that $p\leqslant t/2$, then $p\leqslant t-2\sqrt{t}+1$ or, equivalently, $(\sqrt{p}+1)^{2}\leqslant t$. From (3.36) we have $\#E(\mathbb{F}_{p})\leqslant t$. Therefore,
$$
\begin{equation}
\begin{aligned} \, N_{A}(t)&=\#\{p\colon \#E(\mathbb{F}_{p})\leqslant t\} \notag \\ &\geqslant \#\biggl\{p\colon p \leqslant \frac{t}2\biggr\}= \pi \biggl(\frac{t}2\biggr) \geqslant b \frac{t/2}{\ln (t/2)}\geqslant \frac{b}{2}\, \frac{t}{\ln t}= a_{1} \frac{t}{\ln t}, \end{aligned}
\end{equation}
\tag{3.40}
$$
where $a_1$ is a positive absolute constant. As a result,
$$
\begin{equation}
a_{1} \frac{x}{\ln x} \leqslant N_{A}(x) \leqslant a_{2} \frac{x}{\ln x},
\end{equation}
\tag{3.41}
$$
where $a_1$, $a_2$ are positive absolute constants. Since $x/2 >20$, from (3.40) we have
$$
\begin{equation*}
N_{A}\biggl(\frac{x}2\biggr) \geqslant a_{1} \frac{x/2}{\ln (x/2)}\geqslant \frac{a_1}{2}\, \frac{x}{\ln x}= \frac{a_1}{2a_2}\, a_{2} \frac{x}{\ln x}\geqslant \frac{a_1}{2a_2}\, N_{A}(x)=\gamma_1 N_{A}(x),
\end{equation*}
\notag
$$
where $\gamma_1 = a_{1}/ (2a_{2})$ is a positive absolute constant. This proves (1.4) and (1.5).
We have
$$
\begin{equation*}
10 \leqslant (\ln x)^{1/14} \leqslant (c_{1}\ln x)^{1/13}
\end{equation*}
\notag
$$
if $x_0$ is large enough (here, $c_1$ is a positive absolute constant from (3.19)). Consider the sum
$$
\begin{equation*}
S=\sum_{\substack{q\in \mathbb{P}:\\ \#E(\mathbb{F}_{q})< x}}\, \sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\lambda (q,t) \ln t}{t},
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
\lambda (q, t):= \#\{p\in \mathbb{P}\colon \#E(\mathbb{F}_{q})< \#E(\mathbb{F}_{p})\leqslant x \text{ and }\#E(\mathbb{F}_{p})\equiv \#E(\mathbb{F}_{q})\ (\operatorname{mod} t)\}.
\end{equation*}
\notag
$$
Let $q$ and $t$ be in the range of summation of $S$. From (3.38) and (3.19) we obtain
$$
\begin{equation*}
\begin{aligned} \, \lambda (q, t) &\leqslant \#\{p\leqslant 2x\colon \#E(\mathbb{F}_{p}) \equiv \#E(\mathbb{F}_{q}) \ (\operatorname{mod} t)\} \\ &\leqslant C(E) \biggl(\frac{\pi(2x)} {\varphi (t)}+ 2x\exp(-b t^{-2} \sqrt{\ln (2x)}\,)\biggr). \end{aligned}
\end{equation*}
\notag
$$
Hence
$$
\begin{equation}
\begin{aligned} \, &\sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\lambda (q,t) \ln t}{t} \nonumber \\ &\qquad\leqslant C(E) \Biggl(\pi(2x)\sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\ln t}{t\varphi (t)}+ 2x \sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\ln t}{t\exp(b t^{-2} \sqrt{\ln (2x)}\,)}\Biggr). \end{aligned}
\end{equation}
\tag{3.42}
$$
Since $\varphi (n) \geqslant c n/ \ln\ln(n+2)$ for any positive integer $n$, where $c$ is a positive absolute constant, we obtain
$$
\begin{equation*}
\sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\ln t}{t\varphi (t)} \leqslant \frac{1}{c} \sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\ln t \ln\ln (t+2)}{t^{2}}\leqslant \frac{1}{c} \sum_{n=1}^{\infty}\frac{\ln n \ln\ln (n+2)}{n^{2}}=c_1,
\end{equation*}
\notag
$$
where $c_1$ is a positive absolute constant. We have
$$
\begin{equation}
\pi(2x)\sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\ln t}{t\varphi (t)}\leqslant c_1 \pi(2x)\leqslant c_1 a\frac{2x}{\ln (2x)}\leqslant 2c_1 a\frac{x}{\ln x} = c_2 \frac{x}{\ln x},
\end{equation}
\tag{3.43}
$$
where $c_2$ is a positive absolute constant.
For any prime $t \leqslant (\ln x)^{1/14}$, we have
$$
\begin{equation*}
\frac{b \sqrt{\ln (2x)}}{t^{2}}\geqslant \frac{b \sqrt{\ln (2x)}}{(\ln x)^{1/7}}\geqslant \frac{b (\ln x)^{1/2}}{(\ln x)^{1/7}}= b (\ln x)^{5/14}.
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
2x \sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\ln t}{t\exp(b t^{-2} \sqrt{\ln (2x)}\,)} \leqslant 2x\exp\bigl(-b (\ln x)^{5/14}\bigr) \sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\ln t}{t}.
\end{equation*}
\notag
$$
Putting $k= [(\ln x)^{1/14}]$ and applying Lemma 3.5, we have
$$
\begin{equation*}
\sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\ln t}{t}= \sum_{p\leqslant k} \frac{\ln p}{p}\leqslant c \ln k \leqslant c \ln \bigl((\ln x)^{1/14}\bigr)= \frac{c}{14}\ln\ln x=c_3\ln\ln x,
\end{equation*}
\notag
$$
where $c_3 = c/14$ is a positive absolute constant.
We obtain
$$
\begin{equation*}
2x \sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\ln t}{t\exp(b t^{-2} \sqrt{\ln (2x)}\,)}\leqslant 2c_{3}x\,\exp\bigl(-b (\ln x)^{5/14}\bigr)\ln\ln x.
\end{equation*}
\notag
$$
Let us show that
$$
\begin{equation}
2c_{3}x\exp\bigl(-b (\ln x)^{5/14}\bigr)\ln\ln x \leqslant \frac{x}{\ln x}
\end{equation}
\tag{3.44}
$$
or, equivalently,
$$
\begin{equation*}
2c_{3}\ln x \ln\ln x \leqslant \exp\bigl(b (\ln x)^{5/14}\bigr).
\end{equation*}
\notag
$$
Taking logarithms, we obtain
$$
\begin{equation*}
\ln(2c_3)+\ln\ln x + \ln\ln\ln x \leqslant b (\ln x)^{5/14}.
\end{equation*}
\notag
$$
This inequality holds for sufficiently large $x_0$. Inequality (3.44) is proved.
We have
$$
\begin{equation}
2x \sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\ln t}{t\exp(b t^{-2} \sqrt{\ln (2x)}\,)} \leqslant \frac{x}{\ln x}.
\end{equation}
\tag{3.45}
$$
Substituting (3.43) and (3.45) into (3.42), we obtain
$$
\begin{equation*}
\sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\lambda (q,t) \ln t}{t}\leqslant C(E)(c_2 +1)\frac{x}{\ln x} = C_{1}(E) \frac{x}{\ln x},
\end{equation*}
\notag
$$
where $C_{1}(E) >0$ is a constant depending only on $E$.
Applying (3.41), we obtain
$$
\begin{equation*}
\begin{aligned} \, \sum_{\substack{q\in \mathbb{P}:\\ \#E(\mathbb{F}_{q})< x}}\, \sum_{\substack{t\in \mathbb{P}:\\ t\leqslant (\ln x)^{1/14}}} \frac{\lambda (q,t) \ln t}{t} &\leqslant C_{1}(E)\, \frac{x}{\ln x} \, N_{A}(x) \\ &\leqslant\frac{C_{1}(E)}{a_1} (N_{A}(x))^{2}= \gamma_{2}(E) (N_{A}(x))^{2}, \end{aligned}
\end{equation*}
\notag
$$
where $\gamma_{2}(E) >0$ is a constant depending only on $E$. This proves inequality (1.6) with $\alpha=1/14$.
By Theorem 1.6, there are positive constants $c_{1}=c_{1}(\gamma_1)$, $c_{2}=c_{2} (\gamma_{1}, \gamma_{2}(E), \alpha)$ such that
$$
\begin{equation*}
\#\biggl\{1\leqslant n \leqslant x\colon r(n)\geqslant c_{1}\frac{N_{A}(x)}{\ln x}\biggr\} \geqslant c_{2}x\frac{N_{A}(x)}{N_{A}(x)+\rho_{A}(x)\ln x},
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
r(n)=\#\{(p, q)\in \mathbb{P}^{2}\colon p+\#E(\mathbb{F}_q)=n\}.
\end{equation*}
\notag
$$
Since $\alpha = 1/14$, $\gamma_1$ is a positive absolute constant, and $\gamma_2(E)$ is a positive constant depending only on $E$, we see that $c_1$ is a positive absolute constant, and $c_{2}$ is a positive constant depending only on $E$.
By (3.41),
$$
\begin{equation*}
\#\biggl\{1\leqslant n \leqslant x\colon r(n)\geqslant c_{1}\frac{N_{A}(x)}{\ln x}\biggr\} \leqslant \#\biggl\{1\leqslant n \leqslant x\colon r(n)\geqslant c_{1} a_{1} \frac{x}{(\ln x)^{2}}\biggr\}.
\end{equation*}
\notag
$$
An appeal to (3.39) shows that
$$
\begin{equation*}
\rho_{A}(x)\ln x \leqslant 13 \sqrt{x}\ln x\leqslant a_{1}\frac{x}{\ln x}
\end{equation*}
\notag
$$
if $x_0$ is sufficiently large (here, $a_1$ is a positive absolute constant from (3.41)). Hence and, therefore,
$$
\begin{equation*}
\frac{N_{A}(x)}{N_{A}(x)+\rho_{A}(x)\ln x}\geqslant \frac{N_{A}(x)}{N_{A}(x)+ N_{A}(x)}= \frac{1}{2}.
\end{equation*}
\notag
$$
We obtain
$$
\begin{equation*}
\#\biggl\{1\leqslant n \leqslant x\colon r(n)\geqslant c_{1} a_{1} \frac{x}{(\ln x)^{2}}\biggr\}\geqslant \frac{c_{2}(E)}{2}x.
\end{equation*}
\notag
$$
Consequently, $c_{1} a_{1}$ is a positive absolute constant, and $c_{2}(E)/2$ is a positive constant depending only on $E$. It suffices to denote $c_{1} a_{1}$ by $c_1$, and write $c_{2}(E)$ for $c_{2}(E)/2$. Theorem 1.8 is proved. Proof of Theorem 1.9. We put We assume that $x\geqslant x_{0}(a, b)$, where $x_{0}(a, b) >0$ is a constant depending only on $a$ and $b$; the (sufficiently large) constant $x_{0}(a, b)$ will chosen later. We are going to apply Theorem 1.6. It is clear that
$$
\begin{equation*}
\begin{gathered} \, \operatorname{ord}_{A}(n)=\#\bigl\{j\geqslant 0\colon a^{j^{b}}= n\bigr\}\leqslant 1,\qquad n\in\mathbb{N}, \\ N_{A}(x)=\#\bigl\{j\geqslant 0\colon a^{j^{b}}\leqslant x\bigr\} =y+1, \quad \text{where}\quad y:=\biggl[\biggl(\frac{\ln x}{\ln a}\biggr)^{1/b}\biggr]. \end{gathered}
\end{equation*}
\notag
$$
Since $\operatorname{ord}_{A}(1)=1$, we see that
$$
\begin{equation*}
\rho_{A}(x)= \max_{n\leqslant x} \operatorname{ord}_{A}(n) =1.
\end{equation*}
\notag
$$
We have
$$
\begin{equation}
y\geqslant 10,\qquad \biggl(\frac{\ln x}{\ln a}\biggr)^{1/b}\leqslant N_{A}(x)\leqslant 2 \biggl(\frac{\ln x}{\ln a}\biggr)^{1/b},\qquad N_{A}\left(x\over 2\right)\geqslant \frac{1}{\sqrt{8}}\, N_{A}(x)
\end{equation}
\tag{3.46}
$$
if $x_{0}(a, b)$ is sufficiently large. Now (1.4) and (1.5) follow from (3.46).
Let us show that
$$
\begin{equation}
\sum_{0\leqslant k\leqslant y}\, \sum_{p\leqslant (\ln x)^{1/(2b)}} \frac{\lambda(k,p) \ln p}{p}\leqslant \gamma_{2}(a, b) y^{2},
\end{equation}
\tag{3.47}
$$
where
$$
\begin{equation*}
\lambda(k,p) = \#\Lambda (k, p),\qquad \Lambda(k,p):=\bigl\{k<j\leqslant y\colon a^{j^{b}}\equiv a^{k^{b}}\, (\operatorname{mod} p)\bigr\},
\end{equation*}
\notag
$$
and $\gamma_{2}(a, b)$ is a positive constant depending only on $a$ and $b$.
We fix an integer $k$ with $0\leqslant k \leqslant y$. We have
$$
\begin{equation*}
\sum_{p\leqslant (\ln x)^{1/(2b)}} \frac{\lambda(k,p)\ln p}{p}= \sum_{\substack{p\leqslant (\ln x)^{1/(2b)}:\\ p\mid a\text{ or }p\mid (a-1)}} + \sum_{\substack{p\leqslant (\ln x)^{1/(2b)}:\\ (p,a)=1\text{ and }(p,a-1)=1}} =S_1+ S_2.
\end{equation*}
\notag
$$
Since $\lambda (k, p)\leqslant y$, we obtain
$$
\begin{equation*}
S_1\leqslant y \sum_{\substack{p\leqslant (\ln x)^{1/(2b)}:\\ p\mid a\text{ or }p\mid (a-1)}}\frac{\ln p}{p}\leqslant y \sum_{\substack{p:\\ p\mid a\text{ or }p\mid (a-1)}}\frac{\ln p}{p}= c_{1}(a)y,
\end{equation*}
\notag
$$
where $c_{1}(a)>0$ is a constant depending only on $a$.
Let $p$ be in the range of summation of $S_2$. Since $(a,p)= 1$, we have $a^{p-1}\equiv 1$ $ (\operatorname{mod} p)$ (Fermat’s theorem). Let $h_{a}(p)$ be the order of $a$ modulo $p$, that is, $h_{a}(p)$ is the least positive integer $h$ such that $a^{h}\equiv 1\ (\operatorname{mod} p)$. Since $(p,a-1)=1$, we have $1<h_{a}(p)\leqslant p-1$. Let $j\in \Lambda (k, p)$. Hence
$$
\begin{equation*}
a^{j^{b}}\equiv a^{k^{b}}\quad (\operatorname{mod} p).
\end{equation*}
\notag
$$
Since we obtain Hence (see, for example, Ch. VI in [2]), $j^{b}-k^{b}\equiv 0\ (\operatorname{mod} h_{a}(p))$.
We now need the following result of Konyagin (see Theorem 2 in [9]). Let $m, n\in \mathbb{N}$ and let where $a_{0}, \dots, a_{n}$ are integers satisfying $(a_{0},\dots, a_{n}, m)=1$. Next, let $\rho (f, m)$ be the number of solutions of the congruence $f(x)\equiv 0\ (\operatorname{mod} m)$. Then where $c$ is a positive absolute constant.We define
$$
\begin{equation*}
U=\bigl\{j\in \{0,\dots, h_{a}(p)-1\}\colon j^{b}-k^{b}\equiv 0 \ (\operatorname{mod} h_{a}(p))\bigr\}.
\end{equation*}
\notag
$$
From (3.48) we obtain It is easy to see that
$$
\begin{equation*}
\lambda (k, p) \leqslant \sum_{j_{0}\in U} \#\{t\in \mathbb{Z}\colon 1\leqslant j_{0}+h_{a}(p)t\leqslant y\}.
\end{equation*}
\notag
$$
We have
$$
\begin{equation*}
(\ln x)^{1/ (2b)} \leqslant \biggl(\frac{\ln x}{\ln a}\biggr)^{1/b}-1
\end{equation*}
\notag
$$
if $x_{0}(a,b)$ is sufficiently large. Hence
$$
\begin{equation*}
h_{a}(p) \leqslant p-1 < p\leqslant (\ln x)^{1/ (2b)} \leqslant \biggl(\frac{\ln x}{\ln a}\biggr)^{1/b}-1\leqslant y.
\end{equation*}
\notag
$$
Given $j_{0}\in U$, we have
$$
\begin{equation*}
\#\{t\in \mathbb{Z}\colon 1\leqslant j_{0}+h_{a}(p)t\leqslant y\}\leqslant \frac{y}{h_{a}(p)}+1\leqslant \frac{2y}{h_{a}(p)}.
\end{equation*}
\notag
$$
Hence
$$
\begin{equation*}
\lambda (k, p)\leqslant \frac{2y}{h_{a}(p)} \#U \leqslant \frac{2y}{h_{a}(p)} cb \bigl(h_{a}(p)\bigr)^{1-1/b}= c_{2}(b) \frac{y}{\bigl(h_{a}(p)\bigr)^{1/b}},
\end{equation*}
\notag
$$
where $c_{2}(b)=2cb$ is a positive constant depending only on $b$.
As a result,
$$
\begin{equation}
\begin{aligned} \, S_2 &= \sum_{\substack{p\leqslant (\ln x)^{1/(2b)}:\\ (p,a)=1\text{ and }(p,a-1)=1}}\frac{\lambda(k,p)\ln p}{p}\leqslant c_{2}(b) y \sum_{\substack{p\leqslant (\ln x)^{1/(2b)}:\\ (p,a)=1\text{ and }(p,a-1)=1}} \frac{\ln p}{p(h_{a}(p))^{1/b}} \notag \\ &\leqslant c_{2}(b) y\sum_{\substack{p:\\ (p,a)=1}}\frac{\ln p}{p(h_{a}(p))^{1/b}}. \end{aligned}
\end{equation}
\tag{3.49}
$$
We put
$$
\begin{equation*}
D(z)=\sum_{n\leqslant z} d_n,\qquad \text{where}\quad d_n= \sum_{\substack{p:\\ (p,a)=1\\ h_{a}(p)=n}}\frac{\ln p}{p},\quad n=1, 2, \dots\,.
\end{equation*}
\notag
$$
Let $z\geqslant 100$. Then
$$
\begin{equation*}
D(z)=\sum_{n\leqslant z} d_n= \sum_{n\leqslant z} \sum_{\substack{p:\\ (p,a)=1\\ h_{a}(p)=n}}\frac{\ln p}{p}.
\end{equation*}
\notag
$$
Let $n$ and $p$ be in the range of summation. Then $h_{a}(p)=n$, and, hence, $a^{n}\equiv 1\ (\operatorname{mod} p)$, that is, $p\mid (a^{n}-1)$. Setting $P(z)=\prod_{n\leqslant z}(a^{n}-1)$, we obtain
$$
\begin{equation*}
D(z)\leqslant \sum_{p \,|\, P(z)}\frac{\ln p}{p} \leqslant c_{0}\ln\ln P(z),
\end{equation*}
\notag
$$
where $c_{0}>0$ is an absolute constant. Since
$$
\begin{equation*}
P(z)\leqslant \prod_{n\leqslant z} a^{n}= a^{1+2+\dots+[z]}\leqslant a^{z^{2}},
\end{equation*}
\notag
$$
we obtain $D(z)\leqslant c_1(a)\ln z$, where $c_1(a)>0$ is constant depending only on $a$. Hence $D(z)\leqslant c(a)\ln (z+1)$ for any real number $z\geqslant 1$, where $c(a)>0$ is a constant depending only on $a$. Hence $D(z)z^{-1/b}\to 0$ as $z\to +\infty$. By partial summation, we have
$$
\begin{equation*}
\sum_{n\leqslant z}\frac{d_n}{n^{1/b}}=\frac{D(z)}{z^{1/b}}+ \frac{1}{b}\int_{1}^{z}\frac{D(t)}{t^{1+1/b}}\,dt
\end{equation*}
\notag
$$
for any real $z\geqslant 1$. Hence
$$
\begin{equation*}
\sum_{n\geqslant 1}\frac{d_n}{n^{1/b}}= \frac{1}{b}\int_{1}^{+\infty}\frac{D(t)}{t^{1+1/b}}\,dt\leqslant \frac{c(a)}{b}\int_{1}^{+\infty}\frac{\ln (t+1)}{t^{1+1/b}}\,dt = c_{3}(a,b),
\end{equation*}
\notag
$$
where $c_3(a, b)>0$ is a constant depending only on $a$ and $b$.
We have
$$
\begin{equation*}
\begin{aligned} \, \sum_{n\geqslant 1}\frac{d_{n}}{n^{1/b}}&= \sum_{n\geqslant 1} \sum_{\substack{p:\\ (p,a)=1\\ h_{a}(p)=n}} \frac{\ln p}{p (h_{a}(p))^{1/b}}=\sum_{\substack{p:\\ (p,a)=1}} \frac{\ln p}{p (h_{a}(p))^{1/b}}\sum_{\substack{n\geqslant 1:\\ h_{a}(p)=n}}1 \\ &=\sum_{\substack{p:\\ (p,a)=1}} \frac{\ln p}{p (h_{a}(p))^{1/b}}. \end{aligned}
\end{equation*}
\notag
$$
Hence (see (3.49)), $S_{2}\leqslant c_4(a,b)y$, where $c_4(a,b)>0$ is a constant depending only on $a$ and $b$, and
$$
\begin{equation*}
\sum_{p\leqslant (\ln x)^{1/(2b)}} \frac{\lambda(k,p)\ln p}{p}= S_1+S_2 \leqslant \bigl(c_1(a)+ c_4 (a, b)\bigr)y= c_{5}(a, b)y.
\end{equation*}
\notag
$$
As a result,
$$
\begin{equation*}
\begin{aligned} \, \sum_{0\leqslant k\leqslant y}\sum_{p\leqslant (\ln x)^{1/(2b)}}\frac{\lambda(k,p)\ln p}{p} &\leqslant \sum_{0\leqslant k\leqslant y} c_{5}(a,b)y= c_{5}(a,b)y(y+1) \\ &\leqslant 2c_{5}(a, b)y^{2} = \gamma_{2}(a,b) y^{2}, \end{aligned}
\end{equation*}
\notag
$$
where $\gamma_{2}(a,b)>0$ is a constant depending only on $a$ and $b$. This proves inequality (3.47), and, therefore, (1.6) with $\alpha=1/(2b)$.
An application of Theorem 1.6 shows that
$$
\begin{equation*}
\begin{aligned} \, &\#\bigl\{1\leqslant n \leqslant x\colon \text{there are }p\in \mathbb{P} \text{ and }j\in \mathbb{Z}_{\geqslant 0} \text{ such that }p+ a^{j^{b}}=n\bigr\} \\ &\quad\geqslant c_{2}(a,b)x\,\frac{N_{A}(x)}{N_{A}(x)+\rho_{A}(x)\ln x}, \end{aligned}
\end{equation*}
\notag
$$
where $c_{2}(a,b)>0$ is a constant depending only on $a$ and $b$.
We have
$$
\begin{equation*}
\biggl(\frac{\ln x}{\ln a}\biggr)^{1/b}\leqslant \ln x
\end{equation*}
\notag
$$
if $x_{0}(a,b)$ is sufficiently large. Using (3.46) and taking into account that $\rho_{A}(x)=1$, we obtain
$$
\begin{equation*}
\begin{aligned} \, \frac{N_{A}(x)}{N_{A}(x)+\rho_{A}(x)\ln x}&\geqslant \frac{(\ln x/\ln a)^{1/b}}{2(\ln x/\ln a)^{1/b}+\ln x} \\ &\geqslant \frac{(\ln x/\ln a)^{1/b}}{2\ln x+\ln x}= \frac{1}{3 (\ln a)^{1/b}}\frac{1}{(\ln x)^{1-1/b}}. \end{aligned}
\end{equation*}
\notag
$$
Next,
$$
\begin{equation*}
\begin{aligned} \, &\#\bigl\{1\leqslant n \leqslant x\colon \text{there are }p\in \mathbb{P} \text{ and }j\in \mathbb{Z}_{\geqslant 0}\text{ such that }p+ a^{j^{b}}=n\bigr\} \\ &\qquad\geqslant \frac{c_{2}(a,b)}{3 (\ln a)^{1/b}} \frac{x}{(\ln x)^{1-1/b}} = c_{1}(a, b)\frac{x}{(\ln x)^{1-1/b}}, \end{aligned}
\end{equation*}
\notag
$$
where $c_{1}(a,b)>0$ is a constant depending only on $a$ and $b$.
We have
$$
\begin{equation*}
\begin{aligned} \, &\#\bigl\{1\leqslant n \leqslant x\colon \text{there are }p\in \mathbb{P}\text{ and } j\in \mathbb{Z}_{\geqslant 0}\text{ such that }p+ a^{j^{b}}=n\bigr\} \\ &\quad\leqslant \#\bigl\{(p,j)\in \mathbb{P}\times \mathbb{Z}_{\geqslant 0}\colon p\leqslant x\text{ and }a^{j^{b}}\leqslant x\bigr\} = \#\{p\colon p\leqslant x\}\, \#\bigl\{j\geqslant 0\colon a^{j^{b}}\leqslant x\bigr\} \\ &\quad=\pi(x) N_{A}(x) \leqslant c\,\frac{x}{\ln x}\,2 \biggl(\frac{\ln x}{\ln a}\biggr)^{1/b}= c_{2}(a, b)\, \frac{x}{(\ln x)^{1-1/b}}, \end{aligned}
\end{equation*}
\notag
$$
where $c_{2}(a, b)>0$ is a constant depending only on $a$ and $b$.
Since for $p=2$ and $j=0$, the claim in the case $3 \leqslant x < x_{0}(a,b)$ is trivial. Theorem 1.9 is proved.I would like to thank Sergei Konyagin for many useful conversations and suggestions. Also I would like to thank the anonymous referee for many useful comments. 
Citation in format AMSBIB
\Bibitem{Rad23} |
|
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|