# On the probability that $2x^2 + 1$ is prime (quadratic residue)

I tried to compute the multiplicative inverse of the probability that $2 x^2 +1$ is prime.
(I'm aware that proving there are infinitely many such primes is not done yet, but let's ignore that for now).
I know it should be around $2 \log(x) - 1$ from the PNT.
Using the sieve $(1-1/2)(1-1/3)(1-1/5) ... (1-1/p)$ over the primes $p$ we get $O(\log(x))$ actually $2C\log(x)$ with $C$ mertens constant. This is slightly worse but $C$ is not so far from $1$.

However when I tried differently I got confused.

I tried to sieve by using quadratic residues.

Let $p_n*$ be a prime such that it has a solution $x$ to $2 x^2 + 1 = 0 \pmod p$.

I believe that probability is about $1/2$.

Then I sieve : $(1-1/2)(1-1/p_1*)(1-1/p_2*)...(1-1/p_n*)$

And consider the worst case and average scenarios.

This does not agree well with $2 \log(x)$ even after dividing by $C$!??

What did I do wrong?

-
I removed the tag residue-calculus, which is something else. When a tag doesn't have a tag wiki, you may be able to tell from other questions tagged with it what it's about. – joriki Oct 12 '12 at 15:53
I did not find tag quadratic residue , I guess I took the complex analysis residue tag hmm Sorry and thanks. – mick Oct 12 '12 at 15:55
I don't understand the reasoning behind your sieve; could you explain? Also, the $O(\log x)$ probability doesn't come out directly from $\prod_n(1-1/p_n)$, since it's not obvious where to cut the product off; how did you do this for your sieve? – joriki Oct 12 '12 at 15:56
The lack of understanding of the reasoning behind your sieve that I expressed is more fundamental than that. You've offered no reasons to think that the product you wrote down should yield the desired probability. – joriki Oct 12 '12 at 16:12
@mick This does not explain any of your terms $(1-1/p_n^*)$ nor even the initial $(1-1/2)$ term. What is the probability that $2x^2+1$ is 0 mod 3? – Erick Wong Oct 12 '12 at 16:20

If I understand your thoughts behind this approach correctly, then the error lies in taking into account that some primes don't allow solutions but not taking into account that for the remaining primes the probability of $2x^2+1$ being composite is doubled. That is, either $-2^{-1}$ is a quadratic residue mod $p$ or not; if it isn't, the probability for $2x^2+1$ to be divisible by $p$ is $0$, but if it is, then it's $2/p$, since there are two different residues for $x$ that satisfy the equation.
Also, even if your approach had been right, there wouldn't have been any contradiction; it's perfectly possible for some forms of numbers to have a different probability of being prime if you take their special form into account than if you don't. As an extreme case, you can calculate the probability for $2x$ to be prime as $1/\log(2x)$, but of course if you take the form of $x$ into account it's zero. As a less extreme case, $2^n-1$ has a non-zero probability of being prime that's different from $1/\log(2^n-1)$ if you take its form into account, since the residues follow periodic patterns.
Thanks for the answer , and yes you got it right. 2 comments : 1) if its 2/p than $(1-1/2)(1-2/p_1*)(1-2/p_2*)$... should be the correct sieve ?? 2) your comforting talk about $1/log(2x)$ is sweet :) , however I know in this case that the probability is $1/(2 log(x) -1)$ and that is a big difference ! – mick Oct 12 '12 at 18:29
@mick: 1) I think so. 2) What does that mean? As far as I'm aware, that probability is only defined asymptotically; in what sense is the probability $1/(2\log x-1)$? (By the way, you can get proper formatting for the log (or any similar function like sin and exp) using \log.) – joriki Oct 12 '12 at 18:59