Welcome to MathOverflow

Question

3

2

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

flag	asked May 7 2010 at 15:19 Niel de Beaudrap 1,018●4●10

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 2010 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 2010 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 2010 at 5:06

Okay, this seems fairly clear. Thanks. – Niel de Beaudrap May 15 2010 at 12:29

Charles · Answer 1 · 2010-05-12 05:42:27Z UTC

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

Bound on the number of prime factors of logarithmically rough numbers

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.