Reference for the expected number of prime factors of n larger than n^alpha is -log alpha - MathOverflow

Reference for the expected number of prime factors of n larger than n^alpha is -log alpha

2010-03-04T16:41:13Z

Let $0 < \alpha < 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$.

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?

Edited to add (March 28):: 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 larger 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$.

Answer by David Hansen for Reference for the expected number of prime factors of n larger than n^alpha is -log alpha

2010-03-04T17:35:00Z

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.

Answer by Gerry Myerson for Reference for the expected number of prime factors of n larger than n^alpha is -log alpha

2010-03-04T22:41:21Z

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<\log\log p< b$ is proportional to $b-a$ if $b-a$ as well as $x$ are sufficiently large as $N\to\infty$."

Answer by Dimitris Koukoulopoulos for Reference for the expected number of prime factors of n larger than n^alpha is -log alpha

2010-03-09T03:55:46Z

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,

$|{n\le x:\exists p|n\;{\rm with}\;\sqrt{x}\lt p\le x}|\sim x\log2 $

and

$|{n\le x:p\le\sqrt{x}\;{\rm for all}\;p|n}|\sim(1-\log2)x$.

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

$|{n\le x:|\omega(n;x^\alpha,x)-\log(1/\alpha)|\ge(1+\delta)\log(1/\alpha)}|\ll x\alpha^{Q(1+\delta)},$

where $Q(1+\delta)=\int_1^{1+\delta}\log tdt$.

Answer by Eric Naslund for Reference for the expected number of prime factors of n larger than n^alpha is -log alpha

2011-11-28T09:10:47Z

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:

Theorem: Let $x>0$ and fix $0<\alpha<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).$$

Proof: Notice that

$$\frac{1}{x}\sum_{n\leq x} \omega_{x,\alpha}(n)=\frac{1}{x}\sum_{x^{\alpha}<p<\leq x}\left[\frac{x}{p}\right] =\sum_{x^{\alpha}<p<\leq x}\frac{1}{p}-\frac{1}{x}\sum_{x^{\alpha}<p<\leq x}\left\{\frac{x}{p}\right\}$$

$$= \sum_{x^\alpha<p<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)$$ $$=-\log \alpha +O\left(\frac{1}{\log x}\right).$$