Isn't the estimate for the smallest counterexample of the BPSW-test far too optimistic?

Question

Here :

http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html

it is described how the BPSW-test was verified. If I understand the description right, the test was circular because intermediate probable primes were tested with this test.

Despite of this, it is estimated that the smallest counterexample should have at least $10\ 000$ digits.

The argument apparently is that no one found a counterexample during some years. But counterexamples are surely extremely difficult to find, moreover, I doubt that many people actually searched for counterexamples.

Isn't this estimate far too optimistic ?

I read an article giving a heuristic argument that for every $\epsilon>0$ and sufficiently large $x$ the number of counterexamples should be much larger than $x^{1-\epsilon}$. Of course, this does not rule out that the largest counterexample is huge.

In fact there are indications that counterexamples are very rare, but the estimate in the article seems unrealistic to me.

An additional question : Considering the mathworld-article, how sure can we be that the BPSW-test is correct for all numbers upto $2^{64}$ (which seems to be widely believed) ?

Answer 1

Determinism to $2^{64}$

This has been done with the Galway/Feitsma database of all 64-bit base-2 pseudoprimes. To my knowledge nobody has independently reproduced this data either with the same methods or different ones. Even with their methods for reducing the search space, it is a massive amount of computation. Naive brute force suffices up to $2^{50}$ or thereabouts, but that's a small portion of the 64-bit range.

They have described the methods used, and a few people have looked closely at them and believe it is a sound method. The code they used was reviewed by more than one person and some double checks were performed. Independent lists up to $10^{13}$ have been made but I haven't seen anything past that (the lists up to $10^{15}$ and $10^{17}$ were by the same authors of the list to $2^{64}$).

I have tested numerous variations of Lucas and Frobenius tests using the SPSP-2 list and have found no correctly coded variation in use that has a counterexample. So, on the assumptions that base-2 pseudoprime database is correct and the BPSW test is implemented correctly, then we know there are no 64-bit counterexamples.

By the way, Khashin has a Frobenius variant that he recently showed, using different methods, has no 64-bit counterexamples. He has slightly changed his test from his 2013 publication and his 2017 talk. The proofs rely extensively on computation which have not been reproduced or examined by others (to my knowledge). He is also, in my opinion, unwarrentedly optimistic about larger counterexamples (he believes there are none). There seems to be no performance reason to prefer this method.

Larger counterexamples

Pomerance gives an argument for counterexamples existing.

Various projects have been performed to specifically look for counterexamples. Chen and Greene have at least one paper that describes directed searches for a counterexample to a weakened version of the BPSW test, without success. This consists of a fairly large set of primes, with the idea that some subset product has a good chance of being a counterexample. Here is the first sentences of the conclusions section of their 2001 paper:

To date, the \$620 appears to be safe. Unless an efficient scheme to search a space of size $2^{1500}$ is found, or an approach other than that suggested by Pomerance can be found, the problem of constructing a counterexample appears to be intractable.

Jon Grantham has given some talks over the last 15 years, including this one in 2013, that describe similar searches. My interpretation is that there are some known sets with fewer than 1200 primes, some subset of which has a product that is likely to be a counterexample. No subset has yet been shown to be one, and the space is far too large for computation to cover.

Estimate of smallest counterexample

As others have said, I don't think this has any supporting evidence other than a very large number of trials. We know counterexamples are rare, but there are a lot of numbers.

Primo has been in daily use on many machines for over 15 years. ECPP constructs a chain of primes, each one containing a step of "if $p_i$ is prime, then the following data shows that $p_{i+1} > p_i$ is prime". This chain of is made until the first prime is small enough to prove using simple methods like BPSW or small SPSP sets such as Jaeschke 1994. ECPP finds these values, which can then be verified much faster as there is no searching or polynomial root finding needed. As part of running Primo as well as doing a verification step, a BPSW test is performed on candidates. If any of these intermediates were identified as prime by BPSW but ECPP failed to prove them, this is clearly logged. So far no such numbers have been identified.

Conclusion

BPSW variants have been solidly tested for 30+ years with no counterexample found. It is used millions of times daily in many applications. On the assumption of the Galway/Feitsma database, there are no 64-bit counterexamples. This is fairly well believed.

Some directed searches by some really smart people have been made to find counterexamples, with no success so far. In combination with the lack of random counterexamples, this gives a great deal of confidence in the results for large numbers. This is a big barrier to any application considering a different far-less-tested method such as a Frobenius variant.

But there is no proof nor even a statistical argument for a expected size of the smallest counterexample. I don't even know of any better bounds than the simple $1/4 \times 1/8$ for a combination M-R + ES Lucas test, which empirically is clearly too high.