0
$\begingroup$

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!

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

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Will Jagy Sep 3 '13 at 2:18
  • $\begingroup$ see projecteuclid.org/… $\endgroup$ – Will Jagy Sep 3 '13 at 2:34
  • $\begingroup$ Also, your wikipedia bound with the 1.25506 is true for $x > 1,$ that is Theorem 2, Corollary 1, formula 3.6. $\endgroup$ – Will Jagy Sep 3 '13 at 2:44
  • $\begingroup$ Thank You, Rebecca! Cheers :) $\endgroup$ – user92813 Sep 3 '13 at 10:36
  • $\begingroup$ 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! $\endgroup$ – Rebecca J. Stones Sep 3 '13 at 16:15

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.