FOM: Probabilistic proofs

[Don Fallis]

At 02:15 AM 9/22/98 +0100, Harvey Friedman wrote:
>1. What cases have occurred in the mathematical literature where an
>interesting mathematical result has first (and perhaps only) appeared
>documented by a probabilistic proof?

Unfortunately, I do not know of any cases of probabilistic proofs being
rejected (or accepted) by math journals.  However, I can cite a large
number of mathematicians who claim in print that probabilistic proofs (no
matter how high a degree of certainty they provide) are epistemically
inferior to conventional mathematical proofs.  Also, I have given papers on
probabilistic proofs at several math conferences; and I can assure you that
the general consensus of those audiences was that probabilistic proofs are
clearly inferior to conventional mathematical proofs - and this despite the
devastating nature of my arguments to the contrary.  

Of course, as soon as someone discovers a convincing probabilistic proof of
the Riemann hypothesis, it may be that mathematicians will rapidly change
their tune.  However, I doubt it.  (It would be interesting though to check
the literature and see if anyone flip-flopped on the issue of computer
proofs once a computer proof of the four-color theorem had been discovered.)

(By the way, the fact - if it is a fact - that probabilistic proofs are not
going to get published in mainstream math journals is just an indication
that mathematicians think that probabilistic proofs are epistemically
inferior to conventional mathematical proofs.  The important issue is not
whether or not probabilistic proofs get published.  The important issue is
whether or not probabilistic proofs ARE epistemically inferior to
conventional mathematical proofs.)

>2. In any case, consider such a mathematical result, interesting or not,
>that has appeared in a scientific or engineering Journal. E.g., that a big
>integer is prime. Won't it be the case that the documentation cited will be
>its probabilistic proof, generally identified in some clear way so that it
>is reproducible? Won't you never see "it has been proved that n is prime"?

This is probably correct.  Of course, it does not really shed any light on
the epistemic status of probabilistic proofs.  After all, scientists
(unlike mathematicians) have long since lowered their standards and
commonly accept inductive evidence for scientific claims.

>3. So I am suggesting that probabilistic proofs and normal proofs are
>clearly identified as such, and so the issue of whether probabilistic
>proofs are in fact proofs is somehow never joined?

There are a number of reasons why mathematicians might want to label
probabilistic proofs as probabilistic.  For one thing, this label gives
readers a quick idea of the structure of the proof (in the same way that
the labels "proof by induction" or "proof by reductio" do).  However, the
important question is whether or not labeling a proof as "probabilistic"
should indicate a certain epistemic inferiority.  (Cf. for some
mathematicians, labeling a proof as "constructive" not only describes the
structure of the proof, but it indicates a certain epistemic superiority.)

The question may be: is the distinguished
>status of normal proofs "beyond" or "higher" than that of probabilistic
>proofs?

Exactly.

>8. It is my own view that these probabilistic proofs have a certain kind of
>underlying rigor - "even if their actual implementation is imperfect." This
>phrase in quotes is a fancy way of saying, e.g., that we don't have perfect
>random number generators, and in fact don't even know - or cannot even
>define - what a perfect random number generator is. (Kolmogorov's
>definition is so strong that one knows that one cannot prove that any
>particular sequence is random). Or perhaps I am wrong - somebody does know
>what a perfect random number generator is? 

Rabin's test will give you the wrong answer if you are unlucky enough to
pick only non-witnesses in your search for witnesses to compositeness.
However, Rabin's test will very probably give you the right answer if you
are equally likely to pick any given sequence of numbers.  The question of
whether or not the sequence of numbers that you pick is random according to
Kolgomorov's definition of randomness (or according to some weaker
definition of randomness) is not really relevant.  After all, unless we
prove otherwise, a sequence of numbers that are all non-witnesses might
easily be Kolgomorov random.  So, in other words, the process of picking
the numbers (and not the sequence of numbers itself) has to be random.

>9. Thus there remains the question of "what is a "correct" or "valid"
>probabilistic proof?" Is that the real fruitful issue at the heart of this
>thread?

Determining the conditions under with something counts as a probabilistic
PROOF is certainly an interesting project.  However, I am interested in the
more general project of determining the conditions under which something
counts as a PROOF.  Investigating whether or not (any) probabilistic
methods measure up is just a handy technique for carrying out this project.

take care,
don

Don Fallis
School of Information Resources
University of Arizona