Abstract Generated abstract
The paper studies a binary additive problem for representations of an integer N as N = n1 + n2, where all prime divisors of n1 are small and all prime divisors of n2 are large, relative to powers of N. It defines the counting function L(N, N1/alpha, N1/beta) and proves an asymptotic estimate for all real alpha at least 1 and beta tending to infinity with N. The main term is z(beta) omega(alpha) N / log N, with an error O(N beta / log2 N), where omega is characterized by a Buchstab type differential equation and z(beta) by an exponential factor involving the Euler constant. The proof uses Buchstab’s recurrence method together with a sieve lemma of Levin to handle the relevant sequences.
Full Text
UDC 511.29
MATHEMATICS
Yu. A. KURIKZHEV
ONE BINARY ADDITIVE PROBLEM
(Presented by Academician P. S. Novikov on 5 XI 1968)
Many authors have investigated the distribution of numbers with large and small prime divisors (see, for example, \((^{1-6})\)). Denote by \(Q(N; N^{1/\alpha})\) \(\bigl(q(N; N^{1/\beta})\bigr)\) the numerical function expressing the number of numbers \(\leq N\) all of whose prime divisors exceed \(N^{1/\alpha}\) (do not exceed \(N^{1/\beta}\)). In the papers \((^{1,2})\) the functions \(Q\) and \(q\) were studied for fixed, or increasing independently of \(N\), values of \(\alpha\) and \(\beta\). The study of \(Q\) and \(q\) for \(\alpha\) and \(\beta\) increasing together with \(N\) was the subject of the papers \((^{4,5})\); the best results were obtained in \((^{4})\).
For sets of numbers with large and small prime divisors one may pose binary additive problems consisting in finding asymptotic estimates, or lower and upper estimates, for the number of solutions of the equation
\[ N=n_1+n_2. \tag{1} \]
The case when \(n_1\) and \(n_2\) belong to the numbers with large prime divisors was considered by A. A. Buhshtab in \((^{7})\). If \(n_1\) and \(n_2\) are numbers with small prime divisors, then we obtain a problem connected with the bound for the least quadratic non-residue modulo a prime.
The present work is devoted to the investigation of the number of solutions of equation (1) in the case when \(n_1\) and \(n_2\) run respectively through the numbers with small and large prime divisors.
Let \(L(N; N^{1/\alpha}; N^{1/\beta})\) be the function determining the number of solutions of equation (1), where all prime divisors of \(n_1\) do not exceed \(N^{1/\alpha}\), and all prime divisors of \(n_2\) are greater than \(N^{1/\beta}\).
Theorem. For every real \(\alpha \geq 1\) and \(\beta=\beta(N)\to\infty\) as \(N\to\infty\), the estimate
\[ L(N; N^{1/\alpha}; N^{1/\beta}) = z(\beta)\,\omega(\alpha)\frac{N}{\log N} + O\!\left(\frac{N\beta}{\log^2 N}\right), \tag{2} \]
holds, where \(\omega(\alpha)\) satisfies the differential equation
\[ \alpha\omega'(\alpha)+\omega(\alpha-1)=0 \tag{3} \]
with initial condition
\[ \omega(\alpha)=1 \quad \text{for } 0\leq \alpha \leq 1, \tag{3′} \]
\[ z(\beta)=e^{-c\beta}[1+\Delta(\beta/2)], \tag{4} \]
where \(c\) is the Euler–Mascheroni constant and
\[ \Delta(u)=O\!\left(\exp\left(-\frac{u}{2}\log\frac{u}{2}\right)\right). \]
The proof of the theorem is carried out by the method of \((^{4})\) and essentially relies on Lemma 4 of \((^{3})\).
It is evident that the equality
\[ L(N; N^{1/\alpha}; N^{1/\beta}) = \sum_{\substack{ n\leq N\\ n/\pi_{N^{1/\alpha}}\\ (N-n,\pi_{N^{1/\beta}})=1 }} 1, \tag{5} \]
holds, where \(\pi_{N^{1/\beta}}\) is the product of all primes up to \(N^{1/\beta}\), and the symbol \(n/\pi_{N^{1/\alpha}}\) means that the greatest prime divisor of \(n\) does not exceed \(N^{1/\alpha}\).
It is easy to derive the recurrence formula \((\nu \leq \alpha)\)
\[ L(N;\ N^{1/\alpha};\ N^{1/\beta}) = L(N;\ N^{1/\nu};\ N^{1/\beta}) - \sum_{N^{1/\alpha}<p\leq N^{1/\nu}} \sum_{\substack{\tau\leq N/p\\ \tau/\pi_p\\ (N-p\tau,\ \tau N^{1/\beta})=1}} 1 . \tag{6} \]
For \(1\leq \alpha \leq 2\) in our problem \(n_1\) can have at most one prime divisor exceeding \(\sqrt N\). Taking \(\nu=1\) in (6), we obtain:
\[ L(N;\ N^{1/\alpha};\ N^{1/\beta}) = L(N;\ N;\ N^{1/\beta}) - \sum_{N^{1/\alpha}<p\leq N} \sum_{\substack{\tau\leq N/p\\ \tau/\pi_p\\ (N-p\tau,\ \tau N^{1/\beta})=1}} 1 . \tag{7} \]
The condition \(\tau/\pi_p\) for \(1\leq \alpha \leq 2\) in equality (6) disappears, and \(\tau\) runs through all natural numbers not exceeding \(N/p\). Consequently, we arrive at the necessity of estimating the number of terms of the sequence \(\{N-p\tau\}\), where \(N^{1/\alpha}<p\leq N\) and \(\tau\leq N/p\), not divisible by primes not exceeding \(N^{1/\beta}\). It is not difficult to see that, for this sequence, conditions 1) and 2) of Lemma 4 from paper \((^3)\) are fulfilled, with the first condition fulfilled for \(\gamma=1/2-\varepsilon\). Therefore we have
\[ \sum_{N^{1/\alpha}<p\leq N} \sum_{\substack{\tau\leq N/p\\ (N-p\tau,\ \tau N^{1/\beta})=1}} 1 = \frac{N}{\log N}\,z(\beta)c_1\log\alpha + O\!\left(\frac{N\beta}{\log^2 N}\right), \tag{8} \]
where \(z(\beta)\) has the form (4) and
\[ c_1=\prod_p\left(1-\frac{1}{(p-1)^2}\right). \]
Here, using the fact that \(\Delta(u)\) is a decreasing function, we have replaced
\[ \Delta\!\left(\frac{\beta}{2(1/2-\varepsilon)}\right) \quad\text{by}\quad \Delta\!\left(\frac{\beta}{2}\right). \]
Applying the same lemma to the sequence \(\{N-n\}\), where \(n\) runs through the natural numbers \((\leq N)\), we obtain
\[ L(N;\ N;\ N^{1/\beta}) = \frac{N}{\log N}\,z(\beta) + O\!\left(\frac{N\beta}{\log^2 N}\right). \tag{9} \]
(Condition 2) of Lemma 4 is fulfilled for \(\gamma=1-\varepsilon\).)
Estimates (8) and (9), together with formula (7), give for \(1\leq \alpha \leq 2\):
\[ L(N;\ N^{1/\alpha};\ N^{1/\beta}) = \frac{N}{\log N}\,z(\beta)\omega(\alpha) + O\!\left(\frac{N\beta}{\log^2 N}\right), \tag{10} \]
where
\[ \omega(\alpha)=1-c_1\int_1^\alpha \frac{du}{u}. \tag{11} \]
The validity of estimate (2) for all \(\alpha\geq 1\) is obtained by the method of A. A. Buchstab, set forth in paper \((^1)\).
The differential equation (3) and its initial condition \((3')\) can be obtained from the equality
\[ \omega(\alpha)=\omega(n)-\int_n^\alpha \frac{\omega(u-1)}{u}\,du, \]
which is satisfied by \(\omega(\alpha)\) in the interval \(n\leq \alpha \leq n+1\), and by (11).
In conclusion, the author expresses gratitude to Prof. A. A. Buchstab for posing the problem.
Moscow State Pedagogical Institute
named after V. I. Lenin
Received
4 XI 1968
REFERENCES
- A. A. Buchstab, Matem. sborn., 2(44), 6 (1937).
- A. A. Buchstab, DAN, 67, No. 1 (1949).
- B. V. Levin, UMN, 20, issue 5(125) (1965).
- B. V. Levin, A. S. Fainleib, UMN, 22, issue 3(135) (1967).
- A. I. Vinogradov, DAN, 109, No. 4 (1956).
- N. G. de Bruijn, Nederl. Akad. Wetensch., Proc., 54, No. 1, ser. A (1951).
- A. A. Buchstab, Uch. zap. Mosk. gos. ped. inst. im. V. I. Lenina, 21 (1953).