On a conjecture of M. R. Murty and V. K. Murty

Abstract

Let $\omega ^*(n)$ be the number of primes p such that $p-1$ divides n. Recently, M. R. Murty and V. K. Murty proved that

$$ \begin{align*}x(\log\log x)^3\ll\sum_{n\le x}\omega^*(n)^2\ll x\log x.\end{align*} $$

They further 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 short note, we give the correct order of the sum by showing that

$$ \begin{align*}\sum_{n\le x}\omega^*(n)^2\asymp x\log x.\end{align*} $$

Let $\omega (n)$ be the number of distinct prime divisors of n. In about 100 years ago, Hardy and Ramanujan [3] 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 [6] 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 [5] 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 [2] 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 [4] 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 [4, equation (4.10)], we have

(1) $$ \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

(2) $$ \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

(3) $$ \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, [1]), 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

(4) $$ \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

(5) $$ \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 [4, 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*} $$