# Status of the $x^2 + 1$ problem

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.

• 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. – KConrad Dec 7 '13 at 22:54
• Is 12 in $P_2$? – 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".