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?
Primes of the form $n^2+1$ - hard?
-
0another related question: http://math.stackexchange.com/questions/42195/generalization-of-dirichlets-theorem/42198#42198 – 2011-06-08
4 Answers
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.
-
2Oh, 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. – 2011-08-21
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)$
-
0@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. – 2018-03-23