FOM: Consensus vs Indubitability

[Don Fallis]

At 09:52 PM 9/18/98 EDT, Shipman wrote:
>In a message dated 9/18/98 6:21:11 PM Eastern Daylight Time,
>fallis at u.arizona.edu writes:
>
><< Why does our evidence that the probabilistic proof is reliable have to
be a
> conventional mathematical proof?  Why can't it be probabilistic proofs all
> the way down - as long as the probabilistic proofs allow for consensus?
>  >>
>
>I find it very hard to imagine how this might work without some core layer of
>non-probabilistic logical foundations, but this is sufficiently intriguing
>that I would like to see you explicate the possibility of "probabilistic
>proofs all the way down" further. 

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.")

Shipman:
>I agree with you that statements confirmed probabilistically should not be
>disqualified fromm "Annals of Mathematics"; but what makes you suppose that
>they are?  Does anyone know of any examples of probabilistic proofs that have
>appeared in major journals or been rejected from them because they were
>probabilistic?  

I do not know of any probabilistic proofs that have been submitted to, or
rejected by, major mathematics journals.  (I too would be interested in
hearing about any such cases.)  Nevertheless, it seems pretty clear to me
that the standard line among mathematicians is that probabilistic proofs
are not conclusive in the way that conventional mathematical proofs are and
should not be published in major journals.

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."    

When Appel and Haken published their proof of the four-color theorem, it
was pretty much only philosophers (principally, Tymoczko) who questioned
the advisability of publishing computer proofs in major mathematics
journals.  However, when the idea of publishing probabilistic proofs is
brought up (see, e.g., Doron Zeilberger, "Theorems for a price: tomorrow's
semi-rigorous mathematical culture", Notices of the AMS, 1993), it is
mathematicians who vociferously object (see, e.g., George Andrews, "The
death of proof? Semi-rigorous mathematics? You've got to be kidding!",
Mathematical Intelligencer, 1994).  In fact, Carl Pomerance explicitly
rejects the idea of using Rabin's primality test to prove that a number is
prime (see his "Recent developments in primality testing", Mathematical
Intelligencer, 1981).

(There are certainly some mathematicians, such as Zeilberger, who would
consider some probabilistic proofs to be publishable, but this is not the
standard line.)

Shipman:
I can't think of any interesting candidates for probabilistic
>proof that are not delta_0 (i.e. previously reduced to a finite problem),
>though occasionally a delta_0 result is sufficiently interesting to be
>publishable (nonexistence of finite projective planes of order n for some
n, a
>value for a Ramsey number, the existence of a finite simple group of a
>particular order).  Can you give some additional examples of probabilistic
>proofs besides the ones Steve Cook mentioned (Miller/Rabin, Berlekamp,
>Schwartz)? -- Joe Shipman

A standard reply to the suggestion that probabilistic proofs are as good as
conventional proofs is to note that no one has yet been able to "prove"
anything interesting with a probabilistic proof.  (Admittedly, the
probabilistic proof that I discuss in my article is also delta_0.  It is a
technique for "proving" that there is no Hamiltonian path in a given
directed graph.  The technique is based on Leonard Adleman's DNA
computations.)

However, several mathematicians (such as Zeilberger) have predicted that
there are going to be more and more results that it will not be feasible
(or possible) to establish with conventional mathematical proofs.  But not
being a mathematician, I am not in a position to evaluate the accuracy of
their predictions.

In any case, the absence of exciting results that are only provable by
probabilistic proofs does not show that conventional mathematical proofs
can play an epistemic role that probabilistic proofs cannot play.  (In
other words, it does not show that there are good grounds for
mathematicians' refusal to treat probabilistic proofs as anything more than
heuristic tools.)  And, as a philosopher, I find this a very interesting
conceptual question even if it does not have an immediate impact on the
practice of mathematicians.

take care,
don


Don Fallis
School of Information Resources
University of Arizona