Asymptotic density of k-almost primes - MathOverflow

Asymptotic density of k-almost primes

2010-08-18T04:37:54Z

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

Answer by Gerry Myerson for Asymptotic density of k-almost primes

2010-08-18T05:10:57Z

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 by Micah Milinovich for Asymptotic density of k-almost primes

2010-08-18T18:22:35Z

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 by Charles for Asymptotic density of k-almost primes

2010-08-23T04:23:18Z

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 by Geoffrey Caveney for Asymptotic density of k-almost primes

2011-11-18T16:47:54Z

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.

Answer by Roger Boyle for Asymptotic density of k-almost primes

2013-01-08T21:24:51Z

This doesn't help, but it may entertain