## Introduction:

Let’s suppose that $$\forall x \in \mathbb{N}$$, $$\nu(x)$$ counts the number of unique prime divisors of $$x$$. Given $$A = [1,n]$$, for all $$\epsilon \in (0,1)$$ there exists a constant $$c > 0$$ such that at least $$1-\epsilon$$ of the integers in $$A$$ satisfy:

$$\forall x \in A, |\nu(x)- \log \log n| \leq c \cdot \sqrt{\log\log n}$$

as $$n \to \infty$$.

## Turan’s proof:

If we randomly choose $$x \in [1,n]$$, for any prime $$p$$ let’s define the indicator variable $$X_p$$ where $$X_p = 1$$ if $$p|x$$ and $$X_p=0$$ otherwise. So the number of prime divisors of $$x$$ less than or equal to $$M$$ is approximately:

$$X = \sum_{p \leq M} X_p$$

Now, if we pick $$M = \sqrt{n}$$ there are at most two prime factors of $$x$$ larger than $$M$$ so we have:

$$\nu(x) - 2 \leq X \leq \nu(x)$$

Moreover, from a frequentist perspective we have:

$$\mathbb{E}[X_p] = 1 \cdot \frac{1}{p} + 0 \cdot \big(1-\frac{1}{p}\big) = \frac{1}{p}$$

and therefore:

$$\mathbb{E}[X] = \sum_{p \leq M} \frac{1}{p} = \log \log M = \log \log n + \mathcal{O}(1)$$

due to Mertens’ second theorem.

As for the variance of $$X$$ we have:

$$\text{Var}[X] = \sum_{p \leq M} \text{Var}[X_p] + \sum_{p \neq q} \text{Cov}[X_p,X_q]$$

and due to the fact that $$\frac{1}{pq} << \min \big(\frac{1}{p}, \frac{1}{q}\big)$$ for large primes $$p$$ and $$q$$:

$$\text{Cov}[X_p,X_q] = \mathbb{E}[X_p] \cdot \mathbb{E}[X_q] - \mathbb{E}[X_p \cdot X_q] \approx 0$$

It follows that the variance is given by:

$$\text{Var}[X] = \log\log n + \mathcal{O}(1)$$

and so by Chebyshev’s inequality we have:

$$P(|\nu(x) - \log \log n| \geq \lambda \cdot \sqrt{\log \log n}) \leq \frac{1}{\lambda^2}$$

## References:

1. Hardy, G. H.; Ramanujan, S. (1917), “The normal number of prime factors of a number n”, Quarterly Journal of Mathematics
2. Weisstein, Eric W. “Mertens’ Second Theorem.” From MathWorld–A Wolfram Web Resource. https://mathworld.wolfram.com/MertensSecondTheorem.html