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
    I removed the tag [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.2012-10-12
  • 0
    I did not find tag quadratic residue , I guess I took the complex analysis residue tag hmm Sorry and thanks.2012-10-12
  • 0
    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?2012-10-12
  • 0
    As usual around up to the sqrt.2012-10-12
  • 0
    I edited because I forgot to mention that I was working with the inverse of the probability.2012-10-12
  • 1
    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.2012-10-12
  • 0
    If there is no modular solution , then there is no integer solutions so we do not get 0 mod those primes , hence for those primes we do not sieve since 0 mod p is impossible anyway.2012-10-12
  • 1
    @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?2012-10-12
  • 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
    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 !2012-10-12
  • 0
    @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`.)2012-10-12
  • 0
    at 1) you answered : I think so. I ofcourse would like to see a proof. It seems like an interesting identity if true.2012-10-12
  • 0
    ...even if just approximately or statisticly true...2012-10-12
  • 0
    @mick: I don't know how to prove such a thing beyond the arguments that we've already discussed.2012-10-12
  • 0
    Dont underestimate yourself ;) You have 68 k !2012-10-12