Let
$\omega (n)$
be the number of distinct prime divisors of n. In about 100 years ago, Hardy and Ramanujan [Reference Hardy and Ramanujan3] found out that
$\omega (n)$
has normal order
$\log \log n$
, which means that for almost all integers n we have
$\omega (n)\sim \log \log n$
. Later, Turán [Reference Turán6] provided a quite elegantly simplified proof by establishing
$$ \begin{align*}\sum_{n\le x}(\omega(n)-\log\log n)^2\ll x\log\log x.\end{align*} $$
In 1955, Prachar [Reference Prachar5] considered a variant arithmetic function of
$\omega $
. Let
$\omega ^*(n)$
be the number of primes p such that
$p-1$
divides n. Prachar proved that
$$ \begin{align*}\sum_{n\le x}\omega^*(n)=x\log\log x+Bx+O(x/\log x)\end{align*} $$
and
$$ \begin{align*}\sum_{n\le x}\omega^*(n)^2=O\left(x(\log x)^2\right),\end{align*} $$
where B is a constant. Motivated by Prachar’s work, Erdős and Prachar [Reference Erdős and Prachar2] proved that the number of pairs of primes p and q so that the least common multiple
$[p-1, q-1]\le x$
is bounded by
$O(x\log \log x)$
. Following a remark of Erdős and Prachar, M. R. Murty and V. K. Murty [Reference Murty and Murty4] improved this to
$O(x)$
. By this improvement, they reached the nice bounds
$$ \begin{align*}x(\log\log x)^3\ll\sum_{n\le x}\omega^*(n)^2\ll x\log x.\end{align*} $$
With these in hands, M. R. Murty and V. K. Murty conjectured that there is some positive constant C such that
$$ \begin{align*}\sum_{n\le x}\omega^*(n)^2\sim Cx\log x,\end{align*} $$
as
$x\rightarrow \infty $
. In this note, the author shall give a slight improvement of the result due to M. R. Murty and V. K. Murty toward the correct direction of their conjecture.
Theorem 1 There are two absolute constants
$a_1$
and
$a_2$
such that
$$ \begin{align*}a_1x\log x\le \sum_{n\le x}\omega^*(n)^2\le a_2x\log x.\end{align*} $$
Proof We only need to prove the lower bound as the upper bound is displayed by M. R. Murty and V. K. Murty. Throughout our proof, the number x is sufficiently large. From the paper of M. R. Murty and V. K. Murty [Reference Murty and Murty4, equation (4.10)], we have
$$ \begin{align} \sum_{n\le x}\omega^*(n)^2=x\sum_{d\le x}\varphi(d)\left(\sum_{\substack{p\le x\\p\equiv 1 {\ (\mathrm{{mod}}\ d)}}} \frac{1}{p-1}\right)^2+O(x). \end{align} $$
Integrating by parts gives
$$ \begin{align} \sum_{\substack{p\le x\\p\equiv 1 {\ (\mathrm{{mod}}\ d)}}} \frac{1}{p}=\frac{\pi(x;d,1)}{x}+\int_{2}^{x}\frac{\pi(t;d,1)}{t^2}dt\ge \int_{x^{3/4}}^{x}\frac{\pi(t;d,1)}{t^2}dt, \end{align} $$
where
$\pi (t;d,1)$
is the number of primes
$p\equiv 1 {\ (\mathrm {{mod}}\ d)}$
up to t. Thus, from equations (1) and (2), we obtain
$$ \begin{align} \sum_{n\le x}\omega^*(n)^2\ge x\sum_{d\le x^{1/3}}\varphi(d)\left(\int_{x^{3/4}}^{x}\frac{\pi(t;d,1)}{t^2}dt\right)^2+O(x). \end{align} $$
For any integer
$0\le j\le \left \lfloor \frac {\log x}{13\log 2}\right \rfloor $
, let
$Q_j=2^jx^{1/4}$
. Then
$Q_j<x^{1/3}$
for all integers j. From a weak form of the Bombieri–Vinogradov theorem (see, for example, [Reference Davenport1]), we have
$$ \begin{align*} \sum_{Q_j<d\le 2Q_j}\max_{y\le z}\left|\pi(y;d,1)-\frac{\text{li}~y}{\varphi(d)}\right|\ll \frac{z}{(\log z)^5}, \end{align*} $$
for any
$0\le j\le \left \lfloor \frac {\log x}{13\log 2}\right \rfloor $
and
$x^{3/4}\le z\le x$
, where the implied constant is absolute. It follows immediately that
$$ \begin{align} \max_{y\le z}\left|\pi(y;d,1)-\frac{\text{li}~y}{\varphi(d)}\right|<\frac{\text{li}~z}{\varphi(d)\log z} \end{align} $$
hold for all
$Q_j<d\le 2Q_j$
but at most
$O\left (Q_j/(\log x)^2\right )$
exceptions. From equation (4), we have
$$ \begin{align*} \pi(y;d,1)>\frac{\text{li}~y}{2\varphi(d)} \quad \left(z/2<y\le z\right) \end{align*} $$
for all
$Q_j<d\le 2Q_j$
with at most
$O\left (Q_j/(\log x)^2\right )$
exceptions. A little thought with the dichotomy of z between the interval
$[x^{3/4},x]$
leads to the fact
$$ \begin{align} \pi(y;d,1)>\frac{\text{li}~y}{2\varphi(d)}> \frac{y}{3\varphi(d)\log y} \quad \left(\forall~ x^{3/4}\le y\le x\right) \end{align} $$
for all
$Q_j<d\le 2Q_j$
except for
$O\left (Q_j/\log x\right )$
exceptions. For any integer
$0\le j\le \left \lfloor \frac {\log x}{13\log 2}\right \rfloor $
, let
$S_j$
be the set of all integers
$Q_j<d\le 2Q_j$
such that equation (5) holds. Thus, from the analysis above and equations (3) and (5), we conclude that
$$ \begin{align*} \sum_{n\le x}\omega^*(n)^2&\ge \frac{x}{9}\sum_{0\le j\le \left\lfloor \frac{\log x}{13\log 2}\right\rfloor}\sum_{\substack{d\in S_j}}\varphi(d)\left(\int_{x^{3/4}}^{x}\frac{1}{\varphi(d)t\log t}dt\right)^2+O(x)\nonumber\\ &\gg x\sum_{0\le j\le \left\lfloor \frac{\log x}{13\log 2}\right\rfloor}\sum_{\substack{d\in S_j}}\frac1{\varphi(d)}+x\gg x\log x.\\[-36pt] \end{align*} $$
It is worth here mentioning that we have the following corollary:
$$ \begin{align*}\sum_{p,q\le x}\frac{1}{[p-1,q-1]}\asymp \log x\end{align*} $$
due to (see [Reference Murty and Murty4, p. 6, last line])
$$ \begin{align*}\sum_{n\le x}\omega^*(n)^2=\sum_{p,q\le x}\frac{x}{[p-1,q-1]}+O(x).\end{align*} $$
