It is a long-standing conjecture (probably just as old as the twin prime conjecture, which has gotten a lot of attention as of late since Zhang and Maynard's breakthrough results this year) that there exist infinitely many primes of the form $x^2 + 1$. The first few primes of this shape are $5, 17, 37, 101, \cdots$. Of course, no one has been able to prove this theorem, but perhaps if one relaxed the problem one would be able to obtain positive results.

So my question is: what is the least value of $n$ such that one can prove that infinitely many elements of $P_n$ (where $P_n$ is the set of numbers with at most $n$ prime divisors) are of the form $x^2 + 1$?

A similar result to this is a result of Selberg who proved that the polynomial $x(x+2)$ assumes values which have at most 7 prime factors, in particular there exist infinitely many elements of $P_7$ which are of the shape $x(x+2)$.

The parity problem in sieve theory would likely prevent any progress on obtain a lower bound for primes instead of almost primes.

Any insight would be appreciated.

  • 3
    $\begingroup$ Showing $n^2+1$ is prime infinitely often was first raised by Euler in a letter to Goldbach (1752), where he noted that $n^2 + 1$ is often prime for $n$ up to 1500. $\endgroup$ – KConrad Dec 7 '13 at 22:54
  • 1
    $\begingroup$ Is 12 in $P_2$? $\endgroup$ – Emilio Pisanty Dec 8 '13 at 2:22

Yes, Iwaniec proved in "Almost primes represented by quadratic polynomials" (Invent. math. 47(1978) 171–188), that if $f$ is a quadratic polynomial with $f(0)$ an odd integer, then $f$ contains infinitely many elements of $P_2$.

For an arbitrary polynomial $f$ that is irreducible and doesn't have a fixed prime divisor, one can say that $f$ represents infinitely many elements of $P_n$, where $n=1+\deg f$. This was proven by Buhstab in "A combinatorial strengthening of the Eratosthenian sieve method", Usp. Mat. Nauk 22, no. 3, 199–226.


It is known that $n^2+1$ is infinitely often a number with at most $2$ prime factors, this is a result of Iwaniec, Almost-primes represented by quadratic polynomials, Invent. Math. 47 (1978), no. 2, 171–188. It is possible to get numbers with at most $3$ prime factors by a routine application of the weighted sieve, reducing this to $2$ requires a bilinear form of the error term and a bilinear level of distribution for the values of $n^2+1$. You can find a proof of the at most $2$ prime factors result in Friedlander and Iwaniec's book "Opera de Cribro".


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.