Reference for the expected number of prime factors of n larger than n^alpha is -log alpha - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T04:59:48Z http://mathoverflow.net/feeds/question/17105 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17105/reference-for-the-expected-number-of-prime-factors-of-n-larger-than-nalpha-is-l Reference for the expected number of prime factors of n larger than n^alpha is -log alpha Michael Lugo 2010-03-04T16:41:13Z 2011-11-28T09:21:55Z <p>Let $0 &lt; \alpha &lt; 1$ be a constant. The expected number of prime factors of a "random" integer near $n$ which are greater than $n^\alpha$ is $-\log \alpha$.</p> <p>It's my understanding that (properly formulated) this is a well-known fact in analytic number theory but I cannot find a reference for it. Can anybody provide a reference?</p> <p><b>Edited to add (March 28):</b>: The asymptotic density of positive integers $n$ with $k$th largest factor smaller than $n^{1/\alpha}$ is $\rho_k(\alpha)$, where we have $L_0(\alpha) = [\alpha > 0]$ and $$L_k(\alpha) = [\alpha \ge k] \int_k^\alpha L_{k-1}(t-1) \: {dt \over t},$$ and $1-\rho_k(\alpha) = \sum_{n=0}^\infty {-k \choose n} L_{n+k}(\alpha)$. (See Riesel, p. 162.) The density of positive integers with $k$th largest factor <em>larger</em> than $n^{1/\alpha}$ is therefore $1-\rho_k(\alpha)$, and so the expected number of factors larger than $n^{1/\alpha}$ is $\sum_{k \ge 1} (1-\rho_k(\alpha))$. Therefore the expected number of such factors is $$\sum_{k \ge 1} \sum_{n \ge 0} {-k \choose n} L_{n+k}(\alpha).$$ Letting $n+k = j$ we can rewrite this sum as $$\sum_{j \ge 1} \sum_{n=0}^{j-1} {n-j \choose n} L_j = \sum_{j \ge 1} L_j \left( \sum_{n=-0}^{j-1} (-1)^n {j-1 \choose n} \right)$$ and the inner sum is $0$ except when $j=1$, when it is $1$. So the expected number of factors larger than $n^{1/\alpha}$ is $L_1(\alpha)$; this is $\log \alpha$.</p> http://mathoverflow.net/questions/17105/reference-for-the-expected-number-of-prime-factors-of-n-larger-than-nalpha-is-l/17114#17114 Answer by David Hansen for Reference for the expected number of prime factors of n larger than n^alpha is -log alpha David Hansen 2010-03-04T17:35:00Z 2010-03-04T17:35:00Z <p>I believe you can extract this from a paper of Andrew Granville, "Prime divisors are Poisson distributed". There is an electronic copy of this on his website.</p> http://mathoverflow.net/questions/17105/reference-for-the-expected-number-of-prime-factors-of-n-larger-than-nalpha-is-l/17143#17143 Answer by Gerry Myerson for Reference for the expected number of prime factors of n larger than n^alpha is -log alpha Gerry Myerson 2010-03-04T22:41:21Z 2010-03-04T22:41:21Z <p>Theorem 5.4 of Riesel, Prime Numbers and Computer Methods for Factorization, says "the number of prime factors $p$ of integers in the interval $[N-x,N+x]$ such that $a&lt;\log\log p&lt; b$ is proportional to $b-a$ if $b-a$ as well as $x$ are sufficiently large as $N\to\infty$." </p> http://mathoverflow.net/questions/17105/reference-for-the-expected-number-of-prime-factors-of-n-larger-than-nalpha-is-l/17574#17574 Answer by Dimitris Koukoulopoulos for Reference for the expected number of prime factors of n larger than n^alpha is -log alpha Dimitris Koukoulopoulos 2010-03-09T03:55:46Z 2010-03-09T03:55:46Z <p>Do you mean that $\log(1/\alpha)$ is the expected number of prime factors in $(x^\alpha,x]$ when $\alpha\to0$? For fixed $\alpha\in(0,1)$ what you are claiming is not true. For example, </p> <p>$|{n\le x:\exists p|n\;{\rm with}\;\sqrt{x}\lt p\le x}|\sim x\log2$</p> <p>and </p> <p>$|{n\le x:p\le\sqrt{x}\;{\rm for all}\;p|n}|\sim(1-\log2)x$.</p> <p>When $\alpha\to0$ it is not hard to prove what you need, but I am not sure where you can find a precise reference. For example, setting $\omega(n;y,z)=|{p|n:y\lt p\le z}|$ and following the proof of Theorem 6 in page 311 in Tenenbaum's book "Introduction to Analytic and Probabilistic Number Theory" gives that</p> <p>$|{n\le x:|\omega(n;x^\alpha,x)-\log(1/\alpha)|\ge(1+\delta)\log(1/\alpha)}|\ll x\alpha^{Q(1+\delta)},$</p> <p>where $Q(1+\delta)=\int_1^{1+\delta}\log tdt$.</p> http://mathoverflow.net/questions/17105/reference-for-the-expected-number-of-prime-factors-of-n-larger-than-nalpha-is-l/82063#82063 Answer by Eric Naslund for Reference for the expected number of prime factors of n larger than n^alpha is -log alpha Eric Naslund 2011-11-28T09:10:47Z 2011-11-28T09:21:55Z <p>You seem to be over complicating things. For $\alpha$ fixed, this is relatively easy to prove. I leave it to you deduce the desired result as a consequence of the following theorem: </p> <blockquote> <p><strong>Theorem:</strong> Let $x>0$ and fix $0&lt;\alpha&lt;1$. Define $\omega_{x,\alpha}(n)=\sum_{p|n,\ p>x^\alpha} 1$. Then this function has average value $$\frac{1}{x}\sum_{n\leq x} \omega_{x,\alpha}(n)=-\log \alpha +O\left(\frac{1}{\log x}\right).$$</p> </blockquote> <p><em>Proof:</em> Notice that </p> <p><code>$$\frac{1}{x}\sum_{n\leq x} \omega_{x,\alpha}(n)=\frac{1}{x}\sum_{x^{\alpha}&lt;p&lt;\leq x}\left[\frac{x}{p}\right] =\sum_{x^{\alpha}&lt;p&lt;\leq x}\frac{1}{p}-\frac{1}{x}\sum_{x^{\alpha}&lt;p&lt;\leq x}\left\{\frac{x}{p}\right\}$$</code> </p> <p><code>$$= \sum_{x^\alpha&lt;p&lt;x} \frac{1}{p} +O\left(\frac{1}{\log x}\right)=\log \log (x)-\log \log x^\alpha +O\left(\frac{1}{\log x}\right)$$</code> <code>$$=-\log \alpha +O\left(\frac{1}{\log x}\right).$$</code></p>