NON-ABELIAN GENERALIZATIONS OF THE ERDŐS-KAC THEOREM

M. Ram Murty^{†} and Filip Saidak

1. INTRODUCTION

Let ω(n) and Ω(n) denote the number of prime factors of n, counted without multiplicity and with multiplicity, respectively. In 1917, Hardy and Ramanujan [7] proved that the normal order of ω(n) and Ω(n) is log log n. This means that given any ϵ > 0, the number of n ≤ x failing to satisfy the inequality

|f(n) − log log n| < ϵ log log n,

with f = ω or Ω, is o(x) as x → ∞. Subsequently, in 1934, Turán [23] gave a simple proof of this fact by showing that

(1)  ∑_{n≤x}(ω(n) − log log n)^{2} ≪ x log log x.

Recently, Saidak [19] improved Turán’s theorem by proving the asymptotic formula

∑_{n≤x}(ω(n) − log log n)^{2} = x log log x + Cx + O (\frac{x log log x}{log x}) ,

for some constant C. The underlying ideas behind these theorems form the foundations of the theory of probabilistic number theory. Indeed, in 1940, Erdős and Kac [4] proved that the quantity

\frac{ω(n) − log log n}{\sqrt{log log n}}

is distributed ‘normally’. More precisely, they proved that for any α < β,

(2) # \{n ≤ x : α ≤ \frac{ω(n) − log log n}{\sqrt{log log n}} ≤ β\} ∼ Φ(α, β)x,

Erdős-Pomerance conjecture.

1991 Mathematics Subject Classification. 11K36, 11K99.

Key words and phrases. Turán’s theorem, Erdős-Kac theorem, Chebotarev density theorem,

† Research partially supported by an NSERC grant.

as x → ∞, where

Φ(α, β) = \frac{1}{\sqrt{2π}} ∫_{α}^{β} e^{−t^{2}/2} dt.

This theorem opened the way for a more general theory by Kubilius [8] and Shapiro [22] applicable to a wider class of what are called ‘strongly additive’ (see definition below) functions. In the early ‘60s and subsequently the ‘70s, the theory was refined by many authors and one can find a comprehensive treatment of it in the monograph of Elliott [2].

For instance, a ‘prime’ analog of the theorem of Turán, can be proved using the methods indicated in [14]:

(3)  ∑_{p≤x}(ω(p − 1) − log log p)^{2} ≪ π(x) log log x,

where the summation is over primes p ≤ x and π(x) denotes the number of primes p ≤ x. The normal order of ω(p − 1) was first determined in 1935 by Erdős [3] by more complicated methods. The corresponding version of the Erdős-Kac theorem was discovered by Halberstam [6] in 1955, who proved that for all α < β,

(4) # \{p ≤ x : α ≤ \frac{ω(p − 1) − log log p}{\sqrt{log log p}} ≤ β\} ∼ Φ(α, β)π(x),

as x → ∞.

A new type of ‘Erdős-Kac’ theorem, which can be described as ‘non-abelian’, was discovered by Kumar and Ram Murty [14] in the early 1980’s. A special case of their theorem will illustrate our meaning.

Let τ(n) denote the Ramanujan τ-function. Assuming a generalized Riemann hypothesis (to be made more precise below), they proved that

# \{p ≤ x : α ≤ \frac{ω(τ(p)) − log log p}{\sqrt{log log p}} ≤ β\} ∼ Φ(α, β)π(x),

and assuming τ(n) never vanishes (Lehmer’s conjecture [11])

# \{n ≤ x : α ≤ \frac{ω(τ(n)) − \frac{1}{2}(log log n)^{2}}{\frac{1}{\sqrt{3}}(log log n)^{3/2}} ≤ β\} ∼ Φ(α, β)x,

as x → ∞. Murty and Murty [14] prove general theorems applicable to a wider class of functions arising as Fourier coefficients of modular forms.

What distinguishes these theorems from the classical theory is their ‘nonabelian’ character. Indeed, latent in the Erdős-Kac theory is the intervention of the distribution of primes in cyclotomic fields, which are abelian extensions of the rational number field. In the case of Fourier coefficients arising from normalized Hecke eigenforms, one has the theory of l-adic representations (thanks to Deligne [1]) from which divisibility properties of the Fourier coefficients can be deduced via the Chebotarev density theorem. It is here that the generalized Riemann hypothesis intervenes, for in order to control the error terms in the expansions that arise, such a hypothesis is essential. In the classical case, the generalized Riemann hypothesis can be replaced by a direct application of the Bombieri-Vinogradov theorem (or as in the case of Erdős [3], the Siegel-Walfisz theorem combined with Brun’s sieve).

Our purpose here is to indicate yet another new type of the Erdős-Kac theorem formulated in a conjecture of Erdős and Pomerance [5]. Let a be a natural number greater than 1. For any n coprime to a, define f_{a}(n) to be the order of a (mod n). Erdős and Pomerance [5] conjectured that for any α < β,

# \{n ≤ x : (a, n) = 1, α ≤ \frac{ω(f_{a}(n)) − \frac{1}{2}(log log n)^{2}}{\frac{1}{\sqrt{3}}(log log n)^{3/2}} ≤ β\} ∼ Φ(α, β)\frac{ϕ(a)}{a}x,

as x → ∞, where ϕ(a) denotes the number of positive integers less than a and coprime to a. In this paper we prove this conjecture assuming a hypothesis substantially weaker than the generalized Riemann hypothesis. Again, certain non-abelian extensions of ℚ intervene in a natural way.

In the course of our investigations, we prove a variety of interesting results related to the study of f_{a}(n) and these we state in the next section. Most notable is THEOREM 6 which is unconditional.

2. STATEMENTS OF THEOREMS

Before stating the main results of the paper, we elucidate the precise nature of the generalized Riemann hypothesis, or quasi-Riemann hypothesis, invoked in THEOREMs 1 to 4.

In the study of f_{a}(p), or more generally, f_{a}(n), the non-abelian extensions

L_{q} = ℚ(ω_{q}, \sqrt[q]{a}),

where q is a prime and ω_{q} denotes a primitive q-th root of unity, intervene in a natural way. More precisely, if ζ_{q}(s) denotes the Dedekind zeta function of L_{q}, we assume that for some θ < 1, ζ_{q}(s) has no zeros in the region Re(s) > θ, for every prime q. This we refer to as a quasi-Riemann hypothesis. Of course, θ = 1/2 is the celebrated generalized Riemann hypothesis. In the last section of the paper, we discuss how we can weaken the assumption of a quasi-Riemann hypothesis.

Theorem 1. Let a ≥ 2 be squarefree. Assuming there is a θ < 1 such that every ζ_{q}(s) ≠ 0 in Re(s) > θ, for every prime q, we have

(5)  ∑_{{p≤x \atop (a,p)=1}}(ω(f_{a}(p)) − log log p)^{2} ≪ π(x) log log x.

REMARK: A quasi-GRH allows us to prove that the number of primes p ≤ x which split completely in L_{q} is

\frac{Li x}{qϕ(q)} + O(x^{θ} log qax), where Li x = ∫_{2}^{x} \frac{dt}{log t}.

If a were not squarefree, we expect an analogous result as THEOREM 1 to hold. However, the main term in the special case of the Chebotarev density theorem cited above will have to be slightly adjusted for those q that may divide the exponents of the prime powers in the unique factorization of a.

Theorem 2. Under the same hypotheses as in THEOREM 1, we have

(6) # \{p ≤ x : (a, p) = 1, α ≤ \frac{ω(f_{a}(p)) − log log p}{\sqrt{log log p}} ≤ β\} ∼ Φ(α, β)π(x),

as x → ∞.

We will deduce THEOREM 2 from the theorem (4) of Halberstam [6]. If we let i_{a}(p) denote the index of the subgroup generated by a (mod p) in 𝔽_{p}^{∗}, then

ω(p − 1) = ω(f_{a}(p)) + O(ω(i_{a}(p))).

A quasi-GRH is needed to ensure that for almost all p, ω(i_{a}(p)) is not as large as ω(p−1). The technical lemma we invoke to make the transition is of an independent interest in its own right.

THEOREM 2 can be proved directly without invoking the theorem of Halberstam by considering all the higher ‘moments’, as was done in the thesis [20]. We relegate this proof to a future paper [21].

Theorem 3. Under the same hypotheses as in THEOREM 1, we have

(7)  ∑_{{n≤x \atop (a,n)=1}} (ω(f_{a}(n)) − \frac{1}{2}(log log n)^{2})^{2} ≪ x(log log x)^{3}.

Theorem 4. Under the same hypotheses as in THEOREM 1,

(8) # \{n ≤ x : (a, n) = 1, α ≤ \frac{ω(f_{a}(n)) − \frac{1}{2}(log log n)^{2}}{\frac{1}{\sqrt{3}}(log log n)^{3/2}} ≤ β\}

∼ Φ(α, β)\frac{ϕ(a)}{a}x,

as x → ∞.

REMARK: This theorem establishes the conjecture of Erdős and Pomerance [5] assuming a quasi-GRH as defined in the remark following THEOREM 1.

By invoking a method of Kubilius and Shapiro we deduce the following. Let

A(x) = ∑_{{p≤x \atop (a,p)=1}} \frac{ω(f_{a}(p))}{p}, B(x) = ∑_{{p≤x \atop (a,p)=1}} \frac{ω^{2}(f_{a}(p))}{p}. (9)

Theorem 5. Without any hypothesis, we have

# \{n ≤ x : (a, n) = 1, α ≤ \frac{ω(f_{a}(n)) − A(x)}{\sqrt{B(x)}} ≤ β\} ∼ Φ(α, β)\frac{ϕ(a)}{a}x, (10)

as x → ∞.

Theorem 6. For any β > 0, as x → ∞,

# \{n ≤ x : (a, n) = 1, ω(f_{a}(n)) < \frac{1}{2}(log log n)^{2} + \frac{β}{\sqrt{3}}(log log n)^{3/2} \}

≳ Φ(−∞, β)\frac{ϕ(a)}{a}x. (11)

Even though THEOREM 5 is “well-known” or can be deduced from general theory, we isolate it here to show where the quasi-GRH enters in the proof of THEOREM 4. It is to determine the asymptotic behaviour of A(x) and B(x). Even a weak assertion such as

A(x) = \frac{1}{2}(log log x)^{2} + o((log log x)^{2})

would allow us to prove that ω(f_{a}(p)) has normal order log log p, without any hypotheses. But this seems to be beyond reach at the moment. The central assertion to be proved is

∑_{p≤x} \frac{ω(i_{a}(p))}{p} = o((log log x)^{2}).

3. TECHNICAL PREPARATION

What we will need in the proofs of the theorems stated in the previous section are two technical lemmas which are of independent interest.

Lemma 1. Let f, g and h be arithmetical functions, and suppose that for all n we have |f(n) − g(n)| ≤ h(n). Let us define

𝔄(x) = ∑_{p≤x} \frac{f(p)}{p} and 𝔅(x) = ∑_{p≤x} \frac{f^{2}(p)}{p}, (12)

and assume that the following condition is satisfied:

∑_{n≤x} h(n) = o(x\sqrt{𝔅(x)}). (13)

Suppose that for all constants α and β (with α ≤ β) we have:

# \{n ≤ x : α ≤ \frac{f(n) − 𝔄(x)}{\sqrt{𝔅(x)}} ≤ β\} ∼ x (\frac{1}{\sqrt{2π}} ∫_{α}^{β} e^{−t^{2}/2} dt) ,

as x → ∞, then also

# \{n ≤ x : α ≤ \frac{g(n) − 𝔄(x)}{\sqrt{𝔅(x)}} ≤ β\} ∼ x (\frac{1}{\sqrt{2π}} ∫_{α}^{β} e^{−t^{2}/2} dt) .

Proof. First, let us define the functions:

S_{f}(x; α, β) =^{def} # \{n ≤ x : α ≤ \frac{f(n) − 𝔄(x)}{\sqrt{𝔅(x)}} ≤ β\} , and (14)

S_{g}(x; α, β) =^{def} # \{n ≤ x : α ≤ \frac{g(n) − 𝔄(x)}{\sqrt{𝔅(x)}} ≤ β\} .

What we will prove is that if S_{f}(x; α, β) ∼ xΦ(α, β), then S_{g}(x; α, β) ∼ xΦ(α, β). Fix ϵ > 0. Then by the assumption, the number of n ≤ x, for which |h(n)| > ϵ\sqrt{𝔅(x)} is o(x). Hence for almost all n ≤ x, we may suppose that |h(n)| ≤ ϵ\sqrt{𝔅(x)}.

Now,

α ≤ \frac{f(n) − 𝔄(x)}{\sqrt{𝔅(x)}} ≤ β ⟹ 𝔄(x) + α\sqrt{𝔅(x)} ≤ f(n) ≤ 𝔄(x) + β\sqrt{𝔅(x)},

and g(n) − h(n) ≤ f(n) ≤ g(n) + h(n), together imply

g(n) − h(n) ≤ 𝔄(x) + β\sqrt{𝔅(x)} and g(n) + h(n) ≥ 𝔄(x) + α\sqrt{𝔅(x)}. Hence for almost all integers n ≤ x, we have:

g(n) ≤ 𝔄(x) + β\sqrt{𝔅(x)} + ϵ\sqrt{𝔅(x)} and g(n) ≥ 𝔄(x) + α\sqrt{𝔅(x)} − ϵ\sqrt{𝔅(x)}, and hence also: S_{f}(x; α, β) ≤ S_{g}(x; α − ϵ, β + ϵ) + o(x), or in other words: S_{g}(x; α, β) ≥ S_{f}(x; α + ϵ, β − ϵ) + o(x) ∼ (15)

∼ xΦ(α + ϵ, β − ϵ) + o(x),

by assumption (concerning the normality of the function f(n)), where we easily see that Φ(α + ϵ, β − ϵ) = Φ(α, β) + O(ϵ). Similarly, we can write:

α ≤ \frac{g(n) − 𝔄(x)}{\sqrt{𝔅(x)}} ≤ β ⟹ 𝔄(x) + α\sqrt{𝔅(x)} ≤ g(n) ≤ 𝔄(x) + β\sqrt{𝔅(x)} ⟹

⟹ f(n) − h(n) ≤ 𝔄(x) + β\sqrt{𝔅(x)} and f(n) + h(n) ≥ 𝔄(x) + α\sqrt{𝔅(x)}. and so, for almost all integers n ≤ x we have:

f(n) ≤ 𝔄(x) + β\sqrt{𝔅(x)} + ϵ\sqrt{𝔅(x)} and f(n) ≥ 𝔄(x) + α\sqrt{𝔅(x)} − ϵ\sqrt{𝔅(x)}. This proves that S_{g}(x; α, β) ≤ S_{f}(x; α − ϵ, β + ϵ) + o(x), or in other words: S_{g}(x; α, β) ≤ S_{f}(x; α − ϵ, β + ϵ) + o(x) ∼ (16)

∼ xΦ(α − ϵ, β + ϵ) + o(x),

and since again Φ(α − ϵ, β + ϵ) = Φ(α, β) + O(ϵ), the result follows.

Lemma 2. Suppose that 𝔓 ⊂ ℕ, i.e. 𝔓 is a subset of natural numbers, and let 𝔓(x) = |{n ∈ 𝔓, n ≤ x}|. Let f, g and h be arithmetical functions, and suppose that for all n we have |f(n) − g(n)| ≤ ch(n), where c > 0 is a constant. Define 𝔄(x) and 𝔅(x) as in (12), and assume that the following condition is satisfied:

∑_{n≤x} h(n) = o(𝔓(x)\sqrt{𝔅(x)}). (17)

Suppose that for all constants α and β (with α ≤ β) we have:

# \{n ≤ x, n ∈ 𝔓 : α ≤ \frac{f(n) − 𝔄(x)}{\sqrt{𝔅(x)}} ≤ β\} ∼ 𝔓(x) (\frac{1}{\sqrt{2π}} ∫_{α}^{β} e^{−t^{2}/2} dt) ,

as x → ∞, then also

# \{n ≤ x, n ∈ 𝔓 : α ≤ \frac{g(n) − 𝔄(x)}{\sqrt{𝔅(x)}} ≤ β\} ∼ 𝔓(x) (\frac{1}{\sqrt{2π}} ∫_{α}^{β} e^{−t^{2}/2} dt) .

Proof. The proof is similar to LEMMA 1, and we suppress it.

4. PROOF OF THEOREM 1

Let i_{a}(p) be the index in 𝔽_{p}^{∗} of the subgroup generated by a (mod p). It is easily seen that q|i_{a}(p) if and only if p splits completely in L_{q} (see [12]). Clearly, we have

ω(p − 1) − ω(i_{a}(p)) ≤ ω(f_{a}(p)) ≤ ω(p − 1).

By [14], we know that (see (3))

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

Recall that

ω(f_{a}(p)) − log log p = (ω(p − 1) − log log p) + O(ω(i_{a}(p))).

Squaring both sides and summing over all p ≤ x, we have

∑_{p≤x} (ω(f_{a}(p)) − log log p)^{2} ≪ ∑_{p≤x} (ω(p − 1) − log log p)^{2} + ∑_{p≤x} ω^{2}(i_{a}(p)).

An application of (3) shows that it suffices to prove:

∑_{p≤x} ω^{2}(i_{a}(p)) ≪ π(x) log log x,

in order to establish THEOREM 1. In fact, we will show that a quasi-GRH implies the stronger result:

∑_{p≤x} ω^{2}(i_{a}(p)) ≪ π(x). (18)

Indeed, defining

ω_{y}(n) = ∑_{{p|n \atop p<y}} 1,

we have for y = x^{δ}, δ < 1/4,

∑_{p≤x} ω^{2}(i_{a}(p)) ≪ ∑_{p≤x} ω_{y}^{2}(i_{a}(p)) + O(π(x)).

But

∑_{p≤x} ω_{y}^{2}(i_{a}(p)) = ∑_{{q_{1},q_{2}≤y^{2} \atop q_{1}≠q_{2}}} π(x, L_{q_{1}q_{2}}) + ∑_{q≤y} π(x, L_{q}),

where π(x, L_{k}) denotes the number of primes p ≤ x which split completely in L_{k}, because as was pointed out earlier, q|i_{a}(p) if and only if p splits completely in L_{q}.

A quasi-GRH (with no zeros of ζ_{q}(s) for Re(s) > θ) gives

π(x, L_{k}) = \frac{Li x}{kϕ(k)} + O(x^{θ} log kax). (19)

Hence, if we choose 2δ < θ, we obtain

∑_{p≤x} ω^{2}(i_{a}(p)) ≪ π(x),

which completes the proof of THEOREM 1. ■

COROLLARY 1: With the same hypotheses as THEOREM 1,

(20)  ∑_{p≤x} ω(f_{a}(p)) = π(x) log log x + O(π(x)), and

(21)  ∑_{p≤x} ω^{2}(f_{a}(p)) = π(x)(log log x)^{2} + O(π(x) log log x).

COROLLARY 2: With the same hypotheses as THEOREM 1,

(22)  ∑_{p≤x} Ω(f_{a}(p)) = π(x) log log x + O(π(x)), and

(23)  ∑_{p≤x} Ω^{2}(f_{a}(p)) = π(x)(log log x)^{2} + O(π(x) log log x).

By a partial summation, we deduce:

COROLLARY 3: Under the same hypotheses as THEOREM 1,

(24)  ∑_{p≤x} \frac{Ω(f_{a}(p))}{p} = \frac{1}{2}(log log x)^{2} + O(log log x), and

(25)  ∑_{p≤x} \frac{Ω^{2}(f_{a}(p))}{p} = \frac{1}{3}(log log x)^{3} + O((log log x)^{2}).

5. PROOF OF THEOREM 2

By the theorem (4) of Halberstam [6] we know that

\frac{ω(p − 1) − log log p}{\sqrt{log log p}}

obeys a normal distribution. Since ω(p − 1) = ω(f_{a}(p)) + O(ω(i_{a}(p))), we may apply LEMMA 2 of Section 3 to deduce that

\frac{ω(f_{a}(p)) − log log p}{\sqrt{log log p}}

has a normal distribution. This is because

∑_{p≤x} ω(i_{a}(p)) ≪ π(x) = o(π(x)\sqrt{log log x}),

so that the hypotheses of LEMMA 2 are satisfied. This completes the proof of

THEOREM 2. ■

6. TRANSITION FROM Ω(f_{a}(n)) TO ω(f_{a}(n))

It will be convenient to prove the analogs of THEOREMS 3 and 4 for Ω(f_{a}(n)), and then deduce the corresponding result for ω(f_{a}(n)). In this section we will indicate how this can be done, and then, in the next section, we establish THEOREM 3 for Ω(f_{a}(n)). The same strategy will be applied in our proof of THEOREM 4. It will be efficacious to extend the definition of f_{a}(n) when (a, n) ≠ 1, by setting f_{a}(1) = 1, and f_{a}(n) = f_{a}(n_{2}), where n = n_{1}n_{2}, with (n_{1}, n_{2}) = 1 and p|n_{1} ⟹ p|a.

For all 3 < y ≤ x, let us define the truncated functions

ω_{y}(f_{a}(n)) = ∑_{{p|f_{a}(n) \atop p<y}} 1, and Ω_{y}(f_{a}(n)) = ∑_{{p^{α}||f_{a}(n) \atop p^{α}<y}} α, (26)

and observe that ω(f_{a}(n)) ≤ Ω(f_{a}(n)). We will be using:

Lemma 3. For all x ≥ 2, and 2 ≤ k ≤ x,

(27)  ∑_{{p≤x \atop p≡1(mod k)}} \frac{1}{p} = \frac{log log x}{ϕ(k)} + O (\frac{log k}{k} ) .

Proof. This follows easily by partial summation and the Brun-Titchmarsh theorem (see Norton [16] or Pomerance [17] for a complete proof).

The following lemma will also be applied several times in the discussion below:

Lemma 4. If, for all x, we have

∑_{n≤x} (Ω(f_{a}(n)) − \frac{1}{2}(log log n)^{2})^{2} ≪ x(log log x)^{3}, then

(28)  ∑_{n≤x} (ω(f_{a}(n)) − \frac{1}{2}(log log n)^{2})^{2} ≪ x(log log x)^{3}.

Proof. Let ω_{y}^{+}(n) be the number of primes > y, dividing n. Similarly we define Ω_{y}^{+}(n). Then ω(n) = ω_{y}(n) + ω_{y}^{+}(n), so that if y = (log x)^{k}, for some constant k, then

∑_{n≤x} (ω_{y}^{+}(f_{a}(n)) − \frac{1}{2}(log log n)^{2} + ω_{y}(f_{a}(n)))^{2} ≪ (29)

≪ ∑_{n≤x} (ω_{y}^{+}(f_{a}(n)) − \frac{1}{2}(log log n)^{2})^{2} + ∑_{n≤x} ω_{y}(f_{a}(n))^{2}.

Similarly, the same thing can be said about Ω(f_{a}(n)). We have

(30)  ∑_{n≤x} (Ω_{y}^{+}(f_{a}(n)) − \frac{1}{2}(log log n)^{2} + Ω_{y}(f_{a}(n)))^{2} ≪

≪ ∑_{n≤x} (Ω_{y}^{+}(f_{a}(n)) − \frac{1}{2}(log log n)^{2})^{2} + ∑_{n≤x} Ω_{y}(f_{a}(n))^{2}.

Notice that

∑_{n≤x} ω_{y}(f_{a}(n))^{2} ≤ ∑_{n≤x} Ω_{y}(f_{a}(n))^{2} ≤ ∑_{n≤x} ( ∑_{{p|n \atop p≤y}} Ω(f_{a}(p)) + O(Ω_{y}(n)))^{2}
≪ ∑_{n≤x} \{( ∑_{{p|n \atop p≤y}} Ω(f_{a}(p)))^{2} + Ω_{y}(n)^{2}\}
≪ ∑_{p_{1}, p_{2}≤y} Ω(f_{a}(p_{1}))Ω(f_{a}(p_{2}))\frac{x}{p_{1}p_{2}} + O(x(log log y)^{2})
≪ x (∑_{p≤y} \frac{Ω(f_{a}(p))}{p})^{2} ≪ x(log log y)^{4},

by COROLLARY 3. Thus, with our choice of y it suffices to prove that

(31) ∑_{n≤x} (ω_{y}^{+}(f_{a}(n)) − \frac{1}{2}(log log n)^{2})^{2} ≪ x(log log x)^{3}.

Let us recall that f_{a}(n) = lcm{f_{a}(p^{α}) : p^{α}||n}, and f_{a}(p^{α}) divides p^{α−1}f_{a}(p), for all α. So if q^{2}|f_{a}(n), then either A) q|n, or B) q^{2}|f_{a}(p), for some p|n, or C) there exist two primes p_{1}, p_{2}, such that q|f_{a}(p_{1}), q|f_{a}(p_{2}), and p_{1}p_{2}|n. Also,

ω_{y}^{+}(f_{a}(n)) ≤ Ω_{y}^{+}(f_{a}(n)) ≤ ω_{y}^{+}(f_{a}(n)) + Ω(f_{a}(n))δ(n),

where δ(n) = 1, if ∃q^{2}|f_{a}(n), q > y, and δ(n) = 0 otherwise. We immediately have

Ω_{y}^{+}(f_{a}(n)) = ω_{y}^{+}(f_{a}(n)) + O(δ(n)Ω(f_{a}(n))),

so that

∑_{n≤x} (ω_{y}^{+}(f_{a}(n)) − \frac{1}{2}(log log n)^{2})^{2} ≪ ∑_{n≤x} (Ω_{y}^{+}(f_{a}(n)) − \frac{1}{2}(log log n)^{2})^{2}
+ ∑_{n≤x} δ(n)Ω(f_{a}(n))^{2}
≪ ∑_{n≤x} (Ω_{y}^{+}(f_{a}(n)) − \frac{1}{2}(log log n)^{2})^{2}
+ ∑_{A} + ∑_{B} + ∑_{C} ,

where the sums ∑_{A}, ∑_{B}, and ∑_{C} correspond to the cases A), B), C), respectively. But since Ω^{2}(f_{a}(n)) = O((log n)^{2}), we see that

∑_{A} ≪ ∑_{n≤x} Ω(n) ≪ x log log x,
∑_{B} = (log x)^{2} ∑_{{n≤x \atop n∈B}} δ(n) ≪ (log x)^{2} ∑_{q>y} ∑_{p≡1(mod q^{2})} \frac{x}{p} ≪ x log log x,

∑_{C} = (log x)^{2} ∑_{{n≤x \atop n∈C}} δ(n) ≪ (log x)^{2} ∑_{q>y} ∑_{{p_{1}≡1(mod q) \atop p_{2}≡1(mod q)}} \frac{x}{p_{1}p_{2}} ≪ x(log log x)^{2},

if we choose y = (log x)^{2}, for example. Here we have used LEMMA 3 in estimation of the sums ∑_{B} and ∑_{C}. This finishes the proof of (31).

7. PROOF OF THEOREM 3

By the previous section, it suffices to prove THEOREM 3 with ω(f_{a}(n)) replaced by Ω(f_{a}(n)). Evidently

∑_{p|n} Ω(f_{a}(p)) ≤ Ω(f_{a}(n)) ≤ ∑_{p|n} Ω(f_{a}(p)) + Ω(n). (32)

Therefore

∑_{{n≤x \atop (a,n)=1}} Ω(f_{a}(n)) = ∑_{{n≤x \atop (a,n)=1}} (∑_{p|n} Ω(f_{a}(p))) + O (∑_{n≤x} Ω(n)) . (33)

Now, the condition (a, n) = 1 can be removed, if we insert the expression

∑_{d|n,a} μ(d),

where μ is the Möbius function, into our expression above. Thus

∑_{d|a} μ(d) ∑_{p≤x} Ω(f_{a}(p)) ∑_{n≤x ; {d|n \atop p|n}} 1 = ∑_{d|a} μ(d) ∑_{{p≤x \atop (a,p)=1}} Ω(f_{a}(p)) [\frac{x}{pd}]

= \frac{ϕ(a)}{2a}x(log log x)^{2} + O(x log log x),

by COROLLARY 3. Hence

(34)  ∑_{{n≤x \atop (a,n)=1}} Ω(f_{a}(n)) = \frac{ϕ(a)}{2a}x(log log x)^{2} + O(x log log x).

Similarly, it is possible to prove the second moment estimate along the same lines,

(35)  ∑_{{n≤x \atop (a,n)=1}} Ω^{2}(f_{a}(n)) = \frac{ϕ(a)}{4a}x(log log x)^{4} + O(x(log log x)^{3}).

Putting together the estimates (34) and (35) gives us our THEOREM 3.

8. PROOF OF THEOREM 4

The function

F (n) = ∑_{p|n} Ω(f_{a}(p))

is evidently strongly additive (that is, F satisfies the conditions: F (mn) = F (m) + F (n) for (m, n) = 1, and F (p^{α}) = F (p) for all α). Recall the extended definition of f_{a}(n), when gcd(a, n) ≠ 1. For all n ∈ ℕ, we write n = n_{1}n_{2}, where p|n_{1} ⟹ p|a, and (n_{1}, n_{2}) = 1, and we set f_{a}(n) = f_{a}(n_{2}), and f_{a}(1) = 1. We will work with this extended function first

We recall the theorem of Kubilius and Shapiro for strongly additive functions: Let f be strongly additive, and 𝔄(x) and 𝔅(x) defined as in (12). If we suppose that for every fixed ϵ > 0, as x → ∞, we have

∑_{{p≤x \atop |f(p)|>ϵ𝔅(x)^{1/2}}} \frac{f^{2}(p)}{p} = o(𝔅(x)), (36)

then for any real constant γ,

lim_{x→∞} \frac{# \{n : n ≤ x, \frac{f(n)−𝔄(x)}{𝔅(x)^{1/2}} ≤ γ\}}{x} = \frac{1}{\sqrt{2π}} ∫_{−∞}^{γ} e^{−t^{2}/2} dt,

or equivalently, for any real constants α and β, with α < β:

lim_{x→∞} \frac{# \{n : n ≤ x, α < \frac{f(n)−𝔄(x)}{𝔅(x)^{1/2}} ≤ β\}}{x} = \frac{1}{\sqrt{2π}} ∫_{α}^{β} e^{−t^{2}/2} dt. (37)

Now we can apply the Kubilius-Shapiro theorem to F (n), as long as the condition (36) is satisfied. But note that for a prime q, one has F (q) = Ω(f_{a}(q)), and hence we can write:

∑_{{q≤x \atop |F (q)|>ϵ\sqrt{𝔅(x)}}} \frac{F^{2}(q)}{q} = ∑_{{q≤x \atop |F (q)|>ϵ\sqrt{𝔅(x)}}} \frac{Ω^{2}(f_{a}(q))}{q} < (38)

< ∑_{{q≤x \atop Ω(q−1)>ϵ\sqrt{𝔅(x)}}} \frac{Ω^{2}(f_{a}(q))}{q} < ∑_{{q≤x \atop Ω(q−1)>ϵ\sqrt{𝔅(x)}}} \frac{Ω^{2}(q − 1)}{q} = o(𝔅(x)),

the last inequality coming from a computation done by Erdős & Pomerance (see [5], p. 348). But Ω(f_{a}(n)) = ∑_{p|n} Ω(f_{a}(p)) + O(Ω(n)), so that we can apply LEMMA 1 to deduce the following result:

THEOREM 4′: With the extended definition of f_{a}(n), under the assumption of a quasi-GRH, for all x > 0 we have

lim_{x→∞} \frac{H_{a}(x, α, β)}{x} = \frac{1}{\sqrt{2π}} ∫_{α}^{β} e^{−t^{2}/2} dt, (39)

NON-ABELIAN ERDŐS-KAC 13

where H_{a}(x, α, β) is defined as

H_{a}(x, α, β) =^{def} # \{n ≤ x : α ≤ \frac{Ω(f_{a}(n)) − \frac{1}{2}(log log n)^{2}}{\frac{1}{\sqrt{3}}(log log n)^{3/2}} ≤ β\} .

Now it is easy to prove THEOREM 4, after introducing the condition (a, n) = 1 in our enumeration. Let

S = \{n ≤ x : α ≤ \frac{Ω(f_{a}(n)) − 𝔄(x)}{\sqrt{𝔅(x)}} ≤ β\} , (40)

with 𝔄(x) and 𝔅(x) defined as in (12), and S(x) the cardinality of S. Evidently

S(x) ∼ x · Φ(α, β),

and since

∑_{{n∈S \atop (a,n)=1}} 1 = ∑_{n∈S} ∑_{{d|a \atop d|n}} 1 = ∑_{d|a} μ(d) ∑_{{n∈S \atop d|n}} 1 ,

we want to count the number of elements S_{d}(x) in S_{d}, where

S_{d} = \{n ≤ x : d|n, α ≤ \frac{Ω(f_{a}(n)) − 𝔄(x)}{\sqrt{𝔅(x)}} ≤ β\} , (41)

because then the quantity in THEOREM 4 is simply

∑_{d|a} μ(d)S_{d}(x). (42)

Writing n = dm, we see that

Ω(f_{a}(m)) ≤ Ω(f_{a}(n)) ≤ Ω(f_{a}(m)) + Ω(f_{a}(d)),

and since d|a, and a is fixed, d itself is less than a constant, giving us

Ω(f_{a}(n)) = Ω(f_{a}(m)) + O(1).

Therefore

S_{d}(x) = # \{m ≤ \frac{x}{d} : α ≤ \frac{Ω(f_{a}(n)) − 𝔄(x)}{\sqrt{𝔅(x)}} ≤ β\} ∼ \frac{x}{d} · Φ(α, β). (43)

This completes the proof of THEOREM 4. ■

9. PROOFS OF THEOREMS 5 AND 6

The analysis of §8 clearly shows that a couple of important unconditional theorems could be deduced. As stated earlier, we want to isolate for later clinical study the precise role of the GRH. By invoking Lemma 1, we can deduce THEOREMS 5 and 6 from the following. We have

THEOREM 5′: For all constants α and β (with α ≤ β), as x → ∞,

# \{n ≤ x : gcd(a, n) = 1, α ≤ \frac{Ω(f_{a}(n)) − A_{1}(x)}{\sqrt{B_{1}(x)}} ≤ β\} ∼ x · \frac{ϕ(a)}{a} · Φ(α, β),

where

A_{1}(x) = ∑_{p≤x} \frac{Ω(f_{a}(p))}{p} and B_{1}(x) = ∑_{p≤x} \frac{Ω^{2}(f_{a}(p))}{p}.

But in order to accurately estimate the behaviour of A_{1}(x) and B_{1}(x) one needs to assume a certain GRH.

However, utilizing trivial upper bounds (i.e. replacing f_{a}(p) by p−1, and using unconditional results known for p − 1) on the size of A_{1}(x) and B_{1}(x), we have the following useful unconditional theorem:

THEOREM 6′: For any constant α > 0, as x → ∞,

# \{n ≤ x : gcd(a, n) = 1, Ω(f_{a}(n)) < \frac{1}{2}(log log n)^{2} + \frac{α}{\sqrt{3}}(log log x)^{3/2}\}

≳ x · \frac{ϕ(a)}{a} · (\frac{1}{\sqrt{2π}} ∫_{−∞}^{α} e^{−t^{2}/2} dt) .

10. CONCLUDING REMARKS

It would be desirable if one could remove the assumption of a GRH from our results. However, at this point in time, that doesn’t seem to be very realistic, mainly because we are lacking any kind of “mean value” theorems that could serve as replacements of the Bombieri-Vinogradov and the Brun-Titchmarsh theorems in the non-abelian situations. Until one can establish some versions of these theorems (at least in some special cases, or smaller ranges), all we can hope for is to weaken the hypotheses we are using.

As it was already noted, the full strength of the Generalized Riemann Hypothesis is not necessary. In fact, a quasi-GRH is always sufficient. Namely, it is enough to assume that there exists a constant δ > 0, such that:

π(x, L_{q}(a)) = \frac{π(x)}{q(q − 1)} + O(x^{1−δ}). (44)

More generally, for any square-free k ≥ 2, all we need to do is to assume the Chebotarev’s Density Theorem with the following error term:

π(x, L_{k}(a)) = \frac{π(x)}{kϕ(k)} + O(x^{1−δ}), (45)

for some δ > 0. Currently, the best unconditional error version of (42) is still due to Lagarias & Odlyzko [9] from 1977. They proved that there is a constant A > 0 such that

π(x, L_{k}(a)) = \frac{π(x)}{kϕ(k)} + O (x exp (−A\sqrt{\frac{log x}{kϕ(k)}} )) . (46)

An unconditional result of this kind is good enough to deduce asymptotic behaviour of the sum

∑_{p≤x} ω_{y}(f_{a}(p))

for y < (log x)^{1/2−ϵ}. One can extend the range to y < (log x)^{1−ϵ} with some work. But it seems to be beyond reach at the present moment to push this to y = exp(\frac{c log x}{log log x}), for some constant c > 0. Such a result would enable us to deduce all of the theorems in this paper unconditionally. Acknowledgments. We thank the referee for several useful remarks.

References

[1] Deligne, P. - Formes modulaires et représentations l-adiques, Sem. Bourbaki 355, Lecture Notes in Math. 179, 139-172, Springer Verlag, 1971

[2] Elliott, P. D. T. A. - Probabilistic Number Theory, Volume I. & II., Springer Verlag, 1979 [3] Erdős, P. - On the normal order of prime factors of p − 1 and some related problems

concerning Euler’s ϕ-function, Quart. Journ. Math. (Oxford), 6,205 - 213, 1935

[4] Erdős, P. & Kac, M. - The Gaussian law of errors in the theory of additive number theoretic functions. Amer. J. Math. 62, 738-742, 1940

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

[6] Halberstam, H. - On the distribution of additive number-theoretic functions (I., II. & III.), J. London Math. Soc., 30, 43-53, 1955, and 31, 1-14, and 31, 15-27, 1956

[7] Hardy, G. H. & Ramanujan, S. - The normal number of prime factors of a number n, Quart. J. Pure Appl. Math., 48, 76-97, 1917

[8] Kubilius, J. - Probabilistic methods in number theory, Translations of Math. Monographs (No.11), Rhode Island, 1964

[9] Lagarias, J. & Odlyzko, A. - Effective versions of the Tchebotarev density theorem, in “Algebraic Number Fields” (A. Fröhlich ed.), Proceedings of the 1975 Durham Symposium, Academic Press, 1975

[10] Lehmer, D. H. - Ramanujan’s function τ(n), Duke Math. J., 10, 483-492, 1943

[11] Lehmer, D. H. - The vanishing of Ramanujan’s function τ(n), Duke Math. J., 14, 429-433, 1947

[12] Murty, R. - On Artin’s conjecture, J. Number Theory, 16, 147-168, 1983

[13] Murty, R. - Problems in Analytic Number Theory, Springer Verlag, Vol. 206, New York, [14] Murty, K. V. & Murty, R. M. - Prime divisors of Fourier coefficients of modular forms,

Duke Math. J., 51, 57-76, 1984

[15] Murty, K. & Murty, R. - An analogue of the Erdős-Kac theorem for Fourier coefficients of modular forms, Indian J. Pure & App. Math., 15, 1090-1101, 1984

[16] Norton, K. K. - On the number of restricted prime factors of an integer (I.), Illinois J. Math., 20, 681-705, 1976

[17] Pomerance, C. - On the distribution of amicable numbers, J. reine angew. Math., 293/294, 217-222, 1977

[18] Ramanujan, S. - Highly composite numbers, Proc. London Math. Soc. (2), 14, 347-409, 1915 (see also Collected Works, Oxford, 1927)

[19] Saidak, F. - An elementary proof of a theorem of Délange, submitted to the Mathematical Reports of the Royal Society of Canada.

[20] Saidak, F. - Non-Abelian Generalizations of the Erdős-Kac Theorem, Ph.D. Thesis, Queen’s University, Kingston, 2001

[21] Saidak, F. - Erdős-Kac type theorems for ω(f_{a}(p)) and Ω(f_{a}(p)) via higher moments, submitted to Acta Math. Univ. Com.

[22] Shapiro, H. - Distribution functions of additive arithmetic functions, Proc. Nat. Acad. Sci. U.S.A., 42, 426-430, 1956

[23] Turán, P. - On a theorem of Hardy and Ramanujan, J. London Math. Soc., 9, 274-276, 1934

Department of Mathematics, Queen’s University, Kingston, Ontario, K7L 3N6.

    E-mail address: murty@mast.queensu.ca, and filips@math.ucalgary.ca