MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 19 down vote accepted

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.

share|cite|improve this answer

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".

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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