0
$\begingroup$

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?

  • 0
    @ErickWong : 2/3 because x = 1 and x = 2 is a solution.2012-10-12

1 Answers 1

1

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.

  • 0
    Dont underestimate yourself ;) You have 68 k !2012-10-12