FOM: More on conclusiveness of proofs

[Don Fallis]

At 04:26 PM 12/17/97 +0100, Randy Pollack wrote:
>However I disagree with Shipman's comments that randomized proofs
>should be as convincing as conventional proofs.  The reason is that a
>conventional proof itself is the evidence for our belief.  I can
>discuss a particular proof with colleagues and independent referees.
>There is no "proof" that can be discussed when we use Rabin's
>algorithm.  The trace of a probabilistic proof is not convincing, as
>it is the "randomness" of the choices that is important; I must watch
>you flip the coins.  Once you write down the choices, they could just
>as easily have been carefully selected to give the desired outcome.

It is true that the trace of a probabilistic proof (unlike the trace of a
deterministic proof such as the proof of the four-color theorem) cannot by
itself provide convincing evidence for the truth of a theorem.  We also
need to know that the random choices really were made by a truly random
process.  However, this is just a special case of something that we always
need to know when we give a computer proof (and do not have a trace of that
proof).  Namely, we have to good evidence that the computer performed the
algorithm correctly.  For instance, that it added 4 to 3 and got 7 when it
was supposed to, that it picked a number at random between 1 and 100 when
it was supposed to, etc.

Unfortunately, if we use a (deterministic) random number generator
(hereafter RNG) to supply "random" numbers to our randomized algorithm,
then we are pretty sure that the computer did NOT pick a number at random
between 1 and 100 when it was supposed to.  Of course, an RNG is just about
as good as a truly random process as long as we have good reason to believe
that the RNG is just as likely to pick, for instance, witnesses to
compositeness in the Rabin test as is a truly random process.  But do we
have good reason to believe that this is the case?  In fact, do we even
have good reason to believe that some physical process (say radioactive
decay or flipping coins) is a truly random process?  (After all, there are
_deterministic_ theories of quantum mechanics that are as descriptively
adequate as are the stochastic theories.)  Do we at least have good reason
to believe that some physical process is as likely to pick witnesses as is
a truly random process?  Where is the scientific and/or mathematical
evidence for these claims?  The lack of evidence might to give us reason to
suspend judgment on the results of a probabilistic proof.

Nevertheless, scientists believe a lot of things for which they do not have
direct experimental confirmation.  In fact, they HAVE to believe a lot of
such things.  For instance, in order to conclude on the basis of a
controlled experiment that a certain drug slows down reaction time, I have
to assume that a lot of things that I did not control for (such as the eye
color of the subjects) do not affect reaction time (and I cannot control
for everything).  I have to do this even though I have no direct
experimental confirmation of the claim that eye color does not affect
reaction time.  Even though they have no direct experimental confirmation,
scientists do have good theoretical grounds for the claim that eye color
does not affect reaction time (and presumably for the claim that
radioactive decay is just about as likely to pick witnesses as is a truly
random process).

Now, while scientists have compelling reasons to accept the dictates of our
best available scientific theory (and thus the results of probabilistic
proofs), it is not clear that mathematicians qua mathematicians are
similarly compelled.  After all, mathematics can be (and has been) carried
quite far without any appeal to the results of physical science.  Of
course, if mathematicians suspend judgment on the results of a
probabilistic proof (on these particular grounds), then they should
probably also suspend judgment on the computer proof of the four-color
theorem.  In that case as well, we have to appeal to scientific facts (for
instance, about how CPUs work) in order to draw a mathematical conclusion.

don fallis
Don Fallis
Assistant Professor
School of Information Resources & Library Science
University of Arizona

1515 East First Street
Tucson, AZ 85719

Voice: (520) 621-5223
Fax:   (520) 621-3279
Email: fallis at u.arizona.edu