It's a standard result that the number ω(N) of prime factors of N > 2 can be bounded above by$$ \omega(N) \;=\; \frac{\log(N)}{\log\log(N)} \big(1 + O\big(1/\log\log(N)\big)\big) \;.$$ Are tighter bounds known when N is logarithmically rough --- that is, where for some fixed constant c > 0, N has no prime factors smaller than c log(N)?

  • 3
    $\begingroup$ Unless my scribblings on the board are wrong, a short calculation shows that for any such fixed constant, the bound is exactly the same. The scribblings are the following: the largest $\omega$ is achieved by multiplying the primes between $y$ and $x$. To satisfy your condition, $y \sim \frac{c}{c+1}x$, so $N \sim e^{\frac{x}{c+1}}$ and $\omega(N) \sim \frac{x}{(c+1)\log(x)}$. $\endgroup$ – Dror Speiser May 7 '10 at 16:01
  • $\begingroup$ Forgive me, I'm not a number theorist. It's clear that $\omega(N)$ is maximized by taking consecutive primes. But: (a) how do you obtain the bound $y\sim(\frac{c}{c+1})x$, and (b) how do you obtain the asymptotic growth of $N$ with respect to $x$? For the latter (given the ratio of $y$ to $x$ described) I obtain a rough bound of $N>\frac{x!}{[cx/(c+1)]!}\in\Omega\big((x/e)^{x/(c+1)}\big)$ , which is larger than the growth you describe. Could you elaborate further on your scribblings, or refer me to the (likely elementary textbook) reference where I could find the tools you're using? $\endgroup$ – Niel de Beaudrap May 10 '10 at 7:35
  • $\begingroup$ $N=\prod_{y<p<x} p \sim e^{x-y}$. The condition translates to $y > c\log(e^{x-y})=c(x-y)$ or $y>\frac{c}{c+1}x$. So taking equality we have $N \sim e^{\frac{1}{c+1}x}$ and $\omega(N) = \pi(x)-\pi(y) \sim x/\log(x)-cx/(c+1)\log(cx/(c+1)) \sim \frac{x}{(c+1)\log(x)}$. $\endgroup$ – Dror Speiser May 12 '10 at 5:06
  • $\begingroup$ Okay, this seems fairly clear. Thanks. $\endgroup$ – Niel de Beaudrap May 15 '10 at 12:29
  • $\begingroup$ By $\omega(N)$ do you mean number of prime factors or number of distinct prime factors? $\endgroup$ – gen Mar 18 '19 at 15:53

The intuition is that $\log_{c\log N}N=\frac{\log N}{\log(c\log N)}=\frac{\log N}{\log c+\log\log N}$ which is asymptotically $\frac{\log N}{\log\log N}$. For this to work, we need that the kth prime for $k=\frac{\log N}{\log(c\log N)}+\pi(c\log N)\approx\frac{\log N}{\log\log N}$ to be 'close' to $c\log N$ -- actually, any constant multiple of $\log N$ will do.

$p_k\approx\frac{\log N}{\log\log N}\log\frac{\log N}{\log\log N}\approx\log N$, so $\log_{p_k}N\approx\frac{\log N}{\log\log N}$, as desired. This could probably made explicit with Rosser's theorem and/or Dusart's various bounds on $p_n$ and $\pi(n)$.


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.