Maximal order of magnitude of Prime Omega Function

Question

Let $\omega(n)=\sum_{p|n}1$ be the prime omega function.
Prove that for any $\epsilon > 0$,

1. There exists $N>0$ such that for all $n > N$,
   $$\omega (n)<\frac{(1+\epsilon)\log{n}}{\log{\log{n}}}$$
2. There exists infinitely many $n$ such that
   $$\omega (n)>\frac{(1-\epsilon)\log{n}}{\log{\log{n}}}$$

I don't even know how to begin the question.
I only know that $\displaystyle \left| \frac{\sum_{i=1}^n\omega(i)}{n}-\log{\log{n}}\right|<C$ for some constant $C$ and $n\geq 3$.
For (1), I don't know how to come up with $N$ with $\epsilon$;
For (2), I suppose somehow we can construct a formula for those $n$'s, but I don't know how to deal with the $\log{\log{n}}$.
Thank you for any help.

Answer 1

We'll need the PNT: $\pi(x) \sim \frac{x}{\ln x},\theta(x)\sim x$.

Let $N_x = \prod \limits_{p \leq x} p = e^{\theta(x)} $ and so $\omega(N_x) = \sum \limits_{p|N_x} 1 = \sum \limits_{p\leq x} 1 = \pi(x) \sim \frac{x}{\ln x}$.

$\ln N_x = x$ and $ \ln \ln N_x = \ln x$ and so $ \omega(N_x) \sim \frac{x}{\ln x} \sim \frac{\ln N_x} {\ln \ln N_x}$, this means that for all $\epsilon >0$ there exists $x_0 $ such that for all $x> x_0$ we have that $ \frac{(1-\epsilon) \ln N_x}{\ln \ln N_x} < \omega(N_x) < \frac{(1+\epsilon) \ln N_x}{\ln \ln N_x}$, the lower bound is enough to answer your second question.

For the first you need to notice that when $N$ is a multiplication of $\pi(x)$ different primes then $N \geq N_x$ since the primes in $N_x$ are in ascending order and so $\omega(N) =\omega(N_x) < \frac{(1+\epsilon) \ln N_x}{\ln \ln N_x} \leq \frac{(1+\epsilon) \ln N}{\ln \ln N}$ because $\frac{\ln t}{\ln \ln t}$ is monotonic function.

Note : you can use lower/upper bound on $\theta(x),\pi(x)$ to make the upper argument an explicit one rather than implicit.

Answer 2

Using the definition of limit, the problem asks you to prove that

$$ \lim_{n\to\infty}\omega(n)\left/\log n\over\log\log n\right.=1 $$

Now, let's define the following functions:

$$ \pi(x)=\sum_{p\le x}1\tag{Prime-counting function} $$ $$ \vartheta(x)=\sum_{p\le x}\log p\tag{Chebyshev's theta function} $$

As a result, $\exp\vartheta(x)$ gives the product of all prime numbers within $x$, meaning

$$ \pi(x)=\omega[\exp\vartheta(x)]\tag1 $$

By the prime number theorem, we have

$$ \pi(x)\sim{x\over\log x}\quad\text{or}\quad\lim_{x\to\infty}{\pi(x)\log x\over x}=1\tag2 $$

Now, via Riemann-Stieltjes integration, we obtain the following formula:

$$ \begin{aligned} {\vartheta(x)\over x} &=\frac1x\sum_{p\le x}\log p=\frac1x\int_{2-\varepsilon}^x\log t\mathrm d\pi(t) \\ &={\pi(x)\log x\over x}-\frac1x\int_2^x{\pi(t)\over t}\mathrm dt \\ &={\pi(x)\log x\over x}+\mathcal O\left(\frac1x\int_2^x{\mathrm dt\over\log t}\right) \end{aligned} $$

By taking $x\to\infty$ and employing (2), we deduce the following relation:

$$ \vartheta(x)\sim x\quad\text{or}\quad\lim_{x\to\infty}{\vartheta(x)\over x}=1\tag3 $$

This means $\log[\exp\vartheta(x)]\sim x$, allowing us to make the following substitution:

$$ \omega[\exp\vartheta(x)]\sim{\log[\exp\vartheta(x)]\over\log x}\tag4 $$

All we need here is to perform substitution on the denominator. Taking logarithm on (3) gives

$$ \lim_{x\to\infty}[\log\vartheta(x)-\log x]=0 $$

As a result,

$$ \lim_{x\to\infty}{\log\vartheta(x)\over\log x}=\lim_{x\to\infty}{\log x+\log\vartheta(x)-\log x\over\log x}=1 $$

and plugging this into (4) gives

$$ \omega[\exp\vartheta(x)]\sim{\log[\exp\vartheta(x)]\over\log\log[\exp\vartheta(x)]} $$

Finally, substitute $\exp[\vartheta(x)]$ with $n$ produces

$$ \omega(n)\sim{\log n\over\log\log n}\quad\text{or}\lim_{n\to\infty}\omega(n)\left/\log n\over\log\log n\right.=1 $$

$ \Huge\square $