Asymptotic behaviour of $\omega(n)$

Question

I've been working on this homework exercise for quite some time now and I just won't succeed. Any help would be appreciated.

Let $\omega(n)$ be the number of distinct prime divisors of $n$. I need to prove that $\omega(n) = O\left(\frac{\log(n)}{\log\log(n)}\right)$ as $x\to\infty$. There is a hint which says to first prove $\omega(n)!\le n$ (which was easy) . Furthermore, I may use $\omega(n)!\ge \exp(\omega(n)\log(\omega(n))-\omega(n))$.

From these hints it follows that $\omega(n)\log(\omega(n))-\omega(n) \le \log(n)$ and thus $\omega(n) \le \log(n)/(\log(\omega(n))-1)$, but then I get stuck.

Alternatively, $\omega(n)\log(\omega(n)) \le \log(n) + \omega(n) \le 2\log(n)$ and I get stuck again.

I've found a proof which I understand but it does not use any of the hints. Since I have been giving this some time now, I would really like to know how to do it in the way suggested by the exercise.

Thanks in advance!

Answer 1

Once you have the inequality $\omega(n) \log \omega(n) \leq 2\log n$ you're basically there. Now assume for contradiction that for all large enough $n$ we have $\omega(n) > C \frac{\log n}{\log \log n}$. Here $C$ is some large constant, though actually $C>2$ suffices.

Answer 2

The paper by Robin we have here, on page 368 (its second page):

la fonction $\omega(n)$: nombre de diviseurs premiers de l'entier $n$.

Which translates to:

the function $\omega(n)$: the number of prime divisors of the integer $n$.

(This is a standard definition, but it's good to check the paper is using the definition you want.)

Then, on the following page (369, the third page of the article) there are various upper bounds on $\omega(n)$ given. I'll just quote the first one; you can read them yourself with the note that pour means for and a comma is used instead of a decimal point:

$\omega(n) \leq 1.3841 \frac{\log n}{\log\log n}$ for $n \geq 3$

This confirms that $\omega(n)$ is $O(\frac{\log n}{\log \log n})$.

You can also the proof in G.H.Hardy and Wright's "Introduction to the Theory of Numbers".