Do we really know the reliability of PrimeQ[n] (for $n>10^{16}$)?

I and a number of others have proved that there are no BPSW-pseudoprimes below $2^{64}$. This builds on the work of Jan Feitsma around 2009. In particular this means that, barring programming errors, PrimeQ is correct for all values below $1.844\cdot10^{19}.$

I think there is some confusion here (or at least that's how it seems to me, which is why I am writing this). Number theory is a part of mathematics and (arguably) not of the physical world. This means that certain things can be proved exactly and then (if we disregard the human problem of mistakes in proofs) they are "reliable". However, it is pretty easy to come up with statements ( "conjectures") in number theory that defeat all attempts to prove them yet counterexamples are equally hard to find. Such statements can be provably true, false (counter examples exist) but also they can be "true but unprovable" - meaning that neither counterexamples nor proofs will ever be found (of course that fact itself cannot ever be known). Can one speak about probability, reliability etc in such cases?

Strictly speaking: not at all. Thus PrimeQ is "reliable" only as far as it has been tested and nothing at all can be strictly said about its reliability for n larger than the numbers for which it has been tested. The same applies probability: there is no "strict" sense in which one can say that PrimeQ "probably" works for all n (or even "almost all"). The only reasons why people of probability etc in this context are psychological.

However, this does not mean that "empirical testing" of PrimeQ is useless. It of course means that the function is perfectly reliable for all n for which it has been tested. It is more convenient to use such a function that to store a huge list of known primes to look up every time you need to know if some number is a prime. PrimeQ is nothing more than a convenient replacement for a long list of known primes and testing it further simply makes this list longer. Another advantage of PrimeQ over such a list (of known primes) is that there is always some possibility that one day someone will produce a mathematical proof that PrimeQ always returns the right answer and then it will become 100% reliable. Most experts would say that the "probability" of this happening is small - but this is also only "psychology".

I just saw Daniel's comment. I have not seen R. Baillie and S. Wagstaff's paper so it maybe indeed true that there is a sense in which one can define the "probability" of such a counterexample and show that it is "small". One could then perhaps consider PrimeQ as "reliable" in this this particular sense beyond the numbers for which it has been tested. That, of course, would be useful for certain kind of applications but not for others (in particular not for asserting that a single large number that PrimeQ says is prime really is so).

Regarding the original question: it is not necessarily the case that Lucas pseudoprimes less than 1E16 are rare. The point is that, if you make a list of psp's base 2 and a list of Lucas psp's, then the two lists are observed to have very little, if any, overlap.

As for probabilities: In the Miller-Rabin test, if n is composite, then 3/4 of the bases are witnesses for the compositeness of n.

For the strong Lucas test, the corresponding probability (measuring (P,Q) pairs), is 11/15; see F. Arnault, "The Rabin-Monier Theorem for Lucas Pseudoprimes". Mathematics of Computation 66 (218) (April, 1997), pp. 869–881.