Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

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?

share|cite|improve this question
Please see T.. answer here:… – user9413 Jun 8 '11 at 16:26
1… – JavaMan Jun 8 '11 at 16:28
another related question:… – user9413 Jun 8 '11 at 16:43
up vote 25 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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.

share|cite|improve this answer

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)$$

share|cite|improve this answer

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

Would you like to answer one of these unanswered questions instead?

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