Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)?

share|improve this question
3  
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)}$. –  Dror Speiser May 7 '10 at 16:01
    
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? –  Niel de Beaudrap May 10 '10 at 7:35
    
$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)}$. –  Dror Speiser May 12 '10 at 5:06
    
Okay, this seems fairly clear. Thanks. –  Niel de Beaudrap May 15 '10 at 12:29

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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