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

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

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

• I am accepting this even though it is not exactly what I was looking for, because what I was looking for is a couple pages later in Riesel's book. – Michael Lugo Mar 28 '10 at 16:35

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

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.

• Maybe. I feel like I've seen it stated explicitly, though. – Michael Lugo Mar 4 '10 at 18:01

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