3
$\begingroup$

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?

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

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 .

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Erick Wong Sep 13 '16 at 3:09
  • $\begingroup$ @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}$ ) $\endgroup$ – reuns Sep 13 '16 at 3:14
  • $\begingroup$ @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. $\endgroup$ – Erick Wong Sep 13 '16 at 5:26
  • $\begingroup$ @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 $\endgroup$ – reuns Sep 13 '16 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.