ON THE SIEVE OF ERATOSTHENES

M. Ram Murty * and N. Saradha

§1. Introduction

Let ν(n) denote the number of distinct prime factors of a natural number n. A classical theorem of Hardy and Ramanujan states that the normal order of ν(n) is log log n. That is, given any ϵ > 0, the number of natural numbers not exceeding x which fail to satisfy the inequality

(1)  |ν(n) − log log n| < ϵ log log n

is o(x) as x → ∞. A very simple proof of this was subsequently given by Turán. He showed that

(2)  ∑_{n≤x}(ν(n) − log log n)^{2} = x log log x + O(x).

Then, (1) is an immediate consequence of (2). The methods of proof were subsequently generalised to treat other additive functions. The historical developments which ultimately led to the celebrated Erdös-Kac theorem are described in the monographs of Elliott [3].

In 1935, Erdös [1] proved that the number of primes p not exceeding x which fail to satisfy the inequality

(3)  |ν(p − 1) − log log p| < ϵ log log p

is o(x/ log x), for any given ϵ > 0. His main tool to establish (3) was Brun’s sieve. If ϕ denotes the Euler ϕ function, then recently, it was established in [2] and [4], that ν(ϕ(n)) has normal order \frac{1}{2}(log log n)^{2}. In both papers, the Bombieri-Vinogradov theorem on primes in arithmetic progressions was invoked. In [2], it was shown that

(4)  ∑_{n≤x}(ν(ϕ(n)) − \frac{1}{2}(log log n)^{2})^{2} = o(x(log log x)^{4})

as x → ∞. This theorem was a consequence of a general result concerning prime divisors of various sequences, with special reference to Fourier coefficients of modular forms. By

* Research supported in part by NSERC grant U0237 utilising a general theorem of Kubilius and Shapiro [3], Erdös and Pomerance, proved in [4] that if we let G(x, u) denote the number of n ≤ x satisfying the inequality

(5)  ν(ϕ(n)) < \frac{1}{2}(log log x)^{2} + \frac{u}{\sqrt{3}}(log log x)^{3/2},

then

(6)  lim_{x→∞} \frac{G(x, u)}{x} = \frac{1}{\sqrt{2π}} ∫_{−∞}^{u} e^{−t^{2}/2}dt.

The purpose of this paper is to establish (3) and (4) utilising nothing more than the sieve of Eratosthenes. In the course of the proof, we do not need any information on primes in arithmetic progressions, nor do we use the elementary estimate of Tchebycheff on the number of primes less than x.

§2. The sieve of Eratosthenes

Let A be any set of natural numbers ≤ x and let P be a set of primes. To each prime p, let there be ω(p) distinguished residue classes (mod p). Let A_{p} denote the set of elements of A lying in at least one of these distinguished residue classes (mod p) and set for any natural number d,

A_{d} = ∩_{p|d}A_{p}.

As usual, we denote by S(A, P, z) the number of elements of

A \ ∪_{p≤z,p∈P} A_{p}.

Let ω(d) = ∏_{p|d} ω(p) for each squarefree number d. We suppose that there is an X such that

|A_{d}| = \frac{Xω(d)}{d} + R_{d}.

We also set

P (z) = ∏_{p≤z,p∈P} p.

μ, as usual, will denote the Möbius function and we set

W (z) = ∏_{p≤z,p∈P}(1 − \frac{ω(p)}{p}).

We shall further suppose that there is a constant C > 0 such that |A_{d}| = 0 for d > Cx. For convenience, we write the iterated logarithms: log_{m} x = log(log_{m−1} x), log_{1} x = log x.

Theorem 1. Let A be a set of natural numbers ≤ x, satisfying

(i)  |R_{d}| = O(ω(d))
(ii)  ∑_{p≤z,p∈P} \frac{ω(p) log p}{p} ≤ κ log z + O(1).

Then

S(A, P, z) = XW (z) + O(x(log z)^{κ+1} exp(−\frac{log x}{log z})).

We will require the following lemmas. Lemma 1. Let

F_{ω}(t, z) = ∑_{d≤t,d|P (z)} ω(d).

Then,

F_{ω}(t, z) = O(t(log z)^{κ} exp(−\frac{log t}{log z})).

PROOF. We utilise a classical method of Rankin. Clearly, for any δ > 0, we have

F_{ω}(t, z) ≤ ∑_{d|P (z)} ω(d)(t/d)^{δ}.

As ω is multiplicative, we deduce that

F_{ω}(t, z) ≤ exp(δ log t + ∑_{p≤z,p∈P} ω(p)p^{−δ}),

on applying the elementary inequality 1 + x ≤ e^{x}. Setting δ = 1 − η and utilising the inequality e^{x} ≤ 1 + xe^{x}, which is valid for x ≥ 0, we find

F_{ω}(t, z) ≤ t exp(−η log t + ∑_{p≤z,p∈P} \frac{ω(p)}{p} + ηz^{η} ∑_{p≤z,p∈P} \frac{ω(p) log p}{p}).

By condition (ii) in Theorem 1, we find by partial summation that

∑_{p≤z,p∈P} \frac{ω(p)}{p} ≤ κ log_{2} z + O(1).

Thus,

F_{ω}(t, z) ≪ t exp(−η log t + κ log_{2} z + κη(log z)z^{η}).

Choosing η = (log z)^{−1}, gives the desired result. Remark. Let G(x, z) denote the number of n ≤ x all of whose prime factors are ≤ z. A similar method yields the estimate

G(x, z) ≪ x(log z) exp(−\frac{log x}{log z}).

Lemma 2.

∑_{d|P (z),d>Cx} \frac{ω(d)}{d} = O((log z)^{κ+1} exp(−\frac{log x}{log z})).

PROOF. Clearly,

∑_{d|P (z),d>Cx} \frac{ω(d)}{d} ≪ ∫_{Cx}^{∞} \frac{F_{ω}(t, z)}{t^{2}}dt

and the result now easily follows from Lemma 1. PROOF OF THEOREM 1. We have by the inclusion-exclusion principle,

\begin{aligned}S(A, P, z) & = ∑_{d|P (z),d≤Cx} μ(d)|A_{d}| \\ & = ∑_{d|P (z),d≤Cx} μ(d)\frac{Xω(d)}{d} + O(F_{ω}(Cx, z)). \end{aligned}

by utilising (i). Thus, by lemmas 1 and 2, we find easily

S(A, P, z) = XW (z) + O(x(log z)^{κ+1} exp(−\frac{log x}{log z}))

as desired. Corollary 1. Let π(x) denote the number of primes p ≤ x. Then,

π(x) ≪ \frac{x}{log x} log log x.

PROOF. Set

log z = \frac{log x}{3 log log x}

in Theorem 1.

Remark. The elementary reasoning used above actually yields a better result than stated, but to keep the exposition simple we have chosen our parameters in the simplest possible manner. More precisely, if

2κz log z > log x,

then

(†)  S(A, P, z) = XW (z) + O(x(log z)^{κ+1} exp(−\frac{log x}{2 log z} log(\frac{log x}{log z}))).

This is obtained by setting

η = \frac{1}{log z} log(\frac{log x}{2κ log z}) < 1

in lemmas 1 and 2. This would then yield the result

π(x) ≪ \frac{x log_{2} x}{log x log_{3} x}

for the choice

log z = \frac{log x}{log_{2} x} log_{3} x.

This bound for π(x) is better than the estimate derived from the elementary Brun’s sieve.

Corollary 2. For any natural number m < x, denote by N(x, m) to be the number of solutions of

p − 1 = qm,

where p and q are prime numbers ≤ x. Then for some absolute constant B > 0, we have

N(x, m) ≤ \frac{Bx(log_{2}(x/m))^{2}}{ϕ(m)(log(x/m))^{2}} .

PROOF. Let A denote the set of natural numbers ≤ x/m. Clearly, N(x, m) − z^{2} is less than the number of solutions of b − 1 = am, a ∈ A, where a and b are free of prime factors ≤ z. Thus we count the number of a ∈ A such that a and am + 1 are free of prime factors ≤ z. Let P denote the set of primes p ≤ z. Then for each prime p ∈ P, (p, m) = 1, we have ω(p) = 2. If p|m, then ω(p) = 1. For each d|P (z),

|A_{d}| = \frac{ω(d)x}{md} + R_{d},

where |R_{d}| ≤ ω(d). Moreover, |A_{d}| = 0 for d > x/m. Thus, with X = x/m, we apply Theorem 1 and obtain the desired result with

log z = \frac{log(x/m)}{5 log_{2}(x/m)}.

Corollary 3. Let E > 0 and let π(x, q) denote the number of primes p ≤ x, p ≡ 1 (mod q). Then

π(x, q) ≪ \frac{x log_{2} x}{ϕ(q) log x}

uniformly for q ≤ log^{E} x, where the implied constant depends only on E.

PROOF. Let A consist of n ≤ x, n ≡ 1(mod q) and let P be the set of primes p ≤ z where

log z = \frac{log x}{(E + 3) log log x}.

Then,

S(A, P, z) ≪ \frac{x log_{2} x}{ϕ(q) log x} + O(\frac{x}{log^{E+1} x}).

But

π(x, q) ≤ z + S(A, P, z) ≪ \frac{x log_{2} x}{ϕ(q) log x}.

Corollary 4. Uniformly for q ≤ log^{E} x,

∑_{{p≤x \atop p≡1 (mod q)}} \frac{1}{p} ≪ \frac{(log log x)^{2}}{ϕ(q)} .

PROOF. This follows easily from Corollary 3 and partial summation.

Remark. Both Corollary 3 and 4 can be refined in view of our earlier remark concerning the choice of z. Indeed, it is clear that (†) implies that

π(x, q) ≪ \frac{x log_{2} x}{ϕ(q)(log x) log_{3} x}

uniformly for q ≤ log^{E} x. This would yield the corresponding result in corollary 4:

∑_{{p≤x \atop p≡1(mod q)}} \frac{1}{p} ≪ \frac{(log logx)^{2}}{ϕ(q) log_{3} x} ,

uniformly for q ≤ log^{E} x. We will need this slight improvement of corollary 4 in §4 to prove that ν(ϕ(n)) has normal order \frac{1}{2}(log log n)^{2}. It is interesting that crude estimates suffice for establishing the normal order of Ω(ϕ(n)).

§3. The normal order of ν(p − 1)

In this section, we shall show that the normal number of prime factors of p − 1 is log log p. In this, we essentially follow Erdös [1], except in the use of Brun’s sieve. Since we need a more refined version of his result, we state the results explicitly.

Lemma 3. For k ≥ 1, let f_{k}(x) denote the number of primes p ≤ x such that ν(p−1) = k. Then, for any E > 0,

f_{k}(x) < \frac{Bx}{(k − 1)!(log x)^{2}} (log_{2} x + D)^{k+4} + O(\frac{x}{(log x)^{E}}),

where B and D are constants and the constant implied by the O symbol does not depend on k.

Remark. Let Ω(n) denote the number of prime factors of n counted with multiplicity. Then, it will be apparent from the proof that the number of primes p ≤ x such that Ω(p − 1) = k satisfies a similar estimate.

PROOF. Let M_{1} denote the set of all primes p ≤ x such that all of the prime factors of p − 1 are less than

y = exp(\frac{log x}{(E + 1) log log x}).

Then, by the remark after lemma 1, the number of such primes is

O(\frac{x}{(log x)^{E}}).

Thus, we can suppose that some prime factor of p − 1 is greater than y. If we let M_{2} denote the set of all primes p ≤ x such that the square of the largest prime factor of p − 1 divides p − 1, and p ∉ M_{1}, then the cardinality of M_{2} is bounded by

∑_{m>y} \frac{x}{m^{2}} = O(\frac{x}{(log x)^{E}}).

Now let p ∉ M_{1} ∪ M_{2} and suppose that ν(p − 1) = k, then

p − 1 = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{k}^{α_{k}},

where p_{1} < p_{2} < ⋯ < p_{k}, α_{k} = 1. Thus,

p − 1 = p_{k}n_{k},

where n_{k} is a natural number < x/y such that ν(n_{k}) = k − 1. For a fixed n_{k}, the number of primes p < x, satisfying p − 1 = qn_{k}, is by Corollary 2,

\frac{Bx(log log(x/n_{k}))^{2}}{ϕ(n_{k})(log(x/n_{k}))^{2},}

and therefore,

f_{k}(x) ≪ \frac{x}{(log x)^{E}} + Bx ∑_{{n<x/y \atop ν(n)=k−1}} \frac{(log_{2}(x/n))^{2}}{ϕ(n) log^{2}(x/n)},

≪ \frac{x}{(log x)^{E}} + \frac{x(log_{2} x)^{4}}{log^{2} x} ∑_{{n<x/y \atop ν(n)=k−1}} \frac{1}{ϕ(n)}.

Since,

∑_{{n<z \atop ν(n)=k−1}} \frac{1}{ϕ(n)} < \frac{1}{(k − 1)!}(∑_{p<z} \frac{1}{p − 1} + c_{1})^{k−1},

for some constant c_{1}, it follows by elementary estimates that

f_{k}(x) ≪ \frac{x(log_{2} x + c_{1})^{k+3}}{(k − 1)! log^{2} x} + \frac{x}{(log x)^{E}} ,

where the implied constant does not depend on k. This completes the proof of Lemma 3.

Lemma 4. For δ > 1,

(i) ∑_{k>δa} \frac{a^{k}}{k!} ≤ δ^{−δa}e^{δa}

and for δ < 1,

(ii) ∑_{k<δa} \frac{a^{k}}{k!} ≤ δ^{−δa}e^{δa}(δa).

PROOF. We have

∑_{k>δa} \frac{a^{k}}{k!} = ∑_{k>δa} \frac{(δa)^{k}}{k!} δ^{−k} ≤ δ^{−δa}e^{δa}

for δ > 1. This proves (i). To prove (ii), we utilise the elementary inequality

log k! > ∫_{1}^{k} log t dt > k log k − k

and the fact that a^{k}/k! is an increasing function of k for k < δa when δ < 1, to deduce that

∑_{k<δa} \frac{a^{k}}{k!} ≤ (δa)δ^{−δa}e^{δa}

which establishes (ii).

Theorem 2. Let 0 < ϵ < 1. The number of primes p ≤ x which fail to satisfy the inequality

|ν(p − 1) − log log p| < ϵ log log p

is

O(\frac{x}{(log x)^{1+ϵ^{2}}} ).

PROOF. We need to estimate the sums

∑_{k>(1+ϵ) log_{2} x} f_{k}(x)

and

∑_{k<(1−ϵ) log_{2} x} f_{k}(x).

To estimate the first sum, we first note that f_{k}(x) = 0 if k > log x, since ν(n) < log n. Thus, by lemmas 3 and 4, we obtain

∑_{k>(1+ϵ) log_{2} x} f_{k}(x) ≪ \frac{x(log_{2} x)^{4}}{log^{2} x} ∑_{k>(1+ϵ) log_{2} x} \frac{(log_{2} x + c_{1})^{k−1}}{(k − 1)!} ≪ \frac{x(log_{2} x)^{4}}{(log x)^{1+ϵ^{2}}} .

The second sum is estimated similarly.

In order to deduce that the normal order of ν(p − 1) is log log p, we need to show that

π(x) ≫ \frac{x}{log x}.

We have the following elementary result.

Lemma 5.

π(x) ≫ \frac{x}{log x}.

PROOF. Utilising

∑_{p≤x} \frac{1}{p} = log log x + c_{1} + O(\frac{1}{log x}),

for some constant c_{1}, we deduce that for some η > 0, the inequality

∑_{ηx<p<x} \frac{1}{p} ≫ \frac{1}{log x},

holds. Thus, we obtain the inequality,

\frac{π(x)}{ηx} ≥ ∑_{ηx<p<x} \frac{1}{p} ≫ \frac{1}{log x}

which gives us the desired inequality.

Hence, Theorem 1 and lemma 5 imply that for almost all primes, the number of prime factors of p − 1 is log log p. We can proceed to obtain an estimate for the variance. As this is routine and straightforward, we suppress the details. The method is illustrated in the following lemma which we need in the next section.

Lemma 6. As x → ∞,

(i)  ∑_{p≤x} ν(p − 1) ∼ π(x) log log x,

(ii)  ∑_{p≤x} ν^{2}(p − 1) ≪ π(x)(log log x)^{2}.

PROOF. We have

(7)  ∑_{p≤x} ν(p − 1) ≤ (1 + ϵ)π(x) log log x + ∑_{{p≤x \atop ν(p−1)>(1+ϵ) log log p}} ν(p − 1).

The latter sum is by the Cauchy-Schwartz inequality, Theorem 2, and lemma 5,

≤ (\frac{π(x)}{log^{δ} x})^{1/2} (∑_{p≤x} ν^{2}(p − 1))^{1/2} .

Moreover,

∑_{p≤x} ν^{2}(p − 1) ≪ π(x)(log log x)^{2} + ∑_{{p≤x \atop ν(p−1)>2K log log x}} ν^{2}(p − 1).

For K sufficiently large, we deduce by lemmas 3 and 4 that

∑_{k>2K log log x} f_{k}(x) ≪ \frac{x}{log^{K} x}

so that

∑_{{p≤x \atop ν(p−1)>2K log log x}} ν^{2}(p − 1) ≪ \frac{x}{log^{K−2} x}

since ν(p − 1) = O(log p). Again, we have used the fact that f_{k}(x) = 0 if k > log x. Thus,

∑_{p≤x} ν^{2}(p − 1) ≪ π(x)(log log x)^{2}.

This proves (ii). Therefore, the second sum in (7) is found to be

o(π(x) log log x)

as x → ∞. This completes the proof of Lemma 6, since the lower bound asymptotic formula is similarly deduced.

Let Ω(n) denote the total number of prime factors of n, counted with multiplicity, defined earlier. It is clear that the above methods yield a corresponding result for Ω(p−1). We state this for future reference.

Lemma 7. As x → ∞,

(i)  ∑_{p≤x} Ω(p − 1) ∼ π(x) log log x,

(ii)  ∑_{p≤x} Ω^{2}(p − 1) ≪ π(x)(log log x)^{2}.

§4. The normal order of ν(ϕ(n))

We begin by showing that Ω(ϕ(n)) has normal order \frac{1}{2}(log log n)^{2}.

Lemma 8.

∑_{p≤x} \frac{Ω(p − 1)}{p} ∼ \frac{1}{2}(log log x)^{2}.

PROOF. By lemma 7, the sum is by partial summation,

∼ ∫_{2}^{x} \frac{π(t) log log t}{t^{2}}dt.

But

∑_{p≤x} \frac{log log p}{p} ∼ ∫_{2}^{x} \frac{π(t) log log t}{t^{2}}dt.

Moreover,

∑_{p≤x} \frac{log log p}{p} ∼ \frac{1}{2}(log log x)^{2},

which is derived by partial summation from the elementary result

∑_{p≤x} \frac{1}{p} = log log x + c_{1} + O(\frac{1}{log x}).

The desired result now follows immediately. Theorem 3. As x → ∞,

∑_{n≤x}(Ω(ϕ(n)) − \frac{1}{2}(log log x)^{2})^{2} = o(x(log log x)^{4}).

PROOF. Let us define

f(n) = ∑_{p|n} Ω(p − 1).

Then,

f(n) ≤ Ω(ϕ(n)) ≤ f(n) + Ω(n).

In view of (2), it therefore suffices to show that

∑_{n≤x}(f(n) − \frac{1}{2}(log log x)^{2})^{2} = o(x(log log x)^{4}),

since the inequality

(a + b)^{2} ≤ 2(a^{2} + b^{2})

implies that

∑_{n≤x}(Ω(ϕ(n)) − \frac{1}{2}(log log x)^{2})^{2} ≪ ∑_{n≤x}(f(n) − \frac{1}{2}(log log x)^{2})^{2} + ∑_{n≤x}(Ω(ϕ(n)) − f(n))^{2}. To this end, we note that

∑_{n≤x} f(n) = x ∑_{p≤x} \frac{Ω(p − 1)}{p} + O(∑_{p≤x} Ω(p − 1)).

Since

∑_{p≤x} Ω(p − 1) ≪ ∑_{n≤x} Ω(n) ≪ x log log x,

by elementary estimates, we deduce from lemma 8 that

∑_{n≤x} f(n) ∼ \frac{1}{2}x(log log x)^{2}.

Also,

∑_{n≤x} f^{2}(n) = ∑_{n≤x} ∑_{p,q|n} Ω(p − 1)Ω(q − 1),

where p and q denote primes. Then,

∑_{n≤x} f^{2}(n) ≤ x ∑_{pq≤x} \frac{Ω(p − 1)Ω(q − 1)}{pq} + x ∑_{p≤x} \frac{Ω^{2}(p − 1)}{p}.

Noting that

( ∑_{p≤\sqrt{x}} \frac{Ω(p − 1)}{p})^{2} ≤ ∑_{pq≤x} \frac{Ω(p − 1)Ω(q − 1)}{pq} ≤ (∑_{p≤x} \frac{Ω(p − 1)}{p})^{2}

we deduce from lemma 8 that

∑_{pq≤x} \frac{Ω(p − 1)Ω(q − 1)}{pq} ∼ \frac{1}{4}(log log x)^{4}.

Moreover, by lemma 7(ii) and partial summation, we deduce that

∑_{p≤x} \frac{Ω^{2}(p − 1)}{p} ≪ ∫_{2}^{x} \frac{π(t)(log log t)^{2}}{t^{2}} dt ∼ ∑_{p≤x} \frac{(log log p)^{2}}{p} ≪ (log log x)^{3}.

It therefore follows from the above that

∑_{n≤x} f^{2}(n) ≤ \frac{1}{4}x(log log x)^{4} + o(x(log log x)^{4})

as x → ∞. The assertion of the theorem follows immediately from this. We can now prove:

Theorem 4. ν(ϕ(n)) has normal order \frac{1}{2}(log log n)^{2}.

PROOF. We first note that ν(ϕ(n)) ≤ Ω(ϕ(n)) and so

ν(ϕ(n)) ≤ (1 + ϵ)\frac{1}{2}(log log n)^{2}

for almost all n. To establish the corresponding lower bound, we first note that if

Ω(ϕ(n)) − ν(ϕ(n)) ≥ 1,

then there must be a prime q such that q^{2}|ϕ(n). If q > y, the number of n ≤ x such that q^{2}|ϕ(n) is

(8)  ≤ ∑_{q>y} \frac{x}{q^{3}} + ∑_{q>y} ∑_{{p≤x \atop q^{2}|p−1}} \frac{x}{p} + ∑_{q>y} ∑_{{p≤x \atop q|p−1, q|p′−1}} \frac{x}{pp′} .

The first sum is clearly bounded by

\frac{x}{y^{2}} .

To handle the second sum, we write it as

(9)  ∑_{q>log^{E} x} + ∑_{y<q<log^{E} x}

and handle the penultimate sum in a trivial way:

∑_{q>log^{E} x} ∑_{{p≤x \atop q^{2}|p−1}} \frac{x}{p} ≪ ∑_{q>log^{E} x} ∑_{t≤x} \frac{x}{q^{2}t} ≪ \frac{x}{log^{E−1} x}.

For the last sum in (9), we use corollary 4 of Theorem 1 to obtain that the two sums in (9) are

≪ \frac{x}{log^{E−1} x} + \frac{x(log log x)^{2}}{y} .

Similarly, the third sum in (8) is seen to be

≪ \frac{x}{log^{E−2} x} + \frac{x(log log x)^{4}}{y} .

Choosing E = 3 and y = (log log x)^{5}, we deduce that for almost all n ≤ x, q^{2}|ϕ(n) implies that q ≤ y. Therefore, if we define Ω_{y}(n) to be the number of prime powers q^{α} dividing n such that q < y, then we have proved that for almost all n,

ν(ϕ(n)) ≥ Ω(ϕ(n)) − Ω(n) − ∑_{p|n} Ω_{y}(p − 1).

Since Ω(n) has normal order log log n, to prove the theorem, it suffices to show that for any η > 0,

∑_{p|n} Ω_{y}(p − 1) ≤ η(log log n)^{2}

for almost all n. To this end, we have

∑_{n≤x} ∑_{p|n} Ω_{y}(p − 1) ≤ x ∑_{p≤x} \frac{Ω_{y}(p − 1)}{p}

≪ x ∑_{q≤y} ∑_{{p≤x \atop q^{α}|p−1}} \frac{1}{p}

≪ x ∑_{{q<y \atop q^{α}<log^{3} x}} ∑_{{p≤x \atop q^{α}|p−1}} \frac{1}{p} + x ∑_{{q<y \atop q^{α}≥log^{3} x}} ∑_{{p≤x \atop q^{α}|p−1}} \frac{1}{p}.

The last sum is estimated in a trivial way, as before, and is seen to be O(x). By the remark after corollary 4, the penultimate sum is seen to be

≪ x\frac{(log log x)^{2}}{log_{3} x} log_{4} x.

Thus, the inequality

∑_{p|n} Ω_{y}(p − 1) > η(log log n)^{2}

can hold for at most o(x) numbers n ≤ x. Hence, for almost all n,

Ω(ϕ(n)) − η(log log n)^{2} ≤ ν(ϕ(n)) ≤ Ω(ϕ(n)).

Theorem 3 now completes the proof.

§5. Concluding remarks

In proving (6), Erdös and Pomerance [4] utilise a general theorem of Kubilius and Shapiro (see Elliott [3]). This theorem states that for any strongly additive real-valued function f, (that is, f(p^{a}) = f(p)),

lim_{x→∞} G_{f}(x, u) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{u} e^{−t^{2}/2} dt

where

G_{f}(x, u) = card{n ≤ x : f(n) − A(x) ≤ uB(x)},

A(x) = ∑_{p≤x} \frac{f(p)}{p},

B(x)^{2} = ∑_{p≤x} \frac{f^{2}(p)}{p},

provided that for each ϵ > 0,

∑_{{p≤x \atop f(p)>ϵB(x)}} \frac{f^{2}(p)}{p} = o(B^{2}(x))

as x → ∞. It is possible to verify the above condition utilising only the sieve of Eratosthenes (Theorem 1) following the methods of the previous sections. This would then give a proof of (6) independent of the Bombieri-Vinogradov theorem.

It would be highly interesting to derive the “modular analogues” of these results. For instance, in [2], it was proved that

∑_{{p≤x \atop τ(p)≠0}}(ν(τ(p)) − log log p)^{2} ≪ \frac{x log_{2} x}{log x},

where τ denotes the Ramanujan τ function, assuming a non-abelian analogue of the Bombieri-Vinogradov theorem. This latter hypothesis is a consequence of the generalised Riemann hypothesis for the Dedekind zeta functions. The “modular analogue” was established in [5]. Therefore, it would be of exceeding importance if the methods of this paper could be extended to treat Fourier coefficients of modular forms.

Acknowledgements. We would like to thank E. Fouvry and the referee for their comments on an earlier version of this paper.

REFERENCES

[1] P. Erdös, On the normal number of prime factors of p − 1 and some related problems concerning the Euler’s ϕ function, Quarterly Journal of Mathematics, Ser. 6 (1935) 205-213.

[2] M. Ram Murty and V. Kumar Murty, Prime divisors of Fourier coefficients of modular forms, Duke Math. Journal, 51 (1984) 57-76.

[3] P.D.T.A. Elliott, Probabilistic Number Theory I and II, Springer Verlag, New York, 1980.

[4] P. Erdös and C. Pomerance, On the normal number of prime factors of ϕ(n), Rocky Mountain Journal, 15 (1985) 343-352.

[5] M. Ram Murty and V. Kumar Murty, An analogue of the Erdös-Kac theorem for Fourier coefficients of modular forms, Indian Journal of Pure and App. Math., 15(1984)1090-1101.

Department of Mathematics, McGill University, Montréal, Canada

and

Department of Mathematics, Concordia University, Montréal, Canada.