Asymptotic density of k-almost primes

Question

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 those 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)$$ and there are many more recent improvements along these lines.

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) https://arxiv.org/abs/1002.0442

[3] Pierre Dusart, "Autour de la fonction qui compte le nombre de nombres premiers" (1998) https://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)$).

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

As not necessarily proven results were asked for, I have found the following quite accurate:

$$N_k(x):=\ \mid\{n\leq x : \Omega(n)=k\}\mid \ \sim \Re\bigg(\frac{2^{1-k}\alpha e^{1+e}x\log(1+e+\log(2^{1-k}\alpha x))^{\beta}}{\beta!(1+e+\log(2^{1+e}\alpha x)}\bigg) $$ for $1 \leq k\leq \lfloor \log_2 (x) \rfloor$, where $\log_2$ is $\log$ base $2$, $\gamma $ is Euler's constant, $\beta=1+e+ \log \alpha +(1+e+ \log \alpha) ^{1/\pi}$, and$$ \alpha=\frac{1}{2}\ \rm{erfc}\bigg(-\frac{k-(2e^{\gamma}+\frac{1}{4})}{(2e^{\gamma}+\frac{1}{4})\sqrt{2}\ }\bigg)-2\rm{T}\bigg(\bigg(\frac{k}{(2e^{\gamma}+\frac{1}{4})}-1\bigg),e^{\gamma}-\frac{1}{4}\bigg)\\ $$ where $\rm{erfc}$ is the complementary error function and $\rm{T}$ is the Owen T-function.

In integral form, $$\alpha= \frac{1}{\pi}\int_{(-3+8e^\gamma)/(\sqrt{2}(1+8e^\gamma))}^\infty e^{-t^2}\rm{d} t +\int_0^{1/4\ -\ e^\gamma}\frac{e^{-(3\ -\ 8e^\gamma)^2(1+t^2)/(2(1+8e^\gamma)^2)}}{1+t^2}\rm{d} t.$$

As $k\rightarrow \infty$, $\alpha\rightarrow 1$, so

$$\lim_{k \rightarrow \infty}N_{k}(x \cdot 2^{k-1})\sim\frac { {e^{e+1}} x\log\log( {e^{e+1}} x)^{\beta}}{\log( {e^{e+1}} x)\beta!}, $$ where $\beta=\log(e^{e+1})+\log(e^{e+1})^{1/\pi}.$

For $k\leqslant 3$, improvements to the above can certainly be made, but as $k\rightarrow \infty$ (or more correctly, as $k\rightarrow \lfloor \log_2 (x) \rfloor$), the formulae above, as far as have been tested, seem to be fairly accurate.

For convenience, I include the following Mathematica code:

cdf[k_, x_] :=
Re[N[
(2^-k E^(1 + E) x Log[1 + E + Log[2^-k x (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])]]^(1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] +4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])] + (1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])])^(1/\[Pi])) (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma]))/((1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])] + (1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])])^(1/\[Pi]))!
(1 + E + Log[2^-k x (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2] (1 + 8 E^EulerGamma))] +
4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma), 1/4 - E^EulerGamma])]))]];

landau[k_, x_] := N[(x Log[Log[x]]^(-1 + k))/((-1 + k)! Log[x])];

actual[k_, x_] := N[Sum[1, ##] & @@ Transpose[{#, Prepend[Most[#], 1], PrimePi@
Prepend[ Prime[First[#]]^(1 - k) Rest@FoldList[Times, x, Prime@First[#]/Prime@Most[#]],
x^(1/k)]}] &@Table[Unique[], {k}]];

I warmly welcome any criticism or comments on the above, and apologise in advance if I have made any serious errors.

Note: Table code included as requested:

a = 7;
x = 10^a;
kk = 20;
TableForm[Transpose[{Table[x, {x, 1, kk}], Table[Round[landau[k, x]], {k, 1, kk}], 
Table[Round[cdf[k, x]], {k, 1, kk}], Table[actual[k, x], {k, 1, kk}]}], 
TableHeadings -> {None, {"k  ", "Landau", "CDF   ", "Actual"}}, 
TableSpacing -> {2, 3, 0}]

Answer 6

This doesn't help, but it may entertain

Answer 7

The Wolfram MathWorld page for "Semiprime" ($k=2$) at https://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 $\operatorname{Li}(\sqrt{x})$, which is the order of the main error term in the formula $\pi(x) = \operatorname{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.