# Inequality with number of prime divisors

I've got a problem with this inequality. Let $\omega(n)$ be the number of prime divisors of $n$ (as usual, without multiples). Prove that: $2^{\omega(n)} \leq n^{\frac{1}{\log \log n}},$ where $\log n$ is a natural logarithm.

Thanks a lot!

• where did you get this???? – Will Jagy Sep 2 '13 at 23:38
• It's wrong for $n = 2$. – Daniel Fischer Sep 3 '13 at 0:02

Let $p_n$ denote the $n$-th prime and let $k\#$ be the product of the primes $\leq k$ (called primorials). Thus, by definition, $$\omega(p_n\#)=n.$$

Since $n\#>0.92\ e^n$ for $n \geq 563$ (see footnote), if $m \leq 0.92\ e^{n+1}$ and $n \geq 563$, then the greatest primorial not exceeding $m$ is at most $n\#$. Further, $n\#$ has at least as many prime factors as $m$. Hence \begin{align*} \omega(m) & \leq \omega(n\#) & \text{for } n \geq 563 \text{ and all } m\leq 0.92\ e^{n+1} \leq e^n \\ & = \omega(p_{\pi(n)}\#) & \text{by definition} \\ & = \pi(n) \\ \end{align*} where $\pi$ is the prime counting function. Thus $$\omega(m) \leq \pi(\log n)$$ for $n \geq e^{563}$ and $m \leq n$. In particular, $$\omega(n) \leq \pi(\log n).$$

Wikipedia tells us $$\pi(n) \leq \frac{cn}{\log n}$$ for $n \geq 2$, where $c=1.25506$.

We conclude that \begin{align*} 2^{\omega(n)} & \leq 2^{\pi(\log n)} & \text{for all } n \geq e^{563} \\ & = n^{k\ \pi(\log n)/\log n} & \text{where } k=\log 2 \\ & \leq n^{\frac{ck\log n}{\log n \log\log n}} \\ & < n^{\frac{1}{\log\log n}} & \text{since } ck<1. \end{align*}

Footnote: Will Jagy's answer here gives $$\log(x \#) > x \left(1 - \frac{1}{2 \log x} \right)$$ provided $x \geq 563$. Thus, we can compute that $\log(563 \#) > 0.92\ x$ and by noting that $1 - \frac{1}{2 \log x}$ is an increasing function, this proves that $\log(n \#)>0.92\ n$ for all $n \geq 563$.

• Rebecca, for $n>1,$ we have $$\log(n \#) < n \left(1 + \frac{1}{2 \log x} \right).$$ This is Theorem 4, formula 3.15 in Rosser and Schoenfeld (1962), Illinois J. Math. – Will Jagy Sep 3 '13 at 2:18
• – Will Jagy Sep 3 '13 at 2:34
• Also, your wikipedia bound with the 1.25506 is true for $x > 1,$ that is Theorem 2, Corollary 1, formula 3.6. – Will Jagy Sep 3 '13 at 2:44
• Thank You, Rebecca! Cheers :) – user92813 Sep 3 '13 at 10:36
• Thanks for the comments Will Jagy; I did see them late last night, but needed to sleep. It's updated now; feels much more complete! – Rebecca J. Stones Sep 3 '13 at 16:15