FOM: probabilistic rigor

[JoeShipman@aol.com]

It is strange that Odlyzko doesn't recognize the significance of the
difference between the two notions of "probabilistic proof".  The best way I
can think of to make the difference clear to him is to find an example of a
numerical predicate whose frequency is closely approximated by a formula for
numbers in a feasible range but greatly diverges from it afterwards.  Can
anyone suggest a natural example?

I am not sure primality tests are quite as practically feasible as you claim.
There is a deterministic "almost polynomial time" (exponent is loglog of the
input size rather than constant) algorithm and a probabilistic one which fits
your description (never makes an error and *usually* runs quickly) whose worst
case is "almost polynomial time" but with a better constant in the exponent
than the deterministic case, but the *usually* means "always for most inputs"
rather than "most of the time for all inputs".  There is also a test which
runs in polynomial time with randomized input which has an exponentially small
probability of error, and a test which runs in polynomial time and is always
correct if the Extended Riemann Hypothesis is true.  But I am not aware that
there is a test for which it has been unconditionally proven that 
 1) it never makes an error
 2) there is a polynomial P such that for *any* input to be tested for
primality, the probability it does not finish within P(inputsize) steps is
exponentially small.

Such an algorithm would certainly be the next best thing to a true P-time
algorithm; but can you give me a reference that such an algorithm actually
exists for testing primality? 

-- JS