Iwaniec, using the linear sieve, proved that $n^2+1$ can be a product of at most two primes infinitely often and furthermore a lower bound of the correct order of magnitude for the number of such integers $n$ is an expanded interval can be given.

My question is if there is a (possibly different) sieve that allows one to obtain an asymptotic in the case that a larger number of primes is allowed;i.e. letting $\omega$ stand for the number of prime factors and $$N_r(x):=\sharp\{n\leq x: \omega(n^2+1) \leq r\} $$ then is there a large but fixed value of $r$ such that one can prove an asymptotic for the quantity $N_r(x)$ ? I suspect that even correct upper bounds will be hard owing to parity issues but one can always hope.

  • 5
    $\begingroup$ Most of the numbers with $r$ prime factors have $r-1$ small prime factors and one large prime factor. Given that, I think it would be difficult to evaluate $N_r(x)$, since eventually you will be reduced to estimating primes in a quadratic sequence. I don't quite understand your last sentence: any sieve method will give an upper bound of the right order. Maybe you mean right constant as well? Finally there's a difference between counting numbers with $r$ prime factors, and weighting with $\Lambda_r(n)$. My comment applies to the first form (the question as written) and not the second. $\endgroup$ – Lucia Sep 15 '14 at 20:09
  • $\begingroup$ >Most of the numbers with r prime factors have r−1 small >prime factors and one large prime factor. That is interesting, what is the simplest theorem this phenomenon manifests itself? <any sieve method will give an upper bound of the right order> Apologies, I meant with the correct leading constant. $\endgroup$ – Captain Darling Sep 16 '14 at 18:09
  • 2
    $\begingroup$ I think I disagree that Iwaniec's lower bound is of the correct order of magnitude. The numbers he counts are either prime or products of two primes both of which are relatively large (they're bounded below by a power of $x$). I think this means that his bound is less than the true one by a factor $\log\log$. This is always the case with sieve methods since one is always counting numbers with no small prime factors. $\endgroup$ – Alastair Irving Oct 3 '14 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.