Number Theory – Asymptotic Density of k-Almost Primes

asymptoticsnt.number-theoryprime numbers

Let $\pi_k(x)=|\{n\le x:n=p_1p_2\cdots p_k\}|$ be the counting function for the k-almost primes, generalizing $\pi(x)=\pi_1(x)$. A result of Landau is
$$\pi_k(x)\sim\frac{x(\log\log x)^{k-1}}{(k-1)!\log x}\qquad\qquad(1)$$
but this approximation is very poor for $k>1$.

For $\pi(x)$ much more is known. A (divergent) asymptotic series
$$\pi(x)=\frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2}{\log^2x}+\frac{6}{\log^3x}\cdots\right)\qquad\qquad(2)$$
exists (see. e.g., the historical paper of Cipolla [1] who inverted this to produce a series for $p_n$). And of course it is well-known that
$$\pi(x)=\operatorname{Li}(x)+e(x)\qquad\qquad(3)$$
for an error term $e(x)$ (not sure what the best current result) that can be taken [4], on the RH, to be $O(\sqrt x\log x)$. Even better, Schoenfeld [6] famously transformed this into an effective version with
$$|e(x)|<\sqrt x\log x/8\pi\qquad\qquad(4)$$
for $x\ge2657$. For the heretics rejecting the Riemann Hypothesis, Pierre Dusart has a preprint [2] which improves on the results in his thesis [3]; in particular, for $x\ge2953652302$,
$$\frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2}{\log^2x}\right)\le\pi(x)\le\frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2.334}{\log^2x}\right)\qquad\qquad(5)$$

But I know of no results even as weak as (2) for almost primes. Even if nothing effective like (5) exists, I would be happy for an estimate like (3).

Partial results

Montgomery & Vaughan [5] show that
$$\pi_k=G\left(\frac{k-1}{\log\log x}\right)\frac{x(\log\log x)^{k-1}}{(k-1)!\log x}\left(1+O\left(\frac{k}{(\log\log x)^2}\right)\right)$$
for any fixed k (and, indeed, uniformly for any $1\le k\le(2-\varepsilon)\log\log x$ though the O depends (exponentially?) on the $\varepsilon$), where
$$G(z)=F(1,z)/\Gamma(z+1)$$
and
$$F(s,z)=\prod_p\left(1-\frac{z}{p^s}\right)^{-1}\left(1-\frac{1}{p^s}\right)^z$$
though I'm not quite sure how to calculate $F$.

If this is the best result known (rather than simply the best result provable at textbook level) then this shows that far less is known about the distribution of, e.g., semiprimes than about primes.

References

[1] M. Cipolla, “La determinazione assintotica dell n$^\mathrm{imo}$ numero primo”, Matematiche Napoli 3 (1902), pp. 132-166.

[2] Pierre Dusart, "Estimates of Some Functions Over Primes without R.H." (2010) http://arxiv.org/abs/1002.0442

[3] Pierre Dusart, "Autour de la fonction qui compte le nombre de nombres premiers" (1998) http://www.unilim.fr/laco/theses/1998/T1998_01.html

[4] Helge von Koch, "Sur la distribution des nombres premiers". Acta Mathematica 24:1 (1901), pp. 159-182.

[5] Hugh Montgomery & Robert Vaughan, Multiplicative Number Theory I. Classical Theory. (2007). Cambridge University Press.

[6] Lowell Schoenfeld, "Sharper Bounds for the Chebyshev Functions θ(x) and ψ(x). II". Mathematics of Computation 30:134 (1976), pp. 337-360.

[7] Robert G. Wilson v, Number of semiprimes <= 2^n. In the On-Line Encyclopedia of Integer Sequences, A125527. http://oeis.org/A125527 ; c.f. http://oeis.org/A007053


EDIT, by Joël. I edit this old question to bump it up and observe that one aspect has not been answered. Namely, is there under the Riemann Hypothesis an asymptotic estimate for $\pi_k(x)$ analog to (3), (4) for $\pi(x)$ (that is $\pi(x) = Li(x) + O(\sqrt{x} \log x)$)? Or any estimate for $\pi_k(x)$, with a principal term given by some classical functions, and an error term in $O(x^\delta)$ with some $\delta<1$? Micah's answer gives a principal term which is a rational function of $x$, $\log x$, $\log \log x$, but with a much less good error term, which is not surprising since even for $\pi(x)$ it is well-known that the principal term must be written as $Li(x)$, not $x/\log(x)$, if we want to have some hope of and rarer term in $O(x^\delta)$, $\delta<1$ (let alone $O(\sqrt{x}\log x)$).

Best Answer

I'll address Joel's edited question of getting good asymptotics on RH. The argument below is essentially due to Selberg, but this is not quite what he does and I haven't seen it presented this way in the literature. The natural problem is to consider the coefficients of $(\log \zeta (s))^k/k!$ rather than numbers with exactly $k$ prime factors. Note that for $k=1$ and $2$ the two objects are closely related, and some obvious but unpleasant combinatorics is needed for larger $k$.

Thus we want to compute $$ \frac{1}{2\pi i} \frac{1}{k!} \int_{c-i\infty}^{c+i\infty} (\log \zeta(s))^k x^s \frac{ds}{s}, $$ where the integral is taken over some line with $c>1$. Now we want to shift contours as usual, but we need to be careful because logarithmic singularities are involved rather than just poles. First choose $c$ just a little bigger than $1$ and truncate the integral at some height $T$. Then deform the contour as follows: Take a slit along the real axis from $1/2+\epsilon$ to $1$ with a line just above and a line just below the slit, and then line segments from $1/2+\epsilon$ to $1/2+\epsilon +iT$ and then from there to $c+iT$, and similar line segments below the real axis. If one assumes RH, the errors in truncation together with all the integrals except for the ones above and below the slit can be bounded by $x^{1/2+\epsilon}$. Thus we conclude that our integral equals, with error $O(x^{1/2+\epsilon})$, $$ -\frac{1}{2\pi i} \frac{1}{k!} \int_{1/2+\epsilon}^{1} \Big((\log \zeta(\sigma+ 0^+ i))^k - (\log \zeta(\sigma+0^- i))^k \Big) \frac{x^\sigma}{\sigma} d\sigma. $$ Here I use $0^+i$ to denote the upper part of the slit, and $0^-$ to denote the lower part. The two terms don't cancel out because of the change in the argument of $\zeta$ above and below the slit. Note that above the slit one has $\log \zeta(\sigma+0^+i) = \log |\zeta(\sigma)| - i\pi$ and below the slit one has $\log \zeta(\sigma+0^-i) = \log |\zeta(\sigma)| +i \pi$. Thus we find that the desired answer is $$ \frac{1}{\pi k!} \int_{1/2+\epsilon}^1 \text{Im} (\log |\zeta(\sigma)| +i\pi)^k \frac{x^{\sigma}}{\sigma} d\sigma + O(x^{1/2+\epsilon}). $$

To appreciate what this means, consider first the prime number theorem which is the case $k=1$. From above we see that the main term is $$ \int_{1/2+\epsilon}^{1} \frac{x^{\sigma}}{\sigma} d\sigma, $$ and a change of variables produces $\text{Li}(x)$. When $k=2$ (essentially the case of $\pi_2(x)$) the work above gives $$ \int_{1/2+\epsilon}^1 \log |\zeta(\sigma)| \frac{x^{\sigma}}{\sigma} d\sigma + O(x^{1/2+\epsilon}). $$ The leading order asymptotics come from $\sigma$ very close to $1$, on the scale of $1-c/\log x$, and then $\log |\zeta(\sigma)|$ will contribute the extra $\log \log x$. One can obtain more precise asymptotic expansions etc from this expression.

Let me also note that one can make this argument unconditional using the classical zero free region, and it may be worthwhile carrying this out. The usual way in which such results are carried out in the literature is to start with asymptotics for coefficients of $\zeta(s)^z$ for complex $z$, and then to use the saddle point method to identify from this numbers with $k$ prime factors. This is Selberg's argument with various elaborations, most notably by Hildebrand and Tenenbaum. The argument above seems to be a shortcut and may produce better results. It would be surprising if nobody had thought of it before, but at any rate I haven't seen it.

Related Question