## 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:

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

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:

\begin{equation} X = \sum_{p \leq M} X_p \end{equation}

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

\begin{equation} \nu(x) - 2 \leq X \leq \nu(x) \end{equation}

Moreover, from a frequentist perspective we have:

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

and therefore:

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

due to Mertens’ second theorem.

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

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

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

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

It follows that the variance is given by:

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

and so by Chebyshev’s inequality we have:

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

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