# On the Proof of the Normal Order of the Number of Prime Divisors

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!

• 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. Commented Sep 19, 2022 at 22:14
• 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 Commented Sep 19, 2022 at 22:19
• Ah, thank you, it's a simple contradiction that they use to show this. I'll post a solution below Commented Sep 20, 2022 at 16:27

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)$$.