FOM: more on probabilistic proofs
Don Fallis
fallis at u.arizona.edu
Fri Sep 18 18:40:49 EDT 1998
Clearly, an important function of conventional mathematical proofs is that
they allow the mathematical community to achieve consensus that particular
mathematical propositions are true (or, at least, that they are provable).
Joe Shipman suggests that probabilistic proofs such as Rabin's primality
test might also allow the mathematical community to achieve this sort of
consensus. This suggestion leaves us with two interesting questions.
The first question is: Will probabilistic proofs really allow the
mathematical community to achieve consensus? A number of worries have been
raised that suggest that Rabin's primality test in particular will not be
able to do the job:
(a) As Randy Pollack points out, the trace from running Rabin's primality
test is not (by itself) convincing evidence that a random source has been
used.
(b) As Steve Cook points out, it is not clear that there is convincing
evidence that psuedo-random number generators are as random as Rabin's
primality test requires.
Of course, with regard to (a), in most other sciences, what is actually
published in the academic journal is not (by itself) convincing evidence.
(After all, an unscrupulous scientist might have faked the data.) But
these other sciences manage to achieve consensus despite these
difficulties. I imagine that mathematicians would be able to do so in a
similar way.
Of course, with regard to (b), we could use a physical process instead as
Shipman suggests. (But then again, do we really have good reason to
believe that any particular physical process is as random as Rabin's
primality test requires?)
In any case, even if we could clearly establish that Rabin's primality test
will allow the mathematical community to achieve consensus, we would still
be left with a second important question: Is there any other indispensable
epistemic role (beyond consensus-building) that conventional mathematical
proofs play, but that probabilistic proofs cannot play?
It seems that mathematicians are committed to the answer being "yes."
After all, a statement (about the primality of a number) that has only been
confirmed using Rabin's primality test is unlikely to get published in the
"Annals of Mathematics" (even if we could sort out the psuedo-random number
generator worry).
But, if there is an indispensable epistemic role that conventional
mathematical proofs play, but that probabilistic proof cannot, then what is
it? This is the question that I pose in my article, "The Epistemic Status
of Probabilistic Proof", Journal of Philosophy, April 1997. And I am
inclined to think that there is no such indispensable epistemic role of
conventional mathematical proofs and that statements confirmed using
probabilistic proofs ought to get published in the "Annals of Mathematics."
(By the way, in my article, I discuss a probabilistic proof that does not
suffer from the psuedo-random number generator worry that Rabin's primality
test suffers from. Though, of course, it may have other ailments.)
take care,
don
Don Fallis
School of Information Resources
University of Arizona
More information about the FOM
mailing list