SOME RESULTS IN NUMBER THEORY, I

M. RAM MURTY (CAMBRIDGE, MASS.) AND V. KUMAR MURTY (OTTAWA, ONT.)

Dedicated to the memory of Professor Paul Turán

Let φ(n) denote Euler’s totient function and V (n) the number of distinct prime factors of n. In this paper, we shall study the quantity V ((n, φ(n))) which arises naturally in group theory. For example, letting G(n) denote the number of nonisomorphic groups of order n, we have by a classical result of Burnside that G(n) = 1 if and only if V (n, φ(n)) = 0 (i.e. (n, φ(n)) = 1.) Erdös [1] showed that the number F_{1}(x) of n ≤ x satisfying the latter condition is

F_{1}(x) = (1 + o(1))xe^{−γ}/ log_{3} x  (1)

where γ is Euler’s constant and we write log_{1} x = log x, log_{a} x = log(log_{a−1} x). More generally, we can define F_{k}(x) to be the number of n ≤ x for which G(n) = k. The authors [2] have shown that for each k,

F_{k}(x) ≪ x/ log_{4} x.

The proof depended essentially on a weak form of the following result stated by Erdös in [1]: for each ε > 0, the number of n ≤ x that fail to satisfy

(1 − ε) log_{4} n < V (n, φ(n)) < (1 + ε) log_{4} n

is o(x). (A proof of this was supplied by the authors in [2].)

It is an interesting number-theoretic problem to estimate the number A_{k}(x) of n ≤ x for which V (n, φ(n)) = k. Our main result here is the following theorem.

Theorem 1. For each k ≥ 0, we have

A_{k}(x) = \frac{(1 + o(1))xe^{−γ}(log_{4} x)^{k}}{k! log_{3} x} .  (2)

The proof will require several lemmas and intermediate results. The first two lemmas are due to Erdös [1].

Lemma 1. Let p be a fixed prime. Then

\begin{matrix}∑ & ∗ \\ s≤x \end{matrix} \frac{1}{s} ≪ \frac{1}{p}(log p + log_{2} x),

where the asterisk indicates that the sum is over primes s ≤ x, s ≡ 1 (mod p).

We remark here that unless otherwise stated, p, q, and s will denote primes.

Lemma 2. Let p < (log_{2} x)^{1−ε}. Then the number of pm ≤ x such that m has no prime divisor ≡ 1 (mod p) is o(x/(log_{2} x)^{2}), uniformly in p.

2 M. RAM MURTY (CAMBRIDGE, MASS.) AND V. KUMAR MURTY (OTTAWA, ONT.)

Lemma 3. Let H_{k}(x) be the number of n ≤ x of the form n = p_{1}p_{2} ⋯ p_{k}m, where (i) p_{i} < (log_{2} x)^{1−ε}, i = 1, 2, …, k, (ii) all the prime divisors of m are ≫ (log_{2} x)^{1+ε}, (iii) (m, φ(m)) = 1. Then for each fixed k,

Received on 31. 12. 1976.

H_{k}(x) = \frac{(1 + o(1))xe^{−γ}(log_{4} x)^{k}}{k! log_{3} x} .

Proof. By definition,

H_{k}(x) = ∑_{p} \begin{matrix}∑ & ′ \\ m \end{matrix} 1  (3)

where the outer sum is over all p_{i} < (log_{2} x)^{1−ε} (1 ≤ i ≤ k) and the inner sum is over m ≤ x/p_{1} ⋯ p_{k} satisfying (ii) and (iii). Erdös’ proof of (1) shows that

\begin{matrix}∑ & ′ \\ m \end{matrix} 1 = \frac{(1 + o(1))xe^{−γ}}{(p_{1}p_{2} ⋯ p_{k}) log_{3} x}  (4)

and as the product p_{1} ⋯ p_{k} is obtained k! times in the k-fold outer sum of (3), we get

H_{k}(x) = \frac{(1 + o(1))xe^{−γ}}{k! log_{3} x} (∑_{p} \frac{1}{p})^{k} = \frac{(1 + o(1))xe^{−γ}(log_{4} x)^{k}}{k! log_{3} x}

proving the lemma.

We are now ready to prove our theorem.

Proof. We shall give the proof for k = 1 and then sketch the modifications needed for general k. Write

A_{1}(x) = A1^{′}(x) + A1^{′′}(x)  (5)

where A1^{′}(x) counts the contribution of squarefree n to A_{1}(x) and A1^{′′}(x) counts the remaining n. First we estimate A1^{′′}(x). If n is not squarefree and V (n, φ(n)) = 1 then certainly n = p^{a}m (a ≥ 2) with (p, m) = 1 and (m, φ(m)) = 1. The number of such n ≤ x with p > log_{2} x = y (say) is clearly

≪ ∑_{p>y} ∑_{a≥2} \frac{x}{p^{a}} ≪ \frac{x}{y},

and the number of remaining non-squarefree n in A_{1}(x) is

≪ ∑_{p≤y} ∑_{a≥2} A_{0} (\frac{x}{p^{a}} ) ≪ \frac{x}{log_{3} x}

using (1). Thus, we have

A1^{′′}(x) ≪ x/ log_{3} x.  (6)

If n is squarefree, then V (n, φ(n)) = 1 implies that

n = pm, (m, φ(m)) = 1 and m has at least one prime divisor q ≡ 1 (mod p) (7)

Let ε > 0 be fixed. Then, we write

A1^{′}(x) = ∑_{1} + ∑_{2} + ∑_{3} + ∑_{4}

where the sums are over those n ≤ x in A1^{′}(x) of the form (7) and in ∑_{1}, p > (log_{2} x)^{1+ε} in ∑_{2}, (log_{2} x)^{1−ε} ≤ p ≤ (log_{2} x)^{1+ε}, in ∑_{3}, p < (log_{2} x)^{1−ε} and at least one prime divisor of m is < (log_{2} x)^{1−ε}, in ∑_{4}, p < (log_{2} x)^{1−ε} and all the prime divisors of m are > (log_{2} x)^{1−ε}.

Clearly, we have by Lemma 1,

∑1 ≪ ∑_{p} \begin{matrix}∑ & ∗ \\ q<x \end{matrix} \frac{x}{pq} ≪ ∑_{p} \frac{x}{p^{2}} (log p + log_{2} x)  (8)
≪ \frac{x}{(log_{2} x)^{1+ε}} (log_{3} x + log_{2} x) = o(x log_{4} x/ log_{3} x).

Also, we get from (1) that

∑2 ≪ ∑ A_{0} (\frac{x}{p}) ≪ ∑ \frac{x}{p log_{3}(x/p)} ≪ x/ log_{3} x,  (9)

where all the sums are over p in the range indicated for ∑_{2}. Now from Lemma 2, the number of m ≤ x, (m, φ(m)) = 1 which have a prime divisor < (log_{2} x)^{1−ε} is

o(x/(log_{2} x)^{2})(log_{2} x)^{1−ε} = o(x/ log_{2} x).

Hence,

∑3 = o (\frac{x}{log_{2} x} ∑ \frac{1}{p}) = o (\frac{x log_{4} x}{log_{2} x})  (10)

where the sum is over p < (log_{2} x)^{1−ε}. For ∑_{4}, we write

∑4 = ∑4^{′} + ∑4^{′′}  (11)

where in the first sum, all the prime divisors of m are > (log_{2} x)^{1+ε}, and the second sum contains the remaining n of ∑_{4}. Thus, for the n in ∑4^{′′}, there is a prime divisor q (say) with

(log_{2} x)^{1−ε} = q = (log_{2} x)^{1+ε}  (12)

so

∑4^{′′} ≪ ∑_{p} ∑_{q} A_{0}(x/pq) ≪ \frac{x}{log_{3} x} ∑_{p,q} \frac{1}{pq}

where the sum over q is in the range (12) and the sum over p is in the range specified for ∑_{4}. The sum over q is clearly < ε so we get

∑4^{′′} < εx log_{4} x/ log_{3} x.  (13)

Finally, recalling the definition of H_{1}(x) from Lemma 3, noting that our n are now squarefree, and that in the range of ∑_{4} every number in (7) satisfies V (n, φ(n)) = 1, we get

H_{1}(x) ≥ ∑4^{′} ≥ H_{1}(x) − T (x)

where T (x) is the number of pm = n ≤ x such that m has no prime divisor ≡ 1 (mod p) and p is in the range specified for ∑_{4}. Lemmas 2 and 3 imply that

∑4^{′} = \frac{(1 + o(1))xe^{−γ} log_{4} x}{log_{3} x}  (14)

so that combining (5), (6), (8)–(11), (13) and (14), and noting that ε > 0 was arbitrary, the proof for k = 1 is completed.

Now we sketch the modifications needed in the above proof, for general k. As before, we write A_{k}(x) = Ak^{′}(x) + Ak^{′′} using the notation as in (5). Recalling y = log_{2} x, we get

Ak^{′′}(x) ≪ ∑_{p≤y} ∑_{a≥2} A_{k−1} (\frac{x}{p^{a}} ) + \frac{x}{y} ≪ \frac{x(log_{4} x)^{k−1}}{log_{3} x}  (15)

by induction. To estimate Ak^{′}(x), we write the n ≤ x that are counted, in the form

n = p_{1} ⋯ p_{k}m, (m, φ(m)) = 1 and (n, φ(n)) = p_{1} ⋯ p_{k}.  (16)

Then as before,

Ak^{′}(x) = _{∑1} +_{∑2} +_{∑3} +_{∑4}

where now, the sums are over those n ≤ x of the form (16) and

in ∑_{1} some p_{i} > (log_{2} x)^{1+ε},

in ∑_{2} some p_{i} satisfies (log_{2} x)^{1−ε} < p_{i} < (log_{2} x)^{1+ε},

in ∑_{3} all p_{i} < (log_{2} x)^{1−ε} and at least one prime divisor of m is < (log_{2} x)^{1−ε}, in ∑_{4} all p_{i} < (log_{2} x)^{1−ε} and all the prime divisors of m are > (log_{2} x)^{1−ε}.

For ∑_{1}, the estimate (8) holds as before, and also

∑2 ≪ x/ log_{3} x, _{∑3} = o(x(log_{4} x)^{k}/ log_{3} x),  (17)

by simple modifications in (9) and (10). Finally, writing ∑_{4} = ∑4^{′} + ∑4^{′′} in the same notation as in (11), we find again by a simple modification that

∑4^{′′} = o(x(log_{4} x)^{k}/ log_{3} x)  (18)

and

H_{k}(x) ≥ ∑4^{′} ≥ H_{k}(x) − ∑_{j=0}^{k−1} A_{j}(x)  (19)

as clearly all n counted by H_{k}(x) satisfy V (n, φ(n)) ≤ k. By induction,

∑_{j=0}^{k−1} A_{j}(x) ≪ x(log_{4} x)^{k−1}/ log_{3} x,

so that by Lemma 3, we get from (19) that

∑4^{′} = \frac{(1 + o(1))xe^{−γ}(log_{4} x)^{k}}{k! log_{3} x}  (20)

and combining (15), (8), (17), (18) and (20), the proof of the theorem is complete.

Acknowledgement. We would like to thank Professor K. S. Williams for his helpful comments.

References

[1] P. Erdös, Some asymptotic formulas in number theory, J. Indian Math. Soc. 12 (1948), pp. 75–78.

[2] M. Ram Murty and V. Kumar Murty, The number of groups of a given order, to appear.

M.I.T., Cambridge, Massachusetts, U.S.A, and Carleton University, Ottawa, Ontario, Canada