# Show that $\sum\limits_{p\mid n}1= o(\log n)$

How can I prove that $\omega(n)= o(\log{n})$ when $x\to\infty$?

Here $\omega(n)= \sum_{p|n}1,$ i.e. if $n = \prod_{i=1}^{r} p_i^{v_i}$, then $\omega(n)=r.$

I want $$\lim_{n\to\infty}\frac{\omega(n)}{\log{n}}=0.$$

I have tried using the fact that $2^{w(n)}\leq \tau(n)$, but I am stuck. Can anyone help me?

• $\omega(n)$ satisfies $\omega (n) = O\Big{(} \frac{\log(n)}{\log(\log(n))}\Big{)}$, see here. – Dietrich Burde Sep 6 '16 at 20:46

## 1 Answer

The largest $\omega(n)$ occurs at $$n = \prod_{p < k} p$$ (a primorial)

The prime number theorem shows that $$\ln n = \sum_{p < k} \ln p \sim k$$ Now $$\omega(n) = \sum_{p < k} 1 = \pi(k) \sim \frac{k}{\ln k}$$ again by the PNT.

Hence at those $n$ primorials $$\omega(n) \sim \frac{\ln n}{\ln \ln n}$$

And with $n$ arbitrary : $$\omega(n) < C \frac{\ln n}{\ln \ln n}$$ for some $C$ that $\to 1$ when restricting to $n$ large enough .

• You don't need PNT at all here: the $k$th primorial is the least integer $n$ such that $\omega(n) \ge k$, and it's obvious that the $k$th primorial is at least $k!$. The fact that $k!$ exceeds $c^k$ for any fixed $c$ is an elementary exercise. – Erick Wong Sep 13 '16 at 3:09
• @ErickWong for $C \to 1$ you need the PNT (otherwise you can bound $\omega(n)$ with a weak form of the PNT : $x < \alpha \sum_{p < x}\ln p$ and $\pi(x) < \beta \frac{x}{\ln x}$ ) – reuns Sep 13 '16 at 3:14
• @user1952009 Sorry, I was referring to the OP's question, which is just to show that $\omega(n) = o(\log n)$, rather than the precise maximal order. – Erick Wong Sep 13 '16 at 5:26
• @ErickWong then yes I agree, $\omega(n) \ne o(\ln n) \implies \lim\sup_n \frac{\omega(n)}{\ln n} > c \implies k > c\sum_{p < k} \ln p \implies$ a contradiction – reuns Sep 13 '16 at 5:46