## Asymptotic density of k-almost primes

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 who are not certain of 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 Sloane's On-Line Encyclopedia of Integer Sequences, A125527. http://oeis.org/classic/A125527 ; c.f. http://oeis.org/classic/A007053

-
Multiplicative number theory I : classical theory  Hugh L. Montgomery, Robert C. Vaughan.  Cambridge University Press, 2007. – Will Jagy Aug 18 2010 at 5:27
@Will, in particular, Section 7.4, Numbers composed of a prescribed number of primes. The formulas are too complicated to fit within the margins of this comment! – Gerry Myerson Aug 18 2010 at 5:59
I copied out a number of pages, around here somewhere. The raw facts alluded to, perhaps with less detail, are in Hardy and Wright, section 22.18 – Will Jagy Aug 18 2010 at 6:42
@Will: I don't see anything more than (1) -- Theorem 437 in my printing -- in H&W. Am I missing something? – Charles Aug 18 2010 at 7:07
Can you, please, eliminate all instances of the adjective "masterful" from your question? Not only is its utility questionable, it creates an impression that you are trying to promote certain papers. – Victor Protsak Aug 18 2010 at 19:10
show 8 more comments

In Tenenbaum's book "Introduction to analytic and probabilistic number theory" he uses the Selberg-Delange method to prove that the estimate

$$\pi_k(x):=\sum_{n\leq x, \ \omega(n)=k} 1 = \frac{x}{\log x} \sum_{j=0}^N \frac{P_{j,k}(\log\log x)}{(\log x)^j} + O_A\left(\frac{x(\log\log x)^k}{k! \log x} R_N(x) \right)$$

holds uniformly for $x\geq 3$, $1\leq k \leq A \log \log x$, and $N\geq 0$ where $P_{j,k}$ is a polynomial of degree at most $k-1$,

$$R_N(x) = e^{-c_1\sqrt{\log x}} + \left(\frac{c_2 N+1}{\log x}\right)^{N+1},$$

and $c_1$ and $c_2$ are positive constants which may depend on $A$. This is Theorem 4 of Chapter 6.

In Theorem 5, he shows that a similar estimate holds for $\displaystyle{N_k(x):=\sum_{n\leq x, \ \Omega(n)=k} 1}$.

-
 Thank you very much! Is there a version of this result for $\sum_{n\le x,\Omega(n)=k}$ which I think Tenenbaum calls $\tau_k$? And is there a method for determining the polynomials? – Charles Aug 19 2010 at 6:29 The theorem is essentially the same for $\sum_{n\leq x, \Omega(n)=k}$, except that the polynomials are (possibly) different. It seems possible that you could determine the polynomials for small $k$. – Micah Milinovich Aug 19 2010 at 11:35

According to Dickson's History, Gauss, in a manuscript of 1796, stated empirically that the number $\pi_2(x)$ of integers $\le x$ which are products of two distinct primes, is approximately $x\log\log x/\log x$. Landau proved this result and the generalization $$\pi_{\nu}(x)={1\over(\nu-1)!}{x(\log\log x)^{\nu-1}\over\log x}+O\left({x(\log\log x)^{\nu-2}\over\log x}\right)$$ where $\pi_{\nu}(x)$ is the number of integers $\le x$ which are products of $\nu$ distinct primes. So that would be the status quo, as of 1919.

EDIT. Noting John's answer, and not having Tenenbaum's book, I looked for relevant papers by Tenenbaum, and found Adolf Hildebrand and G${\rm\acute e}$rald Tenenbaum, On the number of prime factors of an integer, Duke Math J 56 (1988) 471-501, MR89k:11084. The authors prove what the reviewer
(${\rm Aleksandar\ Ivi\acute c}$) calls a "remarkable asymptotic formula" for $\pi(x,k)$, the number of integers up to $x$ with exactly $k$ distinct prime factors. I don't have the energy to reproduce the lengthy formula here (nor the nerve to just cut'n'paste it from Math Reviews).

Another paper that looks like it may be of interest is Hsien-Kuei Hwang, Sur la repartition des valeurs des fonctions arithmetiques, J No Thy 69 (1998) 135-152, MR99d:11100. The author claims to completely characterize the asymptotic behavior of the number of positive integers up to $x$ with $m$ prime factors (counted with multiplicities).

-
I suppose that speaks to why the error is so bad -- it's off by (1 + O(1/log log x) instead of (1 + O(1/log x)) as in the case of the prime-counting function. – Charles Aug 18 2010 at 7:11
The Hildebrand & Tenenbaum paper is very good, thanks for the pointer. It gives good insight into why different cases are different. Unfortunately it's focused on improving the range of admissible $k$-values, which don't really concern me -- I care mostly about the case k = 2. I've downloaded the Hwang paper and have been reading through it (slowly; my French is passable but not good by any means). – Charles Aug 19 2010 at 17:08

I looked at $$\int_e^x\frac{(\log\log t)^{k-1}}{(k-1)!\log t}dt$$ to see if, empirically, the error was any less in the special case $k = 2,\ x = 2^n$ (semiprimes at powers of 2, as in A125527). Unfortunately the results were inconclusive. The error was smaller over the domain I checked: about half the error around a million, tapering down to a quarter less error at $2^{49}$. But everywhere I checked both estimates were too small, by significant relative factors.

Further, these errors did not seem to taper off much. The error in $x\log\log x/\log x$ went from 10% to 8% fairly smoothly, while the error in the integral reached an apparent relative maximum around $2^{40}$, staying between 5% and 6% the whole way. This seems fundamentally unlike the behavior with Li and $x/\log x$ where the error in the latter (wrt $\pi(x)$) quickly outpaces the error in the former.

-

The Wolfram MathWorld page for "Semiprime" (k=2) at http://mathworld.wolfram.com/Semiprime.html gives the following formula:

"A formula for the number of semiprimes less than or equal to $n$ is given by

$\pi_2(x) = \sum_{k=1}^{\pi(\sqrt{x})} [\pi(x/p_k)-k+1]$

where $\pi(x)$ is the prime counting function and $p_k$ is the $k$th prime (R. G. Wilson V, pers. comm., Feb. 7, 2006; discovered independently by E. Noel and G. Panos around Jan. 2005, pers. comm., Jun. 13, 2006)."

Curiously, the number of terms in the above sum, $\pi(\sqrt{x})$, is approximately $Li(\sqrt{x})$, which is the order of the main error term in the formula $\pi(x) = Li(x) + e(x)$ itself. Further, the value of $\pi(x/p_k)$ in the final term is also equal to $\pi(x/\sqrt{x}) = \pi(\sqrt{x})$.

Here is a follow-up question: Has there been any research about the distribution of primes and semiprimes together? One would expect the error term to be smaller than for either primes or semiprimes alone, because a region with fewer primes will tend to have more semiprimes, and vice versa.

-

This doesn't help, but it may entertain

-