FOM: Probabilistic proofs

[Joe Shipman]

Fallis:
<<It seems to me that mathematicians might have compelling inductive
evidence
of the reliability of a probabilistic proof in just the same way that
scientists can have compelling inductive evidence of the reliability of
some scientific procedure.  It may be the case that we do not have
available to us such evidence for the reliability of Rabin's primality
test
and, thus, that we have to rely on a conventional mathematical proof.
However, this is different from saying that we always HAVE to have a
conventional proof of the reliability of a probabilistic proof in order
for
us to achieve consensus (or some other epistemic benefit) with the
probabilistic proof.  (And this was how I interpreted your statement on
9/16 that treating probabilistic proofs as proofs requires "underlying
completely rigorous proofs that [the probabilistic] algorithms are
correct.")
...
There is an accepted place in mathematics for probabilistic proofs and
other forms of what Polya referred to as "plausible reasoning."  Such
techniques are often useful for determining what propositions are likely
to
be true so that mathematicians can then go on and try to actually (i.e.,

conventionally) prove them.  However, for most mathematicians, that is
the
extent of the usefulness of probabilistic proofs; probabilistic proofs
are
only fit to be published in the "Journal of Experimental Mathematics."
>>

I think you're ignoring a critical distinction here.  Rabin's algorithm
is backed by a real
proof; the only reason not to believe that a number is prime after it
has passed Rabin's
test for 500 randomly chosen witnesses (with the random input taken from
a published
table of random numbers generated by a physical process) is that you
have somehow
made a mistake in running the algorithm (or else that the Universe was
in a vast
conspiracy against you that affected the random numbers in the published
table which
were generated before you chose the number to be tested for primality).
The degree of
subjective certainty that the number is prime is comparable to one's
faith that technology
generally works; all of us who ever step into an airplane bet our lives
on the proper
functioning of a technological system, and I submit that our faith that
a computer
running Rabin's test for us has operated properly is of comparable
magnitude.

This is a much stronger confidence than we have in "plausible reasoning"
a  la Polya.
We have very strong empirical evidence that the Riemann hypothesis is
true, but it isn't
of the same magnitude and does NOT deserve to be called a "probabilistic
proof".  (In
particular, it doesn't lead to any numerical bound on the probability
that the hypothesis is
true, while Rabin's test does!)  I would not bet my life against $1000
that the Riemann
hypothesis is true; I would make such a bet for the primality of a
number that had
passed Rabin's test with 500 witnesses on my computer and the computers
of two
referees who independently verified the calculation [this is the level
of certainty you'd
find in a journal article].  The ONLY differences between the subjective
certainty of an
"n is prime" statement that has been so verified and published and the
subjective
certainty of a computer-aided but deterministic proof such as Appel and
Haken's are
that
1) The "n is prime" statement may be wrong because of bad luck with a
probability between 0 and 2^-1000
2) The Appel-Haken proof verification is significantly more complex
(both the "conventional piece" which is more complex than Rabin's proof
and the "computer piece" which is more complex than running Rabin's
algorithm).

So it seems the "epistemic role" of a "probabilistic proof" in my sense
is much closer to that of the (publishable) Appel-Haken
four-color-theorem proof than that of an
(unpublishable-except-in-the-Journal-of-Experimental-mathematics)
heuristic "plausible reasoning" proof.  It is still possible to reject
such a probabilistic proof on the grounds that it is out of place in the
journal in question which only deals in traditional proofs, but not on
the grounds that the claimed result is epistemically less certain.

-- Joe Shipman