I'm working through Murty's "An Introduction to Sieve Methods and their Applications" and I've come across the Turan's Theorem and Corollary, showing the normal order of $v(n)$, where $v(n)$ is the number of distinct prime factors (I've also seen that $\omega(n)$ is a more common notation for this function, but I'll stick with Murty's definition here). Here are the statements:

Turan's Theorem: $\sum_{n\le x}(v(n)-\log\log x)^2 = O(x\log\log x)$

Corollary: Let $\delta>0$. The number of $n\le x$ that do not satisfy the inequality $$|v(n)-\log\log x| < (\log\log x)^{\frac{1}{2}+\delta}$$ is $o(x)$.

Proof of Corollary: If $n\le x$ doesn't satisfy the inequality, then a summand coming from $n$ satisfies $$|v(n)-\log\log x|\ge(\log\log x)^{\frac{1}{2}+\delta}$$ The theorem implies that the number of such $n\le x$ is $$O(x(\log\log x)^{-2\delta})=o(x)$$

My question is how does the theorem imply the result? I've played around with it for a while, but I don't think I've had any luck (not any that I've understood at least). I think I've managed to show $$|v(n)-\log\log x| = O(x(\log\log x)^{-2\delta})$$ but I'm not sure if this proves the result or not, or if it's even useful here.

Any help is greatly appreciated and thanks in advance!

  • $\begingroup$ an early milestone, en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Kac_theorem They tend to do normal order in Hardy and Wright, let me check that. $\endgroup$
    – Will Jagy
    Commented Sep 19, 2022 at 22:14
  • $\begingroup$ Hardy and Wright, Theorems 430 and 431: both the avergae order and the normal order of both $\omega(n)$ and $\Omega(n)$ is $\log \log n. $ Section 22.10, pages 354-358 in the fifth edition $\endgroup$
    – Will Jagy
    Commented Sep 19, 2022 at 22:19
  • $\begingroup$ Ah, thank you, it's a simple contradiction that they use to show this. I'll post a solution below $\endgroup$
    – James2390
    Commented Sep 20, 2022 at 16:27

1 Answer 1


If we suppose that the number of such $n\le x$ isn't o(x), then we have that for more than $cx$ of the $n$'s, we have that $$|v(n)-\log\log x|\ge(\log\log x)^{\frac{1}{2}+\delta}$$ (for any $c\in\mathbb{R}$). Then, in the sum of Turan's theorem, we get: $$\sum_{n\ge x}(v(n)-\log\log x)^2 \ge cx((\log\log x)^{\frac{1}{2}+\delta})^2 = cx(\log\log x)^{1+2\delta}$$ But this is greater than $cx\log\log x$ for the bounding $c$ in the big $O$ and hence we can't have that the sum is $O(x\log\log x)$. Thus we must have that the number of such $n\le x$ is $o(x)$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .