Proceedings of the Steklov Institute of Mathematics, Vol. 218, 1997, pp. 402–413. Translated from Trudy Matematicheskogo Instituta imeni V. A. Steklova, Vol. 218, 1997, pp. 403–414. Original Russian Text Copyright \begin{matrix}c \\ ◯ \end{matrix} 1997 by Timofeev. English Translation Copyright \begin{matrix}c \\ ◯ \end{matrix} by ���� �����/Interperiodica Publishing (Russia).

Distribution in the Mean in Progressions of Numbers with a Large Number of Prime Factors

N. M. Timofeev

Received February, 1997

We denote by Ω(n) the number of prime factors n with due account of their multiplicity, Ω(1) = 0. Let f_{k}(n) be a characteristic function of the set n for which Ω(n) = k, i.e., f_{k}(n) = 1 if Ω(n) = k and f_{k}(n) = 0 otherwise. We set

�(x, k) = ∑_{n≤x} f_{k}(n).

Before beginning the investigation of the distribution of numbers with a specified value of Ω(n) in progressions, we give the information concerning �(x, k) which is necessary for the sequel. If k is a fixed number, then the asymptotics of �(x, k) was found by Landau [1]. Sathe [2] and Selberg [3] proved that if 1 ≤ k ≤ (2 − ε) ln_{2} x, 0 ≤ ε ≤ 1, x ≥ 3, then

�(x, k) = \frac{x}{ln x} F (\frac{k}{ln_{2} x})\frac{(ln_{2} x)^{k−1}}{(k − 1)!} (1 + O_{ε}(\frac{1}{ln_{2} x})),  (1)

where ln_{2} x = ln ln x,

F (z) = \frac{1}{Γ(z + 1)} ∏_{p}(1 − \frac{1}{p})^{z}(1 − \frac{z}{p})^{−1},

Γ(z) is Euler’s gamma-function.

For (2 + ε) ln_{2} x ≤ k ≤ \frac{ln x}{ln 2} the asymptotics of �(x, k) was found in [4]. Nickolas showed that in this case

�(x, k) = \frac{1}{4} ∏_{p≥2}(1 + \frac{1}{p(p − 2)})\frac{x}{2^{k}} ln \frac{x}{2^{k}} + O(\frac{x}{2^{k}} ln^{b} \frac{x}{2^{k}} ),  (2)

where b is a constant, 0 < b < 1.

It is shown in Lemma 2 of this work that for 1.9 ln_{2} x ≤ k ≤ 2.1 ln_{2} x there exists a constant c_{1} > 0 with which

�(x, k) ≥ c_{1} \frac{x}{ln x}(\frac{e}{2.2})^{k}.  (3)

We introduce the following notation: f_{k}(n, t) = 1 if Ω(n) = k and all prime factors n exceed t and f_{k}(n, t) = 0 otherwise, f_{k}(n, 1) = f_{k}(n),

Δ_{k}(Q, x, t) = ∑_{d≤Q} max_{y≤x} max_{(a,d)=1} | ∑_{\begin{matrix}n≤y \\ n≡a (mod d) \end{matrix}} f_{k}(n, t) − \frac{1}{φ(d)} ∑_{\begin{matrix}n≤y \\ (n,d)=1 \end{matrix}} f_{k}(n, t)| ,

Δ_{k}(Q, x, 1) = Δ_{k}(Q, x).

The following theorem was proved in [5].

Theorem A. If ln^{5B} x ≤ t ≤ x, then Δ_{k}(Q, x, t) ≪ Q\sqrt{x} ln^{3+2B} x + x ln^{4−B/2} x.

This theorem implies that for t ≥ ln^{10A+40} x we have

Δ_{k}(\sqrt{x} ln^{−5A−19} x, x, t) ≪ x ln^{−A} x,  (4)

where A is any positive constant. Theorem 2 in the work [5] also gives the estimates for Δ_{k}(Q, x). We shall give them here with better values of Q than in [5]. Note that the estimates of Δ_{k}(Q, x) in [5] become trivial if k ≥ b ln_{2} x, where b is a sufficiently large constant. The main goal of our work is to obtain the estimates for Δ_{k}(Q, x) when k ≥ (2 + ε ln_{2} x), ε > 0. In the theorem that follows this is done for k ≤ \frac{ln x}{2 ln 13}.

Theorem 1. If k ≤ b ln_{2} x, where b is a constant, then

Δ_{k}(Q, x) ≪ (\frac{Q}{\sqrt{x}} ln^{6B+b ln 2+2} x + ln^{−B/2+b ln 2+1} x)�(x, k).

If b ln_{2} x ≤ k ≤ Θ(x)\frac{ln x}{A ln 13}, where \frac{A ln 2}{ln_{3} x} ≤ Θ(x) ≤ \frac{(1−ε)A}{2}, ln_{3} x = ln ln ln x, then, with

Q ≤ \sqrt{x} exp(−\frac{Θ(x)}{A} ln x) ln^{−5A−19} x,

we have Δ_{k}(Q, x) ≪ �(x, k) ln^{−A/12+9} x, where ε > 0, A is any positive constant.

A similar result for numbers which have k different prime factors, i.e., when ω(n) = k, was obtained in the work [6] in 1993. The theorem proved in [6] is valid for k ≤ \frac{η ln x}{ln_{2} x}, η > 0, with Q ≤ x^{1/2−ε}, where 0 < ε < 1/2. This value of Q does not allow us to prove theorems of the type given below.

Theorem 2. Let (2 + ε) ln_{2} x ≤ k ≤ η(x) ln x, where ε > 0, η(x) ≤ (\frac{ln_{3} x}{ln_{2} x})^{ρ}, ρ > 2, A(x, k) = {n : n ≤ x, Ω(n) = k}. Then, uniformly with respect to k, we have

∑_{n∈A(x,k)} τ(n − 1) = �(x, k) × ln x(1 + O(\frac{1}{ln^{ε} x}) + O(η(x)(\frac{ln_{2} x}{ln_{3} x})^{ρ})).

Here τ(n) is the number of factors of n.

We shall need the following result proved in [7] (see Lemma 3 in [7]).

Lemma 1. If f(n) ≥ 0 and Q < x, then

∑_{d≤Q} max_{(a,d)=1} ( ∑_{\begin{matrix}n≤x \\ n≡a (mod d) \end{matrix}} f(n) + \frac{1}{φ(d)} ∑_{n≤x} f(n)) ≪ (∑_{n≤x} f^{2}(n))^{1/2}(\sqrt{x} ln^{3/2} x + Q).

For (2 − ε) ln_{2} x ≤ k ≤ (2 + ε ln_{2} x) there is no asymptotic relation for �(x, k). In this case we shall use the following lower estimate.

Lemma 2. There exists a constant c_{1} > 0 with which, for 1.9 ln_{2} x ≤ k ≤ 2.1 ln_{2} x, x ≥ 27, the inequaltiy

�(x, k) ≥ c_{1} \frac{x}{ln x}(\frac{e}{2.2})^{k}

is satisfied.

Proof. We have

�(x, k) ≥ \frac{1}{ln x} ∑_{n≤x} f_{k}(n) ∑_{p^{r}∥n} ln p^{r}.

Here p^{r} ∥ n means that p^{r} divides n whereas p^{r+1} does not divide n. Estimating the part of the sum in which the powers of the primes higher than the first participate, we obtain

�(x, k) ≥ \frac{1}{ln x} ∑_{n≤x} f_{k−1}(n) ∑_{p≤x/n} ln p + O(\frac{x}{ln x}) ≥ \frac{x}{ln x} ∑_{n≤x} \frac{f_{k−1}(n)}{n}μ^{2}(n) + O(\frac{x}{ln x}). (5)

We denote Π(s, y) = ∏_{s≤p<y} p, where ln s = ln_{2} x, ln y = \frac{ln x}{(ln_{2} x)^{2}} . Then

∑_{n≤x} \frac{f_{k−1}(n)}{n}μ^{2}(n) ≥ ∑_{n|Π(s,y)} \frac{f_{k−1}(n)}{n}μ^{2}(n) − ∑_{\begin{matrix}n>x \\ n|Π(s,y) \end{matrix}} \frac{f_{k−1}(n)}{n}μ^{2}(n).  (6)

We have

∑_{n|Π(s,y)} \frac{f_{m}(n)}{n}μ^{2}(n) = \frac{1}{2πi} ∫_{|z|=1} ∑_{n|Π(s,y)} \frac{z^{Ω(n)}}{n} μ^{2}(n)\frac{dz}{z^{m+1}} .

The integrand sum is

∏_{s≤p<y}(1 + \frac{z}{p}) = exp(z ln \frac{ln y}{ln s} ) + O(\frac{1}{ln s}).

Hence we get

∑_{n|Π(s,y)} \frac{f_{m}(n)}{n}μ^{2}(n) = \frac{ln \frac{ln y}{ln s}}{m!} + O(\frac{1}{ln s}).

Consequently, for our choice of s and y, we have

∑_{n|Π(s,y)} \frac{f_{m}(n)}{n}μ^{2}(n) = \frac{(ln_{2} x − 3 ln_{3} x)^{m}}{m!} + O(\frac{1}{ln_{2} x}).  (7)

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

Here ln_{2} x = ln ln x, ln_{3} x = ln ln_{2} x. Using Stirling’s formula n! = n^{n}\sqrt{2πn} exp(−n + θ/(12n)), 0 < θ < 1, we find out that for m = k − 1 satisfying the hypothesis of the theorem, the last sum is equal to

exp((k − 1) ln \frac{ln_{2} x − 3 ln_{3} x}{k − 1} + k − 1 + O(ln k)) + O(\frac{1}{ln_{2} x})

≥ exp((k − 1)(1 − ln 2.1 + ln(1 − \frac{3 ln_{3} x}{ln_{2} x}) + O(\frac{ln k}{k} ))) + O(\frac{1}{ln_{2} x}) ≥ c_{2}(\frac{e}{2.2})^{k},

where c_{2} > 0. The second sum on the right-hand side of (6) is

≤ \frac{1}{ln x} ∑_{n|Π(s,y)} μ^{2}(n)\frac{f_{k−1}(n)}{n} ln n ≤ \frac{1}{ln x} ∑_{s≤p≤y} \frac{ln p}{p} ∑_{n|Π(s,y)} \frac{f_{k−2}(n)}{n}μ^{2}(n)

≤ \frac{1}{(ln_{2} x)^{2}} ∑_{n|Π(s,y)} \frac{f_{k−2}(n)}{n}μ^{2}(n).

Using relation (7) with m = k − 2, we find that it is

≤ \frac{1}{(ln_{2} x)^{2}} (\frac{(ln_{2} x − 3 ln_{3} x)^{k−2}}{(k − 2)!} + O(\frac{1}{ln_{2} x})) ≤ \frac{2.1}{(ln_{2} x)^{2}} ∑_{n|Π(s,y)} \frac{f_{k−1}(n)}{n}μ^{2}(n) + O(\frac{1}{(ln_{2} x)^{3}} ).

Thus, the right-hand side of inequality (6) is ≥ c_{3}(e/2.2)^{k} with a certain constant c_{3} > 0. From this and from inequality (5) follows the statement of Lemma 2.

Proof of Theorem 1. We represent n as n = n_{1}n_{2}, where n_{1} are numbers all of whose prime factors are smaller than t whereas all prime factors of n_{2} are larger than or equal to t; n_{1} and n_{2} may be equal to unity. Then we have

Δ_{k}(Q, x) ≤ ∑_{n_{1}≤t} Δ_{k−Ω(n_{1})}(Q, \frac{x}{n_{1}} , t) + Δ_{k,1}(Q, x) + Δ_{k,2}(Q, x),  (8)

where

Δ_{k,1}(Q, x) = ∑_{d≤Q} max_{y≤x} max_{(a,d)=1} | ∑_{\begin{matrix}t≤n_{1}≤T \\ (n_{1},d)=1 \end{matrix}} (  ∑_{\begin{matrix}n_{2}≤y/n_{1} \\ n_{1}n_{2}≡a (mod d) \end{matrix}} f_{k}(n_{1}n_{2}) − \frac{1}{φ(d)} ∑_{\begin{matrix}n_{2}≤y/n_{1} \\ (n_{2},d)=1 \end{matrix}} f_{k}(n_{1}n_{2}))| ,

Δ_{k,2}(Q, x) ≤ ∑_{d≤Q} max_{(a,d)=1} ( ∑_{\begin{matrix}n_{1}>T \\ (n_{1},d)=1 \end{matrix}} (  ∑_{\begin{matrix}n_{2}≤x/n_{1} \\ n_{1}n_{2}≡a (mod d) \end{matrix}} f_{k}(n_{1}n_{2}) + \frac{1}{φ(d)} ∑_{\begin{matrix}n_{2}≤x/n_{1} \\ (n_{2},d)=1 \end{matrix}} f_{k}(n_{1}n_{2}))) .

For ln^{5B} x ≤ t ≤ T ≤ \sqrt[4]{x} it follows from the theorem that the first sum

≤ ∑_{\begin{matrix}n_{1}≤t \\ k− \frac{ln x}{ln t} ≤Ω(n_{1})≤k \end{matrix}}(Q\sqrt{\frac{x}{n_{1}}} ln^{3+2B} x + \frac{x}{n_{1}} ln^{4−B/2} x) ≪ Q\sqrt{t}\sqrt{x} ln^{3+2B} x + x ln^{5−B/2} x.

Let us first considr the case of k ≤ b ln_{2} x, where b is a positive constant. Taking into account that T ≤ \sqrt[4]{x} and estimating the part of the sum Δ_{k,1}(Q, x) with n_{2} ≤ \sqrt{x}, we have

Δ_{k,1}(Q, x) ≪ k max_{l≤k} ∑_{d≤Q} max_{y≤x} max_{(a,d)=1} | ∑_{\begin{matrix}t≤n_{1}≤T \\ (n_{1},d)=1 \end{matrix}} f_{l}(n_{1}) (  ∑_{\begin{matrix}\sqrt{x}<n_{2}≤y/n_{1} \\ n_{1}n_{2}≡1 (mod d) \end{matrix}} f_{k−l}(n_{2})

−\frac{1}{φ(d)} ∑_{\begin{matrix}\sqrt{x}<n_{2}≤y/n_{1} \\ (n_{2},d)=1 \end{matrix}} f_{k−l}(n_{2}))| + x^{3/4} ln x.

We use Lemma 4 from [7] in order to estimate the last sum. Its special case can be formulated as follows.

Lemma 3. Let a(n), b(n) be arbitrary sequences of complex numbers a(n) = 0 for n ≤ R and b(n) = 0 for n ≤ S. Then, for Q ≤ \sqrt{x}, Δ ≪ R_{1} + R_{2} + R_{3}, where

Δ = ∑_{d≤Q} max_{y≤x} max_{(a,d)=1} | ∑_{\begin{matrix}nm≤y \\ nm≡a (mod d) \end{matrix}} a(n)b(m) − ∑_{\begin{matrix}nm≤y \\ (nm,d)=1 \end{matrix}} a(n)b(m)| ,

R_{1} ≪ (ln x)^{2A_{1}+C_{1}+4} max_{y≤x}(∑_{n≤y} |a(n)|max^{∗} max_{v≤2x/y}| ∑_{S<m≤v} b(m)χ_{q}^{∗}(m)|).

Here A_{1}, C_{1} are arbitrary positive constants and the symbol max^{∗} means that the maximum is taken over all q ≤ ln^{C_{1}} x, d ≤ x and all primitive characters χ_{q}^{∗},

R_{2} = (Q ln x + (\sqrt{\frac{x}{R}} + \sqrt{\frac{x}{S}} ) ln^{2} x + \sqrt{x} ln^{2−C_{1}} x) ln x(max_{y≤x} ∑_{n≤y} |a(n)|^{2} ∑_{m≤x/y} |b(m)|^{2})^{1/2},

R_{3} = x(ln x)^{−A_{1}/5+9}(\frac{1}{x} ∑_{n≤2x} |a(n)|^{4} ∑_{m≤2x/n} |b(m)|^{4})^{1/4}.

In our case R = t, S = \sqrt{x}, |a(n)| ≤ 1, |b(m)| ≤ 1, and therefore

R_{2} ≤ Q\sqrt{x} ln^{2} x + \frac{x}{\sqrt{t}} ln^{3} x + x ln^{3−C_{1}} x, R_{3} ≪ x(ln x)^{10−A_{1}/5}.

In order to estimate R_{1}, we note that

∑_{\begin{matrix}\sqrt{x}≤n_{2}≤v \\ (n_{2},d)=1 \end{matrix}} f_{m}(n_{2})χ_{q}^{∗}(n_{2}) = ∑_{\sqrt{x}≤n_{2}≤v} f_{m}(n_{2})χ_{q}^{∗}(n_{2}) + O (∑_{\begin{matrix}p>t \\ p|d \end{matrix}} \frac{x}{p}) .

The second sum is equal to O(\frac{x}{t} ln x), and, in order to estimate the first sum, we use Lemma 1 [5], in which it is shown that for q ≤ (\frac{1}{k} ln x)^{A}, χ_{q} ≠ χ_{0}, we have

∑_{n_{2}≤x} χ_{q}(n_{2}) ≪ (1 + ε)^{k}x exp(−c_{4}\sqrt{\frac{ln x}{k}})(ln_{2} x)^{k},

where c_{4} > 0.

Taking into account that k ≤ b ln_{2} x, we find that R_{1} ≪ x ln^{−B} x + xt^{−1} ln^{2A_{1}+C_{1}+4} x. Let us take t = ln^{8B} x, A_{1} = 3B, C_{1} = B. Then

Δ_{k,1}(Q, x) ≪ Q\sqrt{x} ln^{2} x + x ln^{10−B/2} x.  (9)

Let us estimate the third sum on the right-hand side of relation (8). It follows from Lemma 1 that

Δ_{k,2}(Q, x) ≪ ( ∑_{n_{1}>T} ∑_{n_{2}≤x/n_{1}} 1)^{1/2}(\sqrt{x} ln^{3/2} x + Q).

We shall need the following estimate.

Lemma 4. Let n_{1} be numbers none of whose prime factors exceed y. Then, for y ≥ 2, 2 ≤ ln \frac{ln T}{ln y} ≤ \frac{1}{3} ln y, ε > 0, we have

∑_{n_{1}≥T} \frac{1}{n_{1}} ≪ exp(−(1 − ε)\frac{ln T}{ln y} ln \frac{ln T}{ln y} ) × (ln y)^{e}.

Proof. We denote σ = (ln y)^{−1} ln \frac{ln T}{ln y}, and then we have

∑_{n_{1}≥T} \frac{1}{n_{1}} ≤ \frac{1}{T^{σ}} ∑_{n_{1}} \frac{n_{1}^{σ}}{n_{1}} ≪ exp(−σ ln T + ∑_{p≤y} \frac{p^{σ}}{p} ).

The second sum is

≤ e ∑_{p≤exp(1/σ)} \frac{1}{p} + y^{σ} ∑_{exp(1/σ)<p≤y} \frac{1}{p} ≤ ln \frac{1}{σ} + y^{σ} ln(σ ln y) + O(y^{σ}),

i.e., the sum being estimated is

≪ exp(−\frac{ln T}{ln y} ln \frac{ln T}{ln y} + e ln \frac{ln y}{ln \frac{ln T}{ln y}} + \frac{ln T}{ln y} ln_{2} \frac{ln T}{ln y} + O(\frac{ln T}{ln y} )).

Hence follows the statement of the lemma.

Using Lemma 4, we get Δ_{k,2}(Q, x) ≪ x ln^{−B} x+Q\sqrt{x} ln^{−B} x, where B is any positive constant. Thus it follows from here and from (8) and (9) that

Δ_{k}(Q, x) ≪ Q\sqrt{x} ln^{6B+2} x + x ln^{10−B/2} x
PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

for k ≤b ln_{2} x. If k ≤b ln_{2} x, then it follows from (1), (2) and from Lemma 2 that �(x, k)≥c_{1}x2^{−b ln_{2} x}, where c_{1} > 0.

Therefore the final result is

Δ_{k}(Q, x) ≪ (\frac{Q}{\sqrt{x}} ln^{6B+b ln 2+2} x + ln^{−B/2+b ln 2+10} x)�(x, k).

Let k ≥ b ln_{2} x, b > 3. In this case, taking into account that all prime factors n_{2} exceed t, we have

Δ_{k}(Q, x) ≤ ∑_{\begin{matrix}n≤T \\ k− \frac{ln x}{ln t} ≤Ω(n_{1})≤k \end{matrix}} Δ_{k−Ω(n_{1})}(Q, \frac{x}{n_{1}} , t) + Δ_{k,2}(Q, x),  (10)

where Δ_{k,2}(Q, x) is the same as in relation (8).

Let

Q ≤ \begin{matrix}√ & \overline{x} \\ √ & \overline{T} \end{matrix} ln^{−5A−19} x,  ln^{10A+40} x ≤ t ≤ \sqrt{x},  T ≤ x^{1−ε}.

Then, by virtue of (4), the first sum will be

≪ ∑_{k− \frac{ln x}{ln t} ≤l≤k} ∑_{n_{1}≤T} \frac{f_{l}(n_{1})}{n_{1}}x ln^{−A} x.

Let us represent n_{1} as n_{1} = 2^{r}m, where (m, 2) = 1. Then we have

∑_{n_{1}≤T} \frac{f_{l}(n_{1})}{n_{1}} ≤ \frac{l}{2^{l}} ∑_{m≤T} \frac{2^{Ω(m)}}{m} ≪ \frac{l}{2^{l}} ln^{2} t.

Thus the first sum is

≪ \frac{x}{ln^{A} x}k2^{\frac{ln x}{ln t}} \frac{ln^{2} t}{2^{k}}.  (11)

Let us estimate Δ_{k,2}(Q, x). We represent n_{1} as n_{1} = d_{1}m_{1}, where all prime factors of d_{1} are smaller

than 17 and all prime factors of m_{1} ≥ 17 but < t. We assume that Q ≤ \sqrt{x/13^{k}}. Using Lemma 1, we obtain

Δ_{k,2}(Q, x) ≪ ∑_{d_{1}≤13^{k}} ( ∑_{\begin{matrix}d_{1}m_{1}n_{2}≤x \\ d_{1}m_{1}≥T \end{matrix}} f_{k}(d_{1}m_{1}n_{2}))^{1/2} \sqrt{\frac{x}{d_{1}}} ln^{3/2} x.

Let T be such that 13^{k} ≤ \sqrt{T}. Then we have

∑_{\begin{matrix}m_{1}n_{2}≤x/d_{1} \\ m_{1}>T/d_{1} \end{matrix}} f_{k}(d_{1}m_{1}n_{2}) ≤ \frac{4^{Ω(d_{1})}}{4^{k}} ∑_{\begin{matrix}m_{1}n_{2}≤x/d_{1} \\ m_{1}>\sqrt{T} \end{matrix}} \frac{4^{Ω(m_{1}n_{2})}}{m_{1}n_{2}} \frac{x}{d_{1}} ≪ \frac{x}{4^{k}} \frac{4^{Ω(d_{1})}}{d_{1}} ln^{4} x ∑_{\sqrt{T} ≤m_{1}≤x/d_{1}} \frac{4^{Ω(m_{1})}}{m_{1}} .

Thus we obtain

Δ_{k,2}(Q, x) ≪ \frac{x}{2^{k}} ln^{4} x ∑_{d_{1}≤x} \frac{2^{Ω(d_{1})}}{d_{1}} ( ∑_{\sqrt{T} ≤m_{1}≤x} \frac{4^{Ω(m_{1})}}{m_{1}} )^{1/2}.

DISTRIBUTION IN THE MEAN IN PROGRESSIONS OF NUMBERS 409

The sum over d_{1} is

≤ k ∏_{3≤p≤13}(1 + ∑_{r=1}^{∞}(\frac{2}{p})^{r}) ≪ ln x.

Applying the Cauchy inequality, we get

∑_{\sqrt{T} ≤m_{1}≤x} \frac{4^{Ω(m_{1})}}{m_{1}} ≤ ( ∑_{m_{1}≤x} \frac{16^{Ω(m_{1})}}{m_{1}} )^{1/2}( ∑_{\sqrt{T} ≤m_{1}≤x} \frac{1}{m_{1}} )^{1/2}.

The first sum is equal to O(ln^{16} x). We take

t = exp(\frac{2 ln 2}{A ln_{2} x} ln x), T = t^{Θ(x) \frac{ln_{2} x}{ln 2}} , where \frac{A ln 2}{ln_{3} x} ≤ Θ(x) ≤ (1 − ε)\frac{A}{2}.

In this case,

\frac{A ln_{2} x}{ln_{3} x} ≤ \frac{ln T}{ln t} ≤ (1 − ε)\frac{A ln_{2} x}{2 ln 2} ≤ ln t.

Using Lemma 4, we obtain

∑_{\sqrt{T} ≤m_{1}≤x} \frac{1}{m_{1}} ≪ ln x exp(−\frac{2}{5} \frac{ln T}{ln t} ln \frac{ln T}{ln t} ) ≪ ln^{1−A/3} x,

and therefore, Δ_{k,2}(Q, x) ≪ \frac{x}{2^{k}} ln^{10−A/12} x. From this and from (10), (11) it follows that

Δ_{k}(Q, x) ≪ \frac{x}{2^{k}} (k2^{\frac{ln x}{ln t}} (ln t)^{2}(ln x)^{−A} + ln^{−A/12+10} x),

i.e., for our choice of t and T, we obtain the statement of Theorem 1 with

Q ≤ \sqrt{\frac{x}{T}} ln^{−19−5A} x, k ≤ Θ(x)\frac{ln x}{A ln 13}.

Proof of Theorem 2. By the hypothesis, k ≤ η(x) ln x, where η(x) ≤ \frac{1−ε}{2 ln 13}. We take Q = \sqrt{x} exp(−η(x) × ln 13 × ln x) × ln^{−19−5A} x, i.e., in the notation of Theorem 1, Θ(x) = η(x) ln 13. After the summation under the hyperbola, we obtain

∑_{n∈A(x,k)} τ(n − 1) = 2 ∑_{d≤Q} ∑_{\begin{matrix}n∈A(x,k) \\ n≡1 (mod d) \end{matrix}} 1 + O ( ∑_{Q≤d≤\sqrt{x+1}} ∑_{\begin{matrix}n∈A(x,k) \\ n≡1 (mod d) \end{matrix}} 1 + ∑_{d≤Q} ∑_{\begin{matrix}n∈A(d\sqrt{x+1},k) \\ n≡1 (mod d) \end{matrix}} 1) . (12)

We apply Theorem 1 to the first sum. We find that it is equal to

2 ∑_{n∈A(x,k)} ∑_{\begin{matrix}d≤Q \\ (d,n)=1 \end{matrix}} \frac{1}{φ(d)} + O(�(x, k) ln^{14−A/6} x).

Let us investigate the principal term. Since (see, e.g., [8, Lemma 3]),

∑_{\begin{matrix}d≤Q \\ (d,n)=1 \end{matrix}} \frac{1}{φ(d)} = F ∏_{p|n}(1 + \frac{1}{p(p − 1)})^{−1}(1 − \frac{1}{p}) ln Q + O(∑_{δ|n} \frac{ln 2δ}{δ} ),

where

F = ∏_{p} \frac{p^{2} − p + 1}{p(p − 1)},

it is equal to

2F ln Q ∑_{n∈A(x,k)}(∑_{δ|n} μ(δ)f(δ) + O(\frac{1}{ln x} ∑_{δ|n} \frac{ln 2δ}{δ} )).

Here f(n) is a multiplicative function f(p) = p/(p^{2} − p + 1) < 1/φ(p). Since

∑_{δ|n} \frac{ln 2δ}{δ} ≪ (1 + ∑_{p^{r}∥n} \frac{ln p^{r}}{p^{r}} ) ∏_{p|n}(1 + \frac{1}{p})^{−1}

≪ ( ∑_{p^{r}≤ln 10n} \frac{ln p^{r}}{p^{r}} + O(1)) exp( ∑_{p≤ln 10n} \frac{1}{p} + O(1)) ≪ (ln_{2} 10n)^{2},

we can write the principal term as

2F ln Q(∑_{δ≤z} μ(δ)f(δ)P_{k−Ω(δ)}(\frac{x}{δ}) + O( ∑_{n∈A(x,k)}( ∑_{δ|n, δ>z} \frac{1}{φ(z)} + \frac{(ln_{2}10x)^{2}}{ln x} ))).

We have used here the fact that μ^{2}(n)f(n) ≤ 1/φ(n). Let us estimate the remainder. We choose z = (ln x)^{ε/2}. We divide the sum over δ | n into two sums over δ_{1} with Ω(δ_{1}) ≤ \frac{ε}{2} ln_{2} x and over the remaining δ_{2}. With (2) taken into account, the first sum is equal to

∑_{δ_{1}>z} \frac{1}{φ(δ_{1})}P_{x−Ω(δ_{1})}(\frac{x}{δ}_{1}) ≪ ∑_{δ>z} \frac{2^{Ω(δ)}}{δφ(δ)} \frac{x}{2^{k}} ln \frac{x}{2^{k}} ≪ \frac{�(x, k)}{\sqrt{z}} ∑_{δ} \frac{2^{Ω(δ)}}{\sqrt{δ}φ(δ)}.

The sum over δ_{2} is

≪ q^{− \frac{ε}{2} ln_{2} x} ∑_{n∈A(x,k)} ∑_{δ|n} \frac{q^{Ω(δ)}}{φ(δ)} .

We take q = \sqrt{e}. Having in mind that

∑_{δ|n} \frac{q^{Ω(δ)}}{φ(δ)} ≪ exp(∑_{p|n} \frac{q}{p}) ≪ (ln_{2} 10n)^{q},

we find that the remainder is equal to O(P_{k}(x) ln^{−ε/5} x). In the principal term we use relation (2). Since δ ≤ z, it follows that Ω(δ) ≤ \frac{ε}{2} ln_{2} x, i.e., the constraints imposed on k − Ω(δ) are fulfilled.

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

We obtain

∑_{δ≤z} μ(δ)f(δ)P_{k−Ω(δ)}(\frac{x}{δ}) = \frac{1}{4}c\frac{x}{2^{k}} ln \frac{x}{2^{k}} (∑_{δ} μ(δ)\frac{f(δ)}{δ} + O(∑_{δ>z} \frac{1}{δφ(δ)} + ln^{b+1} x))

= \frac{c}{4} ∏_{p}(1 − \frac{1}{p^{2} − p + 1})\frac{x}{2^{k}} ln \frac{x}{2^{k}} (1 + O(ln^{−ε/2} x)).

Thus the first sum on the right-hand side of relation (12) is equal to

2(ln Q)�(x, k)(1 + O(ln^{−ε/5} x)).  (13)

Let us estimate the third sum in relation (12). It is

∑_{n≤2\sqrt{x}Q} f_{k}(n)τ(n − 1) ≤ ( ∑_{n≤2\sqrt{x}Q} f_{k}(n))^{1/2}( ∑_{n≤2\sqrt{x}Q} τ^{2}(n))^{1/2}.

Taking into account that Q ≤ \sqrt{x}13^{−k} ln^{−9−5A} x, we find that it is equal to O(x/2^{k}).

Let us estimate the second sum in relation (12). We represent n as n = d_{1}n_{1}n_{2}, where all prime factors of d_{1} are smaller than 17 and those of n_{1} ≥ 17, but smaller than s, and the prime factors of n_{2} are ≥ s. Then d_{1} ≤ 13^{k}, and, since k ≤ η(x) ln x, where η(x) → 0 as x → ∞, we can assume that d_{1} ≤ x^{1/5}. Applying the Cauchy inequality, we find that the part of the sum in which n_{1} ≥ Λ is

≤ ∑_{d_{1}≤x} ( ∑_{\begin{matrix}d_{1}n_{1}n_{2}≤x \\ n_{1}≥Λ \end{matrix}})^{1/2} ( ∑_{d_{1}n_{1}n_{2}≤x} τ^{2}(d_{1}n_{1}n_{2} − 1))^{1/2}.

Taking into account that the number of d, δ such that [d, δ] = n, does not exceed τ_{3}(n), we obtain

∑_{n_{1}n_{2}≤x/d_{1}} τ^{2}(d_{1}n_{1}n_{2} − 1) ≤ ∑_{n_{1}n_{2}≤x/d_{1}} τ_{4}(d_{1}n_{2}n_{1} − 1) ≤ ∑_{\begin{matrix}m≤x \\ m≡−1 (mod d_{1}) \end{matrix}} τ_{4}(m) ≪ \frac{x}{d_{1}} ln^{3} x.

Consequently, the part of the sum being estimated is

≪ \frac{x}{2^{k}} ∑_{d_{1}≤13^{k}} \frac{2^{Ω(d_{1})}}{d_{1}} ( ∑_{\begin{matrix}n_{1}n_{2}≤x \\ n_{1}>Λ \end{matrix}} \frac{4^{Ω(n_{1}n_{2})}}{n_{1}n_{2}} )^{1/2} .

We choose s = exp(100 ln_{3} x × ln x × (ln_{2} x)^{−1}), Λ = x^{1/5}. Just as in the proof of Theorem 1, we find that the sum over d_{1} is equal to O(k) = O(η(x) ln x) and the sum over n_{1}n_{2} is

≪ ln^{9} x exp(−\frac{2}{5} \frac{ln Λ}{ln s} ln \frac{ln Λ}{ln s}) ≪ ln^{9} x exp(−8 ln_{2} x) ≪ ln x,

i.e., the part of the sum being estimated is equal to O(\frac{x}{2^{k}} ln^{3/2} \frac{x}{2^{k}} ).

Thus, it remains to estimate the part of the second sum of relation (12) in which d_{1}n_{1} ≤ Λ13^{k} ≤ x^{1/3}. We can assume that all prime factors of n_{2} divide n_{2} in the first degree. Indeed, the remaining part of the sum is

≪ \frac{x}{2^{k}} ∑_{\begin{matrix}d_{1}n_{1}p^{2}n_{2}≤x \\ p>s \end{matrix}} \frac{2^{Ω(d_{1}n_{1}p^{2}n_{2})}}{d_{1}n_{1}p^{2}n_{2}} τ(d_{1}n_{1}p^{2}n_{2} − 1) ≪ \frac{x}{2^{k}} .

Consequently, we have to estimate the sum which is

≤ ∑_{Q≤d≤\sqrt{x}} ∑_{i=0}^{J} \frac{1}{ρ^{i}} ∑_{\begin{matrix}d_{1}n_{1}≤x^{1/3} \\ Ω(d_{1}n_{1})=k−i \end{matrix}} ∑_{\begin{matrix}n_{2}≤x/d_{1}n_{1} \\ d_{1}n_{1}n_{2}≡1 (mod d) \end{matrix}} ρ^{ω(n_{2})},

where J = \frac{ln x}{ln s}, ρ > 1. In order to estimate this sum, we use Shiu’s theorem [9].

Lemma 5. Let g(n) be a multiplicative function such that O ≤ g(p^{r}) ≤ A_{1}^{r} for all prime numbers p and natural r, g(n) ≤ A_{2}n^{ε} for n ≥ 1, (a, d) = 1, and d ≤ x^{1−ε}, 0 < ε < 1. Then there exists a constant A_{3}, depending only on A_{1}, A_{2}, ε, with which

∑_{\begin{matrix}n≤x \\ n≡a (mod d) \end{matrix}} g(n) ≤ A_{3} \frac{x}{φ(d) ln x} exp (∑_{\begin{matrix}p≤x \\ p∤d \end{matrix}} \frac{g(p)}{p}) .

Using Lemma 5, we find that the sum being estimated is

≪ \frac{x ln \frac{\sqrt{x}}{Q}}{ln x} ∑_{i=0}^{J} \frac{1}{ρ^{i}} ∑_{d_{1}n_{1}≤x^{1/3}} \frac{f_{k−i}(d_{1}n_{1})}{d_{1}n_{1}} exp(ρ ln \frac{ln x}{ln s}).

Since J ≤ \frac{ln x}{ln s}, it follows that k − i ≥ (2 + ε/2) ln x. Therefore, taking into account relation (2), after the Abel summation, we obtain

∑_{n≤x} \frac{f_{k−i}(n)}{n} ≪ \frac{x}{2^{k−i}} ln^{2} x.

Consequently, if we choose ρ > 2, then the sum being estimated is equal to

O(\frac{x}{2^{k}} ln x × ln \frac{\sqrt{x}}{Q} × (\frac{ln x}{ln s})^{ρ}).

Substituting the obtained estimate into (12) and taking into account (13), we obtain

∑_{n∈A(x,k)} τ(n − 1) = �(x, k) ln x(1 + O(ln^{−ε} x)) + O(\frac{x}{2^{k}} ln \frac{x}{2^{k}} × ln \frac{\sqrt{x}}{Q} × (\frac{ln_{2} x}{ln_{3} x})^{ρ}),

where ρ > 2. For Q = \sqrt{x} exp(−η(x) ln x) ln^{−19−5A} x the seconnd term is equal to

O(\frac{x}{2^{k}} ln \frac{x}{2^{k}} × ln x × η(x)(\frac{ln_{2} x}{ln_{3} x})^{ρ}).

Hence follows the statement of Theorem 2.

ACKNOWLEDGMENTS

This work was supported by the Russian Foundation for Basic Research (project no. 96-01-00502).

REFERENCES

1. Landau, E., Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1, Leipzig, 1909.

2. Sathe, L. G., On a Problem of Hardy on the Distribution of Integers Having a Given Number of Prime Factors, J. Indian Math. Soc., 1953, vol. 17, pp. 63–141.

3. Selberg, A., Note on a Paper by L. G. Sathe, J. Indian Math. Soc., 1954, vol. 18, pp. 83–87.

4. Nicolas, J.-L., Sur la distribution des nombres entiers ayant une quantite fixee de facteurs premiers, Acta Arith., 1984, vol. 44, pp. 191–200.

5. Timofeev, N. M. and Khripunova, M. V., Distribution of Numbers with a Given Number of Prime Factors in Progressions, Mat. Zametki, 1994, vol. 55, no. 2, pp. 144–156.

6. Wolke, D. and Zhan, Tao, On the Distribution of Integers with a Fixed Number of Prime Factors, Math. Z., 1993, vol. 213, pp. 133–147.

7. Levin, B. V. and Timofeev, N. N., Distribution of Arithmetic Functions in the Mean over Progressions (Theorems of the Vinogradov–Bombieri Type), Mat. Sb., 1984, vol. 125 (167), no. 4 (12), pp. 558–572.

8. Timofeev, N. M. and Khripunova, M. B., Titchmarsh Problem with Numbers Having a Specified Number of Prime Factors, Mat. Zametki, 1996, vol. 59, no. 4, pp. 586–603.

9. Shiu, P., A Brun–Titchmarsh Theorem for Multiplicative Functions, J. Reine Angew. Math., 1980, vol. 313, pp. 161–170.

Translated by I. Aleksandrova