# Primes of the form $n^2+1$ - hard?

I met a student that is trying to prove for fun that there are infinitely many primes of the form $n^2+1$. I tried to tell him it's a hard problem, but I lack references. Is there a paper/book covering the problem? Is this problem really hard or I remember incorrectly?

-
Please see T.. answer here: math.stackexchange.com/questions/4506/… – user9413 Jun 8 '11 at 16:26
en.wikipedia.org/wiki/… – JavaMan Jun 8 '11 at 16:28
another related question: math.stackexchange.com/questions/42195/… – user9413 Jun 8 '11 at 16:43

This is an incredibly difficult problem.

It is one of Landau's 4 problems which were presented at the 1912 international congress of mathematicians, all of which remains unsolved today nearly 100 years later.

-

This problem is hard in the sense that it is still unproven. I will provide a set of references, but little conclusive work (as far as I know) has been done on any of them.

This is a conjecture of Hardy; he later generalized it to say: if a, b, c are relatively prime, a is positive, and $(a+b)$ and c are not both even, and $b^2 - 4ac$ is not a perfect square (I know, quite a set of conditions) - then there are infinitely many primes $an^2 + bn + c$.

He does this on pg. 19 of his book.

I should note that it is proved (even in the same book) that there are infinitely many primes of the form $n^2 + m^2$ and $n^2 + m^2 + 1$. (I'm pretty sure).

There is another statement of this conjecture that is earlier - Are there infinitely many primes $p$ such that $p - 1$ is a perfect square? This is a conjecture of Landau, and it amounts to the same thing (but without Hardy's generalization). As far as I know, the greatest work is to show that there are infinitely many numbers $n^2 + 1$ that have at most 2 prime factors, and it's pretty intense.

Finally, there is a far stronger conjecture called the Horn Conjecture or the Bateman Horn Conjecture. It's a sort of generalization of many other conjectures.

-
Remark: fact that there are infinitely many primes of the form $n^2+m^2$ is (relatively) easy since every prime of the form $4k+1$ can be written this way (Fermat), and there are infinitely many primes of the form $4k+1$. (Dirichlet) – Eric Naslund Jun 8 '11 at 16:47
@Eric: I was more wondering about $n^2 + m^2 + 1$ - I've never actually seen that proof, and I can't think of one now.\ – mixedmath Jun 8 '11 at 18:02
I think it was proved in Acta Aritmetica many years ago, possibly by a Japanese mathematician. Wish I could narrow it down a bit more... – Charles Jun 28 '11 at 2:25
Found it: Y. Motohashi, "On the distribution of prime numbers which are of the form x^2 + y^2 +1", Acta Arithmetica 16 (1969), pp. 351-364. – Charles Aug 21 '11 at 21:45
Oh, and since it hasn't (apparently) been mentioned yet, Iwaniec proved that the primes of the form ax^2 + bxy + cy^2 + ex + fy + g are infinite unless the polynomial 'obviously' produces only finitely many (see his 1974 paper in AA for details) or if the polynomial reduces to a polynomial in one variable. So it includes x^2 + y^2 + 1 as a special case, but not x^2 + 1. – Charles Aug 21 '11 at 21:51

This is a sub-problem of the Bunyakovsky conjecture. I have an interactive form of it at The Bouniakowsky Conjecture. Let $f$ be an integer-coefficient irreducible polynomial with degree higher than 2, and let $k=gcd(f(0),f(1))$.

The conjecture: $f(n)/k$ always generates an infinite number of primes.

Some polynomials, like $x^{12}+488669$ seem to only sparsely make prime numbers, but so far no bounds are known for any of these polynomials.

-

If your interested, here is a heuristic argument I just thought up that gives the supposed asymptotic behavior of the number of primes equal to a square plus one less then or equal to a given quanity:

$$\sum_{n\leq x}\Lambda(n^2+1)=\sum_{n\leq x}\sum_{d\mid n^2+1}-\mu(d)\ln(d)=\sum_{n\leq x}\sum_{d\leq x}\sum_{n^2+1\equiv 0 \text{ mod } d}-\mu(d)\ln(d)$$ $$=\sum_{d\leq x}\sum_{n\leq x}\sum_{n^2+1\equiv 0 \text{ mod } d}-\mu(d)\ln(d)=\sum_{d\leq x}\sum_{k=0}^{d-1}\sum_{n\leq \frac{x-k}{d}}\sum_{(dn+k)^2+1\equiv 0 \text{ mod } d}-\mu(d)\ln(d)$$ $$=\sum_{d\leq x}\sum_{k=0}^{d-1}\sum_{n\leq \frac{x-k}{d}}\sum_{k^2+1\equiv 0 \text{ mod } d}-\mu(d)\ln(d)=\sum_{d\leq x}\sum_{k=0}^{d-1}\sum_{k^2+1\equiv 0 \text{ mod } d}-\mu(d)\ln(d)\lfloor{\frac{x-k}{d}}\rfloor$$ $$=\sum_{d\leq x}\sum_{k=0}^{d-1}\sum_{k^2+1\equiv 0 \text{ mod } d}-\mu(d)\ln(d)(\frac{x}{d}+O(1))\approx\sum_{d\leq x}\sum_{k=0}^{d-1}\sum_{k^2+1\equiv 0 \text{ mod } d}-\mu(d)\ln(d)\frac{x}{d}$$

$$=x\sum_{d\leq x}\frac{-\mu(d)\ln(d)f(d)}{d}$$

Where $f(d)$ counts the number of non congruent solutions $k$ modulo $d$ to $k^2\equiv -1 \text{ mod } d$

So that with $\chi$ the non principal character modulo $4$ we have that: $$f(n)=\sum_{d\mid n}\mu(d)^2\chi(\frac{n}{d})\iff\sum_{n=1}^\infty\frac{f(n)}{n^s}=\frac{L(s,\chi)\zeta(s)}{\zeta(2s)}$$

Then perhaps:

$$\sum_{n\leq x}\Lambda(n^2+1)\approx x\lim_{s\to +1}\sum_{d=1}^\infty\frac{-\mu(d)\ln(d)f(d)}{d^s}=x\prod_{p \text{ odd} }(1-\frac{\chi(p)}{p-1})$$

So that we might have:

$$\sum_{\substack{p\leq x\\p=n^2+1}}1\sim \operatorname{Li}(x^{1/2})\left(\prod_{p\equiv 1 \mod 4} \frac{p-2}{p-1}\right)\left(\prod_{p\equiv 3 \mod 4}\frac{p}{p-1}\right)$$

-

## protected by Community♦Jun 7 '12 at 18:44

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).