I am trying to understand the second moment method proof of the following theorem:
Let $\omega(n)\rightarrow\infty$ arbitrarily slowly and $\vartheta(x)$ the number of primes which divide $x$. Then number of $x$ in $\{1,...,n\}$ such that $$|\vartheta(x) − \ln(\ln(n))| > \omega(n)\sqrt{\ln(\ln(n))}$$ is $o(n)$.
The proof is available in the following papers: https://cs.nyu.edu/spencer/rg06/prime.pdf https://cse.buffalo.edu/~hungngo/classes/2011/Spring-694/lectures/sm.pdf
The problem is that I do not understand how I get the desired result with the following inequality:$$\mathbb{P}\left(|\vartheta(x) − \ln(\ln(n))| > K\sqrt{\ln(\ln(n))}\right)<K^{-2}+o(1).$$
It is clear to pick $K=\omega(n)$ and I get:$$ \mathbb{P}\left(|\vartheta(x) − \ln(\ln(n))| > \omega(n)\sqrt{\ln(\ln(n))}\right)<\omega(n)^{-2}+o(1)$$ How does the theorem follow from the inequality?
I am very grateful for every help!
Sincerely, Hypertrooper
You're almost exactly there: the $\mathbb{P}$ refers to choosing $x$ uniformly between $1$ and $n$, so the number of $x$ for which you have $|\theta(x) - \ln(\ln(n))| > \omega(n) \sqrt{\ln(\ln(n))}$ is exactly $$n\cdot \mathbb{P}\left( |\theta(x) - \ln(\ln(n))| > \omega(n) \sqrt{\ln(\ln(n))}\right). $$
You've bounded this above by $n \omega(n)^{-2} + o(n)$ which is $o(n)$.