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)?
$\begingroup$
$\endgroup$
6
-
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 SpeiserCommented May 7, 2010 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 BeaudrapCommented May 10, 2010 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 SpeiserCommented May 12, 2010 at 5:06
-
$\begingroup$ Okay, this seems fairly clear. Thanks. $\endgroup$– Niel de BeaudrapCommented May 15, 2010 at 12:29
-
$\begingroup$ By $\omega(N)$ do you mean number of prime factors or number of distinct prime factors? $\endgroup$– genCommented Mar 18, 2019 at 15:53
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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)$.
