# 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?

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.\ – davidlowryduda 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)$$

• Would you please introduce some books to study so that I can understand your answer. I'm very interested in studying such problems but even after finishing Introduction to Analytic Number Theory by Apostol and his more advanced book Modular Functions and Dirichlet Series in Number Theory I still can't understand no papers on prime number theory. Thanks. – user231343 Jul 28 '17 at 14:48
• @Edi If you've thoroughly read "Introduction to Analytic Number Theory by Apostol" my answer really shouldn't be that hard to understand. He talks about techniques for interchanging sequences in a summation like I did at the start very early on, introduces the vonmangoldt function on the chapter about arithmetic functions, introduces Euler products later on too, he further introduces $L$ functions during the proof of Dirichlet's theorem on primes in arithmetic progressions and he also gives multiple proofs I believe of the prime number theorem (at least one, at the end using complex analysis). – Ethan Mar 23 '18 at 13:16
• Also Terry Tao has a blog post where hes talking about estimates on sums of the form $\sum_{n\leq x}d(P(n))$ where $P$ is a polynomial that satisfies $P(x)\in \mathbb{N}$ for every $x\in \mathbb{N}$ (it might be less general, in any case at the least hes looking at a broad number of irreducible polynomials with integral coeiffients). Now early on he works through an example estimating the sum $\sum_{n\leq x}d(n^2+1)$ (explaining how estimates for these sums are easy when $P$ is quadratic) and uses similar techniques to the ones I did at the start, you might be interested in that. – Ethan Mar 23 '18 at 13:20
• @Edi *Easy that is for the divisor function at least, certainly not the vonmangoldt function otherwise we'd easily have a proof of what I wrote above. I mean in general for the vast number of commonly used arithmetic functions $f:\mathbb{N}\to \mathbb{C}$ the problem of estimating an asymptotic for $\sum_{n\leq x}f(P(n))$ is an open problem when $P$ has degree greater then two. While for the vanmgoldt function estimating any sort of sum like this tends to be equivalent to powerful statements about the primes so its not an easy task. – Ethan Mar 23 '18 at 13:31