Let $P_k$ be the set of integers with at most $k$ prime factors (counting with multiplicity, say). There is an almost-prime number theorem which gives asymptotic estimates of the size of $P_k$, and (presumably) one can formulate a question analogous to the Riemann Hypothesis on the size of the corresponding error term. My question is: what are the best known unconditional estimates? In particular, if $k$ is large (say $100$) can we obtain a significantly better error term than we know for $P_1$ (say: $n^{1-\varepsilon}$)?

I am also interested in the same question if $P_k$ is replaced by $P'_k$, the set of integers $n$ with at most $k$ prime factors (with multiplicity) none of which is smaller than $\log n$. (Here I am not too concerned about the precise growth rate $\log n$; larger is presumably unhelpful, but $\log\log n$ or $\log_* n$ would be fine)

I would especially be interested in answers of the form 'this question is likely hard because...'.

EDIT: The answer I would like is something of the form $|P_k(n)|=m_k(n)+e_k(n)$ where $m_k(n)$ is the `main term' and $e_k(n)$ the error, and the property I would like is not that $m_k(n)$ should be the simplest function which is $(1+o(1))|P_k(n)|$, but rather $m_k(n)$ should be whatever function with nice analytic properties allows us to make $e_k(n)$ small. For the kinds of things I want to do, I wouldn't need an explicit formula for $m_k(n)$; the approximation which exists (see answers below) and 'niceness' is enough. Let me not try to say exactly what 'nice' should be, since it's not too critical; certainly it should allow us to show (by the obvious argument) that members of $P_k$ have about the same density on the interval $[n,2n]$ as in any sub-interval of length at least $n^{\theta+\varepsilon}$ if we are given $e_k(n)=O(n^\theta)$, for any $\varepsilon>0$ and sufficiently large $n$.

  • $\begingroup$ As stated and edited, the question still allows for $|e_k(n)|\le1$, since one can take as $m_k(n)$ a nonexplicit smooth approximation to $P_k(n)$. $\endgroup$ Nov 4, 2015 at 17:55
  • $\begingroup$ No, one cannot: a smooth approximation can (and will) vary too unpredictably, so that it doesn't grow by (up to polylog-factors) $n^{\varepsilon}$ on all intervals of length $n^{\varepsilon}$, and then you can't use the obvious argument mentioned in the edit to establish the existence of primes in such intervals. $\endgroup$
    – user36212
    Nov 5, 2015 at 10:41
  • $\begingroup$ I wouldn't have any problem with non-explicit approximations, but they have to come with a guarantee that this kind of bad behaviour doesn't occur. This is already known not to be possible (long prime gaps) if $e_k(n)$ is to be bounded by too small a power of $\log n$. $\endgroup$
    – user36212
    Nov 5, 2015 at 10:44
  • $\begingroup$ That's simply false. Any step function can be approximated arbitrarily closely by smooth functions. Maybe you have a more restricted family of functions in mind when you say "smooth function"; in that case, you should define what you mean precisely. $\endgroup$ Nov 5, 2015 at 18:31
  • $\begingroup$ I didn't say 'smooth' in the edit (or the original question). I can certainly agree 'nice' is not the best terminology. If we take a smooth approximation, sometimes it will have gradient close to zero, sometimes very large. This is not the feature I want. I might get more demanding if you can supply this, but: I want to have a guarantee that $m_k(n)+E<m_k(n+t)-E$, where $t$ is some 'small' quantity and $E$ is the maximum absolute value of $e_k(x)$ on the interval $[n,n+t]$. Since, more or less, $m_k(n)$ grows linearly, this is more or less saying that $|e_k(n)|=o(t)$. $\endgroup$
    – user36212
    Nov 6, 2015 at 19:34

2 Answers 2


The typical asymptotic formula, for fixed $k$, is $$ \#\{n\le x\colon \Omega(n)=k\} = \frac{x(\log\log x)^{k-1}}{(k-1)!\log x} + O_k \bigg( \frac{x(\log\log x)^{k-2}}{\log x} \bigg). $$ In this form, the error term is likely to be best possible! Presumably the "correct" main term would have the form $$ \frac x{\log x} P_k(\log\log x), $$ where $P_k(t)$ is a polynomial whose leading term is $\frac{t^{k-1}}{(k-1)!}$. Only in this form would we potentially be able to save a power of $x$ in the error term.

Check out Tenenbaum's book (the chapter on Selberg–Delange) to see if this application is in there, or if it can be derived from that method, perhaps using the function $\Lambda_k$.

  • $\begingroup$ To understand better what you mean with "correct" could you state what the "correct" main term in your sense is for the primes? $\endgroup$
    – user9072
    Oct 29, 2015 at 18:17
  • 1
    $\begingroup$ It would be li$(x)$. Which is a good point - perhaps the correct main term for the almost primes would be li$(x)$ times the appropriate polynomial in $\log\log x$. $\endgroup$ Oct 30, 2015 at 3:04
  • $\begingroup$ See my answer to mathoverflow.net/questions/35927/… . $\endgroup$
    – Lucia
    Oct 30, 2015 at 4:02
  • $\begingroup$ Thanks - I suppose I should edit the question to make clear what I would like. I don't find it in Tenenbaum, anyway (Lucia's answer to the other question seems to address nicely the part of the answer I am less interested in :-( ). $\endgroup$
    – user36212
    Oct 30, 2015 at 9:40

Self-answer, since the answer given addresses the question I didn't mean to ask - I would appreciate it if experts tell me whether or not my attempts at finding out by google and guesstimated calculations make sense.

The situation seems to be:

It is believable (depending on how much you trust Cramer-type models) that the decomposition I would like actually holds even with $e_k(n)$ growing poly-logarithmically (for any $k$ including $1$, so counting the primes). For many practical purposes this is much stronger than the Riemann Hypothesis, but it's actually consistent with the Riemann Hypothesis failing (?), even quite badly, as that conjecture would make some statement stronger than 'nice analytic properties' about the main term.

Probably the equivalent to the Riemann Hypothesis for almost-primes (i.e. proving we can obtain $|e_k(n)|=O(n^{1/2+\varepsilon})$ for each $\varepsilon>0$ is easier than for primes, but 'easier than something very very hard' is not too helpful.

As to unconditional results, nothing seems to have been worked out but standard methods should give results for $|P_k(n)|$ of comparable strength to $|P_1(n)|$ (?).

Where one does gain something is if one asks the corresponding question (correctly phrased, which probably means counting with weight and looking for a main term of order $n$) with respect to a non-trivial Dirichlet character, as then the nastiness caused by potential Siegel zeroes goes away, so for example the counting function for almost-primes in arithmetic progressions has effective error bounds (?), even when the common difference is polylogarithmic in $n$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .