7
$\begingroup$

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

$\endgroup$

4 Answers 4

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 28, 2010 at 16:35
7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Maybe. I feel like I've seen it stated explicitly, though. $\endgroup$ Mar 4, 2010 at 18:01
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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